14
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

15
$\begingroup$

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.

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

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    May 14 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vlad Matei
    May 14 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.