Paper deep dive
A strengthening of the MCFL-ness of $O_2$
Marco B. Caminati
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/20/2026, 5:09:36 AM
Summary
This paper presents a strengthened characterization of the multiple context-free language (MCFL) property for the language O2, which consists of words over a two-letter alphabet where each letter appears as often as its inverse. The author provides a new set of derivation rules for pairs of strings (p0, p1) whose concatenation is in O2, introducing a specific side condition in rule (2) that offers more precise information about the parse tree structure compared to previous proofs. The proof relies on analyzing 'bumps' (minimal non-short detours) in string representations.
Entities (6)
Relation Signals (4)
O2 → istypeof → Multiple Context-Free Grammar
confidence 98% · proofs of the fact that O2 is a multiple context-free grammar (MCFG) were given.
Marco B. Caminati → affiliatedwith → Lancaster University
confidence 95% · Thanks: Lancaster University, Leipzig, Germany
Theorem 1 → characterizes → O2
confidence 95% · Theorem 1. Given a pair of words (p0,p1), assume p0p1∈O2. Then (p0,p1) can be derived using the following rules...
Bump → usedinproofof → Theorem 1
confidence 90% · Section 3 introduces the notion of bump, thanks to which the main result is reduced to two theorems
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.
Tags
Links
- Source: https://arxiv.org/abs/2608.18813v1
- Canonical: https://arxiv.org/abs/2608.18813v1
Trouble viewing inline? Open PDF directly →
Full Text
118,702 characters extracted from source content.
Expand or collapse full text
A strengthening of the MCFL-ness of O2O_2 Marco B. Caminati Thanks: Lancaster University, Leipzig, Germany Email: m.caminati@lancaster.ac.uk Affiliation: ORCID: 0000-0002-4529-5442 Abstract In the last years, a number of proofs of the fact that O2O_2 is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems. 1 Introduction For a given natural N, we consider N letters and, for each of them, another letter called its inverse, thus obtaining a set ΣN _N of 2N2N distinct letters; ONO_N is the sub-language of ΣN∗ _N^* consisting of exactly all the words where the number of occurrences of any letter equals the number of occurrences of the inverse of that letter. From a computational linguistics perspective, it is noteworthy to determine where the ONO_N family of languages fits within the established, rich hierarchy of grammars designed to model natural languages. From the standpoint of computational group theory, insights from formal language theory can aid in investigating related groups [5, 4]. This connection has motivated a series of studies [7, 6], culminating in a result showing that ONO_N can be generated by an N-multiple context-free grammar (N-MCFG) for any value of N [3]. The MCFG definition (see for example [2, 1]) provides little control on the sentential forms introduced at each step of a derivation, for example on their lengths. However, the fact that O2O_2 is a multiple context-free language (MCFL) remains valid even if we replace the MCFG given in [1] with a stronger form of grammar which is no longer a MCFG, giving more precise information on how the parse tree of a string in O2O_2 looks like. This is expressed formally by the following theorem, which is the main result of this paper; more specifically, the “more precise information” is given by the side conditions of rule (2): Theorem 1. Given a pair of words (p0,p1) (p_0,p_1 ), assume p0p1∈O2p_0p_1∈ O_2. Then (p0,p1) (p_0,p_1 ) can be derived using the following rules: (p0,p0¯) (p_0, p_0 ) → \ →\ where p0∈Σ2∗ and |p0|≤1 p_0∈ _2^* and |p_0 |≤ 1 (1) (p0p1,q0q1) (p_0p_1,q_0q_1 ) →(p0,q0),(p1,q1) \ →\ (p_0,q_0 ), (p_1,q_1 ) where |p0|=|q0|=1 or |p1|=|q1|=1 |p_0 |= |q_0 |=1 or |p_1 |= |q_1 |=1 (2) (p0p1,q1q0) (p_0p_1,q_1q_0 ) →(p0,q0),(p1,q1) \ →\ (p_0,q_0 ), (p_1,q_1 ) (3) (p0p1q0,q1) (p_0p_1q_0,q_1 ) →(p0,q0),(p1,q1) \ →\ (p_0,q_0 ), (p_1,q_1 ) (4) (p0,p1q0q1) (p_0,p_1q_0q_1 ) →(p0,q0),(p1,q1) \ →\ (p_0,q_0 ), (p_1,q_1 ) (5) In the derivation rules of Theorem 1, p0p_0, q0q_0, p1p_1, q1q_1 are variables representing words. Rule (1) has an empty right hand, meaning that the corresponding pair on the left hand can be derived without any previous operation: such rules are also called axioms. The other rules can be read as follows: if in previous steps both pairs on the right hand side of the arrow have been derived, then the pair on the left hand side can also be derived in the current step. Iterating this procedure any finite number of times, pairs (p,q) (p,q ) can be derived for some particular words p,qp,q of Σ2∗ _2^*; if a given pair (p,q) (p,q ) is thus derivable using rules (1)-(5), we will write (p,q) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (p,q ). The task is to show that any pair (p,q) (p,q ) such that pq∈O2pq∈ O_2 can be derived. In [1], the main effort was to provide a short and elementary proof amenable to proof assistants. In stark contrast, the apparently small addition of the condition in rule (2) notably complicates the proof, requiring an analysis and categorisation of the occurrence of bumps already introduced in [1]. After Section 2, where notations are introduced, Section 3 introduces the notion of bump, thanks to which the main result is reduced to two theorems, respectively proved in Sections 4 and 5. Section 6 concludes. 2 Notations ℕN, ℤ+Z^+, ℤZ are, respectively, the set of natural numbers (including 00), the set of the positive integers and of the integers. ∪, ∩, \ and × are binary, infix symbols for the set-theoretical operations of union, intersection, set difference and cartesian product, respectively; dom and ran are the operators returning the domain and range (also called image), respectively, of a given relation or function (i.e., ranQ=Q(domQ) Q=Q ( Q ) for any relation or function Q). Q−1Q^-1 is the inverse of the relation or function Q, while Q|X .Q |_X is its restriction to the set X⊆domQX Q, and g∘fg f is the composition of the two functions g and f. Throughout the paper, we will use square brackets to denote intervals of integers: [i,j]:=k∈ℤ.i≤k≤j [i,j ]:= \k .i≤ k≤ j \ and ]i,j[:=[i,j]\i,j∀i,j∈ℤ. ]i,j [:= [i,j ] \i,j \∀ i,j . A string or word is a function with domain [0,j] [0,j ] for some j∈ℤj . A function will be called a sequence if it is either a string or has ℕN as domain. Therefore, if p is a non-empty sequence, p(0)p (0 ) is its first entry. cardY Y is the cardinality of the set Y; when Y is a sequence, cardY Y represents its length;11 1 This is consistent with the fact that, under the standard representation of functions as sets of cartesian pairs, the cardinality and length of a sequence do coincide. we will often write |Y| |Y | as a shorthand for cardY Y. The reverse of a string p, denoted p¯ p, is the unique string q such that |p|=|q| |p |= |q | and q(i)=p(|p|−1−i)∀i∈dompq (i )=p ( |p |-1-i )∀ i∈ p; in particular, if p≠∅p≠ , the last entry of p can be indicated with p¯(0) p (0 ), a notation that we will use often in this paper. Given a set X, X∗X^*, X∞X^∞ and XNX^N are, respectively, the set of the strings over X (i.e., whose range is included in X), of the sequences over X, and of the sequences over X having length N for some N∈ℕN . Given X⊆ℕX and a sequence q, ⟨q⟩X q _X is the subsequence of q obtained by cancelling all its entries whose indices are not in X. More formally, build the strictly monotonic sequence p of the natural numbers belonging to X∩domqX∩ q, and set ⟨q⟩X:=q∘p q _X:=q p. We will employ the special notation p−X:=⟨p⟩ℕ -X:= p _N X. When p=⟨q⟩Xp= q _X and X is an integer interval [i,j][i,j], p is called a factor of q (a left factor if i=0i=0, a right factor if q is a string and j=|q|−1j= |q |-1), and we will just write ⟨q⟩ij q _i^j instead of ⟨q⟩[i,j] q _ [i,j ]; a proper factor of q is a factor of q not equal to q. Given a word p0p_0 and a sequence p1p_1, the concatenation of p0p_0 and p1p_1 (written p0∗p1p_0*p_1, or just p0p1p_0p_1 when safe) is the unique sequence p such that ⟨p⟩[0,|p0|−1]=p0 p _ [0, |p_0 |-1 ]=p_0 and p−[0,|p0|−1]=p1p- [0, |p_0 |-1 ]=p_1. We will be studying strings over a set Σ (our alphabet) possessing a certain structure, which we now introduce. Let τ be a given, fixed injection defined on ℤ\0Z \0 \ such that Σ:=ranτ := τ is disjoint from ℤZ, and consider the injective involution on Σ given by ι:=Σ∋x↦τ(−τ−1(x))∈Σ := x τ (-τ^-1 (x ) )∈ . An element of Σ will also be called a letter; a letter x is said to occur in p∈Σ∗p∈ ^* if x∈ranpx∈ p, and the occurrences of x in p are the indices of the set p−1(x)p^-1 ( \x \ ). We will usually write x¯ x in lieu of ι(x) (x ), and will say that x¯ x is the inverse of x. We denote with Σ(+) ^(+) the set τ(ℤ+)τ (Z^+ ), with ΣN _N the set x∈Σ:|τ(−1)(x)|≤N \x∈ : |τ^(-1) (x ) |≤ N \, and with ΣN(+) _N^(+) the set Σ(+)∩ΣN ^(+)∩ _N, where N is any natural number. Furthermore, with a slight abuse, we will also write p¯ p, with p∈Σ∗p∈ ^*, to mean ι∘p p (i.e., the string obtained by inverting all the letters of p). Given x,y∈Σx,y∈ , we write x//yx//y to mean y∈x,x¯y∈ \x, x \, x⊥yx y (and say that x and y are orthogonal) to mean ¬(x//y) (x//y ), and x⊥x for the set of all letters in Σ orthogonal to x. τ naturally induces a linear well-ordering on Σ(+) ^(+): hence, we can use the first lowercase characters a,b,c,d,…a,b,c,d,… to denote its first elements so that, for example, Σ3=a,a¯,b,b¯,c,c¯ _3= \a, a,b, b,c, c \ and Σ2=a,a¯,b,b¯ _2= \a, a,b, b \. A particular string p can be fully described by writing down either the tuple (p(0),p(1),…,p(|p|−1)) (p (0 ),p (1 ),…,p ( |p |-1 ) ) or the concatenation of all its entries (where parentheses can be omitted thanks to associativity of concatenation): p(0)p(1)…p(|p|−1)p (0 )p (1 )… p ( |p |-1 ). We will generally adopt the first writing when the string belongs to ℤNZ^N for some N∈ℕN , and the second when the string is in Σ∗ ^*. The converse of Theorem (1) is proven by an easy induction argument (omitted): Proposition 1. If (p0,q0) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (p_0,q_0 ), then p0q0∈O2p_0q_0∈ O_2. The proof of Theorem 1 is by contradiction: if it is false, then we are allowed to pick a pair (,) ( p, q ) being not derivable using rules (1)-(5), satisfying ∈O2 p q∈ O_2, and minimal in the sense that any other (p,q) (p,q ) satisfying these two properties must necessarily also satisfy |pq|≥|| |pq |≥ | p q |. A quick check shows that it must be ||≥4 | p q |≥ 4. Using rules (4) and (5), we deduce that it also must be ||≠1≠|| | p |≠ 1≠ | q |. Again using rules (4) and (5), we can assume ||≠0≠|| | p |≠ 0≠ | q | because, for example, if a pair (∅,q) ( ,q ) satisfies the same requirements and is not derivable, then any proper binary factorisation (q0,q1) (q_0,q_1 ) of q is also not derivable (if it were, (∅,q0∅q1=q) ( ,q_0 q_1=q ) would also be derivable using rule (5)). To recapitulate, if Theorem 1 is false, then we can find (,)∈Σ2∗×Σ2∗ ( p, q )∈ _2^*× _2^* such that: P1 : ∈O2 p q∈ O_2; P2 : (,) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ ( p, q ); P3 : Any other pair (p,q)∈Σ2∗×Σ2∗ (p,q )∈ _2^*× _2^* satisfying P1 and P2 must also satisfy |pq|≥|| |pq |≥ | p q |; P4 : min||,||≥2 \ | p |, | q | \≥ 2; P5 : (0)≠(0)¯ p (0 )≠ q (0 ) and ¯(0)≠¯(0)¯ p (0 )≠ q (0 ), where P5 imposes that the first letters of p and q, respectively, must not be related by inversion, and that the same holds for their last letters. This follows immediately from P1-P4 by exploiting the particular form of rule (2). It is clear that to proceed we must use the remaining rules ((3), (4) and (5)) to draw more properties of (,) ( p, q ). This is better done by introducing a new representation of Σ∗ ^*, which is the task of the next section. There, we will also use the new representation to state further properties of (,) ( p, q ), and show that they together imply that (,) ( p, q ) cannot exist. We will reach this conclusion by stating and using two theorems, 2 and 3, which are subsequently proven in Sections 4 and 5, respectively. 3 Representing strings in ΣN∗ _N^* as tuples in ℤNZ^N Until the beginning of Section 3.1, N will be a generic positive integer. Consider the additive group (ℤ∞,+) (Z^∞,+ ) of infinite sequences of integers, and let ie_i, for any i∈ℤ+i ^+, be the element of ℤ∞Z^∞ having the i−1i-1-th entry set to 11 and all the remaining ones set to 00 (e.g., 1=(1,0,0,…)e_1= (1,0,0,… )). We consider the unique map μ defined on Σ which associates the i-th letter of Σ(+) ^(+) to ie_i, and preserves inversion: μ(x¯)=−μ(x)μ ( x )=-μ (x ). This map can be naturally extended to a monoid morphism between (Σ∗,∗) ( ^*,* ) (where ∗* denotes word concatenation) and (ℤ∞,+) (Z^∞,+ ) by imposing μ(pq)=μ(p)+μ(q)μ (pq )=μ (p )+μ (q ); moreover, the restriction of μ to any ΣN∗ _N^* can be identified with a monoid morphism from (ΣN∗,∗) ( _N^*,* ) onto (ℤN,+) (Z^N,+ ), which we indicate with μN _N, or just μ when safe. On ℤNZ^N, we also define N maps πi,i=1,…,N _i,i=1,…,N, each taking a tuple and returning its i-th component (e.g., π2((,,,,,))=4 _2 ( (0,4,3 ) )=4). Intuitively, each letter of a word p∈ΣN∗p∈ _N^* can be regarded as a unit step along a certain axis of ℤNZ^N, where the step is in the positive verse if the letter is in Σ(+) (+ ) and in the opposite direction otherwise; μ(p)μ (p ) yields the vector locating the position in ℤNZ^N obtained after performing, starting from the origin, the steps thus dictated by all the letters of p. We therefore call μ(p)μ (p ) the displacement of p; for example, μ(abba¯)=μ(a)+μ(b)+μ(b)−μ(a)=(1,0)+(0,1)+(0,1)−(1,0)=(0,2)μ (abb a )=μ (a )+μ (b )+μ (b )-μ (a )= (1,0 )+ (0,1 )+ (0,1 )- (1,0 )= (0,2 ). Two words p, q such that for any letter the difference between the occurrences of that letter and the occurrences of its inverse is the same for p and for q will return the same value through μ: we will write p≡qp≡ q. Formally, ≡ is the equivalence relation canonically associated to μ: p≡q⇔μ(p)=μ(q)p≡ q μ (p )=μ (q ); ≡N _N will denote its restriction to ΣN∗ _N^*, but we will just write ≡ when this yields no ambiguity. [p]≡ [p ]_≡ denotes the equivalence class to which p belongs. Obviously, given p∈ΣN∗p∈ _N^*, p∈ONp∈ O_N if and only if μ(p)=0Nμ (p )=0_N; in this case, we will say that p is closed. A loop for p∈Σ∗p∈ ^* is a proper factor of p which belongs to [∅]≡\∅ [ ]_≡ \ \; if p has no loops, it is simple; p is self-factoring if it admits a proper factor equivalent to p. Note that any non-empty closed string is self-factoring. While length is defined for any string, a string p∈ΣN∗p∈ _N^* can also be associated another natural number thanks to the representation just described. Recall that the Manhattan (or taxicab) distance between two N-tuples (x1,…,xn) (x_1,…,x_n ), (y1,…,yN) (y_1,…,y_N ) of integers is defined as ∑j=1N|yj−xj| _j=1^N |y_j-x_j |; we denote with ∥ the Manhattan distance of ∈ℤNx ^N from the origin, and we will often use the shorthand notation ∥p∥ p to mean ∥μN(p)∥ _N (p ) for a given p∈ΣN∗p∈ _N^*, calling ∥p∥ p the radius of p. Hence, we now have two natural numbers associated to any p∈ΣN∗p∈ _N^*: |p| |p | is the number of letters of p, while ∥p∥ p is the minimal number of unit steps along all the N directions needed to arrive to μ(p)μ (p ) from the origin. It is obvious that ∥p∥=mincard[p]≡ p = _ [p ]_≡ for any p∈ΣN∗p∈ _N^*: that is, among all strings equivalent to p, those with fewest letters have exactly ∥p∥ p letters; such strings will be called short. An integer interval [i,j] [i,j ] is a detour for p∈ΣN∗p∈ _N^* if [i,j]⊆domp [i,j ] p and ⟨p⟩ij p _i^j is not short (note that this implies j>ij>i and |p|≥2 |p |≥ 2); in this case, ⟨p⟩ij p _i^j will also be called a detour for p, and its radius will be referred to as the radius of the detour. Any detour of a string can be replaced with something shorter without changing the displacement: more precisely, (i,j,p) (i,j,p ) is an m-shortcut for q if [i,j] [i,j ] is a detour for q, m=|p|<|⟨q⟩ij|m= |p |< | q _i^j |, and p≡N⟨q⟩ijp _N q _i^j; ∥p∥ p will be called the radius of the shortcut, and the string ⟨q⟩0i−1p⟨q⟩j+1|q|−1 q _0^i-1\ p\ q _j+1 |q |-1 will also be called an m-shortcut for q. A detour [i,j] [i,j ] for p is an x-bump for p if no proper subset of [i,j] [i,j ] is a detour for p (i.e., any proper factor of ⟨p⟩ij p _i^j is short) and p(i)=xp (i )=x; note this implies that p(j)=x¯p (j )= x, and that p(k)∉x,x¯∀k∈]i,j[p (k )∉ \x, x \∀ k∈ ]i,j [. x is called the direction of the bump. Bx(p)B^x (p ) is the set of all x-bumps of p, and we set B(p):=⋃x∈ΣNBx(p)B (p ):= _x∈ _NB^x (p ). If [i,j] [i,j ] is a detour (bump) for p, the string ⟨p⟩ij p _i^j will also be called a detour (bump) for p. p is short if and only if it has no detours, and any detour contains a bump. Hence: Remark 1. p is short if and only if B(p)=∅B (p )= . Note that if [i,j] [i,j ] is a detour for q, it is always possible to find p such that (i,j,p) (i,j,p ) is a shortcut for q. In the particular case of [i,j] [i,j ] being a bump, there is a particularly simple way of performing this operation: Remark 2. If [i,j] [i,j ] is a bump for p, then p−i,j≡p- \i,j \≡ p, and p−i,jp- \i,j \ is a shortcut for p. Recall that p−i,jp- \i,j \ denotes the operation of cancelling the letters of indices i and j from the string p. This operation will be extensively used in this paper, especially in the case of [i,j] [i,j ] being a bump for p (bump cancelling). In particular, we will typically be dealing with a pair (p0,p1) (p_0,p_1 ) of strings, and wanting to perform bump cancelling on exactly one between p0p_0 and p1p_1. To find a convenient notation in this situation, we first need to introduce a way of denoting all the bumps of p0p_0 and p1p_1 together, but with the possibility of distinguishing which bumps belongs to which string. A notation to attain this goal is the following: Definition 1. Bx(p0,p1):=Bx(p0)∪[i+|p0|,j+|p0|].[i,j]∈Bx(p1), B^x (p_0,p_1 ):=B^x (p_0 )∪ \ [i+ |p_0 |,j+ |p_0 | ].\ [i,j ]∈ B^x (p_1 ) \, B(p0,p1):=⋃x∈ΣNBx(p0,p1) B (p_0,p_1 ):= _x∈ _NB^x (p_0,p_1 ) Now, if we define Definition 2. (p0,p1)−X:=(p0−X,⟨p0p1−X⟩|p0||p0p1|−1) (p_0,p_1 )-X:= (p_0-X, p_0p_1-X _ |p_0 | |p_0p_1 |-1 ), then, when writing (p0,p1)−i,j (p_0,p_1 )- \i,j \ for some [i,j]∈B(p0,p1) [i,j ]∈ B (p_0,p_1 ), it will be clear which bump we are cancelling from which string. Given x∈ΣNx∈ _N, by an x-bump for (p0,p1) (p_0,p_1 ) we mean any element of Bx(p0,p1)B^x (p_0,p_1 ), while by a minimal bump for (p0,p1) (p_0,p_1 ) we mean an element of argmincardBy(p0,p1) _ B^y (p_0,p_1 ) for some y∈ΣNy∈ _N. Note that Bx(p0,p1)⊆Bx(p0p1)B^x (p_0,p_1 ) B^x (p_0p_1 ), and that the converse inclusion is not always true. We will say that (q0,q1) (q_0,q_1 ) is an m-shortcut for (p0,p1) (p_0,p_1 ) if there is k∈0,1k∈ \0,1 \ such that qkq_k is an m-shortcut for pkp_k and q|k−1|=p|k−1|q_ |k-1 |=p_ |k-1 |. Example 1. Let p0:=abaab¯b¯p_0:=abaa b b, p1:=a¯a¯b¯a¯ba¯b¯a¯a¯ba¯baaaap_1:= a a b ab a b a ab abaaaa ∈Σ2∗∈ _2^*. Then (p0,p1)−8,10 (p_0,p_1 )- \8,10 \ is the 11-shortcut of (p0,p1) (p_0,p_1 ) given by (p0,p1′) (p_0,p_1 ), where p1′:=a¯a¯a¯a¯b¯a¯a¯ba¯baaaap_1 := a a a a b a ab abaaaa. Bb(p0,p1)=[1,4],[10,12]B^b (p_0,p_1 )= \ [1,4 ], [10,12 ] \, and the minimal bumps for (p0,p1) (p_0,p_1 ) are exactly 33: [8,10] [8,10 ], [10,12] [10,12 ], and [16,18] [16,18 ]; note that [3,6]∈Ba(p0p1) (p0,p1) [3,6 ]∈ B^a (p_0p_1 ) B^a (p_0,p_1 ) is a bump for p0p1p_0p_1 but not for (p0,p1) (p_0,p_1 ). Another 11-shortcut of (p0,p1) (p_0,p_1 ) is given by (p0,⟨p1⟩04b)=(p0,p1)−([11,16]∪[18,|p0p1|−1]) (p_0, p_1 _0^4\ b )= (p_0,p_1 )- ( [11,16 ]∪ [18, |p_0p_1 |-1 ] ). The first shortcut is obtained by applying Remark 2, while the second is of more general nature, being obtained by substituting a detour of p1p_1 (having radius 11) which is not a bump. Equivalent strings (i.e., strings for which the value of μN _N is the same) will result in the same displacement in different ways, and the definition of μN _N does not include the exact points of ℤNZ^N that the string touches to arrive to its displacement; we now introduce a notation to represent this additional information. Definition 3. Given p∈ΣN∗p∈ _N^*, define p~:=[0,|p|]∋k↦μN(⟨p⟩0k−1). p:= [0, |p | ] k _N ( p _0^k-1 ). p~(0) p (0 ) is the origin, p~(1) p (1 ) is the displacement after stepping according to the first letter of p, and so on; and, naturally, p~(|p|)=μ(p) p ( |p | )=μ (p ). An N-dimensional walk is any string q∈(ℤN)∗q∈ (Z^N )^* such that q=⟨p~⟩ijq= p _i^j for some p∈ΣN∗p∈ _N^*, i,j∈ℕi,j . Note that p~ p is a sequence of sequences in ℤNZ^N, and that not every sequence of sequences in ℤNZ^N is a walk. Referring back to Example 1, two possible bidimensional walks we can construct are p0~=((0,0),(1,0),(1,1),(2,1),(3,1),(3,0),(3,−1)) p_0= ( (0,0 ), (1,0 ), (1,1 ), (2,1 ), (3,1 ), (3,0 ), (3,-1 ) ) and ⟨p0p1~⟩57=((3,0),(3,−1),(2,−1)). p_0p_1 _5^7= ( (3,0 ), (3,-1 ), (2,-1 ) ). To familiarise with the concepts introduced, we present a result which will be useful in the sequel. It shows that two bidimensional short walks joining pairs of suitably positioned points must meet. Lemma 1. Given p0p_0, p1p_1, q0q_0, q1∈Σ2∗q_1∈ _2^*, assume: 1. p0~(|p0|),p0p1~(|p0p1|)=(x0,y0),(x2,y1); \ p_0 ( |p_0 | ), p_0p_1 ( |p_0p_1 | ) \= \ (x_0,y_0 ), (x_2,y_1 ) \; 2. q0~(|q0|),q0q1~(|q0q1|)=(x1,y0),(x3,y1); \ q_0 ( |q_0 | ), q_0q_1 ( |q_0q_1 | ) \= \ (x_1,y_0 ), (x_3,y_1 ) \; 3. x1≥x0x_1≥ x_0and x2≥x3;x_2≥ x_3; 4. B(p1)=B(q1)=∅.B (p_1 )=B (q_1 )= . Then ran(p0p1~|[|p0|,|p0p1|])∩ran(q0q1~|[|q0|,|q0q1|])≠∅. ( p_0p_1|_ [ |p_0 |, |p_0p_1 | ] )∩ ( q_0q_1|_ [ |q_0 |, |q_0q_1 | ] )≠ . Hypothesis (1) requires that the walk whose steps are given by p1p_1 and whose starting point is given by μ2(p0) _2 (p_0 ) goes from (x0,y0) (x_0,y_0 ) to (x2,y1) (x_2,y_1 ) or vice versa. Similarly, hypothesis (2) requires the same for q0q_0, q1q_1, (x1,y0) (x_1,y_0 ), (x3,y1) (x_3,y_1 ). Hypothesis (3) imposes a condition on the relative horizontal position of the endpoints of the walk described by hypothesis (1) with respect to the horizontal position of the endpoints of the walk described by hypothesis (2). Finally, hypothesis (4) requires that both the walks are short. Lemma 1 then states that the two walks must intersect: indeed, ran(p0p1~|[|p0|,|p0p1|]) ( p_0p_1|_ [ |p_0 |, |p_0p_1 | ] ) is the set of points of ℤ2Z^2 touched by the first walk. Figure 1: Three applications of Lemma 1 to the case x0=1x_0=1, y0=1y_0=1, x2=4x_2=4, y1=6y_1=6, x1=5x_1=5, x3=1x_3=1. Before giving the proof, we loiter on possible applications of Lemma 1 in the configuration of points represented in Figure 1, where the circled point locates the origin, x0=1x_0=1, y0=1y_0=1, x2=4x_2=4, y1=6y_1=6, x1=5x_1=5, x3=1x_3=1, the dashed line represents the walk given by p1p_1, and the dotted line that given by q1q_1; the endpoints of the walks are marked with solid dots. In the first case (Figure 1, left), the two walks do not intersect because, while p1p_1 is short, q1q_1 is not, being B(q1)=[5,10].B (q_1 )= \ [5,10 ] \. In the second case (Figure 1, middle), they do not intersect because, while q1q_1 is short, p1p_1 is not, being B(p1)=[0,2],[3,9][8,13].B (p_1 )= \ [0,2 ], [3,9 ] [8,13 ] \. In the third case (Figure 1, right), they do intersect as mandated by the lemma, because both p1p_1 and q1q_1 are short. Note that the only role of p0p_0 and q0q_0 in the lemma is to set the displacement; that is, the application of the lemma depends only on μ(p0)μ (p_0 ) and μ(q0)μ (q_0 ) rather than on p0p_0 and q0q_0 themselves. Proof. Consider the map f associating to each (y0,y1)∈ℤ2 (y_0,y_1 ) ^2 the set consisting of all the tuples (p0,p1,q0,q1,x0,x1,x2,x3) (p_0,p_1,q_0,q_1,x_0,x_1,x_2,x_3 ) whose entries, together with y0y_0 and y1y_1, satisfy hypotheses (1)–(4), together with ran(p0p1~|[|p0|,|p0p1|])∩ran(q0q1~|[|q0|,|q0q1|])=∅ ( . p_0p_1 |_ [ |p_0 |, |p_0p_1 | ] )∩ ( . q_0q_1 |_ [ |q_0 |, |q_0q_1 | ] )= . If, by contradiction, the set M made of the pairs (y0,y1) (y_0,y_1 ) for which f returns a non-empty set were non-empty, then we could take (y0¯,y1¯)∈M ( y_0, y_1 )∈ M such that |y1¯−y0¯| | y_1- y_0 | is minimal. It is easy to see that y1¯≠y0¯ y_1≠ y_0, so that we can assume y1¯>y0¯ y_1> y_0. f((,,,))f ( ( y_0, y_1 ) ) being non empty, we consider (p0′,p1′,q0′,q1′,x0¯,x1¯,x2¯,x3¯) (p_0 ,p_1 ,q_0 ,q_1 , x_0, x_1, x_2, x_3 ) in it such that |p1′q1′| |p_1 q_1 | is minimal. Set p:=p0′p1′p:=p_0 p_1 and q:=q0′q1′q:=q_0 q_1 ; by possibly applying the reversal operation, we can assume μ(p0′)=(x0¯,y0¯)μ (p_0 )= ( x_0, y_0 ), μ(p)=(x2¯,y1¯)μ (p )= ( x_2, y_1 ), μ(q0′)=(x1¯,y0¯)μ (q_0 )= ( x_1, y_0 ), μ(q)=(x3¯,y1¯)μ (q )= ( x_3, y_1 ). Further, set i:=max(p~−1(ℤ×y1−1))i:= ( p^-1 (Z× \y_1-1 \ ) ) (i.e., i is the last step at which the walk p~ p reaches a point of ordinate y1¯−1 y_1-1), j:=max(q~−1(ℤ×y1−1))j:= ( q^-1 (Z× \y_1-1 \ ) ), p1′:=⟨p⟩|p0′|i−1p_1 := p _ |p_0 |^i-1, p1′:=⟨p⟩i|p|p_1 := p _i |p |, q1′:=⟨q⟩|q0′|j−1q_1 := q _ |q_0 |^j-1, q1′:=⟨q⟩j|q|q_1 := q _j |q |. Now, it cannot be p1′(0)=b=q1′(0)p_1 (0 )=b=q_1 (0 ), otherwise the minimality of |y1¯−y0¯| | y_1- y_0 | would be violated. As a consequence, maxi−|p0′|,j−|q0′|>0 \i- |p_0 |,j- |q_0 | \>0, and therefore |p1′q1′|<|p1′q1′|. |p_1 q_1 |< |p_1 q_1 |. (6) We also note that 1. ran(p~|[|p0′|,|p0′p1′|])∩ranq~|[|q0′|,|q0′q1′|]=∅ ( . p |_ [ |p_0 |, |p_0 p_1 | ] )∩ . q |_ [ |q_0 |, |q_0 q_1 | ]= ran(p~|[|p0′|,|p|])∩ran(q~|[|q0′|,|q|])=∅. ( . p |_ [ |p_0 |, |p | ] )∩ ( . q |_ [ |q_0 |, |q | ] )= . 2. B(p1′)=∅=B(q1′)B (p_1 )= =B (q_1 )because B(p1′)=∅=B(q1′)B (p_1 )= =B (q_1 ) and p1′p_1 , q1′q_1 are factors, respectively, of p1′p_1 and of q1′q_1 . 3. (π1∘μ)(p0′p1′)<(π1∘μ)(q0′q1′) ( _1 μ ) (p_0 p_1 )< ( _1 μ ) (q_0 q_1 )by minimality of |y1¯−y0¯| | y_1- y_0 | and the two previous points. 4. B(p1′)=∅=B(q1′)B (p_1 )= =B (q_1 )because B(p1′)=∅=B(q1′)B (p_1 )= =B (q_1 ) and p1′p_1 , q1′q_1 are factors, respectively, of p1′p_1 and of q1′q_1 . If y1¯>y0¯+1 y_1> y_0+1, then we can use the minimality of |y1¯−y0¯| | y_1- y_0 | and the last two points above to draw that ran(p~|[|p0′p1′|,|p|])∩ran(q~|[|q0′q1′|,|q|])≠∅. ( . p |_ [ |p_0 p_1 |, |p | ] )∩ ( . q |_ [ |q_0 q_1 |, |q | ] )≠ . If y1¯=y0¯+1 y_1= y_0+1, then we can use (6) and the last two points in the list above to draw the same conclusion, due to the minimality of |p1′q1′| |p_1 q_1 |. This conclusion clashes with ran(p~|[|p0′|,|p|])∩ran(q~|[|q0′|,|q|])=∅. ( . p |_ [ |p_0 |, |p | ] )∩ ( . q |_ [ |q_0 |, |q | ] )= . ∎ We conclude this section with a final, elementary Remark 3. Let p be a factor of qur∈ΣNqur∈ _N, with |u|≤1 |u |≤ 1. If u′≡u ≡ u, then there is a factor p′≡p ≡ p of qu′rqu r. Proof. Since |u|≤1 |u |≤ 1, u is either fully included in p or not. If not, we just take p′:=p :=p. Otherwise, p′p is the string obtained by replacing u with u′u in p. ∎ 3.1 Proof of Theorem 1 Rules (1)–(5) are invariant with respect to swapping a’s with a¯ a’s, b’s with b¯ b’s, or a’s with b’s and a¯ a’s with b¯ b’s, as well as under reversal of both the strings in the pairs involved, and under swapping the words in the pairs involved. All the notions we will be interested in enjoy the same invariances; for example, (p0,p1) (p_0,p_1 ) has a 11-shortcut if and only if (p¯1,p¯0) ( p_1, p_0 ) has. We will often use these invariances silently; a first consequence is that we can impose that both the components of μ()μ ( p ) are non-negative without affecting the other properties we proved up to this point. We state this new property explicitly in the following proposition, along with others. Proposition 2. P6 If (m,n)=μ() (m,n )=μ ( p ), then minm,n≥0 \m,n \≥ 0; P7 p qis closed and simple; P8 pand q are both non-self-factoring. Proof. We discussed P6 above, while closure of p q was already established (P1). Assume p q has a loop; then the loop must be a factor of either p or q, otherwise we could use rule (3) to derive (,) ( p, q ). We can suppose then that p has a loop (the other case being symmetric): =p1p0p2 p=p_1p_0p_2, p0∈[∅]≡\∅,p_0∈ [ ]_≡ \ , p \. We can further strengthen this to p1≠∅≠p2p_1≠ ≠ p_2 for otherwise we could use rule (3) to derive (,) ( p, q ). By P3, (p1p2,) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (p_1p_2, q ), hence let us proceed by cases on the last rule applied in the derivation of (p1p2,) (p_1p_2, q ); we suppose this rule is (2), the other cases being simpler. Consider p3,p4,q1,q2p_3,p_4,q_1,q_2 such that p1p2=p3q1p_1p_2=p_3q_1, =p4q2 q=p_4q_2, (p3,p4) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (p_3,p_4 ), (q1,q2) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (q_1,q_2 ), 1∈|p3|,|p4|,|q1|,|q2| \1 \∈ \ \ |p_3 |, |p_4 | \, \ |q_1 |, |q_2 | \ \. We only show the subcase |p3|=|p4|=1 |p_3 |= |p_4 |=1, the other being symmetric. Therefore, we have p1p2=xq1p_1p_2=xq_1 and =x¯q2 q= xq_2 for some letter x∈Σ2x∈ _2; since p1≠∅p_1≠ , this implies that =p1p0p2=xq1′p0q1′ p=p_1p_0p_2=xq_1 p_0q_1 with q1′q1′=q1q_1 q_1 =q_1. By P3, then, (q1′p0q1′,q2) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (q_1 p_0q_1 ,q_2 ), so that we can apply rule (2) to contradictorily derive (,) ( p, q ). Hence, p q cannot have a loop. It p were self-factoring, then =q0pq1 p=q_0pq_1 for some p, q0q_0, q1q_1 such that q0q1∈[∅]≡\∅,q_0q_1∈ [ ]_≡ \ , p \ (if it were q0q1=q_0q_1= p, then p q would have a loop, which we escluded). Again by P3, this implies (q0,q1) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (q_0,q_1 ) and (p,) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ (p, q ), which yields to the contradiction (,) 3.44444pt$ [-6.45831pt]0.47787pt12.91663pt [-0.23894pt]8.00003pt0.47787pt -8.00003pt -1.96112pt [8.00003pt] $ $ -8.00003pt 1.96112pt [8.00003pt] $ $$ ( p, q ) using rule (4). Symmetrically, using rule (5), q cannot be self-factoring. ∎ P7, P5 and P8 state three properties which (,) ( p, q ) satisfies; in the sequel, we will be interested in studying whether such properties apply to other string pairs. Therefore, it is convenient to introduce dedicated definitions to help concisely expressing these properties. Definition 4. • P:=(p,q)∈Σ2∗×Σ2∗.pq is closed and simple P:= \ (p,q )∈ _2^*× _2^*.\ pq is closed and simple \ • T:=(p,q)∈Σ2∗×Σ2∗.p≠∅≠q∧(p(0)=q(0)¯∨p¯(0)=q¯(0)¯)T:= \ (p,q )∈ _2^*× _2^*.\ p≠ ≠ q (p (0 )= q (0 ) p (0 )= q (0 ) ) \ • R:=(p,q)∈Σ2∗×Σ2∗.either p or q is self-factoringR:= \ (p,q )∈ _2^*× _2^*.\ either p or q is self-factoring \ P7, P5 and P8 can thus be condensed into the statement (,)∈P . ( p, q )∈ P T R. We are now ready to prove Theorem 1 using the following two theorems, whose proofs are, respectively, in Sections 4 and 5. Theorem 2. Let (p0,p1)∈P (p_0,p_1 )∈ P T R. Assume 1. B(p0,p1)≠∅B (p_0,p_1 )≠ , and 2. Given any minimal bump [i,j] [i,j ] for (p0,p1) (p_0,p_1 ), (p0,p1)−i,j∉P (p_0,p_1 )- \i,j \∉ P T. Then (p0,p1) (p_0,p_1 ) admits a 11-shortcut which belongs to P T. Theorem 3. There is no minimal bump [i,j] [i,j ] for (,) ( p, q ) such that (,)−i,j∈P . ( p, q )- \i,j \∈ P T. Proof of Theorem 1. Theorem 3 grants that (,) ( p, q ) satisfies hypothesis (2) of Theorem 2; if we also manage to prove B(,)≠∅B ( p, q )≠ , we can apply Theorem 2 to (,) ( p, q ), obtaining a 11-shortcut (p,q) (p,q ) of (,) ( p, q ), and we can assume q=q= q. Then (p,q)∈R (p,q )∈ R, otherwise (p,q) (p,q ) would not be derivable by virtue of P3. This means that p is self-factoring and is also a 11-shortcut of p. Now, it is simple to check that a string admitting a 11-shortcut which is self-factoring is also self factoring, by just applying Remark 3. This contradicts (,)∉R ( p, q )∉ R: (,) ( p, q ) cannot exist, and Theorem 1 holds. We reduced to prove B(,)≠∅B ( p, q )≠ . Assuming the contrary equates to say that p and q are both short. This implies, due to P6, that (0),¯(0)⊆a,b \ p (0 ), p (0 ) \ \a,b \ and (0),¯(0)⊆a¯,b¯. \ q (0 ), q (0 ) \ \ a, b \. Properties P7 and P5 further restrict the possibilities to only two: ((0),¯(0),(0),¯(0))∈(a,a,b¯,b¯),(b,b,a¯,a¯). ( p (0 ), p (0 ), q (0 ), q (0 ) )∈ \ (a,a, b, b ), (b,b, a, a ) \. In both these configurations, we apply Lemma 1 to see that there must be distinct i,j∈]0,||−1[i,j∈ ]0, | p q |-1 [ such that μ(⟨⟩0i)=μ(⟨⟩0j).μ ( p q _0^i )=μ ( p q _0^j ). This contradicts the simplicity of p q. ∎ 4 Proof of Theorem 2 For the rest of the paper, we will mostly restrict ourselves to the case of strings in Σ2∗=a,a¯,b,b¯∗ _2^*= \a, a,b, b \^*. Let us first introduce the set of all the possible pairs satisfying the hypotheses of Theorem 2: Z():=(p0,p1)∈P .∀x,i,j.[i,j]∈argmincardBx(p0,p1)→(p0,p1)−i,j∉P .Z (x ):=\ (p_0,p_1 )∈ P T R.\ ∀ x,i,j.\ [i,j ]∈ _ B^x (p_0,p_1 ) → (p_0,p_1 )- \i,j \∉ P T\. Informally, Theorem 2 tells us that if the cancelling of all the minimal bumps breaks either simplicity of p0p1p_0p_1or the property (p0,p1)∉T (p_0,p_1 )∉ T, then one of the bi-dimensional walks p0~ p_0 and p1~ p_1 has a detour of radius 11. While it is not obvious that such a detour exists, it is intuitive that such a detour can always be shortcut without compromising simplicity. However, Theorem 2 additionally tells us that also the property (p0,p1)∉T (p_0,p_1 )∉ T is preserved after shortcutting. To give an overview of the proof, we illustrate a classification of the possible reasons why cancelling a minimal bump from (p0,p1)∈Z (p_0,p_1 )∈ Z breaks the property of being in P T. Let us take, to fix our ideas, a minimal bump of indices [i,j] [i,j ], belonging to p0p_0, and having the form bam+2b¯ba^m+2 b for some m∈ℕm (note that cancelling a bump of length less than 44 cannot break simplicity). Consider the points of ℤ2Z^2 which are “underneath” the bump (marked in Figure 2, I)): it is clear that a necessary condition for (p0,p1)−i,j (p_0,p_1 )- \i,j \ to be in P∩TP∩ T is that the walk p0p1~ p_0p_1 does not touch any of those points, but the canceling of bump [i,j] [i,j ] changes the first or the last letter of p0p_0 or p1p_1, which means that the first or the last point touched by the walk given by the bump [i,j] [i,j ] is in 0,μ(p0) \0,μ (p_0 ) \. This configuration is depicted in for the case of μ(p0)μ (p_0 ) (whose location is represented by a square) in Figure 2 I). Another possibility implying that the cancelling of [i,j] [i,j ] from (p0,p1) (p_0,p_1 ) breaks the property of being in P T is that (p0,p1)−i,j (p_0,p_1 )- \i,j \ is no longer in P: this happens when the walk p0p1~ p_0p_1 touches at least one of the points marked in Figure 2 I. One configuration which is prevented when [i,j] [i,j ] is minimal is the one depicted in Figure 2 I, where another bump [i′,j′]∈Bb(p0,p1) [i ,j ]∈ B^b (p_0,p_1 ) manages to occupy some of those points having strictly smaller length than [i,j] [i,j ]: this should make clear that the points marked in Figure 2 I cannot belong to another bump in Bb(p0,p1)B^b (p_0,p_1 ). This rules out a number of possibilities, and should help the reader to convince herself that only three configurations remain possibly making (p0,p1)−i,j∉P (p_0,p_1 )- \i,j \∉ P. The first is when there is a bump [i′,j′]∈Bb(p0p1) (p0,p1) [i ,j ]∈ B^b (p_0p_1 ) B^b (p_0,p_1 ) shorter than [i,j] [i,j ] (Figure 2 IV). I) I), type C I) IV), type F V), type E VI), type D Figure 2: Configurations of a minimal bump [i,j]∈Bb(p0,p1) [i,j ]∈ B^b (p_0,p_1 ). p0p_0 goes from the circle (the origin) to the square (μ(p0)μ (p_0 )), while p1p_1 goes from the square to the circle. The other two are visualised in Figure 2 V and VI. Each of the configurations in Figure 2 I, IV, V and VI admits a number of symmetric variations (see the discussion on the transformational invariants at the beginning of Section 3.1). We will denote with C1(p0,p1)C_1 (p_0,p_1 ) the family of configurations represented by that in Figure 2 I, with F1(p0,p1)F_1 (p_0,p_1 ) the family of configurations represented by that in Figure 2 IV, with E1(p0,p1)E_1 (p_0,p_1 ) the family of configurations represented by that in Figure 2 V, and with D1(p0,p1)D_1 (p_0,p_1 ) the ones represented by that in Figure 2 VI. Further variations can be obtained by substituting in Figures 2 I, IV, V and VI the square representing μ(p0)μ (p_0 ) with the circle representing the origin: this formally corresponds to swapping p0p_0 with p1p_1. The configurations we obtain in this way from C1(p0,p1)C_1 (p_0,p_1 ), F1(p0,p1)F_1 (p_0,p_1 ), E1(p0,p1)E_1 (p_0,p_1 ), and D1(p0,p1)D_1 (p_0,p_1 ) will be called, respectively, C0(p0,p1)C_0 (p_0,p_1 ), F0(p0,p1)F_0 (p_0,p_1 ), E0(p0,p1)E_0 (p_0,p_1 ), and D0(p0,p1)D_0 (p_0,p_1 ). In the next subsection, we will give formal definitions for C, F, E, D, and will show that any minimal bump for (p0,p1) (p_0,p_1 ) must indeed fall into one of these families, as soon as (p0,p1)∈Z (p_0,p_1 )∈ Z. First, however, we state the following result, formalising the intuition that, if p~ p “first goes up and then goes down”, then Bb(p)≠∅B^b (p )≠ ; recall that πj _j is the projector extracting the j-th component of a tuple, while τ(m)τ (m ) is the m-th letter of Σ(+) (+ ). Proposition 3. Be given p∈ΣN∗p∈ _N^*, m∈[1,…,N]m∈ [1,…,N ], and i, j, k such that j∈]i,k[⊆[0,|p|]j∈ ]i,k [ [0, |p | ]. If (πm∘p~)(i)<(πm∘p~)(j) and (πm∘p~)(j)>(πm∘p~)(k), then [i,k−1]∩Bτ(m)(p)≠∅; ( _m p ) (i )< ( _m p ) (j ) and ( _m p ) (j )> ( _m p ) (k ), then [i,k-1 ]∩ B^τ (m ) (p )≠ ; if (πm∘p~)(i)>(πm∘p~)(j) and (πm∘p~)(j)<(πm∘p~)(k), then [i,k−1]∩Bτ(m)¯(p)≠∅. ( _m p ) (i )> ( _m p ) (j ) and ( _m p ) (j )< ( _m p ) (k ), then [i,k-1 ]∩ B τ (m ) (p )≠ . Proof. Note that the conditions impose that ⟨p⟩ik−1 p _i^k-1 is not short, so that it must have a detour; then use the definition of bump. ∎ 4.1 Classification of minimal bumps The goal of this subsection is to show that the classification of minimal bumps depicted in Figure 2 I, IV, V, and VI is exhaustive, in the sense that any minimal bump of a pair in Z falls into one of those categories (Lemma 2). We start from a definition capturing the configuration depicted in Figure 2 I. Definition 5. Given [i0,j0],[i1,j1]∈Bα(p) [i_0,j_0 ], [i_1,j_1 ]∈ B^α (p ), we say that [i1,j1] [i_1,j_1 ] nests [i0,j0] [i_0,j_0 ] in p iff p~([i0+1,j0])+μ(α)⊆p~([i1+2,j1−1]) p ( [i_0+1,j_0 ] )+ \μ (α ) \ p ( [i_1+2,j_1-1 ] ). Often, it will be safe to just say that [i1,j1] [i_1,j_1 ] nests [i0,j0] [i_0,j_0 ], without explicitly specifying p. Now we introduce definitions for the families of bumps CmC_m, FmF_m, EmE_m and DmD_m (with m∈0,1m∈ \0,1 \) already informally described at the end of last subsection. We start with helper definitions. Definition 6. Eα(p):=[i,j]∈Bα(p).(i=0∧p(|p|−1)=p(1)¯)∨(j=|p|−1∧p(0)=p(|p|−2)¯).E^α (p ):=\\ \ [i,j ]∈ B^α (p ). (i=0 p ( |p |-1 )= p (1 ) ) (j= |p |-1 p (0 )= p ( |p |-2 ) ) \. Fα(p):=[i,j]∈Bα(p).∃m,n∈ℕ,β⊥α,p1.(p=βnα¯p1αβm∧m+n>0∧(p~[0,n]∪p~[|p|−m,|p|])+α~⊆p~[i+2,j−1])F^α (p ):=\ [i,j ]∈ B^α (p ).∃ m,n ,β α,p_1.\\ (p=β^n αp_1αβ^m m+n>0 ( p [0,n ]∪ p [ |p |-m, |p | ] )+ \ α \ p [i+2,j-1 ] )\ The helper definitions above allow us to introduce CmC_m, FmF_m, EmE_m and DmD_m (m∈0,1m∈ \0,1 \) as follows. Definition 7. C0α(p0,p1):=[i,j]∈Bα(p0,p1).(p0,p1)−i,j∈P∧(i=0∨j=|p0p1|−1)C_0^α (p_0,p_1 ):= \ [i,j ]∈ B^α (p_0,p_1 ).\ (p_0,p_1 )- \i,j \∈ P (i=0 j= |p_0p_1 |-1 ) \ C1α(p0,p1):=[i,j]∈Bα(p0,p1).(p0,p1)−i,j∈P∧(i=|p0|∨j=|p0|−1)C_1^α (p_0,p_1 ):= \ [i,j ]∈ B^α (p_0,p_1 ).\ (p_0,p_1 )- \i,j \∈ P (i= |p_0 | j= |p_0 |-1 ) \ E0α(p0,p1):=Eα(p0p1)∩Bα(p0,p1).E_0^α (p_0,p_1 ):=E^α (p_0p_1 )∩ B^α (p_0,p_1 ). E1α(p0,p1):=[i,j]∈Bα(p0,p1).[i−1,i+1],[j−1,j+1]∩(Bα⊥(p0p1) α⊥(p0,p1))≠∅E_1^α (p_0,p_1 ):= \ [i,j ]∈ B^α (p_0,p_1 ). \ [i-1,i+1 ], [j-1,j+1 ] \∩ (B^α (p_0p_1 ) B^α (p_0,p_1 ) )≠ \ F0α(p0,p1):=Fα(p0p1)∩Bα(p0,p1)F_0^α (p_0,p_1 ):=F^α (p_0p_1 )∩ B^α (p_0,p_1 ) F1α(p0,p1):=[i,j]∈Bα(p0,p1). there is [i0,j0]∈Bα(p0p1) α(p0,p1) nested by [i,j]F_1^α (p_0,p_1 ):= \ [i,j ]∈ B^α (p_0,p_1 ). there is [i_0,j_0 ]∈ B^α (p_0p_1 ) B^α (p_0,p_1 ) nested by [i,j ] \ D0α(p0,p1):=[i,j]∈Bα(p0,p1).(i=1∧[0,2]∈B0α⊥(p0,p1))∨(j=|p0p1|−2∧[|p0p1|−3,|p0p1|−1]∈B1α⊥(p0,p1))D_0^α (p_0,p_1 ):=\ [i,j ]∈ B^α (p_0,p_1 ).\\ (i=1 [0,2 ]∈ B_0^α (p_0,p_1 ) ) (j= |p_0p_1 |-2 [ |p_0p_1 |-3, |p_0p_1 |-1 ]∈ B_1^α (p_0,p_1 ) )\ D1α(p0,p1):=[i,j]∈Bα(p0,p1).(i=|p0|+1∧[|p0|,|p0|+2]∈B1α⊥(p0,p1))∨(j=|p0|−2∧[|p0|−3,|p0|−1]∈B0α⊥(p0,p1))D_1^α (p_0,p_1 ):=\ [i,j ]∈ B^α (p_0,p_1 ).\\ (i= |p_0 |+1 [ |p_0 |, |p_0 |+2 ]∈ B_1^α (p_0,p_1 ) ) (j= |p_0 |-2 [ |p_0 |-3, |p_0 |-1 ]∈ B_0^α (p_0,p_1 ) )\ Notation 1. We will write BX(p)B^X (p ) for ⋃x∈XBx(p) _x∈ XB^x (p ), B(p)B (p ) for BΣ(p)B (p ), and similarly for BX(p0,p1)B^X (p_0,p_1 ), C0X(p0,p1)C^X_0 (p_0,p_1 ), B(p0,p1)B (p_0,p_1 ), C0(p0,p1)C_0 (p_0,p_1 ) and so on. Also, we will write CX(p0,p1)C^X (p_0,p_1 ) for C0X(p0,p1)∪C1X(p0,p1)C^X_0 (p_0,p_1 )∪ C^X_1 (p_0,p_1 ), and so on. Finally, we will often use the following more suggestive notations: B]B^] for BaB^a, B[B^[ for Ba¯B a, B⊓B for BbB^b and B⊔B for Bb¯B b. Similarly for C and the other notions introduced in Definition 7. When it is clear from the context, the argument can be dropped, writing, e.g., BαB^α in lieu of Bα(p0,p1)B^α (p_0,p_1 ). The next result is by symmetry. Proposition 4. For (p0,p1)∈P (p_0,p_1 )∈ P, F0α(p0,p1)=∅→F1α(p1,p0)=∅F_0^α (p_0,p_1 )= →F_1^α (p_1,p_0 )= and E0α(p0,p1)=∅→E1α(p1,p0)=∅E_0^α (p_0,p_1 )= →E_1^α (p_1,p_0 )= . Proposition 5. Let (p0,p1)∈P (p_0,p_1 )∈ P, set p:=p0p1p:=p_0p_1 and assume F0α(p0,p1)∩Bkα(p0,p1)≠∅F_0^α (p_0,p_1 )∩ B_k^α (p_0,p_1 )≠ for some α∈Σ2α∈ _2, k∈0,1k∈ \0,1 \. Then l:=p~−1(α~)l:= p^-1 ( α ) is uniquely defined and belongs to k|p0|+[3−k,|pk|−2−k]k |p_0 |+ [3-k, |p_k |-2-k ]. Moreover, if we define (i0,j0,q0):=(0,l−1,α) if k=0(l−|p0|,|p1|−1,α¯) if k=1, (i_0,j_0,q_0 ):= \ aligned & (0,l-1,α )& if k=0\\ & (l- |p_0 |, |p_1 |-1, α )& if k=1, aligned . then (i0,j0,q0) (i_0,j_0,q_0 ) is a 11-shortcut of pkp_k. Proof. Consider [i,j]∈F0α∩Bkα [i,j ]∈ F_0^α∩ B_k^α. By definition of F0αF_0^α, α~∈p~[i+2,j−1] α∈ p [i+2,j-1 ]. By simplicity of p, this implies that l is uniquely defined and lies in [i+2,j−1] [i+2,j-1 ]. Moreover, the definition of F0F_0 also implies i>0i>0 and j<|p|−1j< |p |-1, so that 4≤i+3≤j 4≤ i+3≤ j l∈[3,|p|−3]. l∈ [3, |p |-3 ]. (7) When k=0k=0, p~0(l)=α~ p_0 (l )= α and |p0|≥j |p_0 |≥ j, so that, using (7), ⟨p0⟩0l−1∼α p_0 _0^l-1 α and |⟨p0⟩0l−1|≥|⟨p0⟩02|=3>|α| | p_0 _0^l-1 |≥ | p_0 _0^2 |=3> |α |. When k=1k=1, i≥|p0|i≥ |p_0 |, p~(l)=p~0+p~1(l−|p0|)=α~ p (l )= p_0+ p_1 (l- |p_0 | )= α and p~0+p~1(|p1|)= p_0+ p_1 ( |p_1 | )=0, so that ⟨p1⟩l−|p0||p1|−1∼α¯ p_1 _l- |p_0 | |p_1 |-1 α. Furthermore, using (7) yields l≤|p|−3=|p0|+|p1|−3l≤ |p |-3= |p_0 |+ |p_1 |-3, so that 0≤l−|p0|≤|p1|−30≤ l- |p_0 |≤ |p_1 |-3 and |⟨p1⟩l−|p0||p1|−1|≥|⟨p1⟩|p1|−3|p1|−1|=3>|α¯| | p_1 _l- |p_0 | |p_1 |-1 |≥ | p_1 _ |p_1 |-3 |p_1 |-1 |=3> | α |. ∎ Proposition 6. Let p∈Σ2∗p∈ _2^* be simple, and [i1,j1],[i0,j0]∈Bα(p) [i_1,j_1 ], [i_0,j_0 ]∈ B^α (p ). Suppose that p~[i0+1,j0]+α∩p~[i1+2,j1−1]≠∅ p [i_0+1,j_0 ]+α∩ p [i_1+2,j_1-1 ]≠ . Then [i1,j1] [i_1,j_1 ] nests [i0,j0] [i_0,j_0 ]. Proof. It must be |p|>2 |p |>2, i0+1<j0i_0+1<j_0, i1+2<j1i_1+2<j_1. Consider the functions f0:[i0+1,j0]∋n↦p~(n)f_0: [i_0+1,j_0 ] n p (n ) and f1:[i1+2,j1−1]∋n↦p~(n)−α~f_1: [i_1+2,j_1-1 ] n p (n )- α. Without loss of generality, we set α:=bα:=b, so that ran(π2∘f0)=ran(π2∘f1)=y ( _2 f_0 )= ( _2 f_1 )= \y \ for some y∈ℤy . ran(π1∘f0) ( _1 f_0 ) and ran(π1∘f1) ( _1 f_1 ) being integer intervals, we can set [k0,l0]:=ran(π1∘f0) [k_0,l_0 ]:= ( _1 f_0 ) and [k1,l1]:=ran(π1∘f1) [k_1,l_1 ]:= ( _1 f_1 ). If it were k0<k1k_0<k_1, then it would be l0≥l1l_0≥ l_1 due to the hypothesis. Hence, k1−1k_1-1 would be in [k0,l0] [k_0,l_0 ], so that (k1−1,y)=p~(j1)∈ranf0=p~[i0+1,j0] (k_1-1,y )= p (j_1 )∈ f_0= p [i_0+1,j_0 ]. This would imply, by simplicity, that j0=|p|j_0= |p | and j1=0j_1=0, which is impossible. Analogously, one shows l0≤l1l_0≤ l_1. Ultimately, ranf0⊆ranf1 f_0 f_1, which is the thesis. ∎ Proposition 7. Let p∈Pp∈ P, and [i1,j1]∈Bα(p) α(p) [i_1,j_1 ]∈ B^α (p ) E^α (p ). Assume that 1. [i1−1,i1+1],[j1−1,j1+1]∩Bα⊥(p)=∅ \ [i_1-1,i_1+1 ], [j_1-1,j_1+1 ] \∩ B^α (p )= and that 2. p−i1,j1p- \i_1,j_1 \ is not simple. Then either [i1,j1]∈Fα(p) [i_1,j_1 ]∈ F^α (p ) or [i1,j1] [i_1,j_1 ] nests some [i0,j0]∈Bα(p) [i_0,j_0 ]∈ B^α (p ). Proof. From hypothesis 2, |p|>2 |p |>2, j1>i1+2j_1>i_1+2 and ⟨p⟩i1j1=αβj1−i1−1α¯ p _i_1^j_1=αβ^j_1-i_1-1 α for some β⊥αβ α. Set M:=p~−1(p~[i1+2,j1−1]−α~).M:= p^-1 ( p [i_1+2,j_1-1 ]- α ). M is not empty because p−i1,j1p- \i_1,j_1 \ is not simple. Define h:M∋i↦⋃J⊆M.J is an interval ∧i∈J.h:M i \J M.J is an interval i∈ J \. ranh h is the coarsest partition of M among those consisting of intervals. As such, it is non empty. We consider a generic [i,j]∈ranh [i,j ]∈ h, and prove the following facts: i≤j<i1−1<j1 or i1<j1<j1+2<i≤j i≤ j<i_1-1<j_1 or i_1<j_1<j_1+2<i≤ j (8) i−1∈domp~→p(i−1)=α i-1∈ p → p (i-1 )=α (9) j+1∈domp~→p(j)=α¯. j+1∈ p → p (j )= α. (10) Proof of (8): since p~[i1+2,j1−1]−α~∩p~[i1,j1+1]=∅, p [i_1+2,j_1-1 ]- α∩ p [i_1,j_1+1 ]= , it must be [i1,j1+1]∩[i,j]=∅ [i_1,j_1+1 ]∩ [i,j ]= , which means that either i≤j<i1<j1i≤ j<i_1<j_1 or i1<j1+1<i≤ji_1<j_1+1<i≤ j. This can be strengthened to the wanted inequality: indeed, if it were j=i1−1j=i_1-1, then p~(i1)−p~(i1−1)=−β~ p (i_1 )- p (i_1-1 )=- β, so that ⟨p⟩i1−1i1+1=β¯αβ p _i_1-1^i_1+1= βαβ, which is prevented by hypothesis 1. Similarly, i can be shown being not equal to j1+2j_1+2. Proof of (9): we note that it cannot be p(i−1)=α¯p (i-1 )= α, for then it would be p~(i−1)∈p~[i1+2,j1−1] p (i-1 )∈ p [i_1+2,j_1-1 ], which would imply i−1∈[i1+2,j1−1]i-1∈ [i_1+2,j_1-1 ] by simplicity, thus violating (8). By exclusion, it hence suffices to show that it cannot be p(i−1)//βp (i-1 )//β, which we do by contradiction. p~(i−1)∈p~[i1+1,j1]−α~ p (i-1 )∈ p [i_1+1,j_1 ]- α, while, by construction of h, it cannot be p~(i−1)∈p~[i1+2,j1−1]−α~ p (i-1 )∈ p [i_1+2,j_1-1 ]- α, so that p~(i−1)∈p~i1+1,j1−α~=p~i1,j1+1 p (i-1 )∈ p \i_1+1,j_1 \- α= p \i_1,j_1+1 \. Now, it cannot be i−1∈i1,j1+1i-1∈ \i_1,j_1+1 \ due to (8), hence the only possibility is that 0,|p| \0, |p | \ includes i−1i-1, together with one element of i1,j1+1 \i_1,j_1+1 \. Since i∈domp~i∈ p, this implies i−1=0i-1=0, and hence j1+1=|p|j_1+1= |p |. Ultimately, we draw p(|p|−1)=α¯p ( |p |-1 )= α, p(|p|−2)=βp ( |p |-2 )=β, and p(0)=β¯p (0 )= β. The last fact follows from noting that p~(i)∈p~[i1+2,|p|−2]−α~⊆−nβ~.n∈ℤ+. p (i )∈ p [i_1+2, |p |-2 ]- α \-n β.n ^+ \. This violates the hypothesis [i1,j1]∉Eα(p) [i_1,j_1 ]∉ E^α (p ). Proof of (10): Analogous to that of (9). Now we proceed by cases. There is [i0,j0]∈ranh [i_0,j_0 ]∈ h such that i0−1∈domp~i_0-1∈ p and j0+1∈domp~:j_0+1∈ p: then, using (9) and (10), p(i0−1)=α p (i_0-1 )=α and p(j0)=α¯, p (j_0 )= α, which implies i0<j0i_0<j_0 by simplicity. Moreover, for every i=i0…j0i=i_0… j_0, p~(i)∈M p (i )∈ M, so that for every i=i0…j0−1i=i_0… j_0-1, p(i)p (i ) must be parallel to β. This means that [i0,j0]∈Bα(p) [i_0,j_0 ]∈ B^α (p ) and hence that [i1,j1] [i_1,j_1 ] nests [i0,j0] [i_0,j_0 ] by definition of M. Remaining cases: consider [i,j]∈ranh≠∅ [i,j ]∈ h≠ . Since we are excluding the previous case, it must be either i=0i=0 or j=|p|j= |p |, which, p being closed, implies that 0,|p|⊆M \0, |p | \ M; given that M⊂[0,|p|]M⊂ [0, |p | ], this yields that [0,j0],[|p|−i0,|p|]⊆ranh \ [0,j_0 ], [ |p |-i_0, |p | ] \ h for some i0,j0∈ℕi_0,j_0 , with j0<|p|−i0j_0< |p |-i_0. Since [0,j0]⊆M [0,j_0 ] M, it must be p(i)⊥αp (i ) α for every i=0…j0−1i=0… j_0-1, while p(j0)=α¯p (j_0 )= α by (10); p being simple, β1j0α _1^j_0α must be a left factor of p for some β1⊥α _1 α. Analogously, p[|p|−i0,|p|−1]⊥αp [ |p |-i_0, |p |-1 ] α, and p(|p|−i0−1)=αp ( |p |-i_0-1 )=α using (9), so that α¯β2i0 α _2^i_0 must be a right factor of p for some β2⊥α _2 α. Now, since |p|>2 |p |>2 and p is closed, it cannot be j0+i0=0j_0+i_0=0, otherwise simplicity of p would fail; this in turn implies that we can take β2=β1 _2= _1. [i1,j1]∈Fα(p) [i_1,j_1 ]∈ F^α (p ) by definition. ∎ Proposition 8. Let (p0,p1)∈P (p_0,p_1 )∈ P, [i1,j1]∈Bα(p0,p1) [i_1,j_1 ]∈ B^α (p_0,p_1 ) and assume that 1. [i1−1,i1+1],[j1−1,j1+1]∩Bα⊥(p0,p1)=∅ \ [i_1-1,i_1+1 ], [j_1-1,j_1+1 ] \∩ B^α (p_0,p_1 )= 2. (p0,p1)−i1,j1∉P. (p_0,p_1 )- \i_1,j_1 \∉ P. Then either [i1,j1]∈Eα(p0,p1)∪Fα(p0,p1) [i_1,j_1 ]∈ E^α (p_0,p_1 )∪ F^α (p_0,p_1 ) or there is [i0,j0]∈Bα(p0,p1) [i_0,j_0 ]∈ B^α (p_0,p_1 ) nested by [i1,j1] [i_1,j_1 ]. Proof. Let p:=p0p1p:=p_0p_1 and assume [i1,j1]∉E1α(p0,p1) [i_1,j_1 ]∉ E_1^α (p_0,p_1 ). Then, by definition 7 and hypothesis 1, [i1−1,i1+1],[j1−1,j1+1]∩Bα⊥(p)=∅ \ [i_1-1,i_1+1 ], [j_1-1,j_1+1 ] \∩ B^α (p )= . After applying Proposition 7, there are three cases: Case [i1,j1]∈Eα(p)∪Fα(p): [i_1,j_1 ]∈ E^α (p )∪ F^α (p ): then [i1,j1]∈E0α(p0,p1)∪F0α(p0,p1) [i_1,j_1 ]∈ E_0^α (p_0,p_1 )∪ F_0^α (p_0,p_1 ) by definition. There is [i0,j0]∈Bα(p0,p1) [i_0,j_0 ]∈ B^α (p_0,p_1 ) nested by [i1,j1] [i_1,j_1 ]: immediate. There is [i0,j0]∈Bα(p) α(p0,p1) [i_0,j_0 ]∈ B^α (p ) B^α (p_0,p_1 ) nested by [i1,j1] [i_1,j_1 ]: then [i1,j1]∈F1α(p0,p1) [i_1,j_1 ]∈ F^α_1 (p_0,p_1 ) by definition. ∎ Proposition 9. Let (p0,p1)∈P (p_0,p_1 )∈ P T, [i1,j1]∈Bα(p0,p1) [i_1,j_1 ]∈ B^α (p_0,p_1 ). Assume that 1. [i1−1,i1+1],[j1−1,j1+1]∩Bα⊥(p0,p1)=∅ \ [i_1-1,i_1+1 ], [j_1-1,j_1+1 ] \∩ B^α (p_0,p_1 )= 2. (p0,p1)−i1,j1∉P . (p_0,p_1 )- \i_1,j_1 \∉ P T. Then either [i1,j1]∈Cα(p0,p1)∪Eα(p0,p1)∪Fα(p0,p1) [i_1,j_1 ]∈ C^α (p_0,p_1 )∪ E^α (p_0,p_1 )∪ F^α (p_0,p_1 ) or there is [i0,j0]∈Bα(p0,p1) [i_0,j_0 ]∈ B^α (p_0,p_1 ) nested by [i1,j1] [i_1,j_1 ]. Proof. Thanks to Proposition 8 and hypotheses, we can assume (p0,p1)−i1,j1∈P∩T (p_0,p_1 )- \i_1,j_1 \∈ P∩ T. In the case j1<|p0|j_1< |p_0 |, this implies that the first or the last letter of p0−i1,j1p_0- \i_1,j_1 \ (or both) are different than those of p0p_0; this can only happen when 0,|p0|−1∩i1,j1≠∅ \0, |p_0 |-1 \∩ \i_1,j_1 \≠ , yielding [i1,j1]∈Cα(p0,p1) [i_1,j_1 ]∈ C^α (p_0,p_1 ) by definition. The other case, i1≥|p0|i_1≥ |p_0 |, is similar. ∎ Lemma 2. Let (p0,p1)∈Z (p_0,p_1 )∈ Z, and [i,j]∈argmincardBα(p0,p1) [i,j ]∈ _ B^α (p_0,p_1 ) for some α. Then [i,j]∈Cα(p0,p1)∪Dα(p0,p1)∪Eα(p0,p1)∪Fα(p0,p1). [i,j ]∈ C^α (p_0,p_1 )∪ D^α (p_0,p_1 )∪ E^α (p_0,p_1 )∪ F^α (p_0,p_1 ). Proof. By cases. Case [i−1,i+1],[j−1,j+1]∩Bα⊥(p0,p1)≠∅ \ [i-1,i+1 ], [j-1,j+1 ] \∩ B^α (p_0,p_1 )≠ : consider k∈i,jk∈ \i,j \ such that [k−1,k+1]∈Bα⊥(p0,p1) [k-1,k+1 ]∈ B^α (p_0,p_1 ). Note that p0p1−k−1,k+1p_0p_1- \k-1,k+1 \ is still simple; moreover, no element of B(p0,p1)B (p_0,p_1 ) has cardinality less than 3=card[k−1,k+1]3= [k-1,k+1 ], because (p0,p1)∈P (p_0,p_1 )∈ P T R. Hence, by definition of Z, (p0,p1)−k−1,k+1∈P∩T (p_0,p_1 )- \k-1,k+1 \∈ P∩ T. Since (p0,p1)∉T (p_0,p_1 )∉ T, this implies that k−1,k+1∩0,|p0|−1,|p0|,|p0p1|−1≠∅ \k-1,k+1 \∩ \0, |p_0 |-1, |p_0 |, |p_0p_1 |-1 \≠ →k−1∈0,|p0|∨k+1∈|p0|−1,|p0p1|−1 → k-1∈ \0, |p_0 | \ k+1∈ \ |p_0 |-1, |p_0p_1 |-1 \ →(k=i∧i∈1,|p0|+1)∨ → (k=i i∈ \1, |p_0 |+1 \ ) (k=j∧j∈|p0|−2,|p0p1|−2): (k=j j∈ \ |p_0 |-2, |p_0p_1 |-2 \ ): [i,j]∈Dα [i,j ]∈ D^α by definition. Case [i−1,i+1],[j−1,j+1]∩Bα⊥(p0,p1)=∅ \ [i-1,i+1 ], [j-1,j+1 ] \∩ B^α (p_0,p_1 )= : by definition of Z, (p0,p1)−i,j∉P (p_0,p_1 )- \i,j \∉ P T. We can hence invoke Proposition 9 to obtain that [i,j]∈Cα∪Eα∪Fα [i,j ]∈ C^α∪ E^α∪ F^α, because if there were a bump nested by [i,j] [i,j ], it would have a strictly smaller cardinality. ∎ 4.2 Bumps in C∪D∪EC∪ D∪ E Proposition 10. Let (p0,p1)∈P(p_0,p_1)∈ P, and assume ∀[i,j]∈Bβ,β¯(p0,p1).card[i,j]>3.∀ [i,j ]∈ B \β, β \ (p_0,p_1 ).\ [i,j ]>3. Then, given [i1,j1]∈Bα(p0,p1) [i_1,j_1 ]∈ B^α (p_0,p_1 ), β⊥αβ α, either [i1,j1] [i_1,j_1 ] nests some [i0,j0]∈Bα(p0,p1) [i_0,j_0 ]∈ B^α (p_0,p_1 ), or p0p1−i1,j1p_0p_1- \i_1,j_1 \ is simple and closed, or [i1,j1]∈Eα∪F.α [i_1,j_1 ]∈ E^α∪ F^α. Proof. This is an immediate corollary of Proposition 8: let us assume, by contradiction, that p0p1−i1,j1p_0p_1- \i_1,j_1 \ is not simple; this triggers the second hypothesis of Proposition 8. The inequality hypothesis triggers the first one, and we obtain the thesis. ∎ Proposition 11. Let p∈Σ2∗p∈ _2^* be simple, α∈Σ2α∈ _2, i,j∈ℤ+i,j ^+, and suppose Bα(p)=∅B^α (p )= . Then Bα(p−i)=∅, and ([i,j]∈Bβ(p)∧β⊥α)→Bα(p−i,j)=∅. B^α (p-i )= , and ( [i,j ]∈ B^β (p ) β α ) → B^α (p- \i,j \ )= . Proof. Let us prove only the second thesis, since the first one is simpler and uses similar ideas. By simplicity, we can assume that ⟨p⟩ij=bam+1b¯ p _i^j=ba^m+1 b for some m∈ℕm , so that β=bβ=b and α∈a,a¯α∈ \a, a \. By contradiction, consider [h,k]∈Bα(q:=p−i,j) [h,k ]∈ B^α (q:=p- \i,j \ ). The interior am+1a^m+1 of the canceled bump cannot be included between the positions h and k, since this is a string whose alphabet is either b \b \ or b¯ \ b \. So it’s either q(k)q (k ) coinciding with the first a of that interior, or h coinciding with its last a. Let us take the first option (the second being analogous). Then the interior of [h,k][h,k] must be made of b¯ b, otherwise we would violate the hypothesis Bα(p)=∅B^α (p )= . But then p would have a factor b¯b bb, violating simplicity. ∎ Lemma 3. The set (p0,p1)∈P.∃i,j∈ℤ+,α⊥β.βαiβ¯ is a left factor of p0∧\ (p_0,p_1 )∈ P.\ ∃ i,j ^+,α β.\ βα^i β is a left factor of p_0\ β¯αjβ is a right factor of p0∧Bα,α¯(p0)=∅=Bα,α¯(p1) βα^jβ is a right factor of p_0\ \ B^α, α (p_0 )= =B^α, α (p_1 )\ is empty. Proof. Suppose it is not, call it M and consider an element (p0,p1) (p_0,p_1 ) of M such that |p0p1| |p_0p_1 | is minimal. We can assume p0=ba¯i0b¯p2=p4b¯a¯j0bp_0=b a^i_0 bp_2=p_4 b a^j_0b for some i0,j0∈ℤ+i_0,j_0 ^+. By definition of M, B[,](p0)=∅=B[,](p1). B^[,] (p_0 )= =B^[,] (p_1 ). (11) Let us set p:=p0p1p:=p_0p_1, (x1,y1):=p~(i0+2)=(−i0,0) (x_1,y_1 ):= p (i_0+2 )= (-i_0,0 ), (x2,y2):=p~(|p4|) (x_2,y_2 ):= p ( |p_4 | ), and (x3,y3):=p~(|p0|) (x_3,y_3 ):= p ( |p_0 | ). Note that it must be 0>x1≥x2>x30>x_1≥ x_2>x_3, because B[(p0)=∅B^[ (p_0 )= . If it were p1(0)=ap_1 (0 )=a, then j0>1j_0>1 by simplicity, so that (p0−(|p0|−2),p1−0) (p_0- ( |p_0 |-2 ),p_1-0 ) would still be in M, contradicting p’s minimality; on the other hand, it cannot be p1(0)=a¯p_1 (0 )= a, because B[(p1)=∅B^[ (p_1 )= : we must conclude p1(0)=bp_1 (0 )=b. Indeed, we can strengthen this by noting that the first letter of p1p_1 different from b cannot be a¯ a, because B[(p1)=∅B^[ (p_1 )= , so that p1p_1 must admit bi5ab^i_5a as a left factor, with i5∈ℤ+i_5 ^+; this can be made even stronger by noting that the first letter of p1p_1 following the left factor bi5ab^i_5a cannot be b¯ b, due to the minimality of p and Proposition 11: p1p_1 admits bi5aγb^i_5aγ, where γ∈Σ2\b¯γ∈ _2 \ b \. Analogously, p1p_1 admits δabj5δab^j_5 as a right factor for some j5∈ℤ+j_5 ^+, δ∈Σ2\b¯δ∈ _2 \ b \. By a similar minimality argument we also draw that j0=i0=1j_0=i_0=1; to recapitulate: bi5aγ is a left factor of p1, b^i_5aγ is a left factor of p_1, δabj5 is a right factor of p1, δ ab^j_5 is a right factor of p_1, i0=j0=1. i_0=j_0=1. (12) Now, y2=y3y_2=y_3, so that we can apply 1 to the pairs ((0,0),(x1,y1)) ( (0,0 ), (x_1,y_1 ) ) and ((x2,y2),(x3,y3)), ( (x_2,y_2 ), (x_3,y_3 ) ), obtaining that B(p6)∪B(p1)≠∅,B (p_6 )∪ B (p_1 )≠ , where p6p_6 is the proper factor of p0p_0 joining the points (x1,y1) (x_1,y_1 ) and (x2,y2) (x_2,y_2 ). Combined with (11), this tells us that the following set is non-empty: [i,j]∈B⊓,⊔(p0,p1).[i,j]⊆[i1,j1]∨[i,j]⊆[|p0|,|p|−1], \ [i,j ]∈ B , (p_0,p_1 ). [i,j ] [i_1,j_1 ] [i,j ] [ |p_0 |, |p |-1 ] \, where i1,j1i_1,j_1 are such that ⟨p0⟩i1j1=p6 p_0 _i_1^j_1=p_6. Hence, consider an element [i2,j2] [i_2,j_2 ] of it having minimal cardinality; to fix the ideas, we assume [i2,j2]∈B⊓(p0,p1), [i_2,j_2 ]∈ B (p_0,p_1 ), with the proof for the case [i2,j2]∈B⊔(p0,p1) [i_2,j_2 ]∈ B (p_0,p_1 ) being similar. p−i2,j2p- \i_2,j_2 \ cannot be in P for, if it were, (p0,p1)−i2,j2 (p_0,p_1 )- \i_2,j_2 \ would also be in M by Proposition 11. Moreover, E(p0,p1)=∅E (p_0,p_1 )= due to (12), and F(p0,p1)=∅F (p_0,p_1 )= because of (11). By Proposition 10, then, [i2,j2] [i_2,j_2 ] must nest some [i3,j3]∈B⊓(p0,p1). [i_3,j_3 ]∈ B (p_0,p_1 ). Due to the minimality of [i2,j2] [i_2,j_2 ], [i3,j3]⊈[i1,j1] [i_3,j_3 ] [i_1,j_1 ] and [i3,j3]⊈[|p0|,|p|−1]. [i_3,j_3 ] [ |p_0 |, |p |-1 ]. Furthermore, [i3,j3]≠[0,2] [i_3,j_3 ]≠ [0,2 ] due to B](p0,p1)=∅B^] (p_0,p_1 )= . The only possibility is j3=j1+1j_3=j_1+1 and i3<j3i_3<j_3. This implies that i2=|p0|i_2= |p_0 |, so that bai4b¯ba^i_4 b is a left factor of p1p_1, where i4:=j2−i2−1>2i_4:=j_2-i_2-1>2; combining this with (12), p1p_1 must have the form p1=bap3abj5p_1=bap_3ab^j_5. Consequently, each of the pairs ((x2,y2),p~(|p0|+2)) ( (x_2,y_2 ), p ( |p_0 |+2 ) ) and ((x1,y1),p~(|p0|+1+|p3|+1)) ( (x_1,y_1 ), p ( |p_0 |+1+ |p_3 |+1 ) ) consists of points having the same abscissas, so that we can invoke 1 again to draw that B(p3)∪B(p6)≠∅B (p_3 )∪ B (p_6 )≠ . In particular, the set [i,j]∈B⊓,⊔(p0,p1).[i,j]⊆[i1,j1]∨[i,j]⊆[|p0|,|p|−1]\[i2,j2] \ [i,j ]∈ B , (p_0,p_1 ). [i,j ] [i_1,j_1 ] [i,j ] [ |p_0 |, |p |-1 ] \ \ [i_2,j_2 ] \ is still not empty, so that we can take an element [i6,j6] [i_6,j_6 ] of it having minimal cardinality. By an argument similar to that brought forward for [i2,j2] [i_2,j_2 ], we can show that it must be j6=|p|−1j_6= |p |-1, i6<j6i_6<j_6, so that b¯aj4b ba^j_4b is a right factor of p1p_1, where j4:=j6−i6−1j_4:=j_6-i_6-1. Adding 11, this means that (p1,p0−[0,2]) (p_1,p_0- [0,2 ] ) also belongs to M, thus contradicting the minimality of (p0,p1) (p_0,p_1 ). ∎ Lemma 4. Let (q0,q1)∈Z (q_0,q_1 )∈ Z and β∈Σ2β∈ _2; assume Cβ(q0,q1)∩argmincardBβ(q0,q1)≠∅C^β (q_0,q_1 )∩ _ B^β (q_0,q_1 )≠ . Then there is a 11-shortcut of (q0,q1) (q_0,q_1 ) which belongs to P T. Proof. Consider [i0,j0]∈Cβ(q0,q1)∩argmincardBβ(q0,q1) [i_0,j_0 ]∈ C^β (q_0,q_1 )∩ _ B^β (q_0,q_1 ). We define (p0,p1):=(q0,q1) if i0=0(q1¯,q0¯) if j0=|p0p1|−1(q1,q0) if i0=|p0|(q0¯,q1¯) if j0=|p0|−1. (p_0,p_1 ):= \ aligned (q_0,q_1 )& if i_0=0\\ ( q_1, q_0 )& if j_0= |p_0p_1 |-1\\ (q_1,q_0 )& if i_0= |p_0 |\\ ( q_0, q_1 )& if j_0= |p_0 |-1. aligned . Since, by definition of C, i0=0∨j0=|p0p1|−1∨i0=|p0|∨j0=|p0|−1i_0=0 j_0= |p_0p_1 |-1 i_0= |p_0 | j_0= |p_0 |-1, we can always obtain at least one (p0,p1) (p_0,p_1 ) from the definition above. It is immediate to see that (p0,p1) (p_0,p_1 ) is still in Z. By definition of (p0,p1) (p_0,p_1 ), [0,j1]∈C0α(p0,p1)∩argmincardBα(p0,p1) [0,j_1 ]∈ C_0^α (p_0,p_1 )∩ _ B^α (p_0,p_1 ) for some α∈Σ2α∈ _2, j1∈ℕj_1 . We will show that there is a 11-shortcut of (p0,p1) (p_0,p_1 ) not belonging to T. Since this property is invariant with respect to the operations through which (p0,p1) (p_0,p_1 ) was obtained from (q0,q1) (q_0,q_1 ), this will imply the thesis. We note that, by hypothesis, j1>1j_1>1; without loss of generality, we can further set α=p0(0):=bα=p_0 (0 ):=b and p0(1):=a¯p_0 (1 ):= a. It must be p1(0)=ap_1 (0 )=a, otherwise (p0,p1)−0,j1 (p_0,p_1 )- \0,j_1 \ would be in P T. Moreover, since p0(0)=bp_0 (0 )=b, it must also be p0(|p0|−1)≠b¯p_0 ( |p_0 |-1 )≠ b. Hence, p0(|p0|−1)∈a,bp_0 ( |p_0 |-1 )∈ \a,b \ (because if p0(|p0|−1)=a¯p_0 ( |p_0 |-1 )= a, simplicity is violated). Through similar reasoning, we also conclude that p1(|p1|−1)=bp_1 ( |p_1 |-1 )=b. We now proceed to see that p0(|p0|−1)p_0 ( |p_0 |-1 ) is not equal to a. Indeed, if we assume it is, we have the following implications: 1. by Proposition 3, B[(p0)≠∅B^[ (p_0 )≠ , which allows us to consider, [i2,j2]∈argmincardB[(p0,p1) [i_2,j_2 ]∈ _ B^[ (p_0,p_1 ). 2. p0(|p0|−2)≠b¯p_0 ( |p_0 |-2 )≠ b. 3. p0(2)≠b¯p_0 (2 )≠ b (otherwise p0p_0 would be self-factoring). It is now easy to see that D1[D_1^[, E[E^[, F[F^[ and C0[C_0^[ are all empty, and from (3) it follows D0[D_0^[ also is. Moreover, if it were [i2,j2]∈C1[ [i_2,j_2 ]∈ C^[_1, then (p0,p1)−i2,j2 (p_0,p_1 )- \i_2,j_2 \ would be in P T (using (2)). Hence, through 2, we got a contradiction, and must conclude that p0(|p0|−1)=bp_0 ( |p_0 |-1 )=b. Let us recapitulate the letters of p0p_0 and p1p_1 we know up to now: p0(0)=p0(|p0|−1)=p1(|p1|−1)=b, p_0 (0 )=p_0 ( |p_0 |-1 )=p_1 ( |p_1 |-1 )=b, p0(1)=a¯, p_0 (1 )= a, p1(0)=a. p_1 (0 )=a. (13) Since ba¯j1−1b¯b a^j_1-1 b is a left factor of p0p_0, and p0(|p0|−1)=bp_0 ( |p_0 |-1 )=b, B⊔(p0)≠∅B (p_0 )≠ , and we can thus consider (i3,j3)∈argmincardB⊔ (i_3,j_3 )∈ _ B . It is easy to see that D⊔D , E0⊔E _0, F⊔F are all empty. Moreover, if it were (i3,j3)∈C1⊔ (i_3,j_3 )∈ C _1, then it would be p0(|p0|−2)=ap_0 ( |p_0 |-2 )=a, j3=|p0|−1j_3= |p_0 |-1, i3>0i_3>0, and consequently (p0,p1)−i3,j3∈P (p_0,p_1 )- \i_3,j_3 \∈ P T, which is prevented by the definition of Z. Similarly, if it were [i3,j3]∈C0⊔ [i_3,j_3 ]∈ C _0, it would also be p1(|p1|−2)∈b,b¯p_1 ( |p_1 |-2 )∈ \b, b \, j3=|p0p1|−1j_3= |p_0p_1 |-1, i3>|p0|i_3> |p_0 |: this would make (p0,p1)−i3,j3 (p_0,p_1 )- \i_3,j_3 \ a member of P T, against the definition of Z. [i3,j3] [i_3,j_3 ] must then belong to E1⊔E _1 by 2; this implies that b¯a¯j3−i3−1b b a^j_3-i_3-1b is a right factor of p0p_0. Moreover, ba¯j0−1b¯b a^j_0-1 b is a left factor of p0p_0, because [0,j0]∈Cb(p0,p1) [0,j_0 ]∈ C^b (p_0,p_1 ) and p0(1)=a¯p_0 (1 )= a. Invoking Lemma 3, we draw that Ba,a¯(p0,p1)≠∅. B^a, a (p_0,p_1 )≠ . (14) We preliminarily observe that C0a,a¯=C1[=D0]=D1a=D1[=E0a,a¯=E1a=E1[=F0[=F1]=∅, C_0^a, a=C_1^[=D_0^]=D_1^a=D_1^[=E_0^a, a=E_1^a=E_1^[=F_0^[=F_1^]= , (15) where D0]=∅D_0^]= follows from p1p_1 not being self-factoring, D1a=∅D_1^a= is due to the simplicity of p0p1p_0p_1, and the remaining facts are immediate consequence of the respective definitions and of (13). Let us finally proceed by cases using (14). Case ∅≠argmincardB](p0,p1) ≠ _ B^] (p_0,p_1 ): consider [i4,j4] [i_4,j_4 ] in it. If it were [i4,j4]∈C1] [i_4,j_4 ]∈ C_1^], then it would be p1(1)=bp_1 (1 )=b due to (13) and simplicity. This would mean (p0,p1)−i4,j4∈P (p_0,p_1 )- \i_4,j_4 \∈ P T, against the definition of Z. The only possibility left from (15) and 2 is then [i4,j4]∈F0] [i_4,j_4 ]∈ F_0^], and thesis follows immediately from 5 and (13). Case ∅≠argmincardB[(p0,p1) ≠ _ B^[ (p_0,p_1 ): consider [i5,j5] [i_5,j_5 ] in it, and suppose [i5,j5]∈D0[ [i_5,j_5 ]∈ D_0^[. This implies that ba¯b¯k0ab a b^k_0a is a left factor of p0p_0 for some k0≥3k_0≥ 3. Since p1(0)=ap_1 (0 )=a and p1(|p1|−1)=bp_1 ( |p_1 |-1 )=b, γbk1γ b^k_1 must be a right factor of p1p_1 for some γ≠bγ≠ b, k1∈ℤ+k_1 ^+. Due to simplicity, k1≤k0−2k_1≤ k_0-2; in turn, this implies that γ cannot be a, otherwise simplicity would be again violated. Ultimately, a¯bk1 ab^k_1 must be a right factor of p1p_1; via 3, this implies B](p1)≠∅B^] (p_1 )≠ . In particular, we can trigger the previous case and get the thesis. Hence, the only possibility left from (15) and 2 is [i5,j5]∈F1[ [i_5,j_5 ]∈ F_1^[. This implies (Proposition 4) that F0[(p1,p0)≠∅F_0^[ (p_1,p_0 )≠ , so that there must be (Proposition 5) either a 11- shortcut of p1p_1 having the form (0,l,a¯)(0,l, a) or a 11-shortcut of p0p_0 having the form (l,|p0|−1,a) (l, |p_0 |-1,a ). In the first case, the first letter of the obtained shortcut of p1p_1 becomes a¯ a, while the first letter of p0p_0 remains b, and therefore the obtained pair is still not in T. Similarly, in the second case, the last letter of the obtained shortcut of p0p_0 is a, while the last letter of p1p_1 remains b, and hence the obtained shortcut pair is still not in T. ∎ Corollary 1. Assume (Cβ(p0,p1)(C^β (p_0,p_1 ) ∪ Dβ(p0,p1))D^β (p_0,p_1 )) ∩ argmincardBβ(p0,p1)≠∅ _ B^β (p_0,p_1 )≠ . for some (p0,p1) (p_0,p_1 )∈ and β∈Σ2 _2. Then there is a 11-shortcut of (p0,p1) (p_0,p_1 ) which belongs to P T. Proof. Consider [i,j]∈ [i,j ]∈ (Cβ(p0,p1)CLOSE(C^β (p_0,p_1 ) ∪ OPENDβ(p0,p1))D^β (p_0,p_1 )) ∩argmincardBβ(p0,p1).∩ _ B^β (p_0,p_1 ). If [i,j]∈Cβ(p0,p1)∩argmincardBβ(p0,p1), [i,j ]∈ C^β (p_0,p_1 )∩ _ B^β (p_0,p_1 ), we apply Lemma 4. Otherwise, [i,j]∈Dα(p0,p1)∩argmincardBα(p0,p1) [i,j ]∈ D^α (p_0,p_1 )∩ _ B^α (p_0,p_1 ) for some α⊥βα β, and we can still apply Lemma 4. ∎ Lemma 5. Given (p0,p1)∈Z, (p_0,p_1 )∈ Z, assume that Eβ(p0,p1)≠∅.E^β (p_0,p_1 )≠ . Then there is a 11-shortcut of (p0,p1) (p_0,p_1 ) which belongs to P T. Proof. We can assume β=bβ=b and, by Proposition 4, E0b(p0,p1)≠∅E^b_0 (p_0,p_1 )≠ . Consider then [i0,j0+1]∈E0b(p0,p1) [i_0,j_0+1 ]∈ E^b_0 (p_0,p_1 ). By possibly employing the transformation (p0,p1)↦(p1¯,p0¯), (p_0,p_1 ) ( p_1, p_0 ), we can further impose that i0=0i_0=0, and finally p0(1)=a¯p_0 (1 )= a by possibly swapping a’s with a¯ a’s. We therefore must conclude that p0p_0 has the form p0=ba¯0jb¯p1p_0=b a^j_0 bp_1 for some p1∈Σ2∗p_1∈ _2^*, and that p1p_1’s last letter is a. Now, it cannot be p1(0)=a¯p_1 (0 )= a, otherwise p1p_1 would be self-factoring. Moreover, it cannot be p1(0)=b¯p_1 (0 )= b, which would make (p0,p1)∈T (p_0,p_1 )∈ T. Proceeding with similar reasoning, we obtain p0(|p0|−1),p1(0)⊆a,b \p_0 ( |p_0 |-1 ),p_1 (0 ) \ \a,b \. Case p0(|p0|−1)=ap_0 ( |p_0 |-1 )=a Then B[(p0)≠∅B^[ (p_0 )≠ by Proposition 3, and we can consider [i1,j1]∈ [i_1,j_1 ]∈ argmincardB[(p0,p1) _ B^[ (p_0,p_1 ). If [i1,j1]∈C[(p0,p1)∪D[(p0,p1) [i_1,j_1 ]∈ C^[ (p_0,p_1 )∪ D^[ (p_0,p_1 ), then we invoke Corollary 1. E0[(p0,p1)=∅E_0^[ (p_0,p_1 )= by simplicity, and F[(p0,p1)=∅F^[ (p_0,p_1 )= , hence it only remains to check the case [i1,j1]∈E1[(p0,p1) [i_1,j_1 ]∈ E_1^[ (p_0,p_1 ), which implies p1(0)=bp_1 (0 )=b and p0(|p0|−2)=b¯p_0 ( |p_0 |-2 )= b. But the latter would imply that p0p_0 is self factoring. Case p0(|p0|−1)=bp_0 ( |p_0 |-1 )=b This implies that B⊔(p0)≠∅B (p_0 )≠ via Proposition 3, so that we can consider [i1,j1]∈argmincardB⊔(p0,p1) [i_1,j_1 ]∈ _ B (p_0,p_1 ). If [i1,j1]∈C⊔(p0,p1)∪D⊔(p0,p1) [i_1,j_1 ]∈ C (p_0,p_1 )∪ D (p_0,p_1 ), then we invoke Corollary 1. Moreover, E0⊔(p0,p1)=∅E_0 (p_0,p_1 )= , and F1⊔(p0,p1)=∅F_1 (p_0,p_1 )= . We also note that if F0⊔(p0,p1)≠∅F_0 (p_0,p_1 )≠ , we would violate simplicity. Ultimately, then, we only need to check the case [i1,j1]∈E1⊔(p0,p1) [i_1,j_1 ]∈ E_1 (p_0,p_1 ), which implies p1(0)=ap_1 (0 )=a and p0=p2b¯a¯kbp_0=p_2 b a^kb for some k∈ℤ+k ^+, p2∈Σ2∗p_2∈ _2^*; as a consequence, Ba,a¯(p0)≠∅B \a, a \ (p_0 )≠ via Lemma 3, and we can consider [i2,j2]∈argmincardBa,a¯(p0,p1) [i_2,j_2 ]∈ _ B \a, a \ (p_0,p_1 ). If [i2,j2]∈(Ca,a¯(p0,p1)∪Da,a¯(p0,p1)), [i_2,j_2 ]∈ (C \a, a \ (p_0,p_1 )∪ D \a, a \ (p_0,p_1 ) ), then we apply Corollary 1. Otherwise, we note that Ea,a¯(p0,p1)=∅E \a, a \ (p_0,p_1 )= , so that it must be [i2,j2]∈Fa,a¯(p0,p1)=F0a(p0,p1)∪F1a¯(p0,p1), [i_2,j_2 ]∈ F \a, a \ (p_0,p_1 )=F^a_0 (p_0,p_1 )∪ F a_1 (p_0,p_1 ), If [i2,j2]∈F0a(p0,p1) [i_2,j_2 ]∈ F^a_0 (p_0,p_1 ), we apply Proposition 5 and check that the obtained shortcut has the wanted property. Otherwise, if [i2,j2]∈F1a¯(p0,p1), [i_2,j_2 ]∈ F a_1 (p_0,p_1 ), we consider (p1,p0) (p_1,p_0 ), apply Proposition 4 and again Proposition 5, finally checking that the obtained shortcut has the wanted property. ∎ 4.3 Bumps in F and final proof Lemma 6. Given (p0,p1)∈Z (p_0,p_1 )∈ Z, assume F(p0,p1)≠∅F (p_0,p_1 )≠ . Then there is a 11-shortcut of (p0,p1) (p_0,p_1 ) which belongs to P T. Proof. Set p:=p0p1p:=p_0p_1. We can assume p0(0)=ap_0 (0 )=a and the existence of i, j such that [i,j]∈F0⊓(p0,p1) [i,j ]∈ F_0 (p_0,p_1 ). Now, by simplicity and by the definition of F0F_0, it must be p1¯(0)∈a,b p_1 (0 )∈ \a,b \. Additionally, by definition of B⊓(p0,p1)B (p_0,p_1 ), it must be either j<|p0|j< |p_0 | or i≥|p0|i≥ |p_0 |. Case j<|p0|j< |p_0 |: then there is a unique k such that p0~(k)=(1,1) p_0 (k )= (1,1 ), and k must be in ]i,j[ ]i,j [; it is immediate to check that (2,k−1,b) (2,k-1,b ) is a 11-shortcut of p0p_0. Since this shortcut does not change the first and last letters of p0p_0, we obtain the thesis. Case i≥|p0|i≥ |p_0 | and p1¯(0)=a p_1 (0 )=a: similar to the previous case. Case i≥|p0|i≥ |p_0 |, p1¯(0)=b p_1 (0 )=b and p0¯(0)≠b p_0 (0 )≠ b: applying Proposition 5, we obtain a shortcut of p1p_1 changing the last letter of p1p_1 into b¯ b. This allows thesis since the last letter of p0p_0 is not b. Case i≥|p0|i≥ |p_0 |, p1¯(0)=b p_1 (0 )=b and p0¯(0)=b p_0 (0 )=b: then the sequence p~ p reaches the point (0,1) (0,1 ) at some index k∈[|p0|,|p|−2]k∈ [ |p_0 |, |p |-2 ], while p(|p|−1)=(0,−1)p ( |p |-1 )= (0,-1 ) and p(|p|)=(0,0)p ( |p | )= (0,0 ). By Proposition 3, then, B⊔(p1)≠∅B (p_1 )≠ . But p1¯(0)=b p_1 (0 )=b implies F0⊔(p0,p1)=∅F_0 (p_0,p_1 )= , and p0¯(0)=b p_0 (0 )=b implies F1⊔(p0,p1)=∅F_1 (p_0,p_1 )= . Hence it must be C⊔(p0,p1)∪D⊔(p0,p1)∪E⊔(p0,p1)≠∅C (p_0,p_1 )∪ D (p_0,p_1 )∪ E (p_0,p_1 )≠ by Lemma 2, and we can use Corollary 1 or Lemma 5. ∎ Proof of Theorem 2. Using hypotheses, (p0,p1)∈Z (p_0,p_1 )∈ Z by definition of Z. Using hypothesis (1) and Lemma 2, we have (argmincardBα(p0,p1))∩(Cα(p0,p1)∪Dα(p0,p1)∪Eα(p0,p1)∪Fα(p0,p1))≠∅ ( _ B^α (p_0,p_1 ) )∩ (C^α (p_0,p_1 )∪ D^α (p_0,p_1 )∪ E^α (p_0,p_1 )∪ F^α (p_0,p_1 ) )≠ for some α∈Σ2α∈ _2. If (argmincardBα(p0,p1))∩(Cα(p0,p1)∪Dα(p0,p1))≠∅, ( _ B^α (p_0,p_1 ) )∩ (C^α (p_0,p_1 )∪ D^α (p_0,p_1 ) )≠ , we apply Corollary 1, if (argmincardBα(p0,p1))∩Eα(p0,p1)≠∅ ( _ B^α (p_0,p_1 ) )∩ E^α (p_0,p_1 )≠ we apply Lemma 5, and if (argmincardBα(p0,p1))∩Fα(p0,p1)≠∅ ( _ B^α (p_0,p_1 ) )∩ F^α (p_0,p_1 )≠ we apply Lemma 6. ∎ 5 Proof of Theorem 3 Proposition 12. Let p0,q1,q2∈Σ2∗p_0,q_1,q_2∈ _2^*, m1,m2∈ℕm_1,m_2 , α,β∈Σ2α,β∈ _2, p:=p0βm1+m2q1q2∈Σ2∗p:=p_0β^m_1+m_2q_1q_2∈ _2^*, and assume 1. p0βm1q2∈[∅]∼\∅.p_0β^m_1q_2∈ [ ]_ \ \. Moreover, suppose that, if q1≠∅q_1≠ and minm1,m2>0 \m_1,m_2 \>0, then the following requirements all hold: 2. α⊥βα β; 3. No factor of q1q2q_1q_2 belongs to ββ¯,β¯β \β β, β \; 4. no non-empty, proper left factor of p0βm1+m2p_0β^m_1+m_2 belongs to [∅]∼ [ ]_ ; 5. ∀[i,j]∈Bα(q1q2).j−i≥m1+m2∀ [i,j ]∈ B^α (q_1q_2 ).\ j-i≥ m_1+m_2; 6. If p0=∅p_0= and β¯ β is a right factor of p, then β¯n β^n is a right factor of p for some n≥m1+m2n≥ m_1+m_2. Then p0αβm1+m2α¯q1q2p_0αβ^m_1+m_2 αq_1q_2 is self-factoring. Proof. Immediate for minm1,m2=0∨q1=∅ \m_1,m_2 \=0 q_1= , hence assume m1,m2>0m_1,m_2>0 and q1≠∅q_1≠ . Then, using hypothesis (1), the following set is non-empty: argmincard[i,j]⊂domp.⟨p⟩ij−1≡2p∧i∈]|p0|,|p0|+m1+m2[∧j≥|p0|+m1+m2; _ \ [i,j ]⊂ p. p _i^j-1 _2p i∈ ] |p_0 |, |p_0 |+m_1+m_2 [ j≥ |p_0 |+m_1+m_2 \; therefore, we can consider [i,j] [i,j ] in it such that i is minimal. Setting n1:=i−|p0|>0n_1:=i- |p_0 |>0, n2:=m1+m2−n1n_2:=m_1+m_2-n_1, and p2:=⟨p⟩j|p|−1p_2:= p _j |p |-1, we have that p=p0βn1+n2p1p2p=p_0β^n_1+n_2p_1p_2 for some p1p_1, and p0βn1p2∈[∅]≡\∅p_0β^n_1p_2∈ [ ]_≡ \ \ by construction. If n2=0n_2=0 or p1=∅p_1= , thesis is immediate, hence assume n2>0n_2>0 and p1≠∅p_1≠ . From p0βn1p_0β^n_1 not being closed by hypothesis (4), we can that p2p_2 is neither. By construction of [i,j] [i,j ], p1¯(0)⊥β p_1 (0 ) β; moreover, if p1¯(0)=α¯, p_1 (0 )= α, thesis is again immediate, so that we also assume p1=p1′αp_1=p_1 α for some p1′p_1 . Furthermore, thanks to hypotheses 3 and 2, we can write p2=β1k1p2′p_2= _1^k_1p_2 with β1//β _1//β, p2′p_2 having no left factor in β,β¯ \β, β \, and k1∈ℕk_1 . Case β1=β _1=β: We have p=p0βn1+lβn2−lp1′αβlβk1−lp2′ and p0βn1+lβk1−lp2′≡∅,p=p_0β^n_1+lβ^n_2-lp_1 αβ^lβ^k_1-lp_2 and p_0β^n_1+lβ^k_1-lp_2 ≡ , with l :=:= min n2,k1\n_2,k_1\. If k1<n2k_1<n_2, this yields p2′∉[∅]≡p_2 ∉ [ ]_≡ by hypothesis (4), so that p2′(0)p_2 (0 ) cannot be α¯ α by hypothesis (5), and therefore it must be p0βn1+lα⟨p2′⟩1|p2′|−1∈[∅]\∅→p_0β^n_1+lα p_2 _1 |p_2 |-1∈ [ ] \ \ → p0αβn1+l⟨p2′⟩1|p2′|−1∈[∅]\∅,p_0αβ^n_1+l p_2 _1 |p_2 |-1∈ [ ] \ \, yielding the thesis. If, on the other hand, k1≥n2k_1≥ n_2, then p0βn1+n2βk1−n2p2′∈[∅]\∅→p_0β^n_1+n_2β^k_1-n_2p_2 ∈ [ ] \ \ → p0αβn1+n2α¯βk1−n2p2′∈[∅]\∅.p_0αβ^n_1+n_2 αβ^k_1-n_2p_2 ∈ [ ] \ \. Case β1=β¯ _1= β: We have p=p0βn1−lβn2+lp1′αβ¯lβ¯k1−lp2′ p=p_0β^n_1-lβ^n_2+lp_1 α β^l β^k_1-lp_2 and p0βn1−lβ¯k1−lp2′∈[∅], p_0β^n_1-l β^k_1-lp_2 ∈ [ ], (16) where l:=minn1,k1l:= \n_1,k_1 \. If n1>k1n_1>k_1, hypothesis (4) implies that p2′∉[∅]≡p_2 ∉ [ ]_≡, so that we can consider p2′(0)p_2 (0 ); the latter cannot be α¯ α due to hypothesis (5), therefore p2′(0)=αp_2 (0 )=α, giving thesis immediately. If n1=k1>0n_1=k_1>0, then p0p2′∈[∅],p_0p_2 ∈ [ ], and p0p2′≠∅p_0p_2 ≠ by hypothesis (6). Finally, if n1<k1n_1<k_1, then (16) gives p0β¯k1−lp2′∈[∅]≡\∅p_0 β^k_1-lp_2 ∈ [ ]_≡ \ \. ∎ Lemma 7. Given α∈Σ2α∈ _2, q∈Σ2∗q∈ _2^*, [i0,j0]∈argmincardBα(q) [i_0,j_0 ]∈ _ B^α (q ), assume that, if |q|>2 |q |>2, then all the following hypotheses hold: 1. q−i0,j0q- \i_0,j_0 \ is simple and self-factoring; 2. [i0,j0]∉G(q), [i_0,j_0 ]∉ G (q ), where, for any p, G(p)G (p ) is defined as G(p):=[i,j]∈B(p).(i=0∧j−i>2∧j<|p|−1∧p(|p|−1)=p(1)¯)∨ G (p ):=\ [i,j ]∈ B (p ).\ (i=0 j-i>2 j< |p |-1 p ( |p |-1 )= p (1 ) ) (j=|p|−1∧j−i>2∧i>0∧p(0)=p(|p|−2)¯). (j= |p |-1 j-i>2 i>0 p (0 )= p ( |p |-2 ) )\. Then q is self-factoring. Proof. We can assume |q|>2 |q |>2, j0−i0>2j_0-i_0>2, [i0,j0]⊂[0,|q|−1] [i_0,j_0 ]⊂ [0, |q |-1 ], and q∉[∅]∼q∉ [ ]_ . Set p:=q−i0,j0p:=q- \i_0,j_0 \, thereby having p=⟨q⟩0i0−1βj0−i0−1⟨q⟩j0+1|q|−1p= q _0^i_0-1\ β^j_0-i_0-1\ q _j_0+1 |q |-1 for some β⊥αβ α and consider, by hypothesis 1, i1≤j1i_1≤ j_1 satisfying ⟨p⟩0i1⟨p⟩j1|p|−1∈[∅]\∅ p _0^i_1\ p _j_1 |p |-1∈ [ ] \ \. Now, if |[i0−1,j0−1]∩i1,j1| | [i_0-1,j_0-1 ]∩ \i_1,j_1 \ | is even, the thesis is immediate; otherwise, we have two cases: Case i1∈[i0−1,j0−2]i_1∈ [i_0-1,j_0-2 ] and j1≥j0j_1≥ j_0: then p=⟨p⟩0i0−1βi1−i0+1βj0−i1−2⟨p⟩j0−1j1−1⟨p⟩j1|p|−1 and ⟨p⟩0i0−1βi1−i0+1⟨p⟩j1|p|−1∈[∅]≡\∅,p= p _0^i_0-1\ β^i_1-i_0+1\ β^j_0-i_1-2\ p _j_0-1^j_1-1\ p _j_1 |p |-1\ and \ p _0^i_0-1β^i_1-i_0+1\ p _j_1 |p |-1∈ [ ]_≡ \ \, so that we can apply Proposition 12 to obtain the thesis. Note that, if ⟨p⟩0i0−1=∅ p _0^i_0-1= , then q(1)=βq (1 )=β, and therefore p¯(0)=q¯(0)≠β¯ p (0 )= q (0 )≠ β because [i0,j0]∉G(q) [i_0,j_0 ]∉ G (q ), allowing to satisfy hypothesis 6 of Proposition 12. Case j1∈[i0−1,j0−2]j_1∈ [i_0-1,j_0-2 ] and i1<i0−1i_1<i_0-1: we consider p¯ p and reason similarly. ∎ Proposition 13. Let (p0,p1)∈P (p_0,p_1 )∈ P T R, [i0,j0]∈Bα(p0)∩G(p0) [i_0,j_0 ]∈ B^α (p_0 )∩ G (p_0 ), where G is defined as in Lemma 7. Assume 1. ∀i.[i,i+2]∈B(p0,p1)→(p0,p1)−i,i+2∉P ∀ i. [i,i+2 ]∈ B (p_0,p_1 ) → (p_0,p_1 )- \i,i+2 \∉ P T; 2. (p0,p1)−i0,j0∈P (p_0,p_1 )- \i_0,j_0 \∈ P T. Then there are β⊥αβ α and [i1,j1]∈argmincardBβ(p0,p1) (p0)\(|p0|+G(p1)) [i_1,j_1 ]∈ _ B^β (p_0,p_1 ) G (p_0 ) ( \ |p_0 | \+G (p_1 ) ) such that (p0−i1,j1,p1)∈P (p_0- \i_1,j_1 \,p_1 )∈ P T. Proof. Looking at the definition of G, we can assume i0=0, i_0=0, j0<|p0|−1, j_0< |p_0 |-1, p0(0)=b, p_0 (0 )=b, p0(1)=p0(2)=a, p_0 (1 )=p_0 (2 )=a, p0(|p0|−1)=a¯. p_0 ( |p_0 |-1 )= a. (17) Since (p0,p1)∈P (p_0,p_1 )∈ P T R and (p0,p1)−i0,j0∈P (p_0,p_1 )- \i_0,j_0 \∈ P T, it also must be p1¯(0)=b=p1(0) p_1 (0 )=b=p_1 (0 ) and p0(|p0|−2)≠b¯. p_0 ( |p_0 |-2 )≠ b. (18) Therefore, we can use simplicity of p0p1p_0p_1 and the respective definitions to check that C0](p0,p1)=D](p0,p1)=E](p0,p1)=F](p0,p1)=∅. C_0^] (p_0,p_1 )=D^] (p_0,p_1 )=E^] (p_0,p_1 )=F^] (p_0,p_1 )= . (19) Combining (17) and (18) with hypothesis 1, one can check that if there is a bump of B(p0,p1)B (p_0,p_1 ) having cardinality 33, it must belong to the set [|p0p1|−3,|p0p1|−1] \ [ |p_0p_1 |-3, |p_0p_1 |-1 ] \. By virtue of (17) and Proposition 3, we can consider [i1,j1]∈argmincardB](p0,p1) [i_1,j_1 ]∈ _ B^] (p_0,p_1 ) and, by what we said in the last sentence, assert that [i1−1,i1+1],[j1−1,j1+1]∩Ba⊥(p0,p1)=∅. \ [i_1-1,i_1+1 ], [j_1-1,j_1+1 ] \∩ B^a (p_0,p_1 )= .. Adding (19) and Proposition 9, if it were (p0,p1)−i1,j1∉P (p_0,p_1 )- \i_1,j_1 \∉ P T, then we could conclude [i1,j1]∈C1](p0,p1) [i_1,j_1 ]∈ C^]_1 (p_0,p_1 ) ([i1,j1] [i_1,j_1 ] cannot nest any other bump of B](p0,p1)B^] (p_0,p_1 ) being minimal). By definition of C1C_1, this implies j1=|p0|−1j_1= |p_0 |-1, [i1,j1]∈B](p0) [i_1,j_1 ]∈ B^] (p_0 ) and (p0,p1)−i1,j1=(p0−i1,j1,p1)∈P. (p_0,p_1 )- \i_1,j_1 \= (p_0- \i_1,j_1 \,p_1 )∈ P. It is immediate to check that (p0−i1,j1,p1) (p_0- \i_1,j_1 \,p_1 ) is not in T, so that we have a contradiction and it must be (p0,p1)−i1,j1∈P (p_0,p_1 )- \i_1,j_1 \∈ P T. By definition of G, (17) and (18), we can check that G(p1)∩B](p1)=∅=G(p0)∩B](p0).G (p_1 )∩ B^] (p_1 )= =G (p_0 )∩ B^] (p_0 ). ∎ Proof of Theorem 3. By simplicity, any bump for (,) ( p, q ) must have cardinality at least 33. If there were a minimal bump for (,) ( p, q ) of the form [i,i+2] [i,i+2 ] and such that (,)−i,i+2∈P ( p, q )- \i,i+2 \∈ P T, then we would have that (,)−i,i+2∈R ( p, q )- \i,i+2 \∈ R due to P3; let us assume [i,i+2]∈B() [i,i+2 ]∈ B ( p ): p0−i,i+2p_0- \i,i+2 \ is then simple and self-factoring, while [i,i+2] [i,i+2 ] cannot be in G()G ( p ) being too short. Therefore, we could invoke Lemma 7 to establish that p is self-factoring, while (,)∉R ( p, q )∉ R. We have thus proved that (,) ( p, q ) satisfies hypothesis 1 of Proposition 13, and can consequently prove that, if there is any bump [i0,j0] [i_0,j_0 ] such that (,)−i0,j0∈P ( p, q )- \i_0,j_0 \∈ P T, then there is a minimal bump [i1,j1] [i_1,j_1 ] for (,) ( p, q ) not belonging to G()∪(||+G())G ( p )∪ ( \ | p | \+G ( q ) ) and such that (,)−i1,j1∈P . ( p, q )- \i_1,j_1 \∈ P T. By P3, then, we have (,)−i1,j1∈R ( p, q )- \i_1,j_1 \∈ R. As before, we can assume [i1,j1]∈B() [i_1,j_1 ]∈ B ( p ), which means −i1,j1 p- \i_1,j_1 \ is simple and self-factoring. Applying Lemma 7 again, we conclude that p is also self factoring, which is impossible because (,)∉R ( p, q )∉ R. ∎ 6 Conclusions The results linking ONO_N and MCFGs provided a starting point for the main question of this paper: that is, which alterations can be made to the notion of a MCFG without severing these links. We provided a first answer, by slightly tweaking the definition of a MCFG and showing that the link persists, at least for the casen N=2N=2. We cursorily note that Theorem 1 still remains valid if the conditions on rule (2) are moved to rule (3), by symmetry. Besides the proof-theoretical interest of a result of this type, it is hoped that the direction pointed out here can be helpful towards establishing further links between ONO_N and structures that are independent of MCFGs, such as indexed grammars, for which the study of such links still poses a number of open problems [7]. A more immediate application of the results presented here is a computational one: we have established that any binary factorisation of a closed, simple walk in ℤ2Z^2 is either in T or R. As the T-membership problem is trivial to decide, and since the notion of a self-factoring string is intimately connected to the word problem in ℤ2Z^2, the present results can be potentially used for arbitrary binary factorisations of closed, simple walks in relation to algorithmic aspects of that problem. Related to this, the style of the proofs provided here has deliberately been kept close to low-level, set-theoretical concepts and free of geometrical arguments (similarly to what done in [1]), so to make at least conceivable to work on a future formalisation in a proof assistant for a verification of the presented results and of possible algorithms deriving from them. This preprint has not undergone any post-submission improvements or corrections. The Version of Record of this contribution is published in MCU 2026, and is available online at https://doi.org/10.1007/978-3-031-81202-6 Acknowledgments The author is grateful to the organisers of the Trimester Program “Prospects of Formal Mathematics” held in Summer 2024 at the Hausdorff Research Institute for Mathematics in Bonn. That event provided ring-fenced time, the right atmosphere and invaluable interaction with colleagues, all key factors in stimulating the ideas from which the present research originated. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC-2047/1 – 390685813. The author would like to thank Lancaster University for providing financial support to attend this conference. References [1] M. B. Caminati (2024) O2O_2 Is a multiple context-free grammar: an implementation-, formalisation-friendly proof. In International Conference on Developments in Language Theory, p. 82–97. Cited by: §1, §1, §6. [2] A. Clark (1985) An introduction to multiple context free grammars for linguists. Linguistics and Philosophy 8, p. 333–343. Cited by: §1. [3] K. Gebhardt, F. Meunier, and S. Salvati (2022) OnO_n Is an n-MCFL. Journal of Computer and System Sciences 127, p. 41–52. Cited by: §1. [4] R. H. Gilman, R. P. Kropholler, and S. Schleimer (2018) Groups whose word problems are not semilinear. Groups Complexity Cryptology 10 (2), p. 53–62. Cited by: §1. [5] R. H. Gilman (2005) Formal languages and their application to combinatorial group theory. Contemporary Mathematics 378, p. 1–36. Cited by: §1. [6] M. Nederhof (2016) A short proof that O2O_2 is an MCFL. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 1117–1126. Cited by: §1. [7] S. Salvati (2015) MIX is a 2-MCFL and the word problem in ℤ2Z_2 is captured by the IO and the OI hierarchies. Journal of Computer and System Sciences 81 (7), p. 1252–1277. Cited by: §1, §6.