Algebra: Reduktionskriterium

[Stephan Gerlach]

Q := rationale Zahlen
Z := ganze Zahlen
Z/n*Z := Restklassenring = {0, 1, 2, ..., n-1} mit n natürliche Zahl
Z[x] := Polynomring ganzzahliger Polynome
(Z/n*Z)[x] := Polynomring über Z/n*Z


Reduktionskriterium (vereinfachte Form)
---------------------------------------
Sei P = Summe_{k=0 bis m} a_k * x^k
ein Polynom aus Z[x] mit Leitkoeffizient a_m = 1.
Dann kann man P auffassen als Element von (Z/n*Z)[x], indem man einfach
die Koeffizienden a_k "modulo n" betrachtet.

Die Aussage des Reduktionskriteriums lautet verschiedenen Quellen
zufolge dann:
Ist n eine Primzahl, und ist P irreduzibel über (Z/n*Z)[x], so ist P
auch irreduzibel über Z[x].

Der Beweis geht wohl einfach so, daß man "P ist reduzibel" in Z[x]
annimmt, also eine Zerlegung P = P1*P1 mit Polynomen P1 und P2 aus Z[x].
Und daraus folgert man dann "P ist reduzibel" in (Z/n*Z)[x].


Soweit, so gut. Jetzt die Frage: Ist die Voraussetzung des
Reduktionskriteriums "n ist eine Primzahl" tatsächlich erforderlich?
Anders gefragt: Was genau geht im Beweis schief, wenn man diese
Voraussetzung wegläßt?
Noch anders gefragt: Gibt es ein Beispiel für ein Polynom, welches
irreduzibel in (Z/n*Z)[x] ist, aber reduzibel in Z[x]? Dabei müßte ja
definitiv n eine Nicht-Primzahl sein.

[Michael Klemm]

Stephan Gerlach

Post by Stephan Gerlach
Q := rationale Zahlen
Z := ganze Zahlen
Z/n*Z := Restklassenring = {0, 1, 2, ..., n-1} mit n natürliche Zahl
Z[x] := Polynomring ganzzahliger Polynome
(Z/n*Z)[x] := Polynomring über Z/n*Z

----

Post by Stephan Gerlach
Reduktionskriterium (vereinfachte Form)
---------------------------------------
Sei P = Summe_{k=0 bis m} a_k * x^k

ein Polynom aus Z[x] mit Leitkoeffizient a_m = 1.
Dann kann man P auffassen als Element von (Z/n*Z)[x], indem man einfach
die Koeffizienden a_k "modulo n" betrachtet.

Post by Stephan Gerlach
Die Aussage des Reduktionskriteriums lautet verschiedenen Quellen zufolge
Ist n eine Primzahl, und ist P irreduzibel über (Z/n*Z)[x], so ist P auch
irreduzibel über Z[x].
Der Beweis geht wohl einfach so, daß man "P ist reduzibel" in Z[x]
annimmt, also eine Zerlegung P = P1*P1 mit Polynomen P1 und P2 aus Z[x].
Und daraus folgert man dann "P ist reduzibel" in (Z/n*Z)[x].
Soweit, so gut. Jetzt die Frage: Ist die Voraussetzung des
Reduktionskriteriums "n ist eine Primzahl" tatsächlich erforderlich?
Anders gefragt: Was genau geht im Beweis schief, wenn man diese
Voraussetzung wegläßt?

Wenn ich mich richtig erinnere, ist n obdA eine Primzahl, weil man über Z/nZ
im
Nichtprimzahlfall genügend viel weiß.

Gruß
Michael

[Detlef Müller]

Post by Stephan Gerlach
Q := rationale Zahlen
Z := ganze Zahlen
Z/n*Z := Restklassenring = {0, 1, 2, ..., n-1} mit n natürliche Zahl
Z[x] := Polynomring ganzzahliger Polynome
(Z/n*Z)[x] := Polynomring über Z/n*Z
Reduktionskriterium (vereinfachte Form)
---------------------------------------
Sei P = Summe_{k=0 bis m} a_k * x^k
ein Polynom aus Z[x] mit Leitkoeffizient a_m = 1.
Dann kann man P auffassen als Element von (Z/n*Z)[x], indem man einfach
die Koeffizienden a_k "modulo n" betrachtet.
Die Aussage des Reduktionskriteriums lautet verschiedenen Quellen
Ist n eine Primzahl, und ist P irreduzibel über (Z/n*Z)[x], so ist P
auch irreduzibel über Z[x].
Der Beweis geht wohl einfach so, daß man "P ist reduzibel" in Z[x]
annimmt, also eine Zerlegung P = P1*P1 mit Polynomen P1 und P2 aus Z[x].
Und daraus folgert man dann "P ist reduzibel" in (Z/n*Z)[x].
Soweit, so gut. Jetzt die Frage: Ist die Voraussetzung des
Reduktionskriteriums "n ist eine Primzahl" tatsächlich erforderlich?
Anders gefragt: Was genau geht im Beweis schief, wenn man diese
Voraussetzung wegläßt?

Irreduzible Elemente sind (zumindest im Fischer/Sacher) für
Integritätsringe definiert.
Die Ringe (Z/n*Z)[x] sind nur für Primzahlen n Integritätsringe.

Setzen wir uns darüber hinweg und definieren einfach

r irreduzibel :<=> r ist nicht das Produkt zweier nicht-Einheiten.

Post by Stephan Gerlach
Noch anders gefragt: Gibt es ein Beispiel für ein Polynom, welches
irreduzibel in (Z/n*Z)[x] ist, aber reduzibel in Z[x]? Dabei müßte ja
definitiv n eine Nicht-Primzahl sein.

Nehmen wir n=4, dann ist p = 4 x^2 - 4 x +1 =(2x+1)(-2x+1) reduzibel
in Z[x].
Das Bild von p in (Z/n*Z)[x] wäre das Bild unter der
Quotienten-Abbildung Phi(p) = 1 das Einselement in (Z/4*Z)[x],
welches per Definition nicht als Produkt von nicht-Einheiten darstellbar
ist (dann wären sie ja Einheiten).

Gruß,
Detlef

[Stephan Gerlach]

Post by Detlef Müller

Post by Stephan Gerlach
Q := rationale Zahlen
Z := ganze Zahlen
Z/n*Z := Restklassenring = {0, 1, 2, ..., n-1} mit n natürliche Zahl
Z[x] := Polynomring ganzzahliger Polynome
(Z/n*Z)[x] := Polynomring über Z/n*Z
Reduktionskriterium (vereinfachte Form)
---------------------------------------
Sei P = Summe_{k=0 bis m} a_k * x^k
ein Polynom aus Z[x] mit Leitkoeffizient a_m = 1.
Dann kann man P auffassen als Element von (Z/n*Z)[x], indem man einfach
die Koeffizienden a_k "modulo n" betrachtet.
Die Aussage des Reduktionskriteriums lautet verschiedenen Quellen
Ist n eine Primzahl, und ist P irreduzibel über (Z/n*Z)[x], so ist P
auch irreduzibel über Z[x].

Zusatz: Läßt man die Voraussetzung a_m = 1 weg, so wird als zusätzliche
Voraussetzung "p teilt nicht a_m" gefordert.

In diesem Fall taugt das Gegenbeispiel (s.u.) nicht als solches.

Post by Detlef Müller

Post by Stephan Gerlach
Der Beweis geht wohl einfach so, daß man "P ist reduzibel" in Z[x]
annimmt, also eine Zerlegung P = P1*P1 mit Polynomen P1 und P2 aus Z[x].
Und daraus folgert man dann "P ist reduzibel" in (Z/n*Z)[x].
Soweit, so gut. Jetzt die Frage: Ist die Voraussetzung des
Reduktionskriteriums "n ist eine Primzahl" tatsächlich erforderlich?
Anders gefragt: Was genau geht im Beweis schief, wenn man diese
Voraussetzung wegläßt?

Irreduzible Elemente sind (zumindest im Fischer/Sacher) für
Integritätsringe definiert.

Ah... das war/ist also die Falle :-) .

Post by Detlef Müller
Die Ringe (Z/n*Z)[x] sind nur für Primzahlen n Integritätsringe.

Also ist - bösartig formuliert - die Voraussetzung "n ist Primzahl"
möglicherweise nur deswegen vorhanden, weil man irreduzible Polynome für
den Fall, daß der Polynomring nur ein "normaler" Ring ist, "vergessen"
hat zu definieren?!

Post by Detlef Müller
Setzen wir uns darüber hinweg und definieren einfach
r irreduzibel :<=> r ist nicht das Produkt zweier nicht-Einheiten.

Ich wüßte jetzt auf die Schnelle nicht, warum das für einen "normalen"
Polynomring (der nicht unbedingt Integritätsring ist) unsinnig wäre.

Evtl. ist aber hier noch ein Haken an der Sache.

Post by Detlef Müller

Post by Stephan Gerlach
Noch anders gefragt: Gibt es ein Beispiel für ein Polynom, welches
irreduzibel in (Z/n*Z)[x] ist, aber reduzibel in Z[x]? Dabei müßte ja
definitiv n eine Nicht-Primzahl sein.

Nehmen wir n=4, dann ist p = 4 x^2 - 4 x +1 =(2x+1)(-2x+1) reduzibel
in Z[x].

Soll das auf der rechten Seite des Gleichheitszeichens evtl.
(-2x+1)(-2x+1)
heißen?

Wie dem auch sei:
Der Leitkoeffizient a_m in Q bzw. Z ist in diesem Beispiel nicht 1; ich
wollte aber gerade voraussetzen, daß der 1 ist.

Post by Detlef Müller
Das Bild von p in (Z/n*Z)[x] wäre das Bild unter der
Quotienten-Abbildung Phi(p) = 1 das Einselement in (Z/4*Z)[x],
welches per Definition nicht als Produkt von nicht-Einheiten darstellbar
ist (dann wären sie ja Einheiten).

Das ist klar - p ist irreduzibel in (Z/4*Z)[x].

Gibt es aber auch ein Beispiel mit Leitkoeffizient a_m = 1 (in diesem
Fall 1 in Z *und* Z/4*Z)? Oder auch allgemeiner ein Beispiel, wo
zumindest n nicht Teiler von a_m ist?
Mir fiel bisher keines ein.

Stattdessen habe ich den Verdacht, daß der Beweis, der für den
Primzahl-Fall funktioniert, auch im Nicht-Primzahl-Fall noch funktioniert.

[Detlef Müller]

Post by Stephan Gerlach

Post by Detlef Müller

Post by Stephan Gerlach
Q := rationale Zahlen
Z := ganze Zahlen
Z/n*Z := Restklassenring = {0, 1, 2, ..., n-1} mit n natürliche Zahl
Z[x] := Polynomring ganzzahliger Polynome
(Z/n*Z)[x] := Polynomring über Z/n*Z
Reduktionskriterium (vereinfachte Form)
---------------------------------------
Sei P = Summe_{k=0 bis m} a_k * x^k
ein Polynom aus Z[x] mit Leitkoeffizient a_m = 1.
Dann kann man P auffassen als Element von (Z/n*Z)[x], indem man einfach
die Koeffizienden a_k "modulo n" betrachtet.
Die Aussage des Reduktionskriteriums lautet verschiedenen Quellen
Ist n eine Primzahl, und ist P irreduzibel über (Z/n*Z)[x], so ist P
auch irreduzibel über Z[x].

Zusatz: Läßt man die Voraussetzung a_m = 1 weg, so wird als zusätzliche
Voraussetzung "p teilt nicht a_m" gefordert.
In diesem Fall taugt das Gegenbeispiel (s.u.) nicht als solches.

Stimmt, der Leitkoeffizient kommt nicht hin.

Post by Stephan Gerlach

Post by Detlef Müller

Post by Stephan Gerlach
...

Nehmen wir n=4, dann ist p = 4 x^2 - 4 x +1 =(2x+1)(-2x+1) reduzibel
in Z[x].

Soll das auf der rechten Seite des Gleichheitszeichens evtl.
(-2x+1)(-2x+1)
heißen?

In der Tat ... natürlich klappt es viel besser mit der 3. Binomischen:

4x^2 - 1 = (2x-1)*(2x+1) u.s.w. Das repariert das Beispiel
natürlich auch nicht ...

Post by Stephan Gerlach
Der Leitkoeffizient a_m in Q bzw. Z ist in diesem Beispiel nicht 1; ich
wollte aber gerade voraussetzen, daß der 1 ist.
...
Gibt es aber auch ein Beispiel mit Leitkoeffizient a_m = 1 (in diesem
Fall 1 in Z *und* Z/4*Z)? Oder auch allgemeiner ein Beispiel, wo
zumindest n nicht Teiler von a_m ist?
Mir fiel bisher keines ein.
Stattdessen habe ich den Verdacht, daß der Beweis, der für den
Primzahl-Fall funktioniert, auch im Nicht-Primzahl-Fall noch funktioniert.

Da hast Du wohl recht:

Da die Quotientenabbildung Phi: Z[x] --> (Z/k*Z)[x], p->p'
ein Homomorphismus ist, gilt

p = p_1 * p_2 => p' = p_1' * p_2'.

Mit deg(p_1),deg(p_2)>0 und Leitkoeffizienten L(p_1)=L(p_2)=1.
Das kann man erreichen weil L(p_1)*L(p_2)=L(p)=1 ist (p ist normiert),
also L(p_1) und L(p_2) beide 1 oder beide -1 (die beiden einzigen
Einheiten in Z) sein müssen.
Falls beide -1 sind geht man zu p=(-p_1)*(-p_2) über.

p' kann also nur irreduzibel sein, wenn p_1' oder p_2' eine
Einheit in (Z/(k*Z))[x] ist (ansonsten wären p_1 und p_2 "Zeugen"
der Reduzibilität von p').

Damit ein Polynom

x^n + a_{n-1} x^(n-1) + ...

eine Einheit ist, müsste in (Z/(k*Z))[x] ein Polynom b existieren mit

1 = (x^n + a_{n-1} x^(n-1) + ...) * (b_m x^m+ b_(m-1)x^(m-1)+...) (*)

wobei b_m=L(b) != 0 sei.

Der Leitterm dieses Produktes ist aber b_m x^(m+n),
wegen b_m!=0 kann b_m x^(m+n) nicht 0 sein und (*) ist für
kein Polynom aus (Z/(k*Z))[x] erfüllbar.

Durch die Normierung von p_1' und p_2' klappt das wirklich für
beliebige k>1. Da die Leitkoeffizienten nun garantiert keine
Nullteiler sind, können sie nicht über eine Polynom-Multiplikation
eliminiert werde.

Gruß,
Detlef

[Ronald Benedik]

Sei I ein Ring:

Ein Polynomring P[X] über I ist genau dann ein Integritätsbereich,
wenn I ein Integritätsberiech ist.