# Polynomial in integral coefficients

• Jul 22nd 2010, 11: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
• Jul 23rd 2010, 02: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.
• Jul 23rd 2010, 10: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! :(
• Jul 24th 2010, 12:13 AM
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
• Jul 24th 2010, 01:06 AM
sashikanth
"Differential Calculus" by Shantinarayan and PK Mittal (S. Chand Publishers). It's an Indian book.
• Jul 24th 2010, 02:10 AM
Bourbaki
Spoiler:
Suppose that all of [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] are distinct. [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] . Multiplying these all together yields [LaTeX ERROR: Compile failed] .

Rearrange to get [LaTeX ERROR: Compile failed] (possible since [LaTeX ERROR: Compile failed] . Since [LaTeX ERROR: Compile failed] is a polynomial with integer coefficients, [LaTeX ERROR: Compile 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: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] is -1 (without loss of generality, let us suppose that [LaTeX ERROR: Compile failed] then [LaTeX ERROR: Compile failed] . But [LaTeX ERROR: Compile failed] and [LaTeX ERROR: Compile failed] , so [LaTeX ERROR: Compile failed] , yielding [LaTeX ERROR: Compile failed] , contradicting our assumption that all the variables were distinct.

It follows that each of [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] is equal to 1, so we have [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] . Substituting, [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] . Rearrange to get [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] . These equalities quickly yield [LaTeX ERROR: Compile failed] , which again contradicts our assumption that [LaTeX ERROR: Compile failed] are distinct.
• Jul 24th 2010, 02:45 AM
sashikanth
Thank you so much. This is a beautiful solution!
• Jul 24th 2010, 02:45 AM
tonio
Quote:

Originally Posted by Bourbaki
Spoiler:
Suppose that all of [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] are distinct. [LaTeX ERROR: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] . Multiplying these all together yields [LaTeX ERROR: Compile failed] .

Rearrange to get [LaTeX ERROR: Compile failed] (possible since [LaTeX ERROR: Compile failed] . Since [LaTeX ERROR: Compile failed] is a polynomial with integer coefficients, [LaTeX ERROR: Compile 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: Compile failed] , [LaTeX ERROR: Compile failed] , and [LaTeX ERROR: Compile failed] is -1 (without loss of generality, let us suppose that [LaTeX ERROR: Compile failed] then [LaTeX ERROR: Compile failed] . But [LaTeX ERROR: Compile failed] and [LaTeX ERROR: Compile failed] , so [LaTeX ERROR: Compile failed] , yielding [LaTeX ERROR: Compile failed] , contradicting our assumption that all the variables were distinct.

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

.
• Jul 24th 2010, 02: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
• Jul 24th 2010, 06: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