Skip to main content
1 of 2
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Regarding the 3rd question, I will show this:

Theorem. For a random word of length $n$, the expected number of $h$th powers is $$ \sim \frac{n}{2^{h-1}-1}. $$ Proof. A basic event about occurrences of powers of a word in a binary word is $$ S_{i,j,h} = \{w\in \{0,1\}^n \mid \text{$w$ has an $h$th power of length $h\cdot i$ ending in position $j$}\} $$ $$ = \{w \mid w = av^hb, |av^h|=j, |v|=i\} $$ We let $p$ denote the probability of 1 as opposed to 0; namely $p=1/2$. We may assume $w$ has odd length $n = 2k-1$. Then $\mathbb P(S_{i,j,h}) = p^{(h-1)i}$, and the ranges for the variables are $$ h\cdot i\le j\le 2k-1 = n $$ Let $W_{n}$ be a uniformly distributed random word of length $n$, and let $s^{(c)}(w)$ be the number of $c$th powers in the word $w$. So $$ \mathbb E \sum_{j=hi}^{2k-1} \mathbf{1}_{S_{i,j,h}} = (2k-hi)p^{(h-1)i} $$ is the expected number of $h$th powers of length $i$, for $hi\le 2k-1$. Then $$ \mathbb E s^{(h)}(W_{2k-1}) = \sum_{i=1}^{\lfloor(2k-1)/h\rfloor}(2k-hi)p^{(h-1)i} $$ is the expected number of $h$th powers in a word of length $n=2k-1$. Let us take $n\rightarrow\infty$ and divide by $n$; we get $$ \sum_{i=1}^\infty p^{(h-1)i} = \frac{p^{h-1}}{1-p^{h-1}} = \frac1{2^{h-1}-1} $$

Corollary. The expected number of squares, cubes, and 4th powers is $\sim n$, $n/3$, $n/7$, respectively.

The total number of nontrivial powers (squares and higher) overall will be something like $$ n\cdot \sum_{h=2}^\infty \frac1{2^{h-1}-1} $$ which is a Lambert series with value $\approx 1.606695n$.

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114