On the threshold for Szemerédi's theorem with random differences (Q6635163)

Let \(\mathcal{F}\) be a family of subsets of \([N]\). We say that a property of \(\mathcal{F}\) is monotone if \(A\in \mathcal{F}\) and \(A\subseteq B\subseteq [N]\) then \(B\in \mathcal{F}\). The critical size of a property is the smallest \(m\) such that a uniformly random \(m\)-element subset of \([N]\) has the property with probability at least \(1/2\). The critical size is denoted by \(m^{*} = m^{*}(N)\). A set \(D\subseteq [N]\) is called \(t\)-intersective if any set \(A\subseteq [N]\) with positive density contains a \((t+1)\)-term arithmetic progression with common difference in \(D\). For the property \(t\)-intersective, the critical size is denoted by \(m_{t}^{*}(N)\).\N\NIn the last few years, many authors gave upper estimations for \(m_{2}^{*}(N)\). The current record is\N\[\Nm_{2}^{*}(N) \ll N^{1/3+o(1)},\N\]\Nand the conjectured bound is \(\Theta(\log N)\). In this paper the authors extend this result to all \(t \ge 2\) by proving\N\[\Nm_{t}^{*}(N) \ll N^{1-2/(t+1)+o(1)}.\N\]\N\NLet \(G\) be a finite abelian group, \(t\ge 1\) and \(0 < \varepsilon < 1\). A set \(S\subseteq G\) is called \((t,\varepsilon)\)-intersective if every \(A\subseteq G\) of size \(|A| \ge \varepsilon|G|\) contains a \((t+1)\)-term arithmetic progression with common difference in \(D\). For the property \((t,\varepsilon)\)-intersective in \(G\), the critical size is denoted by \(m_{t,\varepsilon}^{*}(G)\). In this paper the authors give the following upper estimation for \(m_{t,\varepsilon}^{*}(G)\).\N\[\Nm_{t,\varepsilon}^{*}(G) \ll C(t,\varepsilon)(\log |G|)^{2t+3}|G|^{1-2/(t+1)}\N\]\Nfor every \(t\ge 2\) and \(0 < \varepsilon < 1\), where \(C(t,\varepsilon)\) is a positive constant. In the last section of the paper the authors give some suggestions to improve the upper bound for \(m_{2}^{*}(N)\).