ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For k∈Nk\in\mathbb{N}, let [k]={1,…,k}[k]=\{1,\ldots,k\} and let Sk(n)\mathcal{S}_k(n) be the set of words in [k]2n[k]^{2n} that can be partitioned into two disjoint, identical subwords. A word in Sk(n)\mathcal{S}_k(n) is a shuffle square, and nn is its semi-length. Since ∣Sk(n)∣|\mathcal{S}_k(n)| is supermultiplicative in nn, define

bk=lim⁡n→∞∣Sk(n)∣1/(2n).b_k=\lim_{n\to\infty}|\mathcal{S}_k(n)|^{1/(2n)}.

Large-alphabet shuffle-square growth conjecture. As a function of k∈Nk\in\mathbb{N},

lim⁡n→∞∣Sk(n)∣1/n=4k−2−o(1).\lim_{n\to\infty}|\mathcal{S}_k(n)|^{1/n}=4k-2-o(1).

The conjecture proposes that the known upper bound is essentially tight for large fixed alphabets. The binary case is solved by the paper's main theorem, while the corresponding behavior for larger alphabets remains open; in particular, the paper separately asks whether ∣S3(n)∣=(9−o(1))n|\mathcal{S}_3(n)|=(9-o(1))^n.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.