Erdős–Szemerédi-tétel

Az Erdős–Szemerédi-tétel a matematika, azon belül a számelmélet, kombinatorika, az ergodelmélet és a harmonikus analízis határterületén elhelyezkedő aritmetikus kombinatorika fontos eredménye, amit Erdős Pál és Szemerédi Endre 1983-ban bizonyítottak be.[1] A tétel azt állítja, hogy a valós számok bármely véges halmazából képezett páronkénti összegek, illetve páronkénti szorzatok halmazai közül legalább az egyik lényegesen nagyobb elemszámú halmaz az eredetinél. Precízebben, állítja olyan c és ε {\displaystyle \varepsilon } pozitív konstansok létezését, melyekre igaz, hogy

max ( | A + A | , | A ⋅ A | ) ≥ c | A | 1 + ε {\displaystyle \max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }}

ahol A valós számok véges elemszámú, nem üres halmaza, számossága |A|, továbbá A + A = { a + b : a , b ∈ A } {\displaystyle A+A=\{a+b:a,b\in A\}} megegyezik A önmagán értelmezett összeghalmazával és A ⋅ A = { a b : a , b ∈ A } {\displaystyle A\cdot A=\{ab:a,b\in A\}} .

Általában az A + A összeghalmaz akkor összemérhető A-val, ha A számtani sorozat, A · A pedig akkor összemérhető A-val, ha A mértani sorozat. Az Erdős–Szemerédi-tétel felfogható tehát annak a kimondásának, hogy bármekkora is legyen egy véges halmaz, nem képes egyszerre úgy viselkedni, mint egy számtani sorozat és egy mértani sorozat. Más megközelítésben annak a kimondása, hogy a valós számegyenesnek nincs olyan részhalmaza, ami egy véges részgyűrűre vagy résztestre emlékeztet. Az Erdős–Szemerédi-tétel az első példa az összeg-szorzat jelenségre (sum-product phenomenon), amiről ma már ismert, hogy a gyűrűk és testek (köztük a véges testek) jelentős részén fellép.[2]

Erdős és Szemerédi sejtése szerint ε {\displaystyle \varepsilon } 1-hez tetszőlegesen közel vihető. Ebben a tekintetben a legjobb 2009-2016 között Solymosi József eredménye volt,[3] aki bizonyította, hogy ε {\displaystyle \varepsilon } tetszőlegesen közel vihető 1/3-hoz. Ezt 2016-ban Misha Rudnev, Ilya Shkredov és Sophie Stevens javították 1 / 3 + 1 / 1509 {\displaystyle 1/3+1/1509} -re,[4] majd 2018-ban George Shakan 1 / 3 + 5 / 5277 {\displaystyle 1/3+5/5277} -ra.[5]

Jegyzetek

  1. ↑ Erdős, Paul & Szemerédi, Endre (1983), "On sums and products of integers", Studies in Pure Mathematics. To the memory of Paul Turán, Basel: Birkhäuser Verlag, pp. 213–218, ISBN 978-3-7643-1288-6, doi:10.1007/978-3-0348-5438-2_19.
  2. ↑ Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics 4 (2): 59–82, hdl:10515/sy5r78637.
  3. ↑ Solymosi, József (2009), "Bounding multiplicative energy by the sumset", Advances in Mathematics 222 (2): 402–408, DOI 10.1016/j.aim.2009.04.006.
  4. ↑ Sablon:Cite arxiv
  5. ↑ Sablon:Cite arxiv

További információk

  • How a Strange Grid Reveals Hidden Connections Between Simple Numbers - Quanta Magazine article about the sum-product phenomenon.