CS Paper Radar

The Covering Radius of the Reed--Muller Code \texorpdfstring{$\RM(3,8)$}{RM(3,8)} is 56

Zhihang Zhao, Yansheng Wu

cs.IT ·submitted 2026-11-02 14:18 UTC · v1
theory

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.

Comment
35 pages,

Closest papers

Nearest neighbours by meaning across the whole index.

The Covering Radius of the Reed--Muller Code RM(1,9) is 242

cs.IT ·2026-10-13 ·Qichun Wang, Yueying Lou, Zifan Wang
similarity 0.65
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.

0.44

The covering radius of the first-order Reed-Muller code in nine variables is 242

cs.IT math.NTmath.CO ·2026-10-31 ·Yi Li
theory similarity 0.64
Abstract · 28 pages

We prove that the covering radius of the binary first-order Reed-Muller code RM(1,9) is exactly 242. Equivalently, the maximum nonlinearity of a Boolean function in nine variables is 242. Our proof combines a one-point rigidity theorem with a spectral and computational exclusion of the two larger candidate nonlinearities. We first show that every nine-variable Boolean function of nonlinearity 243 admits a unique one-point modification that raises its nonlinearity to 244: the point to be changed is the vector sum of its support. This part uses exact Walsh-update identities, integer interpolation, rigidity of a quadratic residue, and a sharp Walsh l1 estimate for cubic Boolean functions. To exclude nonlinearity 244, we use Parseval's identity and congruences of integral Walsh coefficients to force an exceptionally restricted spectrum. An associated cubic residue phase must attain the extremal Walsh l1 bound 10240. We eliminate one equality spectrum by hyperplane slicing; the other forces the original Boolean function from the signs of the cubic phase and yields a double-complement-pairing identity for its cubic top part. The classification of alternating trilinear forms over F2, an exact filter of their representatives, and two exhaustive enumerations of 218 quadratic supplements then rule out every remaining candidate. Together with the known construction attaining nonlinearity 242, these arguments establish the asserted covering radius.

0.12

Common zeros of homogeneous polynomials and the weight hierarchy of projective Reed-Muller codes

cs.IT math.ACmath.AG ·2026-11-05 ·Rodrigo San-José
theory similarity 0.64
Abstract

We determine the maximum number of common zeros in projective space of any set of linearly independent homogeneous polynomials of the same degree, when the degree is smaller than the cardinality of the finite field. This proves the conjecture of Beelen, Datta, and Ghorpade, resolving a longstanding problem on common zeros and determining the complete weight hierarchy of the corresponding projective Reed-Muller codes. The proof uses Green's hyperplane restriction bound, combined with a footprint argument that reduces the problem to the affine case solved by Heijnen and Pellikaan. Wei duality then determines the hierarchy in sufficiently large degrees, recovering the complete hierarchy in every degree for the projective plane. Finally, we prove an upper bound valid in every degree, and conjecture that it is always sharp.

0.13

Geometric Obstructions and Sharp Genus Dependence in LCD Scalings

cs.IT math.AG ·2026-11-03 ·Rahim Rahmati-Asghar
theory similarity 0.63
Abstract · All comments are welcome

We study the least pole order of a rational function whose nonzero evaluations scale a prescribed code to a Euclidean LCD code. A residue-one differential yields an obstruction for odd-dimensional one-point AG codes in characteristic two: for $C=C_L(D,aQ)$ with $0\le a<n$ and odd dimension, the threshold is at least $n+2g-a-1$. The obstruction uses alternating Gram matrices and does not require the scaled code to be self-orthogonal. For the dimension-three codes $C_L(D,(r+1)Q)$ on Hermitian curves over $\F_{r^2}$, $r=2^e\ge4$, we obtain \[ n+2g-r-2\leτ_D(C;Q)\le n+2g-3. \] Consequently the leading genus contribution is asymptotically sharp even in dimension three. On the elliptic curve $y^2+y=x^3$ over $\F_4$, we prove the exact dimension-three threshold $6$ by an explicit multiplier. For repetition codes on the Hermitian family, the threshold equals the general interpolation bound $n+2g-1$. The upper bounds use information sets and hold for $q>3k$, and for $q>2k$ in characteristic two.

0.07

Deep holes of full-length Reed--Solomon codes

cs.IT ·2026-10-21 ·Bocong Chen, Jing Huang
similarity 0.59
Abstract · 28 pages

For every prime power $q>19683$, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension $2\le k\le q-2$, with the characteristic-two cases stated explicitly. For odd $q$, the deep holes are precisely the words of degree $k$. For even $q$ and $k\ge3$, the same conclusion holds except for an additional family when $k=q-3$. In even characteristic and dimension two, every deep hole has a unique expression $a h(X)+bX+c$, where $a\ne0$ and $h$ is a normalized $o$-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.

0.53

Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric

cs.IT ·2026-10-12 ·Zhihao Zhu, Haojie Gu, Jun Zhang, Yu Li
similarity 0.59
Abstract

The deep hole problem is a fundamental problem in coding theory, and it has many important applications in code constructions and cryptography. The deep hole problem of Reed-Solomon codes has gained a lot of attention. As a generalization of Reed-Solomon codes under Hamming metric, we study the covering radius and deep holes of Hyperderivative Reed-Solomon (HRS) codes under the Niederreiter-Rosenbloom-Tsfasman (NRT) metric. We determine the NRT covering radius of HRS code and characterize its NRT deep holes via Maximum Distance Separable (MDS) extensions and polynomial remainder conditions. We further relate the enumeration of NRT deep holes to the characteristic polynomial of an associated hyperplane arrangement. We also provide three classes of explicit NRT deep-hole constructions, propose a Cheng-Murray type conjecture for HRS codes under the NRT metric and obtain a conditional low-layer description. Using these characterizations, we derive exact enumeration formulas in several special cases.

0.19

Hyper-derivative Algebraic Geometry Codes via Local Expansions

cs.IT ·2026-09-16 ·Xiaofeng Liu, Hengfeng Liu, Jun Zhang, Fang-Wei Fu, Chunming Tang
theory similarity 0.59
Abstract

In this paper, we develop a systematic construction framework of hyper-derivative algebraic geometry codes via local expansions, extending hyper-derivative Reed-Solomon codes from the rational function field to general algebraic function fields. Using the residue theorem, we determine their Euclidean duals and illustrate that the duals naturally reverse. We further give criteria for reverse self orthogonality and reverse self duality in terms of two classes of bilinear forms. Finally, we provide an asymptotic bound on the rate and relative distance via function field towers.

0.28

Logarithmic asymptotics for polynomial threshold functions

cs.DM cs.ITmath.CO ·2026-10-25 ·Martin Anthony
theory similarity 0.58
Abstract · 39 pages. Revised exposition and organisation, with expanded explanations. Main results and theorem statements unchanged

We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

0.12