INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A12

DISJOINT BEATTY SEQUENCES

Jamie Simpson

Department of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth WA 6001, Australia

                       simpson@maths.curtin.edu.au

Received: 2/6/04, Revised: 9/28/04, Accepted: 9/29/04, Published: 9/30/04

Abstract

Consider two rational Beatty sequences {⌊p_{1}/q_{1} +β_{1}⌋ : n ∈ Z} and {⌊p_{2}/q_{2} +β_{2}⌋ : n ∈ Z} where p_{1}, p_{2}, q_{1}, q_{2} are integers. We set p = gcd(p_{1}, p_{2}), q = gcd(q_{1}, q_{2}), u_{1} = q_{1}/q, u_{2} = q_{2}/q. In 1985 Morikawa showed that the sequences are disjoint for some β_{1} and β_{2} if and only if there exist positive integers x and y such that

xu_{1} + yu_{2} = p − 2u_{1}u_{2}(q − 1).

We give a new proof of this theorem. We also use intermediate results to obtain a generating function for a Beatty sequence and relate this to Fraenkel’s conjecture about disjoint covering systems of rational Beatty sequences.

We define a rational Beatty sequence to be a sequence

S(p/q, β) = {⌊pn/q + β⌋ : n ∈ Z},  (1)

where p and q are positive integers, gcd(p, q) = 1 and β is real. We say p/q is the modulus of the sequence. Such sequences have an extensive literature (see [4], [10], [13]) and are the subject of a famous conjecture, postulated by Fraenkel ([4], [10], [6], [12], [14]). A disjoint covering system of rational Beatty sequences is a set of Beatty sequences {S(p_{i}/q_{i}, b_{i}) : i = 1, …, n} which partitions the integers. Fraenkel’s conjecture is:

Conjecture If the rational Beatty sequences {S(p_{i}/q_{i}, b_{i}) : i = 1, …, n} form a disjoint covering system, with n > 2 and p_{1}/q_{1} < p_{2}/q_{2} < ⋯ < p_{n}/q_{n}, then for i = 1, ⋯, n

p_{i} = 2^{n} − 1, q_{i} = 2^{n−i}.

We will say something more about this conjecture at the end of the paper.

Note that if we set q = 1 in (1) we get the arithmetic progression

{np + ⌊β⌋ : n ∈ Z}.

The Chinese Remainder Theorem concerns the disjointness of pairs of such sequences. In our notation one form of it is the following.

Chinese Remainder Theorem There exist numbers β_{1} and β_{2} such that the sequences S(p_{1}, β_{1}) and S(p_{2}, β_{2}) are disjoint if and only if gcd(p_{1}, p_{2}) > 1.

The situation is considerably more complicated when we deal with rational Beatty sequences with non-integral moduli. Ryozu Morikawa [8] has found necessary and sufficient conditions for the existence of β_{1}, β_{2}, such that S(p_{1}/q_{1}, β_{1}) and S(p_{2}/q_{2}, β_{2}) are disjoint. This is the “Japanese Remainder Theorem”. Morikawa’s proof is difficult and because it was published in a little known journal is not as well known as it should be. In this paper we present a simpler proof.

Thus we are interested in whether or not the Beatty sequences S(p_{1}/q_{1}, β_{1}) and S(p_{2}/q_{2}, β_{2}) intersect. We begin with some results that simplify the question.

Lemma 1 Given a rational Beatty sequence S(p/q, β) there exist integers b_{1} and b_{2} such that

S(p/q, β) = S(p/q, b_{1})
= S(p/q, b_{2}/q)).

For a proof see Lemma 1 of [12], where a slightly more general result is given.

Remark 1 Since ⌊p(n + q)/q + β⌋ = ⌊pn/q + β⌋ + p the sequence S(p/q, β) coincides with a set of residue classes modulo p. It follows that:

S(p/q, b′_{1}) = S(p/q, b_{1}),
S(p/q, b′_{2}/q) = S(p/q, b_{2}/q)

if and only if b′_{1} ≡ b_{1} mod p and b′_{2} ≡ b_{2} mod p. If b_{1} and b_{2} are as in Lemma 1 we have

S(p/q, b_{1}q/q) = S(p/q, b_{2}/q)

from which

b_{1}q ≡ b_{2} (mod p).  (2)

Theorem 2 Let p = gcd(p_{1}, p_{2}). Then

S(p_{1}/q_{1}, b_{1}) ∩ S(p_{2}/q_{2}, b_{2}) = ∅

if and only if

S(p/q_{1}, b_{1}) ∩ S(p/q_{2}, b_{2}) = ∅.

Proof. The “if” part is immediate since S(p_{i}/q_{i}, b_{i}) ⊆ S(p/q_{i}, b_{i}) for i = 1, 2. In the other direction let

p_{1} = R_{1}p, p_{2} = R_{2}p

so that gcd(R_{1}, R_{2}) = 1. By Lemma 1 we may assume that b_{1} and b_{2} are integers. Suppose there exist integers n_{1} and n_{2} such that

⌊n_{1}p/q_{1}⌋ + b_{1} = ⌊n_{2}p/q_{2}⌋ + b_{2}.

Then for any integer m,

⌊(n_{1} + mq_{1})p/q_{1}⌋ + b_{1} = ⌊(n_{2} + mq_{2})p/q_{2}⌋ + b_{2}.  (3)

It is now sufficient to show that there exists m such that

R_{1}|(n_{1} + mq_{1}), R_{2}|(n_{2} + mq_{2})  (4)

for then the left and right sides of (3) are members, respectively, of S(p_{1}/q_{1}, b_{1}) and S(p_{2}/q_{2}, b_{2}).

Since gcd(q_{1}, R_{1}) = 1. there exists m_{0} such that R_{1} divides n_{1} + m_{0}q_{1}. So for any integer k,

R_{1}|n_{1} + (m_{0} + kR_{1})q_{1}.

Now consider the sequence

{n_{2} + (m_{0} + kR_{1})q_{2} : k ∈ Z}.

Since gcd(R_{1}, R_{2}) = 1 and gcd(R_{2}, q_{2}) = 1 there exists k_{0} such that

R_{2}|n_{2} + m_{0}q_{2} + k_{0}R_{1}q_{2},

so that (4) holds with m = m_{0} + k_{0}R_{1}. □

This theorem means that when considering conditions for the disjointness of pairs of Beatty sequences we may assume that the numerators of their moduli are equal. We shall henceforth fix p to be this numerator. For this p and any integer q for which gcd(p, q) = 1 we let \overline{q} be the least non-negative residue modulo p satisfying

q\overline{q} ≡ −1 mod p.

Theorem 3 The sequence S(p/q, b), where b is an integer, coincides with the set of residues

\{\overline{q}m + b : m = 0, …, q − 1\} mod p.

Proof. For any n,

⌊pn/q + b⌋ ≡ (pn − q⌊pn/q⌋)\overline{q} + b (mod p).

The term in parentheses can take any value in the interval [0, q − 1]. Thus for any n there exists m ∈ [0, q − 1] such that

⌊pn/q + b⌋ ≡ m\overline{q} + b (mod p).

Similarly, for any m ∈ [0, q − 1] there exists an n satisfying this relation. □

The next theorem concerns the disjointness of two Beatty sequences in which the denominator of the modulus of one divides the denominator of the modulus of the other. This will be used as a lemma for the main theorem.

Theorem 4 Let u be a positive integer. Then the Beatty sequences S(p/q, b_{1}/q) and S(p/uq, b_{2}/uq) have non-empty intersection if and only if b_{2} is congruent modulo p to some integer n in the interval [(b_{1} − q + 1)u, (b_{1} + q)u − 1].

Proof. Using equation (2) in Remark 1, the two Beatty sequences are S(p/q, −b_{1}\overline{q}) and S(p/uq, −b_{2}\overline{uq}). By Theorem 3 these intersect if and only if there exist integers i and j with 0 ≤ i ≤ q − 1, 0 ≤ j ≤ uq − 1 such that,

i\overline{q} − b_{1}\overline{q} ≡ j\overline{uq} − b_{2}\overline{uq} (mod p).  (5)

Multiplying by uq and rearranging gives

b_{2} ≡ j + b_{1}u − iu (mod p).

That is,

b_{2} ∈ ⋃_{i=0}^{q−1} ⋃_{_{j}=0}^{uq−1}{j + b_{1}u − iu}

≡ ⋃_{i=0}^{q−1}[(b_{1} − i)u, (b_{1} + q − i)u − 1] (mod p).

This is the union of q blocks of uq consecutive residues modulo p, with starting points of consecutive blocks differing by u. Thus it is the interval

[(b_{1} − q + 1)u, (b_{1} + q)u − 1] (mod p).
□

Corollary 5 There exist b_{1}, b_{2} such that the Beatty sequences in Theorem 4 are disjoint if and only if p > (2q − 1)u.

Proof. The interval [(b_{1} − q + 1)u, (b_{1} + q)u − 1] contains (2q − 1)u integers. By the theorem, the Beatty sequences can be made disjoint if and only if we can find b_{2} which is not congruent modulo p to any integer in the interval. This occurs if and only if p > (2q − 1)u. □

We now consider the general case of two Beatty sequences S(p/q_{1}, β_{1}) and S(p/q_{2}, β_{2}). From Remark 1 we may assume that β_{1} = 0, β_{2} = b/q_{2}. The next theorem allows us to apply Theorem 4 to this case. We let

q = gcd(q_{1}, q_{2}), q_{1} = u_{1}q, q_{2} = u_{2}q.  (6)

Theorem 6

S(p/q_{1}, 0) = ⋃_{i=0}^{u_{1}−1} S(p/q, i\overline{u}_{1}/q).

Proof. Treating S(p/q_{1}, 0) as a set of residues modulo p, we have, by Theorem 3,

S(p/q_{1}, 0) = ⋃_{m=0}^{q_{1}−1}\{m\overline{q}_{1}\} (mod p).

By (6) the right hand side is

⋃_{m=0}^{u_{1}q−1}\{m\overline{u_{1}q}\} ≡ ⋃_{i=0}^{u_{1}−1} ⋃_{j=0}^{q−1}\{u_{1}j + i\}\overline{u_{1}q} (mod p).

It is easily checked that

\overline{u_{1}q} ≡ −\overline{u}_{1}\overline{q} (mod p)

so that, using Theorem 3,

S(p/q, 0) ≡ ⋃_{i=0}^{u_{1}−1} ⋃_{j=0}^{q−1}\{−\overline{u}_{1}\overline{q}u_{1}j + i\overline{u_{1}q}\}

≡ ⋃_{i=0}^{u_{1}−1} ⋃_{j=0}^{q−1}\{j\overline{q} + i\overline{u_{1}q}\}

≡ ⋃_{i=0}^{u_{1}−1} S(p/q, i\overline{u_{1}q})
≡ ⋃_{i=0}^{u_{1}−1} S(p/q, −i\overline{u}_{1}\overline{q}q/q)
≡ ⋃_{i=0}^{u_{1}−1} S(p/q, i\overline{u}_{1}/q) (mod p)

as required. □

For i = 0 to u_{1} − 1 we let V_{i} be the set of residues modulo p such that b ∈ V_{i} implies

S(p/q_{2}, b/q_{2}) ∩ S(p/q, i\overline{u}_{1}/q) ≠ ∅.

Remark 2 It follows from Theorem 6 that there exists b such that S(p/q_{1}, 0) and S(p/q_{2}, b/q_{2}) are disjoint if and only if ∪_{i=0}^{u_{1}−1}V_{i} is not a complete residue system modulo p.

If we apply Theorem 4 with u_{2} in the role of u, b in the role of b_{2} and i\overline{u}_{1} in the role of b_{1} we obtain

V_{i} = [(i\overline{u}_{1} − q + 1)u_{2}, (i\overline{u}_{1} + q)u_{2} − 1]
= [(−q + 1)u_{2}, qu_{2} − 1] + i\overline{u}_{1}u_{2},

using an obvious notation. Our problem now is to decide whether the union of these intervals is a complete residue system modulo p. To proceed we need some more notation. Let x and y be integers such that

xu_{1} + yu_{2} = p − 2u_{1}u_{2}(q − 1)  (7)

with

1 ≤ y ≤ u_{1}.  (8)

Since u_{1} and u_{2} are relatively prime by definition, (7) can always be satisfied, and (8) ensures that x and y are uniquely defined. Now let

z = u_{1} − y.  (9)

Recall that gcd(q_{1}, p) = 1, hence gcd(u_{1}, p) = 1, hence by (7) gcd(y, u_{1}) = 1 and by (9) gcd(z, u_{1}) = 1.

Thus for each i ∈ [0, u_{1}−1] there exists a unique integer r(i) satisfying r(i) ∈ [0, u_{1}−1] and i ≡ r(i)z mod u_{1}. For r = 0, …, u_{1} let

M(r) = r(x + (2q − 1)u_{2}) − ⌊zr/u_{1}⌋u_{2}.

We will use the functions r(i) and M(r) to obtain a reordering of the intervals V_{i}.

Lemma 7 For i ∈ [0, u_{1} − 1],

M(r(i)) ≡ −i\overline{u}_{1}u_{2} (mod p).

Proof. Fix i and consider u_{1}(M(r(i))+i\overline{u_{1}}u_{2}). Writing r for r(i) and using (7) this equals

u_{1}r(x + (2q − 1)u_{2}) − u_{1}⌊zr/u_{1}⌋u_{2} + u_{1}i\overline{u_{1}}u_{2}
≡ r(xu_{1} + 2u_{1}u_{2}(q − 1) + u_{1}u_{2}) − u_{1}u_{2}⌊zr/u_{1}⌋ − iu_{2}
≡ r(−yu_{2} + u_{1}u_{2}) − u_{1}u_{2}⌊zr/u_{1}⌋ − iu_{2}
≡ u_{2}((u_{1} − y)r − u_{1}⌊zr/u_{1}⌋ − i)
≡ u_{2}(zr − u_{1}⌊zr/u_{1}⌋ − i) (mod p).

Since zr ≡ i mod u_{1} and 0 ≤ i < u_{1} the term in parentheses equals zero. This, together with the observation that gcd(u_{1}, p) = 1, implies the result. □

We can now prove our main result.

Theorem 8 Using the notation

p = gcd(p_{1}, p_{2}), q = gcd(q_{1}, q_{2}), q_{1} = u_{1}q, q_{2} = u_{2}q,

there exist β_{1}, β_{2} such that the Beatty sequences S(p_{1}/q_{1}, β_{1}) and S(p_{2}/q_{2}, β_{2}) are disjoint if and only if there exist positive integers x and y such that,

xu_{1} + yu_{2} = p − 2u_{1}u_{2}(q − 1).  (10)

Proof. We can assume, as in (7) and (8) that we have x and y satisfying (10) with 1 ≤ y ≤ u_{1}. We must show that disjointness is possible if and only if x > 0. By Remark 2 the Beatty sequences can be disjoint if and only if the union of the intervals V_{i} is not a complete residue system modulo p. By Lemma 7 and the observation that as i takes values from 0 to u_{1} − 1 so, in a different order, does r(i), this union is,

⋃_{i=0}^{u_{1}−1}\{[(−q + 1)u_{2}, qu_{2} − 1] + i\overline{u}_{1}u_{2}\} = ⋃_{r=0}^{u_{1}−1}\{[(−q + 1)u_{2}, qu_{2} − 1] − M(r)\}.

This is the union of u_{1} blocks each containing (2q − 1)u_{2} consecutive residues modulo p. The first member of the rth block is (−q + 1)u_{2} − M(r). Now

M(r + 1) − M(r) = x + (2q − 1)u_{2} − u_{2}(⌊z(r + 1)/u_{1}⌋ − ⌊zr/u_{1}⌋).

The term in parentheses takes the value 0 or 1, and as r increases from 0 to u_{1}, ⌊zr/u_{1}⌋ increases from 0 to z. Thus this term will equal 1 for z values of r and 0 for u_{1} − z = y values. Now y is positive by assumption so the maximum value of M(r + 1) − M(r) is x + (2q − 1)u_{2}. The question of whether the union of the intervals V_{i} is a complete residue system modulo p is then equivalent to asking whether the block size is as big as M(r + 1) − M(r). That is, is (2q − 1)u_{2} ≥ x + (2q − 1)u_{2}? This is so if and only if x ≤ 0. Thus it is possible to find β_{1}, β_{2} such that the Beatty sequences are disjoint if and only if x is strictly positive, which implies the statement of the theorem. □

We have presented an analogue of part of the Chinese Remainder Theorem. That theorem also describes the shape of the intersection S(p_{1}, b_{1})∩S(p_{2}, b_{2}) when it is non-empty: it is an arithmetic progression with common difference equaling the lowest common multiple of p_{1} and p_{2}. In the general case the situation is again more complicated. Fraenkel and Holzman [5] have shown that the intersection of S(p_{1}/q_{1}, b_{1}) and S(p_{2}/q_{2}, b_{2}) can have as many as min{q_{1}, q_{2}} + 3 distinct differences between consecutive members.

We now return to Fraenkel’s conjecture Although this concerns sets of pairwise disjoint Beatty sequences, Theorem 8 does not seem to help a great deal. However, we can use some of the earlier results to produce a generating function for the set of non-negative members of a Beatty sequence. We remark that O’Bryant [9] has recently developed a different technique for producing generating functions for Beatty sequences.

Theorem 9 The Beatty sequence S(p/q, b), where b is a non-negative integer, has generating function

f(x) = g(x) + \frac{x^{b}}{1 − x^{p}} \frac{1 − x^{\overline{q}q}}{1 − x\overline{q}} ,

where g(x) is a polynomial with all coefficients equalling 1.

Proof. By Theorem 3 and Remark 1 we see that the non-negative members of the Beatty sequence S(p/q, b) form the set

\{\overline{q}m + b + np : 0 ≤ m < q, 0 ≤ n < ∞\} + G,

where G is a finite set made up of those members of the sequence which are non-negative but correspond to negative values of n. Set G = {g_{1}, …, g_{M}}. The corresponding generating function is

f(x) = x^{b} ∑_{m=0}^{q−1} x^{\overline{q}m} ∑_{n=0}^{∞} x^{np} + g(x)

where g(x) is the polynomial ∑_{i=1}^{M} x^{g_{i}}. Taking the closed forms of the sums gives the required formula. □

Example The Beatty sequence S(7/4, 4) has non-negative terms 0, 2, 4, 5, 7, 9, 11, 12, 14, 16, 18, 19, 21,… We have p = 7, q = 4, b = 4 and \overline{q} = 5. Then

\frac{x^{4}}{1 − x^{7}} \frac{1 − x^{20}}{1 − x^{5}} = x^{4} + x^{9} + x^{11} + x^{14} + x^{16} + x^{18} + x^{19} + x^{21} + ⋯

To account for the missing terms we set g(x) = 1 + x^{2} + x^{5} + x^{7} + x^{12}.

Corollary 10 If {S(p_{i}/q_{i}, b_{i}) : i = 1, …, n} is a disjoint covering system then there exists a polynomial g(x) whose coefficients all equal to 1 such that

g(x) + ∑_{i=1}^{n} \frac{x^{b_{i}}}{1 − x^{p_{i}}} \frac{1 − x^{\overline{q}_{i}q_{i}}}{1 − x^{\overline{q}^{i}}} = \frac{1}{1 − x}.  (11)

Proof. The generating function for the non-negative integers is 1/(1 − x). Since the Beatty sequences partition the integers we get, using the notation of the theorem,

∑_{i=1}^{n}(g_{i}(x) + \frac{x^{b_{i}}}{1 − x^{p_{i}}} \frac{1 − x^{\overline{q}_{i}q_{i}}}{1 − x^{\overline{q}^{i}}}) = \frac{1}{1 − x}.

The result follows on writing g(x) = ∑_{i=1}^{n} g_{i}(x). □

Example \{S(\frac{7}{1}, 4), S(\frac{7}{2}, 6), S(\frac{7}{4}, 0)\} is a disjoint covering of Beatty sequences. The generating functions of the non-negative parts of the sequences are, respectively,

f_{1}(x) = \frac{x^{4}}{1 − x^{7}} ,
f_{2}(x) = x^{2} + \frac{x^{6}}{1 − x^{7}} \frac{1 − x^{6}}{1 − x^{3}} ,
f_{3}(x) = x + x^{3} + x^{8} + \frac{1}{1 − x^{7}} \frac{1 − x^{20}}{1 − x^{5}} ,

so g(x) = x + x^{2} + x^{3} + x^{8} and we have,

x + x^{2} + x^{3} + x^{8} + \frac{x^{4}}{1 − x^{7}} + \frac{x^{6}}{1 − x^{7}} \frac{1 − x^{6}}{1 − x^{3}} + \frac{1}{1 − x^{7}} \frac{1 − x^{20}}{1 − x^{5}} = \frac{1}{1 − x}.

In 1950 Erdös reported the non-existence of disjoint coverings in which the quotients of the moduli all equal 1 and the numerators are distinct, with a proof obtained, independently, by Mirsky, Newman, Davenport, Rado (see [3]). This proof used a generating function like ours. Combinatorial proofs were later given by other authors ([2], [7], [11] and see [15]). We can use the corollary and their technique to give an alternative proof of a known result [1] about disjoint covering systems.

Corollary 11 If {S(p_{i}/q_{i}, b_{i}) : i = 1, …, n} is a disjoint covering system with p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{n} then p_{n−1} = p_{n}.

Proof. Suppose that p_{n} > p_{n−1} and let ζ be a primitive p_{n}th root of unity. Now let x approach ζ in equation (11). The absolute value of the term \frac{x^{bn}}{1−x^{pn}} \frac{1−x^{\overline{q}_{n}qn}}{1−x^{\overline{q}n}} goes to infinity, but all other terms remain finite. This contradiction proves the result. □

References

[1] Berger, M.A., Felzenbaum, A., Fraenkel, A.S., Disjoint covering systems of rational Beatty sequences, J.Comb. Th.(A) 42(1986), 150-153.

[2] Berger, M.A., Felzenbaum, A., Fraenkel, A.S., A non-analytic proof of the Newman-Zńam result for disjoint covering systems, Combinatorica, 6(1986), 235-243.

[3] Erdös, P., On a problem concerning covering systems (Hungarian, English summary), Mat. Lapok, 3(1950), 122-128.

[4] Fraenkel, A.S., Complementing and exactly covering sequences, J. Comb. Th.(1973), 8-20.

[5] Fraenkel, Aviezri S., Holzman, Ron, Gap problems for integer part and fractional part sequences. J. Number Theory 50 (1995), 66–86.

[6] Graham, R.L., Shen Lin, Chio-Shis Lin, Spectra of numbers, Math. Mag., 51(1978), 174-176.

[7] Lewis, E., Infinite covering systems of congruences which don’t exist, Proc. Amer. Math. Soc., 124(1996), 355-360.

[8] Morikawa, R., Disjoint sequences generated by the bracket function, Bull. Lib. Arts, Nagasaki University, 26(1985), 1-13.

[9] O’Bryant, K., A generating function technique for Beatty sequences and other step functions, J. Number Theory 94 (2002), 299-319

[10] Porubský, Š. and Schönheim, J., Covering Systems of Paul Erdős Past, Present and Future, Bolyai Soc. Math. Studies 11, Paul Erdős and his Mathematics, I, Budapest 2002, 581-627.

[11] Simpson, R.J., Exact coverings of the integers by arithmetic progressions, Discrete Math. 59(1986), 181-190.

[12] Simpson, R.J., Disjoint covering systems of rational Beatty sequences, Discrete Math. 92(1991), 361–369.

[13] Stolarsky, K.B., Beatty sequences, continued fractions and certain shift operators, Can. Math. Bull. 19(1976), 473-482.

[14] Tijdeman, R., Fraenkel’s conjecture for six sequences, Disc. Math. 222(2000), 223–234.

[15] Zeilberger,D., How Berger, Felzenbaum and Fraenkel Revolutionized Covering Systems the Same Way that George Boole Revolutionized Logic, Elect. J. Comb., A1, 8(2), (2002), 10 pages.