A de Bruijn covering code of radius R is a binary string so that the set of words appearing as n consecutive symbols (wi

Definitions and mathematical statement

Let $w=(w_0,\ldots,w_{L-1})$ be a cyclic binary word of positive length $L$, with indices read modulo $L$. For a block length $n\ge1$, its consecutive windows are \[ W_i(w)=(w_i,w_{i+1},\ldots,w_{i+n-1}) \qquad(0\le i<L). \] Windows may repeat. The word is a de Bruijn covering code of radius $R$ if every $x\in\{0,1\}^n$ satisfies $d_H(x,W_i(w))\le R$ for some $i$, where $d_H$ is Hamming distance. Let $D(n,R)$ be the minimum possible cyclic length.

Determine $D(n,R)$, in particular its sharp asymptotic growth for fixed $R\ge1$ as $n\to\infty$, including any limiting leading constant. The source's historical bounds differed by a factor of $\log n$. Ta and Vu's June2026 preprint gives explicit constant-factor constructions at order $2^n/n^R$, removing that gap. The remaining question seeks the exact minimum and sharp leading behavior, beyond bounds up to constants depending on $R$.

The length counts cyclic positions, not the number of distinct windows. Consecutive windows must share their intervening $n-1$ symbols, so an arbitrary covering code cannot automatically be arranged as windows without an additional cost. Wrap-around is part of the definition. At radius zero the condition reduces to the classical de Bruijn requirement, while positive radius allows approximate coverage of each word.

Short English statement

Determine the shortest cyclic binary word whose length-n windows cover the binary cube within fixed Hamming radius.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100076 (AMR-030-0076), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Words and Codes, source-order bullet 76. Original source indexed by AMR-030-0076. https://people.math.sc.edu/cooper/combprob.html.
• S3 Ta and Vu, Near-Optimal Covering Sequences (2026), constant-factor construction for every fixed alphabet and radius. https://arxiv.org/abs/2606.29236.