Combinatorică aditivă

Combinatoria aditivă (din engleză  adăugare  - adăugare) este o zonă interdisciplinară [1] a matematicii care studiază interdependența diferitelor interpretări cantitative ale conceptului de structurare a unui subset al unui grup (de regulă, finit), precum și ca proprietăţi similare ale derivatelor unui set de structuri utilizate în aceste interpretări. În plus, combinatoria aditivă studiază structurarea în diverse sensuri a unor mulțimi sau clase specifice de mulțimi (de exemplu, submulțimi de numere prime sau subgrupuri multiplicative ).

Astfel, obiectul principal de studiu îl constituie mulțimile finite , cât mai abstracte posibil, limitate uneori doar în dimensiunea lor, ceea ce face ca această știință să fie asemănătoare combinatoriei . Totuși, spre deosebire de combinatorică ca atare, unde elementele mulțimilor sunt identificate doar prin diferența lor între ele și aparținând unuia sau altuia multimi luată în considerare, în combinatorică aditivă fiecare element al mulțimii are o semnificație clară, iar între ele apar relații suplimentare. , care decurg din valorile și proprietățile lor de funcționare a grupului (și, eventual, legi specifice specifice grupului dat).

Combinatoria aditivă este strâns legată de combinatoria aritmetică , unde subiectul de studiu este relația dintre un subset al unui câmp (și nu doar un grup, ca aici) cu două operații simultan - adunarea și înmulțirea.

Condiții preliminare pentru apariția

Teoria numerelor aditive

Problemele reprezentării numerelor prin sume de elemente dintr-un număr mic de mulțimi date au fost luate în considerare de matematicieni încă din cele mai vechi timpuri. Exemplele clasice sunt problemele de reprezentabilitate a oricărui număr prin suma a patru pătrate ( teorema lui Lagrange a sumei celor patru pătrate ) sau a oricărui număr par mai mare de trei prin suma a două numere prime ( problema lui Goldbach ). Dacă notăm prin mulțimea tuturor pătratelor numerelor nenegative, atunci în termeni de combinatorie aditivă (vezi secțiunea de notație de mai jos), teorema lui Lagrange poate fi scrisă ca

În cursul rezolvării problemelor asemănătoare au apărut și altele asemănătoare, cu seturi diferite, dar formulări asemănătoare. Toate acestea au format domeniul matematicii numit teoria numerelor aditive .

Cu toate acestea, combinatoria aditivă nu trebuie luată ca o generalizare sau o dezvoltare a teoriei numerelor aditive  - deși problemele acesteia din urmă pot fi scrise convenabil în termeni de combinatorie aditivă, metodele sale generale, de regulă, nu sunt aplicabile acestora. Teoria numerelor are în vedere întotdeauna mulțimi de un fel special - numere prime, pătrate, alte puteri, numere cu un număr mic de divizori etc. Combinatoria aditivă încearcă să înțeleagă structura adunării ca atare, pentru a obține rezultate cât mai generale posibil.

Cu toate acestea, primele rezultate care pot fi clasificate ca aditiv-combinatoriu în spirit s-au născut la începutul secolului al XX-lea tocmai ca parte a teoriei numerelor (numită și teoria combinatorie a numerelor). [1] Aceasta este, de exemplu, metoda Shnirelman pentru rezolvarea problemei Goldbach (care a fost aplicată și de Linnik pentru problema Waring ) - se bazează pe teorema Shnirelman asupra mulțimii sumelor numerelor din două mulțimi arbitrare, de despre care se cunoaște doar densitatea lor [2] (urmează de notat că definiția foarte specifică a densității conform lui Shnirelman, care a fost folosită în această teoremă, nu a prins rădăcini în combinatoria aditivă ca obiect de studiu).

Teoria Ramsey

Teoria lui Ramsey, care a apărut în prima jumătate a secolului al XX-lea , a analizat și diverse idei despre structurare. Afirmațiile teoriei Ramsey se referă la prezența a cel puțin unei mici „insule” de structură în obiecte destul de complexe (în ceea ce privește numărul de părți elementare). [3]

Totuși, teoria Ramsey nu ia în considerare submulțimi, ci partiții ale unei mulțimi date (de exemplu, un set de muchii ale unui grafic, numere naturale sau o parte a unui boolean al unei mulțimi finite), iar rezultatul structurii înseamnă că unul dintre elementele partiției are structură și, de regulă, nu este clar ce. Prin urmare, nu se poate spune nimic despre un anumit subset.

Un bun exemplu este teorema van der Waerden  - spune că pentru orice împărțire a numerelor naturale într-un număr finit de clase, cel puțin una dintre clase va avea o progresie aritmetică (de orice lungime dată). În același timp, este evident că în orice partiție există o clasă în care densitatea numerelor este mai mare decât în ​​altele și se pare intuitiv că progresia ar trebui să fie în acest set - la urma urmei, există cele mai multe elemente aici. , adică cele mai multe posibilități. De asemenea, este evident că cel mai mare set va avea o densitate pozitivă (diferită de zero). Totuși, a demonstra că absolut orice set infinit de numere naturale de densitate pozitivă conține o progresie aritmetică nu se obține pur și simplu prin teorema van der Waerden - conform acesteia, progresia poate fi în orice clasă, chiar și în cea mai mică. Pentru a demonstra prezența unei progresii în orice mulțime densă, trebuie să implicați mijloace mult mai complexe - soluția acestei probleme se numește teorema lui Szemeredi , care este considerată doar un rezultat clasic aditiv-combinator.

Sume trigonometrice

Un instrument flexibil pentru evaluarea ordonării unei mulțimi, care a jucat și un rol semnificativ în teoria numerelor aditive, sunt sumele trigonometrice (sumele rădăcinilor unității corespunzătoare numerelor mulțimii). Ele au devenit un instrument și obiect de studiu și în combinatoria aditivă, deoarece permit o aplicare destul de generală.

Chiar și Gauss, care a fost primul care a studiat sumele trigonometrice, a descoperit prin ele legătura dintre distribuția tuturor diferențelor posibile de numere dintr-o mulțime dată și mulțimea în sine. Investigand reziduurile pătratice , Gauss a luat în considerare suma

și scoateți o estimare pentru pătratul modulului său:

O estimare pentru această sumă a fost obținută pur combinatoriu din proprietățile expresiei sub schimbarea variabilei . [4] Astfel, multisetul de diferențe a furnizat informații despre structura setului de reziduuri pătratice în sine. În combinatoria aditivă, o abordare similară în concept operează, atunci când este deja o mulțime, și nu un multiset de diferențe (sau sume, produse etc.) de elemente dintr-o mulțime dată, oferă informații despre structura acestei mulțimi. O astfel de tranziție - de la un multiset la o mulțime - este asociată cu trecerea de la numărul de soluții ale unei anumite ecuații (de exemplu, ) la reprezentarea numerelor într-o formă sau alta (de exemplu, în forma ), care este în principiu caracteristică metodei sumelor trigonometrice.

Teorema lui Freiman

O bază separată pentru dezvoltarea unei noi științe a sumelor elementare de mulțimi (mulțimi de sume ) a fost teorema demonstrată de Grigory Freiman asupra structurii mulțimilor cu dublare mică (adică mulțimi a căror mulțime de sume a două elemente are o dimensiune mică sau, mai simplu, ale căror sume de elemente coincid adesea) . [5]

Întrebările despre sumele elementelor dintr-o mulțime dată au fost, de asemenea, luate în considerare de către Erdős și Szemeredi fără a introduce o simbolistică specială pentru a denota însumarea mulțimilor. [6]

Subiect

O mulțime de sume

Un concept important în combinatoria aditivă este setul de sume

pentru mulțimi finite , unde  este un grup. Mărimea unui astfel de set este determinată de structură și în funcție de operațiune . Dacă și  sunt progresii aritmetice, atunci nu este suficient. Și dacă, de exemplu, sunt alese aleatoriu conform schemei Bernoulli , atunci este foarte mare. Cazurile intermediare dintre aceste două cazuri sunt tocmai de interes aditiv-combinatoriu.

În plus, structura seturilor este interesantă în sine . În special, din 2018, nu există criterii generale (altele decât enumerarea directă) pentru a determina dacă un anumit set este reprezentat sub forma .

Caracteristici asociate multimilor

Tabelul de mai jos enumeră teoremele și inegalitățile combinatoriei aditive care relaționează diferite caracteristici ale submulților de grupuri. Declarația specificată într-o celulă raportează caracteristicile specificate în rândul și coloana acesteia. Sunt date doar unele dintre cele mai faimoase dintre aceste teoreme.

Pentru concizie, următoarele abrevieri sunt folosite în titluri:

Există, de asemenea, câteva notații specifice utilizate în celule:

  Densitate OAP Coeficienții Fourier CRU
Densitate              
OAP teorema lui Szemeredi            
Inegalitatea lui Shnirelman , teorema Furstenberg-Sharkozy teorema lui Freiman          
  în general și conțin lung a. n. [7] [8]
Inegalitatea Plünnecke-Rouge        
Coeficienții Fourier Principiul incertitudinii [9] Dacă , este mic, atunci conține a. n. lungime 3 [10] Dacă mic, atunci mare        
CRU teorema lui Roth Dacă - a. p., atunci [unsprezece] Din rapoartele energiilor aditive, putem trage concluzii despre structura mulțimii [12] Dacă , atunci    

Unele concepte folosite

Norma Gowers  este o generalizare a conceptului de coeficienți Fourier, inventat deWilliam Gowersîn cursul demonstrării teoremei lui Szémeredy.

Un izomorfism Freiman  este o mapare de la o submulțime a unui grup la o submulțime a altuia care păstrează relația de egalitate a sumelor unui număr dat de elemente ale mulțimii.

O mulțime finită de numere reale se numește șir convex (sau mulțime convexă) dacă pentru , adică dacă este imaginea unui segment pentru o funcție strict convexă . [13] Proprietățile unor astfel de seturi sunt studiate pe scară largă în combinatoria aditivă. [14] [15] [16] [17] Această noțiune nu trebuie confundată cu o mulțime convexă în sensul obișnuit .

Mulțimea Bohr  este o structură mică de dublare, uneori folosită în dovezi ca un analog slăbit al noțiunii de subspațiu. [18] . Este definit ca ansamblul elementelor de câmp pe care toate caracterele aditive dintr-o familie dată au o valoare mică. Mulțimile Bohr conțin progresii aritmetice generalizate mari, astfel încât prezența progresiilor într-o mulțime este uneori dovedită prin prezența mulțimii Bohr necesare în ea.

O funcție aproape periodică  este o funcțieastfel încât normaeste suficient de mică pentru uniiși pentru toți, unde este o mulțime oarecare (de exemplu, mulțimea Bohr). Una dintre dovezileteoremei lui Roth. [19]

Mulțimea sumelor trigonometrice mari (uneori numită și spectru ) ale mulțimii este mulțimea de reziduuripentru care suma(coeficientul Fourier) are un modul mare . [douăzeci]

O mulțime disociativă este o mulțime pentru care combinațiile liniare sunt egale cu zero, unde, numai când toatesunt egale cu zero. În special, aceasta înseamnă că sumele elementelor din două submulțimi diferite sunt întotdeauna diferite [20] . Disociativitatea poate fi privită ca un analog al independenței liniare peste.

Metode de studiu

Metode elementare

Desigur, în ciuda existenței unor metode puternice și complexe de studiere a teoremelor combinatoriei aditive, unele tehnici și sarcini se pretează la o descriere elementară. Din inegalitatea lui Cauchy, sunt derivate proprietăți ale energiei aditive care se aplică aproape universal. În general, abordarea elementară analizează adesea numărul de soluții ale anumitor ecuații. Argumentul mediu este, de asemenea, folosit adesea  - de exemplu, atunci când se descompune numărul de soluții la o ecuație prin suma numărului de soluții pentru o anumită valoare a unei singure variabile. [21]

Prin metode elementare se poate demonstra teorema Roth [22] și teorema Cauchy-Davenport [23] .

Cu toate acestea, multe dovezi obținute prin alte metode nu au analogi elementari.

Metode combinatorii

Una dintre cele mai emblematice dovezi combinatorii ale combinatoriei aditive este prima demonstrație a teoremei lui Szemeredy [24] care apare  - în ea Szemeredy a formulat și a folosit așa-numita lemă de regularitate , referitoare la teoria grafurilor pure . Analogiile grafice sunt, de asemenea, folosite pentru a demonstra versiuni speciale ale inegalității Plünnecke-Rouge sau estimări ale tipului Balogh-Semeredi-Gowers [25] .

Metode algebrice

Metodele algebrice din combinatoria aditivă folosesc proprietățile polinoamelor, care sunt construite pe baza anumitor mulțimi. Gradele unor astfel de polinoame, de regulă, depind de dimensiunile mulțimilor studiate, iar mulțimea rădăcinilor polinoamelor poate oferi una sau alta informații despre sumele, intersecțiile etc. ale mulțimilor originale.

Un exemplu de instrument pentru aplicarea unei astfel de metode este teorema nulă combinatorie . Cu aceasta, teorema Cauchy-Davenport și unele dintre generalizările sale pot fi demonstrate . [23]

Alte aplicații ale metodei algebrice pot fi găsite în dovezile teoremei lui Roth pentru anumite grupuri de formă specială [26] [27] [28] sau în estimarea mărimii intersecțiilor deplasărilor subgrupurilor multiplicative de câmpuri și demonstrarea problemei lui Waring pentru un câmp prim (pentru aceasta, în special, se folosește metoda lui Stepanov ). ). [29]

Metode analitice

Principalul instrument analitic în combinatoria aditivă sunt coeficienții Fourier . Acest lucru se datorează legăturii strânse dintre operația de luare a coeficientului Fourier și operația de convoluție a funcțiilor . Coeficienții Fourier au fost folosiți încă de la prima demonstrație a teoremei lui Roth. [30] Generalizarea lor este norma Gowers, a cărei știință este numită și analiză Fourier de ordin superior. [douăzeci]

Folosind exemplul coeficienților Fourier (în special, aplicarea lor la demonstrarea teoremei lui Roth), așa-numitul argument iterativ este cel mai bine ilustrat, atunci când luarea în considerare a unei mulțimi arbitrare este împărțită în două cazuri - când mulțimea nu are mari dimensiuni. (față de mărimea mulțimii) Coeficienții Fourier și când o face. În primul caz, se pot folosi direct proprietățile coeficienților Fourier, iar în al doilea, se poate găsi o substructură a unei mulțimi cu o densitate mai mare într-o progresie aritmetică infinită și cu o densitate atât de mare încât numărul de astfel de pașii posibili până la atingerea densității limită vor fi limitate de o valoare care depinde de densitatea totală a setului inițial. Aceasta dezvăluie ideea împărțirii în cazul unui set pseudo-aleatoriu și al unui set cu o anumită structură globală. Această idee se reflectă și în alte metode. [1] [10]

O altă abordare analitică este studierea aproape periodicității funcțiilor asociate cu funcțiile caracteristice mulțimilor studiate. [31]

Metode ergodice

Abordarea ergodică implică aplicarea rezultatelor din teoria sistemelor dinamice la problemele combinatorii aditive . Această abordare a fost aplicată pentru prima dată de Hillel Furstenberg teoremei lui Szemeredy [32] , dar în curând s-a dovedit că poate fi generalizată la o gamă mult mai largă de probleme.

Teoria sistemelor dinamice face adesea posibilă demonstrarea unor rezultate care nu pot fi reformulate prin alte metode, dar nu este capabilă să ofere estimări cantitative (de exemplu, estimări pentru densitatea unei mulțimi în teorema lui Szemeredy). [33]

Alte metode

Alte domenii au aplicații la știința în cauză:

Unii cercetători

Vezi și

Literatură

Note

  1. 1 2 3 Postnauka, I. D. Shkredov, „Combinatorică aditivă” . Preluat la 11 iunie 2018. Arhivat din original la 18 august 2021.
  2. Gelfand, 1962 , p. 9-43.
  3. Graham, 1984 .
  4. Vinogradov, 1971 , p. 5-6.
  5. Freiman, 1966 .
  6. Erdős, Paul & Szemerédi, Endre (1983), Despre sume și produse de numere întregi , Studii de matematică pură. În memoria lui Paul Turán , Basel: Birkhäuser Verlag, p. 213–218, ISBN 978-3-7643-1288-6 , doi : 10.1007/978-3-0348-5438-2_19 Arhivat 24 mai 2013 la Wayback Machine . 
  7. ^ Ernie Croot, Izabella Laba, Olof Sisask , „Arithmetic Progressions in Sumsets and L^p-Almost-Periodicity” . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  8. Tom Sanders, „Structuri aditive în sumsets” . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  9. Terence Tao, „Un principiu de incertitudine pentru grupurile ciclice de ordin prim” . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  10. 1 2 http://www.mathnet.ru/php/seminars.phtml?presentid=3055 Reuniunile Societății de Matematică din Moscova, 1 martie 2011, I. D. Shkredov, Metode de combinatorie aditivă
  11. Garaev, 2010 , p. 25.
  12. Seminarul pentru toate institutele „Matematica și aplicațiile sale” al Institutului de Matematică. V. A. Steklova RAS, 18.09.14, I. D. Shkredov, „Teoreme structurale în combinatorică aditivă”
  13. 1 2 A. Iosevich, S. Konyagin, M. Rudnev și V. Ten, „On combinatorial complexity of convex sequences”, 19 iulie 2004 . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  14. MZ Garaev, „On Lower Bounds for the L1-Norm of Exponential Sums”, Note matematice, noiembrie 2000, volumul 68, numărul 5-6, pp. 713-720 . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  15. Imre Z. Ruzsa, Dmitrii Zhelezov, „Convex sequences may have thin additive bases”, preprint . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  16. 1 2 Tomasz Schoen, Ilya Shkredov, „On Sumsets of Convex Sets” . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  17. 1 2 Elekes, Nathanson, Ruzsa, „Convexity and sumsets” (link indisponibil) . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018. 
  18. Ben Green, „Modele de câmp finit în combinatorică aditivă” . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  19. Tom Sanders, „Despre teorema lui Roth asupra progresiilor”, preprint . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  20. 1 2 3 Shkredov, 2010 .
  21. Garaev, 2010 .
  22. Graham, 1984 , p. douăzeci.
  23. 1 2 Laboratorul de matematică P. L. Cebyshev, Curs de curs „Combinatorică aditivă”, Cursul 1
  24. Szemerédi, Endre (1975), On sets of integers containing no k elements in arithmetic progression , Acta Arithmetica T. 27: 199–245, Zbl 0303.10056, MR : 0369312 , < http://matwbn.icm.edbn.pl . ksiazki/aa/aa27/aa27132.pdf > Arhivat 10 decembrie 2020 la Wayback Machine . 
  25. Garaev, 2010 , p. 18-25.
  26. E. Croot, V. Lev și P.P. Pach, Seturile fără progresie sunt exponențial mici (2016). arXiv preprint 1605.01506. . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  27. Demonstrarea teoremei lui Roth pentru grupuri cu torsiune mică la arxiv.org . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  28. Enunțarea demonstrației teoremei lui Roth pentru în rusă
  29. I. V. Vyugin, I. D. Shkredov, „Despre deplasările aditive ale subgrupurilor multiplicative”, Mat. Sb., 2012, volumul 203, numărul 6, filele 81-100 . Preluat la 11 iunie 2018. Arhivat din original la 12 iunie 2018.
  30. Shkredov, 2006 , p. 119-124.
  31. I. D. Shkredova, prelegere de recenzie „Metode analitice în combinatorică aditivă”, Sala de curs a Laboratorului de Matematică. Cebişev
  32. Yufei Zhao, „Teorema lui Szemer'edi prin Teoria Ergodică” . Preluat la 11 iunie 2018. Arhivat din original la 27 februarie 2021.
  33. Post-știință, I. D. Shkredov, „Teoria ergodică combinatorie”
  34. Imre Ruzsa, „Combinatoria aditivă și geometria numerelor” . Preluat la 11 iunie 2018. Arhivat din original la 11 august 2017.
  35. JA Dias da Silva, YO Hamidoune, Spații ciclice pentru derivați Grassmann și teoria aditivilor, Bull. London Math. soc. 26 (1994) 140-146
  36. I. D. Shkredov, „Unele rezultate noi asupra energiilor superioare” . Preluat la 3 ianuarie 2019. Arhivat din original la 3 ianuarie 2019.