2
$\begingroup$

I have proved a result that seems (to me) interesting, and I am wondering whether it is a known result, and if not whether it seems interesting to others. The result is as follows:

Let $R=\mathbb Z / n \mathbb Z$ and let $\mathcal A = R^R$ denote the algebra of functions from $R$ to itself. Then:

  1. If $n$ is prime, every function in $\mathcal A$ can be represented by a unique polynomial in $R[x]$ of degree at most $n-1$; more specifically, there exists a natural isomorphism $R[x]/(x^n-x) \cong \mathcal A$.
  2. If $n$ is composite, then most functions in $\mathcal A$ cannot be represented by any polynomial in $R[x]$; that is, the natural homomorphism $R[x] \to \mathcal A$ is not onto.

Is this a well-known result? A trivial one? It certainly seemed interesting to me when I came across it, and I have been unsuccessful in finding any statement of this online.

Just to clarify, I am not asking for a proof -- I have one already -- just for an assessment of the value of the result.

$\endgroup$
  • 1
    $\begingroup$ A related question. See the answers by Bill Dubuque and yours truly. Not an exact duplicate, but close enough to prevent me from answering this with a clear conscience. $\endgroup$ – Jyrki Lahtonen Apr 20 '15 at 15:07
  • 1
    $\begingroup$ IMO the simplest argument showing that you cannot get all the functions from polynomials is the following. If $p$ is a prime divisor of $n$, $n$ composite, then all the polynomials $f$ with coefficients in $R$ will satisfy $$a\equiv b\pmod p\implies f(a)\equiv f(b)\pmod p.$$ IIRC in a paper by Carlitz there is a description of the set of functions that you get by evaluating polynomials. $\endgroup$ – Jyrki Lahtonen Apr 20 '15 at 15:10
  • 1
    $\begingroup$ The fact that every function from $\mathbb Z/n\mathbb Z$ to itself is a polynomial when $n$ is prime is something that I think of as well known because I know it and because the proof is obvious, but I haven't taken any poll of mathematicians to see how many are aware of it. The other point I don't recall having thought of before. However, if you call a function algebraic, I am at first inclined to think it means the function somehow is a zero of a polynomial, rather than that the function itself is a polynomial function. ${}\qquad{}$ $\endgroup$ – Michael Hardy Apr 20 '15 at 15:47
4
$\begingroup$

It's certainly well-known. It is an immediate corollary of the Chinese Remainder Theorem. Notice that you could also work with $R^S$ for any finite set $S$. (And you don't mean $R^R$, which doesn't exist; you mean $R^S$, where $S$ is the underlying set of the ring $R$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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