# Polynomiality of functions over residue rings

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)}$$ by D. Singmaster; there are also a series of papers by Z. Chen (1 and 2) 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!$$.

• ( I took the liberty of editing the notation, as a member of the International Committee for the Abolition of the Notation $\mathbb{Z}_p$ for Denoting Other Than p-Adic Numbers ) Sep 27 '13 at 13:49
• I took the liberty of editing the notation, writing $(\mathbb{Z}/p \mathbb{Z})[x]$ instead of $\mathbb{Z}/p \mathbb{Z}[x]$ :-) Sep 27 '13 at 14:04
• Chapter I of the book 'Polynomial Mappings' by Narkiewicz has important information about your question (but no simple answer). Sep 27 '13 at 14:49
• @SJR: Thanks, this book is helpful. Sep 27 '13 at 15:37

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.

• It's very interesting. Is it possible to obtain a similar criterium if $m=p_1p_2 \ldots p_n$, where $p_1,p_2,\ldots,p_n$ are distinct primes, using this trick with Chinese remainder theorem? Sep 28 '13 at 12:15
• Yes, that's true. The result is the same as for products of two primes. More generally, the Chinese remainder theorem lets you reduce from the case of arbitrary $m$ to the case of prime power $m$: if $m=p_1^{e_1}...p_n^{e_n}$ where the $p_i$ are distinct primes, then a function $f$ mod $m$ comes from a polynomial if and only if $f$ induces well-defined functions mod $p_i^{e_i}$ for every $i$, and each of those functions is given by a polynomial. Sep 28 '13 at 12:21
• @Michael: Do you know an example of a function f mod m that is well-defined mod every divisor of m but does not come from a polynomial? Could it be that simple? Sep 28 '13 at 12:54
• @SJR: it's not that simple. One example is when $m=p^2$ with $p$ an odd prime, where $f$ is zero except that $f(2p)=p$. If this were a polynomial then Taylor's theorem for polynomials would imply that $f(c+p)-f(c)\equiv p f'(c)$ mod $p^2$. For $c=0$ this gives $f'(0)\equiv 0$ mod $p$, but for $c=p$ it gives $f'(p)\equiv 1$ mod $p$, contradiction. Sep 28 '13 at 13:13
• Incidentally, functions mod $p^k$ that are well-defined mod every divisor of $p^k$ are called $T$-functions. These have been studied in the cryptography and $p$-adic dynamics literature, especially by Vladimir Anashin. Sep 28 '13 at 14:12