$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.
- $GCD(a_0, a_1, \dots, a_n) = 1$ can be considered as a condition
Richmond, B. On a Perplexing Polynomial Puzzle.