# Thread: Polynomial in integral coefficients

1. ## Polynomial in integral coefficients

Prove that there exists no polynomical $\displaystyle f(x)$ with integral coefficients such that $\displaystyle f(a)=b, \ f(b)=c, \ f(c)=a$ are satisfied for $\displaystyle a, b, c$ distinct integers

2. ## 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 $\displaystyle f(x)$ must be higher than quadratic.

For starters, these "chains" are not difficult to find. Here is a simple example: $\displaystyle f(x)=x^2-2$. $\displaystyle 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 $\displaystyle (a,b),(b,c),(c,a)$ are not collinear (I'll let the reader satisfy him/herself with an explanation for this), therefore $\displaystyle f(x)$ cannot be linear. It must have curvature, and therefore must be at least quadratic.

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

$\displaystyle \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 $\displaystyle u,v,w$. The following proves that u is never an integer:

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

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

So $\displaystyle u=\frac{(n-m)^2-mn}{mn(n-m)}$. Call $\displaystyle d=n-m, p=mn$ for "difference" and "product" respectively. $\displaystyle u=\frac{d^2+p}{dp}$. Rewriting, $\displaystyle p=\frac{d^2}{du-1}$. Since the denominator $\displaystyle D\equiv-1 (\bmod d)$, there is no possible way it can divide the numerator $\displaystyle 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 $\displaystyle 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.

3. 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!

4. 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

5. "Differential Calculus" by Shantinarayan and PK Mittal (S. Chand Publishers). It's an Indian book.

6. Spoiler:
Suppose that all of $\displaystyle a$, $\displaystyle b$, and $\displaystyle c$ are distinct. $\displaystyle F(a) -F(b) = b - c$, $\displaystyle F(b) - F(c) = c - a$, and $\displaystyle F(c) - F(a) = a - b$. Multiplying these all together yields $\displaystyle (F(a) - F(b))(F(b) - F(c))(F(c) - F(a)) = (b-c)(c-a)(a-b)$.

Rearrange to get $\displaystyle \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$ (possible since $\displaystyle a-b, b-c, c-a \ne 0)$. Since $\displaystyle f(x)$ is a polynomial with integer coefficients, $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}, \frac{F(b) - F(c)}{b - c}, \frac{F(c) - F(a)}{c-a} \in\mathbb{Z}$. Since their product is one, $\displaystyle \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 $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}$, $\displaystyle \displaystyle \frac{F(b) - F(c)}{b - c}$, and $\displaystyle \displaystyle \frac{F(c) - F(a)}{c-a}$ is -1 (without loss of generality, let us suppose that $\displaystyle \dfrac{F(a) - F(b)}{a-b} = -1)\right)$ then $\displaystyle F(a) - F(b) = b - a$. But $\displaystyle F(a) = b$ and $\displaystyle F(c) = c$, so $\displaystyle b - c = b - a$, yielding $\displaystyle a = c$, contradicting our assumption that all the variables were distinct.

It follows that each of $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}$, $\displaystyle \displaystyle \frac{F(b) - F(c)}{b - c}$, and $\displaystyle \displaystyle\frac{F(c) - F(a)}{c-a}$ is equal to 1, so we have $\displaystyle F(a) - F(b) = a - b$, $\displaystyle F(b) - F(c) = b - c$, and $\displaystyle F(c) - F(a) = c - a$. Substituting, $\displaystyle b - c = a - b$, $\displaystyle c-a = b - c$, and $\displaystyle a-b = c - a$. Rearrange to get $\displaystyle 2b = a + c$, $\displaystyle 2a = b + c$, and $\displaystyle 2c = a + b$. These equalities quickly yield $\displaystyle a=b=c$, which again contradicts our assumption that $\displaystyle a, b, c$ are distinct.

7. Thank you so much. This is a beautiful solution!

8. Originally Posted by Bourbaki
Spoiler:
Suppose that all of $\displaystyle a$, $\displaystyle b$, and $\displaystyle c$ are distinct. $\displaystyle F(a) -F(b) = b - c$, $\displaystyle F(b) - F(c) = c - a$, and $\displaystyle F(c) - F(a) = a - b$. Multiplying these all together yields $\displaystyle (F(a) - F(b))(F(b) - F(c))(F(c) - F(a)) = (b-c)(c-a)(a-b)$.

Rearrange to get $\displaystyle \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$ (possible since $\displaystyle a-b, b-c, c-a \ne 0)$. Since $\displaystyle f(x)$ is a polynomial with integer coefficients, $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}, \frac{F(b) - F(c)}{b - c}, \frac{F(c) - F(a)}{c-a} \in\mathbb{Z}$.

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 \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 $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}$, $\displaystyle \displaystyle \frac{F(b) - F(c)}{b - c}$, and $\displaystyle \displaystyle \frac{F(c) - F(a)}{c-a}$ is -1 (without loss of generality, let us suppose that $\displaystyle \dfrac{F(a) - F(b)}{a-b} = -1)\right)$ then $\displaystyle F(a) - F(b) = b - a$. But $\displaystyle F(a) = b$ and $\displaystyle F(c) = c$, so $\displaystyle b - c = b - a$, yielding $\displaystyle a = c$, contradicting our assumption that all the variables were distinct.

It follows that each of $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}$, $\displaystyle \displaystyle \frac{F(b) - F(c)}{b - c}$, and $\displaystyle \displaystyle\frac{F(c) - F(a)}{c-a}$ is equal to 1, so we have $\displaystyle F(a) - F(b) = a - b$, $\displaystyle F(b) - F(c) = b - c$, and $\displaystyle F(c) - F(a) = c - a$. Substituting, $\displaystyle b - c = a - b$, $\displaystyle c-a = b - c$, and $\displaystyle a-b = c - a$. Rearrange to get $\displaystyle 2b = a + c$, $\displaystyle 2a = b + c$, and $\displaystyle 2c = a + b$. These equalities quickly yield $\displaystyle a=b=c$, which again contradicts our assumption that $\displaystyle a, b, c$ are distinct. $\displaystyle \blacksquare$
.

9. Use the fact that $\displaystyle x^n - y^n$ is divisible by $\displaystyle x-y$ for any positive integer $\displaystyle n$ and integers $\displaystyle x, \ y$ and also use the fact that $\displaystyle F(x)$ is a polynomial with integral coefficients to prove that $\displaystyle \displaystyle \frac{F(a) - F(b)}{a-b}$ is an integer

10. 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