Second order Recurrences, quadratic number fields and cyclic codes
Minjia Shi, Xuan Wang, Bouazzaoui Zakariae, Jon-Lark Kim, Patrick Solé · 2026
Read Second order Recurrences, quadratic number fields and cyclic codes by Minjia Shi, Xuan Wang, Bouazzaoui Zakariae, Jon-Lark Kim, Patrick Solé (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-25343.txt.
Introduction
Shi and co-authors link rare Fibonacci-type primes to the weights of cyclic codes. Their primes generalize Wall-Sun-Sun primes to second-order recurrences tied to quadratic fields. For such a prime, they study codes over two rings whose check polynomial mirrors the recurrence. The weight lists of those codes are the prize. Some codes come out MDS, the best possible spread, when the polynomial splits. Others land near that bar. The work ties a number theory curiosity to code design.
Catalog record
| CREATOR | Minjia Shi, Xuan Wang, Bouazzaoui Zakariae, Jon-Lark Kim, Patrick Solé |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39602 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.25343
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Second order Recurrences, quadratic number fields and cyclic codes Thanks: The work of Minjia Shi was supported in part by the National Natural Science Foundation of China under Grant 12471490. The work of Jon-Lark Kim was supported in part by the BK21 FOUR (Fostering Outstanding Universities for Research) funded by the Ministry of Education(MOE, Korea) and National Research Foundation of Korea(NRF) under Grant No. 4120240415042 and by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science and ICT under Grant No. RS-2025-24534992. Minjia Shi, Xuan Wang, Bouazzaoui Zakariae, Jon-Lark Kim, Patrick Solé Abstract . Wall-Sun-Sun primes (shortly WSS primes) are defined as those primes p p such that the period of the Fibonacci recurrence is the same modulo p p and modulo p 2 . p^{2}. This concept has been generalized recently to certain second order recurrences whose characteristic polynomials admit as a zero the principal unit of ℚ ( d ) , \mathbb{Q}(\sqrt{d}), for some integer d > 0 . d>0. Primes of the latter type we call W S S ( d ) . WSS(d). They correspond to the case when ℚ ( d ) \mathbb{Q}(\sqrt{d}) is not p p -rational. For such a prime p p we study the weight distributions of the cyclic codes over 𝔽 p \mathbb{F}_{p} and ℤ p 2 \mathbb{Z}_{p^{2}} whose check polynomial is the reciprocal of the said characteristic polynomial. Some of these codes are MDS (reducible case) or NMDS (irreducible case). Keywords: WSS primes, quadratic number fields, p -rational number fields, second order recurrences, cyclic codes, MDS codes, NMDS codes MSC (2020): 11B39, 11B50, 11R11, 94B15 1. Introduction The famous Fibonacci sequence is defined by the linear recurrence F_{n}=F_{n-1}+F_{n-2},\;n\geq 2, with initial conditions F_{0}=0,\,F_{1}=1. This is a periodic sequence modulo every positive integer m , its period \pi(m) is called the Pisano period. Formulas and properties of \pi(m) are well known since Wall’s paper in 1960 [ 30 ] . That paper renewed interest in the subject and motivated studies of Pisano periods, which were later related to other objects and generalized to other classes of second order recurrence sequences. A natural question was asked by Wall in his paper: Can there be a prime p such that \pi(p)=\pi(p^{2})? It is known that up to 10^{14} , there are no such primes (cf. [ 16 ] ). Still, using heuristics and probabilistic arguments, some authors conjecture the existence of infinitely many primes p satisfying \pi(p)=\pi(p^{2}) [ 7 , 11 ] . It was shown by the Sun brothers in [ 29 ] that the existence of these primes is related to Fermat’s Last Theorem, the reason why we call them Wall-Sun-Sun primes, or WSS primes for short. The question of Wall can naturally be asked for other types of second order recurrence sequences. In [ 2 , 3 ] , this was considered for generalized Fibonacci sequences of the form F_{n}=-AF_{n-1}-BF_{n-2},\;n\geq 2, whose characteristic polynomial is X^{2}+AX+B , with A,B\in\mathbb{Z} being associated with a given real quadratic field. The question of Wall for these sequences is related to certain deep arithmetic properties of real quadratic fields. More precisely, let d>0 be a fundamental discriminant and let \varepsilon_{d} be the fundamental unit of \mathbb{Q}(\sqrt{d}) . Then \varepsilon_{d}=\frac{a+b\sqrt{d}}{2} when (a,b) represent the smallest solution of the Pell equation x^{2}-dy^{2}=\pm 4 . The sequence in [ 2 , 3 ] is then given by F_{n+2}=aF_{n+1}-\frac{a^{2}-db^{2}}{4}F_{n}, where X^{2}-aX+\frac{a^{2}-db^{2}}{4} is the minimal polynomial of \varepsilon_{d} . Write k(m) for the period of this sequence modulo m>1 and say that a prime p is a WSS(d) prime if we have k(p^{2})=k(p) . Then for a large enough prime p , we have k(p^{2})=k(p) exactly when the quadratic field \mathbb{Q}(\sqrt{d}) is p -rational [ 2 , 3 ] (see Section 3 below for details about p -rational fields). In this setting, for the classical Fibonacci sequence, that is d=5 , there are no known WSS(5) primes. However, for other values d>5 , one can find many WSS(d) primes [ 2 , Table] . To allow more generality, we shall say that a prime is WSS(d)^{*} if the characteristic polynomial in a general form discussed above has discriminant d up to square factors, but not necessarily \varepsilon_{d} as a zero. With every second order recurrence, can be attached a cyclic code of dimension two, whose codewords are the period window of the sequence when the initial conditions vary. The weight distribution of cyclic codes of dimension two is studied over finite fields in [ 25 , 26 , 27 ] and over rings in [ 23 , 24 ] . The methods in [ 23 , 24 , 25 ] are based on a local Binet-like formula; while the technique in [ 26 , 27 ] is a more classical coding theoretic approach. Their salient property is that they are one-weight code or two-weight codes, a fact which ties them up with strongly regular graphs in the projective case [ 4 ] . Some of our codes are MDS (reducible case) or near MDS (shortly NMDS) (irreducible case). NMDS codes is an important class of codes introduced in [ 6 ] that resembles MDS codes. For some primes p, we construct in Proposition 5, NMDS [2p+2,2,2p] codes, that are optimal for the length. The material is organized as follows. The next section contains prerequisite notions. Section 3 develops the connection between WSS primes and quadratic number fields. Section 4 shows that, given a prime p>0 , there is an infinitude of integers d>0 such that p is WSS(d)^{*}. Section 5 considers the cyclic codes over \mathbb{F}_{p} and \mathbb{Z}_{p^{2}} of length the common period when p is WSS(d). Section 6 concludes the article. 2. Preliminary 2.1. Codes We assume that the reader has some basic familiarity with Coding Theory as can be gained from the first chapter of [ 14 ] or [ 9 ] . The Hamming weight of a vector \boldsymbol{u} over a finite field F and of length n is the number of all nonzero coordinates of \boldsymbol{u} , denoted by \wt(\boldsymbol{u}) . A code of length n over a finite field F is a vector subspace of F^{n}. Its elements are called codewords . Its dimension is denoted by \kappa, and its minimum weight or minimum distance by d. The three parameters are written compactly as [n,\kappa,d] or [n,\kappa,d]_{q} if F=\mathbb{F}_{q} , the finite field of order q, where q=p^{r} ( p a prime and r\geq 1 ). An [n,\kappa,n-\kappa+1] is called MDS . An [n,\kappa,n-\kappa] is called almost-MDS, simply AMDS and near-MDS, simply NMDS if its dual is also AMDS. A generator matrix G of the code is any \kappa by n matrix whose rows span the code. A code is projective if any pair of columns of G is linearly independent. A code is two weight if it has only two nonzero weights w_{1},\,w_{2} with w_{1}<w_{2} . This is denoted by [n,k,\{w_{1},\,w_{2}\}]. It was shown by Delsarte that if the code is projective then w_{2}-w_{1} is a power of the charcteristic p of F. If m>1 is the largest factor of w_{2}-w_{1} that is coprime to p , then by [