Long Twin Subsequences in Ternary Words

Definitions and mathematical statement

Let $A$ be an alphabet of cardinality $k\geq 2$, and let $w=(w_1,\ldots,w_n)\in A^n$. A subsequence of $w$ is a word $(w_{i_1},\ldots,w_{i_\ell})$ with $1\leq i_1<\cdots<i_\ell\leq n$; its positions need not be consecutive. Two subsequences are twins if they are identical as words and their sets of positions are disjoint. Thus a pair of twins of length $\ell$ consists of indices \[ 1\leq i_1<\cdots<i_\ell\leq n,\qquad 1\leq j_1<\cdots<j_\ell\leq n, \] with $\{i_1,\ldots,i_\ell\}\cap\{j_1,\ldots,j_\ell\}=\varnothing$ and $w_{i_r}=w_{j_r}$ for every $1\leq r\leq\ell$. Define $t(w)$ to be the maximum such $\ell$, allowing $\ell=0$, and define \[ t(n,k)=\min_{w\in A^n}t(w). \] The length counts the symbols in each twin separately, so $0\leq t(w)\leq\lfloor n/2\rfloor$.

Fix $|A|=3$, and let $W_3(n)$ be uniformly distributed on $A^n$. The supplied problem asks both of the following questions as $n\to\infty$:

1. Is it true that, for every $\varepsilon>0$, \[ \lim_{n\to\infty}\mathbb{P}\!\left(t(W_3(n))\geq\left(\frac12-\varepsilon\right)n\right)=1? \] This expresses the supplied asymptotically almost sure assertion $t(W_3(n))=n/2-o(n)$.
2. Is it true that \[ \lim_{n\to\infty}\frac{t(n,3)}{n}=\frac12? \] Equivalently, for every $\varepsilon>0$ there exists $N\in{\mathbb{N}}$ such that, for every integer $n\geq N$ and every $w\in A^n$, \[ t(w)\geq\left(\frac12-\varepsilon\right)n. \]

The extracted original uses the term "subwords" and contains corrupted notation. The subsequence interpretation and the uniform random model above follow the supplied clean statement; the original extraction alone does not fully specify the random model. These are questions, with the open status supplied by the record rather than independently verified here.

Short English statement

Must every sufficiently long ternary word contain two identical subsequences, using disjoint positions, each of length $n/2-o(n)$? Does the same conclusion hold with probability tending to one for a uniformly random ternary word? Length refers to each of the two subsequences. Both assertions are posed as questions requiring mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005121$, title "Long Twin Subsequences in Ternary Words," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection.
• Supplied report citation: Combinatorics, Probability and Computing (2023), Oberwolfach Reports, pp. 1165--1237, DOI 10.4171/owr/2022/22. https://doi.org/10.4171/owr/2022/22. The extracted original attributes the question to Andrzej Ruciński; the registry's proposed year is 2022. The supplied report designation and year are retained without bibliographic reconciliation.
• Supplied literature reference: Axenovich, Person, and Puzynina, "twins in words." https://doi.org/10.1016/j.jcta.2013.01.001.
• Supplied literature reference: Dudek, Grytczuk, and Rucinski, "long twins in random words." https://arxiv.org/abs/2112.14197.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that known deterministic and random lower bounds for ternary words are strictly below $n/2$, while the asserted $n/2-o(n)$ behavior has not been proved. This is supplied dated curation, not an independently verified literature assessment; the record requests independent verification of time-sensitive status and cited claims.
• The supplied registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly when preparing its clean statement. This is a source-provided verification claim; no independent source consultation is asserted in this draft.