Raising the roof on the threshold for Szemerédi‘s theorem with random differences

EUROCOMB’23

Abstract
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi‘s theorem with random differences is bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions. This improves the previous best bounds of $N^{1-\frac{1}{\lceil{k/2}\rceil} + o(1)}$ for all odd $k$.

Pages:
231–237
References

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, and Peter Manohar, A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation, 2022, Electronic Colloquium on Computational Complexity (ECCC). Report no. TR22-101.
https://doi.org/10.1145/3564246.3585143

Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf, A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs, 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2008, pp. 477-486.
https://doi.org/10.1109/FOCS.2008.45

V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, J. Amer. Math. Soc. 9 (1996), no. 3, 725-753. MR 1325795
https://doi.org/10.1090/S0894-0347-96-00194-4

B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35-38. MR 905149
https://doi.org/10.1007/BF02579198

J. Bourgain, Ruzsa's problem on sets of recurrence, Israel J. Math. 59 (1987), no. 2, 150-166. MR 920079
https://doi.org/10.1007/BF02787258

Jop Briët, Zeev Dvir, and Sivakanth Gopi, Outlaw distributions and locally decodable codes, Theory Comput. 15 (2019), Paper No. 12, 24. MR 4028880
https://doi.org/10.4086/toc.2019.v015a012

Jop Briët and Sivakanth Gopi, Gaussian width bounds with applications to arithmetic progressions in random settings, Int. Math. Res. Not. IMRN (2020), no. 22, 8673-8696. MR 4216700

Jop Briët, On embeddings of l k 1 from locally decodable codes, 2016.
https://doi.org/10.1007/978-3-642-27848-8_708-1

Michael Christ, On random multilinear operator inequalities, 2011.

Nikos Frantzikinakis, Emmanuel Lesigne, and Máté Wierdl, Random sequences and pointwise convergence of multiple ergodic averages, Indiana Univ. Math. J. 61 (2012), no. 2, 585-617. MR 3043589
https://doi.org/10.1512/iumj.2012.61.4571

Nikos Frantzikinakis, Emmanuel Lesigne, and Máté Wierdl, Random differences in Szemerédi's theorem and related results, J. Anal. Math. 130 (2016), 91-133. MR 3574649
https://doi.org/10.1007/s11854-016-0030-z

Harry Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256. MR 498471
https://doi.org/10.1007/BF02813304

Iordanis Kerenidis and Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, J. Comput. System Sci. 69 (2004), no. 3, 395-420, Preliminary version in STOC'03. MR 2087942
https://doi.org/10.1016/j.jcss.2004.04.007

E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. MR 369312On the threshold for Szemerédi's theorem with random differences 7
https://doi.org/10.4064/aa-27-1-199-245

Nicole Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes S p (1 ≤ p < ∞), Studia Math. 50 (1974), 163-182. MR 355667

P. Varnavides, Note on a theorem of Roth, J. London Math. Soc. 30 (1955), 325-326. MR 76797
https://doi.org/10.1112/jlms/s1-30.3.325

Trevor D. Wooley and Tamar D. Ziegler, Multiple recurrence and convergence along the primes, Amer. J. Math. 134 (2012), no. 6, 1705-1732. MR 2999293
https://doi.org/10.1353/ajm.2012.0048

Metrics

0

Views

0

PDF views