Few coefficients, few roots

Here’s an elegant little theorem I just learned about. Informally,

A polynomial with few non-zero coefficients has few real roots.

More precisely,

If a polynomial has k non-zero coefficients, it can have at most 2k – 1 distinct real roots.

This says, for example, that a polynomial like x100 – 12 x37 + 1 can have at most 5 distinct real roots, even though it has a total of 100 roots when you count complex roots and count with multiplicity.

I won’t repeat the proof here, but it’s not long or advanced.

The upper bound 2k – 1 in the theorem is sharp. To see this, note that

x(x2 – 1)(x2 – 4) … (x2 – (k-1)2)

has k non-zero coefficients and 2k – 1 distinct real roots.

Source: Mathematical Omnibus

Update: Someone asked about the converse. Does having few real roots imply few non-zero coefficients? No. The polynomial (x2 + 1)n has no real roots but it has n+1 non-zero coefficients.

4 thoughts on “Few coefficients, few roots

  1. If I recall correctly this falls right out of some basic calculus. Which is cute. It’s nice to have algebra results informed by calculus.

    I feel this is somehow useful in looking at the behaviour of linear recurrences but I don’t remember how.

  2. @Nick so is the question does the upper bound hold for real roots given complex coefficients? The bound clearly doesn’t hold for complex roots.

    For real roots I think the result is just a corollary for the theorem with real coefficients. Since a polynomial fin C[X] can just be written as f_1(x) + if_2(x) with f_i in R[X] (where they each have fewer coefficients than f) you must have the same constraint on real roots.

Leave a Reply

Your email address will not be published. Required fields are marked *