The Setting
Periodic passages through the hierarchical word graph have a start position and an exit position. Lemma 3.2 concerns the layers obtained by sorting passage exits at each start, with passages aligned to the same full periodic text.
A substring-closed vertex set is a set of finite words over symbols that contains every contiguous substring of each of its words, including the empty word.✦ A hierarchical walk in consists of up steps that append one symbol and down steps that delete the first symbol, with both endpoints of every step in ; empty walks and concatenations of composable walks are allowed.✦ The cost of a hierarchical walk in is its number of up steps.✦ A walk visits a word when that word is one of its vertices, including an endpoint.✦
A down edge threading on with finite token set is an assignment of a nonempty word to each token , together with a successor permutation of such that deleting the first symbol of leaves a prefix of .✦ The induced text at token is defined by (1); negative powers use the inverse permutation. (1)✦ For an integer-indexed text , its finite window lists the symbols at positions , and is empty when .✦ A positive period of is a positive integer satisfying for every integer . The primitive period of an integer-indexed text is its least positive period.✦
Two tokens of a down edge threading are text translation equivalent when their full induced texts agree after an integer shift.✦ For a down edge threading with token set , the primitive text groups are the text translation equivalence classes in , given by (2).✦ For each group , choose a representative token , write , and let be the primitive period of . (2)
Passage Exits and Layers
The tokens fully aligned with the text form the set in (3); alignment here concerns every integer position. Let and enumerate these tokens bijectively as .✦ (3)✦ The unsorted passage exit is the endpoint in (4), where word length counts symbols. (4)✦ For a finite family of ordered values, its sorted value list is its list of values in nondecreasing order, retaining repetitions✦; its th order statistic is the entry at index , starting at zero.✦ The sorted layer exit is the order statistic in (5). (5)✦
A periodic layer for and a nonnegative integer parameter is an integer-valued exit function satisfying (6) and having whenever .✦ The first and last exit positions of a periodic layer with exit function at an integer are and . Write for the set of these layers. (6)
Count Data and Their Budget
A finite count instance consists of finite sets of vertex words , required words , and symbols .✦ A valid finite count instance is a finite count instance for which contains the empty word, is substring-closed, and every symbol in a vertex word belongs to .✦ The count iteration starts with the zero count and applies ’s count recursion at each successive stage.✦ The maximum vertex length and forced occurrence count of a finite count instance are given by (7). (7) The base down multiplicity and total forced letter count are (8), where is the one-letter word, denotes the word obtained by appending to , and subtraction is truncated at zero. (8) A down token of is a pair with and ✦; its token word is .✦ Denote the set of these tokens by . For a valid count instance , its base edge threading assigns each token its token word and chooses a successor permutation of such that deleting the first symbol of each token word leaves a prefix of the next token word.
The Claim
Theorem 1 (Lemma 3.2). Let be a down edge threading on with finite token set , let be a text, and let be a nonnegative integer. If is substring-closed and for every integer , the ordered layer construction is (9). (9)✦ For any , indices and integer , the exits satisfy (10). (10)✦ For all integers , the upward unit-edge multiplicities satisfy (11), with both sets indexed by . (11)✦ If is substring-closed, then for any , any , and integers with , the actual window satisfies (12). (12)✦ Let , with substring-closed and for every integer . For every integer , there is a closed hierarchical walk based at satisfying (13). (13)✦ The primitive text groups of every finite threading satisfy (14). (14)✦ For every valid finite count instance , the specialization to its base edge threading is (15), with groups and aligned token sets taken in . (15)✦
In the paper, the result reads: closed walks with the same periodic text up to translation and least period can be rearranged without changing their edge multiset into pointwise ordered one-turn layers whose exit functions obey (6), each with up cost , and with total cost over all groups.
What Is Checked
The statements range over finite down edge threadings, substring-closed vertex sets where required, integer-indexed texts with a specified period for layer construction and turns, and valid finite count instances for the budget . For sorted exits, monotonicity and the lower bound hold for every text, and the shift identity holds for each period of that text.✦ For count data, every down token has a nonempty vertex word.