Student Number Theory Seminar

John C. Saunders, Department of Pure Math, University of Waterloo

“The Turan Sieve”

Abstract

In 1934, Turan gave an elementary proof of the famous theorem by Hardy and Ramanujan that the normal order of distinct prime factors of n is log log n. More precisely, if ω(n) is the number of distinct prime factors of n, we have n≤x(ω(n) − log log x)2 ≪ x log logx. His proof relied on a sieve method derived from the theory of bipartite graphs. In 2004, Yu-Ru Liu and Ram Murty used the Turan sieve to derive results in combinatorics, including obtaining an improved upperbound on the number of Latin squares, connected graphs, and characters of abelian groups. We will discuss the sieve and how it relates to such problems.

MC 5479