 What's On at UWA
 | UWA Home | Prospective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  | Search UWA Website People Structure Intranet for

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

 * Login to add events... * Today's date is Friday, June 25, 2021
 Groups and Combinatorics Seminar: Combinatorial counting principles in axiomatic number theory Other events...
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.

 Speaker(s) Alan Woods Location Maths Lecture Room 2 Contact Michael Giudici <[email protected]> Start Fri, 11 Nov 2011 13:00 End Fri, 11 Nov 2011 13:45 Submitted by Michael Giudici <[email protected]> Last Updated Wed, 09 Nov 2011 12:47
 Included in the following Calendars:
 Additional Information:
• Locations of venues on the Crawley and Nedlands campuses are available via the Campus Maps website.
• Download this event as: Text | iCalendar
• Mail this event:

Top of Page
 © 2001-2010  The University of Western Australia Questions? Mail [email protected] 