Rank Distribution and Dynamics of Gram Matrices from Binary m-Sequences with Applications to LCD Codes
Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou · 2026
Read Rank Distribution and Dynamics of Gram Matrices from Binary m-Sequences with Applications to LCD Codes by Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou (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-2604-26387.txt.
Introduction
Liu and three colleagues mapped the rank distribution of Gram matrices built from binary m-sequences, sequences prized for balance, run, and autocorrelation properties. For each window length, they formed Gram matrices from consecutive subsequences and derived an explicit rank formula for all lengths. Full rank holds for about half the admissible lengths, deficient ranks never persist to the next length, and full rank persists over stretches. The results also settle the hull distribution of punctured cyclic simplex codes.
Catalog record
| CREATOR | Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70716 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26387
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rank Distribution and Dynamics of Gram Matrices from Binary m-Sequences with Applications to LCD Codes Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou Abstract The Gram matrix is a classical object formed from the pairwise inner products of a collection of vectors, with fundamental roles in functional analysis, statistics, combinatorics, and coding theory. In the realm of sequence design, maximum-length sequences (m-sequences) are among the most fundamental classes of sequences, traditionally characterized by their span, decimation, shift-and-add, balance, run, and ideal autocorrelation properties. In this paper, we bridge the two foundational concepts by uncovering novel structural features of m-sequences through the lens of a family of Gram matrices. Specifically, for each 1 ≤ t ≤ 2 n − 1 1\leq t\leq 2^{n}-1 , we extract n n consecutive subsequences of length t t from an m-sequence of period 2 n − 1 2^{n}-1 , construct their corresponding n × n n\times n Gram matrix, and investigate its rank, denoted by r n ( t ) r_{n}(t) . Utilizing semilinear representation of Galois groups and Bézoutian of polynomials, we derive an explicit formula for r n ( t ) r_{n}(t) for all t t , thereby establishing the complete rank distribution of these Gram matrices. Notably, we prove that full rank is attained for approximately half of the admissible values of t t . We further uncover the intricate dynamics of r n ( t ) r_{n}(t) : rank-deficient states are strictly unstable (i.e., r n ( t ) < n r_{n}(t)<n implies r n ( t + 1 ) ≠ r n ( t ) r_{n}(t+1)\neq r_{n}(t) ), whereas the full-rank state exhibits strong persistence, remaining at n n over a nontrivial interval of consecutive values of t t . Altogether, our results fully characterize both the global rank distribution and the local dynamics of rank function, as invariant of m-sequences. As an application, our findings completely determine the hull distribution of the family of punctured cyclic simplex codes. keywords m -sequence, sequence design, coding theory, Gram matrix, rank distribution, LCD code MSC 94A55, 94B05, 94B15, 11T71 1 Introduction Binary m-sequences form a distinguished class of periodic sequences generated by linear feedback shift registers (LFSRs). Their systematic study goes back to the pioneering work of Solomon Golomb in the 1960s, whose book Shift Register Sequences [ 19 ] established much of the basic theory of shift register sequences. Let \mathbb{F}_{2} be the binary field. An n -stage linear feedback shift register (LFSR) generates a binary periodic sequence \{s_{t}\}_{t=0}^{\infty} satisfying s_{t+n}=c_{n-1}s_{t+n-1}+\dots+c_{1}s_{t+1}+c_{0}s_{t}, (1) where c_{0},\dots,c_{n-1}\in\mathbb{F}_{2} . Such an LFSR sequence is determined by its initial state (s_{0},s_{1},\dots,s_{n-1})\in\mathbb{F}_{2}^{n} and its characteristic polynomial f(x)=x^{n}+c_{n-1}x^{n-1}+\dots+c_{1}x+c_{0}\in\mathbb{F}_{2}[x]. When f(x) is a primitive polynomial of degree n , the resulting sequence has the maximum possible period 2^{n}-1 and is called a binary maximum-length sequence , or simply a binary m-sequence of order n . The following figure illustrates an LFSR that generates an m-sequence. R_{4} R_{3} R_{2} R_{1} R_{0} s_{t+4} s_{t+3} s_{t+2} s_{t+1} s_{t} Output \{s_{t}\} s_{t+5} Figure 1: A 5 -stage linear feedback shift register with f(x)=x^{5}+x^{2}+1 . Over the past five decades, m-sequences have served as indispensable building blocks in digital communications, radar synchronization, and modern cryptography [ 25 ] . Beyond these applications, their rich algebraic and combinatorial structures are closely related to some fundamental topics in other disciplines, including cryptography [ 10 , 12 , 47 , 50 ] , coding theory [ 14 , 16 , 31 , 49 ] , number theory [ 22 ] , finite geometry [ 18 ] , and combinatorial [ 48 ] . Golomb [ 19 ] characterized several remarkable properties of m-sequences, which we list below. 1. Span Property: Each nonzero n -tuple over \mathbb{F}_{2} occurs exactly once in one period of \{s_{t}\} . 2. Decimation Property: For any positive integer d coprime to 2^{n}-1 , the decimated sequence \{s_{dt}\} is also an m-sequence of period 2^{n}-1 . 3. Shift-and-Add Property: For any shift \tau\not\equiv 0\pmod{2^{n}-1} , the sequence \{s_{t}^{\prime}\} with s_{t}^{\prime}=s_{t+\tau}+s_{t} is also an m-sequence of period 2^{n}-1 . 4. Balance Property: In one period of \{s_{t}\} , the element 1 occurs exactly 2^{n-1} times, and the zero element occurs 2^{n-1}-1 times. 5. Run Property: In one period of \{s_{t}\} , exactly 1/2 of the runs have length 1 , 1/4 have length 2 , 1/8 have length 3 , 1/16 have length 4 , and so on, as long as these fractions give integral numbers of runs. Here, a run of length k is defined as a block s_{i}\dots s_{i+k-1} such that s_{i-1}\neq s_{i}=\dots=s_{i+k-1}\neq s_{i+k} . 6. Ideal Autocorrelation Property: The periodic autocorrelation function C_{s}(\tau) is given by C_{s}(\tau)=\sum_{t=0}^{2^{n}-2}(-1)^{s_{t+\tau}-s_{t}}=\begin{cases}2^{n}-1,&\text{if }\tau\equiv 0\pmod{2^{n}-1},\\ -1,&\text{if }\tau\not\equiv 0\pmod{2^{n}-1}.\end{cases} In particular, Golomb recognized the importance of the balance, run, and ideal autocorrelation properties in the context of randomness. Binary sequences satisfying these three properties are called pseudo-noise (PN) sequences . Due to their good pseudo-random properties, PN sequences have many practical applications in digital communications, including navigation, radar, and spread-spectrum systems [ 24 ] . Other interesting properties of m-sequences can be found in [ 19 , 22 , 45 ] . Let \{s_{t}\}_{t=0}^{\infty} be a binary m-sequence of order n . For each integer t with 1\leq t\leq 2^{n}-1 , we take the n consecutive subsequences of length t beginning at positions 0,1,\dots,n-1 , and arrange them into the matrix G_{t}=\begin{pmatrix}s_{0}&s_{1}&\cdots&s_{t-1}\\ s_{1}&s_{2}&\cdots&s_{t}\\ \vdots&\vdots&\ddots&\vdots\\ s_{n-1}&s_{n}&\cdots&s_{n+t-2}\end{pmatrix}\in\mathbb{F}_{2}^{\,n\times t}. (2) G_{t} is the observability matrix associated with the m-sequence. Here, each column (s_{j},s_{j+1},\dots,s_{j+n-1})^{\top}\in\mathbb{F}_{2}^{\,n\times 1} is exactly the state vector of the underlying n -stage LFSR at time j , and thus G_{t} may also be viewed as the matrix formed by the consecutive state vectors from time 0 to time t-1 . It is also easy to see that {\mathrm{rank}}(G_{t})=\min\{n,t\} . Given a matrix G , its Gram matrix GG^{\top} is formed from the pairwise inner products of row vectors. Since the Gram matrix is a classical object, it is natural to consider the Gram matrix of the observability matrix G_{t} . In particular, one can ask the following rank questions of G_{t}G_{t}^{\top} , and the rank evolution and distribution of the cases n=5,6 are illustrated in Figure 2 . Question 1: Is there a general characterization for {\mathrm{rank}}(G_{t}G_{t}^{\top}) ? Question 2: What can we say about distribution \displaystyle\#\{\,1\leq t\leq 2^{n}-1\mid{\mathrm{rank}}(G_{t}G_{t}^{\top})=k\,\} , for 0\leq k\leq n ? In particular, how many of the Gram matrices are full-rank? In this paper, we not only answer the two questions, but also reveal new properties of m-sequences that go beyond the classical ones established by Golomb. More precisely, we derive new properties of {\mathrm{rank}}(G_{t}G_{t}^{\top}) , which are independent of the choice of primitive polynomials attached to m-sequences. Our first goal is to determine the rank distribution of the family \{G_{t}G_{t}^{\top}\mid 1\leq t\leq 2^{n}-1\} . To this end, we first characterize the singular matrices of the family \{G_{t}G_{t}^{\top}\mid 1\leq t\leq 2^{n}-1\} by a canonical representation of rational functions. This representation leads to an explicit rank characterization for singular matrices, and thereby reduces the determination of the whole rank distribution to the enumeration of some special rational functions. Next, we also investigate the rank dynamics along the natural cyclic ordering, and