coding theory engineers

Abstract: Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via $δ$-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.

Abstract: We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.

Abstract: Let $(T, \circ)$ be a loop of order $k \geq 3$ and $D_S^*$ the loopless central digraph obtained from the associated central digraph $D_S$ by removing the $k$ self-loops at the diagonal vertices. We construct an explicit arc-labeling $f$ of $D_S^*$ ordering all arcs lexicographically by $(\text{tail}, \text{head})$ and assigning labels $1, \ldots, m$ in that order and prove that $f$ is an antimagic labeling. Consequently, $D_S$ is antimagic for every loop of order $k \geq 3$, a property that depends only on $k$ and is invariant across all non-isomorphic loops of the same order.

Abstract: Minimal binary linear codes play an important role in secret-sharing schemes and in the structural study of linear codes. We study the minimality of three classes of known constructions: codes from a single complete Hamming-weight layer, codes from arbitrary unions of such layers and graph cut-space codes. For the previously studied single-layer codes C, we give a complete minimality classification: C is minimal if and only if t is even. For t = 4, we determine the minimum and maximum weights, and show that the family strictly violates the binary Ashikhmin Barg sufficient condition for every k. We also calculate the minimum distance of the dual code. For arbitrary unions of complete Hamming-weight layers, we obtain an if-and-only-if classification of minimality and uniform criteria for evenness, self-orthogonality, the doubly even property and hull dimension. We further analyze the family for odd k. Finally, using the classical bond characterization of cuts, we translate minimality of graph cut space codes into a graph-theoretic condition: a nonempty simple graph has a minimal cut code precisely when it has one edge-containing component and that component is complete. We also give a graph-function realization of the known binary tetrahedron code and explicitly identify the resulting code equivalence.

Abstract: We prove the Golomb--Welch conjecture for lattice tilings: for every $n\ge3$ and $r\ge2$, the integer lattice $\Z^n$ admits no lattice tiling by Lee balls $B_n(r)$ of radius $r$. Together with the classical constructions for $n\le2$ and for $r=1$, this determines all parameters for which a lattice Lee tiling exists. Equivalently, we show that every abelian Cayley graph of even degree $2n\ge6$ and diameter $r\ge2$ has strictly fewer than $|B_n(r)|$ vertices.

Abstract: Let $\F$ be a finite field. Given $N$ distinct points $\bmα_1,\ldots,\bmα_N \in \F^m$ and associated values $β_1,\ldots,β_N \in \F$, we study the problem of computing an $m$-variate polynomial $f(\vy) \in \F[\vy]$ of individual degree less than $d$, with $d^m \ge N$, that satisfies $f(\bmα_i)=β_i$ for all $i\in[N]$, whenever such an $f$ exists. This is known as the\textit{ multivariate polynomial interpolation} problem. In this work, given $N=d^m$, we present a deterministic algorithm for multivariate polynomial interpolation over an arbitrary finite field $\F$ that runs in near-quadratic time $N^{2+o(1)}\poly(m,d,\log|\F|)$, assuming $d$ is $ω(1)$. This bound holds whenever the associated \emph{multivariate Vandermonde} matrix is nonsingular, has constant co-rank, or admits some special structure. In the general case, we give a randomized Las Vegas algorithm attaining the same near-quadratic running time, provided the finite field is sufficiently large and $d$ grows similar to the previous case. Unlike other multivariate interpolation strategies, we do not assume black-box access to the polynomial. In particular, we are not permitted to query arbitrary input points to obtain their evaluations. Our interpolation result follows by combining Wiedemann's classical approach~\cite{w86} for solving sparse linear systems with known bounds for fast \emph{multivariate multipoint evaluation} over finite fields~\cite{umans08, KU11, BGKM23, BGGKU24}. Specifically, our deterministic interpolation strategy relies on a deterministic variant of Wiedemann's approach, which is more commonly used in the randomized setting.

Abstract: This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time $n^{O(k)}$ where $m = n^β, β\in [0,k]$ is the number of samples and $\mathsf{Bern}(n^{-δ}),δ\in (0,+\infty)$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $β> 1, δ>1$ based on Gaussian elimination; II. A folklore algorithm when $β\ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $β> δ+ k(1-δ), δ\in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $β> δ+ (k-1)(1-δ), δ\in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.

Abstract: We study Frobenius intersection profiles of maximum rank distance (MRD) codes arising from ordinary polynomial multiples over finite fields. We prove that every numerically admissible profile is realized within this family over every sufficiently large extension, using a root-exponent pattern independent of the extension degree. A factor-orbit gap formula provides the underlying structural description, while effective extension-degree bounds guarantee realization. We also establish a lower bound valid for all polynomial generators and show that the upper and lower bounds differ by only $O_q(\log n)$ along an infinite family of parameters. Finally, we characterize the generalized Gabidulin members and obtain non-generalized-Gabidulin realizations of every profile with initial loss at least two over infinitely many extensions.

Abstract: We give the asymptotic rate of Delsarte's linear programming bound for binary codes and spherical codes. This extends previous work of the author which formulated and proved an analogue of the conjecture of Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini for binary codes, obtaining the rate of the Delsarte linear program at distance $1/2-1/π$. The lower bounds introduce ideas from potential theory into the study of Delsarte's bounds, whereby the measures underlying a system of orthogonal polynomials give an obstacle problem. We solve the resulting obstacle problem in the case of binary codes and spherical codes, obtaining a closed form for the lower bound in terms of elliptic integrals. For the upper bounds, we relate the $N$-qubit construction for binary codes used in previous work of the author to the constructions in OpenAI's Chapter 2 for spherical codes and observe that they both involve interlacing spectra. This leads to a variational problem involving measures constructed from these spectra under the Markov-Krein correspondence. This variational problem admits an exact solution and matches the lower bound.

Abstract: The $\mathbb{Z}_{p^s}$-additive codes are subgroups of $\mathbb{Z}_{p^s}^n$. A $\mathbb{Z}_{p^s}$-linear generalized Hadamard (GH) code is a GH code over $\mathbb{Z}_p$ which is the Gray map image of a $\mathbb{Z}_{p^s}$-additive code. A recursive construction gives such codes $H_p^{t_1,\dots,t_s}$, of type $(n;t_1,\dots,t_s)$ and length $p^t$, and a partial classification of them is known. In this paper, we complete the classification of these codes for every prime $p$. The main tool is the derived code, obtained by puncturing the code outside a block of coordinates determined by its kernel. For a nonlinear code $H_p^{t_1,\dots,t_s}$ with $t_1\geq2$, the derived code is a $\mathbb{Z}_{p^{s-1}}$-linear GH code of the same family, although the mechanism for odd $p$ differs from the binary one. As a consequence, for $t\geq3$, there are $\mathcal P(t+1)-\mathcal P(t)$ nonequivalent such codes of length $p^t$ if $p$ is odd, and $\mathcal P(t+1)-\mathcal P(t)-1$ if $p=2$, where $\mathcal P(n)$ is the number of partitions of $n$. In particular, this completes the classification of the $\mathbb{Z}_{2^s}$-linear Hadamard codes. We also prove a conjecture on the codes with $t_1\geq2$ and $t_s=0$.

Abstract: We study non-additive rank-metric codes contained in the space of symmetric matrices over a finite field. Our main focus is on symmetric $2$-codes. For odd $q$, we introduce a quotient construction for $\mathrm{Sym}_3(q)$ in which rank-one differences are described by isotropic vectors of a nondegenerate quadratic form on $\mathbb F_q^4$. This leads to a correspondence with partial ovoids of the elliptic quadric $Q^-(5,q)$. Using a construction of Cossidente and Pavese, we obtain a non-additive symmetric $2$-code in $\mathrm{Sym}_3(q)$ of cardinality $q^4+2q^3$, improving the previously known general lower bound. We also give an explicit matrix description of this family. Lastly, we present a block-based construction for symmetric $2$-codes that extends the three-dimensional improvement to all odd dimensions. In particular, for every odd $n\geq3$ and every prime power $q>2$, we obtain \begin{equation*} A_q^{\rm sym}(n,2) \ge q^{(n^2-1)/2}+q^{(n^2-3)/2}+q^{(n^2-9)/2}, \end{equation*} which is strictly larger than the maximum cardinality of an additive symmetric $2$-code with the same parameters. This yields the first infinite family (as the matrix dimension $n$ varies) of non-additive symmetric $2$-codes whose size is larger than the largest achievable size of an additive code with the same parameters; before this, such a gap had only been established for $n=3$.

Abstract: Let $q$ be a prime power. An $(r, i)$-regular fat $\mathbb F_q$-linear set has exactly $r$ points of weight $i\ge2$, called fat points. All of its remaining points have weight one, and at least one such point occurs. We solve two open problems posed by three of the authors of this paper. First, we derive divisibility constraints on the point weights using the scalar stabilizer of the defining subspace. Consequently, a regular fat linear set of rank $2i$ in $\operatorname {PG}(1,q^n)$ has at most two or exactly $q + 1$ fat points. In the latter case, the fat points form an $\mathbb F_q$-subline. Second, we construct higher-dimensional regular fat linear sets whose fat points do not form an $\mathbb F_q$-subgeometry. In particular, for every $k\geq 3$ we obtain examples of rank $2k$ whose fat locus consists of an $\mathbb F_q$-subgeometry $\operatorname {PG}(k-2,q)$ in $\operatorname {PG}(k-1,q^4)$ together with one external point. This construction is then generalized further. Finally, we apply our projective-line results to $q$-matroid representability and present an infinite family of non-representable rank-two $q$-matroids arising from partial spreads.

Abstract: We study the variation of hull dimensions of symplectic linear codes under equivalence transformations preserving the symplectic distance. For a symplectic linear code $C$, we introduce an even-valued invariant $Δ(C)$, which depends only on the equivalence class of $C$. This invariant can be expressed as the generic rank of an associated space of alternating matrices and, equivalently, as twice a corresponding matroid matching number. If $C$ has dimension $k$, we prove that the minimum symplectic hull dimension among all codes equivalent to $C$ is $k-Δ(C)$. Consequently, $C$ is equivalent to a symplectic LCD code if and only if $Δ(C)=k$. We further show that every symplectic MDS code of even dimension is monomially equivalent to a symplectic LCD code. For a symplectic self-orthogonal code $C$, we determine all attainable hull dimensions: for every integer $r$ with $0\le r\le Δ(C)/2$, there exists a monomially equivalent code whose symplectic hull has dimension $k-2r$. We also refine a standard form for the generator matrix of a symplectic self-orthogonal code and derive the corresponding parity-check matrix and the Gram matrix of the dual code. In the self-dual case, we characterize $Δ(C)$ through minors of an associated symmetric matrix. Furthermore, we relate hull variation to graph matchings, establish a bound for $Δ(C)$, and give graph constructions producing symplectic self-dual MDS, optimal, and best-known codes.

Abstract: The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

Abstract: Alon, Bishnoi, Das and Neri constructed sequences of strong blocking sets in $(k-1)$-dimension projective space $P({\bf F}_q, k-1)$ with sizes at most $Cqk$, where $k$ goes to the infinity and $C$ is a fixed positive constant not depending on $q$, in their paper published in Transactions AMS, vol. 277, pp. 5389-5410, 2024. This is equivalent to a sequence of minimal $[n_i,k_i]_q$ codes with positive rate $\frac{k_i}{n_i} \geq c$, where $k_i$ goes to the infinity and $c$ is a fixed positive constant only depending on $q$. They solved one of the main open problems on minimal codes. The Alon-Bishnoi-Das-Neri construction was based on asymptotically good sequences of algebraic geometric codes and expander graphs. However, the constant $C$ is large for small prime power $q$. In this paper, based on a simple approach using $(q-1)$-power intersecting algebraic geometric codes via concatenation to construct minimal codes, we construct explicit strong blocking sets in $(k-1)$-dimension projective space with sizes around $2(q^2-1)k$, equivalently, explicit minimal $[n,k]_q$ codes with length around $2(q^2-1)k$. This is an essential improvement on the previous result of Alon-Bishnoi-Das-Neri, when $q \leq 11$. For large $q$, strong blocking sets and minimal codes in our construction are worse than the previous construction of Alon-Bishnoi-Das-Neri. However, our approach is much simpler and does not depend on expander graphs.

Abstract: Given a finite Cartesian set $S=X \times Y$ and a decreasing set of monomials $\mathcal M$, we call extremal polynomials for $\mathcal M$ over $S$ those that have the maximum number of zeros in $S$ and whose support belongs to $\mathcal M$. Coordinate factorizations give a family of extremal polynomials; we call them canonical. If $\max(\mathcal M)$, taken with respect to divisibility, is a single monomial, all extremal polynomials are canonical. If $|\max(\mathcal M)|=2$, either all extremal polynomials are canonical, or the problem reduces to the case where $\max(\mathcal M)=\{x^{d_x},y^{d_y}\}$. In the latter case, we prove that the existence of noncanonical extremal polynomials depends on finding families of subsets whose elementary symmetric functions agree. This condition is more restrictive than the classical Prouhet--Tarry--Escott problem, which asks for two sets whose elementary symmetric functions agree. We determine the number of triples $(X, Y, h)$, where $h$ is a quadratic noncanonical extremal polynomial. We apply extremal polynomials to coding theory via minimum-weight codewords.

Abstract: Function-correcting codes, recently introduced by Lenz et al.\ (2023), provide a framework for the receiver to provide a higher level of protection against channel errors than the level of protection for messages. In this paper, we derive a generalised Plotkin-type bound on the redundancy of FCCs under the Hamming metric for arbitrary functions over finite fields. The proposed bound recovers the classical Plotkin bound for classical error-correcting codes as a special case. We further obtain explicit Plotkin-type bounds for linear functions, Hamming-weight functions, and Hamming-weight threshold functions. In addition, we study FCCs for monomial mappings $f(x)=x^n$ over $\mathbb{F}_{q^k}$, which are widely utilised in coding theory, cryptography, and finite geometry, and derive an explicit Plotkin-type redundancy bound.

Abstract: We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism counts from that class. More precisely, we construct connected graphs $H$ for which counts from graphs excluding $H$ as a minor determine the number of homomorphisms from $H$ to any target graph. We also refute the analogous conjecture with immersions in place of minors. We give explicit infinite families of excluded graphs, including cubic bipartite graphs that yield counterexamples for both relations. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these equivalences for infinitely many primes using prime-order automorphisms of graphs that exclude their orbit quotients as minors or immersions.

Abstract: Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

Abstract: In 2025, Jordan et al. introduced Decoded Quantum Interferometry (DQI), a quantum algorithm for combinatorial optimization based on decoding. They considered Reed-Solomon decoding and its associated optimization problem, called Optimal Polynomial Intersection (OPI), which may be viewed as a polynomial regression problem over a finite field. DQI exhibits provable speedups on certain problem instances and establishes a connection between decoding problems and optimization tasks. Leveraging the well-understood dual structure and decoding theory of algebraic geometry codes from other curve families, we introduce COFI: Curve-based Optimal Function Intersection. By considering two-point Hermitian codes, Suzuki codes, and extended norm-trace codes, we broaden the range of algebraic geometry codes used in DQI and identify families that offer further improvements over one-point Hermitian codes in the Hermitian Optimal Polynomial Intersection framework considered by Jordan and Gu. Depending on the family and parameter regime, these curves can reduce quantum resource requirements or increase the number of constraints that can be considered.

Abstract: For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

Abstract: A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.

Abstract: Delsarte (1973) conjectured that there are no nontrivial perfect codes in the Johnson scheme. In this paper, we prove that there are no nontrivial $e$-perfect codes in the Johnson scheme for $e\in\{1,2,4,9,10,12,16\}$. This paper complements "Perfect Codes in the Johnson Scheme Hardly Exist", thus proving Delsarte's conjecture completely.

Abstract: The kissing number in dimension $d$ is the largest number of non-overlapping congruent spheres that can simultaneously touch a central sphere of the same size. We study dimensions $25$-$31$, where the best previous constructions are based on Leech lifting from the optimal kissing configuration in dimension $24$. Our method exploits the absence of contacts between the unlifted bulk and the block consisting of lifted and auxiliary vectors. Rotating this block while keeping the bulk fixed creates room for two antipodal points in dimensions $26$, $27$, and $28$, and one point in dimension $29$. Two further modifications yield improvements in dimensions $25$ and $31$: a nonorthogonal diagonal linear deformation of the lifted block admits two antipodal points in dimension $25$, while rotating only the additional coordinates of the lifted vectors admits four nonantipodal points in dimension $31$. Together, these constructions yield the new lower bounds $τ_{25}\geq 197058$, $τ_{26}\geq 198552$, $τ_{27}\geq 200046$, $τ_{28}\geq 204522$, $τ_{29}\geq 209497$, and $τ_{31}\geq 238354$.

Abstract: The linear complexity and the error linear complexity of multi-sequences are measures for security in stream ciphers. In this manuscript, we present a general framework for constructing periodic multi-sequences via function fields. We prove that the constructed multi-sequences possess both large linear complexity and large error linear complexity. We apply this framework of constructing multi-sequences to various maximal function fields and we obtain many new multi-sequences with various lengths and dimensions. As a byproduct, we adopt this idea and produce many new quasi-cyclic algebraic geometric codes as well.

Abstract: LCD codes over finite commutative chain rings are known to be free. However, if the ring is not indecomposable, there always exists an LCD ideal that is projective but not free. We prove that all two-sided LCD codes are projective. We generalise the characterisation of finite commutative Frobenius rings by means of the size condition of a code and its dual to the noncommutative setting. This result is applied to prove that group codes are LCD if and only if they are generated by a central idempotent.