6
$\begingroup$

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!$.

$\endgroup$
  • 10
    $\begingroup$ ( 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 ) $\endgroup$ – Qfwfq Sep 27 '13 at 13:49
  • 1
    $\begingroup$ I took the liberty of editing the notation, writing $(\mathbb{Z}/p \mathbb{Z})[x]$ instead of $\mathbb{Z}/p \mathbb{Z}[x]$ :-) $\endgroup$ – Francesco Polizzi Sep 27 '13 at 14:04
  • 1
    $\begingroup$ Chapter I of the book 'Polynomial Mappings' by Narkiewicz has important information about your question (but no simple answer). $\endgroup$ – Sidney Raffer Sep 27 '13 at 14:49
  • $\begingroup$ @SJR: Thanks, this book is helpful. $\endgroup$ – user35603 Sep 27 '13 at 15:37
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user35603 Sep 28 '13 at 12:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Zieve Sep 28 '13 at 12:21
  • 1
    $\begingroup$ @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? $\endgroup$ – Sidney Raffer Sep 28 '13 at 12:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Michael Zieve Sep 28 '13 at 13:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Zieve Sep 28 '13 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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