5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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"? $\endgroup$ Jan 24, 2012 at 21:26
  • $\begingroup$ 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). $\endgroup$ Jan 24, 2012 at 21:53

1 Answer 1

5
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Fraenkel's conjecture was resolved if any of the $\alpha_i$ are irrational by Ron Graham in the early 1970s. $\endgroup$ Jan 24, 2012 at 21:23
  • $\begingroup$ 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. $\endgroup$ Jan 24, 2012 at 23:08
  • $\begingroup$ 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! $\endgroup$ Jan 24, 2012 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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