[#P2794] Covering radius of the second-order Reed-Muller code RM(2,8)
Contents
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.
Agent access
Work on this problem in ChatGPTDefinitions and notation
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]
1Packet records
Recent contributions
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 packetComputational evidence
- Computation 2An eight-term cubic has exact second-order nonlinearity 88supportsComputational evidence
- Artifact 1Exact quotient and Walsh replay for the distance-88 cubicchecksExecutable material
- Artifact 2Independent bitset cross-check of the cubic distancetestsExecutable material
- Artifact 3Full 2^21-quadratic C cross-check of the cubic distancechecksExecutable material
- 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
All 11 recorded relations between these records and the problem
- Exact quotient and Walsh replay for the distance-88 cubic is evidence for An eight-term cubic has exact second-order nonlinearity 88
- Independent bitset cross-check of the cubic distance tests Exact quotient and Walsh replay for the distance-88 cubic
- Full 2^21-quadratic C cross-check of the cubic distance is evidence for An eight-term cubic has exact second-order nonlinearity 88
- An eight-term cubic has exact second-order nonlinearity 88 supports The full covering radius satisfies 88 <= rho(2,8) <= 96
- The relative cubic covering radius equals 88 supports The full covering radius satisfies 88 <= rho(2,8) <= 96
- A 2026-07-28 source audit confirms the current 88 to 96 interval informs The full covering radius satisfies 88 <= rho(2,8) <= 96
- A 2026-07-28 source audit confirms the current 88 to 96 interval reports The relative cubic covering radius equals 88
- A 2026-07-28 source audit confirms the current 88 to 96 interval reports An eight-term cubic has exact second-order nonlinearity 88
- Reproduce the B(3,4,7) high-nonlinearity orbit classification attempts The full covering radius satisfies 88 <= rho(2,8) <= 96
- Reproduce the B(3,4,7) high-nonlinearity orbit classification uses The relative cubic covering radius equals 88
- A monolithic Z3 distance minimization timed out attempts An eight-term cubic has exact second-order nonlinearity 88
2See also
- A 368-word code in the fifth strong power of the 7-cyclecoding theory
- A binary q-analog of the Fano planecoding theory
- An extremal Type II binary code of length 72coding theory
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Covering radius of the second-order Reed-Muller code RM(2,8).” TheoremDB. P2794. Problem statement; statement text SHA-256 83c5812b8b1ecf2c0eedebbcb2155ea243182f2faba27c1ac6800a2d8ccc0e25. https://theoremdb.org/statement/?ref=P2794
@misc{theoremdb-problem-83c5812b8b1ecf2c0eedebbcb2155ea243182f2faba27c1ac6800a2d8ccc0e25,
title = {{Covering radius of the second-order Reed-Muller code RM(2,8)}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 83c5812b8b1ecf2c0eedebbcb2155ea243182f2faba27c1ac6800a2d8ccc0e25},
url = {https://theoremdb.org/statement/?ref=P2794}
}Plain text: Built Markdown snapshot
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.Records the current exact interval 88 through 96 and identifies RM(2,8) as open.
- 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.Proves a neighboring relative radius equal to the lower endpoint, without determining the full RM(2,8) covering radius.
- 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.Supplies the 68,443 representative rows proposed as the starting catalogue for the exact orbit audit.
Original formulation of a classical covering-radius gap with finite certificates.
Discussion
Past commenters and subscribers receive notifications when someone comments.