[#P2822] Least uniform modulus of an abelian-square-free morphism on four letters
Problem. Determine the least integer \(L\ge2\) for which there is a morphism \(h:\{0,1,2,3\}^*\to\{0,1,2,3\}^*\) such that \(|h(a)|=L\) for every letter \(a\), and \(h(w)\) is abelian-square-free whenever \(w\) is abelian-square-free.
1Context
The 85-uniform construction proves existence with a large structured certificate. Removing its symmetry restriction creates a finite sequence of reusable SAT instances, forbidden-factor lemmas, and verified morphism candidates.
2Problem setup
Definition 1 (A morphism satisfies \(h(uv)=h(u)h(v)\) and). A morphism satisfies \(h(uv)=h(u)h(v)\) and is determined by the four letter images.
Definition 2 (A word). A word is abelian-square-free when it has no factor \(uv\) with \(|u|=|v|>0\) and equal Parikh vectors.
Definition 3 (The common image length \(L\). The common image length \(L\) is called the uniform modulus.
Remark 1. The 85-uniform construction proves existence with a large structured certificate. Removing its symmetry restriction creates a finite sequence of reusable SAT instances, forbidden-factor lemmas, and verified morphism candidates.
3What counts as a solution
- Give an \(L\)-uniform morphism with a complete finite-test or direct proof that it preserves abelian-square-freeness, and prove that no such morphism exists for any smaller modulus.
- A negative certificate for a fixed modulus must cover unrestricted morphisms up to explicitly stated alphabet and reversal symmetries.
1Status
Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus. Give an \(L\)-uniform morphism with a complete finite-test or direct proof that it preserves abelian-square-freeness, and prove that no such morphism exists for any smaller modulus.[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-31. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus.
- 2026-07-27 prior-art search checked Keränen's 1992 construction, the 2009 powerful substitution, later abelian-square-free morphism searches, and claims of minimality. The located minimality statement applies to the cyclic-permutation template used by the 85-uniform morphism.
- The known construction gives \(L\le85\). A lower-bound search must range over all four image words, rather than assume that the images are letter permutations of one seed word.
- Finite-test criteria for power-free morphisms can turn a candidate into a bounded verification problem, but the exact test set and its proof must be recorded.
Recorded example 1. Keränen's construction supplies an admissible morphism at modulus 85, so the requested least value is at most 85.
How the 2 records connect
ProblemLeast uniform modulus of an abelian-square-free morphism on four letters
2See also
- Minimum avoiding alphabet for every avoidable wordcombinatorics on words
- Infinitely many ones in the greedy three-term-progression-free sequencecombinatorics on words
- Zero density in the easily bored sequencecombinatorics on words
How to cite
TheoremDB contributors, “Least uniform modulus of an abelian-square-free morphism on four letters,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/abelian-square-free-uniform-morphism-minimumThis page as plain text: abelian-square-free-uniform-morphism-minimum.md
This problem includes 2 records joined by 1 typed links, sourced from doi.org[1], current as of July 31, 2026.
1References
- Packet source. Veikko Keränen, “Abelian squares are avoidable on 4 letters”. Lecture Notes in Computer Science (1992), 41-52. DOI 10.1007/3-540-55719-9_62. Keränen's 85-uniform construction and its symmetry-restricted minimality motivate the unrestricted minimum; this CC0 record was written on 2026-07-27. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN as of 2026-07-27. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Least uniform modulus of an abelian-square-free morphism on four letters: UNKNOWN as of 2026-07-27. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus.Source named by the research packet.
- Veikko Keränen, “A powerful abelian square-free substitution over 4 letters”. Theoretical Computer Science 410(38-40) (2009), 3893-3900. DOI 10.1016/j.tcs.2009.05.027. Status evidence identified in the source record and checked at the linked publication. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN as of 2026-07-27. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus.Also cited at Full journal article relevant to Least uniform modulus of an abelian-square-free morphism on four letters.Source used to assess the problem's recorded status.For Least uniform modulus of an abelian-square-free morphism on four letters: UNKNOWN as of 2026-07-27. An 85-uniform abelian-square-free endomorphism is known and was shown minimal inside its cyclic-symmetry form; the checked sources do not identify the unrestricted least modulus.
Original CC0 exact-minimum formulation based on a sourced uniform morphism construction.