Representation of powers by polynomials and the language of powers
Natalia Garcia‐Fritz · Journal of the London Mathematical Society · 2012
Given a field F and polynomials a and b in F[t], we prove that in general the sets {aλ+b : λ∈F} and {λ2+aλ+b : λ∈F} contain only finitely many powers and find bounds that are uniform from various points of view. We derive from this analysis various first-order definability and undecidability results. For example, we prove that there is no algorithm to decide whether or not an arbitrary system of linear equations over the integers, together with conditions of the form ‘x is a power’ and of the form ‘x is non-constant’ on some of the variables, has a solution in F[t].