# P2794: Covering radius of the second-order Reed-Muller code RM(2,8)

- ID: `P2794`
- Reference: `reed-muller-rm2-8-covering-radius`
- Page: https://theoremdb.org/statements/P2794
- Record maturity: Reviewed problem with recorded work

## 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.

### Problem setup

- **Definition.** The Hamming distance between two binary words is the number of coordinates where they differ.
- **Remark.** 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.** RM(2,8) consists of evaluation vectors of all degree-at-most-two Boolean polynomials on \(\mathbb F_2^8\).

### What 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.

## Status

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](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (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.

Write
\[
\rho(2,8)=\max_{F:\mathbb F_2^8\to\mathbb F_2}\min_{Q\in RM(2,8)}\operatorname{wt}(F+Q).
\]
The cubic in rm28-claim-cubic-witness-distance-88 has distance 88 from \(RM(2,8)\), so \(\rho(2,8)\geq 88\). Wang proves \(\rho(2,7)=40\) in Theorem 11 of the cited paper. The recursive inequality
\[
\rho(k,m)\leq \rho(k,m-1)+\rho(k-1,m-1)
\]
and the known value \(\rho(1,7)=56\) give
\[
\rho(2,8)\leq 40+56=96.
\]
Gillot and Langevin's current specialist page records the same interval and labels the second-order case in eight variables as open. A complete answer still needs either a global upper bound of 88 or an exhaustive classification that identifies a larger value in the interval.

### Background and intake notes

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.

- Original intake status: UNKNOWN: A specialist project page checked 2026-07-27 records the interval 88 through 96 and labels the case open.
- 2026-07-27: The initially considered RM(2,7) target was discarded because Wang proved its covering radius is 40 in 2019. The University of Toulon covering project lists RM(2,8) as 88-96 and still open.
- 2026-07-27: No equivalent RM(2,8) target was found in the earlier TheoremDB corpora or live prospecting set.
- Lower witnesses are Boolean functions far from every quadratic. Upper certificates may classify high-nonlinearity functions modulo affine transformations and addition of quadratics.

- Recorded example: 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.

### Other known results

- **Computation 2** (reproduced): The cubic f=abc+adg+afh+agh+bdh+beg+ceh+def has minimum distance exactly 88 from every 8-variable Boolean polynomial of degree at most two. [3](#reference-3)
- **Claim 1** (supported): 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. [2](#reference-2)

### Prior approaches

- **Route 1** (supported): A dated audit of six primary or specialist sources found current support for 88 <= rho(2,8) <= 96; the 2026 sources still treat 88 as a lower or relative cubic value. [1](#reference-1) [3](#reference-3) [4](#reference-4) [5](#reference-5) [6](#reference-6) [7](#reference-7) [8](#reference-8) [9](#reference-9) [10](#reference-10) [2](#reference-2)
- **Route 2** (timed out): Z3 Optimize did not certify the cubic's distance within 120 seconds; the quotient and Walsh reduction completed the same exact objective in a few seconds.

### Open directions

- **Route 3** (reported): 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. [1](#reference-1) [11](#reference-11)

### Runnable artifacts

- **Artifact 1** (reproduced): A deterministic standard-library program enumerates all 8,192 quotient representatives, checks the complete score histogram, and verifies a nearest quadratic by direct truth-table weight.
- **Artifact 2** (reproduced): A second implementation replaces Walsh transforms with 128-bit truth masks and exhaustive comparison against all 256 affine functions on each slice.
- **Artifact 3** (reproduced): A third exact implementation enumerates every homogeneous quadratic directly and decodes both slices against all 256 affine functions.

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `reed-muller-rm2-8-covering-radius`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Table of covering radii, row r(k,8), k=2; methodology and open-case statement, last modified February 2024. Table of covering radii, row r(k,8), k=2; methodology and open-case statement, last modified February 2024 https://langevin.univ-tln.fr/project/covering/covering.html
   - 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
   - website; reference source; web version checked 2026-08-01; checked 2026-07-28
   - Source use: citation_only
   - Records the current interval 88 through 96 for the covering radius of RM(2,8) and labels the exact value open.
   - 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.
2. <a id="reference-2"></a>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, equations defining d_r and the relative radius; discussion of rho_{2,3}(8)=88 https://arxiv.org/abs/2607.02365
   - Also cited at Sections 1-2, distinction between relative and full covering radii
   - preprint; reference source; arXiv:2607.02365v1; checked 2026-07-28
   - Source use: citation_only
   - Proves a neighboring relative Reed–Muller covering radius equal to 88 without determining the full RM(2,8) radius.
3. <a id="reference-3"></a>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 https://doi.org/10.1109/ITW.2003.1216724
   - Also cited at Published pages 179-182; author preprint sections 5-6, especially the distance-88 cubic, split formula, and Proposition 7
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Classifies Boolean cubic forms and supplies an explicit eight-variable function at distance 88 from RM(2,8).
4. <a id="reference-4"></a>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 https://citeseerx.ist.psu.edu/document?doi=ce3a521a0a1b6c5743685e85c6d607b53e83391c&repid=rep1&type=pdf
   - website; reference source; commit ce3a521a0a1b6c5743685e85c6d607b53e83391c; checked 2026-07-28
   - Source use: citation_only
   - Provides the checked open manuscript copy of the Boolean cubic-form classification.
5. <a id="reference-5"></a>Theorem 11 and Corollary 12; final publication in Discrete Mathematics 342 (2019), article 111625 https://arxiv.org/abs/1809.04864v1
   - preprint; reference source; arXiv:1809.04864v1; checked 2026-07-28
   - Source use: citation_only
   - Proves the neighboring exact radius for RM(2,7), which prevents confusing that settled case with RM(2,8).
6. <a id="reference-6"></a>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 https://doi.org/10.1016/j.disc.2019.111625
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Publishes the exact RM(2,7) covering-radius theorem used to separate that settled case from RM(2,8).
7. <a id="reference-7"></a>Valérie Gillot, Philippe Langevin, Classification of some cosets of the Reed-Muller code Lemma 1 and Table 1, rho(2,8) row https://doi.org/10.1007/s12095-023-00652-4
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Classifies selected Reed–Muller cosets and records the current RM(2,8) interval.
8. <a id="reference-8"></a>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 https://langevin.univ-tln.fr/project/agl8/ALCOCRYPT-paper.pdf
   - website; reference source; PDF checked 2026-08-01; checked 2026-07-28
   - Source use: citation_only
   - Provides the checked manuscript behind the selected Reed–Muller coset classification.
9. <a id="reference-9"></a>Introduction, discussion of the RM(2,8) cubic classification and lower bound 88; published January 2026 https://doi.org/10.1587/transfun.2025EAP1015
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Reports recent Reed–Muller covering-radius bounds and retains 88 as the checked RM(2,8) lower endpoint.
10. <a id="reference-10"></a>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 https://www.jstage.jst.go.jp/article/transfun/advpub/0/advpub_2025EAP1015/_pdf/-char/en
   - website; reference source; web version checked 2026-08-01; checked 2026-07-28
   - Source use: citation_only
   - Provides the checked open copy of the recent Reed–Muller covering-radius paper.
11. <a id="reference-11"></a>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 https://github.com/drmichko/radii/tree/b505d1443c79761e291dc79a98117b5e7223117f
   - software; software source; commit b505d1443c79761e291dc79a98117b5e7223117f; checked 2026-07-28
   - Source use: citation_only
   - Supplies the pinned orbit catalogue proposed for an exact RM(2,8) audit, with reuse restricted to output comparison.