Continued Fractions and Modular Forms

Continued Fractions and Modular Forms

Ilan Vardi

IHES

Algorithms Seminar

April 3, 2000

[summary by Cyril Banderier]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract

This incursion into the realm of elementary and probabilistic number theory of continued fractions, via modular forms, allows us to study the alternating sum of coefficients of a continued fraction, thus solving the longstanding open problem of their limit law.

1 Introduction

For the readers of these proceedings,¹ it is not a secret anymore that the continued fraction expansion of p/q, the Jacobi symbol (p/q), or the gcd of two integers (p,q), or even Gauss' lattice reduction algorithm cover phenomena of similar computational complexity. However for continued fractions, two distinct cases have to be considered: the continuous and the discrete case. The discrete case deals with continued fraction expansions of rational numbers whereas the continuous case deals with continued fractions of real (irrational) numbers.

For the continuous model, given the apparatus of ergodic theory, many basic results on continued fractions fall as application of more general theorems (see Chapter 9 in Paul Lévy's book [11]). Ergodic theory, which was guessed by Maxwell and formulated by Boltzmann, concerns itself principally with quantifying how points in a continuous space evolve under iteration of a transformation. The ergodic theorem (due to Birkhoff in 1931) states that for almost all initial points x₀ of the continuous space E with measure l,

lim

n®+¥

j=1

(

T^j(x₀)

)

ó
õ

f(y) dl(y).

For the discrete model, there is some kind of effect that precludes the use of ergodic theory. At least, results from the continuous model may serve as a heuristic for guessing corresponding facts about the discrete world.

What one would need in order to make this heuristic rigorous is a kind of ``ergodic theory with an error term.'' This is to some extent afforded by the introduction of Ruelle operators (see the works by Brigitte Vallée in 1995) and of modular forms (see the works by Ilan Vardi in 1987--1993) in the discrete model.

The main object of this lecture is the alternating sum of coefficients of a continued fraction. A motivation for studying this is the evaluation of Legendre symbol (d/c), which essentially expresses whether d is a perfect square modulo c. This symbol can be evaluated using the Euclidean reduction (d/c) = (dmod c/c) (where c, d are odd) and the quadratic reciprocity law

æ
ç
ç
è

ö
÷
÷
ø

= (-1)^(c-1)(d-1)/4

æ
ç
ç
è

ö
÷
÷
ø

In fact, it was shown by Rademacher [12] that

æ
ç
ç
è

ö
÷
÷
ø

=(-1)

(3 - a - d + c å (-1)ⁱ a_i)/4

where d/c=[0,a₁,...,a_r] (brackets stand for the expansion in continued fraction) and 0<a,d<c, adº1mod c with c and r odd. Note that d^-1mod c can itself be computed using the Euclidean algorithm.

There is also a geometrical motivation: the alternating sum expresses the number of times that a geodesic winds around the cusp of a modular surface.

In the continuous case, Guivarc'h and Le Jan [7] established that the average alternating sum converges to a Cauchy distribution with characteristic function exp(-p|t|/(2ln 2)). For the discrete case, the stumbling block is that even the expected asymptotics estimated s(d,c)~12/p²ln cln ln c is unproved (s(d,c) stands for the sum of the coefficient of the continued fraction of d/c). The problem remained open until Vardi found another approach (see [15]) via Dedekind sums.

2 Dedekind Sums

The Dedekind sum appears to be have been mistakenly defined and instead should have been defined as the alternating sum of continued fraction coefficients. Historically, the Dedekind sum is defined for relatively prime integers d and c as

s(d,c)=

c-1

h=1

((hd/c))((h/c)),

with the notation ((x)) = {

0,	if x is an integer,
x - ë xû - 1/2,	otherwise.

.

This sum was introduced by Dedekind in 1876 while editing Riemann's collected works. He used this sum to express the functional equation of the Dedekind h function

h(z) = e

p i z/12

n=1

(1 - e

2p i n z

)

which, he proved, satisfies

ln h

æ
ç
ç
è

az+b

cz+d

ö
÷
÷
ø

ì
ï
ï
í
ï
ï
î

ln h(z) +

ln (cz+d) +

p i

æ
ç
ç
è

-3+

a+d

-12s(d,c)

ö
÷
÷
ø

for c > 0,

lnh(z)+

p ib

when c=0,

(1)

where Á(z)>0, g=(

a b

c d

), and a, b, c, d are integers satisfying ad-bc=1. Note that

ln h(z) =

p iz

m,n=1

2p imn z

so ln h is holomorphic for Á(z)>0. Using the functional equation (1) Dedekind proved a fundamental identity for Dedekind sums, namely the reciprocity law

s(c, d) =

- s(d, c).

Note that the definition of the Dedekind sum gives that s(d, c) = s(dmod c, c) and the reciprocity law relates the value of s(d,c) to s(c,d). It follows that s(d,c) can be computed by using the Euclidean algorithm, so it should be expressible in terms of the continued fraction expansion of d/c. In fact, this is the statement of a result found independently by three authors in 1977:

Theorem 1 [Barkan [2], Hickerson [9], Knuth [10]] If [0,a₁,a₂,...,a_r] is the regular continued
fraction expansion of d/c with r odd (with d<c and 0<a<c such that adº 1mod c) then

s(d,c)=

æ
ç
ç
è

-3+

a+d

i=1

(-1)ⁱa_i

ö
÷
÷
ø

It remains to find the distribution of the values of the Dedekind sums when c and d range over large intervals. Vardi did so by using Paul Lévy's theorem (details in Section 4) and for this, needed to justify several approximations. To this aim, let us recall a few facts about modular forms and Kloosterman sums, since these objects appeared to be the key to the asymptotic analysis.

3 Modular Forms

The group SL(2,Z) acts on the upper half complex plane H by (

a b

c d

) z=az+b/cz+d. One now considers subgroups G of SL(2,Z) containing every matrices of SL(2,Z) congruent to the identity matrix in SL(2,Z/NZ). Every such group G has a fundamental domain: an open set DÌ H such that for all zÎ H there is at most one g Î G with g(z)Î D and at least one g Î G with g(z)Î D.

Definition. A modular form of weight k is a holomorphic function on H satisfying:

1)Modularity condition: f(gz) = (cz+d)^k f(z) for g Î G,
2)Meromorphy condition: f(z) is bounded in the cusps (i.e., parts of D going off to infinity).

Definition. A non-holomorphic modular form of weight r and multiplier system c is a function f(z) on H satisfying:

1') f(gz)=c(g)

æ
ç
ç
è

cz+d

|cz+d|

ö
÷
÷
ø

f(z) (for gÎ G), and 2') ó
õó
õ

f(x+iy)

dxdy

y²

<¥.

Condition 2') shows that the non-holomorphic modular forms form a Hilbert space L²(D, c, r) under the Petersson inner product

á f,gñ =ó
õó
õ

f(z)g(z)y^r

dxdy

y²

The Kloosterman sum (introduced by Kloosterman in 1927 in a refinement of the Hardy--Littlewood circle method) is defined by

S(m,n,c)=å

2p i(ma+nd)/c

where the sum ranges over d<c for adº1mod c and gcd(d,c)=1.

In 1948, André Weil proved the estimate S(m,n,c)=O(c^1/2+e). Asymptotics of sums of Kloosterman sums is a vivid subject, e.g., this ``kloostermania'' recently succeeded [5] to prove that there are infinitely many numbers of the form x²+y⁴. Sums of Kloosterman sums exhibit strong cancellations that can be estimated by making use of modular forms.

Generalized Kloosterman sums (for some subgroup G of SL(2,Z)) are defined by

S(m,n,c,c,G)=åc(g)

2p i

(

(m-a)a+(n-a)d

)

/(qc)

where the sums ranges over g=(

a c

c d

)Î G with 0 < a < qc and 0 < d < qc. In the sum, q is the smallest integer such that (

1 q

0 1

)Î G and a is defined by e^{-2p i a}=c (

1 q

0 1

) with 0£a<1.

Goldfeld and Sarnak's formulation (see [6]) of Kuznetsov's trace formula gives

c < N

S(m, n, c, c, G) =

1/2 < s_j < 1

t_j(m, n, c, G)

2s_j-1

2s_j

+ O(N

b/3 + e

), (2)

where b is the best constant that can be put in the estimate S(m, n, c,c, G) = O(c^{b +}^e), and the sum is over exceptional eigenvalues s_j (defined hereafter) of the operator D_r=y²(¶²/¶ x²+¶²/¶ y²)-iry¶/¶ x. Since D_r has a self-adjoint extension to L²(D, c, r), its spectrum is discrete and real: there is a sequence of eigenvalues going to infinity, with only a finite set of negative eigenvalues which correspond to holomorphic modular forms if r is an even integer. The non-negative eigenvalues are simple except the case l = 1/4, which could have multiplicity 2.

According to Selberg's notation, one writes an eigenvalue as l = s(1-s), with Â(s) ³ 1/2. It follows that there is a finite number of exceptional eigenvalues for which l < 1/4. An exceptional eigenvalue corresponds to s > 1/2, while the other eigenvalues have Â(s) = 1/2 (note the analogy with the Riemann hypothesis).

For a given non-holomorphic Poincaré series P_m (see [4]), the Petersson product á P_m,u_jñ gives the mth Fourier coefficient r_j(m) of the eigenfunction u_j (which is a modular form) associated to the eigenvalue s_j (1-s_j). This allows to make explicit the t_j's of the formula (2):

t_j(m, n, c, G) =

q²r_j(m)r_j(n)

(

p² (m-a)(n-a)/q²

)

1-s_j

G(s_j+r/2) G(2s_j-1)

(-i)^rpG(s_j-r/2)

Finally, the following theorem provides the link between a sum of generalized Kloosterman sums and a sum whose asymptotics allows the application of Lévy's theorem:

Theorem 2 [Vardi [14]]

p i r/2

0 < d < c

gcd(d, c) = 1

2p i r s(d, c)

(

1,1,c,c_r,SL(2,Z)

)

where c_r=e^{2p i r (}^a+d/c^-3-12s(d,c)).

4 Limiting Distribution

One says that an arithmetic function f(n) has a limiting distribution F(x) if

lim

N®¥

{ n<N:f(n)<x }

=F(x).

In other words, one takes a histogram of values of the function f(n) and looks at its shape. One method of showing that an arithmetic function has a limiting distribution is due to Paul Lévy (see examples in [13]).

Theorem 3 [Paul Lévy] If there exists a function g(t) continuous in 0 such that

lim

N®¥

n<N

e^itf(n)=g(t),

then f(n) has a limiting distribution F(x) satisfying g(t)=ò_-¥^¥e^{it x} dF(x).

This is simply the probabilist's terminology for the Fourier transform; g is the characteristic function of the distribution. In order to prove the limiting distribution result for Dedekind sums (and thus for alternating sums of continued fraction coefficients) one applies Lévy's theorem to s(d, c)/ln c. What we want to prove is the estimate

lim

N®¥

0<d<c<N

gcd(d,c)=1

its(d,c)/ln c

{ 0<d<c<N:gcd(d,c)=1 }

-|t|/(2p)

, (3)

where the right-hand side corresponds to the characteristic function of the Cauchy distribution

ó
õ

-¥

a e^ity

a² + y²

dy = e

-a|t|

with a = 1/(2p). The well-known estimate [8]

{ 0<d<c<N:gcd(d,c)=1 }

3N²

p²

+O(Nln N)

shows that the sought estimate (3) can be rewritten as

0< d < c <N

gcd(d, c) = 1

it s(d, c)/ln c

~ e

-|t|/(2p)

3N²

p²

Proving such a formula presents a number of technical difficulties. For example, one would like to remove the absolute values on the right hand side, and the bothersome 1/ln c term in the exponential. The first point is solved since s(c-d, c) = - s(d, c) so that the left-hand side is independent of the sign of t. Consequently, one may restrict attention to t>0. The second point is solved noting that the ln function does not vary very much, and that for most values of c < N, ln c is almost equal to ln N. An estimate obtained by the continued fraction formula for Dedekind sums and the subsequent upper bound of S(d/c) £ (ln N)^{3/2 +}^e for almost all d < c < N, shows that-5mm

0< d < c <N

gcd(d, c) = 1

it s(d, c)/ln c

0< d < c <N

gcd(d, c) = 1

it s(d, c)/ln N

+ O

æ
è

N²(ln

-1/5 +e

ö
ø

See [15] for details. The problem is therefore reduced to showing that

0< d < c <N

gcd(d, c) = 1

it s(d, c)/ln N

~ e

-t/(2p)

3N²

p²

, t > 0. (4)

Summing the relation of Theorem 2 leads to

0<d<c<N

gcd(d,c)=1

2p irs(d,c)

-ip r/2

0<c<N

(

1,1,c,c_r,SL(2,Z)

)

so it suffices to obtain asymptotics of the last right-hand side when r=t/(2pln N). This is given by the specialization of Kuznetsov's trace formula (2) with b = 1 (the trivial bound) which yields

(1/4)^r

p A_r (1-r/2)

N^2-r + O(N

4/3 + e

p A₀

-t/(2p)

N² + O(N²/ln N)

where A_r = òò_D y^r |h(x+iy)|^4rdxdy/y² is the Petersson norm of y^r/2h^2r(x+iy) (the eigenfunction of the only exceptional eigenvalue r/2(1-r/2)).

As one easily computes A₀=p/3, Equation (4) is satisfied.

5 Conclusion

This talk is based on [4], for more details, refer to Ilan Vardi's articles, available from

http://www.ihes.fr/~ilan/publications.html.

The alternating sum of coefficients of a continued fraction seems to be the first example where one needs not only upper bounds for sums of Kloosterman sums, but also their precise asymptotics.

The following fact is noteworthy. Euclidean algorithms are fundamental is several branches of science while counting amongst the oldest known algorithms. It is another testimony of the ``unreasonable effectiveness of mathematics'' (a phrase due to Eugene Wigner [16]) that they reveal their finest secrets only with our recent knowledges of dynamical systems and of analytical number theory. Long live applied mathematics!

References

[1]: Banderier (Cyril). -- Unified analysis of Euclidean algorithms [ summary of a talk by Brigitte Vallée ]. In Salvy (Bruno) (editor), Algorithms Seminar, 1998--1999, pp. 53--56. -- Institut National de Recherche en Informatique et en Automatique, December 1999. Research Report n°3830.
[2]: Barkan (Philippe). -- Sur les sommes de Dedekind et les fractions continues finies. Comptes rendus hebdomadaires des Séances de l'Académie des Sciences. Séries A et B, vol. 284, n°16, 1977, pp. A923--A926.
[3]: Flajolet (Philippe). -- Continued fractions from Euclid till present [ summary of a talk by Ilan Vardi ]. In Salvy (Bruno) (editor), Algorithms Seminar, 1998--1999, pp. 89--96. -- Institut National de Recherche en Informatique et en Automatique, December 1999. Research Report n°3830.
[4]: Flajolet (Philippe), Vallée (Brigitte), and Vardi (Ilan). -- Continued fractions from Euclid to the present day. -- In preparation.
[5]: Friedlander (John) and Iwaniec (Henryk). -- The polynomial X²+Y⁴ captures its primes. Annals of Mathematics. Second Series, vol. 148, n°3, 1998, pp. 945--1040.
[6]: Goldfeld (D.) and Sarnak (P.). -- Sums of Kloosterman sums. Inventiones Mathematicae, vol. 71, n°2, 1983, pp. 243--250.
[7]: Guivarc'h (Y.) and Le Jan (Y.). -- Asymptotic winding of the geodesic flow on modular surfaces and continued fractions. Annales scientifiques de l'École normale supérieure. Quatrième Série, vol. 26, n°1, 1993, pp. 23--50.
[8]: Hardy (G. H.) and Wright (E. M.). -- An introduction to the theory of numbers. -- The Clarendon Press Oxford University Press, New York, 1979, fifth edition, xvi+426p.
[9]: Hickerson (Dean). -- Continued fractions and density results for Dedekind sums. Journal für die reine und angewandte Mathematik, vol. 290, 1977, pp. 113--116.
[10]: Knuth (Donald E.). -- Notes on generalized Dedekind sums. Acta Algorithmica, vol. 33, n°4, 1977, pp. 297--325.
[11]: Lévy (P.). -- Théorie de l'addition des variables aléatoires. -- Gauthier--Villars, 1937.
[12]: Rademacher (Hans). -- Generalization of the reciprocity formula for Dedekind sums. Duke Mathematical Journal, vol. 21, 1954, pp. 391--397.
[13]: Tenenbaum (Gérald). -- Introduction to analytic and probabilistic number theory. -- Cambridge University Press, Cambridge, 1995, xvi+448p. Translated from the second French edition (1995) by C. B. Thomas.
[14]: Vardi (Ilan). -- A relation between Dedekind sums and Kloosterman sums. Duke Mathematical Journal, vol. 55, n°1, 1987, pp. 189--197.
[15]: Vardi (Ilan). -- Dedekind sums have a limiting distribution. International Mathematics Research Notices, n°1, 1993, pp. 1--12.
[16]: Wigner (Eugene P.). -- The unreasonable effectiveness of mathematics in the natural sciences. Communications in Pure and Applied Mathematics, vol. 13, n°1, 1960, pp. 1--14. -- Also available at the URL http://www.txwesleyan.edu/aegis/aegistwo/Unreasonable.html.

1: For newcomers, I highly recommend the reading of summaries of previous talks by I. Vardi [3] and B. Vallée [1]!

This document was translated from L^AT_EX by H^EV^EA.