Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 209 - Number Theory

S. Fraenkel

The structure of complementary sets of integers: a 3-shift theorem

Abstract:

Let $0 < alpha < beta$ be two irrational numbers satisfying $1/alpha + 1/beta = 1$. Then the sequences $a'_n = lfloor {nalpha}rfloor$, $b'_n = lfloor{nbeta}rfloor$, $nge 1$, are complementary over $IZ_{ge 1}$. Thus $a'_n = {rm mex_1} {a'_i,b'_i : 1 le i< n}$, $n geq 1$ (${rm mex_1}(S)$, the smallest positive integer not in the set $S$). Suppose that $c = beta-alpha$ is an integer. Then $b'_n = a'_n+cn$ for all $n ge 1$. We define the following generalization of the sequences $a'_n$, $b'_n$: Let $c,;n_0inIZ_{ge 1}$, and let $XsubsetIZ_{ge 1}$ be an arbitrary finite set. Let $a_n = {rm mex_1}(Xcup{a_i,b_i : 1 leq i< n})$, $b_n = a_n+cn$, $nge n_0$. Let $s_n = a'_n-a_n$. We show that no matter how we pick $c,;n_0$ and $X$, from some point on the {it shift sequence/} $s_n$ assumes either one constant value or three successive values; and if the second case holds, it assumes these values in a very distinct fractal-like pattern, which we describe. This work was motivated by a generalization of Wythoff's game to $Nge 3$ piles.

Host:

May 6, 2004

2:00 PM

AP&M 6438

****************************