# P3068: Minimum avoiding alphabet for every avoidable word

- ID: `P3068`
- Reference: `avoidable-word-minimum-alphabet`
- Page: https://theoremdb.org/statements/P3068
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(u\) be a finite word using \(c(u)\) distinct variables. Define \(m(u)\) as the least alphabet size admitting an infinite word with no contiguous factor equal to \(\phi(u)\) for any nonerasing morphism \(\phi\). Determine \(m(u)\) for every avoidable word \(u\).

### Context

Known frontier: General estimates and values for special pattern classes are known.

Open boundary: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

### Problem setup

- **Definition (avoidable word).** A pattern u is avoidable when such an infinite word exists over some finite alphabet.
- **Definition (nonerasing morphism).** A morphism from pattern variables to nonempty finite words, extended to a pattern by concatenation.
- **Remark.** This is Problem 2.5 in the 2026 Lyapin Notebook; the public formulation fixes the input and equivalence conventions needed for independent review.

### What counts as a solution

- Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: General estimates and values for special pattern classes are known.

The exact unresolved remainder is: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

A complete resolution must meet the following acceptance conditions:
- Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: "Lyapin notebook" "Problem 2.5"; "Minimum avoiding alphabet for every avoidable word"; site:arxiv.org semigroup "avoidable word" open problem
- Strongest checked neighboring result: General estimates and values for special pattern classes are known.
- Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

### Other known results

- **Claim 2** (supported): General estimates and values for special pattern classes are known. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `avoidable-word-minimum-alphabet`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Bershadsky, S., Kublanovsky, S., and Mashevitzky, G., “The Lyapin's notebook: a collection of unsolved problems in Semigroup Theory”. arXiv (2026). DOI 10.48550/arXiv.2604.04763. Problem 2.5 and its immediately following status paragraph https://doi.org/10.48550/arXiv.2604.04763
   - Also cited at S. Bershadsky, S. Kublanovsky, and G. Mashevitzky, “The Lyapin’s notebook: a collection of unsolved problems in Semigroup Theory,” arXiv:2604.04763 (2026). Problem 2.5 and its immediately following status paragraph
   - preprint; primary source; arXiv:2604.04763, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2604.04763
   - Source use: original_summary
   - States the numbered open problem, identifies its proposer, and summarizes known special cases.
   - Source used to assess the problem's recorded status.
   - For Minimum avoiding alphabet for every avoidable word: This is the dated publication status for the canonical target Minimum avoiding alphabet for every avoidable word.
   - Source named by the research packet.
2. <a id="reference-2"></a>Kirby A. Baker, George F. McNulty, and Walter Taylor, “Growth problems for avoidable words”. Theoretical Computer Science 69(3) (1989), 319-345. DOI 10.1016/0304-3975(89)90071-6. Bounds for avoidable patterns https://doi.org/10.1016/0304-3975(89)90071-6
   - journal_article; secondary source; checked 2026-08-01
   - Source use: original_summary
   - Provides established estimates and foundational definitions for the exact alphabet-size problem.
   - Source used to assess the problem's recorded status.
   - For Minimum avoiding alphabet for every avoidable word: Provides established estimates and foundational definitions for the exact alphabet-size problem.