Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
add comment

1 Answer

up vote 5 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|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
add comment

Your Answer

 
discard

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.