# Are there infinitely many integer-valued polynomials dominated by $1.9^n$ on all of $\mathbb{N}$?

The original post is below. Question 1 was solved in the negative by David Speyer, and the title has now been changed to reflect Question 2, which turned out to be the more difficult one. A bounty of 100 is offered for a complete solution.

Original post. It follows from the prime number theorem and the periodicity properties $f(n+p) \equiv f(n) \mod{p}$ that for each $A < e$ there are only finitely many integer polynomials $f \in \mathbb{Z}[x]$ such that $|f(n)| < A^n$ for all $n \in \mathbb{N}$. On the other hand, for each $k \in \mathbb{N}$ the binomial coefficient $\binom{n}{k}$ is an integer-valued polynomial in $n$ bounded by $2^n$.

Question 1. Are there infinitely many integer polynomials with $|f(n)| < e^n$ for all $n \in \mathbb{N}$?

Question 2. Given $A < 2$, are there only finitely many integer-valued polynomials $f \in \mathbb{Q}[x]$ with $|f(n)| < A^n$ for all $n \in \mathbb{N}$?

• For any fixed $k$, $n^k < e^n$ for all $n$ sufficiently large - say, larger than $m$. It follows that $f_k(n) := n^k - m^k$ is smaller than $e^n$ for every $n$ and $k$. Unless I'm making a groggy mistake... – Paul Siegel Aug 11 '13 at 12:53
• It's probably worth noting here the fact that any integer-valued polynomial is an integral linear combination of the polynomials $\binom{x}{k}$. – Harry Altman Aug 12 '13 at 18:35
• Hm, does this mean I should somehow donate half of the 200-point bounty to David Speyer? I suppose I can achieve this purpose by posting a new question "What's the optimal $A$?", putting a 100-point bounty on it, and accepting David's answer which would be basically a link or pointer here... – Noam D. Elkies Aug 26 '13 at 21:59
• Looking beyond Mathoverflow, is it worth writing this up for publication as a joint paper? – Noam D. Elkies Aug 26 '13 at 23:20
• @Vesselin Dimitrov: Your contribution is not minimal; not only is asking a good question valuable in itself, but you also gave the example showing $A \leq 2$ which suggested that this "Question 2" has quite a different flavor from "Question 1" on ${\bf Z}[x]$. – Noam D. Elkies Aug 27 '13 at 14:44

Question 2: The constant $A$ can be brought down to $\sqrt 3$, and probably a bit below that but not all the way down to $1+\epsilon$.

Instead of the polynomial $f(n) = {n \choose m}$, use a finite difference of such polynomials, $$f(n) = \sum_{i=0}^m (-1)^i {m \choose i} {n \choose m+i}.$$ This is the $x^n$ coefficient of $$\frac1{1-x} \left( \frac{x(1-2x)}{(1-x)^2} \right)^m$$ and can be estimated by contour integration on $|x| = 3^{-1/2}$; the maximum of $|f(n)|^{1/n}$ occurs near $n=3m$, for which the critical points are at $x = (3 \pm \sqrt{-3}) / 6$.

Note that for $f(n) = {n \choose m}$ the generating function was $\frac1{1-x} (x/(1-x))^m$, and the maximum occurred near $n=2m$, for which the critical point was at $x = 1/2$. The factor $1-2x$ kills that maximum, and it seems that using $x/(1-x)$ and $(1-2x)/(1-x)$ to the same power is optimal. To reduce $A$ further, try to include also some power of $(3x^2-3x+1)/(1-x)^2$ to kill the new critical point.

• So I was wrong on both questions :-). Since you believe the limit infimum [of values of $A$] to be nonetheless strictly $> 1$, interesting what the actual value would be. Regarding integer polynomials the right question would have been: what is the limit infimum $\delta$ of the values of $c > 0$ such that there are infinitely many $f \in \mathbb{Z}[t]$ with $|f(n)|/n! < c$ for all $n \in \mathbb{N}$? We know from David Speyer's solution that $\delta \in [1/2,1]$. – Vesselin Dimitrov Aug 26 '13 at 4:29
• Thanks. Since $25 \geq 2 \cdot 11$ (and $11 \geq 10$) this also gives David Speyer the rare "Populist" badge, which is his third gold and which David may actually prefer to the bounty points :-) – Noam D. Elkies Aug 26 '13 at 4:47
• Let me spell out what I think Noam is implying. Let $p(x)$ be a polynomial with integer coefficients and degree $d$. Let $f_m(n)$ be the coefficient of $x^n$ in $p(x)^m/(1-x)^{dm+1}$. Then $f_m$ is an integer valued polynomial. If $|p(x)/(1-x)^d| \leq 1$ on the circle $|x| = r$, then integrating on this contour gives a bound $|f_m(n)| \leq C r^{-n}$. So our goal is to find polynomials $p$ which can push the radius $r$ as far out as possible. – David E Speyer Aug 26 '13 at 14:46
• The integers $f(n)$, when $n = 3m$ seem to be divisible by all primes between $2m$ and $4m$, which leads to a Chebyshev estimate slightly better than the one from the middle binomial coefficient. I haven't looked at David's new example but this suggests that getting $A$ down to $1$ might involve the PNT. – Felipe Voloch Aug 26 '13 at 18:12
• For $m$ large, the average of $|f_m(z)|$ over $|z|=r$ is $o(1)$ because $|f_m|$ behaves like the $m$-th power of a function that's at most $1$ but attains that value at only finitely many points. (Most likely $O(m^{-1/2})$ unless for some reason $1 - \lim_{m\rightarrow\infty} |f_m|^{1/m}$ has a quadruple or higher-order zero at some point of $|z|=r$.) – Noam D. Elkies Aug 26 '13 at 19:55

$\def\ZZ\mathbb{Z}$Question 1: No. Let $C>1$. I will show that there are only finitely many $f(x)$ in $\ZZ[x]$ so that $|f(n)| \leq C^n$ for all $n \in \ZZ_{\geq 0}$.

Choose $d$ large enough that, for all $k>d$, we have $k! > 2 C^k$. I claim that a polynomial with $|f(n)|<C^n$ is determined by its values on $0$, $1$, ..., $d$. Suppose, to the contrary, that $f(n) \neq g(n)$ but that they agree for $0 \leq n \leq d$. Let $k$ be the first integer where $f$ and $g$ disagree.

So $f(x)-g(x)$ is divisible by $x(x-1)(x-2) \cdots (x-k+1)$, so $f(x) - g(x) = x(x-1) \cdots (x-k+1) h(x)$ for some $h$ with integer coefficients. So $f(k) - g(k) = k! h(k) \equiv 0 \bmod k!$.

But, by assumption, $|f(k)|$ and $|g(k)| < C^k < k!/2$. So it is impossible that $f(k) \neq g(k)$ and $f(k) \equiv g(k) \bmod k!$. This contradiction concludes the proof.

Question 2 is still stumping me.

• Very neat. I had failed to fully exploit the polynomial assumption. My argument for $C < e$ was otherwise similar; it amounted to noting that $f(k)-g(k)$ was divisible by the product of the primes less than $k$. The latter argument works for arbitrary mappings $f : \mathbb{N} \to \mathbb{Z}$ with the property $f(n+p) \equiv f(n) \mod{p}$ for all $n \in \mathbb{N}$ and all primes $p$: for $C < e$ there are only finitely many such mappings (conjectured to be polynomials anyway), while for $C = e$ there are uncountably many. – Vesselin Dimitrov Aug 12 '13 at 18:19
• Thus, you have shown that for each $n_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $|f(n)| < n!/2$ for all $n \geq n_0$. This is close to optimal upon considering $k!\binom{n}{k}$, although (especially in view of the proof) it could still be an interesting problem to see whether the coefficient $1/2$ of $n!$ is optimal, or if it could be improved to any constant smaller than $1$. – Vesselin Dimitrov Aug 12 '13 at 18:23
• (To correct my first comment above: I meant to say that for each $C > e$ there are uncountably many such mappings $f : \mathbb{N} \to \mathbb{Z}$ --- not for $C = e$.) – Vesselin Dimitrov Aug 12 '13 at 18:35

The optimal growth rate is $$\tau:= (1+\sqrt{5})/2$$. Specifically, for any $$\epsilon>0$$, there are infinitely many integer valued polynomials bounded by $$(\tau+\epsilon)^n$$, but only finitely many below $$(\tau-\epsilon)^n$$. The first part of this answer (written first) proves the finiteness; the second uses Noam Elkies' idea combined with a theorem of Fekete to prove the infinitude.

Fix $$\epsilon>0$$. I will show that there are only finitely many integer values polynomial $$f(z)$$ with $$|f(n)| < (\tau-\epsilon)^n$$.

Let $$f$$ be such a polynomial of degree $$d$$. Set $$\frac{p(z)}{(1-z)^{d+1}} = \phi(z) = \sum_{n=0}^{\infty} f(n) z^n$$ Then $$p(z)$$ has integer coefficients, $$p(1) \neq 0$$, and we can uniquely recover $$f$$ from $$p$$. Moreover, there is some $$M$$ and some $$\delta_1>0$$ (dependent on $$\epsilon$$) so that $$|\phi(z)| < M$$ on $$|z|=\tau^{-1}+\delta_1$$.

We make the change of variables $$u = 1/(1-z)$$, so $$z=1-1/u$$. We have $$\phi(1-1/u) = p(1-1/u) u^{d+1}$$. Set $$q(u) = p(1-1/u) u^{d+1}$$. From the properties of $$p$$ above, $$q$$ is a polynomial with integer coefficients of degree $$d+1$$, and $$|q(1/(1-z))| < M$$ when $$|z|=\tau^{-1}+\delta_1$$. The map $$z \mapsto 1/(1-z)$$ sends $$|z|=\tau^{-1}+\delta_1$$ to a circle which contains the circle of radius $$1+\delta_2$$ around $$\tau$$ (for some $$\delta_2>0$$). So, using the maximum modulus principle, $$|q(u)| on the circle of radius $$1+\delta_2$$ around $$\tau$$.

We therefore make one more change of coordinates, $$v=u-\tau$$ and $$s(v) = q(v+\tau)$$, to get a polynomial $$s$$ with $$|s(v)| on the circle of radius $$1+\delta_2$$ around $$0$$. Although $$s$$ does not have integer coefficients, its leading term $$v^{d+1}$$ is a nonzero integer.

Choose $$D_1$$ sufficiently large enough that $$2 \pi M (1+\delta_2)^{-D_1-1} <1$$. Then, for $$D_2 \geq D_1$$, taking a contour integral around $$|v|=1+\delta_2$$ shows that the coefficient of $$v^{D_2}$$ in $$s(v)$$ has absolute value $$<1$$. Since the coefficient of $$v^{d+1}$$ is a nonzero integer, this establishes that $$d. So we have bounded the degree of $$f$$. Thus, $$f$$ is determined by its values at $$D_1$$ integers, and there are only finitely many possible polynomials $$f$$.

Now for the reverse bound. This argument is closely based on the proof of Fekete's Theorem here. (The original paper is here, but I don't speak German so I haven't checked whether they are the same argument.)

Our first goal is to establish the following: Let $$r < 1$$. There exists a nonzero polynomial $$q(u)$$ with integer coefficients so that $$|q(u)|<1$$ on the circle $$|u-\tau|.

Choose an integer $$T$$ large enough that, for any $$N > T$$, we have $$r^N + (1/2) r^{N-1} + (1/2) r^{N-2} + \cdots + (1/2) r^{T+1} + (1/2) r^T < 1/3.$$

Take $$N$$ larger than $$T$$. Define $$q^N_N(u) = (u-\tau)^N$$. Define $$q^N_i(u)$$ to be the unique polynomial of the form $$q^N_i(u) = q^N_{i+1}(u) + \theta_i \cdot (u-\tau)^{i}$$ so that $$|\theta_i| \leq 1/2$$ and the coefficient of $$u^{i}$$ in $$q^N_i$$ is an integer. Set $$q^N(u) = q^N_T(u)$$. So the coefficient of $$u^k$$ in $$q^N(u)$$ is an integer for $$T \leq k \leq N$$. For $$u$$ on the circle $$|u-\tau|=r$$, we get $$|q^N_T(u)| \leq r^N + (1/2) r^{N-1} + \cdots + (1/2) r^T < 1/3.$$

Let $$(c^N_{T-1}, C^N_{T-2}, \ldots, c^T_0)$$ be the last $$T$$, noninteger, coefficients of $$q^N$$. By the Pigeonhole principle, we can find $$q^M$$ and $$q^N$$ so that $$\sum_i |\{ c^N_i - c^M_i \}| r^i < 1/3$$ where $$\{ x \}$$ is the distance from $$x$$ to the nearest integer. We define $$q(u)$$ to be the result of taking $$q^N(u) - q^M(u)$$ and rounding the last $$T$$ coefficients to the nearest integer. We have now constructed $$q$$.

We now undo the above argument. Since $$|q(u)|<1$$ for $$|u-\tau|, we have $$|q(1/(1-z))|<1$$ on the disc with diameter $$(1-(\tau+r)^{-1}, 1-(\tau-r)^{-1})$$. This contains the circle of radius $$\tau^{-1} - \delta_1$$ about $$0$$, where $$\delta_1 \to 0$$ as $$r \to 1$$. So Noam's argument constructs infinitely many polynomials bounded by $$(\tau+\delta_2)^n$$.

Just for the fun of it, I used the above construction to find a polynomial $$\sum_{i=1}^{20} \theta_i (u-\tau)^i$$ with $$|\theta_i| < 1/2$$ and all coefficients other than the constant term integral. The constant term turned out to be $$-3878005 + 1739105 \sqrt{5} \approx 10752.00000977$$. If I round that off to $$10752$$, the resulting polynomial factors as $$(2 - u)^9 (1 - u)^5 (3 - 3 u + u^2) (7 - 15 u + 14 u^2 - 6 u^3 + u^4)$$. Making the variable substitution suggests that our next family of polynomials should be the coefficients of $$\frac{1}{1-z} \left( \frac{z^5 (1 - 2 z)^9 (1 - 3 z + 3 z^2) (1 - 5 z + 11 z^2 - 13 z^3 + 7 z^4)}{(1 - z)^{20}} \right)^m.$$ Of the four roots of $$7 - 15 u + 14 u^2 - 6 u^3 + u^4$$, two are at distance $$0.883514$$ from $$\tau$$ and two are at distance $$1.02472$$. Much past $$N=20$$, my naive implementation times out.

• The best exponent $k$ in $z^k(1-2z)^k (1-3z+z^2) / (1-z)^{2+2k}$ is not $k=2$ but $k \approx 3.7559$ [it doesn't have to be rational; just use $z^A (1-2z)^A (1-3z+z^2)^B / (1-z)^{2A+2B}$ with $A/B \rightarrow k$]. This gives a bound about $1.68053$, which is the largest root of $x^8 - 7x^6 + 23x^4 - 49x^2 + 49$. One can do better yet by using different multiplicities for the factors $z$ and $1-2z$, which brings the bound down to about $1.656246$. – Noam D. Elkies Aug 26 '13 at 18:42
• A generalization of Fekete's theorem inspired by arithmetic geometry (and, I think, in a particularly illuminating way) appears in Chinburg's paper "Capacity theory on varieties": archive.numdam.org/ARCHIVE/CM/CM_1991__80_1/CM_1991__80_1_75_0/… See Theorem 1.2 and the Minkowski application in the paragraph following it. – Vesselin Dimitrov Aug 26 '13 at 21:10
• In any case, this is amazing. Now I have to award the bounty. Since the solution is a joint one, here is what I will do. I will award the current bounty to Noam Elkies' answer, and start a new bounty of the same worth to reward this complete answer. – Vesselin Dimitrov Aug 26 '13 at 21:39
• A bounty of 200 will be awarded to this answer in 24 hours. (It turns out that 1) one may not set two bounties of the same worth on the same question, and 2) one has to wait for 24 hours before the bounty can be awarded.) – Vesselin Dimitrov Aug 26 '13 at 21:53
• Do you know if there are finitely many integer-valued $f$ such that $f(n) \leq \tau^n$? – Will Sawin Aug 27 '13 at 15:24