Skip to main content
Notice removed Reward existing answer by Vesselin Dimitrov
Bounty Ended with David E Speyer's answer chosen by Vesselin Dimitrov
Notice added Reward existing answer by Vesselin Dimitrov
Bounty Started worth 200 reputation by Vesselin Dimitrov
Notice removed Improve details by Vesselin Dimitrov
Bounty Ended with Noam D. Elkies's answer chosen by Vesselin Dimitrov
deleted 510 characters in body; edited title
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95

Are there infinitely many integer-valued polynomials dominated by $e^n$$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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $n_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{n \geq n_0} |f(n)|/n! \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $n_0$.)

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

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $n_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{n \geq n_0} |f(n)|/n! \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $n_0$.)

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}$?

Notice added Improve details by Vesselin Dimitrov
Bounty Started worth 100 reputation by Vesselin Dimitrov
Last edit: Gamma(t) had to be changed by n!, as I had neglected that Gamma(n) = (n-1)! rather than n!.
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $t_0 < \infty$$n_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{t > t_0} |f(t)|/\Gamma(t) \leq c$$\sup_{n \geq n_0} |f(n)|/n! \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $t_0$$n_0$.)

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $t_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{t > t_0} |f(t)|/\Gamma(t) \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $t_0$.)

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $n_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{n \geq n_0} |f(n)|/n! \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $n_0$.)

In the follow-up question, "inf" had to be replaced with "sup." My apology for being careless here.
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $t_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\inf_{t > t_0} |f(t)|/\Gamma(t) \leq c$$\sup_{t > t_0} |f(t)|/\Gamma(t) \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $t_0$.)

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $t_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\inf_{t > t_0} |f(t)|/\Gamma(t) \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $t_0$.)

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}$?


An update on question 1. David Speyer's solution below raises the following

Follow-up question. What is the supremum of those $c \in \mathbb{R}^{> 0}$ such that, for any $t_0 < \infty$, there are only finitely many $f \in \mathbb{Z}[x]$ with $\sup_{t > t_0} |f(t)|/\Gamma(t) \leq c$?

He shows that any $c < 1/2$ has this property. On the other hand, the example of $k!\binom{x}{k}$ shows that this no longer holds with $c = 1$, and the supremum lies in the interval $[1/2,1]$.

(My apology for modifying the original Question 1: it is only in view of the proof below that I think the follow-up question might be interesting. As far as I can see, it does not appear to be easy to construct an explicit sequence of examples with $c < 1$ and a fixed $t_0$.)

Correction: ...does *not* appear to be easy to construct...
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95
Loading
A follow-up on David Speyer's solution.
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95
Loading
A follow-up on David Speyer's solution.
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95
Loading
Source Link
Vesselin Dimitrov
  • 13.8k
  • 3
  • 56
  • 95
Loading