Joseph Meleshko

Pascal Ochem

Jeffrey Shallit

Sonja Linghui

Pseudoperiodic Words and a Question of Shevelev

Keywords: pseudoperiodic word, automata, Thue-Morse sequence, Rudin-Shapiro sequence, Tribonacci sequence, paperfolding sequence, critical exponent

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete.

Introduction

Periodicity is one of the simplest and most studied aspects of words (sequences). Let w = a 0 a 1 a 2 • • • a t-1 be a finite word. We say that w is (purely) periodic with period p (1 ≤ p ≤ t) if a i = a i+p for 0 ≤ i < t -p. For example, the French word entente is periodic with periods 3, 6, and 7. The definition is extended to infinite words as follows: w = a 0 a 1 • • • is periodic with period p if a i = a i+p for all i ≥ 0. Unless otherwise stated, all words in this paper are indexed starting with index 0. All infinite words are defined over a finite alphabet.

In this paper we begin the study of a simple and obvious-yet apparently little-studied-generalization of periodicity, which we call k-pseudoperiodicity.

Definition 1. We say that a finite word w = a 0 a 1 • • • a t-1 is k-pseudoperiodic if there exist k ≥ 1 integers 0 < p 1 < p 2 < • • • < p k such that a i ∈ {a i+p1 , a i+p2 , . . . , a i+p k } for all i with 0 ≤ i < t -p k . For infinite words the membership must hold for all i. If this is the case, we call (p 1 , p 2 , . . . , p k ) a pseudoperiod for w.

2

Joseph Meleshko et al.

In this paper, when we write a pseudoperiod (p 1 , p 2 , . . . , p k ) we always assume 0 < p 1 < • • • < p k . Note that 1-pseudoperiodicity is the ordinary notion of (pure) periodicity. If an infinite word w is kpseudoperiodic for some k < ∞, we call it pseudoperiodic.

We note that our definition of pseudoperiodicity is not the same as that studied by Blondin [START_REF] Blondin Massé | Pseudoperiodic words[END_REF]. Nor is it the same as the notion of quasiperiodicity, as introduced by [START_REF] Marcus | Quasiperiodic infinite words[END_REF], and now widely studied in many papers. Nor is it the same as "almost periodicity", which is more commonly called uniform recurrence (i.e., every block that occurs, occurs with bounded gaps between successive occurrences).

Notation

We use the familiar regular expression notation for regular languages. For infinite words, we let x ω for a nonempty finite word x denote the infinite word xxx • • • .

The exponent of a finite word x, denoted exp(x) is |x|/p, where p is the smallest period of x. For example, if x = entente, then exp(x) = 7/3. If q divides |x|, then by x p/q we mean the word of length p|x|/q that is a prefix of x ω . For example, (alf) 7/3 = alfalfa.

If all the nonempty factors f of a (finite or infinite) word x satisfy exp(f ) < e, we say that x is e-free. If they satisfy exp(f ) ≤ e, we say that x is e + -free.

The critical exponent of an infinite word w is the supremum of exp(x) over all finite nonempty factors x of w. Here the supremum is taken over the extended real numbers, where for each real number α there is a corresponding number α + satisfying α < α + < β for all β > α. Thus if x is a real number, the inequality x ≥ α + has the same meaning as x > α.

If S is a set of (finite or infinite) words, then its repetition threshold is the infimum of the critical exponents of all its words.

A run in a word is a maximum block of consecutive identical letters. The first run is called the initial run.

An occurrence of a finite nonempty word x in another word w (finite or infinite) is an index i such that w[i + j] = x[j] for 0 ≤ j < |x|. The distance between two occurrences i and i ′ is their difference |i ′ -i|.

The Thue-Morse word t = 01101001 • • • is the infinite fixed point, starting with 0, of the morphism µ(0) = 01 and µ(1) = 10.

Goals of this paper

There are five basic questions that interest us in this paper.

1. Given an infinite sequence s, is it pseudoperiodic? 2. If s is k-pseudoperiodic for some k, what is the smallest such k? 3. If s is k-pseudoperiodic, what are all the possible pseudoperiods of size k? 4. What is the smallest possible critical exponent of an infinite pseudoperiodic word with specified pseudoperiod?

5. How quickly can we tell if a given finite sequence has a pseudoperiod of bounded size?

Pseudoperiodic Words and a Question of Shevelev

3

In particular, we are interested in answering these questions for the class of sequences called automatic. A novel feature of our work is that much of it is done using a theorem-prover for automatic sequences, called Walnut, originally developed by Hamoon Mousavi. For more information about Walnut, see [START_REF] Mousavi | Automatic theorem proving in Walnut[END_REF]; [START_REF] Shallit | The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut[END_REF].

Here is a brief summary of what we do in our paper. In Section 2 we prove basic results about pseudoperiodicity, and show that questions 1, 2, and 3 above are decidable for the class of automatic sequences. In Section 3, we recall Shevelev's problems about pseudoperiods of the Thue-Morse word, solve them using our method, and also solve his open question from 2012. In Section 4, we obtain analogous pseudoperiodicity results for some other famous sequences. In Section 5 we turn to question 4, obtaining the best possible critical exponent for binary words having certain pseudoperiods. In Section 6 we treat the case of larger alphabets and obtain some results. In Section 7 we prove that checking the existence of a pseudoperiod of size k is, in general, a difficult computational problem, thus answering question 5. Along the way, we state two conjectures (Conjectures 34 and 39) and one open problem (Open Problem 30). Finally, in Section 8, we make some brief biographical remarks about Vladmir Shevelev.

Basic results

Proposition 2. An infinite word s is pseudoperiodic if and only if there exists a bound B < ∞ such that two consecutive occurrences of the same letter in s are always separated by distance at most B.

Proof: Suppose s has pseudoperiod (p 1 , p 2 , . . . , p k ), with p 1 < • • • < p k . Then clearly we may take B = p k .
On the other hand, if two consecutive occurrence of every letter are always separated by distance ≤ B, then we may take (1, 2, . . . , B) as a pseudoperiod for s.

For binary words we can say this in another way. Proposition 3. Let x be an infinite binary word.

(a) If M is the maximum element of a pseudoperiod, then the longest non-initial run in x is of length ≤ M -1;

(b) if the longest non-initial run length in x is B, then (1, 2, 3, . . . , B + 1) is a pseudoperiod.

In particular, an infinite binary word is pseudoperiodic if and only if it consists of a single letter repeated, or its sequence of run lengths is bounded.

Proof: Suppose x is pseudoperiodic with pseudoperiod (p 1 , p 2 , . . . , p k ) and let M = max 1≤i≤k p i . Let a ∈ {0, 1} and let x[p..q] be a run of a's and x[q + 1..r] be the following run (of a's). Then x[r + 1] = a. Now consider x[q] = a. Since x is pseudoperiodic, we know that (r + 1) -q ≤ M . Hence all non-initial runs are of length at most M -1.

On the other hand, if index p does not correspond to the last letter of a run, then

x[p] = x[p + 1].
If it does so correspond, since the word is binary and all non-initial run lengths are bounded, say by B, we know that x[p Proof: Follows immediately from Proposition 3.

+ i] = x[p] for some i ≤ B + 1. So (1, 2, . . . , B + 1) is a pseudoperiod.
Theorem 5. If an infinite word has pseudoperiod S then it has ≤ max S distinct letters. If it has exactly max S distinct letters, then it must have a suffix of the form x ω , where x is a word of length max S containing each letter exactly once.

Proof: Suppose w has pseudoperiod S, with k = max S. Since each occurrence of a letter is followed by another occurrence of the same letter at distance ≤ k, it follows that each letter of w must occur with frequency ≥ 1/k in w. But the total of all frequencies must sum to 1, so there cannot be more than k distinct letters.

Now suppose w has exactly k distinct letters, say 0, 1, . . . , k -1. Without loss of generality, assume that the last letter to occur for the first time is k -1 and p k-1 is this first occurrence. Furthermore, let p 0 , . . . , p k-2 be the positions of the last occurrence of the letters 0, 1, . . . , k -2 that precede p k-1 , and again, without loss of generality assume

p 0 < • • • < p k-2 < p k-1 . Thus w[p 0 ..p k-1 ] = 0 w 1 1 w 2 2 • • • (k -2) w k-1 (k -1)
for some words w 1 , w 2 , . . . , w k-1 , where w i contains no occurrences of letters < i. However, if any of these w i were nonempty then w could not be pseudoperiodic (because the 0 at position p 0 would not be followed by another 0 at distance ≤ k). So all the w i are empty. Furthermore, pseudoperiodicity also shows that w[p k-1 + 1] = 0, and inductively, that w[p k-1 + i] = (i -1) mod k for all i ≥ 0.

We now turn to results about automatic sequences. This is a large and interesting class of sequences where the nth term is computed by a finite automaton taking as input the representation of n in some base (or generalizations, such as Fibonacci base). For more information about automatic sequences, see [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF].

Corollary 6. Problems 1, 2, and 3 above are decidable, if s is an automatic sequence.

Proof: By the results of [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF], it suffices to create first-order logical formulas asserting each property. The domain of the variables in all logical statements is assumed to be N = {0, 1, 2, . . .}, the natural numbers.

By Proposition 2, we know that s is pseudoperiodic if there is a bound on the separation of two consecutive occurrences of the same letter. We can assert this as follows. First, define a formula that asserts that i < j are two consecutive occurrences of the same letter:

twoconsec(i, j) := i < j ∧ s[i] = s[j] ∧ ∀p (p > i ∧ p < j) =⇒ s[i] ̸ = s[p]. Next, the formula sep(B) := ∀i, j twoconsec(i, j) =⇒ j ≤ i + B.
asserts the claim that two consecutive occurrences of the same letter are separated by at most B. Finally, the formula ∃B sep(B) evaluates to TRUE if and only s is pseudoperiodic. This solves the first problem.

Once we know that s is pseudoperiodic, we can find the smallest B such that sep(B) holds. To do so, form the automaton for sep(B) ∧ ¬ sep(B -1);

it will accept exactly one value of B, which is the desired minimum. This tells us that s has pseudoperiod (1, 2, . . . , B), so certainly it is B-pseudoperiodic.

We can now write the assertion that s has a pseudoperiod of size p, as follows:

∃a 1 , a 2 , . . . , a p 1 ≤ a 1 ∧ a 1 < a 2 ∧ • • • ∧ a p-1 < a p ∧ ∀n (s[n] = s[n + a 1 ] ∨ s[n] = s[n + a 2 ] ∨ • • • ∨ s[n] = s[n + a p ]).
By testing this for p = 1, . . . , B, we can find the smallest p for which this holds. This solves problem 2. Finally, we can determine all possible pseudoperiods of size p with the formula

1 ≤ a 1 ∧ a 1 < a 2 ∧ • • • ∧ a p-1 < a p ∧ ∀n (s[n] = s[n + a 1 ] ∨ s[n] = s[n + a 2 ] ∨ • • • ∨ s[n] = s[n + a p ]).
The corresponding finite automaton accepts all the possible pseudoperiods (a 1 , . . . , a p ) of size p.

From these ideas we can prove an interesting corollary.

Corollary 7. Suppose the automatic sequence s is not k-pseudoperiodic. Then there exists a constant C (depending only on s) such that for all k-tuples 0

< p 1 < p 2 < • • • < p k , the smallest n for which s[n] ̸ ∈ {s[n + p 1 ], s[n + p 2 ], . . . , s[n + p k ]} satisfies n ≤ Cp k .
Proof: A trivial variation on the previous arguments shows that if s is automatic, then there is an automaton accepting, in parallel, n, p 1 , p 2 , . . . , p k such that n is the smallest natural number satisfying

s[n] ̸ ∈ {s[n + p 1 ], s[n + p 2 ], . . . , s[n + p k ]}.
Thus, in the terminology of [START_REF] Shallit | Synchronized sequences[END_REF], this n can be considered a "synchronized function" of (p 1 , . . . , p k ). We can then apply the known linear bound on synchronized functions (Shallit, 2021, Thm. 8) to deduce the existence of C such that n ≤ Cp k .

Although, as we have just seen, these problems are all decidable for automatic sequences in theory, in practice, the automata that result can be extremely large and require a lot of computation to find. We can use Walnut, a theorem-prover originally designed by [START_REF] Mousavi | Automatic theorem proving in Walnut[END_REF] to translate logical formulas to automata.

Example 8. Let us consider an example, the Fibonacci word f = 01001010 • • • , the fixed point of the morphism 0 → 01, 1 → 0. The following Walnut code demonstrates that it is 2-pseudoperiodic. (In fact, this follows from the much more general Proposition 9 below.)

eval isfibpseudo "?msd_fib Ea,b 1<=a & a<b & An (F[n]=F[n+a]|F[n]=F[n+b])": It returns TRUE.
We can determine all possible pseudoperiods of size 2 using Walnut, as follows:

def fib2pseudoperiod "?msd_fib 1<=a & a<b & An (F[n]=F[n+a]|F[n]=F[n+b]
)": The resulting automaton accepts all pairs (a, b) that are pseudoperiods of f , in Fibonacci representation. It has 28 states and is displayed in Figure 1.

We now consider a famous uncountable class of binary sequences, the Sturmian words (Lothaire, 2002, Chap. 2). These are infinite words of the form s α,β := (⌊(n+1)α+β⌋-⌊nα+β⌋) n≥1 , where 0 < α < 1 is an irrational real number and 0 ≤ β < 1. Proof: If s α,β were 1-pseudoperiodic, it would be periodic and hence the letter 1 would occur with rational density. However, the 1's appear in s α,β with density α, which is irrational.

Proposition 9. Every Sturmian sequence is 2-pseudoperiodic but not 1-pseudoperiodic. 0 [0,0] 1 [0,1] 2 [1,1] 3 [0,0] 4 [1,0] 5 [0,0] 6 [0,0] 7 [1,0] 8 [0,1] 9 [1,1] 10 [0,0] 11 [0,1] [1,1] 12 [0,0] 13 [0,1] [0,1] [0,0] [1,0] 14 [1,1] 15 [0,0] 16 [0,1] [0,0]
Now let [0, c 1 , c 2 , . . .] be the continued fraction expansion of α. Without loss of generality, we can assume that α < 1/2; otherwise consider s 1-α,0 which is the binary complement of s α,0 . Hence c 1 ≥ 2.

It is easy to see from the definition of s α,β that s α,0 is a suffix of an infinite concatenation of blocks of the form 0 c1-1 1 and 0 c1 1. It follows that (c 1 , c 1 + 1) is a pseudoperiod.

Remark 10. There are, of course, non-Sturmian sequences that are 2-pseudoperiodic but not 1-pseudoperiodic. For example, every sequence in {01, 001} ω has pseudoperiod (2, 3).

Remark 11. Trivial observation: to determine whether a given fixed tuple (p 1 , p 2 , . . . , p k ) is a pseudoperiod of an infinite sequence s, it suffices to examine all of the factors of length p k + 1 of s.

Shevelev's problems

In this section, we consider some results of Vladimir [START_REF] Shevelev | Equations of the form t(x + a) = t(x) and t(x + a) = 1 -t(x) for Thue-Morse sequence[END_REF]. We reprove some of his results in a much simpler manner, obtain new results, and completely solve one of his open questions.

Recall from Section 1.1 that the Thue-Morse sequence t = 01101001 • • • is the infinite fixed point, starting with 0, of the map sending 0 → 01 and 1 → 10. Shevelev was interested in the pseudoperiodicity of t, and gave a number of theorems and open questions involving this sequence. We are able to prove all of the theorems and conjectures in Shevelev (2012) using our method, with the exception of his Conjecture 1. Luckily, this conjecture was already proved by Allouche (Allouche, 2015, Thm. 3.1).

Proposition 12. The Thue-Morse sequence is 3-pseudoperiodic, but not 2-pseudoperiodic.

Proof: The first statement follows from the (almost trivial) fact that every word in {01, 10} ω has pseudoperiod (1, 2, 3).

For the second statement, we use Walnut again. To prove the second half of the theorem, we assert 2-pseudoperiodicity as follows and show that it is false:

∃a, b (a ≥ 1) ∧ (a < b) ∧ ∀i (t[i] ∈ {t[i + a], t[i + b]}).
Translating the assertion into Walnut, we have:

eval twopseudotm "Ea,b (a>=1 & a<b) & Ai (T[i]=T[i+a] | T[i]=T[i+b])": # returns FALSE # 23 ms
This returns FALSE, which proves that the Thue-Morse sequence is not 2-pseudoperiodic.

Since t is not 2-pseudoperiodic, we know from Corollary 7 that there exists a constant C such that for

1 ≤ a < b we have t[n] ̸ ∈ {t[n + a], t[n + b]} for some n ≤ Cb.
For the Thue-Morse word, we can prove the following bound:

Theorem 13. (a) For all a, b with 1 ≤ a < b there exists n ≤ 5 3 b such that t[n] ̸ ∈ {t[n + a], t[n + b]}. (b)
The previous result is optimal, in the sense that if the bound 5 3 b is reduced, then there are infinitely many counterexamples.

Proof: To prove (a) and (b), we can use the following Walnut commands:

eval casea "Aa,b (1<=a & a<b) => En (3 * n<=5 * b) & T[n]!=T[n+a] & T[n]!=T[n+b]": # evaluates to TRUE eval caseb "Am Ea,b 1<=a & a<b & b>m & Ai (3 * i<5 * b) => (T[i]=T[i+a]|T[i]=T[i+b]
)": # evaluates to TRUE We now turn to Shevelev's Proposition 1 in [START_REF] Shevelev | Equations of the form t(x + a) = t(x) and t(x + a) = 1 -t(x) for Thue-Morse sequence[END_REF] which (in our terminology) asserts the following:

Theorem 14. The triples {(a, a + 2 k , a + 2 k+1 ) : a ≥ 1, k ≥ 0} are pseudoperiods for the Thue-Morse sequence.

Shevelev's proof of this was rather long and involved. We can prove it almost instantly with Walnut, as follows:

Proof: We express the conditions placed on the triples as follows.

Power2(x) := ∃k x = 2 k ShevCond(a, b, c) := (a ≥ 1) ∧ (∃x Power2(x) ∧ (b = a + x) ∧ (c = a + 2x)).
We write the proposition as:

∀a, b, c, i ShevCond(a, b, c) =⇒ (t[i] ∈ {t[i + a], t[i + b], t[i + c]}).
Translating the above into Walnut commands, we have:

reg power2 msd_2 "0 * 10 * ": def shevcond "(a>=1) & (Ex $power2(x) & (b=a+x) & (c=a+2 * x))": # returns a DFA with 7 states # 13 ms eval prop1 "Aa,b,c,i $shevcond(a,b,c) => (T[i]=T[i+a] | T[i]=T[i+b] | T[i]=T[i+c]
)": # returns TRUE # 6 ms The assertion returns TRUE, which proves that the Thue-Morse sequence is 3-pseudoperiodic.

Shevelev observed that Theorem 14 did not characterize all such triples. In his Proposition 2, he showed (1, 8, 9) is a pseudoperiod. We can do this with Walnut as follows:

eval shevprop2 "Ai (T[i]=T[i+1])|(T[i]=T[i+8])|(T[i]=T[i+9])": # 97 ms # return TRUE
These two results caused Shevelev to pose his "Open Question 1", which in our terminology is the following:

Open Problem 15. Characterize all triples (a, b, c) with 1 ≤ a < b < c that are pseudoperiods for the Thue-Morse sequence.

Shevelev was unable to solve this, but using our methods, we can easily solve it.

Theorem 16. There is a DFA of 53 states that accepts exactly the triples (a, b, c) such that 1 ≤ a < b < c is a pseudoperiod of t.

Proof: We want to characterize the triples (a, b, c) such that

Triple(a, b, c) := (a ≥ 1) ∧ (a < b) ∧ (b < c) ∧ ∀i t[i] ∈ {t[i + a], t[i + b], t[i + c]}.
We construct the following DFA triple in Walnut to answer the question.

def triple "(a>=1) & (a<b) & (b<c) & Ai (T[i]=T[i+a] | T[i]=T[i+b] | T[i]=T[i+c]
)": # returns a DFA with 53 states # 4356513 ms This gives us an automaton of 53 states, which is presented in the Appendix. Determining it was a major calculation in Walnut, requiring 4356 seconds of CPU time and 18 GB of storage. The complete answer to Shevelev's question is then the set of triples accepted by our DFA triple.

Because the answer is so complicated, it is not that surprising that Shevelev did not find a simple answer to his question. Now that we have the automaton triple, we can easily check any triple (a, b, c) to see if it is a pseudoperiod of t in O(log abc) time, merely by feeding the automaton with the base-2 representations of the triple (a, b, c).

Furthermore, our automaton can be used to easily prove other aspects of the pseudoperiods of the Thue-Morse sequence. For example:

Corollary 17. We now look at the possible distances between pseudoperiods of t.

Corollary 18.

(a) {b -a : ∃c (a, b, c) is a pseudoperiod of t} = {(2 j -1)2 i : j ≥ 1, i ≥ 0} ∪ {(2 2j-1 + 1)2 i : j ≥ 1, i ≥ 0} ∪ {11 • 2 i : i ≥ 0}. (b) {c -b : ∃a (a, b, c) is a pseudoperiod of t} = {(2 j -1)2 i : j ≥ 1, i ≥ 0} ∪ {(2 j + 1)2 i : j ≥ 1, i ≥ 0}.
Proof: We use the following Walnut code. Proof: To assert the claim in first-order logic, we first construct a formula to show that at least one of the values in S is not equal to the other two; this implies that S contains both t[i] and t[i]:

NeqTriple(a, b, c) := (a ≥ 1) ∧ (a < b) ∧ (a < c) ∧ ∀i (t[i + a] ̸ = t[i + b] ∨ t[i + b] ̸ = t[i + c] ∨ t[i + c] ̸ = t[i + a]).
Our theorem can then be expressed as follows. We now turn to Shevelev's Propositions 3 and 4 in [START_REF] Shevelev | Equations of the form t(x + a) = t(x) and t(x + a) = 1 -t(x) for Thue-Morse sequence[END_REF]. In our terminology, these are as follows:

Proposition 20. For all k ≥ 1, the Thue-Morse sequence has pseudoperiod (a, b, c) if and only if it has pseudoperiod (2 k a, 2 k b, 2 k c).

Proof: We prove the following equivalent statement which implies the proposition by induction on k:

∀a, b, c Triple(a, b, c) ⇐⇒ Triple(2a, 2b, 2c).
Translating this into Walnut, we have the following.

Other sequences

After having obtained pseudoperiodicity results for the Thue-Morse sequence t, it is logical to try to obtain similar results for other famous sequences.

In this section we examine sequences such as the Rudin-Shapiro sequence rs, the variant Thue-Morse sequence vtm, the Tribonacci sequence tr, and so forth.

For each sequence s in this section, we assert 2-pseudoperiodicity as follows and use Walnut to determine whether it holds:

∃a, b (a ≥ 1) ∧ (a < b) ∧ ∀i (s i ∈ {s i+a , s i+b }).
And we assert 3-pseudoperiodicity as follows and use Walnut to determine whether it holds:

∃a, b, c (a ≥ 1) ∧ (a < b) ∧ (b < c) ∧ ∀i (s i ∈ {s i+a , s i+b , s i+c }).

The Mephisto Waltz sequence

The Mephisto Waltz sequence mw = 001001110 • • • is defined by the infinite fixed point of the morphism 0 → 001, 1 → 110 starting with 0. It is sequence A064990 in the OEIS.

Proposition 21. The Mephisto Waltz sequence is 3-pseudoperiodic, but not 2-pseudoperiodic.

Proof: We translate the assertions of 2-pseudoperiodicity into Walnut as follows and show that it is false.

eval twopseudomw "?msd_3 Ea,b (a>=1 & a<b) & Ai (MW[i]=MW[i+a] | MW[i]=MW[i+b]
)": # 496 ms # return FALSE We translate the assertions of 3-pseudoperiodicity into Walnut as follows and show that it is true.

eval threepseudomw "?msd_3 Ea,b,c (a>=1 & a<b & b<c) & Ai (MW[i]=MW[i+a] | MW[i]=MW[i+b] | MW[i]=MW[i+c])": # 2202253 ms # return TRUE
Knowing that the Mephisto Waltz sequence is 3-pseudoperiodic naturally leads to the following problem.

Problem 22. Characterize all triples (a, b, c) with 1 ≤ a < b < c that are pseudoperiods for the Mephisto Waltz sequence.

We want to characterize the triples (a, b, c) such that

TripleMW(a, b, c) := (a ≥ 1) ∧ (a < b) ∧ (b < c) ∧ ∀i mw[i] ∈ {mw[i + a], mw[i + b], mw[i + c]}.
We construct the following DFA triplemw in Walnut to solve the problem.

def triplemw "?msd_3 (a>=1 & a<b & b<c) & Ai (MW[i]=MW[i+a] | MW[i]=MW[i+b] | MW[i]=MW[i+c]
)": # returns a DFA with 13 states # 2331762 ms The complete answer to this problem is the set of triples accepted by our DFA triplemw.

The ternary Thue-Morse sequence

The ternary Thue-Morse sequence vtm = 210201 • • • is defined by the infinite fixed point of the morphism 2 → 210, 1 → 20, and 0 → 1 starting with 2. It is sequence A036577 in the OEIS.

Proposition 23. The ternary (variant) Thue-Morse sequence is 3-pseudoperiodic, but not 2-pseudoperiodic.

Proof: We translate the assertions of 2-pseudoperiodicity into Walnut as follows and show that it is false.

eval twopseudovtm "Ea,b (a>=1 & a<b) & Ai (VTM[i]=VTM[i+a] | VTM[i]=VTM[i+b]
)": # 235 ms # return FALSE We translate the assertions of 3-pseudoperiodicity into Walnut as follows and show that it is true.

eval threepseudovtm "Ea,b,c (a>=1 & a<b & b<c) & Ai (VTM[i]=VTM[i+a] | VTM[i]=VTM[i+b] | VTM[i]=VTM[i+c])": # 505315560 ms # 188 GB # return TRUE
Knowing that the ternary Thue-Morse sequence is 3-pseudoperiodic naturally leads to the following problem.

Problem 24. Characterize all triples (a, b, c) with 1 ≤ a < b < c that are pseudoperiods for the ternary Thue-Morse sequence.

We want to characterize the triples (a, b, c) such that

TripleVTM(a, b, c) := (a ≥ 1) ∧ (a < b) ∧ (b < c) ∧ ∀i (vtm[i] ∈ {vtm[i+a], vtm[i+b], vtm[i+c]}).
We construct the following DFA triplevtm in Walnut to solve the problem.

def triplevtm "(a>=1 & a<b & b<c) & Ai (VTM[i]=VTM[i+a] | VTM[i]=VTM[i+b] | VTM[i]=VTM[i+c]
)": # returns a DFA with 12 states # 815830898 ms The complete answer to this problem is the set of triples accepted by our DFA triplevtm. It is depicted in Figure 2. Again, this was a very large computation with Walnut.

0 [0,0,0] 1 [0,0,1] 2 [0,1,1] 3 [1,1,1] 4 [1,1,0] 5 [0,0,0] 6 [0,0,1] 7 [0,0,0] [1,1,0] 8 [0,1,0] [0,0,0] 9 [1,1,0] [0,0,0] 10 [0,0,1] 11 [0,0,0] [1,0,0] [0,1,0] [0,0,0]
Fig. 2: Automaton recognizing all pseudoperiods of size 3 for the vtm sequence.

Pseudoperiodic Words and a Question of Shevelev

13

By looking at the acceptance paths of Figure 2, we can deduce the following result.

Theorem 25. The only 3-pseudoperiods for the vtm sequence are

• {((2 2i+1 -1)2 2j+1 , (2 2i+2 -1)2 2j , 2 2i+2j+2 ) : i, j ≥ 0} • {(3 • 2 2j , (2 2i+2 + 1)2 2j+1 , (2 2i+1 + 1)2 2j+2 ) : i, j ≥ 0} • {(2 2i+2j+3 , (2 2i+3 + 1)2 2j , (2 2i+2 + 1)2 2j+1 ) : i, j ≥ 0}.
Proof: There are only essentially three possible paths to the accepting state labeled 8 in Figure 2. They are labeled

• [0, 0, 0] * [0, 0, 1][1, 1, 0]([1, 1, 0][1, 1, 0]) * [0, 1, 0]([0, 0, 0][0, 0, 0]) * • [0, 0, 0] * [0, 1, 1]([0, 0, 0][0, 0, 0]) * [0, 0, 1][1, 1, 0][1, 0, 0]([0, 0, 0][0, 0, 0]) * • [0, 0, 0] * [1, 1, 1][0, 0, 0]([0, 0, 0][0, 0, 0]) * [0, 0, 1][0, 1, 0]([0, 0, 0][0, 0, 0]) *
By considering the base-2 numbers specified by each coordinate, we obtain the theorem.

The period-doubling sequence

The period-doubling sequence pd = 1011101011 • • • is defined by the infinite fixed point of the morphism 1 → 10, 0 → 11 starting with 1. It is sequence A035263 in the OEIS.

Proposition 26. The period-doubling sequence is 3-pseudoperiodic, but not 2-pseudoperiodic.

Proof: We translate the assertions of 2-pseudoperiodicity into Walnut as follows and show that it is false.

eval twopseudopd "Ea,b (a>=1 & a<b) & Ai (PD[i]=PD[i+a] | PD[i]=PD[i+b]
)": # 424 ms # return FALSE We translate the assertions of 3-pseudoperiodicity into Walnut as follows and show that it is true.

eval threepseudopd "Ea,b,c (a>=1 & a<b & b<c) & Ai (PD[i]=PD[i+a] | PD[i]=PD[i+b] | PD[i]=PD[i+c])": # 40 ms # return TRUE
Knowing that the period-doubling sequence is 3-pseudoperiodic naturally leads to the following problem.

Problem 27. Characterize all triples (a, b, c) with 1 ≤ a < b < c that are pseudoperiods for the perioddoubling sequence.

We want to characterize the triples (a, b, c) such that

TriplePD(a, b, c) := (a ≥ 1) ∧ (a < b) ∧ (b < c) ∧ ∀i (pd[i] ∈ {pd[i + a], pd[i + b], pd[i + c]}).
We construct the following DFA triplepd in Walnut to solve the problem.

def triplepd "(a>=1 & a<b & b<c) & Ai (PD[i]=PD[i+a] | PD[i]=PD[i+b] | PD[i]=PD[i+c]
)": # returns a DFA with 28 states # 30 ms

The complete answer to this problem is the set of triples accepted by our DFA triplepd.

The Rudin-Shapiro sequence

The Rudin-Shapiro sequence r = 00010010

• • • is defined by the relation r[n] = |(n) 2 | 11 mod 2, that
is, the number of occurrences of 11, computed modulo 2, in the base-2 representation of n. It is sequence A020987 in the OEIS.

Theorem 28. The Rudin-Shapiro sequence is 4-pseudoperiodic, but not 3-pseudoperiodic.

Proof: To check 3-pseudoperiodicity, we used the Walnut command

eval rudinpseudo "Ea,b,c a>=1 & a<b & b<c & An (RS[n]=RS[n+a]|RS[n]=RS[n+b]|RS[n]=RS[n+c])":
which returned the result FALSE. This was a big computation, requiring 20003988ms and more than 200 GB of memory on a 64-bit machine.

It is 4-pseudoperiodic, as Walnut can easily verify that (2, 3, 4, 5) is a pseudoperiod.

The Tribonacci sequence

The Tribonacci sequence is a generalization of the Fibonacci sequence. It is defined by the infinite fixed point of the morphism 0 → 01, 1 → 02, and 2 → 0 and is sequence A080843 in the OEIS.

Theorem 29. The Tribonacci sequence is 3-pseudoperiodic, but not 2-pseudoperiodic.

Proof: It has pseudoperiod (4, 6, 7), as can be easily verified by checking all factors of length 8 (or with Walnut).

Open Problem 30. Characterize all the 3-pseudoperiods of the Tribonacci sequence.

Although this is in principle doable with Walnut, so far, this seems to be beyond our computational abilities, requiring the determinization of a large nondeterministic automaton.

The paperfolding sequences

The paperfolding sequences are an uncountable family of sequences originally introduced by [START_REF] Davis | Number representations and dragon curves-I, II[END_REF] and later studied by Dekking et al. (1982). The first-order theory of the paperfolding sequences was proved decidable in [START_REF] Goč | A new approach to the paperfolding sequences[END_REF]. Every infinite paperfolding sequence is specified by an infinite sequence f of unfolding instructions. Since Walnut's automata work on finite strings-they are not Büchi automata-we have to approximate an infinite f by considering its finite prefixes f . A fuller discussion of exactly how to do this can be found in (Shallit, 2022, Chap. 12); we just sketch the ideas here.

We can use Walnut to determine the pseudoperiods of any specific paperfolding sequence, or the pseudoperiod common to all paperfolding sequences.

Walnut can prove that no paperfolding sequence is 2-pseudoperiodic, as follows:

reg linkf {-1,0,1} {0,1} "() * [0,1][0,0] * ": def pffactoreq "?lsd_2 At (t<n) => FOLD[f][i+t]=FOLD[f][j+t]": eval paper_pseudo2 "?lsd_2 Ef,a,b,x 1<=a & a<b & $linkf(f,x) & x>=2 * b+3 & Ai (i>=1 & i+b+1<=x) => ($pffactoreq(f,i,i+a,1)|$pffactoreq(f,i,i+b,1))": # FALSE, 26926 secs
Here pffactoreq asserts that the two length-n factors of the paperfolding sequence specified by a finite code f , one beginning at position i and one at position j are the same. And linkf asserts that x = 2 |f | . The assertion paper pseudo2 is that there exists some paperfolding sequence and numbers a, b such that every position i has a symbol equal to either the symbol at position i + a or i + b.

All paperfolding sequences are 3-pseudoperiodic; for example, (1, 3, 4) is a pseudoperiod of all paperfolding sequences.

eval paper_pseudo134 "?lsd_2 Af,x,i ($linkf(f,x) & i>=1 & i+5<=x) => ($pffactoreq(f,i,i+1,1)|$pffactoreq(f,i,i+3,1)| $pffactoreq(f,i,i+4,1))":
However, not all pseudoperiods work for all paperfolding sequences. For example, we can use Walnut to show that (1, 2, 16) is a pseudoperiod for the paperfolding sequence specified by the unfolding instructions 1 1 1 • • • , but not a pseudoperiod for the regular paperfolding sequence (specified by

1 1 1 • • • ).
We can compute the pseudoperiods that work for all paperfolding sequences simultaneously, using the following Walnut code:

def paper_pseudo3 "?lsd_2 1<=a & a<b & b<c & Af,x,i ($linkf(f,x) & i>=1 & i+c+1<=x) => ($pffactoreq(f,i,i+a,1)|$pffactoreq(f,i,i+b,1)|$pffactoreq(f,i,i+c,1))": # 10 states, 2356 ms
The automaton in Figure 3 accepts the base-2 representation (here, least significant digit first) of those triples (a, b, c) with 1 ≤ a < b < c as a pseudoperiod for all paperfolding sequences. The general strategy we employ is the following. We use a heuristic search procedure to try to guess a morphism h a,b such that either h a,b (t) or h a,b (vtm) has pseudoperiod (a, b) and avoids e + powers for some suitable exponent e. Once such an h a,b is found, we can verify its correctness using Walnut. Simultaneously we can do a breadth-first search over the tree of all binary words having pseudoperiod (a, b) and avoiding e-powers. If this tree turns out to be finite, we have proved the optimality of this e.

Our first result shows that this critical exponent can never be ≤ 7/3.

Theorem 31. If x is an infinite binary word that is 2-pseudoperiodic, then x contains a (7/3)-power.

Proof: Suppose x has pseudoperiod 1 ≤ a < b, but is (7/3)-power-free. Theorem 6 of [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF] says that every infinite (7/3)-power-free binary word contains factors of the form µ i (0) for all i ≥ 0. These factors are all prefixes of t.

However, as we have seen in Theorem 13, the prefix of length 5 3 b + 1 of t cannot have pseudoperiod a, b, as the relation t

[n] ∈ {t[n + a], t[n + b]} is violated for some n ≤ 5
3 b. Thus it suffices to choose i large enough such that 2 i ≥ 5 3 b + 1. This contradiction proves the result. Next we consider the case b = 2a.

Proposition 32. Let a ≥ 1 be an integer. If an infinite word has pseudoperiod (a, 2a), then it has critical exponent ∞.

Proof: Suppose that x has pseudoperiod (a, 2a). From x extract the subsequences x a,i = (x[an + i]) n≥0 corresponding to indices that are congruent to i (mod a), for 0 ≤ i < a. Clearly each such subsequence has pseudoperiod (1, 2). By Proposition 4, each subsequence x a,i must be of the form c ω or c * (cd) ω for c, d distinct letters. It now follows that x is eventually periodic with period 2a, and hence has infinite critical exponent.

Proposition 33. Let α ≥ 2 + . If an α-free (resp., α + -free) binary word w has pseudoperiod (a 1 , . . . , a k ), then µ(w) is an α-free (resp., α + -free) binary word with pseudoperiod (2a 1 , . . . , 2a k ).

Proof: The claim about the pseudoperiods is clear. The result about power-freeness can be found in, e.g., (Karhumäki and Shallit, 2004, Theorem 5).

We now summarize our results on critical exponents in the following table. Each entry corresponding to a pseudoperiod (a, b) with b ̸ = 2a has three entries: Tab. 1: Optimal critical exponents for binary words with certain specified pseudoperiod.

See the files longest finite seqs.txt and critical exp morphisms.txt at https://github.com/sonjashan/sha_gen.git for the specific morphisms.

From examination of Table 1, we see that all the critical exponents are at most 3 + . This leads to the following conjecture.

Conjecture 34. For all pairs (a, b) with 1 ≤ a < b and b ̸ = 2a, there exists an infinite binary word with pseudoperiod (a, b) and avoiding 3 + -powers.

We verified this conjecture for 1 ≤ a < b ≤ 54. For each pair of a and b, we first try each previously saved morphism h on the Thue-Morse sequence t to see if h(t) has pseudoperiod {a, b} and avoids 3 +powers. If that fails, we use backtracking to search for a new morphism that meets the criteria. Once we find such an morphism, we verify the pseudoperiodicity and the powerfreeness with Walnut and save the morphism for future use.

The following morphism is an example. It is initially generated for a = 1 and b = 5 but it also works for 122 other pairs of a and b we tested.

morphism sha3 "0->11100011000 1->11100111000": image S3 sha3 T: eval pp1_5_checkS3 "An (S3[n]=S3[n+1]|S3[n]=S3[n+5])": eval cubeplusfree_S3 "˜Ei,n n>0 & Aj (j<=2 * n) => S3[i+j] = S3[i+j+n]":
For more details on this implementation, please see the github repository at https://github.com/sonjashan/sha_gen.git . Let us also provide details about the exceptional case of a = 1 and b = 6. The morphic word with pseudoperiod (1, 6) which avoids (7/3) + -powers is h 1,6 (vtm), where h 1,6 (0) = 0011011001011001, h 1,6 (1) = 0011011001, and h 1,6 (2) = 001101.

A simple computation shows that h(vtm) has pseudoperiod (1, 6) and that its factors of length 1000 avoid (7/3) + -powers.

Suppose that h 1,6 (vtm) contains a factor w that is a (7/3) + -power. Thus |w| > 1000. Notice that the factor 0011 is a common prefix of the h 1,6 -image of all three letters. Moreover, 0011 appears in h 1,6 (vtm) only as the prefix of the h-image of a letter.

We consider the word w ′ obtained from w by erasing the smallest prefix of w such that w ′ starts with 0011. Since we erase at most |h(0)| -1 = 15 letters, the word w ′ is a repetition of period p and exponent at least 2.2.

So w ′ [1.

.4] = w ′ [p + 1..p + 4] = w ′ [2p + 1..2p + 4] = 0011. This implies that w ′ [1..2p] = h(uu) where the pre-image uu must be a factor of vtm. This is a contradiction, since vtm is squarefree.

Finally, the results with a morphic word using µ as outer morphism are obtained via Proposition 33.

5.1 Binary words with pseudoperiods of the form (1, a)

Theorem 35. For at least 85% of all positive integers a ≥ 3 there is an infinite binary word with pseudoperiod (1, a), and avoiding 3 + -powers.

Proof: The idea is to search for words with the given properties that have pseudoperiod (1, a) for all a in a given residue class a ≡ i (mod n). As before, our words are constructed by applying an n-uniform morphism (obtained by a heuristic search) to the Thue-Morse word t, and then correctness is verified with Walnut.

Our results are summarized in Table 2.

As an example, here is the Walnut code verifying the results for (i, n) = (4, 5): morphism a45 "0->00011 1->00111": image B45 a45 5,7,9,11,13,14,15,16. Now lcm(5,7,9,11,13,14,15,16) = 720720, and the residue classes above cover 614614 of the possible residues (mod 720720). So we have covered 614614/720720 . = .852 of all the possible a.

Theorem 35 can obviously be improved by considering larger moduli. For example, there exists a morphism for every residue class modulo 41 except 0, 1, 2, 5, 6, 21, 23, 39.

Larger alphabets

Up to now we have been mostly concerned with binary words. In this section we consider pseudoperiodicity in larger alphabets.

The (unrestricted) repetition threshold RT (k) for words over k letters is well-known: we have RT (3) = 7/4, RT (4) = 7/5, and RT (k) = k/(k -1) if k = 2 or k ≥ 5 Currie and Rampersad (2011); [START_REF] Rao | Last cases of Dejean's conjecture[END_REF]. Notice that the words attaining the repetition threshold are necessarily 3-pseudoperiodic. Indeed, every infinite (k -1)/(k -2)-free word over k ≥ 3 letters is (k -1, k, k + 1)-periodic. Thus, it remains to investigate 2-pseudoperiodic words.

Let us consider the repetition threshold RT ′ (k) for 2-pseudoperiodic words over k letters. Obviously, RT (k) ≤ RT ′ (k). From the previous section, we know that RT ′ (2) = 7/3. The following results show that RT ′ (3) = 7/4, RT ′ (4) ≤ 3/2, and RT ′ (5) ≤ 4/3, respectively.

Theorem 36. The image of every (7/5) + -free word over 4 letters by the following 188-uniform morphism avoids (7/4) + -powers and has pseudoperiod (18, 37). Theorem 38. The image of every (5/4) + -free word over 5 letters by the following 84-uniform morphism avoids (4/3) + -powers and has pseudoperiod (9, 19).

Proposition 4 .

 4 The only infinite words with pseudoperiod (1, 2) are those of the form a ω or a * (ab) ω and b * (ba) ω for distinct letters a, b. The only finite words with pseudoperiod (1, 2) are those of the form a * (ab) * (a + ϵ) with a ̸ = b.

Fig. 1 :

 1 Fig. 1: Pseudoperiods of size 2 for the Fibonacci word.

  (a) For each a ≥ 1 there exist arbitrarily large b, c such that (a, b, c) is a pseudoperiod of t. (b) For each b ≥ 2 there exist pairs a, c such that (a, b, c) is a pseudoperiod of t. (c) For each c ≥ 3 there exist pairs a, b such that (a, b, c) is a pseudoperiod of t. Proof: We use the following Walnut code. eval tmpa "Aa,m (a>=1) => Eb,c b>m & c>m & $triple(a,b,c)": eval tmpb "Ab (b>=2) => Ea,c $triple(a,b,c)": eval tmpc "Ac (c>=3) => Ea,b $triple(a,b,c)": and Walnut returns TRUE for all three.

  reg parta msd_2 "0 * 11 * 0 * |0 * 1(00) * 10 * |0 * 10110 * ": reg partb msd_2 "0 * 100 * 10 * |0 * 11 * 0 * ": eval checka "An $parta(n) <=> (Ea,b,c $triple(a,b,c) & b=a+n)": eval checkb "An $partb(n) <=> (Ea,b,c $triple(a,b,c) & c=b+n)": and Walnut returns TRUE twice. We now turn to Shevelev's Theorem 2 in Shevelev (2012). Theorem 19. The only triples of distinct positive integers (a, b, c) for which both t[i] and t[i] belong to {t[i + a], t[i + b], t[i + c]} for all i ≥ 0 are those satisfying b = a + 2 k and c = a + 2 k+1 for some k ≥ 0.

  ∀a, b, c (Triple(a, b, c) ∧ NeqTriple(a, b, c)) ⇐⇒ ShevCond(a, b, c).Translating the above into Walnut, we build a DFA neqtriple.def neqtriple "(a>=1) & (a<b) & (b<c) & Ai (T[i+a]!=T[i+b] | T[i+b]!=T[i+c] | T[i+c]!=T[i+a])": # returns a DFA with 7 states # 554 ms We prove the theorem with the Walnut command below: eval thm2 "Aa,b,c ($triple(a,b,c) & $neqtriple(a,b,c)) <=> $shevcond(a,b,c)": # returns TRUE # 6 ms This returns TRUE, which proves the Theorem.

  eval prop3n4 "Aa,b,c $triple(a,b,c) <=> $triple(2 * a, 2 * b, 2 * c)": # returns TRUE # 14 ms This returns TRUE, which proves the proposition.

Fig. 3 :

 3 Fig. 3: Automaton accepting base-2 representations of pseudoperiod triples common to all paperfolding sequences.

  (a) upper left: an exponent e, where the repetition threshold for C a,b is e + ; (b) upper right: the length of the longest finite word having pseudoperiod (a, b) and avoiding e-powers; (c) lower line: the morphic word with pseudoperiod (a, b) and avoiding e + powers.

  eval cube45 "˜Ei,n (n>=1) & At (t<=2 * n) => B45[i+t]=B45[i+n+t]": eval test45 "Ap (Ek p=5 * k+4) => An (B45[n]=B45[n+1]|B45[n]=B45[n+p])":and both commands return TRUE.The residue classes in Table2correspond to n =

  The image of every (7/5) + -free word over 4 letters by the following 170-uniform morphism avoids (3/2) + -powers and has pseudoperiod (4

Joseph Meleshko et al.

Acknowledgements

This work benefited from the use of the CrySP RIPPLE Facility at the University of Waterloo. Thanks to Ian Goldberg for allowing us to run computations on this machine.

We thank the referees for a careful reading of the paper and for many useful suggestions and corrections.

We are grateful to Daniel Berend and Simon Litsyn for their assistance in obtaining information about the life of Vladimir Shevelev.

In honor of Vladimir Shevelev (* The research of JS is supported by NSERC Grant 2018-04118.

where p = 043012032142.

Theorems 36, 37, and 38 make use of [START_REF] Ochem | A generator of morphisms for infinite words[END_REF], Lemma 2.1), which has been recently extended to larger exponents in (Mol et al., 2020, Lemma 23). In each case, the common prefix p appears only as the prefix of the image of a letter. This ensures that the morphism is synchronizing. Then we check that the image of every considered Dejean word u of length t is RT ′ (k) + -free, where t is specified by (Ochem, 2006, Lemma 2.1).

In addition, using depth-first search of the appropriate space, we have constructed:

• A (5/4) + -free word over 6 letters with pseudoperiod (9,24), of length 500000.

• A (6/5) + -free word over 7 letters with pseudoperiod (22,33), of length 500000.

These examples suggest the following conjecture.

Conjecture 39. For every k ≥ 4 we have

Computational complexity

For a finite word, checking a given specific pseudoperiod is obviously easy. However, checking the existence of an arbitrary pseudoperiod is computationally hard, as we show now. Consider the following decision problem:

PSEUDOPERIOD:

Instance: a string x of length n, and positive integers k and B. Question: Does there exist a set S = {p 1 , p 2 , . . . , p k } of cardinality k with

Theorem 40. PSEUDOPERIOD is NP-complete.

Proof: It is easy to see that PSEUDOPERIOD is in NP, as we can check an instance in polynomial time.

To see that PSEUDOPERIOD is NP-hard, we reduce from a classical NP-complete problem, namely, HITTING SET [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. It is defined as follows:

HITTING SET Instance: A list of sets S 1 , S 2 , . . . , S m over a universe U = {1, 2, . . . , n} and an integer k ′ . Question: Does there exist a set H = {h 1 , h 2 , . . . , h k ′ } of cardinality k ′ such that S i ∩ H ̸ = ∅ for all i?

Joseph Meleshko et al.

Given an instance of HITTING SET S 1 , S 2 , . . . , S m and U = {1, 2, . . . , n}, and integer k ′ , define a ℓ,i = 1 if ℓ ∈ S i and a ℓ,i = 0 otherwise. We construct a PSEUDOPERIOD instance with k = k ′ + 4, B = 4n + 5, and a string x, as follows:

We first show that if the PSEUDOPERIOD instance has a solution, then we can extract a solution for the HITTING SET instance. To do so, we examine what a valid pseudoperiod would look like for x by first considering each 1 symbol.

The first 1 symbol, u[1] = x[1] = 1, is followed by 10 4n+3 and since the p j forming the pseudoperiod are bounded by B = 4n + 5, we require p 1 = 1 for the pseudoperiod property to be satisfied at x[1]. Similarly, the next 1 symbol u[2] = x[2] = 1 is followed by 0 4n+3 1, which requires that some p j equal 4n+4, in order to satisfy the pseudoperiod property. The v factor is analogous in that v[1] = 1 is followed by 010 4n+3 , which gives us that p 2 = 2 and v[3] = 1 has a 1 symbol 4n + 4 symbols afterward, so it also satisfies the pseudoperiod property. The w factor is such that w[1] = 1 is followed by 0010 4n+3 , which then forces p 3 = 3 with w[4] satisfied by having a 1 symbol 4n + 4 symbols afterward as previous.

We now consider the z i factors. For each z i , the 1 symbol at z i [1] satisfies the pseudoperiod property if and only if the pseudoperiod contains some p j such that pj 4 ∈ S i . Since the only possible indices that can be 1 within the B bound are the a ℓ,i , the pseudoperiod property is satisfied at z i [1] using some p j of the pseudoperiod if and only if z i [1 + p j ] = a p j 4 ,i = 1 which means pj 4 ∈ S i . Considering the remaining 1 symbols in z i , we see that each a j,i is followed by a 0 symbol and has a 1 symbol exactly 4n + 4 indices later in the (0011) n factor. Regardless of the assignment of a j,i the pseudoperiod property is satisfied. Each 1 symbol in the (0011) n factor has another 1 symbol either p 1 = 1, p 2 = 2, or p 3 = 3 indices later, as each 0011 is followed by one of: another 0011, 01 where the 1 symbol is z i+1 [1], or the end of the string if i = m in which case it satisfies the pseudoperiod property by default.

Finally, we observe that there are no more than two consecutive 1 symbols in x, so the pseudoperiod property is satisfied at every 0 symbol, as there is another 0 symbol either p 1 = 1, p 2 = 2, or p 3 = 3 indices later.

Taken together, a satisfying pseudoperiod for this instance is of the form {1, 2, 3, 4n + 4} ∪ P , where P is a set of cardinality k ′ that has the property for all S i , there exists p j ∈ P such that pj 4 ∈ S i . Therefore, if such a pseudoperiod exists, then we can derive a solution H = { p 4 | p ∈ P } for the HITTING SET instance from the solution to the generated PSEUDOPERIOD instance.

Conversely, if the HITTING SET instance has a solution H then

Pseudoperiodic Words and a Question of Shevelev 23 is a valid pseudoperiod for x. All of the 0 symbols and most of the 1 symbols are satisfied by the p 1 = 1, p 2 = 2, p 3 = 3, or p k = 4n + 4 as previously explained. We only need to check that the z i [1] = 1 also satisfy the desired property. There exists some h i ∈ S i ∩ H, since H is a hitting set, which means that a hi,i = 1. This gives us that z i [1 + h i • 4] = a hi,i = 1 and 4 • h i ∈ P , which means each z i [1] also satisfies the pseudoperiod property and P is a pseudoperiod for this instance. Therefore, PSEUDOPERIOD is NP-Hard. This completes the proof.

About Vladimir Shevelev

Here we present some details about Vladimir Shevelev's life and contributions, based on Shevelev (2022).

Vladimir Samuil Shevelev was born on March 9 1945 in Novocherkassk, Russia, under the name Vladimir Abramovich. He received his Ph.D. in mathematics in 1971 from the Rostov-on-Don State University in the USSR. In 1992 he received a D.Sc. in combinatorics from the Glushkov Cybernetic Institute, Academy of Ukraine, Kiev.

From 1971 to 1974 he was Assistant Professor at the Department of Mathematics, Rostov State University. From 1974 to 1999 he taught at the Department of Mathematics, Rostov State Building University. In 1982 he took the surname "Shevelev" and in 1999 he emigrated to Israel, where he taught at the Ben-Gurion University of the Negev and did research at the Tel Aviv University.

From 1969 to 2016, Vladimir Shevelev published approximately 60 mathematical papers in refereed journals. He also published approximately 40 preprints on the arXiv. He was an excellent chess player, played the violin, and was a member of a Russian vocal group. He was married and had three children and six grandchildren. He died on May 3 2018 in Beersheba, Israel.

May his memory be a blessing.

Photograph taken from https://www.math.bgu.ac.il/ ˜shevelev/Hobbies.pdf.

Appendix A The automaton triple

In this section we provide the Walnut code for the automaton triple.

2 0 0 0 0 -> 8 1 0 0 -> 9 0 0 1 -> 10 1 0 1 -> 11 1 1 1 -> 12 3 0 0 0 0 -> 3 0 0 1 -> 13 0 1 1 -> 14 1 1 1 -> 3 4 0 0 0 0 -> 15 1 0 0 -> 16 0 1 0 -> 17