The Lyapin's Notebook — Problem 8

Definitions and mathematical statement

Let $u$ be a finite word, let $X$ be the set of letters occurring in $u$, and put $c(u)=|X|$. The source asks for the minimum alphabet size permitting an infinite word that avoids every substitution image of $u$.

The following makes this precise under a conditional interpretation: substitutions are non-erasing, occurrences are contiguous factors, and infinite words are indexed by the nonnegative integers. These conventions are not specified explicitly in the supplied record. For a finite nonempty alphabet $A$, write $A^*$ for the finite words, including the empty word, and $A^+$ for the nonempty finite words. A non-erasing substitution is a monoid homomorphism $h:X^*\to A^*$ such that $h(x)\in A^+$ for every $x\in X$. For an infinite word $w=(w_i)_{i\geq 0}$ over $A$, let $\operatorname{Fact}(w)$ be its set of finite contiguous factors, including the empty word. Say that $w$ avoids $u$ if \[ \forall h:X^*\to A^*\text{ non-erasing},\qquad h(u)\notin\operatorname{Fact}(w). \] Under these conventions, the requested quantity is \[ m(u)=\min\left\{|A|:\ A\text{ is a finite nonempty alphabet and there exists an infinite word over }A\text{ avoiding }u\right\}, \] whenever the set on the right is nonempty.

Problem (attributed to I. Melnichuk). For each non-blocking word $u$ containing $c(u)$ distinct letters, determine $m(u)$.

Unresolved qualification. The supplied record does not define "non-blocking," specify whether substitutions may erase letters, or explicitly specify the meaning of containment. Thus the displayed formalization is conditional on the stated conventions. In particular, the source's non-blocking hypothesis cannot yet be identified precisely with a condition ensuring that this minimum exists. The question does not explicitly assert that $m(u)$ depends only on $c(u)$.

Short English statement

For a word $u$, determine the smallest finite alphabet supporting an infinite word with no occurrence of any substitution image of $u$, assuming the source's non-blocking hypothesis. The precise meaning of that hypothesis and the substitution and occurrence conventions require clarification. The supplied source reports earlier estimates.

Sources

• Local UnsolvedMath registry, permanent ID $800008$, exact source problem code catalogue entry, title The Lyapin's Notebook --- Problem 8. The registry labels the problem open; this is a supplied status, not an independently verified mathematical assessment.
• Bershadsky, Kublanovsky, Mashevitzky, The Lyapin's Notebook: Unsolved Problems in Semigroup Theory (2026), Problem 8, https://arxiv.org/abs/2604.04763. The statement attributes the problem to I. Melnichuk; the registry's proposer field instead names Bershadsky, Kublanovsky, Mashevitzky and gives the year 2026.
• Supplied provenance: source accessed 2026-10-16; extraction method arxiv_latex. This access date is supplied provenance and does not indicate independent source verification for this draft.
• The source reports that some estimates were obtained in works labeled [Melnich1], [Melnich2], [McNulty], and [Baker]. The supplied record contains no bibliographic details or links resolving these four labels, and gives no statements of the estimates.