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