On a problem of Gowers. (English. Russian original) Zbl 1149.11006

Shkredov, I. D.

Izv. Math. 70, No. 2, 385-425 (2006); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 70, No. 2, 179-221 (2006).

Given a positive integer \(N\), let \(a_k(N)=N^{-1}\max\{| A| :A\subset [1,N]\), \(A\) contains no arithmetic progression of length \(k\}\), where \(| A| \) stands for the cardinality of \(A\). The well-known Szemerédi’s theorem [E. Szemerédi, Acta Arith. 27, 199–245 (1975; Zbl 0303.10056)] says that \(a_k(N)\to \infty\) as \(N\to\infty\). In 2001 W. T. Gowers [Geom. Funct. Anal. 11, No. 3, 465–588 (2001); Erratum 11, No. 4, 869 (2001; Zbl 1028.11005)] generalizing Roth’s analytic argument for three term progressions and using a variation of Freiman’s inverse problem theorem proved the first effective result on the rate of convergence of \(a_k(N)\) to zero for \(k\geq 4\).
Gowers in the above mentioned paper asked for rate of convergence of
\[ \begin{split} L(N)= N^{-2}\max\{| A|: A\subset[1,N^2],\\ A\text{ contains no triple of the form }(k,m),\;(k+d,m),\;(k,m+d),\;d>0\}. \end{split} \]
It is known that \(L(N)\to0\) as \(N\to\infty\) [cf. e.g. M. Ajtai and E. Szemerédi, Stud. Sci. Math. Hung. 9(1974), 9–11 (1975; Zbl 0303.10046)]. The author proves that if \(A\subset\{1,2,\dots,N\}^2\) is of cardinality at least \(\delta N^2\), where \(\delta>0\), \(N>\exp\exp\exp\{\delta^{-c}\}\), and \(c>0\) is an effective constant, then \(A\) contains a triple of the form \((k,m),(k+d,m),(k,m+d)\), where \(\delta>0\) (such triples are called corners). This result implies that \(L(N)\ll1/(\log\log\log N)^{C_1}\) with \(C_1\) an effective constant.
It is also shown in the paper that conventional methods of Fourier analysis cannot be used in the proof of the main result of the paper. The main ingredients of the proof are based on the notion of \(\alpha\)-uniformity (\(\alpha\)-uniform sets have almost the same number of corners as random sets), the association of sets with bipartite oriented graphs, matrices and their eigenvalues and Gowers technique. In the last section the main result is applied to dynamical systems.

Reviewer: Štefan Porubský (Praha)

MSC:

11B25	Arithmetic progressions
11B75	Other combinatorial number theory
37C25	Fixed points and periodic points of dynamical systems; fixed-point index theory; local dynamics
37B20	Notions of recurrence and recurrent behavior in topological dynamical systems
37A05	Dynamical aspects of measure-preserving transformations
28D05	Measure-preserving transformations

Keywords:

van der Waerden theorem; Szemerédi theorem; arithmetic progression; corner; dynamical system; \(\alpha\)-uniformity; Gower’s technique

Citations:

Zbl 0303.10056; Zbl 1028.11005; Zbl 0303.10046