Suppose $\mathbb{Z}/m \mathbb{Z}$ is a residue ring for some $m \in \mathbb{N}$. If $m=p$ is a prime number then every function $f:\mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{Z}/p \mathbb{Z}$ is a polynomial $f(x) \in (\mathbb{Z}/p \mathbb{Z})[x]$.


**Question:** Are there any simple criteria of polynomiality of $f$ if $m$ is composite (particularly, if $m$ is a power of a prime number or $m$ is a product of two *distinct* primes)?


**Update:** Recently I found the article [On polynomial functions $\text{(mod $m$)}$](http://www.sciencedirect.com/science/article/pii/0022314X74900316) by D. Singmaster; there are also a series of papers by Z. Chen ([1](http://www.sciencedirect.com/science/article/pii/0012365X9500305G) and [2](http://www.sciencedirect.com/science/article/pii/0012365X93E0162W)) about polynomial functions. One interesting result is the following:



> 
> Let $f$ be a polynomial function $\text{(mod $m$)}$. Then $f$ has a unique polynomial representation $$f=\sum\_{k=0}^{n-1} b\_k x^k\quad \text{with}\quad 0 \leq b\_k \leq m/(k!,m)$$ and $n$ is the least integer s.t. $m | n!$. 
> 
> 
> 



Polynomiality of functions over residue rings
If $p$ and $q$ are distinct primes, then a function $f:\mathbb{Z}/pq\mathbb{Z}\to\mathbb{Z}/pq\mathbb{Z}$ is induced by a polynomial if and only if $f$ induces well-defined functions mod $p$ and mod $q$: in other words, if and only if $f(c+p)\equiv f(c)\pmod{p}$ and $f(c+q)\equiv f(c)\pmod{q}$ for all $c\in\mathbb{Z}/pq\mathbb{Z}$. That polynomials have this property follows by reducing mod $p$; conversely, if a function has this property then there are polynomials $f\_1,f\_2\in\mathbb{Z}[x]$ such that $f\_1(c)\equiv f(c)\pmod{p}$ and
$f\_2(c)\equiv f(c)\pmod{q}$ for all $c$. Then the function $f$ is represented by the polynomial $qu f\_1(x) + pv f\_2(x)$ where $u,v\in\mathbb{Z}$ satisfy $qu\equiv 1\pmod{p}$ and $pv\equiv 1\pmod{q}$.


The problem is much more difficult for functions $f:\mathbb{Z}/m\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}$ when $m$ is a prime power, say $m=p^n$. One constraint is that if $f$ comes from a polynomial then $f$ must induce well-defined functions mod $p^i$ for all $i<n$. But that is far from being sufficient. Carlitz gave necessary and sufficient conditions for $f$ to come from a polynomial. One such condition is that
$$
\Delta^r f(0) \equiv 0 \pmod{p^{\nu(r)}}
$$
for every nonnegative integer $r$ less than $p^n$, where
$\nu(r)=\min(n, \text{ord}\_p(r!))$ and $\Delta$ is the difference operator $\Delta h(c)=h(c+1)-h(c)$. Carlitz's paper is "Functions and polynomials (mod $p^n$)", Acta Arithmetica 9 (1964), 67--78.


