Fraenkel's Partition and Brown's Decomposition

Original · EN

Denote the sequence ([(n-x') / x])ₙ₌₁∞ 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 cₖ = 1 if k ∈ B(x, 0), and cₖ = 0 otherwise, i.e., cₖ=[(k+1) / x] - [k / x]. For a positive integer m let Cₘ be the binary word c₁c₂c₃... cₘ. Brown's Decomposition gives integers q₁, q₂,..., independent of m and growing at least exponentially, and integers t, z₀, z₁, z₂,..., zₜ (depending on m) such that Cₘ = CqₜᶻᵗCqₜ₋₁ᶻₜ₋₁... Cq₁ᶻ¹Cq₀ᶻ⁰. In other words, Brown's Decomposition gives a sparse set of initial segments of C∞ and an explicit decomposition of Cₘ (for every m) into a product of these initial segments.