Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a given irrational number $\alpha>0$ and a real number $\beta$, the inhomogeneous Beatty sequence sequence $S_{\alpha,\beta}$ is the set $\lbrace\lfloor n\alpha+\beta\rfloor:n=1,2,\dots\rbrace$ (the case $\beta=0$ corresponds to a homogeneous Beatty sequence).

If $\beta=0$, the two homogeneous Beatty sequences $S_{\alpha_1,0}$ and $S_{\alpha_2,0}$ partition the set of positive integers iff $1/\alpha_1+1/\alpha_2=1$. There is also a similar result for inhomogeneous $S_{\alpha_1,\beta_1}$ and $S_{\alpha_2,\beta_2}$: assuming that neither $n\alpha_1+\beta_1$ nor $n\alpha_2+\beta_2$ is an integer for $n=1,2,\dots$, the sequences partition $\mathbb Z_{>0}$ iff $1/\alpha_1+1/\alpha_2=1$ and $\beta_1/\alpha_1+\beta_2/\alpha_2=0$.

Question. For a given $k\ge3$, what are the conditions on $\alpha_1,\dots,\alpha_k$ (and on $\beta_1,\dots,\beta_k$ in the inhomogeneous case) to ensure that the sets $S_{\alpha_i,\beta_i}$, $i=1,\dots,k$, partition the positive integers.

It looks like the book Old and new problems and results in combinatorial number theory by P. Erdős and R.L. Graham (which I do not have) mentions a version of the problem, but I am interested in some (possibly very recent) progress in the direction. My interest is motivated by the study of functional equations of the Mahler-type generating functions of the Beatty sequences.

share|improve this question
    
This problem is much easier (but not all questions have been answered) if all of the $\alpha$ are integers, and is also much easier if any of the $\alpha$ are irrational. What are "Mahler-type generating functions"? –  Kevin O'Bryant Jan 24 '12 at 21:26
    
Kevin, as you have contributions in the area and so you are familiar (=cite) the Borwein's 1993 JNT paper, you know that the generating function of a Beatty sequence can be written as a Lambert series. Mahler was the first to show this systematically (and also to study arithmetical properties of values of the series). –  Wadim Zudilin Jan 24 '12 at 21:53
add comment

1 Answer

up vote 5 down vote accepted

In 1973, Fraenkel showed that, for fixed $k \geq 3$, if $\alpha_i = (2^k - 1)/2^{i-1}$ and $\beta_i = -2^{k-i} + 1$ for $i = 1, 2, \ldots k$, then the $k$ Beatty sequences $S_{\alpha_i,\beta_i} := \lbrace{\lfloor n\alpha_i + \beta_i\rfloor\rbrace}_{n\geq 1}$ partition the positive integers. Many other cases have been proved by Simpson (1991).

Fraenkel also conjectured that any partition of the positive integers into $k \geq 3$ Beatty sequences $S_{\alpha_i,\beta_i}$, with $\alpha_i$, $\beta_i$ real and $0 < \alpha_1 < \alpha_2 < \cdots < \alpha_k$, satisfies $\alpha_i = (2^k - 1)/2^{i-1}$ for $i = 1, 2, \ldots, k$.

To date, Fraenkel's conjecture has been proved for up to $k=7$ sequences. I would recommend taking a look at this paper by Tijdeman (2001), who proved the conjecture for $k = 5, 6$ (and for $k = 3$ in an earlier paper). Altman, Gaujal, Hordijk (1997) proved it for $k = 4$, and more recently, Barát and Varjú (2003) verified the conjecture for $k=7$. It's a tantalising open problem, which I have dabbled with recently too (albeit from a different point of view).

share|improve this answer
    
Fraenkel's conjecture was resolved if any of the $\alpha_i$ are irrational by Ron Graham in the early 1970s. –  Kevin O'Bryant Jan 24 '12 at 21:23
    
There is a paper by Graham on covering the positive integers by disjoint Beatty sets with at least one irrational parameter; J Combinatorial Theory, Series A 15 (1973) 354-358, MR 48 #3911, but judging from the review it does not claim to settle Fraenkel's conjecture. Maybe it does, but I don't see it. –  Gerry Myerson Jan 24 '12 at 23:08
    
Yes, here is the doi link to Graham's paper: dx.doi.org/10.1016/0097-3165(73)90084-8. Rob's preprint (published in Discr. Math. 2000) is really great at explaining everything. Many thanks to Amy, Kevin and Gerry! –  Wadim Zudilin Jan 24 '12 at 23:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.