Skip to content

Polynomials Behaving Badly

February 7, 2013


Composite Moduli Ahead—Danger

KenJeong

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 {6}, for example.

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

\displaystyle  x \equiv (4x+3)(3x+4) \bmod 6.

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 {0}. Otherwise, the number of roots is bounded by its degree: if it has degree {d \ge 1}, then it can have at most {d} 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 {4}, denoted by {\mathbb{Z}_{4}}. In this ring there are zero-divisors, that is cases of {a \cdot b = 0} where neither {a} nor {b} is zero:

\displaystyle  2 \cdot 2 = 0.

This allows polynomials with many roots. Consider {f(x) = 2x}. This polynomial is of degree one and has two zeroes, {0} and {2} in {\mathbb{Z}_{4}}. Nasty.

I am interested in polynomials {f(x)} modulo {4}. Call a polynomial {f(x)} modulo {4} useful provided

\displaystyle  f(0) \neq f(2) \text{ or } f(1) \neq f(3).

Note the polynomial {f(x)=2x} is not useful, since {f(0)=f(2)=0} and {f(1)=f(3)=2}.

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

\displaystyle  f(x) = x^{2}

modulo {4}. This is not useful: {f(0)=f(2)=0} and {f(1)=f(3)=1}. Nor is {f(x) = x^2 + 2x} useful. But {f(x) = x^2 + x} 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 {4} is useful.

Proof:
Since {f(x)} is monic it can be written as

\displaystyle  x^{3} + ax^{2} + bx + c,

for some coefficients from {\mathbb{Z}_{4}}. Assume that {f(x)} is not useful, which implies that {f(0)=f(2)} and {f(1)=f(3)}. Since these equations are translation invariant we can assume that {c=0}. Thus {f(x) = x^{3} + ax^{2} +bx}. Now the first equality implies that {0=2b} which forces {b=0} or {b=2}.

In the first case {f(x) = x^{3} + ax^{2}}. The second equality implies that {1+a = -1 + a}: this is impossible modulo {4}. In the second case {f(x) = x^{3} + ax^{2} +2x}. The second equality now implies that

\displaystyle  1 + a + 2 = -1 + a + 2.

Note we use here that {2 = -2} modulo {4}. This is again impossible. This proves the proposition.
\Box

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

\displaystyle x^{5} + ax^{4} + bx^{3} + cx^{2} + dx + e.

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

\displaystyle x^{5} + bx^{3}.

Alas with {b = 1} we have {x^{5} + x^{3}} which is not useful. Although {x^{5}} and {x^{5} + 2x^{3}} 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 {f(x)} 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” {s} modulo {2}, but want to know its value modulo {4}. Suppose that I have a useful polynomial {f(s)}. Then if I can compute {f(s)} modulo {4}, I can calculate {s} modulo {4}. Well almost. I can do this provided I can calculate {f(s+1)} modulo {4} too.

Theorem 2
Let {f(s)} be a useful polynomial modulo {4}. The value of {s} modulo {2} and the values of {f(s)} and {f(s+1)} modulo {4} determine the value of {s} modulo {4}.

Proof:
We know that {f(x)} is useful. Suppose that {f(0) \neq f(2)} modulo {4}: the argument is the same if {f(1) \neq f(3)} modulo {4}. If {s} is even, then we just look at the value of {f(s)} modulo {4} and we are done. If on the other hand {s} is odd, then we look at the value of {f(s+1)} modulo {4}.
\Box

More Than One Variable

Ken on the other hand finds the property I’m calling “useless” to be useful. For a multi-variable polynomial {f(x_1,\dots,x_n)} one can state a strong form of uselessness to hold when {f(x_1,\dots,x_n)} is invariant upon replacing any {x_i} by {x_i + 2}. 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 {f: \mathbb{Z}_4^n \longrightarrow \mathbb{Z}_4^n} can really be regarded as a function with arguments in {\{0,1\}^n}, 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.

About these ads
12 Comments leave one →
  1. February 7, 2013 11:04 pm

    “Ken is Ken—not Dr. Ken—though actually Ken is me now” . This reads almost like some kind of mathematical statement.

    Interestingly, this was one of the most difficult sentences in the article to comprehend, thank you for showcasing in such an intuitive way this subject.

  2. February 8, 2013 3:56 am

    I don’t know if you’ve come across the concept of an APN (almost perfect nonlinear) function, but it seems to be closely related. Here are slides from a talk by a colleague of mine which starts by introducing the notion of APNity: http://www.ucc.ie/en/crypto/CodingandCryptographyWorkshop/TheClaudeShannonInstituteWorkshoponCodingCryptography2010/FGologlu.pdf

  3. Petter permalink
    February 8, 2013 8:35 am

    Isn’t the fact that x^5 = x^3 (mod 4) enough to show that polynomials of degree 5 are not useful in general?

  4. February 8, 2013 7:41 pm

    ken jeong… what a hilarious/brilliant/scene-stealing performer. but you barely scratched the surface of his true accomplishments. hes in the hangover movies, & was in transformers III. your initial paragraph on him seems like its a nonsequitur though. huh? oh I get it. insider blog joke. “dr.ken” would make the perfect complexity theory mad scientist when the movie comes out. oh and hows that script going by the way? :-p

  5. TCNE permalink
    February 8, 2013 11:39 pm

    The resolution to the Trio is now accessible online.

    You may start here: http://www.cqr.info/complexity/tcne?page=analogy

    Since the intended audience is general public, it may appear a bit verbose to some people. Suggestions to further simplify and/or succinctify are welcome and highly appreciated.

    Also, if you would be so kind as to help host the contents somewhere else other than my site (so I can take mine down), please let me know (tcne1837@hotmail.com). Thanks tremendously!

    Regards,
    TCNE

    • TCNE permalink
      February 8, 2013 11:43 pm

      Two curiosities:

      Has anybody tried (or simulated), either in thought experiment or actuality, the n-wire problem (n=10, for example, can give a pretty good idea, though)? Even without a proof, one can quickly and easily sense that it will have to exhaust the combinations till the right one is hit. Any tries with DNAC or QC (more reasonably in thought experiment of course)?

      Looking back now, finding just one problem for NP (Negative Proposition) seems much easier. Any different thoughts? Why almost never heard one serious attempt in this direction? Is it because people think that way is ‘more’ proving a negative?

      Regards,
      TCNE

    • TCNE permalink
      February 12, 2013 10:51 am

      My great apologies!

      Please use this URL:
      http://www.cqr.info:2013/complexity/tcne?page=analogy
      for access to the resolution.

      I am extremely sorry for any inconvenience caused by the previous one. Very sorry indeed!

      In case of problems with this one, please kindly bring that to my attention (tcne1837@hotmail.com). Thank you!

      Regards,
      TCNE

  6. February 9, 2013 1:13 am

    The title didn’t mean something like this?
    http://tercespot.com/PollyNomial.html

    • February 9, 2013 12:34 pm

      Arun, that was my initial thought as well. Thank you for that link:
      “she went to l’Hospital and generated a small but pathological function which left little surds all over the place”
      Is there more? Please, show me The Source? Please!

    • TCNE permalink
      February 12, 2013 11:39 am

      like it ter[sc]e
      did ’1/t’ break Kolmogorov lower bound?

Trackbacks

  1. Another Interesting Ingredient « The Epsilon Tale
  2. The Informatics Prize « Gödel’s Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,244 other followers