Corners theorem

Corners theorem In arithmetic combinatorics, the corners theorem states that for every {displaystyle varepsilon >0} , for large enough {estilo de exibição N} , any set of at least {displaystyle varepsilon N^{2}} points in the {displaystyle Ntimes N} grid {estilo de exibição {1,ldots ,N}^{2}} contains a corner, ou seja, a triple of points of the form {estilo de exibição {(x,y),(x+h,y),(x,y+h)}} com {displaystyle hneq 0} . It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem.[1] Dentro 2003, József Solymosi gave a short proof using the triangle removal lemma.[2] Conteúdo 1 Declaração 2 Proof overview 3 Limites quantitativos 4 Multidimensional extension 4.1 Multidimensional Szemerédi's Theorem 5 Referências 6 External links Statement Define a corner to be a subet of {estilo de exibição mathbb {Z} ^{2}} of the form {estilo de exibição {(x,y),(x+h,y),(x,y+h)}} , Onde {estilo de exibição x,y,hin mathbb {Z} } e {displaystyle hneq 0} . Para cada {displaystyle varepsilon >0} , existe um inteiro positivo {estilo de exibição N(varepsilon )} such that for any {displaystyle Ngeq N(varepsilon )} , any subset {displaystyle Asubseteq {1,ldots ,N}^{2}} with size at least {displaystyle varepsilon N^{2}} contains a corner.

The condition {displaystyle hneq 0} can be relaxed to {displaystyle h>0} by showing that if {estilo de exibição A} is dense, then it has some dense subset that is centrally symmetric.

Proof overview What follows is a sketch of Solymosi's argument.

Suponha {displaystyle Asubset {1,ldots ,N}^{2}} is corner-free. Construct an auxiliary tripartite graph {estilo de exibição G} with parts {estilo de exibição X={x_{1},ldots ,x_{N}}} , {displaystyle Y={s_{1},ldots ,s_{N}}} , e {displaystyle Z={z_{1},ldots ,z_{2N}}} , Onde {estilo de exibição x_{eu}} corresponds to the line {displaystyle x=i} , {estilo de exibição y_{j}} corresponds to the line {displaystyle y=j} , e {estilo de exibição z_{k}} corresponds to the line {displaystyle x+y=k} . Connect two vertices if the intersection of their corresponding lines lies in {estilo de exibição A} .

Note that a triangle in {estilo de exibição G} corresponds to a corner in {estilo de exibição A} , except in the trivial case where the lines corresponding to the vertices of the triangle concur at a point in {estilo de exibição A} . It follows that every edge of {estilo de exibição G} is in exactly one triangle, so by the triangle removal lemma, {estilo de exibição G} tem {estilo de exibição o(|V(G)|^{2})} arestas, assim {estilo de exibição |UMA|=o(N^{2})} , como desejado.

Quantitative bounds Let {estilo de exibição r_{angle }(N)} be the size of the largest subset of {estilo de exibição [N]^{2}} which contains no corner. The best known bounds are {estilo de exibição {fratura {N^{2}}{2^{(c_{1}+o(1)){quadrado {registro _{2}N}}}}}leq r_{angle }(N)leq {fratura {N^{2}}{(log log N)^{c_{2}}}},} Onde {estilo de exibição c_{1}Aproximadamente 1.822} e {estilo de exibição c_{2}Aproximadamente 0.0137} . The lower bound is due to Green,[3] building on the work of Linial and Shraibman.[4] The upper bound is due to Shkredov.[5] Multidimensional extension A corner in {estilo de exibição mathbb {Z} ^{d}} is a set of points of the form {estilo de exibição {uma}copo {a+he_{eu}:1leq ileq d}} , Onde {displaystyle e_{1},ldots ,e_{d}} is the standard basis of {estilo de exibição mathbb {R} ^{d}} , e {displaystyle hneq 0} . The natural extension of the corners theorem to this setting can be shown using the hypergraph removal lemma, in the spirit of Solymosi's proof. The hypergraph removal lemma was shown independently by Gowers[6] and Nagle, RodlGenericName, Schacht and Skokan.[7] Multidimensional Szemerédi's Theorem The multidimensional Szemerédi theorem states that for any fixed finite subset {displaystyle Ssubseteq mathbb {Z} ^{d}} , and for every {displaystyle varepsilon >0} , existe um inteiro positivo {estilo de exibição N(S,varepsilon )} such that for any {displaystyle Ngeq N(S,varepsilon )} , any subset {displaystyle Asubseteq {1,ldots ,N}^{d}} with size at least {displaystyle varepsilon N^{d}} contains a subset of the form {displaystyle acdot S+h} . This theorem follows from the multidimensional corners theorem by a simple projection argument.[6] Em particular, Roth's theorem follows directly from the ordinary corners theorem.

References ^ Ajtai, Miklós; Ela pertence a você, Mudar (1974). "Sets of lattice points that form no squares". Stud. Sci. Matemática. húngaro. 9: 9-11. MR 0369299.. ^ Solymosi, Joseph (2003). "Note on a generalization of Roth's theorem". In Aronov, Boris; Basu, Saugata; O cheiro, John; et al. (ed.). Discrete and computational geometry. Algorithms and Combinatorics. Volume. 25. Berlim: Springer-Verlag. pp. 825–827. doi:10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1. MR 2038505. ^ Verde, Ben (2021). "Lower Bounds for Corner-Free Sets". arXiv:0710.3032 [math.CO]. ^ Linial, Nati; Shraibman, Adi (2021). "Larger Corner-Free Sets from Better NOF Exactly-N Protocols". Discrete Analysis. 2021. arXiv:2102.00421. doi:10.19086/da.28933. S2CID 231740736. ^ Shkredov, I.D. (2006). "On a Generalization of Szemerédi's Theorem". Anais da Sociedade Matemática de Londres. 93 (3): 723–760. arXiv:math/0503639. doi:10.1017/S0024611506015991. S2CID 55252774. ^ Saltar para: a b Gowers, Timóteo (2007). "Regularidade do hipergrafo e o teorema de Szemerédi multidimensional". Anais da Matemática. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/anais.2007.166.897. MR 2373376. S2CID 56118006. ^ Rodl, V.; Nagle, B.; Saltador, J.; Schacht, M.; Kohayakawa, S. (2005-05-26). "From The Cover: The hypergraph regularity method and its applications". Anais da Academia Nacional de Ciências. 102 (23): 8109–8113. Bibcode:2005PNAS..102.8109R. doi:10.1073/pnas.0502771102. ISSN 0027-8424. PMC 1149431. PMID 15919821. External links Proof of the corners theorem on polymath. Categorias: 1974 introductions1974 in mathematicsRamsey theoryAdditive combinatoricsTheorems in combinatorics