An alternating antimorphic Fine-Wilf theorem
ORCID: 0009-0001-9320-500X · DOI and Zenodo record · Zenodo version 1.0
Original verification ZIP · Open PDF · Download PDF · BibTeX
Original manuscript abstract
Let θ be an antimorphic involution of a free monoid. If a finite word w has alternating θ-periods p,q and |w| ≥ p+q−gcd(p,q), then gcd(p,q) is an alternating θ-period of w. This proves the unnumbered conjecture stated after Theorem 23 in Nowotka's contribution, joint with Bischoff, to Mini-Workshop: Combinatorics on Words (2010). The proof applies the classical Fine–Wilf theorem to the common reflected extension θ(w)w and recovers the alternating phase at its center. The length formula cannot be decreased by one uniformly.
Overview
An alternating period describes a word built by repeating a block, its reflected image, the block, its reflected image, and so on. The reflection may also swap letters. The theorem says that two such patterns sharing a sufficiently long finite prefix force a common alternating pattern whose block length is the greatest common divisor of the two lengths.
The threshold is the familiar Fine–Wilf expression p+q−gcd(p,q). The proof obtains it by reflecting the whole finite word once, applying the classical theorem for ordinary periods, and using the reflection center to recover the required alternating phase.
The exact theorem
Let A be an arbitrary alphabet and θ an antimorphic involution of its free monoid A*: θ(xy) = θ(y)θ(x), and θ2 is the identity. Fixed letters and swapped letters are both allowed; ordinary word reversal is included.
A positive integer p is an alternating θ-period of w if w is a prefix of (uθ(u))ω for a length-p word u. The symbol ω means infinite repetition. The block order is prescribed, and p need not be a minimal period.
If the finite word w has alternating θ-periods p and q, put d = gcd(p,q). If
|w| ≥ p + q − d,
then, for the length-d prefix v of w, w is a prefix of (vθ(v))ω. Thus d is an alternating θ-period, with the phase anchored at the beginning of w. No minimality of d is asserted.
The length hypothesis already implies |w| ≥ max(p,q). The theorem allows a final incomplete block and includes equal periods and divisibility cases. Arbitrary-order concatenations of u and θ(u) form a different model.
Why the reflected word works
Every antimorphic involution reverses a word and applies an involutive permutation σ to its letters. For one alternating period p, extending uθ(u) in both directions gives an ordinary 2p-periodic sequence with reflection identity s−1−i = σ(si).
Its restriction around the center is exactly W = θ(w)w. Applying the same argument to q gives ordinary periods 2p and 2q on this same finite word. The construction uses the observed w; it assumes no equality between two unseen infinite completions.
Writing L = |w|, the bound gives 2L ≥ 2p+2q−2d. Classical Fine–Wilf therefore gives W ordinary period 2d. Its central block is θ(v)v. Moving by multiples of 2d within the finite interval, on either side of that center, shows that the right-hand word w follows v, θ(v), v, θ(v), … exactly.
Why the formula cannot always be shortened
Take ordinary reversal, distinct letters a,b, and w = abb. It is a prefix of both (ab ba)ω and (abb bba)ω, so it has alternating periods 2 and 3. Its length is one below 2+3−gcd(2,3) = 4. Alternating period 1 would force the constant word aaa…, which does not begin abb.
This example rules out lowering the formula by one uniformly. It does not determine the best threshold separately for every pair of periods, alphabet, or involution.
The question and earlier work
The theorem proves the exact unnumbered conjecture following Theorem 23 on printed p. 2220 of Nowotka's contribution, joint with Bischoff, to the 2010 mini-workshop report, published in 2011. It is distinct from numbered Conjecture 27. Theorem 23 and Bischoff's thesis give the longer sufficient bound p+q.
The ordinary Fine–Wilf theorem and the reflection/doubled-period machinery are prior work. Bischoff's thesis develops the relevant reflection method. This note uses one common extension of the entire finite prefix to reach the shorter threshold.
Czeizler–Kari–Seki and Kari–Seki study related θ-primitive-root and more general block-power questions, with different hypotheses and conclusions. For p > q ≥ 2d, Kari–Seki's author manuscript has a piecewise bound: at q = 2d its stronger branch is 2p−⌊d/2⌋. The note's single sufficient comparison is valid but weaker at that endpoint.
For ordinary reversal at the common phase, Simpson's published palindromic-periodicity theorem directly requires 2p+2q−2d on w itself, twice the threshold here. A general letter-twisted reflection is not automatically an ordinary palindrome. These comparisons do not exclude every indirect reformulation of earlier work or certify first discovery.
Scope and review status
The theorem concerns the stated alternating-prefix definition for one arbitrary antimorphic involution. Its uniform obstruction is not a pairwise-optimality claim. The bounded literature assessment does not certify global novelty or present worldwide openness.
The verification supplement contains finite controls supporting the written proof and records the access and version gaps in the bounded source comparison.
AI tools were used extensively in solving, proof checking, literature research, drafting, computation, and adversarial agent reviews. This is an unrefereed research note. Automated reviews are not independent external human peer review.
Original files and rights
The downloads above preserve the original bytes and native ZIP-then-PDF order. Zenodo originals: alternating-antimorphic-verification.zip · alternating-antimorphic-fine-wilf.pdf.
The original research note and author-produced verification materials are licensed under CC BY 4.0. Cited third-party works retain their own rights.
Collaboration
Independent verification, substantive extensions, and development toward a journal submission would be welcome. Collaboration and authorship would reflect actual contributions.
Related literature
- N. J. Fine and H. S. Wilf: Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society 16(1) (1965), 109–114.
- D. Nowotka, joint with B. Bischoff: Word periods under involution. In Mini-Workshop: Combinatorics on Words, Oberwolfach Report 37/2010; contribution 2219–2222, published 2011.
- B. Bischoff: Wortbegrenzung unter Involution. Diplomarbeit 3095, Universität Stuttgart, 18 November 2010, Chapter 3.
- E. Czeizler, L. Kari and S. Seki: On a special class of primitive words. Theoretical Computer Science 411(3) (2010), 617–630; 2010 journal version.
- L. Kari and S. Seki: An improved bound for an extension of Fine and Wilf's theorem and its optimality. Fundamenta Informaticae 101(3) (2010), 215–236; comparison uses the dated author manuscript.
- J. Simpson: Palindromic periodicities. Australasian Journal of Combinatorics 92(3) (2025), 450–462.
Citation
Alec Kriebel. An alternating antimorphic Fine-Wilf theorem. Zenodo, version 1.0, 3 October 2026. doi:10.5281/zenodo.23130727.