2003/05/09 by Kevin O'Bryant
Mathematics · #math.NT #math.CO #msc:11B83 #msc:68R15
published as Integers (2003), paper A11 (17 pages). http://www.integers-ejcnt.org/ · 19 pages
arxiv created 2003/05/09 · arxiv updated 2009/11/30
Denote the sequence ([ (n-x') / x ])n=1^∞ by B(x, x'), a so-called Beatty sequence. Fraenkel's Partition Theorem gives necessary and sufficient conditions for B(x, x') and B(y, y') to tile the positive integers, i.e., for B(x, x') ∩ B(y, y') = ∅ and B(x, x') ∪ B(y, y') = 1,2, 3, .... Fix 0 < x < 1, and let ck = 1 if k ∈ B(x, 0), and ck = 0 otherwise, i.e., ck=[ (k+1) / x ] - [ k / x]. For a positive integer m let Cm be the binary word c1c2c3... cm. Brown's Decomposition gives integers q1, q2, ..., independent of m and growing at least exponentially, and integers t, z0, z1, z2, ..., zt (depending on m) such that Cm = CqtztC_qt-1^zt-1 ... Cq1z1Cq0z0. In other words, Brown's Decomposition gives a sparse set of initial segments of C_∞ and an explicit decomposition of Cm (for every m) into a product of these initial segments.