# Algorithms for deciding whether a function over a finite ring is polynomial or not?

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?

-
Is $f$ total or partial not? – user2468 Apr 1 '12 at 16:28
$f$ is a total function. – Norman Apr 1 '12 at 16:30

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.

-

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

-