arxiv: 2604.26387 · v1 · submitted 2026-04-29 · 💻 cs.IT · math.IT

Rank Distribution and Dynamics of Gram Matrices from Binary m-Sequences with Applications to LCD Codes

Hengfeng Liu , Chunming Tang , Cuiling Fan , Zhengchun Zhou This is my paper

Pith reviewed 2026-05-07 11:07 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords m-sequencesGram matricesrank distributionrank dynamicsGalois groupsBézoutianhull distributionsimplex codes

0 comments

The pith

An explicit formula gives the rank of every Gram matrix formed from consecutive segments of a binary m-sequence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs n by n Gram matrices using n consecutive subsequences of length t from a binary maximum-length sequence of period 2^n minus 1. Through semilinear representations of the Galois group and the Bézoutian of certain polynomials, it derives a closed-form expression for the matrix rank r_n(t) at each t. This establishes the full distribution, proving full rank for roughly half the possible t values. The work also maps how the rank changes as t increases, showing that any rank below n must shift at the next t while full rank endures over stretches of consecutive t. These findings serve as a complete invariant for m-sequences and determine the hull distribution for the family of punctured cyclic simplex codes.

Core claim

Utilizing semilinear representation of Galois groups and Bézoutian of polynomials, we derive an explicit formula for r_n(t) for all t, thereby establishing the complete rank distribution of these Gram matrices. We prove that full rank is attained for approximately half of the admissible values of t. The dynamics of r_n(t) show that rank-deficient states are strictly unstable, meaning r_n(t) less than n implies r_n(t+1) differs from r_n(t), while the full-rank state persists over nontrivial intervals of consecutive t. These results fully characterize the global rank distribution and local dynamics as invariants of m-sequences and determine the hull distribution of punctured cyclic simplex cod

What carries the argument

The rank function r_n(t) of the n by n Gram matrix formed from n consecutive t-length subsequences of a binary m-sequence, computed via semilinear representations of Galois groups and Bézoutians of polynomials.

If this is right

Full rank is attained for approximately half of the admissible values of t.
If the rank at some t is less than n then the rank at t plus 1 must differ from it.
Full rank, once attained, remains at n over a nontrivial interval of consecutive t values.
The hull distribution of the family of punctured cyclic simplex codes is completely determined.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The persistence of full rank over intervals of t could simplify verification of linear independence when m-sequences are used in sliding-window signal processing.
The same combination of Galois representations and Bézoutians might yield rank distributions for Gram matrices built from other families of sequences with two-level autocorrelation.
Knowing the exact hull distribution opens a route to construct families of LCD codes whose minimum distance is controlled by the underlying m-sequence parameters.

Load-bearing premise

The ideal autocorrelation and balance properties of m-sequences together with semilinear Galois representations and Bézoutians suffice to produce the explicit rank formula without further hidden constraints on subsequence choice or field characteristic.

What would settle it

Direct computation of the actual Gram matrix ranks for small n such as n equals 3 or 4 across every t from 1 to 2 to the n minus 1, then checking whether the fraction of full-rank cases is near one half and whether deficient ranks always change while full rank holds in consecutive blocks.

read the original 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 \le t \le 2^n - 1$, we extract $n$ consecutive subsequences of length $t$ from an m-sequence of period $2^n - 1$, construct their corresponding $n \times n$ Gram matrix, and investigate its rank, denoted by $r_n(t)$. Utilizing semilinear representation of Galois groups and B\'ezoutian of polynomials, we derive an explicit formula for $r_n(t)$ for all $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$. We further uncover the intricate dynamics of $r_n(t)$: rank-deficient states are strictly unstable (i.e., $r_n(t) < n$ implies $r_n(t+1) \ne r_n(t)$), whereas the full-rank state exhibits strong persistence, remaining at $n$ over a nontrivial interval of consecutive values of $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives an explicit formula for the rank of Gram matrices from m-sequence segments and determines the hull distribution for punctured simplex codes.

read the letter

Colleague, The key point is that this paper gives a closed-form expression for the rank r_n(t) of the Gram matrix from n consecutive t-length pieces of a binary m-sequence, along with its dynamics, and then applies that to find the exact hull distribution for the punctured cyclic simplex codes. What they do is take the ideal autocorrelation and balance of m-sequences, represent the shifts via semilinear Galois actions, and use the Bézoutian to compute the rank explicitly for every t. They show full rank occurs for about half the values, that deficient ranks are unstable in the sense that they must change at the next step, and that full rank persists over consecutive t's. This seems like a fresh invariant, and the code application follows directly from it. The work looks solid on the surface. The tools are the right ones for turning sequence correlations into matrix ranks, and the results are stated precisely enough to be testable. No obvious circularity or invented entities here. A minor concern is that the abstract doesn't show the actual formula or small-n examples, so it's hard to see if the expression simplifies nicely or if there are edge cases for small n or certain characteristics. But the stress-test didn't turn up structural problems. This is aimed at researchers in algebraic coding theory and sequence design, particularly those studying LCD codes or m-sequence properties. A reader with background in finite fields and linear codes will get value from the explicit results and the dynamics. I would send it for peer review. The explicit formula and complete distribution are concrete contributions that warrant checking by experts in the area.

Referee Report

0 major / 3 minor

Summary. The paper derives an explicit closed-form expression for the rank r_n(t) of the n×n Gram matrix formed by n consecutive length-t segments of a binary m-sequence of period 2^n−1, for every admissible t. The derivation relies on the semilinear action of the Galois group and the Bézoutian of the associated polynomials; the resulting formula is used to establish the complete rank distribution (full rank for approximately half the values of t), to prove that rank-deficient states are strictly unstable while the full-rank state is persistent over intervals of t, and to determine the hull distribution of the family of punctured cyclic simplex codes.

Significance. If the algebraic derivation is correct, the work supplies a parameter-free, explicit characterization of an invariant of m-sequences that had not previously been obtained in closed form. The combination of Galois-theoretic and Bézoutian techniques yields both the global distribution and the local dynamics of the rank function, together with a concrete coding-theoretic application to hulls of LCD codes. These results would constitute a substantive advance in the algebraic study of sequence-derived matrices.

minor comments (3)

The abstract states that the formula holds 'for all t' yet does not indicate whether the derivation imposes any auxiliary restrictions on the characteristic or on the choice of consecutive windows; a brief clarifying sentence in the introduction would remove any ambiguity.
Notation for the Gram matrix and the rank function r_n(t) is introduced in the abstract but the precise definition of the inner-product matrix (including normalization or field embedding) appears only later; moving the definition to the first paragraph of Section 2 would improve readability.
The claim that full rank occurs for 'approximately half' of the admissible t values is stated without an accompanying exact count or asymptotic density; adding the precise proportion (or the exact cardinality) in the statement of the main theorem would strengthen the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful review and positive recommendation of minor revision. The referee's summary accurately captures the main contributions of the paper, including the explicit formula for r_n(t), the rank distribution, the stability properties of the rank function, and the application to hulls of punctured cyclic simplex codes. We are pleased that the significance of the Galois-theoretic and Bézoutian approach is recognized.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper applies semilinear representations of Galois groups and Bézoutians of polynomials to the known ideal autocorrelation and balance properties of m-sequences to derive an explicit formula for the rank r_n(t). This constitutes a direct algebraic computation rather than any self-referential definition, fitted prediction, or load-bearing self-citation. The derivation chain is self-contained and does not reduce the claimed results to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the classical algebraic properties of m-sequences and standard tools from finite-field polynomial theory; no new entities or fitted parameters are introduced in the abstract.

axioms (2)

domain assumption Binary m-sequences of period 2^n-1 possess ideal two-level autocorrelation, balance, and run properties.
These properties are invoked to construct the Gram matrices and to apply the Galois and Bezoutian machinery.
standard math Semilinear representations of Galois groups and the Bezoutian of associated polynomials yield an explicit rank expression.
Cited as the technical route to the closed-form formula for r_n(t).

pith-pipeline@v0.9.0 · 5642 in / 1535 out tokens · 71761 ms · 2026-05-07T11:07:08.808078+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

50 extracted references · 1 canonical work pages

[1]

Artin,Geometric Algebra, Interscience Publishers, New York, 1957

E. Artin,Geometric Algebra, Interscience Publishers, New York, 1957

1957
[2]

E. F. Assmus and J. D. Key,Affine and projective planes, Discrete Math., 83 (1990), pp. 161–187. 30

1990
[3]

B´ ezout,Recherches sur le degr´ e des ´ equations r´ esultants de l’´ evanouissement des inconnues, et sur les moyens qu’il convient d’employer pour trouver ces ´ equations, M´ em

E. B´ ezout,Recherches sur le degr´ e des ´ equations r´ esultants de l’´ evanouissement des inconnues, et sur les moyens qu’il convient d’employer pour trouver ces ´ equations, M´ em. Acad. Roy. Sci. Paris, (1764), pp. 288–338
[4]

B´ ezout,Th´ eorie g´ en´ erale des ´ equations alg´ ebriques, Ph.-D

E. B´ ezout,Th´ eorie g´ en´ erale des ´ equations alg´ ebriques, Ph.-D. Pierres, Paris, 1779
[5]

Bouyuklieva, I

S. Bouyuklieva, I. Bouyukliev, and F. ¨Ozbudak,Sequence of numbers of linear codes with increasing hull dimensions, Des. Codes Cryptogr., 94 (2026), 39

2026
[6]

S. D. Cardell, J. J. Climent, and A. Roca,Decoding a perturbed sequence generated by an LFSR, in International Castle Meeting on Coding Theory and Applications, Springer International Publishing, Cham, 2017, pp. 62–71

2017
[7]

Carlet and S

C. Carlet and S. Guilley,Complementary dual codes for counter-measures to side-channel attacks, in Coding Theory and Applications, CIM Ser. Math. Sci. 3, E. R. Pinto et al., eds., Springer-Verlag, 2014, pp. 97–105

2014
[8]

Carlet, S

C. Carlet, S. Mesnager, C. Tang, Y. Qi, and R. Pellikaan,Linear codes overF q are equivalent to LCD codes forq >3, IEEE Trans. Inform. Theory, 64 (2018), pp. 3010–3017

2018
[9]

Carlet, S

C. Carlet, S. Mesnager, C. Tang, and Y. Qi,New characterization and parametrization of LCD codes, IEEE Trans. Inform. Theory, 65 (2019), pp. 39–49

2019
[10]

Carlet,Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020

C. Carlet,Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020

2020
[11]

Cayley,Note sur la m´ ethode d’´ elimination de B´ ezout, J

A. Cayley,Note sur la m´ ethode d’´ elimination de B´ ezout, J. Reine Angew. Math., 53 (1857), pp. 366–367
[12]

C. Ding, G. Xiao, and W. Shan, eds.,The Stability Theory of Stream Ciphers, Springer-Verlag, Berlin, Heidelberg, 1991

1991
[13]

Ding,Linear complexity of generalized cyclotomic binary sequences of order 2, Finite Fields Appl., 3 (1997), pp

C. Ding,Linear complexity of generalized cyclotomic binary sequences of order 2, Finite Fields Appl., 3 (1997), pp. 159–174

1997
[14]

Ding,Cyclic codes from some monomials and trinomials, SIAM J

C. Ding,Cyclic codes from some monomials and trinomials, SIAM J. Discrete Math., 27 (2013), pp. 1977–1994

2013
[15]

Ding,Linear codes from some 2-designs, IEEE Trans

C. Ding,Linear codes from some 2-designs, IEEE Trans. Inform. Theory, 61 (2015), pp. 3265– 3275

2015
[16]

Ding,A sequence construction of cyclic codes over finite fields, Cryptogr

C. Ding,A sequence construction of cyclic codes over finite fields, Cryptogr. Commun., 10 (2018), pp. 319–341

2018
[17]

Fontaine,Le corps des p´ eriodesp-adiques, Ast´ erisque, 223 (1994), pp

J.-M. Fontaine,Le corps des p´ eriodesp-adiques, Ast´ erisque, 223 (1994), pp. 59–111

1994
[18]

R. A. Games,The geometry of quadrics and correlations of sequences, IEEE Trans. Inform. Theory, 32 (1986), pp. 423–426

1986
[19]

S. W. Golomb,Shift Register Sequences, Holden-Day, San Francisco, 1967

1967
[20]

Goresky and A

M. Goresky and A. Klapper,Algebraic Shift Register Sequences, Cambridge University Press, Cambridge, 2012

2012
[21]

Guenda, S

K. Guenda, S. Jitman, and T. A. Gulliver,Constructions of good entanglement-assisted quan- tum error correcting codes, Des. Codes Cryptogr., 86 (2018), pp. 121–136

2018
[22]

Helleseth,Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16 (1976), pp

T. Helleseth,Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16 (1976), pp. 209–232

1976
[23]

Helleseth, J

T. Helleseth, J. Lahtonen, and P. Rosendahl,On Niho type cross correlation functions of m-sequences, Finite Fields Appl., 13 (2007), pp. 305–317

2007
[24]

Helleseth and C

T. Helleseth and C. Li,Pseudo-noise sequences, in Concise Encyclopedia of Coding Theory, Chapman and Hall/CRC, Boca Raton, 2021, pp. 613–644

2021
[25]

Helleseth and C

T. Helleseth and C. Li,An updated review on cross-correlation of m-sequences, preprint, arXiv:2407.16072, 2024

work page arXiv 2024
[26]

C. G. J. Jacobi,De eliminatione variablis e duabus aequatione algebraicis, J. Reine Angew. Math., 15 (1836), pp. 101–124
[27]

Kailath,Linear Systems, Prentice-Hall, Englewood Cliffs, NJ, 1980

T. Kailath,Linear Systems, Prentice-Hall, Englewood Cliffs, NJ, 1980

1980
[28]

Lascoux and P

A. Lascoux and P. Pragacz,B´ ezoutians, Euclidean algorithm, and orthogonal polynomials, Ann. Comb., 9 (2005), pp. 301–319

2005
[29]

C. Li, C. Ding, and S. Li,LCD cyclic codes over finite fields, IEEE Trans. Inform. Theory, 63 (2017), pp. 4344–4356

2017
[30]

Li and C

C. Li and C. Gan,A class of affine-invariant codes and their related codes, SIAM J. Discrete Math., 39 (2025), pp. 2067–2101

2025
[31]

S. Li, T. Feng, and G. Ge,On the weight distribution of cyclic codes with Niho exponents, IEEE Trans. Inform. Theory, 60 (2014), pp. 3903–3912

2014
[32]

S. Li, M. Shi, and S. Ling,A mass formula for linear codes with prescribed hull dimension and related classification, IEEE Trans. Inform. Theory, 71 (2024), pp. 273–286

2024
[33]

Li and M

S. Li and M. Shi,Characterization and classification of binary linear codes with various hull dimensions from an improved mass formula, IEEE Trans. Inform. Theory, 70 (2023), pp. 3357–3372. 31

2023
[34]

Lidl and H

R. Lidl and H. Niederreiter,Finite Fields, Cambridge University Press, Cambridge, 1997

1997
[35]

J. L. Massey,Linear codes with complementary duals, Discrete Math., 106–107 (1992), pp. 337–342

1992
[36]

Massey,Shift-register synthesis and BCH decoding, IEEE Trans

J. Massey,Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), pp. 122–127

1969
[37]

Niederreiter,A combinatorial approach to probabilistic results on the linear complexity pro- file of random sequences, J

H. Niederreiter,A combinatorial approach to probabilistic results on the linear complexity pro- file of random sequences, J. Cryptology, 2 (1990), pp. 105–112

1990
[38]

Sendrier,Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans

N. Sendrier,Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory, 46 (2000), pp. 1193–1203

2000
[39]

Sendrier and G

N. Sendrier and G. Skersys,On the computation of the automorphism group of a linear code, in Proc. IEEE International Symposium on Information Theory, Washington, DC, 2001

2001
[40]

Sendrier,Linear codes with complementary duals meet the Gilbert–Varshamov bound, Dis- crete Math., 285 (2004), pp

N. Sendrier,Linear codes with complementary duals meet the Gilbert–Varshamov bound, Dis- crete Math., 285 (2004), pp. 345–347

2004
[41]

Serre,Galois Cohomology, Springer Monogr

J.-P. Serre,Galois Cohomology, Springer Monogr. Math., Springer-Verlag, Berlin, 2002

2002
[42]

M. Shi, N. Liu, J. L. Kim, and P. Sol´ e,Additive complementary dual codes overF 4, Des. Codes Cryptogr., 91 (2023), pp. 273–284

2023
[43]

M. Shi, S. Li, T. Helleseth, and J. L. Kim,Binary self-orthogonal codes which meet the Griesmer bound or have optimal minimum distances, J. Combin. Theory Ser. A, 214 (2025), 106027

2025
[44]

J. J. Sylvester,The Collected Mathematical Papers, Cambridge University Press, Cambridge, 1904

1904
[45]

H. M. Trachtenberg,On the Cross-Correlation Functions of Maximal Linear Sequences, Ph.D. thesis, University of Southern California, Los Angeles, 1970

1970
[46]

Y. Xia, N. Li, X. Zeng, and T. Helleseth,An open problem on the distribution of a Niho-type cross-correlation function, IEEE Trans. Inform. Theory, 62 (2016), pp. 7546–7554

2016
[47]

Y. Xia, N. Li, X. Zeng, and T. Helleseth,On the correlation distribution for a Niho decimation, IEEE Trans. Inform. Theory, 63 (2017), pp. 7206–7218

2017
[48]

Xiang, C

C. Xiang, C. Tang, H. Yan, and M. Guo,Codes and pseudo-geometric designs from the ternary m-sequences with Welch-type decimationd= 2·3 (n−1)/2+1, Finite Fields Appl., 94 (2024), 102341

2024
[49]

Xiong and N

M. Xiong and N. Li,Optimal cyclic codes with generalized Niho-type zeros and the weight distribution, IEEE Trans. Inform. Theory, 61 (2015), pp. 4914–4922

2015
[50]

Xiong and H

M. Xiong and H. Yan,On correlation distribution of Niho-type decimationd= 3(p m −1) + 1, IEEE Trans. Inform. Theory, 70 (2024), pp. 8289–8302. 32

2024