The Weight Distribution of the Third-Order Reed–Muller Code of Length 2048
July 02, 2026
Abstract
We compute the weight distribution of the third-order Reed–Muller code \(\mathop{\mathrm{RM}}(3,11)\) of length \(2048\). The weight enumerator is assembled from the coset weight enumerators of \(f+\mathop{\mathrm{RM}}(2,10)\), evaluated for representatives of all \(3\,691\,560\) nonzero \(\mathop{\mathrm{GL}}(10,2)\)-orbits of Boolean cubic forms in ten variables. The computation rests on a structural theorem: a nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for a single orbit in each odd dimension. The same pass determines the second-order nonlinearity of every cubic form: the relative covering radius of \(\mathop{\mathrm{RM}}(2,10)\) in \(\mathop{\mathrm{RM}}(3,10)\) is \(408\), attained on \(179\) orbits. This raises the best known lower bound on the covering radius of \(\mathop{\mathrm{RM}}(2,10)\) from \(400\) to \(408\). A complementary heuristic search shows that the relative covering radius of \(\mathop{\mathrm{RM}}(6,10)\) in \(\mathop{\mathrm{RM}}(7,10)\) is at most \(32\), improving the previous bound of \(50\).
1 Introduction↩︎
The weight distributions of the Reed–Muller codes \(\mathop{\mathrm{RM}}(r,m)\) [1], [2] are a classical subject of coding theory, yet they are known in closed form only for orders \(r\leqslant 2\) [3] and, through the MacWilliams identities, for the dual orders \(r\geqslant m-3\) (see [4] for a survey). Beyond these layers, general results cover only the low-weight range [5], and complete distributions are known only from individual computations. For the third-order codes the known cases form a chain of length-doubling steps: \(\mathop{\mathrm{RM}}(3,7)\) [6], \(\mathop{\mathrm{RM}}(3,8)\) [7], [8], \(\mathop{\mathrm{RM}}(3,9)\) [9], and \(\mathop{\mathrm{RM}}(3,10)\) [10]; recently the fourth-order code \(\mathop{\mathrm{RM}}(4,9)\) of length \(512\) was enumerated [11]. This paper computes the next step of the chain, the weight distribution of the third-order Reed–Muller code \(\mathop{\mathrm{RM}}(3,11)\) of length \(2048\) (Tab. 1).
The route is the Sarwate-type recursion [8], [11]: the weight enumerator of \(\mathop{\mathrm{RM}}(3,m+1)\) is the sum of squared coset weight enumerators of \(f+\mathop{\mathrm{RM}}(2,m)\) over all cubic forms \(f\), and since a coset enumerator depends only on the \(\mathop{\mathrm{GL}}(m,2)\)-orbit of \(f\), the sum collapses to orbit representatives weighted by orbit sizes (Sec. 2). Every computation in the chain therefore rests on a classification one dimension lower: Hou classified the cubic forms for \(m\leqslant 8\) [12], the case \(m=9\) was classified in [10], [13], and the fourth-order computation [11] uses the classifications of quartic forms in eight variables and of the cosets of \(\mathop{\mathrm{RM}}(2,7)\) in \(\mathop{\mathrm{RM}}(4,7)\) [14]. For \(m=10\) the required input became available only recently: the classification of Boolean cubic forms in ten variables [15], which provides representatives and stabilizer orders for all \(3\,691\,560\) nonzero \(\mathop{\mathrm{GL}}(10,2)\)-orbits.
The classification alone does not make the computation feasible; the concluding remarks of [11] name the per-coset cost as the principal obstacle to any progress beyond length \(512\). The split formula of Brier and Langevin [10] evaluates one coset enumerator by an outer enumeration over the homogeneous quadratic forms one dimension lower, \(2^{36}\) forms for \(m=10\), which is out of reach at the scale of the catalog. The second ingredient of this paper is a structural theorem: every nondegenerate Boolean cubic form admits a nondegenerate hyperplane restriction, except for one orbit in each odd dimension (Thm. 1). Splitting along such a restriction saves a factor of \(2^m\) in the enumeration, \(2^{26}\) instead of \(2^{36}\) cosets per orbit at \(m=10\). With this speedup the full catalog pass takes about \(65\) CPU-years and yields the coset weight enumerator of every orbit (Sec. 3).
The lowest nonzero coefficient of the coset enumerator of \(f\) is its second-order nonlinearity \(d_2(f)\), a long-studied quantity in the covering-radius literature [16] and in cryptographic Boolean function analysis, and more recently a measure of Clifford approximability in fault-tolerant quantum compilation [17]. Its worst case over cubic forms is the relative covering radius \(\rho_{2,3}(m)\) of \(\mathop{\mathrm{RM}}(2,m)\) in \(\mathop{\mathrm{RM}}(3,m)\): the value \(\rho_{2,3}(6)=18\) goes back to Schatz [18], the values \(40\) and \(88\) for \(m=7,8\) follow from the classification in at most eight variables [12], and \(\rho_{2,3}(9)=196\) was computed in [10]. The enumerator pass determines \(d_2\) on every orbit and hence \(\rho_{2,3}(10)=408\), attained on \(179\) orbits, listed in Tab. ¿tbl:tab:rep?. This also raises the best known lower bound on the covering radius of \(\mathop{\mathrm{RM}}(2,10)\) from \(400\) [19] to \(408\) (Sec. 6).
Two further results accompany the computation. We prove a bound (Thm. 4) for cubic forms of alternating rank \(r\), which forces rank at least \(6\) on the extremal orbits and describes the correlation between Clifford approximability and non-Clifford resource cost [15], [17], [20]. We develop a local-search heuristic that produces explicit upper-bound certificates, one correction per orbit, reproducing \(\rho_{2,3}(10)\leqslant 408\) at roughly a thousandth of the cost of the enumerator pass; applied to degree-seven forms, it yields \(\rho_{6,7}(10)\leqslant 32\), improving the bound of \(50\) [21].
2 Reed–Muller Codes↩︎
For \(0\leqslant r\leqslant m\), the Reed–Muller code \(\mathop{\mathrm{RM}}(r,m)\) consists of the Boolean polynomials of degree at most \(r\) in \(m\) variables, reduced modulo \(x_j^2=x_j\) and read as functions \(\mathbb{F}_2^m\to\mathbb{F}_2\). Listing its \(2^m\) values turns a Boolean function into a vector in \(\mathbb{F}_2^{2^m}\), so \(\mathop{\mathrm{RM}}(r,m)\) is a linear code, with the lower-order codes as nested subcodes (Fig. 1a). The weight of a Boolean function counts its support, \[\mathop{\mathrm{wt}}(f)=|\{x\in\mathbb{F}_2^m: f(x)=1\}|,\] and its distance to \(\mathop{\mathrm{RM}}(r,m)\), \[d_r(f)=\min_{q\in\mathop{\mathrm{RM}}(r,m)}\mathop{\mathrm{wt}}(f+q),\] is the \(r\)-th order nonlinearity of \(f\); the case \(r=2\) gives the second-order nonlinearity \(d_2\). The worst case of \(d_r\) over the next-order code is the relative covering radius of \(\mathop{\mathrm{RM}}(r,m)\) in \(\mathop{\mathrm{RM}}(r+1,m)\), \[\rho_{r,r+1}(m)=\max_{f\in\mathop{\mathrm{RM}}(r+1,m)} d_r(f).\] Maximizing over all Boolean functions instead gives the covering radius \(\rho_r(m) \geqslant\rho_{r,r+1}(m)\) of \(\mathop{\mathrm{RM}}(r,m)\). The main covering-radius target of this paper is \(\rho_{2,3}(10)\); the cocubic value \(\rho_{6,7}(10)\) appears in Sec. 5.
Adding any quadratic to \(f\) leaves \(d_2(f)\) unchanged, so \(d_2\) descends to the quotient \(\mathop{\mathrm{RM}}^*(3,m)=\mathop{\mathrm{RM}}(3,m)/\mathop{\mathrm{RM}}(2,m)\), identified with the homogeneous cubic forms. Two cubic forms are \(\mathop{\mathrm{GL}}(m,2)\)-equivalent when \[f_1\sim f_2 \;\Leftrightarrow\;\exists A\in\mathop{\mathrm{GL}}(m,2): f_1(x)\mathrel{\smash[t]{\overset{3}{=}}} f_2(Ax),\] where \(g\mathrel{\smash[t]{\overset{k}{=}}}h\) denotes equality of the degree-\(k\) homogeneous parts. Weight is \(\mathop{\mathrm{GL}}(m,2)\)-invariant, so \(d_2\) is constant on orbits. For \(m=10\) there are \(3\,691\,560\) nonzero orbits, cataloged in [15], whose representatives we use throughout. The stabilizer of a form is \[\mathop{\mathrm{St}}(f)=\{A\in\mathop{\mathrm{GL}}(m,2): f(Ax)\mathrel{\smash[t]{\overset{3}{=}}}f(x)\},\] and its orbit has size \(|\mathop{\mathrm{GL}}(m,2)|/|\mathop{\mathrm{St}}(f)|\). We write representatives in the monomial notation of [15]: a string \(ijk\) denotes \(x_ix_jx_k\) and strings are summed over \(\mathbb{F}_2\), so for instance \(025+034\) means \(x_0x_2x_5+x_0x_3x_4\).
For \(u\in\mathbb{F}_2^m\) the finite difference \(\Delta_u f(x)=f(x+u)+f(x)\) lowers the degree by one. The radical \[\mathop{\mathrm{Rad}}(f)=\{u\in\mathbb{F}_2^m:\Delta_u f\mathrel{\smash[t]{\overset{2}{=}}}0\}\] collects the directions along which \(f\) reduces. A cubic form is nondegenerate when \(\mathop{\mathrm{Rad}}(f)=0\).
The weight distribution of \(\mathop{\mathrm{RM}}(3,m+1)\), recorded by \[W_{\mathop{\mathrm{RM}}(3,m+1)}(z)=\sum_{f\in\mathop{\mathrm{RM}}(3,m+1)} z^{\mathop{\mathrm{wt}}(f)},\] is the main quantity of this paper. Following [8], [10], it is determined by the coset weight enumerators of the \(\mathop{\mathrm{GL}}(m,2)\)-orbits in \(\mathop{\mathrm{RM}}^*(3,m)\). The coset weight enumerator of a Boolean function \(f\) is \[W_f(z)=\sum_{q\in\mathop{\mathrm{RM}}(2,m)} z^{\mathop{\mathrm{wt}}(f+q)}, \label{eq:coset-enum}\tag{1}\] and its lowest nonzero exponent is \(d_2(f)\). Weights are \(\mathop{\mathrm{GL}}(m,2)\)-invariant and \(W_f\) is unchanged by adding a quadratic to \(f\), so \(W_f\) depends only on the \(\mathop{\mathrm{GL}}(m,2)\)-orbit of \(f\). The reduction then reads \[W_{\mathop{\mathrm{RM}}(3,m+1)}(z)=\sum_{f}\frac{|\mathop{\mathrm{GL}}(m,2)|}{|\mathop{\mathrm{St}}(f)|}\,W_f(z)^2, \label{eq:wd-reduction}\tag{2}\] summed over orbit representatives \(f\), with the zero orbit contributing \(W_{\mathop{\mathrm{RM}}(2,m)}(z)^2\). For \(m=10\) the coset enumerators of the \(3\,691\,561\) orbits thus give the complete \(\mathop{\mathrm{RM}}(3,11)\) weight distribution (Tab. 1).
3 Coset Weight Enumerators↩︎
In this section we evaluate the coset weight enumerator 1 for every nonzero orbit representative of the catalog [15]. The zero orbit contributes the classical weight distribution of \(\mathop{\mathrm{RM}}(2,10)\) [3], so by 2 this data assembles into the weight distribution of \(\mathop{\mathrm{RM}}(3,11)\). The lowest nonzero exponent of each enumerator is the value of \(d_2\) on its orbit, so the same pass also determines \(\rho_{2,3}(10)\) and the extremal orbits.
The enumerator of a single orbit reduces to affine coset enumerators. Fix a linear coordinate \(t\) and write \(x=(t,y)\) with \(y\in\mathbb{F}_2^{m-1}\). The cubic form has a unique split \[f(t,y)=g(y)+tp(y),\] where \(g\in\mathop{\mathrm{RM}}^*(3,m-1)\) is the restriction of \(f\) to the hyperplane \(t=0\) and \(p\in\mathop{\mathrm{RM}}^*(2,m-1)\). A quadratic correction \(q\in\mathop{\mathrm{RM}}(2,m)\) is determined by a homogeneous quadratic form \(h\in\mathop{\mathrm{RM}}^*(2,m-1)\) and two affine corrections \(a_0,a_1\in\mathop{\mathrm{RM}}(1,m-1)\) on the two slices, \[f(t,y)+q(t,y)=\left\{\begin{align} &g(y)+h(y)+a_0(y), & t&=0,\\ &g(y)+p(y)+h(y)+a_1(y), & t&=1, \end{align}\right.\] and conversely every triple \((h,a_0,a_1)\) arises from a unique \(q\). Thus, if \[A_u(z)=\sum_{a\in\mathop{\mathrm{RM}}(1,m-1)} z^{\mathop{\mathrm{wt}}(u+a)}\] is the affine coset enumerator of a Boolean function \(u\) on \(\mathbb{F}_2^{m-1}\), then the split gives [10] \[W_f(z)=\sum_{h\in\mathop{\mathrm{RM}}^*(2,m-1)} A_{g+h}(z)\,A_{g+p+h}(z). \label{eq:split-weight-enumerator}\tag{3}\] The weights \(\mathop{\mathrm{wt}}(u+a)\) over an affine coset are read off the Walsh spectrum of \(u\), so each factor is computed by a fast Walsh–Hadamard transform on \(2^{m-1}\) points. For \(m=10\), the split reduces the outer enumeration from the \(|\mathop{\mathrm{RM}}(2,10)|=2^{56}\) corrections \(q\) to the \(|\mathop{\mathrm{RM}}^*(2,9)|=2^{36}\) forms \(h\). Whenever the lowest nonzero bin of \(W_f\) is attained, we keep a triple \((h,a_0,a_1)\) attaining it, which reconstructs an explicit quadratic correction \(q\) with \(\mathop{\mathrm{wt}}(f+q)=d_2(f)\).
The product in 3 is unchanged under two translations of \(h\). First, replacing \(h\) by \(h+p\) swaps the two factors. Second, write \(\Delta_i u=u(y+e_i)+u(y)\) for a coordinate direction \(e_i\) of the \(y\)-space; since \(A_u\) is invariant under translations of \(y\) and under adding affine functions, replacing \(h\) by \(h+\Delta_i g\) leaves both factors unchanged. Therefore the product is constant on the cosets of \[V_f=\langle p,\Delta_0 g,\ldots,\Delta_{m-2}g\rangle\subseteq\mathop{\mathrm{RM}}^*(2,m-1),\] and 3 factors as \[W_f(z)=|V_f|\sum_{h\in\mathop{\mathrm{RM}}^*(2,m-1)/V_f} A_{g+h}(z)\,A_{g+p+h}(z), \label{eq:quotient-enumerator}\tag{4}\] with one representative \(h\) chosen from each coset of \(V_f\).
The size of the quotient is controlled by the radical of the slice: for a nondegenerate form \(f\), every split satisfies \(\dim V_f=m-\dim\mathop{\mathrm{Rad}}(g)\) (App. 7.1), so a split with nondegenerate \(g\) has \(\dim V_f=m\) and saves a factor \(2^m\) in the enumeration. The following theorem guarantees that such a split exists.
Theorem 1. Every nondegenerate Boolean cubic form on \(\mathbb{F}_2^m\) has a nondegenerate hyperplane restriction, except for one orbit in each odd dimension: the forms equivalent to \(f_*(x)=x_0(x_1x_2+x_3x_4+\ldots+x_{m-2}x_{m-1})\) have no nondegenerate hyperplane restriction.
The proof is given in the Appendix. The dimension \(m=10\) is even, so there is no exception, and the evaluation of 4 runs over \(2^{26}\) coset representatives instead of \(2^{36}\) forms for every nondegenerate orbit; without this reduction the full catalog pass would be out of reach. Degenerate forms need no separate treatment: the \(348\) degenerate nonzero orbits, lifted from the orbits in dimension at most \(9\), are processed by the same computation with a smaller \(V_f\) and a correspondingly larger quotient.
We evaluated 4 for all \(3\,691\,560\) nonzero orbit representatives. All timings in this paper are summed single-thread CPU times measured on \(48\)-core Intel Xeon Gold 6246 nodes. The pass is trivially parallel across orbits and took \(64.7\) CPU-years, averaging \(9.2\) CPU-minutes per orbit; the degenerate orbits account for only \(126\) CPU-hours of this total. Two checks support the result: the same computation one dimension lower reproduces the known weight distribution of \(\mathop{\mathrm{RM}}(3,10)\) [10], and the coefficients of the assembled enumerator sum to \(2^{232}=|\mathop{\mathrm{RM}}(3,11)|\). Combining the enumerators via 2 , with the orbit sizes \(|\mathop{\mathrm{GL}}(10,2)|/|\mathop{\mathrm{St}}(f)|\) taken from the catalog [15] and the zero orbit contributing \(W_{\mathop{\mathrm{RM}}(2,10)}(z)^2\), gives the main result.
Theorem 2. The weight distribution of the third-order Reed–Muller code of length \(2048\) is as given in Tab. 1.
The lowest nonzero bin of each coset enumerator is the value of \(d_2(f)\) on its orbit. The maximum over the catalog is \(408\), attained on \(179\) orbits; their representatives are listed in Tab. ¿tbl:tab:rep? together with the kissing number \[K=|\{q\in\mathop{\mathrm{RM}}(2,10):\mathop{\mathrm{wt}}(f+q)=408\}|.\] All \(179\) forms are nondegenerate, so \(|V_f|=2^{10}\) and every \(K\) is divisible by \(2^{10}\); the table lists \(K/2^{10}\).
Theorem 3. The relative covering radius of \(\mathop{\mathrm{RM}}(2,10)\) in \(\mathop{\mathrm{RM}}(3,10)\) is \(408\).
4 Connection with Alternating Rank↩︎
We now relate \(d_2\) to the alternating rank (arank) of a cubic form, defined [15] as the smallest \(r\) such that \[f(x)\mathrel{\smash[t]{\overset{3}{=}}}\sum_{t=1}^r u_t(x)v_t(x)w_t(x)\] for linear forms \(u_t,v_t,w_t\). Both invariants have natural readings in fault-tolerant quantum compilation: \(\mathop{\mathrm{arank}}(f)\) is the non-Clifford cost of realizing the phase polynomial \((-1)^{f(x)}\) [17], and \(d_2(f)\) measures its approximability by a Clifford. They quantify distance from the Clifford layer in complementary senses. The bound below makes one direction precise: adding a rank-one cubic to \(f\) can only increase \(d_2(f)\) by a controlled amount.
Lemma 1. Let \(f\) be a Boolean function on \(\mathbb{F}_2^m\). Then \(d_2(f+\varphi) \leqslant 2^{m-3}+\frac{3}{4} d_2(f)\) for every cubic form \(\varphi\) of alternating rank one.
Proof. Write \(\varphi=\ell_1\ell_2\ell_3\) with independent linear forms. Let \(q\in\mathop{\mathrm{RM}}(2,m)\) attain \(d_2(f)\), so \(E=\{x:f(x)+q(x)=1\}\) has size \(|E|=d_2(f)\). For each \(\alpha=(\alpha_1,\alpha_2,\alpha_3)\in\mathbb{F}_2^3\), define \[\varphi_\alpha=(\ell_1+\alpha_1)(\ell_2+\alpha_2)(\ell_3+\alpha_3).\] The cubic part of \(\varphi_\alpha\) equals \(\varphi\), so \(\varphi+\varphi_\alpha\in\mathop{\mathrm{RM}}(2,m)\). Its support is the cell \(C_\alpha=\{x:\ell_i(x)=1+\alpha_i,\;i=1,2,3\}\), one of eight cells of size \(2^{m-3}\) partitioning \(\mathbb{F}_2^m\). Adding \(\varphi_\alpha\) to \(f+q\) flips values on \(C_\alpha\), so \[d_2(f+\varphi)\leqslant\mathop{\mathrm{wt}}(f+q+\varphi_\alpha)=|E|+2^{m-3}-2|C_\alpha\cap E|.\] The eight intersections \(C_\alpha\cap E\) partition \(E\), so some has size at least \(|E|/8\), giving \[d_2(f+\varphi)\leqslant 2^{m-3}+\tfrac{3}{4}|E|,\] as claimed. ◻
A cubic form of alternating rank \(r\) is a sum of \(r\) arank-1 cubics, so iterating Lemma 1 gives a closed-form bound.
Theorem 4. Let \(f\) be a Boolean cubic form on \(\mathbb{F}_2^m\) of alternating rank \(r\). Then its second-order nonlinearity satisfies \(d_2(f) \leqslant 2^{m-1}\left(1-\left(\frac{3}{4}\right)^r\right)\).
Proof of Theorem 4. Put \(f_k=\varphi_1+\cdots+\varphi_k\) and \(D_k=d_2(f_k)\), where each \(\varphi_i\) has alternating rank one. Since \(D_0=0\), Lemma 1 gives \(D_k\leqslant 2^{m-3}+\frac{3}{4}D_{k-1}\). Iterating this recurrence yields \[D_r\leqslant 2^{m-3}\sum_{j=0}^{r-1}\left(\frac{3}{4}\right)^j =2^{m-1}\left(1-\left(\frac{3}{4}\right)^r\right).\] Since \(D_r=d_2(f)\), the result follows. ◻
For any cubic form \(f\) with \(d_2(f)=408\), Theorem 4 forces \(\mathop{\mathrm{arank}}(f)\geqslant 6\). Together with the maximum \(\mathop{\mathrm{arank}}=7\) in \(m=10\) [15], this gives \(\mathop{\mathrm{arank}}(f)\in\{6,7\}\). The dimension \(m=10\) is the first for which the bound admits more than one value: in dimensions \(m\leqslant 9\), substituting \(\rho_{2,3}(m)\) [10], [12], [18] forces \(\mathop{\mathrm{arank}}(f)\) equal to the maximum value attained in that dimension [15]. Both possibilities occur at \(m=10\): of the \(179\) orbits with \(d_2=408\) found in Sec. 3, \(177\) have \(\mathop{\mathrm{arank}}=7\) and \(2\) have \(\mathop{\mathrm{arank}}=6\) (Tab. ¿tbl:tab:rep?).
5 Heuristic Upper Bounds↩︎
The computation of Sec. 3 settles \(m=10\), but its cost is dominated by the \(2^{26}\)-fold enumeration repeated on every orbit. An upper bound on the covering radius needs much less: a single correction \(q\) with small \(\mathop{\mathrm{wt}}(f+q)\) per orbit is a certificate, found by local search and verified by one weight evaluation. This section describes such a search. It reproduces the bound \(\rho_{2,3}(10)\leqslant 408\) at roughly a thousandth of the cost of the enumeration pass, and it extends to settings where no enumeration is available: applied to degree-seven forms, it yields \(\rho_{6,7}(10)\leqslant 32\), improving the previous bound of \(50\) [21].
For a fixed representative \(f\), the coefficients of a correction \(q\in\mathop{\mathrm{RM}}(2,10)\) form a \(56\)-dimensional vector: one constant, \(10\) linear, and \(45\) quadratic coefficients. The local search varies only the nonconstant coordinates; whenever a candidate is evaluated, the constant term is set to the value giving the smaller \(\mathop{\mathrm{wt}}(f+q)\). The effective search space is thus \(\mathbb{F}_2^{55}\), indexed by the linear and quadratic monomials.
We initialize each search at \(q=0\). The baseline is one-flip greedy descent: at each step we try all single coefficient flips and accept the one giving the largest decrease of \(\mathop{\mathrm{wt}}(f+q)\), stopping when no improving flip remains. Three extensions improve this descent. First, a \(\tau\)-move flips any nonempty set of at most \(\tau\) coefficients. Second, after reaching a local endpoint, a random kick (\(k\) random \(\tau\)-moves) followed by a new descent gives, after \(i\) iterations, an iterated local search (ILS). Third, instead of keeping only the best improving move, one can keep the best \(w\) improving descendants and continue from this beam. The best-performing routine combines all three ideas and is specified by the parameter tuple \((\tau,w,i,k)\).
For calibration we used a hard sample of \(10^4\) catalog representatives. Preliminary runs showed that reaching weight \(408\) was relatively easy, whereas the threshold \(400\) produced a useful hard tail. We therefore built the sample from representatives for which a stronger but slower preliminary search had already found a correction of weight \(400\), and measured how quickly the tested routines could rediscover such a correction; an instance was called unresolved if the best correction found still had weight greater than \(400\). Fig. 1b plots the unresolved fraction against the running time for greedy descent, beam descent, ILS, and the combined \((\tau,w,i,k)\) search; for the combined search we swept the relevant \((w,i)\) choices and kept the best points at each time scale. The comparison showed that \(\tau=2\) is preferable at very small budgets, while \(\tau=3\) gives a better hard tail once more time is available, so the combined search with \(\tau=3\) was used for the full catalog pass.
The full pass with \((\tau,w,i,k)=(3,64,24,1)\) found a correction of weight at most \(408\) for every one of the \(3\,691\,560\) nonzero representatives in \(538\) CPU-hours, about three orders of magnitude below the enumeration pass of Sec. 3, and left \(3038\) representatives on the boundary \(\mathop{\mathrm{wt}}(f+q)=408\). A second pass on the boundary with a longer ILS part \(i=384\) and larger kicks \(k=4\) reduced the boundary to \(258\) representatives in another \(14\) CPU-hours. The enumerators measure how tight this cheap search is: of the \(258\) orbits where it stalled at \(408\), the \(179\) orbits of Tab. ¿tbl:tab:rep? indeed have \(d_2(f)=408\), while the remaining \(79\) have \(d_2(f)<408\).
The same framework gives the cocubic bound. Here the corrections range over \(\mathop{\mathrm{RM}}(6,10)\). Complementing monomials [21] identifies the \(\mathop{\mathrm{GL}}(10,2)\)-orbits in \(\mathop{\mathrm{RM}}^*(7,10)\) with those in \(\mathop{\mathrm{RM}}^*(3,10)\), so the same catalog provides all \(3\,691\,560\) degree-seven representatives. The combined search with corrections in \(\mathop{\mathrm{RM}}(6,10)\) found, for every representative \(g\in\mathop{\mathrm{RM}}^*(7,10)\), a polynomial \(p\in\mathop{\mathrm{RM}}(6,10)\) with \(\mathop{\mathrm{wt}}(g+p)\leqslant 32\).
Lemma 2. The relative covering radius of \(\mathop{\mathrm{RM}}(6,10)\) in \(\mathop{\mathrm{RM}}(7,10)\) is at most \(32\).
The cocubic pass took \(1705\) CPU-hours. The move set, adapted to the degree-seven geometry, is described in App. 7.2.
| \(w\) | number of codewords of weight \(w\) |
|---|---|
| \(0\) | \(1\) |
| \(256\) | \(407647768\) |
| \(384\) | \(98572491484544\) |
| \(448\) | \(276678901812617216\) |
| \(480\) | \(20615149353221226496\) |
| \(496\) | \(61905903043104210944\) |
| \(512\) | \(376732003274980265308\) |
| \(528\) | \(61905903043104210944\) |
| \(544\) | \(36067676304128622985216\) |
| \(576\) | \(4744067074463987615916032\) |
| \(592\) | \(58004870978198589344317440\) |
| \(608\) | \(1337472133556209119154667520\) |
| \(624\) | \(9396613326131873902296563712\) |
| \(640\) | \(224515947039561245253371260800\) |
| \(656\) | \(5830645939509459951889648975872\) |
| \(664\) | \(2419077324635505387171301294080\) |
| \(672\) | \(143171775339255975773371298217984\) |
| \(680\) | \(118534788907139763971393763409920\) |
| \(688\) | \(4172133049353846806513019732885504\) |
| \(696\) | \(6530702417407652710233456393584640\) |
| \(704\) | \(142049722384193638439855542034857984\) |
| \(712\) | \(370985666710560047000945480957952000\) |
| \(720\) | \(6572128354504685192324577309902241792\) |
| \(728\) | \(28716300050295011531014790520420433920\) |
| \(736\) | \(415629184674851549258147208655812952064\) |
| \(744\) | \(2690951593078403784716729428137071345664\) |
| \(752\) | \(37827275484769393002546972405932606095360\) |
| \(760\) | \(370900717708670977732674519658689233682432\) |
| \(768\) | \(5505529296214564743102269157190400156746664\) |
| \(776\) | \(79894247600845975291315175037253158124388352\) |
| \(784\) | \(1450305177493270675359691374214264637850910720\) |
| \(792\) | \(29235356704790566516562551934810916714341990400\) |
| \(800\) | \(665799808379784560217854189229920478427489501184\) |
| \(808\) | \(16063992125312051655233396041061195367979885264896\) |
| \(816\) | \(389343899216758993477153060624106334133347655090176\) |
| \(824\) | \(8999235314122324085793822909334985019312993120288768\) |
| \(832\) | \(191323551649196821711001947792058498033273954293481472\) |
| \(840\) | \(3658740594851885600503798449378675081425867112456388608\) |
| \(848\) | \(62180730085983850326083175198032893774117004267936022528\) |
| \(856\) | \(933627921643138541428942307297065262293476936162893365248\) |
| \(864\) | \(12352904069973355408081004302523980802074961354772346568704\) |
| \(872\) | \(143893873726630427501277688558916646342435284778499147038720\) |
| \(880\) | \(1475434974947081710061936957117530055868461154884705079787520\) |
| \(888\) | \(13318672685563145171399602295039475393147723949626043926577152\) |
| \(896\) | \(105868711887026301874770702718612016167682651408928401326236416\) |
| \(904\) | \(741226717029475749508906553789588949003364241669009433251807232\) |
| \(912\) | \(4572123337168224454714897939810929009585250051627595597537607680\) |
| \(920\) | \(24852350650395129270609343467555813365645108334460498873040240640\) |
| \(928\) | \(119066951769505173151986670780366771667129702286785938434899836928\) |
| \(936\) | \(502890594559615896984236136146693696560200753886279445577002385408\) |
| \(944\) | \(1872800847399495130252973899847591197256947718238294722030933639168\) |
| \(952\) | \(6150577569231431151720935138862873464324233440424302381575971012608\) |
| \(960\) | \(17815991389962934481252993676594060919773199784241432513439128895488\) |
| \(968\) | \(45522975052166290589248064985562854640499044441971806982761147793408\) |
| \(976\) | \(102619006074996608740719830566521478416265414163140030900851676545024\) |
| \(984\) | \(204100811417817928738018318757436575622758854101050048337198119387136\) |
| \(992\) | \(358193705074942017878606080764562076052212316814353868657935396110336\) |
| \(1000\) | \(554724454472328610642650250933921456820000687270430933160620818694144\) |
| \(1008\) | \(758134074338700783303792829592026102708636982915591852455410408620032\) |
| \(1016\) | \(914409270550460874661954063324503188329102135989979060750359088594944\) |
| \(1024\) | \(973354525080350422090405188363407729099289656148339075855691911557574\) |
6 Discussion↩︎
Theorem 1 is not specific to \(m=10\): it guarantees the full \(2^m\) quotient in every dimension, up to the single exceptional orbit in odd ones. At \(m=11\) this cuts the coset enumeration from \(2^{45}\) homogeneous quadratic forms to \(2^{34}\) cosets, which is feasible per representative. For comparison, the current record \(\rho_2(11)\geqslant 856\) was established by computing \(d_2=856\) for the cubic form \(\mathrm{Tr}(x^7)\) on \(\mathop{\mathrm{GF}}(2^{11})\), reported as taking about six days [22]; the quotient enumeration of Sec. 3 produces the full coset weight enumerator of the same form in \(60\) CPU-hours.
The relative results bear on the covering radius of \(\mathop{\mathrm{RM}}(2,m)\) itself. For \(m\leqslant 7\) the covering radius \(\rho_2(m)\) is attained on cubic forms: \(\rho_2(6)=18\) [18] and \(\rho_2(7)=40\) [23]. For \(m=9,10,11\) the best known lower bounds likewise come from cubic forms [10], [19], [22]; in particular, the previous bound \(\rho_2(10)\geqslant 400\) is attained by cubic trace monomials [19]. The present computation raises it to \(\rho_2(10)\geqslant 408\), with the \(179\) orbits of Tab. ¿tbl:tab:rep? as explicit witnesses and as the natural candidates for the extremal functions.
Two structural signatures of the extremal orbits suggest where to look for high-\(d_2\) forms in \(m>10\). The first signature is the alternating rank. Thm. 4 forces \(\mathop{\mathrm{arank}}(f)\geqslant 6\) on every \(m=10\) extremal orbit, and \(177\) of the \(179\) sit at the maximal \(\mathop{\mathrm{arank}}=7\). Thus, high-\(d_2\) candidates appear to be strongly concentrated among forms of maximal alternating rank.
The second signature is the trace structure. Every cubic trace monomial in ten variables has \(d_2\leqslant 400\) (App. 7.3), so the monomial family behind the best known lower bounds stops short of the extremal set, and only one of the \(179\) extremal orbits is a two-term trace polynomial \(\mathrm{Tr}(\omega x^{21}+x^{49})\). This shift from monomials to binomials suggests searching for high-\(d_2\) forms in \(m>10\) among sparse trace polynomials with two or more terms.
The enumeration data and reference code are archived on Zenodo, zenodo.org/records/20773273 [24]. The archive contains the coset weight enumerators for \(f+\mathop{\mathrm{RM}}(2,10)\), the assembled weight enumerators of \(\mathop{\mathrm{RM}}(3,10)\) and \(\mathop{\mathrm{RM}}(3,11)\), the explicit distance-\(408\) quadratic corrections, and the cocubic certificates. It also
includes reference implementations, in particular the exact \(\mathop{\mathrm{RM}}(2,10)\) coset-enumerator code. The archive is shared with the classification paper [15]; therefore it also contains the catalog data used here, such as packed representatives and stabilizer orders, together with verification scripts for the classification data. The accompanying
repository, github.com/khoruzhii/bcf10, contains supplementary code from [15],
as well as the heuristic upper-bound search, the \(m=11\) coset-enumeration example, and the trace-polynomial checks.
Acknowledgments↩︎
This research was supported by the DFG Cluster of Excellence MATH+ (EXC-2046/2, project id 390685689) funded by the Deutsche Forschungsgemeinschaft (DFG), as well as by the National High-Performance Computing (NHR) network.
7 Appendix↩︎
7.1 Proof of Nondegenerate Restrictions↩︎
Lemma 3. Fix a coordinate split \(x=(t,y)\in\mathbb{F}_2\times\mathbb{F}_2^{m-1}\) and write \(f(t,y)=g(y)+tp(y)\) for a nondegenerate cubic form \(f\) on \(\mathbb{F}_2^m\). Put \(V_f=\langle p,\Delta_a g\rangle\) with \(a\in\mathbb{F}_2^{m-1}\). Then \(\dim V_f=m-\dim\mathop{\mathrm{Rad}}(g)\). In particular, if \(g\) is nondegenerate, then \(\dim V_f=m\).
Proof. The map \(a\mapsto\Delta_a g\) from the \(y\)-space to \(\mathop{\mathrm{RM}}^*(2,m-1)\) has kernel \(\mathop{\mathrm{Rad}}(g)\), so its image has dimension \(m-1-\dim\mathop{\mathrm{Rad}}(g)\). It remains to show that \(p\) is not in this image. Suppose, to the contrary, that \(p\mathrel{\smash[t]{\overset{2}{=}}}\Delta_a g\) for some \(a\). Then \[\Delta_{(1,a)}f\mathrel{\smash[t]{\overset{2}{=}}}\Delta_a g+p+t\Delta_a p.\] The first two terms cancel, and \(\Delta_a p\mathrel{\smash[t]{\overset{1}{=}}}\Delta_a\Delta_a g=0\). Hence \(\Delta_{(1,a)}f\mathrel{\smash[t]{\overset{2}{=}}}0\), so \((1,a)\in\mathop{\mathrm{Rad}}(f)\), contradicting the nondegeneracy of \(f\). Thus \(p\) contributes one additional independent generator. ◻
The useful case for the enumerator is therefore a split with nondegenerate \(g\). The remaining question is whether such a split can always be found. Equivalently, can a nondegenerate cubic form have only degenerate cubic restrictions in every coordinate split? The next lemma shows that this failure is rigid: it happens only in odd dimension and only for one \(\mathop{\mathrm{GL}}(m,2)\)-orbit.
Lemma 4. Let \(f\) be a nondegenerate cubic form on \(\mathbb{F}_2^m\) with \(m>3\). If every hyperplane restriction of \(f\) is degenerate, then \(m\) is odd and there is an \(A\in\mathop{\mathrm{GL}}(m,2)\) such that \(f(Ax)\mathrel{\smash[t]{\overset{3}{=}}} f_* (x) = x_0(x_1x_2+x_3x_4+\cdots+x_{m-2}x_{m-1})\).
Proof. Fix a nonzero linear form \(\lambda\), determining the hyperplane \(\ker\lambda = \{x : \lambda(x) = 0 \}\). Since the restriction is degenerate, there is a nonzero \(a\in\ker\lambda\) such that \[\Delta_a f |_{\ker \lambda} \mathrel{\smash[t]{\overset{2}{=}}} 0.\] and therefore \[\Delta_a f \mathrel{\smash[t]{\overset{2}{=}}} \lambda \mu\] for some linear form \(\mu\notin\langle\lambda\rangle\). For each such factorization, keep the two-dimensional space \(P_a=\langle\lambda,\mu\rangle\) of linear factors. These spaces cover all nonzero linear forms, because the construction starts from an arbitrary \(\lambda\).
We claim that these spaces are pairwise intersecting. Suppose, to the contrary, that two of them satisfy \(P_a\cap P_b=0\). The linear part of \(\Delta_b\Delta_a f=\Delta_a\Delta_b f\) lies in both \(P_a\) and \(P_b\), hence \(\Delta_b\Delta_a f\mathrel{\smash[t]{\overset{1}{=}}}0\). Writing \(\Delta_a f\mathrel{\smash[t]{\overset{2}{=}}}\alpha\beta\) with \(P_a=\langle\alpha,\beta\rangle\), gives \[\alpha(b)\beta+\beta(b)\alpha=0,\] so \(\nu(b)=0\) for all \(\nu\in P_a\). Similarly, \(\nu(a)=0\) for all \(\nu\in P_b\). Also \(\Delta_a\Delta_a f=\Delta_b\Delta_b f=0\), so \(\nu(a)=0\) for all \(\nu\in P_a\) and \(\nu(b)=0\) for all \(\nu\in P_b\). Thus \[\nu(a)=\nu(b)=0\] for every \(\nu\in P_a+P_b\). Since \(a\) and \(b\) are distinct nonzero vectors, choose a linear form \(\eta\) with \(\eta(a)=\eta(b)=1\). By the covering property, \(\eta\) lies in some space \(P\). The space \(P\) cannot be disjoint from either \(P_a\) or \(P_b\), because otherwise every form in \(P\) would be zero on \(a\) or on \(b\), contradicting \(\eta(a)=\eta(b)=1\). Thus \(P\cap P_a\ne0\) and \(P\cap P_b\ne0\). Since \(P_a\cap P_b=0\) and \(\dim P=2\), these two intersections force \(P\subseteq P_a+P_b\). But then \(\eta\in P_a+P_b\), contradicting \(\eta(a)=\eta(b)=1\). Therefore the spaces are pairwise intersecting.
A pairwise-intersecting collection of two-dimensional spaces either has a common nonzero form or is contained in a three-dimensional space. Since our spaces cover all nonzero linear forms and \(m>3\), the second alternative is impossible. Hence all spaces contain a common nonzero linear form \(\ell\).
Since the supports cover all nonzero linear forms and all contain \(\ell\), for every \(\lambda\notin\langle\ell\rangle\) there is a witness \(a \in \ker \ell\) such that \[\Delta_{a}f\mathrel{\smash[t]{\overset{2}{=}}}\ell\lambda.\] Choose linear forms \(\lambda_1,\ldots,\lambda_{m-1}\), forming with \(\ell\) a basis, with corresponding witnesses \(a_1,\ldots,a_{m-1}\in\ker\ell\). The quadratics \(\ell\lambda_i\) are independent, so the vectors \(a_i\) are independent because \(f\) is nondegenerate. Hence \(a_1,\ldots,a_{m-1}\) form a basis of \(\ker\ell\). Since the quadratic part of \(\Delta_a f\) depends linearly on \(a\), every quadratic derivative in a direction \(a\in\ker\ell\) is a linear combination of the quadratics \(\ell\lambda_i\). Hence each such derivative has a factor \(\ell\), and \(\Delta_a f|_{\ker\ell}\mathrel{\smash[t]{\overset{2}{=}}}0\) for all \(a\in\ker\ell\). Thus \(f|_{\ker \ell} \mathrel{\smash[t]{\overset{3}{=}}} 0\).
Choose coordinates with \(x_0=\ell\). Therefore \[f\mathrel{\smash[t]{\overset{3}{=}}}x_0\omega\] for some homogeneous quadratic form \(\omega\) in the remaining \(m-1\) variables. The nondegeneracy of \(f\) forces \(\omega\) to be nondegenerate. Thus \(\omega\) is a nondegenerate alternating quadratic form on an \((m-1)\)-dimensional space. Hence \(m-1\) is even, and by the symplectic normal form over \(\mathbb{F}_2\) there is a further linear change of coordinates such that \[\omega\mathrel{\smash[t]{\overset{2}{=}}}x_1x_2+x_3x_4+\cdots+x_{m-2}x_{m-1}.\] This gives the required \(A\in\mathop{\mathrm{GL}}(m,2)\). ◻
The cases \(m<3\) are vacuous. For \(m=3\), the space of cubic forms is one-dimensional, and its nonzero element is equivalent to \(x_0x_1x_2\). This form is nondegenerate, and every hyperplane restriction has zero cubic part, so it is the exceptional orbit. Assume \(m>3\). If a nondegenerate cubic form has no nondegenerate hyperplane restriction, the previous lemma shows that \(m\) is odd and the form is equivalent to \(f_*\). Thus every other nondegenerate cubic form has a nondegenerate hyperplane restriction.
It remains to check that \(f_*\) is exceptional. First, \(f_*\) is nondegenerate. For \((\alpha,v)\in\mathbb{F}_2\times\mathbb{F}_2^{m-1}\), \[\Delta_{(\alpha,v)} f_*\mathrel{\smash[t]{\overset{2}{=}}}\alpha\omega+x_0\Delta_v\omega.\] The two summands have different \(x_0\)-degree, so the quadratic part can vanish only if \(\alpha=0\) and \(\Delta_v\omega\mathrel{\smash[t]{\overset{1}{=}}}0\). Since \(\omega\) is nondegenerate, this forces \(v=0\). Therefore \(\mathop{\mathrm{Rad}}f_* = 0\).
Now fix any coordinate split \(x=(t,y)\in\mathbb{F}_2\times\mathbb{F}_2^{m-1}\) and write \(f_*(t,y)=g(y)+tp(y)\). If \(t=x_0\), then \(g=0\). Otherwise choose coordinates on \(t=0\) so that one coordinate is the restriction of \(x_0\) and the remaining coordinate space is \(L=\{t=x_0=0\}\). In these coordinates, \[g\mathrel{\smash[t]{\overset{3}{=}}}x_0\,\omega|_L.\] Since \(\dim L=m-2\) is odd, \(\omega|_L\) has a nonzero radical, so \(g\) is degenerate.
7.2 Cocubic Upper-Bound Search↩︎
Here we describe the auxiliary computation behind the bound for \(\mathop{\mathrm{RM}}(6,10)\) in \(\mathop{\mathrm{RM}}(7,10)\). For each cubic representative \(f_j\in\mathop{\mathrm{RM}}^*(3,10)\), we form the complementary representative \(g_j\in\mathop{\mathrm{RM}}^*(7,10)\) by replacing each monomial \(x_i x_j x_k\) with the product of the other seven variables. These are representatives of all nonzero \(\mathop{\mathrm{GL}}(10,2)\)-orbits in \(\mathop{\mathrm{RM}}^*(7,10)\) [21].
For the cocubic search we used a different move space. Instead of flipping monomial coefficients in \(\mathop{\mathrm{RM}}(6,10)\), a move adds a polynomial of the form \[h(x)=\prod_{s=1}^{6}\ell_s(x),\] where the \(\ell_s\) are affine linear forms with independent linear parts. Preliminary tests showed that these geometric moves were more effective than moves in the monomial basis. The full move set has about \(3.4 \times 10^9\) distinct moves, so we do not scan the whole neighborhood. Instead we sample \(2048\) moves. A sampled move is produced from the current polynomial \(g+p\) by choosing five random affinely independent points from the set \(\{x:g(x)\neq p(x)\}\). These points span a \(4\)-dimensional affine subspace of \(\mathbb{F}_2^{10}\). We take \(h\) to be the polynomial of the form above whose support \(\{x:h(x)=1\}\) is this affine span. This biases the search toward large support overlap. The local search then uses the same beam and ILS approach as in Sec. 5, but with sampled moves.
The full pass used \((w,i,k)=(16,\;2048,\;1)\) and \(2048\) sampled moves per beam node. It completed for all \(3691560\) nonzero representatives. No representative remained above weight \(32\). For each representative \(g_j\), the computation stores an explicit correction \(p_j\in\mathop{\mathrm{RM}}(6,10)\).
7.3 Trace Representations of the Extremal Forms↩︎
Here we test whether the \(179\) extremal orbits admit compact finite-field descriptions. Identify \(\mathbb{F}_2^{10}\) with \(\mathop{\mathrm{GF}}(2^{10})=\mathbb{F}_2[\alpha]/(\alpha^{10}+\alpha^3+1)\) and write \[\mathrm{Tr}(a)=a+a^2+\cdots+a^{2^9}\] for the absolute trace. For an exponent \(d\) of binary weight three, the function \(x\mapsto\mathrm{Tr}(\lambda x^d)\) is a Boolean cubic form and Frobenius conjugation \(d\mapsto 2d\) partitions these exponents into \(12\) cyclotomic classes. The previous lower bound \(\rho_2(10)\geqslant 400\) is attained by such trace monomials [19], so it is natural to ask whether the extremal orbits contain them.
A candidate is tested by evaluating the complete \(\mathop{\mathrm{GL}}(10,2)\)-invariant of [15]. The invariant takes distinct values on all orbits, so a matching value identifies the orbit. Scanning all \(12\cdot (2^{10}-1)\) trace monomials \(\mathrm{Tr}(\lambda x^d)\) with \(\lambda\neq 0\) shows that each exponent class produces one or two \(\mathop{\mathrm{GL}}(10,2)\)-orbits, all with \(d_2\in\{352,360,400\}\). No trace monomial reaches \(408\).
We then scanned all two-term trace polynomials \(\mathrm{Tr}(\lambda x^d+\mu x^e)\) over the same exponent classes and all nonzero coefficient pairs, \(66\cdot (2^{10}-1)^2=69\,070\,914\) candidates in total. It reaches a single \(d_2=408\) orbit, \[f=\mathrm{Tr}(\omega x^{21}+x^{49}),\] where \(\omega=\alpha^2+\alpha^3+\alpha^5+\alpha^6+\alpha^7\) satisfies \[\omega^2+\omega+1=0,\] a primitive cube root of unity. The catalog representative of this orbit is \(025+028+047+128+129+136+148+156+179+236+359+378+469+568+678\), with \(|\mathop{\mathrm{St}}(f)|=5\) and \(\mathop{\mathrm{arank}}(f)=7\). The remaining \(178\) extremal orbits admit no trace representation with at most two terms over the cubic exponent classes.