György Elekes (19 May 1949 – 29 September 2008)
was a
Hungarian mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
and
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
who specialized in
Combinatorial geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...
and
Combinatorial set theory
In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets.
Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom ...
. He may be best known for his work in the field that would eventually be called
Additive Combinatorics
Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are ''inverse problems'': given the size of the sumset is small, what can we say about the structures of and ? In the case of th ...
. Particularly notable was his "ingenious" application of the
Szemerédi–Trotter theorem
The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given points and lines in the Euclidean plane, the number of incidences (''i.e.'', the number of point-line pairs, such that the point ...
to improve the best known lower bound for the
sum-product problem. He also proved that any
polynomial-time algorithm
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
approximating the
volume
Volume is a measure of regions in three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch) ...
of
convex bodies must have a
multiplicative error, and the error grows
exponentially on the dimension.
With
Micha Sharir
Micha Sharir (; born 8 June 1950 in Tel Aviv, Israel) is an Israeli mathematician and computer scientist. He is a professor at Tel Aviv University, notable for his contributions to computational geometry and combinatorial geometry, having authore ...
he set up a framework which eventually led
Guth and
Katz to the solution of the
Erdős distinct distances problem
In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015.
...
.
[The Erdős distance problem](_blank)
(See below.)
Life
After graduating from the mathematics program at
Fazekas Mihály Gimnázium (i.e., "
Fazekas Mihály high school" in
Budapest
Budapest is the Capital city, capital and List of cities and towns of Hungary, most populous city of Hungary. It is the List of cities in the European Union by population within city limits, tenth-largest city in the European Union by popul ...
, which is known for its excellence, especially in mathematics), Elekes studied mathematics at the
Eötvös Loránd University
Eötvös Loránd University (, ELTE, also known as ''University of Budapest'') is a Hungarian public research university based in Budapest. Founded in 1635, ELTE is one of the largest and most prestigious public higher education institutions in ...
. Upon completing his degree, he joined the faculty in the Department of
Analysis
Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
at the university. In 1984, he joined the newly forming Department of
Computer Science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, which was being headed by
László Lovász
László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...
. Elekes was promoted to
full professor
Professor (commonly abbreviated as Prof.) is an academic rank at universities and other post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin as a 'person who professes'. Professors ...
in 2005. He received the ''
Doctor of Mathematical Sciences'' title from the
Hungarian Academy of Sciences
The Hungarian Academy of Sciences ( , MTA) is Hungary’s foremost and most prestigious learned society. Its headquarters are located along the banks of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. The Academy's primar ...
in 2001.
Work
Elekes started his mathematical work in
combinatorial set theory
In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets.
Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom ...
, answering some questions posed by
Erdős
Erdős, Erdos, or Erdoes is a Hungarian surname.
Paul Erdős (1913–1996), Hungarian mathematician
Other people with the surname
* Ágnes Erdős (1950–2021), Hungarian politician
* Brad Erdos (born 1990), Canadian football player
* Éva Erd� ...
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''.
His interest later switched to another favorite topic of Erdős,
discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...
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'')>2
0.99''n''vol(''K''). That is, any polynomial-time estimator of volume over ''K'' must be inaccurate by at least an exponential factor.
Not long before his death he developed new tools in
Algebraic geometry
Algebraic geometry is a branch of mathematics which uses abstract algebraic techniques, mainly from commutative algebra, to solve geometry, geometrical problems. Classically, it studies zero of a function, zeros of multivariate polynomials; th ...
and used them to obtain results in
Discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...
, proving
Purdy's Conjecture.
Micha Sharir
Micha Sharir (; born 8 June 1950 in Tel Aviv, Israel) is an Israeli mathematician and computer scientist. He is a professor at Tel Aviv University, notable for his contributions to computational geometry and combinatorial geometry, having authore ...
organized, extended and published Elekes's posthumous notes on these methods.
[''On lattices, distinct distances, and the Elekes-Sharir framework'',
Javier Cilleruelo, Micha Sharir, Adam Sheffer, https://arxiv.org/abs/1306.0242] Then
Nets Katz Nets Hawk Katz is the W.L. Moody Professor of Mathematics at Rice University. He was a professor of mathematics at Indiana University Bloomington until March 2013 and the IBM Professor of Mathematics at the California Institute of Technology until ...
and
Larry Guth used them to solve (apart from a factor of (log n)
1/2 ) the
Erdős distinct distances problem
In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015.
...
, posed in 1946.
References
External links
Elekes' home page
{{DEFAULTSORT:Elekes, Gyorgy
Number theorists
Combinatorialists
Researchers in geometric algorithms
20th-century Hungarian mathematicians
21st-century Hungarian mathematicians
Hungarian computer scientists
1949 births
2008 deaths