Asymptotics

of some number theoretic functions and an application

to the growth of nilpotent groups

Inaugural–Dissertation

zur

Erlangung des Doktorgrades

der

Hohen Mathematisch–Naturwissenschaftlichen Fakultät

der

Rheinischen Friedrich–Wilhelms–Universität zu Bonn

vorgelegt von Michael Stoll aus Bonn

Referent:  Prof. Fritz Grunewald
Korreferent: Prof. Werner Ballmann

Bonn 1993

CONTENTS 1

Contents

Notations 2 1 Introduction 3 2 Ψ–functions 12 3 Approximating Ψ near a rational point 19

3.1 Some simple facts and definitions . . . . . . . . . . . . . . . . 20 3.2 Rewriting Ψ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Describing g_{1,γ} . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 The relevant set of parameters—describing \overline{f}_{1,γ} . . . . . . . . 29 3.5 An important estimate . . . . . . . . . . . . . . . . . . . . . . 34 3.6 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4 Ψ_{a,b}(μ, ·) converges to a constant 38 5 Proof of Theorem 4.2 41

5.1 A convergence result . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 A number theoretic equidistribution property . . . . . . . . . 43 5.3 Application to some sums . . . . . . . . . . . . . . . . . . . . 47 5.4 End of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6 Dependence on a and b 51 7 Ψ–functions with non-constant a and b 54 8 Computing C(1, 1) 56 9 Suggestions for further work 62 A Appendix: Distributions on T 64 B Appendix: Some number theoretic estimates 66

Notations

ℕ  the set of natural numbers, {0, 1, 2, …}
ℤ  the ring of integers
ℝ  the field of real numbers
ℝ_{+}  the set of positive real numbers, {x ∈ ℝ | x > 0}
ℂ  the field of complex numbers
n ⊥ m  n and m are coprime
n ⊓ m  the greatest common divisor of n and m
[a, b]  closed interval, {x ∈ ℝ | a ≤ x ≤ b}
[a, b[  half-open interval, {x ∈ ℝ | a ≤ x < b}
]a, b]  half-open interval, {x ∈ ℝ | a < x ≤ b}
]a, b[  open interval, {x ∈ ℝ | a < x < b}
⌊x⌋  floor function, max{ν ∈ ℤ | ν ≤ x}
⌈x⌉  ceiling function, min{ν ∈ ℤ | ν ≥ x}
s(x)  saw-tooth function, min{|x − ν| | ν ∈ ℤ}
μ(n)  Möbius function, ∑_{n≥1} μ(n)n^{−s} = 1/ζ(s)
C^{∞}(Ω)  infinitely differentiable functions on Ω

D(Ω) test functions on Ω, infinitely differentiable functions with compact support

D′(Ω)  space of distributions on Ω, dual space of D(Ω)
⟨T, ϕ⟩  application of T ∈ D′(Ω) to ϕ ∈ D(Ω)
ϕ̂, T̂  Fourier transform of ϕ ∈ D(Ω) or T ∈ D′(Ω)
χ_{S}  characteristic function of the set S,

χ_{S}(x) = \{ \begin{matrix}1 , if & x ∈ S \\ 0 , if & x ∉ S \end{matrix}

O(f(x)) a function of x, bounded by Cf(x) with some C > 0 for x → 0 or x → ∞ (depending on context)

o(f(x)) a function g(x) such that g(x)/f(x) → 0 as x → 0 or x → ∞ (depending on context)

f(x) ≪ g(x)  equivalent to f(x) = o(g(x))
f(x) ≫ g(x)  the same as g(x) ≪ f(x)
B(α, β)  Beta function, B(α, β) = Γ(α)Γ(β)/Γ(α + β)

1 Introduction

Consider the following problem: Let T (n) = the number of lattice points in the union of the symmetric rectangles [−ab, ab] × [−ac, ac], where a, b, c are natural numbers with a + b + c = n. That is, let

R(n) = ⋃{[−ab, ab] × [−ac, ac] | a, b, c ∈ ℕ, a + b + c = n}

and define

T (n) = #(R(n) ∩ ℤ^{2}) .

What can be said about T (n)?

Before considering this problem, we will briefly explain where it comes from.

Consider a group G with some finite system of generators S, where for ease of notation we will assume that S is symmetric, that is, if x ∈ S, then x^{−1} ∈ S, too. Then we may count the elements of G that can be obtained as a product of at most n elements of S, for n ∈ ℕ:

γ_{G,S}(n) = #B_{S}(n) ,

where

B_{S}(n) = {s_{1} ⋯ s_{m} | m ≤ n, s_{1}, …, s_{m} ∈ S} .

γ_{G,S} is called the growth function of G w.r.t. S (for more information see e.g. [10]). It turns out that the rate of growth of γ_{G,S} doesn’t depend on S; it is an invariant of G. Gromov [5] has shown that the groups with polynomial growth are essentially the (finitely generated) nilpotent groups. (To be precise: the virtually nilpotent groups, i.e. those containing a nilpotent subgroup of finite index.) Another question is, how simple is γ_{G,S} combinatorially? The ‘best possible’ answer would be that the generating function (or Poincaré series) of γ_{G,S},

P_{G,S}(X) = ∑_{n=0}^{∞} γ_{G,S}(n)X^{n} ,

is a rational power series. This is indeed the case for, e.g., virtually abelian and word hyperbolic groups [1, 2, 3], whereas not much is known for nilpotent groups. Since calculations tend to be rather involved, one should first study some simpler problems. One possibility is to restrict the counting to a suitable subgroup U of G:

γ_{U,S}(n) = #(B_{S}(n) ∩ U) ;

this is the relative growth function of U w.r.t. G, S.

Now let us look at the following nilpotent group G of class 2:

G = ⟨x, y, z | [y, z] = 1, [x, y], [x, z] central⟩ .

G may also be represented as a linear group:

G = \{( \begin{matrix}1 & a & b & c \\ 0 & 1 & d & e \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) | a, b, c, d, e ∈ ℤ\} ,

where x, y, z are given by b = c = 0 and (a, d, e) = (1, 0, 0), (0, 1, 0), (0, 0, 1), resp. We take S = {x, x^{−1}, y, y^{−1}, z, z^{−1}} and look at the center Z = Z(G). Bernhard Weber shows in his thesis [11] that γ_{Z,S}(n) = T (⌊n/2⌋). Furthermore, he proves that n^{2} ≪ \frac{1}{8}n^{4} − T (n) ≪ n^{3}, which implies that the corresponding power series ∑ γ_{Z,S}(n)X^{n} is irrational.

Now one may ask, what kind of function is γ_{Z,S}? Rationality of the generating function would mean that for n large, γ_{Z,S}(n) is given by a polynomial in n (whose coefficients may be periodic functions of n). So, perhaps there is some kind of asymptotic expansion? In this work, we will show that there is at least a second term after the leading \frac{1}{8}n^{4}: we show that there is a constant C > 0 such that

T (n) = \frac{1}{8}n^{4} − Cn^{8/3} + o(n^{8/3}) .  (1)

As an example of what our problem looks like, T (10) counts the following points:

[figure]

Since ab + ac = a(b + c) = a(n − a) ≤ \frac{1}{4}n^{2}, the set of points counted by T (n) is contained in the square given by \{(x, y) | |x| + |y| ≤ \frac{1}{4}n^{2}\}. We do not get all of the lattice points in that square, however—there are some missing near the boundary. Let us call U(n) the area of the square minus R(n). For example, U(18) measures the area of the shaded region in the following picture (the corners of the square are at a distance \frac{1}{4} · 18^{2} = 81 from the origin):

[figure]

By attaching to each lattice point (u, v) the square ]u − 1, u]×]v − 1, v], we see that the number of lattice points with positive coordinates counted by T (n) is equal to \frac{1}{32}n^{4} − \frac{1}{4}U(n). Since the number of lattice points on the axes counted by T (n) is 1 + 4 ⌊n^{2}/4⌋, we have

T (n) = \frac{1}{8}n^{4} − U(n) + 4 ⌊\frac{n^{2}}{4} ⌋ + 1 = \frac{1}{8}n^{4} − U(n) + O(n^{2}) .  (2)

You will observe that the boundary of R(n) is a complicated zig-zagging line—it seems to be quite difficult to calculate the area between it and the sides of the square. How can we do it? First, an obvious simplification: We restrict to the part in the positive quadrant and consider the boundary of R(n) as the graph of a function u_{n} in a rectangular coordinate system whose x–axis is given by the side of the square:

[figure]

A certain periodicity seems to be present in this graph. To take advantage of this, we express u_{n}(\frac{n^{2}}{4} x) as ϕ_{n}(x, \frac{n}{2}x) with a function ϕ_{n} on [0, 1] × ℝ that is 1–periodic in the second variable.

[figure: y; x; y; x]

Using this periodicity, we now can approximate ∫ u_{n} by (a suitable multiple of) the integral of ϕ_{n} over the unit square [0, 1]^{2}. If we do the integration in the y direction first, we have a representation of U in the following form:

U(n) = n^{3} ∫_{0}^{1} Φ_{n}(x) dx + O(n^{5/2}) .  (3)

Here, Φ_{n} is a function that typically looks as follows (the graphs shown are those of Φ_{100}, Φ_{200}, Φ_{300}, and Φ_{1000}):

0  1 .......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................^{\frac{1}{2}}^{\frac{1}{3}}^{\frac{1}{4}}^{\frac{1}{5}}  ^{\frac{2}{5}}  ^{\frac{2}{3}}^{\frac{3}{5}}  ^{\frac{3}{4}} ^{\frac{4}{5}}

0  1 .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................^{\frac{1}{2}}^{\frac{1}{3}}^{\frac{1}{4}}^{\frac{1}{5}}^{\frac{1}{6}}^{\frac{1}{7}}^{\frac{1}{8}}  ^{\frac{2}{5}} ^{\frac{3}{7}}  ^{\frac{2}{3}}^{\frac{3}{5}}^{\frac{4}{7}}  ^{\frac{3}{4}} ^{\frac{4}{5}} ^{\frac{5}{6}} ^{\frac{6}{7}}^{\frac{7}{8}}^{0  1 ...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................^{\frac{1}{2}}^{\frac{1}{3}}^{\frac{1}{4}}^{\frac{1}{5}}^{\frac{1}{6}}^{\frac{1}{7}}^{\frac{1}{8}}^{\frac{1}{9}}  ^{\frac{2}{7}}  ^{\frac{2}{5}} ^{\frac{3}{7}}^{\frac{4}{9}}  ^{\frac{2}{3}}^{\frac{3}{5}}^{\frac{4}{7}}^{\frac{5}{9}}  ^{\frac{3}{4}}^{\frac{5}{7}}  ^{\frac{4}{5}} ^{\frac{5}{6}} ^{\frac{6}{7}}^{\frac{7}{8}}^{\frac{8}{9}}}

0  1 ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................^{\frac{1}{2}}^{\frac{1}{3}}^{\frac{1}{4}}^{\frac{1}{5}}^{\frac{1}{6}}^{\frac{1}{7}}^{\frac{1}{8}}^{\frac{1}{9}}  ^{\frac{2}{9}}  ^{\frac{2}{7}}  ^{\frac{2}{5}}^{\frac{3}{8}} ^{\frac{3}{7}}^{\frac{4}{9}}  ^{\frac{2}{3}}^{\frac{3}{5}}^{\frac{4}{7}}^{\frac{5}{9}}  ^{\frac{5}{8}}  ^{\frac{3}{4}}^{\frac{5}{7}}  ^{\frac{4}{5}}^{\frac{7}{9}} ^{\frac{5}{6}} ^{\frac{6}{7}}^{\frac{7}{8}}^{\frac{8}{9}}

You will observe that Φ_{n} gets more complicated as n grows and that it has maxima at simple rational numbers (more fractions being considered ‘simple’ if n is bigger). The maxima at the simpler fractions are the higher ones. The shape of the maxima varies; they become more and more pointed as they approach the endpoints of the unit interval. To make things easier, we introduce functions Ψ_{a,b} similar to the Φ_{n}, but without this change of shape. We then may write

Φ_{n}(x) = n^{−1/3}Ψ_{2x,2(1−x)}(n^{1/3}, x) ,

where the varying with x of the subscripts mirrors the change of shape described above. In particular,

U(n) = n^{8/3} ∫_{0}^{1} Ψ_{2x,2(1−x)}(n^{1/3}, x) dx + O(n^{5/2}) .

We first study functions Ψ_{a,b}(μ, ·) with constant a, b. To do this, we cut the unit interval into small intervals at the rational numbers indicated in the graphs above (this depends on μ). It turns out that within these small intervals, Ψ_{a,b}(μ, ·) can be approximated rather accurately by functions that are invariant under certain scalings (which accounts for the striking (approximate) self-similarity of the above graphs). This fact permits us to

express integrals ∫_{x_{1}}^{x_{2}}Ψ_{a,b}(μ, x) dx as sums μ^{−2} ∑_{(u,v)∈L_{μ}}F (μ^{−1}u, μ^{−1}v). Taking

into account some results from number theory, which amount to the assertion that the points (μ^{−1}u, μ^{−1}v) ((u, v) ∈ L_{μ}) tend to be evenly distributed for μ → ∞, we then get the main result of this work:

Ψ_{a,b}(μ, ·) converges (in some appropriate sense) to a constant function x ↦ C(a, b), as μ tends to infinity.

Furthermore, the constant value C(a, b) varies continuously with the parameters a, b. From this, it is not too difficult to conclude that

U(n) ∼ n^{8/3} ∫_{0}^{1} C(2x, 2(1 − x)) dx .

Whence the result:

T (n) = \frac{1}{8}n^{4} − ∫_{0}^{1} C(2x, 2(1 − x)) dx · n^{8/3} + o(n^{8/3}) .

For a = b = 1, all calculations can be done explicitly, leading to an explicit value for C(1, 1):

C(1, 1) = \frac{729}{640π^{2}} B(\frac{1}{3}, \frac{1}{3}).

We also obtain estimates for other C–values and for the constant

C = ∫_{0}^{1} C(2x, 2(1 − x)) dx

in (1).

In section 2, the rewriting of U(n) is done and the Ψ–functions are defined. Section 3 is quite technical. Its main result is that there is a continuous function F_{a,b} (satisfying some bounds needed later on) such that for suitable rational numbers p/q and p′/q′, we have

∫_{p/q}^{p′/q′}Ψ_{a,b}(μ, x) dx = \frac{1}{μ^{2}} F_{a,b}(\frac{q}{μ}, \frac{q′}{μ} ) + O(\frac{1}{qq′\sqrt{μ}}) .

Section 4 puts together results of sections 3 and 5 to prove the convergence result. Section 5 proves the equidistribution result alluded to above, starting with bounds for Kloosterman sums. Sections 3 to 5 together constitute the proof of Ψ_{a,b}(μ, ·) → C(a, b). Section 6 investigates the dependence of C(a, b) from (a, b). Its results are used in section 7 to prove a generalization of the convergence result, namely: If a, b are continuous functions of x, then (x ↦ Ψ_{a(x),b(x)}(μ, x)) → (x ↦ C(a(x), b(x))) (as μ → ∞). This then easily implies (1). Section 8 contains the explicit computation of C(1, 1). Section 9 discusses some possibilities for further work on this topic. In the appendices, we gather together some results needed for section 5: In appendix A, two propositions concerning periodic distributions are proved, and Appendix B gives some number theoretic estimates.

I wish to thank Fritz Grunewald for suggesting the topic of this work and many interesting discussions. Furthermore, it is a pleasure for me to thank Bruno Haible for carefully reading the manuscript and for his many helpful suggestions for improving the readability of this thesis.

2 Ψ–functions

In this section, we carry out the rewriting of U(n) described in the introduction. The result obtained then serves as the motivation to define the Ψ–functions Ψ_{a,b}(μ, x).

We will need the saw-tooth function, so we will define it now and give its main properties. Define for x ∈ ℝ

s(x) = min{|x − ν| | ν ∈ ℤ} = dist(x, ℤ) .  (4)

[figure: x; s(x); -1; 0; 1; 2; 3]

Lemma 2.1 Let x, y ∈ ℝ. Then

a) 0 ≤ s(x) ≤ \frac{1}{2};

b) |s(x) − s(y)| ≤ |x − y|;

c) s(−x) = s(x);

d) s(x + 1) = s(x).

Proof: Obvious. □

Now for U(n). Let us consider only the positive quadrant. We will write n = 2m from now on, where m may be half an integer. Transforming the plane by (x, y) ↦ \frac{1}{2}(−x + y + m^{2}, −x − y + m^{2}), the points (ab, ac) go to

\frac{1}{2}(a(−b + c) + m^{2}, −a(b + c) + m^{2}) = \frac{1}{2}(k^{2} + 2(m + k)ν, k^{2}) ,

where we have put a = m + k and c = ν, so that b = m − k − ν (k ∈ ℤ + m, ν ∈ ℤ).

[figure: 0; ab; ac; m^{2}; m^{2}; ⟹; 0; m^{2}; \frac{1}{2} (m^{2}−ab+ac); \frac{1}{2} (m^{2}−ab−ac)]

From this, we see that

U(n) = 4 ∫_{0}^{m^{2}}u(x) dx = n^{2} ∫_{0}^{1} u(m^{2}x) dx ,

where (taking into account that the determinant of our transformation is \frac{1}{2})

u(x) = min{k^{2} + |2x − k^{2} − 2(m + k)ν| | k ∈ ℤ + m, ν ∈ ℤ, m + k > 0} , so

u(m^{2}x) = min\{k^{2}+2(m+k)s(\frac{m^{2}}{m + k} x− \frac{k^{2}}{2(m + k)}) | k ∈ ℤ+m, m+k > 0\} .

We see that (by Lemma 2.1, a)) u(x) ≤ min_{k}(k^{2} + k + m) ≤ m for all x, so we may restrict k to |k| ≤ \sqrt{m}. Let us work on u for a while:

2(m + k)s(\frac{m^{2}}{m + k} x − \frac{k^{2}}{2(m + k)})

= 2ms(\frac{m^{2}}{m + k} x − \frac{k^{2}}{2(m + k)}) + O(|k|)
= 2ms((m − k)x + \frac{k^{2}}{2(m + k)}(2x − 1)) + O(|k|)
=^{2.1,b)} 2ms((m − k)x + \frac{k^{2}}{2m}(2x − 1)) + O(|k|) + O(\frac{|k|^{3}|2x − 1|}{m(m + k)})
=^{|k|≤\sqrt{m}} ns(mx − kx + \frac{k^{2}}{n} (2x − 1)) + O(\sqrt{n})

for 0 ≤ x ≤ 1. If we now define

ϕ_{n}(x, y) = min\{\frac{k^{2}}{n} + s(kx − y − \frac{k^{2}}{n} (2x − 1)) | k ∈ ℤ + \frac{1}{2}n\} ,  (5)

we see that

U(n) = n^{2}∫_{0}^{1} u(m^{2}x) dx = n^{3}∫_{0}^{1} ϕ_{n}(x, mx) dx + O(n^{5/2}) .

ϕ_{n} has the following properties:

Lemma 2.2

a) ϕ_{n}(x, y + 1) = ϕ_{n}(x, y);

b) 0 ≤ ϕ_{n}(x, y) ≤ \frac{1}{2} + \frac{1}{4n} < 1;

c) |ϕ_{n}(x_{1}, y) − ϕ_{n}(x_{2}, y)| ≤ (\sqrt{m} + 1)|x_{1} − x_{2}|.

d) |ϕ_{n}(x, y_{1}) − ϕ_{n}(x, y_{2})| ≤ |y_{1} − y_{2}|.

Proof: These follow immediately from Lemma 2.1. For c), note that |s(kx_{1} −y−(2x_{1} −1)k^{2}/n)−s(kx_{2} −y−(2x_{2} −1)k^{2}/n)| ≤ |k−2k^{2}/n||x_{1} −x_{2}| and that we may take |k| ≤ \sqrt{m}. □

For the convenience of the reader, we now state a well-known result concerning the approximation of sums by integrals.

Lemma 2.3 Let f : [0, 1] → ℝ and L > 0 such that for all x, y ∈ [0, 1], |f(x) − f(y)| ≤ L|x − y|. Then for every 0 ≤ δ ≤ 1,

\frac{1}{n} ∑_{j=0}^{n−1} f(\frac{j + δ}{n} ) = ∫_{0}^{1} f(x) dx + O(\frac{L}{n}) .

Proof: Well-known and easy. □

We will assume n to be even for now, so m is an integer. Because of part a) of Lemma 2.2, we can write

∫_{0}^{1} ϕ_{n}(x, mx) dx = ∑_{j=0}^{m−1} ∫_{j/m}^{(j+1)/m}ϕ_{n}(x, mx − j) dx

= ∑_{j=0}^{m−1} ∫_{0}^{1/m}ϕ_{n}(\frac{j}{m} + x, mx) dx

= ∫_{0}^{1} \frac{1}{m} ∑_{j=0}^{m−1} ϕ_{n}(\frac{j + y}{m} , y) dy

= ∫_{0}^{1}(∫_{0}^{1} ϕ_{n}(x, y) dx + O(m^{−1/2})) dy

= ∫_{0}^{1}∫_{0}^{1} ϕ_{n}(x, y) dy dx + O(n^{−1/2}) .

For the transformation of the sum into an integral, we have used Lemmas 2.2, c) and 2.3. If n is odd, we have in the same way

∫_{0}^{1} ϕ_{n}(x, mx) dx

= ∑_{j=0}^{m−3/2} ∫_{j/m}^{(j+1)/m}ϕ_{n}(x, mx − j) dx + ∫_{1−1/2m}^{1}ϕ_{n}(x, mx − m + \frac{1}{2}) dx

=^{2.2,b)} ∑_{j=0}^{m−3/2} ∫_{0}^{1/m}ϕ_{n}(\frac{j}{m} + x, mx) dx + O(m^{−1})

= ∫_{0}^{1} \frac{1}{m} ∑_{j=0}^{m−3/2} ϕ_{n}(\frac{j + y}{m} , y) dy + O(m^{−1})

= ∫_{0}^{1} (∫_{0}^{1} ϕ_{n}(x, y) dx + O(m^{−1/2})) dy + O(m^{−1})

= ∫_{0}^{1}∫_{0}^{1} ϕ_{n}(x, y) dy dx + O(n^{−1/2}) .

Let us write

Φ_{n}(x) = ∫_{0}^{1} ϕ_{n}(x, y) dy ,

then we get formula (3) for U:

U(n) = n^{3} ∫_{0}^{1} Φ_{n}(x) dx + O(n^{5/2}) .

The term \frac{k^{2}}{n} (2x − 1), which occurs inside s in the definition (5) of ϕ_{n}, is a bit of a nuisance. Luckily, the factor k^{2}/n also occurs as a summand outside the s–term, so that we may get rid of the offender by a suitable affine transformation of the graph of ϕ_{n}(x, ·). We have to pay for this, however: our saw-tooth function gets somewhat distorted. Let us fix some notations. Take real numbers a, b ≥ 0, not both zero, and define

ℓ_{a,b}(x) = \{ \begin{matrix}−x/a for & x < 0 \\ 0 for & x = 0 \\ x/b for & x > 0 \end{matrix} ,  (6)

where −x/a or x/b are to be interpreted as ∞ if a or b are zero, resp. Then set

s_{a,b}(x) = min{ℓ_{a,b}(x − ν) | ν ∈ ℤ} .  (7)

As an example, ℓ_{1,1}(x) = |x|, and s_{1,1} = s. Note that in all cases, s_{a,b} is a bounded, non-negative real function.

Now let us fix x and look at Φ_{n}(x):

Φ_{n}(x) = ∫_{0}^{1} ϕ_{n}(x, y) dy
= area of {(y, z) | 0 ≤ y ≤ 1, 0 ≤ z ≤ ϕ_{n}(x, y)}
=^{2.2,a)} area of {(y, z) | 0 ≤ y + (2x − 1)z ≤ 1, 0 ≤ z ≤ ϕ_{n}(x, y)}
=^{(∗)} area of {(y, z) | 0 ≤ y ≤ 1, 0 ≤ z ≤ ϕ_{n}(x, y − (2x − 1)z)}
= area of {(y, z) | 0 ≤ y ≤ 1, 0 ≤ z ≤ ϕ̃_{n}(x, y)}
= ∫_{0}^{1} ϕ̃_{n}(x, y) dy ,

where for (∗) we have used the area-preserving affine transformation

(y, z) ↦ (y + (2x − 1)z, z) .

Note that because of Lemma 2.2, d), and since |2x − 1| ≤ 1, we may indeed describe the transformed set as the area below the graph of a well-defined function ϕ̃_{n}(x, ·). Since y ↦ α + |β − y| is transformed into

y ↦ α + ℓ_{2x,2(1−x)}(β − y + (2x − 1)α) ,

[figure: β; α]
⇓

[figure: β + α(2x − 1); α]

we have that y ↦ α+s(β−y) goes over to y ↦ α+s_{2x,2(1−x)}(β−y+α(2x−1)), hence

ϕ̃_{n}(x, y) = min\{\frac{k^{2}}{n} + s_{2x,2(1−x)}(kx − y) | k ∈ ℤ + m\}
= n^{−1/3} min\{\frac{k^{2}}{n^{2/3}} + n^{1/3}s_{2x,2(1−x)}(kx − y) | k ∈ ℤ + \frac{1}{2}n\} .

This leads to the following definitions: Take μ > 0 and some fixed δ ∈ [0, 1[ and put for a, b ≥ 0, not both zero,

f_{a,b}(μ, x, y) = min\{\frac{k^{2}}{μ^{2}} + μs_{a,b}(kx − y) | k ∈ ℤ + δ\}  (8)

Ψ_{a,b}(μ, x) = ∫_{0}^{1} f_{a,b}(μ, x, y) dy .  (9)

(It will turn out that the factor μ introduced in these definitions gives the proper scaling for our problem.) Using these notations, we now have

ϕ̃_{n}(x, y) = n^{−1/3}f_{2x,2(1−x)}(n^{1/3}, x, y)
Φ_{n}(x) = n^{−1/3}Ψ_{2x,2(1−x)}(n^{1/3}, x) .

Here, δ = s(n/2) has to be taken as 0 or \frac{1}{2} for n even or odd, resp. By (3) and (9), we then finally get

U(n) = n^{8/3} ∫_{0}^{1} Ψ_{2x,2(1−x)}(n^{1/3}, x) dx + O(n^{5/2}) .  (10)

The functions Ψ_{a,b} and their behaviour when μ goes to infinity will be our main objects of study.

3 Approximating Ψ near a rational point

The main result of this section is Proposition 3.13: If 0 ≤ γ ≤ 1, and I = [\frac{p}{q}, \frac{p′}{q′}] is such that

p′q − pq′ = 1 and qq′|q − q′| < μ^{3} ≤ qq′(q + q′)

then

∫_{I} Ψ_{1,γ}(μ, x) dx = \frac{1}{μ^{2}} F_{1,γ}(\frac{q}{μ}, \frac{q′}{μ} ) + O(\frac{1}{qq′\sqrt{μ}}) ,

where F_{1,γ} is a continuous function on ℝ_{+}^{2} satisfying the following bounds:

F_{1,γ}(x, y) = O(1)  for x → ∞, y = x + O(x^{−2}) ,
F_{1,γ}(x, y) = O(x^{3})  for x → ∞, y = x^{−2} + O(x^{−5}) ,
F_{1,γ}(x, y) = O(x^{−3/2}) for x → 0, y = x^{−1/2} + O(x) .

This is proved by first rewriting Ψ_{1,γ}(μ, p/q + ξ) as

Ψ_{1,γ}(μ, \frac{p}{q} + ξ) = \frac{μ}{q^{2}} ∑_{jmod q}\overline{Ψ}_{1,γ}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{j + δ}{q}; q^{2}ξ) ,

where p/q is in lowest terms and pr ≡ −1 mod q (this is Lemma 3.3). \overline{Ψ}_{1,γ} is a suitable variant of Ψ_{1,γ}. The next important step (which constitutes the largest and most technical part of this section) is to give an estimate for \frac{∂}{∂λ} \overline{Ψ}_{1,γ}(ρ, σ, λ; ξ), namely (Lemma 3.12):

For suitable (ρ, σ, ξ),

\frac{∂}{∂λ}\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = O(ρ) ,

uniformly in σ, λ, ξ.

This estimate then makes it possible to replace the sum by an integral in the formula above:

Ψ_{1,γ}(μ, \frac{p}{q} + x) = \frac{μ}{q} ∫_{0}^{1} \overline{Ψ}_{1,γ}((\frac{q}{μ})^{3}, \frac{r}{q}, λ; q^{2}x) dλ + O(\frac{1}{\sqrt{μ}}) .

From this, our result is easily derived.

The bounds on F_{1,γ} will be needed later on for the convergence proof.

3.1 Some simple facts and definitions

We begin by listing some more or less obvious facts.

Lemma 3.1 1a) ℓ_{b,a}(x) = ℓ_{a,b}(−x) . 1b) ℓ_{a,b}(tx) = tℓ_{a,b}(x) for t > 0. 1c) ℓ_{ta,tb}(x) = ℓ_{a,b}(x)/t for t > 0. 1d) If a ≥ a′ and b ≥ b′, then ℓ_{a,b}(x) ≤ ℓ_{a′,b′}(x) for all x. 2a) f_{b,a}(μ, x, y) = f_{a,b}(μ, −x, −y) . 2b) f_{a,b}(μ, −x, y) = f_{a,b}(μ, x, y) if δ = 0 or δ = \frac{1}{2} . 2c) f_{a,b}(μ, x, y + 1) = f_{a,b}(μ, x, y) . 2d) f_{a,b}(μ, x + 1, y) = f_{a,b}(μ, x, y − δ) . 2e) f_{ta,tb}(μ, x, y) = t^{−2/3}f_{a,b}(t^{−1/3}μ, x, y) for t > 0 . 2f) If a ≥ a′ and b ≥ b′, then f_{a,b}(μ, x, y) ≤ f_{a′,b′}(μ, x, y) for all μ, x, y. 3a) Ψ_{b,a}(μ, x) = Ψ_{a,b}(μ, −x) . 3b) Ψ_{a,b}(μ, −x) = Ψ_{a,b}(μ, x) if δ = 0 or δ = \frac{1}{2} . 3c) Ψ_{a,b}(μ, x + 1) = Ψ_{a,b}(μ, x) . 3d) Ψ_{ta,tb}(μ, x) = t^{−2/3}Ψ_{a,b}(t^{−1/3}μ, x) for t > 0 . 3e) If a ≥ a′ and b ≥ b′, then Ψ_{a,b}(μ, x) ≤ Ψ_{a′,b′}(μ, x) for all μ, x.

Proof: 1a)–1d) are clear from (6). 2a) comes from 1a)— s_{a,b}(−x) = s_{b,a}(x). 2b) is obtained by replacing k by −k in (8) (which is possible because ℤ+δ = −(ℤ + δ) for δ = 0 or \frac{1}{2}). 2c) Obvious— s_{a,b}(x + 1) = s_{a,b}(x). 2d) s_{a,b}(k(x + 1) − y) = s_{a,b}(kx + δ − y). 2e) comes from substituting 1c) into (8). 2f) is a consequence of 1d). 3a) comes from 2a) and 2c):

∫_{0}^{1} f_{b,a}(μ, x, y) dy = ∫_{0}^{1} f_{a,b}(μ, −x, −y) dy

= ∫_{−1}^{0} f_{a,b}(μ, −x, y) dy

= ∫_{0}^{1} f_{a,b}(μ, −x, y) dy .

3b) follows from 2b). 3c) is a consequence of 2d) and 2c):

∫_{0}^{1} f_{a,b}(μ, x + 1, y) dy = ∫_{0}^{1} f_{a,b}(μ, x, y − δ) dy

= ∫_{−δ}^{1−δ}f_{a,b}(μ, x, y) dy

= ∫_{−δ}^{0} f_{a,b}(μ, x, y) dy + ∫_{0}^{1−δ}f_{a,b}(μ, x, y) dy

= ∫_{0}^{1} f_{a,b}(μ, x, y) dy .

3d) follows from 2e). 3e) is a consequence of 2f). □

The key observation in the study of the Ψ–functions is that if x is near a suitable fraction p/q, then f_{a,b}(μ, x, ·) is ‘almost periodic’ with ‘period’ 1/q. To make this precise, we introduce some more functions:

g_{a,b}(ρ, λ; ξ, η) = min{(λ + n)^{2}ρ + ℓ_{a,b}((λ + n)ξ − η) | n ∈ ℤ} , (11)
\overline{f}_{a,b}(ρ, σ, λ; ξ, η) = min\{g_{a,b}(ρ, λ − nσ; ξ, η − n) | n ∈ ℤ\} ,  (12)
\overline{Ψ}_{a,b}(ρ, σ, λ; ξ) = ∫_{0}^{1} \overline{f}_{a,b}(ρ, σ, λ; ξ, η) dη .  (13)

\overline{f}_{a,b}(q/μ, σ, δ; q^{2}(x − p/q), ·) will be the properly rescaled version of f_{a,b} with the dependence on the ‘right’ parameters made explicit, and analogously for \overline{Ψ}_{a,b} and Ψ_{a,b}. σ will be a parameter depending on p and q, whereas λ is responsible for the change of shape when taking translates—see 2b) below.

Let us continue with the listing of simple facts.

Lemma 3.2 1a) g_{a,b}(ρ, λ + 1; ξ, η) = g_{a,b}(ρ, λ; ξ, η) . 1b) g_{b,a}(ρ, λ; ξ, η) = g_{a,b}(ρ, −λ; ξ, −η) . 1c) If a ≥ a′ and b ≥ b′, then g_{a,b}(ρ, λ; ξ, η) ≤ g_{a′,b′}(ρ, λ; ξ, η) for all ρ, λ, ξ, η. 2a) \overline{f}_{a,b}(ρ, σ, λ + 1; ξ, η) = \overline{f}_{a,b}(ρ, σ, λ; ξ, η) . 2b) \overline{f}_{a,b}(ρ, σ, λ; ξ, η + 1) = \overline{f}_{a,b}(ρ, σ, λ − σ; ξ, η) .

Proof: 1a) Shift n by 1 in (11). 1b) comes from Lemma 3.1, 1a)—replace n by −n in (11). 1c) follows from Lemma 3.1, 1d). 2a) follows from 1a). 2b) Shift n by 1 in (12). □ Property 2b) is the ‘almost periodicity’ referred to above: Translating η by one results in a change of λ only.

3.2 Rewriting Ψ

Now we are ready to state the first important result.

Lemma 3.3 If p/q is in lowest terms and pr ≡ −1 mod q, then

Ψ_{a,b}(μ, \frac{p}{q} + ξ) = \frac{μ}{q^{2}} ∑_{jmod q}\overline{Ψ}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{j + δ}{q}; q^{2}ξ) .

Proof: We first express f_{a,b} in terms of \overline{f}_{a,b} by scaling appropriately and taking suitable parameters:

f_{a,b}(μ, \frac{p}{q} + ξ, y)

= min\{\frac{(k + δ)^{2}}{μ^{2}} + μℓ_{a,b}(\frac{(k + δ)p}{q} + (k + δ)ξ − y − n) | k, n ∈ ℤ\}

=^{r⊥q} min\{\frac{(jr + mq + δ)^{2}}{μ^{2}}

+ μℓ_{a,b}(−\frac{j}{q} + \frac{δp}{q} + (jr + mq + δ)ξ − y − n) | j, m, n ∈ ℤ\}

=^{3.1,1b)} \frac{μ}{q} min\{(\frac{jr + δ}{q} + m)^{2} \frac{q^{3}}{μ^{3}}

+ ℓ_{a,b}((\frac{jr + δ}{q} + m)q^{2}ξ − qy + δp − qn − j) | j, m, n ∈ ℤ\}

=^{(11)}  \frac{μ}{q} min\{g_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{jr + δ}{q}; q^{2}ξ, qy − δp + qn + j) | j, n ∈ ℤ\}
=^{3.2,1a)} \frac{μ}{q} min\{g_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{jr + δ}{q}; q^{2}ξ, qy − δp + j) | j ∈ ℤ\}
=^{(12)}  \frac{μ}{q}\overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{δ}{q}; q^{2}ξ, qy − δp) .

Hence, we can express Ψ_{a,b} as follows:

Ψ_{a,b}(μ, \frac{p}{q} + ξ) = ∫_{0}^{1} f_{a,b}(μ, \frac{p}{q} + ξ, y) dy

= \frac{μ}{q^{2}} ∫_{0}^{q} \overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{δ}{q}; q^{2}ξ, η − δp) dη

= \frac{μ}{q^{2}} ∫_{−δp}^{q−δp}\overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{δ}{q}; q^{2}ξ, η) dη

=^{3.2,2a),b)} \frac{μ}{q^{2}} ∫_{0}^{q} \overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{δ}{q}; q^{2}ξ, η) dη

= \frac{μ}{q^{2}} ∑_{j=0}^{q−1} ∫_{0}^{1} \overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{δ}{q}; q^{2}ξ, η + j) dη

=^{3.2,2b)}  \frac{μ}{q^{2}} ∑_{j=0}^{q−1} ∫_{0}^{1} \overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{−jr + δ}{q}; q^{2}ξ, η) dη

=^{r⊥q}  \frac{μ}{q^{2}} ∑_{jmod q} ∫_{0}^{1} \overline{f}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{j + δ}{q}; q^{2}ξ, η) dη

=^{(13)}  \frac{μ}{q^{2}} ∑_{jmod q} \overline{Ψ}_{a,b}(\frac{q^{3}}{μ^{3}} , \frac{r}{q}, \frac{j + δ}{q}; q^{2}ξ) .

□

It is tempting to replace the sum by an integral in this expression for Ψ_{a,b}. We will show that it is indeed possible to do this without making too large an error, provided that we are sufficiently near a suitable p/q.

3.3 Describing g_{1,γ}

We remark that by Lemma 3.1, 3a),d), it is no loss of generality to assume (a, b) = (1, γ) with 0 ≤ γ ≤ 1. We will do this from now on. Furthermore, we will always take ξ > 0.

First of all, we need a good description of g_{1,γ}(ρ, λ; ξ, ·). Let us define the following auxiliary function:

h_{1,γ}(ρ, λ; ξ, η) = λ+max{n ∈ ℤ | g_{1,γ}(ρ, λ; ξ, η) = (λ+n)^{2}ρ+ℓ_{1,γ}((λ+n)ξ−η)}.

Let us call η a minimum of g_{1,γ}(ρ, λ; ξ, ·), if η = h_{1,γ}(ρ, λ; ξ, η)ξ (then g_{1,γ} has a local minimum at (η, ρη^{2}/ξ^{2}) with the possible exception of the case when the set of n’s in the definition of h_{1,γ}(…, η) contains more than one element). Now an elementary observation:

Lemma 3.4 Let β_{1} ≤ β_{2} and α_{1}, α_{2} ∈ ℝ. Define ℓ_{j}(η) = α_{j} + ℓ_{1,γ}(β_{j} − η) for j ∈ {1, 2}.

a) Exactly one of the following three assertions is true:

1) ℓ_{1}(η) < ℓ_{2}(η) for all η ∈ ℝ;

2) There is some β_{1} < η_{0} ≤ β_{2} such that ℓ_{1}(η) < ℓ_{2}(η) ⟺ η < η_{0};

3) ℓ_{1}(η) ≥ ℓ_{2}(η) for all η ∈ ℝ. Assertion 1) is equivalent to α_{2} −α_{1} > β_{2} −β_{1}, and assertion 3) is equivalent to γ(α_{1} − α_{2}) ≥ β_{2} − β_{1}.

b) If there is some η ∈ ℝ with ℓ_{1}(η) \left\{{< \atop ≤}\right\} ℓ_{2}(η), then ℓ_{1}(β_{1}) \left\{{< \atop ≤}\right\} ℓ_{2}(β_{1}). If there is some η ∈ ℝ with ℓ_{2}(η) \left\{{< \atop ≤}\right\} ℓ_{1}(η), then ℓ_{2}(β_{2}) \left\{{< \atop ≤}\right\} ℓ_{1}(β_{2}).

Proof: Obvious (see the following figure). □

[figure: β_{1}; β_{2}; α_{1}; α_{2}; 1); β_{1}; β_{2}; η_{0}; α_{1}; α_{2}; 2); β_{1}; β_{2}; α_{1}; α_{2}; 3)]

This established, we now proceed to describe g_{1,γ}:

Lemma 3.5 Let g(η) = g_{1,γ}(ρ, λ; ξ, η) and define h(η) analogously.

a) There is a biggest minimum η_{+} of g. We have η_{+} = (λ+n)ξ, where n ∈ ℤ is given by

\frac{ξ}{2ρ} − \frac{1}{2} < λ + n ≤ \frac{ξ}{2ρ} + \frac{1}{2} .

b) There is N ∈ ℕ ∪ {∞} (N = ∞ ⟺ γ = 0) such that all minima of g are given by η_{+} −jξ for j ∈ ℕ, j < N. If γ > 0, there is a smallest minimum η_{−} of g; it is given by η_{−} = (λ + n)ξ, where

−\frac{ξ}{2γρ} − \frac{1}{2} < λ + n ≤ −\frac{ξ}{2γρ} + \frac{1}{2} .

If γ = 0, we take η_{−} = −∞.

c) h is a monotonically increasing, right continuous step function. Every maximal interval on which h is constant contains exactly one minimum of g.

d) If η_{−} ≤ η ≤ η_{+}, then (h(η) − 1)ξ ≤ η ≤ (h(η) + 1)ξ. If η ≥ η_{+}, then h(η)ξ = η_{+}, and if η ≤ η_{−}, then h(η)ξ = η_{−}.

e) For all η ≤ η_{+}, g(η) ≤ \frac{ρ}{ξ^{2}} η^{2} − 2\frac{ρ}{ξ}η + ρ + ξ .

If η_{−} ≤ η ≤ η_{+}, then g(η) = \frac{ρ}{ξ^{2}} η^{2} + O(\frac{ρ}{ξ}|η|) + O(ρ) + O(ξ) .

f) For all η, g(η) ≥ \frac{ρ}{ξ^{2}} η_{+}^{2} + η − η_{+} .

For η ≥ η_{+}, we have equality, and η − \frac{ξ^{2}}{4ρ} ≤ g(η) ≤ η − \frac{ξ^{2}}{4ρ} + \frac{1}{4}ρ . g) If γ > 0, then for all η, g(η) ≥ \frac{ρ}{ξ^{2}} η_{−}^{2} + \frac{η_{−} − η}{γ} .

For η ≤ η_{−}, we have equality, and −\frac{η}{γ} − \frac{ξ^{2}}{4γ^{2}ρ} ≤ g(η) ≤ −\frac{η}{γ} − \frac{ξ^{2}}{4γ^{2}ρ} + \frac{1}{4}ρ .

Proof: a),b) Lemma 3.4 tells us that η = (λ + n)ξ is a minimum of g if and only if for all k ≥ 1, we have

(λ + n − k)^{2}ρ + ξ ≥ (λ + n)^{2}ρ and (λ + n + k)^{2}γρ + ξ > (λ + n)^{2}γρ .

If these hold for k = 1, the left hand sides are increasing with k, hence the condition for all k is equivalent to that for k = 1. An easy calculation then gives the values of η_{+} and of η_{−} and shows that every possible η in between is a minimum.

c) It is clear from its definition that h is a step function. Monotonicity follows from Lemma 3.4, a): If there were η_{1} > η_{2} such that h(η_{1})ξ = β_{1} < h(η_{2})ξ = β_{2}, then, taking α_{j} = β_{j}ρ/ξ^{2}, we see that none of the three assertions could hold. Lemma 3.4, a), now also shows that h is right continuous. Lemma 3.4, b), implies that if there is some η with h(η)ξ = β, then h(β)ξ = β, whence β is a minimum of g. Hence, every maximal interval on which h is constant must contain a minimum of g. Since it is clear by definition that it can contain at most one minimum, it has to contain exactly one minimum.

d) If η_{−} ≤ η ≤ η_{+}, then there is a minimum η_{0} of g such that η_{0} ≤ η ≤ η_{0} +ξ, and by c), h(η) is either η_{0}/ξ or η_{0}/ξ + 1. The two equalities also follow from c): h has to be constant right of η_{+} and left of η_{−}, and h(η_{+})ξ = η_{+}, h(η_{−})ξ = η_{−}.

f) Using the fact that η_{+} is the biggest minimum of g and Lemma 3.4, a), we see that the inequality holds for all η that are minima of g. But then it must hold for all η. Equality for η ≥ η_{+} follows from d), and the rest is an easy consequence of the bounds on η_{+} given by a).

3 APPROXIMATING Ψ NEAR A RATIONAL POINT 27 Here is a picture of g and h:

[figure: g(η); ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; ·; \frac{ρ}{ξ^{2}} η^{2}; η; η_{−}; η_{+}; h(η); η/ξ; η]

(Proof continued:)

g) Similarly as for f).

e) For η_{−} ≤ η ≤ η_{+}, take η_{0} as in the proof of d). Then g(η) ≤ g(η_{0})+η−η_{0} = ρη^{2}/ξ^{2} + (η − η_{0})(1 − (η + η_{0})ρ/ξ^{2}) ≤ ρη^{2}/ξ^{2} − 2ρη/ξ + ξ + ρ. Furthermore,

g(η) ≥ min_{|t|≤1} ρ(η + tξ)^{2}/ξ^{2} = ρη^{2}/ξ^{2} + O(ρ|η|/ξ) + O(ρ). For η ≤ η_{−}, we must

show that (see g)) −η/γ − ξ^{2}/4γ^{2}ρ + \frac{1}{4}ρ ≤ ρη^{2}/ξ^{2} − 2ρη/ξ + ρ + ξ, i.e. that (ξ − ξ^{2}/2γρ − η)^{2} + ξ^{3}/γρ + ξ^{3}/ρ ≥ \frac{1}{4}ξ^{2}. By b), the term in parentheses is at least ξ/2, whence the result. □

From the preceding picture of g and h, one gets the impression that modulo a constant factor and when looked upon at a coarse scale, g is roughly an integral function of h. This observation is made explicit in the following lemma.

Lemma 3.6 With the notations of Lemma 3.5, we have for η_{1} ≤ η_{2} that

∫_{η_{1}}^{η_{2}}h(η) dη = \frac{ξ}{2ρ}(g(η_{2}) − g(η_{1})) + O(|η_{1}|) + O(|η_{2}|) + O(ξ) + O(\frac{ξ^{2}}{ρ} ) ,

uniformly in ρ, λ, and ξ.

Proof: First, let us consider η_{−} ≤ η ≤ η_{+}. Then |h(η) − η/ξ| ≤ 1 by Lemma 3.5, d). From this, we see that for η_{−} ≤ η_{1} ≤ η_{2} ≤ η_{+},

∫_{η_{1}}^{η_{2}}h(η) dη = \frac{η_{2}^{2} − η_{1}^{2}}{2ξ} + O(η_{2} − η_{1}) ,

and the claim follows for this range of η’s by taking into account that

\frac{ξ}{2ρ}g(η) = \frac{η^{2}}{2ξ} + O(|η|) + O(ξ) + O(\frac{ξ^{2}}{ρ} )

by Lemma 3.5, e).

Now, let us take η ≥ η_{+}. We then have (by Lemma 3.5, a) and d))

\frac{ξ^{2}}{2ρ} − \frac{ξ}{2} ≤ η_{+} = h(η)ξ ≤ \frac{ξ^{2}}{2ρ} + \frac{ξ}{2} ,

hence |h(η) − \frac{1}{2}ξ/ρ| ≤ \frac{1}{2}. Therefore, if η_{+} ≤ η_{1} ≤ η_{2},

∫_{η_{1}}^{η_{2}}h(η) dη = \frac{ξ}{2ρ}(η_{2} − η_{1}) + O(η_{2} − η_{1})
= \frac{ξ}{2ρ}(g(η_{2}) − g(η_{1})) + O(η_{2} − η_{1}) ,

the last equality following from Lemma 3.5, f).

The case η ≤ η_{−} is handled in a similar way using Lemma 3.5, b) and g). The lemma then follows by putting together the above results. □

3.4 The relevant set of parameters—describing \overline{f}_{1,γ}

When looking for a set of parameters (ρ, σ, ξ) such that \overline{f}_{1,γ}(ρ, σ, λ; ξ, ·) has a particularly nice description, one is led to the following. Let

S_{1} = {(ρ, σ) | ρ, σ > 0, ρσ|σ − 1| < 1 ≤ ρσ(σ + 1)}  (14)

and

S = {(ρ, σ, ξ) | (ρ, σ) ∈ S_{1}, 0 < 2σξ < 1 + ρσ(σ − 1)} .  (15)

Lemma 3.7 For (ρ, σ, ξ) ∈ S, we have

a) ξ < 1 ,

b) ξ^{2} < ρ,

c) (1 − ξ)ρ > ξ^{2} .

Proof: We set ρ = 4/(α^{2} − β^{2}) and σ = \frac{1}{2}(α − β) . The conditions on ρ, σ, and ξ then translate into

α > 1 and − 1 < β ≤ 1 and 0 < ξ < 2\frac{α − 1}{α^{2} − β^{2}} .

a) 1 − ξ > \frac{α^{2} − β^{2} − 2(α − 1)}{α^{2} − β^{2}} = \frac{(α − 1)^{2} + 1 − β^{2}}{α^{2} − β^{2}} > 0.

b) 2α − 1 − β^{2} > 1 − β^{2} ≥ 0, hence (α − 1)^{2} < α^{2} − β^{2}, so

ξ^{2} < (2\frac{α − 1}{α^{2} − β^{2}} )^{2} < \frac{4}{α^{2} − β^{2}} = ρ .

c) (1 − ξ)ρ > 4\frac{(α − 1)^{2} + 1 − β^{2}}{(α^{2} − β^{2})^{2}} ≥ 4\frac{(α − 1)^{2}}{(α^{2} − β^{2})^{2}} > ξ^{2} . □

We will soon see that f_{1,γ} indeed has a rather nice description for (ρ, σ, ξ) ∈ S. But first some auxiliary results.

Lemma 3.8 Let X, σ > 0, and for λ ∈ ℝ take ν_{λ}, ν′_{λ} ∈ ℤ such that

X − \frac{1}{2} < λ + ν_{λ} ≤ X + \frac{1}{2} and − X − \frac{1}{2} < λ − σ − ν′_{λ} ≤ −X + \frac{1}{2} .

Then

sup_{λ}(2X + 2λ − σ + ν_{λ} − ν′_{λ})(ν_{λ} + ν′_{λ} + σ)

= (4X − σ + 1 − ⌈2X − σ⌉)(⌈2X − σ⌉ + σ) .

Proof: Since ν_{λ} decreases by 1 and ν′_{λ} increases by 1 when λ increases by 1, the expression in the sup is 1–periodic in λ. We may therefore assume X − \frac{1}{2} < λ ≤ X + \frac{1}{2}, so that ν_{λ} = 0 and 2X − σ − 1 < ν′_{λ} < 2X − σ + 1, that is, ν′_{λ} = ⌈2X − σ⌉ or ⌈2X − σ⌉ − 1. At λ = ⌈2X − σ⌉ − X + σ − \frac{1}{2}, ν′_{λ} jumps up by 1; apart from this point, the expression in the sup is a linear function of λ. Hence, the sup is a limit (from left or right) at one of the points λ = X − \frac{1}{2}, ⌈2X − σ⌉ − X + σ − \frac{1}{2}, or X + \frac{1}{2}. These limits have the following values:

(4X − σ − ⌈2X − σ⌉)(⌈2X − σ⌉ + σ − 1) ,
(⌈2X − σ⌉ + σ)(⌈2X − σ⌉ + σ − 1) , and
(4X − σ − ⌈2X − σ⌉ + 1)(⌈2X − σ⌉ + σ) .

The last one is the biggest of these: It is by 4X bigger than the first one and the difference to the second one is 2(⌈2X − σ⌉+σ)(2X −σ+1−⌈2X − σ⌉) ≥ 0. □

Lemma 3.9 For (ρ, σ, ξ) ∈ S and all λ, there are minima η_{1} and η_{2} of g_{1,γ}(ρ, λ; ξ, ·) such that

\frac{ξ^{2}}{2ρ} − \frac{ξ}{2} < η_{1} ≤ \frac{ξ^{2}}{2ρ} + \frac{ξ}{2} and − \frac{ξ^{2}}{2ρ} − \frac{ξ}{2} < η_{2} ≤ −\frac{ξ^{2}}{2ρ} + \frac{ξ}{2}

with

g_{1,γ}(ρ, λ; ξ, η_{1}) < g_{1,γ}(ρ, λ − σ; ξ, η_{1} − 1)

and

g_{1,γ}(ρ, λ; ξ, η_{2}) ≤ g_{1,γ}(ρ, λ + σ; ξ, η_{2} + 1) .

Furthermore, η_{1} ≥ η_{2}.

Proof: We first assume that γ = 1 and show the existence of η_{1} with the required properties.

We write X = \frac{1}{2}ξ/ρ (Xξ is the point where η ↦ ρη^{2}/ξ^{2} has slope 1) and take ν, ν′ ∈ ℤ such that Λ = λ + ν is in ]X − \frac{1}{2}, X + \frac{1}{2}] and such that Λ′ = λ − σ − ν′ is in ]−X − \frac{1}{2}, −X + \frac{1}{2}]. Then by Lemma 3.5, a),b), η_{1} = Λξ = 2ΛXρ is the biggest minimum of g_{1,1}(ρ, λ; ξ, ·) and Λ′ξ is the smallest minimum of g_{1,1}(ρ, λ − σ; ξ, ·). By Lemma 3.5, g), we have for all η that

g_{1,1}(ρ, λ − σ; ξ, η) ≥ \frac{ρ(Λ′ξ)^{2}}{ξ^{2}} − η + Λ′ξ = (Λ′ + X)^{2}ρ − η − X^{2}ρ .

Therefore, we want to show that (take η = η_{1} − 1 = 2ΛXρ − 1 in the last equation)

g_{1,1}(ρ, λ; ξ, η_{1}) = Λ^{2}ρ < (Λ′ + X)^{2}ρ + 1 − 2ΛXρ − X^{2}ρ ,

or equivalently that

(2X + Λ + Λ′)(Λ − Λ′) < \frac{1}{ρ} .

Now fix X and let λ vary. By Lemma 3.8, the left hand side is bounded by

(4X − σ + 1 − ⌈2X − σ⌉)(⌈2X − σ⌉ + σ) .

This is a continuous, strictly monotonically increasing function of X: At the points where X ↦ ⌈2X − σ⌉ has jumps, the left and right limits both are equal to 2X(2X+1). Strict monotonicity is then clear from ⌈2X − σ⌉+σ > 0.

Therefore, we may take the supremum of the possible values for 2X = ξ/ρ, namely (see (15))

2X = \frac{1}{2ρσ} + \frac{σ − 1}{2} = \frac{α − 1}{2}

in the notation of the proof of Lemma 3.7. Then 2X −σ = \frac{1}{2}(β −1) ∈]−1, 0], hence ⌈2X − σ⌉ = 0, and the bound is equal to

(4X − σ + 1)σ = \frac{1}{ρ} .

Bearing in mind that 2X may not actually reach the supremum, we get the scrict inequality that was to be proved. (This calculation explains our choice of S as the set of admissible parameters—they give exactly the best possible bound here.)

The existence of η_{2} is proved in the same way.

If now 0 ≤ γ ≤ 1 is arbitrary, we may take the same η_{1} and η_{2} as for γ = 1 (the other parameters being fixed): Lemma 3.5 shows that η_{−}(γ) ≤ η_{−}(1) and η_{+}(γ) = η_{+}(1), hence η_{1} and η_{2} are also minima of g_{1,γ}(ρ, λ; ξ, ·). Furthermore by Lemma 3.2, 1c), (suppressing ρ and ξ)

\frac{ρ}{ξ^{2}} η_{1}^{2} = g_{1,γ}(λ; η_{1}) = g_{1,1}(λ; η_{1}) < g_{1,1}(λ − σ; η_{1} − 1) ≤ g_{1,γ}(λ − σ; η_{1} − 1) ,

and analogously for η_{2}.

The last assertion follows by noting that η_{1} and η_{2} differ by a multiple of ξ and that η_{1} − η_{2} > ξ^{2}/ρ − ξ > −ξ.

For later use, we remark that the proof shows that for γ = 1, one has η_{1} = η_{+} and (analogously) η_{2} = η_{−} in the notation of Lemma 3.5. □

The following lemma plays a similar role for the description of \overline{f}_{1,γ} as Lemma 3.4 did for g_{1,γ}.

Lemma 3.10 For all (ρ, σ, ξ) ∈ S and all λ there is some η_{0} ∈ [−∞, ∞] such that

g_{1,γ}(ρ, λ; ξ, η) \{ \begin{matrix}< \\ ≥ \end{matrix} \} g_{1,γ}(ρ, λ − σ; ξ, η − 1) if \{ \begin{matrix}η < η_{0} \\ η ≥ η_{0} \end{matrix} .

Proof: Let g_{1}(η) = g_{1,γ}(ρ, λ; ξ, η) and g_{2}(η) = g_{1,γ}(ρ, λ−σ; ξ, η−1). Assuming the lemma to be false, there have to be η_{1} > η_{2} such that g_{1}(η_{1}) < g_{2}(η_{1}) and g_{1}(η_{2}) ≥ g_{2}(η_{2}). By Lemma 3.4, b), we may assume that η_{1} is a minimum of g_{1} and that η_{2} is a minimum of g_{2}. Since η_{2} is less than the biggest minimum η_{+} of g_{1}, we have by Lemma 3.5, e), that

g_{1}(η_{2}) ≤ ρ(η_{2} − ξ)^{2}/ξ^{2} + ξ < ρ(η_{2} − 1)^{2}/ξ^{2} = g_{2}(η_{2}) ,  (16)

which gives a contradiction. We have to verify the second inequality in (16). It is equivalent to

\frac{ξ^{2}}{1 − ξ} < ρ\frac{ξ + 1 − 2η_{2}}{ξ} ,

which follows from Lemma 3.7, c)—note that η_{2} < η_{+} ≤ \frac{1}{2}(ξ^{2}/ρ + ξ) < \frac{1}{2}. □

Now for the description of \overline{f}_{1,γ}. We first introduce a notation for the n that gives the minimal term in \overline{f}_{1,γ}. Let us define

n_{1,γ}(ρ, σ, λ; ξ, η) = max\{n | \overline{f}_{1,γ}(ρ, σ, λ; ξ, η) = g_{1,γ}(ρ, λ − nσ; ξ, η − n)\} .

Lemma 3.11 Let (ρ, σ, ξ) ∈ S and λ ∈ ℝ. For n ∈ ℤ, let

g_{n}(η) = g_{1,γ}(ρ, λ − nσ; ξ, η − n) .

Then there is a sequence of numbers ⋯ ≤ η_{−2} ≤ η_{−1} ≤ η_{0} ≤ η_{1} ≤ η_{2} ≤ ⋯ such that n − \frac{1}{2}ξ ≤ η_{n} ≤ n + 1 + \frac{1}{2}ξ for all n ∈ ℤ and such that for η_{n−1} ≤ η < η_{n},

n_{1,γ}(ρ, σ, λ; ξ, η) = n and \overline{f}_{1,γ}(ρ, σ, λ; ξ, η) = g_{n}(η) .

If γ = 1, all the minima of g_{n} occur between η_{n−1} and η_{n}.

Proof: Let η_{n} be such that g_{n}(η) < g_{n+1}(η) ⟺ η < η_{n}; this is possible by Lemma 3.10. By Lemma 3.9, we have η_{n} ≥ n − \frac{1}{2}ξ, η_{n} ≤ n + 1 + \frac{1}{2}ξ and η_{n} ≥ η_{n−1}. Hence, for η_{n−1} ≤ η < η_{n}, g_{n}(η) < g_{n+1}(η) < g_{n+2}(η) < … and g_{n}(η) ≤ g_{n−1}(η) ≤ g_{n−2}(η) ≤ . . .. Therefore, n_{1,γ}(…, η) = n, and \overline{f}_{1,γ}(…, η) = g_{n}(η). The last assertion follows from the proof of Lemma 3.9 and the remark concluding it. □

We now define \overline{h}_{1,γ} analogously for \overline{f}_{1,γ} as h_{1,γ} for g_{1,γ}, namely,

\overline{h}_{1,γ}(ρ, σ, λ; ξ, η) = h_{1,γ}(ρ, λ − n_{1,γ}(ρ, σ, λ; ξ, η)σ; ξ, η − n_{1,γ}(ρ, σ, λ; ξ, η)) .

Lemma 3.11 tells us that n_{1,γ} is a monotonically increasing, right continuous step function in η (the other parameters being fixed). Hence, \overline{h}_{1,γ} also is a right continuous step function in η.

3.5 An important estimate

The key point in approximating the sum in Lemma 3.3 is to have an estimate for the derivative w.r.t. λ of the term summed over. This is given by the following lemma:

Lemma 3.12 For (ρ, σ, ξ) ∈ S, λ ↦ \overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) is absolutely continuous, and

\frac{∂}{∂λ}\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = O(ρ) ,

uniformly in σ, λ, ξ.

Proof: We first claim that

\frac{∂}{∂λ}\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = 2ρ ∫_{0}^{1} \overline{h}_{1,γ}(ρ, σ, λ; ξ, η) dη
+ ξ(\overline{f}_{1,γ}(ρ, σ, λ; ξ, 0) − \overline{f}_{1,γ}(ρ, σ, λ; ξ, 1)) .

Looking at the definitions of g_{1,γ} and of \overline{f}_{1,γ}, we see immediately that

\frac{∂}{∂λ}\overline{f}_{1,γ}(ρ, σ, λ; ξ, η + λξ) = 2ρ\overline{h}_{1,γ}(ρ, σ, λ; ξ, η + λξ)

(in the sense of derivative of an absolutely continuous function). Writing

\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = ∫_{−λξ}^{1−λξ}\overline{f}_{1,γ}(ρ, σ, λ; ξ, η + λξ) dη ,

we see that by the chain rule,

\frac{∂}{∂λ}\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = ∫_{−λξ}^{1−λξ}2ρ\overline{h}_{1,γ}(ρ, σ, λ; ξ, η + λξ) dη
− ξ\overline{f}_{1,γ}(ρ, σ, λ; ξ, 1) + ξ\overline{f}_{1,γ}(ρ, σ, λ; ξ, 0)
= 2ρ ∫_{0}^{1} \overline{h}_{1,γ}(ρ, σ, λ; ξ, η) dη
+ ξ(\overline{f}_{1,γ}(ρ, σ, λ; ξ, 0) − \overline{f}_{1,γ}(ρ, σ, λ; ξ, 1)) ,

whence the claim.

By Lemmas 3.6 and 3.7,

∫_{0}^{1} \overline{h}_{1,γ}(ρ, σ, λ; ξ, η) dη = \frac{ξ}{2ρ}(\overline{f}_{1,γ}(ρ, σ, λ; ξ, 1) − \overline{f}_{1,γ}(ρ, σ, λ; ξ, 0)) + O(1) ,

since by Lemma 3.11, the number of jumps of n_{1,γ} in [0, 1] is at most three and the corresponding (η −n_{1,γ})’s in g_{1,γ}(ρ, λ−n_{1,γ}(…)σ; ξ, η −n_{1,γ}(…)) are in [−\frac{1}{2}, \frac{3}{2}]. This finally gives

\frac{∂}{∂λ}\overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = O(ρ) .

□

3.6 Result

Lemmas 3.3 and 3.12 now allow us to conclude the following result:

Proposition 3.13 If I = [\frac{p}{q}, \frac{p′}{q′}] is such that

p′q − pq′ = 1 and ((q/μ)^{3}, q′/q) ∈ S_{1} ,  (17)

then

∫_{I} Ψ_{1,γ}(μ, x) dx = \frac{1}{μ^{2}} F_{1,γ}(\frac{q}{μ}, \frac{q′}{μ} ) + O(\frac{1}{qq′\sqrt{μ}}) ,  (18)

where F_{1,γ} is a continuous function on ℝ_{+}^{2} that satisfies the following bounds:

F_{1,γ}(x, y) = O(1)  for x → ∞, y = x + O(x^{−2}) ,
F_{1,γ}(x, y) = O(x^{3})  for x → ∞, y = x^{−2} + O(x^{−5}) ,
F_{1,γ}(x, y) = O(x^{−3/2}) for x → 0, y = x^{−1/2} + O(x) .

Proof: Divide I at the point z = \frac{1}{2}(\frac{p}{q} + \frac{p′}{q′}) + \frac{q′−q}{2μ^{3}} and call I_{1} = [\frac{p}{q}, z] and I_{2} = [z, \frac{p′}{q′}]. Let ρ = (q/μ)^{3} and σ = q′/q. If 0 < x < z − \frac{p}{q}, we have that 0 < q^{2}x < \frac{q}{2q′} + \frac{q^{2}(q′−q)}{2μ^{3}} = \frac{1}{2σ} + \frac{1}{2}ρ(σ − 1); hence (ρ, σ, q^{2}x) ∈ S.

From Lemmas 3.3, 3.12 and 2.3 we get

Ψ_{1,γ}(μ, \frac{p}{q} + x) = \frac{μ}{q^{2}} ∑_{jmod q}\overline{Ψ}_{1,γ}(ρ, σ, \frac{j + δ}{q}; q^{2}x)
= \frac{μ}{q} ∫_{0}^{1} \overline{Ψ}_{1,γ}(ρ, σ, λ; q^{2}x) dλ + O(\frac{q}{μ^{2}} )
= \frac{μ}{q} ∫_{0}^{1} \overline{Ψ}_{1,γ}(ρ, σ, λ; q^{2}x) dλ + O(\frac{1}{\sqrt{μ}})

(using q = O(μ^{3/2}), which follows from qq′|q − q′| < μ^{3}). Note that δ has no influence on the approximating expression. This means that we may suppose δ = 0 without loss of generality. Now,

∫_{I_{1}} Ψ_{1,γ}(μ, x) dx = \frac{1}{ρμ^{2}} ∫_{0}^{\frac{1}{2} (1+ρ(σ−1))/σ}∫_{0}^{1} \overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) dλ dξ + O(\frac{1}{qq′\sqrt{μ}})
= \frac{1}{μ^{2}} F̃(\frac{q}{μ}, \frac{q′}{μ} ) + O(\frac{1}{qq′\sqrt{μ}}) ,

where, abbreviating l = l(x, y) = \frac{x}{2y} + \frac{x^{2}(y−x)}{2},

F̃(x, y) = \frac{1}{x^{3}} ∫_{0}^{l}∫_{0}^{1} \overline{Ψ}_{1,γ}(x^{3}, \frac{y}{x}, λ; ξ) dλ dξ .

F̃ is continuous because \overline{Ψ}_{1,γ} is.

Because of the symmetry and periodicity of Ψ (Lemma 3.1, 3b),c); remember that we may assume δ = 0), we have Ψ_{1,γ}(μ, 1 − x) = Ψ_{1,γ}(μ, x). Since I′ = [\frac{q′−p′}{q′} , \frac{q−p}{q}] also satisfies condition (17) and since I_{2} = 1 − I′_{1}, we get

∫_{I_{2}} Ψ_{1,γ}(μ, x) dx = \frac{1}{μ^{2}} F̃(\frac{q′}{μ} , \frac{q}{μ}) + O(\frac{1}{qq′\sqrt{μ}}) .

Hence, taking F_{1,γ}(x, y) = F̃(x, y) + F̃(y, x), we have equation (18). As to the bounds on F_{1,γ}, note that for 0 ≤ η ≤ 1,

\overline{f}_{1,γ}(ρ, σ, λ; ξ, η) ≤ g_{1,γ}(ρ, λ; ξ, η)
≤ g_{1,γ}(ρ, λ; ξ, 0) + η
≤ ρ + ξ + η
= O(ρ) + O(1) .

(For the last line, use Lemma 3.7, a).) This implies \overline{Ψ}_{1,γ}(ρ, σ, λ; ξ) = O(ρ) + O(1) and hence F̃(x, y) = O(l) + O(l/x^{3}). Using that l(x, y) = O(1) for x → ∞, y = x + O(x^{−2}) or y = x^{−2} + O(x^{−5}) and that l(x, y) = O(x^{3/2}) for x → 0, y = x^{−1/2} + O(x), the required bounds follow. □

4 Ψ_{a,b}(μ, ·) CONVERGES TO A CONSTANT 38

4 Ψ_{a,b}(μ, ·) converges to a constant

This section contains our main result, obtained by applying a general theorem to the results of sections 3. The theorem (Theorem 4.2) will be proved in section 5.

Call I_{μ} the set of all intervals I = [\frac{p}{q}, \frac{p′}{q′}] ⊂ [0, 1] satifying condition (17). Call P_{μ} the set of all pairs (q, q′) of positive integers such that q ⊥ q′ and ((q/μ)^{3}, q′/q) ∈ S_{1}. Then

Lemma 4.1 The map

I_{μ} ∋ [\frac{p}{q}, \frac{p′}{q′} ] ↦ (q, q′) ∈ P_{μ}

is a bijection. I_{μ} is finite, and the intervals in I_{μ} give a partition of [0, 1], i.e. there are 0 = x_{0} < x_{1} < … < x_{N} = 1 such that I_{μ} = {[x_{j−1}, x_{j}] | 1 ≤ j ≤ N}.

Proof: The map is clearly well-defined. It is bijective, because for q ⊥ q′, the equation p′q − pq′ = 1 has exactly one solution in integers p, p′ such that 0 ≤ p < q and 0 < p′ ≤ q′.

As to the finiteness of I_{μ}, we see that from q ⊥ q′ and qq′|q − q′| < μ^{3} we get q, q′ < \sqrt{2μ^{3}}. Therefore, P_{μ} and hence I_{μ}, too, are finite.

It is known (cf. [4]) that all intervals [\frac{p}{q}, \frac{p′}{q′}] ⊂ [0, 1] with p′q − pq′ = 1 occur exactly once as a node in the Stern–Brocot tree T . T is an infinite complete binary tree of intervals whose endpoints are given as fractions in lowest terms. It is defined as follows:

The root is given by [\frac{0}{1}, \frac{1}{1}]. The left and right successors of a node [\frac{p}{q}, \frac{p′}{q′}] are defined to be [\frac{p}{q}, \frac{p+p′}{q+q′}] and [\frac{p+p′}{q+q′} , \frac{p′}{q′}], resp. (It is easy to check by induction that the fractions that occur indeed are in lowest terms.)

We show by induction on T that I_{μ} contains exactly the leaves of some finite tree obtained by cutting T appropriately. This is done as follows. Call T_{1} the set of all nodes I = [\frac{p}{q}, \frac{p′}{q′}] of T such that qq′|q − q′| < μ^{3} and call T_{2} the set of all nodes I = [\frac{p}{q}, \frac{p′}{q′}] of T such that qq′(q + q′) ≥ μ^{3}. Then T = T_{1} ∪ T_{2} and I_{μ} = T_{1} ∩ T_{2}. It is immediately verified that if I ∈ T_{1} ∩ T_{2} (i.e. I ∈ I_{μ}), then the successors of I are in T_{2} \ T_{1}. On the other hand, if I ∈ T_{2} \T_{1}, then its successors stay in this set. Furthermore, if I ∈ T_{1} \T_{2}, its successors both stay in T_{1}. Since every infinite path in T eventually leaves T_{1}, it contains exactly one element of I_{μ}. This is equivalent to saying that I_{μ} partitions the unit interval. □

Now, let D ⊂ ℝ_{+}^{2} be the set of all (x, y) such that xy|x − y| < 1 ≤ xy(x + y). Then we have the following result:

Theorem 4.2 Let Ψ and F be nonnegative functions such that for all I = [\frac{p}{q}, \frac{p′}{q′}] ∈ I_{μ},

∫_{I} Ψ(μ, x) dx = \frac{1}{μ^{2}} F (\frac{q}{μ}, \frac{q′}{μ} ) + O(\frac{1}{qq′\sqrt{μ}}) .  (19)

Let F be continuous on ℝ_{+}^{2} and let F satisfy the following bounds:

F (x, y) = O(1)  for x → ∞, y = x + O(x^{−2}) ,
F (x, y) = O(x^{3})  for x → ∞, y = x^{−2} + O(x^{−5}) ,
F (x, y) = O(x^{−3/2}) for x → 0, y = x^{−1/2} + O(x) .

Then for every function φ on [0, 1] that is a uniform limit of step functions, we have the formula

lim_{μ→∞} ∫_{0}^{1} Ψ(μ, x)φ(x) dx = C ∫_{0}^{1} φ(x) dx ,

where the constant C is given by

C = \frac{6}{π^{2}} ∫_{D} F (x, y) d(x, y) .

This means that Ψ(μ, ·) converges to the constant function C in the topology of point-wise convergence in the dual space of the closure of the space of step functions in L^{∞}([0, 1]). Theorem 4.2 will be proved in section 5.

Taking this together with Proposition 3.13 and the simple facts of Lemma 3.1, 3a),d), we have the following corollary:

Corollary 4.3 For every function φ on [0, 1] that is a uniform limit of step functions, we have

lim_{μ→∞} ∫_{0}^{1} Ψ_{a,b}(μ, x)φ(x) dx = C(a, b) ∫_{0}^{1} φ(x) dx ,

where the constant C(a, b) is given by

C(a, b) = \frac{6}{π^{2}} ∫_{D} F_{a,b}(x, y) d(x, y) .

Here, we define F_{a,b} to be a^{−2/3}F_{1,b/a} for a ≥ b and to be b^{−2/3}F_{1,a/b} otherwise.

5 Proof of Theorem 4.2

In this section, Theorem 4.2 will be proved. Its assumptions imply that integrals ∫_{0}^{t} Ψ(μ, x) dx can be written in the form μ^{−2} ∑_{(u,v)∈L∩μD}F (u/μ, v/μ)

(plus some error term), where L is some set of lattice points, depending on t. The first step in the proof is to establish convergence for t = 1, i.e.

that μ^{−2} ∑_{{(u,v)∈ℤ^{2}∩μD \atop u⊥v}}F (u/μ, v/μ) → 6/π^{2} ∫_{D} F. For this step the boundedness

assumptions in the statement of Theorem 4.2 are needed. The second step is to show that the points in L are evenly distributed on a large scale. In order to do this, we need some estimates for the (classical) Kloosterman sums and make use of the theory of (periodic) distributions.

Recall the definition of D:

D = {(x, y) ∈ ℝ_{+}^{2} | xy|x − y| < 1 ≤ xy(x + y)} .

Let D′ be ‘one half’ of D, namely,

D′ = {(x, y) ∈ ℝ_{+}^{2} | y < x, xy(x − y) < 1 ≤ xy(x + y)} .

The solutions of the equations xy(x ± y) = 1 are y = −\frac{1}{2}x + \frac{1}{2} \sqrt{x^{2} + 4/x} and y = \frac{1}{2}x ± \frac{1}{2} \sqrt{x^{2} − 4/x}, resp. For a given large x, the set of y such that (x, y) ∈ D′ is therefore

[x^{−2} − x^{−5} + O(x^{−8}), x^{−2} + x^{−5} + O(x^{−8})[ ∪ ]x − x^{−2} − x^{−5} + O(x^{−8}), x[ ,

so that D′ has two “arms” going to infinity. Conversely, given some small y > 0, the corresponding x–values on the lower arm are \sqrt{y^{−1} + \frac{1}{4}y^{2}} − \frac{1}{2}y ≤ x < \sqrt{y^{−1} + \frac{1}{4}y^{2}} + \frac{1}{2}y; the length of this interval is y.

5 PROOF OF THEOREM 4.2 42

[figure: x; y; 0; 0; \sqrt[3]{\frac{1}{2}}; \sqrt[3]{4}; \sqrt[3]{\frac{1}{2}}; D′; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

5.1 A convergence result

Lemma 5.1 Let F : ℝ_{+}^{2} → ℝ be continuous and such that F is bounded on the upper arm of D′ and F (x, y) = O(x^{3}) on the lower arm of D′. Then

lim_{ε↓0} \underbrace{ε^{2} ∑_{{a,b∈ℕ \atop (εa,εb)∈D′}}F (εa, εb)}_{= I_{ε}} = ∫_{D′} F (x, y) d(x, y) ,

the sum converges absolutely for all ε > 0, and I_{ε} is bounded for ε > 0.

Proof: First of all, the sum is finite, because there are no points (εa, εb) ∈ D′ with a ≫ ε^{−3/2}, hence absolute convergence is a trivial matter.

Next, denoting by D′_{X} the part of D′ where x > X, we show that sum and integral are O(1/X), uniformly in ε, when restricted to D′_{X}. For the integral, this is fairly clear, since the bounds on F imply that it is dominated by ∫_{X}^{∞}x^{−2} dx = 1/X. For the sum, we consider the two arms of D′ separately. Looking at the upper arm, we see that the number of b’s such that (εa, εb) lies in it is O(a^{−2}ε^{−3}), so that this part of the sum is dominated by ε^{2} ∑_{a>X/ε} a^{−2}ε^{−3} = O(1/X). As to the lower arm, the description of D′ above

tells us that there are exactly b a’s such that (εa, εb) is in the lower arm, if bε ≤ 2^{−1/3}. The boundedness condition for F on the lower arm implies F (x, y) = O(y^{−3/2}) there, hence the second part of the sum is dominated by

ε^{2} ∑_{0<b<X^{−2}/ε}b(bε)^{−3/2} = O(1/X).

Since the claim is correct when replacing D′ by D′ \ D′_{X} (by bounded convergence of step functions to F · χ_{D′\D′_{X}} on the compact domain [0, X] × [0, X]), the lemma follows from the above estimate of the remainder terms: The two sides of the equality differ by at most O(1/X), and X can be made arbitrarily large.

Boundedness of I_{ε} follows from uniformicity in ε of the above estimate by taking X = 2^{−1/3}. □

5.2 A number theoretic equidistribution property

We put T = ℝ/ℤ × ℝ/ℤ and consider for n ∈ ℕ the following distribution D_{n} ∈ D′(T):

⟨D_{n}, f⟩ := \frac{1}{φ(n)} ∑_{{a,bmod n \atop ab≡1}} f(\frac{a}{n}, \frac{b}{n});

φ will denote the Euler totient function throughout this and the following subsection (φ(n) = #{k ∈ ℕ | 0 ≤ k < n, k ⊥ n}). We then have:

Proposition 5.2

D_{n} → 1 in D′(T) as n → ∞ .

More precisely, for every fixed ε > 0,

⟨D_{n} − 1, f⟩ = O(n^{−1/2+ε}∥f∥_{3})  (20)

for f ∈ D(T), where

∥f∥_{3} = max{max_{x,y} |∂_{1}^{α}∂_{2}^{β}f(x, y)| | α + β = 3} .

(Here, 1 denotes the distribution generated by the constant function 1.)

Proof: We look at the Fourier coefficients of D_{n} (u, v ∈ ℤ):

D̂_{n}(u, v) = ⟨D_{n}, (x, y) ↦ e^{−2πi(ux+vy)}⟩
= \frac{1}{φ(n)} ∑_{{a,bmod n \atop ab≡1}} e^{−2πi(ua+vb)/n}

= \frac{1}{φ(n)}S(−u, −v; n) ,

where S(u, v; n) denotes the Kloosterman sum. We have the following estimates (cf. [9] and [12]):

S(u, v; mn) = S(u, v_{1}; m)S(u, v_{2}; n) for m ⊥ n and suitable v_{1}, v_{2}
|S(u, v; p^{r})| ≤ 2p^{r/2}(u ⊓ p^{r})^{1/2}  for odd primes p
|S(u, v; 2^{r})| ≤ 2\sqrt{2} 2^{r/2}(u ⊓ 2^{r})^{1/2}

(a ⊓ b here denotes the g.c.d. of a and b.) For u ≠ 0, this gives

|S(u, v; n)| ≤ \sqrt{2|u|} 2^{ω(n)}\sqrt{n} ,

where ω(n) denotes the number of different prime divisors of n. It is a wellknown fact (see Lemmas B.1 and B.2) that 2^{ω(n)} ≪ n^{ε} and φ(n) ≫ n^{1−ε} for all (fixed) ε > 0. Hence

D̂_{n}(u, v) = O(min{|u|, |v|}^{1/2}n^{−1/2+ε}) for u ≠ 0, v ≠ 0
D̂_{n}(u, 0) = O(|u|^{1/2}n^{−1/2+ε})  for u ≠ 0
D̂_{n}(0, v) = O(|v|^{1/2}n^{−1/2+ε})  for v ≠ 0

(21)

where the O–constants depend on the fixed ε > 0. In particular, D̂_{n}(u, v) → 0, as n → ∞ for all (u, v) ≠ (0, 0), and since D̂_{n}(0, 0) = 1, our claim is proved (taking into account the trivial bound |D̂_{n}(u, v)| ≤ 1 for all n, u, v), see Proposition A.2.

The bound (20) comes from ⟨D_{n}, f⟩ = ∑_{u,v} D̂_{n}(−u, −v)f̂(u, v) (see Proposition A.1) and (21), since (by partial integration)

|f̂(u, v)| = |∫_{T} f(x, y)e^{−2πi(ux+vy)} d(x, y)| ≤ (2π)^{−|α+β|}|u|^{−α}|v|^{−β} max |∂_{1}^{α}∂_{2}^{β}f| .

□

Remark: Using elementary means, i.e. only the results of [9], it can be shown that (21) holds with −1/4 + ε in place of −1/2 + ε.

We need the following consequence of Proposition 5.2:

Proposition 5.3 For nonnegative reals u, v and a positive integer n let

R_{n}(u, v) = \frac{1}{φ(n)}#\{(a, b) ∈ ℤ^{2} | ab ≡ 1 mod n, 0 < a < un, 0 < b < vn\} .

Then for every ε > 0, there is an N such that for all n ≥ N and all u, v

|R_{n}(u, v) − uv| < (u + v + 1)ε .

In particular, R_{n}(u, v) → uv, as n → ∞.

Proof: Heuristically, we have R_{n}(u, v) = “⟨D_{n}, χ_{]0,u[×]0,v[}⟩”. Now χ_{]0,u[×]0,v[} is defined on ℝ^{2} and not on T, so we will have to make it periodic. And it is not smooth either, so we have to approximate suitably by smooth functions.

Let ε > 0. Choose h ∈ C^{∞}(ℝ) such that there is some g ∈ D(ℝ) with |h−χ_{[0,∞[}| ≤ g and ∫ g < ε. Choose k_{1}, k_{2} ∈ C^{∞}(ℝ) such that k_{2} ≤ χ_{[0,∞[} ≤ k_{1} and k_{1} −k_{2} ∈ D(ℝ) with ∫ (k_{1} −k_{2}) < ε. We may assume that the supports of g, k′_{1} and k′_{2} are contained in [−\frac{1}{2}, \frac{1}{2}]. Put f(x, y) = (h(x) − h(x − u))(h(y) − h(y − v)), then (use that ab − a′b′ = a′(b − b′) + (a − a′)b′ + (a − a′)(b − b′))

|f(x, y) − χ_{]0,u[×]0,v[}(x, y)|

= |χ_{]0,u[}(x)(h(y) − h(y − v) − χ_{]0,v[}(y))
+ (h(x) − h(x − u) − χ_{]0,u[}(x))χ_{]0,v[}(y)

+ (h(x) − h(x − u) − χ_{]0,u[}(x))(h(y) − h(y − v) − χ_{]0,v[}(y))|

≤ χ_{]0,u[}(x)(g(y) + g(y − v)) + (g(x) + g(x − u))χ_{]0,v[}(y)
+ (g(x) + g(x − u))(g(y) + g(y − v))
≤ (k_{1}(x) − k_{2}(x − u))(g(y) + g(y − v))
+ (g(x) + g(x − u))(k_{1}(y) − k_{2}(y − v))
+ (g(x) + g(x − u))(g(y) + g(y − v))
= g̃(x, y) ,

where g̃ ∈ D(ℝ^{2}) and

∫ g̃ = 2 ∫ (k_{1} − k_{2}(· − u)) ∫ g + 2 ∫ (k_{1} − k_{2}(· − v)) ∫ g + 4(∫ g)^{2}
≤ 2(u + v)ε + 8ε^{2} ,

since ∫ (k_{1}−k_{2}(·−u)) = u+∫ (k_{1}−k_{2}) ≤ u+ε. We let \overline{χ}(x, y) = ∑_{a,b∈ℤ} χ_{]0,u[}(x+

a)χ_{]0,v[}(y + b), \overline{f}(x, y) = ∑_{a,b∈ℤ} f(x + a, y + b) and \overline{g}(x, y) = ∑_{a,b∈ℤ} g̃(x + a, y + b).

For functions F_{1}, F_{2} ∈ C^{∞}(ℝ) let

M(F_{1}, F_{2}) = max{∥F_{1}∥ ∥F′′′_{2}∥, ∥F′_{1}∥ ∥F′′_{2}∥, ∥F′′_{1}∥ ∥F′_{2}∥, ∥F′′′_{1}∥ ∥F_{2}∥} ,

where ∥ · ∥ denotes sup-norm. Then it is easily verified that ∥\overline{f}∥_{3} ≤ 4 M(h, h) and ∥\overline{g}∥_{3} ≤ 4 M(k_{1}, g) + 4 M(g, k_{2}) + 4 M(g, g); these bounds do not depend on u or v. For n sufficiently large, the bound (20) of Proposition 5.2 then yields

|R_{n}(u, v) − uv| = |\frac{1}{φ(n)} ∑_{{a,bmod n \atop ab≡1}} \overline{χ}(\frac{a}{n}, \frac{b}{n}) − ∫_{T} \overline{χ}(x, y) d(x, y)|
≤ |⟨D_{n} − 1, \overline{f}⟩| + |⟨D_{n}, \overline{g}⟩| + |⟨1, \overline{g}⟩|
≤ |⟨D_{n} − 1, \overline{f}⟩| + |⟨D_{n} − 1, \overline{g}⟩| + 2|⟨1, \overline{g}⟩|
< ε + ε + 2(2(u + v)ε + 8ε^{2})
≤ 4(u + v + 1)ε if ε ≤ \frac{1}{8}.
□

5.3 Application to some sums

Let f : ℝ_{+}^{2} → ℝ be integrable and such that there is an increasing sequence of step functions (g_{n}) with g_{n} ≤ f everywhere and g_{n} ↑ f almost everywhere. Furthermore, assume that

lim_{ε↓0} \underbrace{ε^{2} ∑_{a,b∈ℕ} f(εa, εb)}_{= I_{ε}(f)} = ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy

where the sum converges absolutely for all ε > 0 and I_{ε}(f) ≤ C for all ε > 0. For 0 ≤ t ≤ 1, let

M_{t} = {(a, n) ∈ ℕ^{2} | ∃b ∈ ℕ : 0 < b < tn and ab ≡ 1 mod n}

and

S_{f}(ε, t) = ε^{2} ∑_{(a,n)∈M_{t}}f(εa, εn) ,

where ε > 0. Then we have the following result: Proposition 5.4

lim_{ε↓0} S_{f}(ε, t) = t \frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy for all t ∈ [0, 1] .

Proof: Let us first take f = χ_{[0,u[×[0,v[}. Then

S_{f}(ε, t) = ε^{2}#(M_{t} ∩ (]0, \frac{u}{ε}[×]0, \frac{v}{ε}[))
= ε^{2} ∑_{1≤n<v/ε}φ(n)R_{n}(\frac{u}{εn}, t)
=^{5.3} ε^{2} ∑_{1≤n<v/ε}φ(n)(\frac{tu}{εn} + o_{n→∞}(1)(\frac{u}{εn} + 1))
= (t + o_{ε→0}(1))uε ∑_{1≤n<v/ε} \frac{φ(n)}{n} + ε^{2} ∑_{1≤n<v/ε}o_{n→∞}(n)
=^{B.3} (t + o_{ε→0}(1))uε\frac{v}{ε} (\frac{6}{π^{2}} + o_{ε→0}(1)) + ε^{2}o_{ε→0}(v^{2}/ε^{2})
= \frac{6}{π^{2}} tuv + o_{ε→0}(1) .

This proves the claim for step functions f. Now let f be arbitrary, and take a sequence of step functions (g_{n}) as at the beginning of this subsection. Then, since (S_{g_{n}}(ε, t))_{n} is increasing,

lim inf_{ε↓0} S_{f}(ε, t) ≥ lim inf_{ε↓0} lim_{n→∞} S_{g_{n}}(ε, t)
≥ lim_{n→∞} lim_{ε↓0} S_{g_{n}}(ε, t)
= lim_{n→∞} t\frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}g_{n}(x, y) dx dy

= t\frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy .

The last equality comes from monotonic convergence. In the same way, one can show (using that equality holds for step functions)

lim inf_{ε↓0}(S_{f}(ε, 1) − S_{f}(ε, t)) ≥ (1 − t)\frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy ,

that is,

lim sup_{ε↓0} S_{f}(ε, t) ≤ t\frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy

+ lim_{ε↓0} S_{f}(ε, 1) − \frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy .

Hence, it suffices to prove the claimed equality in the case t = 1. This is established as follows: (μ denotes the Möbius function)

lim_{ε↓0} S_{f}(ε, 1) = lim_{ε↓0} ε^{2} ∑_{a⊥n} f(εa, εn)
= lim_{ε↓0} ε^{2} ∑_{d∈ℕ} μ(d) ∑_{a,n} f(εda, εdn)
= lim_{ε↓0} ∑_{d∈ℕ} \frac{μ(d)}{d^{2}}I_{dε}(f)

= ∑_{d∈ℕ} \frac{μ(d)}{d^{2}} lim_{ε↓0} I_{dε}(f)
= ∑_{d∈ℕ} \frac{μ(d)}{d^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy

= \frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}f(x, y) dx dy .

Exchanging lim and ∑ is allowed because of the uniformly absolute convergence of the sum (I_{ε}(f) ≤ C for all ε > 0, hence the sum is dominated by ∑_{d} C/d^{2}). □

5.4 End of proof

Let Ψ and F as in the statement of Theorem 4.2. Then F (x, y) and F (y, x) both satisfy the conditions of Lemma 5.1. We recall that q, q′ = O(μ^{3/2}) for (q, q′) ∈ P_{μ} and observe that the bounds on F then imply that ∫_{I} Ψ(μ, x) dx = O(μ^{−1/2}) for I ∈ I_{μ}.

Let 0 < t ≤ 1 and take φ = χ_{[0,t[}. Then from the above remark, we have

∫_{0}^{1} Ψ(μ, x)φ(x) dx = ∫_{0}^{t} Ψ(μ, x) dx
= \frac{1}{μ^{2}} ∑_{I} F (\frac{q}{μ}, \frac{q′}{μ} ) + O(μ^{−1/2}) ,

where the sum is taken over those I = [\frac{p}{q}, \frac{p′}{q′}] ∈ I_{μ} that have \frac{p′}{q′} < t. Equivalently, we may sum over those (q, q′) ∈ P_{μ} that are in M_{t} (because p′q ≡ 1 mod q′). Since P_{μ} = μD ∩ ℤ^{2}, we get, writing ε for μ^{−1},

∫_{0}^{1} Ψ(μ, x)φ(x) dx = ε^{2}  ∑_{(q,q′)∈ε^{−1}D∩M_{t}}F (εq, εq′) + O(\sqrt{ε})
= ε^{2}  ∑_{(q,q′)∈ε^{−1}D′∩M_{t}}(F (εq, εq′) + F (εq′, εq)) + O(\sqrt{ε}) .

Let Φ(x, y) = (F (x, y) + F (y, x))χ_{D′}. Since Φ is nonnegative and F is continuous, Φ can be approximated by an increasing sequence of step functions g_{n} such that g_{n} ≤ Φ everywhere and g_{n} ↑ Φ almost everywhere on ℝ_{+}^{2}. Furthermore, by Lemma 5.1,

lim_{ε↓0} ε^{2} ∑_{q,q′∈ℕ} Φ(εq, εq′) = ∫_{0}^{∞}∫_{0}^{∞}Φ(x, y) d(x, y) ,

and the sum converges absolutely for all ε > 0. By Proposition 5.4, we now get

lim_{μ→∞} ∫_{0}^{1} Ψ(μ, x)φ(x) dx = t \frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}Φ(x, y) dx dy

= \frac{6}{π^{2}} ∫_{0}^{∞}∫_{0}^{∞}Φ(x, y) dx dy ∫_{0}^{1} φ(x) dx

= \frac{6}{π^{2}} ∫_{D} F (x, y) d(x, y) ∫_{0}^{1} φ(x) dx ,

hence the claim is proved for our special choice of φ. By taking linear combinations, we see that this holds for step functions φ, too.

Now let φ be any function on [0, 1] that can be approximated uniformly by step functions. Then for every ε > 0, there are step functions s_{1} and s_{2} such that φ − ε ≤ s_{1} ≤ φ ≤ s_{2} ≤ φ + ε. Since Ψ is nonnegative, the assertion for step functions yields

| lim_{μ→∞} ∫_{0}^{1} Ψ(μ, x)φ(x) dx − C ∫_{0}^{1} φ(x) dx| ≤ Cε ,

where C = \frac{6}{π^{2}} ∫_{D} F (x, y) d(x, y). Letting ε ↓ 0, we have the result that was to be proved.

6 DEPENDENCE ON a AND b 51

6 Dependence on a and b

In this section, we will study the function

C : [0, ∞[^{2}\{(0, 0)} → ℝ_{+} , (a, b) ↦ C(a, b)

defined by Corollary 4.3. The main result will be that it is continuous. We have the following properties:

Lemma 6.1

a) C(a, b) = C(b, a) .

b) C(ta, tb) = t^{−2/3}C(a, b) for t > 0 .

c) If a ≥ a′ and b ≥ b′, then C(a, b) ≤ C(a′, b′) .

d) If 1/a = 1/a_{1} + 1/a_{2} and 1/b = 1/b_{1} + 1/b_{2}, then C(a, b)^{3/2} ≥ C(a_{1}, b_{1})^{3/2} + C(a_{2}, b_{2})^{3/2} .

Proof: a) This follows from Lemma 3.1, 3a) and 3b) (we may assume δ = 0, since C(a, b) does not depend on δ).

b) is a consequence of Lemma 3.1, 3d).

c) comes from Lemma 3.1, 3e).

d) We have ℓ_{a,b}(x) = ℓ_{a_{1},b_{1}}(x) + ℓ_{a_{2},b_{2}}(x). Let C_{j} = C(a_{j}, b_{j}) and t_{j} = C_{j}^{3/2}/(C_{1}^{3/2} + C_{2}^{3/2}). Then

min\{\frac{k^{2}}{μ^{2}} + μℓ_{a,b}(kx − y − ν) | k, ν ∈ ℤ\}

= min\{t_{1}^{1/3}(\frac{k^{2}}{(μt_{1}^{−1/3})^{2}} + μt_{1}^{−1/3}ℓ_{a_{1},b_{1}}(kx − y − ν))

+ t_{2}^{1/3}(\frac{k^{2}}{(μt_{2}^{−1/3})^{2}} + μt_{2}^{−1/3}ℓ_{a_{2},b_{2}}(kx − y − ν)) | k, ν ∈ ℤ\}

≥ t_{1}^{1/3} min\{\frac{k^{2}}{(μt_{1}^{−1/3})^{2}} + μt_{1}^{−1/3}ℓ_{a_{1},b_{1}}(kx − y − ν) | k, ν ∈ ℤ\}

+ t_{2}^{1/3} min\{\frac{k^{2}}{(μt_{2}^{−1/3})^{2}} + μt_{2}^{−1/3}ℓ_{a_{2},b_{2}}(kx − y − ν) | k, ν ∈ ℤ\} ,

hence

C(a, b) ≥ t_{1}^{1/3}C_{1} + t_{2}^{1/3}C_{2} = (C_{1}^{3/2} + C_{2}^{3/2})^{2/3} .
□

Lemma 6.2 ℝ_{+} ∋ α ↦ κ(α) = C(1, 1/α)^{3/2} is a monotonically increasing, bounded function that is convex from above. κ is continuous, and left and right derivatives ∂_{−}κ and ∂_{+}κ exist and are finite. κ satisfies the functional equation κ(1/α) = κ(α)/α, and lim_{α→0} κ(α) = 0.

Proof: Monotonicity comes from Lemma 6.1, c). κ is bounded because C(1, α) ≤ C(1, 0) < ∞. Convexity is a consequence of Lemma 6.1, b),d):

κ(tα + (1 − t)α′) = C(\frac{1}{t + (1 − t)}, \frac{1}{tα + (1 − t)α′} )^{3/2}
≥ C(\frac{1}{t}, \frac{1}{tα})^{3/2} + C(\frac{1}{1 − t}, \frac{1}{(1 − t)α′} )^{3/2}
= tκ(α) + (1 − t)κ(α′) .

Every function with these properties is continuous [7, Thm. 3.2], and has finite left and right derivatives. The functional equation follows from Lemma 6.1, a) and b). The limit formula then comes from the boundedness of κ by letting α → ∞ in the functional equation. □

Corollary 6.3 C is continuous.

Proof: C(a, b) = a^{−2/3}κ(a/b)^{2/3} = b^{−2/3}κ(b/a)^{2/3}, and κ is continuous. □ We state without proof the following proposition.

Proposition 6.4 γ ↦ C(1, γ) is differentiable. The function

γ ↦ (1 + γ)^{2} \frac{∂}{∂γ} C(1, γ)

is decreasing, and

\frac{∂}{∂γ} C(1, γ)|_{γ=1} = −\frac{1}{3}C(1, 1) .

6 DEPENDENCE ON a AND b 53

(The value of \frac{∂}{∂γ} C(1, γ)|_{γ=1} is obtained by differentiating the equation C(1, 1/γ) = γ^{2/3}C(1, γ) and setting γ = 1.) Corollary 6.5 C(1, ·) is decreasing. For all γ,

C(1, γ) ≤ \frac{5 + γ}{3(1 + γ)}C(1, 1) .

In particular, C(1, γ) ≤ C(1, 0) ≤ \frac{5}{3}C(1, 1). Proof: Write c(γ) = C(1, γ). c is decreasing by Lemma 6.1, c). By Proposition 6.4, c′(γ) \left\{{≥ \atop ≤}\right\} − \frac{4}{3}c(1)/(1 + γ)^{2} for γ \left\{{≤ \atop ≥}\right\} 1. Hence,

c(γ) = c(1) + ∫_{1}^{γ} c′(t) dt ≤ c(1)(1 + \frac{4}{3} ∫_{γ}^{1} \frac{dt}{(1 + t)^{2}} ) = c(1)\frac{5 + γ}{3(1 + γ)} .

□

7 Ψ–FUNCTIONS WITH NON-CONSTANT a AND b 54

7 Ψ–functions with non-constant a and b

In this section, we put together the results we have got so far to handle functions of the type x ↦ Ψ_{a(x),b(x)}(μ, x) with continuous functions a and b. We then apply the result we get to the problem we started with: the asymptotics of T (n).

Let (a, b) : [0, 1] → [0, ∞[^{2}\{(0, 0)} be continuous and set

Ψ_{a,b}(μ, x) = Ψ_{a(x),b(x)}(μ, x) .

Then we have a result analogous to Corollary 4.3:

Theorem 7.1 For every function φ on [0, 1] that is a uniform limit of step functions, we have

lim_{μ→∞} ∫_{0}^{1} Ψ_{a,b}(μ, x)φ(x) dx = ∫_{0}^{1} C(a(x), b(x))φ(x) dx .

Proof: As in the proof of Theorem 4.2, it suffices to show the assertion for φ = χ_{[0,t[}.

Because of the monotonicity of Ψ in (a, b) we have for every interval I

that Ψ_{a_{+},b_{+}}(μ, x) ≤ Ψ_{a,b}(μ, x) ≤ Ψ_{a_{−},b_{−}}(μ, x) for x ∈ I, where a_{+} = max_{I} a

and a_{−} = min_{I} a and analogously for b. Let ε > 0. Since x ↦ C(a(x), b(x)) is continuous, we can divide [0, t] into small intervals I such that C(a_{−}, b_{−}) − C(a_{+}, b_{+}) < ε for each such I. Then,

| lim_{μ→∞} ∫_{I} Ψ_{a,b}(μ, x) dx − ∫_{I} C(a(x), b(x)) dx| ≤ ελ(I)

(λ here denotes Lebesgue measure), hence

| lim_{μ→∞} ∫_{0}^{t} Ψ_{a,b}(μ, x) dx − ∫_{0}^{t} C(a(x), b(x)) dx| ≤ εt .

Letting ε → 0, we see that the claimed equality must hold. □ As a corollary, we now have proved formula (1):

7 Ψ–FUNCTIONS WITH NON-CONSTANT a AND b 55 Corollary 7.2

T (n) = \frac{1}{8}n^{4} − Cn^{8/3} + o(n^{8/3}) .

Here, C = ∫_{0}^{1} C(2x, 2(1 − x)) dx = ∫_{0}^{1} C(x, 2 − x) dx (use symmetry of C(a, b)).

From Corollary 6.5, we get the following bounds on C:

3( ^{3} \sqrt{2} − 1)C(1, 1) ≤ C ≤ (2 ^{3} \sqrt{2} − \frac{3}{2})C(1, 1) .

The difference of the bounds is ∼ 0.24 · C(1, 1). The value of C(1, 1) will be determined in section 8. From this, we get the numerical bounds

0.476957 ≤ C ≤ 0.623806 .

8 COMPUTING C(1, 1) 56

8 Computing C(1, 1)

In this section, we compute an explicit value for C(1, 1).

We first need an explicit formula for F_{1,1}(x, y). This is given by the following proposition:

Proposition 8.1 F_{1,1}(x, y) = F̃(x, y) + F̃(y, x), where, abbreviating l = l(x, y) = \frac{1}{2xy} + \frac{y−x}{2},

12F̃(x, y) = 3\frac{l}{x} + x^{2}l + (\frac{1}{3}x^{3} − 1)l^{3} + \frac{1}{2}x^{2}l^{4} + \frac{1}{5}xl^{5}  (22)
− x^{5} ∫_{0}^{l} s(\frac{u − y}{x})^{2}(1 − s(\frac{u − y}{x}))^{2} du .  (23)

Proof: Going back to Proposition 3.13, we see that

F̃(x, y) = \frac{1}{x^{3}} ∫_{0}^{lx^{2}} ∫_{0}^{1}∫_{0}^{1} \overline{f}_{1,1}(x^{3}, \frac{y}{x}, λ; ξ, η) dλ dη dξ .

If (ρ, σ, ξ) ∈ S, we get from Lemmas 3.5 and 3.7, c), that η_{+} ≤ \frac{1}{2} and η_{−} ≥ −\frac{1}{2}. From this and Lemma 3.11, we see that

∫_{0}^{1}∫_{0}^{1} \overline{f}_{1,1}(x^{3}, \frac{y}{x}, λ; ξ, η) dλ dη = ∫_{−1/2}^{1/2} ∫_{0}^{1} g_{1,1}(x^{3}, λ; ξ, η) dλ dη − E(ξ) ,

where E(ξ) is an error term arising from the fact that η_{n} is not exactly equal to n + \frac{1}{2} in Lemma 3.11. Writing

δ(ρ, σ, λ; ξ) = η_{0} − \frac{1}{2} = \frac{1}{2}(g_{1,1}(ρ, λ − σ; ξ, −\frac{1}{2}) − g_{1,1}(ρ, λ; ξ, \frac{1}{2})) ,

we have

E(ξ) = ∫_{0}^{1} δ(x^{3}, \frac{y}{x}, λ; ξ)^{2} dλ . [figure: \frac{1}{2}; η_{0}; δ; 2δ; ←; →; g_{1,1}(λ; ·); g_{1,1}(λ − σ; · − 1)]

A straightforward calculation gives

∫_{0}^{1} g_{1,1}(x^{3}, λ; ξ, η) dλ

= \{ \begin{matrix}−η − \frac{ξ^{2}}{4x^{3}} + \frac{1}{12}x^{3}  for & η ≤ −\frac{ξ^{2}}{2x^{3}} − \frac{1}{2}ξ \\ \frac{x^{3}}{ξ(x^{3}+ξ)}η^{2} + \frac{1}{4}ξ + \frac{1}{12}x^{3} for & −\frac{ξ^{2}}{2x^{3}} − \frac{1}{2}ξ ≤ η ≤ \frac{ξ^{2}}{2x^{3}} − \frac{1}{2}ξ \\ η − \frac{ξ^{2}}{4x^{3}} + \frac{1}{12}x^{3}  for & \frac{ξ^{2}}{2x^{3}} − \frac{1}{2}ξ ≤ η \end{matrix}

Integration over η and ξ and multiplication by 12/x^{3} then leads to the first part (22) of the result.

Now for E. Define θ_{+}(λ, ξ) and θ_{−}(λ, ξ) by

η_{+}(x^{3}, λ; ξ) = \frac{ξ^{2}}{2x^{3}} + θ_{+}(λ, ξ)ξ ,
η_{−}(x^{3}, λ − \frac{y}{x}; ξ) = −\frac{ξ^{2}}{2x^{3}} + θ_{−}(λ, ξ)ξ .

Then we have by Lemma 3.5, f),g), that |δ(…)| = \frac{1}{2}x^{3}|θ_{+}^{2} − θ_{−}^{2}| and hence

E(ξ) = \frac{1}{4}x^{6} ∫_{0}^{1} (θ_{+}(λ, ξ)^{2} − θ_{−}(λ, ξ)^{2})^{2} dλ .

It is not difficult to compute this integral (taking into account that the difference of θ_{+} and θ_{−} is constant mod 1) and thus finally to obtain the second part (23) of the result. □

C(1, 1) is given by

C(1, 1) = \frac{6}{π^{2}} ∫_{D} F_{1,1}(x, y) d(x, y)
= \frac{6}{π^{2}} ∫_{D} (F̃(x, y) + F̃(y, x)) d(x, y)
= \frac{12}{π^{2}} ∫_{D} F̃(x, y) d(x, y) ,

Using the substitution

x = ξ^{−1/3}η^{−1/3}, y = ξ^{−1/3}η^{2/3},  d(x, y) = \frac{1}{3}ξ^{−5/3}η^{−2/3} d(ξ, η) , (24)

8 COMPUTING C(1, 1) 58 we get

C(1, 1) = \frac{4}{π^{2}} ∫_{D̃} F̃(ξ^{−1/3}η^{−1/3}, ξ^{−1/3}η^{2/3}) ξ^{−5/3}η^{−2/3} d(ξ, η) .

The domain of integration D̃ is given here by |ξ − 1| < η ≤ ξ + 1:

[figure: ξ; η; 0; 0; 1; 1; D̃]

Let us look at the term coming from (23) first:

− ∫_{D} ∫_{0}^{l(x,y)}x^{5}s(\frac{u − y}{x})^{2}(1 − s(\frac{u − y}{x}))^{2} du (.x, y)

= −\frac{1}{3} ∫_{D̃} ∫_{0}^{\frac{ξ+η−1}{2ξ^{1/3}η^{1/3}}}s(ξ^{1/3}η^{1/3}u − η)^{2} ×

(1 − s(ξ^{1/3}η^{1/3}u − η))^{2}ξ^{−10/3}η^{−7/3} du d(ξ, η)

= −\frac{1}{3} ∫_{D̃} ∫_{(1−ξ+η)/2}^{η} s(ζ)^{2}(1 − s(ζ))^{2}ξ^{−11/3}η^{−8/3} dζ d(ξ, η)

= −\frac{1}{3} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}η^{−8/3} dη ∫_{η+1−2ζ}^{η+1} ξ^{−11/3} dξ

− \frac{1}{3} ∫_{1}^{∞}s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}η^{−8/3} dη ∫_{η−1}^{η+1}ξ^{−11/3} dξ

= −\frac{1}{8} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}((η(η + 1 − 2ζ))^{−8/3} − (η(η + 1))^{−8/3}) dη

− \frac{1}{8} ∫_{1}^{∞}s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}(η(η − 1))^{−8/3} − (η(η + 1))^{−8/3}) dη

= −\frac{1}{8} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}((η(η + 1 − 2ζ))^{−8/3} − (η(η + 1))^{−8/3}) dη

− \frac{1}{8} ∫_{1}^{∞}s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ−1}^{ζ} (η(η + 1))^{−8/3} dη

= −\frac{1}{8} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}((η(η + 1 − 2ζ))^{−8/3} − (η(η + 1))^{−8/3}) dη

− \frac{1}{8} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}(η(η + 1))^{−8/3} dη

= −\frac{1}{8} ∫_{0}^{1} s(ζ)^{2}(1 − s(ζ))^{2} dζ ∫_{ζ}^{∞}(η(η + 1 − 2ζ))^{−8/3} dη

= −\frac{1}{8} ∫_{0}^{1} ζ^{2}(1 − ζ)^{2} dζ ∫_{ζ}^{∞}(η(η + 1 − 2ζ))^{−8/3} dη

= −\frac{1}{256} ∫_{D̃} (ξ − η + 1)^{2}(η − ξ + 1)^{2}ξ^{−8/3}η^{−8/3} d(ξ, η) ,

8 COMPUTING C(1, 1) 60 where for the last step we have used the substitution

ζ ↦ \frac{1}{2}(−ξ + η + 1) .

Taking this together with what we get from (22) by our substitution (24), we have the following nice expression:

∫_{D} F̃(x, y) d(x, y)

= \frac{1}{138240} ∫_{D̃} (−21ξ^{5} − 180ξ^{4}η + 4290ξ^{3}η^{2} + 4740ξ^{2}η^{3} − 405ξη^{4} + 24η^{5}

+ 1440ξ^{3}η − 2880ξ^{2}η^{2} + 1440ξη^{3} + 10ξ^{3} + 60ξ^{2}η + 330ξη^{2} − 80η^{3}

− 1440ξη + 75ξ + 120η − 64)ξ^{−11/3}η^{−8/3} d(ξ, η) .

We therefore need a method of computing integrals like

∫_{D̃} ξ^{α−1}η^{β} d(ξ, η) .

Let us first suppose that α, β > −1 and α + β < −1. Then

α ∫_{D̃} ξ^{α−1}η^{β} d(ξ, η)

= ∫_{0}^{1} η^{β} dη ∫_{1−η}^{1+η}αξ^{α−1} dξ + ∫_{1}^{∞}η^{β} dη ∫_{η−1}^{η+1}αξ^{α−1} dξ
= ∫_{0}^{1} η^{β}((1 + η)^{α} − (1 − η)^{α}) dη + ∫_{1}^{∞}η^{β}((η + 1)^{α} − (η − 1)^{α}) dη
= ∫_{0}^{∞}η^{β}(η + 1)^{α} dη − ∫_{0}^{1} η^{β}(1 − η)^{α} dη − ∫_{0}^{1} η^{−α−β−2}(1 − η)^{α} dη
= B(−α − β − 1, β + 1) − B(α + 1, β + 1) − B(−α − β − 1, α + 1) .

If we now have to integrate a linear combination ∑_{j} a_{j}ξ^{α_{j}}η^{β_{j}}, we get the corresponding linear combination of beta functions, as long as the (α_{j}, β_{j}) satisfy the condition mentioned above. If they move out of this domain, but the integral still converges absolutely, the formula remains true by analytic continuation. In this way, we get an expression for ∫_{D} F_{1} as a rational linear

combination of beta function values B(a, b), where a, b ≡ \frac{1}{3} mod 1. Hence the integral can finally be expressed as a rational multiple of B(\frac{1}{3}, \frac{1}{3}). Carrying out the calculations, one gets

∫_{D} F̃(x, y) d(x, y) = \frac{243}{2560}B(\frac{1}{3}, \frac{1}{3})

and therefore

C(1, 1) = \frac{12}{π^{2}} ∫_{D} F̃(x, y) d(x, y) = \frac{729}{640π^{2}} B(\frac{1}{3}, \frac{1}{3}) = 0.611669486 …. (25)

9 Suggestions for further work

Four questions may be considered for futher work on this topic.

• Get better estimates for the error term. By suffiently hard work, it is certainly possible to get an estimate of the form O(n^{8/3−δ}) with some δ > 0 instead of o(n^{8/3}). The numerical data even suggest the following Conjecture:

T (n) = \frac{1}{8}n^{4} − Cn^{8/3} + O(n^{5/2}) .

To prove this, hard work alone probably will not suffice; some ideas are needed. One possible line of attack could be to try and prove that

\sqrt{μ}(Ψ_{a,b}(μ, ·) − C(a, b)) → D_{a,b}

with some reasonable distribution D_{a,b}. However, the methods developed here do not seem sufficient to tackle this.

• Find an explicit formula for C(a, b). The explicit computation of C(1, 1) seems to be possible only because of several ‘miracles’. The method does not work for values C(a, b) with a ≠ b, since symmetry plays an important role in the computation. One might perhaps try to find a differential equation for γ ↦ C(1, γ).

• Explain the value of C(1, 1).

It is somewhat mysterious how the beta function comes into play here. This suggests relations to the hexagonal torus and to SL_{2}(ℤ). It might be quite interesting and illuminating to find such relations. Perhaps this may lead to a more natural proof of our results.

• Generalize to higher dimensions.

The counting problem we started with is easily generalized to higher dimensions: Take

R_{d}(n) = ⋃{[−ab_{1}, ab_{1}] × ⋯ × [−ab_{d}, ab_{d}] | a, b_{1}, …, b_{d} ∈ ℕ,
a + b_{1} + ⋯ + b_{d} = n}

and define

T_{d}(n) = #(R_{d}(n) ∩ ℤ^{d}) .

It is quite clear that

T_{d}(n) = \frac{1}{2^{d}d!}n^{2d} + O(n^{2d−1}) ,

so let

U_{d}(n) = T_{d}(n) − \frac{1}{2^{d}d!}n^{2d}

and ask for the asymptotics of U_{d}. Heuristic considerations suggest the Conjecture that

U_{d}(n) ∼ C n^{2d−1− \frac{1}{2d−1}} .

One may try to carry over the theory of Ψ–functions to this case, but apparently additional complications are to be faced.

A APPENDIX: DISTRIBUTIONS ON T 64

A Appendix: Distributions on T

For some general information, see Jantscher [6] and Rudin [8, 7.ex.22].

Remember that we have defined T = ℝ/ℤ × ℝ/ℤ. The space of test functions D(T) is the space C^{∞}(T) of (complex-valued) smooth functions on T, equipped with the topology induced by the family of semi-norms given by ∥ϕ∥_{α} = sup_{x∈T} |∂^{α}ϕ(x)|. Thus, D(T) is a topological vector space, and we

define the space of distributions on T to be its dual D′(T). This means that a distribution on T is a linear and continuous map D(T) → ℂ. Every function f that is integrable on T induces a distribution (often also denoted by f)

ϕ ↦ ∫_{T} fϕ.

We now define the Fourier transform for test functions ϕ and distributions D. The Fourier transform ϕ̂ is the function on ℤ^{2} given by ϕ̂(u, v) = ∫_{T} ϕ(x, y)e^{−2πi(ux+vy)} d(x, y). In analogy to this definition, the Fourier trans-

form of a distribution D is D̂(u, v) = ⟨D, (x, y) ↦ e^{−2πi(ux+vy)}⟩ (⟨D, ϕ⟩ denotes application of D to ϕ). For example, the Fourier transform of the distribution induced by the constant function 1 is ˆ1(u, v) = 1, if u = v = 0 and 0 otherwise.

Since ϕ is smooth, P (u, v)ϕ̂(u, v) is bounded for all polynomials P, and (x, y) ↦ ∑_{u,v} ϕ̂(u, v)e^{2πi(ux+vy)} converges absolutely (i.e. independently of the order of summation) to ϕ in D(T). From this we get

Proposition A.1 For ϕ ∈ D(T) and D ∈ D′(T):

⟨D, ϕ⟩ = ∑_{u,v∈ℤ} D̂(−u, −v)ϕ̂(u, v) .

Proof:

⟨D, ϕ⟩ = ⟨D, (x, y) ↦ ∑_{u,v} ϕ̂(u, v)e^{2πi(ux+vy)}⟩
= ∑_{u,v} ϕ̂(u, v)⟨D, (x, y) ↦ e^{2πi(ux+vy)}⟩
= ∑_{u,v} D̂(−u, −v)ϕ̂(u, v) .

□

Convergence D_{n} → D in D′(T) means convergence ⟨D_{n}, ϕ⟩ → ⟨D, ϕ⟩ for all ϕ ∈ D(T). We then have the following criterion for convergence.

Proposition A.2 Let D_{n} (n ∈ ℕ) and D be distributions on T. If D̂_{n}(u, v) converges to D̂(u, v) for all u, v ∈ ℤ and if there are numbers c > 0 and k ∈ ℕ such that |D̂_{n}(u, v)| ≤ c(1 + |u| + |v|)^{k} for all n, then D_{n} → D in D′(T).

Proof: Take any ϕ ∈ D(T) and an ε > 0. Then there is some w ∈ ℕ such that ∑_{|u|>w or |v|>w}c(1 + |u| + |v|)^{k}|ϕ̂(u, v)| < \frac{1}{3}ε. Taking n large enough, we

also have | ∑_{|u|,|v|≤w}(D̂_{n}(−u, −v) − D̂(−u, −v))ϕ̂(u, v)| < \frac{1}{3}ε. Then clearly

| ∑_{u,v} D̂_{n}(−u, −v)ϕ̂(u, v) − ∑_{u,v} D̂(−u, −v)ϕ̂(u, v)| < ε ,

that is, |⟨D_{n}, ϕ⟩ − ⟨D, ϕ⟩| < ε. □

B Appendix: Some number theoretic estimates

This appendix contains some estimates needed in section 5. Lemma B.1 For n a positive integer, denote by ω(n) the number of different prime divisors of n. If ε > 0, then 2^{ω(n)} ≪ n^{ε}.

Proof: Let f(n) = max{2^{ω(ν)} | ν ≤ n} and look at g(n) = log f(n)/ log n. Let p_{1}, p_{2}, … be the prime numbers in ascending order and put P_{n} = p_{1} ⋯ p_{n}. Obviously, f(n) = 2^{m} for P_{m} ≤ n < P_{m+1}, hence g(n) ≤ m log 2/ log P_{m} in this range. Since log P_{m}/m tends to infinity, we have g(n) → 0, and since 2^{ω(n)} ≤ f(n) = n^{g(n)}, we are done. □

Let φ(n) denote the Euler totient function.

Lemma B.2 If ε > 0, then φ(n) ≫ n^{1−ε}.

Proof: It is well-known that φ(n) = n ∏_{p|n}(1 − 1/p). Hence n/φ(n) =

∏_{p|n}(1 − 1/p)^{−1} ≤ 2^{ω(n)}. By Lemma B.1, n/φ(n) ≪ n^{ε}, whence φ(n) ≫ n^{1−ε}.

□

Lemma B.3 lim_{x→∞} \frac{1}{x} ∑_{1≤n<x} \frac{φ(n)}{n} = \frac{6}{π^{2}} .

Proof: We use the well-known fact that φ(n) = ∑_{d|n} μ(d)n/d. Then,

\frac{1}{x} ∑_{n<x} \frac{φ(n)}{n}  =  \frac{1}{x} ∑_{n<x} ∑_{d|n} \frac{μ(d)}{d}
= \frac{1}{x} ∑_{d<x} \frac{μ(d)}{d}(⌈\frac{x}{d}⌉ − 1) = ∑_{d<x} \frac{μ(d)}{d^{2}} + \frac{1}{x} ∑_{d<x} O(\frac{1}{d})
= \frac{6}{π^{2}} + O(\frac{1}{x}) + O(\frac{log x}{x}) =  \frac{6}{π^{2}} + o(x) .
□

References

[1] Max Benson: Growth series of finite extensions of ℤ^{n} are rational, Invent. Math. 73 (1983), 251–269

[2] James W. Cannon: The combinatorial structure of cocompact discrete hyperbolic groups, Geometriae Dedicata 16 (1984), 123–148

[3] David B.A. Epstein et al.: Word processing in groups, Boston, London 1992

[4] Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics, 1990, Addison-Wesley

[5] Mikhael Gromov: Groups of polynomial growth and expanding maps, Publ. Math. I.H.E.S. 53 (1981), 53–73

[6] Lothar Jantscher: Distributionen, de Gruyter 1971

[7] Walter Rudin: Real and complex analysis, third edition, McGraw–Hill 1987

[8] Walter Rudin: Functional analysis, TMH edition, McGraw–Hill 1974

[9] Hans Salié: Über die Kloostermanschen Summen S(u, v; q), Math. Z. 34 (1932), 91–109

[10] Philip Wagreich: The growth function of a discrete group, in: J.B. Carrell (ed.): Group actions and vector fields, Springer Lecture Notes in Mathematics 956

[11] Bernhard Weber: Zur Rationalität polynomialer Wachstumsfunktionen, Bonner Mathematische Schriften 197 (1989)

[12] André Weil: On some exponential sums, Proc. Natl. Acad. Sci. 34 (1948), 204–207