Die Mathe-Redaktion - 20.04.2019 02:33 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt2 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 268 Gäste und 8 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Erzeugende Funktionen » Eigenschaften normierter Polynome mittels analytischer Kombinatorik zeigen
Druckversion
Druckversion
Autor
Universität/Hochschule J Eigenschaften normierter Polynome mittels analytischer Kombinatorik zeigen
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-03-21


Hallo allerseits,

ich habe ein kombinatorisches Problem, bei dem ich auf eure Hilfe hoffe:
Sei R = GF(p)[x] der Polynomring mit Koeffizienten aus dem endlichen Körper GF(p), p Primzahl. Es sei als bekannt vorausgesetzt, dass jeden normierte Polynom eine eindeutige Darstellung als Produkt von irreduziblen normierten Polynomen besitzt. Sei $a_n$ die Anzahl der normierten irreduziblen Polynome vom Grad n in R. Zeige:
a) $\prod_{k \geq 1}(1+z^k+z^{2k}+...)^{a_k} = \sum_{n \geq 0}p^n z^n$,
b) $p^n = \sum_{d|n, d>0}da_d$.

Mir fehlt leider sowohl zu a) als auch zu b) jegliche Idee. Die Aufgabe sollte sich irgendwie mit symbolischen Methoden (der analytischen Kombinatorik) und/oder (exponentiellen) erzeugenden Funktionen lösen lassen, aber ich schaffe es eben nicht.

Würde mich freuen, wenn mir jemand auf die Sprünge helfen könnte. Danke!



  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 1115
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-03-21


Hallo Newmath2012,

zumindest für a) hätte ich einen Vorschlag (ohne Garantie auf Erfolg).
a) $\prod_{k \geq 1}(1+z^k+z^{2k}+...)^{a_k} = \sum_{n \geq 0}p^n z^n$
Um diese Gleichung etwas handlicher zu machen, hast Du für $z\in\IC; |z|<1/p$ auf beiden Seiten es mit konvergenten geometrischen Reihen zu tun. Durch einsetzen der Formeln, Logarithmus und ggf. ableiten sollte eine etwas angenehmere Aussage entstehen.



  Profil  Quote  Link auf diesen Beitrag Link
Creasy
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-03-21


Hey
Bei b) kann man (vermutlich) zeigen, dass $$X^{p^n}-X=\prod_{d|n} \prod_{f\in M_d}f ,$$ wobei $M_d$ die Menge der normierten irreduziblen Polynome vom Grad d (über GF(p)) ist. Dann folgt die Aussage aus Gradgründen.


Edit: p (jetzt f) als Wahl für Polynom war eine schlechte Wahl :S
Beste Grüße
Creasy


-----------------
Smile (:



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2107
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-03-21


Hallo,

wenn du die a) gelöst hast, ist die b) nicht mehr schwer. Multipliziere die linke Seite aus und vergleiche die Koeffizienten vor $z^k$.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-03-22

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Hallo,

Teil a) ist eine Umformulierung der Aussage

dass jeden normierte Polynom eine eindeutige Darstellung als Produkt von irreduziblen normierten Polynomen besitzt.

Das sieht man am einfachsten, indem man das Produkt umformt zu
\[\prod_{k \geq 1}(1+z^k+z^{2k}+\ldots)^{a_k} = \prod_{\substack{f\in R\\ f \text{ irreduzibel}}}(1+z^{\deg f}+z^{2\deg f}+z^{3\deg f}+\ldots)\] und sich dann klar macht, dass nach Ausmultiplizieren der Koeffizient vor $z^n$ gerade die Anzahl der normierten Polynome vom Grad $n$ ist.

Creasys Ansatz aus No.2 für Teil b) funktioniert.
Wie Ochens Ausmultiplizieransatz aus No.3 geht ist mir im Moment nicht klar, was aber nicht heißt, dass der Ansatz falsch wäre.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-03-22


Danke für eure Antworten!

Ich habe jetzt einmal a) versucht, aber komme leider nicht so weit:
$\prod_{k \geq 1}(1+z^k+z^{2k}+...)^{a_k} = \sum_{n \geq 0}p^n z^n \Leftrightarrow log(\sum_{k \geq 1}a_k(1+z^k+...)) = log (\sum_{n \geq 0} p^n z^n) \Leftrightarrow \sum_{k \geq 1}a_k(1+z^k+...) = 1+ \sum_{n \geq 1}p^n z^n$.
Ich nehme an, dass man da jetzt das verwenden muss, was in der Angabe als bekannt vorausgesetzt ist? Aber ich weiß nicht, wie.

[Die Antwort wurde nach Beitrag No.3 begonnen.]

Okay, ich versuche es nun mit Nuramons Beitrag weiterzuverstehen.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-03-22


Hallo Nuramon, danke für deine Antwort.
Ich sehe nicht, warum man in \[\prod_{k \geq 1}(1+z^k+z^{2k}+\ldots)^{a_k} = \prod_{f\in R}(1+z^{\deg f}+z^{2\deg f}+z^{3\deg f}+\ldots)\] nicht noch beim Produkt auf der rechten Seite extra fordern muss, dass f irreduzibel und normiert ist. (Weil R enhält ja ALLE normierten Polynome, nicht nur die normierten, irreduziblen, auf die sich $a_k$ bezieht?)
Und das mit dem Ausmultiplizieren schaffe ich leider nicht, bei so "unendlichen" Produkten kriege ich leider immer einen Knopf im Hirn. Hast du einen Tipp, wie ich mir überlegen kann, wie das Produkt aussieht?



  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 10.01.2011
Mitteilungen: 3154
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-03-22


Hallo.

Siehe Klick mich.

Gruss endy




  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-03-22

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-03-22 13:35 - Newmath2012 in Beitrag No. 6 schreibt:
Ich sehe nicht, warum man in \[\prod_{k \geq 1}(1+z^k+z^{2k}+\ldots)^{a_k} = \prod_{f\in R}(1+z^{\deg f}+z^{2\deg f}+z^{3\deg f}+\ldots)\] nicht noch beim Produkt auf der rechten Seite extra fordern muss, dass f irreduzibel und normiert ist.
Da hast du recht. Ich werde es gleich korrigieren.

Die Idee ist im Wesentlichen so:
Angenommen $g\in R$. Um die Zerlegung von $g$ in ein Produkt irreduzibler Polynome anzugeben, muss man für jedes irreduzible Polynom  $f$ angeben, wie oft es in dieser Zerlegung vorkommt. Letzteres entspricht der Wahl eines Summanden im Faktor $(1+z^{\deg f}+z^{2\deg f}+z^{3\deg f}+\ldots)$ des Produkts.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 1115
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-03-22


2019-03-22 13:21 - Newmath2012 in Beitrag No. 5 schreibt:
$\prod_{k \geq 1}(1+z^k+z^{2k}+...)^{a_k} = \sum_{n \geq 0}p^n z^n \\ \Leftrightarrow log(\sum_{k \geq 1}a_k(1+z^k+...)) = log (\sum_{n \geq 0} p^n z^n) \\ \Leftrightarrow \sum_{k \geq 1}a_k(1+z^k+...) = 1+ \sum_{n \geq 1}p^n z^n$.

Hallo Newmath2012,

in der zweiten Zeile sollte der log in der (ersten) Summe stehen. Wenn Du nun $\sum (pk)^n = \frac{1}{1-pz}$ - analog auf der rechten Seite der Gleichung - verwendest, wird es auch einfacher. Im Link aus #7 von endy findest Du dieselbe Rechnung im Detail.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-03-22


@Nuramon
Hallo Nuramon,
ich stehe leider auf der Leitung. Die von dir beschriebene Idee ist mir klar, aber ich verstehe nicht, wie man nun die Brücke zu $\sum_{n \geq 0}p^n z^n$ baut.




  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2019-03-22


@endy und @TomTom314:
Wie in dem verlinkten Thread habe ich nun $\sum_{n \geq 0}p^nz^n = \prod_{k \geq 1}\frac{1}{(1-z^k)^{a_k}} \Leftrightarrow ... \Leftrightarrow \sum_{n=1}^{\infty}z^np^n = \sum_{j=1}^{\infty}a_j \cdot j \cdot \frac{z^j}{1-z^j}$. Ablesen des Koeffizienten auf der linken Seite ergibt $p^n$. Auf der rechten Seite muss der Koeffizient also $\sum_{d|n, d>0}da_d$ sein, damit wir das Gewünschte gezeigt haben. Ich bekomme aber die Reihendarstellung von $\frac{z^j}{1-z^j}$ nicht hin und fürchte, dass ich da dann auch nicht auf den gewünschten Koeffizienten komme?



  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 1115
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-03-22


Mit $\frac{z^j}{1-z^j} = z^j \cdot \frac{1}{1-z^j}$ hast Du hier eine geometrische Reihe in $z^j$. Danach mußt Du nur noch die Koeffizienten auf der rechten Seite zählen.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-03-22

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-03-22 16:26 - Newmath2012 in Beitrag No. 10 schreibt:
@Nuramon
Hallo Nuramon,
ich stehe leider auf der Leitung. Die von dir beschriebene Idee ist mir klar, aber ich verstehe nicht, wie man nun die Brücke zu $\sum_{n \geq 0}p^n z^n$ baut.


Die Anzahl der normierten Polynome mit Grad $n$ ist $p^n$.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-03-22


Danke, TomTom314, b) habe ich nun.

@Nuramon: Du hast Recht, den Satz hatte ich gerade nicht parat. Allerdings verstehe ich es leider immer noch gar nicht.
Wieso betrachten wir die Zerlegung eines $g \in R$? Ich dachte, die Idee war nur für die Umformung die du hingeschrieben hast? Aber offenbar stellt sie den gesuchten Zusammenhang her?
Kann man sich unter $\prod_{k\geq 1}(1+z^k+z^{2k}+...)^{a_k}$ und/oder $\sum_{n \geq 0}p^n z^n$ etwas Bestimmtes vorstellen, das bei der Überlegung hilft (also sowas wie das Produkt der Faktoren eines Polynoms oder irgendwas?$ Ich blicke grad absolut gar nicht durch leider...



  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 1115
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-03-23 13:36


Hallo Newmath2012,

eine kleine Anmerkung habe ich noch.
... b) habe ich nun.
Effektiv hast Du nun a) <=> b). Mit dem Ansatz von Creasy aus #2 kannst Du b) direkt zeigen und somit a). Wahrscheinlich sollte aber eher a) => b) verwendet werden.  wink



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-03-23 14:47

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-03-22 22:23 - Newmath2012 in Beitrag No. 14 schreibt:
@Nuramon: Du hast Recht, den Satz hatte ich gerade nicht parat. Allerdings verstehe ich es leider immer noch gar nicht.
Wieso betrachten wir die Zerlegung eines $g \in R$? Ich dachte, die Idee war nur für die Umformung die du hingeschrieben hast? Aber offenbar stellt sie den gesuchten Zusammenhang her?
Kann man sich unter $\prod_{k\geq 1}(1+z^k+z^{2k}+...)^{a_k}$ und/oder $\sum_{n \geq 0}p^n z^n$ etwas Bestimmtes vorstellen, das bei der Überlegung hilft (also sowas wie das Produkt der Faktoren eines Polynoms oder irgendwas?$ Ich blicke grad absolut gar nicht durch leider...
$\prod_{k\geq 1}(1+z^k+z^{2k}+...)^{a_k}$ und $\sum_{n \geq 0}p^n z^n$ sind die erzeugenden Funktionen der Folge deren $n$-tes Folgenglied die Anzahl der normierten Polynome vom Grad $n$ ist:

Sei $S\subset R$ die Menge der normierten Polynome und sei $P\subset S$ die Menge der normierten irreduziblen Polynome. Sei $P^{(\IN)}$ die Menge der Tupel $(k_f)_{f\in P}$ mit $k_f \in \IN$, wobei nur endlich viele $k_f \not=0$ sind.
Dann ist die Abbildung
\[P^{(\IN)} \to S, \qquad (k_f)_{f\in P} \mapsto \prod_{f\in P}f^{k_f}\] eine Bijektion.
Ein Element $(k_f)_{f\in P}\in P^{(\IN)}$ wird von dieser Bijektion auf ein Polynom von Grad $n$ abgebildet, genau dann, wenn $\sum_{f\in P} k_f\deg f =n$ gilt.
Daher ist die Anzahl der normierten Polynome von Grad $n$ gleich der Anzahl der Tupel $(k_f)_{f\in P}\in P^{(\IN)}$ mit $\sum_{f\in P}k_f\deg f =n$.
Letztere Anzahl ist aber genau der Koeffizient vor $z^n$ in der Potenzreihe
\[\prod_{f\in P}(1+z^{\deg f}+z^{2\deg f}+...) = \prod_{k\geq 1}(1+z^k+z^{2k}+...)^{a_k}\]
Andererseits ist die Anzahl der normierten Polynome von Grad $n$ offenbar gleich $p^n$ und somit folgt a).
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, vom Themenstarter, eingetragen 2019-03-27 17:58


@TomTom314: Danke für den Hinweis!



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 302
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2019-03-27 17:58


@Nuramon: Hallo Nuramon, vielen Dank für die Erklärung!
Ich habe es nun verstanden. :)



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012 hat die Antworten auf ihre/seine Frage gesehen.
Newmath2012 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]