2
$\begingroup$

Let $A$ be a finite set. Let $A^k$ be the set of words in the alphabet $A$ of length $k$ and $A^*$ be the set of infinite words. I was looking for an element $a = \lbrace a_n \rbrace_{n \in \mathbb{N}}$ of $A^*$ so that, $\exists k_0 \in \mathbb{N}$ so that $\forall k>k_0$, any finite subsequence (of length $k \cdot m$) of $a$ is different from the sequences obtained by repeating some word at least $k$ times.

In other words, I was looking for an infinite sequence so that all subwords are not element of the diagonal in $X^k$ where $X= A^n$ and $n$ runs over all integers, $k$ runs over all integers larger than some $k_0$.

There is an [I suppose] absurdly complicated way to answer this by looking at a geodesic ray in the Burnside groups (this requires $|A| \geq 4$ and gives a $k_0$ around 665/2). Curiosity pushes me to ask

$\mathbf{Question:}$ How to produce (elementarily) such a sequence?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ the proofs that free burnside groups are infinite use the existence of square-free or cube-free words. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 9, 2015 at 3:06

1 Answer 1

Reset to default
6
$\begingroup$

Square free words exist over all alphabet sizes greater than 2, and cube free words exist over all alphabet sizes greater than or equal to 2 (same article).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Also, for completeness-sake, there is no square-free word over an alphabet of size 2: suppose the alphabet is $\{a,b\}$ and WLOG that the first element of the sequence is $a$. Then the next must be $b$ (else $aa$ is a square), and the next after that must be again $a$ (else $bb$ is a square). But now there's no choice for the fourth element; $a$ will yield $a^2$, while $b$ will yield $(ab)^2$. $\endgroup$
    – Steven Stadnicki
    Commented Jan 8, 2015 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .