15.JUNGTINIAI ELEMENTAI.MIOBIUSO FUNKCIJA

Žinodami, kad kiekvienas kūno GF (q^{n}) elementas yra neredukuojamo polinomo virš GF (q) šaknis (šis neredukuojamas polinomas yra polinomo x^{q^{n}} − x daliklis ir nebūtinai šio polinomo laipsnis yra n), pateiksime apibrėžima_{‘}.

11.10 apibrėžimas. Du elementai a, b ∈ GF (q^{n}) vadinami jungtiniais virš kūno GF (q), jeigu jie abu yra to paties neredukuojamo polinomo f(x) virš GF (q) šaknys.

11.11 pastabos. 1. Polinomas f(x) yra elementu_{‘} a ir b minimalusis polinomas.

2. Elemento a ∈ GF (q^{n}) jungtiniai elementai virš GF (q) yra

a, a^{q}, a^{g^{2}}, …, a^{q^{m−1}};

čia m – toks mažiausias teigiamas sveikas skaičius, kad a^{q^{m}} = a.

3. Kūno GF (q^{n}) primityviojo elemento a visi jungtiniai elementai virš kūno GF (q) taip pat yra primityvieji kūno GF (q^{n}) elementai.

11.12 pavyzdys. Tegu a ∈ GF (16) yra polinomo f(x) = x^{4}+x+1 ∈ GF (2) [x] šaknis. Elemento a jungtiniai elementai virš GF (2) yra

a, a^{2}, a^{4} = a + 1, a^{8} = a^{2} + 1.

Visi šie elementai yra primityvieji kūno GF (16) elementai (polinomas f(x) = x^{4} + x + 1 – neredukuojamas polinomas virš GF (2)).

Pasirėme_{‘} 11.11 pastaba, pateiksime būda_{‘} elemento a ∈ GF (q^{n}) minimaliajam polinomui virš GF (q) rasti.

11.13 teiginys. Elemento a ∈ GF (q^{n}) minimalusis polinomas virš GF (q) yra

g(x) = (x − a)(x − a^{q}) … (x − a^{q^{m−1}});

čia m – toks mažiausias teigiamas sveikas skaičius, kad a^{q^{m}} = a. Elementai a, a^{q}, …, a^{q^{m−1}} yra elemento a jungtiniai elementai, o polinomas g – minimalusis visu_{‘} šiu_{‘} elementu_{‘} polinomas virš kūno GF (q).

11.14 pavyzdys. Rasime visu_{‘} kūno GF (16) elementu_{‘} minimaliuosius polinomus virš GF (2). Iš 11.7 pavyzdžio žinome, kad neredukuojamo polinomo g(x) = x^{4} + x^{3} + 1 šaknis a generuoja multiplikacine_{‘} grupe_{‘} GF (16)^{∗}, t.y. bet kuris nenulinis kūno GF (16) elementas yra a laipsnis. Taip yra todėl, kad ord_{GF (16)^{∗}} = ord_{GF (2)}(g(x)) = 15.

Pradėsime nuo jungtiniu_{‘} elementu_{‘} klasiu_{‘} kūne GF (16) išskyrimo. Elemento a jungtiniai yra: a, a^{2}, a^{4}, a^{8} (a^{16} = a). Elemento a^{3} jungtiniai yra: a^{3}, a^{6}, a^{12}, a^{24} = a^{9} (a^{48} = a^{3}). Elemento a^{5} jungtiniai yra: a^{5}, a^{10} (a^{20} = a^{5}). Elemento a^{7} jungtiniai yra: a^{7}, a^{14}, a^{28} = a^{13}, a^{56} = a^{11} (a^{112} = a^{7}). Tegu m_{k}(x) yra elemento a^{k} minimalusis polinomas. Tada m_{0}(x) =

x + 1 ir

m_{1}(x) = m_{2}(x) = m_{4}(x) = m_{8}(x) = (x − a)(x − a^{2})(x − a^{4})(x − a^{8})
= (x^{2} − (a + a^{2})x + a^{3})(x^{2} − (a^{4} + a^{8})x + a^{12})
= (x^{2} − a^{13}x + a^{3})(x^{2} − a^{7}x + a^{12})

= x^{4} − (a^{7} + a^{13})x^{3} + (a^{3} + a^{12} + a^{20})x^{2} − (a^{25} + a^{10})x + a^{15}

= x^{4} + x^{3} + 1,

nes, atsižvelgiant i_{‘} 10.2 pavyzdžio lentele_{‘},

a + a^{2} = (0, 0, 1, 0) + (0, 1, 0, 0) = (0, 1, 1, 0) = a^{13},
a^{4} + a^{8} + (1, 0, 0, 1,) + (1, 1, 1, 0) = (0, 1, 1, 1) = a^{7},
a^{7} + a^{13} = (0, 1, 1, 1) + (0, 1, 1, 0) = (0, 0, 0, 1) = 1,
a^{3} + a^{12} + a^{20} = a^{+}a^{12} + a^{5} = (1, 0, 0, 0) + (0, 0, 1, 1) + (1, 0, 1, 1)
= (0, 0, 0, 0) = 0,
a^{25} + a^{10} = a^{10} + a^{10} = 2a^{10} = 0,
a^{15} = 1.

Be to,

m_{3}(x) = m_{6}(x) = m_{9}(x) = m_{12}(x) = (x − a^{3})(x − a^{6})(x − a^{9})(x − a^{12})

= (x − a^{3})(x − a^{12})(x^{6} − a^{6})(x − a^{9})

= (x^{2} − (a^{3} + a^{12}) + a^{15})(x^{2} − (a^{6} + a^{9}) + a^{15})

= (x^{2} − a^{5}x + 1)(x^{2} − a^{10}x + 1)

= x^{4} − (a^{6} + a^{10})x^{3} + (1 + 1 + a^{15})x^{2} − (a^{5} + a^{10}) + 1 = x^{4} + x^{3} + x^{2} + x + 1,

m_{5}(x) = m_{10}(x) = (x − a^{5})(x − a^{10}) = x^{2} − (a^{5} + a^{10})x + a^{15} = x^{2} + x + 1,

m_{7}(x) = m_{11}(x) = m_{13}(x) = m_{14}(x)
= (x − a^{7})(x − a^{11})(x − a^{13})(x − a^{14})
= (x^{2} − (a^{11} + a^{11})x + a^{18})(x^{2} − (a^{13} + a^{14})x + a^{27})
= (x^{2} + a^{10}x + a^{3})(x^{2} + a^{10}x + a^{12})

= x^{4} + (a^{10} + a^{10})x^{3} + (a^{3} + a^{12} + a^{20})x^{2} + (a^{22} + a^{13})x + a^{15}

= x^{4} + x + 1.

Pastebėsime, kad elemento a = 0 minimalusis polinomas yra x. Galime pateikti tikslia_{‘} fiksuoto laipsnio neredukuojamu_{‘} virš GF (q)

polinomu_{‘} kiekio formule_{‘}. Šiai formulei rasti pasitelksime viena_{‘} iš aritmetiniu_{‘} funkciju_{‘} – Miobiuso^{1} funkcija_{‘}.

11.15 apibrėžimas. Funkcija_{‘} μ : ℕ → ℤ, kurios reikšmės

μ(n) = \{ \begin{matrix}1, & kai n = 1, \\ (−1)^{k}, & kai skaičiaus n kanoninis skaidinys yra \\ & n = p_{1}p_{2} … p_{k}, p_{i} ≠ p_{j}, i ≠ j, \\ 0, & kai skaičius n dalijasi iš pirminio skaičiaus kvadrato, \end{matrix}

vadiname Miobiuso funkcija.

Suformuluosime pagrindines Miobiuso funkcijos savybes. 11.16 teiginys. 1 (Miobiuso funkcijos multiplikatyvumas). Tegu n, m ∈ ℕ ir DBD (n, m) = 1. Tada μ(m · n) = μ(m) · μ(n).

1 A.–F. Möbius, 1790–1868, – vokiečiu_{‘} matematikas.

2. Jeigu n ∈ ℕ, tai

∑_{d | n} μ (d) = \{ \begin{matrix}1, & kai n = 1, \\ 0, & kai n > 0, \end{matrix}

čia sumuojama pagal visus skaičiaus n daliklius d. 3 (Miobiuso apgre_{‘}žimo formulė). 3.1 (adityvusis variantas). Tegu h ir H yra funkcijos, apibrėžtos

natūraliesiems skaičiams su reikšmėmis adicinėje komutatyvioje grupėje A: h, H : ℕ → A.

Lygybė

H(n) = ∑_{d | n} h(d), visiems n ∈ ℕ  (∗)

teisinga tada ir tik tada, kai

h(n) = ∑_{d | n} μ(\frac{n}{d})H(d) = ∑_{d | n} μ(d) H(\frac{n}{d}), visiems n ∈ ℕ.  (∗∗)

3.2 (multiplikatyvusis variantas). Tegu h ir H yra funkcijos, apibrėžtos natūraliesiems skaičiams su reikšmėmis multiplikacinėje komutatyvioje grupėje B: h, H : ℕ → B.

Lygybė

H(n) = ∏_{d | n} h(d), visiems n ∈ ℕ

teisinga tada ir tik tada, kai

h(n) = ∏_{d | n} H(d)^{μ( \frac{n}{d})} = ∏_{d | n} H(\frac{n}{d})^{μ(d)}, visiems n ∈ ℕ.

Simbolis ∏_{d | n} yra multiplikacinis simbolio ∑_{d | n} variantas, reiškiantis,

kad dauginama pagal visus skaičiaus n daliklius d.

I_{‘} rodymas. 1. Miobiuso funkcijos multiplikatyvumas išplaukia iš funkcijos apibrėžimo.

2. Aišku, kai n = 1, tai lygybė teisinga. Kai n > 1 ir skaičiaus n kanoninis skaidinys yra n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{k}^{α_{k}}, tai

\begin{aligned}∑_{d | n} μ(d) & = μ(1) + ∑_{i=1}^{k} μ(p_{i}) + ∑_{1⩽i_{1}<i_{2}⩽k} μ(p_{i_{1}}p_{i_{2}}) + … + μ(p_{1}p_{2} … p_{k}) = \\ & = 1 + C_{k}^{1}(−1) + C_{k}^{2}(−1)^{2} + … + C_{k}^{k}(−1)^{n} = (1 + (−1))^{k} = 0. \end{aligned}

3.1. Tegu d_{1}, d_{2}, …, d_{s} yra visi skaičiaus n dalikliai. Kai teisinga (∗), tai

∑_{d | n} μ(\frac{n}{d}) H(d) = ∑_{d | n} μ(d) H(\frac{n}{d}) = ∑_{d | n} μ(d) ∑_{c | \frac{n}{d}} h(c)

= μ(d_{1}) ∑_{d_{i} | \frac{n}{d_{1}}} h(d_{i}) + … + μ(d_{s}) ∑_{d_{i} | \frac{n}{ds}} h(d_{i})

= h(d_{1}) ∑_{d_{i} | \frac{n}{d_{1}}} μ(d_{i}) + … + h(d_{s}) ∑_{d_{i} | \frac{n}{ds}} μ(d_{i})

= ∑_{c | n} h(c) ∑_{d | \frac{n}{c}} μ(d) = h(n).

Paskutinė lygybė teisinga, nes

∑_{d | \frac{n}{c}} μ(d) ≠ 0 ⟺ \frac{n}{c} = 1 ⟺ n = c.

Kai teisinga (∗∗), tai

∑_{d | n} h(d) = ∑_{d | n} ∑_{c | d} μ(c) H(\frac{d}{c}) = ∑_{d | n} ∑_{c | d} μ(\frac{d}{c})H(c)

= ∑_{c | d_{1}} μ(\frac{d_{1}}{c} ) H(c) + … + ∑_{c | d_{s}} μ(\frac{d_{s}}{c} ) H(c)

= ∑_{c | n} H(c) · ∑_{d_{i} | \frac{n}{c}} μ(d_{i}) = H(n).

3.2. I_{‘}rodymas analogiškas 3.1 i_{‘}rodymui.

△

Gri_{‘}žkime prie fiksuoto laipsnio neredukuojamu_{‘} polinomu_{‘} kiekio formulės.

11.17 teiginys. Bet kuriam natūraliajam skaičiui n ∈ ℕ visu_{‘} neredukuojamu_{‘} virš kūno GF (q) polinomu_{‘}, kuriu_{‘} laipsnis yra n daliklis, sandauga lygi f_{q^{n}}(x) = x^{q^{n}} − x.

I_{‘} rodymas. Iš 11.2 teiginio žinome, kad polinomo f_{q^{n}}(x) ∈ GF (q) [x] kanoniniame skaidinyje yra visi neredukuojami virš GF (q) polinomai, kuriu_{‘} laipsniai yra skaičiaus n dalikliai. Kita vertus,

f′_{q^{n}}(x) = q^{n} x^{q^{n}−1} − 1 = −1 ≠ 0,

t.y. polinomas f_{q^{n}}(x) neturi kartotiniu_{‘} šaknu_{‘}, ir todėl kiekvieno neredukuojamo polinomo f_{q^{n}}(x) kartotinumas polinomo kanoniniame skaidinyje yra lygus 1.

△

Neredukuojamu_{‘} virš kūno GF (q) d laipsnio polinomu_{‘} skaičiu_{‘} žymėsime N_{q}(d).

11.18 išvada. Su visais natūraliaisiais skaičiais n teisinga lygybė

q^{n} = ∑_{d | n} d N_{q}(d).

11.19 išvada. Teisinga formulė

N_{q}(n) = \frac{1}{n} ∑_{d | n} μ(\frac{n}{d})q^{d} = \frac{1}{n} ∑_{d | n} μ(d) q^{\frac{n}{d}} .

I_{‘} rodymas. Šiai formulei gauti reikia funkcijoms h, H : ℕ → ℤ, apibrėžtoms lygybėmis h(n) = n N_{q}(n) ir H(n) = q^{n}, pritaikyti adityvu_{‘}ji_{‘} Miobiuso apgre_{‘}žimo varianta_{‘}.

△

11.20 pavyzdys. 18-ojo laipsnio neredukuojamu_{‘} polinomu_{‘} virš kūno GF (q) skaičius yra

\begin{aligned}N_{q}(18) & = \frac{1}{18}(μ(1)q^{18} + μ(2)q^{9} + μ(3)q^{6} + μ(6)q^{3} + μ(9)q^{2} + μ(18)q) \\ & = \frac{1}{18}(q^{18} − q^{9} − q^{6} + q^{3}). \end{aligned}

4-ojo laipsnio neredukuojamu_{‘} polinomu_{‘} virš kūno GF (2) skaičius yra

N_{2}(4) = \frac{1}{4}(μ(1)2^{4} + μ(2)2^{2} + μ(4)2^{1}) = \frac{1}{4}(2^{4} − 2^{2}) = 3

(palyginkite su 11.7 pavyzdžio lentele).

Taikydami Miobiuso apgre_{‘}žimo formule_{‘}, galime rasti ne tik n-ojo laipsnio neredukuojamu_{‘} polinomu_{‘} virš GF (q) skaičiu_{‘}, bet ir šiu_{‘} polinomu_{‘} sandauga_{‘}, žymima_{‘} I(q, n, x).

11.21 išvada. Teisinga formulė

I(q, n, x) = ∏_{d | n} (x^{q^{d}} − x)^{μ( \frac{n}{d})} = ∏_{d | n} (x^{q^{\frac{n}{d}}} − x)^{μ(d)}.

I_{‘} rodymas. Remiantis 11.17 teiginiu,

x^{q^{n}} − x = ∏_{d | n} I(q, d, x).

Tegu funkcijos, apibrėžtos lygybėmis h(n) = I(q, n, x) ir H(n) = x^{q^{n}} − x, h, H : ℕ → B; čia B – multiplikacinė racionaliu_{‘}ju_{‘} funkciju_{‘} virš kūno GF (q) grupė (t.y. funkciju_{‘} f(x) = \frac{p_{1}(x)}{p_{2}(x)}; čia p_{1}(x) ir p_{2}(x) polinomai virš GF (q), p_{1}(x) p_{2}(x) ≠ 0). Pritaike_{‘} funkcijoms h ir H multiplikatyvia_{‘}ja_{‘} Miobiuso apgre_{‘}žimo formule_{‘}, gausime norima_{‘} formule_{‘}.

△

11.22 pavyzdys.

\begin{aligned}I(2, 4, x) & = (x^{16} − x)^{μ(1)}(x^{4} − x)^{μ(2)}(x^{2} − x)^{μ(4)} \\ & = \frac{x^{16} − x}{x^{4} − x} = \frac{x^{15} − 1}{x^{3} − 1} = x^{12} + x^{9} + x^{6} + x^{3} + 1. \end{aligned}