Composite lacunary polynomials and the proof of a conjecture of Schinzel

Abstract

Let $g(x)$ be a fixed non-constant complex polynomial. It was conjectured by Schinzel that if $g(h(x))$ has boundedly many terms, then $h(x)\in \C[x]$ must also have boundedly many terms. Solving an older conjecture raised by Rényi and by Erdös, Schinzel had proved this in the special cases $g(x)=x^d$; however that method does not extend to the general case. Here we prove the full Schinzel's conjecture (actually in sharper form) by a completely different method. Simultaneously we establish an "algorithmic" parametric description of the general decomposition $f(x)=g(h(x))$, where $f$ is a polynomial with a given number of terms and $g,h$ are arbitrary polynomials. As a corollary, this implies for instance that a polynomial with $l$ terms and given coefficients is non-trivially decomposable if and only if the degree-vector lies in the union of certain finitely many subgroups of ${\mathbb{Z}}^l$.

9 pages

Cited by in corpus (12)

• Counting decomposable univariate polynomials
• Functional composition of polynomials: indecomposability, Diophantine equations and lacunary polynomials
• On the growth of linear recurrences in function fields
• On fewnomials, integral points and a toric version of Bertini's theorem
• A Polynomial Variant of Diophantine Triples in Linear Recurrences
• Perfect powers in polynomial power sums
• Composite polynomials in linear recurrence sequences
• Explicit bounds for composite lacunary polynomials
• Diophantine equations in separated variables and lacunary polynomials
• Decomposable polynomials in second order linear recurrence sequences
• Diophantine equations and the monodromy groups
• On the size of a linear combination of two linear recurrence sequences over function fields