For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the word $w$. For example, for periodic sequences we have $f_w(n)=O(1)$, for Sturmian words $f_w(n)=n+1$, for the Thue-Morse word and, more generally, for automatic sequences we have $f_w(n)=\Theta(n)$, etc.

Let $p_k$ denote the $k$-th odd prime, and let $w=(w_1w_2...)$, where $w_k = (p_k-1)/2 \mod 2$. We have $w=(10110...)$. I am curious if any nontrivial bounds are known about the word complexity in this case. The Cramér model would suggest $f_w(n)=2^n$, of course.

UPDATE (Feb 9, 2015)
I started with Shiu's reference pointed out by Lucia, and found a sizable literature on sequences of primes mod $4$. Guy reports that special cases of the problem go back to Chebyshev. It seems likely that the question is open, but here are some relevant refs.

S. Knapowski and P. Turán, On prime numbers ≡1 resp. 3 mod 4 (1977).
I.Z. Ruzsa, Consecutive primes modulo 4 (2001).
R.K. Guy, Unsolved Problems in Number Theory, 2004, $\S$A4.
K. Monks, S. Peluse and L. Ye, Strings of special primes in arithmetic progressions (2013).

  • 6
    $\begingroup$ See this related MO question: mathoverflow.net/questions/168378/… . So far as I know, the only non-trivial result is Shiu's theorem which implies that arbitrarily long strings of $0$'s (or arbitrarily long strings of $1$'s) appear in this word. $\endgroup$ – Lucia Feb 8 '15 at 16:38
  • 3
    $\begingroup$ Just a comment :) Lengths of the shortest initial segments of $w$ which contain all words of length 1, 2, ..., 10 are, respectively, 2, 5, 45, 76, 377, 1394, 1464, 5834, 7574, 31797 $\endgroup$ – მამუკა ჯიბლაძე Feb 8 '15 at 17:01
  • 1
    $\begingroup$ Just a side remark: putting the $w_k$ corresponding to the primes less than $10^9$ into a file of 6355941 bytes, I observed that ZIP can compress this file to 6341358 bytes, i.e. by about 0.23 percent. BZIP2 fails at obtaining any compression. $\endgroup$ – Stefan Kohl Feb 9 '15 at 15:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.