# If $f:\mathbb{Z}\to\mathbb{Z}$ has period $q$ modulo for any $q$, is it necessarily a polynomial?

If $f:\mathbb{Z}\to\mathbb{Z}$ satisfies the property $f(a+q)\equiv f(a)\pmod{q}$ for all $a\in\mathbb{Z},q\in\mathbb{N}$, can we conclude that $f(n)$ is a polynomial function? Seems like it should be the case, and that the proof should be obvious, but I can't figure it out. Since $n|(f(n)-f(0))$ for all $n\in\mathbb{N}$, we can define a $g$ in a decomposition with $f(n)=ng(n)+f(0)$. Plugging this back in we get $g(a+q)\equiv g(a)\pmod{q}$ so long as $\gcd(a,q)=1$. Is this direction viable? I also suspect that one might be able to prove that iterated the forward difference $\Delta^kf(n)$ eventually dies for sufficiently large $k$ (which would prove the hypothesis), but can't quite see how.

It seems to me that one can construct a function $f(n)$ that grows faster than any polynomial which would satisfy your constraint. This is simply because once we have defined $f(-n+1), ..., f(-1), f(0), f(1), ..., f(n-1)$ we have only constrained the values of $f(n), f(-n)$ up to congruence mod $(2n)!$.
• Ah, so we can go through an iterative construction procedure, and at each stage the value of $f$ is at most only determined modulo some $p$, so we can plan ahead of time to always choose multiples of $p$ so large that the overall growth is superexponential. I think this works. – anon Sep 7 '11 at 15:13