György Elekes (19 May 1949 – 29 September 2008)[1] was a Hungarian mathematician and computer scientist who specialized in Combinatorial geometry and Combinatorial set theory. He may be best known for his work in the field that would eventually be called Additive Combinatorics. Particularly notable was his "ingenious"[2] application of the Szemerédi–Trotter theorem to improve the best known lower bound for the sum-product problem.[3] He also proved that any polynomial-time algorithm approximating the volume of convex bodies must have a multiplicative error, and the error grows exponentially on the dimension.[4] With Micha Sharir he set up a framework which eventually led Guth and Katz to the solution of the Erdős distinct distances problem.[5] (See below.)
György Elekes | |
|---|---|
| Born | 19 May 1949 |
| Died | 29 September 2008 (aged 59) |
| Alma mater | Eötvös Loránd University |
| Known for | Combinatorial geometry Combinatorial set theory Number theory |
| Scientific career | |
| Fields | Mathematics and Computer science |
| Institutions | Eötvös Loránd University |
Life
editAfter graduating from the mathematics program at Fazekas Mihály Gimnázium (i.e., "Fazekas Mihály high school" in Budapest, which is known for its excellence, especially in mathematics), Elekes studied mathematics at the Eötvös Loránd University. Upon completing his degree, he joined the faculty in the Department of Analysis at the university. In 1984, he joined the newly forming Department of Computer Science, which was being headed by László Lovász. Elekes was promoted to full professor in 2005. He received the Doctor of Mathematical Sciences title from the Hungarian Academy of Sciences in 2001.[1]
Work
editElekes started his mathematical work in combinatorial set theory, answering some questions posed by Erdős and Hajnal. One of his results states that if the set of infinite subsets of the set of natural numbers is split into countably many parts, then in one of them, there is a solution of the equation A∪B=C.[1][6] His interest later switched to another favorite topic of Erdős, discrete geometry and geometric algorithm theory. In 1986 he proved that if a deterministic polynomial algorithm computes a number V(K) for every convex body K in any Euclidean space given by a separation oracle such that V(K) always at least vol(K), the volume of K, then for every large enough dimension n, there is a convex body in the n-dimensional Euclidean space such that V(K)>20.99nvol(K). That is, any polynomial-time estimator of volume over K must be inaccurate by at least an exponential factor.[1][4]
Not long before his death he developed new tools in Algebraic geometry and used them to obtain results in Discrete geometry, proving Purdy's Conjecture. Micha Sharir organized, extended and published Elekes's posthumous notes on these methods.[7] Then Nets Katz and Larry Guth used them to solve (apart from a factor of (log n) 1/2 ) the Erdős distinct distances problem, posed in 1946.[5][8]
References
edit- ^ a b c d "Obituary". Eötvös Loránd University. Retrieved 21 March 2010.
- ^ Tao, Terence; Vu, Van H. (2010). "8.3". Additive Combinatorics (Paperback ed.). Cambridge University Press. p. 315. ISBN 978-0-521-13656-3.
- ^ Elekes, György (1997). "On the number of sums and products". Acta Arith. 81 (4): 365–367. doi:10.4064/aa-81-4-365-367.
- ^ a b Elekes, György (1986). "A geometric inequality and the complexity of computing volume". Discrete and Computational Geometry. 1 (4): 289–292. doi:10.1007/bf02187701.
- ^ a b The Erdős distance problem Archived 2011-06-11 at the Wayback Machine
- ^ Elekes, György; Erdős, Paul; Hajnal, András (1978). "On some partition properties of families of sets". Studia Scientiarum Mathematicarum Hungarica: 151–155.
- ^ On lattices, distinct distances, and the Elekes-Sharir framework, Javier Cilleruelo, Micha Sharir, Adam Sheffer, https://arxiv.org/abs/1306.0242
- ^ Guth, Larry; Katz, Nets (January 2015). "On the Erdős distinct distances problem in the plane". Annals of Mathematics: 155–190. doi:10.4007/annals.2015.181.1.2. ISSN 0003-486X.