Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.