5
$\begingroup$

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.)
$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What's $r_4(n)$? $\endgroup$ Feb 6, 2018 at 4:49
  • $\begingroup$ @GerryMyerson $r_k(n)$ is the maximum size of a subset of $[n]$ containing no $k$-term arithmetic progression. en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem $\endgroup$
    – bof
    Feb 6, 2018 at 5:52
  • 2
    $\begingroup$ $r_4(n)=o(n)$ was proved by Szemeredi before he proved "Szemeredi's theorem". $\endgroup$
    – bof
    Feb 6, 2018 at 5:54
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How can there be a stronger result, with a weaker hypothesis? $\endgroup$ Feb 8, 2018 at 21:46
  • 1
    $\begingroup$ The conditions under which the conclusion of the result fails for multiplicative functions (which are not completely multiplicative) are determined. $\endgroup$ Feb 8, 2018 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.