Arithmetic Progressions - Almost Periodicity

The purpose of this repository is to digitise some mathematical definitions, theorem statements and theorem proofs. Digitisation, or formalisation, is a process where the source material, typically a mathematical textbook or a pdf file or website or video, is transformed into definitions in a target system consisting of a computer implementation of a logical theory (such as set theory or type theory).

The source

The definitions, theorems and proofs in this repository are taken from the exposition of Bloom and Sisask on the Kelley-Meka bound on Roth numbers 2302.07211.

The main result is that there is some constant c > 0 such that, if A ⊆ {1, ..., N} contains no non-trivial arithmetic progression of length 3, then |A| ≤ N/exp(c * (log n)^(1/12))) for some constant c > 0. This is an amazing improvement over previous bounds, which were all of the form N/(log n)^c for some constant c.

The target

The formal system which we are using as a target system is Lean’s dependent type theory. Lean is a project being developed at AWS and Microsoft Research by Leonardo de Moura and his team.

At this stage, mathlib4 contains all the background material that we need. However, not all quality-of-life improvements that we know from Lean 3 have made it to Lean 4 (yet) and Lean 4 suffers from its own problems that currently make it unsuitable for new formalisation of research-level mathematics. As a consequence, we are sticking to Lean 3 until the project is complete. Then we will port it to Lean 4 in order to upstream our basic results.

Content of this project

This project currently contains about 3k lines of Lean code about the discrete (difference) convolution, discrete Lp norms, discrete Fourier transform. It also contains proofs of a version of almost periodicity and of a quantitative version of the Marcinkiewicz-Zygmund inequality.

Once finished, this project will contain two main results (here R is the Roth number, the maximum size of a set without three term arithmetic progressions):

The finite field case: A proof that R(F_q^n) ≤ q ^ (n - c * n ^ (1/9)) for some constant c. This is worse than the Ellenberg-Gijswijt bound R(F_q^n) ≤ q ^ (n - c * n) which was formalised in Dahmen, Hölzl, Lewis. The goal here is therefore not to improve on the existing bound but instead demonstrate the probability and Fourier analysis techniques, whereas Ellenberg-Gijswijt used the polynomial method.
The integer case: A proof that R(n) ≤ N/exp(c * (log n)^(1/9))), using the same techniques as in the finite field case, except for the fact that we now use Bohr sets instead of subspaces. This bound is a slight improvement over the Kelley-Meka bound (with 1/12 as the exponent instead of 1/9). It is due to Bloom and Sisask.

Code organisation

The Lean code is contained in the directory src/. The subdirectories are:

Mathlib: Material missing from existing mathlib developments
Prereqs: New developments to be integrated to mathlib
Physics: The physical (as opposed to Fourier space) proof steps that are shared between the finite field cases and integer case
FiniteField: The proof steps specific to the finite field case
Integer: The proof steps specific to the integer case

Current progress

The project is not yet finished. The following table details live which files are unfinished, and how many ‘sorries’ (unproven statements) remain in each file.

File	Sorries
APAP: FiniteField: Basic	6
APAP: Mathlib: Tactic: Positivity	14
APAP: Physics: Unbalancing	2
APAP: Prereqs: Bohr: Basic	1
APAP: Prereqs: Bohr: Regular	1
APAP: Prereqs: Discrete: DFT: Basic	2
APAP: Prereqs: Discrete: DFT: Compact	1
APAP: Prereqs: Discrete: LpNorm: Basic	1
APAP: Prereqs: Discrete: LpNorm: Compact	2
APAP: Prereqs: Discrete: LpNorm: Weighted	1

What next?

Almost periodicity is nowadays a standard tool in additive combinatorics. The version we formalised is sufficient for many applications. In particular, it gives one of the best known bounds on Freiman’s theorem. As a side goal, we might tackle Freiman’s theorem.

The discrete convolution/Lp norm/Fourier transform material belongs in mathlib and we hope to PR it there once the transition to Lean 4 has completed. Almost periodicity should similarly be upstreamed to mathlib given the numerous applications. The rest of the material might forever live in this repository.

On top of the new developments, there are many basic lemmas needed for this project that are currently missing from mathlib.

Here is the list of files that do not depend on any other LeanAPAP file, indicating they are good candidates for upstreaming to mathlib:

Build the Lean files

To build the Lean files of this project, you need to have a working version of Lean. See the installation instructions (under Regular install). Alternatively, click on the button below to open a Gitpod workspace containing the project.

In either case, run lake exe cache get and then lake build to build the project.

Build the blueprint

To build the web version of the blueprint, you need a working LaTeX installation. Furthermore, you need some packages:

sudo apt install graphviz libgraphviz-dev
pip install -r blueprint/requirements.txt

To actually build the blueprint, run

lake exe cache get
lake build
inv all

Acknowledgements

Our project builds on mathlib. We must therefore thank its numerous contributors without whom this project couldn’t even have started.

Much of the project infrastructure has been adapted from

Source reference

[BS] : https://arxiv.org/abs/2302.07211