# Polynomial values are powers of two

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.

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.

• Did you mean $f(a) \equiv f(a + 2^k) \pmod 2^k$? (Of course, what you wrote is true, too!) May 14 at 13:10
• @LSpice Yes. Editing the answer to prove a stronger statement, will try to fix that, too. May 14 at 13:12
• Awesome! Thanks for the more general version. May 14 at 13:30

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.

• Nice! One can improve this to $\sim n^2 \log n$ by choosing $p_j = m_{1 + j c}$ where $c \sim \log n$, since we want $2 > (1+ 2^{-c})^n - (1 - 2^{-c})^n$ which can be achieved for $c$ of size a constant times $\log n$. May 14 at 12:46
• This is great! If you know the solution of the initial question about finding the sequence of $t_i$ that does the job, this would be also interesting. May 14 at 13:29