The asymptotic number of equivalence classes of linear codes with given dimension

Basic Information

• Paper ID: 2510.14424
• Title: The asymptotic number of equivalence classes of linear codes with given dimension
• Authors: Andrea Di Giusto (Eindhoven University of Technology), Alberto Ravagnani (Eindhoven University of Technology)
• Classification: cs.IT (Information Theory), math.CO (Combinatorics), math.IT (Mathematical Information Theory)
• Publication Date: October 16, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.14424

Abstract

This paper investigates the asymptotic number of equivalence classes of linear codes with given length and dimension. While the total number of inequivalent codes of a given length has been studied, the case where dimension varies as a function of length has not been considered. The authors derive explicit asymptotic formulas for the number of equivalence classes under three standard equivalence concepts, for fixed alphabet size and increasing length. The approach also yields exact asymptotic expressions for the sum of all q-binomial coefficients, which has independent value and answers an open problem in the field. Finally, a natural connection is established between these asymptotic quantities and certain discrete Gaussian distributions arising from Brownian motion, providing a probabilistic interpretation of the results.

Research Background and Motivation

Core Problem

The central question addressed in this paper is: How does the asymptotic behavior of the number of equivalence classes evolve when the dimension k of linear codes varies as a function of code length n, i.e., k(n)?

Problem Significance

1. Theoretical Completeness: Fills an important theoretical gap in coding theory. Previous research primarily focused on the total number of equivalence classes of all dimensions for fixed length, overlooking the case where dimension varies with length.
2. Practical Application Value: In practical applications, code dimension often needs to be adjusted according to code length to meet specific performance requirements, making the study of equivalence class numbers with varying dimension practically significant.
3. Mathematical Significance: This research connects coding theory, combinatorics, and probability theory, particularly discrete Gaussian distributions related to Brownian motion.

Limitations of Existing Methods

• Wild (2000): Studied the number of monomial equivalence classes for binary codes, but the proof contained gaps
• Lax (2004): Identified problems in Wild's proof
• Hou (2005, 2007, 2009): Provided correct proofs and obtained asymptotic formulas for total equivalence classes, but did not consider dimension-restricted cases

The main limitation of existing research is that it only considered the total number of equivalence classes of codes with all possible dimensions, of the form: $N_n \sim \frac{\sum_{j=0}^n \binom{n}{j}_q}{n!(q-1)^{n-1}}$

but did not study the number of equivalence classes $N_{k(n),n}$ when dimension k = k(n).

Core Contributions

1. Established asymptotic formulas for dimension-restricted equivalence classes: For dimension functions k(n) satisfying condition (⋆), provided exact asymptotic expressions under three equivalence relations
2. Resolved the open problem on q-binomial coefficient sums: Provided exact asymptotic behavior for $S(n) = \sum_{k=0}^n \binom{n}{k}_q$, answering an open problem posed by Wild in 2000
3. Established connection with discrete Gaussian distributions: Discovered that the asymptotic behavior of equivalence class proportions relates to Jacobi θ₂ and θ₃ distributions, providing a probabilistic interpretation
4. Unified three equivalence concepts: Proved that equivalence class proportions exhibit the same asymptotic behavior under permutation equivalence, monomial equivalence, and semilinear equivalence

Methodology Details

Problem Definition

Given:

• Finite field $\mathbb{F}_q$, where q is a prime power
• Code length n and dimension function k(n)
• Three equivalence relations: permutation equivalence ($S_n$), monomial equivalence ($M_n$), semilinear equivalence ($\Gamma_n$)

Objective: Determine the asymptotic behavior of the number of equivalence classes $N^G_{k(n),n}$, where G ∈ {S, M, Γ}

Core Methodological Framework

1. Application of Burnside's Lemma

For a group G acting on a set X, the number of equivalence classes is: $|X/G| = \frac{1}{|G|}\sum_{g \in G}|\text{Fix}(g,X)| = \frac{|\Delta(G,X)||X|}{|G|} + \sum_{g \in G\setminus\Delta(G,X)}|\text{Fix}(g,X)|$

where $\Delta(G,X) = \{g \in G | \forall x \in X, g.x = x\}$ is the kernel of the action.

2. Introduction of Condition (⋆)

Key technical condition: there exist positive constants A, ε such that $\lim_{n \to \infty} \frac{1}{4}n^2 - εn + A\sqrt{n} - k(n)(n-k(n)) = -\infty$

This condition ensures that the number of fixed points of non-trivial group elements can be neglected in asymptotic analysis.

3. Asymptotic Analysis of q-binomial Coefficients

Established the key asymptotic relationship: $\binom{n}{k(n)}_q \sim \frac{1}{K_q(k(n))} q^{k(n)(n-k(n))}$

where $K_q = \prod_{j=1}^{\infty}(1-q^{-j})$ is the Euler function.

Technical Innovations

1. Separate Treatment of Odd and Even Lengths

Discovered that asymptotic behavior differs fundamentally for odd and even n, requiring separate treatment:

• Even length: related to θ₃ distribution
• Odd length: related to θ₂ distribution

2. Precise Analysis of Central q-binomial Coefficients

Proved the asymptotic behavior of central q-binomial coefficients: $\binom{n}{\lfloor n/2 \rfloor}_q \sim \frac{1}{K_q} q^{\lfloor n/2 \rfloor \lceil n/2 \rceil}$

3. Convergence of Probability Distributions

Established convergence of discrete probability distributions to continuous Jacobi θ distributions, providing profound probabilistic interpretation.

Experimental Setup

Theoretical Verification Methods

Since this is a pure theoretical paper, correctness of results is verified primarily through mathematical proof:

1. Asymptotic Analysis Verification: Verified accuracy of asymptotic formulas by controlling the order of error terms
2. Boundary Case Testing: Verified consistency of formulas in special cases
3. Comparison with Known Results: Compared with existing formulas for total equivalence classes

Key Examples

Example 3.1: $k(n) = \lfloor n/2 \rfloor - r$ (r is a constant) Such functions satisfy condition (⋆) because: $k(n)(n-k(n)) \geq \frac{1}{4}n^2 - \frac{1}{4} - r^2 - r$

Example 3.2: More general function classes $k(n) = \lfloor n/2 \rfloor - \ell(n)$, where $\ell(n) \in o((\varepsilon n - A\sqrt{n})^{1/2})$

Experimental Results

Main Theoretical Results

Theorem 4.1 (Main Result)

For k(n) satisfying condition (⋆), as n → ∞:

$N^S_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q n!}$

$N^M_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q n!(q-1)^{n-1}}$

$N^Γ_{k(n),n} \sim \frac{q^{k(n)(n-k(n))}}{K_q h n!(q-1)^{n-1}}$

where h is the exponent in q = p^h.

Theorem 5.1 (Asymptotic Behavior of Proportions)

Asymptotic behavior of equivalence class proportions:

• Even length: $p_e(k,m) \sim \frac{K_q}{K_q(k)\theta_3(q^{-1})} q^{-(m-k)^2}$
• Odd length: $p_o(k,m) \sim \frac{K_q}{K_q(k)\theta_2(q^{-1})} q^{-(m-k+1/2)^2}$

Corollary 5.3 (Resolution of Open Problem)

$S(2m) \sim \frac{\theta_3(1/q)}{K_q} q^{m^2}$$S(2m+1) \sim \frac{\theta_2(1/q)}{K_q} q^{(m+1/2)^2}$

This completely resolves Wild's 2000 open problem regarding the exact asymptotic behavior of $S(n)$.

Probabilistic Findings

Corollary 5.2 (Distribution Convergence)

As m → ∞:

• $P^e_m \to P_{\theta_3}$ (converges to θ₃ Gaussian distribution)
• $P^o_m \to P_{\theta_2}$ (converges to θ₂ Gaussian distribution)

where the nome parameter is 1/q.

Related Work

Historical Development

1. Wild (2000): First studied asymptotic equivalence classes of binary codes, but the proof was flawed
2. Lax (2004): Identified and pointed out problems in Wild's proof
3. Hou (2005-2009): Provided correct proof framework, established asymptotic theory for total equivalence classes
4. This Paper: First systematic study of dimension-restricted cases and establishment of deep connections with probability theory

Technical Comparison

• Existing Methods: Primarily used Burnside's lemma and group action theory
• This Paper's Innovations:
  • Introduced condition (⋆) to precisely control dimension function growth
  • Discovered fundamental differences between odd and even lengths
  • Established connection with Jacobi θ functions

Conclusions and Discussion

Main Conclusions

1. Completely resolved the dimension-restricted equivalence class counting problem: For dimension functions satisfying condition (⋆), provided exact asymptotic formulas under three equivalence relations
2. Unified different equivalence concepts: Proved that equivalence class proportions exhibit the same asymptotic behavior under three equivalence relations
3. Established bridge between coding theory and probability theory: Discovered profound connections between equivalence class distributions and discrete Gaussian distributions related to Brownian motion
4. Resolved important open problem: Provided exact asymptotic expressions for q-binomial coefficient sums

Limitations

1. Restrictions on dimension functions: Condition (⋆) excludes some important dimension functions, such as constant dimension k(n) = α or linear growth k(n) = λn (0 < λ < 1/2)
2. Complexity of technical conditions: The form of condition (⋆) is relatively complex, potentially limiting the application range of results
3. Practical application considerations: The paper primarily focuses on theoretical results; guidance for practical coding applications requires further research

Future Directions

1. Extend range of dimension functions: Study equivalence class numbers for dimension functions not satisfying condition (⋆)
2. Consider minimum distance: Incorporate minimum distance constraints into equivalence class counting problems
3. Computational complexity analysis: Study construction and identification algorithms for equivalence class representatives
4. Application-oriented research: Apply theoretical results to concrete code design problems

In-Depth Evaluation

Strengths

1. Significant theoretical contribution: First systematic resolution of an important open problem in coding theory, filling a theoretical gap
2. Sophisticated mathematical techniques: Skillfully employed group theory, combinatorics, and asymptotic analysis techniques with rigorous and complete proofs
3. Interdisciplinary value: Established profound connections between coding theory and probability theory (particularly Brownian motion theory), with important mathematical significance
4. Completeness of results: Simultaneously addressed three equivalence relations, providing a unified theoretical framework
5. Resolution of historical problem: Answered Wild's 2000 open problem regarding q-binomial coefficient sums

Weaknesses

1. Limited applicability: Condition (⋆) restricts some natural dimension functions (such as constant dimension) from being handled
2. Limited practical utility: As pure theoretical research, direct guidance for practical code design is limited
3. Computational complexity: While asymptotic formulas are provided, computation for specific n values remains complex
4. Generalization issues: Results primarily apply to linear codes; generalization to nonlinear codes is unclear

Impact

1. Academic influence: Expected to become an important reference in the field of asymptotic analysis in coding theory
2. Theoretical value: Opens new directions for interdisciplinary research between coding theory and other mathematical branches
3. Methodological contribution: Provided techniques potentially applicable to other combinatorial counting problems

Applicable Scenarios

1. Theoretical research: Researchers in coding theory, combinatorics, and asymptotic analysis
2. Teaching applications: Can serve as supplementary material for advanced coding theory courses
3. Related problems: Other combinatorial counting problems with group action structure

References

The paper cites 18 important references, primarily including:

• Wild (2000): Pioneering work establishing the basic problem framework
• Hou (2005-2009): Systematically established theoretical foundations for equivalence class counting
• Huffman & Pless (2010): Standard textbook in coding theory
• Salminen & Vignat (2024): Probabilistic aspects of Jacobi θ functions

This paper represents an important breakthrough in the field of asymptotic analysis in coding theory, not only resolving long-standing theoretical problems but also establishing profound connections with probability theory, possessing significant academic and theoretical value.