Asymptotic distribution of the number of monochromatic arithmetic progressions in random colourings of the integers

Asymptotic distribution of the number of monochromatic arithmetic progressions in random colourings of the integers

Rissalah, Abdellah (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Delft Institute of Applied Mathematics)

Redig, Frank (mentor)
Gijswijt, Dion (graduation committee)
van den Dries, Bart (graduation committee)
van Elderen, Emiel (graduation committee)

Delft University of Technology

Applied Mathematics

2019

In this thesis we research arithmetic progressions in random colourings of the integers. We ask ourselves how many arithmetic progressions are contained in zero density subsets of the integers? And what is the asymptotic distribution of the number of arithmetic progressions? Key motivation for this research are the famous results of Van der Waerden, Szemerédi and Green-Tao. In chapter 1 we introduce the necessary mathematical background in the form of Ergodic theory. Some key concepts from Ergodic theory are studied and connected to random colourings of the integers. We spent a great deal of time defining various concepts such as zero density sets and the arithmetic progression counting summation. We are able to derive a law of rare events for zero density sets, with the use of moment generating functions. Secondly, we look at different modes of convergence. Various modes of convergence like convergence in probability, distribution, almost sure convergence and total variation are properly defined. This is done to look at the occurrence of arithmetic progressions in zero density sets. We proof that almost surely, zero density sets, generated by independent colourings, contain infinitely many arithmetic progressions of any finite length. A fun application to a stochastic analogue of the prime numbers is presented. In chapter 3 we introduce the Chen-Stein method for Poisson approximation. First we build the basic theory behind the method and show it's application for proving Poisson convergence of the length 1 arithmetic progression counting summation. We show that, by utilizing a very general theorem of Arratia, Goldstein & Gordon, that the number of finite length arithmetic progressions is Poisson distributed. This is the main result of this thesis. We end by giving another application of this theorem to obtain a similar result for the occurrence of very large progressions. Lastly, we try to apply the transfer matrix method as an alternative method for showing Poisson convergence. These transfer matrices are introduced, because they provide explicit expressions and convenient ways of computation for the moment generating function of the arithmetic progression counting summation. We obtain a rigours result for arithmetic progressions of length 1, and a partial result for progressions of length 2. We emphasize that more research is needed on this topic.

Poisson approximation
arithmetic progression
random colourings

http://resolver.tudelft.nl/uuid:cffea4a5-38ed-4152-965a-8ee0b25a87a4

Student theses

bachelor thesis

© 2019 Abdellah Rissalah