Almost Beatty Partitions

A. J. Hildebrand and Xiaomin Li

Department of Mathematics University of Illinois 1409 W. Green St. Urbana, IL 61801

USA

ajh@illinois.edu
xiaomin3@illinois.edu

Junxian Li Mathematisches Institut

Bunsenstraße 3–5 D-37073 Göttingen

Germany

Junxian.Li@mathematik.uni-goettingen.de

Yun Xie Department of Statistics University of Washington

Box 354322 Seattle, WA 98195

USA yunxie@uw.edu

Abstract

Given 0 < α < 1, the Beatty sequence of density α is the sequence B_{α} = (⌊n/α⌋)_{n∈ℕ}. Beatty’s theorem states that if α, β are irrational numbers with α + β = 1, then the Beatty sequences B_{α} and B_{β} partition the positive integers; that is, each positive integer belongs to exactly one of these two sequences. On the other hand, Uspensky showed that this result breaks down completely for partitions into three (or more) sequences: There does not exist a single triple (α, β, γ) such that the Beatty sequences B_{α}, B_{β}, B_{γ} partition the positive integers.

In this paper we consider the question of how close we can come to a three-part Beatty partition by considering “almost” Beatty sequences, that is, sequences that represent small perturbations of an “exact” Beatty sequence. We first characterize all cases in which there exists a partition into two exact Beatty sequences and one almost Beatty sequence with given densities, and we determine the approximation error involved. We then give two general constructions that yield partitions into one exact Beatty sequence and two almost Beatty sequences with prescribed densities, and we determine the approximation error in these constructions. Finally, we show that in many situations these constructions are best-possible in the sense that they yield the closest approximation to a three-part Beatty partition.

1 Introduction

A Beatty sequence is a sequence of the form B_{α} = (⌊n/α⌋)_{n∈ℕ}, where 0 < α < 1 is a real number^{1} and the bracket notation denotes the floor (or greatest integer) function. Beatty sequences arise in a variety of areas, from diophantine approximation and dynamical systems to theoretical computer science and the theory of quasicrystals. They have a number of remarkable properties, the most famous of which is the following theorem. Here, and in the sequel, ℕ = {1, 2, 3, … } denotes the set of positive integers, and by a partition of ℕ we mean a collection of subsets of ℕ such that every element of ℕ belongs to exactly one of these subsets.

Theorem A (Beatty’s theorem, [4]). Two Beatty sequences B_{α} and B_{β} partition ℕ if and only if α and β are positive irrational numbers with α + β = 1.

This result was posed in 1926 by Samuel Beatty as a problem in the American Mathematical Monthly [4], though it had appeared some 30 years earlier in a book by Rayleigh on the theory of sound [22, p. 123]. The result has been rediscovered multiple times since (e.g., [3, 24]), and it also appeared as a problem in the 1959 Putnam Competition [5]. The theorem has been variably referred to as Beatty’s theorem [13], Rayleigh’s theorem [23], and the Rayleigh-Beatty theorem [20]. For more about Beatty’s theorem, we refer to the paper by Stolarsky [26] and the references cited therein. Recent papers on the topic include Ginosar and Yona [11] and Kimberling and Stolarsky [16].

A notable feature of Beatty’s theorem is its generality: the only assumptions needed to ensure that two Beatty sequences form a partition of ℕ are (1) the obvious requirement that the two densities add up to 1, and (2) the (slightly less obvious, but not hard to verify) condition that the numbers α and β be irrational.

1We are using the notation ⌊n/α⌋ instead of the more common notation ⌊αn⌋ for the nth term of a Beatty sequence. This convention has the advantage that the parameter α has a natural interpretation as the density of the sequence B_{α}, and it simplifies the statements and proofs of our results.

As effective as Beatty’s theorem is in producing partitions of ℕ into two Beatty sequences, the result breaks down completely for partitions into three (or more) such sequences:

Theorem B (Uspensky’s theorem, [29]). There exists no partition of ℕ into three or more Beatty sequences.

This result was first proved in 1927 by Uspensky [29]. Other proofs have been given by Skolem [24] and Graham [12]. As with Beatty’s theorem, Uspensky’s theorem eventually made its way into the Putnam, appearing as Problem B6 in the 1995 William Lowell Putnam Competition.^{2}

The theorems of Beatty and Uspensky can be stated in the following equivalent fashion, which highlights the complete breakdown of the partition property when more than two Beatty sequences are involved:

Theorem A^{∗} (Complement version of Beatty’s theorem). The complement of a Beatty sequence with irrational density is always another Beatty sequence.

Theorem B^{∗} (Complement version of Uspensky’s theorem). The complement of a union of two or more pairwise disjoint Beatty sequences is never a Beatty sequence.

In light of the results of Beatty and Uspensky on the existence (resp., non-existence) of partitions into two (resp., three) Beatty sequences it is natural to ask how close we can come to a partition of ℕ into three Beatty sequences. Specifically, given irrational densities α, β, γ ∈ (0, 1) that sum to 1, can we obtain a proper partition of ℕ by slightly “perturbing” one or more of the Beatty sequences B_{α}, B_{β}, B_{γ}? If so, how many of the sequences B_{α}, B_{β}, B_{γ} do we need to perturb and what is the minimal amount of perturbation needed?

In this paper we seek to answer such questions by constructing partitions into “almost” Beatty sequences that approximate, in an appropriate sense, “exact” Beatty sequences. We call such partitions “almost Beatty partitions.”

Since, by Uspensky’s theorem, partitions into three Beatty sequences do not exist, the best we can hope for is partitions into two exact Beatty sequences, B_{α} and B_{β}, and an almost Beatty sequence B̃_{γ}. In Theorem 1 we characterize all triples (α, β, γ) of irrational numbers for which such a partition exists, and we determine the precise “distance” (in the sense of (2) below) between the almost Beatty sequence B̃_{γ} and the corresponding exact Beatty sequence B_{γ} in such a partition.

In Theorems 3, 4, and 6 we consider partitions into one exact Beatty sequence, B_{α}, and two almost Beatty sequences, B̃_{β} and B̃_{γ}, with given densities α, β, and γ. In Theorem 3 we give a general construction of such partitions based on iterating the two-part Beatty partition process, and we determine the approximation errors involved. In Theorem 4 we present a different construction that requires a condition on the relative size of the densities α, β, γ, but leads to a better approximation. In Theorem 6 we consider the special case when two of the three densities α, β, γ are equal, say α = β. We show that in this case we can always obtain an almost Beatty partition from the Beatty sequences B_{α}, B_{β}(= B_{α}), and B_{γ}, by shifting all elements of B_{β} and selected elements of B_{γ} down by exactly 1.

2Interestingly, neither the “official” solution [17] published in the Monthly, nor the two solutions presented in the compilation [14], while mentioning the connection to Beatty’s theorem, made any reference to Uspensky’s theorem and its multiple proofs in the literature. Thus, the Putnam problem may well represent yet another rediscovery of this result.

As special cases of the above results we recover, or improve on, some particular three-part almost Beatty partitions of ℕ that have been mentioned in the literature; see Examples 2, 5, and 7. We emphasize that, while these particular partitions involve sequences with densities related to the golden ratio or other “special” irrational numbers, our results show that almost Beatty partitions of similar quality exist for any triple of irrational densities that sum up to 1, with the quality of the approximation tied mainly to the size of these densities, and not their arithmetic nature.

Our final result, Theorem 8, is a non-existence result showing that the almost Beatty partitions obtained through the construction of Theorem 4 represent, in many situations, the closest approximation to a partition into three Beatty sequences that can be obtained by any method. Specifically, Theorem 8 shows that, for “generic” densities α, β, γ with α > 1/3, there does not exist an almost Beatty partition ℕ = B_{α} ∪ B̃_{β} ∪ B̃_{γ} in which the elements of the almost Beatty sequences B̃_{β} and B̃_{γ} differ from the corresponding elements of the exact Beatty sequences B_{β} and B_{γ} by at most 1.

The remainder of this paper is organized as follows: In Section 2 we state our main results, Theorems 1–8, along with some examples illustrating these results. In Section 3 we gather some auxiliary results, while Sections 4–8 contain the proofs of our main results. We conclude in Section 9 with some remarks on related questions, extensions and generalizations of our results, and directions for future research.

2 Statement of Results

2.1 Notation and conventions

Given a real number x, we let ⌊x⌋ denote its floor, defined as the largest integer n such that n ≤ x, and {x} = x − ⌊x⌋ its fractional part.

We let ℕ denote the set of positive integers, and we use capital letters A, B, …, to denote subsets of ℕ or, equivalently, strictly increasing sequences of positive integers. We denote the nth elements of such sequences by a(n), b(n), etc.

It will be convenient to extend the definition of a sequence (a(n))_{n∈ℕ} indexed by the natural numbers to a sequence indexed by the nonnegative integers by setting a(0) = 0. For example, this convention allows us to consider the “gaps” a(n) − a(n − 1) for all n ∈ ℕ, with the initial gap, a(1) − a(0), having the natural interpretation as the first element of the sequence.

Given a set A ⊂ ℕ, we denote by

A(n) = #{m ≤ n : m ∈ A}  (1)

the counting function of A, i.e., the number of elements of A that are ≤ n.

We measure the “closeness” of two sequences (a(n))_{n∈ℕ} and (b(n))_{n∈ℕ} by the sup-norm

∥a − b∥ = sup{|a(n) − b(n)| : n ∈ ℕ}.  (2)

Thus, ∥a − b∥ < ∞ holds if and only if one sequence can be obtained from the other by “perturbing” each element by a bounded quantity. For integers sequences the norm ∥a − b∥ is attained and represents the maximal amount by which one sequence needs to be perturbed in order to obtain the other sequence.

2.2 Beatty sequences and almost Beatty sequences

Given α ∈ (0, 1), we define the Beatty sequence of density α as

B_{α} = (a(n))_{n∈ℕ}, a(n) = ⌊n/α⌋.  (3)

We call a sequence B̃_{α} = (ã(n))_{n∈ℕ} an almost Beatty sequence of density α if it satisfies ∥ã − a∥ < ∞, where a(n) = ⌊n/α⌋ is the nth term of the Beatty sequence B_{α}. Thus, an almost Beatty sequence is a sequence that can be obtained by perturbing the elements of a Beatty sequence by a bounded amount. Equivalently, an almost Beatty sequence of density α is a sequence B̃_{α} satisfying

B̃_{α}(N) = #{n ≤ N : n ∈ B̃_{α}} = αN + O(1) (N → ∞).

We use the analogous notation

B_{β} = (⌊n/β⌋)_{n∈ℕ} = (b(n))_{n∈ℕ}, B̃_{β} = (b̃(n))_{n∈ℕ},  (4)
B_{γ} = (⌊n/γ⌋)_{n∈ℕ} = (c(n))_{n∈ℕ}, B̃_{γ} = (c̃(n))_{n∈ℕ},  (5)

to denote Beatty sequences and almost Beatty sequences of densities β and γ.

In the sequel, the notations a(n), b(n), and c(n) will always refer to the elements of the Beatty sequences B_{α}, B_{β}, B_{γ} as defined in (3), (4), and (5), and ã(n), b̃(n), and c̃(n) will refer to the elements of almost Beatty sequences B̃_{α}, B̃_{β}, and B̃_{γ}, of densities α, β, and γ, respectively.

2.3 Partitions into two exact Beatty sequences and one almost Beatty sequence

We assume that we are given arbitrary positive real numbers α, β, and γ subject only to the conditions

α, β, γ ∈ ℝ^{+} \ ℚ, α + β + γ = 1,  (6)

which are analogous to the conditions in Beatty’s theorem (Theorem A). Our goal is to construct a partition of ℕ into almost Beatty sequences B̃_{α}, B̃_{β}, B̃_{γ} that are as close as possible to the exact Beatty sequences B_{α}, B_{β}, B_{γ}, where “closeness” is measured by the distance (2).

By Uspensky’s theorem (Theorem B), a partition of ℕ into three exact Beatty sequences is impossible, so the best we can hope for is a partition into two exact Beatty sequences B_{α} and B_{β} and one almost Beatty sequence B̃_{γ}. Our first theorem shows that such partitions do exist, it gives necessary and sufficient conditions on the densities α, β, γ under which such a partition exists, and it shows exactly how close the almost Beatty sequence B̃_{γ} is to the exact Beatty sequence B_{γ}.

Theorem 1 (Partition into two exact Beatty sequences and one almost Beatty sequence). Let α, β, γ satisfy (6). Then there exists a partition ℕ = B̃_{α} ∪ B̃_{β} ∪ B̃_{γ} with B̃_{α} = B_{α}, B̃_{β} = B_{β} if and only if

rα + sβ = 1 for some r, s ∈ ℕ.  (7)

If this condition is satisfied, then B_{α} and B_{β} are disjoint and B̃_{γ} = ℕ \ (B_{α} ∪ B_{β}) is an almost Beatty sequence satisfying

∥c̃− c∥ = max (⌊\frac{2 − α}{1 − α}⌋ , ⌊\frac{2 − β}{1 − β} ⌋) ,  (8)

where c(n) = ⌊n/γ⌋, resp., c̃(n), denote the nth elements of B_{γ}, resp., B̃_{γ}. More precisely, we have

0 ≤ c(n) − c̃(n) ≤ max (⌊\frac{2 − α}{1 − α}⌋ , ⌊\frac{2 − β}{1 − β} ⌋) (n ∈ ℕ),  (9)

where the upper bound is attained for infinitely many n. In particular, if α and β satisfy

max(α, β) < 1/2,  (10)

then we have

c(n) − c̃(n) ∈ {0, 1, 2} (n ∈ ℕ).  (11)

The error bound (9) in this theorem is best-possible in the strongest possible sense: There does not exist a single triple (α, β, γ) of irrational densities satisfying the assumptions of Theorem 1 for which this bound can be improved. In particular, since

⌊\frac{2 − t}{1 − t}⌋ = ⌊1 + \frac{1}{1 − t}⌋ ≥ 2 (0 < t < 1),

it follows that there exists no partition into two exact Beatty sequences and an almost Beatty sequence whose elements differ from the elements of the corresponding exact Beatty sequence by at most 1. Put differently, if only one of the three Beatty sequences is perturbed, the minimal amount of perturbation (in the sense of the distance (2)) needed in order to obtain a partition of ℕ is 2. Moreover, by Theorem 1 a perturbation by at most 2 is sufficient if and only if the conditions (6) and (7) are satisfied and max(α, β) < 1/2.

Example 2. Let α = 1/Φ^{3}, β = 1/Φ^{4}, γ = 1/Φ, where Φ = (\sqrt{5} + 1)/2 = 1.61803 … is the golden ratio. Using the relation Φ^{2} = Φ + 1 one can check that 1/Φ^{3} + 1/Φ^{4} + 1/Φ = 1 and 3/Φ^{3} + 2/Φ^{4} = 1, so conditions (6) and (7) of Theorem 1 hold. Moreover, since max(α, β) < 1/2, by the last part of the theorem the perturbation errors c(n) − c̃(n) are in {0, 1, 2}. Table 1 shows the partition ℕ = B_{α} ∪ B_{β} ∪ B̃_{γ} obtained from the theorem, along with the perturbation errors. The two exact Beatty sequences B_{α} and B_{β} in this partition are the sequences \underline{A004976} and \underline{A004919} in OEIS [25], while the almost Beatty sequence B̃_{γ} is a perturbation of the sequence \underline{A000201}, obtained by subtracting an appropriate amount in \{0, 1, 2\} from the elements in \underline{A000201}.

\begin{matrix}a(n) & 4 & 8 & 12 & 16 & 21 & 25 & 29 & 33 & 38 & 42 & 46 & 50 & 55 & 59 & 63 \\ b(n) & 6 & 13 & 20 & 27 & 34 & 41 & 47 & 54 & 61 & 68 & 75 & 82 & 89 & 95 & 102 \\ c(n) & 1 & 3 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & 16 & 17 & 19 & 21 & 22 & 24 \\ c̃(n) & 1 & 2 & 3 & 5 & 7 & 9 & 10 & 11 & 14 & 15 & 17 & 18 & 19 & 22 & 23 \\ Error & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 2 & 0 & 1 \end{matrix}

Table 1: An almost Beatty partition with α = 1/Φ^{3}, β = 1/Φ^{4}, γ = 1/Φ. (The three highlighted rows form the partition.)

2.4 Partitions into one exact Beatty sequence and two almost Beatty sequences

We next consider partitions into one exact Beatty sequence and two almost Beatty sequences. In contrast to the situation in Theorem 1, here the two almost Beatty sequences are not uniquely determined. We give two constructions that lead to different partitions. Our first approach is based on iterating the two-part Beatty partition process and leads to the following result.

Theorem 3 (Partition into one exact Beatty sequence and two almost Beatty sequences—- Construction I). Let α, β, γ satisfy (6) and suppose

\frac{β}{γ} ∉ ℚ.  (12)

Let

b̃(n) = ⌊⌊\frac{1 − α}{β}n⌋\frac{1}{1 − α}⌋, c̃(n) = ⌊⌊\frac{1 − α}{γ}n⌋\frac{1}{1 − α}⌋.  (13)

Then the sequences B_{α}, B̃_{β} = (b̃(n))_{n∈ℕ}, and B̃_{γ} = (c̃(n))_{n∈ℕ} form an almost Beatty partition of ℕ satisfying

∥b̃ − b∥ ≤ ⌊\frac{2 − α}{1 − α}⌋ , ∥c̃− c∥ ≤ ⌊\frac{2 − α}{1 − α}⌋ .  (14)

In particular, if α satisfies

α < 1/2,  (15)

then we have

∥b̃ − b∥ ≤ 2, ∥c̃− c∥ ≤ 2.  (16)

Our second construction consists of starting out with two exact Beatty sequences B_{α} and B_{β}, and then shifting those elements of B_{β} that also belong to B_{α} to get a sequence B̃_{β} that is disjoint from B_{α}.

Theorem 4 (Partition into one exact Beatty sequence and two almost Beatty sequences—- Construction II). Let α, β, γ satisfy (6) and suppose

max(α, β) < γ.  (17)

Let B̃_{β} = (b̃(n))_{n∈ℕ} be defined by

b̃(n) = \begin{cases}b(n), & if b(n) ∉ B_{α}; \\ b(n) − 1, & if b(n) ∈ B_{α}, \end{cases}  (18)

and let B̃_{γ} = ℕ\(B_{α} ∪B̃_{β}) = (c̃(n))_{n∈ℕ}. Then the sequences B_{α}, B̃_{β}, and B̃_{γ} form an almost Beatty partition of ℕ satisfying

∥b̃ − b∥ ≤ 1, ∥c̃− c∥ ≤ 2.  (19)

More precisely, we have

b(n) − b̃(n) ∈ {0, 1} (n ∈ ℕ),  (20)
c(n) − c̃(n) ∈ {0, 1, 2} (n ∈ ℕ).  (21)

Our proof will yield a more precise result that gives necessary and sufficient conditions for each of the three possible values in (21), and which allows one, in principle, to determine the relative frequencies of these values.

Example 5. Let τ = 1.83929 … be the Tribonacci constant, defined as the positive root of 1/τ + 1/τ^{2} + 1/τ^{3} = 1, and let α = 1/τ^{3}, β = 1/τ^{2}, γ = 1/τ. Then α, β, γ satisfy the conditions (6) and (17) of Theorem 4. Thus, Theorem 4 can be applied to yield a partition of ℕ into the exact Beatty sequence B_{α} = B_{1/τ^{3}} and two almost Beatty sequences B̃_{β} and B̃_{γ} of densities 1/τ^{2} and 1/τ, respectively, with perturbation errors in {0, 1} for the former sequence, and in {0, 1, 2} for the latter sequence. The resulting partition is shown in Table 2 below.

The sequences B_{α}, B_{β}, B_{γ} are the OEIS sequences \underline{A277723}, \underline{A277722}, \underline{A158919}, respectively, while sequence \underline{A277728} represents the numbers not in any of these sequences. The OEIS entry for the latter sequence mentions three related sequences, \underline{A003144}, \underline{A003145}, and \underline{A003146}, that do form a partition of ℕ and which differ from B_{α}, B_{β}, and B_{γ} by at most 3. The partition obtained by Theorem 4 is different from this partition, and it yields a better approximation to a proper Beatty partition, with perturbation errors of 2 in the case of B̃_{γ}, and 1 in the case of B̃_{β}.

a(n) 6 12 18 24 31 37 43 49 56 62 68 74 80 87 93
b(n) 3 6 10 13 16 20 23 27 30 33 37 40 43 47 50
b̃(n) 3 5 10 13 16 20 23 27 30 33 36 40 42 47 50
Error 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0
c(n) 1 4 6 7 10 13 13 14 17 19 21 23 24 25 28
c̃(n) 1 3 5 7 9 11 12 14 16 18 20 22 23 25 27
Error 0 1 1 0 1 2 1 0 1 1 1 1 1 0 1
Table 2: An almost Beatty partition with α = 1/τ^{3}, β = 1/τ^{2}, γ = 1/τ.

It is interesting to compare the constructions of Theorem 3 and Theorem 4. Both constructions are applicable under slightly different additional conditions beyond (6): Theorem 3 requires that β/γ be irrational, while Theorem 4 requires that γ > max(α, β). Thus, the results are not directly comparable. However, in cases where both constructions can be applied, the construction of Theorem 4 yields stronger bounds than those that can be obtained from Theorem 3, namely ∥b̃− b∥ ≤ 1 and ∥c̃− c∥ ≤ 2 instead of ∥b̃− b∥ ≤ 2 and ∥c̃− c∥ ≤ 2.

2.5 Partitions into one exact Beatty sequence and two almost Beatty sequences: The case of two equal densities

In the case when the densities α and β are equal, we can improve on the bounds (19) of Theorem 4.

Theorem 6 (Partition into one exact Beatty sequence and two almost Beatty sequences—Special case). Let α, β, γ satisfy (6), and suppose β = α. Let B̃_{β} = (b̃(n))_{n∈ℕ} be defined by

b̃(n) = b(n) − 1 (n ∈ ℕ),  (22)

and let B̃_{γ} = ℕ\(B_{α} ∪B̃_{β}) = (c̃(n))_{n∈ℕ}. Then the sequences B_{α}, B̃_{β}, and B̃_{γ} form an almost Beatty partition of ℕ satisfying

∥b̃ − b∥ = 1, ∥c̃− c∥ ≤ 1.  (23)

More precisely, we have

b(n) − b̃(n) = 1 (n ∈ ℕ),  (24)
c(n) − c̃(n) ∈ {0, 1} (n ∈ ℕ).  (25)

Example 7. Let α = β = 1/Φ^{2} and γ = 1/Φ^{3}, where Φ is the golden ratio. Since 1/Φ^{3} = 1/Φ−1/Φ^{2}, we have α+β +γ = 1/Φ^{2} +1/Φ = 1, so the density condition (6) is satisfied and Theorem 6 yields an almost Beatty partition consisting of the sequences B_{α} = (⌊Φ^{2}n⌋)_{n∈ℕ}, B_{β} = B_{α} − 1 = (⌊Φ^{2}n⌋ − 1)_{n∈ℕ}, and B̃_{γ}, where the elements of B̃_{γ} differ from those of B_{γ} = (⌊Φ^{3}n⌋)_{n∈ℕ} by at most 1. In fact, the elementary identity ⌊Φ^{2}n⌋ − 1 = ⌊Φ⌊Φn⌋⌋ shows that this partition is the same as that obtained by Theorem 3, namely

ℕ = (⌊Φ^{2}n⌋)_{n∈ℕ} ∪ (⌊Φ⌊Φn⌋⌋)_{n∈ℕ} ∪ (⌊Φ⌊Φ^{2}n⌋⌋)_{n∈ℕ}.

This particular partition is known. It was mentioned in Skolem [24, p. 68], and it can be interpreted in terms of Wythoff sequences; see the OEIS sequence \underline{A003623}.

We remark that, while the identity ⌊Φ^{2}n⌋−1 = ⌊Φ⌊Φn⌋⌋, and hence the connection with the iterated Beatty partition construction, is closely tied to properties of the golden ratio, Theorem 6 shows that almost Beatty partitions of the same quality (i.e., with one exact Beatty sequence and two almost Beatty sequences with perturbation errors at most 1) exist whenever two of the densities α, β, γ are equal.

The constructions of both Theorem 6 and Theorem 1 can be viewed as special cases of the construction of Theorem 4. Indeed, if B_{α} = B_{β}, then the formula for b̃(n) of Theorem 4 reduces to b̃(n) = b(n) − 1 for all n, while in the case when B_{α} and B_{β} are disjoint, this formula yields b̃(n) = b(n) for all n and thus B̃_{β} = B_{β}. We note, however, that Theorems 1 and 6 are more general in one respect: they do not require the condition (17) of Theorem 4.

2.6 A non-existence result

As mentioned in the remarks following Theorem 1, the bounds on the perturbation errors in this result are best-possible. As a consequence, there exists no partition ℕ = B̃_{α} ∪ B̃_{β} ∪ B̃_{γ} such that B̃_{α} = B_{α} and B̃_{β} = B_{β} are exact Beatty sequences and B̃_{γ} is an almost Beatty sequence satisfying ∥c̃− c∥ ≤ 1.

A similarly universal optimality result does not hold for the bound ∥c−c̃∥ ≤ 2 in Theorem 4. Indeed, as Theorem 6 shows, in the case of two equal densities this bound can be improved to ∥c − c̃∥ ≤ 1. In the following theorem we show that, for “generic” densities α, β, γ with α > 1/3, the error bound ∥c − c̃∥ ≤ 2 is indeed best-possible.

Theorem 8 (Non-existence of partitions into an exact Beatty sequence and two almost Beatty sequences with perturbation errors ≤ 1). Let α, β, γ satisfy (6) and suppose that

α > 1/3,  (26)
1, α, β are linearly independent over ℚ.  (27)

There exists no partition ℕ = B̃_{α} ∪ B̃_{β} ∪ B̃_{γ} such that B̃_{α} = B_{α} is an exact Beatty sequence and B̃_{β} = (b̃(n))_{n∈ℕ} and B̃_{γ} = (c̃(n))_{n∈ℕ} are almost Beatty sequences of densities β and γ, respectively, satisfying ∥b̃ − b∥ ≤ 1 and ∥c̃− c∥ ≤ 1.

3 Lemmas

We begin by stating, without proof, some elementary relations involving the floor and fractional part functions.

Lemma 9 (Floor and fractional part function identities). For any real numbers x, y we have

⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ + δ({x}, {y}),
⌊x − y⌋ = ⌊x⌋ − ⌊y⌋ − δ({x − y}, {y}),
{x + y} = {x} + {y} − δ({x}, {y}),
{x − y} = {x} − {y} + δ({x − y}, {y}),

where

δ(s, t) = \begin{cases}1, & if s + t ≥ 1; \\ 0, & if s + t < 1. \end{cases}  (28)

In the following lemma we collect some elementary properties of Beatty sequences. We will provide proofs for the sake of completeness.

Lemma 10 (Elementary properties of Beatty sequences). Let α ∈ (0, 1) be irrational, and let B_{α} = (a(n))_{n∈ℕ} = (⌊n/α⌋)_{n∈ℕ} be the Beatty sequence of density α.

(i) Membership criterion: For any m ∈ ℕ we have

m ∈ B_{α} ⟺ {(m + 1)α} < α ⟺ {mα} > 1 − α.

(ii) Counting function formula: For any m ∈ ℕ we have

B_{α}(m) = ⌊α(m + 1)⌋ = αm + α − {α(m + 1)},

where B_{α}(m) is the counting function of B_{α}, as defined in (1).

(iii) Gap formula: Let k = ⌊1/α⌋. For any n ∈ ℕ we have

a(n + 1) − a(n) = \begin{cases}k + 1, & if \{n/α\} ≥ 1 − \{1/α\}; \\ k, & otherwise. \end{cases}

(iv) Gap criterion: Given m ∈ B_{α}, let m′ denote the successor to m in the sequence B_{α}, so that, by (iii), m′ = m + k or m′ = m + k + 1, where k = ⌊1/α⌋. Then we have, for any m ∈ ℕ,

m ∈ B_{α} and m′ = m + k ⟺ {1/α}α < {(m + 1)α} < α,
m ∈ B_{α} and m′ = m + k + 1 ⟺ {(m + 1)α} < {1/α}α.

Remark 11. Our assumption that α is irrational ensures that equality cannot hold in any of the above relations.

Proof. (i) We have

m ∈ B_{α} ⟺ m = ⌊n/α⌋ for some n ∈ ℕ
⟺ m < n/α < m + 1 for some n ∈ ℕ
⟺ mα < n < (m + 1)α for some n ∈ ℕ
⟺ {(m + 1)α} < α
⟺ {mα} > 1 − α.

(ii) We have

B_{α}(m) = n ⟺ ⌊n/α⌋ ≤ m ≤ ⌊(n + 1)/α⌋ − 1
⟺ n/α < m + 1 < (n + 1)/α
⟺ n < (m + 1)α < n + 1
⟺ n = ⌊(m + 1)α⌋ = (m + 1)α − {(m + 1)α}.

(iii) By Lemma 9 we have

a(n + 1) − a(n) = ⌊\frac{n + 1}{α}⌋ − ⌊\frac{n}{α}⌋ = ⌊\frac{1}{α}⌋ + δ (\{\frac{1}{α}\} , \{\frac{n}{α}\}) ,

where the last term is equal to 1 if {1/α} + {n/α} ≥ 1, and 0 otherwise.

(iv) Note that

kα = (\frac{1}{α} − \{\frac{1}{α}\}) α = 1 − \{\frac{1}{α}\} α.

Thus, using the results of part (i) and (iii) we have

m ∈ B_{α} and m′ = m + k ⟺ m ∈ B_{α} and m + k ∈ B_{α}
⟺ {(m + 1)α} < α and {(m + 1)α + kα} < α
⟺ {(m + 1)α} < α and {(m + 1)α − {1/α}α} < α
⟺ {1/α}α < {(m + 1)α} < α.

This proves the first of the asserted equivalences in (iv). The second equivalence, asserting that m ∈ B_{α} and m′ = m + k + 1 holds if and only if {(m + 1)α} < {1/α}α, follows from this on observing that, by (i), m ∈ B_{α} is equivalent to {(m + 1)α} ∈ (0, α), and by (iii) for any m ∈ B_{α}, we have either m′ = m + k or m′ = m + k + 1.

For our next lemma we assume that α, β, γ are irrational numbers satisfying (6), so that, in particular,

γ = 1 − α − β,  (29)

and we define

u_{m} = {(m + 1)α}, v_{m} = {(m + 1)β}, w_{m} = {(m + 1)γ}.  (30)

Using (29), the latter quantity, w_{m}, can be expressed in terms of u_{m} and v_{m}:

w_{m} = {(m + 1)(1 − α − β)} = {−(m + 1)(α + β)}  (31)
= 1 − {(m + 1)α + (m + 1)β} = 1 − {u_{m} + v_{m}}.

Lemma 12 (Counting function identity). Let α, β, γ satisfy (6), and let u_{m} and v_{m} be as in (30). Then we have, for any m ∈ ℕ,

B_{α}(m) + B_{β}(m) + B_{γ}(m) = m − δ(u_{m}, v_{m}),  (32)

where δ(s, t) ∈ {0, 1} is given by (28).

Proof. Using Lemma 10(ii) together with (29) and (31) we obtain

B_{α}(m) + B_{β}(m) + B_{γ}(m) = (m + 1)(α + β + γ) − u_{m} − v_{m} − w_{m}
= m − u_{m} − v_{m} + {u_{m} + v_{m}}.

Since u_{m}, v_{m} ∈ (0, 1), Lemma 9 yields {u_{m}+v_{m}} = u_{m}+v_{m}−δ(u_{m}, v_{m}). The desired identity now follows.

The remaining lemmas in this section are deeper results which we quote from the literature. The first of these results characterizes disjoint Beatty sequences; see Theorem 3.11 in Niven [19].

Lemma 13 (Disjointness criterion). Let α, β be irrational numbers in (0, 1). Then the Beatty sequences B_{α} and B_{β} are disjoint if and only if there exist positive integers r and s such that

rα + sβ = 1.  (33)

The next lemma is a special case of Weyl’s Theorem in the theory of uniform distribution modulo 1; see Examples 2.1 and 6.1 in Chapter 1 of Kuipers and Niederreiter [18].

Lemma 14 (Weyl’s Theorem).

(i) Let θ be an irrational number. Then the sequence (nθ)_{n∈ℕ} is uniformly distributed modulo 1; that is, we have

lim_{N→∞} \frac{1}{N} #\{n ≤ N : \{nθ\} < t\} = t (0 ≤ t ≤ 1).

(ii) Let θ_{1}, …, θ_{k} be real numbers such that the numbers 1, θ_{1}, …, θ_{k} are linearly independent over ℚ. Then the k-dimensional sequence {(nθ_{1}, …, nθ_{k})} is uniformly distributed modulo 1 in ℝ^{k}; that is, we have

lim_{N→∞} \frac{1}{N} #\{n ≤ N : \{nθ_{i}\} < t_{i} for i = 1, …, k\} = t_{1} … t_{k} (0 ≤ t_{i} ≤ 1).

4 Proof of Theorem 3

Let α, β, γ satisfy (6) and (12). Thus, α, β, γ are positive irrational numbers with α+β+γ = 1 and β/γ irrational.

Since α is irrational, we can apply Beatty’s theorem (Theorem A) to the pair of densities (α, 1 − α) to obtain a partition ℕ = B_{α} ∪ B_{1−α}, where B_{α} is the exact Beatty sequence in the three-part partition we are trying to construct and

B_{1−α} = (⌊n\frac{1}{1 − α}⌋)_{n∈ℕ} .

We partition the latter sequence by partitioning the index set ℕ into two Beatty sequences with densities β/(1 − α) and 1 − β/(1 − α) = γ/(1 − α). These densities sum to 1, and our assumption that β/γ is irrational ensures that both densities are irrational. Thus Beatty’s theorem can be applied again, yielding the partition

B_{1−α} = (⌊⌊\frac{1 − α}{β}n⌋\frac{1}{1 − α}⌋)_{n∈ℕ} ∪ (⌊⌊\frac{1 − α}{γ}n⌋\frac{1}{1 − α}⌋)_{n∈ℕ} .

The two sequences in this partition are exactly the sequences B̃_{β} = (b̃(n))_{n∈ℕ} and B̃_{γ} = (c̃(n))_{n∈ℕ} defined in Theorem 3. Thus, it remains to show that these sequences satisfy the bounds (14). By symmetry, it suffices to prove the first of these bounds, ∥b̃ − b∥ ≤ ⌊(2 − α)/(1 − α)⌋.

Using elementary properties of the floor and fractional part functions we have, for all n ∈ ℕ,

b̃(n) = ⌊⌊\frac{1 − α}{β}n⌋\frac{1}{1 − α}⌋ ≤ ⌊\frac{n}{β}⌋ = b(n)

and

b̃(n) = ⌊\frac{n}{β} − \{\frac{1 − α}{β}n\} \frac{1}{1 − α}⌋ ≥ ⌊\frac{n}{β}⌋ − ⌊\frac{1}{1 − α}⌋ − 1

= b(n) − ⌊\frac{1}{1 − α}⌋ − 1.

Hence

0 ≤ b(n) − b̃(n) ≤ ⌊\frac{1}{1 − α}⌋ + 1 = ⌊\frac{2 − α}{1 − α}⌋

for all n ∈ ℕ. It follows that ∥b̃ − b∥ ≤ ⌊(2 − α)/(1 − α)⌋, which is the asserted bound (14) for ∥b̃ − b∥. This completes the proof of Theorem 3.

Let α, β, γ satisfy the conditions (6) and (17) of Theorem 4. Thus, α, β, γ are positive irrational numbers satisfying α + β + γ = 1 and γ > max(α, β). The latter two conditions imply

α < 1/2, β < 1/2, γ > 1/3.  (34)

Let B̃_{β} = {b̃(n)} and B̃_{γ} = ℕ \ (B_{α} ∪ B̃_{β}) be the sequences defined in Theorem 4.

5.1 Proof of the partition property

We first show that the sequences B̃_{β} and B_{α} are disjoint. Consider an element m = b̃(n) ∈ B̃_{β}. By definition, we have m = b(n) if b(n) ∉ B_{α}, and m = b(n) − 1 if b(n) ∈ B_{α}. In the former case, we immediately get m ∉ B_{α}, while in the latter case we have m+1 ∈ B_{α}, which by Lemma 10(iii) and the above assumption α < 1/2 implies m ∉ B_{α}. Thus the sequences B_{α} and B̃_{β} are disjoint.

Since B̃_{γ} is defined as the complement of the sequences B_{α} and B̃_{β}, it follows that the three sequences B_{α}, B̃_{β}, B̃_{γ} form a partition of ℕ, as claimed.

5.2 Proof of the bounds (19) and (21)

The norm estimates (19) obviously follow from the definition of b̃(n) and (21), so it suffices to prove the latter relation, i.e.,

c(n) − c̃(n) ∈ {0, 1, 2} for all n ∈ ℕ.  (35)

We break up the argument into several lemmas. We recall the notation

u_{m} = {(m + 1)α}, v_{m} = {(m + 1)β}, w_{m} = {(m + 1)γ} = 1 − {u_{m} + v_{m}}.  (36)

We set

E_{β}(m) = B̃_{β}(m) − B_{β}(m), E_{γ}(m) = B̃_{γ}(m) − B_{γ}(m).  (37)

Thus, the sequences E_{β} and E_{γ} represent the differences between the counting functions of the almost Beatty sequences B̃_{β} and B̃_{γ} and the counting functions of the corresponding exact Beatty sequences. In the following two lemmas we show that these differences are always in {0, 1}, and we characterize the cases in which each of the values 0 and 1 is taken on.

Lemma 15. We have, for all m ∈ ℕ,

E_{β}(m) = \begin{cases}1, & if u_{m} > 1 − α and v_{m} > 1 − β; \\ 0, & otherwise. \end{cases}

Proof. By the definition of the sequence B̃_{β} = (b̃(n))_{n∈ℕ} we have b̃(n) = b(n) − 1 if b(n) ∈ B_{α} ∩ B_{β}, and b̃(n) = b(n) otherwise. In the first case, we necessarily have b(n) + 1 ∉ B_{β} and thus b(n) ∉ B̃_{β} since, by Lemma 10(iii) and our assumption (34), the difference between consecutive elements of B_{β} is at least ≥ ⌊1/β⌋ ≥ 2. It follows that the counting functions of B̃_{β} and B_{β} satisfy

B̃_{β}(m) = \begin{cases}B_{β}(m) + 1, & if m + 1 ∈ B_{α} ∩ B_{β}; \\ B_{β}(m), & otherwise. \end{cases}

By Lemma 10(i), m + 1 ∈ B_{α} ∩ B_{β} holds if and only if {(m + 1)α} > 1 − α and {(m + 1)β} > 1 − β, which, by the definition of the numbers u_{m} and v_{m}, is equivalent to the condition u_{m} > 1 − α and v_{m} > 1 − β. The assertion of the lemma then follows on noting that E_{β}(m) = B̃_{β}(m) − B_{β}(m).

Lemma 16. We have, for all m ∈ ℕ,

E_{γ}(m) = \begin{cases}1, & if u_{m} + v_{m} > 1 and (u_{m} < 1 − α or v_{m} < 1 − β); \\ 0, & otherwise. \end{cases}

Proof. Using the relation B̃_{γ} = ℕ \ (B_{α} ∪ B̃_{β}) along with Lemma 15, we get, for all m ∈ ℕ.

B̃_{γ}(m) = m − B_{α}(m) − B̃_{β}(m) = m − B_{α}(m) − B_{β}(m) − η(u_{m}, v_{m}),

where η(u, v) = 1 if u > 1 − α and v > 1 − β, and η(u, v) = 0 otherwise. On the other hand, Lemma 12 yields

B_{γ}(m) = m − B_{α}(m) − B_{β}(m) − δ(u_{m}, v_{m}),

where δ(u, v) is given by (28), i.e., δ(u, v) = 1 if u + v ≥ 1, and δ(u, v) = 0 otherwise. Hence,

E_{γ}(m) = B̃_{γ}(m) − B_{γ}(m) = δ(u_{m}, v_{m}) − η(u_{m}, v_{m}).

It follows that E_{γ}(m) = 1 if and only if δ(u_{m}, v_{m}) = 1 and η(u_{m}, v_{m}) = 0, i.e., if and only if u_{m} + v_{m} ≥ 1 and u_{m} < 1 − α or v_{m} < 1 − β. The latter conditions are exactly the conditions in the lemma characterizing the case E_{γ}(m) = 1.

If these conditions are not satisfied, then we have either (i) δ(u_{m}, v_{m}) = η(u_{m}, v_{m}), and hence E_{γ}(m) = 0, or (ii) δ(u_{m}, v_{m}) = 0 and η(u_{m}, v_{m}) = 1, in which case we would have E_{γ}(m) = −1. Thus, to complete the proof, it suffices to show that case (ii) is impossible. Indeed, the conditions δ(u_{m}, v_{m}) = 0 and η(u_{m}, v_{m}) = 1 are equivalent to the three inequalities u_{m} + v_{m} < 1, u_{m} > 1 − α, and v_{m} > 1 − β holding simultaneously. But the latter two inequalities imply u_{m} + v_{m} > 2 − α − β, which contradicts the first inequality since, by (34), α + β < 1.

Lemma 17. We have, for all m ∈ ℕ,

m ∈ B̃_{γ} ⟺ u_{m} > α and v_{m} > β and (u_{m} < 1 − α or v_{m} < 1 − β).

Proof. By construction, we have B̃_{γ} = ℕ \ (B_{α} ∪ B̃_{β}), with

B̃_{β} = {m ∈ ℕ : m ∈ B_{β} \ B_{α} or m + 1 ∈ B_{β} ∩ B_{α}}.

Therefore, using Lemma 10(i), we get

m ∈ B̃_{γ} ⟺ m ∉ B_{α} and m ∉ B̃_{β}
⟺ m ∉ B_{α} and m ∉ B_{β} \ B_{α} and m + 1 ∉ B_{β} ∩ B_{α}
⟺ u_{m} > α and v_{m} > β and (u_{m} < 1 − α or v_{m} < 1 − β).

Lemma 18. We have, for all n ∈ ℕ,

c(n − 1) ≤ c̃(n) ≤ c(n).

Proof. Note that B̃_{γ}(c̃(n)) = n and B̃_{γ}(c̃(n) − 1) = n − 1. Thus, if c̃(n) ≥ c(n) + 1, then, using the monotonicity of the counting function B̃_{γ}(m) and Lemma 16, we have

n − 1 = B̃_{γ}(c̃(n) − 1)) ≥ B̃_{γ}(c(n))
= B_{γ}(c(n)) + E_{γ}(c(n))
= n + E_{γ}(c(n)) ≥ n,

which is a contradiction. This proves the desired upper bound, c̃(n) ≤ c(n).

Similarly, if c̃(n) ≤ c(n − 1) − 1, then, using the relation B_{γ}(c(n − 1) − 1) = n − 2, we get

n = B̃_{γ}(c̃(n)) ≤ B̃_{γ}(c(n − 1) − 1)
= B_{γ}(c(n − 1) − 1) + E_{γ}(c(n − 1) − 1)
= n − 2 + E_{γ}(c(n − 1) − 1) ≤ n − 1,

which is again a contradiction, thus proving the lower bound c̃(n) ≥ c(n − 1).

Lemma 19. We have, for all n ∈ ℕ,

c(n) − 2 ≤ c̃(n) ≤ c(n).

Proof. Note that γ > 1/3 by our assumption (34). Hence, Lemma 10(iii) yields

c(n − 1) ≥ c(n) − ⌊1/γ⌋ − 1 ≥ c(n) − 3,

and combining this with Lemma 18 we obtain

c(n) − 3 ≤ c(n − 1) ≤ c̃(n) ≤ c(n).  (38)

If γ > 1/2, then the same argument yields the stronger bound

c(n) − 2 ≤ c(n − 1) ≤ c̃(n) ≤ c(n),

which proves the asserted inequality. Thus, we may assume

\frac{1}{3} < γ < \frac{1}{2},  (39)

and it remains to show that in this case we cannot have c(n) − 3 = c̃(n).

We argue by contradiction. Suppose that c(n) − 3 = c̃(n). In view of (38), this forces the double equality

c̃(n) = c(n − 1) = c(n) − 3.  (40)

Our assumption (39) then implies 3 = ⌊1/γ⌋ + 1. Thus, 3 is the larger of the two possible gaps in the Beatty sequence B_{γ}, and by Lemma 10(iv) it follows that {(m + 1)γ} < {1/γ}γ, where m = c(n − 1). Since (see (30) and (31))

{(m + 1)γ} = w_{m} = 1 − {u_{m} + v_{m}},

the latter condition is equivalent to

{u_{m} + v_{m}} > 1 − {1/γ}γ.  (41)

On the other hand, our assumption (40) implies B_{γ}(m) = B_{γ}(c(n−1)) = n−1, B̃_{γ}(m) = B̃_{γ}(c̃(n)) = n, and hence E_{γ}(m) = 1. By Lemma 16 the latter condition holds if and only if u_{m} + v_{m} > 1 and at least one of the inequalities u_{m} < 1 − α and v_{m} < 1 − β holds. It follows that {u_{m} + v_{m}} = u_{m} + v_{m} − 1 and hence

{u_{m} + v_{m}} = u_{m} + v_{m} − 1 < 1 − min(α, β).  (42)

Comparing (41) with (42) yields

min(α, β) < {1/γ}γ = 1 − 2γ,

where the last step follows since, by our assumption 1/3 < γ < 1/2, {1/γ} = (1/γ) − 2. But the latter condition implies 2γ + min(α, β) < 1, which contradicts the assumptions α + β + γ = 1 and γ > max(α, β) of Theorem 4. Hence, the case c(n) − 3 = c̃(n) is impossible.

This completes the proof of Lemma 19.

5.3 Distribution of perturbation errors

Lemma 19 implies the asserted relation (35) and thus completes the proof of Theorem 4. In the remainder of this section we study the distribution of the perturbation errors c(n) − c̃(n) more closely.

Lemma 20. Given n ∈ ℕ, let m = c̃(n) (so that, in particular, m ∈ B̃_{γ}). Then

c(n) − c̃(n) = \begin{cases}0 & ⟺ m ∈ B̃_{γ} and E_{γ}(m) = 0; \\ 1 & ⟺ E_{γ}(m) = 1 and m ∈ B̃_{γ} and m + 1 ∈ B_{γ}; \\ 2 & ⟺ E_{γ}(m) = 1 and m ∈ B̃_{γ} and m + 1 ∉ B_{γ}. \end{cases}

Proof. Let m = c̃(n) and m′ = c(n), so that B̃_{γ}(m) = n, B_{γ}(m′) = n. By Lemma 19 we have m′ ∈ {m, m + 1, m + 2}.

If m′ = m, then B̃_{γ}(m) = n = B_{γ}(m), so E_{γ}(m) = B̃_{γ}(m) − B_{γ}(m) = 0. On the other hand, if m′ ≥ m + 1, then

B_{γ}(m) ≤ B_{γ}(m′ − 1) = B_{γ}(c(n) − 1) = n − 1 = B̃_{γ}(m) − 1

and hence E_{γ}(m) = 1. Thus, m′ = m holds if and only if E_{γ}(m) = 0, while m′ ∈ {m + 1, m + 2} holds if and only if E_{γ}(m) = 1. In the latter case, if m + 1 ∈ B_{γ}, then m′ = m + 1, while if m + 1 ∉ B_{γ}, then m′ > m + 1, and thus necessarily m′ = m + 2. This yields the desired characterization of the values c(n) − c̃(n) (i.e., m′ − m).

Proposition 21 (Characterization of perturbation errors). Under the assumptions of Theorem 4 we have, for any n ∈ ℕ, with m = c̃(n),

c(n) − c̃(n) = \begin{cases}0 & ⟺ u_{m} > α and v_{m} > β and u_{m} + v_{m} < 1; \\ 1 & ⟺ u_{m} > α and v_{m} > β and 1 < u_{m} + v_{m} < 1 + γ; \\ 2 & ⟺ (u_{m} < 1 − α or v_{m} < 1 − β) and u_{m} + v_{m} > 1 + γ. \end{cases}

Proof. In view of Lemma 20 it suffices to show that the three sets of conditions in this lemma are equivalent to the corresponding conditions in the proposition.

By Lemmas 16 and 17 we have

m ∈ B̃_{γ} ⟺ u_{m} > α and v_{m} > β and (u_{m} < 1 − α or v_{m} < 1 − β),  (43)
E_{γ}(m) = 1 ⟺ u_{m} + v_{m} > 1 and (u_{m} < 1 − α or v_{m} < 1 − β),  (44)
E_{γ}(m) = 0 ⟺ u_{m} + v_{m} < 1 or (u_{m} > 1 − α and v_{m} > 1 − β).  (45)

Hence the first condition in Lemma 20, “m ∈ B̃_{γ} and E_{γ}(m) = 0”, holds if and only if the three conditions u_{m} > α, v_{m} > β, and u_{m} + v_{m} < 1, hold simultaneously, i.e., if and only if the first condition in the proposition is satisfied. This proves the first of the three asserted equivalences.

For the second equivalence, note that, by Lemma 10(i), (30), and (31),

m + 1 ∈ B_{γ} ⟺ w_{m} > 1 − γ ⟺ {u_{m} + v_{m}} < γ  (46)
⟺ u_{m} + v_{m} < γ or 1 < u_{m} + v_{m} < 1 + γ.

Combining this with the conditions (43) and (44) for m ∈ B̃_{γ} and E_{γ}(m) = 1, we see that the second condition in Lemma 20, i.e., “m ∈ B̃_{γ} and E_{γ}(m) = 1 and m + 1 ∈ B_{γ}”, holds if and only if

1 < u_{m} + v_{m} < 1 + γ and u_{m} > α and v_{m} > β and (u_{m} < 1 − α or v_{m} < 1 − β). (47)

Now note that the first condition in (47) implies u_{m} + v_{m} < 2 − α − β = (1 − α) + (1 − β), so that at least one of u_{m} < 1 − α and v_{m} < 1 − β must hold. Thus the last condition in (47) is a consequence of the first condition and can therefore be dropped. Hence (47), and therefore also the second condition in Lemma 20, is equivalent to the second condition in the proposition.

The equivalence between the third conditions in Lemma 20 and the proposition can be seen by a similar argument.

The conditions of Proposition 21 can be described geometrically as follows:

c(n) − c̃(n) = d ⟺ (u_{m}, v_{m}) ∈ R_{d} (d = 0, 1, 2),

where m = c̃(n) and R_{0}, R_{1}, and R_{2} are the regions inside the unit square shown in Figure 1 below.

Figure 1: The regions R_{0}, R_{1}, and R_{2} in the uv-plane representing the conditions given in Proposition 21 for the perturbation errors c(n)−c̃(n) to be equal to 0, 1, and 2, respectively. The vertical boundary lines are given by the equations u = α and u = 1 − α, the horizontal boundary lines are given by the equations v = β, v = 1 − β, and the two diagonal lines are given by u + v = 1 and u + v = 1 + γ.

If α, β, 1 are linearly independent over ℚ, then Weyl’s Theorem (Lemma 14) implies that the points (u_{m}, v_{m}) are uniformly distributed in the unit square. By Lemma 17 and Proposition 21 it follows that, under this linear independence condition, the densities of the perturbation errors

P (d) = lim_{N→∞} \frac{1}{N} #\{n ≤ N : c(n) − c̃(n) = d\}  (48)

are given by P (d) = A(R_{d})/A(R_{0} ∪ R_{1} ∪ R_{2}), where A(R) denotes the area of a region R. An elementary computation of the areas of the regions R_{d} depicted in Figure 1 then yields

P (0) = \frac{γ}{2} , P (1) = 1 − \frac{α^{2} + β^{2} + γ^{2}}{2γ} , P (2) = \frac{α^{2} + β^{2}}{2γ} .

In particular, under the density conditions (34) of Theorem 4 and the above linear independence assumption, it follows all three densities are nonzero. Hence, under these conditions the perturbation errors c(n) − c̃(n) take on each of the values 0, 1, 2 on a set of positive density.

6 Proof of Theorem 6

Let α, β and γ be as in Theorem 6. Thus β = α and α and γ are positive irrational numbers satisfying

2α + γ = 1.  (49)

In particular, we must have

α < \frac{1}{2}.  (50)

Let B̃_{β} = (b̃(n))_{n∈ℕ}, where b̃(n) = b(n) − 1, and B̃_{γ} = ℕ \ (B_{α} ∪ B̃_{β}) = (c̃(n))_{n∈ℕ} be the sequences defined in Theorem 6. Using (50), we see as in the proof of Theorem 4 that the sequences B_{α}, B̃_{β}, and B̃_{γ} form a partition of ℕ. The relations b(n) − b̃(n) = 1 and ∥b̃ − b∥ = 1 follow directly from the definition of b̃(n). Thus, to complete the proof of Theorem 6 it remains to prove that

c(n) − c̃(n) ∈ {0, 1}.  (51)

This will follow from the three lemmas below.

We recall the notations (see (36) and (37))

E_{γ}(m) = B̃_{γ}(m) − B_{γ}(m)

and

u_{m} = {(m + 1)α}, v_{m} = {(m + 1)β}, w_{m} = 1 − {u_{m} + v_{m}}

from the proof of Theorem 4. We note that, by our assumption α = β, we have

u_{m} = v_{m}, w_{m} = 1 − {2u_{m}}.  (52)

The first two lemmas are the special cases α = β (and thus u_{m} = v_{m}) of Lemma 16 and Lemma 18, respectively^{3}.

3Theorem 4 involved the additional condition γ > max(α, β), which in the case when α = β reduces to γ > α. However, the proofs of Lemmas 16 and 18, while requiring the upper bounds α < 1/2 and β < 1/2, did not make use of this lower bound for γ. Thus the conclusions of these lemmas remain valid under the present conditions, i.e., α = β < 1/2.

Lemma 22. We have, for all n ∈ ℕ,

E_{γ}(m) = \begin{cases}1, & if 1/2 < u_{m} < 1 − α; \\ 0, & otherwise. \end{cases}

Lemma 23. We have, for all n ∈ ℕ,

c(n − 1) ≤ c̃(n) ≤ c(n).

The following lemma is a stronger version of Lemma 18, valid under the conditions of Theorem 6.

Lemma 24. We have, for all n ∈ ℕ,

c(n) − 1 ≤ c̃(n) ≤ c(n),

Proof. The upper bound, c̃(n) ≤ c(n), follows from Lemma 23. For the lower bound, suppose c̃(n) ≤ c(n) − 2. Let m = c̃(n). Then

B_{γ}(m) ≤ B_{γ}(m + 1) ≤ B_{γ}(c(n) − 1) = n − 1,

while

B̃_{γ}(m + 1) ≥ B̃_{γ}(m) = B̃_{γ}(c̃(n)) = n.

Thus we have

E_{γ}(m) = B̃_{γ}(m) − B_{γ}(m) ≥ 1 and E_{γ}(m + 1) = B̃_{γ}(m + 1) − B_{γ}(m + 1) ≥ 1.

By Lemma 22 this implies that

1/2 < u_{m} < 1 − α and 1/2 < {u_{m} + α} < 1 − α.

The latter two relations imply

1/2 < u_{m} < 1 − 2α,  (53)

and hence, by (49), γ = 1 − 2α > 1/2. Therefore ⌊1/γ⌋ = 1, and by Lemma 10(iii) it follows that c(n) − c(n − 1) ∈ {1, 2}. Our assumption c̃(n) ≤ c(n) − 2 and Lemma 23 then implies

c(n − 1) = c̃(n) = c(n) − 2.

By Lemma 10(iv) it follows that, with m = c(n − 1) = c̃(n), we have

w_{m} < {1/γ}γ = ((1/γ) − 1)γ = 1 − γ = 2α.  (54)

On the other hand, using (52) and (53) we have

w_{m} = 1 − {2u_{m}} = 1 − (2u_{m} − 1) = 2(1 − u_{m}) > 2(2α).  (55)

Comparing (54) and (55) yields 4α < 2α, which is a contradiction. Hence we must have c(n) − c̃(n) ∈ {0, 1}. This completes the proof of Lemma 24 and of Theorem 6.

The necessity of the condition (7) follows from the disjointness criterion of Lemma 13. Thus, it remains to show that if this condition is satisfied, then B̃_{γ} = ℕ \ (B_{α} ∪ B_{β}) is an almost Beatty sequence satisfying the bounds (9), and that the upper bound here is attained for infinitely many n.

Suppose that α, β, γ are irrational numbers satisfying the conditions (6) and (7) of Theorem 1. Thus, there exist r, s ∈ ℕ such that

rα + sβ = 1.  (56)

We distinguish two cases: (I) r = 1 or s = 1, and (II) r > 1 and s > 1.

7.1 Proof of the error bounds (9), Case I: r = 1 or s = 1.

By symmetry it suffices to consider the case r = 1. Then (56) reduces to α + sβ = 1, and since γ = 1 − α − β > 0, we necessarily have s ≥ 2 and

γ = (s − 1)β.  (57)

Moreover, since β = (1 − α)/s < 1/2, we have ⌊(2 − β)/(1 − β)⌋ = 2 and therefore

max (⌊\frac{2 − α}{1 − α}⌋ , ⌊\frac{2 − β}{1 − β} ⌋) = max (⌊1 + \frac{1}{1 − α}⌋ , 2) = 1 + ⌊\frac{1}{1 − α}⌋ .

Thus, to prove the desired bounds (9), it suffices to show that, for all n ∈ ℕ,

0 ≤ c(n) − c̃(n) ≤ ⌊\frac{1}{1 − α}⌋ + 1.  (58)

Let

B_{sβ} = (⌊n/(sβ)⌋)_{n∈ℕ}  (59)

be the Beatty sequence of density sβ. Since α + sβ = 1, by Beatty’s theorem the sequences B_{α} and B_{sβ} partition ℕ.

Now observe that the sequence B_{β} = (⌊n/β⌋)_{n∈ℕ} is the subsequence of B_{sβ} obtained by restricting the index n in (59) to integers n ≡ 0 mod s. Since B_{α} and B_{sβ} partition ℕ, it follows that

B̃_{γ} = ℕ \ (B_{α} ∪ B_{β}) = B_{sβ} \ B_{β} = {⌊n/(sβ)⌋ : n ∈ ℕ, n ≢ 0 mod s}.

Hence c̃(m), the mth term of the sequence B̃_{γ}, is equal to ⌊n_{m}/(sβ)⌋, where n_{m} is the mth positive integer n satisfying n ≢ 0 mod s. A simple enumeration argument shows that if we represent m (uniquely) in the form

m = i(s − 1) + j, i ∈ {0, 1, … }, j ∈ {1, 2 …, s − 1},

then n_{m} = is + j. With this notation, the mth term of B̃_{γ} is given by

c̃(m) = c̃(i(s − 1) + j) = ⌊\frac{n_{m}}{sβ} ⌋ = ⌊\frac{is + j}{sβ} ⌋ = ⌊\frac{i}{β} + \frac{j}{sβ} ⌋.  (60)

On the other hand, since, by (57), c(n) = ⌊n/γ⌋ = ⌊n/((s − 1)β)⌋, we have

c(m) = ⌊\frac{m}{(s − 1)β} ⌋ = ⌊\frac{i(s − 1) + j}{(s − 1)β} ⌋ = ⌊\frac{i}{β} + \frac{j}{(s − 1)β} ⌋.  (61)

From (60) and (61) we obtain, on using Lemma 9,

0 ≤ c(m) − c̃(m) = ⌊\frac{i}{β} + \frac{j}{(s − 1)β} ⌋ − ⌊\frac{i}{β} + \frac{j}{sβ} ⌋  (62)

= ⌊(\frac{i}{β} + \frac{j}{(s − 1)β} ) − (\frac{i}{β} + \frac{j}{sβ} )⌋ + δ_{i,j}

≤ ⌊\frac{j}{s(s − 1)β} ⌋ + 1 ≤ ⌊\frac{1}{sβ} ⌋ + 1 = ⌊\frac{1}{1 − α}⌋ + 1,

where

δ_{i,j} = δ (\{\frac{is + j}{sβ} \} , \{\frac{j}{s(s − 1)β} \})

= \begin{cases}1, & if \{\frac{is+j}{sβ} \} + \{\frac{j}{s(s−1)β} \} ≥ 1; \\ 0, & otherwise. \end{cases}

This proves the bounds (58).

7.2 Proof of the error bounds (9), Case II: r > 1 and s > 1.

In this case, we have γ = 1 − α − β = (r − 1)α + (s − 1)β ≥ α + β, so in particular

γ > 1/2, α < 1/2, β < 1/2.  (63)

Hence

max (⌊\frac{2 − α}{1 − α}⌋ , ⌊\frac{2 − β}{1 − β} ⌋) = 2,

so the desired bounds (9) reduce to

0 ≤ c(n) − c̃(n) ≤ 2.  (64)

Now note that, by (63), we have γ > max(α, β), so the conditions of Theorem 4 are satisfied. Moreover, since B_{α} and B_{β} are disjoint, the sequence B̃_{β} defined in this theorem is identical to B_{β}, and consequently the sequences B̃_{γ} defined in Theorems 1 and 4 must also be equal. Hence, all results established in the proof of Theorem 4 can be applied in the current situation. In particular, Lemma 19 yields the desired bounds (64) for the perturbation errors c(n) − c̃(n).

7.3 Optimality of the error bounds (9)

To complete the proof of Theorem 1, it remains to show that the upper bounds in (9) are sharp.

Consider first Case I above, i.e., the case when r = 1. In this case (9) reduces to (58), and we need to show that the upper bound in the latter inequality is attained infinitely often.

Consider integers m ∈ ℕ satisfying m ≡ 0 mod (s−1). For such integers we have j = s−1 in the representation m = i(s − 1) + j. Thus (62) reduces to

c(m) − c̃(m) = ⌊\frac{1}{sβ} ⌋ + δ_{i,s−1} = ⌊\frac{1}{1 − α}⌋ + δ_{i,s−1},  (65)

where

δ_{i,j} = \begin{cases}1, & if \{\frac{is+s−1}{sβ}\} ≥ 1 − \{\frac{1}{sβ} \}; \\ 0, & otherwise. \end{cases}

Note that {(is + (s − 1))/(sβ)} = {iβ + θ} with θ = (s − 1)/(sβ). Since β is irrational, by Weyl’s theorem (Lemma 14) the sequence ({iβ})_{i∈ℕ}, and therefore also the shifted sequence ({iβ + θ})_{i∈ℕ}, is dense in [0, 1]. Hence δ_{i,s−1} = 1 holds for infinitely many values of i. By (65) it follows that c(m) − c̃(m) = ⌊1/(1 − α)⌋ + 1 also holds for infinitely many m. This proves that the upper bound in (58) is attained for infinitely many m.

In Case II the bounds (9) reduce to 0 ≤ c(n) − c̃(n) ≤ 2, and we need to show that c(n) − c̃(n) = 2 holds for infinitely many n. By Proposition 21 (which, as noted above, is applicable under the assumptions of Case II), c(n) − c̃(n) = 2 holds for infinitely many n if and only if the conditions

(u_{m} < 1 − α or v_{m} < 1 − β) and u_{m} + v_{m} > 1 + γ,  (66)

where u_{m} = {(m + 1)α} and v_{m} = {(m + 1)β}, hold for infinitely many m. Thus, it remains to show the latter assertion.

We may assume without loss of generality that s > r. (Note that the case s = r is impossible since then (6) and (7) imply α + β = 1/r and γ = 1 − (α + β) = 1 − 1/r, contradicting the irrationality of γ.) Under this assumption we have

β < \frac{1}{s}(rα + sβ) = \frac{1}{s},
γ = 1 − α − β < 1 − \frac{1}{s}(rα + sβ) = 1 − \frac{1}{s}.

In view of these bounds, a sufficient condition for (66) is

u_{m} ∈ (1 − ϵ_{1}, 1), v_{m} ∈ (1 − \frac{1}{s}, 1 − \frac{1}{s} + ϵ_{2}) ,  (67)

provided ϵ_{1}, ϵ_{2} > 0 are small enough. Indeed, if β < (1/s) − ϵ_{2} and γ < 1 − (1/s) − ϵ_{1}, then the upper bound for v_{m} in (67) implies v_{m} < 1 − β, while the lower bounds for u_{m} and v_{m} imply u_{m} + v_{m} > 2 − (1/s) − ϵ_{1} > 1 + γ. Thus it remains to show that, given arbitrarily small ϵ_{1} and ϵ_{2}, there exist infinitely many m satisfying (67).

By (7) we have β = (1 − rα)/s and hence

v_{m} = \{β(m + 1)\} = \{\frac{m + 1}{s} − r\frac{α(m + 1)}{s}\} .  (68)

Setting

u_{m}^{∗} = \{\frac{α(m + 1)}{s}\}

and letting j ∈ {1, 2, …, s} be defined by

m + 1 ≡ j mod s,

we can write (68) as

v_{m} = \{\frac{j}{s} − r\frac{α(m + 1)}{s}\} = \{\frac{j}{s} − r \{\frac{α(m + 1)}{s}\}\}  (69)

= \{\frac{j}{s} − ru_{m}^{∗}\} = 1 − \{ru_{m}^{∗} − \frac{j}{s}\} .

Let 0 < ϵ < 1 be given, and suppose that m satisfies

m + 1 ≡ r − 1 mod s  (70)

and

u_{m}^{∗} ∈ (\frac{1 − ϵ}{s}, \frac{1}{s}) .  (71)

Then

u_{m} = \{s\frac{α(m + 1)}{s}\} = \{s \{\frac{α(m + 1)}{s}\}\} = \{su_{m}∗\} ∈ (1 − ϵ, 1).  (72)

Moreover, if ϵ < 1/r, then (69) with j = r − 1 implies

v_{m} = 1 − \{ru_{m}^{∗} − \frac{r − 1}{s}\} = 1 − \{\frac{1}{s} + r (u_{m}^{∗} − \frac{1}{s})\} ∈ (1 − \frac{1}{s}, 1 − \frac{1}{s} + \frac{rϵ}{s}) .  (73)

From (72) and (73) we see that the (67) holds with ϵ_{1} and ϵ_{2} given by

ϵ_{1} = ϵ, ϵ_{2} = \frac{rϵ}{s}.  (74)

Hence, if ϵ is chosen small enough, then for any m satisfying the conditions (70) and (71), the desired bounds (66) hold.

It remains to show that there are infinitely many m satisfying these two conditions. The first of these conditions, (70), restricts m to integers of the form m = is+r−2, i = 0, 1, 2, . . .. For such m we have

u_{m}^{∗} = \{\frac{α(m + 1)}{s}\} = \{\frac{α(is + r − 1)}{s}\} = \{αi + \frac{(r − 1)α}{s}\} .

Since α is irrational, by Weyl’s theorem (Lemma 14), the sequence ({αi})_{i≥0}, and hence also the sequence ({αi + ((r − 1)α/s)})_{i≥0} = (u_{is+r−2}^{∗})_{i≥0}, is dense in [0, 1]. Thus there exist infinitely many m for which u_{m}^{∗} falls into the interval ((1−ϵ)/s, 1/s), i.e., satisfies (71). This proves our claim and completes the proof of Theorem 1. Remark 25. The above argument yields the maximal value taken on by the perturbation errors c(n) − c̃(n). One can ask, more generally, for the exact set of values taken on by these errors, and for the densities with which these values occur. This is a more difficult problem that leads to some very delicate questions on the behavior of the pairs (u_{m}, v_{m}). We plan to address this question in a future paper. We note here only that, in general, it is not the case that the perturbation errors c(n) − c̃(n) are uniformly distributed over their range of possible values.

8 Proof of Theorem 8

Let α, β, γ satisfy the conditions of the theorem; that is, assume that α, β, γ are positive irrational numbers summing to 1 and suppose in addition that α > 1/3 and that the numbers 1, α, β are linearly independent over ℚ.

We will show that, under these assumptions, there exist infinitely many m ∈ ℕ such that

m ∈ B_{α}, m + 1 ∈ B_{β} ∩ B_{γ}, m + 2 ∈ B_{α}.  (75)

The desired conclusion follows from (75). Indeed, for any m satisfying (75) the element m+1 belongs to both B_{β} and B_{γ}. Thus, in order to obtain a partition of the desired type (i.e., of the form ℕ = B_{α} ∪ B̃_{β} ∪ B̃_{γ}), for one of these latter two sequences the element m + 1 would have to “perturbed” to avoid the overlap. However, since m and m + 2 are elements of B_{α}, a perturbation of m + 1 by ±1 creates an overlap with an element in B_{α}, in contradiction to the partition property. Thus there does not exist a partition ℕ = B_{α} ∪ B̃_{β} ∪ B̃_{γ} in which the perturbation errors for the almost Beatty sequences B̃_{β} and B̃_{γ} are bounded by 1 in absolute value.

It remains to show that (75) holds for infinitely many m. We distinguish two cases, 1/3 < α < 1/2 and 1/2 < α < 1.

Suppose first that

1/3 < α < 1/2.  (76)

Without loss of generality, we may assume that β ≤ γ, which, by (76), implies

β ≤ \frac{1}{2}(β + γ) = \frac{1}{2}(1 − α) < \frac{1}{3} < α.  (77)

Applying part (i) of Lemma 10 we obtain

m + 1 ∈ B_{β} ∩ B_{γ} ⟺ {(m + 1)β} > 1 − β and {(m + 1)γ} > 1 − γ.  (78)

Using the notation (cf. (30) and (31))

u_{m} = {(m + 1)α}, v_{m} = {(m + 1)β}, w_{m} = {(m + 1)γ} = 1 − {u_{m} + v_{m}},

and the relation γ = 1 − α − β, the two conditions on the right of (78) are seen to be equivalent to

v_{m} > 1 − β,  (79)
{u_{m} + v_{m}} < 1 − α − β,  (80)

respectively.

Next, by part (iv) of Lemma 10 along with our assumption (76) (which implies that the number k in Lemma 10(iv) is equal to ⌊1/α⌋ = 2) we have

m ∈ B_{α} and m + 2 ∈ B_{α} ⟺ {1/α}α < u_{m} < α.  (81)

Since {1/α}α = ((1/α) − 2)α = 1 − 2α, the condition on the right of (81) is equivalent to

1 − 2α < u_{m} < α.  (82)

Thus m satisfies (75) if and only if the numbers u_{m} and v_{m} satisfy (79), (80), and (82), and it remains to show that the latter three conditions hold for infinitely many m. To this end, let ϵ > 0 be given and consider the intervals

I_{ϵ} = (α − ϵ, α), J_{ϵ} = (1 − β, 1 − β + ϵ).

If ϵ is sufficiently small, then, since 1 − 2α < α by (76), we have

I_{ϵ} ⊂ (1 − 2α, α), J_{ϵ} ⊂ (1 − β, 1).  (83)

Moreover, our assumption (77) implies α − ϵ + (1 − β) > 1 provided ϵ is sufficiently small, and hence

I_{ϵ} + J_{ϵ} ⊂ (α + 1 − β − ϵ, α + 1 − β + ϵ) ⊂ (1, 2),  (84)

where I + J denotes the sumset of I and J, i.e., the set of all elements x + y with x ∈ I and y ∈ J.

Assume now that ϵ is small enough so that (83) and (84) both hold. Let (u_{m}, v_{m}) be such that

u_{m} ∈ I_{ϵ} and v_{m} ∈ J_{ϵ}.  (85)

Then, by (83), (82) and (79) are satisfied. Moreover, in view of (84), we have

{u_{m} + v_{m}} = u_{m} + v_{m} − 1 < α + (1 − β + ϵ) − 1 = α − β + ϵ,  (86)

and since α < 1/2, we have α + ϵ < 1/2 < 1 − α provided ϵ < (1/2) − α. Hence, for sufficiently small ϵ, the right-hand side of (86) is smaller than 1 − α − β, and condition (80) is satisfied as well.

Thus, assuming ϵ is sufficiently small, any pair (u_{m}, v_{m}) for which (85) holds satisfies the three conditions (79), (80), and (82). Since (u_{m}, v_{m}) = ({(m + 1)α}, {(m + 1)β}) and, by assumption, the numbers 1, α, β are linearly independent over ℚ, the two-dimensional version of Weyl’s Theorem (Lemma 14(ii)) guarantees that there are infinitely many such pairs. This completes the proof of the theorem in the case when 1/3 < α < 1/2.

Now suppose 1/2 < α < 1. As before, the condition m+1 ∈ B_{β} ∩B_{γ} in (75) is equivalent to the two conditions (79) and (80). However, the remaining condition in (75), “m ∈ B_{α} and m + 2 ∈ B_{α}”, requires a slightly different treatment in the case when α > 1/2. In this case, the number k in Lemma 10(iv) is equal to k = ⌊1/α⌋ = 1 and we have {1/α}α = 1−α. Hence, by Lemma 10(iv) a sufficient condition for m ∈ B_{α} and m + 2 ∈ B_{α} to hold is

u_{m} < 1 − α.  (87)

The latter condition is the analog of (82), which characterizes the integers m satisfying “m ∈ B_{α} and m + 2 ∈ B_{α}” in the case when 1/3 < α < 1/2.

The remainder of the argument parallels that for the case 1/3 < α < 1/2. We seek to show that there exist infinitely many m such that (79), (80), and (87) hold. Given ϵ > 0, set

I′_{ϵ} = (β, β + ϵ), J_{ϵ} = (1 − β, 1 − β + ϵ).

If ϵ is sufficiently small, then, since β = 1 − α − γ < 1 − α, we have

I′_{ϵ} ⊂ (0, 1 − α) J_{ϵ} ⊂ (1 − β, 1),  (88)

and

I′_{ϵ} + J_{ϵ} ⊂ (1, 2).  (89)

From (88) we immediately see that (79) and (87) hold whenever u_{m} ∈ I′_{ϵ} and v_{m} ∈ J_{ϵ}. Moreover, by (89) we have, for any sufficiently small ϵ,

{u_{m} + v_{m}} = u_{m} + v_{m} − 1 < (β + ϵ) + (1 − β + ϵ) − 1 = 2ϵ < 1 − α − β,  (90)

so (80) holds as well whenever u_{m} ∈ I′_{ϵ} and v_{m} ∈ J_{ϵ}. As before, Weyl’s Theorem ensures that there are infinitely many m for which the latter two conditions hold, and hence infinitely many m for which (85) holds. This completes the proof of Theorem 8.

9 Concluding Remarks

In this section we discuss some related results in the literature, other approaches to almost Beatty partitions, possible extensions and generalizations of our results, and directions for future research.

More on iterated Beatty partitions. In Theorem 3 we constructed almost Beatty partitions by iterating the standard two-part Beatty partition process. This is perhaps the most natural approach to partitions into more than two “Beatty-like” sequences, and many special cases of such constructions have appeared in the literature. Skolem observed in 1957 [24, p. 68] that starting out with the complementary Beatty sequences (⌊nΦ⌋)_{n∈ℕ} and (⌊nΦ^{2}⌋)_{n∈ℕ} and “partitioning” the index n in the first sequence into the same pair of complementary Beatty sequences yields a three part partition consisting of the sequences (⌊Φ⌊Φn⌋⌋)_{n∈ℕ}, (⌊Φ⌊Φ^{2}n⌋⌋)_{n∈ℕ}, and (⌊Φ^{2}n⌋)_{n∈ℕ}. Further iterations of this process lead to partitions into arbitrarily many Beatty-like sequences involving the golden ratio or other special numbers; see, for example, Fraenkel [8, 9, 10], Kimberling [15], and Ballot [2].

The “iterated Beatty partition” approach leads to sequences whose terms are given by iterated floor functions. Removing all but the outermost floor function in such a sequence, one obtains an exact Beatty sequence whose terms differ from the original sequence by a bounded quantity. Thus, the partitions generated by this approach are almost Beatty partitions in the sense defined of this paper. However, as our results show, these partitions do not necessarily yield the smallest perturbation errors.

Partitions into non-homogeneous Beatty sequences. Another natural approach to almost Beatty partitions is by considering non-homogeneous Beatty sequences, that is, sequences of the form (⌊(n + β)/α⌋)_{n∈ℕ}. Clearly, any sequence of this form differs from the exact Beatty sequence (⌊n/α⌋)_{n∈ℕ} by a bounded amount, and hence is an almost Beatty sequence. Thus, any partition of ℕ into non-homogeneous Beatty sequences is a partition into almost Beatty sequences. The question of when a partition of ℕ into k non-homogeneous Beatty sequences exists has received considerable attention in the literature, but a complete solution is only known in the case k = 2; see, for example, Fraenkel [7] and O’Bryant [21] for the case k = 2, and Tijdeman [28] and the references therein for the general case. An intriguing question is whether any of the sequences constructed in Theorems 1–6 can be represented as a non-homogeneous Beatty sequence.

Very recently, Allouche and Dekking [1] considered two- and three-part partitions of ℕ into sequences of the form (p⌊αn⌋+qn+r)_{n∈ℕ}, where p, q, r are integers and α is an irrational number. Such sequences can be viewed as generalized non-homogeneous Beatty sequences, and they represent almost Beatty sequences in the sense of this paper, associated with the exact Beatty sequence (⌊(pα + q)n⌋)_{n∈ℕ}. Again, it would be interesting to see if any of the sequences constructed in our partitions are of the above form.

Other approximation measures. In our results we measured the “closeness” of two sequences A = (a(n))_{n∈ℕ} and B = (b(n))_{n∈ℕ} by the sup-norm ∥a − b∥. This norm has the natural interpretation as the maximal amount by which an element in one sequence needs to be “perturbed” in order to obtain the corresponding element in the other sequence. An alternative, and seemingly equally natural, measure of closeness of two sequences A and B is the sup-norm of the associated counting functions, i.e.,

∥A − B∥ = sup{|A(n) − B(n)| : n ∈ ℕ}.

One can ask how our results would be affected if the approximation errors had been measured in terms of the latter norm. Surprisingly, this question has a trivial answer, at least in the case of Theorems 1, 4, and 6: In all of these cases, we have ∥B_{β} −B̃_{β}∥ ≤ 1 and ∥B_{γ} −B̃_{γ}∥ ≤ 1 whenever the conditions of the theorems are satisfied. In other words, when measured by the counting function norm, the almost Beatty sequences constructed in these theorems are either exact Beatty sequences or just one step away from being an exact Beatty sequence. This follows easily from Lemmas 12, 15, and 16. The reason for the simple form of this result is that the counting function norm is a much less sensitive measure than the element-wise norm we have used in this paper.

Partitions into n almost Beatty sequences. A natural question is whether the constructions of Theorems 3–6 can be generalized to yield partitions of ℕ into more than three almost Beatty sequences. The “iterated Beatty partition” approach in Theorem 3 lends itself easily to such a generalization, though it is not clear what the best-possible perturbation errors are that can be achieved in the process.

Densities of perturbation errors. Another question concerns the densities with which the perturbation errors in our results occur. We have computed these densities in the case of Theorem 4 under an appropriate linear independence assumption (see the end of Section 5), but in the case of Theorem 1 this would be a much more difficult undertaking (see Remark 25). One motivation for computing these densities is that we can then consider a refined approximation measure given by the weighted average of the absolute values of the errors, with the weights being the associated densities. It would be interesting to see which approaches yield the closest approximation to a partition into Beatty sequences in terms of this refined measure of closeness.

Connection with optimal assignment problems. Finally we remark on an interesting connection with a class of problems involving the assignment or scheduling of tasks in a manner that is, in an appropriate sense, most efficient or most fair. Problems of this type arise in many contexts, from distributing tasks among different machines, to allocating seats in an election, to assigning drivers in a carpool; see, for example, Coppersmith et al. [6].

We describe one such problem, the chairman assignment problem of Tijdeman [27]: Suppose k states with weights λ_{1}, …, λ_{k}, where the λ_{i} are positive real numbers satisfying ∑_{i=1}^{k} λ_{i} = 1, form a union. Each year one of the states is chosen to designate the chair of the union. The goal is to perform this assignment in such way that, at any time, the proportion of chairs chosen from a given state up to that time is as close as possible to the weight of that state. In his paper, Tijdeman determines an assignment that is optimal in a certain global sense, and he gives a recursive algorithm to compute the optimal assignment sequence.

Mathematically, an assignment of chairs amounts to a partition of the positive integers into k sets. Partitions into k almost Beatty sequences with densities given by the weights λ_{i} of the states provide natural candidates for a “fair” assignment. In particular, any of the partitions produced by Theorems 1–6 yields a possible chair assignment sequence for the case of three states with weights α, β, and γ. These partitions turn out to be different from those given by Tijdeman, and they are not optimal with respect to the measure used by Tijdeman (which essentially amounts to minimizing the discrepancies sup_{n} |A_{i}(n) − λ_{i}n|, where A_{i} is the ith set in the partition). However, as shown in this paper, these partitions are, in many cases, best-possible in a different sense and thus might be of interest in applications to assignment problems. Exploring these connections and applications further could be a fruitful area for future research.

10 Acknowledgments

This work originated with an undergraduate research project carried out in Spring 2018 at the Illinois Geometry Lab at the University of Illinois; we thank the IGL for providing this opportunity. We also thank Michel Dekking for calling our attention to the paper [1] and the editor-in-chief for referring us to Tijdeman’s paper [27] on the chairman assignment problem.

References

[1] J. P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, preprint, 2018. Available at https://arXiv.org/abs/1809.03424.

[2] C. Ballot, On functions expressible as words on a pair of Beatty sequences, J. Integer Sequences 20 (2017), Article 17.4.2.

[3] T. Bang, On the sequence [nα], n = 1, 2, · · ·. Supplementary note to the preceding paper by Th. Skolem, Math. Scand. 5 (1957), 69–76.

[4] S. Beatty, Problem 3173, Amer. Math. Monthly 33 (1926), 159.

[5] L. E. Bush, The William Lowell Putnam Mathematical Competition, Amer. Math. Monthly 68 (1961), 18–33.

[6] D. Coppersmith, T. J. Nowicki, G. A. Paleologo, C. Tresser, and C. W. Wu, The optimality of the online greedy algorithm in carpool and chairman assignment problems, ACM Trans. Algorithms 7 (2011), Art. 37.

[7] A. S. Fraenkel, The bracket function and complementary sets of integers, Canad. J. Math. 21 (1969), 6–27.

[8] A. S. Fraenkel, Complementary systems of integers, Amer. Math. Monthly 84 (1977), 114–115.

[9] A. S. Fraenkel, Iterated floor function, algebraic numbers, discrete chaos, Beatty subsequences, semigroups, Trans. Amer. Math. Soc. 341 (1994), 639–664.

[10] A. S. Fraenkel, Complementary iterated floor words and the Flora game, SIAM J. Discrete Math. 24 (2010), 570–588.

[11] Y. Ginosar and I. Yona, A model for pairs of Beatty sequences, Amer. Math. Monthly 119 (2012), 636–645.

[12] R. L. Graham, On a theorem of Uspensky, Amer. Math. Monthly 70 (1963), 407–409.

[13] A. Holshouser and H. Reiter, A generalization of Beatty’s theorem, Southwest J. Pure Appl. Math. (2001), 24–29.

[14] K. S. Kedlaya, B. Poonen, and R. Vakil, The William Lowell Putnam Mathematical Competition, 1985–2000, Mathematical Association of America, 2002.

[15] C. Kimberling, Complementary equations and Wythoff sequences, J. Integer Sequences 11 (2008), Article 08.3.3.

[16] C. Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly 123 (2016), 267–273.

[17] L. F. Klosinski, G. L. Alexanderson, and L. C. Larson, The Fifty-Sixth William Lowell Putnam Mathematical Competition, Amer. Math. Monthly 103 (1996), 665–677.

[18] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience, 1974.

[19] I. Niven, Diophantine Approximations, Dover Publications, 2008.

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

[21] K. O’Bryant, Fraenkel’s partition and Brown’s decomposition, Integers 3 (2003), A11.

[22] Lord Rayleigh, The Theory of Sound, Macmillan, 1894.

[23] I. J. Schoenberg, Mathematical Time Exposures, Mathematical Association of America, 1982.

[24] T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957), 57–68.

[25] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2018. Published elec-

    tronically at https://oeis.org.

[26] K. B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull. 19 (1976), 473–482.

[27] R. Tijdeman, The chairman assignment problem, Discrete Math. 32 (1980), 323–330.

[28] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, in Algebraic Number Theory and Diophantine Analysis (Graz, 1998), de Gruyter, 2000, pp. 467–483.

[29] J. V. Uspensky, On a problem arising out of the theory of a certain game, Amer. Math. Monthly 34 (1927), 516–521.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 05A17, 11P81. Keywords: Beatty sequence, complementary sequence, partition of the integers.

(Concerned with sequences \underline{A000201}, \underline{A003144}, \underline{A003145}, \underline{A003146}, \underline{A003623}, \underline{A004919}, \underline{A004976}, \underline{A158919}, \underline{A277722}, \underline{A277723}, and \underline{A277728}.)

Received October 5 2018; revised version received July 3 2019. Published in Journal of Integer Sequences, July 7 2019.

Return to Journal of Integer Sequences home page.