Take the 2-minute tour ×
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|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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

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.