For a given $n$ is there a guaranteed way to construct any possible function from $\mathbb{Z}/n\mathbb{Z}$ to itself in terms of polynomials? Specifically, for $T = \mathbb{Z}/n\mathbb{Z}$ I'd like to use polynomials with $T$ coefficients to describe all functions $T \to T$.


My original hypothesis was that I could express functions $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ as a polynomial of order $n$ or less with coefficients in $\mathbb{Z}/n\mathbb{Z}$. I determined that this was true for $n=1, 2, 3, 5, 7$ (using brute force) but that it was false for $n=4, 6$. My new hypothesis is that it may only be true for prime $n$ (but I can't use brute force to test $11$ or larger primes).


Is this true for all prime $n$? If so, is there a more general result I can use for composite $n$? If not, are there other approaches I could use? Is this impossible in general?


One idea I had for composite $n$ was to use the prime factorization of $n$ ($p\_0^{k\_0}p\_1^{k\_1}...$) to construct polynomials for all the factors and then combine them into a single multivariate polynomial. I was able to do this for $n=4$ ($2^2$) by constructing $axy + bx + cy + d$ for $x, y \in [0, 1]$ and $a, b, c, d \in [0, 3]$. But I wasn't able to adapt this approach to $n=6$.


I'm interested in programmatically generating an enumeration of all possible functions $T \to T$ in terms of a given enumeration of $T$. Since the cardinality of this set is $|T|^{|T|}$ I won't actually generate most of these functions. The important part is that I have a mapping from each $index$ to a distinct function, and that in principle there is an $index$ for every possible function (even if some indices are far too large to work with). I'm doing this in a [software library](https://github.com/non/kronecker) that already contains enumeration strategies for many other data structures such as lists, tuples, sets, maps, and so on.


I have an existing solution that uses tables to map a subset of inputs to non-zero outputs (mapping all other inputs to zero). I can show that my enumeration constructs every possible table (eventually) so that in principle every function can be represented (although for data structures like 32-bit integers most interesting functions such as $f(x) = x + 1$ would have tables far too big to be useful). However most enumerations for small $index$ values are uninteresting (they produce zero for most inputs).


I was hoping to generate polynomials instead of tables, since even relatively simple polynomials would have more interesting behaviors. But I can't do this unless I know a way to construct a set of polynomials that represents each possible function exactly once.



Given the set of integers modulo $n$, can all functions from this set to itself be expressed as polynomials?
The 1995 paper *On polynomial functions from $\mathbb{Z}\_n$ to $\mathbb{Z}\_m$* in Discrete Mathematics, Vol. 137, proves the following strongly related result:


**Theorem:** *Every function $f:\mathbb{Z}\_n \rightarrow \mathbb{Z}\_m$ is a polynomial function if and only if $n$ is not greater than the least prime factor of $m.$*


To see the necessity, note that if $p|m$ then the representing polynomial $F \in \mathbb{Z}[x]$ for the function $f$ will satisfy $F(0)\equiv F(p) \pmod p$ so those values cannot be chosen independently.


For the sufficiency, since $n$ is not greater than the least prime factor of $m$ one has $(i-1,j)=1,$ for any $i\neq j$ and $i,j\in \{0,1,\ldots,n-1\}.$ Thus $i-j$ is a unit in $\mathbb{Z}\_m.$ Let $(i-j)^{-1} \in \mathbb{Z}\_m$ be denoted by $c\_{ij}.$


If $f:\mathbb{Z}\_n \rightarrow \mathbb{Z}\_m$ is given by $f(i)=b\_i,$ for $i=0,1,\ldots,n-1$ the following expression
$$
F(x)=\sum\_{i=0}^{n-1}b\_i \prod\_{\stackrel{j=0}{j\neq i}}^{n-1} c\_{ij}(x-j)
$$
will represent the function $f.$


