\[ \newcommand{\im}{\mathsf{im}} \newcommand{\sign}{\mathsf{sign}} \]

(This is a work-in-progress draft.)

Bryce Kille, my co-author on the density lower bound for forward sampling schemes paper (Kille et al. 2024), recently mentioned that ChatGPT found optimal sampling schemes for \(w=2\) with \(k\) odd.

I’ve been considering whether to throw this problem of finding optimal-density sampling schemes at an LLM for a while now, and this made me finally do it. For context, my recent WABI SUS-anchors paper (Groot Koerkamp 2026) is a pretty simple scheme that makes a step towards optimal density for \(k=1\) (fixing the other axis to the smallest non-trivial value¹). But SUS-anchors do not yet achieve optimal density nor does I have a proof of their density apart from empirical evaluations.

So anyway, I asked Sol (on xhigh mode) to also search for optimal \(w=2\) schemes. I initially let it read my python scribbles for searching \(k=1\) schemes, as well as the integration Bryce made with an ILP solver, so that it can fix part of a sampling scheme and then use the solver to decide whether the partial scheme can be completed into a scheme of optimal density.

It tried a bunch of things, but they didn’t quite work. I think my python notes distracted the search, since \(k=1\) turns out to be quite different from \(w=2\). At some point, it started talking about comma-free codes and the Eastman construction. I had told it earlier not to use the internet, so as not to accidentally spoil the process of finding a solution, but at this point I helped it download a very nice overview paper: “Hall Sets, Lazard Sets and Comma-Free Codes” (Perrin and Reutenauer 2018). Sol then implemented a number of the techniques from the paper. At first it made some mistakes in some tie-breaking rules and it started trying other things, but after I convinced it that surely this paper must lead to a solution, it indeed did find one eventually!

In this post, I will first explain Bryce’s solution. Then, I’ll collect background on comma-free codes and related concepts (both for my and your understanding), and then to reverse engineer/re-invent the solution that Sol found.

1 WIP paper Link to heading

1.1 Abstract Link to heading

1.2 Introduction Link to heading

• connection between DBg, minimizers, independence numbers

• TODO: framing from graph perspective; with application to w=2 minimizers

• Relation to SUS-anchors and 10-minimizers

• TODO: what about \(w=2\) and even \(k\) or even \(n\) with \(\sigma=2\)

• TODO: investigate potential journals

• TODO: cite previous work on DBg independence number

• TODO: some result to extend to larger alphabets

  • https://shop.elsevier.com/books/sequences-and-the-de-bruijn-graph/etzion/978-0-443-13517-0

• TODO: Read “Sequences and the de Bruijn Graph” pdf

1.3 Preliminaries Link to heading

Cycle-cover Link to heading

Independence numbers of DBg history Link to heading

old papers:

• (Lempel 1971) (JCT)
  • Lempel paper with conjecture proven by Mykkeltveit
• (Mykkeltveit 1972) (JCT): decycling set; 1 per cycle

new papers:

• search: https://www.sciencedirect.com/search?qs=bruijn%20graph
• https://www.sciencedirect.com/science/article/pii/S0012365X06000999
  • Lichiardopol, Independence number of de bruijn graphs
  • bounds; asymptotes for even n
  • also check out papers cited by this one
• https://www.sciencedirect.com/science/article/pii/S0898122109007202
  • proves a subset of Mykkeltveit’s ‘72 paper
• https://www.sciencedirect.com/science/article/pii/S0012365X10000270
  • perfect matching on the necklace graph
• https://www.sciencedirect.com/science/article/pii/0166218X9290133U
  • drawing DBg
• https://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p194/pdf
  • maximum independent set for n=3
• https://arxiv.org/html/2604.14671v2 [2026]
  • “on the independence number of de bruijn graphs”
  • mostly asymptotic
  • extends lichiardopol from n=17 to infinite odd n
• https://www.sciencedirect.com/science/article/pii/0012365X91903626
  • “Covering the de Bruijn graph” 1989
  • (NO_ITEM_DATA:covering-dbg)

equivalences:

• vertex cover
• independence number
• edge cover?

We consider the problem of finding the size of a maximal independent set of a De Bruijn graph. Specifically, we consider the node-centric De Bruijn graph of order \(n\), where nodes correspond to words of length \(n\) over an alphabet of size \(\sigma\). Edges correspond to nodes that overlap in \(n-1\) characters.

The independence number is the size of a maximal independent set, that is, a subset of nodes such that no two nodes are adjacent.

This has been studied since 1991 [CITE]. Lichiardopol [2006, CITE] computes this for \(n\in\{2,3,5,7\}\) and Majer and Novaga [2026, CITE] give a construction for \(n\in\{11,13,17\}\). These all work for arbitrary \(\sigma\).

Independent sets, vertex covers, and max cuts Link to heading

A maximum independent set is the complement of a minimal vertex cover, which is a subset of nodes such that each node is either in the set or adjacent to the set.

A cut is implied by partitioning the vertices into two sets \(V_0\) and \(V_1\) via \(\lambda: V \to \{0,1\}\): each undirected edge between \(V_0\) and \(V_1\) is in the cut. A directed cut counts directed edges from \(V_0\) to \(V_1\).

Since the De Bruijn graph is Eulerian (ie every node has even degree),

optimal minimizer density Link to heading

• kmer
• window
• context
• cycles; lower bound

Our \(w=2\) sampling scheme must sample either the first or second position of each length \(\ell\) window (where \(\ell=w+k-1\) is even and \(k \equiv 1\pmod w\) is odd).

Connecting the problems Link to heading

equivalent:

• charged contexts [marcais paper]
• density over cycles
• density over random sequence
• random over De Bruijn seq
• removing edges/nodes to make graph bipartite

1.4 Mykkeltveit embedding Link to heading

The classical Mykkeltveit embedding Link to heading

TODO Explain why this decycling

The Mykkeltveit embedding was introduced by Mykkeltveit (1972) in order to prove a conjecture of Lempel (Lempel 1971) stating that the order-\(n\) De Bruijn graph \(B_n\) can be made acyclic by removing \(Z(n)\) vertices. In particular, it is clear that \(Z(n)\), the number of disjoint cycles is \(Z(n)\) and thus that this is a lower bound.

In particular, a node \(w=w_0\dots w_{n-1}\) of the De Bruijn graph is mapped to

\begin{equation*} f(w) = \sum_{i=0}^{n-1} w_i \cdot \omega^i, \end{equation*}

where \(\omega=\omega_n\) is the complex \(n\)-th root of unity. The Mykkeltveit decycling set (Pellow et al. 2023) then consists of all words with \(\pi-2\pi/n \leq \arg(f(w)) < \pi\), i.e., those words that are the first rotation having positive imaginary part.

A new embedding Link to heading

We want to build on optimal \(w=2\) minimizer scheme for some odd \(k\). Thus, we must build a function from a length-\(k+1\) window \(w=w_1\dots w_{k+1}\) to \(\{0,1\}\). [todo].

Let \(n=k+2\) be odd and now let \(\omega=\omega_{2n}\) be a \(2n\)’th root of unity so that \((-\omega)^n=-\omega^n = 1\). We define

\begin{equation*} g(w) = \sum_{i=1}^{n-1} w_i (-\omega)^i, \end{equation*}

where the \((-\omega)^0\) term is skipped. Like Mykkeltveit, we choose the first or second \(k\)-mer based on the sign of the imaginary part of \(g(w)\), \(\sign(\im(g(w)))\).

Now consider a primitive cyclic context \(c=c_0\dots c_{n-1}\) of length \(n=k+2\) and the \(n\) windows \(w_1\) to \(w_n\) contained in it, with \(w_j = c_{j}\dots c_{j+n-2}\) with indices modulo \(n\). Then

\begin{align*} \im(g(w_j)) &= \im(g(c_{j}\dots c_{j+n-2})) = \im\left(\sum_{i=1}^{n-1} c_{j+i} (-\omega)^i\right) = \im\left(\sum_{i=0}^{n-1} c_{j+i} (-\omega)^i\right)\\ &= \im\left((-\omega)^{-j}\sum_{i=0}^{n-1} c_{j+i} (-\omega)^{i+j}\right) = \im((-\omega)^{-j}g(w_0)). \end{align*}

Assuming that \(g(w_0)\neq 0\), \((-\omega)^n g(w_0)\) changes imaginary sign \(n-1\) out of \(n\) times. Thus, for all but one pair of consecutive windows we choose “synchronized” \(k\)-mers. [todo this “big picture stuff” needs to be more precise.]

[todo: distinguish \(n\) and \(d|n\) for shorter primitive contexts?]

[todo: what if \(g(w_0)=0\)? Note that \(g(w_0)=0\) for periodic sequences.]

Degenerate and non-primitive cases Link to heading

A (primitive?) cycle \(c\) is degenerate when \(g( c)=0\).

Lemma: distinct degenerate cycles are vertex (window)-disjoint, so we can simply “hardcode” an alternating order.

Dfn: we can make that order comparible: if \(\im(g(w))=0\) but no extended context has \(g( c)=0\), then set \(\lambda_0(w)=0\) (Bryce’s notation). Otherwise, let \(a\) be the unique such symbol, and anchor by the lexicographically smallest rotation.

(Importantly, we should make sure this is compatible with the choice in the non-degenerate case.)

1.5 Comma-free codes Link to heading

Previous work on comma-free codes Link to heading

We will now consider a completely different approach to solving our problem of finding an optimal minimizer scheme, or equivalently a vertex(?) cover of the De Bruijn graph. Our construction closely builds on existing work to build comma-free codes, which are specific codes (sets of words) such that no other code words can be found in the overlap between two code words. Comma-free codes were first introduced by Crick, Griffith, and Orgel (1957) as a (wrongly) hypothesized structure of the amino acids to avoid reading-frame issues. Golomb, Gordon, and Welch (1958) find comma-free codes of maximal size for odd \(k\) up to 15 and show that, in general, optimality is not possible for even \(k\). Eastman (1965) is the first to show a construction for all odd \(k\). Their presentation is quite intricate. (NO_ITEM_DATA:knuth-aopc4-5b-backtracking) gives a significantly simpler presentation in terms of dips, which are locally maximal subsequences \(w=w_1\dots w_k\) with \(w_1\geq\dots\geq w_{k-1}<w_k\). Given a cyclic word, one then finds all odd-length dips and splits the word before each odd-length dip, and proceeds recursively on these substrings. Perrin and Reutenauer (2018) further improve terminology with superdips (an odd-length dip followed by even-length dips) and \(n\)-(super)dips, which are (super)dips over the alphabet of \((n-1)\)-dips using the radix order.

Meanwhile, Scholtz (1969) provides a simpler technique to create a maximal-size comma-free codes that is initially explained in terms of “erasing commas between tokens”. Again, the presentation was significantly simplified in terms of Lazard sets (NO_ITEM_DATA:lazard60, NO_ITEM_DATA:codes-and-automata) by Perrin and Reutenauer (2018). Their main theorem shows that the Eastman construction also arises as a Lazard set.

Lastly, a helpful algorithm is that of Melancon (NO_ITEM_DATA:melancon-thesis, NO_ITEM_DATA:codes-and-automata; Perrin and Reutenauer 2018), which gives a general bottom-up procedure similar to the ones of Knuth and Scholtz to find the conjugate of a word that is part of the comma-free code.

Hall Sequences, Lazard Sets, and Comma-Free Codes Link to heading

Our presentation will closely follow Section 7.3 and Chapter 8 of (NO_ITEM_DATA:codes-and-automata) and definitions and lemmas are taken from there unless otherwise mentioned. Further background can be found in (NO_ITEM_DATA:free-lie-algebras-reutenauer) and Viennot (1978).

Notation. We write \(A\) for the alphabet use \(u\in A^*\) for words over \(A\). A word can be seen both as a string of characters as well as an element of the free monoid over \(A\). The empty word is written \(1\), and \(A^{\leq n}\) is the set of words of length up to \(n\). The characters of a word are indexed counting from 0, and the suffix starting at the \(i\)’th $0$-based character is denoted \(w[i..]\). The radix order \(u<_rv\) compares words \(u\) and \(v\) first by length \(|u|<|v|\), and breaks ties lexicographically. Two words \(w\) and \(w’\) are conjugate when they are a rotation of each other, i.e. there are \(u\) and \(v\) such that \(w=uv\) and \(w’=vu\). A word is primitive when it is not the power of some other word. A strict prefix (suffix) of a word is a prefix (suffix) that does not equal the word itself.

We now move on to re-stating some relevant definitions. Originally Hall sets are defined in terms of trees (NO_ITEM_DATA:free-lie-algebras-reutenauer), but here we take a simpler definition.

TODO Example

TODO drop hall sequence; replace by remark

Closely related are Lazard sets (NO_ITEM_DATA:lazard60), that induce an order on their elements via lazard elimination.

In fact, each Hall set is a Lazard set, and each Lazard set is a Hall set (,thm NO_ITEM_DATA:free-lie-algebras-reutenauer). As an example, when \(x_i\in X_i\) is chosen a word of minimal length in the Hall construction, then \(\{x_i\}_{i\geq 1}\) is a Lazard set.

TODO mention strings vs words vs free algebra; concatenation vs products

TODO drop general unique factorization

TODO write more about \(\nu\) and \(\delta\)

The following construction is a modern presentation by Perrin and Reutenauer (2018, 3.3; NO_ITEM_DATA:codes-and-automata) of Scholtz’ original “comma erasing method” (Scholtz 1969).

From here on, \(x_i\in X_i\), \(Y\), and \(Z\) all refer to this specific construction, and for \(u,v\in U\) we write \(u<v\) as ordered by the Lazard set. In particular, for \(x_i,x_j\in Z\) we have \(x_i<x_j\) iff \(i<j\).

We now cover some basic facts about this construction and the sets \(U\), \(Y\), and \(Z\).

TODO add more explaining text here

TODO tree of z[2..]

TODO this is not the factor tree, but construction of the code word

TODO fix the tree

TODO example of tree of prefix and suffix of \(z\)

As an example, consider Figure 1, showing how \(z=10101101101\in Z\) is recursively built from smaller elements of \(U\). The root \(z\) itself has odd length, and each non-leaf node \(u=x_iu’\) is made by concatenating some \(x_i\in Z\) of odd length (the left branch) with some \(u’\in U\) with length of opposite parity of \(u\) with \(x_i < u’\). As we will see below, every prefix of \(z\) corresponds to the concatenation of a number of decreasing odd-length \(z_i\in Z\), as shown in red, while every suffix of \(z\) corresponds to a number of even-length \(y\in Y\), as shown in blue, possibly followed by one odd-length factor \(s\in Z\). An algorithm to build this tree given any \(u\in U\) is Melancon’s algorithm Definition 6

Although we won’t directly use this fact here, the main point of all this theory is to develop a maximal comma-free code:

For any \(x\in X\), \(xx\) may contain only \(x\) itself as code word of length \(m\), so that \(X\) contains at most one element of every conjugacy class. Thus, \(|X|\leq \ell_m(k)\), which counts the number of conjugacy classes of words of length \(m\) over an alphabet of size \(k\) (or equivalently, the number of primitive words with length dividing \(m\)).

TODO: Define and detangle \(\ell_m(k)\), the number of primitive words of length \(m\) over alphabet \(k\), and the total number of conjugacy classes of words of length \(m\)

TODO maximal vs maximum vs optimal

What this means is that comma-free codes provide a way to sample a representative from every conjugacy class, i.e., they sample one vertex in every primitive length \(n=k+2\) cycle in the order \(n\) De Bruijn graph. [ TODO Or do we look at edges in the order \(n-1\) DBg?]

We won’t repeat the proof here, but do re-state a few lemmas that will be useful to us later.

One of the core lemmas is the following, which follows directly from the more general unique factorization lemma mentioned above:

TODO even terms are large

Some implications are the following.

Intuition Link to heading

The last lemma tells us that there is, in fact, a lot more structure to our comma-free code than just “one sample per conjugacy class”: Any time two code words overlap, or in the graph setting, that there is a path from sampled vertex \(u\) to sampled vertex \(v\) of length \(<n\), this path has length \(n-|b|\), which is even. Thus, looking modulo two, \(u\) and \(v\) are “synchronized”. In particular, given a long string, we can consider the subset of \(n\)-mers that is a code word. If we look at two consecutive code words (not necessarily adjacent \(n\)-mers), they are either synchronized, or non-overlapping.

So far, this argument does not yet give us a way to take a sample from every context, since some strings may not contain any code word. Instead, we can, for every \(n\)-mer in our string, mark the position/character that starts its code word conjugate. Now suppose we have a string that starts in a code word \(c\), and consider the first \(n\) \(n\)-mers, each of which overlapping a suffix of \(c\). Then, if they sample a position within \(c\) (in the first \(n\) characters of the string), this position must be even by the previous lemma.

The remaining question is: what happens in overlapping non-code word context? In this case, the second code word is not an extension of the first and our previous lemma doesn’t apply. We will show that we

Corollary of streaming algorithm: the sampled anchor can only move right

• Every time the anchor shrinks to a suffix of the current on, things remain aligned
• Every time the anchor grows from a push, things remain aligned
• Every time the anchor ‘jumps’, we get a new unsynchronized sample.
• Along a cycle, it only jumps once!
• How does the representation of the algorithm work along a cycle?
• TODO On pop, the new leftmost suffix of \(z_k\) might eat some of the following terms!
• TODO we can also get a disjoint jump: 001*001 0010 01 001*00101
  • pop moves to 01*001*001|0
  • push moves to 01001*00101*
    • here it’s synchronized, but might not be in general
    • TODO: Example of unsynchronized push

TODO relate n-mer context to (k+1)-mer window

TODO figures

TODO Random question: Are comma-free codes a decycling set? Does every sufficiently long string contain a code word of length \(m\)???

TODO what if for every kmer we sample the start of the code word rotation

The largest contained word Link to heading

With this theory in hand, we are now ready to prove that the largest code word contained in a prefix (suffix) of a code word is a prefix (suffix) itself.

Suppose not, so \(z=az_{i-1}\dots z_{j31} b\) with \(a\) a non-empty suffix of \(z_i\) and \(b\) a non-empty prefix of \(z_j\). Then \(a\) and \(b\) are both in \(Z\) by the previous overlap lemma.

Furthermore, \(b\leq z_j\) because \(|b|\leq |z_j|\). Let \(c\) be the factor after \(a\), i.e. \(c=b\) if \(z_{i-1}\dots z_{j+1}\) is empty and \(c=z_{i-1}\) otherwise. It’s not possible that \(a\geq c\), because then \(z=az_{i-1}\dots z_{j+1}b\) are two distinct representations of a word in \(U\). It’s also not possible that \(a<c\), since then \(ac\in Y^*\) and \(z=(ac)z_{i-2}\dots z_{j+1}b\) (or just \(z=ac\) itself when \(c=b\)) are again two distinct representations of a word in \(U\). Thus, we reach a contradiction.

Now suppose that the largest word contained in the suffix \(w\) is \(z’\). Suppose that \(z’\) is not already a suffix of \(w\), so \(w=az’b\) with \(b\neq 1\).

Since \(b\) is itself a suffix of \(z\), it factorizes as \(y\) or as \(yx_k\) with \(y\in Y^*\) and \(x_k\in Z\). If \(y\neq 1\), let \(e=x_ix_j\in Y\) be the first non-empty term of \(y\). Then \(z’e=z’x_ix_j\in Z\) because \(\nu(e)=i\), \(\delta(e)=\infty\), and \(\delta(z’)\geq i\) because \(z’\geq x_i\) by assumption and thus \(\nu(e)\leq \delta(z’) < \delta(e)\), so that \(z’e\in Z\), giving a contradiction. Thus, \(b=x_k\) with \(x_k \leq z’\), so that \(z’x_k\) is a suffix of \(w\) consisting of two decreasing code words, whereas we know that any suffix must have a unique representation containing at most one odd code word; again a contradiction.

An optimal minimizer scheme Link to heading

We are now ready to define our minimizer scheme. Let \(k\) be the odd \(k\)-mer length of interest. Each window of length \(k+1\) consists of \(w=2\) \(k\)-mers. A context consists of two consecutive windows totalling \(C=k+2\) characters. A \(w=2\) minimizer scheme is optimal if it matches the lower bound for each primitive cycle of length up to \(C\), sampling exactly \(\lceil |C|/2\rceil\) distinct \(k\)-mers.

TODO move this earlier

Finding the largest contained code word Link to heading

We now give an algorithm to find the largest code word contained in a word \(w\). We start with a one-off algorithm based on the unique factorization, and then improve this to a streaming algorithm in the next subsection.

At the core is Melancon’s algorithm, as defined by (NO_ITEM_DATA:melancon-thesis) and further explained in (NO_ITEM_DATA:free-lie-algebras-reutenauer) and (Perrin and Reutenauer 2018, 5.4). (Note that (NO_ITEM_DATA:free-lie-algebras-reutenauer) reverses both the order and the “direction” of the Lazard elimination.) Starting with an arbitrary odd-length word, this gives the conjugate that is a code word. It generalizes and streamlines the algorithms of Scholtz (1969) and (NO_ITEM_DATA:knuth-aops4-5-backtracking).

As a direct corollary, a word in \(A^+\) is a code word if applying the algorithm never “wraps around”.

We now slightly modify the algorithm to find code words in non-cyclic strings.

We now prove that this final state is exactly the unique \(yz_k\dots z_1\) factorization of \(w\).

As before, write \(w = yz_k\dots z_1\). Clearly \(z_k\) starts at an even position.

If the largest contained code word \(z\) is contained in \(z_k\dots z_1\), it must equal \(z_k\) itself by Lemma 9. Otherwise, the largest code word intersects \(y = y_1\dots y_n\in Y^*\). Then the largest code word starts with a non-empty suffix of some \(y_i\in Y\). By Lemma 7, this overlap \(s\) must be in \(Z\) and hence have odd length, so that \(z\) starts at an odd position.

We now directly obtain our result.

A Sliding-window algorithm Link to heading

Compared to the twice-repeated linear Melancon algorithm above, we can be slightly more precise.

If the largest code word starts at an even position, it must be \(z_k\), as highlighted red below, and we are done.

Otherwise, consider \(y_1 = y[1..]\) and factorize \(w’=y_1 z_k\dots z_1\) as \(w’ = y’z’_{k’}\dots z’_1\). Now we prepend \(c\) to \(w’\) to obtain \(w = cy’ z’_{k’}\dots z’_1\). Since \(cy’\in ZY^*\subseteq Y^*Z\), we get \(cy’=y’’s\) with \(s\in Z\). Thus, \(w=y’’ sz’_{k’}\dots z’_1\). Now, if \(s\geq z’_{k’}\) this is the unique factorization and thus must coincide with \(w=yz_k\dots z_1\), giving \(z’_{k’} = z_{k-1}\), with \(z_k\) (in red) as largest factor. Otherwise, if \(s<z’_{k’}\), then \(sz’_{k’}\in Y^*\) and \(w=y’’(sz’_{k’})z’_{k’-1}\dots z_1\) is the normal factorization and \(z’_{k’-1} = z_k\), so that \(z’_{k’}\) in the factorization of \(w’\) is the largest overall factor.

Thus, the factorization of \(w\) has one exactly more or one less odd factor than the factorization of \(w’\), and the one with the larger number of odd factors contains the largest code word in \(w\) as largest factor.

This gives rise to a linear-time streaming algorithm, where we push characters to the right of a window \(w\) and pop characters from its left.

TODO: Figure of streaming algorithm states.

TODO: Figure out constant-time pop; GPT did something and it seems allright but I still have to digest it.

1.6 Discussion / Conclusion Link to heading

• Does the Eastman construction also work? In (Perrin and Reutenauer 2018), it is shown that Eastman’s construction of a comma-free code (Eastman 1965) are also a Lazard set by taking \(x_i\in X_i\) as the odd-length word with minimal index, noting that longer words may have a smaller index than shorter words.

  The expectation is that the proofs above work out mostly unmodified, with the one exception that length-based arguments have to be replaced by using the new order directly.

AI statement Link to heading

Claude Opus X.Y was used by BK to find and prove the results of Degenerate and non-primitive cases.

RGK used OpenAI Sol 5.6 to find an optimal \(w=2\) minimizer schemes based on earlier unsuccesfull manual experiments to find optimal \(k=1\) minimizer schemes. Sol found the connection to comma-free codes, which, in hindsight, indeed show exactly the structures that our initial experiments hinted at that we couldn’t pinpoint ourselves. We then gave it access to the paper by Perrin and Reutenauer (2018), after which Sol came up with the idea of sampling the start of the largest contained code word. It implemented this for both the Scholtz and Eastman orders to confirm it works for small \(\sigma\) and \(k\). This was done overnight using 2 to 3 5-hour limits (of the 20$ plan).

The structure of the proof of optimality of this scheme is our own, following conjectures based on manually inspecting the sampled anchors in small LLM-generated examples similar to Figure 2. Sol 6.1 proved most of the lemmas with access to (Chapters 7 and 8 of) the excellent book (NO_ITEM_DATA:codes-and-automata).

Sol 6.1 was also used to generate initial versions of the figures. LLMs were used to find mistakes and unclarities in the text and proofs. None of the final text was generated using LLMs.

TODO 1.7 Link to heading

• Figures for comma-free codes
• Figures for DBg

Journal? Link to heading

• Discrete mathematics
• JCTA => Combinatorial Theory (CT)
• JCTB
• European Journal of Combinatorics
• TCS: https://www.sciencedirect.com/journal/theoretical-computer-science
• electronic journal of combinatorics
• discussion: https://www.reddit.com/r/math/comments/1rshc0h/thoughts_on_the_flipped_journal_combinatorial/
  • https://www.reddit.com/r/math/comments/1rshc0h/comment/oa7uf85/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button

2 Notes Link to heading

2.1 Graveyard: Scholtz’ construction Link to heading

Scholtz (Scholtz 1969) gives the following construction to construct a comma-free code. Start with \(X_1 = A\). Then repeatedly choose \(x_i\) as an element of \(X_i\) with minimal odd length. Then define \(X_{i+1} = x_i^*(X_i\backslash x_i)\), i.e., remove \(x_i\) from \(X_i\) and then prepend it an arbitrary number of times to each of the remaining elements. This is called Lazard elimination. The resulting set \(U = \cup_{n\geq 1} X_n\) is a Lazard set for the elimination order defined by \(u\preceq v\) if \(|u|\) is odd and \(|v|\) is even, or if they have the same parity and \(u<_rv\) via the radix order. (Scholtz 1969 Prop 6). Note that all odd-length elements in any of the \(X_i\) are eventually chosen as some \(x_j\).

2.2 graveyard: Eastman construction Link to heading

Eastman’s construction. (We should probably drop as much as possible of this and just do the concluding theorem, and use that as a definition instead?)

A second, more complicated, construction is given by Eastman.

Given a word, there is an algorithm to detect if it is in \(D_n(A)^*\) or \(S_n(A)^*\).

2.3 graveyard: Codes Link to heading

• \(x\in X\) is a code word.

This condition is sufficient to imply that \(X\) is a code: otherwise, if \(x_1\dots x_n=y_1\dots y_m\) is some minimal counter example, we would have \(x_1\neq y_1\) and so one would be a prefix of the other, and \(x_n\neq y_m\) so one would be a suffix of the other.

(Roll-up the definitions above into a single dfn of comma-free codes?)

• Every comma-free code is circular (since closing the circle cannot introduce new code words across the boundary).
• A comma-free code on contains primitive words, and at most one element of every conjugacy class under rotation.
• The number of conjugacy classes of primitive words of length \(n\) is \(\ell_n(k) = \frac 1n \sum_{d|n} \mu(d) k^{n/d}\).

By (Eastman 1965)

(In general, this does not hold for even \(n\).)

2.4 Notes2 Link to heading

• every left-branch in the tree has odd length.
  • TODO: Draw some trees

Do we get a \(k=1\) scheme? Link to heading

• lower bound: 2/(w+1), ie 2 along every cycle.
• If we can detect
• need to detect whether the anchor is a prefix or suffix
• can we do that? Then we get a single(!) sampled position

Do we get a \(k=0\) scheme? Link to heading

• if we can distinguish the start vs end of each max code.
• lower bound: ceil((w+k)/w)/(w+k) = 1/w
  • really it’s just 2/(w+1) because larger k is easier and we have the k=1 bound
• for \(k=1\), just pick the first prefix or last suffix char.
• for \(k=0\), increase \(w\) by 1, decrease \(k\) by 1, pick the position ‘outside’ the prefix/suffix.

observations Link to heading

1
2
3
4
5
6
7
8

1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1
│ │ │ └┬┘ │ └┬┘ └┬┘ │ └┬┘ └┬┘ │ │ └┬┘ │ │ └┬┘
│ │ └┬─┘  └┬─┘   │  └┬─┘   │  │ └┬─┘  │ └┬─┘
│ └┬─┘     └──┬──┘   └──┬──┘  └┬─┘    └┬─┘
└┬─┘          │         └──┬───┘       │
 │            └─────┬──────┘           │
 └────────┬─────────┘                  │
          └─────────────┬──────────────┘

We cannot determine is a code is prefix or suffix! Link to heading

0010 is a counterexample:

Its unique maximal codeword is 001. Appending the final bit changes its role:

3 Notes on comma-free codes Link to heading

3.1 Resources Link to heading

We’ll now revisit in detail the aforementioned paper, as well as some papers that precede it:

• codes and automata
• “Comma-Free Codes”, Golomb, Gordon, and Welch (1958)
• “On the Construction of Comma-Free Codes”, Eastman (1965)
• “Maximal and Variable Word-Length Comma-Free Codes”, Scholtz (1969)
• Algèbres de Lie Libres et Monoïdes Libres, Viennot (1978)
  • Lazard factorization is dfn 1.1
• “Hall Sets, Lazard Sets and Comma-Free Codes”, Perrin and Reutenauer (2018)
• slides: http://www-igm.univ-mlv.fr/~perrin/Enseignement/Master2016-2017/
• See [free lie algebras 1993, section 7.2]
• original: [melancon phd thesis]
• [lazard 60]
• not relevant:
  • (NO_ITEM_DATA:comma-free-codes-perrin2)
  • comma free code of Devitt Jackson 1981

(Side note: I can only hope my papers are as beautiful and nice to read as all these older texts. It really is such a joy to read them.)

Following existing work, we use \(A\) to denote the alphabet. A word is a non-empty string of characters of \(A\).

3.2 Golomb’s comma-free codes Link to heading

We start with Golomb, Gordon, and Welch (1958).

(The authors use the term comma-free dictionary even though the paper is titled comma-free codes. Subsequent literature consistently uses code as well. Furthermore they use \(n\) instead of our \(\sigma\) for the size of the alphabet and \(n\) instead of our \(n\) for the length of the word.)

Clearly, \(x,y\in D\) with \(x\neq y\) can never be a rotation of each other, and so \(|D| \leq \frac 1k \sum_{d|n} \mu(d) \sigma^{n/d}\), which counts the number of necklaces (distinct words under rotation) of length \(n\), or equivalently, does inclusion-exclusion (via the Môbius \(\mu\) function) on the divisors \(d\) of \(n\) over the total number of words of length \(n/d\), i.e. \(\sigma^{n/d}\).

They believe that equality can be attained for all odd \(n\) and proves it up to \(n=15\) by giving explicit constructions.

To give an idea (since this will do some foreshadowing for later): for \(n=3\) he considers words \(abc\) with \(a<b\geq c\), which is optimal. For \(n=5\), Golomb et al. use the constraint \(a<b\geq c\) and \(d\geq e\), or otherwise \(a<b<c<d\geq e\). Looking at at the sign of all \(n\) consecutive (cyclic) differences, we get patterns +---, +-+- and +++-, all of which start with an odd number of + and end with an odd number of -. Call this property \(P\). We then have the following construction: because \(n\) is odd, there is always a sequence of + followed by a sequence of - of total odd length. Then we can break the cycle at the boundary of these two, removing the sign that occurs an even number of times, so that indeed we now have a sequence satisfying \(P\).

For \(n=7\), the list of all possible patterns of differences satisfying \(P\) is given and it turns out to work.

For \(n=9\), there may be multiple places where the sequence could be broken. This is solved using a recursive structure: split the word into three words of length 3 satisfying \(a<b\geq c\), and then impose \(w_1 < w_2 \geq w_3\).

For \(n\in \{11,13,15\}\), the same technique can be used. In particular, it works for \(n=15=3\cdot 5\).

The paper then continues with partial results for even \(n\) as well as asymptotic results for \(n\to\infty\). I’ll omit those here.

At this point, I am obliged to quote the application that is listed:

From their researches in the transfer of genetic information from parent to offspring, Crick, Griffith, and Orgel (Crick, Griffith, and Orgel 1957) advance the following hypothesis. Genetic information, they suggest, is encoded into a giant molecule (chromosome) by means of an affixed sequence of nucleotides, of which there are four types. Each such sequence is uniquely decodable into a new protein molecule, consisting of a long sequence of amino acids, of which there are twenty types. They propose that each amino acid is specified by three consecutive nucleotides. However, only twenty of the sixty-four sequences of three nucleotides “make sense”. Crick, Griffith, and Orgel theorize that the twenty sequence of nucleotides actually corresponding to amino acids form a comma-free dictionary. As we have seen, \(W_3(4)=20\), which agrees with the number of amino acids. The reasonableness of this condition can be seen if we think of the sequence of nucleotides as an infinite message, written without punctuation, from which an finite portion must be decodable into a sequence of amino acids by suitable insertion of commas. If the manner of inserting commas were not unique, genetic chaos could result.

I don’t know about you, but I’m literally having teary eyes writing this. Math and science can just be so beautiful, even when it turns out to be wrong. And indeed, Crick et al. use exactly the same \(a<b\geq c\) pattern for their solution.

3.3 Eastman’s construction Link to heading

We continue our journey with (Eastman 1965), who gives a construction for comma-free codes for any odd \(n\). In earlier work [CITE], Eastman already give an explicit construction for all primes \(n\leq 31\), but now a new, recursive method is introduced. I’ll first copy Eastman’s notation, and then give the equivalent in terms of Golomb’s presentation.

For \(\sigma=2\) and \(n=3\), we have {100, 101} as code, which can be represented by {10a} where a indicates a character at least at large as the preceding character (i.e. Golomb’s +).

For \(\sigma=2\), \(n=5\), we get {10Ba}:={1010a, 10aaa}, i.e., where B can be replaced by either 10 or aa. For \(n=7\), we get {10BBa}, where each of the B’s is substituted independently.

Generalizing, pattern \(i\) is 10B..Ba with a total of \(i\) copies of \(B\), and always having odd length. For alphabets \(\sigma>2\), the general pattern is xyB..Ba where \(x>y\) and B is replaced by either any decreasing sequence xy or aa.

For \(n=13\), we get a comma-free code when selecting patterns \(5\), \(200\), and \(101\), where the latter two should be interpreted as the concatenation of patterns \(2\), \(0\), \(0\) and \(1\), \(0\), \(1\) respectively. These latter words have 3 sections. Each section of a word can also be seen as its own value under lexicographic comparison, corresponding to an integer up to \(\sigma^m\) for sections of length \(m\). (Note that by lexicographic value, I do not mean the number of repetitions of \(B\), but rather the value of the entire word. E.g. the value of 110 would be \(v=6\) when \(\sigma=2\).)

We now get to the recursive construction:

Similar to Golomb et al., Eastman now considers the sequence of cyclic differences for any odd length word \(z\) to recover a factorization of a rotation of \(z\) into sections: 0 for increments/equality (\(z_i\leq z_{i+1}\)) and 1 for decrements (\(z_i > z_{i+1}\)). Clearly, a maps to 0, while B maps to either 00 or ?1. A pattern xyB..Ba maps to ?1(00|?1)*0, with the initial question mark corresponding to the wrap-around comparison. y implies 1, a implies 0, and x maps to either 0 or 1. In particular, any sequence of 1 ends in an a and starts in an xy: odd-length sequences of 1 are of the form y(xy)* and even-length sequences are of the form xy(xy)*. Using this, we can fully infer the pattern of x/y/a characters for each cyclic input sequence z. Since \(z\) has odd length and xy characters come in pairs, we get an odd number of a characters and thus an odd number of sections, where each section starts after an odd-length run of a characters.

The proof that \(\mathcal C_{\sigma, n}\) is comma-free is somewhat involved and I have not yet (TODO?) figured out an intuitive summary, so please see the original instead. (Unfortunately, I kinda expect that we’ll need to understand this proof in some detail to be able to prove our final result later on; we’ll see.)

The paper ends with a proof that \(\mathcal C_{\sigma,n}\) is maximal, i.e., that for every aperiodic word of length \(n\), it contains exactly one of its rotations. The proof is by induction on \(n\): first split \(z\) into sections (of which there are \(<n\)) as described above. Then by induction, some rotation of the sections is in the corresponding comma-free code, and we can use that rotation to recover the rotation of \(z\).

So now that we have defined this construction of a comma-free code for arbitrary odd \(n\), the question is what we learn from this. I think one specific reason why this recursive construction works only for odd lengths is the following: an odd number can be written as the sum of an odd number of odd numbers. This means that after doing one such step, we are again left with an odd-length string, so that at last we end with a single (high-order) pattern, and we can simply sample the start position of the rotation of that pattern.

Knuth’s take Link to heading

In The art of computer programming, volume 4, fascicle 5b (todo bibtex), Donald Knuth covers Eastman’s algorithm in exercise 37 with a simplified presentation.

We start with the entire string and repeatedly partition it into longer substrings. Initially, there are \(n\) substrings of length 1, and the number of parts remains odd. Strings are first compared by length, with longer strings being larger, and otherwise compared lexicographically. Knuth then introduces dips: substrings \(z_1\dots z_k\) such that \(z_1\geq \dots\geq z_{k-1} < z_k\), equivalent to xyaaaa strings from before that had a single decrement and then only increments. Every string can be uniquely factored into dips, by starting a dip at every \(z_i < z_{i+1}\) and extending them left as far as possible. We then consider the dips of odd length and right-extend them by as many succeeding even-length dips as possible, to obtain an odd number of odd-length superdips.

Perrin et al.’s take Link to heading

Perrin and Reutenauer (2018) also explain Eastman’s construction in terms of Knuth’s dips and superdips. They define:

• \(S_0(A) = A\);
• \(D_n(A) = D(S_{n-1}(A))\), i.e. $n$-dips are dips over the alphabet \(S_{n-1}(A)\) with the radix order \(u<v\) if either \(|u|<|v|\) or \(|u|=|v|\) and \(u\) is lex smaller than \(v\);
• \(S_n(A) = S(S_{n-1}(A))\), i.e. $n$-superdips are superdips over the alphabet \(S_{n-1}(A)\), also with radix order.

Again, each \(S_n(A)\) contains only words of odd length. A (cyclic) word can be parsed into the form \(D_n(A)*\) or \(S_n(A)*\) by doing this for \(i=1,\dots,n\).

3.4 Scholtz’ construction Link to heading

Here we use a Lazard set:

• \(X_1 = A\)
• \(x_i\) is any word of minimal odd length of \(X_i\)
• \(X_{i+1} = x_i^*(X_i\backslash x_i)\), i.e., any number of repetitions of \(x_i\) followed by another element of \(X_i\).

1
2
3
4

a    | a b
b    | a*b
aab  | b*a*ab = bab aab ...
     | (aab)*

These words also have a specific structure: TODO

In section 2 of the paper, there is not yet the restriction that the chosen words have odd length. The reconstruction in section 3 is as follows:

• start with commas between all characters: ,1,0,1,0,0,
• suppose the first word is 0 (but in this paper, as a suffix). We get ,10,100,
• suppose the second word is 1 (again, as suffix), we get ,10100 after removing the , before ,1. Here, the paper is very confusing and/or buggy: actually we ought to remove the first , in ,1,, but we don’t even have the 2nd comma?!
• Either way, they do a unique ‘bottom up’ construction to go fron a (cyclic) word to a sequence of codewords.

Section 4 then develops comma free codes for odd length.

• Here, code word \(w_{i+1}\) is always chosen as the shortest odd-length word in \(D_i\), using only suffix (or prefix, in our case) constructions.
• The words of odd length \(L\) for a comma-free code.
• For each non-periodic sequence of odd length \(L\), exactly one rotation is in the code.
  • Basically: if a word nor any of its rotations is a code word, then there is some rotation that is the concatenation of code words. But \(L\) is odd and the only non-code words shorter than \(L\) are even and so (somehow; I don’t fully understand) this means this situation cannot be. Thus, there must be some rotation that is a codeword.

Lemma 1: given a word \(c\in D_n\) with \(c\not\in D_j\) for some \(j<n\). Then \(c\) ends in a odd-length word of \(D_j\).

Lemma 2: Let \(f_T\) denote the last \(T\) characters of a code word \(f\). If \(T\) is even, \(f_T\) cannot equal the first \(T\) symbols of any other code word or sequence of code words.

From this, it quickly follows that the code is comma free: for any two code words \(a\) and \(b\), any substring of equal length of \(ab\) must have even overlap with either \(a\) or \(b\), and thus cannot be a code word itself!

See also (NO_ITEM_DATA:scholtz-synchronizing-codes)

3.5 Lyndon words Link to heading

It turns out this theory concerns the factorization of words, and words are “simply” elements of the free Lie algebra (wikipedia) over \(A\). This page links to Hall sets and Lyndon words.

A Lyndon word (Lyndon 1954) is a non-empty string that is the lexicographic minimum over all its rotations. E.g. ab is Lyndon, but ba is not. aabababb is also Lyndon.

One property of Lyndon words is that they admit a (standard) factorization: every non-empty Lyndon word \(w\) can be split into Lyndon words \(w=uv\) with \(v\) as long as possible. The example above factorizes as \(a((ab)((ab)((ab)b)))\). Note how, as we go from left to right, the factors increase in value.

More generally, every word can be formed in a unique way by concatenating a sequence of non-decreasing Lyndon words, called the Lyndon factorization.

3.6 Hall sets Link to heading

Hall sets generalize Lyndon words to arbitrary orders (other than the lexicographic one). Given an order that respects \(u < uv\) for arbitrary words \(u\) and \(v\), Hall words \(w\) are the concatenation of two words \(xy\) with \(x<y\) and either \(y\in A\) or \(y=(z,t)\) with \(z\leq x\).

3.7 Lazard sets Link to heading

Let \(<\) be some order on words. A Lazard set \(Z = \{z_1,\dots, z_k\}\) is a set of words of length \(\leq n\) with \(z_1<z_2<\dots < z_k\) that has the following property:

• For all \(i<j\), \(z_i\) is smaller (under \(<\)) than every non-empty suffix of \(z_j\).

The way we achieve this is by starting with \(Z_1 = A\) and choosing \(z_1 = \min Z_1\).

3.8 Perrin’s construction Link to heading

3.9 LLM overview Link to heading

1
2
3
4
5
6

Goal
Status: complete
Objective: Discover, implement, and verify a local construction algorithm for a globally optimal w=2 sampling scheme
for every odd k and arbitrary alphabet size sigma, using Rust experiments and the local ILP oracle without web search.
Time used: 4h 45m
Tokens used: 2.11M

References Link to heading