pith. sign in

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
0 comments X

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.

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)
  1. 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.
  2. 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.
  3. 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)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [1]

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

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

    work page 1957

  2. [2]

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

    work page 1990

  3. [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

    work page

  4. [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

    work page

  5. [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

    work page 2026

  6. [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

    work page 2017

  7. [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

    work page 2014

  8. [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

    work page 2018

  9. [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

    work page 2019

  10. [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

    work page 2020

  11. [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

    work page

  12. [12]

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

    work page 1991

  13. [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

    work page 1997

  14. [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

    work page 2013

  15. [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

    work page 2015

  16. [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

    work page 2018

  17. [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

    work page 1994

  18. [18]

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

    work page 1986

  19. [19]

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

    work page 1967

  20. [20]

    Goresky and A

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

    work page 2012

  21. [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

    work page 2018

  22. [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

    work page 1976

  23. [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

    work page 2007

  24. [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

    work page 2021

  25. [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. [26]

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

    work page

  27. [27]

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

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

    work page 1980

  28. [28]

    Lascoux and P

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

    work page 2005

  29. [29]

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

    work page 2017

  30. [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

    work page 2025

  31. [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

    work page 2014

  32. [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

    work page 2024

  33. [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

    work page 2023

  34. [34]

    Lidl and H

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

    work page 1997

  35. [35]

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

    work page 1992

  36. [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

    work page 1969

  37. [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

    work page 1990

  38. [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

    work page 2000

  39. [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

    work page 2001

  40. [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

    work page 2004

  41. [41]

    Serre,Galois Cohomology, Springer Monogr

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

    work page 2002

  42. [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

    work page 2023

  43. [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

    work page 2025

  44. [44]

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

    work page 1904

  45. [45]

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

    work page 1970

  46. [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

    work page 2016

  47. [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

    work page 2017

  48. [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

    work page 2024

  49. [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

    work page 2015

  50. [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

    work page 2024