Somma limitata di set
Nella teoria dei numeri additiva e in calcolo combinatorio , una somma ristretta di insiemi è un insieme del modulo
S={a1+⋯+anon | a1∈A1,...,anon∈Anon e (a1,...,anon)∉B},{\ displaystyle S = \ {a_ {1} + \ cdots + a_ {n} ~ | ~ a_ {1} \ in A_ {1}, \ ldots, a_ {n} \ in A_ {n} {\ text { e}} (a_ {1}, \ ldots, a_ {n}) \ notin B \},}
dove A 1 ,…, A n sono parti di un gruppo abeliano G e B è una parte di G n .
Il gruppo G considerato è spesso il gruppo additivo di un anello commutativo , come l'anello ℤ degli interi o un anello ℤ / n ℤ .
Se l'insieme B escluso è vuoto , S è semplicemente la solita somma degli insiemi A 1 +… + A n (denotato nA se tutti gli A k sono uguali allo stesso insieme A ).
Se B è l'insieme di n -uple di non tutti gli elementi distinti, allora S è denotato da
A1∔⋯∔Anon,{\ displaystyle A_ {1} \ dotplus \ cdots \ dotplus A_ {n},}
o
non∧A{\ displaystyle n ^ {\ wedge} A}
quando tutto il A k sono uguali a A .
Teorema di Cauchy-Davenport
Dimostra Augustin Louis Cauchy e riscoperto da Harold Davenport che poi notato anteriorità di Cauchy, questo teorema garantisce che per ogni numero primo p e per tutte le parti non vuoti A e B del campo finito ℤ / p ℤ, si ha la seguente disuguaglianza sulle cardinali :
|A+B|≥min(p, |A|+|B|-1).{\ displaystyle | A + B | \ geq \ min (p, ~ | A | + | B | -1).}
Un corollario immediato è che per ogni risultato S di p - 1 non zero elementi di ℤ / p ℤ (non necessariamente distinti), ogni elemento di ℤ / p ℤ è somma di una sottosequenza (eventualmente svuotare ) di S .
Da esso possiamo dedurre anche il teorema di Erdős-Ginzburg-Ziv : per ogni numero naturale n , ogni successione di 2 n - 1 elementi di ℤ / n ℤ contiene n termini a somma zero.
Congettura di Erdős-Heilbronn
Nel 1980, Paul Erdős e Ronald Graham formularono la seguente congettura, che è consuetudine datare come loro al 1964 attribuendola a Erdős e Heilbronn :
per qualsiasi numero primo p e qualsiasi parte A del campo ℤ / p ℤ,
|2∧A|≥min(p, 2|A|-3){\ displaystyle | 2 ^ {\ wedge} A | \ geq \ min (p, ~ 2 | A | -3)}![{\ displaystyle | 2 ^ {\ wedge} A | \ geq \ min (p, ~ 2 | A | -3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9de944f3c965879127dc7c36fce25ae6723da94)
.
Nel 1994, José António Dias da Silva e Yahya Ould Hamidoune (1948-2011) lo hanno dimostrato, dimostrando anche che per ogni parte finita A di un corpo F ,
|non∧A|≥min(p(F), non|A|-non2+1){\ displaystyle | n ^ {\ wedge} A | \ geq \ min (p (F), ~ n | A | -n ^ {2} +1)}![{\ displaystyle | n ^ {\ wedge} A | \ geq \ min (p (F), ~ n | A | -n ^ {2} +1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6201ac1780cea5939e4ad469b42c796cd1ab566e)
,
dove p ( F ) denota la caratteristica di F se non è zero, e p ( F ) = ∞ altrimenti.
Varie generalizzazioni sono state date da Noga Alon , Melvyn Nathanson e Imre Z. Ruzsa (en) nel 1996, Qing-Hu Hou e Zhi Wei Sun nel 2002 e Gyula Károlyi nel 2004.
Combinatorial nullstellensatz
Un potente strumento per abbassare i cardinali di varie somme ristrette di insiemi è un metodo polinomiale, introdotto nel 1989 da Alon e Tarsi e poi sviluppato da Alon, Nathanson e Ruzsa. Alon (1999) lo ha riformulato con il seguente principio, che considera una variante del Nullstellensatz di Hilbert :
Sia f ( x 1 ,…, x n ) un polinomio con coefficienti in un campo F e x 1 k 1 … x n k n un monomio con coefficiente diverso da zero in f e massimo grado. Per tutte le parti A 1 ,…, A n di F tale che per ogni i , | A i | > k i , esiste nel loro prodotto un n -uplet in cui f non svanisce.
Alon descrive molte applicazioni di questo principio, tra cui dimostrazioni di teoremi classici come quella di Cauchy-Davenport presentata sopra o quella di Chevalley-Warning .
Note e riferimenti
(
fr ) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in
inglese intitolato
" Restricted sumset " ( vedere l'elenco degli autori ) .
-
parte B è quindi spesso scelta dalla forma {( a 1 ,…, a n ) ∈ G n | f ( a 1 ,…, a n ) = 0} per un certo polinomio f con coefficienti in questo anello: si veda ad esempio (en) Noga Alon , “ Combinatorial Nullstellensatz ” , Combin. Probab. Comput. , vol. 8, n osso 1-2,1999, p. 7-29 ( leggi in linea ).
-
(en) Melvyn B. Nathanson , Teoria dei numeri additivi: problemi inversi e geometria delle somme , Springer , et al. " GTM " ( n o 165),1996( leggi in linea ) , p. 13.
-
A. Cauchy , " Research on numbers ", JEP , vol. 9,1813, p. 99-123 ( leggi in linea ).
-
(a) H. Davenport , " Sull'aggiunta di classi di residui " , J. London Math. Soc. , vol. 10,1935, p. 30-32.
-
(in) H. Davenport , " A historical notes " , J. London Math. Soc. , vol. 22,1947, p. 100-101.
-
Nathanson 1996 , p. 73.
-
Nathanson 1996 , p. 44.
-
Una dimostrazione, "essenzialmente quella di (in) Noga Alon , Melvyn B. Nathanson e Imre Ruzsa , " Aggiunta di classi di congruenza distinte modulo un premio " , Amer. Matematica. Mese. , vol. 102, n ° 3,1995, p. 250-255 ( leggi in linea ) », È presentato in (en) « Dimostrazione del teorema di Cauchy-Davenport »su PlanetMath .
-
Per un'affermazione leggermente più generale, vedere (in) Eric W. Weisstein , " Teorema di Cauchy-Davenport " su MathWorld .
-
Nathanson 1996 , p. 48.
-
(in) P. Erdős e RL Graham , " Vecchi e nuovi problemi e risultati nella teoria dei numeri combinatori " , The Enseign. Matematica. ,1980, p. 1-128 ( leggi in linea ), p. 95 .
-
Nathanson 1996 , p. 77.
-
(in) Zhi-Wei Sun, "Su alcune congetture di Erdős-Heilbronn, Lev e Snevily" pdf : presentazione presentazione.
-
Nell'articolo citato da Erdős e Graham, la congettura era in realtà una riduzione, secondo | A |, il numero di somme distinte ottenute sommando gli elementi di qualsiasi parte di A : (en) P. Erdös e H. Heilbronn , “ Sull'aggiunta di classi di residui modulo p ” , Acta Arith. , vol. 9,1964, p. 149-159 ( leggi in linea ), Congettura 2.
-
Alain Plagne, " Yahya Ould Hamidoune, grande mauritano, uomo singolare, matematico eccezionale " , su École Polytechnique .
-
Alain Plagne , " Yahya Ould Hamidoune il matematico mauritano: 1948-11 marzo 2011 ", Combin. Probab. Comput. , vol. 20, n o 5,2011, p. 641-645 ( DOI 10.1017 / S0963548311000332 ).
-
(in) JA Dias da Silva e YO Hamidoune , " Spazi ciclici per i derivati di Grassman e la teoria degli additivi " , Bull. London Math. Soc. , vol. 26, n o 21994, p. 140-146 ( DOI 10.1112 / blms / 26.2.140 ).
-
(en) Noga Alon , Melvyn B. Nathanson e Imre Ruzsa , “ Il metodo polinomiale e somme ristrette classi di congruenza ” , J. Theor numero. , vol. 56, n o 21996, p. 404-417 ( leggi in linea ).
-
(in) Qing Hu Hu e Zhi-Wei Sun , " Somme limitate in un campo " , Acta Arith. , vol. 102, n ° 3,2002, p. 239-249 ( leggi in linea ).
-
(in) Gyula Károlyi , " Il problema Erdős-Heilbronn nei gruppi abeliani " , Isr. J. Math. , vol. 139,2004, p. 349-359 ( DOI 10.1007 / BF02787556 ).
-
(in) Noga Alon e Michael Tarsi , " A stitch in nowhere-zero linear mappings " , combinatorica , vol. 9, n o 4,1989, p. 393-395 ( leggi in linea ).
Vedi anche
link esterno
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">