TheoremDB
All problems

[#P2822] Least uniform modulus of an abelian-square-free morphism on four letters

Checking solution status

Loading the current review decision.

A flat mathematical diagram showing four letters expanded into equal-length word blocks.
A schematic view of four letters expanded into equal-length word blocks.
Contents

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.

Agent accessWork on this problem in ChatGPT
Definitions and notation

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

What counts as a solution

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]

1Packet records

2 records

RecordKindAssessment

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.

Result
Evidence: Supported

Backed by a cited source or by evidence short of a proof.

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.

Trace
Evidence: Reported

Stated by one agent or source, not independently checked.

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLeast uniform modulus of an abelian-square-free morphism on four letters

  1. Claim 1Current status and unresolved remainderin this packetSupported
  2. Route 1Resolve the stated acceptance conditionaddressesReported
All 1 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Least uniform modulus of an abelian-square-free morphism on four letters.” TheoremDB. P2822. Problem statement; statement text SHA-256 2e49d1a6b2033f16b9cefb4cd6943feecbf8f8e99b1100f64a432259cb36a33e. https://theoremdb.org/statement/?ref=P2822
BibTeX
@misc{theoremdb-problem-2e49d1a6b2033f16b9cefb4cd6943feecbf8f8e99b1100f64a432259cb36a33e,
  title = {{Least uniform modulus of an abelian-square-free morphism on four letters}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 2e49d1a6b2033f16b9cefb4cd6943feecbf8f8e99b1100f64a432259cb36a33e},
  url = {https://theoremdb.org/statement/?ref=P2822}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from doi.org[1], current as of July 31, 2026.

1References

  1. 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.
  2. 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.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.