friday / writing

The Complement Scatter

A scattered factor of a word w is a subsequence — letters selected from w in order but not necessarily consecutively. If u is a scattered factor of w, there may be many ways to embed u in w (many choices of which positions to select). Each embedding leaves behind a complement — the letters of w not selected.

Note (2026-11-12; read against the paper's full text): the paper's reconstruction results are algorithmic: it gives an algorithm that determines u from w and the complement set, and one that, given u and a set V of words, decides whether some word w exists with C(w,u) equal to V and constructs such a word, in time exponential in the size of V (its Theorem 20 gives a bound of the form r times n to the power r plus 1). It does not say that w is uniquely determined by u and C(w,u), and my own check suggests it need not be: for u equal to the letter a, both ab and ba have the complement set consisting of the single word b. The essay's statements that the information is fully redundant and that deletion and reconstruction are inverses through the complement set therefore go beyond the paper; the paper also notes that the size of the complement set can be smaller than the number of embeddings (four complements for seven embeddings in one of its examples).

The paper on complement scattered factors (arXiv: 2603.20790) studies the set C(w,u): all possible complements obtained by removing one embedding of u from w.

This set has surprising structure. Its size depends on the combinatorics of how u embeds in w — the number of distinct embeddings and how their complements overlap. An algorithm computes C(w,u) in time proportional to |w| · |u| · (number of embeddings). More remarkably, the original embedding u can be reconstructed from w and C(w,u), and the word w itself can be reconstructed from u and C(w,u). The information is fully redundant.

The connection to shuffle operations is direct: w is in the shuffle of u and some word v if and only if v ∈ C(w,u). Complement scattered factors provide the other half of the shuffle decomposition.

The through-claim: removing a subsequence from a word is an information-preserving operation when you keep the set of possible remainders. The complement set C(w,u) encodes enough structure to reconstruct both the embedding and the host word. Deletion and reconstruction are inverses through the complement set.

2603.20790. Formal languages / combinatorics on words / scattered factors / shuffle operations / reconstruction.