OctoInformBeta

OpenAI preprint, September 2026 · §2. Forced occurrence counts · §2

Lemma 2.1: Occurrence bounds for arbitrary count instances, with input length bounds after preprocessing

Forced counts give superstring lower bounds.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Overlapping copies of a word can share symbols in a common superstring. Their occurrences are distinguished by their starting positions, even when those positions lie inside another occurrence.

A symbol is a finite binary string✦, and a word is a finite sequence of symbols.✦ A superstring instance SS is a finite list of words.✦ Write ε\varepsilon for the empty word and s≼Ts\preceq T for contiguous substring containment, including the empty word. The length |s||s| counts symbols, and the total input symbol length LL is the sum in (1), with repeated input words counted as often as they occur in SS. L=∑s∈S|s|.L=\sum_{s\in S}|s|.(1)

A common superstring TT of a superstring instance SS is a word containing every word in SS.✦ s≼Tfor every s∈S.s\preceq T\qquad\text{for every }s\in S.(2) The optimum superstring length OPT⁡(S)\operatorname{OPT}(S) is the infimum of the natural number lengths of common superstrings, as in (3). OPT⁡(S)=inf⁡{n∈ℕ:there is a common superstring T of S with |T|=n}.\operatorname{OPT}(S) =\inf\bigl\{n\in\mathbb N:\text{there is a common superstring }T \text{ of }S\text{ with }|T|=n\bigr\}.(3)✦

For words TT and ss over an alphabet α\alpha, the occurrence set Occ⁡T(s)\operatorname{Occ}_T(s) is the set of starting positions of ss in TT satisfying the length and symbol conditions in (4). The occurrence count occ⁡T(s)\operatorname{occ}_T(s) of a word ss in a word TT is the cardinality of its occurrence set Occ⁡T(s)\operatorname{Occ}_T(s), as in (5). Occ⁡T(s)={x∈{0,…,|T|}:x+|s|≤|T| and T[x+i]=s[i] for every 0≤i<|s|}.\operatorname{Occ}_T(s)= \bigl\{x\in\{0,\ldots,|T|\}:x+|s|\leq |T| \text{ and }T[x+i]=s[i]\text{ for every }0\leq i<|s|\bigr\}.(4)✦ occ⁡T(s)=|Occ⁡T(s)|.\operatorname{occ}_T(s)=\bigl|\operatorname{Occ}_T(s)\bigr|.(5)✦

The Counting Data

A finite count instance D=(V,R,A)D=(V,R,A) over α\alpha consists of finite sets VV and RR of words, called its substring vertices and required words, together with a finite alphabet A⊆αA\subseteq\alpha.✦ The maximum vertex length hh of a finite count instance D=(V,R,A)D=(V,R,A) is the nonnegative integer in (6), taking the value zero when VV is empty. h=max⁡({0}∪{|v|:v∈V}).h=\max\bigl(\{0\}\cup\{|v|:v\in V\}\bigr).(6)✦

For a finite count instance DD, its count recursion operator FDF_D transforms a function assigning nonnegative integer counts to words into the next such count function; the count iteration (mn)(m_n) starts with zero counts and applies this operator repeatedly, as in (7). The forced occurrence count mm of DD is the function obtained after h+1h+1 iterations, as specified by (8). m0(s)=0,mn+1=FD(mn).m_0(s)=0,\qquad m_{n+1}=F_D(m_n).(7)✦ m(s)=mh+1(s).m(s)=m_{h+1}(s).(8)✦ The total forced letter count WW of DD is the sum of the one-letter counts in (9). W=∑c∈Am(c),W=\sum_{c\in A}m(c),(9)✦ where cc in the argument of mm denotes the one-letter word consisting of cc.

For a word ss, its substring set Sub⁡(s)\operatorname{Sub}(s) is the finite set of all contiguous substrings, including ε\varepsilon.✦ For a superstring instance SS, the substring vertex set V(S)V(S) is the set in (10); it contains ε\varepsilon even when SS is empty. V(S)={ε}∪⋃s∈SSub⁡(s).V(S)=\{\varepsilon\}\cup\bigcup_{s\in S}\operatorname{Sub}(s).(10) The irredundant input core C(S)C(S) is the set of distinct nonempty input words whose only containing input word is themselves, as in (11). C(S)={s∈S:s≠ε and every t∈S with s≼t equals s}.C(S)=\{s\in S:s\ne\varepsilon \text{ and every }t\in S\text{ with }s\preceq t\text{ equals }s\}.(11)✦ The input alphabet A(S)A(S) is the set of symbols appearing in the input words.✦ The preprocessed count instance DSD_S of a superstring instance SS is the finite count instance with substring vertices V(S)V(S), required words C(S)C(S), and alphabet A(S)A(S), as in (12); write mSm_S and WSW_S for its forced count and total forced letter count. DS=(V(S),C(S),A(S)).D_S=\bigl(V(S),C(S),A(S)\bigr).(12)✦

The Claim

Theorem 1. Let D=(V,R,A)D=(V,R,A) be a finite count instance, with forced count mm and total forced letter count WW. Let TT be a word containing every word of RR as a contiguous substring. For every word ss, m(s)≤occ⁡T(s).m(s)\leq\operatorname{occ}_T(s).(13)✦ Moreover, W≤|T|.W\leq |T|.(14)✦ For a superstring instance SS, the counts of its preprocessed count instance satisfy WS≤OPT⁡(S).W_S\leq\operatorname{OPT}(S).(15)✦ For every nonempty word ss, mS(s)≤L.m_S(s)\leq L.(16)✦

What Is Checked

The statements (13) and (14) range over arbitrary finite count instances and words containing all their required words, while (15) and (16) concern the preprocessed input instance DSD_S, with symbol lengths throughout and a nonempty word ss in (16).