**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⊂*under that colouring is

**N***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

*cn*. Behrend proved about 30 years later that this result is essentially best possible up to logarithmic factors.

^{1/4}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.