The Mesirov-Sweet property over F_2 up to degree 33, with two quotients of degree two up to degree 28

Statements

For $a_1,\ldots,a_r \in\mathbb{F}_2[T]$ let $K(a_1,\ldots,a_r)$ denote the continuant, so that

in lowest terms.

Every pair $(f,g)$ with $g$ monic, $\gcd(f,g)=1$ and $\deg f < \deg g$ arises from exactly one sequence of non-constant quotients, and $\deg g = \sum_i \deg a_i$.

The bound 2 cannot be lowered: $T^2+T$ has no admissible $f$ with linear quotients only. For irreducible $g$ Mesirov and Sweet proved that all quotients can be taken linear [2]; for general $g$ the best known bound grows like $\log d$ [3]. For an admissible $g$ let $k(g)$ be the least number of quotients of degree 2 among the $f$ of Conjecture 1.

Theorem 2 gives Theorem 1 for $d \le28$; the degrees $29 \le d \le33$ are treated separately. Table 2 records the number of $g$ with $k(g)=2$.

Method

Cells

Cells. A cell is a finite sequence $\pi=(e_1,\ldots,e_r)$ with $e_i \in\{1,2\}$ and $\sum e_i=d$. Since every polynomial of degree $e$ over $\mathbb{F}_2$ is monic, the cell carries exactly $\prod_i 2^{e_i}=2^d$ quotient sequences, and we write $I_\pi\subseteq\mathbb{F}_2[T]$ for the set of their continuants. The pure cell $(1,\ldots,1)$ is the one of Mesirov and Sweet; $k(g) \le j$ if and only if $g$ lies in $I_\pi$ for some cell with at most $j$ entries equal to 2.

Two enumerations

Two enumerations. Program A runs through each cell depth first, appending quotients on the right and updating the pair $(K(a_1,\ldots,a_i), K(a_1,\ldots,a_{i-1}))$. Program B was written separately: it runs through the same sequences in a different order (the first quotient varies fastest) and evaluates the continuants by the recurrence in the opposite direction. Both mark the images in a bitmap indexed by the $d$ low coefficients of $g$.

Certificates

Certificates. For the $g$ outside the union of the cells, an explicit $f$ is produced and then checked by a third program, which runs the Euclidean algorithm on $(g,f)$ from scratch and verifies $\deg g=d$, $\deg f<d$, that every quotient has degree 1 or 2 (and, for Theorem 2, that at most two have degree 2), and that the last non-zero remainder is 1.

Search for certificates

Search for certificates. For $g$ outside the union of the cells, $f$ is searched for by a meet-in-the-middle procedure resting on two classical identities: for $1\leq j<r$,

and, in characteristic 2,

Fix a cut degree $c$ ($c=17$ for $d=33$, $c=\lfloor d/2\rfloor$ for $29\leq d\leq32$) and a random sample of $2^{20}$ prefixes $(a_1,\ldots,a_j)$ with $\sum_{i\leq j}\deg a_i=c$ and all degrees in $\{1,2\}$. For each prefix put $q=K(a_1,\ldots,a_j)$, $q'=K(a_1,\ldots,a_{j-1})$, $\rho=K(a_2,\ldots,a_j)$, $\rho'=K(a_2,\ldots,a_{j-1})$. The second identity gives $q'\rho\equiv1\pmod q$, so a suffix with $V=K(a_{j+2},\ldots,a_r)$ of degree $<c$ must be $V=g\rho\pmod q$, and then $U=K(a_{j+1},\ldots,a_r)=(g-q'V)/q$. The candidate is kept when $\deg U=d-c$ and the Euclidean algorithm on $(U,V)$ produces quotients of degree 1 or 2 only and ends with 1; then $f=\rho U+\rho'V$. If the sample fails, all prefixes at the cuts $c$ and $c+1$ are tried. Certificates are accepted only after the independent check described above, so the search needs no correctness argument of its own.

Results

$d$	not reached by the cells	share	fallback searches	certificates rejected	A=B
29	2 015 190	0.375%	0	0	yes
30	4 020 219	0.374%	0	0	yes
31	8 051 860	0.375%	0	0	yes
32	16 187 206	0.377%	0	0	yes
33	32 430 306	0.378%	0	0	yes

$d$	$\#\{g : k(g) = 2\}$	share	$d$	$\#\{g : k(g) = 2\}$	share
1	0	0.0000	15	756	0.0231
2	0	0.0000	16	1 364	0.0208
3	0	0.0000	17	2 524	0.0193
4	0	0.0000	18	4 582	0.0175
5	0	0.0000	19	8 322	0.0159
6	3	0.0469	20	14 974	0.0143
7	4	0.0312	21	27 440	0.0131
8	4	0.0156	22	50 069	0.0119
9	16	0.0312	23	90 076	0.0107
10	19	0.0186	24	163 599	0.0098
11	48	0.0234	25	295 916	0.0088
12	110	0.0269	26	535 199	0.0080
13	216	0.0264	27	967 956	0.0072
14	419	0.0256	28	1 748 470	0.0065

Ancillary files

The folder anc contains: c_sources.py, which writes out the C sources of programs A and B, of the certificate search, of the checker and of the small-degree enumeration, together with the run scripts and a description of the file formats; the cell lists cells_d29.csv, . . . , cells_d33.csv; the logs of the runs; and verif_ms_f2.py (Python with numpy only), which repeats the exhaustive computation of the counts $\#\{g : k(g) = j\}$, $j = 0,1,2$, in degree 18, 20 or 22 (according to a memory budget set in the file) and checks the samples certs_d28_two_insertions.csv and certs_d33_sample.csv of $10^{5}$ certificates each, together with a control on corrupted certificates. Polynomials are written as integers whose binary digits are their coefficients.

ORCID 0009-0009-1526-1178