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.
If $f:\mathbb{Z}\to\mathbb{Z}$ has period $q$ modulo for any $q$, is it necessarily a polynomial?
3
$\begingroup$
elementary-number-theory
-
0[This link is listed as "Related"](http://math.stackexchange.com/questions/33521/functions-f-mathbbn-rightarrow-mathbbz-such-that-m-n-fm-fn) – 2011-09-07
1 Answers
6
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)!$.
-
0Ah, 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. – 2011-09-07