error correction engineers

Abstract: We prove that the covering radius of the third-order Reed--Muller code in eight variables is fifty-six. The proof separates even- and odd-weight inputs by moment-controlled slicing. On the even side, a transport invariant on quadratic-label stars and consistency of singleton restrictions give a compatible cubic correction. On the odd side, symmetry of the third moment yields a covariance-rank obstruction. Its rank-two exception is a quartic plus three points of a two-plane; the zero-second-moment case is a prescribed-point perturbation of a quintic. We prove that every such point perturbation has third-order nonlinearity at most fifty-five by a marked derivative identity and complete restriction-code covers. Consequently the maximum among exact-degree-eight functions is fifty-five. The structural reductions are proved analytically, and complete finite certificates verify the explicitly stated local covering and compatibility assertions. The matching lower bound follows from the published quartic relative radius.

Abstract: We prove a fixed-characteristic density form of the Berger-Charpin conjecture for non-degenerate irreducible cyclic codes: for each prime $p$, the lengths admitting such a non-standard code over some finite field of characteristic $p$ have natural density zero. Thus, for almost every length coprime to $p$, every such code over every finite field of characteristic $p$ has only the permutation automorphisms generated by the cyclic shift and the Frobenius map. The proof uses the Feng--Hollmann--Li--Xiang classification for non-standard irreducible cyclic codes, a normal form for the deriving constructions in that paper, and a theorem by Wiertelak on multiplicative orders, in the form recalled by Moree.

Abstract: For a balanced Boolean function $f$ on the discrete hypercube, we study the $α$-stability $\mathbb{E}[(T_ρf)^α]$, where $T_ρ$ is the Boolean noise operator and $0<α<1$. Using the asymmetric Hellinger kernel estimates recently established by OpenAI, we prove that dictators minimize the $7/8$-stability in every dimension and at every correlation $0\leρ\le1$. At interior correlations they are the only minimizers. As a consequence, dictators minimize the $α$-stability for every $7/8\leα<1$, maximize the $α$-stability for every $1<α<2$, and maximize the one-sided Shannon entropy stability $\mathbb{E}[T_ρf\log T_ρf]$. This resolves a conjecture of Li and Médard and strengthens the Courtade--Kumar conjecture in the balanced setting.

Abstract: For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

Abstract: We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.

Abstract: Byrne, Gluesing-Luerssen, and Ravagnani determined the number of codewords with a prescribed nonzero support in a linear maximum sum-rank distance code whose blocks have a common number of columns. Their formula depends only on the code parameters and the support dimensions. Evaluating it for arbitrary parameters gives a family of necessary nonnegativity conditions for existence. We prove their conjecture that this family is equivalent to the condition at the vector of total dimension $d+1$ obtained by filling the longest blocks first, where $d$ is the distance parameter. The resulting explicit criterion applies over every finite field $\mathbb F_q$, for all row numbers $n_i\leqslant m$ and $1\leqslant d<N$, where $m$ is the common number of columns and $N$ is the total number of rows. It also covers the boundary cases in which this vector fills each of its nonzero blocks completely, not explicitly included in the conjecture's displayed parameter range. The proof uses a generating function and an exchange identity to reduce the problem to vectors obtained by filling the longest blocks first. We then estimate alternating sums of elementary symmetric polynomials, with a separate argument for $q=2$. The dual conditions admit the same reduction. For codes that exist, the joint condition follows from sphere-packing bounds for the code and its dual. An infinite family of parameters satisfies the joint condition but admits no such linear code.

Abstract: We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.

Abstract: Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over $\mathbb F_q$ with designed distance $n-m$, write $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrtρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $σ<1$, with positive limiting rate and relative error radius.

Abstract: We prove a new lower bound on the $b$-symbol weight of codewords in dual Melas codes, which is strictly better than known results. We employ a new strategy that translates a pattern counting problem in linear-feedback shift register sequences to a problem on orbits of binary polynomials under a certain action. We use the same techniques to provide an improved lower bound on the burst-covering radius of Melas codes and a new upper bound on the critical exponent of dual Melas codes. We then define a new randomness postulate on (families of) binary sequences, based on the definition of infinite Poisson generic sequences. We conjecture that codewords in the dual Melas code satisfy this postulate, and we show partial progress in establishing this conjecture. We also show how a relaxed version of the problem can be completely resolved, and relate the conjecture to the first part of the paper, giving a justification of why the improved bounds on the $b$-symbol weight were somewhat to be expected.

Abstract: Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

Abstract: Mass formulas for prescribed hull dimensions have mainly been studied for linear codes viewed as subspaces of the whole space. We study internal enumeration for an arbitrary fixed parent code. Let $C$ be an $[n,k]_q$ linear code with an $\ell$-dimensional hull, and let $s$ be the subcode dimension. We determine the number of subcodes with prescribed dimension, hull dimension, and type over finite fields of both even and odd characteristic. We decompose the parent code into an LCD complement and its hull, and use projection to reduce enumeration to the corresponding problem inside the LCD complement. This yields explicit formulas refined by complete type and shows that the counts depend only on the relevant parameters, not on the particular parent code or its length. The known whole-space mass formulas and the enumeration of LCD subcodes of LCD codes arise as special cases. Motivated by code extension, we also study the dual containment problem: for a fixed code, we enumerate larger codes containing it with prescribed hull dimension and type. By duality, this problem is converted into the subcode enumeration problem already solved above, leading to corresponding conditional mass formulas. Finally, we investigate the asymptotic distributions arising from the exact enumeration formulas. When both the subcode dimension $s$ and $k-\ell-s$ tend to infinity, the hull distribution is governed by the LCD complement, and the limiting proportions are explicit constants determined by the field, the prescribed hull dimension, and the relevant type. When $s$ approaches or exceeds the dimension $k-\ell$ of the LCD complement, we determine the asymptotic proportion of subcodes attaining the minimum possible hull dimension and establish the associated concentration behavior. Analogous asymptotic results are obtained for the containment problem.

Abstract: Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.

Abstract: Certifying that a parity-check matrix has no nonempty set of at most t variable nodes leaving at most b checks unsatisfied arises in minimum-distance and trapping-set analysis. Such absence is the infeasibility of a polynomial system, provable by an independently checkable Nullstellensatz certificate. The degree of these certificates depends strongly on how the two cardinality constraints are encoded, although the encodings have identical solutions. For a local encoding with inclusion-exclusion and cardinality obstructions, we construct explicit certificates of degree at most t + b + K + 1, with K logarithmic in the maximum check degree; this bound is independent of the block length and cannot be improved in general. For a standard counting encoding, a generalized planted-knapsack theorem, which pulls back a knapsack functional with an arbitrary target, gives lower bounds linear in the block length for cycle codes, regular codes of girth at least six near the feasibility boundary, array-based quasi-cyclic codes and minimum-distance certificates for arrays of circulant permutation matrices, where the local degree stays bounded. On array codes and regular codes of girth at least eight, planted column pairs extend these bounds to odd column weight with no unsatisfied checks. The planting argument is optimal among such pullbacks. All computed degrees and certificates are verified in exact rational arithmetic; bounds are distinguished from exact minimum degrees. Local certificates for quasi-cyclic matrices, including a lifted fifth-generation New Radio base graph, pass two independent verifiers.

Abstract: We give explicit characterizations of the permutations and linear isometries that leave (univariate) multiplicity codes invariant. We consider any evaluation subset of the finite field, any multiplicity and dimension, and the automorphisms are with respect to the Niederreiter-Rosenblom-Tsfasman (NRT) metric. For multiplicity one, we recover the permutation and automorphism groups of classical Reed--Solomon codes in the classical Hamming metric. In the main dimension range, automorphisms are uniquely determined by a projectivity that permutes the evaluation subset, up to multiplication by a nonzero scalar. For multiplicity one, permutations are given by affine maps that permute the evaluation subset. In contrast, for multiplicity at least two, permutations are only given by translations that permute the evaluation subset. Finally, we give an algebraic characterization of automorphisms of multiplicity codes for the folded Hamming metric.

Abstract: For full-length Reed--Solomon codes, every received word whose interpolation polynomial has degree equal to the code dimension is a deep hole. The Cheng--Murray conjecture asserts that these are the only deep holes in dimensions $3\le k\le q-2$, except when $q$ is even and $k=q-3$. Earlier results settled the conjecture over odd prime fields and in the high-dimensional range. We resolve the remaining cases $3\le k\le\lfloor q/2\rfloor$ over every finite field $\F_q$, thereby completing the classification in all nonexceptional dimensions. Our proof combines two complementary approaches. The tangent envelope of a marked arc yields differential constraints that settle the even-characteristic range $3\le k\le q/2$ and the odd-characteristic range $3\le k\le q/3$. In the remaining odd-characteristic range, local syndrome compatibility and combinatorial counting rule out additional deep holes.

Abstract: For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

Abstract: We study the maximum length of nontrivial simple-root cyclic maximum distance separable (MDS) codes over ${\mathbb F}_q$. We prove $n\le q+1$ if $\gcd(n,q^2-1)>2$, or if the dimension is even and $\gcd(n,q^2-1)>1$. The bound also holds for all lengths whose prime factors lie in $\{2,3,5,7\}$. We obtain further cases involving primes $\ell\ge11$ with $(\ell-1)/2$ prime, under conditions on the exponents and the characteristic. The proofs combine Fourier supports, locality bounds and field descent with arithmetic restrictions on multiplicative orders and prime-adic valuations.

Abstract: We study the set of weights occurring in the high-order binary Reed-Muller codes $RM(m-7,m)$. For every $m\geq 14$, we prove that the weight spectrum contains all even weights in $[336,2^m-336]$, together with an explicit finite set of low weights and their complements. The proof first establishes the corresponding base-code inclusion in $RM(7,14)$. This base step uses four-block concatenation, explicit degree-six monomial witnesses, and known spectrum inputs for $RM(5,10)$ and $RM(6,12)$. The base inclusion is then lifted to all $m\geq 14$ by a concatenation-based induction. We also analyze the remaining base-code target weights $322,326,330,334$ in several restricted families, including four-block branches, affine-flat and structured inner corrections in a fixed Carlet-type Maiorana-McFarland outer shell, and sparse sums of degree-7 coordinate monomials. The residual analysis delineates several construction routes that cannot yield the four unresolved base-code weights, thereby sharpening the remaining $c=7$ spectrum problem.

Abstract: Let $C$ be an $[n,k,d]_q$ Griesmer code, where $q=p^f$ with $p$ prime, and write $e=ν_p(d)$. Ward conjectured that $C$ is $p^{\max\{0,e-f+1\}}$-divisible. In this paper, we prove this conjecture.

Abstract: We prove the MDS length bound for nontrivial irreducible cyclic codes of every composite length. The classical trace realization turns the MDS property into independence of elements of a multiplicative subgroup. Every nonidentity subgroup must have the full extension degree. This restriction yields length congruences, and the Frobenius-orbit description of the coefficient field gives an exact descent obstruction. A cyclotomic argument reduces each fixed dimension to finitely many parameters. For dimensions at most thirty, established geometric bounds reduce the alphabet to a small finite range; the remaining twelve parameter triples are excluded by explicit products of at most three determinant factors and a low-degree multiplier argument. An independent argument proves the composite-length theorem in arbitrary dimension. The standardness conclusion is stated separately as a conditional consequence of the classification statement of Feng, Hollmann, Li, and Xiang; the correct extension-field reduction retains a semilinear quotient. The general prime-length problem is not settled here. Neither length proof uses the automorphism classification or the recent odd-characteristic range announced by Fan.

Abstract: For an integer $k$ and a set of integers $L$, a $(k,L)$-system is a family of $k$-element sets such that the size of the intersection of any two distinct members belongs to $L$. Let $m(n,k,L)$ denote the maximum size of a $(k,L)$-system on a ground set of $n$ elements. In this work, we establish a close connection between the asymptotic growth of $m(n,k,L)$ and almost entropic matroids. As a consequence, we obtain a general computable upper bound on the asymptotics of $m(n,k,L)$ that unifies and strengthens all previously known upper bounds.

Abstract: In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~$\mathcal{O}(n^4 q^3)$ operations in~$\mathbb{F}_q$, where~$n$ is the length of the code and~$q$ is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.

Abstract: The classical theory of arcs in finite projective spaces provides a powerful geometric framework for studying maximum distance separable (MDS) codes and their possible lengths. In this paper, we investigate how this perspective extends to maximum sum-rank distance (MSRD) codes, whose geometric description involves systems of linear sets rather than individual projective points. Our main goal is to understand how the block structure of an MSRD code constrains its length. In dimension three, we determine the possible intersection patterns of lines with the associated linear sets and obtain explicit formulas for their characters and the weight distribution of the corresponding codes. These results lead to new length bounds and show that the block structure comes at a cost: the presence of a block of rank at least two reduces the maximum possible total length by at least $q-1$, and sufficiently long MSRD codes must be classical, that is, MDS codes over $\mathbb F_{q^m}$. We also prove that three-dimensional one-weight MSRD codes do not exist. In arbitrary dimension, we interpret shortening geometrically as projection and establish a general projection bound that extends classical counting arguments for arcs. This yields restrictions depending explicitly on the block profile and, for full-length blocks, identifies parameter ranges in which linearized Reed--Solomon codes attain the maximum possible number of blocks. Finally, we construct an exceptional three-dimensional MSRD code over $\mathbb F_9$ with three blocks of length two and propose a sum-rank analogue of the MDS conjecture.

Abstract: What is the covering radius of the Reed--Muller code RM(1,9) ? This is a long-standing open problem in cryptography and coding theory. In this paper, we resolve this problem, and prove that the covering radius of RM(1,9) is 242. We exclude nonlinearity 244 by obtaining a cubic Boolean function achieving a sharp Walsh $\ell^1$ bound. Its equality cases reduce either to an impossible cubic hyperplane restriction or to two homogeneous cubic forms in the Brier--Langevin classification. To exclude nonlinearity 243, we deduce the inequality ${\Vert W_g\Vert }_{1}+2|W_g(0)|\le 10368$, and then reduce either to a spectrum bounded by 24 or to the same expression to be at least 10496.

Abstract: Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

Abstract: We investigate the linear codes derived from the zero-divisor graph $Γ(R)$ of the finite local ring $R = \mathbb{F}_p[x]/\langle x^4 \rangle$ for an odd prime $p$. Using an equitable partition of $Z^*(R)$, we determine the parameters of the binary incidence code of $Γ(R)$ and construct induced bipartite subgraph codes achieving dual minimum distance $4$. Over $\mathbb{F}_p$, we parameterize the adjacency and Laplacian codes, derive the closed-form weight distribution of the Laplacian code via the MacWilliams identity, and establish its LCD property. Additionally, we determine the automorphism groups of the graph and its matrix codes. Finally, from extremal subgraphs of $Γ(R)$, we construct two families of Griesmer-optimal linear codes over $\mathbb{F}_p$, comprising a constant-weight minimal code and an optimal two-weight code.

Abstract: We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.

Abstract: Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

Abstract: We ask whether non-signaling correlations shared between the sender and receiver can increase the Rényi capacity of a classical channel. Non-signaling boxes form a strictly larger class than that of encoder and decoder pairs assisted by shared randomness, so the usual argument based on independent preprocessing and postprocessing is insufficient, and the constraints defining such boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We resolve this mismatch with a variational approach based on the Legendre transform, which recasts the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we prove that no non-signaling box can raise the Rényi capacity at any order, from order zero through the Shannon capacity to the limiting order at infinity. Consequently, non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

Abstract: In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+ε$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + γ}$ equations, for a small constant $γ$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$Ω(n)$ sum-of-squares lower bound, showing that ''[BKW03]-style'' algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.

Abstract: We revisit the claimed converse theorem for mismatched decoding over binary-input discrete memoryless channels (Balakirsky, 1995) and the subsequent work refuting this converse via a numerical counter-example (Scarlett, Somekh-Baruch, Martinez, and Guillén i Fàbregas, 2015). A notable gap in the existing understanding is that no concrete flaw was identified in Balakirsky's analysis. In this paper, Balakirsky's proof is "diagnosed", and it is demonstrated that (i) his permutation lemma is flawed regardless of the correctness of his combinatorial approximation lemma; (ii) there are at least two specific incorrect steps regarding restricted codes and selector sequences, and these appear to be unlikely to admit a local repair; and (iii) the proposition in which these incorrect steps are used is false in general.

Abstract: We give snakes that are longer than the previous best known in dimensions 13 through 20 and improve the general lower bound for every dimension $d \geq 21$. Our explicit snakes reach 371,711 edges in dimension 20. Twenty compatible paths in that cube allow generalisation to give snakes of length at least $(17/48)2^d$ for every $d \geq 21$. Their controlled overlaps allow copies to be joined across the layers of a larger cube without creating shortcuts. Four additional paths give the same bound for coils. We explain the construction, prove the joining rule, and then count its length. The finite paths and their required intersections are independently verifiable.

Abstract: This is an essentially derivative note, whose goal is to interpret the 'whole-cube' bound of OpenAI for binary codes in a possibly somewhat more accessible way. This is attained, in part, by connecting it to some previously known results. All of the heavy technical lifting in the interpretation below is also due to the OpenAI language models ChatGPT 5.6 and ChatGPT 6. With that, we hope that the statements of the main results, the ensuing discussion, and the arguments themselves may be of some interest.

Abstract: We study the asymptotic density of $\mathbb{F}_q$-point-free linear sections of geometrically irreducible projective varieties over finite fields. We then apply these results to rank-metric codes via determinantal varieties. Our approach recovers the known cases in which the density tends to $0$ or $1$ and determines the limit in the cases where it was previously unknown. To compute these previously unknown limits, we extend the notion of quasireflexivity to higher-dimensional varieties and show that determinantal varieties satisfy this property. This allows us to invoke the Chebotarev density theorem for varieties over finite fields to obtain the desired estimate.

Abstract: Chen and Xie recently proved, using the Ashikhmin--Barg lemma on minimal vectors, that every binary linear $[n,k,d]$ code with $k=n-2d+2+v$ ($v\ge 0$) has no codewords of weight in the interval $[2d-v,\,2d-1]$. Their argument uses two of the five basic properties of minimal vectors established by Ashikhmin and Barg (1998). In this note we utilize the third property, the disjoint-support decomposition of non-minimal codewords in binary codes, to generate a \emph{mirror} vanishing band on the other side of $2d$: if $A_{d+1}=\cdots=A_{d+t}=0$ for some $t\ge 1$ and $k\ge n-2d+1$, then $A_w=0$ for all $w\in[2d+1,\,2d+t]$. Combining the two bands, the number of nonzero weights of such a code is at most $n-d-v-2t+1$, improving the Chen--Xie bound $n-d+1-v$ by $2t$.

Abstract: The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established redundancy-seven range. We also prove the generalized Hamming-weight bound $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$, using an auxiliary-code criterion that converts a syndrome-space covering property into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

Abstract: The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.

Abstract: Let $\mathrm{RM}_q(r,m)$ denote the generalized Reed--Muller code of order $r$ and length $q^m$ over the finite field $\mathbb{F}_q$. We completely determine the weight spectra of $\mathrm{RM}_3(2m-i,m)$ for $i=3,4$, $\mathrm{RM}_4(3m-i,m)$ for $i=2,3$, $\mathrm{RM}_5(4m-4,m)$, and $\mathrm{RM}_7(6m-4,m)$, in the ranges of $m$ specified in the corresponding results. The proofs proceed by induction on $m$, using a sumset inclusion for GRM weight spectra together with results on low-weight codewords. The required base cases are established by computations in Magma and, for certain ternary cases, exact constraint solving with Z3.

Abstract: We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-λ,λ]$ for every fixed $λ>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $Θ_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.