Polynomials Behaving Badly

Ken Jeong is a doctor of internal medicine, and a stand-up comic, and a TV and movie actor. His full name is Kendrick Kang-Joh Jeong, but he goes by “Dr. Ken.” His wife is also a doctor, but to date she has not tried show business. He got his break in the movies when the producers of the 2009 movie “Knocked Up” came to a comedy club looking to fill a short role of a maternity doctor at the end of the movie. They saw his performance and pegged him for the role even before learning he was a doctor in real life. In unreal life he’d had some TV appearances, including regular bit parts in the cable TV series, “Girls Behaving Badly.”

Today, getting away from thoughts of show business, I want to talk about polynomials over composite moduli and how they can behave badly.

Truth in blogging: I am working on a paper, and one of the proofs requires an understanding of how polynomials behave over composites. I knew they could be nasty, and they are indeed. So this discussion today is more to educate me on what is going on. I hope you find it useful, since one of the mysteries that we have discussed repeatedly is the complexity of computation over composites. We have little idea how multi-variable polynomials behave modulo even , for example.

Even just univariate polynomials, polynomials of one variable, can do wild things over composite moduli. For example, Adam Klivans notes that

Pretty strange.

When Polynomials Act Badly

A polynomial in one variable over a field can have lots of roots only if it is the degenerate polynomial . Otherwise, the number of roots is bounded by its degree: if it has degree , then it can have at most roots. This holds whether the field is the rationals, the reals, the complex numbers, a finite field, or any field. Nice.

A polynomial over a ring can exceed the degree bound. Consider the ring of the integers modulo , denoted by . In this ring there are zero-divisors, that is cases of where neither nor is zero:

This allows polynomials with many roots. Consider . This polynomial is of degree one and has two zeroes, and in . Nasty.

I am interested in polynomials modulo . Call a polynomial modulo useful provided

Note the polynomial is not useful, since and .

A plausible conjecture might be that monic polynomials will behave better: recall a polynomial is monic if the leading coefficient is . A monic linear polynomial has exactly one root in any ring. Perhaps monic is the key to good behavior. Wrong. Consider the monic polynomial

modulo . This is not useful: and . Nor is useful. But is useful.

Monic Not Manic in the Third Degree

This bad behavior stops for degree three—at cubic polynomials.

Proposition 1
Every monic cubic polynomial over modulo is useful.

Proof:
Since is monic it can be written as

for some coefficients from . Assume that is not useful, which implies that and . Since these equations are translation invariant we can assume that . Thus . Now the first equality implies that which forces or .

In the first case . The second equality implies that : this is impossible modulo . In the second case . The second equality now implies that

Note we use here that modulo . This is again impossible. This proves the proposition.

At degree 4 we run into trouble again—indeed since is not useful, we already know its square is not useful either. How about quintic? A monic quintic polynomial has the form

The above logic again tells us we can take and must be 0 or 2. Now regardless of what and are, those terms are the same for , and are also the same for —indeed, even powers do not contribute to or detract from usefulness. Nor do terms with even coefficients, so we can also ignore the term, bringing us down to

Alas with we have which is not useful. Although and are useful, this is enough to show generally that to assure usefulness, you want monic cubic.

What is “Useful” Useful For?

In summary, a monic cubic polynomial must be useful. Why do I call this property “useful” and not something else? Such a polynomial can be used as follows. Suppose that I know the value of some “secret” modulo , but want to know its value modulo . Suppose that I have a useful polynomial . Then if I can compute modulo , I can calculate modulo . Well almost. I can do this provided I can calculate modulo too.

Theorem 2
Let be a useful polynomial modulo . The value of modulo and the values of and modulo determine the value of modulo .

Proof:
We know that is useful. Suppose that modulo : the argument is the same if modulo . If is even, then we just look at the value of modulo and we are done. If on the other hand is odd, then we look at the value of modulo .

More Than One Variable

Ken on the other hand finds the property I’m calling “useless” to be useful. For a multi-variable polynomial one can state a strong form of uselessness to hold when is invariant upon replacing any by . Terms with even coefficients, or terms that are functions of the squares of variables, do not affect this condition either. Ken is Ken—not Dr. Ken—though actually Ken is me now, since Dick wrote just the third paragraph of this section.

The use of uselessness is that such an can really be regarded as a function with arguments in , that is with the same domain as a Boolean function, though with mod-4 values. Such polynomials arise in the polynomial translation of quantum cricuits described here.

I myself am mostly interested in the number of solutions modulo composites for polynomials. Ken’s student Robert Surowka is finding some interesting positive results about cardinalities of solution sets modulo powers of 2, which we intend to report soon.

Open Problems

Are useful polynomials really useful? Useless ones too? The proof I had fell apart in another place, so this notion about useful polynomials is on hold for now. Proofs behaving badly… But perhaps we can use it in the future.