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)|<M$ 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)|<M$ 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<D_1$. 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|<r$.

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|<r$, 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.

12more comments