Summen und Einheitswurzel

23.06.2010, 18:48

frieder

Summen und Einheitswurzel

Hallo. Ich arbeite gerade einen Beweis durch und verstehe dabei einen Schritt nicht:

Sei C eine Menge (Teilmenge von $\begin{eqnarray*} \mathbb{F}_q \end{eqnarray*}$ ), deren Elemente Vektoren der Länge n sind. Sei M die Anzahl der der Elemente von C. Definiere die Zuordnung d durch d(x,y)=die Anzahl der Stellen, an denen sich x,y (aus C) unterscheiden. (Beispiel: x=(100101), y=(101111), d(x,y)=2). Sei w die q-te Einheitswurzel. Sei g(x) definiert durch g(x)=Anzahl der Stellen ungleich null. (Beispiel: x=(10111001), g(x)=5). Dann gilt zu einem festen k:

$\begin{eqnarray*} \sum_{i=0}^n \sum_{(x,y) \in C^2 \atop d(x,y)=i} \sum_{z \in \mathbb{F}_q^n \atop g(z)=k} w^{<x-y,z>} = \sum_{z \in \mathbb{F}_q^n \atop g(z)=k} |\sum_{x \in C} w^{<x,x>}|^2 \end{eqnarray*}$

Ich verstehe diesen Schritt "=" einfach nicht..... traurig

Über eine Hilfe wäre ich sehr dankbar,
lg frieder

24.06.2010, 10:48

Reksilat

Auf diesen Beitrag antworten »

RE: Summen und Einheitswurzel
Hi frieder,

Zitat:

Sei w die q-te Einheitswurzel.

Was meinst Du damit? Vielleicht "Sei w eine (primitive?) Einheitswurzel in $\begin{eqnarray*} \mathbb{C} \end{eqnarray*}$ "? In $\begin{eqnarray*} \mathbb{F}_q \end{eqnarray*}$ gibt es dagegen eine eindeutige q-te Einheitswurzel, das wäre dann die 1. Erstaunt2

Außerdem sehe ich auf der rechten Seite keinen Bezug mehr zu $\begin{eqnarray*} z \end{eqnarray*}$ bzw. $\begin{eqnarray*} k \end{eqnarray*}$ .
Beispiel:
Sei $\begin{eqnarray*} n=q=2 \end{eqnarray*}$
$\begin{eqnarray*} C=\mathbb{F}_2\times \mathbb{F}_2 \end{eqnarray*}$
$\begin{eqnarray*} w=-1 \end{eqnarray*}$ eine 2-te Einheitswurzel in $\begin{eqnarray*} \mathbb{C} \end{eqnarray*}$

Dann ist $\begin{eqnarray*} \sum_{x\in C} w^{\langle x,x\rangle}=(-1)^0+(-1)^1+(-1)^1+(-1)^0=0 \end{eqnarray*}$
Auf der rechten Seite steht also immer eine Null.
Setzen wir aber k=0, so ist z=0 und somit auch $\begin{eqnarray*} \langle x-y,z\rangle=0 \end{eqnarray*}$ . Dann stehen auf der linken Seite nur Einsen als Summanden, die Summe ist also positiv.
verwirrt

Irgendwas fehlt mir hier. Die Glaskugel ist leider beim WM-Tippspiel im Einsatz.

Gruß,
Reksilat.

26.06.2010, 13:20

frieder

Auf diesen Beitrag antworten »

Oje, ich hab mich auch vertippt: Es ist

$\begin{eqnarray*} & = \sum_{i=0}^n \sum_{(x,y)\in C^2\atop d(x,y)=i} \sum_{z\in \mathbb{F}_q^n\atop g(z)=k} w^{\langle x-y,z \rangle}<br /> & = \sum_{(x,y)\in C^2} \sum_{z\in \mathbb{F}_q^n\atop g(z)=k} w^{\langle x-y,z \rangle}<br /> & = \sum_{z\in \mathbb{F}_q^n\atop g(z)=k} \left| \sum_{x\in C} w^{\langle x,z \rangle}\right|^2 \end{eqnarray*}$

und natürlich ist w eine primitive q-te Einheitswurzel in $\begin{eqnarray*} \mathbb{C} \end{eqnarray*}$ .

Zitat:

In $\begin{eqnarray*} \mathbb{F}_q \end{eqnarray*}$ gibt es dagegen eine eindeutige q-te Einheitswurzel, das wäre dann die 1

Gilt das auch allgemein in dem Ring $\begin{eqnarray*} \mathbb{Z}/q\mathbb{Z} \end{eqnarray*}$ , wenn q nicht prim ist?

Und das letzte "=" krieg ich immer noch nicht hin. traurig

ls frieder

26.06.2010, 18:46

Reksilat

Auf diesen Beitrag antworten »

Damit ist das auch einfacher. smile

Die Summation über $\begin{eqnarray*} z \end{eqnarray*}$ wird für den Schritt nicht benötigt, es ist also noch dies zu zeigen:

$\begin{eqnarray*} \sum_{(x,y)\in C^2} w^{\langle x-y,z \rangle}= \left| \sum_{x\in C} w^{\langle x,z \rangle}\right|^2 \end{eqnarray*}$

Auf der rechten Seite steht ein Betrag. Da wir in den komplexen Zahlen sind, lösen wir den mit Hilfe der Beziehung $\begin{eqnarray*} |a|^2=a\overline{a} \end{eqnarray*}$ für $\begin{eqnarray*} a\in \mathbb{Z} \end{eqnarray*}$ auf.

Die linke Seite kann man erst mal schreiben als $\begin{eqnarray*} \sum_{x\in C}\sum_{y\in C}w^{\langle x-y,z\rangle} \end{eqnarray*}$ . Das Skalarprodukt im Exponenten kann man auch noch auseinanderziehen.

Schau mal, wie weit Du damit kommst.

Zitat:

Gilt das auch allgemein in dem Ring Z/qZ, wenn q nicht prim ist?

Nein, dann kann man auch andere Einheitswurzeln finden.
Beispiel: $\begin{eqnarray*} q=6 \end{eqnarray*}$ , $\begin{eqnarray*} x=5 \end{eqnarray*}$

Gruß,
Reksilat.

27.06.2010, 23:48

frieder

Auf diesen Beitrag antworten »

Hui danke. das sieht nach was aus, also

$\begin{eqnarray*} \sum_{x\in C}\sum_{y\in C} w^{\langle x-y,z\rangle}=\sum_{x\in C}\sum_{y\in C} w^{\langle x,z\rangle -\langle y,z\rangle}=\sum_{x\in C}\sum_{y\in C} w^{\langle x,z\rangle} w^{ -\langle y,z\rangle}=\left( \sum_{x\in C} w^{\langle x,z\rangle}\right) \left(\sum_{y\in C} w^{ -\langle y,z\rangle}\right) \end{eqnarray*}$

Aber das ist wohl nur dann gut, wenn noch $\begin{eqnarray*} \overline{\left( \sum_{x\in C} w^{\langle x,z\rangle}\right)}=\left(\sum_{y\in C} w^{ -\langle y,z\rangle}\right) \end{eqnarray*}$ gilt, dann wäre ja alles gut, denn dann gilt $\begin{eqnarray*} a\overline{a}=\vert a\vert^2 \end{eqnarray*}$ also $\begin{eqnarray*} \sum_{x\in C}\sum_{y\in C} w^{\langle x-y,z\rangle} = \left| \sum_{x\in C} w^{\langle x,z\rangle}\right|^2 \end{eqnarray*}$ .

Aber wieso sollte $\begin{eqnarray*} \overline{\left( \sum_{x\in C} w^{\langle x,z\rangle}\right)}=\left(\sum_{y\in C} w^{ -\langle y,z\rangle}\right) \end{eqnarray*}$ stimmen. Wie konjugiert man denn Einheitsswurzeln?

EDIT: Ja super, hab nen Beweis für letztere Aussage gefunden. Das ist ja bestens. Ich danke Dir, vielmals.

lg,

Frieder

28.06.2010, 12:44

Reksilat

Auf diesen Beitrag antworten »

Prima!

Neue Frage »

Antworten »

Summen und Einheitswurzel

Verwandte Themen