# Verification report — OWR-4425-012 (Shallit: can patterns characterise fractional powers?)

Verification date: 2026-10-20.

**Verdict.** The note answers the question in the universal reading and gives a near-complete answer for fixed
alphabets; every statement it makes is proved, part of it by exact finite computation, and the scope is as follows.
- **Universal reading (one pattern set for words over every finite alphabet, as in the source's overlap example).**
  Negative answer for every non-integer α > 1 (Theorem 1.2). The argument is elementary and may be folklore or
  coincide with the ideas of Currie and Cassaigne mentioned in the source (no write-up found); no priority is claimed.
- **Fixed alphabet of s letters (the pattern set may depend on the alphabet).** s = 1: a set exists for every α.
  s = 2: a set exists if and only if α < 2 (complete). s ≥ 3: a set exists if and only if α ≤ 1 + 1/s, for every
  non-integer α > 1 outside the window 2 − 2^−16 < α < 2 (Theorem 1.3).
- **Open.** For s ≥ 3 and 2 − 2^−16 < α < 2. Remark 6.2 reduces the closing of this window, for the certificates
  used, to an unproved statement about factors of words derived from the Thue–Morse word.
- **Computer-assisted, finite.** Lemmas 5.2, 5.3, 5.4, one small binary certificate, and the 29 ternary certificates
  of Proposition 6.1(b) (covering 5/3 < α ≤ 2 − 2^−16) are exact integer computations. Each is reproduced by at
  least four independent programs. All infinite families are proved in the text.

The note is unrefereed. It should not be described as a plain solution of the problem: the fixed-alphabet case for
s ≥ 3 is partial.

## Statement checked
- **Primary source.** J. Shallit, "On patterns and pattern avoidance", extended abstract in Mini-Workshop:
  Combinatorics on Words, Oberwolfach Reports 7 (2010), no. 3, Report No. 37/2010, pp. 2195–2244,
  doi:10.4171/OWR/2010/37 (Crossref: issue published 2011-03-02; organisers Berthé, Karhumäki, Nowotka, Shallit).
  Shallit's abstract runs pp. 2230–2236 (Problems 38–47 and its reference list; the next abstract, by Stoll, starts
  on p. 2237). Read in full in the publisher's open PDF (50 pages).
  - p. 2230: alphabet = non-empty finite set; pattern = non-empty word over a pattern alphabet Δ; a word w over Σ
    matches p if w = h(p) for a nonerasing morphism h: Δ* → Σ* (the general definition of a morphism just before it
    has its arrow reversed, a misprint without consequence).
  - p. 2231: the overlap example (a word has an overlap factor iff some factor matches xxx or xyxyx); exact p/q-powers
    for integers p > q ≥ 1 (x = y^e y′, e ≥ 1, y′ a prefix of y, |x| = p, |y| = q); "x has an occurrence of an
    α-power" if some factor is an exact p/q-power with p/q ≥ α; Problem 38 (paraphrased: for non-integer real α > 1,
    does some set P of patterns, finite or infinite, detect exactly the words with an occurrence of an α-power, in
    the sense that some factor matches a pattern of P?); the Remark after it (Currie and Cassaigne proposed ways to
    show impossibility, for restricted ranges of α; more work is needed for all α > 1).
  - p. 2232: Problem 39 mentions counting the 1s between consecutive 0s of the Thue–Morse word, the construction
    used in Sections 5 and 6 of the note.
- **Corpus record.** OWR-4425-012 (ulamai/UnsolvedMath), status "open"; the record does not fix the alphabet of x.
  The paper paraphrases Problem 38 faithfully (Problem 1.1).

## Readings
The source does not say whether P may depend on the alphabet. The note treats both readings:
- (U) one set P for all words over every finite alphabet — the literal reading, and the one of the overlap example;
- (F_s) an alphabet of s letters fixed in advance, P depending on it.
A positive answer in (U) gives one in every (F_s); a negative answer in some (F_s) gives one in (U). The note states
both clues: the Remark's hope to cover all α > 1 can come true only in (U), since for a fixed alphabet of s letters a
set exists for α ≤ 1 + 1/s; the phrase "for some restricted ranges of α" fits (F_s) better, since in (U) the negative
answer is a short argument valid for all α. The reader can judge which reading the proposer meant.

## Results in the paper
- Lemma 2.1: x has an occurrence of an α-power iff ce(x) ≥ α. Lemma 2.2 (closure criterion): over Σ a set P exists
  iff {x : ce(x) ≥ α} is closed under nonerasing endomorphisms of Σ*. Corollary 2.3: one pair (x, σ) with
  ce(x) ≥ α > ce(σ(x)) rules out α over Σ, over every larger alphabet and in reading (U).
- Proposition 3.1 and Theorem 1.2: x = (a_1⋯a_q)^k a_1⋯a_r, σ(a_q) = a_q⋯a_N gives ce(x) = k + r/q and
  ce(σ(x)) = k + r/N; with suitable q, r, N every non-integer α > 1 is ruled out in reading (U). The number of letters
  N exceeds 1/(α − ⌊α⌋).
- Proposition 4.1: positive cases (s = 1; α ≤ 1 + 1/s with P = {xx, xyx}; s = 2 and 3/2 < α < 2 with P = {xx}).
- Lemma 4.2: Thue–Morse desubstitution (proved in the note; standard).
- Propositions 4.3 (binary, (k, k + 1/2]), 4.4 (three letters, (k, k+1), k ≥ 2; computer-free), 4.5 (s letters,
  (1 + 1/s, 1 + (s−2)/(s−1)] for s ≥ 4, (4/3, 3/2] for s = 3).
- Section 5 (binary, α > 2): gap words of μ^n(0) and μ^n(001); Lemma 5.1 (proved: no square uu in E^Z with N ∤ |u|);
  Lemmas 5.2, 5.3, 5.4 (finite, by computation); Lemma 5.5 (proved from 5.1–5.3); Proposition 5.6 (binary: no set for
  every non-integer α > 2), with the extra certificate x = 00100100, σ(1) = 101101 for (9/4, 8/3].
- Section 6 (s ≥ 3, α < 2): Proposition 6.1 (a) two explicit certificates for (4/3, 7/4]; (b) 29 certificates
  (x_N, σ0) with ce(x_N) = 2 − 1/N_i (proved) and ce(σ0(x_N)) = 2 − 1/N_{i−1} (computed), covering (5/3, 2 − 2^−16].
  Proof of Theorem 1.3. Remark 6.2 (the open window), Remark 6.3 (two further certificates, N = 98304 and 131072,
  which would shrink the window to (2 − 2^−17, 2); the statements keep 2 − 2^−16), Remark 6.4 (exhaustive
  classification for three letters up to 7/4, a cross-check not used in any proof).

## Computations (programs and outputs in reproducibility/)
- **`check_note.py`** (standard library only; written with the note; a third implementation of all finite checks).
  Default run about 1 s (TOTAL failures: 0); `--nmax 65536` 101 s (all 29 certificates; TOTAL failures: 0);
  `--nmax 131072 --only 14` 398 s (the two certificates of Remark 6.3; TOTAL failures: 0). It tests its critical-exponent
  routine against a direct loop and against the source's definition, and checks Propositions 3.1, 4.1, 4.3–4.5,
  Lemma 4.2 on examples, Lemmas 5.1–5.4, the constants of Lemma 5.5, the formulas and coverings of Proposition 5.6,
  Proposition 6.1 and the identities of Remark 6.2. Deliberately wrong inputs are detected.
- **First-version programs** (`original/`): `verify_constructions.py`, `binary_family.py` (Lemmas 5.2–5.4, 0.3 s),
  `ternary_chain.py` (29 certificates, 120 s with numpy), `finite_classify.py` (Remark 6.4).
- **Verification run A** (`verification_run_A/`, numpy): `check1.py`, `check2.py 192`, `check3.py 65536`
  (29 certificates, 79 s for the largest); all with 0 failures.
- **Verification run B** (`verification_run_B/`, C and Python): exact ce in C (`vb_ce.c`), the cyclic bound on M^Z in
  C (`vb_cyc.c`, no appeal to Fine–Wilf), tests T0–T8; the 29 certificates and the two of Remark 6.3 (221 s in all);
  all checks passed.
- **Last independent verification run** (`independent_run_2/`, standard library only, bit-parallel critical
  exponent): `t1`–`t5` recompute all finite statements and test the propositions (0 failures, 17 deliberate-error
  tests detected; the 29 certificates and the two of Remark 6.3 in 81 s); `package_rerun/` and `t6` re-run every
  program above from the archive of the previous version: all 20 recorded outputs reproduced up to timing.

## Independent verification runs
The results were first obtained, with written proofs and programs, in a first written version. Two independent
verification runs, both AI-assisted, examined it; each read the source in the publisher's open PDF, re-derived the
proofs line by line and wrote its own programs; neither read the other's report. Both found no mathematical error and
confirmed the results with corrections of wording and of details, all applied in the note:
- state both readings wherever the status is described, and never call the problem plainly solved; keep the window
  visible and the folklore caveat on Theorem 1.2 (both runs);
- add that the Remark's "restricted ranges of α" fits the fixed-alphabet reading (run A);
- Lemma 5.2 holds for all nine pairs (a, b), so its consequence does not need Lemma 5.1 (run A; checked by both);
- Lemma 5.4: explain why the finite computation suffices (Fine–Wilf; or the exact cyclic computation of run B) (A, B);
- Lemma 5.5, case without admissible t: the bound is L ≤ p + 22 (run B);
- page range pp. 2230–2236 of the source (run B); the description of the citation lists (run A).
In writing the note, Remark 6.2 was also corrected: the first version reduced the window to the absence of factors
u d u with N − 1 ≤ |u| ≤ 2N − 2 in θ(x_N); this is equivalent to ce(σ0(x_N)) < ce(x_N) (checked by run B for
N ≤ 256) but does not give the chaining of the intervals. The note states the condition that does.

## Last independent verification run (2026-10-20)
A further independent verification run, also AI-assisted, examined the text of the note itself, as if nothing had
been checked before. It downloaded the source again (the same file, by checksum) and read Shallit's abstract
(pp. 2230–2236) and the relevant sections of Berstel's survey; checked the bibliographic data of the report with
Crossref and every DOI of the bibliography with Crossref, DataCite or the arXiv API; re-derived every proof of the
note line by line (Lemma 2.2 in both directions, the passage of certificates to larger alphabets and to reading U,
Theorem 1.2, Proposition 4.1, Lemma 4.2, Propositions 4.3–4.5, Lemma 5.1, both cases of Lemma 5.5, the interval
chain of Proposition 5.6, Proposition 6.1, the assembly of Theorem 1.3, Remark 6.2); and wrote new programs
(`reproducibility/independent_run_2/`). With them it recomputed, in exact arithmetic: Lemma 5.2 for all nine pairs;
Lemma 5.3 (456 words, every p < 42, maximum exactly 8/3, attained only for p = 3); Lemma 5.4 for N ∈ {1, 2, 3, 4, 6}
and the same cyclic bound for every word of 𝓕 with N ≤ 3072; Lemma 5.1 for N ≤ 6144; the certificate for
(9/4, 8/3]; the formulas after Proposition 5.6 for N ≤ 24, k = 2, 3, 4; both certificates of Proposition 6.1(a); all
29 certificates of Proposition 6.1(b) and the two of Remark 6.3; the identities of Remark 6.2; the interval unions
and the assembly of Theorem 1.3(c) for 3 ≤ s ≤ 40; Sections 3 and 4 on many parameters (Theorem 1.2 for 40 values of
α, up to 10,001 letters); and the counts of Remark 6.4 (533 words, longest 38). Its critical-exponent routine was
compared with the definition on 1,517 words and on 16,263 (word, α) pairs; 17 deliberately corrupted inputs were all
detected. It re-ran every program of the package from the archive of the previous version: all 20 recorded outputs
were reproduced up to timing. It repeated part of the literature search (below).

It found no error in a theorem, proposition or lemma, and required the following corrections, all made in the note:
- proof of Proposition 4.1(b): the sentence "a factor matching xx or xyx begins and ends with the same letter" is
  false (abab = h(xx)); it now says that such a factor contains the first letter of h(x) twice, which is what the
  argument uses;
- Section 1.1: besides the remark that "restricted ranges of α" fits the fixed-alphabet reading, the note now says
  that the hope to cover all α > 1 can come true only in reading (U), since over a fixed alphabet of s letters a set
  exists for α ≤ 1 + 1/s;
- abstract and Zenodo description: the ideas of Currie and Cassaigne are no longer called unpublished (the source
  only reports that they suggested ways; no write-up was found); "decided by exact integer computation, each
  reproduced by several independent programs";
- the caveat on Theorem 1.2 (elementary, possibly folklore, no priority claimed) is repeated after its proof;
- the description of the verification runs, of the computations and of the searches was completed; in the proof of
  Lemma 5.1 the length of the window is now called ℓ (it was P, the name of the pattern set).

## Relation to the literature, novelty and scope
- **Searches (19–20 October 2026).** arXiv, zbMATH, Crossref, OpenAlex and Semantic Scholar (patterns and fractional
  powers; Shallit and patterns; nonerasing morphisms and powers; Currie, Cassaigne and patterns; critical exponent and
  closure under morphisms), the citing works of the report in OpenAlex and Semantic Scholar, and eight web searches;
  the last verification run repeated part of them on 20 October 2026 (arXiv, Crossref, OpenAlex, zbMATH, one web
  search). Some arXiv, OpenAlex and Semantic Scholar requests were refused with HTTP 429 (or 503) and were repeated
  at most once.
  - Citing works: Semantic Scholar lists Fleischmann–Lejeune–Manea–Nowotka–Rigo (DLT 2020, arXiv:2001.11218) and
    Rigo–Stipulanti–Whiteland (DLT 2022; extended version arXiv:2201.04603); OpenAlex lists the first and a 2026
    Zenodo preprint on an antimorphic Fine–Wilf theorem. None concerns Problem 38.
  - Other works found concern avoidance, not characterisation: Currie–Mol (TCS 866, 2021), Rowland–Shallit (Discrete
    Math. 312, 2012), Pudwell–Rowland (EJC 25(2), 2018, P2.27), Shallit (CPM 2022 invited talk), Loftus–Shallit–Wang
    (DLT 1999).
  - No printed answer to Problem 38 and no write-up of the Currie–Cassaigne arguments were found. A search that finds
    nothing is not a proof of novelty.
- **Classical tools, with sources.** Overlap-freeness of the Thue–Morse word (Thue 1906) and the square-free ternary
  word obtained from it by gap words (Thue 1912), attributed following Berstel's survey "Wörter ohne Wiederholungen"
  (Thue's papers were not read); the desubstitution lemma, proved in the note (standard; Allouche–Shallit 2003,
  Lothaire 1997, not consulted); Fine and Wilf (1965); Dejean (1972) for Remark 6.4 only; Walnut (Mousavi 2016;
  Shallit 2022) only as a possible route to close the window. All DOIs were checked with Crossref (DataCite for the
  LIPIcs and Zenodo DOIs).
- **Scope.** Reading (U): answered (negative, all non-integer α > 1). Fixed alphabets: s ≤ 2 complete; s ≥ 3 partial,
  open exactly for 2 − 2^−16 < α < 2. No priority is claimed for Theorem 1.2.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/