

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
up vote 6 down vote accepted

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)!$.

share|cite|improve this answer
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

Your Answer


