Aritmetická kombinatorika - Arithmetic combinatorics

V matematice aritmetická kombinatorika je pole v průsečíku teorie čísel, kombinatorika, ergodická teorie a harmonická analýza.

Rozsah

Aritmetická kombinatorika je o kombinatorických odhadech spojených s aritmetickými operacemi (sčítání, odčítání, násobení a dělení). Aditivní kombinatorika je zvláštní případ, kdy se jedná pouze o operace sčítání a odčítání.

Ben Green vysvětluje aritmetickou kombinatoriku ve své recenzi „Additive Combinatorics“ od autora Tao a Vu.^[1]

Důležité výsledky

Szemerédiho věta

Szemerédiho věta je výsledkem aritmetické kombinatoriky týkající se aritmetické průběhy v podmnožinách celých čísel. V roce 1936 Erdős a Turán domnělý^[2] že každá sada celých čísel A s pozitivním přirozená hustota obsahuje a k termín aritmetický postup pro každého k. Tato domněnka, která se stala Szemerédiho teorémem, zobecňuje tvrzení van der Waerdenova věta.

Věta o Green – Tao a rozšíření

The Věta o Green-Tao, prokázáno Ben Green a Terence Tao v roce 2004,^[3] uvádí, že posloupnost prvočísla obsahuje libovolně dlouhý aritmetické průběhy. Jinými slovy, existují aritmetické průběhy prvočísel, s k podmínky, kde k může být jakékoli přirozené číslo. Důkazem je rozšíření Szemerédiho věta.

V roce 2006 Terence Tao a Tamar Ziegler rozšířil výsledek tak, aby pokrýval polynomiální průběhy.^[4] Přesněji řečeno, jakýkoli celočíselné polynomy P₁,..., P_k v jedné neznámé m vše s konstantním členem 0, existuje nekonečně mnoho celých čísel X, m takhle X + P₁(m), ..., X + P_k(m) jsou současně prime. Zvláštní případ, kdy jsou polynomy m, 2m, ..., km znamená předchozí výsledek, že existují délky k aritmetický průběh prvočísel.

Příklad

Li A je sada N celá čísla, jak velká nebo malá mohou souprava

${ displaystyle A + A: = {x + y: x, y v A },}$

sada rozdílů

${ displaystyle A-A: = {x-y: x, y v A },}$

a produktová sada

${ displaystyle A cdot A: = {xy: x, y v A }}$

a jak souvisí velikost těchto sad? (Nezaměňovat: podmínky sada rozdílů a sada produktů může mít i jiné významy.)

Rozšíření

Studované množiny mohou být také podmnožinami algebraických struktur jiných než celá čísla, například skupiny, prsteny a pole.^[5]

Viz také

• Teorie aditivních čísel
• Veta o rozích
• Ergodická Ramseyova teorie
• Problémy spojené s aritmetickými průběhy
• Schnirelmannova hustota
• Lemma Shapley – Folkman
• Sidon set
• Sada bez součtu

Poznámky

Reference

• Laba, Izabella (2008). „Od harmonické analýzy k aritmetické kombinatorice“. Býk. Amer. Matematika. Soc. 45 (01): 77–115. doi:10.1090 / S0273-0979-07-01189-5.
• Aditivní kombinatorika a teoretická informatika, Luca Trevisan, SIGACT News, červen 2009
• Bibak, Khodakhast (2013). "Aditivní kombinatorika s ohledem na počítačovou vědu a kryptografii". In Borwein, Jonathan M .; Shparlinski, Igor E .; Zudilin, Wadim (eds.). Teorie čísel a související pole: Na památku Alfa van der Poortena. 43. New York: Springer Proceedings in Mathematics & Statistics. 99–128. doi:10.1007/978-1-4614-6642-0_4. ISBN  978-1-4614-6642-0.
• Otevřené problémy v aditivní kombinatorice, E Croot, V Lev
• Od rotujících jehel po stabilitu vln: rozvíjející se spojení mezi kombinatorikou, analýzou a PDE, Terence Tao „Oznámení AMS z března 2001
• Tao, Terence; Vu, Van H. (2006). Aditivní kombinatorika. Cambridge studia pokročilé matematiky. 105. Cambridge: Cambridge University Press. ISBN  0-521-85386-9. PAN  2289012. Zbl  1127.11002.
• Granville, Andrew; Nathanson, Melvyn B .; Solymosi, József, eds. (2007). Aditivní kombinatorika. Sborník CRM a poznámky k přednášce. 43. Americká matematická společnost. ISBN  978-0-8218-4351-2. Zbl  1124.11003.
• Manne, Henry (1976). Věty o sčítání: Věty o sčítání teorie skupin a teorie čísel (Opravený dotisk 1965 Wiley ed.). Huntington, New York: Robert E. Krieger Publishing Company. ISBN  0-88275-418-1.
• Nathanson, Melvyn B. (1996). Teorie aditivních čísel: klasické základy. Postgraduální texty z matematiky. 164. New York: Springer-Verlag. ISBN  0-387-94656-X. PAN  1395371.
• Nathanson, Melvyn B. (1996). Teorie aditivních čísel: Inverzní problémy a geometrie součtů. Postgraduální texty z matematiky. 165. New York: Springer-Verlag. ISBN  0-387-94655-1. PAN  1477155.

Další čtení

• Některé hlavní body aritmetické kombinatoriky, zdroje od Terence Tao
• Additive Combinatorics: Winter 2007, K. Soundararajan
• Nejranější souvislosti aditivní kombinatoriky a informatiky, Luca Trevisan