Kombinatoryka arytmetyczna - Arithmetic combinatorics

W matematyce kombinatoryka arytmetyczna jest dziedziną z pogranicza teorii liczb , kombinatoryki , teorii ergodycznej i analizy harmonicznej .

Zakres

Kombinatoryka arytmetyczna dotyczy kombinatorycznych szacunków związanych z operacjami arytmetycznymi (dodawanie, odejmowanie, mnożenie i dzielenie). Kombinatoryka addytywna jest szczególnym przypadkiem, gdy w grę wchodzą tylko operacje dodawania i odejmowania.

Ben Green wyjaśnia kombinatorykę arytmetyczną w swojej recenzji „Kombinatoryki addytywnej” autorstwa Tao i Vu .

Ważne wyniki

Twierdzenie Szemerédiego

Twierdzenie Szemerédiego jest wynikiem kombinatoryki arytmetycznej dotyczącej postępów arytmetycznych w podzbiorach liczb całkowitych. W 1936 r. Erdős i Turán wywnioskowali, że każdy zbiór liczb całkowitych A o dodatniej gęstości naturalnej zawiera k terminowy postęp arytmetyczny dla każdego k . To przypuszczenie, które stało się twierdzeniem Szemerédiego, uogólnia twierdzenie van der Waerdena .

Twierdzenie Greena-Tao i rozszerzenia

Twierdzenie Greena-Tao , udowodnione przez Bena Greena i Terence'a Tao w 2004 roku, stwierdza, że ​​ciąg liczb pierwszych zawiera arbitralnie długie ciągi arytmetyczne . Innymi słowy, istnieją ciągi arytmetyczne liczb pierwszych z k wyrazów, gdzie k może być dowolną liczbą naturalną. Dowód jest rozszerzeniem twierdzenia Szemerédiego .

W 2006 Terence Tao i Tamar Ziegler rozszerzyli wynik o progresje wielomianowe. Dokładniej, biorąc pod uwagę dowolne wielomiany o wartościach całkowitych P ₁ ,..., P _k w jednym nieznanym m wszystkie o stałym członie 0, istnieje nieskończenie wiele liczb całkowitych x , m takich, że x  +  P ₁ ( m ), ..., x  +  P _k ( m ) są jednocześnie pierwszymi. Specjalny przypadek, gdy wielomiany to m , 2 m , ..., km implikuje poprzedni wynik, że istnieją ciągi arytmetyczne liczb pierwszych o długości .

Twierdzenie Breuillarda–Greena–Tao

Twierdzenie Breuillarda-Green-Tao, udowodnione przez Emmanuela Breuillarda , Bena Greena i Terence'a Tao w 2011 roku, daje pełną klasyfikację grup przybliżonych. Wynik ten można postrzegać jako nieabelową wersję twierdzenia Freimana i uogólnienie twierdzenia Gromowa na grupy wzrostu wielomianowego .

Przykład

Jeśli A jest zbiorem N liczb całkowitych, jak duża lub mała może być suma

${\ Displaystyle A + A: = \ {x + y: x, y \ w A \},}$

zestaw różnic

${\displaystyle AA:=\{xy:x,y\w A\}}$

i zestaw produktów!

${\ Displaystyle A \ cdot A: = \ {xy: x, y \ w A \}}$

być i jak są ze sobą powiązane rozmiary tych zestawów? (Nie mylić: terminy zestaw różnic i zestaw produktów mogą mieć inne znaczenia.)

Rozszerzenia

Badane zbiory mogą być również podzbiorami struktur algebraicznych innych niż liczby całkowite, na przykład grup , pierścieni i ciał .

Zobacz też

• Teoria liczb addytywnych
• Przybliżona grupa
• Twierdzenie o rogach
• Ergodyczna teoria Ramseya
• Problemy z progresjami arytmetycznymi
• Gęstość Schnirelmanna
• Lemat Shapleya-Folkmana
• Zestaw sydonu
• Zestaw bez sum
• Problem sumaryczno-produktowy

Uwagi

Bibliografia

• Łaba, Izabella (2008). „Od analizy harmonicznej do kombinatoryki arytmetycznej” . Byk. Amer. Matematyka. Soc . 45 (1): 77-115. doi : 10.1090/S0273-0979-07-01189-5 .
• Kombinatoryka addytywna i informatyka teoretyczna , Luca Trevisan, Wiadomości SIGACT, czerwiec 2009
• Bibak, Khodakhast (2013). „Kombinatoryka addytywna z myślą o informatyce i kryptografii”. W Borwein Jonathan M.; Szparliński, Igor E.; Zudilin, Wadim (red.). Teoria liczb i pola pokrewne: Pamięci Alf van der Poorten . 43 . New York: Springer Proceedings w matematyce i statystyce. s. 99–128. arXiv : 1108.3790 . doi : 10.1007/978-1-4614-6642-0_4 . Numer ISBN 978-1-4614-6642-0.
• Otwarte problemy w kombinatoryce addytywnej , E Croot, V Lev
• Od obracających się igieł do stabilności fal: pojawiające się powiązania między kombinatoryką, analizą i PDE , Terence Tao , AMS Notices marzec 2001
• Tao, Terence ; Vu, Van H. (2006). Kombinatoryka addytywna . Studia Cambridge z matematyki zaawansowanej. 105 . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-85386-9. MR  2289012 . Zbl  1127.11002 .
• Granville, Andrzej ; Nathanson, Melvyn B.; Solymosi, József , wyd. (2007). Kombinatoryka addytywna . Proceedings CRM i notatki do wykładów. 43 . Amerykańskie Towarzystwo Matematyczne . Numer ISBN 978-0-8218-4351-2. Zbl  1124.11003 .
• Manna, Henryka (1976). Twierdzenia o dodawaniu: Twierdzenia o dodawaniu teorii grup i teorii liczb (Poprawiony przedruk z 1965 Wiley ed.). Huntington, Nowy Jork: Robert E. Krieger Publishing Company. Numer ISBN 0-88275-418-1.
• Nathanson, Melvyn B. (1996). Teoria liczb addytywnych: podstawy klasyczne . Teksty magisterskie z matematyki . 164 . Nowy Jork: Springer-Verlag. Numer ISBN 0-387-94656-X. MR  1395371 .
• Nathanson, Melvyn B. (1996). Teoria liczb addytywnych: zagadnienia odwrotne i geometria sumsetów . Teksty magisterskie z matematyki . 165 . Nowy Jork: Springer-Verlag. Numer ISBN 0-387-94655-1. MR  1477155 .

Dalsza lektura

• Niektóre najważniejsze elementy kombinatoryki arytmetycznej , materiały Terence'a Tao
• Kombinatoryka addytywna: Zima 2007 , K Soundararajan
• Najwcześniejsze połączenia kombinatoryki addytywnej i informatyki , Luca Trevisan