Fraenkel's Partition and Brown's Decomposition

Fraenkel’s Partition and Brown’s Decomposition
Kevin O’Bryant
May 8, 2003
Abstract
We give short proofs of Fraenkel’s Partition Theorem and Brown’s Decom-
∞0 0position. Denotethesequence(b(n−α)/αc) byB(α,α),aso-calledBeattyn=1
sequence. Fraenkel’s Partition Theorem gives necessary and sufficient condi-
0 0 0tions for B(α,α) and B(β,β ) to tile the positive integers, i.e., for B(α,α)∩
0 0 0B(β,β ) = ∅ and B(α,α)∪B(β,β ) = N. Fix α ∈ (0,1), and let c = 1 ifk
k ∈B(α,0), and c = 0 otherwise, i.e., c =b(k+1)αc−bkαc. For a positivek k
integermletC bethebinarywordc c c ···c . Brown’sDecompositiongivesm 1 2 3 m
integers q ,q ,..., independent of m and growing at least exponentially, and in-1 2
zt−1z z zt 1 0tegerst,z ,z ,z ,...,z (dependingonm)suchthatC = C C ···C C .0 1 2 t m qt−1q q qt 1 0
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∞ m
initial segments.Contents
1 Introduction 3
2 Statement of Fraenkel’s Partition 5
3 Statement of Brown’s Decomposition 6
4 Preliminaries 7
5 Proof of Fraenkel’s Theorem 8
5.1 Spirit of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 Without loss of generality ... . . . . . . . . . . . . . . . . . . . . . . . 9
5.2.1 Fraenkel’s Partition is symmetric in α and β. . . . . . . . . . 9
0 05.2.2 If α is rational, then α,α,β,β are all rational with the same
denominator. . . . . . . . . . . . . . . . . . . . . . . . . . ...