Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring

Basic Information

• Paper ID: 2510.09057
• Title: Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring
• Authors: Ankit Yadav, Ritumoni Sarma, Anuj Kumar Bhagat (Indian Institute of Technology Delhi)
• Classification: cs.IT math.IT
• Publication Date: October 10, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.09057v1

Abstract

This paper investigates the subfield codes $\mathcal{C}_{D}^{(2)}$ of $\mathcal{C}_D$-codes over the non-chain ring $\mathcal{R} := \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$, where the defining set $D$ is constructed based on simplicial complexes. The authors determine the Hamming weight distributions and parameters of $\mathcal{C}_D^{(2)}$ for various $D$, identify multiple infinite families of distance-optimal codes, and provide sufficient conditions for these codes to be minimal and self-orthogonal. Additionally, two families of strongly regular graphs are obtained from the constructed binary codes.

Research Background and Motivation

Problem Background

1. Importance of distance-optimal codes: For fixed parameters $n$ and $k$, distance-optimal codes achieve the maximum possible error detection and correction capability, which is one of the primary objectives in coding theory.
2. Existing construction methods:
   • Gray mapping: constructing codes over finite fields from codes over finite rings
   • Simplicial complexes: first introduced by Chang and Hyun for constructing optimal linear codes
3. Limitations of prior work: Shi and Li in reference 27 studied the Lee weight distribution of $\mathcal{C}_D$-codes over ring $\mathcal{R}$ and their Gray images, but did not investigate subfield codes.

Research Motivation

1. Parameter improvement: Demonstrate that binary subfield codes $\mathcal{C}_D^{(2)}$ have better parameters compared to the binary Gray images in reference 27
2. Theoretical refinement: Provide theoretical conditions for minimality and self-orthogonality of code families based on simplicial complexes
3. Application extension: Apply binary codes to the construction of strongly regular graphs

Core Contributions

1. Determined Hamming weight distributions of subfield codes: Completely characterized the weight distribution of $\mathcal{C}_D^{(2)}$ for various defining sets $D$ constructed from simplicial complexes
2. Constructed multiple distance-optimal code families: Identified several infinite families of distance-optimal binary linear codes, some achieving the Griesmer bound
3. Established conditions for minimality and self-orthogonality: Provided sufficient conditions for $\mathcal{C}_D^{(2)}$ to be minimal and self-orthogonal codes
4. Demonstrated parameter advantages: Proved that subfield codes exhibit better parameter performance compared to Gray image codes
5. Strongly regular graph construction: Utilized binary projective codes to construct two families of strongly regular graphs

Methodology Details

Problem Definition

Study linear codes $\mathcal{C}_D$ over the ring $\mathcal{R} = \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$, where:

• The defining set $D$ is constructed based on simplicial complexes
• The objective is to analyze the properties of its binary subfield code $\mathcal{C}_D^{(2)}$

Theoretical Framework

1. Ring Structure and Basis

Each element of ring $\mathcal{R}$ can be expressed as $a + bu + cv + duv$, where $a,b,c,d \in \mathbb{F}_2$, $u = x + \langle x^2, y^2\rangle$, $v = y + \langle x^2, y^2\rangle$.

Choose the $\mathbb{F}_2$-basis $\mathcal{B} = \{b_1 = 1+u+v, b_2 = u+v, b_3 = u, b_4 = uv\}$.

2. Subfield Code Construction

Utilize the $\mathbb{F}_2$-valued trace map $\tau: \mathcal{R} \to \mathbb{F}_2$: $\tau(a + bu + cv + duv) = a + b + c + d$

Theorem 3.3: If $D = b_1D_1 + b_2D_2 + b_3D_3 + b_4D_4$, then $\mathcal{C}_D^{(2)}$ is generated by the matrix: $G^{(2)} = \begin{pmatrix} G_1 + G_4 \\ G_3 \\ G_2 \\ G_1 \end{pmatrix}$

3. Weight Calculation Formula

For $(x_1,x_2,x_3,x_4) \in (\mathbb{F}_2^m)^4$: $\text{wt}(c_D^{(2)}(x_1,x_2,x_3,x_4)) = \frac{|D|}{2} - \frac{1}{2}\sum_{d_1 \in D_1} (-1)^{(x_1+x_4)d_1} \sum_{d_2 \in D_2} (-1)^{x_3d_2} \sum_{d_3 \in D_3} (-1)^{x_2d_3} \sum_{d_4 \in D_4} (-1)^{x_1d_4}$

Core Technical Innovations

1. Boolean Function Technique

Define the Boolean function $\psi(\cdot | Y): \mathbb{F}_2^m \to \mathbb{F}_2$: $\psi(x_1 | Y) = \prod_{i \in Y}(1-\alpha_i) = \begin{cases} 1, & \text{if } \text{Supp}(x_1) \cap Y = \emptyset \\ 0, & \text{if } \text{Supp}(x_1) \cap Y \neq \emptyset \end{cases}$

2. Application of Simplicial Complexes

Utilize properties of simplicial complex $\Delta_X$ and its complement $\Delta_X^c$: $\sum_{t \in \Delta_Y} (-1)^{x_1 t} = 2^{|Y|}\psi(x_1 | Y)$$\sum_{t \in \Delta_Y^c} (-1)^{x_1 t} = 2^m\delta_{0,x_1} - 2^{|Y|}\psi(x_1 | Y)$

Experimental Setup

Theoretical Verification

This is primarily a theoretical work, with results verified through mathematical proofs. The authors used the MAGMA computer algebra system to verify specific examples.

Verification Example

Example 4.8: $m=4$, $X=Y=Z=\emptyset$, $W=\{1,2,3\}$

• Obtained a binary optimal linear code with parameters $[120, 7, 60]$
• Weight enumerator: $x^{120} + 15x^{56}y^{64} + 112x^{60}y^{60}$
• The code is both minimal and self-orthogonal, enabling construction of quantum error-correcting code $[[120, 106, 3]]$

Experimental Results

Main Theoretical Results

Theorem 4.2 provides code parameters for six different defining sets:

1. First-order codes: $D = b_1\Delta_X + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$
   • Parameters: $[2^{|X|+|Y|+|Z|+|W|}, |X|+|Y|+|Z|+|W|, 2^{|X|+|Y|+|Z|+|W|-1}]$
   • Distance-optimal condition: $|X|+|Y|+|Z|+|W| \geq 2$
2. Second-order codes: $D = b_1\Delta_X^c + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$ ($|X| < m$)
   • Parameters: $[(2^m-2^{|X|})2^{|Y|+|Z|+|W|}, m+|Y|+|Z|+|W|, (2^m-2^{|X|})2^{|Y|+|Z|+|W|-1}]$
   • Achieves Griesmer bound, distance-optimal
3. Fourth-order codes: $D = b_1\Delta_X^c + b_2\Delta_Y^c + b_3\Delta_Z + b_4\Delta_W$
   • Parameters: $[(2^m-2^{|X|})(2^m-2^{|Y|})2^{|Z|+|W|}, 2m+|Z|+|W|, (2^m-2^{|X|}-2^{|Y|})2^{m+|Z|+|W|-1}]$
   • Distance-optimal condition: $2^{|X|+|Y|+|Z|+|W|} \leq m+|Z|+|W|+\min\{|X|,|Y|\}$

Minimality and Self-Orthogonality Conditions

Theorem 4.7 provides sufficient conditions:

• Self-orthogonality: When every codeword has weight divisible by 4 (using Theorem 2.2)
• Minimality: When $\frac{\text{wt}_{\min}}{\text{wt}_{\max}} > \frac{1}{2}$ (using Lemma 2.3)

Strongly Regular Graph Construction

Theorems 4.12 and 4.13 construct two families of strongly regular graphs:

• First family parameters: $(2^{m+|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|+1})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|})$
• Second family parameters: $(2^{m+|Y|+|Z|+|W|}, 2^{|X|+|Y|+|Z|+|W|}-1, 2^{|X|+|Y|+|Z|+|W|}-2, 0)$

Related Work

Historical Development

1. Gray mapping method: Hammons et al. first applied Gray mapping to construct optimal nonlinear codes
2. Simplicial complex method: Chang and Hyun introduced simplicial complexes for constructing optimal linear codes
3. Coding theory over rings: Research on constructing codes over various finite rings

Positioning of This Work's Contributions

• Extends the work of Shi and Li, transitioning from Gray images to subfield codes
• Provides a more systematic theoretical framework
• Demonstrates parameter advantages and optimality

Conclusions and Discussion

Main Conclusions

1. Successfully constructed multiple families of distance-optimal binary linear codes
2. Established theoretical criteria for minimality and self-orthogonality
3. Proved parameter advantages of subfield codes over Gray image codes
4. Achieved application from coding theory to graph theory

Limitations

1. Only considers simplicial complexes with a single maximal element
2. Extension to complexes with two maximal elements becomes computationally prohibitive
3. Some distance-optimality conditions are relatively restrictive

Future Directions

1. Study subfield codes of $\mathcal{C}_D$-codes over different alphabets
2. Explore simplicial complexes with two maximal elements
3. Seek more general distance-optimality conditions

In-Depth Evaluation

Strengths

1. Significant theoretical contribution: Systematically analyzes weight distributions of subfield codes, filling theoretical gaps
2. Strong methodological innovation: Cleverly combines simplicial complexes, Boolean functions, and trace maps
3. Good result completeness: Provides complete weight distribution tables and parameter formulas
4. High application value: Constructed codes can be used for quantum error-correcting codes and strongly regular graphs

Weaknesses

1. High computational complexity: Calculations become extremely tedious for complex simplicial complexes
2. Insufficient practical verification: Lacks large-scale numerical experiments and practical application testing
3. Limited generalizability: Methods primarily apply to specific ring structures

Impact

1. Academic value: Provides new research directions for algebraic coding theory
2. Practical value: Constructed optimal codes have potential applications in communication systems
3. Reproducibility: Theoretical results are complete but require strong mathematical background for understanding

Applicable Scenarios

1. Communication systems requiring efficient error correction
2. Quantum error-correcting codes in quantum information processing
3. Strongly regular graph construction in combinatorial mathematics
4. Secret sharing schemes in cryptography

References

The paper cites 35 related references, primarily including:

• 27 Shi, M. and Li, X. - Prior work directly extended by this paper
• 9 Chang, S. and Hyun, J.Y. - Pioneering work on simplicial complexes
• 13 Hammons et al. - Classical work on Gray mapping
• 12 Griesmer - Foundational theory on code length bounds