Omezený součet sad
V doplňkové teorii čísel a kombinatorika , je omezený součet sad je sada formy
S={na1+⋯+nane | na1∈NA1,...,nane∈NAne a (na1,...,nane)∉B},{\ displaystyle S = \ {a_ {1} + \ cdots + a_ {n} ~ | ~ a_ {1} \ v A_ {1}, \ ldots, a_ {n} \ v A_ {n} {\ textu { and}} (a_ {1}, \ ldots, a_ {n}) \ notin B \},}
kde 1 , ..., n jsou díly z o abelian skupiny G a B je součástí G n .
Uvažovaná skupina G je často aditivní skupinou komutativního kruhu , jako je kruh ℤ celých čísel nebo kruh ℤ / n ℤ .
Pokud je vyloučená množina B prázdná , S je jednoduše obvyklý součet množin A 1 +… + A n (označeno nA, pokud jsou všechny A k stejné stejné množině A ).
Pokud B je množina n -uples ne všech odlišných prvků, pak S je označeno
NA1∔⋯∔NAne,{\ displaystyle A_ {1} \ dotplus \ cdots \ dotplus A_ {n},}
nebo
ne∧NA{\ displaystyle n ^ {\ wedge} A}
když všichni k jsou rovny A .
Cauchy-Davenportova věta
Dokládá Augustin Louis Cauchy a nově objevený Harold Davenport , který se později všimli Cauchyův asnosti, tato věta je zajištěno, že pro každou prvočísla p a všech neprázdných částech A a B z konečného pole ℤ / p ℤ jsme má následující nerovnosti na kardinály :
|NA+B|≥min(p, |NA|+|B|-1).{\ displaystyle | A + B | \ geq \ min (p, ~ | A | + | B | -1).}
Důsledkem bezprostřední je, že pro každý výsledek S z p - 1 nenulových složek, ze ℤ / p ℤ (ne nezbytně odlišné), každý prvek ℤ / p ℤ je suma subsekvencí (případně prázdný ) ze S .
Můžeme také odvodit z ní Erdős-Ginzburg-Ziv věta : pro všechny přirozené číslo n , jakékoliv sekvence 2 n - 1 prvků ℤ / n ℤ obsahuje n nulový součet podmínky.
Erdős-Heilbronn dohad
V roce 1980 Paul Erdős a Ronald Graham zformulovali následující domněnku, kterou je obvyklé jako do roku 1964 přisuzovat Erdősovi a Heilbronnovi :
žádného prvočísla p a jakoukoli část A z pole ℤ / p ℤ,
|2∧NA|≥min(p, 2|NA|-3){\ displaystyle | 2 ^ {\ klín} A | \ geq \ min (p, ~ 2 | A | -3)}.
V roce 1994, Jose Antonio Dias da Silva a Yahya Ould Hamidoune (1948-2011) demonstroval, i což dokazuje, že pro každou konečnou část A tělesa F ,
|ne∧NA|≥min(p(F), ne|NA|-ne2+1){\ displaystyle | n ^ {\ wedge} A | \ geq \ min (p (F), ~ n | A | -n ^ {2} +1)},
kde p ( F ) označuje charakteristiku z F , pokud není nula, a p ( F ) = ∞ jinak.
Různá zevšeobecnění poskytli Noga Alon , Melvyn Nathanson a Imre Z. Ruzsa (en) v roce 1996, Qing-Hu Hou a Zhi Wei Sun v roce 2002 a Gyula Károlyi v roce 2004.
Kombinatorický nullstellensatz
Silným nástrojem pro snižování kardinálů různých omezených součtů množin je polynomiální metoda, kterou v roce 1989 zavedli Alon a Tarsi a poté ji vyvinuli Alon, Nathanson a Ruzsa. Alon (1999) ji přeformulovat s tímto principem, který se považuje za variantu v Hilbertově Nullstellensatz :
Nechť f ( x 1 ,…, x n ) je polynom s koeficienty v poli F a x 1 k 1 … x n k n monomiál s nenulovým koeficientem vf a maximálním stupněm. U všech částí 1 , ..., n o F taková, že pro každé i , | A i | > k i , existuje v jejich produktu n -uplet, ve kterém f nezmizí.
Alon popisuje mnoho aplikací tohoto principu, mezi nimiž jsou důkazy klasických vět jako Cauchy-Davenport uvedené výše nebo Chevalley-Warning .
Poznámky a odkazy
(
fr ) Tento článek je částečně nebo zcela převzat z článku
anglické Wikipedie s názvem
„ Restricted sumset “ ( viz seznam autorů ) .
-
Část B se pak často vybírá z formy {( a 1 ,…, a n ) ∈ G n | f ( a 1 , ..., a n ) = 0} pro určitý polynom f se součiniteli v tomto kruhu: viz například (en) Noga Alon , „ Combinatorial Nullstellensatz “ , Combin. Probab. Comput. , sv. 8, n kost 1-2,1999, str. 7-29 ( číst online ).
-
(en) Melvyn B. Nathanson , Additive teorie čísel: Inverzní problémy a geometrie Sumsets , Springer , et al. " GTM " ( n o 165),1996( číst online ) , s. 13.
-
A. Cauchy , „ Výzkum čísel “, JEP , sv. 9,1813, str. 99-123 ( číst online ).
-
(in) H. Davenport , „ O přidání tříd reziduí “ , J. London Math. Soc. , sv. 10,1935, str. 30-32.
-
(in) H. Davenport , „ Historické poznámky “ , J. London Math. Soc. , sv. 22,1947, str. 100-101.
-
Nathanson 1996 , str. 73.
-
Nathanson 1996 , str. 44.
-
Demonstrace, „v zásadě ukázka (ne) Nogy Alona , Melvyna B. Nathansona a Imre Ruzsy , „ Přidání odlišných tříd kongruence modulo prémie “ , Amer. Matematika. Měsíc. , sv. 102, n o 3,1995, str. 250–255 ( číst online ) », Je představen v (en) « Důkaz Cauchy-Davenportovy věty »na PlanetMath .
-
Trochu obecnější prohlášení viz (in) Eric W. Weisstein , „ Cauchy-Davenportova věta “ na MathWorld .
-
Nathanson 1996 , str. 48.
-
(in) P. Erdős a RL Graham , „ Staré a nové problémy a výsledky v kombinatorické teorii čísel “ , The Enseign. Matematika. ,1980, str. 1-128 ( číst online ), str. 95 .
-
Nathanson 1996 , str. 77.
-
(in) Zhi-Wei Sun, „O některých domněnkách Erdős-Heilbronna, Leva a Snevilyho“ pdf : prezentace.
-
V článku zmíněném Erdősem a Grahamem byla domněnka ve skutečnosti redukcí, podle | A |, počet zřetelných součtů získaných přidáním prvků kterékoli části A : (en) P. Erdös a H. Heilbronn , „ O přidání tříd reziduí modulo p “ , Acta Arith. , sv. 9,1964, str. 149-159 ( číst online ), Domněnka 2.
-
Alain Plagne, „ Yahya Ould Hamidoune, velký Mauritánčan, jedinečný muž, výjimečný matematik “ , na École Polytechnique .
-
Alain Plagne , „ Yahya Ould Hamidoune, mauritánský matematik: 1948–11. Března 2011 “, Combin. Probab. Comput. , sv. 20, n o 5,2011, str. 641-645 ( DOI 10.1017 / S0963548311000332 ).
-
(in) JA Dias da Silva a YO Hamidoune , „ Cyklické prostory pro Grassmanovy deriváty a aditivní teorie “ , Bull. London Math. Soc. , sv. 26, n O 21994, str. 140-146 ( DOI 10.1112 / blms / 26.2.140 ).
-
(en) Noga Alon , Melvyn B. Nathanson a Imre Ruzsa , „ Polynomiální metoda a omezené součty tříd kongruence “ , J. Number Theor. , sv. 56, n O 21996, str. 404-417 ( číst online ).
-
(in) Qing Hu Hu a Zhi-Wei Sun , „ Omezené částky v poli “ , Acta Arith. , sv. 102, n o 3,2002, str. 239-249 ( číst online ).
-
(in) Gyula Károlyi , „ Problém Erdős-Heilbronn v abelianských skupinách “ , Isr. J. Math. , sv. 139,2004, str. 349-359 ( DOI 10.1007 / BF02787556 ).
-
(v) Noga Alon a Michael Tarsi , " Steh v nikde nula lineární zobrazení " , combinatorica , sv. 9, n O 4,1989, str. 393-395 ( číst online ).
Podívejte se také
externí odkazy
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">