# Power values of polynomial

$$f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$$ is a polynomial of degree $$n$$ with positive integer coefficients.

Primary problem statement: Is the Exponential Diophantine Equation $$f(f(a) + 1) = y^m$$ solvable in integers $$y, m \geq 2, a$$?

Background: This problem arises in data encoding and representation for compression. Given $$n + 1$$ data values (think bytes with values ranging 0 to 255), we represent them as integer coefficients of $$f(x)$$. We require the data values to all be positive integers $$\ge 0$$. Under this condition, $$f(1)$$ is just the sum of the coefficients. Let $$b = f(1) + 1$$ and $$c = f(b)$$. Given just the values $$c$$ and $$b$$, we can recover the coefficients $$a_0, a_1, \dots, a_n$$ through repeated division of $$c$$ by $$b$$. i.e., the base-$$b$$ representation of $$c$$ has the coefficients of $$f(x)$$.

This base-$$b$$ representation and recovery works for any choice of $$b$$ that is greater than the height of the polynomial $$f(x)$$. $$f(a) + 1$$ is guaranteed to be greater than the height of the polynomial.

Alternate Problem Statement: Does the Exponential Diophantine Equation $$f(b) = y^m$$ have integer solutions $$b, y, m \geq 2$$, where $$b > \max(a_0, a_1, a_2, \dots, a_n)$$.

The compression arises from the fact that we are using perfect powers to encode a set of values. The hope is $$b, y, m$$ are small and require fewer bits to represent than the original data.

An acceptable answer may solve either the Primary Problem Statement or the Alternate Problem Statement.

Edits:

• $$GCD(a_0, a_1, \dots, a_n) = 1$$ can be considered as a condition

References:

Richmond, B. On a Perplexing Polynomial Puzzle.

• +1 Interesting problem - well articulated/presented. Personally, way out of my league. – user2661923 Sep 24 '20 at 15:10
• I assume you want $m\geq 2$? – QC_QAOA Sep 25 '20 at 19:27
• @QC_QADA: Yes. $m>=2$ desired. Good catch. – vvg Sep 25 '20 at 19:30
• You appear, since a is a constant, to be given information about y at a single point, a+ 1. That is not enough information to determine the function y for all x. – user247327 Sep 25 '20 at 20:13
• Please take a look at the linked article titled 'On a Perplexing Polynomial Puzzle'. It talks about how we can encode information about the coefficients of any polynomial and recover those coefficients with just two evaluations of the polynomial. For eg: $f(x) = 2x^2 + 3x + 1$. $f(1) = 2.1^2 + 3.1 + 1 = 2 + 3 + 1 = 6.$ $b = f(1) + 1 = 6 + 1 = 7$ $f(b) = 2.7^2 + 3.7 + 1 = 4802 + 21 + 1 = 4824$ The base-$b$ (i.e. base-7 representation of 4824 is exactly $2.7^2 + 3.7 + 1$, the coefficients of $f(x)$. – vvg Sep 25 '20 at 20:23

Consider the simplest case where $$f(x)=a_0+a_1x$$ and $$(a_0,a_1)=1$$. Then $$y^m=f(f(x)+1)=(a_0+a_1+a_0a_1)+a_1^2x$$ and write $$y=a_1^2n+k$$ for some integer $$k$$ such that $$(a_1,k)=1$$. We obtain $$k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$$ and choosing $$m=2$$ means that $$a_0+a_1+a_0a_1$$ is a quadratic residue of $$a_1^2$$. This means that $$\left(\frac{a_0+a_1+a_0a_1}{a_1^2}\right)=\left(\frac{a_1+1}{a_1^2}\right)\left(\frac{a_0+a_1}{a_1^2}\right)=1$$ using Legendre symbol notation. We can evaluate the first term as follows \left(\frac{a_1+1}{a_1^2}\right)=\begin{align}\begin{cases}1&\text{if}\,a_1\,\text{is odd or}\, \sqrt{a_1+1}\,\text{is an integer}\\-1&\text{otherwise}\end{cases}\end{align} by noting that $$(a_1^2-a_1-2)^2/4\equiv a_1+1\pmod{a_1^2}$$ when $$a_1$$ is odd.

In the first case, choosing $$a_0=a_1^2-3a_1+1$$ suffices for all $$a_1>3$$ as $$a_0+a_1$$ is a perfect square and $$(a_0,a_1)=1$$. This is enough to generate not one, but two infinite sets of solutions.

For this value of $$a_0$$, the congruence $$k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$$ reduces to $$k^2\equiv-a_1+1\pmod{a_1^2}\implies k=\frac{a_1^2\pm(a_1-2)}2$$ after removing higher-order terms.

As the "generating" function is $$f(x)=r^2-3r+1+r^2x$$ on replacing $$r:=a_1$$, substituting this back into $$y^2=f(f(x)+1)$$ yields the two families $$(x,y)=\left(r^2n^2+(r^2\pm(r-2))n+\frac{(r-1)^2}2\pm(r-2),r^2n+\frac{r^2\pm(r-2)}2\right)$$ for all positive integers $$n$$ and odd $$r\ge5$$.

One can obtain further solution sets by choosing $$a_0=a_1^2-(2c+1)a_1+c^2$$ for a positive integer $$c>1$$ provided that $$(a_0,a_1)=1$$ and then repeating the process above.

I have found a polynomial without any solutions. Let $$n=1$$ and

$$f(x)=2+4x$$

Then

$$f(f(r)+1)=2(7+8r)=y^m$$

This implies $$y$$ is even. But then $$y=2k$$ gives

$$2^m k^m=2(7+8r)$$

$$2^{m-1}k^m=7+8r$$

The left side is always even (since $$m\geq 2$$) while the right side is always odd. We conclude there is no $$y$$ and $$m\geq 2$$ which solves the exponential diophantine equation.

However, there is still a lot of interesting stuff that might be done with this problem. I think that in general, adding the condition that

$$\gcd(a_0,a_1,...,a_n)=1$$

might succeed in guaranteeing a solution. However, I have not proved this. For example, the same sort of problem arises when you consider the following polynomials

$$f(x)=2+2x+2x^2$$

$$f(x)=2+2x+2x^2+4x^3$$

$$f(x)=2+2x+2x^2+2x^3+2x^4$$

$$\vdots$$

• Interesting. So, there are potentially a class of polynomials where $GCD(a0, a1, .. an) \neq 1$ that are likely (not always) to fail generating perfect power values. So, we can always consider $f(x) = x.g(x) + c$ as the polynomial where $a_0, a_1, .. a_{n-1}$ are the coefficients of $g(x)$ and we force a constant $c$ that ensures $GCD(a0, a1, .., a_{n-1}, c) = 1$. I think adding the GCD condition is reasonable and if we can establish a solution can always be generated, we are making progress! – vvg Sep 25 '20 at 21:38