Ciklikus rend

A ciklikus rend algebrai fogalom, a véges testek elméletében van alapvető szerepe. Fontos elméleti szerepe van például az ilyen testek feletti polinomok felbonthatóságának jellemzésében, de a testbővítések elméletében is hasznos. A véges testek elméletének egyébként például a digitális jelfeldolgozás elméletében van fontos szerepe (kódoláselmélet stb.).

Legyen K véges test, és R ≤ K ennek egy részteste (tehát K|R, azaz K az R egy bővítése). Az a∈K elem R résztestre vonatkozó ciklikus rendje ekkor

$c_{R}(a)\ :=\ min\left\{j\in N^{+}\ |\ a^{|R|^{j}}=a\right\}\in N^{+}$.

A definícióban szereplő $a^{|R|^{j}}\ ,\ j\in \mathbb {N} ^{+}$ elemet, mely tehát az a egy hatványa az a∈K testbeli elem R résztestre vonatkozó j indexű ciklikus asszociáltjának nevezzük.

A fentivel ekvivalens az a definíció, hogy egy test valamely elemének adott résztestre vonatkozó ciklikus rendje az adott résztestre vonatkozó ciklikus asszociáltjai sorozatának – amely periodikus – (minimális) periódusa. Lásd lentebb.

Egyértelmű létezése

Belátható, hogy véges test bármely elemének bármely résztestre vonatkozóan létezik ciklikus rendje, ugyanis

• ha $a=0$ (a test nulleleme); akkor $0^{|R|^{1}}=0^{|R|}=0$ miatt ennek a ciklikus rendje a definíció szerint automatikusan $c_{R}(0)=1$;
• ha pedig $a\neq 0$ nem nullelem, akkor is „kiszámolható” a ciklikus rend, a következőképp:
  • ha valamely $j\in N^{+}$ -re $a^{|R|^{j}}=a$, akkor szorozva ezt az egyenlőséget az $a$ elem $a^{-1}$ inverzével, adódik $a^{|R|^{j}}\cdot a^{-1}=a^{|R|^{j}-1}\ =\ 1=a^{0}$, ami pedig akkor és csak akkor igaz, ha $|R|^{j}-1\equiv 0{\pmod {o(a)}}$, azaz $|R|^{j}\equiv 1{\pmod {o(a)}}$, ahol $o(a)=o_{K}^{\times }(a)=o_{K^{*}}(a)$ az a elem rendje a K test multiplikatív csoportjában.
  • Mi most a legkisebb ilyen pozitív egész $j$-t keressük, ez pedig definíció szerint az $|R|\geq 2$ nemnegatív szám mod(o(a)) multiplikatív rendje, azaz $o_{o(a)}^{\times }\left(|R|\right)$.
  • Megmutatjuk, hogy ez létezik: ennek szükséges és elégséges feltétele, hogy $\left(o(a),|R|\right)=1$, azaz ezek relatív prímek legyenek. Valóban, hiszen o(a) osztója a $K^{*}=\left(K-{0},\times \right)$ multiplikatív csoport rendjének, azaz $|K|-1$-nek, $|R|$ pedig $|K|$-nak (ezek lényegében Lagrange tételéből következnek), tehát $1=\left(|K|-1,|K|\right)=\left(z_{1}o(a)\ ,\ z_{2}|R|\right)=\left(o(a),|R|\right)$ (ha utóbbiaknak lenne 1-nél nagyobb közös osztója, akkor |K|-1-nek és |K|-nak is, holott egy kettőnél nagyobb egész és bármely szomszédja mindig relatív prímek).
  • Tehát $c_{R}(a)=o_{o(a)}(|R|)$ $=$ $o_{o_{K}^{\times }(a)}^{\times }(|R|)$ (az indexek sorra azt jelzik, hogy itt egy egész számokon értelmezett multiplikatív rendről van szó, melynek modulusa egy K test multiplikatív csoportján belül értelmezett (tehát szintén multiplikatív jellegű) rend.

A ciklikus rend tehát lényegében egy számelméleti, az egész számok körében értelmezett multiplikatív rend, a számelméletben értelmezett multiplikatív rendre pedig nem adható olyan explicit képlet, mint az additív rendre, ezért a ciklikus rendre sem. De már a fenti alak is rávilágít arra, hogy bármely elem ciklikus rendje létezik és egyértelmű (persze ha az R résztest rögzített), hiszen az elem („multiplikatív csoportbeli multiplikatív”) rendje is egyértelmű, és erre a modulusra nézve az |R| („egész számokbeli multiplikatív”) multiplikatív rendje is egyértelmű.

Megjegyezzük, hogy a definícióban szereplő elemhalmazból kizártuk a $a^{|R|^{0}}=a^{1}=a$ elemet (pontosabban, az a benne van, csak az indexe nem 0), és a továbbiakban is ezt tesszük, hiszen ez triviálisan egyenlő a-val, tehát j = 0 megengedése esetén a ciklikus rend mindig 0 volna, és így nem lenne sok értelme e fogalomnak.

Tulajdonságok

Kapcsolat a ciklikus asszociáltakkal

Mint a rendfogalom általában a matematikában, a ciklikus rend is egy hatványokból álló sorozat, a ciklikus asszociáltak végtelen sorozat periódusa. Ha K|R, azaz R≤K a K részteste, és a∈K, akkor Ekkor az $a^{|R|^{j}}\ ,\ j\in \mathbb {N} ^{+}$ elemet, mely tehát az a egy hatványa az a∈K testbeli elem R résztestre vonatkozó j indexű ciklikus asszociáltjának nevezzük. Ezen elemek végtelen sorozatát jelölje $C_{R}\left(a\right):=\left(a^{|R|^{j}}\right)_{j\in \mathbb {N} ^{+}}$ $=$ $\left(a^{|R|^{1}},a^{|R|^{2}},\cdots ,a^{|R|^{j}},\cdots \right)\in K^{\mathbb {N} ^{+}}$. A $j\in \mathbb {N} ^{+}$ kitevő az $a^{|R|^{j}}$ ciklikus asszociált indexe.

Bár e sorozat végtelen, értékkészlete, vagyis a „benne lévő” K-beli elemek $R\left(C_{R}\left(a\right)\right):=$ $=\left\{k\in K\ |\ \exists j\in \mathbb {N} ^{+}\ :\ k=a^{|R|^{j}}\right\}$ $=$ $\left\{a^{|R|^{1}},a^{|R|^{2}},\cdots ,a^{|R|^{j}},\cdots \right\}$ értékkészlete véges, mivelhogy maga K is véges. Belátható, hogy e sorozat periodikus, és (minimális) periódusa épp az a R-re vonatkozó ciklikus rendje. Lásd lentebb.

A ciklikus rend modulusra kongruens indexű asszociáltak egyenlőek

Tétel: Az a∈K elem R≤K résztestre vonatkozó két ciklikus asszociáltja akkor és csak akkor egyenlő, ha indexük kongruens az a R-re vonatkozó ciklikus rendjére mint kongruenciamodulusra nézve. Azaz

$a^{|R|^{i}}=a^{|R|^{j}}\Leftrightarrow i\equiv j{\pmod {c_{R}(a)}}$.

• Legyen $a^{|R|^{i}}=a^{|R|^{j}}$,
  • szorozva (a nemnullaság miatt létező) inverzzel $a^{|R|^{i}-|R|^{j}}=1=a^{0}$. Szorozva még a-val is, $a^{|R|^{i}-|R|^{j}+1}=a=a^{1}$.
  • Ez azonban a csoportelméletben értelmezett rend tulajdonságai miatt pontosan akkor teljesül, ha $|R|^{i}-|R|^{j}+1\equiv 1{\pmod {o(a)}}$, azaz $|R|^{i}\equiv |R|^{j}{\pmod {o(a)}}$.
  • Mivel i,'j két tetszőlegesen választott index volt, az általánosság megszorítása nélkül feltehető j≤i, így $|R|^{j}\leq |R|^{i}$.
  • Kongruenciát egyszerűsíthetünk egy szorzóval (jelen esetben $|R|^{j}$-vel), hogy a modulust osztjuk a modulus és a szorzó legnagyobb közös osztójával. Tehát érvényes $|R|^{i-j}\equiv 1{\pmod {\frac {o(a)}{\left(o\left(a\right),|R|^{j}\right)}}}$.
  • Ahogy az egyértelmű létezés igazolásánál már beláttuk, $\left(o(a),|R|^{j}\right)=\left(o(a),|R|\right)=1$, mert a pozitív kitevőjű hatványozás a relatív prímségen nem változtat, és Lagrange tétele szerint o(a) | |R|-1 = |R*|, tehát ekkor $d=\left(o(a),\ |R|\right)\ |\ |R|,|R|-1$ esetén $d\ |\ |R|-1-|R|=1$ miatt $d=1$ (ha $d$ osztója két számnak, a különbségüknek is).
  • Egyszóval azt kaptuk, $|R|^{i-j}\equiv 1=|R|^{0}{\pmod {o(a)}}$. Ez pedig ekvivalens azzal a multiplikatív rend tulajdonságai miatt, hogy $i-j\equiv 0{\pmod {o_{o(a)}^{\times }(|R|)}}$, ami pontosan azt jelenti, hogy $i\equiv j{\pmod {o_{R}(a)}}$, mivelhogy már beláttuk, $o_{o(a)}^{\times }(|R|)=c_{R}(a)$.

A „fordított irány” igazolása elemibb:

• legyen $i,j\in \mathbb {N} ^{+}$, ekkor $c_{R}(a):=c$ és $i\equiv j{\pmod {c}}$, azaz valamely q∈ℤ-re $i=cq+j$.
  • Feltehető $q>0$. Ha ugyanis q=0, akkor i=j, és ez esetben triviálisan $a^{|R|^{j}}=a^{|R|^{i}}$, egyébként pedig ha az i-j különbség c-vel osztva nem pozitív, akkor a j-i különbség c-vel osztva már pozitív, így as jelöléseket megfelelően választhatjuk meg.
  • Ekkor $a^{|R|^{i}}$ $=$ $a^{|R|^{cq+j}}$ $=$ $a^{|R|^{cq}\cdot |R|^{j}}$ $=$ $\left[a^{|R|^{cq}}\right]^{|R|^{j}}$ $=$ $\left[a^{\left(|R|^{c}\right)^{q}}\right]^{|R|^{j}}$ $=$ $\left[a\right]^{|R|^{j}}$.
  • Ha ez igaz, akkor készen is vagyunk. Márpedig igaz, az egyetlen dolog, ami a fenti levezetésben kérdéses hitelességű lehet, az az $a^{\left(|R|^{c}\right)^{q}}=a$ egyenlőség. A q>0-ra vonatkozó indukcióval azonban egyszerűen megmutatható, hogy ez igaz (arról van szó, hogy egy q-lépcsős emeletes hatvány képződik, az a elemet először az $|R|^{c}$ -edik hatványra emeljük; ami c definíciója szerint a-t eredményez, aztán ezt megint ugyanarra a kitevőre emeljük, az is a-t ad, … s.í.t.; de e gondolatmenetet nyomdatechnikai képtelenség leírni, ezért inkább teljes indukciót alkalmazunk).
  • Ugyanis q = 1 -re $a^{\left(|R|^{c}\right)^{1}}=a^{|R|^{c}}=a$, hisz ez a c ciklikus rend definíciója. Ha pedig valamilyen 1-nél nagyobb q-ra már igaz $a^{\left(|R|^{c}\right)^{q}}=a$ („indukciós feltevés”), akkor ezt eggyel növelve $a^{\left(|R|^{c}\right)^{q+1}}=a^{\left(|R|^{c}\right)^{q}\cdot |R|^{c}}=\left(a^{\left(|R|^{c}\right)^{q}}\right)^{|R|^{c}}=$ (most használjuk az „indukciós feltevést”) $\left(a\right)^{|R|^{c}}=a$.
• Ezzel az utolsó hiányzó bizonyítási lépés is megvan, QED.

Az a-t adó indexek a ciklikus rend többszörösei

A tétel egy fontos alesetét a következőképp fogalmazhatjuk: az a-val egyenlő ciklikus asszociáltak indexei pontosan a ciklikus rend többszörösei. Ez a = 0 esetében azért igaz, mert a ciklikus rend 1, és bármely pozitív egész 0-t adó index, és az 1 mindet osztja is; ha pedig a≠0, akkor ha $a^{|R|^{j}}=a=a^{1}=a^{|R|^{0}}$ épp akkor igaz az előzőek szerint, ha $j\equiv 0{\pmod {c_{R}(a)}}$, azaz ha c_R(a) | j.

A ciklikus rend az asszociált-sorozat minimális periódusa

A fenti tétel azonnali következménye, hogy a ciklikus rend a ciklikus asszociáltak sorozatának minimális periódusa (az előző tétel tkp. ennek matematikai megfogalmazása). Hiszen azt állítjuk, hogy – c-vel jelölve a ciklikus rendet – az i, i+c, i+2c, … , i+kc … indexű elemek lesznek pontosan az i indexű ciklikus asszociálttal egyenlőek, tehát c szerint periodikus a sorozat.

A ciklikus asszociáltak száma

Tétel: Az a elem R résztestre vonatkozó különböző ciklikus asszociáltjainak száma az elem R-re vonatkozó ciklikus rendje, azaz $c:=|C_{R}(a)|=c_{R}(a)$.

• Először is, C véges; és egyik eleme sem 0; ugyanis elemei a K test elemei, és K véges; továbbá minden elem a K*=(K\{0},×) multiplikatív csoport eleme, és a 0 ebben nincs benne.
• C-nek pontosan c db. eleme van, mert $a^{|R|^{1}}$ , $a^{|R|^{2}}$ , … , $a^{|R|^{c}}$ páronként különböző C-beli elemek, ha ugyanis valamely i,j∈ℕ⁺-ra $a^{|R|^{i}}=a^{|R|^{j}}$ volna, akkor az indexek a ciklikus rend (mint modulus) szerint kongruensek volnának az előző tétel miatt. Ez azonban nem lehetséges, hisz az indexek láthatóan a ciklikus rend szerinti legkisebb pozitív teljes maradékrendszer elemei (csak a 0 maradt ki), és teljes maradékrendszer elemei inkongruensek a modulus szerint.
• Tehát legalább c db. elem van C-ben, a fent említettek, ennél több viszont nincs, mert az indexek egy mod(c) teljes maradékrendszert alkotnak, és ezen kívüli minden index már kongruens valamelyik fenti indexszel mod(c'), tehát egyenlő az ahhoz az indexhez tartozó asszociálttal.

Testbővítések és a ciklikus rend

A ciklikus rend osztója a bővítés fokának

Tétel: Ha R≤K és K véges, azaz K az R valamilyen véges d-edfokú testbővítése, akkor bármely a∈K-ra $c_{R}(a)\ |\ d$.

• Ha K|R és dg(K|R) = d, akkor belátható $|K|=|R|^{d}$ , azaz felhasználjuk azt a tételt, hogy egy R test véges- és ezért véges fokú K bővítésének |R|^d számú eleme van; ti. van ilyen $d\in \mathbb {N} ^{+}$ pozitív egész, ezt egyébként a bővítés fokának nevezzük. Ekkor a K*=(K\{0},×) multiplikatív csoport rendje $|R|^{d}-1$; hisz csak a nullát nem tartalmazza; aminek az a∈K elem o(a) rendje az osztója Lagrange tételéből következően, és így érvényes $a^{|R|^{d}-1}=1$, ezt az egyenlőséget a-val szorozva $a^{|R|^{d}}=a$. Ez egy előző tétel miatt akkor és csak akkor teljesül, ha $c_{R}(a)\ |\ d$. QED.

A ciklikus rend 1, ha az elem a résztestben van

Könnyen látható, hogy egy K véges test bármely a∈K elemére $o_{K}(a)=1$. Ez Lagrange tételéből következik, ti. a-nak a test multiplikatív csoportjabeli rendje osztója a csoport elemszámának; azaz $|K|-1=o(a)q\ \ (q\in \mathbb {Z} )$, és mivel a rend többszörösei 1-et adó kitevők, ezért $a^{K-1}=$ $a^{o(a)q}=$ $1\in K$; emiatt valóban $a^{|K|^{1}}=$ $a^{|K|}=$ $a^{\left(|K|-1\right)+1}=$ $a^{o(a)q+1}=$ $a^{o(a)q}a^{1}=$ $\left(a^{o(a)}\right)^{q}a=$ $1^{q}a=$ $a$. Tehát $j=1$ már megfelel a rend definíciójában előírt tulajdonságnak, és ez a lehető legkisebb ilyen pozitív egész, tehát éppen ez a rend.

Valójában a fenti észrevétel is csak egy speciális esete egy általánosabb
Tételnek: az a ciklikus rendje az R résztestre vonatkozóan akkor és csak akkor 1, ha a eleme az R résztestnek. Azaz ha $R\leq K$ véges testek és $a\in K$;

$c_{R}(a)=1\Leftrightarrow a\in R$

• Minthogy a∈R miatt a csoportelméletben ismert Lagrange tételéből következően $o_{R^{*}}(a):=o(a)\ |\ \left|R^{*}\right|=|R|-1$, tehát a-nak a test multiplikatív csoportjabeli rendje osztója a csoport elemszámának (ezt következik a Lagrange-tételből), így tehát $|R|-1=o(a)q\ \ (q\in \mathbb {Z} )$, és mivel a rend többszörösei 1-et adó kitevők, ezért $a^{R-1}=a^{o(a)q}=1\in R$. Ezért érvényes bármely $j\in \mathbb {N} ^{+}$ számra, a binomiális tételt is felhasználva, $a^{|R|^{j}}$ $=$ $a^{\left(|R|-1+1\right)^{j}}$ $=$ $a^{\left(o(a)q+1\right)^{j}}$ $=$ $a^{\sum _{k=0}^{j}{j \choose k}\left(o(a)q\right)^{j-k}}$ $=$ $a^{{j \choose 0}\left(o(a)q\right)^{j}+{j \choose 1}\left(o(a)q\right)^{j-1}+\cdots +{j \choose j-1}\left(o(a)q\right)^{1}+{j \choose j}\left(o(a)q\right)^{0}}$ $=$ $a^{{j \choose 0}\left(o(a)q\right)^{j}}\cdot a^{{j \choose 1}\left(o(a)q\right)^{j-1}}\cdot a^{{j \choose j-1}\left(o(a)q\right)^{1}}\cdot a^{{j \choose j}\left(o(a)q\right)^{0}}$ $=$ $\left(a^{o(a)^{j}}\right)^{{j \choose 0}q^{j}}\cdot \left(a^{o(a)^{j-1}}\right)^{{j \choose 1}q^{j-1}}\cdot \left(a^{o(a)^{1}}\right)^{{j \choose j-1}q^{1}}\cdot \left(a^{o(a)^{0}}\right)^{{j \choose j}q^{0}}$ $=$ $\left(1\right)^{{j \choose 0}q^{j}}\cdot \left(1\right)^{{j \choose 1}q^{j-1}}\cdot \left(1\right)^{{j \choose j-1}q^{1}}\cdot \left(a^{1}\right)^{{j \choose j}q^{0}}$ $=$ $\left(a\right)^{1\cdot 1}$ $=$ $a\in K$. Indukcióval bizonyítható, hogy az a elemet a rendjének valamely pozitív egész kitevőjű hatványára emelve, az egységelemet kell kapjuk. Ezt indukció nélkül úgy láthatjuk be, hogy „az egységelemet adó kitevők a rend többszörösei”, tehát ha olyan kitevőre emelünk, amely pozitív kitevőjű hatványa a rendnek, akkor e kitevő többszöröse is a rendnek, csak önmagával van többszörözve, tehát szintén az egységelem a hatvány értéke. Ezzel pedig beláttuk, hogy tetszőleges $j\in \mathbb {N} ^{+}$ számra $a^{|R|^{j}}=a$, ez tehát $j=1$ -re is teljesül, ez a legkisebb ilyen pozitív szám, tehát ez a ciklikus rend.
• A fent belátott állítás megfordítása valamivel komolyabb eszközöket igényel.
  • Be lehet látni, hogy bármely R≤K résztestre bármely a∈K-ra $a\in R\Leftrightarrow a^{|R|}=a$. Ugyanis belátható (például a Lagrange-féle interpolációs tétel segítségével), hogy bármely R testre $x^{|R|}-x=\prod _{u\in R}\left(x-u\right)$, tehát bármely x∈R elem gyöke az f = f_R[x] = x^|R|-x polinomnak. Mármost ezért ekkor a∈R esetén nyilván a^|R|-x = 0; de fordítva is, ha a o^|R|(a) = 1, azaz a^|R| = 1; akkor tehát gyöke f-nek. De ha ekkor nem lenne R-beli, akkor az f-nek van |R| darab gyöke és lenne még egy gyöke ezeken kívül, így f foka |R|+1 lenne, ami lehetetlen, hiszen |R|-edfokú.
  • Ha pedig az a ciklikus rendje 1, az épp azt jelenti, hogy a fenti dolog teljesül, azaz $c_{R}(a)=1\Rightarrow a^{|R|^{1}}=a^{|R|}=a\Rightarrow a\in R$, egyébként fordított irányú nyilakat is írhatunk, mivel „visszafelé” is igaz mindez; azaz így az is igazolható, amit a binomiális tétel segítségével fáradságosan kiszámoltunk.

Alkalmazások

Polinomok felbonthatósága/felbonthatatlansága

A ciklikus rend fogalma rendkívül fontos a véges testek feletti polinomok felbonthatóságának (irreducibilitás) vizsgálatában. Megmutatható, hogy ha K|R véges testek, és f∈K[x] egy K feletti polinom, akkor ennek bármely a∈K gyökére (ha f(a)=0) érvényes c_R(a)≤dg(f); azaz polinom gyökének ciklikus rendje legfeljebb akkora, mint a polinom foka. A dologban az az érdekes, hogy ha f irreducibilis (sőt csakis akkor ha irreducibilis), dg(f)≤c_R(a) is teljesül, vagyis R feletti irreducibilis polinom bármely K-beli gyökének ciklikus rendje pontosan a polinom fokszáma. Ennek az állításnak sok következménye van, például hogy irreducibilis polinom gyökei valamely bővítésben legfeljebb egyszeres gyökök (ez végtelen testekre nem igaz).

• Tétel: Ha f∈K[x] a K test feletti polinom, melynek a∈K gyöke, azaz f(a)=0; akkor c_K(a)≤dg(f); vagyis egy test feletti polinom gyökének ciklikus rendje kisebb, mint a polinom foka.
  • Legyen röviden c_K(a)=c∈ℕ⁺. Fentebb beláttuk, hogy ha f(a)=0, akkor a $C:=$ $C_{K}\left(a\right):=$ $:=\left\{a^{|K|^{j}}\ |\ j\in \mathbb {N} ^{+}\right\}$ ⊆ K\{0} halmaz épp c db. nem nulla elemet tartalmaz. Megmutatható, hogy minden elem gyöke f-nek. Ebből már következik c≤df(f), hisz egy polinomnak legfeljebb annyi gyöke lehet, amennyi a fokszáma.

Kapcsolódó szócikkek

• rend

Források

• Gonda János: Véges testek (egyetemi jegyzet, pdf).