Skip to content

The Informatics Prize

February 13, 2013


From a specialty in Complex Analysis

Nevanlinna

Rolf Nevanlinna was one of the top complex analysts of the last century, and is widely cited as the most famous Finnish mathematician of all time. Many might argue that his contributions go beyond country boundaries, placing him on the list of the greats from the last century.

Today I want to talk about him, his prize, and his work.

Actually Avi Wigderson asked me to announce that it is time to make nominations for the prestigious Rolf Nevanlinna Prize—named after Nevanlinna of course. At GLL we never do announcements…well there are exceptions. Avi is chairing the committee that will award this prize, so please help by nominating deserving young researchers. See here for details.

The prize is given “for outstanding contributions in Mathematical Aspects of Information Sciences”—in many countries the term for computer science is a form of “informatics.” It comes with a medal that has a picture of Nevanlinna and a small mark “RH 83”. The “RH” refers not to the Riemann Hypothesis but to Raimo Heino, the medal’s designer, and “83” to the year of the first minting. The rim has the winner’s name. Pretty cool.

I was always intrigued by complex analysis and took four classes on it as an undergraduate. One was taught by Frank Ryan who then was the quarterback of the Cleveland Browns of the NFL. See a previous discussion about Ryan and his graduate class on complex analysis. This is before the late Art Modell moved the Browns to Baltimore, where they just became the Super Bowl champions.

Nevanlinna’s Work

Since we are talking about Nevanlinna I thought I should say something about his brilliant work. It is not always possible to point out the exact moment when a field was changed by a single paper, but this is exactly what Nevanlinna did in 1925. The paper has been called

“one of the few great mathematical events of our century”

by the eminent Hermann Weyl.

What did Nevanlinna actually do? As a non-expert in complex analysis—four courses or not—I will try to give a high-level flavor of what he did. As usual see any number of survey papers to get the real story. This one by Felix Wong is quite readable. Or see our friends at Wikipedia here.

The easiest functions to consider are polynomials and then rational functions. For example, if {f(z)} is a non-trivial polynomial of degree {d} then we completely understand the number of solutions to

\displaystyle  f(z) = a,

for any complex {a}. The answer is exactly {d}: provided solutions are counted correctly. This is the Fundamental Theorem of Algebra. That the answer is independent of the value of {a} and does not depend on the fine structure of the polynomial may seem obvious now, but it is a beautiful and deep fact. Thus the polynomial {z^{4}} has exactly the same number of solutions (with multiplicities) as

\displaystyle  z^{4} -1881z^{3} +7633z^{2} -200i z + 1.

A remarkable state of affairs.

What happens for rational functions is not too much more complicated, but of course now the functions can also have poles not just roots. Instead of thinking about roots of the equation {f(z)=a} a better way to think about the above is to ask: What values can the function take on? Again the answer for a non-trivial polynomial is simple: the function can take on any finite value. We can twist this statement around and assert the following.

Theorem: If a polynomial {f(z)} misses taking on one value, then it is the constant polynomial.

Statements like the above concern what is called the value distribution of a function.

Nevanlinna Theory

Nevanlinna theory generalizes these facts to transcendental functions. For example the above theorem is false for general analytic functions. Consider {f(z) = e^{z}}. It is easy to see that this function fails to take on the finite value {0}, but is certainly not constant. So the behavior of what values are possible for complex functions beyond polynomials and rational functions is more complicated.

What his theory does is replace the degree of a polynomial by the characteristic function {T_{f}(r)}. The surprise is that one can “summarize” the value behavior of a non-rational function via just one simple-to-define function. Yes it is not a single number like the degree is—it is now a function. But again what it says is that the very fine structure of the function {f} is less important, and what values it takes on can be determined by the simpler function {T_f}. This is the remarkable achievement of Nevanlinna.

Even more surprising is that he proved two “Fundamental Theorems” that allow many important questions about the value distribution of meromorphic functions to be determined. A meromorphic function is the generalization of a rational one: it can have infinitely many poles, provided they are isolated—see here for more information. For an example his theory can be used to prove the following beautiful result: If a meromorphic function omits three values then it must be a constant. I decided not to actually define {T_{f}(r)}, not because it is hard, but because it is better explained in many other places. I will state the ”’First Fundamental Theorem”’ of Nevanlinna theory:

Theorem: For any meromorphic function {f},

\displaystyle  T_{f}(r) = N_{f}(r,a) + m_{f}(r,a) + O(1).

Here {N_f(r,a)} is the number of poles of {\frac{1}{f-a}} among complex numbers of norm at most {r}, and {m_f(r,a)} tracks the magnitude of {\frac{1}{f-a}} on the concentric circles of radius {r}. This and his second theorem allowed him and others to easily derive powerful theorems about the value structure of functions, both re-proving old theorems by simple arguments and proving new ones. One of his many doctoral students, Lars Ahlfors, won one of the first Fields Medals for work on this theory. Of course Ahlfors wrote “the book” on Complex Analysis—at least the book Ken and I learned from in college.

Beyond Meromorphic Functions

The simple function {z \mapsto \overline{z}}, the map from {z} to its conjugate, is not a meromorphic function. Hence it behaves badly—in a different sense from the bad behavior of univariate functions here. The issue, of course, is simple: this function is an automorphism of the complex numbers, but it does not have a smooth derivative. Hence the entire machinery of complex analysis, all the great properties that meromorphic functions have, are not available. Recall an automorphism preserves addition and multiplication:

\displaystyle  \overline{ z + w} = \overline{z} + \overline{w} \text{ and } \overline{ z \cdot w} = \overline{z} \cdot \overline{w}.

Yet the lack of a derivative makes understanding this simple function a huge challenge.

One way to see that understanding {\overline{z}} is so hard is to consider the following class of functions from complex numbers to complex numbers: Let {z \mapsto P(z,\overline{z})} where {P(x,y)} is a polynomial in {x} and {y} with complex coefficients. Call this class generalized polynomials. Understanding them is very hard. For one the following is true:

Conjecture: If {P(z,\overline{z})} is a generalized polynomial and it is locally one-to-one, then it is globally one-to-one.

This is equivalent to the famous, very much open, and annoying Jacobian Conjecture. Thus understanding a “slight” generalized of polynomials is very hard.

The Prize

Nevanlinna was also an able administrator. He chaired the committee creating Finland’s first computer project in 1954, and later served as president of the International Mathematical Union. His passing in 1980 coincided with the realization by the IMU that theoretical computer science had matured alongside mathematics as a discipline. Creating a prize for mathematical computer science—can we call it “informathematics”?—also allowed Finland to endow a major prize that can stand alongside the Nobel Prizes, though it is awarded every four years alongside the Fields Medals and carries the same under-age-40 eligibility condition.

The winners since 1982 have been Bob Tarjan, Les Valiant, Sasha Razborov, Avi, Peter Shor, Madhu Sudan, Jon Kleinberg, and Dan Spielman. It seems to help to go by a short first name—indeed one can scarcely find any reference to the 2006 winner as “Jonathan.”

Open Problems

Who will win? Of course there haven’t even been any nominations yet. Unlike with the Oscars, the nominations are secret anyway. But you can help by nominating candidates.

Does the above idea help with the Jacobian Conjecture? Can we ever make progress on it?

About these ads
12 Comments leave one →
  1. February 13, 2013 3:16 pm

    see also tcs.se, Complex analysis in theoretical computer science
    or check out my blog 1st post for more on Razborov, & an outline of an attack on P vs NP based on a generalization of Razborovs approximation method.

  2. asdf permalink
    February 13, 2013 7:42 pm

    I couldn’t think of a more stupid criterion than an under 40 years requirement. If mathematicians can’t produce anything good beyond that age, then let them prove it by not winning those prices. Besides, Fields never set such a criterion.

  3. February 13, 2013 10:26 pm

    “We choose to forgo defining this function and do other things, not because they are hard, but because they are easy (to look up elsewhere).”

  4. February 14, 2013 12:17 am

    An great note about Rolf Nevanlinna

  5. Jeffrey Shallit permalink
    February 14, 2013 5:49 am

    “Wigderson”, not “Widgerson”. Everybody gets it wrong.

  6. H. Fordt permalink
    February 14, 2013 10:06 am

    It is amazing that although the prize officially covers many areas other than analysis of algorithms, cryptography and complexity, all those who won this award were from these areas. The definition of the prize officially lists the following fields in addition to analysis of algorithms, cryptography and complexity:

    logic of programming languages, computer vision, pattern recognition, information processing and modelling of intelligence.
    Scientific computing and numerical analysis. Computational aspects of optimization and control theory. Computer algebra.

    • Serge permalink
      February 15, 2013 9:19 am

      To some extent, that’s perhaps because the prize is given for outstanding contributions in *mathematical* aspects of information sciences. Some of the other mentioned fields seem more likely to yield new software than new theorems: computer vision, pattern recognition, information processing, modeling of intelligence…

      • H. Fordt permalink
        February 15, 2013 5:47 pm

        All I am saying that there is a very clear official IMU description of the prize. It says explicitly and officially that the prize is intended for the listed areas, so they had in mind also non theorem proving areas that use mathematical insights and methods but don’t necessarily prove theorems. These are definitely mathematical aspects of information sciences that produce important results that I respect very much. The prize description is *not* for new mathematical theorems originating from information sciences, but for *mathematical aspects* of computer science. I am surprised that the initial intention of the prize is not respected and effectively it was hijacked by a certain (important, deep, and politically powerful) subset of the areas for which the prize was made.

      • Serge permalink
        February 15, 2013 7:29 pm

        I hope some jury members will change their minds after reading comments such as yours – although scientists too are sensitive to fashion trends. Anyway, the official list of prize fields looks somewhat hypocritical in view of the history of the prize. It’s rather a list of good intentions, a bit like the list of good resolutions that you make at the beginning of the year…

      • Peter Shor permalink
        March 24, 2013 8:40 am

        Feel free to nominate people who have done great mathematical work in computer vision, pattern recognition, information processing and modelling of intelligence. If nobody nominates anybody in these areas, the chances are that nobody will win.

  7. February 15, 2013 6:24 am

    Dear Dick, how do you see (or where can you find) the equivalence of the conjecture on generalized polynomials with the Jacobian conjecture?

Trackbacks

  1. ETFs Eating Everything, Credit Supernova, Theorems, Nevanlinna « Pink Iguana

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,870 other followers