5
$\begingroup$

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

$\endgroup$
1
  • 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$ Commented Oct 22, 2015 at 20:16

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

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

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