# Existence of an infinite word with a predetermined asymptotic for the word complexity

Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$

Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of $N_w(k)$ .
The function $n_w$ is the word complexity of $w$. Note that $1 \le n_w(k) \le 2^k$.

Question: Is there a word $w$ with $n_w(k) \sim p_k$ the k-th prime number?
If so, is there a word $w$ with $n_w(k) = p_k$?

Remark: more than an existence proof, a natural example with this property could be interesting. More generally, we can ask what are all the possible asymptotics for such a word complexity.

Let the finite binary word $w = 10000100101$, then:

• $N_w(1) = \{0 , 1 \}$
• $N_w(2) = \{00 , 01, 10\}$
• $N_w(3) = \{000 , 001, 010, 100, 101 \}$
• $N_w(4) = \{0000 , 0001, 0010, 0100, 0101, 1000, 1001 \}$

It follows that $n_w(k) = 2,3,5,7$ for $k = 1,2,3,4$.

• The condition $n_w(k)=p_k$ cannot be satisfied for all $k$, otherwise we would have $p_{k+1}-p_k\leq 2(p_k-p_{k-1})$. Commented Oct 22, 2015 at 20:16

I have already mentioned in a comment that the condition $N_w(k)=p_k$ cannot be satisfied for all $k$, otherwise we would have $p_{k+1}−p_k\leq 2(p_k−p_{k−1})$ which is not the case (should I explain the necessity of this condition?). Moreover, it should be at least true that there are infinitely many $k$ violating this inequality.

On the other hand, the required growth rate is possible.

Let us start with a general construction. Assume that $a_1,a_2,\dots$ is an increasing sequence such that the sequence $d_i=a_{i+1}-a_i$ is also strictly increasing. Let $w$ be the word where ones are placed exactly on the positions numbered by the $a_i$.

Take any $n$; find the largest $k$ with $d_k<n-1$. Then each of the first $a_k$ subwords of length $n$ contains at least two ones and hence its position in $w$ is uniquely determined by the gap between these ones. All the next $n$-subwords contain at most one 1, and there are $n+1$ of them. Thus $N_w(n)=a_k+n+1$. Notice here that if the monotonicity arises only eventually, this changes $N_w(n)$ by at most a constant, thus it does not affect its grpwth rate.

Now we need to specify this construction in order to get $N_w(n)\sim n\ln n$. Set $a_k=[e^{\sqrt{2k}}]$; Then the sequences $(a_k)$ and $(d_k)$ are eventually monotone, and $d_{k+1}/d_k\to 1$ as $k\to \infty$. Next, $$d_k=a_{k+1}-a_k\sim e^{\sqrt{2k}}(e^{\sqrt{2(k+1)}-\sqrt{2k}}-1) \sim \frac{e^{\sqrt{2k}}}{\sqrt{2k}}\sim \frac{a_k}{\sqrt{2k}}.$$ Thus $$N_w(d_k+2)=a_k+d_k+3\sim a_k\sim d_k\sqrt{2k}\sim d_k\ln d_k;$$ due to the monotonicity of $N_w$ and the fact that $d_{k+1}/d_k\to 1$, we obtain $N_w(n)\sim n\ln n$, as required.

REMARKS. How to find this strange form of $a_k$? Setting $a_k=e^{f(k)}$, we obtain that we need $f(k)(e^{f(k+1)-f(k)}-1)\sim 1$. Replacing $f(k+1)-f(k)$ by $f'(k)$, we get $e^{f'}-1=1/f$, or $f'=\ln(1+1/f)\sim 1/f$. Thus $f(k)\sim \sqrt{2k}$.

We have used the properties that $d_k$ increases, that $d_k=o(a_k)$ (in the last estimate), and that $d_{k+1}/d_k\to 1$. This shows the conditions within which this method works.

Your function $$n_w$$ is usually called the word complexity function. There are several works on these possible asymptotics, though the question seems quite difficult and surprisingly little is known.

Ferenczi has a survey "Complexity of sequences and dynamical systems" which gives a large list of necessary/sufficient conditions on functions to be a word complexity function. Some highlights are:

• Necessary conditions: $$n_w$$ is nondecreasing, if $$n_w$$ is not strictly increasing it is bounded, $$n_w$$ is subadditive (i.e. $$n_w(j+k) \leq n_w(j) n_w(k)$$)

• Sufficient conditions: one can achieve any function $$an+b$$ for $$a, b \in \mathbb{N}$$ for sufficiently large $$n$$, one can achieve (asymptotically) any polynomial $$n^{\alpha}$$, and one can achieve (asymptotically) any $$\phi: \mathbb{R}^+ \rightarrow \mathbb{R}^+$$ which is increasing, unbounded, has second derivative in $$[0,1]$$, and has first derivative approaching $$\infty$$.

In particular, this last result implies that it's possible to get $$n_w \sim k \log k$$ (in fact the relevant theorem says you can even do this for a sequence which has the property of uniform recurrence, meaning that every subword of $$w$$ appears with bounded gaps within $$w$$).