Polynomial values are powers of two

Question

The initial question comes from Komal in 1999.

Namely it asks to show that for infinitely many $n$ there is a polynomial $f\in\mathbb{Q}[X]$ of degree $n$ such that $f(0),f(1),\dotsc,f(n+1)$ are distinct powers of $2$. This is equivalent to finding $(t_0,\dotsc,t_n)$ different positive integers such that $\displaystyle \sum_{i=0}^{n} (-1)^{n-i}\dbinom{n+1}{i} 2^{t_i}$ is a power of $2$.

We could ask something more: Is it true that there exists $c_n$ and we can bound it in terms of $n$ such that for all $f\in\mathbb{Q}[X]$ of degree $n$ we have that $f(0),f(1),\dotsc, f(c_n)$ cannot all be powers of $2$? The existence of $c_n$ and that it is bounded in terms of $n$ follows from a strengthened conjectural version of Falting's theorem for curves of the type $y^m=f(x)$. Can we say something unconjecturally about this? For $f(0),f(1),f(2),\dotsc, f(n)$ distinct powers of $2$ we can even construct $f\in\mathbb{Z}[X]$ thus $c_n\geq n+1$ always.

Answer 1

I'll prove a stronger statement.

Let $S$ be a finite set of primes. I claim there is a $c_{n,S}$ such that a polynomial $f$ with rational coefficients cannot take only values that are $S$-units on $\{1,\dots, c_{n,S}\}$.

Indeed, we can take $$c_{n, S} =(2n+1) \prod_{p \in S} p^{ \lfloor \log_p(n)\rfloor + 1}. $$

This is a polynomial in $n$ of degree $|S|+1$. In particular, in the original case $S =\{2\}$, this is quadratic in $n$.

Proof:

We can write $f(x) = a \prod_{i=1}^n (x-\alpha_i)$ for $\alpha_i \in \overline{\mathbb Q}$.

If $p^k> n$ then there exists $x_p \in (\mathbb Z/p^k)$ such that $x_p$ is not congruent mod $p^k$ to $\alpha_i$ for any $i$. If $y$ is congruent mod $p^k$ to $x_p$, it follows that $$ v_p(f(y)) = v_p(a) +\sum_{i=1}^n v_p(y -\alpha_i) = v_p(a) +\sum_{i=1}^n v_p(x_p -\alpha_i)$$ since $y-\alpha_i = (y-x_p) + (x_p-\alpha_i)$ and the first term is divisible by $p^k$ while the second is not, so the $p$-adic valuation is independent of $y$ in this congruence class.

We can take $k = \lfloor \log_p(n)\rfloor + 1$.

By the Chinese remainder theorem, the number of $a \in \{1, \dots, (2n+1) \prod_{p \in S} p^{ \lfloor \log_p(n)\rfloor + 1}\}$ such that $a$ is congruent to $x_p$ modulo $p^{\lfloor \log_p(n)\rfloor + 1}$ is $2n+1$.

All $2n+1$ values in this arithmetic progression have the same $p$-adic valuation for all $p \in S$. If they are all $S$-units, then it follows they are all equal to the same value, up to $\pm 1$. But since $f$ is nonconstant, only $n$ can take the same value so only $2n$ can take the same value up to $\pm 1$, a contradiction.

So it is not possible to have all $c_{n,S}$ values $S$-units.

It is not too hard to see a similar argument works for $S$-units in an arbitrary number field.

Answer 2

Yes, such $c_n$ is bounded by something effective. Below is a cubic bound, which probably may be improved. (Update: see $n^2\log n$ upper bound by Will in the comments.)

Assume that $f(x)$ is a power of 2 for all integer $x$ on $[0,c_n]$. Note that $[0,c_n]$ is partitioned onto at most $n$ segments, onto each of which $f$ is monotone. Thus there exist $N:=(c_n+1)/n$ consecutive integers onto which the values of $f(x)$ are, say, increasing powers of 2: $2^{m_1}<2^{m_2}<\ldots<2^{m_N}$. Assume that $N>(n+1)^2$. Denote $p_j=m_{1+j(n+1)}$ for $j=0,1,\ldots,n+1$. The numbers $2^{p_j}$ are the values of a polynomial of degree $n$ along $n+2$ elements of an arithmetic progression. Thus $$2^{p_{n+1}}-{n+1\choose 1}2^{p_n}+{n+1\choose 2}2^{p_{n-1}}-\ldots=0.$$ But the first summand is greater than the sum of all others.

Let me also prove that for distinct powers of 2 the bound is linear.

Assume that $f(0),\ldots,f(m)$ are distinct owers of 2. Let $A\subset \{0,1,\ldots,m\}$ be a subset of size $n+1$ with $n+1$ minimal values. Denote $t=\max_{a\in A} f(a)$. For $x\in \{0,1,\ldots,m\}$ we get by Lagrange interpolation $$ |f(x)|=\left|\sum_{a\in A} f(a)\prod_{b\in A\setminus \{a\}} \frac{x-b}{a-b}\right|\leqslant t2^nm^n/n!\leqslant t(2em/n)^n $$ (I bounded all $f(a)$ as $t$, all $x-b$ as $m$, and the sum of reciprocals of absolute values of the denominators is obviously minimal when $A$ consists of $n+1$ consecutive numbers. In the latter case this reciprocals are equal to ${n\choose i}/n!$ for $i=0,\ldots,n$, thus the bound).

On the other hand, we have $f(x)\geqslant 2^{m-n}t$. Therefore $2^{n(m/n-1)}\leqslant f(x)/t\leqslant (2em/n)^n$ and $2^{m/n-1}\leqslant 2e m/n$, thus $m/n$ is bounded from above.