# 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

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

-