The arithmetical theory of linear recurring series. (Q5924894)

\((u)\) bezeichne eine arithmetische Folge \[ u_0,u_1,\ldots,u_n,\ldots \] der Ordnung \(k\), die der Rekursionsgleichung \[ x_{n+k} = c_1 x_{n+k-1} + c_2 x_{n+k-2} + \ldots + c_k x_n \tag{1} \] mit ganzen rationalen Koeffizienten \(c_1,c_2,\ldots,c_k\) genügt; die Anfangswerte \(u_0,u_1,\ldots,u_{k-1}\) von \((u)\) sind feste vorgegebene ganze Werte. Ist \(m\) eine beliebige ganze Zahl, so wird \((u)\) mod \(m\) eine Folge \((a)\) zugeordnet, die aus den kleinsten positiven Resten \(a_n\) der Zahlen \(u_n \mod {m}\) besteht. Die Folge \((a)\) wiederholt sich nach einer endlichen Anzahl von Anfangsgliedern periodisch. Die Periodenzahlen sind Vielfache der kleinsten unter ihnen, der charakteristischenZahl \(\mu \) von \((u) \mod {m}\); die Anzahl der sich nicht wiederholenden Anfangsglieder, \(\lambda \), heißt numerus (``numeric'') der Folge \((u) \mod {m}\). Bei \(\lambda = 0\) heißt \((u)\) rein periodisch. Besteht der periodische Teil von \((a)\) nur aus der Zahl \(0\), so heiße \((u)\) Nullfolge \(\mod {m}\). Im folgenden auftretende Folgen sollen, wenn nicht andres vermerkt wird, stets (1) genügen. Ferner bezeichne man mit \(F(x)\) das charakteristische Polynoim von (1) \[ F(x) = x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c_k \tag{2} \] und nenne erzeugendes Polynom von (1) \[ U(x) = u_0 x^{k-1} + (u_1 - c_1 u_0)x^{k-2} + (u_2 - c_1 u_1 - c_2 u_0)x^{k-3}\tag{3} \] \[ +\ldots + (u_{k-1} - c_1 u_{k-2} - \ldots - c_{k-1} u_0). \] Die Folge \((u)\) ist durch \(U(x)\) eindeutig bestimmt. Schließlich bezeichne man mit \(\Delta (u)\) die Determinante \[ \Delta (u) = \begin{vmatrix} u_0 & u_1 & \ldots & u_{k-1} \\ u_1 & u_2 & \ldots & u_k \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \\\cdot & \cdot & \cdot \\ u_{k-1} & u_k & \ldots & u_{2k-1} \end{vmatrix} ; \tag{4} \] \((-1)^k \Delta (u)\) ist die Resultante der Polynome \(F(x)\) und \(U(x)\). Das Problem, mit dem sich Verf. beschäftigt, ist die Bestimmung der Zahlen \(\lambda \) und \(\mu \) unter verschiedenen Gesichtspunkten, für eine bestimmte Folge \((u)\) oder für gewisse Klassen solcher Folgen. Ist \(\pi \) eine Periodenzahl \(\mod {m}\) aller Folgen \((u)\), die (1) genügen, so heiße sie allgemeine Periode von (1); die kleinste Zahl \((\tau )\) unter den \(\pi \) Hauptperiode. Es ist dann die charakteristische Zahl \(\mu \) irgendeiner Folge \((u)\) ein Teiler von \(\tau \). Es gibt dabei stets Folgen \((u)\), die \(\tau \) charakteristischen Zahl haben; diese Eigenschaft besitzen nämlich alle Folgen \((u)\), für die \((\Delta (u),m) = 1\) ist. Die Grundlage der Untersuchungen des Verf. bildet die Tatsache, daß die Folgen \((u) \mod {m}\) einen Ring bilden, der dem Restklassering aller Polynome mit ganzen rationalen Koeffizienten nach dem Doppelmodul \(m\) und \(F(x)\) einstufig isomorph ist. Unter \((u) + (v)\) verstehe man die Folge \[ (u + v) = u_0 + v_0,u_1 + v_1,\ldots,\;u_n + v_n,\;\ldots, \] die mit \((u)\) und \((v)\) der Gleichung (1) genügt. Daher bilden die Folgen \((u)\) eine unendliche abelsche Gruppe, \(\mod {m}\) eine endliche abelsche Gruppe \(\mathfrak {A}\). Diese ist das direkte Produkt der Gruppe \(\mathfrak {N}\) der Nullfolgen und der Gruppe \(\mathfrak {P}\) der reinperiodischen Folgen. Dafür, daß eine \((u)\)-Folge Nullfolge oder reinperiodisch ist, bestehen folgende Kriterien: \((u)\) ist Nullfolge mit einem numerus \(\leqq n\) dann und nur dann, wenn \[ x^n U(x) \equiv 0\;(\text{modd } m,F(x));\tag{5} \] \((u)\) ist reinperiodisch mit der Periode \(n\) dann und nur dann, wenn \[ (x^n - 1) U(x) \equiv 0\;(\text{modd } m,F(x)). \tag{6} \] Damit ist sofort für Nullfolgen der numerus als der kleinste Wert \(n\) bestimmt, für den (5) gilt; ebenso ist \(\mu \) für eine reinperiodische Folge der kleinste Wert \(n\), für den (6) erfülltist. Hieraus folgt weiter, daß \(\tau \) der kleinste Wert \(n\) ist, für den \[ x^n \equiv 1\;(\text{modd } m,F(x)). \] Sind \((a)\) und \((b)\) zwei \(\mod {m}\) reduzierte Folgen mit den \(\mod {m}\) reduzierten erzeugenden Polynomen \(L(x)\)und \(M(x)\), so verstehe man unter \((a)\cdot (b)\) die Folge \((c)\), die der Klasse von \((u)\)-Folgen entspricht, deren \(U(x)\) der Kongruenz genügt: \[ U(x) \equiv L(x)M(x)\;(\text{modd }m,F(x)). \] Damit ist der Isomorphismus zwischen dem Ring \(\mathfrak {A}\) und dem Ring \(\mathfrak {R}\) der \(\text{modd }m\) und \(f(x)\) reduzierten Polynome hergestellt. Der Folge \((a)\) ist das Polynom \[ L(x) = l_0 x^{k-1} + l_1 x^{k-2} + \ldots + l_{k-1} \] zugeordnet, wobei \[ l_\varkappa \equiv a_\varkappa - c_1 a_{\varkappa -1} - c_2 a_{\varkappa -2} - \ldots - c_\varkappa a_0\pmod {m}\quad (\varkappa = 0,\ldots,k,-1). \] Den Einheiten des Ringes \(\mathfrak {R}\) entspricht die \((a)\)-Folge, deren charakteristische Zahl \(\mu \) die Hauptperiode \(\tau \) von (1) \(\mod {m}\) ist, dem Element \(1\) von \(\mathfrak {R}\) insbesondere die Folge \((w)\) mit den Anfangswerten \(0,0,\ldots,0,1\). Die Zerlegung des Moduls \(m\) seine Primfaktoren \[ m = p_1^{n_1} p_2^{n_2} \ldots p_r^{n_r} \] bringt wesentliche Vereinfachungen; denn die charakteristische Zahl einer Folge \(\mod {m}\) ist das kleinste gemeinschaftliche Vielfache der charakteristischen Zahlen modulis \(p_\varrho ^{n_\varrho } (\varrho =1,2,\ldots,r)\), der numerus \(\mod {m}\) das Maximum der numeri modulis \(p_\varrho ^{n_\varrho }\). Aus diesem Grunde kann man sich für die weiteren Untersuchungen auf den Fall beschränken, daß \(m\) eine Primzahlpotenz \(p^N\) ist. Für \(F(x)\) gelte die Zerlegung \[ F(x) \equiv (\varphi _1(x))^{t_1} (\varphi _2(x))^{t_2} \ldots (\varphi _x(x))^{t_s}\pmod {p} \] in irreduzible Polynome \(\varphi (x)\), deren höchster Koeffizient \(1\) ist; dann läßt sich \(F(x) \mod {p^N}\) in der Form \[ F(x) \equiv F_1(x)F_2(x) \ldots F_s(x) \pmod {p^N} \tag{7} \] schreiben, wobei \[ F_\sigma (x) \equiv \left (\varphi _\sigma (x)\right )^{t_\sigma }\pmod {p} \quad (\sigma = 1,2,\ldots,s). \] (7) werde als die \textit{Schönemann}-Zerlegung von \(F(x) \mod {p^N}\) bezeichnet. Wird dann \[ U(x) \equiv U_\sigma (x)\;(\text{modd } p^N,\;F_\sigma (x)) \] gesetzt und \(U_\sigma \) als erzeugendes Polynom einer Folge \((u^{(\sigma )})\) aufgefaßt, deren charakteristisches Polynom \(F_\sigma (x)\) ist, so ist die charakteristische Zahl \(\mu \) der Folge \((u)\^^M(\text{modd }p^N,F(x))\) das kleinste gemeinschaftliche Vielfache der charakteristischen Zahlen der Folgen \((u^{(\sigma )})\) \((\text{modd }p^N,F_\sigma (x))\) und der numerus von \((u)\) das Maximum der numeri der Folgen \((u^{(\sigma )})\). Aus diesen Untersuchungen geht nun als wesentliches Ergebnis hervor: Sind die \textit{Schönemann}-Zerlegungen von \(F(x)\) und \(U(x)\) bekannt, so kann der numerus der Folge \((u)\) bestimmt werdenm unabhängig von der Berechnung der charakteristischen Zahl. Die Bestimmung dieser Zahlen macht weitaus größere Schwierigkeiten; der letzte Teil der Arbeit ist dieser Aufgabe für ungerade Primzahlen \(p\) gewidmet. Es würde hier zu weit führenm über diese Untersuchungen Genaueres zu sagen. Nur soviel sei noch gesagt, daß die charakteristische Zahl für Potenzen einer ungeraden Primzahl \(p\) unter folgenden Voraussetzungen bestimmt werden kann: Man kennt die \textit{Schönemann}-Zerlegungen von \(F(x)\) und \(U(x) \mod {p^N}\); man kennt der kleinsten Wert von \(n\), für den \[ x^n \equiv 1 \pmod {p,\varphi _\sigma (x)} \] und, falls \(\lambda \) dieser Wert ist, das Polynom \(L(x)\), das durch \[ x^\lambda - 1 \equiv pL(x)\;(\text{modd } p^2,\varphi _\sigma ^2(x)) \] bestimmt ist. Der Fall \(m = 2^N\) erfordert eine ausführlichere und besondere Behandlung, die Verf. an andrer Stelle geben will.