A Generating Function Technique for Beatty Sequences and Other Step Sequences

To Appear in Journal of Number Theory Accepted August 22, 2001

Kevin O’Bryant

Department of Mathematics University of Illinois at Urbana-Champaign

1409 W. Green Street

Urbana, IL 61801 E-mail: obryant@math.uiuc.edu

Let g(x, n), with x ∈ ℝ^{+}, be a step function for each n. Assuming certain technical hypotheses, we give a constant α and function f such that ∑_{n=1}^{∞} g(x, n) can be written in the form α + ∑_{0<r<x} f(r), where the summation is extended over all points in (0, x) at which some g( · , n) is not continuous. A typical example is ∑_{n=1}^{∞} z^{⌊n/x⌋} = ( \frac{1}{z} − 1) ∑ \frac{z^{q}}{1−z^{q}}, with the summation extending over all pairs p, q of positive integers satisfying 0 < p/q < x and gcd(p, q) = 1. We then apply such representations to prove identities such as ζ(z) = ∑_{n=1}^{∞} \frac{ϕ(n)}{n^{z}} (ζ(z) − ζ(z, 1 + \frac{1}{n})), the Lambert Series for Euler’s Totient

function, and ∑_{n=0}^{∞}(−1)^{n} \frac{σ_{z}(2n + 1)}{2n + 1} = \frac{π}{4} \frac{z}{1 + z^{2}} , where ζ(z) and ζ(z, a) are

the Riemann and Hurwitz zeta functions and σ_{z}(n) = ∑_{d|n} dz^{d}. We also give a generalization of the Rayleigh-Beatty Theorem, and a new result of a similar nature for the sequences (⌊2nα⌋ − ⌊nα⌋)_{n=1}^{∞}.

Key Words: Beatty Sequences, Generating Functions, Farey Fractions, Lambert Series, Complementary Sequences, Fraenkel’s Conjecture

1. INTRODUCTION

For α irrational, sequences of integers such as (⌊nα + γ⌋)_{n=1}^{∞}, called the non-homogeneous Beatty Sequence for (α, γ), and such as ⌊2nα⌋ − ⌊nα⌋, have many interesting properties and are well-studied. The reader is referred to Stolarsky & Porta (1990) [15], Brown (1993) [5], and Fraenkel (1994) [8] for recent bibliographies.

The generating function K_{γ}(z, \frac{1}{α}) := ∑_{n=1}^{∞} t^{n}z^{⌊nα+γ⌋} (shown in Figure (1) with t = 1, z = 7/16, γ = 1/2) was first studied by Böhmer [2] in 1927, and more recently by Mordell (1965) [11], Newman (1960) [12] and Bowman (1988) [4]. Research has been focused on analyzing the irrationality and transcendence of K_{γ}(z, x) at particular values, including expressing K_{γ}(z, x) as a continued fraction. Borwein & Borwein (1993) [3], outlined in Section 4.1.5, subsumes many earlier results along these lines.

In this paper we present a technique for expressing generating functions of sequences of integers defined with a real parameter x (and satisfying some technical growth conditions depending on the type of generating function) as a summation extended over certain values of α ∈ (0, x). For example,

K_{0}(z, x) := ∑_{n=1}^{∞} z^{⌊n/x⌋} = (\frac{1}{z} − 1) ∑_{\begin{matrix}p,q \\ 0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}} .  (†)

The technique is quite general and applies to ∑ z^{⌊an/x⌋−⌊bn/x⌋}, to ∑⌊\frac{n}{x} + 1⌋^{−z}, and to ∑ z^{⌊n/x+γ⌋}, with interesting corollaries.

For rational x, K_{0}(z, x) is the sum of several geometric series. For example, K_{0}(z, 3) = ∑_{n=1}^{∞} z^{⌊n/3⌋} = 2z^{0} + 3z^{1} + 3z^{2} + 3z^{3} + ⋯ = 2\frac{1}{1−z} + \frac{z}{1−z} = \frac{2+z}{1−z}, and more generally K_{0}(z, x) = \frac{x−1+z}{1−z} whenever x ∈ ℤ^{+}. When x is not an integer, it is more difficult to identify precisely which geometric series are involved. Identifying these is the essential difficulty in applying our Main Theorem. The reader is invited to recognize the right-hand-side of Eq. (†) as a sum of geometric series with initial term (\frac{1}{z} − 1) z^{q} and ratio z^{q}.

The summands become small as q becomes large, so that one may approximate K_{0}(z, x) by summing over the nth Farey Series F_{n}:

K_{0}(z, x) ≈ (\frac{1}{z} − 1) ∑_{\begin{matrix}p/q∈F_{n} \\ 0<p/q<x \end{matrix}} \frac{z^{q}}{1 − z^{q}} .

There are ϕ(n) members in F_{n} \ F_{n−1}, all with denominator n. Hence K_{0}(z, 1) = (\frac{1}{z} − 1) ∑_{q=2}^{∞} ϕ(q)z^{q}/ (1 − z^{q}), and also K_{0}(z, 1) = z/(1 − z) since 1 is an integer. A little algebraic manipulation gives the Lambert Series for Euler’s phi-function (set b = 1 in Eq. (††) below). Considering K_{(b−1)/b}(z^{b}, x) gives the generalization (valid for |z| < 1):

∑_{\begin{matrix}n=1 \\ (n,b)=1 \end{matrix}}^{∞} ϕ(n)\frac{z^{nM(n)}}{1 − z^{bn}} = \frac{b z^{b+1}}{(1 − z^{b})^{2}} + \frac{z}{1 − z^{b}}  (††)

where M(n) satisfies 1 ≤ M(n) ≤ b and M(n) ≡ n^{−1} (mod b). This same argument applied to the Dirichlet generating function ∑_{n=1}^{∞}⌊\frac{n}{x}+1⌋^{−z} yields the novel zeta function identity (valid for ℜ(z) > 1)

ζ(z) = ∑_{q=1}^{∞} \frac{ϕ(q)}{q^{z}} (ζ(z) − ζ(z, 1 + \frac{1}{q})) .

The rationals in the interval (0, 1) are symmetric about \frac{1}{2}, and together with Eq. (†) this allows us to prove a generalization of the Rayleigh-Beatty Theorem: if α and β are irrational and \frac{1}{α} + \frac{1}{β} = m ∈ ℤ^{+}, then each positive integer occurs in the sequences (⌊nα⌋)_{n=1}^{∞} and (⌊nβ⌋)_{n=1}^{∞} a combined total of exactly m times. This proof of the Rayleigh-Beatty Theorem is new, and the technique can be applied to prove similar theorems.

In fact, we obtain a new theorem of this sort by considering the generating function ∑ z^{⌊2n/x⌋−⌊n/x⌋}. If α, β are positive irrationals satisfying \frac{1}{α} + \frac{1}{β} − \frac{1}{α/2} = 1, then

(⌊2nα⌋ − ⌊nα⌋)_{n=1}^{∞} ⋃(⌊2nβ⌋ − ⌊nβ⌋)_{n=1}^{∞} = ℤ^{+}

and

(⌊2nα⌋ − ⌊nα⌋)_{n=1}^{∞} ⋂(⌊2nβ⌋ − ⌊nβ⌋)_{n=1}^{∞} = (⌊2n\frac{α}{2}⌋ − ⌊n\frac{α}{2}⌋)_{n=1}^{∞}.

The rationals are periodic modulo 1, and so Eq. (†) indicates that K_{0}(z, x) has some periodic behavior in x. In fact, we will show that for irrational x, K_{0}(z, x) can be written as the sum of a drift term and an infinite sum of sines. For x = \frac{1}{4}, this expression for K_{0}(z, x) will simplify to

∑_{n=0}^{∞}(−1)^{n} \frac{σ_{z}(2n + 1)}{2n + 1} = \frac{π}{4} \frac{z}{1 + z^{2}} ,

where σ_{z}(n) := ∑_{d|n} dz^{d}. Note that σ_{1} is the usual sum-of-divisors function, but that our expressions for K_{0}(z, x) are valid only for |z| < 1.

FIG. 1. ∑_{n=1}^{∞}(7/16)^{⌊n/x+1/2⌋}

2. CONNECTIONS IN THE LITERATURE

The function K_{γ}(z, x) := ∑_{n=1}^{∞} z^{⌊n/x+γ⌋} has several exotic properties. It is a strictly increasing function of x, and, if γ = 0, is a rational function of z if and only if x is rational (this is elaborated upon in Newman (1960) [12]). Further, a simple ϵ-δ argument shows that K_{γ}(z, x) is continuous only at irrational x. The image of (0, ∞) under K_{γ}(z, ·) has measure zero both as a subset of the complex plane and—if z is real—as a subset of the reals.

This is not the first time a strictly increasing function which is continuous exactly on the irrationals has appeared in the literature. In the 1982 Monthly article “A Naturally Occurring Function Continuous Only at Irrationals” [1] one was encountered in the analysis of random binary search trees.

Erdős & Faudree & Győri (1995) [6] may have encountered another one while counting the number of “books” in a graph with large minimum degree. A book of k pages is defined to be k triangles all sharing a common edge. For each c ∈ [0, 1] define b(c) to be the minimum value b such that every graph with n vertices and minimum degree cn+o(n) contains a book of bn pages. Their bound suggests that b(c) may be monotonic on (\frac{1}{2}, 1) and discontinuous at every rational.

If a(n) > 0 with ∑_{n=1}^{∞} a(n) < ∞, and n(r) is a bijection from the positive rationals onto the positive integers, then ∑\begin{matrix}0<r<x \\ r∈ℚ \end{matrix} a(n(r)) is a strictly

increasing function of x which is continuous exactly on the irrationals. Theorem 4.1 below shows that K_{a/b}(z, x) has such a decomposition provided that we restrict x to a bounded domain. What is remarkable here is that a(n(r)) is easily expressible and depends only on the denominator of r and on γ = a/b.

The presence of such a decomposition is surprising even given the information that K_{γ}(z, x) is increasing and continuous only on the irrationals; K_{γ}(z, x) + x does not have such a decomposition, after all, nor does K_{γ}(z, x) + C(x), where C(x) is Cantor’s Ternary Function, which has 0 derivative a.e.

Borwein & Borwein (1993) [3] present ∑_{n=1}^{∞} t^{n}z^{⌊n/x+γ⌋} as an infinite series in terms of the convergents to x and certain integers involved in the one-sided approximation of γ, provided that \frac{n}{x} + γ is not an integer for any n. From this, they derive a continued fraction representation for (\frac{1}{z} − 1) ∑_{n=1}^{∞} z^{⌊n/x⌋}. Their work rests heavily on a functional equation for this sum, and from this equation they give a simple proof of a theorem of Fraenkel (1969) [7]: If 1 < α ∉ ℚ, γ ∈ [0, 1), and nα + γ is never integral, then

(⌊nα + γ⌋)_{n=1}^{∞} and (⌊nα′ + γ′⌋)_{n=1}^{∞}

partition the positive integers iff \frac{1}{α} + \frac{1}{α′} = 1, and \frac{γ}{α} + \frac{γ′}{α′} = 0. As mentioned in the Introduction, our technique yields simple proofs of several theorems of this sort. To date, however, Fraenkel’s Theorem has eluded the present techniques.

3. MAIN THEOREM

Let V_{I}(g) be the variation of g on the interval I, i.e.,

V_{(0,x)}(g) = sup_{\begin{matrix}n \\ 0<a_{1}<···<a_{n}<x \end{matrix}} ∑_{i=1}^{n−1} |g(a_{i+1}) − g(a_{i})|.

By a simple step function, we mean a step function defined on (0, ∞) whose discontinuities contain no limit point in (0, ∞). We use the notation

[[Q]] = \begin{cases}1 & Q is True; \\ 0 & Q is False, \end{cases}

extensively, and write f(x → r) for lim_{x→r} f(x).

Theorem 3.1 (Main Theorem). Let g(x, n) : ℝ^{+}×ℤ^{+} → ℂ, with each g( · , n) a simple step function, and ∑_{n=1}^{∞} V_{(0,x)}(g( · , n)) < ∞ for each x. Let D be any set containing {r : g( · , n) is not continuous at r for some n}. Suppose that α := ∑_{n=1}^{∞} g(r → 0, n) is finite. Then for x ∉ D,

∑_{n=1}^{∞} g(x, n) = α + ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r),  (1)

where f(r) := ∑_{n=1}^{∞} (g(x → r^{+}, n) − g(x → r^{−}, n)). If each g( · , n) is continuous from the left, then Eq. (1) holds for all x ∈ ℝ^{+}.

The reader may wish to keep the example g(x, n) = 2^{−⌊n/x⌋} in mind. For this example, we have D = ℚ, α = 0, and f(\frac{p}{q}) = \frac{1}{2^{q}−1}. The Main Theorem implies, in this example, that

∑_{n=1}^{∞} (\frac{1}{2})^{⌊n/x⌋} = ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{1}{2^{q} − 1}.

This example is looked at in substantially greater generality in Section 4.1.

Proof. Let D(n) be the set of discontinuities of g( · , n), so that ∪_{n=1}^{∞}D(n) ⊆ D. Define f(r, n) := g(x → r^{+}, n) − g(x → r^{−}, n), so that ∑_{n=1}^{∞} f(r, n) = f(r). Since g( · , n) is a simple step function, we have for x ∉ D(n)

g(x, n) = g(r → 0, n) + ∑_{\begin{matrix}0<r<x \\ r∈D(n) \end{matrix}} f(r, n),  (2)

and the summation is over a finite set. Eq. (2) holds for x ∈ D(n) also if g( · , n) is left continuous at x. If x ∉ D ⊇ ∪_{n=1}^{∞}D(n) (or if each g( · , n) is left continuous), then we may sum Eq. (2) over n ∈ ℤ^{+}, to get

∑_{n=1}^{∞} g(x, n) = ∑_{n=1}^{∞} g(r → 0, n) + ∑_{n=1}^{∞} ∑_{\begin{matrix}0<r<x \\ r∈D(n) \end{matrix}} f(r, n)

= α + ∑_{n=1}^{∞} ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r, n)  (3)

since if r ∉ D(n) then f(r, n) = 0. We use the hypothesis on the variation of g to justify rearranging this sum. To wit, we may rearrange terms because

∞ > ∑_{n=1}^{∞} V_{(0,x)}(g( · , n)) = ∑_{n=1}^{∞} ∑_{\begin{matrix}0<r<x \\ r∈D(n) \end{matrix}} |f(r, n)|

and we arrive at

∑_{n=1}^{∞} ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r, n) = ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} ∑_{n=1}^{∞} f(r, n) = ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r),

whence Eq. (3) reads

∑_{n=1}^{∞} g(x, n) = α + ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r).

4. SPECIAL SEQUENCES

In this section we conduct a more detailed analysis of several examples to which we may apply the Main Theorem. We will collect corollaries along the way. We provide full details for the first example only.

4.1. Beatty Sequences

Set g(x, n) := t^{n}z^{⌊n/x+a/b⌋}, with a ∈ ℤ, b ∈ ℤ^{+}, (a, b) = 1, 0 < |z| < 1, and |t| ≤ \frac{1}{|z|}.

The function K_{a/b}(z, x) := ∑_{n=1}^{∞} t^{n}z^{⌊n/x+a/b⌋} (pictured in Figure 1 with a/b = 1/2, z = 7/16, t = 1) has several exotic properties. If t, z > 0, then K_{a/b}(z, x) is strictly increasing. With t = 1, K_{a/b}(z, x) is a rational function of z if and only if x ∈ ℚ (for more along these lines, see Mordell (1965) [11] and Newman (1960) [12]). A simple ϵ-δ argument shows that K_{a/b}(z, x) is continuous only at irrational x. If t, z ∈ ℝ, the image of (0, ∞) has measure zero.

To apply the Main Theorem, we must bound the sum of the variations of g(x, n) and identify the set of discontinuities of g( · , n). After doing so, we will compute α := g(r → 0, n) and f(r) := ∑_{n=1}^{∞} f(r, n) := ∑_{n=1}^{∞} g(x → r^{+}, n) − g(x → r^{−}, n). We combine the calculations in Theorem 4.1 below.

We first bound the sum of the variations of the g(x, n) := t^{n}z^{⌊n/x+a/b⌋}. We have

V_{(0,x)}(g( · , n)) ≤ ∑_{i=⌊n/x+a/b⌋}^{∞} |t|^{n} |z^{i+1} − z^{i}|

= |t|^{n}|z − 1| ∑_{i=⌊n/x+a/b⌋}^{∞} |z|^{i}

= |t|^{n} \frac{|1 − z|}{1 − |z|}|z|^{⌊n/x+a/b⌋},

and so

∑_{n=1}^{∞} V_{(0,x)}(g( · , n)) ≤ ∑_{n=1}^{∞} |t|^{n} \frac{|1 − z|}{1 − |z|}|z|^{⌊n/x+a/b⌋}

≤ \frac{|1 − z|}{1 − |z|} ∑_{n=1}^{∞} |t|^{n}|z|^{n/x+a/b}

= \frac{|1 − z|}{1 − |z|}|z|^{a/b} \frac{|t| · |z|^{1/x}}{1 − |t| · |z|^{1/x}}  < ∞.

Clearly g(x, n) is not continuous at x = r iff \frac{n}{r} + \frac{a}{b} ∈ ℤ. This requires that r be rational; we take D := ℚ. Not that for each n, g( · , n) is continuous from the left. Thus the Main Theorem implies that

∑_{n=1}^{∞} t^{n}z^{⌊n/x+a/b⌋} = α + ∑_{\begin{matrix}0<r<x \\ r∈D \end{matrix}} f(r)

for all x ∈ ℝ^{+}.

We first show that α = 0, and then turn to finding a simple expression for f(r). Since ⌊\frac{n}{x} + \frac{a}{b}⌋ → ∞ as x → 0, we see that g(r → 0, n) = lim_{k→∞} t^{n}z^{k} = 0, since |z| < 1. Thus

α := ∑_{n=1}^{∞} g(r → 0, n) = 0.

Set, as in the proof of the Main Theorem, f(r, n) := g(x → r^{+}, n) − g(x → r^{−}, n). We need only concern ourselves with r ∈ D = ℚ, say r = \frac{p}{q} with (p, q) = 1. The function g(x, n) is continuous at r unless \frac{qn}{p} + \frac{a}{b} = \frac{qnb+ap}{bp} ∈ ℤ. From this we see that b|p. Replace p with bp, so that our condition is now \frac{qnb+abp}{bbp} = \frac{qn+ap}{bp} ∈ ℤ. We see now that p|n, so replace n with pj to make the condition \frac{qpj+ap}{bp} = \frac{qj+a}{b} ∈ ℤ. This gives

f(\frac{bp}{q}, pj) := g (x → (\frac{bp}{q})^{+} , pj) − g (x → (\frac{bp}{q})^{−} , pj)
= [[b|qj + a]]t^{pj} (z^{(pj/(bp/q))+a/b−1} − z^{pj/(bp/q)+a/b})
= [[b|qj + a]] (\frac{1}{z} − 1) z^{a/b} (t^{p}z^{q/b})^{j} .

We now give f(r) := ∑_{n=1}^{∞} f(r, n). Define M(q) to be the unique integer satisfying 1 ≤ M(q) ≤ b and M(q) ≡ −q^{−1}a (mod b), provided such an integer exists at all. Thus b|qj + a iff j = M(q) + bi for some i ≥ 0.

f(\frac{bp}{q}) := ∑_{n=1}^{∞} f(\frac{bp}{q}, n)

= ∑_{j=1}^{∞}[[b|qj + a]] (\frac{1}{z} − 1) z^{a/b} (t^{p}z^{q/b})^{j}

= z^{a/b} (\frac{1}{z} − 1) ∑_{i=0}^{∞} (t^{p}z^{q/b})^{M(q)+bi}

= z^{a/b} (\frac{1}{z} − 1) (t^{p}z^{q/b})^{M(q)} \frac{1}{1 − t^{bp}z^{q}} .

If r does not have the form \frac{bp}{q}, then f(r) = 0. Thus we only need M(q) to be defined when r = \frac{bp}{q}, with (bp, q) = 1. In this case, (b, q) = 1, and so the defining characteristic of M(q), “M(q) ≡ −q^{−1}a (mod b),” is satisfiable.

We have demonstrated Theorem 4.1.

Theorem 4.1. For all x > 0, a ∈ ℤ, b ∈ ℤ^{+}, (a, b) = 1, 0 < |z| < 1, |t| ≤ \frac{1}{|z|}

∑_{n=1}^{∞} t^{n}z^{⌊n/x+a/b⌋} = z^{a/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} <x \\ (bp,q)=1 \end{matrix}} \frac{(t^{p}z^{q/b})^{M(q)}}{1 − t^{bp}z^{q}} .

where M(q) satisfies 1 ≤ M(q) ≤ b and M(q) ≡ −q^{−1}a (mod b).

We now explore some of applications of Theorem 4.1.

4.1.1. The Lambert Series for Euler’s Totient Function Corollary 4.1 generalizes Theorem 309 of Hardy & Wright [10].

Corollary 4.1. If |z| < 1 and b ∈ ℤ^{+}, then

∑_{\begin{matrix}n=1 \\ (n,b)=1 \end{matrix}}^{∞} ϕ(n)\frac{z^{nM(n)}}{1 − z^{bn}} = \frac{b z^{b+1}}{(1 − z^{b})^{2}} + \frac{z}{1 − z^{b}} = \frac{z − (b − 1)z^{b+1}}{(1 − z^{b})^{2}} ,

where M(n) satisfies 1 ≤ M(n) ≤ b and M(n) ≡ n^{−1} (mod b).

To get Hardy & Wright’s Theorem 309 (∑_{n=1}^{∞} ϕ(n)\frac{z^{n}}{1−z^{n}} = \frac{z}{(1−z)^{2}} , the Lambert Series for Euler’s Totient Function), set b = 1, and note that then M(n) = 1 for all n.

Proof. Applying Theorem 4.1 with x = b, t = 1, a = b − 1, we may write

∑_{n=1}^{∞} z^{⌊(n+b−1)/b⌋} = z^{(b−1)/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} <b \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q}} .  (4)

Since kb < n ≤ (k + 1)b implies that ⌊\frac{n+b−1}{b}⌋ = k + 1, the left-hand-side of Eq. (4) becomes

∑_{n=1}^{∞} z^{⌊(n+b−1)/b⌋} = b\frac{z}{1 − z} .

For q ≥ 2 the number of p with 0 < \frac{bp}{q} < b and (bp, q) = 1 is ϕ(q)[[(b, q) = 1]]. The right-hand-side of Eq. (4) becomes

z^{(b−1)/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} <b \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q}} = z^{−1/b}(1−z) ∑_{q=2}^{∞} ϕ(q)[[(b, q) = 1]]\frac{(z^{q/b})^{M(q)}}{1 − z^{q}}

Now replace z with z^{b}, and solve for the summation to get

∑_{q=2}^{∞} ϕ(q)[[(b, q) = 1]]\frac{z^{qM(q)}}{1 − z^{bq}} = \frac{b z^{b+1}}{(1 − z^{b})^{2}} .

Include the q = 1 term to finish the proof of Corollary 4.1.

4.1.2. The Rayleigh-Beatty Theorem

The m = 1 case of the following Theorem 4.2 is usually known as “Beatty’s Theorem”, but was known to Lord Rayleigh earlier (see [13], Section 92). The essential fact of this proof is that the rationals in (0, m) are centrally symmetric, and that this symmetry preserves denominators.

Theorem 4.2. Let α, β be positive reals. Then each positive integer occurs exactly m ∈ ℤ^{+} times (altogether) in the sequences (⌊nα⌋)_{n=1}^{∞}, (⌊nβ⌋)_{n=1}^{∞} iff α ∉ ℚ and \frac{1}{α} + \frac{1}{β} = m.

Proof. Density considerations imply the “only if” direction.

The conclusion of the “if” direction is equivalent to

∑_{n=1}^{∞} z^{⌊nα⌋} + ∑_{n=1}^{∞} z^{⌊nβ⌋} = m\frac{z}{1 − z} .

Set x := \frac{1}{α} and y := \frac{1}{β}, so that x + y = m, and both x and y are irrational. Then

∑_{n=1}^{∞} z^{⌊nα⌋} + ∑_{n=1}^{∞} z^{⌊nβ⌋} = ∑_{n=1}^{∞} z^{⌊n/x⌋} + ∑_{n=1}^{∞} z^{⌊n/y⌋}

= (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}} + (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <y \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

= (\frac{1}{z} − 1) ( ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} + ∑_{\begin{matrix}0< \frac{p}{q} <y \\ (p,q)=1 \end{matrix}}) (\frac{z^{q}}{1 − z^{q}} )

Using the map \frac{p}{q} ↦ m − \frac{p}{q} = \frac{mq−p}{q}, the summation operator, as applied to the summand \frac{z^{q}}{1−z^{q}}, satisfies

∑_{\begin{matrix}0< \frac{p}{q} <y \\ (p,q)=1 \end{matrix}} = ∑_{\begin{matrix}m−y< \frac{mq−p}{q} <m \\ (p,q)=1 \end{matrix}} = ∑_{\begin{matrix}x< \frac{p}{q} <m \\ (p,q)=1 \end{matrix}}

GENERATING FUNCTIONS FOR STEP SEQUENCES 13

since \frac{z^{q}}{1−z^{q}} depends only on q. We have used the equalities (mq − p, q) = (p, q) and m − y = x. Since x is irrational,

∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} + ∑_{\begin{matrix}0< \frac{p}{q} <y \\ (p,q)=1 \end{matrix}} = ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} + ∑_{\begin{matrix}x< \frac{p}{q} <m \\ (p,q)=1 \end{matrix}} = ∑_{\begin{matrix}0< \frac{p}{q} <m \\ (p,q)=1 \end{matrix}}

and so

∑_{n=1}^{∞} z^{⌊nα⌋} + ∑_{n=1}^{∞} z^{⌊nβ⌋} = (\frac{1}{z} − 1) ( ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} + ∑_{\begin{matrix}0< \frac{p}{q} <y \\ (p,q)=1 \end{matrix}}) (\frac{z^{q}}{1 − z^{q}} )

= (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <m \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

= ∑_{n=1}^{∞} z^{⌊n/m⌋} = m\frac{z}{1 − z} .

4.1.3. Fourier Expansion Set t = 1, and consider

K_{a/b}(z, x) := ∑_{n=1}^{∞} z^{⌊n/x+a/b⌋} = z^{a/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} <x \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q/b}}

as a function of x. If 0 < \frac{bp}{q} < x with (bp, q) = 1, then b < b + \frac{bp}{q} = \frac{b(q+p)}{q} < b + x and (b(q + p), q) = 1. Thus

∑_{\begin{matrix}0< \frac{bp}{q} <x \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q/b}} = ∑_{\begin{matrix}b< \frac{bp}{q} <b+x \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q/b}} .

This means that for 0 < x ∉ ℚ

K_{a/b}(z, x + b) − K_{a/b}(z, x) = z^{a/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}x< \frac{bp}{q} <b+x \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q/b}}

= z^{a/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} <b \\ (bp,q)=1 \end{matrix}} \frac{(z^{q/b})^{M(q)}}{1 − z^{q/b}}

which is independent of x!

Hence for x > b, K_{a/b}(z, x)−K_{a/b}(z, b⌊\frac{x}{b}⌋) is a periodic function of x with period b, and we can compute a Fourier Series expression for K_{a/b}(z, x).

While we can compute the Fourier Series of K(x) for general a and b, the algebra is substantial and the final expression is quite involved. For a = 0, b = 1, both the computation and result are more elegant.

For the remainder of this section, we will work with γ = 0 and z will not vary. When this is the case, we drop them from our notation. The discontinuities of

K(x) := K_{0}(z, x) = ∑_{n=1}^{∞} z^{⌊n/x⌋} = (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

are a set of measure zero (the rationals), and so are not relevant to computing the Fourier Series. Assume in what follows, therefore, that x is irrational.

The periodic part of K(x) is

K(\{x\}) = (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <\{x\} \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}} = (\frac{1}{z} − 1) ∑_{\begin{matrix}⌊x⌋< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}} .

We first compute the drift term K(x) − K({x}). If x < 1, then obviously K(x) − K(\{x\}) = ⌊x⌋\frac{1}{1−z}. If x ≥ 1, then

K(x) − K(\{x\}) = (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}} − (\frac{1}{z} − 1) ∑_{\begin{matrix}⌊x⌋< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

= (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} ≤⌊x⌋ \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

= (\frac{1}{z} − 1) \frac{z^{1}}{1−z^{1}} + (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <⌊x⌋ \\ (p,q)=1 \end{matrix}} \frac{z^{q}}{1 − z^{q}}

= 1 + K(⌊x⌋)

= 1 + ∑_{n=1}^{∞} z^{⌊n/⌊x⌋⌋}

= 1 + ∑_{k=0}^{∞} #\{n ≥ 1 : k ≤ \frac{n}{⌊x⌋} < k + 1\}z^{k}

= 1 + ∑_{k=0}^{∞} (⌊x⌋ − [[k = 0]]) z^{k}

= ⌊x⌋\frac{1}{1−z}

We now need to compute K({x}) as a Fourier Series. We write K({x}) = ∑_{j=−∞}^{∞} a_{j}e(jx), where e(x) = e^{2π\sqrt{−1}x} as usual.

Define d_{n}(x) to be the number of positive multiples of \frac{1}{x} in the interval [n, n + 1), so that K(x) = ∑_{n=0}^{∞} d_{n}(x)z^{n}. We observe that d_{0}({x}) = 0, and that more generally d_{n}({x}) = ∑_{k=1}^{n} χ_{(k/(n+1),k/n]}({x}), a sum of characteristic functions of the intervals (\frac{k}{n+1}, \frac{k}{n}].

We have

a_{−j} = ∫_{0}^{1} K(x)e(j x) dx = ∫_{0}^{1} ∑_{n=1}^{∞} d_{n}(x)z^{n}e(j x) dx

= ∑_{n=1}^{∞} z^{n} ∫_{0}^{1} d_{n}(x)e(j x) dx = ∑_{n=1}^{∞} z^{n} ∑_{k=1}^{n} ∫_{k/(n+1)}^{k/n} e(j x) dx

From this point we need a separate analysis for j = 0.

a_{0} = ∑_{n=1}^{∞} z^{n} ∑_{k=1}^{n} ∫_{k/(n+1)}^{k/n} 1 dx = ∑_{n=1}^{∞} z^{n} (\frac{1}{n} − \frac{1}{n + 1}) ∑_{k=1}^{n} k

= ∑_{n=1}^{∞} \frac{1}{2}z^{n} = \frac{z}{2(1 − z)}

For j ≠ 0 we will need to evaluate the geometric sums ∑_{k=1}^{n} e(\frac{j k}{n}) = n [[n|j]] and ∑_{k=1}^{n} e(\frac{j k}{n+1}) = (n + 1) [[n + 1|j]] − 1.

Now, writing σ_{z}(j) := ∑_{n|j} nz^{n}

a_{−j} = ∑_{n=1}^{∞} z^{n} ∑_{k=1}^{n} \frac{1}{2πij} (e(\frac{j k}{n}) − e(\frac{j k}{n+1}))

= \frac{−i}{2πj} ∑_{n=1}^{∞} z^{n} (n[[n|j]] − (n + 1) [[n + 1|j]] + 1)

= \frac{−i}{2πj} (σ_{z}(j) − (\frac{1}{z}σ_{z}(j) − 1) + \frac{z}{1 − z} )

= \frac{−i}{2πj} (\frac{1}{1 − z} − (\frac{1 − z}{z} ) σ_{z}(j)) .

Since

a_{j} e(j x) + a_{−j} e(−j x) = \frac{−1}{πj} (\frac{1}{1 − z} − (\frac{1 − z}{z} ) σ_{z}(j)) sin(2πjx)

and \frac{1}{π} ∑_{j=1}^{∞} \frac{1}{j} sin(2πjx) = \frac{1}{2} − \{x\} we have

K(\{x\}) = \frac{z}{2(1 − z)} − \frac{1}{π} ∑_{j=1}^{∞} \frac{1}{j} (\frac{1}{1 − z} − (\frac{1 − z}{z} ) σ_{z}(j)) sin(2πj x)

= \frac{\{x\}}{1 − z} − \frac{1}{2} + \frac{1}{π} \frac{1 − z}{z} ∑_{j=1}^{∞} \frac{σ_{z}(j)}{j} sin(2πjx).

The Fourier Series converges where K(x) := ∑_{n=1}^{∞} z^{⌊n/x⌋} is continuous, i.e., at irrational x, and averages the left and right limits where K(x) is not continuous. We have shown

Theorem 4.3. K(x) := ∑_{n=1}^{∞} z^{⌊n/x⌋} with 0 ≠ |z| < 1 satisfies

\frac{1}{2} (K(y → x^{−}) + K(y → x^{+})) = \frac{x}{1 − z} − \frac{1}{2} + \frac{1}{π} \frac{1 − z}{z} ∑_{j=1}^{∞} \frac{σ_{z}(j)}{j} sin(2πjx).

This theorem can be used to gain information about the arithmetic function σ_{z}(n).

Corollary 4.2. If |z| < 1 then

∑_{n=0}^{∞}(−1)^{n} \frac{σ_{z}(2n + 1)}{2n + 1} = \frac{π}{4} \frac{z}{1 + z^{2}} .

Proof. We can use the definition of K(x) to compute the left and right limits: K(y → (\frac{1}{4})^{−}) = ∑_{n=1}^{∞} z^{4n} = \frac{z^{4}}{1−z^{4}} and K(y → (\frac{1}{4})^{+}) = ∑_{n=1}^{∞} z^{4n−1} = \frac{z^{3}}{1−z^{4}} . The left-hand-side of Theorem 4.3 is \frac{1}{2} \frac{z^{4}+z^{3}}{1−z^{4}} .

Since sin(2πn\frac{1}{4}) = 0 if n is even, 1 if n ≡ 1 mod 4, and −1 if n ≡ 3 mod 4, the summation ∑_{n=1}^{∞}(σ_{z}(n)/n) sin(2πn x) simplifies to ∑_{n=0}^{∞}(−1)^{n}σ_{z}(2n+ 1)/(2n + 1).

Theorem 4.3 is now

\frac{1}{2} \frac{z^{4} + z^{3}}{1 − z^{4}} = \frac{1}{1 − z} − \frac{1}{2} + \frac{1}{π} \frac{1 − z}{z} ∑_{n=0}^{∞}(−1)^{n} \frac{σ_{z}(2n + 1)}{2n + 1},

which can be rearranged to give the corollary.

Corollary 4.2 can be used to compute rational approximations to π, although it is exceptionally poor for such purposes. Using the first 5 terms of the sum and taking z → \frac{1}{2} (the optimal choice), we get π ≈ \frac{57983}{16128} ≈ 3.60. The first 10000 terms give only π ≈ 3.1413.

4.1.4. Integrals

In computing the Fourier Series of K(x) := ∑_{n=1}^{∞} z^{⌊n/x⌋}, we computed the integral ∫_{0}^{1} K(x)e^{2πijx} dx for each integer j. There are other integrals involving K(x) which we can compute.

Consider the integral A := ∫_{0}^{1} K(x) dx. If we use the transformation x → 1 − x, we see that A = ∫_{0}^{1} K(1 − x) dx. Adding these gives 2A = ∫_{0}^{1} (K(x) + K(1 − x)) dx = ∫_{0}^{1} K(1) dx = \frac{z}{1−z}, as \frac{1}{x} and \frac{1}{1−x} satisfy the hypotheses of Beatty’s Theorem (at least on the irrationals, a set of full measure). Thus ∫_{0}^{1} K(x) dx = \frac{z}{2(1−z)}.

The above integral can also be computed by substituting K(x) = ∑_{n=0}^{∞} d_{n}(x)z^{n} and juggling the summations and integrals as was done in the computation of the Fourier coefficients. In fact, we can also compute:

∫_{0}^{1} x^{2}K(x) dx = \frac{1 + 2z}{12(1 − z)} + \frac{1 − z}{12z} ln(1 − z)
∫_{0}^{1} xK(x) dx = \frac{1 + 3z}{12(1 − z)} + \frac{1 − z}{12z} ln(1 − z)
∫_{0}^{1} K(x) dx = \frac{1}{2} \frac{z}{1 − z}
∫_{0}^{1} \frac{K(x)}{x} dx = ∑_{n=1}^{∞} z^{n} ln ((1 + \frac{1}{n})^{n})
∫_{0}^{1} \frac{K(x)}{x^{2}} dx = \frac{ln(1 − z)}{z − 1}

With z = \frac{1}{2}, we get

∫_{0}^{1} \frac{K(x)}{x^{3}} dx = 6 ln 2 − \frac{3}{2}(ln 2)^{2} + \frac{π^{2}}{4} .

4.1.5. Expansions of Borwein & Borwein

In (1993) [3], “On the Generating Function of the Integer Part: [nα+γ],” the generating functions

G_{α,γ}(t, z) := ∑_{n=1}^{∞} t^{n}z^{⌊nα+γ⌋}; F_{α,γ}(t, z) := ∑_{n=1}^{∞} t^{n} ∑_{m=1}^{⌊nα+γ⌋} z^{m}

are analyzed. Assuming that nα + γ is never an integer and that all sums converge absolutely, they show (for p_{n}/q_{n} a convergent to α, and particular integers s_{n}, r_{n})

G_{α,γ}(t, z) = \frac{t}{1 − t} + \frac{1 − z}{z} ∑_{n=0}^{∞} \frac{(−1)^{n+1}t^{r_{n}}z^{s_{n}}}{(1 − t^{q_{n}}z^{p_{n}})(1 − t^{q_{n+1}}z^{p_{n+1}})}

F_{α,γ}(t, z) = ∑_{n=0}^{∞} \frac{(−1)^{n+1}t^{r_{n}}z^{s_{n}}}{(1 − t^{q_{n}}z^{p_{n}})(1 − t^{q_{n+1}}z^{p_{n+1}})}.

These are used to demonstrate that

(\frac{1 − z}{z} ) ∑_{n=1}^{∞} t^{n}z^{⌊nα⌋} = \frac{1}{T_{0} + _{\frac{1}{T_{1}+ \frac{1}{T_{2}+...}}}} ,

where

T_{0} := (\frac{z}{1 − z} ) (\frac{1}{tz^{a_{0}}} − 1)

and

T_{n} := \frac{1}{t^{q_{n−2}}z^{p_{n−2}}} \frac{⌊(t^{q_{n−1}}z^{p_{n−1}})^{−a_{n}}⌋ − 1}{⌊(t^{q_{n−1}}z^{p_{n−1}})^{−1}⌋ − 1}

with a_{n} the partial quotients and p_{n}/q_{n} the convergents to α.

To these expansions, our Main Theorem adds

G_{α,a/b}(t, z) = z^{a/b} (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{bp}{q} < \frac{1}{α} \\ (bp,q)=1 \end{matrix}} \frac{(t^{p}z^{q/b})^{M(q)}}{1 − t^{bp}z^{q}}

F_{α,a/b}(t, z) = \frac{tz}{(1 − t)(1 − z)} − z^{a/b} ∑_{\begin{matrix}0< \frac{bp}{q} < \frac{1}{α} \\ (bp,q)=1 \end{matrix}} \frac{(t^{p}z^{q/b})^{M(q)}}{1 − t^{bp}z^{q}}

where M(q) satisfies 1 ≤ M(q) ≤ b and M ≡ −q^{−1}a (mod b).

This forces the duality relation

\frac{z}{1 − z} G_{α,γ}(t, z) + F_{α,γ}(t, z) = \frac{tz}{(1 − t)(1 − z)},

which [3] leans upon heavily, to our attention. This duality relation and the functional equation

F_{α,γ}(t, z) + F_{α^{−1},−γα^{−1}}(z, t) = \frac{tz}{(1 − t)(1 − z)}

are combined to give a new proof of a theorem of Fraenkel: for α > 0 irrational, the sequences (⌊nα + γ⌋)_{n=1}^{∞} and (⌊nα′ + γ′⌋)_{n=1}^{∞} partition the positive integers if and only if \frac{1}{α} + \frac{1}{α′} = 1, γ ∈ [0, 1), and \frac{γ}{α} + \frac{γ′}{α′} = 0.

The techniques in this paper do not seem to yield the functional equation (which is proved directly in [3] by noting that either 1 ≤ m ≤ ⌊nα + γ⌋ or 1 ≤ n ≤ ⌊(m − γ)/α⌋ and not both), or results such as Fraenkel’s Theorem that depend on the functional equation, because one of γ, −γα^{−1} must be irrational. Our Main Theorem still applies, but the set D and the function f(r) are too complicated to be very useful.

4.2. Dirichlet Series

Let ζ(z, a) := ∑_{n=0}^{∞}(n + a)^{−z} be the Hurwitz Zeta Function. The Riemann zeta function is given by ζ(z) := ζ(z, 1). Our Main Theorem applied to g(x, n) := ⌊\frac{n}{x} + k⌋^{−z}, with k ∈ ℤ^{+} gives

Theorem 4.4. Let z have real part ℜ(z) > 1, 0 < x ∈ ℝ, and k ∈ ℤ^{+}. Then

∑_{n=1}^{∞}⌊\frac{n}{x} + k⌋^{−z} = ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} q^{−z} (ζ(z, 1 + \frac{k−1}{q}) − ζ(z, 1 + \frac{k}{q})) .

This theorem serves as well as Theorem 4.1 in our proof of the Rayleigh-Beatty Theorem, where the requirements is only that summand depends on q and not p.

Setting x = k = 1 and including the q = 1 term gives the novel equation

Corollary 4.3. If ℜ(z) > 1 then

1 = ∑_{q=1}^{∞} \frac{ϕ(q)}{q^{z}} \frac{ζ(z) − ζ(z, 1 + \frac{1}{q})}{ζ(z)}.

Note that the left-hand-side does not depend on z.

4.3. Difference Beatty Sequences

We can also use our Main Theorem to study sequences such as (⌊anα⌋ − ⌊bnα⌋)_{n=1}^{∞} (with a, b ∈ ℤ and a > b > 0).

Theorem 4.5. Suppose that |z| < 1, x > 0 irrational, and a > b > 0 are integers. Then

∑_{n=1}^{∞} z^{⌊an/x⌋−⌊bn/x⌋} = (\frac{1}{z} − 1) ∑_{\begin{matrix}0< \frac{p}{q} <x \\ (p,q)=1 \end{matrix}} \frac{R(a, b, p, q)}{1 − z^{(a−b)q}},

where R(a, b, p, q) is defined by

R(a, b, p, q) := ∑_{j=1}^{(p,a)−1} z^{⌊ \frac{q(a−b)j}{(p,a)} ⌋} − z ∑_{j=1}^{(p,b)−1} z^{⌊ \frac{q(a−b)j}{(p,b)} ⌋}.

Note that R(a, b, p, q) is a polynomial in z, and in particular that if (p, a) = (p, b) = 1, then R(a, b, p, q) = 0.

In deriving Theorem 4.5 from the Main Theorem, one sets g(x, n) = z^{⌊an/x⌋−⌊bn/x⌋}. If g( · , n) is not continuous at r, then either \frac{an}{r} ∈ ℤ or \frac{bn}{r} ∈ ℤ. The reader is reminded that D need only be a superset of the set of discontinuities of the g( · , n); we may take D := ℚ. As g( · , n) may be left-continuous at some points and right-continuous at others (and possibly neither), we must restrict our attention to x ∉ D, i.e., to irrational x.

We find—as in earlier examples—that α = 0. Finding

f(r) = (\frac{1}{z} − 1) \frac{R(a, b, p, q)}{1 − z^{(a−b)q}}

is more involved than in the earlier examples, but still involves only routine manipulations.

4.3.1. A New Beatty-Type Theorem

Theorem 4.6. Let S(x) = (⌊2nx⌋ − ⌊nx⌋)_{n=1}^{∞}, and suppose that α > 0. Then, as multisets,

S(α) ∪ S(β) = S(1) ∪ S(\frac{α}{2}) ⇔ α ∉ ℚ and \frac{1}{α} + \frac{1}{β} = 1 + \frac{1}{α/2}.

We attack Theorem 4.6 much as we attacked Theorem 4.2. Density considerations give the “⇒” implication. On the other hand, S(α)∪S(β) = S(1) ∪ S(\frac{α}{2}) only if

∑ z^{⌊2nα⌋−⌊nα⌋} + ∑ z^{⌊2nβ⌋−⌊nβ⌋} = ∑ z^{⌊2n⌋−⌊n⌋} + ∑ z^{⌊2nα/2⌋−⌊nα/2⌋}.

If suffices, by Theorem 4.5, to prove that

∑_{r∈D∩(0,1/α)} f(r) + ∑_{r∈D∩(0,1/β)} f(r) = ∑_{r∈D∩(0,1)} f(r) + ∑_{r∈D∩(0,1/(α/2))} f(r),

where f(r) = 0 unless r = \frac{2p}{q} with (2p, q) = 1, and f(\frac{2p}{q}) does not depend on p. At this point we see that Theorem 4.6 hinges on counting the rationals with even numerator and odd denominator in the intervals (0, \frac{1}{α}), (0, \frac{1}{β}), (0, 1), and (0, \frac{1}{α/2}). In the proof of Theorem 4.2 this counting was handled by a simple bijection. Since the intervals concerned here are more complicated, we must be content with a more involved counting argument.

Proof. Set x := \frac{1}{α} and y := \frac{1}{β}. Density considerations demand that, if S(α) ∪ S(β) = S(1) ∪ S(\frac{α}{2}), then x + y = \frac{1}{α} + \frac{1}{β} = 1 + \frac{1}{α/2} = 1 + \frac{x}{2}. We assume in what follows that x + y = 1 + \frac{x}{2}, i.e., y = 1 − \frac{x}{2}.

First, observe that for any v ∈ ℝ and k ∈ ℤ,

⌊2v⌋ − ⌊v⌋ = −⌊\frac{1}{2} − v⌋ = k − ⌊k + \frac{1}{2} − v⌋.

Replace v ↦ \frac{x}{4}q and k ↦ \frac{q−1}{2} = ⌊\frac{1}{2}q⌋ to get

⌊\frac{x}{2}q⌋ − ⌊\frac{x}{4}q⌋ = ⌊\frac{1}{2}q⌋ − ⌊\frac{q−1}{2} + \frac{1}{2} − \frac{x}{4}q⌋ = ⌊\frac{1}{2}q⌋ − ⌊(\frac{1}{2} − \frac{x}{4}) q⌋.

Since x is irrational, we may write this as

⌊\frac{x}{2}q⌋ − ⌈\frac{x}{4}q⌉ + 1 = ⌊\frac{q}{2}⌋ − ⌈(\frac{1}{2} − \frac{x}{4}) q⌉ + 1  (5)

Eq. (5) gives us the middle equality in

\begin{aligned}|\{p ∈ ℤ : \frac{x}{2} < \frac{2p}{q} < x\}| & = |\{p ∈ ℤ : \frac{x}{4}q < p < \frac{x}{2}q\}| \\ & = |\{p ∈ ℤ : (\frac{1}{2} − \frac{x}{4}) q < p < \frac{1}{2}q\}| \\ & = |\{p ∈ ℤ : (1 − \frac{x}{2}) < \frac{2p}{q} < 1\}|. \end{aligned}  (6)

Set

A_{q} = \{p ∈ ℤ : \frac{x}{2} < \frac{2p}{q} < x, (2p, q) = 1\}

and

B_{q} = \{p ∈ ℤ : 1 − \frac{x}{2} < \frac{2p}{q} < 1, (2p, q) = 1\}.

Since (2p, 1) = 1, Eq. 6 above shows that |A_{1}| = |B_{1}|. We now proceed by induction to show for q odd that |A_{q}| = |B_{q}|. Note that the cardinalities of A_{q} and B_{q} are the same as those of

A_{q}^{∗} = \{\frac{2p}{q} : \frac{x}{2} < \frac{2p}{q} < x, (2p, q) = 1\}

and

B_{q}^{∗} = \{\frac{2p}{q} : 1 − \frac{x}{2} < \frac{2p}{q} < x, (2p, q) = 1\} .

Moreover, if s and t are distinct odd numbers, then A_{s}^{∗} and A_{t}^{∗} are disjoint, and so are B_{s}^{∗} and B_{t}^{∗}. Now we have

|A_{d}| = |A_{d}^{∗}| = |B_{d}| = |B_{d}^{∗}|

for d < q, d odd, by the induction hypothesis. Hence

|\{\frac{2p}{q} : \frac{x}{2} < \frac{2p}{q} < x\}| = |⋃_{d|q} A_{d}^{∗}| = ∑_{d|q} |A_{d}^{∗}| = ∑_{d|q} |A_{d}|

= |A_{q}| − |B_{q}| + ∑_{d|q} |B_{d}| = |A_{q}| − |B_{q}| + |∪_{d|q}B_{d}^{∗}|

= |A_{q}| − |B_{q}| + |\{\frac{2p}{q} : 1 − \frac{x}{2} < \frac{2p}{q} < x\}| (7)

Combining Eq. 6 with Eq. 7, we find |A_{q}| = |B_{q}|, completing the induction.

Thus, defining f(q) = (\frac{1}{z} − 1) R(2, 1, 2p, q)/ (1 − z^{q}) = \frac{1}{z} \frac{1−z}{1−z^{q}} z^{⌊q/2⌋}, we have

∑_{\begin{matrix}\frac{x}{2} < \frac{2p}{q} <x \\ (2p,q)=1 \end{matrix}} f(q) = ∑_{\begin{matrix}q=1 \\ q odd \end{matrix}}^{∞} |A_{q}^{∗}|f(q) = ∑_{\begin{matrix}q=1 \\ q odd \end{matrix}}^{∞} |B_{q}^{∗}|f(q) = ∑_{\begin{matrix}1− \frac{x}{2} < \frac{2p}{q} <1 \\ (2p,q)=1 \end{matrix}} f(q). (8)

Since x is irrational, (\frac{x}{2}, x)∩ℚ = ((0, x) \ (0, \frac{x}{2}))∩ℚ and (1− \frac{x}{2}, 1)∩ℚ = ((0, 1) \ (0, 1 − \frac{x}{2})) ∩ ℚ. Thus Eq. 8 implies

∑_{\begin{matrix}0< \frac{2p}{q} <x \\ (2p,q)=1 \end{matrix}} f(q) − ∑_{\begin{matrix}0< \frac{2p}{q} < \frac{x}{2} \\ (2p,q)=1 \end{matrix}} f(q) = ∑_{\begin{matrix}0< \frac{2p}{q} <1 \\ (2p,q)=1 \end{matrix}} f(q) − ∑_{\begin{matrix}0< \frac{2p}{q} <1− \frac{x}{2} \\ (2p,q)=1 \end{matrix}} f(q). (9)

Now, Theorem 4.5 reads, with a = 2, b = 1:

G(x) := ∑_{n=1}^{∞} z^{⌊2n/x⌋−⌊n/x⌋} = ∑_{\begin{matrix}0< \frac{2p}{q} <x \\ (2p,q)=1 \end{matrix}} f(q).

Since y = 1 − \frac{x}{2}, Eq. (9) can be written as G(x) − G(\frac{x}{2}) = G(1) − G(y), whence S(α) ∪ S(β) = S(\frac{1}{x}) ∪ S(\frac{1}{y}) = S(1) ∪ S(\frac{1}{x/2}) = S(1) ∪ S(\frac{α}{2}).

REFERENCES

1. Bagchi, Amitava & Reingold, Edward M., A Naturally Occurring Function Continuous Only at Irrationals, The American Mathematical Monthly 89(6) (1982), 411-417. MR84b:26002.

2. Böhmer, P. E., Über die Transzendenz Gewisser Dyadischer Brüche, Mathematische Annalen 96 (1927), 367-377.

3. Borwein, J. M. & Borwein, P. B., On the Generating Function of the Integer Part: [nα + γ], Journal of Number Theory 43(3) (1993), 293-318. MR94i:11044.

4. Bowman, D., A New Generalization of Davison’s Theorem, Fibonacci Quarterly 26 (1988), no. 1, 40-45. MR89c:11016.

5. Brown, T.C., Descriptions of the Characteristic Sequence of an Irrational. Canad. Math. Bull., 36(1):15–21, 1993. MR94g:11051.

6. Erdős, P. & Faudree, R. & Győri, E., On the Book Size of Graphs with Large Minimum Degree, Studia Sci. Math. Hungar. 30(1-2) (1995), 25-46. MR96f:05135.

7. Fraenkel, A. S, The Bracket Function and Complementary Sets of Integers, Canad. J. Math. 21(1) (1969), 6-27. MR38#3214.

8. Fraenkel, Aviezri S., Iterated Floor Function, Algebraic Numbers, Discrete Chaos, Beatty Subsequences, Semigroups. Trans. Amer. Math. Soc. 341(2) (1994), 639-664. MR94d:11011.

9. Fraenkel, A. S. & Mushkin, M. & Tassa, U., Determination of [nθ] by Its Sequence of Differences, Canadian Math. Bull. 21(4) (1978), 441-446. MR80d:10051.

10. Hardy, G. H. & Wright, E. M., An Introduction to the Theory of Numbers, 5th ed., Oxford University Press Inc., New York, 1996. MR81i:10002.

11. Mordell, L. J., Irrational Power Series II. Acta Arith. 11(2) (1965), 181-188. MR32#1186a.

12. Newman, Morris, Irrational Power Series. Proc Amer. Math. Soc. 11(5) (1960), 699-702. MR22#9483.

13. Rayleigh, John William Strutt, Third Baron, The Theory of Sound, Vol. 1, 2nd ed., Macmillan and Co., London, 1894, pp 122-123.

14. Stolarsky, Kenneth B., Certain Sequences of Wythoffian Matrices and Maximal Geometric Progressions Therein. J. Combin. Theory. Ser. A. 68 (1994), 361-371. MR95k:11029.

15. Stolarsky, Kenneth B. & Porta, Horacio, Half-silvered Mirrors and Wythoff’s Game, Canad. Math. Bull. 33(1), (1990), 119-125. MR91b:11019.