2
$\begingroup$

Let $R$ be a finite ring, and $f$ be a function from $R$ to $R.$

Suppose I want to know whether $f$ can be represented as a polynomial or not? Are there any good algorithms for finding this out?

  • 0
    $f$ is a total function.2012-04-01

2 Answers 2

3

There is a criterion of Spira that a function on a finite commutative ring $R$ is representable by a polynomial if and only if all the iterated divided differences that can be formed by subsets of the arguments and the respective values are in $R$. The reference is R. Spira, Polynomial interpolation over commutative rings, Amer. Math. Monthly, 75 (1968), 638–640, MR0229625 (37 #5199).

Also possibly of interest is Sophie Frisch, Polynomial functions on commutative rings, in D. E. Dobbs, M. Fontana, S.-E. Kabbaj (eds.), Advances in Commutative Ring Theory (Fes III Conf. 1997) Lecture Notes in Pure and Appl. Mathematics 205, Dekker 1999, pp 323–336, MR1767431 (2001d:13006), available at http://blah.math.tu-graz.ac.at/~frisch/wwwpdf/pfr.pdf

0

Another reference is Jian Jun Jiang, Guo Hua Peng, Qi Sun, Qi Fan Zhang, ``On polynomial functions over finite commutative rings,'' Acta Math. Sinica, v. 22, issue 4, Springer, 2006, pp. 1047-1050.

Theorem 3 Let $R$ be a finite commutative local ring with a maximum ideal $\mathfrak{m}$ and let $N$ be the minimal positive integer such that $\mathfrak{m}^N = 0$. Assume $f$ is a function from $R$ to $R$. Then $f$ is a polynomial function if and only if there exist $N$ functions $f_i$ ($i = 0, 1, \ldots , N - 1$) from $R$ to $R$ such that $f(x + s) = f_0(x) + f_1(x)s + \cdots + f_{N-1}(x)s^{N-1}$ holds for any $x\in R$ and any $s\in \mathfrak{m}$.

For example, if $R=\mathbb{Z}_{p^2}$, then $\mathfrak{m}=p\mathbb{Z}_{p^2}$ and N=2. The theorem says that a function $f:R\rightarrow R$ is a polynomial function if and only if $f(x+kp)-f(x)=f_1(x)kp$ for some function $f_1$. From the binomial theorem, if $f$ is a polynomial function then $f_1=f'\mod{p^2}$.

It suffices to check just for $k=1$, if you also check that $f_1(x+p)=f_1(x)\mod{p}$. The latter condition is necessary for all polynomial functions.