Integers 3 (2003), A11, 17 pp. MR 2004g:11017
We give short proofs of Fraenkel's Partition Theorem and Brown's Decomposition. Denote the sequence
( [ (n-x') / x ] )_{n=1}^\infty
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') \cap B(y, y') = \emptyset
and
B(x, x') \cup B(y, y') = {1,2, 3, ...}.
Fix 0 < x < 1, and let c_k = 1 if k \in B(x, 0), and c_k = 0 otherwise, i.e., c_k=[ (k+1) / x ] - [ k / x]. For a positive integer m let C_m be the binary word c_1c_2c_3\cdots c_m. Brown's Decomposition gives integers q_1, q_2, \dots, independent of m and growing at least exponentially, and integers t, z_0, z_1, z_2, \dots, z_t (depending on m) such that
C_m = C_{q_t}^{z_t}C_{q_{t-1}}^{z_{t-1}} ... C_{q_1}^{z_1}C_{q_0}^{z_0}.
In other words, Brown's Decomposition gives a sparse set of initial segments of C_\infty and an explicit decomposition of C_m (for every m) into a product of these initial segments.
Click to download from the publisher. Note that the PDF file available below contains hyperlinked references, a table of contents, etc.
Click here for postscript (470 kb)
The PDF file is heavily hyperlinked (for instance, you can click to see the Math Review of the articles in the bibliography).