Dicksonův polynom - Dickson polynomial

v matematika, Dicksonovy polynomy, označeno $D n (X, α)$ , tvoří a polynomiální sekvence představil L. E. Dickson (1897 ). Byli znovuobjeveni Sládek (1961) ve své studii o Pivovarské částky a někdy byly, i když jen zřídka, označovány jako Pivovarské polynomy.

Přes komplexní čísla jsou Dicksonovy polynomy v podstatě ekvivalentní Čebyševovy polynomy se změnou proměnné a ve skutečnosti se Dicksonovy polynomy někdy nazývají Čebyševovy polynomy.

Dicksonovy polynomy jsou obecně studovány znovu konečná pole, kde někdy nemusí být ekvivalentní Čebyševovým polynomům. Jedním z hlavních důvodů zájmu o ně je důvod pro pevné $α$ , uvádějí mnoho příkladů permutační polynomy; polynomy působící jako obměny konečných polí.

Definice

První druh

Pro celé číslo $n > 0$ a $α$ v komutativní prsten $R$ s identitou (často se volí jako konečné pole $F q = GF (q)$ ) Dicksonovy polynomy (prvního druhu) přes $R$ jsou dány^[1]

{ displaystyle D_ {n} (x, alpha) = součet _ {i = 0} ^ { levý lfloor { frac {n} {2}} pravý rfloor} { frac {n} { ni}} { binom {ni} {i}} (- alpha) ^ {i} x ^ {n-2i} ,.}

Prvních pár Dicksonových polynomů je

{ displaystyle { begin {zarovnáno} D_ {1} (x, alpha) & = x D_ {2} (x, alpha) & = x ^ {2} -2 alpha D_ {3 } (x, alpha) & = x ^ {3} -3x alpha D_ {4} (x, alpha) & = x ^ {4} -4x ^ {2} alpha +2 alpha ^ {2} D_ {5} (x, alpha) & = x ^ {5} -5x ^ {3} alpha + 5x alpha ^ {2} ,. End {zarovnáno}}}

Mohou být také generovány relace opakování pro $n \geq 2$ ,

{ displaystyle D_ {n} (x, alpha) = xD_ {n-1} (x, alpha) - alpha D_ {n-2} (x, alpha) ,,}

s původními podmínkami $D 0 (X, α) = 2$ a $D 1 (X, α) = X$ .

Druhý druh

Dicksonovy polynomy druhého druhu, $E n (X, α)$ , jsou definovány

{ displaystyle E_ {n} (x, alpha) = součet _ {i = 0} ^ { levý lfloor { frac {n} {2}} pravý rfloor} { binom {ni} { i}} (- alpha) ^ {i} x ^ {n-2i}.}

Nebyly příliš studovány a mají podobné vlastnosti jako Dicksonovy polynomy prvního druhu. Prvních několik Dicksonových polynomů druhého druhu je

{ displaystyle { begin {aligned} E_ {0} (x, alpha) & = 1 E_ {1} (x, alpha) & = x E_ {2} (x, alpha) & = x ^ {2} - alpha E_ {3} (x, alpha) & = x ^ {3} -2x alpha E_ {4} (x, alpha) & = x ^ {4 } -3x ^ {2} alpha + alpha ^ {2} ,. End {zarovnáno}}}

Mohou být také generovány relací opakování pro $n \geq 2$ ,

{ displaystyle E_ {n} (x, alpha) = xE_ {n-1} (x, alpha) - alpha E_ {n-2} (x, alpha) ,,}

s původními podmínkami $E 0 (X, α) = 1$ a $E 1 (X, α) = X$ .

Vlastnosti

The $D n$ jsou jedinečné monické polynomy splňující funkční rovnici

{ displaystyle D_ {n} left (u + { frac { alpha} {u}}, alpha right) = u ^ {n} + left ({ frac { alpha} {u}} vpravo) ^ {n},}

kde $α \in F q$ a $u \neq 0 \in F q 2$ .^[2]

Také splňují pravidlo složení,^[2]

{ displaystyle D_ {mn} (x, alpha) = D_ {m} { bigl (} D_ {n} (x, alpha), alpha ^ {n} { bigr)} , = D_ { n} { bigl (} D_ {m} (x, alpha), alpha ^ {m} { bigr)} ,.}

The $E n$ také uspokojit funkční rovnici^[2]

{ displaystyle E_ {n} left (y + { frac { alpha} {y}}, alpha right) = { frac {y ^ {n + 1} - left ({ frac { alpha } {y}} vpravo) ^ {n + 1}} {y - { frac { alpha} {y}}}} ,,}

pro $y \neq 0$ , $y 2 \neq α$ , s $α \in F q$ a $y \in F q 2$ .

Dicksonův polynom $y = D n$ je řešením obyčejná diferenciální rovnice

{ displaystyle left (x ^ {2} -4 alpha right) y '' + xy'-n ^ {2} y = 0 ,,}

a Dicksonův polynom $y = E n$ je řešení diferenciální rovnice

{ displaystyle left (x ^ {2} -4 alpha right) y '' + 3xy'-n (n + 2) y = 0 ,.}

Jejich běžné generující funkce jsou

{ displaystyle { begin {zarovnáno} součet _ {n} D_ {n} (x, alpha) z ^ {n} & = { frac {2-xz} {1-xz + alpha z ^ {2 }}} součet _ {n} E_ {n} (x, alpha) z ^ {n} & = { frac {1} {1-xz + alpha z ^ {2}}} ,. end {zarovnáno}}}

Odkazy na jiné polynomy

Podle výše uvedeného relace rekurence jsou Dicksonovy polynomy Lucasovy sekvence. Konkrétně pro $α = -1$ , Dicksonovy polynomy prvního druhu jsou Fibonacci polynomy a Dicksonovy polynomy druhého druhu jsou Lucasovy polynomy.

Podle pravidla složení výše, když α je idempotentní, složení Dicksonových polynomů prvního druhu je komutativní.

Dicksonovy polynomy s parametrem $α = 0$ dát monomials.

${ displaystyle D_ {n} (x, 0) = x ^ {n} ,.}$

Dicksonovy polynomy s parametrem $α = 1$ souvisí s Čebyševovy polynomy $T n (X) = cos (n arccos X)$ prvního druhu od^[1]

${ displaystyle D_ {n} (2x, 1) = 2T_ {n} (x) ,.}$

Od Dicksonova polynomu $D n (X, α)$ lze definovat přes prsteny s dalšími idempotenty, $D n (X, α)$ často nesouvisí s Čebyševovým polynomem.

Permutační polynomy a Dicksonovy polynomy

A permutační polynom (pro dané konečné pole) je pole, které funguje jako permutace prvků konečného pole.

Dicksonův polynom $D n (X, α)$ (považováno za funkci $X$ s α fixní) je permutační polynom pro pole s $q$ prvky právě tehdy $n$ je coprime $q 2 - 1$ .^[3]

Smažené (1970) dokázal, že jakýkoli integrální polynom, který je permutačním polynomem pro nekonečně mnoho hlavních polí, je složením Dicksonových polynomů a lineárních polynomů (s racionálními koeficienty). Toto tvrzení se stalo známým jako Schurova domněnka, ačkoli ve skutečnosti Schur tuto domněnku nevytvořil. Vzhledem k tomu, že Friedův článek obsahoval řadu chyb, opravený účet byl dán uživatelem Turnwald (1995), a následně Müller (1997) poskytl jednodušší důkaz v duchu hádky kvůli Schurovi.

Dále, Müller (1997) dokázal, že jakýkoli permutační polynom nad konečným polem $F q$ jehož stupeň je současně coprime $q$ a méně než $q 1 / 4$ musí být složením Dicksonových polynomů a lineárních polynomů.

Zobecnění

Dicksonovy polynomy obou druhů nad konečnými poli lze považovat za počáteční členy posloupnosti zobecněných Dicksonových polynomů označovaných jako Dicksonovy polynomy $(k + 1)$ th druh.^[4] Konkrétně pro $α \neq 0 \in F q$ s $q = str E$ pro některé prime $str$ a všechna celá čísla $n \geq 0$ a $0 \leq k < str$ , $n$ Dicksonův polynom z $(k + 1)$ th druh přes $F q$ , označeno $D n, k (X, α)$ , je definováno^[5]

{ displaystyle D_ {0, k} (x, alpha) = 2-k}

a

{ displaystyle D_ {n, k} (x, alpha) = součet _ {i = 0} ^ { levý lfloor { frac {n} {2}} pravý rfloor} { frac {n -ki} {ni}} { binom {ni} {i}} (- alpha) ^ {i} x ^ {n-2i} ,.}

$D n,0 (X, α) = D n (X, α)$ a $D n,1 (X, α) = E n (X, α)$ , což ukazuje, že tato definice sjednocuje a zobecňuje původní polynomy Dicksona.

Významné vlastnosti Dicksonových polynomů také zobecňují:^[6]

Vztah opakování: Pro $n \geq 2$ ,

{ displaystyle D_ {n, k} (x, alpha) = xD_ {n-1, k} (x, alpha) - alpha D_ {n-2, k} (x, alpha) ,, }

s původními podmínkami

D 0, k (X, α) = 2 - k

a

D 1, k (X, α) = X

.

Funkční rovnice:

{ displaystyle D_ {n, k} left (y + alpha y ^ {- 1}, alpha right) = { frac {y ^ {2n} + k alpha y ^ {2n-2} + cdots + k alpha ^ {n-1} y ^ {2} + alpha ^ {n}} {y ^ {n}}} = { frac {y ^ {2n} + { alpha} ^ {n }} {y ^ {n}}} + left ({ frac {k alpha} {y ^ {n}}} right) { frac {y ^ {2n} - { alpha} ^ {n -1} y ^ {2}} {y ^ {2} - alpha}} ,,}

kde

y \neq 0

,

y 2 \neq α

.

Generující funkce:

{ displaystyle sum _ {n = 0} ^ { infty} D_ {n, k} (x, alpha) z ^ {n} = { frac {2-k + (k-1) xz} {1 -xz + alpha z ^ {2}}} ,.}

Poznámky

^ ^A ^b Lidl & Niederreiter 1983, str. 355
^ ^A ^b ^C Mullen & Panario 2013, str. 283
^ Lidl & Niederreitter 1983, str. 356
^ Wang, Q .; Yucas, J. L. (2012), „Dicksonovy polynomy nad konečnými poli“, Konečná pole a jejich aplikace, 18 (4): 814–831, doi:10.1016 / j.ffa.2012.02.001
^ Mullen & Panario 2013, str. 287
^ Mullen & Panario 2013, str. 288

Reference

Brewer, B. W. (1961), „O určitých částkách znaků“, Transakce Americké matematické společnosti, 99 (2): 241–245, doi:10.2307/1993392, ISSN 0002-9947, JSTOR 1993392, PAN 0120202, Zbl 0103.03205
Dickson, L. E. (1897). "Analytické znázornění substitucí na mocnině prvního počtu písmen s diskusí o lineární skupině I, II". Ann. matematiky. Annals of Mathematics. 11 (1/6): 65–120, 161–183. doi:10.2307/1967217. ISSN 0003-486X. JFM 28.0135.03. JSTOR 1967217.CS1 maint: ref = harv (odkaz)
Fried, Michael (1970). „O domněnce o Schurovi“. Michigan Math. J. 17: 41–55. doi:10,1307 / mmj / 1029000374. ISSN 0026-2285. PAN 0257033. Zbl 0169.37702.CS1 maint: ref = harv (odkaz)
Lidl, R .; Mullen, G. L .; Turnwald, G. (1993). Dicksonovy polynomy. Pitmanovy monografie a průzkumy v čisté a aplikované matematice. 65. Longman Scientific & Technical, Harlow; publikováno ve Spojených státech se společností John Wiley & Sons, Inc., New York. ISBN 978-0-582-09119-1. PAN 1237403. Zbl 0823.11070.CS1 maint: ref = harv (odkaz)
Lidl, Rudolf; Niederreiter, Harald (1983). Konečná pole. Encyklopedie matematiky a její aplikace. 20 (1. vyd.). Addison-Wesley. ISBN 978-0-201-13519-0. Zbl 0866.11069.
Mullen, Gary L. (2001) [1994], „Dicksonovy polynomy“, Encyclopedia of Mathematics, Stiskněte EMS
Mullen, Gary L .; Panario, Daniel (2013), Příručka konečných polí, CRC Press, ISBN 978-1-4398-7378-6
Müller, Peter (1997). „Weil-free free proof of Schur's dohad“. Konečná pole a jejich aplikace. 3: 25–32. doi:10.1006 / ffta.1996.0170. Zbl 0904.11040.CS1 maint: ref = harv (odkaz)
Rassias, Thermistocles M .; Srivastava, H.M .; Yanushauskas, A. (1991). Témata v polynomech jedné a několika proměnných a jejich aplikacích: Odkaz PL Chebysheva. World Scientific. 371–395. ISBN 978-981-02-0614-7.
Turnwald, Gerhard (1995). „O Schurově domněnce“. J. Austral. Matematika. Soc. Ser. A. 58 (3): 312–357. doi:10.1017 / S1446788700038349. PAN 1329867. Zbl 0834.11052.CS1 maint: ref = harv (odkaz)
Young, Paul Thomas (2002). „Na upravených Dicksonových polynomech“ (PDF). Fibonacci čtvrtletně. 40 (1): 33–40.

[LN355-1] A ^b Lidl & Niederreiter 1983, str. 355

[MP283-2] A ^b ^C Mullen & Panario 2013, str. 283

[LN356-3] Lidl & Niederreitter 1983, str. 356

[4] Wang, Q .; Yucas, J. L. (2012), „Dicksonovy polynomy nad konečnými poli“, Konečná pole a jejich aplikace, 18 (4): 814–831, doi:10.1016 / j.ffa.2012.02.001

[5] Mullen & Panario 2013, str. 287

[6] Mullen & Panario 2013, str. 288

[1]

[2]

[3]

[4]

[5]

[6]