A relative Szemerédi theorem
The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106219 |
| _version_ | 1811089239035609088 |
|---|---|
| author | Conlon, David Fox, Jacob Zhao, Yufei |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Conlon, David Fox, Jacob Zhao, Yufei |
| author_sort | Conlon, David |
| collection | MIT |
| description | The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for k-term arithmetic progressions in pseudorandom subsets of Z[subscript N] of density N[superscript −c[subscript k]]. The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem. |
| first_indexed | 2024-09-23T14:16:02Z |
| format | Article |
| id | mit-1721.1/106219 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:16:02Z |
| publishDate | 2017 |
| publisher | Springer Basel |
| record_format | dspace |
| spelling | mit-1721.1/1062192022-09-28T19:37:19Z A relative Szemerédi theorem Conlon, David Fox, Jacob Zhao, Yufei Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Zhao, Yufei The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for k-term arithmetic progressions in pseudorandom subsets of Z[subscript N] of density N[superscript −c[subscript k]]. The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem. Simons Foundation. Postdoctoral Fellowship National Science Foundation (U.S.) (grant DMS-1069197) Alfred P. Sloan Foundation Massachusetts Institute of Technology (MIT NEC Corporation Fund Award) Microsoft Research (PhD Fellowship) 2017-01-05T22:56:57Z 2017-01-05T22:56:57Z 2015-03 2016-08-18T15:40:23Z Article http://purl.org/eprint/type/JournalArticle 1016-443X 1420-8970 http://hdl.handle.net/1721.1/106219 Conlon, David, Jacob Fox, and Yufei Zhao. “A Relative Szemerédi Theorem.” Geometric and Functional Analysis 25, no. 3 (March 17, 2015): 733–762. en http://dx.doi.org/10.1007/s00039-015-0324-9 Geometric and Functional Analysis Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Basel application/pdf Springer Basel Springer Basel |
| spellingShingle | Conlon, David Fox, Jacob Zhao, Yufei A relative Szemerédi theorem |
| title | A relative Szemerédi theorem |
| title_full | A relative Szemerédi theorem |
| title_fullStr | A relative Szemerédi theorem |
| title_full_unstemmed | A relative Szemerédi theorem |
| title_short | A relative Szemerédi theorem |
| title_sort | relative szemeredi theorem |
| url | http://hdl.handle.net/1721.1/106219 |
| work_keys_str_mv | AT conlondavid arelativeszemereditheorem AT foxjacob arelativeszemereditheorem AT zhaoyufei arelativeszemereditheorem AT conlondavid relativeszemereditheorem AT foxjacob relativeszemereditheorem AT zhaoyufei relativeszemereditheorem |