Erdős – Szemerédiho věta - Erdős–Szemerédi theorem

v aritmetická kombinatorika, Erdős – Szemerédiho věta, prokázáno Paul Erdős a Endre Szemerédi v roce 1983,^[1] uvádí, že pro každého konečná množina z reálná čísla, buď párové součty, nebo párové produkty čísel v množině tvoří podstatně větší množinu. Přesněji řečeno, tvrdí existenci kladných konstant C a ${ displaystyle varepsilon}$ takhle

${ displaystyle max (| A + A |, | A cdot A |) geq c | A | ^ {1+ varepsilon}}$

kdykoli A je konečná neprázdná množina reálných čísel mohutnosti |A|, kde ${ displaystyle A + A = {a + b: a, b v A }}$ je součet z A sám se sebou a ${ displaystyle A cdot A = {ab: a, b v A }}$.

Je možné pro A + A mít srovnatelnou velikost jako A -li A je aritmetický postup, a je možné pro A · A mít srovnatelnou velikost jako A -li A je geometrický průběh. Erdős – Szemerédiho teorém lze tedy chápat jako tvrzení, že není možné, aby se velká množina chovala jako aritmetická posloupnost a současně jako geometrická posloupnost. Lze jej také považovat za tvrzení, že skutečná čára neobsahuje žádnou množinu připomínající konečný podřetězec nebo konečné podpole; je to první příklad toho, co je nyní známé jako fenomén součtového produktu, o kterém je nyní známo, že drží v široké škále prstenů a polí, včetně konečných polí.^[2]

Erdős a Szemerédi se domnívali, že si člověk může vzít ${ displaystyle varepsilon}$ libovolně blízko k 1. Nejlepším výsledkem v tomto směru je v současné době George Shakan,^[3] kdo ukázal, že člověk může vzít ${ displaystyle varepsilon}$ libovolně blízko ${ displaystyle 1/3 + 5/5277}$. Misha Rudnev, Ilya Shkredov a Sophie Stevens dříve ukázaly, že člověk může ${ displaystyle varepsilon}$ libovolně blízko ${ displaystyle 1/3 + 1/1509}$,^[4] zlepšení dřívějšího výsledku o József Solymosi,^[5] kdo ukázal, že se to dá libovolně přiblížit${ displaystyle 1/3}$.

externí odkazy

• Jak podivná mřížka odhaluje skrytá spojení mezi jednoduchými čísly - Časopis Quanta článek o fenoménu součtového produktu.

Reference