Applications of Szemeredi's Theorem

Question

Szemeredi's Theorem is a famous theorem in Additive Combinatorics, Ergodic Theory and maybe some other parts of Mathemtatics:

(Szemeredi's Theorem) Let $\Lambda \in \mathbb{Z}$ be a subset of integers of positive upper density, then $\Lambda$ contains arbitrary long arithmetic progressions.

As I know, the techniques used for prooving the Szemeredi's Theorem are important in Mathematics.

My Questions is this:

• Do you have any example of interesting or important problems that can be solved with Szemeredi's Theorem? (I know that Green-Tao Theorem is one of famous theorems, Szemeredi's Theorem used in solving it.)

Answer 1

If $n$ is a natural number let $f(n)$ denote the largest number of squares in an AP of length $n$ (consisting of integers). As there is no AP of length 4 consisting of squares (Euler), $f(n)\leq r_4(n)$. By Szemeredi's theorem for 4-AP, $r_4(n)=o(n)$, so $f(n)=o(n)$. In fact, this was Szemeredi's orginal motivation for his theorem.

Answer 2

Szemerédi's Theorem (possibly in its dynamical version established by Furstenberg) is used to derive many generalizations and variants of Szemerédi's Theorem itself. I'm not an expert so I give just two examples, but I know there are many more:

• In "Markov processes and Ramsey Theory for trees" (available here), Furstenberg and Weiss prove the following variant of Szemerédi's Theorem for trees: given an integer $h>0$ and $\delta>0$ there is $H(h,\delta)$ such that any subtree of the full binary tree of height $>H(h,\delta)$ and density $>\delta$ contains a full arithmetic subtree of height $h$ (see the paper for the precise definitions).

• The following version of Szemerédi's Theorem relativized to random sets was obtained independently by Conlon and Gowers and by Balogh, Morris and Samotij. Say that a set $E\subset\mathbb{Z}$ is $(k,\delta)$-szemerédi if every subset of $E$ of relative density $\ge \delta$ contains an arithmetic progression of length $k$. Then, given $\delta>0$ and $k\in\mathbb{N}$ there is $C>0$ such that if $p_n\ge C n^{-1/(k-1)}$, then the probability that a random subset of $\{1,\ldots,n\}$ with each element chosen independently with probability $p_n$ is $(k,\delta)$-szemerédi is $1-o_{n\to\infty}(1)$. (The exponent $1/(k-1)$ is easily seen to be sharp.)

The proofs of these results use Szemerédi's Theorem as a black box (rather than adapting its proof), together with substantial new ideas.

Answer 3

In ''A statistical theorem of set addition'', Balog and Szemerédi proved that if a subset $A$ of integers has cardinality $n$ and amount of $cn^{2} $ three-term arithmetical progressions, then $A$ contains $k$- length arithmetical progression for any $k$ when $n$ is large enough. Here $c$ is an absolutely constant. This answered a question of Erdős positively. To prove their result, they first proved nowadays we called it Balog-Szemerédi-Gowers theorem, and then combined it with Freiman theorem and Szemerédi theorem (k-length arithmetic progression).

Answer 4

A recent paper of Klurman and Mangerel proves that any completely multiplicative function $f: \mathbb{N} \to \mathbb{T}$ satisfies $$\liminf_{n \to \infty} |f(n+1)-f(n)|=0.$$ See https://arxiv.org/abs/1707.07817. A stronger result for multiplicative functions is also available. Gowers' quantitative improvement of Szemeredi's theorem (as a black box) is one of three or so key ingredients.