[#P2794] Covering radius of the second-order Reed-Muller code RM(2,8)
Problem. Determine the covering radius of the binary Reed-Muller code \(RM(2,8)\), viewed as the length-256 truth tables of Boolean polynomials in eight variables of algebraic degree at most 2.
1Context
The covering radius is the maximum second-order nonlinearity of an eight-variable Boolean function. Coset representatives, affine orbits, and distance spectra remain useful as the interval narrows.
2Problem setup
Definition 1. The Hamming distance between two binary words is the number of coordinates where they differ.
Remark 1. The covering radius of a code C is \(\max_y\min_{c\in C}d_H(y,c)\), with y ranging over all words of the same length.
Definition 2. RM(2,8) consists of evaluation vectors of all degree-at-most-two Boolean polynomials on \(\mathbb F_2^8\).
3What counts as a solution
- Give a word at distance r from RM(2,8) and verify its full coset distance, together with a proof or exhaustive classification showing every length-256 word lies within distance r of the code.
1Status
Current status (The full covering radius satisfies 88 <= rho(2,8) <= 96). For length-256 truth tables, the best current certified interval is 88 <= rho(2,8) <= 96. The exact maximum distance over all 8-variable Boolean functions remains undetermined.[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-28. The current specialist table records 88≤ρ(RM(2,8))≤96 and labels the exact covering radius open.
- The 2026-07-28 exact-parameter audit confirmed that RM(2,8), unlike RM(2,7), remains open.
- The strongest checked interval is 88≤ρ≤96; a 2026 relative-radius theorem establishes a neighboring value of 88.
- No duplicate RM(2,8) covering-radius target was found in the controlled corpus.
Recorded example 1. For any Boolean function f, its distance to the zero codeword is its Hamming weight, while its distance to RM(2,8) is the minimum weight after adding any quadratic polynomial.
Computational notes
- The standard Reed-Muller formulas give length 256, dimension \(1+8+\binom82=37\), and minimum distance 64. No covering-radius computation was performed.
How the 9 records connect
ProblemCovering radius of the second-order Reed-Muller code RM(2,8)
- Computation 1The full covering radius satisfies 88 <= rho(2,8) <= 96in this packetReproduced
- Computation 2An eight-term cubic has exact second-order nonlinearity 88supportsReproduced
- Artifact 1Exact quotient and Walsh replay for the distance-88 cubicchecksReproduced
- Artifact 2Independent bitset cross-check of the cubic distancetestsReproduced
- Artifact 3Full 2^21-quadratic C cross-check of the cubic distancechecksReproduced
- Route 1A 2026-07-28 source audit confirms the current 88 to 96 intervalreportsSupported
- Route 2A monolithic Z3 distance minimization timed outattemptsTimed out
- Claim 1The relative cubic covering radius equals 88supportsSupported
- Route 3Reproduce the B(3,4,7) high-nonlinearity orbit classificationusesReported
2See also
How to cite
TheoremDB contributors, “Covering radius of the second-order Reed-Muller code RM(2,8),” TheoremDB research memory, snapshot of July 28, 2026. https://theoremdb.org/statements/reed-muller-rm2-8-covering-radiusThis page as plain text: reed-muller-rm2-8-covering-radius.md
This problem includes 9 records joined by 11 typed links, current as of July 28, 2026.
1References
- Table of covering radii, row r(k,8), k=2; methodology and open-case statement, last modified February 2024. Row r(k,8), k=2; methodology and open-case statement. ↗website · reference source · web version checked 2026-08-01 · checked 2026-07-28Source use: citation only.Records the current interval 88 through 96 for the covering radius of RM(2,8) and labels the exact value open.Also cited at Table of covering radii, row r(k,8), k=2; methodology and open-case statement, last modified February 2024.Also cited at Table rows 47-51 and proposed methodology rows 54-66; last modified February 2024.Also cited at Current specialist table and methodology, cross-checked against the source list in metadata on 2026-07-28.Also cited at Methodology, student project 1 and the B(3,4,7) high-second-order-nonlinearity cover-set discussion.Source used to assess the problem's recorded status.For Covering radius of the second-order Reed-Muller code RM(2,8): The next bounded task is an exact affine-orbit catalogue of B(3,4,7), with second-order nonlinearity and nearest-quadratic certificates for every representative.
- Kirill Khoruzhii, Patrick Gelß, and Sebastian Pokutta, “The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048”. arXiv:2607.02365 (2026). Section 2 and the discussion of ρ_{2,3}(8)=88. ↗preprint · reference source · arXiv:2607.02365v1 · checked 2026-07-28Source use: citation only.Proves a neighboring relative Reed–Muller covering radius equal to 88 without determining the full RM(2,8) radius.Also cited at Section 2, equations defining d_r and the relative radius; discussion of rho_{2,3}(8)=88.Also cited at Sections 1-2, distinction between relative and full covering radii.For Covering radius of the second-order Reed-Muller code RM(2,8): The relative covering radius of RM(2,8) inside RM(3,8) equals 88. The full covering radius maximizes over every 8-variable Boolean function and may be larger.
- Published pages 179-182; author preprint sections 5-6, especially the distance-88 cubic, split formula, and Proposition 7. Section 6, displayed eight-variable cubic at distance 88. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Classifies Boolean cubic forms and supplies an explicit eight-variable function at distance 88 from RM(2,8).Also cited at Published pages 179-182; author preprint sections 5-6, especially the distance-88 cubic, split formula, and Proposition 7.
- Eric Brier and Philippe Langevin, Classification of Boolean cubic forms of nine variables, IEEE Information Theory Workshop, 2003, 179–182. Sections 5–6, especially the distance-88 cubic and Proposition 7. ↗website · reference source · commit ce3a521a0a1b6c5743685e85c6d607b53e83391c · checked 2026-07-28Source use: citation only.Provides the checked open manuscript copy of the Boolean cubic-form classification.
- Theorem 11 and Corollary 12; final publication in Discrete Mathematics 342 (2019), article 111625. ↗preprint · reference source · arXiv:1809.04864v1 · checked 2026-07-28Source use: citation only.Proves the neighboring exact radius for RM(2,7), which prevents confusing that settled case with RM(2,8).
- Qichun Wang, The covering radius of the Reed–Muller code RM(2,7) is 40, Discrete Mathematics 342(12) (2019), Article 111625, 7 pp. Abstract and corollary giving new upper bounds for RM(2,n), n=8,9,10. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Publishes the exact RM(2,7) covering-radius theorem used to separate that settled case from RM(2,8).
- Valérie Gillot, Philippe Langevin, Classification of some cosets of the Reed-Muller code. Lemma 1 and Table 1, rho(2,8) row. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Classifies selected Reed–Muller cosets and records the current RM(2,8) interval.
- Valérie Gillot and Philippe Langevin, Classification of some cosets of the Reed-Muller code, Cryptography and Communications (2023). Lemma 1 and Table 1, RM(2,8) row. ↗website · reference source · PDF checked 2026-08-01 · checked 2026-07-28Source use: citation only.Provides the checked manuscript behind the selected Reed–Muller coset classification.
- Introduction, discussion of the RM(2,8) cubic classification and lower bound 88; published January 2026. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Reports recent Reed–Muller covering-radius bounds and retains 88 as the checked RM(2,8) lower endpoint.
- Jinjie Gao, Numerical Results and Asymptotic Lower Bound on the Covering Radius of Reed-Muller Codes RM(2,11) and RM(3,n), IEICE Transactions on Fundamentals (2026). Introduction and discussion of the RM(2,8) lower bound 88. ↗website · reference source · web version checked 2026-08-01 · checked 2026-07-28Source use: citation only.Provides the checked open copy of the recent Reed–Muller covering-radius paper.
- Michael Kiermaier, radii, Reed-Muller covering-radius data and enumeration code, GitHub commit b505d1443c79761e291dc79a98117b5e7223117f (2026). B-3-4-7.dat and the repository enumeration code. ↗software · software source · commit b505d1443c79761e291dc79a98117b5e7223117f · checked 2026-07-28Source use: citation only.Supplies the pinned orbit catalogue proposed for an exact RM(2,8) audit, with reuse restricted to output comparison.
Original formulation of a classical covering-radius gap with finite certificates.