KolakoskiFrequencies < CoWiki

CoWiki Web>ImportantOpenProblems>KolakoskiFrequencies (2014-02-13, JeffreyShallit) (raw view)

The Kolakoski word can be defined in a number of different ways, but probably the simplest is as the unique infinite word *k* over the alphabet {1, 2}, starting with 1, such that the sequence of lengths of blocks of consecutive identical symbols is equal to *k* itself.

The first few terms are 12211212212211211221211212211211212212211212212112. As you can see, the lengths of successive blocks are 1,2,2,1,1, etc., the sequence itself.

W. Kolakoski asked [Elementary Problem 5304, Amer. Math. Monthly *72* (1965), 674] for a formula for the <em>n</em>th term, and if the sequence is periodic. Recently, however, Jean Berstel and Srecko Brlek reported that the Kolakoski sequence actually appeared as early as 1939, in two papers of Oldenburger, cited below. Thus it should probably be called the Oldenburger-Kolakoski sequence.

A result of Shallit and Swart ["An efficient algorithm for computing the <em>i</em>'th letter of &phi;<sup>n</sup> (a)", Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp. 768-775] that shows that Kolakoski is a member of a general class of sequences (i. e., those generated by finite-state transducers) for which predicting the <em>n</em>'th term of the <em>i</em>'th iterate is provably hard (in a computational complexity sense). Unfortunately this proves nothing about the particular case of the Kolakoski sequence.

A more interesting question is if the symbols "1" and "2" occur with limiting frequency 1/2. This problem is still open. The best result is that if the frequency exists, then the frequency is between .499 and .501, and is due to Chvátal in a technical report.

If, instead of 1's and 2's, we use 1's and 3's, then the resulting sequence is morphic.

The image shows a discussion of the problem at an Oberwolfach meeting, December 16 1988.

References:

A. Carpi. Repetitions in the Kolakovski [sic] sequence. _Bull. European Assoc. Theor. Comput. Sci._ (50) (1993), 194-196.

A. Carpi. On repeated factors in C<sup>&infin;</sup>-words. _Inform. Process. Lett._ *52* (1994), 289-294.

V. Chvátal. Notes on the Kolakoski sequence. Technical Report 93-84, DIMACS, March 1994. Revised.

K. Culik II and J. Karhumäki. Iterative devices generating infinite words. In _STACS 92, Proc. 9th Symp. Theoretical Aspects of Comp. Sci._, Vol. 577 of _Lecture Notes in Computer Science_, pp. 531-543. Springer-Verlag, 1992.

K. Culik II, J. Karhumäki, and A. Lepistö. Alternating iteration of morphisms and the Kolakovski [sic] sequence. In G. Rozenberg and A. Salomaa, editors, _Lindenmayer Systems_, pp. 93-103. Springer-Verlag, 1992.

F. M. Dekking. Regularity and irregularity of sequences generated by automata. _Sém. Théor. Nombres Bordeaux_ (1979-80), 9.01-9.10.

F. M. Dekking. On the structure of selfgenerating sequences. _Sém. Théor. Nombres Bordeaux_ (1981), 31.01-31.06.

F. M. Dekking. What is the long range order in the Kolakoski sequence? In R. V. Moody, editor, _The Mathematics of Long-Range Aperiodic Order_, Vol. 489 of _NATO ASI Ser., Ser. C., Math. Phys. Sci._, pp. 115-125. Kluwer, 1997.

M. S. Keane. Ergodic theory and subshifts of finite type. In T. Bedford, M. Keane, and C. Series, editors, _Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces_, pp. 35-70. Oxford University Press, 1991.

C. Kimberling. Advanced problem 6281. _Amer. Math. Monthly_ *86* (1979), 793.

C. Kimberling. The Kolakoski sequence and other runners. Unpublished manuscript, 2003.

W. Kolakoski. Elementary problem 5304. _Amer. Math. Monthly_ *72* (1965), 674. Solution, *73* (1966), 681-682.

A. Lepistö. Repetitions in Kolakoski sequence. In G. Rozenberg and A. Salomaa, editors, _Developments in Language Theory_, pp. 130-143. World Scientific, 1994.

Rufus Oldenburger. Exponent trajectories in symbolic dynamics. _Trans. Amer. Math. Soc._ *46* (1939), 453-466.

Rufus Oldenburger. Recurrence of symbolic elements in dynamics. _Bull. Amer. Math. Soc._ *47* (1941), 294-297.

G. Paun. How much Thue is Kolakovski? [sic]. _Bull. European Assoc. Theor. Comput. Sci._ (49) (February 1993), 183-185.

Chuanlong Shen and Yunbao Huang. Some properties of C<sup>&infin;</sup>-words with applications. _SEA Bull. Math._ *20* (1996), 19-30.

B. Sing. Kolakoski-(2m, 2n) are limit-periodic model sets. _J. Math. Physics_ *44* (2003), 899-912.

B. Sing. More Kolakoski sequences. Preprint, available at <a href="http://arxiv.org/abs/1009.4061">http://arxiv.org/abs/1009.4061</a>, September 21 2010.

R. Steacy. Structure in the Kolakoski sequence. _Bull. European Assoc. Theor. Comput. Sci._ (59) (1996), 173-182.

B. Steinsky. A recursive formula for the Kolakoski sequence A000002. _J. Integer Sequences_ *9* (2006), Article 06.3.7.

W. D. Weakley. On the number of C<sup>&infin;</sup>-words of each length. _J. Combin. Theory. Ser. A_ *51* (1989), 55-62.

-- Main.JeffreyShallit - 13 Jul 2011
   * kolakoski-oberwolfach.JPG: <br /> <img width="1000" alt="kolakoski-oberwolfach.JPG" src="%ATTACHURLPATH%/kolakoski-oberwolfach.JPG" />

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	kolakoski-oberwolfach.JPG	r1	manage	3045.0 K	2011-07-13 - 11:38	JeffreyShallit

Topic revision: r4 - 2014-02-13 - JeffreyShallit

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit