Colourings, Discrepancies and Arithmetic Progressions

Colourings, Discrepancies and Arithmetic Progressions

Serdar Boztas, RMIT

Date: Friday 11th October
Time: 3-4pm (Talk & Q/A)
Venue: Building 8 Level 9 Room 66 (AGR) RMIT City campus

The seminar will be followed by snacks and drinks
All students, staff and visitors are welcome

ABSTRACT: In the 1920’s Van der Waerden showed that any two-coloring of the natural numbers must contain an infinite monochromatic arithmetic progression. This was the beginning of discrepancy theory.

Given a colouring of the natural numbers by the map χ :N → {± 1}, the
discrepancy of a set A⊂N under that colouring is DISC(χ,A) = ∑a ∈ A χ(a)
and the discrepancy DISCχ(𝒜 ) of the colouring χ on a family of sets 𝒜 is
the largest absolute value of the discrepancies of the sets A ⊂ 𝒜 belonging
to the family. The discrepancy of the family 𝒜 is then defined as
The discrepancy of the family 𝒜 is then defined as
DISC(A):=minχ max {DISC(χ,A): A ⊂ 𝒜},
with the minimization being taken over all colourings. Informally this measures how unbalanced the most balanced colouring can be on 𝒜.

In the 1960’s Klaus Roth proved that if 𝒜 is the collection of all arithmetic progressions inside N, the discrepancy of this family is infinite. He actualy proved that the collection of arithmetic progressions supported on {1,2,…,n} is lower bounded by cn1/4. Behrend proved about 30 years later that this result is essentially best possible up to logarithmic factors.

The family of homogeneous arithmetic progressions also have infinite discrepancy, proved by Terry Tao in 2016, using ergodic theory and pretentious characters. This proof came after an online collaboration named Polymath 5, where he was an active participant. Timothy Gowers, who organised Polymath 5, has commented that Tao’s proof is “unlikely to yield an explicit growth rate of log n or higher. It is known from a construction by Peter Borwein and coauthors that any lower bound cannot be more that c log n.

We discuss a modern version of Roth’s proof and indicate a path towards obtaining an explicit lower bound on the growth rate of the discrepancy of homogeneous arithmetic progressions.

BIOGRAPHY: Serdar Boztas received the S.B. degree from the Massachusetts Institute of Technology, in 1983 and the M.S. and Ph.D. degrees from the University of Southern California in 1986 and 1990, respectively, all in electrical engineering.

He was a Research Engineer at the Telecom Australia Research Laboratories in 1991-1992, and a Lecturer in the School of Electrical and Computer Systems Engineering at Monash University in 1993-1995. Since 1996 he has been with RMIT University, Melbourne, Australia, where he is presently an  Associate Professor in the Discipline of Mathematics.

Serdar was an invited speaker at the 2014 IEEE International Workshop on Signal Design and Applications, in Tokyo, as well as in ISC 2007 and SSGRR 2001. He was Program Committee Chair for AAECC (Applied Algebra, Algebraic Algorithms and Error Correcting Codes) Symposia in 2001 and 2007 as well as the General Chair for the Australasian Conference in Information Security and Privacy  in  2011.

His interests include pseudorandom sequence design, combinatorics, randomness testing, coding and information theory, cryptography and  information security.