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$.

| cite | improve this question | | | | |
  • 5
    $\begingroup$ 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})$. $\endgroup$ – Ilya Bogdanov Oct 22 '15 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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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