SEMINAR: Groups and Combinatorics Seminar: Combinatorial counting principles in axiomatic number theory

Groups and Combinatorics Seminar

Alan Woods (UWA)

will speak on

Combinatorial counting principles in axiomatic number theory

at 1pm on Friday 11th of November in Maths Lecture Room 2

Abstract: Proofs of even simple statements in number theory are notorious for being ``tricky''. They often seem to involve concepts that go well beyond what is needed to state the theorem. Is there some way of systematically characterising the assumptions (``axioms'', if you will) required?

It has long been recognised that full Peano Arithmetic (as sometimes briefly encountered in first or second year courses) is actually significantly stronger than what is needed for everyday number theoretic practice (or for that matter, the typical finite combinatorics or finite group theory seminar). An alternative is the axiom system similar to Peano Arithmetic, but with induction hypotheses restricted to being arithmetic formulas having only bounded quantifiers, i.e., ``there exists'' occurs only in the form ``there exists y < x'', and ``for every'' occurs only in the form ``for every y < x''. Such a bounded formula can only ``talk about'' numbers bounded above by the free variables appearing in it. There is a long list of theorems of elementary number theory for which no proof from this weaker axiom system is known, and yet which are provable if, for a suitably chosen bounded arithmetic formula A(x), one adds a census function c(n)=|{x: x < n and A(x)}| counting how many numbers x less than n have the property A(x), and allows induction on bounded quantifier formulas containing c.

Using census functions one can also prove certain combinatorial principles, notably versions of the pigeonhole principle and the equipartition principle - a phenomenon which facilitates some of the applications to number theory.

Examples surveyed briefly should include: the existence of arbitrarily large primes (including recently published joint work with Cornaros), the index of the subgroup of squares in the multiplicative group (mod p) for p prime, Lagrange's four squares theorem, and Jerabek's recent proof of the Quadratic Reciprocity Law which is arguably the logically simplest known proof of this theorem of Gauss.