4
$\begingroup$

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 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.

$\endgroup$
2
  • $\begingroup$ I think I used the term endomorphism incorrectly. I'm interested in all $T \to T$ functions, not just of the form $x \to ax$. I'll edit the question to fix this. $\endgroup$
    – d_m
    Nov 22, 2020 at 2:30
  • 4
    $\begingroup$ This reminds me of Lagrange interpolation $\endgroup$ Nov 22, 2020 at 2:42

3 Answers 3

9
$\begingroup$

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.$

$\endgroup$
1
  • $\begingroup$ From the paper, the notation $c_{ij}$ is used to denote the inverse of $i - j$ in $\mathbb{Z}_m.$ $\endgroup$
    – d_m
    Nov 24, 2020 at 3:48
17
$\begingroup$

Suppose you have a composite $n=ab$, with $a,b>1$. Any function that satisfies $f(0)=0, f(a)=1$ can not be a polynomial otherwise we would have $$0=b\left(f(a)-f(0)\right)=b$$ in $\mathbb Z/n\mathbb Z$, which is a contradiction. However this is not a problem for $n$ prime, where you can use Lagrange interpolation to represent any function as a polynomial.

$\endgroup$
3
  • $\begingroup$ can you remind me why 0=b(f(a)-f(0)) $\endgroup$
    – lalala
    Nov 22, 2020 at 12:41
  • $\begingroup$ @lalala, $f(a) - f(0)$ is divisible by $a$. (And, in fact, isn't that all that's being claimed here—that is, there's nothing special about $f(a) = 1$ and $f(0) = 0$?) $\endgroup$
    – LSpice
    Nov 22, 2020 at 15:14
  • $\begingroup$ An alternate explanation: $f(x) = (x)g(x) + f(0)$ (for some $g$). So, $(b)f(a) = (ba)g(a) + (b)f(0)$. We know that $f(0) = 0$ and also that $ba = 0$ (mod $n$), so $(b)f(a) = 0$. Thus, $b(f(a) - f(0)) = 0$. $\endgroup$
    – d_m
    Nov 22, 2020 at 21:40
4
$\begingroup$

If $F:\Bbb Z/n\Bbb Z\to \Bbb Z/n\Bbb Z$ is given by a polynomial then for each $m \mid n$, $F(a)\equiv F(a+m)\bmod m$. Not all functions satisfy this condition.

If $n$ is squarefree and $F$ satisfies this condition then it is given by a polynomial: let $n=\prod_j p_j$, $c_j \frac{n}{p_j} \equiv 1\bmod p_j$, we'll have $$F(x) =\sum_j c_j \frac{n}{p_j^{e_j}} \sum_{a=0}^{p_j-1} F(a)(1-(x-a)^{p_j-1}).$$

I don't know if there is a simple congruence condition ensuring that $F$ is given by a polynomial when $n$ is not squarefree.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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