# Representing the function $\mathbb Z_9\to\mathbb Z_9$, $f(0) = 1$, $f(1) = \ldots = f(8) = 0$ as a polynomial in $\mathbb Z_9[x]$

Let $\mathbb Z_9=\left\{0,1,2,3,4,5,6,7,8\right\}$ be the set of integers modulo 9 and $f:\mathbb Z_9 \rightarrow \mathbb Z_9$ be a function.

Assume $f(0)=1$, $f(1)=f(2)=...=f(8)=0$. What is the definition of $f(x)$? That is, can we find a polynomial with one variable satisfying these properties?

Actually, it would be better if there is a general method for finding polynomials whose values are determined like this one. For $\mathbb Z_2$, there is a method called butterfly algorithm. Using this, one can find the algebraic normal form of a function using the values (truth table of that function).

Thank you.

-
$f\equiv 0{}{}$? –  Git Gud Apr 29 '13 at 19:29
Sorry about the misprint... f(0)=1. I have fixed it now. –  Math_D Apr 29 '13 at 19:53
FYI, the fact that $9$ is divisible by the square of a prime number makes things problematic. For a square-free modulus, every function is a polynomial function. –  Hurkyl Apr 30 '13 at 10:20

There is no such polynomial $q$.

We show this by contradiction. Assume that $q = a_k x^k + \ldots + a_0 x^0\in\mathbb Z_9[x]$ is a polynomial with $q(0) = 1$ and $q(x) = 0$ otherwise.

Since $0^2 = 3^2 = 6^2 = 0$ in $\mathbb Z_9$, we get $$-1 = f(3) - f(0) = (a_k 3^k + a_{k-1} 3^{k-1} + \ldots + a_1 3 + a_0) - (a_k 0^k + a_{k-1} 0^{k-1} + \ldots + a_1 0 + a_0) = 3 a_1.$$ But in $\mathbb Z_9$, $-1$ is not a multiple of $3$, so this is a contradiction.

Conclusion: In contrast to $\mathbb Z_2$, not every function $\mathbb Z_9\to \mathbb Z_9$ can be represented as a polynomial.

-
There was a misprint in the question. I have corrected it now.. –  Math_D Apr 29 '13 at 19:57
Maybe if f(0)=3 and the other values are 0, then we could find a function.. The question is, how? –  Math_D Apr 30 '13 at 11:47
Okay, this works for any $\mathbb{Z_{n^2}}$ and then also for a bunch of other $f(0)$'s than 1. –  Nikolaj K. Apr 30 '13 at 15:00

There can be no such polynomial. In general, if $R$ is a commutative ring, and $p(x)\in R[x]$, then for any $a,b,c\in R$, such that $ac=bc$, we can show $p(a)c=p(b)c$.

Now, take $a=0,b=3,c=3$ in $R=\mathbb Z_9$.

You can solve the general problem in $\mathbb Z_m$ if $m=p$ is prime. In that case, you can think of the solution as a case of Chinese Remainder Theorem in $\mathbb Z_p[x]$, since we want a polynomial, $q(x)$ such that $q(x)\equiv f(a) \pmod{x-a}$.

If $m$ is square-free or twice a square-free number, my condition above is sufficient. (Essentially, the case $m=4$ is a special case.)

Unfortunately, the above condition is not sufficient otherwise.

Write $q(x)=\sum_{i=0}^n a_i(x)_i$ where $$(x)_i=x(x-1)\dots(x-(i-1))$$ is the $i$th falling factorial polynomial.

Then if $m=8$, then $(b)_i=0$ for $b\in\mathbb Z_8$ and $i\geq 4$. So we can restrict ourselves to cubic polynomials $q$.

Now try to find a cubic polynomial $q$ such that $q(0)=4$ and $q(a)=0$ for $a\neq 0$. I don't think it can be done.

If $p>2$ then consider the polynomial $q(x)=\frac{(x)_{2p}}{p}$. This polynomial (with rational coefficients) maps $\mathbb Z\to \mathbb Z$, and it has the property that for all $a,b\in\mathbb Z$, $a-b|q(a)-q(b)$. This means, in particular, that we can view this as defining a function which maps $\hat q:\mathbb Z_{p^2}\to\mathbb Z_{p^2}$ and we can show $\hat q$ matches my necessary condition.

However, it is impossible to find a polynomial in $\mathbb Z_{p^2}[x]$ which evaluates as $\hat q$. This is because if $h$ is such a polynomial, we have that $h(p+a)=h(a)=0$ for $a=0,1,2,\dots,p-1$. But $h(a+p)\equiv h(a)+ph'(a)\pmod{p^2}$. This means that $h'(a)\equiv 0\pmod p$ for $a=0,\dots,p-1$, and hence for all $a$. But that in turn means that $h(a+p)\equiv h(a)\pmod {p^2}$ for all $a$, which would mean that $\hat q$ is the zero function. Since we know it is not (that is where $p>2$ is needed) we are done.

-
You claim that the problem can be solved if and only if whenever ac=bc, f(a)c=f(b)c.Could you give any referances about this?-Thank you. –  Math_D Apr 29 '13 at 20:54
Actually, I'm not sure it is true. For example, if $m=8$ I don't thinh $f(0)=4$ and $f(a)=0$ for $a\neq 4$ has a solution. –  Thomas Andrews Apr 29 '13 at 21:06
@Math_D: I think that a paper by Carlitz titled Functions and polynomials $\pmod{p^n}$ that appeared in Acta Arithmetica in 1964 gives a necessary and sufficient condition. Or may be an earlier paper by Carlitz? He has a sufficient and necessary condition, but I'm not positive about the paper. –  Jyrki Lahtonen Apr 30 '13 at 12:19
@JyrkiLahtonen Ah, glad it wasn't something obvious. My condition essentially means you can reduce the problem to the case of $\mathbb Z_{p^k}$ where $p^k|m$. But I was stuck from there. –  Thomas Andrews Apr 30 '13 at 12:44

The (+1) answer by Azimut identified a fundamental obstacle: $p(0)\equiv p(3)\pmod3$ for all polynomials $p$ (and other similar congruences). IIRC in a paper by Carlitz a necessary and sufficient condition is derived (for a general modulus, not just $9$). I give a counting argument as a proof that not all functions from $R=\mathbb{Z}_9$ to itself can be described as polynomial function with integer coefficients (the coefficients can obviously be reduced modulo 9).

Consider the polynomial $$p(x)=x(x-1)(x-2)(x-3)(x-4)(x-5).$$ If $x$ is an integer $\ge6$, then we see that $$p(x)=6!{x\choose 6}$$ is divisible by $6!=9\cdot80$, and thus vanishes modulo $9$. As clearly also $p(x+9)\equiv p(x)\pmod9$ for all integers $x$, we can conclude that any polynomial multiple of $p(x)$ yields the constant function $0:R\to R$. The same holds for the polynomial $q(x)=3x(x-1)(x-2)$.

A result discovered independently by Singmaster in the 1960s and Niven & Warren in 1950s (and probably by others earlier) implies that the polynomials $p(x),q(x)$ generate the ideal $I\subset R[x]$ of polynomials yielding the constant function zero. We see that every polynomial in $R[x]$ is congruent modulo $I$ to exactly one polynomial of the form $$a_0+a_1x+a_2x^2+a_3x^3+a_4x^4 +a_5x^5,$$ where $a_0,a_1,a_2$ are arbitrary elements of $R$, and $a_3,a_4,a_5$ are arbitrary elements of the set $\{0,1,2\}\subset R$. So we can conclude that there are only $9^3\cdot 3^3$ distinct polynomial functions from $R$ to itself. This is obviously way too small a number to cover them all.

-
This is an example of the general result I learned from Singmaster's paper. –  Jyrki Lahtonen Apr 30 '13 at 12:20
Hah, I found an alternative reason for your $q(x)=(x)_6$ function being important above. Basically, if $h$ is any polynomial with $2p$ consecutive roots modulo $p^2$, then $h'(a)\equiv 0\pmod p$ for all $a$, and therefore $h(a+p)=h(a)$ for all $a\in\mathbb Z_{p^2}$, implying $h$ is the zero function. –  Thomas Andrews Apr 30 '13 at 15:35
Well spotted trick with the derivative, @Thomas! As you observed, falling factorials are useful here, and we can keep going. As the next step we see that the values of $(x)_9$ are divisible by $9!$ so that polynomial vanishes modulo $3^4$ - we get divisibility by two more multiples of $3$ even though we only increase the degree by three. –  Jyrki Lahtonen Apr 30 '13 at 16:26

If $f(X)\in \mathbb{Z}_9[X]$ has $f(6)=0$, then $f(X)=(X-6)g(X)$ for some $g(X)$ so $f(0)=3g(0)\neq 1.$

-
Doesn't that have the same "zero divisors problem" as Pece's answer? –  Elmar Zander Apr 30 '13 at 15:51
@ElmarZander Natural question to ask! See my other answer here =] In short, the root theorem holds in any commutative ring which is all I needed, while Pece used something stronger. –  Ragib Zaman Apr 30 '13 at 15:55
@ElmarZander To emphasize Ragib Zaman's comment, see the edit of my answer. –  Pece Apr 30 '13 at 16:43
Thanks! Now I see it. I'm not used to working in non-integral domains, so it took me a while to see, why you can factor out single roots, but not all of them at once. –  Elmar Zander May 1 '13 at 8:53

Pece's attempt brings to mind some interesting questions about how far we can stretch the root theorem. Recall:

1) Let $R$ be any commutative ring, $a\in R$ and $f(X)\in R[X].$ Then $(X-a)\mid f(x)$ in $R[X]$ if and only if $f(a)=0.$

2) Let $R$ be an integral domain and $f(X)\in R[X].$ Suppose $f$ has distinct roots $a_1, \cdots, a_n \in R.$ Then $(X-a_1)\cdots (X-a_n) \mid f(x)$ in $R[X].$

Let us examine the proof of 2) to see where the domain condition is used:

We induct on $n.$ The $n=1$ case is a direct application of 1). Suppose $n>1$ and that 2) is true for the $n-1$ case. From that we deduce that there exists a $g(X)\in R[X]$ such that

$$f(x) = (X-a_1)\cdots (X-a_{n-1}) g(X).$$ Using that $a_n$ is a root of $f$ we have $$(a_n-a_1)\cdots (a_n - a_{n-1}) g(a_n)=0.$$

We would like to be able to conclude from this that $g(a_n)=0$ and then by 1) again we would be done. This is where the domain condition is used: The $a_i$ are distinct so none of the $(a_n-a_i)$ terms are $0$ so since $R$ is an integral domain, $g(a_n)=0.$

So we can get the result in a general commutative ring $R$ for $n=2$ if we can ensure that $a_2-a_1$ is not a zero divisor. If so, then we get the $n=3$ case if we can ensure that $(a_3-a_1)(a_3-a_2)$ is not a zero divisor. And if so, then we can get the $n=4$ case if ... etc.

-
Note: This does not directly answer the question in itself but I think it is relevant. –  Ragib Zaman Apr 30 '13 at 15:15
Since this is not an answer to the question, I think you should move these thoughts to your nice (+1) answer (the credit for this term goes to Jyrki Lahtonen). –  azimut Apr 30 '13 at 16:27

A shorter anwser : if $f$ is a polynomial, as $1,2,\ldots,8$ are roots, $f(x) = (x-1)(x-2)\ldots(x-8)q(x)$ with $q$ some polynomial. Hence $f(0) = 1\times2\ldots\times8\times q(0) = 0$ since $9 \mid 8!$ .

Edit : As pointed out by the comment, this argument is not valid because the ring $\mathbb Z_9$ is not an integral domain. So it is allowed to make the euclidean division by $(x-1)$ (because the coefficient of $x$ is inversible) to find $f(x) = (x-1)g(x)$ for some polynomial $g(x)$. BUT, one then cannot assume that $g(x)$ vanishes on $2,3,\ldots,8$ because of the possible divisors of zero.

For a correct use of that kind of argument, see answer Ragib Zaman's answer (the short one).

-
This f does not fit to the one that is given in the question. azimut's answer is correct, I suggest you to read it. no such function exists –  Math_D Apr 30 '13 at 9:59
The proof is by contraposition : if $f$ is a polynomial with coefficients in $\mathbb Z_9$ with $1,2,\ldots,8$ among its roots, then $f(0)=0$. Hence, a $f$ as in the question is no polynomial. –  Pece Apr 30 '13 at 10:17
@Pece: This argumentation does not work, since $\mathbb Z_9$ has zero divisors. As a counterexample, consider $f(x) = x^2$. It has three zeros $0,3,6$, so by your argumentation you would have $f(x) = x (x-3)(x-6)q(x)$ which is not true. –  azimut Apr 30 '13 at 11:37
Don't delete your answer. Often even incorrect answers have nice ideas that can sometimes be salvaged. See my answer. –  Ragib Zaman Apr 30 '13 at 14:45
But it would be nice for readers of your post to put up a warning sign somewhere and state that the answer doesn't work and why (so the reader doesn't have to read the comments to figure that out). –  Elmar Zander Apr 30 '13 at 15:49
show 1 more comment