| |
| Autor |
  Gleichung für die Anzahl von Polynomen eines gewissen Grades zeigen. |
|
julian2000P
Aktiv 
Dabei seit: 25.10.2020
Mitteilungen: 225
 |  Themenstart: 2023-03-23
|
Hallo zusammen,
ich habe gerade folgendes Problem:
Wir betrachten einen endlichen Polynomring $R = GF(p)[x]$ mit Koeffizienten aus dem endlichen Körper $GF(p)$, wobei $p$ eine Primzahl ist. Wir können verwenden, dass jedes normierte Polynom eine eindeutige Darstellung als Produkt von irreduziblen Polynomen besitzt. Bezeichne mit $a_n$ die Anzahl der Polynome vom Grad $n$ in $R$.
Nun sollte ich folgende Gleichung zeigen (hierbei werden formale Potenzreihen betrachtet):
$$
\prod_{k \geq 1}(1 + z^k + z^{2k} + ...)^{a_k} = \sum_{n \geq 0} p^n z^n
$$
Dabei habe ich so argumentiert, dass ich jedes Polynom von einem gewissen Grad mit einer Multimenge (Wiederholungen erlaubt, Reihenfolge egal) von irreduziblen Polynomen identifizieren kann. Die Gleichung ergibt sich dann aus einer allgemeinen Darstellung für die erzeugende Funktion einer Multimenge.
Nun soll ich zeigen, dass für alle $n \in \mathbb{N}$ gilt
$$
p^n = \sum_{d|n, d> 0} d \; a_d,
$$
wobei die Summe über alle Teiler $d > 0$ von $n$ läuft.
Wenn ich die Koeffizienten von $z^n$ des Produktes auf der linken Seite ablesen könnte, sollte ich auf die gewünschte Gleichung kommen. Leider habe ich hierbei keine richtigen Ansatz wie ich die Koeffizienten gezielt "herauslesen" kann.
Hat jemand einen Denkanstoß oder Ansatz für mich, wie ich die Koeffizienten des Produktes erhalte oder ich die Darstellung für $p^n$ auf einem anderen Weg zeigen kann?
Danke!
|
 Profil
|
Nuramon
Senior 
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.1, eingetragen 2023-03-23
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Hallo,
ich sehe im Moment nicht, wie man die zweite Gleichung aus der ersten ablesen könnte.
Unabhängig von der ersten Gleichung kann man aber mit Körpertheorie argumentieren:
$GF(p^n)$ ist eine normale algebraische Erweiterung von $GF(p)$. Was kann man über die Grade der Minimalpolynome der Elemente von $GF(p^n)$ aussagen?\(\endgroup\)
|
Profil
|
julian2000P
Aktiv
Dabei seit: 25.10.2020
Mitteilungen: 225
| Beitrag No.2, vom Themenstarter, eingetragen 2023-03-23
|
Hallo Nuramon,
ich danke dir für deine Antwort! Leider habe ich keine Erfahrung mit abstrakter Algebra und dahingehend auch noch nie Kurse besucht. Dementsprechend weiß ich leider auch nicht was eine algebraische Erweiterung von $GF(p)$ ist. (Ich kann natürlich in Wikipedia nachsehen, müsste mich aber gründlich einlesen, bevor ich das ganze wirklich verstehe...)
Würdest du sagen, dass es auch mit elementaren Mitteln möglich ist, den von dir vorgeschlagenen Lösungsweg zu verstehen?
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.3, eingetragen 2023-03-24
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Ok, gleiche Idee ein bisschen anders:
Sei $q:= p^n$. Was sind die Nullstellen von $x^q-x$ in $GF(q)$? Welche irreduziblen Faktoren hat das Polynom in $R$?
\(\endgroup\)
|
Profil
|
julian2000P
Aktiv
Dabei seit: 25.10.2020
Mitteilungen: 225
| Beitrag No.4, vom Themenstarter, eingetragen 2023-03-25
|
Tut mir leid für die späte Rückmeldung.
Die Nullstellen von $x^q - x$ in $GF(q)$ sind zunächst sicher einmal $0$ und $x^{q-1} - 1 = 0$ hat laut Wikipedia (das habe ich leider noch nicht ganz verstanden) anscheinend die Nullstellen $1,\dots,q-1$ in $GF(q)$, also jede Zahl ungleich 0.
Nun kann ich das Polynom ja faktorisieren
$$
x^q - x = x\cdot(x-1)\cdot \dots \cdot (x-(p-1)) \cdot \dots \cdot (x-(q-1))
$$
Da die Zahlen $p,\dots,q-1$ ja nicht in $GF(p)$ sind, sind die irreduziblen Faktoren in $R$ dann wohl $x,(x-1), \dots, (x-(p-1))$.
Stimmt das soweit?
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3705
| Beitrag No.5, eingetragen 2023-03-25
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Es ist richtig, dass jedes Element von $GF(q)$ eine Nullstelle von $x^q-x$ ist.
Es ist nicht richtig, dass die Elemente von $GF(q)$ gleich $0,1,2,\ldots, q-1$ sind.
Zur Faktorisierung:
Es gibt auch noch nichtlineare irreduzible Faktoren.
Ich gebe zu, es ist nicht leicht zu sehen, daher hier die Aussage, auf die ich hinauswill:
$x^q-x$ ist das Produkt aller irreduziblen Polynome in $R$, deren Grad ein Teiler von $n$ ist.
Hier ist ein Beweis, der nur wenig Vorwissen voraussetzt.\(\endgroup\)
|
Profil
|
Kuestenkind
Senior
Dabei seit: 12.04.2016
Mitteilungen: 2570
| Beitrag No.6, eingetragen 2023-03-25
|
Huhu Julian,
logarithmiere (formal) deine Gleichung und bedenke dann \(\log \frac{1}{1-z}=z+\frac 12 z^2+\frac 13 z^3+\ldots\)
\(\displaystyle \prod_{k \geq 1}(1 + z^k + z^{2k} + ...)^{a_k} = \sum_{n \geq 0} p^n z^n\)
\(\displaystyle \prod_{k \geq 1}\left(\frac{1}{1-z^k}\right)^{a_k} = \frac{1}{1-pz}\)
\(\displaystyle \sum_{k=1}^\infty a_k \sum_{j=1}^\infty \frac{z^{jk}}{j}=\sum_{n=1}^\infty \frac{(pz)^n}{n}\)
Nun bedenke:
\(\displaystyle \sum_{n\ge1}\sum_{k\ge1}f(n,k)=\sum_{m\ge1}\sum_{nk=m}f(n,k)=\sum_{m\ge1}\sum_{n|m}f(n,m/n)\)
Damit kannst du dann deine Koeffizienten vergleichen und erhältst:
\(\displaystyle \sum_{d|n} a_d\frac{1}{n/d}=\frac{p^n}{n} \).
Gruß,
Küstenkind
|
Profil
|
julian2000P
Aktiv
Dabei seit: 25.10.2020
Mitteilungen: 225
| Beitrag No.7, vom Themenstarter, eingetragen 2023-03-25
|
Danke Nuramon und Kuestenkind, ich glaube die Aufgabe nun gelöst zu haben.
Grüße
|
Profil
|
endy
Senior 
Dabei seit: 10.01.2011
Mitteilungen: 3270
 | Beitrag No.8, eingetragen 2023-04-02
|
Hallo.
Folgender Thread könnte für dich noch interessant sein.
Siehe Klick mich.
generatingfunctionology findest Du in meinem Notizbuch zum Download.
Ebenfalls einen Algorithmus in mma für die a(n,q).
Gruss endy
|
Profil
|
julian2000P
Aktiv
Dabei seit: 25.10.2020
Mitteilungen: 225
| Beitrag No.9, vom Themenstarter, eingetragen 2023-04-03
|
Profil
|
julian2000P hat die Antworten auf ihre/seine Frage gesehen.
julian2000P hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
