trureturing — Discovering truth

bibkey: floriandvorakova2016periodicity
authors: J. Florian, Ľ. Dvořáková
year: 2016
title: On periodicity of generalized pseudostandard words
doi: 10.37236/4771
url: https://arxiv.org/abs/1508.02020
claim: 'Conjecture 29 characterizes periodic d-ary generalized pseudostandard words by two conditions on their normalized directive tails.'
strata_touched:
  - D5/S1/Words/Palindromes/PseudopalindromicNormalization
  - D5/S1/Words/Palindromes/GeneralizedPseudostandardPeriodicity
license: citation-only
triage: anchor

Verified locator

DOI: https://doi.org/10.37236/4771

Source: https://arxiv.org/abs/1508.02020

Journal: Electronic Journal of Combinatorics 23(1), #P1.2.

Involutory antimorphisms and closure

ArXiv v1, page 3: “An involutory antimorphism is a map $\vartheta :{\mathcal{A}}^{\ast }\to {\mathcal{A}}^{\ast }$ such that for every $v,w\in {\mathcal{A}}^{\ast }$ we have $\vartheta (vw)=\vartheta (w)\vartheta (v)$ and moreover ${\vartheta }^2$ equals identity.”

“Consider an involutory antimorphism $\vartheta$ over $\mathcal{A}$. A finite word $w$ is a $\vartheta$-palindrome if $w=\vartheta (w)$. The $\vartheta$-palindromic closure $w^{\vartheta }$ of a word $w$ is the shortest $\vartheta$-palindrome having $w$ as prefix.”

Finite words are List α. InvAntimorphism records the two laws, the palindrome condition is θ.toFun w = w (Mathlib’s Function.IsFixedPt θ.toFun w), and IsClosure θ w z says that z has prefix w, is a θ-palindrome, and has length at most every other such extension. The closure bound is $|w|\le |z|\le 2|w|$; the lower inequality need not be strict.

Generation and normalization

ArXiv v1, page 4, Definition 1: “Let $\mathcal{A}$ be an alphabet and $G$ be the set of all involutory antimorphisms on ${\mathcal{A}}^{\ast }$. Let $\Delta ={\delta }_1{\delta }_2\dots$ and $\Theta ={\vartheta }_1{\vartheta }_2\dots$, where ${\delta }_i\in \mathcal{A}$ and ${\vartheta }_i\in G$ for all $i\in \mathbb{N}$. The infinite generalized pseudostandard word $\mathbf{u}(\Delta ,\Theta )$ generated by the generalized pseudopalindromic closure is the word whose prefixes $w_n$ are obtained from the recurrence relation $w_{n+1}=(w_n{\delta }_{n+1}{)}^{{\vartheta }_{n+1}},w_0=\epsilon .$ The sequence $\Lambda =(\Delta ,\Theta )$ is called the directive bi-sequence of the word $\mathbf{u}(\Delta ,\Theta )$.”

Page 4, Definition 2: “A directive bi-sequence $\Lambda =(\Delta ,\Theta )$ of a binary generalized pseudostandard word $\mathbf{u}(\Delta ,\Theta )$ is called normalized if the sequence of prefixes $(w_n{)}_{n\ge 0}$ of $\mathbf{u}(\Delta ,\Theta )$ contains all palindromic and $E$-palindromic prefixes of $\mathbf{u}(\Delta ,\Theta )$.” Page 5, Section 3.3: “A normalized directive bi-sequence can be defined similarly as in Definition 2 over multiliteral alphabet.”

Infinite words are ℕ → α. Their length-m prefixes are the literal expression List.ofFn (fun i : Fin m => u i). Generates states the recursion and that each stage is such a prefix. IsNormalized requires every prefix fixed by some involutory antimorphism to occur as a stage. The directive indices start at one; the entries at zero do not participate in closure steps.

Conjecture 29

ArXiv v1, pages 20–21, Section 6:

Consider an alphabet $\mathcal{A}$ with $\#\mathcal{A}=d$ and $G$ the set of all involutory antimorphisms on ${\mathcal{A}}^{\ast }$. Let $\mathbf{u}(\Delta ,\Theta )$ be a $d$-ary generalized pseudostandard word, where $\Delta$ is a sequence of letters from $\mathcal{A}$ and $\Theta$ is a sequence of antimorphisms from $G$. Then $\mathbf{u}$ is periodic if and only if the following conditions are met:

1. The normalized directive bi-sequence is of the form $(\tilde{\Delta },\tilde{\Theta })=(v{\delta }_1{\delta }_2{\delta }_3\dots ,\sigma {\vartheta }_1{\vartheta }_2{\vartheta }_3\dots )$, where $|v|=|\sigma |$ and ${\vartheta }_i({\delta }_{i+1})={\vartheta }_j({\delta }_{j+1})$ for all $i,j\in \mathbb{N}$.
2. For all $i\in \mathbb{N}$, if $w$ is a ${\vartheta }_i$-palindrome, then ${\vartheta }_{i+1}(w)$ is a ${\vartheta }_{i+2}$-palindrome.

The alphabet is arbitrary and finite. The $d$-ary requirement is Function.Surjective u; periodicity is ∃ p, 0 < p ∧ Function.Periodic u p. The finite prefix length is k, and the two tail conditions quantify over i,j ≥ 1. Letter images are one-letter words. The claim also asserts existence of a normalized directive generating the same infinite word. It does not assert a computable normalization algorithm or a formula for the least period.

Mathematical scope

The arbitrary-alphabet argument uses earliest insertion for normalization, nonincreasing positive gaps and a constant product of adjacent letter permutations for sufficiency, and global reflection of periodic prefixes for necessity. The least-period identity $p=g\mathrm{ord}(\rho )$ remains open here.

The finite experiment entry is docs/reports/florian-dvorakova-2016-generalized-pseudostandard-periodicity/check.py in the-omega-institute/trureturing-experiments, commit 4cb84370f8da7ba85f147f92e55b423c9feff76e, SHA-256 8372d38f2d12809dc76457fd2b6af9bdc4887ea608528e912f4c5732d5d84f28. Finite screens do not prove the conjecture.

The bounded literature screen does not establish exhaustive novelty. Florian’s ČVUT thesis remains ASSUMED-UNVERIFIED because the recorded Firecrawl request returned HTTP 402.