The distribution of residues in a sequence satisfying a linear recursion relation. (Q572057)

Es sei die Folge \(w_n\) eine Lösung der Rekursionsgleichung \[ \varOmega_{n+3} = P\varOmega_{n+2} - Q\varOmega_{n+1} + R\varOmega_n \qquad (R \neq 0) \] mit ganzen Zahlen \(P, Q, R\) und den ganzzahligen Anfangswerten \(w_0, w_1, w_2\); ist \(m\) eine beliebige natürliche Zahl, so geht die Folge \(w_n\) mod \(m\) in eine neue Folge \(A_n\) über: \[ w_n \equiv A_n \;(\text{mod } m) \qquad (0 \leqq A_n \leqq m-1), \] die als die \(w_n\) entsprechende mod \(m\) reduzierte Folge bezeichnet wird. Die Folge \(A_n\) ist periodisch; die kleinste Periodenzahl heißt die charakteristische Zahl der Folge \(w_n\) mod \(m\) und werde mit \(\tau\) bezeichnet. Es tritt hier das folgende Problem auf: Sind \(P, Q, R\), \(w_0, w_1, w_2, m, \tau\) vorgegeben, so ist die Verteilung der Reste nach \(m\) in irgendeiner Periode der Folge \(A_n\) zu untersuchen. Verf. beschäftigt sich mit einer diesem Problem entnommenen speziellen Frage: Es ist, falls \(m\) eine Primzahl \(p\) und die charakteristische Funktion \[ F(x) = x^3- Px^2 + Qx - R \] mod \(p\) irreduzibel ist, zu untersuchen, wievielmal ein beliebiger Rest mod \(p\) in einer Periode der Folge \(A_n\) auftritt. Es bedeute \(k(\nu)\) die Zahl, die angibt, wie oft der Rest \(\nu\) (\(0 \leqq \nu \leqq p-1\)) in der Reihe der ersten \(\tau\) Glieder \(A_0, A_1, \dots, A_{\tau -1}\) auftritt. \(k(\nu)\) heißt die Verteilungsfunktion. Da die Folge \(A_n\) durch die Angabe der ersten drei Werte vollkommen bestimmt ist, ist ohne weiteres klar, daß durch irgend drei aufeinanderfolgende Elemente (eine Triade) eines Zyklus die Verteilung der Reste mod \(p\) schon festgelegt ist. Daher stimmen zwei Zyklen mit verschiedenem Anfang dann überein, wenn sie eine Triade gemeinsam haben. Es kommt also im wesentlichen die Untersuchung auf die Frage hinaus, ob eine Triade in einem festen Zyklus vorkommt. Die Anzahlen der Nullen in verschiedenen Zyklen sind nicht unabhängig voneinander, sondern genügen gewissen diophantischen Gleichungen; diese lassen sich im Falle \(\tau = \frac 13 (p^2 + p +1)\) \ \((p = 3N +1)\) \ lösen. Hier kann also \(k(0)\) genau bestimmt werden. Für einen beliebigen Rest gelten die folgenden Resultate: Bei \(\tau \, | \, p^2 + p + 1\) erscheint jeder Rest in jedem Zyklus wenigstens einmal. Ferner kann das Verteilungsproblem auf das spezielle Problem des Falles \(\tau \, | \, p^2 + p + 1\) und \((\tau, 3) = 1\) zurückgeführt werden. Hier ist die Verteilungsfunktion genau bestimmt, wenn die Reste von \(k(n)\) mod \(p\) und mod 3 bekannt sind. Die Reste mod \(p\) können zwar bestimmt werden; aber die Bestimmung der Reste mod 3 macht bedeutende Schwierigkeiten. Zum Schluß wird noch eine Abschätzung der Verteilungsfunktion nach oben behandelt.