Two lectures

Last Friday I heard two very interesting lectures. One was the London Mathematical Society’s Mary Cartwright lecture, timed to coincide with the launch of a report by the LMS on good practice in supporting women in academic careers. It was given by Margaret Wright from the Courant Institute. I had been very impressed with the talk she gave at the launch of the International Review report, and knew that there would be a treat in the offing. For an event like this, the big lecturer gets to choose her running mate; she chose Jeff Lagarias, her former colleague at Bell Labs.

Jeff’s lecture had the intriguing title “From ABC to XYZ”. Now ABC recognisably refers to the ABC conjecture in number theory. XYZ is more likely to suggest the XYZ affair, a diplomatic and military row between the United States and France at the end of the eighteenth century (so-called because the letters X, Y and Z were substituted for names when the documents were published). Many years ago, I heard a lecture by Leonard Scott with the title “The XYZ affair”; I think it was on representation theory but cannot remember precisely.

Anyway, Lagarias’ general theme was about how addition and multiplication in the natural numbers interact with one another, and the answer was “Not very well”. Before getting to the ABC conjecture, he gave us a number of examples of this:

  • The theory of the natural numbers with addition (Presburger arithmetic) is decidable, as is the theory of the natural numbers with multiplication (Skolem arithmetic); there are complexity bounds, doubly and triply exponential in the two cases (lower bounds for time complexity and upper bounds for space complexity). But put them together and the result is undecidable.
  • Define the complexity of a natural number n to be the smallest number of ones needed to express n using +, ×, and parentheses. For example, 6 = (1+1)(1+1+1), and indeed, 6 has complexity 5. The complexity of n is between 3log3n and 3log2n. Defining the complexity defect of n to be the complexity minus 3log3n, the values of complexity defect are non-negative real numbers; remarkably, they are well-ordered, with order-type ωω (a result of Altman).
  • the upper Banach density of a set of natural numbers can be at least 1−ε for addition and 0 for multiplication, or vice versa. It is an open problem whether we can replace “at least 1−ε” by 1.
  • The action of the multiplicative group of the rational numbers on the rational adèles (an additive construct) is ergodic, that is, it mixes them up thoroughly. This has been extended to all global fields.

The conjectures of the title concern solutions to a+b = c in the natural numbers. Since signs don’t matter here, we can write more symmetrically a+b+c = 0. The height of such a triple is the maximum of |a|, |b|and |c|; the radical is the product of the prime divisors of abc; and the smoothness is the largest prime divisor of abc. the ABC-conjecture asserts:

For any ε>0, there are only finitely many triples a,b,c with a+b+c = 0 whose height h and radical r satisfy r ≤ h1−ε.

An extreme example is given by the equation 2+310.109−235 = 0, whose height and radical satisfy log r/log h = 0.6315…

The conjecture is important since lots of results and conjectures in number theory, including Fermat’s Last Theorem for large exponents, the Thue–Siegel–Roth theorem, Mordell’s conjecture, Catalan’s conjecture, etc., follow from it. Shinichi Mochizuki has claimed a proof of the conjecture; the proof is 500 pages long, and depends on 500 pages of his previous work, so it may be a while before we have confirmation of his claim.

The XYZ conjecture is a similar statement connecting the height and smoothness. One result about it is the so-called “Alphabet Soup Theorem”, ABC+GRH⇒XYZ, where GRH is the Generalized Riemann Hypothesis.

After tea Margaret Wright spoke. Her title gave little away; the talk was about the Nelder–Mead simplex method in optimization. I met John Nelder (a statistician who, incidentally, almost invented Sudoku); I have used the simplex method (which is not to be confused with the simplex method in linear programming!); but I had no idea that there was a connection.

The simplex method searches for an optimum (let’s say, a minimum) of a function of several variables by moving a simplex around in the space according to five specified rules (with a few parameters which can be tuned). It is especially useful if the objective function is hard to calculate, depends on time-limited observation or measurement, or is “noisy”. After it was proposed, it quickly became very popular for applications, though it doesn’t always work (an example, found by the Scottish mathematician McKinnon, is essentially a small lochan under a cliff), and defied (and still defies) attempts at a thorough analysis. We were shown examples (such as a narrow winding valley) where the simplex adapts itself remarkably to the surrounding geometry.

Wright herself, with Lagarias and others, have obtained results on the convergence of the algorithm in some cases.

[Two misprints corrected]


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , . Bookmark the permalink.

3 Responses to Two lectures

  1. Jon Awbrey says:

    The interaction between addition and multiplication in the natural numbers has long been an interest of mine, leading to broader questions about the relationship between algebra and combinatorics. My gropings with these enigmas led me to the structures of Riffs and Rotes, extracting what we might think of as the “purely combinatorial” properties of primes factorizations. Thinking of the additive structure of the positive integers as embodied in their linear ordering, the first couple of questions that arise here are these —

    • How much of the natural ordering of the natural numbers is purely combinatorial?
    • What extra axioms on the partial ordering of Riffs and Rotes would restore their natural order?

  2. Pingback: Riffs and Rotes : 2 | Inquiry Into Inquiry

  3. Ursula Martin says:

    Lisa Jardine (formerly Queen Mary, now UCL) has a nice piece about Mary Cartwright on the BBC this week

Leave a Reply

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

You are commenting using your 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