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

A Wikipédiából, a szabad lexikonból.

Tartalomjegyzék

[szerkesztés] kiképlet

x,y∈R; \underline{x,y} := \left\{ z \in \mathbb{Z} | x \le z \le 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| \le 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| \le p } \end{matrix} }  C_{ k_{1}, k_{2}, ... , k_{|B|} } \prod_{j=1}^{|B|} b_{j}^{k_{j}}  \right) =

[szerkesztés] 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;

[szerkesztés] Nullösszeg-problémák

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 = Cn⊕Cn 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|.

[szerkesztés] Érdekes linkek


  •  ?ide jön? [1]




== Feldolgozott linkek ==ú

[szerkesztés] A cikkbe nem tett linkek

[szerkesztés] A cikkbe tett linkek

[szerkesztés] Nullösszeg-probléma cikkbe

[szerkesztés] 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)

[szerkesztés] 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)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

Ebben van pl. a2. 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 Pp(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)