CONTINUED FRACTIONS AND UNIQUE ADDITIVE PARTITIONS

DAVID J. GRABINER

Abstract. A partition of the positive integers into sets A and B avoids a set S ⊂ ℕ if no two distinct elements in the same part have a sum in S. If the partition is unique, S is uniquely avoidable. For any irrational α > 1, Chow and Long constructed a partition which avoids the numerators of all convergents to α, and conjectured that the set S_{α} which this partition avoided was uniquely avoidable. We prove that the set of numerators of convergents is uniquely avoidable if and only if the continued fraction for α has infinitely many partial quotients equal to 1. We also construct the set S_{α} and show that it is always uniquely avoidable.

1. Introduction

A partition of the positive integers into sets A and B avoids a set S ⊂ ℕ if no two distinct elements in the same part have a sum in S. We say that S is avoidable; if the partition is unique, S is uniquely avoidable.

The Fibonacci numbers are uniquely avoidable [1]. Generalized Fibonacci sequences defined by (s_{1}, s_{2}) = 1, s_{n} = s_{n−1} + s_{n−2}, are also uniquely avoidable provided that s_{1} < s_{2} or 2|s_{1}s_{2}; Alladi, Erdos and Hoggatt [1] proved this for s_{1} = 1, and Evans [3] proved the general case. This suggests a connection with continued fractions. Chow and Long [2] studied this connection, and proved that the set of the numerators of continued-fraction convergents to any irrational α with 1 < α < 2 (easily generalized to any irrational α) is avoidable, although not necessarily uniquely avoidable. Their partition uses the sets

A_{α} = {n ∈ ℕ : the integer multiple of α nearest n is greater than n},
B_{α} = {n ∈ ℕ : the integer multiple of α nearest n is less than n}.

Let S_{α} be the set avoided by the partition {A_{α}, B_{α}}. The main results of Chow and Long are that S_{α} contains the numerators of all convergents to α, and every other element of S_{α} is either the numerator of an intermediate fraction or twice the numerator of a convergent.

We give a characterization of a large class of sets which are uniquely avoidable if they are avoidable at all. We use this to show that the set of numerators of convergents to α is uniquely avoidable for any α if and only if infinitely many partial quotients of α are 1. We can also use the best approximation property to determine S_{α} precisely, and show that S_{α} is uniquely avoidable for any irrational α > 1.

Research at MSRI supported by an NSF Postdoctoral Fellowship.

2. Results on continued fractions

We will use some elementary results on continued fractions, as given in [4] for example. We use the standard notation for continued fractions, in which α = [a_{0}, a_{1}, …], p_{−2} = 0, q_{−2} = 1, p_{−1} = 1, q_{−1} = 0, and for n ≥ 0, we have p_{n+1} = a_{n+1}p_{n} + p_{n−1}.

For 1 < α < 2, let α′ = α/(α−1). Then α = [1, a_{1}, a_{2}, …], and α′ = [a_{1}+1, a_{2}, …]. Thus α′ and α have the same numerators of convergents; p_{0,α′} = p_{1,α} = a_{1}+1, and the lost numerator p_{0,α} = 1 appears as p_{−1,α′}. The numerators of intermediate fractions between p_{0,α} = p_{−1,α′} and p_{1,α} = p_{0,α′} are all the integers in this interval. Also, since 1/α + 1/α′ = 1, we have A_{α} = B_{α′}, and thus α and α′ give the same partition. Thus generalizing to arbitrary α does not give any extra generality; we may assume α < 2 to reduce the number of special cases to be considered.

We will study continued fractions in terms of their approximation properties. For any p, let E(p) = p − qα be the error in approximating p by the closest multiple of α. Then A_{α} is the set of all n with E(n) < 0. Also, if |E(x) + E(y)| < α/2, then E(x + y) = E(x) + E(y); otherwise, E(x + y) = E(x) + E(y) ± α.

We can restate several elementary results on continued fractions in terms of E. The best approximation property of convergents is that |E(x)| ≤ |E(y)| for all positive integers y < x if and only if x is the numerator of a convergent. The property that alternating convergents approach α from opposite sides is that E(p_{n}) < 0 for n even and E(p_{n}) > 0 for n odd. The property that |α − p_{n}/q_{n}| < 1/(q_{n}q_{n+1}) is that |E(p_{n})| < 1/q_{n+1}.

We also need the following lemma, which appears in similar form in [2].

Lemma 1. If p < p_{n+1} and |E(p)| < |E(p_{n−1})|, then p is either kp_{n} or the numerator kp_{n} + p_{n−1} of an intermediate fraction for some k ∈ N.

Proof. For simplicity of notation, we will assume n is odd, so that E(p_{n}) > 0. If E(p) > 0, then let

k = min (⌊\frac{E(p)}{E(p_{n})}⌋ , ⌊\frac{p}{p_{n}} ⌋) .

Then p′ = p − kp_{n} still satisfies 0 < E(p′) < |E(p_{n−1})|, and satisfies either p′ < p_{n} or 0 ≤ E(p′) < E(p_{n}). But no positive p′ < p_{n} can have 0 < E(p′) < |E(p_{n−1})|, by the best approximation property of p_{n−1}, and no positive p′ < p_{n+1} can have 0 < E(p′) < E(p_{n}). Thus we have p′ = 0 and p = kp_{n}.

If E(p) < 0, then E(p−p_{n−1}) = E(p)−E(p_{n−1}), which is between 0 and −E(p_{n−1}), so we can apply the above result to p − p_{n−1}.

We will often need to use the following generalization of this lemma to cases with p > p_{n−1} Lemma 2. If |E(p)| < |E(p_{n−1})| and p ≤ kp_{n+1}, then p = ip_{n−1} + jp_{n}, where i and j are non-negative integers and i ≤ k.

Proof. We again assume n is odd, so that E(p_{n+1}) < 0 < E(p_{n}). The proof is by induction on p. The previous lemma proves the case p < p_{n+1}. If E(p) > 0, then we let p = p′ + p_{n}. Since E(p′) < E(p) < |E(p_{n−1})| and E(p′) > −E(p_{n}) > −|E(p_{n−1})|, and apply the lemma inductively to p′ with the same k. If E(p) < 0, then we let p = p′ + p_{n+1} = p′ + p_{n−1} + a_{n+1}p_{n}. Since E(p′) > E(p) > −|E(p_{n−1})| and E(p′) < E(p_{n+1}) < |E(p_{n−1})|, we can apply the lemma inductively to p′ with k reduced by 1.

3. Characterization of S_{α}

The characterization of A_{α} and B_{α} in terms of E gives a natural characterization of the avoided set S_{α}.

Theorem 1. If E(x) > 0, then x ∈ S_{α} if and only if there is no even z < 2x with 0 < E(z) < E(x); likewise, if E(x) < 0, then x ∈ S_{α} if and only if there is no even z < 2x with 0 > E(z) > E(x).

The following lemma, which we need in the proof of the theorem, is often easier to use in showing that a particular x does occur as a sum.

Lemma 3. If E(x) > 0, then x ∈ S_{α} if and only if there is no y < x with y ≠ x/2 and either 0 < E(y) < E(x) or 0 < E(y) + α/2 < E(x); likewise, if E(x) > 0, then x ∈ S_{α} if and only if there is no y < x with y ≠ x/2 and either 0 > E(y) > E(x) or 0 > E(y) − α/2 > E(x).

Proof of Lemma 3 and Theorem 1. If E(x) > 0 and x = y_{1} + y_{2} with y_{1}, y_{2} ∈ B_{α}, and y_{1} ≠ y_{2}, then E(y_{1}) and E(y_{2}) are both positive and thus E(y_{1} + y_{2}) is either negative or equal to E(y_{1}) + E(y_{2}). If E(y_{1} + y_{2}) is positive, then E(y_{1}) and E(y_{2}) are both less than E(x). Let E(y_{1}) be the smaller of the two (they are not equal since y_{1} ≠ y_{2}); then E(y_{1}) < E(x)/2 < α/2, and 0 < E(2y_{1}) = 2E(y_{1}) < E(x), so we can take z = 2y_{1} in Theorem 1. Similarly, if x = y_{1} + y_{2} with y_{1}, y_{2} ∈ A_{α} and y_{1} ≠ y_{2}, then E(y_{1}) and E(y_{2}) are both negative, and thus E(y_{1} + y_{2}) can only be positive if it is E(y_{1}) + E(y_{2}) + α; it thus follows that E(y_{1}) + α/2 and E(y_{2}) + α/2, which are both positive, must be less than E(x). Let E(y_{1}) + α/2 < E(x)/2 be the smaller of the two; then z = 2y_{1} gives 0 < E(z) = 2E(y_{1}) + α < E(x).

The following two theorems, the main theorems of [2], follow immediately from Lemma 3 and Theorem 1.

Theorem 2. The numerator p_{n} of every convergent is in S_{α}.

Proof. We apply Theorem 1 to x = p_{n}. The number z would have to satisfy |E(z)| < |E(p_{n})|, but Lemma 1 shows that any such z must be at least p_{n} + p_{n+1}, which is too large.

Theorem 3. If p ∈ S_{α}, then p is either the numerator p_{n} of a convergent, twice the numerator of a convergent, or the numerator p_{n−1} + kp_{n} of an intermediate fraction.

Proof. If p is not the numerator of a convergent, then p_{n} < p < p_{n+1} for some n and |E(p)| > |E(p_{n})|. As in Lemma 1, we assume that n is odd for simplicity of notation. If 0 < E(p_{n}) < E(p), then we can take y = p_{n} in Lemma 3 unless p = 2p_{n}. If E(p) < E(p_{n−1}) < 0, then we can take y = p_{n−1} in Lemma 3 unless p = 2p_{n−1}. Otherwise, we have E(p_{n}) < E(p) < −E(p_{n−1}), which is only possible if p is the numerator of an intermediate fraction by Lemma 1.

The cases which are not resolved by these two theorems can be checked similarly.

Theorem 4. For p_{n} a convergent, 2p_{n} is in S_{α} if and only if p_{n} is odd, and either (i) p_{n+1} is odd and a_{n+1} ≥ 3, or (ii) p_{n+1} is even and a_{n+1} ≥ 2, or (iii) p_{n} = 1.

Proof. We first assume |E(p_{n})| < α/4; we will deal with the special case |E(p_{n})| > α/4 at the end. In the general case, we will again assume that n is odd for simplicity of notation.

We will apply Theorem 1 to x = 2p_{n}. If p_{n} is even, then we can take z = p_{n}, and thus 2p_{n} ∉ S_{α}.

If p_{n} is odd, we need an even z < 4p_{n} with 0 < E(z) < 2E(p_{n}). If E(z) < E(p_{n}), we can apply Lemma 2 to z. If E(z) > E(p_{n}) with z > p_{n}, then we can apply Lemma 2 to z − p_{n}. If E(z) > E(p_{n}) with z < p_{n}, then we can take z′ = 2p_{n} − z, which has 0 < E(z′) < E(p_{n}), and use z′ instead of z. Thus, in any of these cases, we must have an even z = ip_{n} + jp_{n+1} for some i, j ≥ 0 with z < 4p_{n} and 0 < E(z) < 2E(p_{n}). If j is even, then since p_{n} is odd, i must also be even, but this is impossible because z = 2p_{n} is forbidden and z = 4p_{n} or z = 2p_{n} + 2p_{n+1} is too large. If j = 3, then we must have i = 0 to have z < 4p_{n}, but if |E(p_{n+1})| < α/6, we get E(3p_{n+1}) = 3E(p_{n+1}) < 0 while we need E(z) > 0, and if α/6 < |E(p_{n+1})| < α/4, we have E(3p_{n+1}) = α + 3E(p_{n+1}) > α/4 while we need E(z) < E(p_{n}) < α/4. If j = 1, then we must have i > 0 since E(p_{n+1}) > 0. The condition z < 4p_{n} is equivalent to i < a_{n+1} − 3, since z = p_{n+1} + ip_{n} = p_{n−1} + a_{n+1}p_{n} + ip_{n}, and p_{n−1} < p_{n} for p_{n} ≠ 1. Either choice of z has E(z) in the correct range, since E(ip_{n} + p_{n+1}) = iE(p_{n}) + E(p_{n+1}), which is positive because E(p_{n}) > −E(p_{n+1}) and less then 2E(p_{n}) < α/2 since E(p_{n+1}) < 0. Thus we need only check that z is even; it is even if p_{n+1} is odd and i = 1, or p_{n+1} is even and i = 2.

We now need to check the special cases with |E(p_{n})| > α/4. Recall that we may assume α < 2. Since |E(p_{n})| < 1/q_{n+1}, there can only be problems if q_{n+1} ≤ 3, which implies q_{n} ≤ 2; thus the only possible p_{n}/q_{n} are 1/1, 2/1, and 3/2. Case (iii) covers p_{n} = 1. If p_{n}/q_{n} = 2/1 is a convergent, then 3/2 < α < 2; the theorem says that the sum of 4 should occur, and it does occur because 1 and 3 are both in A_{α}. If p_{n}/q_{n} = 3/2 is a convergent, then 4/3 < α < 2, and for any such α, |E(p_{n})| < α/4.

Theorem 5. The numerator x = p_{n} + kp_{n+1} of an intermediate fraction is in S_{α} if and only if either (i) p_{n+1} is even, or (ii) k = 1 and p_{n} is odd, or (iii) k = a_{n+2} − 1 and p_{n+2} is odd.

Proof. Again, we will prove the special case |E(p_{n})| > α/3 at the end, and assume in the general case that n is odd for simplicity of notation.

Since x is the numerator of an intermediate fraction, 0 < −E(p_{n+1}) < E(x) < E(p_{n}). We can apply Theorem 1 to see whether x ∈ S_{α}; it is not if there is an even z < 2x with 0 < E(z) < E(p_{n}) + kE(p_{n+1}). Since 0 < E(z) < E(p_{n}), we can apply Lemma 2 to write z = ip_{n} + jp_{n+1}; since x < p_{n+2}, we have z < 2p_{n+2} and thus i ≤ 2. If i = 0 then we must have j ≤ 2k + 1 to have z < 2x, and since p_{n} > −a_{n+2}E(p_{n+1}) and k < a_{n+2}, we have j|E(p_{n+1})| < 2E(p_{n}). If E(p_{n}) < α/4, then E(z) = E(jp_{n+1}) = jE(p_{n+1}) < 0, which is impossible; if α/4 < E(p_{n}) < α/3, then we may instead have E(z) = α + jE(p_{n+1}) > α − 2E(p_{n}) > E(p_{n}), which is also impossible. If i = 2, we have E(z) > E(z − p_{n+2}) = E(z) − E(p_{n+2}) = E(p_{n} + (j − a_{n+2})p_{n+1}), and E(p_{n} + (j − a_{n+2})p_{n+1}) is less than E(p_{n} + kp_{n+1}) only if j − a_{n+2} > k, which implies z > x + p_{n+2}; this is impossible because x is a numerator of an intermediate fraction between p_{n+1}/q_{n+1} and p_{n+2}/q_{n+2}.

Thus the only possibility is i = 1, which gives z = p_{n} +jp_{n+1}. We have 0 < E(z) < E(x) for k < j ≤ a_{n+2}, and z < 2x if p_{n} + jp_{n+1} < 2p_{n} + 2kp_{n+1}, which requires j ≤ 2k since p_{n} < p_{n+1}. If p_{n+1} is even, then p_{n} is odd, and thus no choice of j gives even z; this is case (i). If p_{n+1} is odd and k = 1, the only choice allowed is j = 2, which gives odd z if p_{n} is odd and even z if p_{n} is even; this is case (ii). If p_{n+1} is odd and k = a_{n+2} − 1, the only choice allowed is j = a_{n+2} = k + 1, which z = p_{n+2}; this is case (iii). If p_{n+1} is odd and we have any other k, we can take either j = k + 1 or j = k + 2; one of these will give z even.

We now deal with the special cases with |E(p_{n})| > α/3, which requires q_{n+1} ≤ 2 and thus q_{n} = 1. If p_{n}/q_{n} = 1/1, then n = 1, and |E(p_{1})| > α/3 only for α > 3/2. We must have a_{2} = 1, and thus p_{2} = 2, so case (i) applies to all odd x < 2a_{3} + 1. We have 2 − 1/(a_{3} + 1) < α < 2. Therefore every odd number up to 2a_{3} + 1 is in A_{α} and every even number up to 2a_{3} is in B_{α}, and thus odd numbers less than 2a_{3} + 1 are avoided as required. If p_{n}/q_{n} = 2/1. then n = 2, a_{2} = 1, and α > 3/2, so |E(2)| < 1/2 < α/3.

Theorems 2, 3, 4, and 5 give the complete characterization of the avoided set S_{α}.

4. Uniquely avoidable sets

The most natural characterization of unique avoidability is the graph-theoretic characterization of [1]. If S ⊂ ℕ, then the graph G(S) of S is the graph with vertex set is ℕ with an edge between x and y if x ≠ y and x+y ∈ S. A partition which avoids S is a 2-coloring of G(S), and thus S is avoidable if and only if G(S) is bipartite, and S is uniquely avoidable if and only if G(S) is bipartite and connected.

Note that, if a ∈ S and x < a, then x and a − x are in the same connected component of G(S); either x = a − x, or x ≠ a − x and their sum is a. Thus, if a and a + b ∈ S, then x and x + b are in the same connected component for every x < a. This allows us to prove the following result.

Theorem 6. If S contains d, a + d, c, and b + c with (a, b) = 1, a ≤ c, and b ≤ d (in particular, if S contains a, b, and a + b), then all numbers less than a + b are in the same connected component of G(S). If S contains infinitely many such subsets, then G(S) is connected, and therefore S is uniquely avoidable if it is avoidable at all.

Proof. Assume a < b. By the Chinese Remainder Theorem, any integer m with 0 < m ≤ ab (and thus any m with 0 < m < a + b) can be uniquely written m = xa − yb with 0 < x ≤ b, 0 ≤ y < a. We prove connectivity for 0 < m < a + b by induction on x + y. The base case is m = a. For any other m, if m > a, then m and m − a are in the same component; if m < a, then m and m + b are in the same component.

Our main results on unique avoidability follow.

Theorem 7. The set of numerators of convergents of α is uniquely avoidable if and only if infinitely many partial quotients a_{n} are 1.

Proof. If infinitely many a_{n} are 1, then we can apply Theorem 6 to p_{n−2}, p_{n−1}, and p_{n} to show that the graph is connected, and we have already shown that the set of numerators is avoidable. If only finitely many a_{n} are 1, then there is some N such that for any n > N we have p_{n} > 2p_{n−1}. Thus, regardless of the partition of integers less than p_{n−1}, we can extend the partition up to integers less than p_{n} by placing integers from p_{n−1} to ⌊p_{n}/2⌋ arbitrarily, and placing p_{n} − x in the set which does not contain x for ⌊p_{n}/2⌋ < x < p_{n}. We can continue inductively for all n.

Theorem 8. The set S_{α} avoided by the partition A_{α}, B_{α} is uniquely avoidable for any irrational α > 1.

Proof. If p_{n+1} is even, then p_{n}+p_{n+1} is either p_{n+2} or the numerator of an intermediate fraction, and if it is the numerator of an intermediate fraction, it is in S_{α} by case (i) of Theorem 5. If p_{n+1} is odd, then p_{n+1} − p_{n} is either p_{n−1} or the numerator of an intermediate fraction, and if it is the numerator of an intermediate fraction, it is in S_{α} by case (i) or (iii) of Theorem 5. In either case, we can apply Theorem 6.

The unique avoidability of generalized Fibonacci sequences starting with arbitrary s_{1}, s_{2} [3] follows as a special case of these results. If s_{1} < s_{2}, we can let s_{1} and s_{2} be the numerators p_{n−1} and p_{n} of two consecutive convergents, and let a_{m} = 1 for all m > n. If s_{1} > s_{2}, we can let p_{n} = s_{2}, p_{n+1} = s_{1} + s_{2}; the set of all the s_{i} other than s_{1} is thus uniquely avoidable, and s_{1} is the intermediate fraction p_{n+1} − p_{n}, which is an avoided sum by case (i) of Theorem 5 if s_{2} = p_{n} is even and by case (iii) of Theorem 5 if s_{1} + s_{2} = p_{n+1} is odd. Thus the sequence of s_{i} is uniquely avoidable if s_{1} < s_{2} or either s_{1} or s_{2} is even, and not avoidable at all otherwise.

References

[1] K. Alladi, P. Erdős, and V. E. Hoggatt, Jr., “On additive partitions of integers,” Discrete Math. 23(1978), 201-221.

[2] T. Y. Chow and C. D. Long, “Additive partitions and continued fractions,” preprint.

[3] R. J. Evans, “On additive partitions of sets of positive integers,” Discrete Math. 36(1991), 239-245.

[4] A. I. Khinchin, Continued Fractions, 3rd ed., Chicago: University of Chicago Press, 1964.

  E-mail address: grabiner@msri.org

Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1003