Vita:Erdős–Ginzburg–Ziv-tétel

Ez a szócikk témája miatt a matematikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe! Vázlatos Ez a szócikk vázlatos besorolást kapott a kidolgozottsági skálán. Kevéssé fontos Ez a szócikk kevéssé fontos besorolást kapott a műhely fontossági skáláján. Értékelő szerkesztő: Gubb (vita), értékelés dátuma: 2010. január 31.

kiképlet

x,y∈R; ${\underline {x,y}}:=\left\{z\in \mathbb {Z} |x\leq z\leq y\right\}$

---

$=$ $\sum _{\begin{matrix}{\mbox{ }}_{k_{1},k_{2},...,k_{|B|}\in \mathbb {N} ^{+}}\\{\mbox{ }}_{\sum _{u=1}^{|B|}k_{u}=p-1}\end{matrix}}\left(\sum _{\begin{matrix}{\mbox{ }}_{B=\left\{b_{1},b_{2},...,b_{|B|}\right\}\subseteq A}\\{\mbox{ }}_{|B|\leq p}\end{matrix}}C_{k_{1},k_{2},...,k_{|B|}}\prod _{j=1}^{|B|}b_{j}^{k_{j}}\right)$ $=$
$=$ $\sum _{\begin{matrix}{\mbox{ }}_{k_{1},k_{2},...,k_{|B|}\in \mathbb {N} ^{+}}\\{\mbox{ }}_{\sum _{u=1}^{|B|}k_{u}=p-1}\end{matrix}}\left(\sum _{\begin{matrix}{\mbox{ }}_{B=\left\{b_{1},b_{2},...,b_{|B|}\right\}\subseteq A}\\{\mbox{ }}_{|B|\leq p}\end{matrix}}C_{k_{1},k_{2},...,k_{|B|}}\prod _{j=1}^{|B|}b_{j}^{k_{j}}\right)$ $=$

CDE

Cauchy–Davenport-lemma:

This was first proved by Cauchy (cf. [9]) in 1813 and was rediscovered by Davenport (cf. [10]) in 1947.

• [9] A. L. Cauchy, Recherches sur les nombers, J. Ecole Polytechniques, 9 (1813), 99-123.
• [10] H. Davenport, On the addition of residue classes, J. London Math. Soc., 10 (1935) 30-32.
• R. Thangadurai: Az EGZT nem-kanonikus általánosításai;

---

• CAUCHY–DAVENPORT THEOREM IN GROUP EXTENSIONS Károlyi Gyula cikke

Nullösszeg-problémák

• Sequences not containing long zero-sum subsequences; Weidong Gao, J. J. Zhuang.

Let G be a finite abelian group (written additively), and let D(G) denote the Davenport's constant of G, i.e. the smallest integer d such that every sequence of d elements (repetition allowed) in G contains a nonempty zero-sum subsequence. Let S be a sequence of elements in G with |S| ¸ D(G). We say S is a normal sequence if S contains no zero- sum subsequence of length larger than |S|-D(G)+1. In this paper we obtain some results on the structure of normal sequences for arbitrary G. If G = C_n⊕C_n and n satis¯es some well-investigated property, we determine all normal sequences. With applying these results, we obtain correspondingly some results on the structure of the sequence S in G of length |S| = |G| + D(G)-2 and S contains no zero-sum subsequence of length |G|.

Érdekes linkek

• Zero-sum sets of prescribed size
• A%20Combinatorial%20Problem%20on%20Finite%20Abelian%20Groups
• ON ZERO-SUM SEQUENCES IN Z=nZ © Z=nZ az extremális f(n,k) függvény
• ON ZERO-SUM SUBSEQUENCES IN FINITE ABELIAN GROUPS Schmidt
• Upper bounds 4 Davenport const
• Hegyvári Norbert Dolgozatai de 53 dollár ha jól nézem?

---

• ?ide jön? [1]

---

• Grin's Unichart

---

• Probs and ress in CNT

---

• BioGenomatematik

---

• hírös Kombinatorikus sze problémák
• LIST OF PUBLICATIONS ON ZERO-SUM PROBLEMS

Feldolgozott linkek

A cikkbe nem tett linkek

• On the structure of p-zero-sum free sequences and its application to a variant of Erd os–Ginzburg–Ziv theorem (Weidong Gao, A. Panigrahi, R. Thangadurai)
• Weidong Gao: A Combinatorial Problem on Finite Abelian Groups
  • mindkettő nagyjából ugyanaz: definiál egy speciális f(n,k) extremális függvényt, de ez nemcsak itt nem fontos (la.is én nem fogok írni róla), de talán a nullösszeg-problémák szócikkben sem túlzottan. A p-csoportok és direktösszegek nullösszegei témakörbe tartozik. A Gao-cikk címe egyezik egy fontos, de a neten úgy láccik nem lévő Olson-dolgozatéval,ez kavart meg.

A cikkbe tett linkek

• Gao’s conjecture on zero-sum sequences Nagyon részletes leírása a Davenport-kontans kétféle értelmezésének, tárgyalja a Ch-W-tételt; a Kemnitz-Gao-féle direktösszeg-körbe látszik tartozni, de sajnos kevéssé szól a nullösszeg-kontansról.
• A UNIFIED THEORY OF ZERO-SUM PROBLEMS, SUBSET SUMS AND COVERS OF Z ami fontos dolgot tartalmazott, azt feldolgoztam

Nullösszeg-probléma cikkbe

• A lefedőrendszerek és a nullösszeg-problémák kapcsolatáról
  • Zhi-Wei Sun: Covering systems and their connection to zero-sums
  • Zhi-Wei Sun: Unification of zero-sum problems, subset sums and covers of ℤ
  • Zhi-Wei Sun: A unified tbeory of zero-sum problems, subset sums and covers of Z

Másképp szólva

Szerintem a másképp szólva rész az elején nem kellene. Aki nem tudja, hogy mit jelent az, hogy 2m-1 szám esetén biztosan van m ..., az úgyse fog ilyesmit olvasgatni. Ennyire szerintem nem kell lemenni kutyába. Péter ✎ 2006. február 7., 10:06 (CET)

Példa

Vegyük a p=3-at. Ekkor 2p-1 = 5.

Legyen hát A={a,b,c,d,e}, |A| = 5.

Ekkor S az összes 3-elemű A-beli kombináció 2. hatványának, négyzetének összege:

S= (a+b+c)²+ (a+b+d)²+ (a+b+e)²+ (a+c+d)²+ (a+c+e)²+ (a+d+e)²+ (b+c+d)²+ (b+c+e)²+ (c+d+e)²

Ebben van pl. a². De hányszor?

Annyiszor, ahányszor úgy tudunk 3-elemű kombinációt kiválasztani A-ból, hogy abban szerepeljen a. Ez egyszerű: az a elem rögzített, a kombináció maradék két eleme tetszőlegesen választható, azaz A/{a} két elemű kombinációja, tehát hányszor szerepel az a elem:

(4 2)-szer=4!/(2!)(2!) = (3×4)/2 = 6-szor.

És valóban, 6-szor fordul elő.

Van aztán pl. 2ab, ahol 2 polinomiális együttható. De hányszor van 2ab? Hát annyiszor, ahányszor előfordul a kombinációk közt a is meg b is. Hasonlóan mint előbb, A/{a,b}-ből még egy elemet kell választani. Ez tehát (3 1) = 3-féleképp. tehát 3×2ab. És ez valóban osztható 3-mal. Tehát úgy jön ki, hogy ([2p-1]-2 3-2).

Hasonló módon, általában ([2p-1]-s p-s). Ennek oszthatónak kellene lennie mindig p-vel.

Szégyen, gyalázat, de ki kell fejtenem az egészet.

S= (a+b+c)2+ (a+b+d)2+ (a+b+e)2+ (a+c+d)2+ (a+c+e)2+ (a+d+e)2+ (b+c+d)2+ (b+c+e)2+ (c+d+e)2	$\sum _{\begin{matrix}{\mbox{ }}_{I\subseteq A}\\{\mbox{ }}_{|I|=p}\end{matrix}}\left(\sum _{a\in I}a\right)^{p-1}$
u.a.	$\sum _{\begin{matrix}{\mbox{ }}_{I\subseteq A}\\{\mbox{ }}_{|I|=p}\end{matrix}}\left(\sum _{H_{I}=1_{I}}^{p_{I}}a_{H_{I}}\right)^{p-1}$
(a2+b2+c2+2ab+2ac+2bc)+ (a2+b2+d2+2ab+2ad+2bd)+ ... +(c2+d2+e2+2cd+2ce+2de)	$\sum _{\begin{matrix}{\mbox{ }}_{I\subseteq A}\\{\mbox{ }}_{|I|=p}\end{matrix}}\left(\sum _{\begin{matrix}{\mbox{ }}_{k_{1},k_{2},...,k_{p}\in \mathbb {N} }\\{\mbox{ }}_{\sum _{u=1}^{p}k_{u}=p-1}\end{matrix}}C_{k_{1},k_{2},...,k_{p}}\cdot a_{1_{I}}^{k_{1}}a_{2_{I}}^{k_{2}}...a_{p_{I}}^{k_{p}}\right)$ $=$
mellesleg	$\sum _{\begin{matrix}{\mbox{ }}_{I\subseteq A}\\{\mbox{ }}_{|I|=p}\end{matrix}}\left(\sum _{\begin{matrix}{\mbox{ }}_{\left(a_{1},a_{2},...,a_{p}\right)\in I^{p-1}}\end{matrix}}a_{1_{I}}a_{2_{I}}...a_{p_{I}}\right)$

---

Heuréka! Definiálni kell egy mátrixot, melynek oszlopindexei az A elemek indexei, sorindexei a P_p(A) elemei; és/vagy használni kell a karakterisztikus függvény fogalmát. A szumma alsóindexébe(?) ezután a11=a1-et lehet írni, legalábbis eszerint kell számolni, hogy mT-t kapjuk. Asszem, hétvégéig vagy hétvégén meg tudom csinálni. ♥♥♥: Gubb  ✍    2006. február 21., 15:01 (CET)