Skip to main content
2 of 2
added 981 characters in body
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459