Polynomial in integral coefficients

Printable View

July 22nd 2010, 10:09 AM
sashikanth

Polynomial in integral coefficients

Prove that there exists no polynomical $f(x)$ with integral coefficients such that $f(a)=b, \ f(b)=c, \ f(c)=a$ are satisfied for $a, b, c$ distinct integers
July 23rd 2010, 01:06 PM
Media_Man

n>2

This problem has captivated me. At first glance, I thought it must be either false or simple. So far, neither seems to be correct. So far all I have managed to prove is the polynomial $f(x)$ must be higher than quadratic.

For starters, these "chains" are not difficult to find. Here is a simple example: $f(x)=x^2-2$ . $f(.3473)=-1.8794, f(-1.8794)=1.5321, f(1.5321)=.3473$ . Therefore I figured that the reason no integer "chain" can exist must be numerical, not analytical.

The three points $(a,b),(b,c),(c,a)$ are not collinear (I'll let the reader satisfy him/herself with an explanation for this), therefore $f(x)$ cannot be linear. It must have curvature, and therefore must be at least quadratic.

Let $f(x)=ux^2+vx+w$ and solve using the three sample points in the usual manner.

$ \begin{bmatrix} u \\ v \\ w \end{bmatrix} =\begin{bmatrix} a^2 & a & 1 \\ b^2 & b & 1 \\ c^2 & c & 1 \end{bmatrix}^{-1} \begin{bmatrix} b \\ c \\ a \end{bmatrix} $

Using a computer (actually Wolfram Alpha -- shameless plug), one can easily find $u,v,w$ . The following proves that u is never an integer:

According to Wolfram Alpha, $u=\frac{b(b-c)+c(c-a)+a(a-b)}{(a-b)(a-c)(b-c)}$

Substitute $m=a-b, n=a-c$ , so $b=a-m, c=a-n, b-c=n-m$

So $u=\frac{(n-m)^2-mn}{mn(n-m)}$ . Call $d=n-m, p=mn$ for "difference" and "product" respectively. $u=\frac{d^2+p}{dp}$ . Rewriting, $p=\frac{d^2}{du-1}$ . Since the denominator $D\equiv-1 (\bmod d)$ , there is no possible way it can divide the numerator $d^2$ . (Can someone verify this last point rigorously please?)

Since assuming all variables are integers ends in contradiction, one of them must be non-integral. The end result is that $f(x)$ must be at least cubic.

I seriously doubt this is the correct approach for this problem, but it is as much as I can contribute, so it may inspire someone else. I believe abstract algebra may hold the key.
July 23rd 2010, 09:07 PM
sashikanth

Hi media_man!

Thank you for your post. If it helps, this problem has been picked up from the "Functions" chapter of a 1st year college text book. So I'm reasoning that the solution would be analytic and not numerical. And it would most probably involve some concepts of functions and inverses along with number theory. This book particularly is not very challenging so I think there is a simple concept that I am missing out on. When I first saw it I thought it would be simple too. But I've been grappling with this for over two days to no avail! :(
July 23rd 2010, 11:13 PM
CaptainBlack

Quote:

Originally Posted by sashikanth

Hi media_man!

Thank you for your post. If it helps, this problem has been picked up from the "Functions" chapter of a 1st year college text book. So I'm reasoning that the solution would be analytic and not numerical. And it would most probably involve some concepts of functions and inverses along with number theory. This book particularly is not very challenging so I think there is a simple concept that I am missing out on. When I first saw it I thought it would be simple too. But I've been grappling with this for over two days to no avail! :(

Can you tell which textbook this is from?

CB
July 24th 2010, 12:06 AM
sashikanth

"Differential Calculus" by Shantinarayan and PK Mittal (S. Chand Publishers). It's an Indian book.
July 24th 2010, 01:10 AM
Bourbaki

Spoiler:

Suppose that all of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] are distinct. [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Multiplying these all together yields [LaTeX ERROR: Convert failed] .

Rearrange to get [LaTeX ERROR: Convert failed] (possible since [LaTeX ERROR: Convert failed] . Since [LaTeX ERROR: Convert failed] is a polynomial with integer coefficients, [LaTeX ERROR: Convert failed] . Since their product is one, $\displaystyle \left|\frac{F(a) - F(b)}{a-b}\right| = \left|\frac{F(b) - F(c)}{b - c}\right| = \left|\frac{F(c) - F(a)}{c-a}\right| = 1.$

If one of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] is -1 (without loss of generality, let us suppose that [LaTeX ERROR: Convert failed] then [LaTeX ERROR: Convert failed] . But [LaTeX ERROR: Convert failed] and [LaTeX ERROR: Convert failed] , so [LaTeX ERROR: Convert failed] , yielding [LaTeX ERROR: Convert failed] , contradicting our assumption that all the variables were distinct.

It follows that each of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] is equal to 1, so we have [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Substituting, [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Rearrange to get [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . These equalities quickly yield [LaTeX ERROR: Convert failed] , which again contradicts our assumption that [LaTeX ERROR: Convert failed] are distinct.
July 24th 2010, 01:45 AM
sashikanth

Thank you so much. This is a beautiful solution!
July 24th 2010, 01:45 AM
tonio

Quote:

Originally Posted by Bourbaki

Spoiler:

Suppose that all of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] are distinct. [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Multiplying these all together yields [LaTeX ERROR: Convert failed] .

Rearrange to get [LaTeX ERROR: Convert failed] (possible since [LaTeX ERROR: Convert failed] . Since [LaTeX ERROR: Convert failed] is a polynomial with integer coefficients, [LaTeX ERROR: Convert failed] .

There's my only doubt: why is this true? Couldn't it be, for example, that one of these quotients is one whereas the other two are rationals inverse to each other?

Tonio

Since their product is one, $\displaystyle \left|\frac{F(a) - F(b)}{a-b}\right| = \left|\frac{F(b) - F(c)}{b - c}\right| = \left|\frac{F(c) - F(a)}{c-a}\right| = 1.$

If one of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] is -1 (without loss of generality, let us suppose that [LaTeX ERROR: Convert failed] then [LaTeX ERROR: Convert failed] . But [LaTeX ERROR: Convert failed] and [LaTeX ERROR: Convert failed] , so [LaTeX ERROR: Convert failed] , yielding [LaTeX ERROR: Convert failed] , contradicting our assumption that all the variables were distinct.

It follows that each of [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] is equal to 1, so we have [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Substituting, [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . Rearrange to get [LaTeX ERROR: Convert failed] , [LaTeX ERROR: Convert failed] , and [LaTeX ERROR: Convert failed] . These equalities quickly yield [LaTeX ERROR: Convert failed] , which again contradicts our assumption that [LaTeX ERROR: Convert failed] are distinct. $\blacksquare$

.
July 24th 2010, 01:50 AM
sashikanth

Use the fact that $x^n - y^n$ is divisible by $x-y$ for any positive integer $n$ and integers $x, \ y$ and also use the fact that $F(x)$ is a polynomial with integral coefficients to prove that $\displaystyle \frac{F(a) - F(b)}{a-b}$ is an integer
July 24th 2010, 05:54 AM
Media_Man

Excellent proof, Bourbaki. As a continuation, this can also be extended to "chains" of not just three elements, but any arbitrary number. As another continuation, this proves that in any chain (removing the integer requirement), the product of all the elements is always plus or minus 1. Ex: (.347)(-1.879)(1.532)=-1