# Lacunary Polynomial Compositions

A. Moscariello  Dipartimento di Matematica, Università di Pisa, Largo Bruno
Pontecorvo 5, 56127 Pisa, Italy<EMAIL_ADDRESS>
###### Abstract.

This work is a study of polynomial compositions having a fixed number of
terms. We outline a recursive method to describe these characterizations, give
some particular results and discuss the general case. In the final sections,
some applications to Universal Hilbert Sets generated by closed forms of
linear recurrence relations and to integer perfect powers having few digits in
their representation in a given scale $x\geq 2$ are provided.

A _lacunary polynomial_ (also called _sparse polynomial_) is a polynomial
where the number of terms is assumed fixed, with no control on the value of
the degrees and coefficients of said terms. For instance, we may write
$g(x)=a_{1}x^{l_{1}}+\dots+a_{k}x^{l_{k}}$ for a lacunary polynomial with at
most $k$ different terms, where $k$ is fixed and $a_{1},\ldots,a_{k}$ and
$l_{1},\ldots,l_{k}$ can be taken with no restriction. This assumption on the
number of terms of a polynomial is equivalent to a bound on the polynomial’s
complexity; for instance, a non-constant monomial only admits one root (that
is, zero), while the set of roots of a given polynomial having exactly two
terms has a very simple structure, since these roots can only differ by some
$n$th roots of unit.

This focus on the number of terms of a polynomial rather than the values of
these terms or their degree, naturally brings some open questions, regarding
in particular the behaviour of these polynomials under composition. For
instance, Erdős and Rényi independently conjectured (see [5], [11]) the
existence of a bound for the number of terms of the square of a given
polynomial having a fixed number $k$ of terms, depending only on $k$. Later,
this was proved by Schinzel (see [14]) in a more general setting, providing a
lower bound for the number of terms of a lacunary power $P(T)^{d}$, where
$P(T)$ is a lacunary polynomial. In the same work, he further conjectured that
a bound could be found for the number of terms of the polynomial composition
$f(g(x))$, depending on the number of terms of both polynomials involved.
Schinzel’s conjecture has then been proved by Zannier ([17]), developing
completely different methods from those used by Schinzel.

In this work, we will further extend this setting by studying lacunary
polynomials obtained as composition of a Laurent polynomial
$g(X_{1},\ldots,X_{\sigma})$ in $\sigma\geq 1$ indeterminates, with a classic
univariate polynomial $f(T)$. Our motivation stems from some applications of
this question in some arithmetic contexts; for this motive, after an overview
on this problem, we will focus on some special cases, according to our needs.
The general Question is the following:

######  Question 1.

Let $\sigma\geq 1$ and $\rho\geq 0$ be integers, let
$g(X_{1},\ldots,X_{\sigma})\in\mathbb{C}[X_{1}^{\pm 1},\ldots,X_{\sigma}^{\pm
1}]$ be a Laurent polynomial in the indeterminates $X_{1},\ldots,X_{\sigma}$,
and let $f(T)\in\mathbb{C}[T]$, which we can assume monic without loss of
generality.
Determine for which polynomials $f$ and $g$ the identity

(*)
$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\ldots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\ldots,X_{\sigma})+\ldots+a_{\sigma+\rho}T_{\rho}(X_{1},\ldots,X_{\sigma})$

holds, for $l_{1},\ldots,l_{\sigma}$ positive integers,
$a_{1},\ldots,a_{\sigma+\rho}\in\mathbb{C}$ and
$T_{1},\ldots,T_{\rho}\in\mathbb{C}[X_{1}^{\pm 1},\ldots,X_{\sigma}^{\pm 1}]$
monomials in $X_{1},\ldots,X_{\sigma}$.

Notice that, while this formulation may appear very specific at first sight,
it is actually quite generic. In order to see this, consider a polynomial
composition of the form

$f(g(X_{1},\ldots,X_{\sigma}))=a_{1}T_{1}(X_{1},\dots,X_{\sigma})+\ldots+a_{k}T_{k}(X_{1},\ldots,X_{\sigma}),$

where $T_{1},\ldots,T_{k}$ are monomials in $X_{1},\ldots,X_{\sigma}$. Among
those monomials, we can choose a set $\mathcal{M}$ of multiplicative
independent terms with maximal cardinality $\sigma$; now, choose a new set of
indeterminates $Y_{1},\ldots,Y_{\sigma}$ such that each element of
$\mathcal{M}$ becomes a power $Y_{i}^{l_{i}}$, where the exponents $l_{i}$ are
chosen so that all exponents of the original composition are still in
$\mathbb{Z}$. With this substitution, it is very easy to check that a generic
polynomial composition can be associated to an identity of the form (* ‣ 3).

We study some particular cases of this question, starting with lacunary
polynomial powers ($f(T)=T^{m}$, Section 1) and then, leveraging the results
obtained, we will investigate the general case, considering polynomial
compositions with few monomials $T_{i}(X_{1},\ldots,X_{\sigma})$ (solving the
cases $\rho\in{1,2}$, Section 3). This choice is motivated by an application
to a question concerning closed forms of linear recurrence relations and
Universal Hilbert Sets, which we will first describe in Section 2. Also, in
the Appendix, we provide a brief application of our results on lacunary
polynomial powers to perfect powers having few non-zero digits in their
representation in a fixed scale, coming from a work of Corvaja and Zannier
([2]).

##  1\. Polynomial powers with few terms

Consider a lacunary polynomial power $P(T)^{d}$ having exactly $k$ non-zero
terms; we can assume without loss of generality that the term of degree zero
is $1$, i.e.

$P(T)^{d}=1+\sum_{i=1}^{k-1}\xi_{i}T^{l_{i}}.$

The following remark will allow us to make some further assumptions in our
study.

######  Remark 2.

  1. (1)

If $P(T)^{d}=1+\displaystyle\sum_{i=1}^{k-1}\xi_{i}T^{l_{i}}$, take the
polynomial $Q(T)=\sqrt[d]{\frac{1}{\xi_{k-1}}T^{l_{k-1}}}P(T^{-1})$. Then
$Q(T)^{d}=1+\left(\displaystyle\sum_{i=1}^{k-2}\frac{\xi_{i}}{\xi_{k-1}}T^{l_{k-1}-l_{i}}\right)+\frac{1}{\xi_{k-1}}T^{l_{k-1}}$.
Rearranging the indices appearing in this equation in a way such that the
exponents of $Q(T)^{d}$ are in increasing order, we see that the
$\left\lceil\frac{k-1}{2}\right\rceil$th exponent of $Q(T)^{d}$ is
$l_{k-1}-l_{k-1-\lceil\frac{k-1}{2}\rceil}\geq
l_{k-1}-l_{\lceil\frac{k-1}{2}\rceil}$; thus, by swapping $P(T)$ with $Q(T)$,
we can first assume that $l_{\lceil\frac{k-1}{2}\rceil}\geq\frac{l_{k-1}}{2}$,
and then deduce the remaining cases using the relation between $P(T)$ and
$Q(T)$.

  2. (2)

Assume that $\displaystyle P(T)=1+\sum_{i=l_{1}}^{degP(T)}a_{i}T^{i}$ contains
at least one term whose degree is not a multiple of $l_{1}$, and let $r$ be
the smallest such degree. Then $P(T)^{d}$ has a term of degree $r$, that is,
$r\in\\{l_{2},\dots,l_{k-1}\\}$.

The first step of our study consists in limiting the value of $d$ in function
of the number of terms of the power $P(T)^{d}$; the next result can be deduced
from known Theorems of Zannier and Schinzel ([14], [15]); for the sake of
completeness, we include here an elementary proof.

######  Proposition 3.

Let $d\geq 2$ and $k\geq 2$ be integers, and let
$\xi_{1},\dots,\xi_{k-1}\in\mathbb{C}\setminus\\{0\\}$ and
$l_{1}<l_{2}<\dots<l_{k-1}$ be positive integers. Consider a polynomial
$P(T)\in\mathbb{C}[T]$ such that $\displaystyle
P(T)^{d}=1+\sum_{i=1}^{k-1}\xi_{i}T^{l_{i}}$. Then $d\leq k-1$, and moreover,
if $d=k-1$, then $P(T)=1+\frac{\xi_{1}}{d}T^{l_{1}}$.

###### Proof.

Clearly, all root multiplicities of $P(T)^{d}$ are divisible by $d$; take a
root $\alpha$ of $P(T)^{d}$, and let $\lambda d$ be its multiplicity. Then,
using the substitution $Q(T)=P(T)^{d}$, we have that all derivatives
$Q(\alpha)=\derivative[j]{Q}{T}(\alpha)$ vanish for every $j=1,\dots,\lambda
d-1$. On the other hand

$\derivative[j]{Q}{T}=\sum_{i=1}^{k-1}\xi_{i}l_{i}(l_{i}-1)\dots(l_{i}-j+1)T^{l_{i}-j}.$

Thus, the condition $\derivative[j]{Q}{T}(\alpha)=0$ for every
$j=1,\dots,\lambda d-1$ can be naturally translated in a system consisting of
$\lambda d-1$ equations; now, multiplying the $i$th equation by $T^{i}$
(remember that $P(0)\neq 0$) yields the equivalent system

$\begin{cases}\displaystyle\sum_{i=1}^{k-1}\xi_{i}l_{i}T^{l_{i}}=0,\\\
\displaystyle\sum_{i=1}^{k-1}\xi_{i}l_{i}(l_{i}-1)T^{l_{i}}=0,\\\ \dots\\\
\displaystyle\sum_{i=1}^{k-1}\xi_{i}l_{i}(l_{i}-1)\dots(l_{i}-\lambda
d+2)T^{l_{i}}=0.\end{cases}.$

At this stage, a solution of this system induces a solution of the associated
linear system over $\mathbb{C}^{k}$ in the indeterminates
$T^{l_{1}},\dots,T^{l_{k-1}}$, and the matrix associated to this linear system
can be easily reduced to a Vandermonde matrix, whose determinant is non-
vanishing: then, if $\lambda d>k-1$, this linear system admits only the
trivial solution $y_{1}=\dots=y_{k}=0$, which is not admissible since
$P(0)\neq 0$; therefore $d\leq k-1$.

Furthermore, arguing in the same way, if $d=k-1$ we have $\lambda=1$, hence
all roots of $Q(T)$ have multiplicity $d$ and all roots of $P(T)$ are simple.
Moreover, every solution of the linear system obtained from the vanishing
condition on derivatives has the form
$\mu(\alpha^{l_{1}},\dots,\alpha^{l_{k-1}})$, with $\mu\in\mathbb{C}$.
Consider a root $\beta$ of $P(T)$ distinct from $\alpha$, there exists
$\mu\in\mathbb{C}$ such that
$(\beta^{l_{1}},\dots,\beta^{l_{k-1}})=\mu(\alpha^{l_{1}},\dots,\alpha^{l_{k-1}})$.
Therefore, since $Q(\alpha)=0$, clearly $\displaystyle
1=-\sum_{i=1}^{k-1}\xi_{i}\alpha^{l_{i}}$, while on the other hand
$Q(\beta)=0$ yields $\displaystyle
0=1+\mu\left(\sum_{i=1}^{k-1}\xi_{i}\alpha^{l_{i}}\right)=1-\mu$, that is,
$\mu=1$. Then $\beta^{l_{i}}=\alpha^{l_{i}}$ for every $i=1,\dots,k-1$,
implying that there exists a $m$th root of unity $\zeta$ such that
$\beta=\zeta\alpha$, where $m$ is such that $m|l_{i}$ for every
$i=1,\dots,k-1$. Then we obtain that $P(T)$ has at most $l_{1}$ roots; thus,
since those roots are all simple, it easily follows that $m=l_{1}=\deg P(T)$.
The remaining claims follow immediately.∎

Another tool we need is a generalization of the _Vandermonde’s identity_ ;
remember that, for a real number $r\in\mathbb{R}$ that is not a negative
integer, and for $n\in\mathbb{N}$, the _binomial coefficient_ $\binom{r}{n}$
is defined as $\binom{r}{n}:=\frac{r(r-1)(r-2)\dots(r-n+1)}{n!}$, and is such
that the Binomial Theorem expansion
$\displaystyle(1+x)^{r}=1+\sum_{i=1}^{+\infty}\binom{r}{i}x^{i}$ holds. Then,
by expanding the right side of the identity
$(1+x)=(1+x)^{\frac{1}{d}}\dots(1+x)^{\frac{1}{d}}$, and noticing that all
terms of degree greater than 1 of the expansion must vanish, we obtain the
following lemma.

######  Lemma 4.

Let $d$ and $n$ be integers greater than $1$. Then

$\sum_{x_{1}+\dots+x_{d}=n}\binom{1/d}{x_{1}}\binom{1/d}{x_{2}}\dots\binom{1/d}{x_{d}}=0.$

Leveraging these preliminary results, we can prove the main result of this
Section, that is, a characterization for complex polynomials
$P(T)\in\mathbb{C}[T]$ having at most five terms.

######  Proposition 5.

Let $d\geq 2$ and $k\leq 5$ be positive integers, and let
$\xi_{1},\dots,\xi_{k-1}\in\mathbb{C}\setminus\\{0\\}$ and
$l_{1}<l_{2}<\dots<l_{k-1}$ be positive integers. Assume that
$P(T)\in\mathbb{C}[T]$ is a complex polynomial such that $\displaystyle
P(T)^{d}=1+\sum_{i=1}^{k-1}\xi_{i}T^{l_{i}}$. Then the following tables
describe the admissible values for coefficients and exponents of $P(T)$ and
$P(T)^{d}$.

  1. (1)

If $k=5$:

$d$ | $l_{2}$ | $l_{3}$ | $l_{4}$ | $\xi_{2}$ | $\xi_{3}$ | $\xi_{4}$ | $P(T)$
---|---|---|---|---|---|---|---
$4$ | $2l_{1}$ | $3l_{1}$ | $4l_{1}$ | $\frac{3}{8}\xi_{1}^{2}$ | $\frac{1}{16}\xi_{1}^{3}$ | $\frac{1}{256}\xi_{1}^{3}$ | $1+\frac{1}{4}\xi_{1}T^{l_{1}}$
$3$ | $3l_{1}$ | $5l_{1}$ | $6l_{1}$ | $-\frac{5}{27}\xi_{1}^{3}$ | $\frac{1}{81}\xi_{1}^{5}$ | $-\frac{1}{729}\xi_{1}^{6}$ | $1+\frac{1}{3}\xi_{1}T^{l_{1}}-\frac{1}{9}\xi_{1}^{2}T^{2l_{1}}$
$2$ | $4l_{1}$ | $5l_{1}$ | $6l_{1}$ | $\frac{5}{64}\xi_{1}^{4}$ | $-\frac{1}{64}\xi_{1}^{5}$ | $\frac{1}{256}\xi_{1}^{6}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{16}\xi_{1}^{3}T^{3l_{1}}$
$2$ | $3l_{1}$ | $5l_{1}$ | $6l_{1}$ | $-\frac{5}{32}\xi_{1}^{4}$ | $\frac{1}{256}\xi_{1}^{5}$ | $\frac{19}{1024}\xi_{1}^{6}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}-\frac{1}{64}\xi_{1}^{3}T^{3l_{1}}$
$2$ | $4l_{1}$ | $7l_{1}$ | $8l_{1}$ | $\frac{7}{64}\xi_{1}^{4}$ | $-\frac{1}{512}\xi_{1}^{7}$ | $\frac{1}{4096}\xi_{1}^{8}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{16}\xi_{1}^{3}T^{3l_{1}}+\frac{1}{64}\xi_{1}^{4}T^{4l_{1}}$
$2$ | $2l_{1}$ | $5l_{1}$ | $6l_{1}$ | $\frac{5}{4}\xi_{1}^{2}$ | $-\frac{1}{4}\xi_{1}^{5}$ | $\frac{1}{16}\xi_{1}^{6}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}+\frac{1}{2}\xi_{1}^{2}T^{2l_{1}}-\frac{1}{4}\xi_{1}^{3}T^{3l_{1}}$

Table 1.

$d$ | $l_{2}$ | $l_{3}$ | $l_{4}$ | $\xi_{2}$ | $\xi_{3}$ | $\xi_{4}$ | $P(T)$
---|---|---|---|---|---|---|---
$2$ | $2l_{1}$ | $3l_{1}$ | $4l_{1}$ |  | $-\frac{1}{8}\xi_{1}^{3}+\frac{1}{2}\xi_{1}\xi_{2}$ | $\left(-\frac{1}{8}\xi_{1}^{2}+\frac{1}{2}\xi_{2}\right)^{2}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}+\left(\frac{1}{2}\xi_{2}-\frac{1}{8}\xi_{1}^{2}\right)T^{2l_{1}}$

Table 2.

  2. (2)

If $k=4$:

$d$ | $l_{2}$ | $l_{3}$ | $\xi_{2}$ | $\xi_{3}$ | $P(T)$
---|---|---|---|---|---
$2$ | $3l_{1}$ | $4l_{1}$ | $-\frac{1}{8}\xi_{1}^{3}$ | $-\frac{1}{64}\xi_{1}^{4}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}$
$3$ | $2l_{1}$ | $3l_{1}$ | $\frac{1}{3}\xi_{1}^{2}$ | $\frac{1}{27}\xi_{1}^{3}$ | $1+\frac{1}{3}\xi_{1}T^{l_{1}}$

Table 3.

  3. (3)

If $k=3$:

$d$ | $l_{2}$ | $\xi_{2}$ | $P(T)$
---|---|---|---
$2$ | $2l_{1}$ | $\frac{1}{4}\xi_{1}^{2}$ | $1+\frac{1}{2}\xi_{1}T^{l_{1}}$

Table 4.

###### Proof.

The last two items are a reformulation of ([2, Lemma 2.1]).

Take $k=5$; by Proposition 3 we have $d\leq 4$. Hence we have to study the
three cases $d=2,3,4$; in each case, we will focus on determining $P(T)$; the
parameters will then follow by expanding the power $P(T)^{d}$. Moreover,
thanks to Remark 2, we can assume that $l_{2}\geq\frac{l_{4}}{2}$ first, and
then deduce the remaining solutions.
$d=4$. By Proposition 3 we immediately obtain
$P(T)=1+\frac{1}{4}\xi_{1}T^{l_{1}}$.
$d=3$. Since $\deg P(T)=\frac{l_{4}}{3}<\frac{l_{4}}{2}\leq l_{2}$, from the
second part of Remark 2 it follows that there exist $m\geq 1$ positive
integers $1=\sigma_{1}<\sigma_{2}<\dots<\sigma_{m}$ and
$\alpha_{1},\dots,\alpha_{m}\in\mathbb{C}\setminus\\{0\\}$ such that
$\displaystyle P(T)=1+\sum_{i=1}^{m}\alpha_{i}T^{\sigma_{i}l_{1}}$. Meanwhile,
taking
$\rho(T)=\xi_{1}+\xi_{2}T^{l_{2}-l_{1}}+\xi_{3}T^{l_{3}-l_{1}}+\xi_{4}T^{l_{4}-l_{1}}$
and comparing the terms of degree $\sigma_{i}l_{1}$ of $P(T)$ with those of
the binomial expansion

$(1+T^{l_{1}}\rho(T))^{\frac{1}{3}}=1+\sum_{i=1}^{+\infty}\binom{1/3}{i}T^{il_{1}}\rho(T)^{i}$

we have $\alpha_{i}=\binom{1/3}{\sigma_{i}}\xi_{1}^{\sigma_{i}}$.

Let $r$ be the smallest positive integer such that $P(T)$ has no term of
degree $rl_{1}$ (clearly $rl_{1}\leq\frac{l_{4}}{3}+l_{1}$). From the
minimality of $r$ we can deduce that the coefficient of degree $rl_{1}$ of
$P(T)^{3}$ is equal to
$\displaystyle\left[\left(\sum_{p,q,s\in\mathbb{N}}^{p+q+s=r}\binom{1/3}{p}\binom{1/3}{q}\binom{1/3}{s}\right)-3\binom{1/3}{r}\right]\xi_{1}^{r}$,
which is non-zero by Lemma 4; therefore $rl_{1}\geq l_{2}\geq\frac{l_{4}}{2}$,
which implies $\frac{l_{4}}{2}\leq\frac{l_{4}}{3}+l_{1}$ and $l_{4}\leq
6l_{1}$. Hence $\deg P(T)\leq 2l_{1}$, and since $P(T)$ must contain at least
three different terms (since otherwise $P(T)^{3}$ would have at most four
terms), then
$P(T)=1+\frac{1}{3}\xi_{1}T^{l_{1}}-\frac{1}{9}\xi_{1}^{2}T^{2l_{1}}$.
$d=2$. We have $\deg P(T)=\frac{l_{4}}{2}\leq l_{2}$; let us distinguish two
cases.

  * •

$l_{2}>\deg P(T)$. Arguing as in the case $d=3$, we can infer that
$\displaystyle P(T)=1+\sum_{i=1}^{m}\alpha_{i}T^{\sigma_{i}l_{1}}$, with
$\alpha_{i}=\binom{1/2}{\sigma_{i}}\xi_{1}^{\sigma_{i}}$; actually
$l_{1}|(l_{2},l_{3},l_{4})$ and $l_{1}|\frac{l_{4}}{2}$, and moreover, since
$P(T)$ has at least three terms whose degree is lower than $l_{2}$, we must
have $l_{2}\geq 3l_{1}$ and $l_{4}\geq 6l_{1}$.

Now, let $r$ be the smallest positive integer such that $P(T)$ has no term of
degree $rl_{1}$; then, as before, we easily obtain that $rl_{1}\geq
l_{2}>\frac{l_{4}}{2}$. Therefore $m=\frac{l_{4}}{2l_{1}}\geq 3$ and
$\displaystyle P(T)=1+\sum_{i=1}^{m}\alpha_{i}T^{il_{i}}$, with
$\alpha_{i}=\binom{1/2}{i}\xi_{1}^{i}$.

In this setting, $P(T)^{2}$ has terms of degree $0,l_{1},l_{4},l_{4}-l_{1}$.
Moreover, the term of degree $\frac{l_{4}}{2}+l_{1}$ of $P(T)^{2}$ is equal to

$\displaystyle\left[\left(\sum_{i\in\mathbb{N}}^{m+1}\binom{1/2}{i}\binom{1/2}{m+1-i}\right)-2\binom{1/2}{m+1}\right]\xi_{1}^{m+1},$

which is non-zero by Lemma 4, and the term of degree $l_{4}-2l_{1}$ of
$P(T)^{2}$ is

$\displaystyle\left(2\binom{1/2}{m}\binom{1/2}{m-2}+\binom{1/2}{m-1}^{2}\right)\xi_{1}^{2m-2},$

which is again non-zero because $\binom{1/2}{m}$ and $\binom{1/2}{m-2}$ have
the same sign (notice that $m\geq 3$).

Hence, two integers belonging to the set
$\\{0,l_{1},\frac{l_{4}}{2}+l_{1},l_{4}-2l_{1},l_{4}-l_{1},l_{4}\\}$ must
coincide; it is simple to show that the only possible equality is
$\frac{l_{4}}{2}+l_{1}=l_{4}-2l_{1}$, which yields $l_{4}=6l_{1}$, $m=3$ and
$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{16}\xi_{1}^{3}T^{3l_{1}}$.

  * •

$l_{2}=\deg P(T)$. Again, following the proof of the case $d=3$, we can deduce
that $P(T)$ is a finite subsum of the infinite sum $\displaystyle
1+\left(\sum_{i=1}^{+\infty}\alpha_{i}T^{il_{1}}\right)+\frac{1}{2}\xi_{2}T^{l_{2}}$,
with $\alpha_{i}=\binom{1/2}{i}\xi_{1}^{i}$.

First, assume that $l_{1}$ is not a divisor of $l_{2}$. Then, if
$\sigma_{m}l_{1}$ is the greatest degree multiple of $l_{1}$ among the terms
of $P(T)$, $P(T)^{2}$ must have terms of degree
$2l_{2},l_{2}+\sigma_{m}l_{1},2\sigma_{m}l_{1},l_{2},l_{1},0$ (which are all
pairwise distinct), contradicting our hypotheses. Then $l_{1}|l_{2}$.

Next, consider the smallest positive integer $r$ such that $P(T)$ has no term
of degree $rl_{1}$: arguing as above, we can easily obtain that $rl_{1}\geq
l_{2}$. Moreover, since $\deg P(T)=l_{2}$, by studying the term of degree
$l_{2}$ of the expansion of $P(T)^{2}$ we obtain

$\displaystyle
P(T)=1+\left(\sum_{i=1}^{m}\alpha_{i}T^{il_{1}}\right)+\frac{1}{2}\xi_{2}T^{l_{2}},\
\ m=\frac{l_{4}}{2l_{1}},\ \ \alpha_{i}=\binom{1/2}{i}\xi_{1}^{i}.$

Therefore, it is straightforward to see that $P(T)^{2}$ has non-zero terms of
degrees $0,l_{1},l_{2},2l_{2}-l_{1},2l_{2}$ (which are all pairwise distinct):
thus, these must be the only terms of $P(T)^{2}$.

At this point, we will reach a contradiction by considering the terms of
degree $l_{2}+l_{1}$ and $2l_{2}-2l_{1}$ obtained expanding the square
$P(T)^{2}$. In fact:

    * –

The coefficient of the term of degree $l_{2}+l_{1}$ is equal to
$-2\binom{1/2}{m+1}\xi_{1}^{m+1}+\frac{1}{2}\xi_{1}\xi_{2}$, according to
Lemma 4.

    * –

The coefficient of the term of degree $2l_{2}-2l_{1}$ is

$\left[2\binom{1/2}{m}\binom{1/2}{m-2}+\binom{1/2}{m-1}^{2}\right]\xi_{1}^{2m+2}+\binom{1/2}{m-2}\xi_{1}^{m-2}\xi_{2}.$

Clearly, if one of those coefficients is non-zero, the associated degree must
be among the ones listed before. Thus we have two possible cases:

    1. (1)

If at least one of those coefficients is non-zero, then the associated degree
must belong to $\\{0,l_{1},l_{2},2l_{2}-l_{1},2l_{2}\\}$. It is trivial to
check that if the associated degree is $l_{1}+l_{2}$, we must have
$l_{1}+l_{2}=2l_{2}-l_{1}$, while if this degree is $2l_{2}-2l_{1}$ then we
must have $2l_{2}-2l_{1}=l_{2}$; in both cases we deduce from the equality
that $l_{2}=2l_{1}$, that is,
$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}+\left(\frac{1}{2}\xi_{2}-\frac{1}{8}\xi_{1}^{2}\right)T^{2l_{1}}.$

    2. (2)

If both coefficients are non-zero, we can solve for $\xi_{2}$ in one of the
two equations, and then, substituting in the other one, we obtain
$\displaystyle\xi_{2}=4\binom{1/2}{m+1}\xi_{1}^{ml_{1}}$ and

$4\binom{1/2}{m+1}=-2\binom{1/2}{m}-\binom{1/2}{m-1}\frac{\frac{1}{2}-m+2}{m-1},$

or equivalently, that

$\frac{4\left(\frac{1}{2}-m+1\right)\left(\frac{1}{2}-m\right)}{m(m+1)}=-\frac{2\left(\frac{1}{2}-m+1\right)}{m}-\frac{\frac{1}{2}-m+2}{m-1}.$

This is a cubic equation in $m$, whose roots are $\frac{1}{2},3,4$. Then, in
this case we have the two solutions:

       * –

$m=3$, $\xi_{2}=4\binom{1/2}{4}\xi_{1}^{3l_{1}}$ and
$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}-\frac{1}{64}\xi_{1}^{3}T^{3l_{1}}$.

       * –

$m=4$, $\xi_{2}=4\binom{1/2}{5}\xi_{1}^{4l_{1}}$
$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}-\frac{1}{8}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{16}\xi_{1}^{3}T^{3l_{1}}+\frac{1}{64}\xi_{1}^{4}T^{4l_{1}}$.

The previous cases describe all polynomials $P(T)$ whose power has five terms,
and such that $l_{2}\geq\frac{l_{4}}{2}$; then, we only have to study the case
$l_{2}<\frac{l_{4}}{2}$. For that purpose, thanks to Remark 2 we know that
there is a polynomial $Q(T)$, associated to $P(T)$ and such that
$Q(T)^{d}=1+\xi_{1}^{\prime}T^{l_{1}^{\prime}}+\xi_{2}^{\prime}T^{l_{2}^{\prime}}+\xi_{3}^{\prime}T^{l_{3}^{\prime}}+\xi_{4}^{\prime}T^{l_{4}^{\prime}}$,
with $l_{2}^{\prime}>\frac{l_{4}^{\prime}}{2}$. Therefore, $Q(T)$ must be one
of the solutions obtained in the previous cases; however, there is only one
solution satisfying $l_{2}^{\prime}>\frac{l_{4}^{\prime}}{2}$, that is,
$Q(T)=1+\frac{1}{2}\xi_{1}^{\prime}T^{l_{1}^{\prime}}-\frac{1}{8}\xi_{1}^{\prime
2}T^{2l_{1}^{\prime}}+\frac{1}{16}\xi_{1}^{\prime 3}T^{3l_{1}^{\prime}}$,
which yields
$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}+\frac{1}{2}\xi_{1}^{2}T^{2l_{1}}-\frac{1}{4}\xi_{1}^{3}T^{3l_{1}}$,
thus concluding our proof. ∎

##  2\. An application: Closed forms of linear recursions and Universal
Hilbert Sets

Let $A\subseteq\mathbb{C}$ be a ring; denote by $\mathcal{E}_{A}$ the ring of
complex functions defined over $\mathbb{N}$ of the form
$\displaystyle\alpha(n)=\sum_{i=1}^{k}c_{i}\alpha_{i}^{n}$, with $k\geq 2$,
$c_{1},\dots,c_{k}\in\mathbb{Q}$ and $\alpha_{1},\dots,\alpha_{k}\in A$. In
this work, $A$ will usually be either $\mathbb{Z}$ or $\mathbb{Q}$; in these
cases, we further denote by $\mathcal{E}_{A}^{+}$ the subring formed by
functions having only positive roots $a_{i}$. These functions are closed forms
for linear recurrence relations of order $k$ having only simple roots; the
behaviour of these functions under composition and exponentiation is the main
subject of several papers (see [4, 6, 16]). Our interest in this topic stems
from the characterization presented in [4], which in turn was motivated by a
question posed by Yasumoto in [16], asking whether the set $\\{2^{n}+3^{n}\\}$
is a _Universal Hilbert Set_ , that is, a set $H$ such that for every
polynomial $P(X,Y)\in\mathbb{Q}[X,Y]$ irreducible over $\mathbb{Q}$, the
specialized polynomial $P(h,Y)\in\mathbb{Q}[Y]$ is irreducible for every $h\in
H$, except at most for a finite set of values.

Our work is based on the following characterization proved by Corvaja and
Zannier.

######  Theorem 6 ([4, Theorem 4]).

For $\alpha\in\mathcal{E}_{\mathbb{Z}}^{+}$, the following conditions are
equivalent:

  1. (i)

$\alpha(\mathbb{N})$ is a Universal Hilbert Set;

  2. (ii)

there exist no integer $d\geq 2$, a polynomial $P(X)\in\mathbb{Q}[X]$ of
degree $d$ and an element $\beta\in\mathcal{E}_{\mathbb{Z}}$ such that
$\alpha^{\prime}=P(\beta)$, where $\alpha^{\prime}(n)=\alpha(dn)$.

This result allowed the authors to prove a generalization of Yasumoto’s
question.

######  Corollary 7 ([4, Corollary 3]).

Let
$\displaystyle\alpha(n)=\sum_{i=1}^{k}c_{i}\alpha_{i}^{n}\in\mathcal{E}_{\mathbb{Z}}^{+}$
be such that $\alpha_{1},\dots,\alpha_{n}\in\mathbb{Z}^{+}$ are
multiplicatively independent. Then the set $\alpha(\mathbb{N})$ is a Universal
Hilbert Set.

Write
$\alpha(n)=\sum_{i=1}^{k}c_{i}\alpha_{i}^{n}\in\mathcal{E}_{\mathbb{Z}}^{+}$,
and assume that $\alpha(\mathbb{N})$ is not a Universal Hilbert Set.
Therefore, by the previous result there must exist a polynomial
$P(T)\in\mathbb{Q}[T]$ of degree $d$ and
$\beta(n)=\sum_{j=1}^{j}f_{j}\beta_{j}^{n}\in\mathcal{E}_{\mathbb{Z}}$ such
that $\alpha^{\prime}=P(\beta)$, where $\alpha^{\prime}(n)=\alpha(dn)$, thus
obtaining an identity of the form

(1)
$P(\beta)=\sum_{i=1}^{k}c_{i}\alpha_{i}^{dn}=\sum_{i=1}^{k}c_{i}(\alpha_{i}^{d})^{n}.$

We can choose among the integers $\beta_{1},\ldots,\beta_{h}$ a subset of
multiplicatively independent integers with maximal cardinality $\sigma\geq 1$,
which we can rename for simplicity $\\{\beta_{1},\ldots,\beta_{\sigma}\\}$.
Then, the maximality condition guarantees that if we add another element
$\beta_{\sigma+1}$ to this subset, the elements of the new set will not be
multiplicatively independent, and must therefore satisfy a relation of the
form $\displaystyle\prod_{i=1}^{\sigma+1}\beta_{i}^{m_{i}}=1$ for some
suitable integers $m_{1},\ldots,m_{\sigma+1}\in\mathbb{Z}$; repeating these
steps for all other elements $\alpha_{\sigma+1},\ldots,\alpha_{k}$ we obtain a
set of equations of the form

(2)
$\beta_{i}^{m_{ii}}=\beta_{1}^{m_{i1}}\beta_{2}^{m_{i2}}\dots\beta_{\sigma}^{m_{i\sigma}}$

for $i=\sigma+1,\dots,h$, and $m_{i1},\dots,m_{i\sigma},m_{ii}\in\mathbb{Z}$.

On the other hand, from identity (1), we obtain that each element of the form
$\alpha_{i}^{d}$ must be a term of the expansion of $P(\beta)$, and can be
thus expressed as a monomial in $\beta_{1},\dots,\beta_{h}$, which, in light
of (2), is actually a monomial in $\beta_{1},\dots,\beta_{\sigma}$, yielding
something of the form

(3)
$\alpha_{i}^{d}=\beta_{1}^{v_{i1}}\beta_{2}^{v_{i2}}\dots\beta_{\sigma}^{v_{i\sigma}},$

for $i=1,\ldots,k,$ and $v_{i1},\dots,v_{i\sigma}\in\mathbb{Q}$.

Our aim is to turn identity (1) in a polynomial identity; we achieve this by
sending the term associated to each element of our subset
$\\{\beta_{1},\dots,\beta_{\sigma}\\}$ to a power $(\beta_{j})^{n}\mapsto
Y_{j}^{r_{j}}$. Hence, we can deduce from (2) and (3) the image
$(\beta_{i})^{m_{ii}}\mapsto T_{i}(Y_{1},\dots,Y_{\sigma})$, and that there
exists $M\in\mathbb{Z}^{+}$ such that $(\alpha_{i}^{d})^{M}$ has integer
exponents in the terms of equation (3), and hence
$[(\alpha_{i}^{d})^{M}]^{n}\mapsto R_{i}(Y_{1},\dots,Y_{\sigma})$ (notice that
the exponents of the monomials $T_{i}$ and $R_{i}$ might be negative). Next,
we choose integers $r_{j}$ such that we can pick monomials
$\tilde{T}_{i}(Y_{1},\dots,Y_{\sigma})$ and
$\tilde{R}_{i}(Y_{1},\dots,Y_{\sigma})$ satisfying
$\tilde{T}_{i}(Y_{1},\dots,Y_{\sigma})^{m_{ii}}=T_{i}(Y_{1},\dots,Y_{\sigma})$
and $\tilde{R}_{i}(Y_{1},\dots,Y_{\sigma})^{M}=R_{i}(Y_{1},\dots,Y_{\sigma})$,
thus obtaining $(\beta_{i})^{n}\mapsto\tilde{T}_{i}(Y_{1},\dots,Y_{\sigma})$
and $(\alpha_{i}^{d})^{n}\mapsto\tilde{R}_{i}(Y_{1},\dots,Y_{\sigma})$.

Using this map, $\beta(n)$ becomes a certain polynomial
$G(Y_{1},\dots,Y_{\sigma})$, while identity (1) yields a polynomial
composition

$P(G(Y_{1},\dots,Y_{\sigma}))=\sum_{i=1}^{k}c_{i}\tilde{R}_{i}(Y_{1},\dots,Y_{\sigma}).$

Clearly, we can choose a set $\mathcal{M}$ of multiplicative independent
monomials with maximal cardinality $\sigma$, and map these monomials to a set
of indeterminates $Y_{1},\ldots,Y_{\sigma}$ such that each element of
$\mathcal{M}$ becomes a power $Y_{i}^{l_{i}}$, where the exponents $l_{i}$ are
chosen so that all exponents of our composition are still in $\mathbb{Z}$.
With this change of variables, we can easily see that this problem actually
asks for solutions of our main question.

Let $k=\sigma+\rho$ be the number of terms of the composition
$f(g(X_{1},\dots,X_{\sigma}))$. In the context given by Question 1, Corollary
7 deals with the case $\rho=0$; thus, in order to extend their result, we have
to study Question 1 for fixed (small) values of $\rho$.

Also, it is worth noticing that all invariants related to our study are
dependent only on the cardinality $\sigma$ of the set of multiplicatively
independent elements chosen, and are not dependent on the elements we choose;
thus, in some steps, we can pick a suitable set (with the same cardinality) of
elements without losing information. Therefore in our results we will only
list a subset of solutions such that any other solution can be obtained with
an appropriate change of variables (dictated by the set of multiplicatively
independent elements used).

##  3\. Small values of $\rho$

Here, we will investigate the equation

(*)
$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\ldots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\ldots,X_{\sigma})+\ldots+a_{\sigma+\rho}T_{\rho}(X_{1},\ldots,X_{\sigma}).$

for small values of $\rho$.

######  Remark 8.

The only solution of equation $(*)$ for $\rho=0$ is $\sigma=1$, $f(T)=T^{s}$,
$g(X_{1})=cX_{1}^{a}$, since a solution with $\rho=0$ and $\sigma>1$ would
produce a counterexample to Corollary 7.

Take a polynomial composition $f(g(X_{1},\dots,X_{\sigma}))$ with at least
$\sigma+1$ terms (i.e. $\rho\geq 1$). This composition must include some
monomials $T(X_{1},\dots,X_{\sigma})$; we focus on the case where there are
few such monomials.

Our approach is recursive; namely, starting from the equation

(*)
$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+\dots+a_{\sigma+\rho}T_{\rho}(X_{1},\dots,X_{\sigma})$

for a fixed value of $\rho$, we look for a specialization for one variable,
say, $X_{\sigma}$, as a function of the others, such that equation $(*)$ is
reduced to the equation

(**)
$f(\tilde{g}(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma^{\prime}}X_{\sigma^{\prime}}^{l_{\sigma^{\prime}}}+a_{{\sigma^{\prime}}+1}T_{1}(X_{1},\dots,X_{\sigma^{\prime}})+\dots+a_{{\sigma^{\prime}}+{\rho^{\prime}}}T_{\rho^{\prime}}(X_{1},\dots,X_{\sigma^{\prime}})$

where both parameters $\sigma^{\prime}$ and $\rho^{\prime}$ are strictly lower
than $\sigma$ and $\rho$. Thus, assuming that equation $(**)$ has already been
solved for all values of $\rho^{\prime}$ up to $\rho-1$, we can deduce from
that solution the polynomials $f(T)$ and
$\tilde{g}(X_{1},\dots,X_{\sigma^{\prime}})$, and deduce the value of $\sigma$
from $\sigma^{\prime}$, $\rho^{\prime}$ and our specialization; after that,
from these information we try to deduce the inner polynomial
$g(X_{1},\dots,X_{\sigma})$, solving our equation.

We use this approach to deal with the cases $\rho=1,2$.

######  Proposition 9.

Let $\sigma\geq 1$ be an integer, and let
$g(X_{1},\dots,X_{\sigma})\in\mathbb{C}[X_{1}^{\pm 1},\dots,X_{\sigma}^{\pm
1}]$ be a Laurent polynomial in the indeterminates $X_{1},\dots,X_{\sigma}$,
and $f(T)\in\mathbb{C}[T]$ is such that

$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma}),$

with $l_{1},\dots,l_{\sigma}$ positive integers,
$a_{1},\dots,a_{\sigma+1}\in\mathbb{C}$ and $T_{1}\in\mathbb{C}[X_{1}^{\pm
1},\dots,X_{\sigma}^{\pm 1}]$ monomial in $X_{1},\dots,X_{\sigma}$.

Then, up to a suitable change of variables, we have one of the following:

  1. (1)

$\sigma=1$, $f(T)=T^{m_{1}}+cT^{m_{2}}$, $g(X_{1})=\sqrt[S]{a_{1}}X_{1}^{r}$,
with $m_{1}r=l_{1}$, $m_{2}r=l_{2}$, $c=a_{2}a_{1}^{-\frac{m_{2}}{m_{1}}}$.

  2. (2)

$\sigma=2$, $f(T)=T^{2}$,
$g(X_{1},X_{2})=\sqrt{a_{1}}X_{1}^{\frac{l_{1}}{2}}+\sqrt{a_{2}}X_{2}^{\frac{l_{2}}{2}}$.

###### Proof.

First, assume that $\sigma=1$, that is,
$f(g(X_{1}))=a_{1}X_{1}^{l_{1}}+a_{2}X_{1}^{l_{2}}$. Let $D_{1},D_{2},d_{1}$
be respectively, the maximum, second maximum and minimum degree of $g$;
similarly, let $m_{1}$ and $m_{2}$ be, respectively, the maximum and minimum
degree of $f$ (hence $D_{1}\geq D_{2}\geq d_{1}$ and $m_{1}\geq m_{2}$). We
can expand $f(g(X_{1}))$ as

$f(g(X_{1}))=\sum_{j\in I_{f}}f_{j}\left(\sum_{i\in
I_{g}}g_{i}X_{1}^{i}\right)^{j},$

and the expansion on the right has only one term for each of the degrees
$m_{1}D_{1}$, $(m_{1}-1)D_{1}+D_{2}$ and $m_{2}d_{1}$ (or $m_{1}d_{1}$ if
$d_{1}<0$); thus, at least two among those degrees must coincide. However, we
can easily show that this can happen only if $D_{1}=D_{2}=d_{1}$, that is, if
$g(X_{1})$ is a monomial $bX_{1}^{r}$, and $f(T)=T^{m_{1}}+cT^{m_{2}}$. Thus,
we obtain $b=\sqrt[s]{a_{1}}$ and $m_{1}r=l_{1},m_{2}r=l_{2}$,
$c_{2}b^{s}=a_{2}$.

Assume then $\sigma>1$. Write
$T_{1}(X_{1},\dots,X_{\sigma})=X_{1}^{v_{1}}\dots X_{\sigma}^{v_{\sigma}}$; as
explained before, we look for a specialization, depending on the values of
$v_{i}$:

  1. (1)

If there is an index $i$ such that $l_{i}\neq v_{i}$, hence, assuming that
this index is $\sigma$, we impose the identity
$a_{\sigma}X_{\sigma}^{l_{\sigma}}=-a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})$.
Since $l_{\sigma}\neq v_{\sigma}$, this equation yields a specialization of
the form $X_{\sigma}=\tilde{T}(X_{1},\dots,X_{\sigma-1})$ (where we can assume
that the exponents of $\tilde{T}$ are integers, up to changing the variables
$X_{i}$ with some suitable roots).

  2. (2)

If $l_{i}=v_{i}$ for every $i=1,\dots,\sigma$, then the change of variables
$Y_{i}=X_{i}^{l_{i}}$ maps the equation in

$f(g(Y_{1},\dots,Y_{\sigma}))=a_{1}Y_{1}+\dots+a_{\sigma}Y_{\sigma}+a_{\sigma+1}Y_{1}\dots
Y_{\sigma}.$

In this case, we choose $Y_{\sigma}=0$.

In both cases, the specialization is such that the original equation is
reduced to the identity

$f(\tilde{g}(X_{1},\dots,X_{\sigma-1}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma-1}X_{\sigma-1}^{l_{\sigma-1}}.$

Then, from Remark 8 it follows that $\sigma-1=1$, $f(T)=T^{s}$ and
$\tilde{g}(X_{1})=bX_{1}^{r}$. Hence,

$f(g(X_{1},X_{2}))=g(X_{1},X_{2})^{s}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}T_{1}(X_{1},X_{2}).$

Define a function $\varphi:\mathbb{C}[X_{1},X_{2}]\rightarrow\mathbb{C}[T]$,
dependent on $T_{1}(X_{1},X_{2})$, defined by the images of the two
indeterminates $\varphi(X_{1})=T^{m_{1}}$ and $\varphi(X_{2})=T^{m_{2}}$, such
that all terms involved in the expansion of $g(X_{1},X_{2})^{s}$ are mapped to
different terms. Hence, with this mapping, the previous equation becomes

$P(T)^{s}=a_{1}T^{\omega_{1}}+a_{2}T^{\omega_{2}}+a_{3}T^{\omega_{3}}.$

It has been proved (see Proposition 5, or [2, Lemma 2.1]) that the only
solution of this equation is $s=2$ and $P(T)$ is a binomial. Therefore,
$g(X_{1},X_{2})$ is also a binomial, where the two terms are multiplicatively
independent; moreover, there is no cancellation in the expansion of
$g(X_{1},X_{2})^{2}$. Hence, it suffice to apply a suitable change of
variables such that those two multiplicatively independent terms become powers
of the two indeterminates $X_{1}$ and $X_{2}$ (with a slight notation abuse)
to conclude that
$g(X_{1},X_{2})=\sqrt{a_{1}}X_{1}^{\frac{l_{1}}{2}}+\sqrt{a_{2}}X_{2}^{\frac{l_{2}}{2}}$.
∎

######  Proposition 10.

Let $\sigma\geq 2$ be an integer,
$g(X_{1},\dots,X_{\sigma})\in\mathbb{C}[X_{1}^{\pm 1},\dots,X_{\sigma}^{\pm
1}]$ a Laurent polynomial in the indeterminates $X_{1},\dots,X_{\sigma}$, and
$f(T)\in\mathbb{C}[T]$ a polynomial in $T$ such that

(*)
$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+a_{\sigma+2}T_{2}(X_{1},\dots,X_{\sigma}),$

with $l_{1},\dots,l_{\sigma}$ positive integers,
$a_{1},\dots,a_{\sigma+1}\in\mathbb{C}$ and
$T_{1},T_{2}\in\mathbb{C}[X_{1}^{\pm 1},\dots,X_{\sigma}^{\pm 1}]$ distinct
monomials in $X_{1},\dots,X_{\sigma}$.

Then, up to a suitable change of variables, we have one of the following:

  1. (1)

$\sigma=2$,
$g(X_{1},X_{2})=\sqrt[3]{a_{1}}X_{1}^{\frac{l_{1}}{3}}+\sqrt[3]{a_{2}}X_{2}^{\frac{l_{2}}{3}}$,
$f(T)=T^{3}$.

  2. (2)

$\sigma=2$,
$g(X_{1},X_{2})=\sqrt{a_{1}}X_{1}^{\frac{l_{1}}{2}}+\sqrt{a_{2}}X_{2}^{\frac{l_{2}}{2}}+i\sqrt[4]{4a_{1}a_{2}}X_{1}^{\frac{l_{1}}{4}}X_{2}^{\frac{l_{2}}{4}}$,
$f(T)=T^{2}$.

###### Proof.

First, we can assume, up to a rearrangement, that the indeterminate
$X_{\sigma}$ appears in $T_{1}$ and $T_{2}$ with different exponents (not
necessarily non-zero), that is, there exist integers $m_{\sigma 1}\neq
m_{\sigma 2}$ such that $T_{1}=X_{\sigma}^{m_{\sigma 1}}\tilde{T}_{1}$ and
$T_{2}=X_{\sigma}^{m_{\sigma 2}}\tilde{T}_{2}$, with
$\tilde{T}_{1},\tilde{T}_{2}$ monomials not containing $X_{\sigma}$. Hence, if
we impose that $a_{\sigma+1}X_{\sigma}^{m_{\sigma
1}}\tilde{T}_{1}=-a_{\sigma+2}X_{\sigma}^{m_{\sigma 2}}\tilde{T}_{2}$ and
solve for $X_{\sigma}$, we obtain a specialization
$X_{\sigma}=\tilde{a}\tilde{T}$, where $\tilde{T}$ is a monomial in
$X_{1},\dots,X_{\sigma-1}$ with rational exponents; however, we can assume
without loss of generality (by changing $X_{1},\dots,X_{\sigma-1}$ with some
suitable roots) that these exponents are integers, i.e. $\tilde{T}$ is a
Laurent monomial in $X_{1},\dots,X_{\sigma-1}$.

With this specialization, we can turn equation $(*)$ in another equation

(**)
$f(\tilde{g}(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma-1}X_{\sigma-1}^{l_{\sigma-1}}+a_{\sigma}\tilde{a}^{l_{\sigma}}\tilde{T}^{l_{\sigma}}$

in at most $\sigma-1$ indeterminates, where
$\tilde{g}(X_{1},\dots,X_{\sigma-1})=g(X_{1},\dots,X_{\sigma-1},\tilde{T})$,
and such that $\rho^{\prime}\leq 1$ (notice that $\tilde{T}$ might coincide
with one of the monomials $X_{i}^{l_{i}}$). We are now in the hypotheses of
Remark 8 and Proposition 9; hence we have the following cases:

  1. (1)

If $\tilde{T}^{l_{\sigma}}=X_{i}^{l_{i}}$ for some $i$ and
$a_{\sigma}\tilde{a}^{l_{\sigma}}=-a_{i}$, then these two terms cancel out.
Thus we fall in the case considered in Remark 8, yielding $\sigma-2=1$,
$f(T)=T^{s}$. Then, equation $(*)$ becomes

(E1)
$g(\boldsymbol{X})^{s}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}X_{3}^{l_{3}}+a_{4}T_{1}(X_{1},X_{2},X_{3})+a_{5}T_{2}(X_{1},X_{2},X_{3}).$

  2. (2)

If $\tilde{T}^{l_{\sigma}}=X_{i}^{l_{i}}$ for some $i$ and
$a_{\sigma}\tilde{a}^{l_{\sigma}}\neq-a_{i}$, then these two terms can be
merged in a single non-zero term. Then, again by Remark 8 we deduce that
$\sigma-1=1$ and $f(T)=T^{s}$, thus yielding

(E2)
$g(X_{1},X_{2})^{s}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}T_{1}(X_{1},X_{2})+a_{4}T_{2}(X_{1},X_{2}).$

  3. (3)

Lastly, if the exponents of $\tilde{T}^{l_{\sigma}}$ are different from those
of the other terms of equation $(**)$, we can study equation $(**)$ by
applying Proposition 9, obtaining two cases associated to the two solutions
described therein.

    1. (a)

$\sigma-1=1$, $f(T)=T^{s_{1}}+cT^{s_{2}}$, thus the equation becomes

(E3)
$f(g(X_{1},X_{2}))=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}T_{1}(X_{1},X_{2})+a_{4}T_{2}(X_{1},X_{2}).$

    2. (b)

$\sigma-1=2$, $f(T)=T^{2}$, yielding again equation (E1), with $s=2$.

Then, to conclude our study, we have to examine those three equations:

  1. (1)

First, consider the equation

(E1)
$g(\boldsymbol{X})^{s}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}X_{3}^{l_{3}}+a_{4}T_{1}(X_{1},X_{2},X_{3})+a_{5}T_{2}(X_{1},X_{2},X_{3}).$

With a suitable parametrization of the form $X_{i}\rightarrow T^{m_{i}}$ \-
such that all terms of equation (E1) have distinct images - we can turn our
equation to the following polynomial identity in the single indeterminate $T$

$P(T)^{s}=a_{1}T^{\omega_{1}}+a_{2}T^{\omega_{2}}+a_{3}T^{\omega_{3}}+a_{4}T^{\omega_{4}}+a_{5}T^{\omega_{5}}.$

Clearly, we can assume without loss of generality that $\omega_{1}=0,a_{1}=1$,
thus falling under the hypotheses of Lemma 5. Hence the solutions of this last
equation are described in the following Tables:

$s$ | $\omega_{3}$ | $\omega_{4}$ | $\omega_{5}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $P(T)$
---|---|---|---|---|---|---|---
$4$ | $2\omega_{2}$ | $3\omega_{2}$ | $4\omega_{2}$ | $\frac{3}{8}a_{2}^{2}$ | $\frac{1}{16}a_{2}^{3}$ | $\frac{1}{256}a_{2}^{3}$ | $1+\frac{1}{4}a_{2}T^{\omega_{2}}$
$3$ | $3\omega_{2}$ | $5\omega_{2}$ | $6\omega_{2}$ | $-\frac{5}{27}a_{2}^{3}$ | $\frac{1}{81}a_{2}^{5}$ | $-\frac{1}{729}a_{2}^{6}$ | $1+\frac{1}{3}a_{2}T^{\omega_{2}}-\frac{1}{9}a_{2}^{2}T^{2\omega_{2}}$
$2$ | $4\omega_{2}$ | $5\omega_{2}$ | $6\omega_{2}$ | $\frac{5}{64}a_{2}^{4}$ | $-\frac{1}{64}a_{2}^{5}$ | $\frac{1}{256}a_{2}^{6}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}-\frac{1}{8}a_{2}^{2}T^{2\omega_{2}}+\frac{1}{16}a_{2}^{3}T^{3\omega_{2}}$
$2$ | $3\omega_{2}$ | $5\omega_{2}$ | $6\omega_{2}$ | $-\frac{5}{32}a_{2}^{4}$ | $\frac{1}{256}a_{2}^{5}$ | $\frac{19}{1024}a_{2}^{6}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}-\frac{1}{8}a_{2}^{2}T^{2\omega_{2}}-\frac{1}{64}a_{2}^{3}T^{3\omega_{2}}$
$2$ | $4\omega_{2}$ | $7\omega_{2}$ | $8\omega_{2}$ | $\frac{7}{64}a_{2}^{4}$ | $-\frac{1}{512}a_{2}^{7}$ | $\frac{1}{4096}a_{2}^{8}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}-\frac{1}{8}a_{2}^{2}T^{2\omega_{2}}+\frac{1}{16}a_{2}^{3}T^{3\omega_{2}}+\frac{1}{64}a_{2}^{4}T^{4\omega_{2}}$
$2$ | $2\omega_{2}$ | $5\omega_{2}$ | $6\omega_{2}$ | $\frac{5}{4}a_{2}^{2}$ | $-\frac{1}{4}a_{2}^{5}$ | $\frac{1}{16}a_{2}^{6}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}+\frac{1}{2}a_{2}^{2}T^{2\omega_{2}}-\frac{1}{4}a_{2}^{3}T^{3\omega_{2}}$

Table 5.

$d$ | $\omega_{3}$ | $\omega_{4}$ | $\omega_{5}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $P(T)$
---|---|---|---|---|---|---|---
$2$ | $2\omega_{2}$ | $3\omega_{2}$ | $4\omega_{2}$ |  | $-\frac{1}{8}a_{2}^{3}+\frac{1}{2}a_{2}a_{3}$ | $\left(-\frac{1}{8}a_{2}^{2}+\frac{1}{2}a_{3}\right)^{2}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}+\left(\frac{1}{2}a_{3}-\frac{1}{8}a_{2}^{2}\right)T^{2\omega_{2}}$

Table 6.

Now, notice that since $g(X_{1},X_{2},X_{3})^{s}$ contains the $3$
multiplicatively independent terms $X_{i}^{l_{i}}$, then
$g(X_{1},X_{2},X_{3})$ also must contain at least three multiplicatively
independent terms. Moreover, if $g(X_{1},X_{2},X_{3})$ has exactly three
terms, these must be all multiplicatively independent, thus there are no
cancellations in the expansion of $g(X_{1},X_{2},X_{3})^{s}$, which then will
have at least $\binom{4}{2}=6$ terms; hence, looking at the Tables we can
deduce that $s=2$, and $g(X_{1},X_{2},X_{3})$ has $4$ or $5$ terms; since in
both cases there must be exactly three multiplicatively independent terms, we
can map those three terms each in a power of one indeterminate, thus obtaining
an equation of the form

$g(X_{1},X_{2},X_{3})=c_{1}X_{1}^{\alpha_{1}}+c_{2}X_{2}^{\alpha_{2}}+c_{3}X_{3}^{\alpha_{3}}+c_{4}R_{1}(X_{1},X_{2},X_{3})+c_{5}R_{2}(X_{1},X_{2},X_{3})$

(where $g(X_{1},X_{2},X_{3})$ has four terms if and only if $R_{1}=R_{2}$).
Then, expanding $g(X_{1},X_{2},X_{3})^{2}$ it is easy to check that among the
terms dependent on $R_{1},R_{2}$ we cannot impose equalities such that there
are only five terms left in the end.

  2. (2)

Consider now the equation

(E2)
$g(X_{1},X_{2})^{s}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}T_{1}(X_{1},X_{2})+a_{4}T_{2}(X_{1},X_{2}).$

Similarly, using a suitable parametrization, dependent on $T_{1}$ and $T_{2}$,
of the form $X_{1}\rightarrow T^{m_{1}}$, $X_{2}\rightarrow T^{m_{2}}$ such
that no terms of (E2) have the same image, we reduce our equation to

$P(T)^{s}=a_{1}T^{\omega_{1}}+a_{2}T^{\omega_{2}}+a_{3}T^{\omega_{3}}+a_{4}T^{\omega_{4}}.$

Again, we can assume without loss of generality that $\omega_{1}=0,a_{1}=1$.
Thus, as a consequence of Lemma 5, we have the following solutions:

$s$ | $\omega_{3}$ | $\omega_{4}$ | $P(T)$
---|---|---|---
$2$ | $3\omega_{2}$ | $4\omega_{2}$ | $1+\frac{1}{2}a_{2}T^{\omega_{2}}-\frac{1}{8}a_{2}^{2}T^{2\omega_{2}}$
$3$ | $2\omega_{2}$ | $3\omega_{2}$ | $1+\frac{1}{3}a_{2}T^{\omega_{2}}$

Essentially, these two solutions can be described as the cube of a binomial,
and the square of a special trinomial. Next, we examine in detail these two
cases:

     * •

If $s=3$, and $g(X_{1},X_{2})$ is a binomial, since the two terms of
$g(X_{1},X_{2})$ must be multiplicatively independent (because
$g(X_{1},X_{2})^{3}$ has two multiplicatively independent terms), we can
assume without loss of generality (up to a suitable change of variables) that
$g(X_{1},X_{2})=c_{1}X_{1}^{\alpha_{1}}+c_{2}X_{2}^{\alpha_{2}}$, which
immediately yields the first solution.

     * •

If $s=2$, and $g(X_{1},X_{2})$ is a trinomial, as before, there must be at
least two multiplicatively independent terms in $g(X_{1},X_{2})$; on the other
hand, clearly the three terms cannot be multiplicatively independent (since in
this case the square would have six terms). Moreover, we deduce from the table
that in $P(T)^{2}$ the square of the middle term cancels out with the mixed
product of the other two. Thus, reflecting this in our original equation, we
can assume, up to a suitable change of variables, that $g(X_{1},X_{2})$ has
the form

$g(X_{1},X_{2})=c_{1}X_{1}^{\alpha_{1}}+c_{2}X_{2}^{\alpha_{2}}+c_{3}R(X_{1},X_{2}),$

with $R(X_{1},X_{2})$ distinct from the other two terms, and such that one of
the following conditions hold (up to a rearrangement):

       1. (a)

$2c_{2}c_{3}X_{2}^{\alpha_{2}}R(X_{1},X_{2})=-c_{1}^{2}X_{1}^{2\alpha_{1}}$,
that is, $R(X_{1},X_{2})=X_{1}^{2\alpha_{1}}X_{2}^{-\alpha_{2}}$,
$c_{3}=-\frac{c_{1}^{2}}{2c_{2}}$.

       2. (b)

$c_{3}^{2}R^{2}(X_{1},X_{2})=-2c_{1}c_{2}X_{1}^{\alpha_{1}}X_{2}^{\alpha_{2}}$,
which implies
$R(X_{1},X_{2})=X_{1}^{\frac{\alpha_{1}}{2}}X_{2}^{\frac{\alpha_{2}}{2}}$,
$c_{3}=\sqrt{-2c_{1}c_{2}}$.

However, it is easy to see that these two solutions are equivalent up to a
change of variables, obtained by mapping $R(X_{1},X_{2})$ to one indeterminate
(or to an appropriate root). Therefore, expanding the square yields the second
solution.

  3. (3)

Finally, consider now the equation

(E3)
$f(g(X_{1},X_{2}))=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}T_{1}(X_{1},X_{2})+a_{4}T_{2}(X_{1},X_{2}),$

with $f(T)=T^{s_{1}}+\alpha T^{s_{2}}$, $s_{1}>s_{2}\geq 1$. In this context,
we have $\tilde{g}(X_{1})=cX_{1}^{r}$, where
$\tilde{g}(X_{1})=g(X_{1},\tilde{T})$, and $X_{2}=\tilde{T}$ is obtained from
$(*)$; in particular, $\tilde{T}$ is a monomial in the single indeterminate
$X_{1}$, that is, $\tilde{T}=t_{1}X_{1}^{\gamma_{1}}$. But since
$g(X_{1},X_{1}^{\gamma_{1}})=cX_{1}^{r}$, the terms (disregarding the
coefficients) of $g(X_{1},X_{2})$ must necessarily be contained in the sum
$\displaystyle\sum_{i\in\mathbb{Z}}X_{1}^{r-i\gamma_{1}}X_{2}^{i}.$ At this
point, write

$\displaystyle g(X_{1},X_{2})=\sum_{i\in I}X_{1}^{r-i\gamma_{1}}X_{2}^{i},$

and consider $f(g(X_{1},X_{2}))=g(X_{1},X_{2})^{s_{1}}+\alpha
g(X_{1},X_{2})^{s_{2}}$. We want to prove that the two polynomials
$g(X_{1},X_{2})^{s_{1}}$ and $g(X_{1},X_{2})^{s_{2}}$ have no common term: in
fact, if such a monomial $X_{1}^{N_{1}}X_{2}^{N_{2}}$ exists, there must be
$i_{1},\dots,i_{s_{1}}$ and $j_{1},\dots,j_{s_{2}}$ such that

$\begin{cases}(r-\gamma_{1}i_{1})+\dots+(r-\gamma_{1}i_{s_{1}})=N_{1},\\\
i_{1}+\dots+i_{s_{1}}=N_{2},\\\
(r-\gamma_{1}j_{1})+\dots+(r-\gamma_{1}j_{s_{2}})=N_{1},\\\
j_{1}+\dots+j_{s_{2}}=N_{2},\end{cases}\text{ implying
}\begin{cases}i_{1}+\dots+i_{s_{1}}=N_{2},\\\ s_{1}r-\gamma_{1}N_{2}=N_{1},\\\
j_{1}+\dots+j_{s_{2}}=i_{1}+\dots+i_{s_{1}},\\\
s_{2}r-\gamma_{1}N_{2}=N_{1}.\end{cases}.$

The second and the fourth equation of this linear system are incompatible if
$s_{1}\neq s_{2}$; hence, the two polynomials $g(X_{1},X_{2})^{s_{1}}$ and
$g(X_{1},X_{2})^{s_{2}}$ have no common term. The number of terms of
$f(g(X_{1},X_{2}))$ is then equal to the sum of the number of terms of
$g(X_{1},X_{2})^{s_{1}}$ and $g(X_{1},X_{2})^{s_{2}}$. Since $s_{1}>s_{2}\geq
1$, and $g(X_{1},X_{2})$ has at least two terms, $g(X_{1},X_{2})^{s_{1}}$ has
at least three terms, while $g(X_{1},X_{2})^{s_{2}}$ has at least two:
therefore $f(g(X_{1},X_{2}))$ has at least $5>4=\sigma+\rho$ terms, which is a
contradiction.∎

A direct application of this result yields an extension of Corollary 7.

######  Corollary 11.

Let
$\alpha(n)=\displaystyle\sum_{i=1}^{k}c_{i}\alpha_{i}^{n}\in\mathcal{E}_{\mathbb{Z}^{+}}$.

  1. (1)

If there are exactly $k-1\geq 2$ (and not more) multiplicatively independent
integers among the elements of the set $\\{\alpha_{1},\dots,\alpha_{k}\\}$,
then the set $\alpha(\mathbb{N})$ is a Universal Hilbert Set, unless
$\alpha(n)$ is of the form
$\alpha(n)=(b_{1}\beta_{1}^{m}+b_{2}\beta_{2}^{m})^{2}$.

  2. (2)

If there are exactly $k-2\geq 2$ (and not more) multiplicatively independent
integers among the elements of the set $\\{\alpha_{1},\dots,\alpha_{k}\\}$,
then the set $\alpha(\mathbb{N})$ is a Universal Hilbert Set, unless
$\alpha(n)$ is of the form
$\alpha(n)=(b_{1}\beta_{1}^{m}+b_{2}\beta_{2}^{m})^{3}$.

In particular, if $\alpha(n)=\alpha_{1}^{n}+\dots+\alpha_{k}^{n}$, and among
the $\alpha_{i}$ there are at least $k-2\geq 2$ multiplicatively independent
elements, then $\alpha(n)$ is a Universal Hilbert Set.

###### Proof.

Let $\alpha(n)=\sum_{i=1}^{k}c_{i}\alpha_{i}$ be such that
$\alpha(\mathbb{N})$ is not a Universal Hilbert Set. Then by Theorem 6 there
exist $\beta\in\mathcal{E}_{\mathbb{Z}}$ and a polynomial
$P(T)\in\mathbb{Q}[T]$ of degree $d\geq 2$ such that $\alpha(dn)=P(\beta(n))$
identically.

  1. (1)

We can map this relation to an equation of the form

$F(G(X_{1},\dots,X_{\sigma}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma}).$

Hence, since $k\geq 3$, by Proposition 9 we obtain $F(T)=T^{2}$ and that
$G(X_{1},X_{2})$ is a binomial, and pulling back this map yields the thesis.

  2. (2)

In this case, the relation $\alpha(dn)=P(\beta(n))$ is mapped, via a suitable
change of variables, to the equation

$F(G(X_{1},\dots,X_{\sigma}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+a_{\sigma+2}T_{2}(X_{1},\dots,X_{\sigma}).$

Therefore, since $k\geq 3$, we are under the assumptions of Proposition 10.
However, since both polynomials $F(T)$ and $G(X_{1},\ldots,X_{\sigma})$ cannot
contain terms with non-real cofficients, the only admissible solution is the
one where $F(T)=T^{3}$ and $G(X_{1},X_{2})$ is a binomial; pulling back our
map yields again the thesis. ∎

######  Example 12.

  1. (1)

From the previous proposition we immediately deduce that any set of the form
$\\{\alpha_{1}^{n}+\alpha_{2}^{n}+\alpha_{3}^{n}\\}$, or
$\\{\alpha_{1}^{n}+\alpha_{2}^{n}+\alpha_{3}^{n}+\alpha_{4}^{n}\\}$, where the
integers $\alpha_{i}$ are not powers of the same integer, is a Universal
Hilbert Set.

  2. (2)

Let $\alpha(n)=8^{n}+27^{n}+3\cdot 12^{n}+3\cdot 18^{n}$. Since
$\alpha(n)=(2^{n}+3^{n})^{3}$, $\alpha(\mathbb{N})$ is not a Universal Hilbert
Set.

##  4\. The general case

We studied compositions having few monomials (besides the fixed ones); one of
the drawbacks of our recursive strategy is that such a method produces
mechanical proofs with an increasing number of cases that would not give much
insight on the general case, thus making this kind of result pointless and
tedious. However, it makes sense to ask how many multiplicatively independent
elements there can be in a polynomial composition
$f(g(X_{1},\dots,X_{\sigma}))$. Namely, we will ask the following: _if we fix
the number of variables $\sigma$, can we determine the minimum number $k$ of
terms of a composition?_

Let $\sigma\geq 1$, $\rho\geq 0$ be integers, $f\in\mathbb{C}[T]$ a polynomial
of degree larger than $1$, $g\in\mathbb{C}[X_{1}^{\pm 1},\dots,X_{\sigma}^{\pm
1}]$ a Laurent polynomial in $X_{1},\dots,X_{\sigma}$, and consider the
equation of Question 1

$f(g(X_{1},\dots,X_{\sigma}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+\dots+a_{\sigma+\rho}T_{\rho}(X_{1},\dots,X_{\sigma}),$

where $a_{1},\dots,a_{\sigma+\rho}\in\mathbb{C}$,
$l_{1},\dots,l_{\sigma}\in\mathbb{Z}$, and $T_{1},\dots,T_{\rho}$ are Laurent
monomials in $X_{1},\dots,X_{\sigma}$. Fix $\sigma+\rho=k$, and write the two
polynomials $f$ and $g$ as

$f(T)=\sum_{j\in J}f_{j}T^{j}\ \ \ \text{ and }\ \ \
g(X_{1},\dots,X_{\sigma})=\sum_{(i_{1},\dots,i_{\sigma})\in
I}g_{i_{1},\dots,i_{\sigma}}X_{1}^{i_{1}}\dots X_{\sigma}^{i_{\sigma}},$

where both polynomials have coefficients in $\mathbb{C}$, and the sets
$J\subset\mathbb{Z}$ and $I\subset\mathbb{Z}^{\sigma}$ are finite, with
$h=|I|$ being the number of terms of the inner polynomial
$g(X_{1},\dots,X_{\sigma})$. We want to provide a lower bound for the minimum
number of terms $k=\sigma+\rho$ of these polynomial compositions, depending on
$\sigma$ and $h$; we will denote this minimum by $\tilde{k}(\sigma,h)$.
Moreover, denote by
$\displaystyle\tilde{k}(\sigma)=\min_{k\geq\sigma}\tilde{k}(\sigma,h)$.

Clearly, considering $g(X_{1},\dots,X_{\sigma})=X_{1}+\dots+X_{\sigma}$ and
$f(T)=T^{2}$ we see that $f(g(X_{1},\dots,X_{\sigma}))$ has exactly
$\binom{\sigma+1}{2}$ terms, thus $\tilde{k}(\sigma)\leq\binom{\sigma+1}{2}$.

On the other hand, we can easily prove that, if $k\leq 2\sigma-2$, there are
no polynomials $f$ and $g$ such that

(4)
$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+\dots+a_{\sigma+\rho}T_{\rho}(X_{1},\dots,X_{\sigma}).$

For this purpose, consider the two monomials $T_{1}$ and $T_{2}$. Since they
are distinct, we can deduce from the assumption
$a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})=-a_{\sigma+2}T_{2}(X_{1},\dots,X_{\sigma})$
a specialization $X_{i}=\tilde{T}$ for one of our indeterminates. Moreover, if
we apply this specialization, our equation will be reduced to another one
having $\sigma^{\prime}\leq\sigma-1$ variables and $k^{\prime}\leq k-2$ terms;
further, in order to cancel out one variable $X_{j}$, the term
$a_{j}X_{j}^{l_{j}}$ must cancel out with another term, which has to be
associated (after our specialization) to a certain monomial - that is, the
only way to cancel out a variable is to diminish the number of terms (at
least) by two. Therefore, it is easy to check that this second equation would
still satisfy $k^{\prime}\leq 2\sigma^{\prime}-2$; hence we can prove by a
descent argument (notice that we have no solution for $\sigma=1,2$) that
$\tilde{k}(\sigma)\geq 2\sigma-1$.

It is worth noticing that this argument can be applied to Theorem 6, yielding
the following result.

######  Proposition 13.

With the notation used in this chapter, let
$\displaystyle\alpha(n)=\sum_{i=1}^{k}c_{i}\alpha_{i}^{n}\in\mathcal{E}_{\mathbb{Z}^{+}}$
be such that there are at least $\frac{k}{2}+1$ multiplicatively independent
elements between $\alpha_{1},\dots,\alpha_{n}\in\mathbb{Z}^{+}$.

Then the set $\alpha(\mathbb{N})$ is a Universal Hilbert Set.

###  4.1. Small values of $\sigma$

We have proved that

$2\sigma-1\leq\tilde{k}(\sigma)\leq\binom{\sigma+1}{2}.$

In order to guess whether those two bounds are sharp and gather more insight
on $\tilde{k}(\sigma)$, we study the behavior of $\tilde{k}(\sigma)$ for small
values of $\sigma$.

######  Remark 14.

  1. (1)

Clearly, $\tilde{k}(1)=1=2\cdot 1-1=\binom{1+1}{2}$ (see Remark 8).

  2. (2)

Remark 8 and Proposition 9 yield $\tilde{k}(2)=3=\binom{2+1}{2}$.

  3. (3)

Since $6=\binom{\sigma+1}{2}$, $\tilde{k}(3)\leq 6$. On the other hand, for a
composition having $k<6$ terms, we are under the hypotheses of either Remark 8
or Propositions 9 and 10. Since these results show that there are no solutions
for $\sigma=3$ under these hypotheses, $\tilde{k}(3)=6=\binom{3+1}{2}$.

The case $\sigma=4$ is significantly harder to deal with our tools, since
Proposition 10 would not cover the cases $7\leq k\leq 9$, and we already noted
that, as $k$ grows, our recursive strategy becomes way more impractical.
However, we can still show that $\tilde{k}(4)=\binom{4+1}{2}$ if
$g(X_{1},\dots,X_{4})$ is a polynomial in
$\mathbb{C}[X_{1},X_{2},X_{3},X_{4}]$:

######  Proposition 15.

Let $g(X_{1},X_{2},X_{3},X_{4})\in\mathbb{C}[X_{1},X_{2},X_{3},X_{4}]$ be a
polynomial in the indeterminates $X_{1},X_{2},X_{3},X_{4}$, and
$f(T)\in\mathbb{C}[T]$ a polynomial in $T$ such that

(*)
$f(g(X_{1},X_{2},X_{3},X_{4}))=a_{1}X_{1}^{l_{1}}+\dots+a_{4}X_{4}^{l_{4}}+\sum_{i=1}^{\rho}a_{4+i}T_{i}(X_{1},X_{2},X_{3},X_{4}),$

with $l_{1},l_{2},l_{3},l_{4}$ positive integers,
$a_{1},\dots,a_{4+\rho}\in\mathbb{C}$ and
$T_{1},\dots,T_{\rho}\in\mathbb{C}[X_{1},X_{2},X_{3},X_{4}]$ monomials in
$X_{1},\dots,X_{4}$. Let $k=4+\rho$ be the number of terms of
$f(g(X_{1},X_{2},X_{3},X_{4}))$.

Then $k\geq 10=\binom{4+1}{2}$.

###### Proof.

We only need to work on the cases $k=7,8,9$.

  1. (1)

Assume $k=7$. Assume that $X_{4}$ appears in the monomial $T_{1}$; therefore,
with the specialization $X_{4}=0$, we obtain that $f(g(X_{1},X_{2},X_{3},0))$
is still a composition of the form $(*)$ (with $3$ variables) with at most $5$
terms, which yields a contradiction since $\tilde{k}(3)=6$ by Remark 14.

  2. (2)

Suppose $k=8$. Now, assume that there is one variable $X_{i}$ dividing at
least two monomials $T_{j},T_{r}$. Then, with the specialization $X_{i}=0$, we
obtain again a composition of the form $(*)$ in $3$ variables having between
three and five terms, yielding again a contradiction by Remark 14. Hence, each
variable divides at most one of the four monomials $T_{i}$: clearly, this
leads to the equation (up to a rearrangement)

$f(g(X_{1},\dots,X_{4}))=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}X_{3}^{l_{3}}+a_{4}X_{4}^{l_{4}}+a_{5}X_{1}^{l^{\prime}_{1}}+a_{6}X_{2}^{l^{\prime}_{2}}+a_{7}X_{3}^{l^{\prime}_{3}}+a_{8}X_{4}^{l^{\prime}_{4}}.$

However, at this point, if $\tilde{g}(X_{1},X_{2})=g(X_{1},X_{2},0,0)$, with
the substitution $X_{3}=X_{4}=0$ we obtain

$f(\tilde{g}(X_{1},X_{2}))=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{5}X_{1}^{l^{\prime}_{1}}+a_{6}X_{2}^{l^{\prime}_{2}},$

which by Proposition 10 implies either $f(T)=T^{2}$ or $f(T)=T^{3}$.

On the other hand, if $\bar{g}(X_{1})=g(X_{1},0,0,0)$, with the specialization
$X_{2}=X_{3}=X_{4}=0$ we obtain

$f(\bar{g}(X_{1}))=a_{1}X_{1}^{l_{1}}+a_{5}X_{1}^{l^{\prime}_{1}},$

which in turn implies, by Proposition 9, that $f(T)$ has the form
$f(T)=T^{m_{1}}+cT^{m_{2}}$, which is impossible.

  3. (3)

Finally, let $k=9$. In that case, clearly there exists one variable dividing
at least two between the monomials $T_{1},\dots,T_{5}$. Notice that if there
is an indeterminate $X_{i}$ dividing at least three monomials, we would obtain
once again a contradiction with the specialization $X_{1}=0$ and Remark 14.
Hence, each indeterminate appears in at most two monomials, and there is at
least one variable appearing in exactly two. Let $X_{1}$ be one of the
variables appearing in the maximum number of terms of our composition; then
$X_{1}$ divides exactly two monomials (say, $T_{4}$ and $T_{5}$), and all
other variables divide at most two monomials between $T_{1},\dots,T_{5}$.
Then, with the specialization $X_{1}=0$ we have

$f(g(0,X_{2},X_{3},X_{4}))=a_{2}X_{2}^{l_{2}}+a_{3}X_{3}^{l_{3}}+a_{4}X_{4}^{l_{4}}+\sum_{i=1}^{3}a_{4+i}T_{i}(0,X_{2},X_{3},X_{4}).$

Now, let $X_{2}$ be the variable that divides the most monomials among
$T_{1},T_{2},T_{3}$. As we said, $X_{2}$ must divide at most two of these
three. We have two possible cases:

    1. (a)

Assume that $X_{2}$ divides exactly one monomial (say, $T_{3}$). Then, setting
$X_{2}=0$ we are left with the equation

$f(g(0,0,X_{3},X_{4}))=a_{3}X_{3}^{l_{3}}+a_{4}X_{4}^{l_{4}}+a_{5}T_{1}(0,0,X_{3},X_{4})+a_{6}T_{2}(0,0,X_{3},X_{4}),$

with the added information that $X_{3}$ and $X_{4}$ both divide exactly one of
the monomials $T_{1},T_{2}$. This equation is a polynomial composition in $2$
variables; thus by Proposition 10 we obtain that either $f(T)=T^{2}$ or
$f(T)=T^{3}$. However, assuming that $X_{3}$ divides $T_{2}$, further setting
$X_{3}=0$ we get

$f(g(0,0,0,X_{4}))=a_{4}X_{4}^{l_{4}}+a_{5}T_{1}(0,0,X_{3},X_{4}),$

which implies by Proposition 9 that $f(T)$ is of the form
$f(T)=T^{m_{1}}+cT^{m_{2}}$, contradicting the previous statement.

    2. (b)

Suppose then that $X_{2}$ divides exactly two of these monomials (say, $T_{2}$
and $T_{3}$). Then by imposing $X_{2}=0$ we obtain

$f(g(0,0,X_{3},X_{4}))=a_{3}X_{3}^{l_{3}}+a_{4}X_{4}^{l_{4}}+a_{5}T_{1}(0,0,X_{3},X_{4}),$

which by Proposition 9 implies $f(T)=T^{2}$.

Now, notice that, since there are four variables, each dividing at most two
monomials, there must be a monomial $T_{i}$ containing exactly one variable,
say $T_{i}=X_{j}^{l^{\prime}_{j}}$. However, if there is exactly one monomial
containing only the variable $X_{j}$ between $T_{1},\dots,T_{5}$, clearly by
sending all other variables to zero we would obtain an equation of the form

$f(\tilde{g}(X_{j}))=a_{j}X_{j}^{l_{j}}+a_{i+4}\tilde{T}_{i}(X_{j}),$

which would imply by Proposition 9 that $f(T)=T^{m_{1}}+cT^{m_{2}}$,
contradicting the previous part; thus, since each indeterminate can divide at
most two monomials, we can conclude (since each variable divides at most two
monomials) that there is a variable $X_{s}$, dividing exactly two monomials,
such that those two monomials do not contain other variables besides $X_{s}$.
Now, let us rearrange our indexes such that this variable $X_{s}$ is $X_{1}$
and the two monomials $T_{4}$ and $T_{5}$ are of the form
$T_{4}=X_{1}^{v_{4}}$, $T_{5}=X_{1}^{v_{5}}$ (we can do that since this does
not contradict our previous assumption on $X_{1}$).

Therefore our main equation becomes

$g(X_{1},X_{2},X_{3},X_{4})^{2}=a_{1}X_{1}^{l_{1}}+a_{2}X_{2}^{l_{2}}+a_{3}X_{3}^{l_{3}}+a_{4}X_{4}^{l_{4}}+$
$+a_{8}X_{1}^{v_{4}}+a_{9}X_{1}^{v_{5}}+\sum_{i=1}^{3}a_{i+4}T_{i}(X_{2},X_{3},X_{4}).$

We will conclude the proof by showing that it is not possible for the square
of a polynomial $g(X_{1},\dots,X_{\sigma})^{2}$ (assuming that this square has
the form $(*)$) to contain no mixed product between $X_{1}$ and the other
variables.

In fact, remembering that such a polynomial $g(X_{1},\dots,X_{\sigma})$
contains monomials consisting of single variables for each variable $X_{i}$,
then clearly it must necessarily contain also some mixed products between
$X_{1}$ and some other variables (else it would be impossible to cancel out
the mixed products arising from the square expansion of
$g(X_{1},\dots,X_{\sigma})$). Between those mixed products, pick the maximum
one with respect to the natural lexicographic order, and denote it by
$\tilde{m}(X_{1},\dots,X_{\sigma})$; also, denote by
$\tilde{M}(X_{1},\dots,X_{\sigma})$ the maximum term of
$g(X_{1},\dots,X_{\sigma})$. Clearly, the term
$\tilde{m}(X_{1},\dots,X_{\sigma})\tilde{M}(X_{1},\dots,X_{\sigma})$ is a
mixed product containing $X_{1}$ and some other variables, which appears in
the square expansion of $g(X_{1},\dots,X_{\sigma})^{2}$; in order to check
that this term does not cancel out (and thus appears in
$g(X_{1},\dots,X_{\sigma})^{2}$, we consider two cases:

      1. (i)

If $\tilde{m}(X_{1},\dots,X_{\sigma})=\tilde{M}(X_{1},\dots,X_{\sigma})$, then
$\tilde{m}(X_{1},\dots,X_{\sigma})\tilde{M}(X_{1},\dots,X_{\sigma})=\tilde{M}^{2}(X_{1},\dots,X_{\sigma})$
appears only once in the expansion, and thus does not cancel out.

      2. (ii)

If $\tilde{m}(X_{1},\dots,X_{\sigma})\neq\tilde{M}(X_{1},\dots,X_{\sigma})$,
we have $\tilde{M}(X_{1},\dots,X_{\sigma})=X_{1}^{\alpha}$, and clearly it is
not possible to realize
$\tilde{m}(X_{1},\dots,X_{\sigma})\tilde{M}(X_{1},\dots,X_{\sigma})$ in any
other ways in the square expansion of $g(X_{1},\dots,X_{\sigma})$, and thus
this term does not cancel out.

∎

###  4.2. Sum of sets of vectors and cancellations

The previous results point to $\tilde{k}(\sigma)$ being close to
$\binom{\sigma+1}{2}$; while a general result is out of reach at the moment,
there is some evidence suggesting that this might indeed be the case. In fact,
assuming fixed the number of terms $h=|I|$ of $g(X_{1},\dots,X_{\sigma})$, the
number of terms $k$ of the composition $f(g(X_{1},\dots,X_{\sigma}))$ is
obtained by expanding the sum

($\star$) $f(g(X_{1},\dots,X_{\sigma}))=\sum_{j\in
J}f_{j}g(X_{1},\dots,X_{\sigma})^{j},$

and then cancelling out some terms. Then, in order to study
$\tilde{k}(\sigma,h)$, we can consider two invariants:

  1. (1)

The number of different exponents in the expansion $(\star)$ of
$f(g(X_{1},\dots,X_{\sigma}))$, counting all exponents appearing before any
cancellation between terms belonging to different powers of
$g(X_{1},\dots,X_{\sigma})$ is performed. We will denote this value by
$W(f,g)$, and is obviously an upper bound for $k$.

  2. (2)

The number of exponents (among the $W(f,g)$ listed before) appearing in the
expansion that are cancelled out in the final computation of
$f(g(X_{1},\dots,X_{\sigma}))$. We will denote this value by $C(f,g)$;
obviously $k=W(f,g)-C(f,g)$.

The motivation behind this division lies in the fact that the two invariants
$W(f,g)$ and $C(f,g)$ describe very different problems.

In fact, we can study $W(f,g)$ using tools from additive number theory. By
definition we can associate to the exponents of $g(X_{1},\dots,X_{\sigma})$
the set $I\subseteq\mathbb{Z}^{\sigma}$, and, for a fixed integer $\alpha\geq
1$, the exponents of $g(X_{1},\dots,X_{\sigma})^{\alpha}$ described by
$W(f,g)$ are exactly the elements of the set $\alpha I$. Therefore, by
studying $W(f,g)$ we are basically studying the cardinality of the union set
$\displaystyle\bigcup_{\alpha\in J}\alpha I$, where
$I\subseteq\mathbb{Z}^{\sigma}$ and $J\subseteq\mathbb{Z}$ are fixed. In this
context, the following result, due to Ruzsa, comes handy.

######  Theorem 16 ([12, Corollary 1.1]).

Let $A,B\subseteq\mathbb{R}^{\sigma}$ be two sets such that $|A|\leq|B|$ and
$\dim(A+B)=\sigma$. Then

$|A+B|\geq|B|+\sigma|A|-\frac{\sigma(\sigma+1)}{2}.$

In our context, the set $I$ has dimension at least equal to $\sigma-1$ (since
$f(g(X_{1},\dots,X_{\sigma}))$ must contain $\sigma$ multiplicatively
independent terms); then, if $h=|I|\geq\sigma-1$, from the previous theorem we
immediately deduce that

$|\alpha I|\geq
h+(\alpha-1)\left[(\sigma-1)h-\frac{\sigma(\sigma-1)}{2}\right],$

which yields

$W(f,g)=|\bigcup_{\alpha\in J}\alpha I|\geq|deg(f)I|\geq
h+(deg(f)-1)\left[(\sigma-1)h-\frac{\sigma(\sigma-1)}{2}\right].$

We can deduce from here that our claim is true in the naive case $C(f,g)=0$
(for instance if $f(T)$ and $g(X_{1},\dots,X_{\sigma})$ have positive real
coefficients).

######  Proposition 17.

Let $\sigma\geq 1$, and let $f\in\mathbb{C}[T]$ be a polynomial and
$g\in\mathbb{C}[X_{1},\dots,X_{\sigma}]$ a Laurent polynomial, having exactly
$h$ terms, such that

$f(g(\boldsymbol{X}))=a_{1}X_{1}^{l_{1}}+\dots+a_{\sigma}X_{\sigma}^{l_{\sigma}}+a_{\sigma+1}T_{1}(X_{1},\dots,X_{\sigma})+\dots+a_{\sigma+\rho}T_{\rho}(X_{1},\dots,X_{\sigma}),$

with $l_{1},\dots,l_{\sigma}$ positive integers,
$a_{1},\dots,a_{\sigma+1}\in\mathbb{C}$ and
$T_{1},T_{2}\in\mathbb{C}[X_{1}^{\pm 1},\dots,X_{\sigma}^{\pm 1}]$ monomials
in the indeterminates $X_{1},\dots,X_{\sigma}$, and denote by $k=\sigma+\rho$
the number of terms of this polynomial composition.

Then

$W(f,g)\geq
h+(deg(f)-1)\left[(\sigma-1)h-\frac{\sigma(\sigma-1)}{2}\right]\geq\sigma
h-\frac{\sigma(\sigma-1)}{2}\geq\binom{\sigma+1}{2}.$

The lower bounds provided in Proposition 17 are sharp; in fact, it is easy to
see that, for

$f(T)=T^{2}\ \ ,\ \ \
g(X_{1},\dots,X_{\sigma})=X_{1}+\dots+X_{\sigma}+\sum_{i=2}^{h-\sigma+1}\frac{X_{1}^{i}}{X_{\sigma}^{i-1}},$

the composition $f(g(X_{1},\dots,X_{\sigma}))=g(X_{1},\dots,X_{\sigma})^{2}$
has exactly $\sigma h-\frac{\sigma(\sigma-1)}{2}$ terms.

Furthermore, we can rewrite the second bound as

$W(f,g)\geq\sigma
h-\frac{\sigma(\sigma-1)}{2}=\binom{\sigma+1}{2}+\sigma(h-\sigma).$

Therefore, if we could prove that $C(f,g)\leq\sigma(h-\sigma)$, we would
obtain the desired bound for $\tilde{k}(\sigma)$. Since
$g(X_{1},\dots,X_{\sigma})$ must contain, by definition, at least $\sigma$
multiplicatively independent terms, this upper bound for $C(f,g)$ basically
states that for each term of $g(X_{1},\dots,X_{\sigma})$, besides the $\sigma$
multiplicatively independent ones, there can be no more than $\sigma$
cancellations.

However, studying $C(f,g)$ is an extremely hard task. In fact, each
cancellation would imply a polynomial relation between the coefficients of the
involved monomials (from the expansion $(\star)$) and an equality on the
exponents.

The first problem can be reduced to a study of intersection of algebraic
surfaces, which is in itself a very hard problem, given our little knowledge
on the behaviour of these coefficients.

As for the second one, in order to have a cancellation involving terms of (at
least) two different polynomial powers $g(X_{1},\dots,X_{\sigma})^{j_{1}}$ and
$g(X_{1},\dots,X_{\sigma})^{j_{2}}$ there should exist a monomial
$X_{1}^{\alpha_{1}}\dots X_{\sigma}^{\alpha_{\sigma}}$ appearing in both these
powers; clearly, this is equivalent to saying that the vector
$(\alpha_{1},\dots,\alpha_{\sigma})\in\mathbb{Z}^{\sigma}$ must belong to both
sets $j_{1}I$ and $j_{2}I$.

Thus we have to face the following additive problem:

######  Question 18.

Let $\sigma\geq 1$, and consider two finite sets
$I\subseteq\mathbb{Z}^{\sigma}$ and $J\subseteq\mathbb{Z}^{+}$. Set $|I|=h$.

Given a vector $\boldsymbol{w}\in\mathbb{Z}^{\sigma}$, determine all
factoriztions of $\boldsymbol{w}$ of the type

$\boldsymbol{w}=c_{1}\boldsymbol{v}_{1}+\dots+c_{k}\boldsymbol{v}_{k},$

where $\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{k}\in I$ and
$c_{1},\dots,c_{k}\in\mathbb{Z}^{+}$ are such that $c_{1}+\dots+c_{k}\in J$.

Additive decompositions have been the subject of several works ([8] and [9]
are good monographs on this argument); in general, these decompositions are
not unique, and finding the possible decompositions of a given vector with
respect to a finite set of generators $I$ is very hard. In fact, the easiest
case $\sigma=1$ (where our vectors are, actually, integers) is a reformulation
of the well-known _Subset Sum Problem_ ([7]), which asks, given a finite set
$I\subseteq{Z}$, if there exists a subset $J$ of $I$ such that the sum of the
elements of $J$ is a target value $w$; however, the Subset Sum Problem is NP-
complete (see [7] for a proof).

In light of both the evidence provided and the final considerations, we
conclude this work with the following question:

######  Question 19.

Is it true that $\tilde{k}(\sigma)=\binom{\sigma+1}{2}$?

## Acknowledgements

This work is part of my PhD thesis. I would like to thank my advisors,
Professors Roberto Dvornicich and Umberto Zannier for their supervision, and
for helpful discussions.

##  Appendix A Perfect powers in base $x$ and polynomial powers

In this Appendix, we will apply Lemma 5 on lacunary polynomial powers to study
perfect powers in a given base $x$ having exactly $k$ non-zero digits, using
(a part of) a method developed by Corvaja and Zannier in [2]. First, notice
that, dividing by a power of $x$, we can assume without loss of generality
that the units digit is non-zero, obtaining the Diophantine equation

(5) $y^{d}=c_{0}+\sum_{i=1}^{k-1}c_{i}x^{m_{i}},$

with fixed $k\in\mathbb{N}$, $y,d,x$ positive integers greater than $1$,
$c_{0},c_{1},\dots,c_{k-1}\in\\{1,\dots,x-1\\}$ and $m_{1}<\dots<m_{k-1}$
positive integers. This problem is actually quite complex; to get a feel of
its difficulty, notice that the case $k=2,c_{0}=c_{1}=1$ is the well-known
Catalan Conjecture, which stood open for more than a century and was proved by
Mihailescu in [10].

Here, we describe Corvaja and Zannier’s method. Recall that the logarithmic
Weil height of a rational number $\frac{a}{b}\in\mathbb{Q}$ in lowest terms is
defined as $h\left(\frac{a}{b}\right)=\log\max\\{|a|,|b|\\}$, with the
assumption that $h(0)=0$. The absolute logarithmic Weil height of an element
$\alpha$ in a number field $K$ is defined as

$h(\alpha)=\frac{1}{[K:\mathbb{Q}]}\sum_{v\in
M_{K}}[K_{v}:\mathbb{Q}_{v}]\log\max\\{||\alpha||_{v},1\\},$

where $M_{K}$ is a normalized set of inequivalent absolute values defined on
$K$. Further, the Weil height of a point $P=[\alpha_{0}:\ldots:\alpha_{n}]$ in
a projective space $\mathbb{P}_{n}(K)$ as

$h(P)=\frac{1}{[K:\mathbb{Q}]}\sum_{v\in
M_{K}}[K_{v}:\mathbb{Q}_{v}]\log\max_{0\leq i\leq n}\\{||\alpha||_{v}\\}.$

Moreover, if $S\subset M_{K}$ is a finite set of absolute values of $K$
containing the archimedean ones $S_{\infty}$, we will say that $x\in K$ is a
$S$-integer if $|x|_{v}\leq 1$ for every $v\not\in S$, and denote the ring of
$S$-integer elements of $K$ by $\mathcal{O}_{S,K}$. Invertible elements in
$\mathcal{O}_{S,K}$ are called $S$-units (see [1], [3]), and several results
in the literature deal with properties and distributions of $S$-integral
points. In particular, our problem also falls in this category.

We will consider the following cases:
First case: Let $C_{k-2}\in]0,1[$ be a constant, and assume that there is a
linear gap between the two leftmost non-zero digits, that is, $m_{k-1}\leq
C_{k-2}m_{k-2}$.

Dividing equation (5) by $x^{m_{k-1}}$, with the positions
$n_{i}=m_{k-1}-m_{k-1-i}$, for $i=1,\dots,k-2$, $n_{k-1}=m_{k-1}$, and
$x_{i}=x^{-n_{i}}$ for $i=1,\dots,k-1$, we obtain

$y^{d}x^{-m_{k-1}}=c_{0}+\sum_{i=1}^{k-1}c_{i}x_{i}.$

Define now the series
$F(X_{1},\dots,X_{k-1})\in\mathbb{Q}[\\![X_{1},\dots,X_{k-1}]\\!]$ obtained
applying the Binomial Theorem

$F(X_{1},\dots,X_{k-1}):=\left[c_{0}+\sum_{i=1}^{k-1}c_{i}X_{i}\right]^{\frac{1}{d}}=c_{0}^{\frac{1}{d}}\left[1+\sum_{i=1}^{k-1}\frac{c_{i}}{c_{0}}X_{i}\right]^{\frac{1}{d}}=$
$=c_{0}^{\frac{1}{d}}\left[1+\frac{1}{d}\left(\sum_{i=1}^{k-1}\frac{c_{i}}{c_{0}}X_{i}\right)+\frac{1-d}{2d^{2}}\left(\sum_{i=1}^{k-1}\frac{c_{i}}{c_{0}}X_{i}\right)^{2}+\dots\right].$

This expression converges absolutely if
$\displaystyle\sum_{i=1}^{k-1}\frac{c_{i}}{c_{0}}X_{i}<1$, then, for instance,
noticing that $c_{i}\leq x-1$ for $i=0,\dots,k-1$, it converges absolutely for
$X_{1},\dots,X_{k-1}\in\mathbb{C}$ such that $|X_{i}|<\frac{1}{(k-1)(x-1)}$,
to a function, which we will denote by (slightly abusing our notation) $F$,
that takes the value $c_{0}^{\frac{1}{d}}$ at the origin and is such that
$\displaystyle F(X_{1},\dots,X_{k-1})^{d}=c_{0}+\sum_{i=1}^{k-1}c_{i}X_{i}$.
Since $n_{k-1}>n_{k-2}>\dots>n_{1}=m_{k-1}-m_{k-2}\geq(1-C_{k-2})m_{k-1}$, for
sufficiently large values of $m_{k-1}$ we have

$x^{-n_{k-1}}=x^{-m_{k-1}}\leq\frac{1}{(k-1)(x-1)},$

thus the series converges at $(x_{1},\dots,x_{k-1})$; moreover, taking
$z=F(x_{1},\dots,x_{k-1})$, this yields

$z^{d}=c_{0}+c_{1}x^{-n_{1}}+\dots+c_{k-1}x^{-n_{k-1}}.$

Let $K$ be the splitting field of $Y^{d}-x$ over $\mathbb{Q}$; since
$z=yx^{-\frac{m_{k-1}}{d}}$, our sequence of solutions is defined over $K$.
Further, if $S$ is the finite set of places defined over $K$ consisting of the
ones lying over either $\infty$ or $x$; then, by definition, $z$ is an
$S$-integer, while $x_{1},\dots,x_{k-1}$ are $S$-units. Moreover, the usual
absolute value on $\mathbb{C}$ induces an absolute value on $\mathbb{Q}(z)$,
which we can further extend to an infinite place $v$ defined over $K$; thus,
embedding $K$ in $\mathbb{C}$ by means of $v$ we obtain that
$z=F(x_{1},\dots,x_{k-1})$ also with respect to $v$-adic convergence.

It is easy to check that
$\displaystyle\sum_{i=1}^{k-1}h(x_{i})\leq(k-1)m_{k-1}$; further, since we
have $\max_{i}|x_{i}|_{v}\leq x^{-(1-C_{k-2})m_{k-1}}$, it follows that

$\sum_{i=1}^{k-1}h(x_{i})=O(-\log(\max_{i}|x_{i}|_{v})),$

whence the convergence implies that $h(z)=h(F(x_{1},\dots,x_{k-1}))\leq
2m_{k-1}$. Hence, we fall under the assumptions of the following theorem.

######  Theorem 20 ([3, Theorem 1]).

Let $K$ be a number field, $v$ a place defined over $K$ and let $C_{v}$ a
completion of an algebraic closure of $K_{v}$. Let $S$ be a finite set of
absolute values of $K$ containing $S_{\infty}$, and define the $S$-height
$h_{s}(x)=\sum_{v\not\in S}\log^{+}|x|_{v}$ of a non-zero element $x\in
K^{*}$.

Next, let $f(X)=\displaystyle\sum_{i}a_{i}X^{i}$ be a power series with
algebraic coefficients in $C_{v}$ converging in a neighborhood of the origin
in $C_{v}^{n}$; let $x_{h}=(x_{h1},\dots,x_{hn})$, $h\in\mathbb{N}$ be a
sequence in $(K^{*})^{n}$ tending to the origin of $K_{v}^{n}$, such that
$f(x_{h})$ is well defined and belongs to $K$.

Suppose that:

  1. (1)

For $i=1,\dots,n$ we have $h_{s}(x_{hi})+h_{s}(x_{hi}^{-1})=o(h(x_{hi}))$ as
$h\rightarrow+\infty$;

  2. (2)

$h(x_{h})=O(-\log(\max_{i}|x_{hi}|_{v}))$;

  3. (3)

$h_{s}(f(x_{h}))=o(h(x_{h}))$;

  4. (4)

$h(f(x_{h}))=O(h(x_{h}))$.

Then there exist a finite number of cosets
$u_{1}H_{1},\dots,u_{r}H_{r}\in\mathbb{G}_{m}^{n}$ such that
$\\{x_{h}\\}\subset\bigcup_{i=1}^{r}u_{i}H_{i}$ and such that, for
$i=1,\dots,r$, the restriction of $f(X)$ to $u_{i}H_{i}$ coincides with a
polynomial in $K[X]$.

Thus there are a finite number of cosets
$u_{1}H_{1},\dots,u_{r}H_{r}\in\mathbb{G}_{m}^{n}$ such that our sequence of
solutions belongs to the union of these cosets, and such that for
$i=1,\dots,r$ the restriction of $F(X)$ to $u_{i}H_{i}$ coincides with a
polynomial. Then, since the elements of our sequence are $S$-units, we can use
the following known theorem.

######  Theorem 21 ([1, Theorem 7.4.7]).

Let $\mathbb{Q}^{\times}$ be the multiplicative group of units of
$\overline{\mathbb{Q}}$, and let $\Gamma$ be a finitely generated subgroup of
$(\overline{\mathbb{Q}^{\times}})^{n}$; let $\Sigma$ be a subset of $\Gamma$.

Then the Zariski closure of $\Sigma$ in $\mathbb{G}_{m}^{n}$ is a finite union
of translates of algebraic subgroups of $\mathbb{G}_{m}^{n}$.

In our setting, Theorem 21 states that the Zariski closure of our sequence is
a certain finite union of translates of algebraic subgroups of
$\mathbb{G}_{m}^{n}$. Then, going to an appropriate infinite subsequence of
solutions (and by taking intersection with one of our cosets), we can assume
that there is a single coset $uH$ containing all our solutions, where
$u=(\chi_{1},\dots,\chi_{k-1})\in\mathbb{G}_{m}^{k-1}$ is a solution of our
sequence (thus $\chi_{i}\in x^{\mathbb{Z}}$, with negative exponent), and that
our sequence is Zariski-dense in said coset. Clearly, this coset cannot be a
single point, therefore $s:=\dim H>0$; since our sequence converges
$v$-adically to the origin in $uH$, the following proposition delivers the
promised relation between this problem and lacunary polynomial powers.

######  Proposition 22 ([3, Proposition 1]).

Let $H$ be a connected algebraic subgroup of $\mathbb{G}_{m}^{n}$. Then the
following conditions are equivalent.

  1. (1)

The Zariski closure of $H$ in $\mathbb{A}^{n}$ contains $(0,\dots,0)$.

  2. (2)

The lattice $\Lambda_{H}$ does not contain any non-zero vectors with all non-
negative coordinates.

  3. (3)

There exists a parametrization $\varphi:\mathbb{G}_{m}^{k}\rightarrow H$, with
$k=\dim H$, given by $X_{i}=T^{u_{i}},i=1,\dots,n,T=(T_{1},\dots,T_{k})$,
where all coordinates of $u_{i}\in\mathbb{Z}^{k}$ are strictly positive.

  4. (4)

There exists a point $(x_{1},\dots,x_{n})\in H\cap C_{v}^{n}$, where
$C_{v}^{n}$ is as in Theorem 20, such that $|x_{i}|_{v}<1$ for $i=1,\dots,n$.

  5. (5)

There exists a sequence in $H\cap C_{v}^{n}$ converging to $(0,\dots,0)$ in
the $v$-adic topology.

Our sequence satisfies the fifth condition of Proposition 22; then, every
condition holds in our coset $uH$. In particular, the third one states that
there exists a parametrization of $uH$ of the form
$X_{i}=\tilde{\xi}_{i}T_{1}^{a_{i1}}\dots T_{s}^{a_{is}},$ with
$i=1,\dots,k-1$ and $a_{ij}\geq 0$ for every $i,j$. Moreover, Theorem 20
ensures that $F(X_{1},\dots,X_{k-1})$ becomes, with this parametrization of
$uH$, a polynomial in the indeterminates $T_{1},\dots,T_{s}$. Since
$F^{d}(x_{1},\dots,x_{k-1})=c_{0}+c_{1}x_{1}+\dots+c_{k-1}x_{k-1}$, and our
sequence of solutions is Zariski-dense in $uH$, we obtain a polynomial
identity of the shape

$F^{d}(X_{1},\dots,X_{k-1})=c_{0}+\sum_{i=1}^{k-1}c_{i}\tilde{\xi}_{i}T_{1}^{a_{i1}}\dots
T_{s}^{a_{is}}.$

Since our sequence converges $v$-adically to $(0,\dots,0)$, the vectors
$\boldsymbol{a}_{i}=(a_{i1},\dots,a_{is})\in\mathbb{N}^{s}$ are non-zero,
hence there is a vector
$\boldsymbol{b}=(b_{1},\dots,b_{s}),b_{i}\in\mathbb{Z}^{+}$ such that the
scalar products $l_{i}:=\boldsymbol{b}\boldsymbol{a}_{i}$ are all positive and
$l_{i}=l_{j}$ if and only if $\boldsymbol{a}_{i}=\boldsymbol{a}_{j}$. Thus,
replacing $T_{j}$ with $T^{b_{j}}$, for $j=1,\dots,s$,
$F(X_{1},\dots,X_{k-1})$ becomes a non-constant polynomial
$P(T)\in\mathbb{C}[T]$ such that the following identity holds (dividing by
$c_{0}$ if needed):

(6) $P(T)^{d}=1+\sum_{i=1}^{k-1}\xi_{i}T^{l_{i}}.$

At this stage, notice that, following these substitutions, our coefficients
$\xi_{i}$ are such that $\xi_{i}\in\mathcal{C}_{x}=\\{\frac{px^{q}}{r}\ |\
p,r\in\\{1,\dots,x-1\\},q\in\mathbb{Z}^{-}\\}$, and that $l_{1}\leq l_{2}\leq
l_{3}\leq l_{4}$ are positive integers, associated to the $n_{i}$ (not
necessarily in the same order), such that $l_{i}=l_{j}$ implies
$\xi_{i}\neq\xi_{j}$. Therefore, we can use classification results for
lacunary polynomial powers with complex coefficients to solve equation (6),
and then check for every solution whether the coefficients $\xi_{i}$ belong to
$\mathcal{C}_{x}$; after that, we can then pull back some useful information
that will allow us to solve the original equation (5). However, before this,
we will briefly outline, for the sake of simplicity (since the proof is
completely analogous), how such a relation can be built in the other setting,
that is, in a way, symmetric to the one we have considered in this case, where
the extremal gap involves the rightmost digits rather than the leftmost ones.
This exposition is necessary since we will write explicitly these relations in
the following.
Second case: Let $C_{1}\in]0,1[$ be a constant, and assume that there is a
linear gap between the two rightmost non-zero digits, that is, $m_{1}\geq
C_{1}m_{k-1}$ (namely, the first leftmost non-zero digit after the units one
grows linearly with the length of our perfect power).

Let $x_{i}=x^{m_{i}}$; then

$y^{d}=c_{0}+\sum_{i=1}^{k-1}c_{i}x_{i}.$

Then, in a similar fashion as in the first case, we can reduce, with some
analogous parametrization, this equation to the same polynomial identity (6),
with $\xi_{i}\in\mathcal{C}_{x}.$

We now study equation (6). Lemma 5 allows us to solve this polynomial equation
under the assumption $k\leq 5$; clearly, since the cases $k=3$ and $k=4$ have
already been investigated by Corvaja and Zannier, we will focus on the next
case $k=5$; further, we will assume for simplicity that all the non-zero
digits of the perfect powers in equation (5) are equal to $1$, that is,
$c_{0}=\dots=c_{k-1}=1$, although this method can be extended to deal with the
other cases with some tedious calculations. Then
$\mathcal{C}_{x}=x^{\mathbb{Z}^{-}}$, and all coefficients $\xi_{i}$ must be
perfect powers of $x$ with negative exponent.

Therefore, we have to examine the tables described in Lemma 5; our aim is to
rewrite the polynomials contained therein as polynomials with at most five
terms, whose degrees are not necessarily different, and with coefficients
belonging to $x^{\mathbb{Z}^{-}}$:

  * •

Table 1: Here $P(T)^{d}$ has exactly five terms, hence we must have
$l_{1}<l_{2}<l_{3}<l_{4}$ and $\xi_{i}\in x^{\mathbb{Z}}$ for every
$i=1,\dots,4$. Since the coefficients $\xi_{i}$ must be positive, only the
first solution is admissible; however, since $\xi_{i}\in x^{\mathbb{Z}}$, for
that case we would obtain $\frac{3}{8}=\frac{\xi_{2}}{\xi_{1}^{2}}\in
x^{\mathbb{Z}}$, which is impossible.

  * •

Table 2: In this case, all coefficients are depending on $\xi_{1},\xi_{2}$.
Thus, taking $\xi_{1}=x^{a}$, $\xi_{2}=x^{b}$, the condition $\xi_{3}\in
x^{\mathbb{Z}}$ implies that
$\xi_{3}=\xi_{1}\left(\frac{4\xi_{2}-\xi_{1}^{2}}{8}\right)\in
x^{\mathbb{Z}}$, that is $\frac{4x^{b}-x^{2a}}{8}=x^{c}$ for some
$c\in\mathbb{Z}$ (such that $\xi_{3}=x^{c+a}$), or equivalently
$\frac{4x^{b-2a}-1}{8}=x^{c-2a}$. However, it is easy to see that if $x\neq 2$
the left-hand side of the equation cannot belong to $x^{\mathbb{Z}}$; on the
other hand, if $x=2$, the equation becomes $2^{b+2}-2^{2a}=2^{c+3}$, whose
solutions are $c+3=2a$ and $b+2=2a+1$, that is $b=2a-1$, $c=2a-3$, yielding
the coefficients $\xi_{2}=\frac{1}{2}\xi_{1}^{2}$,
$\xi_{3}=\frac{1}{8}\xi_{1}^{3}$ and
$\xi_{4}=\left(\frac{\xi_{3}}{\xi_{1}}\right)^{2}=\frac{1}{64}\xi_{1}^{4}$.
Therefore, we obtain the polynomial

$P(T)=1+\frac{1}{2}\xi_{1}T^{l_{1}}+\frac{1}{8}\xi_{1}^{2}T^{2l_{1}},\ \ \ \
P(T)^{2}=1+\xi_{1}T^{l_{1}}+\frac{1}{2}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{8}\xi_{1}^{3}T^{3l_{1}}+\frac{1}{64}\xi_{1}^{4}T^{4l_{1}}.$

  * •

Table 3: In this case we have
$P(T)^{d}=1+\xi^{\prime}_{1}T^{l^{\prime}_{1}}+\xi^{\prime}_{2}T^{l^{\prime}_{2}}+\xi^{\prime}_{3}T^{l^{\prime}_{3}}$
(hence exactly two among the $l_{i}$ are equal), with
$\xi^{\prime}_{1},\xi^{\prime}_{2},\xi^{\prime}_{3}$ such that exactly two of
them belong to $x^{\mathbb{Z}}$ while the other one is a sum of two elements
of $x^{\mathbb{Z}}$. Therefore, at least one between
$\frac{1}{3}=\frac{\xi^{\prime}_{2}}{(\xi^{\prime}_{1})^{2}}$ and
$\frac{1}{27}=\frac{\xi^{\prime}_{3}}{(\xi^{\prime}_{1})^{3}}=\frac{(\xi^{\prime}_{3})^{2}}{(\xi^{\prime}_{2})^{2}}$
must belong to $x^{\mathbb{Z}}$: this implies that $x$ is a power of $3$.
Obviously, any solution of this form follows from a solution in base $3$,
hence we can safely assume that $x=3$. But if at least two among
$\xi^{\prime}_{1},\xi^{\prime}_{2},\xi^{\prime}_{3}$ belong to
$3^{\mathbb{Z}}$, from the relations written in the table we easily deduce
that they must all belong $3^{\mathbb{Z}}$; since one of these is obtained as
sum of two $\xi_{i}$ (which belong to $3^{\mathbb{Z}}$), we obtain the
equation $3^{a}+3^{b}=3^{c}$, which has no solution for $a,b,c\in\mathbb{Z}$.

  * •

Table 4: In this last case
$P(T)^{d}=1+\xi^{\prime}_{1}T^{l^{\prime}_{1}}+\xi^{\prime}_{2}T^{l^{\prime}_{2}}$,
$d=2$ and $\xi^{\prime}_{2}=\left(\frac{1}{2}\xi^{\prime}_{1}\right)^{2}$.
Hence, there are three ways in which the four coefficients $\xi_{i}$ (and the
associated exponents $l_{i}$) can combine to form the two $\xi^{\prime}_{i}$,
namely:

    1. (1)

$\xi^{\prime}_{1}$ is obtained as a sum of three $\xi_{i}$, and
$\xi^{\prime}_{2}=\xi_{j}\in x^{\mathbb{Z}}$;

    2. (2)

$\xi^{\prime}_{2}$ is obtained as a sum of three $\xi_{i}$, and
$\xi^{\prime}_{1}=\xi_{j}\in x^{\mathbb{Z}}$;

    3. (3)

$\xi^{\prime}_{1},\xi^{\prime}_{2}$ are both obtained as a sum of two
$\xi_{i}$ each.

As $\xi_{i}\in x^{\mathbb{Z}}$, we can write $\xi_{i}=x^{\sigma_{i}}$, with
$\sigma_{i}\in\mathbb{Z}$. Thus, these three cases give us (rearranging the
indexes if needed) the following equations:

    1. (1)

$\frac{1}{4}(x^{\sigma_{1}}+x^{\sigma_{2}}+x^{\sigma_{3}})^{2}=x^{\sigma_{4}}$,
that is $(x^{\sigma_{1}}+x^{\sigma_{2}}+x^{\sigma_{3}})^{2}=4x^{\sigma_{4}};$

    2. (2)

$\frac{1}{4}(x^{\sigma_{1}})^{2}=x^{\sigma_{2}}+x^{\sigma_{3}}+x^{\sigma_{4}}$,
or equivalently that
$x^{2\sigma_{1}}=4x^{\sigma_{2}}+4x^{\sigma_{3}}+4x^{\sigma_{4}};$

    3. (3)

$\frac{1}{4}(x^{\sigma_{1}}+x^{\sigma_{2}})^{2}=x^{\sigma_{3}}+x^{\sigma_{4}}$,
which yields
$x^{2\sigma_{1}}+x^{2\sigma_{2}}+2x^{\sigma_{1}+\sigma_{2}}=4x^{\sigma_{3}}+4x^{\sigma_{4}}.$

Let us study each case separately:

    1. (1)

Assume without loss of generality that $\sigma_{1}>\sigma_{2}>\sigma_{3}.$
Then the left-hand side yields an integer whose base $x$ representation has at
least two non-zero digits, one at place $2\sigma_{3}$ and one at place
$2\sigma_{1}\geq 2\sigma_{3}+4$ or higher, while the one on right-hand side
has either one or two digits (only if $x=3$), which are, however, consecutive:
therefore this equation admits no solution.

    2. (2)

Similarly, the left-hand side of this equation yields an integer whose base
$x$ representation has exactly one non-zero digit, whence the one on the
right-hand side has at least two: again, this equation admits no solution.

    3. (3)

In this case, notice that if $x\geq 4$, the left-hand side yields an integer
whose base $x$ representation has exactly three non-zero digits, while the
right-hand side has exactly two: thus $x\in\\{2,3\\}$.

      1. (a)

If $x=3$, we have $3^{2\sigma_{1}}+3^{2\sigma_{2}}+2\cdot
3^{\sigma_{1}+\sigma_{2}}=4\cdot 3^{\sigma_{3}}+4\cdot 3^{\sigma_{4}};$ assume
without loss of generality that $\sigma_{1}>\sigma_{2}$ and
$\sigma_{3}>\sigma_{4}.$ Then $3^{2\sigma_{1}}+2\cdot
3^{\sigma_{1}+\sigma_{2}}+3^{2\sigma_{2}}=3^{\sigma_{3}+1}+3^{\sigma_{3}}+3^{\sigma_{4}+1}+3^{\sigma_{4}};$
clearly, since the base $3$ representation of an integer must be unique, we
must have

$\begin{cases}\sigma_{3}=\sigma_{4}+1\\\ 2\sigma_{2}=\sigma_{4}\\\
2\sigma_{1}=\sigma_{3}+1\end{cases}\text{ and this implies
}\begin{cases}\sigma_{1}=\sigma_{2}+1\\\ \sigma_{3}=2\sigma_{2}+1\\\
\sigma_{4}=2\sigma_{2}\end{cases}.$

Then, rearranging those $\sigma_{i}$ in increasing order, and computing the
associated coefficients $\xi_{i}$, we obtain

$P(T)^{2}=1+\xi_{1}T^{l_{1}}+3\xi_{1}T^{l_{1}}+\xi_{1}^{2}T^{2l_{1}}+3\xi_{1}^{2}T^{2l_{1}}.$

      2. (b)

If $x=2$ we obtain
$2^{2\sigma_{1}}+2^{2\sigma_{2}}+2^{\sigma_{1}+\sigma_{2}+1}=2^{\sigma_{3}+2}+2^{\sigma_{4}+2};$
again, we can assume without loss of generality that $\sigma_{1}>\sigma_{2}$
and $\sigma_{3}>\sigma_{4}.$ These two base $2$ representation define the same
integer, and thus must coincide. Thus we have

$\begin{cases}\sigma_{1}+\sigma_{2}+1=2\sigma_{1}\\\
2\sigma_{2}=\sigma_{4}+2\\\ 2\sigma_{1}+1=\sigma_{3}+2\end{cases}\text{
yielding }\begin{cases}\sigma_{1}=\sigma_{2}+1\\\ \sigma_{3}=2\sigma_{2}+1\\\
\sigma_{4}=2\sigma_{2}-2\end{cases},$

which, rearranging the $\sigma_{i}$ in increasing order and computing the
coefficients $\xi_{i}$, defines the solution

$P(T)^{2}=1+\xi_{1}T^{l_{1}}+2\xi_{1}T^{l_{1}}+\frac{1}{4}\xi_{1}^{2}T^{2l_{1}}+2\xi_{1}^{2}T^{2l_{1}}.$

Therefore, the only solutions to the equation

$P(T)^{d}=1+\xi_{1}T^{l_{1}}+\xi_{2}T^{l_{2}}+\xi_{3}T^{l_{3}}+xi_{4}T^{l_{4}},$

with $\xi_{i}\in x^{\mathbb{Z}}$ are the following:

  1. (1)

$x=3,d=3,P(T)^{2}=1+\xi_{1}T^{l_{1}}+3\xi_{1}T^{l_{1}}+\xi_{1}^{2}T^{2l_{1}}+3\xi_{1}^{2}T^{2l_{1}};$

  2. (2)

$x=2,d=2,P(T)^{2}=1+\xi_{1}T^{l_{1}}+\frac{1}{2}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{8}\xi_{1}^{3}T^{3l_{1}}+\frac{1}{64}\xi_{1}^{4}T^{4l_{1}};$

  3. (3)

$x=2,d=2,P(T)^{2}=1+\xi_{1}T^{l_{1}}+2\xi_{1}T^{l_{1}}+\frac{1}{4}\xi_{1}^{2}T^{2l_{1}}+2\xi_{1}^{2}T^{2l_{1}}.$

As before, our parametrization induces the correspondence

$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}}\mapsto
P(T)=1+\xi_{1}T^{l_{1}}+\xi_{2}T^{l_{2}}+\xi_{3}T^{l_{3}}+\xi_{4}T^{l_{4}},$

We can then go back to our two settings, and deduce the associated solutions
of the equation

$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}}$

via our parametrizations.
First case: Remember that, in this setting, from our parametrizations we
obtain the following correspondences

$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}}\mapsto
z^{d}=1+x^{-n_{1}}+x^{-n_{2}}+x^{-n_{3}}+x^{-n_{4}}$ $\mapsto
P(T)=1+\xi_{1}T^{l_{1}}+\xi_{2}T^{l_{2}}+\xi_{3}T^{l_{3}}+\xi_{4}T^{l_{4}}.$

Therefore, each term of our polynomial is associated to a perfect power
$x^{-n_{i}}$, which in turn will be used to compute the $x^{m_{i}}$. Let us
study now the three solutions described before:

  1. (1)

$x=3,d=3,P(T)^{2}=1+\xi_{1}T^{l_{1}}+3\xi_{1}T^{l_{1}}+\xi_{1}^{2}T^{2l_{1}}+3\xi_{1}^{2}T^{2l_{1}}.$

Hence there exists a permutation
$\\{n^{\prime}_{1},n^{\prime}_{2},n^{\prime}_{3},n^{\prime}_{4}\\}$ of the
exponents $n_{i}$ such that

$\begin{cases}3^{-n^{\prime}_{1}}\mapsto\xi_{1}T^{l_{1}},\\\
3^{-n^{\prime}_{2}}\mapsto 3\xi_{1}T^{l_{1}},\\\
3^{-n^{\prime}_{3}}\mapsto\xi_{1}^{2}T^{2l_{1}},\\\ 3^{-n^{\prime}_{4}}\mapsto
3\xi_{1}^{2}T^{2l_{1}},\end{cases}\text{ which implies
}\begin{cases}n^{\prime}_{1}\in\mathbb{Z}^{+},\\\
-n^{\prime}_{2}=(-n^{\prime}_{1})+1,\\\ -n^{\prime}_{3}=2(-n^{\prime}_{1}),\\\
-n^{\prime}_{4}=2(-n^{\prime}_{1})+1.\end{cases}.$

Clearly, $n^{\prime}_{2}<n^{\prime}_{1}<n^{\prime}_{4}<n^{\prime}_{3}$, thus
the relations between the $n_{i}$ yield $n_{1}=n^{\prime}_{2}$,
$n_{2}=n^{\prime}_{1}$, $n_{3}=n^{\prime}_{4}$ and $n_{4}=n^{\prime}_{3}$;
thus, by substituting the values of $m_{i}$ and solving in function of $m_{1}$
we obtain

$\begin{cases}m_{2}\in\mathbb{Z}^{+},\\\ (m_{4}-m_{2})=(m_{4}-m_{3})+1,\\\
(m_{4}-m_{1})=2(m_{4}-m_{3})+1,\\\ m_{4}=2(m_{4}-m_{3})+2,\end{cases}\text{
yielding }\begin{cases}m_{1}=1,\\\ m_{2}\in\mathbb{Z}^{+},\\\
m_{3}=m_{2}+1,\\\ m_{4}=2m_{2}.\end{cases},$

giving the infinite family of solutions defined by $d=2$, $x=3$ and

$(m_{1},m_{2},m_{3},m_{4})=(1,m_{2},m_{2}+1,2m_{2}),y=3^{m_{2}}+2.$

  2. (2)

$x=2,d=2,P(T)^{2}=1+\xi_{1}T^{l_{1}}+\frac{1}{2}\xi_{1}^{2}T^{2l_{1}}+\frac{1}{8}\xi_{1}^{3}T^{3l_{1}}+\frac{1}{64}\xi_{1}^{4}T^{4l_{1}}.$

Again, there is a permutation $\\{n^{\prime}_{1},\dots,n^{\prime}_{4}\\}$ of
the exponents $n_{i}$ such that

$\begin{cases}2^{-n^{\prime}_{1}}\mapsto\xi_{1}T^{l_{1}},\\\
2^{-n^{\prime}_{2}}\mapsto\frac{1}{2}\xi_{1}^{2}T^{2l_{1}},\\\
2^{-n^{\prime}_{3}}\mapsto\frac{1}{8}\xi_{1}^{3}T^{3l_{1}},\\\
2^{-n^{\prime}_{4}}\mapsto\frac{1}{64}\xi_{1}^{4}T^{4l_{1}},\end{cases}\text{
thus implying }\begin{cases}n^{\prime}_{1}\in\mathbb{Z}^{+},\\\
-n^{\prime}_{2}=2(-n^{\prime}_{1})-1,\\\
-n^{\prime}_{3}=3(-n^{\prime}_{1})-3,\\\
-n^{\prime}_{4}=4(-n^{\prime}_{1})-6.\end{cases}$

This time we have
$n^{\prime}_{1}<n^{\prime}_{2}<n^{\prime}_{3}<n^{\prime}_{4}$, hence
$n_{i}=n^{\prime}_{i}$ for every $i$, and this system yields a linear system
in the exponents $m_{i}$, which we can solve in function of $m_{1}$, obtaining

$\begin{cases}-(m_{4}-m_{2})=-2(m_{4}-m_{3})-1,\\\
-(m_{4}-m_{1})=-3(m_{4}-m_{3})-3,\\\
-m_{4}=-4(m_{4}-m_{3})-6,\end{cases}\text{ and then
}\begin{cases}m_{2}=2m_{1}-1,\\\ m_{3}=3m_{1}-3,\\\
m_{4}=4m_{1}-6,\end{cases},$

that gives the infinite family of solutions described by $d=2$, $x=2$ and

$(m_{1},m_{2},m_{3},m_{4})=(m_{1},2m_{1}-1,3m_{1}-3,4m_{1}-6),y=1+2^{m_{1}-1}+2^{2m_{1}-3}.$

  3. (3)

$x=2,d=2,P(T)^{2}=1+\xi_{1}T^{l_{1}}+2\xi_{1}T^{l_{1}}+\frac{1}{4}\xi_{1}^{2}T^{2l_{1}}+2\xi_{1}^{2}T^{2l_{1}}.$

Thus, there exists a permutation
$\\{n^{\prime}_{1},n^{\prime}_{2},n^{\prime}_{3},n^{\prime}_{4}\\}$ of the
exponents $n_{i}$ such that

$\begin{cases}2^{-n^{\prime}_{1}}\mapsto\xi_{1}T^{l_{1}},\\\
2^{-n^{\prime}_{2}}\mapsto 2\xi_{1}T^{l_{1}},\\\
2^{-n^{\prime}_{3}}\mapsto\frac{1}{4}\xi_{1}^{2}T^{2l_{1}},\\\
2^{-n^{\prime}_{4}}\mapsto 2\xi_{1}^{2}T^{2l_{1}},\end{cases}\text{ which
implies }\begin{cases}n^{\prime}_{1}\in\mathbb{Z}^{+},\\\
-n^{\prime}_{2}=(-n^{\prime}_{1})+1,\\\
-n^{\prime}_{3}=2(-n^{\prime}_{1})-2,\\\
-n^{\prime}_{4}=2(-n^{\prime}_{1})+1.\end{cases}$

This time we have
$n^{\prime}_{2}<n^{\prime}_{1}<n^{\prime}_{4}<n^{\prime}_{3}$, thus
$n_{1}=n^{\prime}_{2}$, $n_{2}=n^{\prime}_{1}$, $n_{3}=n^{\prime}_{4}$ and
$n_{4}=n^{\prime}_{3}$; again, by substituting these $n_{i}$ and solving in
function of $m_{1}$ we get

$\begin{cases}m_{2}\in\mathbb{Z}^{+},\\\ (m_{4}-m_{2})=(m_{4}-m_{3})+1,\\\
(m_{4}-m_{1})=2(m_{4}-m_{3})-3,\\\ m_{4}=2(m_{4}-m_{3}),\end{cases}\text{
which yields }\begin{cases}m_{1}=3,\\\ m_{2}\in\mathbb{Z}^{+},\\\
m_{3}=m_{2}+1,\\\ m_{4}=2m_{2}-2,\end{cases},$

giving the infinite family of solutions described by $d=2$, $x=2$ and

$(m_{1},m_{2},m_{3},m_{4})=(3,m_{2},m_{2}+1,2m_{2}-2),y=2^{m_{2}-1}+3.$

We have thus proved the following result.

######  Theorem 23.

The only infinite families of solutions to the equation
$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}},$ for $x,y,d$ positive
integers and $\boldsymbol{m}=(m_{1},m_{2},m_{3},m_{4})$ such that $x,d\geq 2$,
$m_{1}<m_{2}<m_{3}<m_{4}$ and $m_{3}\leq C_{3}m_{4},$ with $C_{3}\in]0,1[$
fixed, are the following:

  * •

$x=3,d=2,\boldsymbol{m}=(1,m_{2},m_{2}+1,2m_{2}),y=3^{m_{2}}+2;$

  * •

$x=2,d=2,\boldsymbol{m}=(m_{1},2m_{1}-1,3m_{1}-3,4m_{1}-6),y=1+2^{m_{1}-1}+2^{2m_{1}-3};$

  * •

$x=2,d=2,\boldsymbol{m}=(3,m_{2},m_{2}+1,2m_{2}-2),y=2^{m_{2}-1}+3.$

Second case: In this case, the correspondence obtained is easier, since we get

$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}}\mapsto
P(T)=1+\xi_{1}T^{l_{1}}+\xi_{2}T^{l_{2}}+\xi_{3}T^{l_{3}}+\xi_{4}T^{l_{4}}.$

Since this time each term of $P(T)$ gives a perfect power $x^{m_{i}}$, we can
immediately deduce the solutions:

  1. (1)

$x=2,d=2,(m_{1},2m_{1}-1,3m_{1}-3,4m_{1}-6),y=1+2^{m_{1}-1}+2^{2m_{1}-3};$

  2. (2)

$x=3,d=2,(m_{1},m_{1}+1,2m_{1},2m_{1}+1),y=2\cdot 3^{m_{1}}+1;$

  3. (3)

$x=2,d=2,(m_{1},m_{1}+1,2m_{1}-2,2m_{1}+1),y=1+2^{m_{1}-1}+2^{m_{1}}.$

Thus, we obtain the following result.

######  Theorem 24.

The only infinite families of solutions to the equation
$y^{d}=1+x^{m_{1}}+x^{m_{2}}+x^{m_{3}}+x^{m_{4}},$ for $x,y,d$ positive
integers and $\boldsymbol{m}=(m_{1},m_{2},m_{3},m_{4})$ such that $x,d\geq 2$,
$m_{1}<m_{2}<m_{3}<m_{4}$ and $m_{1}\geq C_{1}m_{4},$ with $C_{1}\in]0,1[$
fixed, are the following:

  * •

$x=2,d=2,\boldsymbol{m}=(m_{1},2m_{1}-1,3m_{1}-3,4m_{1}-6),y=1+2^{m_{1}-1}+2^{2m_{1}-3};$

  * •

$x=3,d=2,\boldsymbol{m}=(m_{1},m_{1}+1,2m_{1},2m_{1}+1),y=2\cdot 3^{m_{1}}+1;$

  * •

$x=2,d=2,\boldsymbol{m}=(m_{1},m_{1}+1,2m_{1}-2,2m_{1}+1),y=1+2^{m_{1}-1}+2^{m_{1}}.$

## References

  * [1] E. Bombieri, W. Grubler, _Heights in Diophantine Geometry_ , New Mathematical Monographs 4, Cambridge University Press, 2006.
  * [2] P. Corvaja, U. Zannier, Finiteness of odd perfect powers with four nonzero binary digits, _Annales de l’Institut Fourier_ 63, 2 (2013), p. 715-731.
  * [3] P. Corvaja, U. Zannier, $S$-unit points on analytic hypersurfaces, _Ann. Sci. École Norm. Sup._ 38, 4 (2005) no. 1, p. 76-92.
  * [4] P. Corvaja, U. Zannier, Diophantine equations with power sums and Universal Hilbert Sets, _Indag. Mathem. N. S._ 9 (1998) no. 3, p. 317-332.
  * [5] P. Erdős, On the number of terms of the square of a polynomial, _Nieuw Archief voor Wiskunde_ 23 (1949) no. 2, p. 63-65.
  * [6] C. Fuchs, C. Karolus, Composite polynomials in linear recurrence sequences, Preprint.
  * [7] M. Garey, D. Johnson, Computers and Intractability. _A Guide to a NP-completeness Theory_, Freeman, San Francisco (1979).
  * [8] A. Geroldinger, I. Ruzsa, Additive group theory and non-unique factorizations. _Combinatorial number theory and additive group theory_ (2009),p. 1-86.
  * [9] A. Geroldinger, On the arithmetic of certain not integrally closed noetherian integral domains, Comm. Algebra 19(1991), p. 685–698.
  * [10] P. Mihailescu, Primary cyclotomics units and a proof of Catalan’s conjecture, _J. Reine Angew. Math._ 572 (2004), p. 167-195.
  * [11] A. Rényi, On the minimal number of terms of the square of a polynomial, _Hungarica Acta Mathematica_ 1 (1947), p. 30-34.
  * [12] I. Ruzsa, Sum of sets in several dimensions, _Combinatorica_ 14 (4) (1994), p. 485-490.
  * [13] A. Schinzel, _Polynomials with special regard to reducibility_ , Encyclopedia of Mathematics and its applications, Cambridge University Press, 2000.
  * [14] A. Schinzel, On the number of terms of a power of a polynomial, _Acta Arithmetica_ 49 (1) (1987), p. 55-70.
  * [15] A. Schinzel, U. Zannier, On the number of terms of a power of a polynomial, _Atti della Accademia Nazionale dei Lincei, Classe di Scienze Fisiche, Matematiche e Naturali, Rendiconti Lincei Matematica E Applicazioni_ 20 (1) (2009), p. 95-98.
  * [16] M. Yasumoto, Hilbert irreducibility sequences and nonstandard arithmetic, _J. Number Theory_ 26 (1987), p. 274-285.
  * [17] U. Zannier, On composite lacunary polynomials and the proof of a conjecture of Schinzel, _Inventiones mathematicae_ 174 (2008), p. 127-138.