6
$\begingroup$

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

Shorey, T. N. Perfect powers in values of certain polynomials at integer points

$\endgroup$
6
  • $\begingroup$ +1 Interesting problem - well articulated/presented. Personally, way out of my league. $\endgroup$ Sep 24 '20 at 15:10
  • 1
    $\begingroup$ I assume you want $m\geq 2$? $\endgroup$
    – QC_QAOA
    Sep 25 '20 at 19:27
  • $\begingroup$ @QC_QADA: Yes. $m>=2$ desired. Good catch. $\endgroup$
    – vvg
    Sep 25 '20 at 19:30
  • $\begingroup$ 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. $\endgroup$
    – user247327
    Sep 25 '20 at 20:13
  • $\begingroup$ 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)$. $\endgroup$
    – vvg
    Sep 25 '20 at 20:23
4
+50
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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$$

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – vvg
    Sep 25 '20 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.