The classification conjecture for complete \Phi_{\kappa}-sequences

From papers

Let $p\geq 5$ be a prime number, and fix $\kappa\in\{2,\ldots,p-2\}$ . A $\Phi_{\kappa}$ -sequence $(a_n)_n$ in $\mathbb F_p$ is a sequence satisfying the recurrence associated with $\Phi_{\kappa}$ , and it is complete when its terms run through the nonzero elements of $\mathbb F_p$ in the intended complete sequence. A primitive root $b$ in $\mathbb F_p$ is a $\Phi_{\kappa}$ -primitive root if $b^{\kappa}=b+1$ .

Classification conjecture. A $\Phi_{\kappa}$ -sequence $(a_n)_n$ is complete if and only if

a_n=b^n

for all $n$ , where $b$ is a $\Phi_{\kappa}$ -primitive root.

The claim would classify all complete $\Phi_{\kappa}$ -sequences by primitive roots satisfying the defining relation. The paper presents it as suggested by numerical data; the supplied text gives no resolution, so its status remains open.

Progress summary

Partially solved

The conjecture remains open: only several special cases are known, and no general proof or verified counterexample has been found.

The conjecture asserts that every complete $\Phi_{\kappa}$ -sequence over $\mathbb{F}_p$ is geometric, namely $a_n=b^n$ for a primitive root satisfying $b^{\kappa}=b+1$ . The source presents this as a conjecture motivated by numerical data.

Known results

$\kappa=2$ : Brison proved that every complete sequence has the asserted form, with $b$ a Fibonacci primitive root.
$\kappa=3$ : the classification holds when $\varrho_p<3$ .
$\kappa=3$ : it holds when $\varrho_p=3$ and $p\leq N_p^2+1$ ; the finitely many computational exceptions below $10^5$ were checked individually.
Related cases for $\kappa=p-2$ , $\kappa=p-3$ , and $\kappa=(p-1)/2$ are treated under corresponding hypotheses.

Current status (as of August 2026): The general classification conjecture remains open, with only the cited special cases and computational checks established; no verified general proof or counterexample is recorded.

Sources

ar5iv.labs.arxiv.org

Sources & referencesView supporting material

Primary source

Juan B. Gil, Michael D. Weiner and Catalin Zara, “Complete Padovan sequences in finite fields”, arXiv:math/0605348 (2006).

1 week ago

The proposed characterization of complete $\Phi_\kappa$ -sequences is false. Take $p=73$ , $\kappa=19$ , and define, for every $n\in\mathbb Z$ ,

a_n=3\cdot13^n-2\cdot59^n\pmod {73}.

Since

13^{19}=14=13+1,\qquad 59^{19}=60=59+1\pmod {73},

we have

a_{n+19} =3\cdot13^n(13+1)-2\cdot59^n(59+1) =a_n+a_{n+1}.

Also $a_0=3-2=1$ , and Fermat's theorem gives $a_{n+72}=a_n$ .

To verify completeness, put

q=13\cdot59^{-1}=46\pmod {73}.

Then $q^2=-1$ , so $q$ has order $4$ . Moreover, $59$ has order $72$ , since

59^{36}=-1,\qquad 59^{24}=64\ne1\pmod {73}.

Therefore

H=\langle59^4\rangle\subset\mathbb F_{73}^{\times}

has order $18$ . For $n=4m+j$ , $0\le j\le3$ ,

a_{4m+j} =(59^4)^m\,59^j(3q^j-2).

The four coset representatives $t_j=59^j(3q^j-2)$ are

(t_0,t_1,t_2,t_3)=(1,67,42,34),

and their eighteenth powers are

(t_0^{18},t_1^{18},t_2^{18},t_3^{18})=(1,72,46,27).

These values are distinct. Since the kernel of $x\mapsto x^{18}$ on $\mathbb F_{73}^{\times}$ is precisely $H$ , the four sets $t_jH$ are the four distinct cosets of $H$ . Consequently

\{a_0,a_1,\ldots,a_{71}\}=\mathbb F_{73}^{\times}.

Thus the sequence is complete and has least period $72$ .

Finally,

a_1=67,\qquad a_2=42,\qquad a_1^2=67^2=36\ne42\pmod {73}.

Hence $a_n$ cannot equal $b^n$ for any $b\in\mathbb F_{73}$ , let alone a primitive root satisfying $b^{19}=b+1$ . Therefore a complete $\Phi_{19}$ -sequence need not arise from a primitive root.

0 endorsements

Shivam Patel · 1 day ago