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

share|improve this question
2  
$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
2  
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

6 Answers 6

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  NikolajK 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.

share|improve this answer
    
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
3  
@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.

share|improve this answer
    
This is an example of the general result I learned from Singmaster's paper. –  Jyrki Lahtonen Apr 30 '13 at 12:20
1  
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.$

share|improve this answer
    
Doesn't that have the same "zero divisors problem" as Pece's answer? –  Elmar Zander Apr 30 '13 at 15:51
1  
@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.

share|improve this answer
1  
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).

share|improve this answer
    
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
1  
@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
2  
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
1  
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

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.