Elementordnungen in S_n

28.04.2020, 13:15

Phasma

Elementordnungen in S_n

a) Eine Permutation $\begin{eqnarray*} \sigma \end{eqnarray*}$ sei das Produkt zweier disjunkter Zykel der teilerfremden Längen $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} l \end{eqnarray*}$ . Welche Ordnung hat $\begin{eqnarray*} \sigma \end{eqnarray*}$ ?
b) Sei $\begin{eqnarray*} a(n) \end{eqnarray*}$ die größte Elementordnung in der symmetrischen Gruppe $\begin{eqnarray*} S_n \end{eqnarray*}$ . Man zeige $\begin{eqnarray*} \lim_{n \to \infty } \frac{a(n)}{n} = \infty \end{eqnarray*}$ .

Meine Idee zu a): Ich bin mir ziemlich sicher, dass $\begin{eqnarray*} \sigma \end{eqnarray*}$ die Ordnung $\begin{eqnarray*} k\cdot l \end{eqnarray*}$ hat. Begründung: Die Ordnung des einen Zykels ist $\begin{eqnarray*} k \end{eqnarray*}$ , die des anderen Zykels $\begin{eqnarray*} l \end{eqnarray*}$ . Da die beiden Zykel disjunkt sind, sich also nicht gegenseitig "beeinflussen" können, muss die Ordnung von $\begin{eqnarray*} \sigma \end{eqnarray*}$ ein Vielfaches von $\begin{eqnarray*} k \end{eqnarray*}$ und ein Vielfaches von $\begin{eqnarray*} l \end{eqnarray*}$ sein. Also das kleinste gemeinsame Vielfache. Da $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} l \end{eqnarray*}$ teilerfremd sind, ist aber $\begin{eqnarray*} kgV(k,l)=k\cdot l \end{eqnarray*}$ .
Meine Frage: Reicht diese Argumentation als Beweis oder muss man das formaler aufschreiben?

Zu b) habe ich leider keine Idee. Könnte mir hier jemand weiterhelfen?

28.04.2020, 13:20

Elvis

Auf diesen Beitrag antworten »

a) stimmt
b) ist dann trivial . betrachte zwei elementfremde Zykel der Länge ca. n/2 ("ca." weil n auch ungerade sein darf).

28.04.2020, 21:34

Phasma

Auf diesen Beitrag antworten »

Ok, ich nehme also am besten zwei aufeinanderfolgende Zykel, damit sie teilerfremd sind. Also mit Längen $\begin{eqnarray*} \lfloor{\frac{n-1}{2}}\rfloor \end{eqnarray*}$ und $\begin{eqnarray*} \lfloor{\frac{n+1}{2}}\rfloor \end{eqnarray*}$ ?
So, dass sie disjunkt sind, natürlich. Die größte Elementordnung muss größer/gleich die Ordnung dieses Produkts sein, und mit a) divergiert der Grenzwert.

28.04.2020, 21:59

Elvis

Auf diesen Beitrag antworten »

Im Prinzip ja. Die Zykel sind nicht teilerfremd sondern elementfremd. Wie man Zykel so wählen kann, dass ihre Längen teilerfremd sind, ist mir noch nicht ganz klar. Da fehlt ein kleiner Beweis. (n/2 und maximale Primzahl kleiner als n/2 scheint mir ein möglicher Ansatz zu sein. Das Produkt hat dann annähernd die Größe n/2*n/2.)
Man kann auch nicht sagen, dass der Grenzwert divergiert. Man sagt, dass die Folge bestimmt gegen $\begin{eqnarray*} +\infty \end{eqnarray*}$ divergiert.

28.04.2020, 22:54

Elvis

Auf diesen Beitrag antworten »

Übungsaufgabe. Man beweise, dass die Elvis-Funktion $\begin{eqnarray*} f(n) :=max\{\frac {p\cdot q} n:p, q \, prim, p+q\le n\} \end{eqnarray*}$ für $\begin{eqnarray*} n\to +\infty \end{eqnarray*}$ bestimmt gegen $\begin{eqnarray*} +\infty \end{eqnarray*}$ divergiert.

28.04.2020, 23:35

Phasma

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Wie man Zykel so wählen kann, dass ihre Längen teilerfremd sind, ist mir noch nicht ganz klar. Da fehlt ein kleiner Beweis. (n/2 und maximale Primzahl kleiner als n/2 scheint mir ein möglicher Ansatz zu sein. Das Produkt hat dann annähernd die Größe n/2*n/2.)

Das verstehe ich nicht. Kann ich dann nicht einfach zwei Zykel wählen, sodass die Zykellängen sich nur um 1 unterscheiden, z.B. $\begin{eqnarray*} \lfloor{\frac{n-1}{2}}\rfloor \end{eqnarray*}$ und $\begin{eqnarray*} \lfloor{\frac{n+1}{2}}\rfloor \end{eqnarray*}$ ? Dann wären die Zykellängen doch auf jeden Fall teilerfremd.

Was die Divergenz der Elvis-Funktion angeht, bin ich leider noch ratlos.

29.04.2020, 07:11

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} t|a\wedge t|a+1\Rightarrow tb=a\wedge tc=a+1\Rightarrow 1=tc-tb=t(c-b)\Rightarrow t|1\Rightarrow ggT(a, a+1)=1 \end{eqnarray*}$
Du hast recht.

Neue Frage »

Antworten »

Elementordnungen in S_n

Verwandte Themen