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

At least 19 years old · documented by 2006

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A proposed example claims to disprove the conjecture, but nobody has independently checked it, so the question is not settled.

The conjecture says that every complete $\Phi_{\kappa}$ -sequence over $\mathbb{F}_p$ must be geometric, of the form $a_n=b^n$ for a primitive root satisfying $b^{\kappa}=b+1$ . The source paper presents this as a conjecture suggested by numerical data and does not prove it in general.

Known results

$\kappa=2$ : Brison proved the asserted classification.
$\kappa=3$ : proved when $X^3-X-1$ has fewer than three roots in $\mathbb{F}_p$ .
$\kappa=3$ : proved in the three-root case under $p\leq N_p^2+1$ ; the four computational exceptions below $10^5$ were checked individually.
Related cases include $\kappa=p-2$ , $\kappa=p-3$ , $\kappa=(p-1)/2$ , and $\kappa=(p+1)/2$ under corresponding hypotheses.

Posted attempt

A proposed counterexample takes $p=73$ , $\kappa=19$ , and $a_n=3\cdot13^n-2\cdot59^n$ . It claims that the recurrence holds, the sequence has period $72$ and covers all nonzero elements of $\mathbb{F}_{73}$ , while $a_1^2\ne a_2$ , disproving the geometric classification. The calculation is an unverified complete counterexample.

Current status (as of August 2026): The general conjecture has established special cases, while the proposed $p=73$ , $\kappa=19$ counterexample remains unverified; no general proof or independently confirmed counterexample is recorded.

Sources

ar5iv.labs.arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

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.