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
    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
    Jan 8, 2015 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.