{ "id": "epe0f5tjba", "slug": "endre-szemeredi", "title": "Endre Szemerédi", "updated": "2026-10-15", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.scientists", "label": "Physical and mathematical scientists", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists" }, { "id": "physical.scientists.mathematics-statistics", "label": "Mathematicians and statisticians", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics" }, { "id": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria", "label": "Logicians, set theorists, and combinatorialists", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria" }, { "id": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.extremal-and-combinatorial-number-theorists", "label": "Extremal and combinatorial number theorists", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.extremal-and-combinatorial-number-theorists" } ], "geo": [ { "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria", "label": "Eastern Europe · 1946 to 2000: Logicians, set theorists, and combinatorialists", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria", "path": [ { "id": "geo.eeu", "label": "Eastern Europe", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu" }, { "id": "geo.eeu.t1946", "label": "Eastern Europe · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946" }, { "id": "geo.eeu.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical" }, { "id": "geo.eeu.t1946.physical.scientists", "label": "Physical and mathematical scientists", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists" }, { "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics", "label": "Mathematicians and statisticians", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics" }, { "id": "geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria", "label": "Logicians, set theorists, and combinatorialists", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.eeu.t1946.physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria" } ] } ], "excerpt": "Endre Szemerédi, born 1940 in Budapest, is a Hungarian mathematician and computer scientist at Rutgers whose 1975 proof of Szemerédi's theorem won the 2012 Abel Prize.", "snippet": "Endre Szemerédi, born 1940 in Budapest, is a Hungarian mathematician and computer scientist at Rutgers whose 1975 proof of Szemerédi's theorem won the 2012 Abel Prize.", "node": "physical.scientists.mathematics-statistics.logicians-set-theorists-and-combinatoria.extremal-and-combinatorial-number-theorists", "markdown": "# Endre Szemerédi\n\n**Endre Szemerédi** (born 21 August 1940, Budapest) is a Hungarian mathematician and theoretical computer scientist whose 1975 proof that every set of integers of positive density contains arbitrarily long arithmetic progressions, now called [Szemerédi's theorem](https://www.edgepedia.org/szemeredis-theorem), and whose regularity lemma became a foundational tool of graph theory and computer science.[1](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf) • [2](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20citation%20eng.pdf) He received the 2012 [Abel Prize](https://www.edgepedia.org/abel-prize) \"for his fundamental contributions to discrete mathematics and theoretical computer science and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory.\"[2](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20citation%20eng.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Born | 21 August 1940, Budapest, Hungary[1](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf) |\n| Education | M.Sc., Eötvös Loránd University, 1965; Ph.D., Moscow State University, 1970, under Israel M. Gelfand[3](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20Biography%20eng.pdf) |\n| Szemerédi's theorem (1975) | Every set of integers of positive upper density contains arithmetic progressions of every finite length[4](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v13i1r99/pdf/) |\n| Regularity lemma | Any graph can be approximated by a bounded number of random-like bipartite graphs; the number of parts grows as a tower of 2s of height proportional to ε⁻⁵[5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf) |\n| Abel Prize 2012 | 6 million Norwegian kronor (about $1 million), awarded by the Norwegian Academy of Science and Letters[6](https://www.science.org/content/article/endre-szemer-di-wins-maths-biggest-prize) |\n| Academies | Hungarian Academy of Sciences, corresponding member 1982, full member 1987; US National Academy of Sciences, 2010[1](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf) |\n| Positions | Alfréd Rényi Institute of Mathematics, Budapest; New Jersey Professor of Computer Science at Rutgers since 1986[1](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf) |\n\n## Life and career\n\nSzemerédi studied at [Eötvös Loránd University](https://www.edgepedia.org/eotvos-lorand-university) in Budapest, taking his M.Sc. in 1965, then moved to [Moscow State University](https://www.edgepedia.org/moscow-state-university), where he completed a Ph.D. in 1970 under the direction of Israel M. Gelfand.[3](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20Biography%20eng.pdf) Since 1986 he has been New Jersey Professor of Computer Science at [Rutgers University](https://www.edgepedia.org/rutgers-university), and he remains affiliated with the HUN-REN Alfréd Rényi Institute of Mathematics in Budapest.[1](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf) • [3](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20Biography%20eng.pdf) The Rényi Institute lists his research areas as extremal graph theory, combinatorial number theory, random graphs, and theoretical computer science.[7](https://renyi.hu/en/staff/endre-szemeredi)\n\nBy 1973 he had published over 30 papers, and in interviews he has described his working style as that of a problem solver.[8](https://mathshistory.st-andrews.ac.uk/Biographies/Szemeredi/) • [9](https://mathematical-research-institute.sydney.edu.au/laureate-interview-endre-szemeredi/)\n\n## Szemerédi's theorem\n\nThe theorem states: for any integer k ≥ 1 and real number 0 < δ ≤ 1, there exists an integer N_SZ(k, δ) such that for every N ≥ N_SZ(k, δ), every set A ⊂ {1, ..., N} with |A| ≥ δN contains an arithmetic progression of length k.[4](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v13i1r99/pdf/) In plain terms, *positive density forces arithmetic structure of every finite length*: a set occupying a fixed positive fraction of the integers, no matter how irregularly arranged, cannot avoid containing runs a, a + d, a + 2d, ..., a + (k−1)d for every k.\n\nThe problem began as a 1936 conjecture of [Paul Erdős](https://www.edgepedia.org/paul-erdos) and [Pál Turán](https://www.edgepedia.org/pal-turan) in the paper *On some sequences of integers*.[8](https://mathshistory.st-andrews.ac.uk/Biographies/Szemeredi/) [Klaus Roth](https://www.edgepedia.org/klaus-roth) proved the length-3 case in 1953; Szemerédi proved the length-4 case in 1969 and the full conjecture for arbitrary k in 1975.[10](https://arxiv.org/html/2206.10037) • [5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf) Erdős paid $1000 for the solution, one of his cash prizes.[6](https://www.science.org/content/article/endre-szemer-di-wins-maths-biggest-prize)\n\n## From Roth to Green–Tao\n\nSzemerédi's theorem does not apply directly to the primes, which have density zero, but it became a key component of the 2008 [Green–Tao theorem](https://www.edgepedia.org/green-tao-theorem) that the primes contain arbitrarily long arithmetic progressions: Ben Green and [Terence Tao](https://www.edgepedia.org/terence-tao) leveraged the pseudorandomness of the primes in a transference argument that carries the dense-set result over to sparse ones.[10](https://arxiv.org/html/2206.10037) • [11](http://www.scholarpedia.org/article/Szemer%C3%A9di%27s_Theorem) Their proof also relied on a structure theorem in the spirit of the regularity lemma, characterizing a dichotomy between structure and randomness.[5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf)\n\n**Four routes to one theorem.** After 1975, essentially four proofs emerged for general k: Szemerédi's combinatorial proof via the regularity lemma and van der Waerden's theorem; [Hillel Furstenberg](https://www.edgepedia.org/hillel-furstenberg)'s 1977 ergodic-theoretic proof, which established the Multiple Recurrence Theorem and, per the Abel citation, opened the connection to ergodic theory; Gowers's Fourier-analytic proof (2002), which gave the first explicit quantitative bounds; and the hypergraph regularity proofs of Gowers and of Nagle, Rödl, Schacht, and Skokan, completed in 2006.[2](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20citation%20eng.pdf) • [11](http://www.scholarpedia.org/article/Szemer%C3%A9di%27s_Theorem) • [12](https://ar5iv.labs.arxiv.org/html/math/0604456)\n\nA related combinatorial route runs through the Ruzsa–Szemerédi triangle removal lemma of 1978: a graph on n vertices with at most εn³ triangles can be made triangle-free by removing at most c(ε)n² edges, where c(ε) → 0 as ε → 0, and Roth's theorem follows from it.[11](http://www.scholarpedia.org/article/Szemer%C3%A9di%27s_Theorem)\n\n## The regularity lemma\n\nThe lemma, found by Szemerédi at the last stage of the work leading to his 1975 theorem, says that for every ε > 0 there exists M such that the vertex set of any graph can be partitioned into at most M parts of comparable size so that most pairs of parts behave pseudorandomly, with edge densities uniform to within ε.[13](https://n.ethz.ch/~ywigderson/math/static/SzemerediNotes.pdf) • [9](https://mathematical-research-institute.sydney.edu.au/laureate-interview-endre-szemeredi/) Informally, any large system can be divided into chunks of roughly equal size that are connected to one another seemingly at random, so a complicated graph can be approximated, in a statistical sense, by a bounded-complexity random-like object whose underlying structure can then be extracted.[6](https://www.science.org/content/article/endre-szemer-di-wins-maths-biggest-prize) • [5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf)\n\nThis approximation principle spread from extremal graph theory and [Ramsey theory](https://www.edgepedia.org/ramsey-theory) into computer science, probability theory, functional analysis, and machine learning in artificial intelligence, and polynomial-time algorithms exist for computing the partition.[5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf) • [6](https://www.science.org/content/article/endre-szemer-di-wins-maths-biggest-prize) Its cost is quantitative: the bound M is proportional to a tower of 2s of height proportional to ε⁻⁵, so the lemma guarantees finite complexity while giving astronomically large numbers in practice.[5](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf)\n\n## Theoretical computer science\n\nSzemerédi's results in computer science include the Ajtai–Komlós–Szemerédi (AKS) sorting network, the Fredman–Komlós–Szemerédi hashing scheme, and the Paul–Pippenger–Szemerédi–Trotter theorem separating deterministic from non-deterministic linear time.[2](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20citation%20eng.pdf) The AKS sorting algorithm is nonadaptive, meaning the next comparison never depends on the outcome of previous ones, and it runs efficiently on cn processors; despite the n log n lower bound for comparisons, it needs no more comparisons than the best adaptive nonparallel algorithm.[14](https://www.ams.org/notices/201302/rnoti-p221.pdf)\n\nWith Erdős he discovered the sum-product phenomenon in their 1983 paper *On sums and products of integers*: roughly speaking, a set of numbers may have nice additive properties or nice multiplicative properties, but not both at the same time.[14](https://www.ams.org/notices/201302/rnoti-p221.pdf) His theorem with Trotter confirmed Erdős's conjecture that the maximal number of incidences between points and lines is much smaller in the real plane than in the projective one.[14](https://www.ams.org/notices/201302/rnoti-p221.pdf)\n\n## By the numbers\n\nQuantitative work on the theorem asks how small the density δ must be, as a function of N, to force a k-term progression. For k = 3 the ladder of known bounds on r₃(N), the largest progression-free subset of {1, ..., N}, runs: Roth 1953, N/log log N; Heath-Brown 1987 and Szemerédi 1990, N/(log N)ᶜ; Bourgain 1999 and 2008, exponents 1/2 and 2/3; Sanders 2012, 3/4; Bloom 2016 and Schoen 2021, refinements of the N/log N form.[10](https://arxiv.org/html/2206.10037) Gowers's proof of the general theorem showed that for every k there is c = c(k) > 0 such that every subset of {1, ..., N} of size at least N(log log N)⁻ᶜ contains a k-term progression, the first explicit quantitative form.[15](https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sz-thm-gowers-proof.pdf)\n\n## Recent developments\n\nIn 2023 Kelley and Meka proved that for some constant β > 0, any subset of {1, ..., N} of size at least 2−O((log N)ᵝ)·N contains a nontrivial three-term arithmetic progression, a quasipolynomial improvement over the previous threshold of N/(log N)¹⁺ᶜ.[16](https://arxiv.org/pdf/2302.05537) This built on Bloom and Sisask's 2020 result breaking the O(N/log N) barrier, which also implied that any set of natural numbers with divergent reciprocal sum contains a three-term progression.[10](https://arxiv.org/html/2206.10037) A separate, algebraic line of attack came from the [polynomial method](https://www.edgepedia.org/polynomial-method): Croot, Lev, and Pach (2017) bounded three-term-progression-free subsets of (Z/4Z)ⁿ by O(3.61ⁿ), and Ellenberg and Gijswijt adapted it to the cap-set bound r₃(F₃ⁿ) = O(2.756ⁿ).[10](https://arxiv.org/html/2206.10037)\n\n## References\n\n1. [Endre Szemerédi biography, IMU/Abel Prize 2012](https://www.mathunion.org/fileadmin/IMU/Prizes/Abel/2012/Abelprize_2012_Szemeredi_Bio.pdf)\n2. [Abel Prize 2012 Citation for Endre Szemerédi](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20citation%20eng.pdf)\n3. [Abel Prize 2012 Biography of Endre Szemerédi](https://abelprize.no/sites/default/files/2021-04/Abel%20prize%202012%20Endre%20Szemeredi%20Biography%20eng.pdf)\n4. [Tao, A quantitative ergodic theory proof of Szemerédi's theorem, Electronic Journal of Combinatorics](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v13i1r99/pdf/)\n5. [Szemerédi's regularity lemma: a survey, DiVA portal](https://www.diva-portal.org/smash/get/diva2:479100/FULLTEXT01.pdf)\n6. [Endre Szemerédi Wins Math's Biggest Prize, Science/AAAS](https://www.science.org/content/article/endre-szemer-di-wins-maths-biggest-prize)\n7. [Endre Szemerédi, HUN-REN Alfréd Rényi Institute of Mathematics](https://renyi.hu/en/staff/endre-szemeredi)\n8. [Endre Szemerédi, MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk/Biographies/Szemeredi/)\n9. [Laureate Interview with Endre Szemerédi, Sydney Mathematical Research Institute](https://mathematical-research-institute.sydney.edu.au/laureate-interview-endre-szemeredi/)\n10. [Bloom–Sisask, Recent progress on bounds for sets with no three terms in arithmetic progression, arXiv](https://arxiv.org/html/2206.10037)\n11. [Szemerédi's Theorem, Scholarpedia (Terence Tao)](http://www.scholarpedia.org/article/Szemer%C3%A9di%27s_Theorem)\n12. [Tao, The ergodic and combinatorial approaches to Szemerédi's theorem, arXiv](https://ar5iv.labs.arxiv.org/html/math/0604456)\n13. [Notes on Szemerédi's regularity lemma, Y. Wigderson, ETH](https://n.ethz.ch/~ywigderson/math/static/SzemerediNotes.pdf)\n14. [Interview with Endre Szemerédi, AMS Notices (2013)](https://www.ams.org/notices/201302/rnoti-p221.pdf)\n15. [Gowers's quantitative proof of Szemerédi's theorem](https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sz-thm-gowers-proof.pdf)\n16. [Kelley–Meka, strong bounds for three-term arithmetic progressions, arXiv (2023)](https://arxiv.org/pdf/2302.05537)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Physical and mathematical scientists › Mathematicians and statisticians › Logicians, set theorists, and combinatorialists › Extremal and combinatorial number theorists*\n\n*Initially written Oct 10, 2026 · Edited: Oct 11, 2026; Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sz-thm-gowers-proof.pdf" ], "url": "https://www.edgepedia.org/endre-szemeredi", "markdown_url": "https://www.edgepedia.org/endre-szemeredi.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Endre Szemerédi\", Edgepedia (EdgeChat), https://www.edgepedia.org/endre-szemeredi. Edgepedia Community License 1.0.", "credit_md": "\"[Endre Szemerédi](https://www.edgepedia.org/endre-szemeredi)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/endre-szemeredi](https://www.edgepedia.org/endre-szemeredi). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Endre Szemerédi\", Edgepedia (EdgeChat), https://www.edgepedia.org/endre-szemeredi. Edgepedia Community License 1.0.", "speakable": "Endre Szemerédi, born 1940 in Budapest, is a Hungarian mathematician and computer scientist at Rutgers whose 1975 proof of Szemerédi's theorem won the 2012 Abel Prize." }