AustMS 2019 talks

Just so I have these somewhere, these are the notes/slides for the two talks I gave at the annual Australian Mathematical Society talk last week. The first is a revision of this talk.

Terry Tao’s first paper: “Perfect numbers”

Terry Tao has just been awarded the inaugural Riemann prize, and as a result I discovered he had his first mathematics paper published at age 8, in a (now defunct) journal for school mathematics in my home state of South Australia. Since this rare item only appears available reproduced as an appendix in a scanned pdf of a 1984 article in an education journal, I thought I’d re-typeset it. So here it is:

Terence Tao, Perfect numbers, Trigon (School Mathematics Journal of the Mathematical Association of South Australia) 21 (3), Nov. 1983, p. 7–8. (pdf)

Note that this appeared 13 years before his earliest listed paper in Math Reviews/MathSciNet.

Edit: I made a GitHub repository for the paper, the LaTeX source, and the code (working, after minor edits) from it. I passed it on to Tao already.

Diagonal arguments: once more with feeling

I’ve been thinking more about the diagonal argument this week, and realised my version for magmoidal cats with diagonals was insufficient to cover a massively important example: the category of partial recursive functions! This is because every partial endomorphism \mathbb{N} \to \mathbb{N} has a fixed global point, namely the undefined point: the partial function 1 \to \mathbb{N} with empty domain. The same problem holds for arbitrary generalised points X \to \mathbb{N}. So the diagonal argument can’t get started. Any general diagonal argument should be able to deal with the special case of partial recursive functions without special tweaks to deal with such behaviour. So while my magmoidal diagonal argument is valid, it needs more work to apply where one has partial functions.

Continue reading “Diagonal arguments: once more with feeling”

The only curve with a unique focus is the parabola

Recently, an article with a breathless headline (since revised) was published on the ABC website about how a year 12 student in regional Victoria, Mubasshir Murshed, published a proof of the above result in an academic journal. I think this a good achievement and to be commended, but the way it is framed is…problematic.  The original headline, “Teenager’s parabola equation blows away maths world” could have done with some input from mathematicians (I understand how news works, the journalist probably had little choice in the matter). The quote from the editor of the Australian Mathematics Education Journal also seems to me to lack perspective. Publishing in an education journal is not the same as publishing in a mathematics journal, which requires something genuinely previously undiscovered.

I’m all for furthering the idea that everyone can discover interesting mathematics themselves, even if it was already known. That’s part of the fun in mathematics, figuring out how to understand existing work in a new way, or even the joy of realising you discovered a piece of ‘real’ mathematics that someone else had thought of. I definitely had fun deconstructing the proof and rewriting it (below!) in a way I felt more comfortable with. But heralding someone who does this as a “17-year-old mathematics genius” is, I feel, counterproductive to the promotion of mathematics more broadly. It can definitely prompt people to put themselves in the “I’m not a genius, I can’t do mathematics” box, when this is just not true. My colleague David Butler engages with people of all kinds of backgrounds with public mathematical play, and they often are doing little pieces of mathematical discovery without even realising it. Praising up doing mathematics as a work of “genius” alienates people.

It’s easy to praise such an achievement as Murshed’s, but the article missed an opportunity to highlight the way in which discovery in mathematics is cheap: you don’t need any special equipment! With access to the internet, and pen and paper there is little limit to what kinds of theoretical mathematics you can do. The idea that problems such as the result in the title are even amenable to proof is genuinely important. That abstract-looking mathematics can have a real-world impact (parabolic reflector design!) is important to know for non-mathematical policy-makers at the all levels, but also for people genuinely if there is to be an appreciation of mathematics in today’s society. There is also the message that mathematics is not ever truly finished, and that there can be more than one way to approach a theorem and its proof (see below).

With the grumpiness out the way (and I’m happy to discuss the pros and cons), I want to give a variation on the theorem and proof, assuming less than Murshed’s version. I am happy to take as a black box one of the equations he derives, because that is done by elementary geometry.

Theorem: A plane curve given by the graph of a differentiable function and with a unique focus is a parabola.

Continue reading “The only curve with a unique focus is the parabola”

Third solution to writing 3 as a sum of three third powers!

Andrew Booker and Andrew Sutherland have found, using the the Charity Engine distributed computing platform, a third solution in integers to the equation x^3 + y^3 + z^3 = 3, so we now know each of

  • 13 + 13 + 13

  • 43 + 43 + (-5)3

  • 5699368212219623807203 + (-569936821113563493509)3 + (-472715493453327032)3 (verify!)

is equal to 3. It is conjectured that there are infinitely many integer solutions, but we seem to be nowhere near that.

Talk notes from Groupoids, Graphs and Algebras

This week I am at the conference Groupoids, Graphs and Algebras in Sydney. I gave a talk based on these two blog posts:

As well as the preprint

(which is a sequel to the papers Internal categories, anafunctors and localisations and
On Certain 2-Categories Admitting Localisation by Bicategories of Fractions).

The handwritten notes for my talk are here.

Believing in (in-)consistency

By this I mean the consistency, or inconsistency, of certain systems of mathematical axioms. There are very few systems, of very low strength, that we know are consistent. Presburger arithmetic is complete and consistent (and even decidable, but the decision procedure is has at least doubly-exponential runtime) but cannot even define the multiplication function \mathbb{N} \times \mathbb{N} \to \mathbb{N}. Once one has a system of axioms with at least the expressive strength of Robinson arithmetic Q (which doesn’t include induction!), then Gödel’s theorem kicks in and one can construct undecidable statements in the system, including the self-consistency sentence. However, one can get consistency statements assuming an extra fact, namely that if one assumes that the system could prove a certain countable ordering is in fact well-founded then consistency follows. This is known as ordinal analysis, and the original result due to Gentzen is that if one has the axioms of Peano arithmetic (PA) plus the assumption that the set of finite rooted trees (with a certain natural ordering) is well-founded, then PA is consistent. This follows from careful analysis of PA proofs, which are represented (following Gentzen) as finite rooted trees. Another way to look at it is that this ordered set is the ‘smallest ordinal PA cannot prove is well-ordered’, though this requires an external viewpoint. Often people implicitly identify the set of finite rooted trees with the (von Neumann) ordinal ε0.

One might ask in what system such implications are proved—what is the metatheory here? This leads to the remark in a blog post by Russell O’Connor:

As I understand, Gentzen showed that believing in the consistency of PA is equivalent to believing in the well-foundedness of ε0. This can be rephrased as a claim that a particular program, say the hydra game, terminates on all inputs. Therefore, if you believe in the well-foundness of ε0 and you believe Gentzen’s argument, which is done in PRA, then you believe PA is consistent, even if it has impredicative induction principles.

PRA has consistency strength equivalent to the well-foundness of ωω, which can be stated again as the termination of some other program on all inputs. Presumably this equivalence is proved in a still weaker system.

Curious about this ‘still weaker system’, I asked on MathOverflow “What is the weakest system that suffices to prove that well-foundedness of ωω implies consistency of PRA?” Emil Jeřábek provided a very nice answer, and even ironed out some wrinkles: it gets more difficult to talk about what well-foundedness means as the background theory gets weaker. Instead of the classical definition, which requires talking about subsets of the collection, one talks about induction schema instead, and how complex formulas can be that one wants to use. But in any case, the short answer is that the ‘still weaker system’ is the theory PA, which is roughly the part of PA that models an ordered semiring (ie the natural numbers with their ordering) with no induction. This is basically Robinson arithmetic, which while incomplete (after Gödel) it is “only just” incomplete.

This then gets to the heart of ordinal analysis: if one believes the fragment of arithmetic capturing the ordered semiring structure of \mathbb{N} is consistent, then well-foundedness of ωω implies consistency of PRA. So then one should feel comfortable with Gentzen’s proof that PA’s consistency follows from the well-foundedness of ε0. One may, like Voevodsky, question the consistency of PA, but the soundness of the proof of the implication only requires ‘believing’ a much weaker system is consistent.

One can represent, as Jeřábek does on MathOverflow, the set ωω as the set of all finite tuples of natural numbers; in essence \bigcup_n \mathbb{N}^n, with an ordering—the shortlex order—reminiscent of the plain ordering of the natural numbers expressed in some base (secretly this is base ω!). I have a hard time imagining how this can fail to be well-founded, if I make the background assumption that ω itself is well-founded. And that is the point: one reduces consistency arguments to very concrete syntactical structures. We try to bootstrap ourselves up into believing systems are consistent through this process, though we really don’t know what the ordinal consistency strength for eg ZFC or even Z is.

One could try to go down the rabbit hole, and ask what is the corresponding result for Q: what well-foundedness statement is enough to prove Q’s consistency? But it appears that the theories are getting so weak that one needs to resort to different tools. As far as PA is concerned, Timothy Chow gives a conceptual statement (see Theorem 2) equivalent to the well-foundedness of ε0

THEOREM 2. If M is a Turing machine that given i as input, outputs an ordinal M(i), and M(i) ≥ M(i+1) for all i, then the sequence stabilizes.

with a footnote saying “the theorem can be further weakened to assert the stabilization of all primitive recursive descending sequences of ordinals”. (Here by “ordinals” Chow means something he describes in finitary terms using finite nested lists à la Lisp)

If you find it ‘intuitive’ that ωω is well-founded, and Theorem 2 of Chow’s note convincing, then you have just been convinced that PA is consistent.