Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
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

2 Answers 2

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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