# The repetition threshold for ternary rich words (2025) # James D. Currie, Lucas Mol, Jarkko Peltomäki # # The code in this repository implements a backtracking algorithm that can be used to verify the claims of the above paper involving computational searches. The verification can be done by running the file `verify_backtracking.py`. # In addition, code is provided to verify the proof of Lemma 3.10, which is partially omitted in the paper. The verification is done by running `verify_forbidden_factors.py`. Please consult the code for the details. # MIT License # Copyright (c) 2025 Jarkko Peltomäki # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # The above copyright notice and this permission notice shall be included in all # copies or substantial portions of the Software. # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE # SOFTWARE. quiet = True # Change to False to print more details # The eerTree data structure class eerTree(): def __init__(self,word): self._word='' self._vertices={'':0,-1:-1} self._edges={'':{},-1:{}} self._links={'':-1,-1:-1} self._palSuf=-1 self._palSufStack=[-1] self._newPalStack=[None] for i in range(len(word)): self.add(word[i]) def __repr__(self): return "An eerTree for a string with %s palindromes."%(self.numPals()) def numPals(self): count=0 L=self._newPalStack for i in range(len(L)): if L[i]: count+=1 return count def add(self,letter): cs=self._palSuf self._newPal=False while not cs==-1: if len(cs)==len(self._word): cs=self._links[cs] csl=self._vertices[cs] if self._word[-csl-1]==letter: pal=letter+cs+letter if self._edges[cs].get(letter)==None: self._newPal=True self._vertices[pal]=len(pal) self._edges[pal]={} self._edges[cs][letter]=pal ns=self._links[cs] while not ns==-1: nsl=self._vertices[ns] if self._word[-nsl-1]==letter: nextpal=letter+ns+letter break ns=self._links[ns] if ns==-1: nextpal=letter self._links[pal]=nextpal self._palSuf=pal break cs=self._links[cs] if cs==-1: if self._edges[cs].get(letter)==None: self._newPal=True self._vertices[letter]=1 self._edges[letter]={} self._edges[-1][letter]=letter self._links[letter]='' self._palSuf=letter self._word+=letter self._palSufStack+=[self._palSuf] if self._newPal: self._newPalStack+=[cs] else: self._newPalStack+=[None] def pop(self): u=self._palSuf indicator=self._newPalStack.pop() if not indicator==None: del self._vertices[u] del self._links[u] del self._edges[u] if len(u)>1: v=u[1:-1] else: v=-1 del self._edges[v][u[-1]] self._palSufStack.pop() self._palSuf=self._palSufStack[-1] self._word=self._word[:-1] # Specific maps def transducer(w, a): state = (len(w) - 1) % 2 == 0 if state == 0: images = ["001", "00101101", "00101101"*2] else: images = ["002", "00202202", "00202202"*2] return images[int(a)] def phi(w, a): images = ["76", "760", "756", "7560"] return images[int(a)] def psi(w,a): images = ["03","033","0333","01"] return images[int(a)] def f_hat(w, a): images = ["01", "022", "02", "0222", "0121", "01221", "012", "021"] return images[int(a)] def g(w,a): images = ["20", "21", "2"] return images[int(a)] def apply(func, w): """Returns the image of w under func.""" if len(w) == 0: return "" return apply(func, w[:-1]) + func(w[:-1], w[-1]) # Conditions used in the backtracking algorithm class Condition: """A superclass for all conditions.""" pass class FunctionCondition(Condition): """A stateless condition.""" def __init__(self, func): super().__init__() self.func = func def __str__(self): return f"FunctionCondition({str(self.func)})" def add(self, w, a): return self.func(w, a) def pop(self): pass class RichnessCondition(Condition): def __init__(self): self.eertree = eerTree("") def add(self, w, a): self.eertree.add(a) return self.eertree._palSufStack[-1] if not self.eertree._newPal else None def pop(self): self.eertree.pop() class ForbiddenSuffixCondition(Condition): def __init__(self, forbidden): for x in forbidden: assert len(x) > 0, "Forbidden factors must be nonempty." self.forbidden = forbidden def add(self, w, a): for p in [x[:-1] for x in self.forbidden if x[-1] == a]: if w.endswith(p): return p + a return None def pop(self): pass def power_suffix(w, top, bottom): """Checks if the word w has as a suffix a repetition with exponent >= top/bottom.""" n = len(w) p = 1 while n*bottom >= p*top: i = 0 while w[-1 - i] == w[-1 - i - p]: if (i + 1 + p)*bottom >= p*top: return w[-1 - i - p:] i += 1 if i + p >= n: break p += 1 return None def non_prefix_occurrences(u, w): if len(u) == 0: return list(range(1, len(w) + 1)) occurrences = [] pos = 1 while pos > 0 and pos < len(w): pos = w.find(u, pos) if pos != -1: occurrences.append(pos) pos += 1 return occurrences def is_poor(w): is_palindrome = lambda w: w == w[::-1] for l in range(len(w) + 1): pref = w[:l] if not is_palindrome(pref): continue if not pref.count("2") % 2 == 0: continue found = False for pos in non_prefix_occurrences(pref, w): x = w[:pos] if x.count("2") % 2 == 0: found = True break if not found: return False return True def poor_suffix(w): """Checks if w has a poor suffix.""" for l in range(1, len(w) + 1): suff = w[-l:] if is_poor(suff): return suff return None # The backtracking algorithm def backtrack(n, k, preconditions, postconditions=None, func=None, prefix="", quiet=False): """A backtracking algorithm that builds words u satisfying given precondition that maps to words v that satisfy postconditions. Args: n: Max length of u, guarantees termination. k: Alphabet size of u. preconditions: Conditions that u must satisfy.. postconditions: Conditions that v must satisfy. func: A function f that maps u to v defined recursively by f(ua) = f(u)f(u, a). prefix: An initial prefix for u to start with. quiet: Display progress or not. Returns: u: A word u of length n satisfying the conditions if exists. None otherwise. len(u): Length of the longest u satisfying the conditions that was found. """ def config_conditions(conditions): if conditions is None: conditions = [] if not isinstance(conditions, list): conditions = [conditions] # If a condition is a plain function, we assume that we can use # FunctionCondition. for i in range(len(conditions)): if not isinstance(conditions[i], Condition): conditions[i] = FunctionCondition(conditions[i]) return conditions preconditions = config_conditions(preconditions) postconditions = config_conditions(postconditions) pop_lengths = [] # Pop lengths for the image. def pop(conditions, pop_lengths=None, limit=-1): """Calls the pop method of every condition. If limit != -1, then only the first limit pop methods are called. Returns the pop length.""" if len(conditions) == 0: return 1 pop_length = pop_lengths.pop() if pop_lengths is not None else 1 for n, c in enumerate(conditions): if limit != -1 and n >= limit: break for _ in range(pop_length): c.pop() return pop_length def check_conditions(w, x, conditions, pop_lengths=None): """Checks that all conditions are satisfied for w + x. Returns the number of calls to add that were successful and the first nonsuccessful condition (None if it does not exist).""" failed = False n = -1 for n, c in enumerate(conditions): z = "" for a in x: if c.add(w + z, a) is not None: failed = True z += a if failed: break if pop_lengths is not None: pop_lengths.append(len(x)) n_failed = n + 1 if not failed else n return n_failed, None if not failed else c # Check that the provided prefix satisfies the given conditions. u = "" # preimage v = "" # image for a in prefix: x = a if func is None else func(u, a) _, c = check_conditions(u, a, preconditions) if c is not None: raise ValueError(f"The entered prefix does not satisfy the precondition {str(c)}.") _, c = check_conditions(v, x, postconditions, pop_lengths=pop_lengths) if c is not None: raise ValueError(f"The entered prefix does not satisfy postcondition {str(c)}.") u += a v += x longest = prefix extensions = "0" while len(extensions) > 0: a = extensions[-1] x = a if func is None else func(u, a) l_pre, _ = check_conditions(u, a, preconditions) l_post, _ = check_conditions(v, x, postconditions, pop_lengths=pop_lengths) if l_pre == len(preconditions) and l_post == len(postconditions): # u + a and v + x are good u = u + a v = v + x if len(u) > len(longest): # Save and print the new longest word. longest = u if not quiet: print(len(u), u) if len(u) == n: # Terminate if we reach the given length. if not quiet: print(f"Found a word of length {n}.") return u, len(u) else: # Set the next extension letter to be 0. extensions += "0" else: # u + a or v + x is not good, backtrack # First, we pop only on those conditions for which add was called and it succeeded. pop(preconditions, limit=l_pre+1) pop(postconditions, pop_lengths=pop_lengths, limit=l_post+1) a = extensions[-1] extensions = extensions[:-1] # Continue backtracking until we can increment a letter or we reach # th beginning. while len(extensions) > 0 and int(a) == k - 1: l_pre = pop(preconditions) l_post = pop(postconditions, pop_lengths=pop_lengths) a = extensions[-1] extensions = extensions[:-1] u = u[:-l_pre] v = v[:-l_post] if int(a) != k - 1: extensions += str(int(a) + 1) if not quiet: print(f"There are only finitely many words satisfying the given conditions. The longest such word has length {len(longest)}.") return None, len(longest) # Verification of the backtracking claims made in the paper # Section 3.1, 1st paragraph # ----------------------------------------------------------------------------- preconditions = [ ForbiddenSuffixCondition(["001002", "112110", "220221"]), # No given forbidden factors. RichnessCondition(), # No nonrich factors. lambda w, a: power_suffix(w + a, 7, 3) # No powers with exponent 7/3. ] w, l = backtrack(1000, 3, preconditions, quiet=quiet) assert w is None and l == 388, "Section 3.1, 1st paragraph claim of maximum length 388 fails." # Section 3.1, Table 1 # ----------------------------------------------------------------------------- preconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 7, 3) ] w, l = backtrack(1000, 3, preconditions, prefix="102", quiet=quiet) assert w is None and l == 152, "Section 3.1, Table 1, 102: claim of maximum length 152 fails." preconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 7, 3) ] w, l = backtrack(1000, 3, preconditions, prefix="0011", quiet=quiet) assert w is None and l == 498, "Section 3.1, Table 1, 0011: claim of maximum length 498 fails." preconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 7, 3) ] w, l = backtrack(1000, 3, preconditions, prefix="00100200", quiet=quiet) assert w is None and l == 502, "Section 3.1, Table 1, 00100200: claim of maximum length 502 fails." # Lemma 3.3 # ----------------------------------------------------------------------------- preconditions = [ ForbiddenSuffixCondition(["00"]), RichnessCondition(), lambda w, a: power_suffix(w + a, 7, 3) ] w, l = backtrack(1000, 3, preconditions, quiet=quiet) assert w is None and l == 57, "Section 3.1, Lemma 3.3: claim of maximum length 57 fails." # Table 2 # ----------------------------------------------------------------------------- postconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 16, 7) ] w, l = backtrack(1000, 3, preconditions=[], postconditions=postconditions, func=transducer, prefix="201", quiet=quiet) assert w is None and l == 141, "Section 3.2, Table 2, 201: claim of maximum length 141 fails." postconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 16, 7) ] w, l = backtrack(1000, 3, preconditions=[], postconditions=postconditions, func=transducer, prefix="210", quiet=quiet) assert w is None and l == 144, "Section 3.2, Table 2, 210: claim of maximum length 144 fails." postconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 16, 7) ] w, l = backtrack(1000, 3, preconditions=[], postconditions=postconditions, func=transducer, prefix="211", quiet=quiet) assert w is None and l == 101, "Section 3.2, Table 2, 211: claim of maximum length 101 fails." # Proposition 3.6 # ----------------------------------------------------------------------------- postconditions = [ RichnessCondition(), lambda w, a: power_suffix(w + a, 7, 3) ] w, l = backtrack(1000, 2, [], postconditions, func=transducer, quiet=quiet) assert w is None and l == 18, "Section 3.2, Proposition 3.6: claim of maximum length 18 fails." # Claim 3.18 # ----------------------------------------------------------------------------- F_phi = ["00", "11", "22", "33", "01", "20", "31"] preconditions = [ ForbiddenSuffixCondition(F_phi), lambda w, a: power_suffix(w + a, 3, 1) ] postconditions = [ lambda w, a: poor_suffix(w + a) ] func = lambda w, a: "".join(f_hat("", c) for c in phi(w, a)) w, l = backtrack(1000, 4, preconditions=preconditions, postconditions=postconditions, func=func, quiet=quiet) assert w is None and l == 8, "Section 3.4, Claim 3.18: claim of maximum length 8 fails." # Claim 3.19 # ----------------------------------------------------------------------------- preconditions = [ ForbiddenSuffixCondition(["11", "000", "1001"]), lambda w, a: power_suffix(w + a, 5, 1) ] postconditions = [ lambda w, a: poor_suffix(w + a) ] func = lambda w, a: f_hat(w,str(int(a)+4)) w, l = backtrack(1000, 2, preconditions=preconditions, postconditions=postconditions, func=func, quiet=quiet) assert w is None and l == 11, "Section 3.4, Claim 3.19: claim of maximum length 11 fails." # Claim 3.20 # ----------------------------------------------------------------------------- preconditions = [ ForbiddenSuffixCondition(["11", "000", "1001"]), lambda w, a: power_suffix(w + a, 5, 1) ] postconditions = [ lambda w, a: poor_suffix(w + a) ] func = lambda w, a: "".join(f_hat("", c) for c in psi(w, a)) w, l = backtrack(1000, 2, preconditions=preconditions, postconditions=postconditions, func=func, quiet=quiet) assert w is None and l == 11, "Section 3.4, Claim 3.20: claim of maximum length 11 fails." print("All backtracking claims verified successfully.") # Helper functions for verification of Lemma 3.10 def power(period, top, bottom): """Raises the given word to power top/bottom.""" p=len(period) rep="" while (len(rep)+1)*bottom <= p*top: rep+=period[len(rep)%p] return rep def parikh(w): """Returns the Parikh vector of a word w over Sigma_3.""" return [w.count(str(i)) for i in range(3)] def parikh_check(period, top, bottom): """Returns True if and only if every entry of the Parikh vector of period^{top/bottom} is at least 2/7 of the corresponding entry of the Parikh vector of period""" excess = power(period, top, bottom) return all(7*parikh(excess)[i] >= 2*parikh(period)[i] for i in range(3)) def critical_exponent(w): """Returns the critical exponent of w and the factor having this exponent.""" top = 1 bottom = 1 word = "" u = "" for n in range(len(w)): u += w[n] p = 1 while n*bottom >= p*top: i = 0 while u[-1-i] == u[-1-i-p]: i += 1 if i + p >= n + 1: break if i >= 1 and (i+p)*bottom > p*top: bottom = p top = i+p word = u[-p*top//bottom:] p += 1 return [top, bottom, word] def forbidden_factor_check(w, n, BadPeriod, BadTop, BadBottom, Prefixes=[""], Suffixes=[""], quiet=False): """Checks that f^n(awb) contains BadPeriod^{BadTop/BadBottom} for all letters a in prefixes and all letters b in suffixes.""" BadRep = power(BadPeriod, BadTop, BadBottom) for a in Prefixes: for b in Suffixes: word = a + w + b for i in range(n): # First we check that tau(g(f^i(awb))) has a factor of exponent # at least 16/7. We do this only if quiet = False. u = apply(g, word) v = apply(transducer, u) ce_top, ce_bottom, ce_factor = critical_exponent(v) if ce_top*7 < ce_bottom*16: return False, i, a, b # Uncomment to see the factor of exponent at least 16/7. #print(ce_top, ce_bottom, ce_factor) word = apply(f_hat, word) # Now we check that tau(g(f^n(awb))) has the claimed factor. if not BadRep in word: return False, i, a, b return True, None, None, None # Verification of Lemma 3.10 # ----------------------------------------------------------------------------- # The idea is that for each forbidden factor w (key of the below dictionary), # there is a factor v^{p/q} such that it occurs in f^n(awb) for all letters a # in the given prefixes and all letters b in the given suffixes. Once this is # known, we can prove that tau(g(f^k(awb))) has at least a 16/7-power for all # k >= n. Set quiet to False to see the arguments. # # The format of the dictionary is w: (n, v, p, q, prefixes, suffixes) F1 = { "00": (1, "01", 5, 2, [""], ["0","1","2"]), "11": (1, "022", 7, 3, [""], ["0","1","2"]), "212": (3, "2010201022010", 31, 13, [""], ["0","1","2"]), "2222": (2, power("0102",2,1), 5, 2, [""], ["0","1","2"]), "1222": (4, power("02010220102010220102", 2, 1), 19, 8, [""], ["0","1"]), "2221": (4, power("20102010220102020102", 2, 1), 19, 8, ["0","1"], ["0","1","2"]), "1010": (1, "02201", 12, 5, [""], ["1","2"]), "0101": (1, "20102", 12, 5, ["2"], ["2"]), "022022": (2, "2010220102010", 31, 13, ["0","1","2"], ["0","1","2"]), "220220": (2, "2010201020102", 31, 13, ["0","1","2"], ["0","1","2"]) } F2 = { "202202": (2, "2010201022010", 31, 13, ["0","1","2"], ["0","1","2"]), "1022021": (3, "20102010220102020102201020102", 67, 29, [""], [""]), "1202201": (3, "20102010220102010220102020102", 67, 29, [""], [""]), "120102201021": (3, "20102010220102010220102020102201020102010220102020102", 124, 53, [""], [""]), power("021012", 13, 6): (2, "020102201020102020102201020201", 71, 30, ["1","2"], ["1","2"]), power("012021", 13, 6): (2, "020102201020201020102201020102", 71, 30, ["1","2"], ["1","2"]), power("21012010", 21, 8): (0, "21012010", 21, 8, [""], [""]), power("21012210120", 27, 11): (0, "21012210120", 27, 11, [""], [""]), power("2101221012010", 31, 13): (0, "2101221012010", 31, 13, [""], [""]) } F3 = { "2" + power("2101", 17, 4) + "2": (3, "20102010220102010220102010201022010202010220102010201022010201022010201020102201020201022010", 211, 92, ["0","1"], ["0","1"]), power("2101210122101", 31, 13): (0, "2101210122101", 31, 13, [""], [""]) } F4 = { power("0222", 17, 4) + "1": (1, "2010202020102020", 37, 16, ["1","2"], [""]), power("22010", 12, 5): (1, "02020102201", 27, 11, [""], ["0","1","2"]), power("022201", 29, 6): (0, "022201022201", 29, 12, [""], [""]), power("0222010222", 12, 5): (0, "0222010222", 12, 5, [""], [""]), power("0222022201", 12, 5): (0, "0222022201", 12, 5, [""], [""]), power("0222010222010222022201", 5, 2): (0, "0222010222010222022201", 5, 2, [""], [""]) } F = F1 | F2 | F3 | F4 for w in F: exists, i, a, b = forbidden_factor_check(w, *F[w], quiet=quiet) if not exists: if i < F[w][0]: print(f"FAILURE: The word f^n(awb), where w = {w}, a = {a}, b = {b}, and n = {i}, is not 16/7-free.") else: print(f"FAILURE: The word f^n(awb), where w = {w}, a = {a}, b = {b}, and n = {i}, has no factor ({F[w][1]})^{F[w][2]}/{F[w][3]} as claimed.") raise SystemExit if not quiet: print(f"The word f^n(awb), where w = {w}, a in {F[w][4]}, and b in {F[w][5]}, has factor ({F[w][1]})^{F[w][2]}/{F[w][3]} for all n >= {F[w][0]}.") # Print out the arguments. if not quiet: F = F1 | F2 | F3 | F4 for w in F: print() print(f"Argument for w = {w}:") print("-"*(len(w) + 18)) if w in ["00", "11", "1010", "0101"]: k = F1[w][0] print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(awb))) has a factor of exponent at least 7/3 for all n >= {k}.") elif w == power("0222", 17, 4) + "1": print(f"We can write p^{BadTop}/{BadBottom} = (p_1 p_2 p_3 p_4)^2 p_1, where p_1 = 20102, p_2 = 02020, p_3 = 10202, and p_4 = 20. ", end="") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(awb))) has a factor of exponent at least 16/7 for all n>={n}.") elif w == power("22010", 12, 5): print(f"We can write p^{BadTop}/{BadBottom} = (p_1 p_2 p_3)^2 p_1, where p_1 = 02020, p_2 = 102, and p_3 = 201. ", end="") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(awb))) has a factor of exponent at least 7/3 for all n>={n}.") elif w == power("2101221012010", 31, 13): print(f"We can write p^{BadTop}/{BadBottom} = (p_1 p_2 p_3)^2 p_1, where p_1 = p_2 = 21012, and p_3 = 010. ", end="") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(w))) has a factor of exponent at least 7/3 for all n>={n}.") elif w == power("022201", 29, 6): print(f"We can write p^{BadTop}/{BadBottom} = (q 1 q 1)^2 q, where q = 02220. ", end="") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(w))) has a factor of exponent at least 7/3 for all n>={n}.") elif w == power("0222010222", 12, 5): print(f"Further, we can write p^{BadTop}/{BadBottom} = (p_1 p_2 p_3)^2 p_1, where p_1 = p_3 = 0222 and p_2 = 01. ", end="") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(w))) has a factor of exponent at least 7/3 for all n>={n}.") elif w == power("0222022201", 12, 5): print(f"Further, we can write p^{BadTop}/{BadBottom} = (p_1 p_2 p_3)^2 p_1, where p_1 = p_2 = 0222 and p_3 = 01.") print(f"It follows from Lemma 3.7 and Lemma 3.9 that tau(g(f^n(w))) has a factor of exponent at least 7/3 for all n>={n}.") else: n = F[w][0] BadPeriod = F[w][1] BadTop = F[w][2] BadBottom = F[w][3] if parikh_check(BadPeriod, BadTop - 2*BadBottom, BadBottom): if not quiet: print(f"We can write p^{BadTop}/{BadBottom} = p^2 q, where p = {BadPeriod} and q = {power(BadPeriod,BadTop-2*BadBottom,BadBottom)}. ", end="") print(f"We check that each entry in the Parikh vector of q is at least 2/7 of the corresponding entry in the Parikh vector of p. ", end="") print(f"Thus, we conclude that tau(g(f^n(awb))) has a factor of exponent at least 16/7 for all n >= {n}.") else: print(f"The Parikh check failed for {w}.") raise SystemExit print() print("Claims of Lemma 3.10 verified successfully.")