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

Improve this question
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 at 14:49
  • $\begingroup$ @SJR: Thanks, this book is helpful. $\endgroup$
    – user35603
    Sep 27, 2013 at 15:37

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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