On the threshold for Szemerédi's theorem with random differences
type: Item
instance of: scholarly article
title: On the threshold for Szemerédi's theorem with random differences
DOI: 10.37236/12415
author: Jop Briët
author: D. Castro-Silva
published in: The Electronic Journal of Combinatorics
publication date: 2024-11-09T00:00:00Z
review text: 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)\).
reviewed by: Sándor Kiss
Mathematics Subject Classification ID: 11B30
Mathematics Subject Classification ID: 05D40
zbMATH DE Number: 7940951
zbMATH Keywords: Szemerédi's theorem
zbMATH Keywords: intersective set
zbMATH Keywords: locally decodable codes
MaRDI profile type: Publication
cites work: A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
cites work: Polynomial extensions of van der Waerden’s and Szemerédi’s theorems
cites work: Threshold functions
cites work: Ruzsa's problem on sets of recurrence
cites work: Q5204830
cites work: Gaussian Width Bounds with Applications to Arithmetic Progressions in Random Settings
cites work: Locally decodable codes and the failure of cotype for projective tensor products
cites work: Random sequences and pointwise convergence of multiple ergodic averages
cites work: Random differences in Szemerédi's theorem and related results
cites work: Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
cites work: Hypergraph regularity and the multidimensional Szemerédi theorem
cites work: Exponential lower bound for 2-query locally decodable codes via a quantum argument
cites work: Concentration of multivariate polynomials and its applications
cites work: The counting lemma for regular k‐uniform hypergraphs
cites work: Regularity Lemma for k-uniform hypergraphs
cites work: On sets of integers containing k elements in arithmetic progression
cites work: Q4768187
cites work: An Introduction to Matrix Concentration Inequalities
cites work: Multiple recurrence and convergence along the primes
description: scientific article; zbMATH DE number 7940951