Polynomials whose squares have few terms: an O(√k) construction for the Erdős–Rényi problem

For a polynomial P let T(P) denote the number of its non-zero coefficients, and let f(k) = min{T(P²) : T(P) = k}. Rényi and Erdős asked how small f(k) can be. Erdős showed f(k) < k^(1−c), Verdenius improved this to f(k) ≪ k^(log 8/log 13) (≈ k^0.811) along a sequence of values of k, and Schinzel and Zannier proved f(k) ≥ 2 + log(k−1)/log 8. We give an explicit family of polynomials with integer coefficients showing that f(k) < 4√(3(k+1)) + 25(k+1)^(1/4) for every k ≥ 30, so f(k) ≤ (4√3 + o(1))√k. Consequently, if T(P²) ≥ T(P)^ε held for all P, then necessarily ε ≤ 1/2. The construction rests on a non-trivial square root of 1 in the group ring ℚ[ℤ/Mℤ], lifted modulo (x^M − 1)², with M → ∞; we also determine the number of terms of the resulting squares exactly, which requires finding all integral points on an auxiliary elliptic curve. The same idea, with an explicit lift of l-th roots of 1, gives min{T(P^l) : T(P) = k} < l²√(2(l+1)k) + (l+1)l⁴ for every fixed l ≥ 2 and every k ≥ 2(l+1)l⁴.