The Picard Jump: if you are not at an extreme, then you are far from an extreme

Charles Picard was a French mathematician who made great contributions to analysis. His best known results, perhaps, are his theorems that restrict the possible ranges of analytic functions. He also made important contributions to applied mathematics, including telegraphy—the “Internet” of the late 1800’s.

Today I want to talk about one of his great theorems, give a counterpart that holds for finite fields, and in general discuss this type of result.

The search engine Google is pretty good, but it is not perfect. When I searched for some information about Picard I tried “Picard math,” thinking this would be enough to get me to the mathematician Picard. It did. Yet right behind the entry for a Wiki page on his life, was an entry on a New York Post article:

That’s the message the Securities Investor Protection Corp. had for some victims of convicted Ponzi schemer Bernie Madoff who think they’re being short-changed by the trustee of Madoff’s estate.

As part of a larger brief filed with the US Bankruptcy Court in connection with the suit against Irving Picard, SIPC noted that under the calculations that plaintiffs Maureen Ebel and Roger and Diane Peskin want to use, they’d get less than they would using Picard’s math.

Indeed, a New York Times story from the same time shows up on the next page of hits: Picard Opponents Claim Math May Be Faulty. I wondered at first if they could really mean Charles Picard and be referencing a French existential math controversy I didn’t know about. Picard was interested in many things, but I did not see how his main results could help decide how to “fairly” divide the money among those cheated by Madoff.

Picard’s Theorems

The Little Picard Theorem is a pretty powerful theorem, and was first proved in 1879. We all should be so lucky to discover a little theorem like this. One of the most important theorems in elementary number theory is “Fermat’s Little Theorem.” Without the latter theorem there would be no modern cryptography—especially the famous RSA public-key cryptosystem would be missing. Sometimes “little” should be translated into “basic and extremely useful.”

The Little Picard Theorem is:

Theorem: If ${f(z)}$ is an entire non-constant function, then its range includes all complex numbers, with at most one exception.

The theorem is as strong as possible: consider the simple entire function ${e^{z}}$. This takes on all possible values, except ${0}$.

This is a huge improvement over a previous theorem of Joseph Liouville, which states that every entire non-constant function must be unbounded. Even Liouville’s theorem can be used to give a short proof of the Fundamental Theorem of Algebra: that every non-constant polynomial has a root. The idea is suppose that ${p(z)}$ is a non-constant polynomial with no root. Then

$\displaystyle f(z) = \frac{1}{p(z)}$

is easily shown to be a bounded entire analytic function. Since it is not constant, this is a contradiction.

Of course there is a Great Picard Theorem, and the same Google hits found me a statement of it with a nod to the Star Trek Captain Picard:

Theorem: Suppose a transporter ${T}$ has holographic capabilities and transports objects from the neighborhood of a black hole to complex places. Then ${T}$ can transport an object to any complex place desired, except possibly one. [statement altered by Ken and I]

In formal terms,

Theorem: If ${f}$ is an analytic function except for an essential singularity at a point ${z_0}$, then in any neighborhood of ${z_0}$, its range includes all complex numbers, with at most one exception.

The Picard Jump

One way to view the Little Picard theorem is that it shows there is a jump in behavior of analytic functions. An analytic function can take on all complex values, or it can miss one like ${e^{z}}$ does, but if it missed two values, then it misses all but one—it is constant. A huge “jump” in behavior: an analytic function takes on all but one value or it misses all but one. There is no analytic function that misses three values.

This behavior occurs elsewhere in mathematics. Here is a general type of statement, where ${\Delta}$ is some non-negligible gap value:

Theorem: All objects ${\cal O}$ have ${\mu({\cal O}) \le m}$. However, if ${\mu({\cal O}) < m}$, then ${\mu({\cal O}) \le m-\Delta}$.

Note, because Picard’s theorems involve infinities they do not quite fit this structure. However there are whole areas of theory that study exactly this type of behavior—for instance, statements in property testing are of this kind.

A Version For Finite Fields

Mike Zieve is a number theorist at Michigan who drew strong hiring interest at Tech, but that is another story, for another time. I want to thank him for relaying a pretty result and proof of a theorem that is like Picard’s, but holds for finite fields.

The theorem is due to Daqing Wan, and the proof is due to Gerhard Turnwald. The result is:

Theorem: If ${f(x)}$ is a degree-${n}$ polynomial over the finite field ${\mathbb{F}_q}$, and ${\#f(\mathbb{F}_q) < q}$, then ${\#f(\mathbb{F}_q) \le q - (q-1)/n}$.

Note this says, that if ${f(x)}$ is a polynomial over a finite field, then either its range is all of the field, or it is quite a bit smaller. For the history of the problem and a proof that the bound is sharp check the following paper.

Let’s compare Wan’s theorem to Picard’s Little Theorem:

Here is Mike’s version of Gerhard Turnwald’s proof of Daqing Wan’s theorem.

Proof: First replace ${f(x)}$ by ${f(x)-f(0)}$, so that we may assume ${f}$ has no constant term. (Note this simple use of a lever.) This clearly does not change the number of values that ${f}$ takes. Define ${g(x)}$ by:

$\displaystyle g(x) = \prod_{a \in \mathbb{F}_q} (x-f(a)).$

For ${0, the coefficient of ${x^{q-i}}$ in ${g(x)}$ is ${(-1)^i}$ times the ${i^{th}}$ elementary symmetric polynomial in the ${f(a)}$‘s. Thus it is a symmetric polynomial in the ${a}$‘s of degree ${n \cdot i}$ that has no constant term. Hence we claim it is zero if ${n \cdot i < q-1}$. To see this, note that ${\prod_{a \in \mathbb{F}_q} (x-a) = x^q - x}$, so the ${j^{th}}$ elementary symmetric polynomial in the ${a}$‘s has value ${0}$ for ${j=1,2,3,\dots,q-2}$, whence the claim follows from the symmetric polynomial theorem.

Thus ${g(x) - x^q}$ has degree at most ${q - (q-1)/n}$. Hence also ${g(x) - (x^q - x)}$ has degree at most ${q - (q-1)/n}$, since we may assume ${n. But ${g(x) - (x^q - x)}$ is not the zero polynomial (since ${\#f(\mathbb{F}_q) < q}$ ), and every element of ${f(\mathbb{F}_q)}$ is a root of ${g(x) - (x^q-x)}$, so ${\#f(\mathbb{F}_q) \le \deg( g(x) - (x^q-x)) \le q - (q-1)/n}$. $\Box$

Further developments may be found in these slides by Wan.

Farbod Shokrieh pointed out that there are many deep connections between Picard’s theorem and modern number theory. He said:

To understand the distribution of values of entire (and meromorphic) functions, the Finnish mathematician Rolf Nevanlinna developed a theory in 1920’s which is now called Nevanlinna theory. It can be considered as a generalization of Picard’s theorem.

It has been observed by Charles Osgood and Paul Vojta that Nevanlinna theory has many analogues in number theory (e.g. Roth’s theorem). Based on the analogies, Vojta has formulated a number of striking and far-reaching conjectures which would imply a wide range of results, known and unknown, in number theory. These include Fermat’s Theorem—not the “little” one and the ABC conjecture. See here for more details.

Clearly plenty to talk about another day.

Open Problems

Can we use the finite field theorem to prove some complexity results? I am especially interested in what happens to polynomial maps ${g: \mathbb{F}_{q}^{2} \rightarrow \mathbb{F}_{q}^{2}}$. Is there a Picard jump here? And if not when is there one?

September 26, 2011 11:53 am

I would add “zero-one” laws as an extreme case of (meta)Theorem in this note.

September 26, 2011 12:35 pm

Since F_q^2 = F_{q^2} can be achieved canonically, the same result should be applied. Of course, it is not clear whether the theorem was tight for F_q, if it is, then it is likely to be for F_{q^2} as well.

September 26, 2011 4:29 pm

It does not seem to be that simple. You would lose the degree information of the
polynomial map f=(f_1(x), f_2(x)) if you use the identification F_{q^2} = F_q^2.

September 27, 2011 2:29 am

For the open problem on two variable map, the following bound is known.
Let f =(f_1, f_2) be a non-surjective polynomial map from F_q^2 to F_q^2,
where each f_i is a polynomial in two variables of total degree at most d over F_q.
Then

# f(F_q^2) \leq q^2 — 2(q-1)/d.

This bound is attained for f =(x_1, x_1x_2) with d=2.

More generally, for a non-surjective polynomial map f=(f_1, …, f_k) from
F_q^k to F_q^k with total degree at most d, we have the bound

# f(F_q^k) \leq q^k — k(q-1)/d.

Is this type of simple bounds useful in complexity theory?

5. September 28, 2011 1:46 pm

The KAM Theorem provides an example of a jump phenomenon in dynamical simulation theory:

• “If a dynamical trajectory is not stable then it’s ergodic”.

Numerous jump principles are folk-theorems and/or rules-of-thumb in systems engineering:

• “Either a gas turbine is dynamically stable or else it is smoking rubble.”

• “Options markets are stable, except during a financial panic.”

• “Either a quantum computer can factor large integers or else it can be simulated with classical resources in P.”

Even in medicine:

• “If you survive your cancer for five years, we’ll call you cured.”

It’s far from obvious how to distill these examples into provable algebraic/complexity-theoretic models, though.

• September 28, 2011 2:09 pm

Three more well-known jump phenomena:

• Near the Shannon Limit, error correction succeeds perfectly or fails utterly.

• Sparse reconstructions converge fast or not at all.

• Linguists can read a language fluently or not at all.

6. October 2, 2011 10:46 am

Hmm, I have not seen the Wan theorem before. It does seem to have some interesting corollaries:

Corollary: Let f be a non-trivial cyclotomic polyomial. Then #f(F_q) <= q – (q-1)/n.

Proof: If f(x)=0 is solvable in F_q then it has to have at least two solutions, so f can't hit every value (it must miss at least one non-zero value). So #f(F_q) <= q – (q-1)/n. If f(x)=0 is not solvable then again f is not hitting every value, so again #f(F_q) <= q – (q-1)/n.

This leads to a question: Is there some characterization of which polynomials satisfy #f(F_q) <= q – (q-1)/n for all finite fields?