Nombre de solutions dans une binade de l’équation A^{2} + B^{2} = C^{2} + C

Jean-Michel Muller, Jean-Louis Nicolas, et Xavier-François Roblot ^{∗}

18 novembre 2003

Abstract. Let us denote by Q(N, λ) the number of solutions of the diophantine equation A^{2} + B^{2} = C^{2} + C satisfying N ≤ A ≤ B ≤ C ≤ λN − \frac{1}{2}. We prove that, for λ fixed and N → ∞, there exists a constant α(λ) such that Q(N, λ) = α(λ)N + O_{λ} (N^{7/8} log N). When λ = 2, Q(2^{n−1}, 2) counts the number of solutions of A^{2} + B^{2} = C^{2} + C with the same number, n, of binary digits ; these solutions are interesting in the problem of computing the function (a, b) → \sqrt{a^{2} + b^{2}} in radix-2 floating-point arithmetic.

By elementary arguments, Q(N, λ) can be expressed in terms of four sums of the type

S(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d odd \end{matrix}} ( ∑_{\begin{matrix}1≤A≤f(d) \\ 4A^{2}≡−1 (mod d) \end{matrix}} 1)

where u and v are real numbers and f : [u, v] ⟶ ℝ is a function. These sums are estimated by a classical, but deep, method of number theory, using Fourier analysis and Kloosterman sums. This method is effective, and, in the case λ = 2, a precise upper bound for |Q(N, λ) − α(λ)N| is given.

1 Introduction.

1.1 Présentation du problème.

Le problème informatique original est le suivant (cf. [15], chap. 9) : on désire construire des systèmes (programmes ou circuits intégrés) capables de calculer la fonction (a, b) → \sqrt{a^{2} + b^{2}} avec “arrondi correct”, pour a et b compris entre 1 et 2, lorsque le résultat est lui aussi entre 1 et 2. Par “arrondi correct” on entend que le résultat fourni doit toujours être le nombre exactement représentable en virgule flottante en base 2 avec n bits de mantisse (on dira “nombre machine” pour faire court) le plus proche du résultat exact. Pour ceci, il faut savoir avec quelle précision on doit approcher \sqrt{a^{2} + b^{2}} lors de calculs intermédiaires pour être certain qu’arrondir au plus près l’approximation est équivalent à arrondir au plus près le résultat exact. Ceci revient à déterminer deux nombres machines a et b compris entre 1 et 2 tels que a^{2} +b^{2} soit le plus proche du carré du milieu de deux nombres machines consécutifs. En définissant A = 2^{n−1}a et B = 2^{n−1}b, notre problème est ramené à trouver des entiers A, B et C compris entre 2^{n−1} et 2^{n} − 1 tels que

∗Recherche partiellement financée par le CNRS et l’INRIA, Laboratoire d’Informatique du Parallélisme, UMR 5668 et Institut Girard Desargues, UMR 5028.

A^{2} + B^{2} = (C + 1/2)^{2} + ϵ,

où |ϵ| est le plus petit possible. Il est clair que |ϵ| vaut au moins 1/4. Nous cherchons à savoir si le cas |ϵ| = 1/4 se produit. Notre problème est donc de déterminer si pour toute valeur de n il existe des nombres entiers A, B et C compris entre 2^{n−1} et 2^{n} − 1 satisfaisant l’équation diophantienne

(1.1)  A^{2} + B^{2} = C^{2} + C.

Désignons par Q(2^{k}, 2) (cette notation sera justifiée dans l’énoncé du théorème 1 ci-dessous) le nombre de solutions de (1.1) telles que

(1.2)  2^{k} ≤ A ≤ B ≤ C ≤ 2^{k+1} − 1.

On trouvera dans la table 1 la valeur de Q(2^{k}, 2) pour 4 ≤ k ≤ 41 (on a Q(1, 2) = 1 et, pour 1 ≤ k ≤ 3, Q(2^{k}, 2) = 0). Cette table montre que Q(2^{k}, 2)/2^{k} semble tendre vers une limite. L’objet de cet article est de démontrer :

Theorème 1. Soit λ > \sqrt{2} un nombre réel fixé. Pour N entier, on désigne par Q(N, λ) le nombre de solutions de l’équation diophantienne (1.1) vérifiant

(1.3)  N ≤ A ≤ B ≤ C ≤ λN − \frac{1}{2}.

Si l’on pose

(1.4)  α(λ) = \frac{λ}{4} − \frac{λ}{π} arcsin (\frac{1}{λ}) + \frac{log(1 + \sqrt{2})}{π} − \frac{log(λ + \sqrt{λ^{2} − 1})}{π}

on a

(1.5)  Q(N, λ) = α(λ)N + R̃(N, λ)

avec, lorsque N → ∞,

(1.6)  R̃(N, λ) = O_{λ} (N^{7/8} log N) .

Pour λ = 2, on a

(1.7) α(2) = \frac{1}{6} + \frac{log(1 + \sqrt{2})}{π} − \frac{log(2 + \sqrt{3})}{π} = 0.02801587455727 …

et, pour N ≥ 1000,

(1.8) |R̃(N, 2)| ≤ N^{7/8}(51 log N + 211) + N^{1/2}(77 log N + 283) + 29.

Lorsque λ = 2, nous avons voulu donner une majoration effective du reste R̃(N, 2). Cette majoration n’est pas très bonne, et le membre de droite de (1.8) n’est inférieur au terme principal α(λ)N de (1.5) que pour N > 1.32 · 10^{42}. Au prix de calculs encore plus techniques, il serait possible de l’améliorer un peu. Par exemple, dans la majoration (2.19) des sommes de Kloosterman, on peut remplacer (cf. [13], chap. 4) τ(m) = ∑_{d | m} 1 par 2^{ω(m)} où ω(m) est le nombre de facteurs premiers de m, ce qui permettrait de diminuer le membre de droite de (1.8). Mais, pour ne pas trop alourdir la présentation, nous avons effectué assez grossièrement la plupart des majorations. Cependant, il semble difficile, par cette méthode, d’obtenir pour R̃(N, 2) une majoration 100 fois meilleure que (1.8).

1.2 Les diviseurs de 4A^{2} + 1.

Ecrivons C^{2} + C = (C + \frac{1}{2})^{2} − \frac{1}{4} ; par le changement de variable

(1.9)  X = 2A,  Y = 2B,  Z = 2C + 1.

l’équation (1.1) devient

(1.10)  X^{2} + Y^{2} = Z^{2} − 1.

En considérant (1.10) modulo 4, on voit que toute solution X, Y, Z de (1.10) est telle que Z est impair et X et Y sont pairs. Donc, toute solution de (1.10) engendre, par (1.9), une solution de (1.1) et les deux équations diophantiennes (1.1) et (1.10) sont équivalentes.

En écrivant (1.10) sous la forme

X^{2} + 1 = Z^{2} − Y^{2} = (Z − Y)(Z + Y),

on voit que Z − Y = d est un diviseur de X^{2} + 1. Réciproquement, à un diviseur d de X^{2} + 1, la résolution du système

\{ \begin{matrix}Z − Y = d \\ Z + Y = (X^{2} + 1)/d \end{matrix}

fournit

(1.11) \{ \begin{matrix}Y = \frac{1}{2} (\frac{X^{2}+1}{d} − d) \\ Z = \frac{1}{2} (\frac{X^{2}+1}{d} + d) \end{matrix} soit \{ \begin{matrix}B = \frac{1}{4} (\frac{4A^{2}+1}{d} − d) \\ C = \frac{1}{4} (\frac{4A^{2}+1}{d} + d − 2) . \end{matrix}

Notons que, dans (1.11), B et C sont entiers ; en effet les facteurs premiers de 4A^{2} + 1 sont tous congrus à 1 (mod 4) (car −1 est un carré modulo un tel facteur premier) et d, qui divise 4A^{2} + 1, est aussi congru à 1 (mod 4).

Il y a donc, par (1.11), une bijection entre les diviseurs d de 4A^{2} + 1 et les solutions de (1.1), pour A fixé. Dans cette bijection, la condition B ≤ C de (1.3) se traduit par d ≥ 1 et la condition A ≤ B par 4A^{2} − 4Ad + 1 − d^{2} ≥ 0, soit

A ≤ B ≤ C ⟺ A ≥ f_{2}(d) =^{def} \frac{1}{2} (d + \sqrt{2d^{2} − 1}) et d ≥ 1
(1.12)  ⟺ 1 ≤ d ≤ f_{2}^{−1}(A) = \sqrt{8A^{2} + 1} − 2A.

Parallèlement, la condition C ≤ λN − 1/2 de (1.3) se traduit par 4A^{2} + d^{2} − 4λNd + 1 ≤ 0 ; autrement dit, le point (A, d) doit être à l’intérieur de la demi ellipse 4A^{2} + (d − 2λN)^{2} = 4λ^{2}N^{2} − 1, A > 0. Ceci implique 0 < d < 4λN et A < λN. D’autre part, par (1.11), la condition B > 0 entraîne d ≤ 2A < 2λN, et l’on a

C ≤ λN − 1/2 ⟺ A ≤ f_{1}(d) =^{def} \frac{1}{2}\sqrt{d(4λN − d) − 1}
(1.13)  ⟺ d ≥ f_{1}^{−1}(A) = 2λN − \sqrt{4λ^{2}N^{2} − 4A^{2} − 1}.

Les courbes représentatives des fonctions f_{1}^{−1}(A) et f_{2}^{−1}(A) se coupent au point (A_{0}, v_{0}) (1.14)

A_{0} = \frac{1}{4}\sqrt{8λ^{2}N^{2} − 2}, v_{0} = f_{1}^{−1}(A_{0}) = f_{2}^{−1}(A_{0}) = 2λN − \frac{1}{2}\sqrt{8λ^{2}N^{2} − 2}.

Ainsi, la condition (1.3) équivaut à choisir le point (A, d) tel que N ≤ A ≤ A_{0} et f_{1}^{−1}(A) ≤ d ≤ f_{2}^{−1}(A). Si λ ≤ \sqrt{2}, par (1.14), A_{0} < N et Q(N, λ) = 0.

f_{1}^{−1}(A) f_{2}^{−1}(A)  A d\frac{1}{2\sqrt{2}}  N  A_{0} v_{0} u_{1} u_{0}

Fig. 1 – les valeurs possibles pour (A, d)

On suppose donc λ > \sqrt{2} et l’on a

(1.15)  Q(N, λ) = ∑_{N≤A≤A_{0}} ∑_{\begin{matrix}d | 4A^{2}+1 \\ f_{1}^{−1}(A)≤d≤f_{2}^{−1}(A) \end{matrix}} 1.

Permutons l’ordre des sommations. Les valeurs extrèmes prises par d sont

(1.16)  u_{0} = f_{1}^{−1}(N) = 2λN − \sqrt{4(λ^{2} − 1)N^{2} − 1}

et v_{0} défini par (1.14), car les fonctions f_{1}^{−1}(A) et f_{2}^{−1}(A) sont croissantes sur l’intervalle [N, A_{0}]. D’autre part, pour d fixé, A doit vérifierA≥max(N, f_{2}(d)) et, en posant

(1.17)  u_{1} = f_{2}^{−1}(N) = \sqrt{8N^{2} + 1} − 2N,

l’égalité (1.15) devient (1.18)

Q(N, λ) = ∑_{u_{0}≤d≤v_{0}} ∑_{\begin{matrix}N≤A≤f_{1}(d) \\ 4A^{2}+1≡0 (mod d) \end{matrix}}1− ∑_{u_{1}≤d≤v_{0}} ∑_{\begin{matrix}N≤A<f_{2}(d) \\ 4A^{2}+1≡0 (mod d) \end{matrix}}1 = Q̂(N, λ)+ε(N, λ)

avec

(1.19)  Q̂(N, λ) = ∑_{u_{0}≤d≤v_{0}} ∑_{\begin{matrix}N≤A≤f_{1}(d) \\ 4A^{2}+1≡0 (mod d) \end{matrix}} 1 − ∑_{u_{1}≤d≤v_{0}} ∑_{\begin{matrix}N≤A≤f_{2}(d) \\ 4A^{2}+1≡0 (mod d) \end{matrix}} 1

et

(1.20)  ε(N, λ) = ∑_{u_{1}≤d≤v_{0}} ∑_{\begin{matrix}A=f_{2}(d) \\ 4A^{2}+1≡0 (mod d) \end{matrix}} 1.

Définissons

(1.21)  S(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} (  ∑_{\begin{matrix}1≤A≤f(d) \\ 4A^{2}≡−1 (mod d) \end{matrix}} 1) .

L’égalité (1.19) s’écrit (1.22) Q̂(N, λ) = S(u_{0}, v_{0}; f_{1}) − S(u_{0}, v_{0}; N − 1) − S(u_{1}, v_{0}; f_{2}) + S(u_{1}, v_{0}; N − 1)

où N − 1 désigne la fonction constante égale à N − 1. Par (1.22), l’évaluation de Q̂(N, λ) se ramène à l’évaluation de sommes S(u, v; f).

1.3 Les sommes S(u, v; f).

Nous démontrerons au paragraphe 3 le théorème

Theorème 2. Soit u, v deux nombres réels satisfaisant 7 ≤ u ≤ v et f une fonction continûment dérivable de [u, v] dans ℝ. On pose

(1.23)  ∥f∥ = ∥f∥_{[u,v]} = max_{u≤t≤v} |f(t)|,

(1.24)  F (t) = \frac{f(t)}{t}

et

(1.25)  M = M(u, v; f) = ∥tF′(t)∥ + \frac{2}{5} = max_{u≤t≤v} |tF′(t)| + \frac{2}{5}·

Alors la somme S(u, v; f) définie en (1.21) peut s’écrire

(1.26)  S(u, v; f) = S_{0}(u, v; f) − S_{1}(u, v; f)

(1.27)  S_{0}(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} \frac{ρ(d)f(d)}{d}

où ρ est défini par (2.11)et S_{1}(u, v; f) satisfait l’inégalité

(1.28)  |S_{1}(u, v; f)| ≤ \frac{19}{2}(log v + 4)v^{7/8}\sqrt{M}.

La démonstration du théorème 2 suit le chapitre 2 du livre de C. Hooley [11], où, pour prouver que le plus grand facteur premier de ∏_{n≤x}(n^{2} + 1) est,

pour x assez grand, supérieur à x^{11/10}, l’auteur évalue une somme voisine de S(u, v; x). L’exposant 11/10 est amélioré dans [4]. Un résultat plus général est démontré dans [10], où n^{2} + 1 est remplacé par n^{2} + D, avec n^{2} + D irréductible. Ce résultat pourrait être adapté pour compter les racines de l’équation diophantienne X^{2} + D = Z^{2} − Y^{2} dans un intervalle donné.

1.4 Les solutions A = B.

Si l’on impose A = B dans (1.1), on a, par (1.9), X = Y, et l’équation équivalente (1.10) s’écrit

Z^{2} − 2X^{2} = 1;

c’est une équation de Pell-Fermat, dont les solutions sont X_{n}, Z_{n} avec Z_{n} + \sqrt{2}X_{n} = (3 + 2\sqrt{2})^{n}. On a

(1.29)  X_{n} = \frac{(3 + 2\sqrt{2})^{n} − (3 − 2\sqrt{2})^{n}}{2\sqrt{2}} ≤ \frac{(3 + 2\sqrt{2})^{n}}{2\sqrt{2}}

et, pour n ≥ 1,

X_{n} = \frac{(3 + 2\sqrt{2})^{n}}{2\sqrt{2}} (1 − (\frac{3 − 2\sqrt{2}}{3 + 2\sqrt{2}})^{n})

(1.30)  ≥ \frac{(3 + 2\sqrt{2})^{n}}{2\sqrt{2}} (1 − \frac{3 − 2\sqrt{2}}{3 + 2\sqrt{2}}) ≥ \frac{(3 + 2\sqrt{2})^{n}}{3} ·

Par la définition (1.20) de ε(N, λ), la condition A = f_{2}(d) est, par (1.12), équivalente à A = B. Comme la fonction f_{2} définie en (1.12) est croissante, la fonction ε(N, λ) compte le nombre de solutions de l’équation (1.1) avec A = B telle que A soit compris entre f_{2}(u_{1}) = N et f_{2}(v_{0}) = A_{0} < \frac{λN}{\sqrt{2}} par (1.17) et (1.14). On a donc, par (1.29) et (1.30)

(1.31) 0 ≤ ε(N, λ) = ∑_{2N≤X_{n}≤2A_{0}} 1 ≤ ∑_{2N≤X_{n}<λ\sqrt{2}N} 1 ≤ \frac{log \frac{3λ}{4}}{log(3 + 2\sqrt{2})} + 1

et, en particulier, pour λ = 2,

(1.32)  0 ≤ ε(N, λ) ≤ 1.

1.5 Les solutions paramétriques.

On peut donner une représentation paramétrique des solutions de l’équation (1.10) (cf. [5], th. 38 et 39 et [6], p. 210). En effet, si α, β, γ, δ sont des entiers vérifiant

(1.33)  αδ − βγ = 1

il est facile de voir que

(1.34) X = αβ+γδ, Y = \frac{1}{2} (α^{2} + γ^{2} − β^{2} − δ^{2}) , Z = \frac{1}{2} (α^{2} + γ^{2} + β^{2} + δ^{2})

est une solution de (1.10).

Réciproquement, pour voir que toute solution de (1.10) est de cette forme, écrivons la décomposition en facteurs premiers X^{2} + 1 = ∏_{j=1}^{J} p_{j}^{α_{j}}, où les nombres premiers p_{j} sont congrus à 1 modulo 4. Dans l’anneau G des entiers de Gauss (c’est-à-dire l’ensemble des nombres complexes a + bi où a et b sont dans ℤ), chaque p_{j} se factorise sous la forme p_{j} = π_{j}\overline{π_{j}}. Le nombre X + i se factorise dans G sous la forme

(1.35)  X + i = i^{k} ∏_{j=1}^{J} π_{j}^{α_{j}}, 0 ≤ k ≤ 3.

En effet, les deux nombres π_{j} et \overline{π_{j}} ne peuvent apparaître simultanément dans (1.35), sinon p_{j} = π_{j}\overline{π_{j}} diviserait (dans ℤ) X et 1, ce qui est impossible.

Soit d un diviseur de X^{2} + 1. La décomposition en facteurs premiers de d s’écrit d = ∏_{j=1}^{J} p_{j}^{β_{j}} avec 0 ≤ β_{j} ≤ α_{j}. Posons

(1.36)  Δ = i^{k} ∏_{j=1}^{J} π_{j}^{β_{j}} = β + iδ, Δ′ = ∏_{j=1}^{J} π_{j}^{α_{j}−β_{j}} = α − iγ.

On a, par (1.35),

(1.37)  X + i = ΔΔ′ = (β + iδ)(α − iγ) = αβ + γδ + i(αδ − βγ)

qui nous donne (1.33) et la valeur de X dans (1.34). On obtient la valeur de Y et Z dans (1.34) en prenant la norme dans (1.36) :

d = |Δ|^{2} = β^{2} + δ^{2}, \frac{X^{2} + 1}{d} = |Δ′|^{2} = α^{2} + γ^{2}

et en reportant dans (1.11).

Soit θ ∈ ℤ. On pose

α = 10θ + 8, β = 4θ + 3, γ = 5, δ = 2.

On vérifie (1.33) et en substituant dans (1.34), on obtient

X = 40θ^{2} + 62θ + 34, Y = 42θ^{2} + 68θ + 38, Z = 58θ^{2} + 92θ + 51

d’où, par (1.9),

(1.38) A = 20θ^{2} + 31θ + 17, B = 21θ^{2} + 34θ + 19, C = 29θ^{2} + 46θ + 25.

Pour θ > 0, la solution (1.38) vérifie 20θ^{2} ≤ A et C + 1/2 ≤ 29(θ + 1)^{2}. Elle

sera comptée dans Q(N, λ) pour \sqrt{\frac{N}{20}} ≤ θ ≤ \sqrt{\frac{λN}{29}} − 1. On obtient ainsi la minoration

(1.39)  Q(N, λ) ≥ (\sqrt{\frac{λ}{29}} − \sqrt{\frac{1}{20}}) \sqrt{N} − 2.

Lorsque λ = 2, (1.39) entraîne, pour N ≥ 2630 > (\frac{2}{0.039})^{2},

(1.40)  Q(N, 2) ≥ 0.039\sqrt{N} − 2 > 0.

L’inégalité (1.40) et la table 1 montrent que l’équation (1.1) a, pour tout k ≥ 4, des solutions vérifiant (1.2).

1.6 Structure de l’article.

Dans le §2, nous redémontrons des résultats classiques utiles dans la suite, notamment sur la fonction arithmétique ρ (définie par (2.11)) et les sommes de Kloosterman. Nous donnons également deux algorithmes de construction de la table 1 donnée en annexe. Dans le §3, nous démontrons le théorème 2, et dans le §4, le théorème 1.

Nous remercions chaleureusement A. Schinzel pour nous avoir indiqué le livre de C. Hooley [11] ainsi que la solution paramétrique (1.34). Nous avons plaisir à remercier E. Fouvry, R. Heath-Brown, J. Rivat pour leurs remarques positives. Nous remercions également les systèmes de calcul formel MAPLE [14] et PARI/GP [17] que nous avons largement utilisé, ainsi que le Max Planck Institut de Bonn où une partie des idées de cet article a été développée pendant que le deuxième auteur était invité en mai 2002.

2 Résultats généraux.

2.1 Sommes de deux carrés.

Soit d un entier positif impair. On désigne par S_{d} l’ensemble des représentations primitives de d par la forme quadratique r^{2} + 4s^{2}, avec r > 0 et s ∈ ℤ

(2.1)  S_{d} = {(r, s), r ∈ ℕ^{∗}, s ∈ ℤ, r^{2} + 4s^{2} = d, (r, 2s) = 1}

et par E_{d} l’ensemble des classes d’équivalence modulo d satisfaisant la congruence 4ν^{2} ≡ −1 (mod d) :

(2.2)  E_{d} = {ν ∈ (ℤ/dℤ)^{∗} , 4ν^{2} ≡ −1 (mod d)}.

Nous allons redémontrer le résultat classique (cf. [19], articles 86 et 90 et [11], p. 33) :

Proposition 1. L’application Θ définie par Θ(r, s) = r^{−1}s (mod d), où r^{−1} désigne l’inverse de r dans (ℤ/dℤ)^{∗} est une bijection de S_{d} dans E_{d}. On peut écrire ν = Θ(r, s) sous la forme

(2.3)  \frac{ν}{d} ≡ \frac{\overline{4s}}{r} + \frac{s}{r(r^{2} + 4s^{2})} (mod 1)

où l’on a noté \overline{4s} un inverse de 4s modulo r ou bien sous la forme

(2.4)  \frac{ν}{d} ≡ \frac{\overline{r}}{4s} − \frac{r}{4s(r^{2} + 4s^{2})} (mod 1)

où, cette fois, nous notons \overline{r} un inverse de r modulo 4s.

Démonstration.

(i) Θ est bien définie. Si r n’était pas premier avec d, soit p un facteur premier commun à r et d. Comme d est impair, p ≠ 2, et p divise 4s^{2} = d−r^{2}, donc p divise s, et r et s ne seraient pas premiers entre eux. Ainsi r^{−1} est bien défini et r^{2} + 4s^{2} = d entraîne 4s^{2}r^{−2} ≡ −1 (mod d) donc r^{−1}s ∈ E_{d} par (2.2).

(ii) Θ est surjective. Soit ν ∈ E_{d}. On obtient r et s tels que Θ(r, s) = ν par l’algorithme de Cornacchia (cf. [16], [2], [1]) : on développe \frac{2ν}{d} en fraction continue et l’on choisit la réduite \frac{p_{n}}{q_{n}} telle que q_{n} ≤ \sqrt{d} < q_{n+1}. Les deux nombres R = q_{n} et S = 2νq_{n} − dp_{n} vérifient R^{2} + S^{2} = d, (R, S) = 1 et SR^{−1} ≡ 2ν (mod d).

Comme d = R^{2} + S^{2} est impair, l’un des nombres R et S est pair, l’autre est impair. Si S est pair, on pose s = S/2, r = R. On a (r, s) ∈ S_{d} et Θ(r, s) = sr^{−1} ≡ ν (mod d). Si R est pair, on pose s = −R/2, r = S; on a (r, s) ∈ S_{d} et

Θ(r, s) = r^{−1}s = −S^{−1}R/2 ≡ −\frac{1}{2}(2ν)^{−1} ≡ −\frac{1}{2}(−2ν) ≡ ν (mod d).

(iii) Θ est injective. Soit deux éléments (r, s) et (r′, s′) de S_{d} vérifiant Θ(r, s) = Θ(r′, s′), c’est-à-dire

(2.5)  r′s − rs′ ≡ 0 (mod d).

On a

(2.6)  d^{2} = (r^{2} + 4s^{2})(r^{′2} + 4s^{′2}) = (rr′ + 4ss′)^{2} + 4(r′s − rs′)^{2}.

Mais (2.6) et (2.5) entraînent que r′s − rs′ = 0 c’est-à-dire

(2.7)  \frac{s}{r} = \frac{s′}{r′} = w

(car r et r′, impairs, ne sont pas nuls) et l’on a

d = r^{2} + 4s^{2} = r^{′2} + 4s^{′2} = r^{2}(1 + 4w^{2}) = r^{′2}(1 + 4w^{2})

ce qui implique r = r′ puis, par (2.7), s = s′.

Il reste à prouver (2.3) et (2.4) Soit (r, s) ∈ S_{d}; comme (r, 2s) = 1, il existe z_{1}, z_{2} ∈ ℤ, tels que

(2.8)  rz_{1} − 4sz_{2} = 1.

Posons

(2.9)  ν = rz_{2} + sz_{1}.

En prenant les modules dans la relation

(r + 2si)(z_{1} + 2z_{2}i) = (rz_{1} − 4sz_{2}) + 2(rz_{2} + sz_{1})i

on obtient

4ν^{2} + 1 ≡ 0 (mod d).

Enfin, de (2.8) et (2.9), il suit

(2.10)  rν = r^{2}z_{2} + s(1 + 4sz_{2}) = s + z_{2}d ≡ s (mod d)

donc ν = Θ(r, s). Il vient ensuite, par (2.8) et (2.9)

\frac{ν}{d} = \frac{rz_{2} + sz_{1}}{r^{2} + 4s^{2}} = \frac{r^{2}z_{2} + rsz_{1}}{r(r^{2} + 4s^{2})} = \frac{s + (r^{2} + 4s^{2})z_{2}}{r(r^{2} + 4s^{2})}
= \frac{z_{2}}{r} + \frac{s}{r(r^{2} + 4s^{2})} ≡ \frac{\overline{4s}}{r} + \frac{s}{r(r^{2} + 4s^{2})} (mod 1)

ce qui démontre (2.3). De même, on peut écrire

\frac{ν}{d} = \frac{4rsz_{2} + 4s^{2}z_{1}}{4s(r^{2} + 4s^{2})} = \frac{−r + (r^{2} + 4s^{2})z_{1}}{4s(r^{2} + 4s^{2})}
= \frac{z_{1}}{4s} − \frac{r}{4s(r^{2} + 4s^{2})} ≡ \frac{\overline{r}}{4s} − \frac{r}{4s(r^{2} + 4s^{2})} (mod 1)

ce qui prouve (2.4). □

Nous désignerons par ρ(n) le nombre de solutions de la congruence

(2.11)  ν^{2} ≡ −1 (mod n).

On a pour p premier et α ≥ 1

(2.12)  ρ(p^{α}) = \begin{cases}1 & si p = 2 et α = 1 \\ 0 & si p = 2 et α ≥ 2 \\ 0 & si p ≡ 3 (mod 4) \\ 2 & si p ≡ 1 (mod 4) \end{cases}

et par le théorème des restes des chinois, la fonction arithmétique ρ est multiplicative. Par la proposition 1, pour d impair, on a

(2.13)  ρ(d) = Card(E_{d}) = Card(S_{d}).

2.2 Construction de la table.

Une première méthode consiste à utiliser la formule (1.15). Par (1.14), on a

(2.14)  N ≤ A ≤ A_{0} = \sqrt{\frac{λ^{2}N^{2}}{2} − \frac{1}{8}}.

Pour chaque valeur de A vérifiant l’inégalité (2.14), on factorise 4A^{2} + 1, et l’on recherche ses diviseurs. Pour chaque diviseur d de 4A^{2} + 1, on calcule B et C par (1.11) et si (1.3) est satisfaite, on compte cette solution. Cette méthode a pour inconvénient la factorisation de 4A^{2} + 1 qui, pour A grand, devient coûteuse.

Un meilleur algorithme est basé sur la proposition 1. Par une remarque déjà faite juste après (1.11), les facteurs premiers de d, diviseur de 4A^{2} + 1, sont tous congrus à 1 modulo 4, ce qui implique par (2.12), que ρ(d) > 0. Par la proposition 1 et (2.13), il s’ensuit que d admet ρ(d) représentations primitives

(2.15)  d = r^{2} + 4s^{2}, (r, 2s) = 1, r ≥ 1, s ∈ ℤ.

Par (1.18), on sait que d est compris entre u_{0}, défini par (1.16), et v_{0}, défini par (1.14). Par une double boucle en r et s, on engendre les nombres d de la forme (2.15) et vérifiant u_{0} ≤ d ≤ v_{0}. Observons que chaque d va être engendré ρ(d) fois.

Ensuite, pour chaque valeur du couple (r, s), on calcule ν par (2.8) et (2.9) et l’on recherche les nombres A satisfaisant A ≡ ν (mod d) et (2.14). (Notons que, pour λ = 2, il y a au plus un tel A car, par (1.16), d ≥ u_{0} > \sqrt{2N^{2} − 1/8} − N). Comme dans la première méthode, à partir de A et d, on calcule B et C par (1.11) et on incrémente le compteur de solutions si (1.3) est satisfaite.

Cet algorithme est linéaire en N. Il a été implémenté en PARI/C. Le temps d’exécution est de moins d’une seconde pour 2^{20}, d’une dizaine de minutes pour 2^{30} et de plus de deux semaines pour 2^{41}.

2.3 Lemmes analytiques.

Lemme 1. Soit τ(n) = ∑_{d | n} 1. Pour tout x ≥ 1, on a

∑_{1≤n≤x} τ(n) ≤ x(log x + 1).

Démonstration. On a

∑_{1≤n≤x} τ(n) = ∑_{1≤n≤x} ∑_{d | n} 1 = ∑_{d≤x} ⌊\frac{x}{d}⌋ ≤ x ∑_{d≤x} \frac{1}{d}.

Puis on utilise l’inégalité

(2.16)  ∑_{d≤x} \frac{1}{d} ≤ 1 + ∫_{1}^{x} \frac{dt}{t} = 1 + log x. □

Lemme 2. Soit h un nombre entier non nul et τ(n) = ∑_{d | n} 1. Pour tout x ≥ 1, on a

∑_{1≤n≤x} τ(n){(h, n)}^{1/2} ≤ x(log x + 1)ψ(h)

où ψ(h) est défini par

(2.17)  ψ(h) = ∑_{d | h} \frac{τ(d)}{\sqrt{d}}·

Démonstration. En utilisant l’inégalité τ(dd′) ≤ τ(d)τ(d′), valable pour tout couple d’entiers d et d′ et le lemme 1, il vient

∑_{1≤n≤x} τ(n)\{(h, n)\}^{1/2} ≤ ∑_{d | h} \sqrt{d} ∑_{\begin{matrix}n≤x \\ d | n \end{matrix}} τ(n) ≤ ∑_{d | h} \sqrt{d}τ(d) ∑_{d′≤x/d} τ(d′)

≤ ∑_{d | h} \frac{τ(d)}{\sqrt{d}}x (log (\frac{x}{d}) + 1) ≤ x(log x + 1)ψ(h). □

Lemme 3. Soit ψ(h) défini par (2.17). Pour tout x ≥ 1, on a

∑_{1≤h≤x} ψ(h) ≤ 7x.

Démonstration. On a

∑_{1≤h≤x} ψ(h) = ∑_{1≤h≤x} ∑_{d | h} \frac{τ(d)}{\sqrt{d}} = ∑_{d≤x} \frac{τ(d)}{\sqrt{d}} ⌊\frac{x}{d}⌋ ≤ x ∑_{d=1}^{∞} \frac{τ(d)}{d^{3/2}} = xζ(3/2)^{2}

et ζ(3/2)^{2} = 6.8245.... □

Lemme 4. Soit r(n) le nombre de façons d’écrire n comme somme de deux carrés. Pour tout x ≥ 1, on a

∑_{1≤n≤x} r(n) = πx + R̂_{1}(x) avec |R̂_{1}(x)| ≤ 9\sqrt{x}.

Démonstration. L’argument classique (cf. [9], théorème 339) de comptage des points à coordonnées entières dans le disque centré à l’origine et de rayon \sqrt{x} donne

π(\sqrt{x} − \sqrt{2})^{2} ≤ 1 + ∑_{1≤n≤x} r(n) ≤ π(\sqrt{x} + \sqrt{2})^{2}.

Il s’ensuit que

|R̂_{1}(x)| ≤ 2\sqrt{2}π\sqrt{x} + (2π − 1) ≤ 9\sqrt{x}

pour x ≥ 2500. Le calcul direct de r(1) + r(2) + … + r(n) montre que, pour 1 ≤ x ≤ 2500, on a R̂_{1}(x) ≤ 2.29\sqrt{x}. W. Sierpinski a amélioré la majoration de |R̂_{1}(x)|, cf. [18]. Le record est actuellement détenu par [12]. □

Lemme 5. Soit ρ la fonction multiplicative définie par (2.11) et (2.12). Alors, pour tout x ≥ 1, on a

(i) Υ(x) = ∑_{1≤n≤x} ρ(n) = \frac{3}{2π} x + R̂_{2}(x) avec |R̂_{2}(x)| ≤ (\frac{9}{8} log x + 4) \sqrt{x},

(ii) Υ^{∗}(x) = ∑_{\begin{matrix}1≤n≤x \\ n impair \end{matrix}} ρ(n) = \frac{1}{π} x + R̂_{3}(x) avec |R̂_{3}(x)| ≤ (4 log x + 14) \sqrt{x},

et pour x ≥ 7, on a

(iii)  Υ^{∗}(x) ≤ \frac{3x}{7}·

Démonstration. (i) On sait que la fonction \frac{1}{4}r(n) définie dans le lemme 4 est multiplicative et vaut \frac{1}{4}r(2^{α}) = 1 si α ≥ 1, \frac{1}{4}r(p^{α}) = 0 si p ≡ 3 (mod 4) et α impair, \frac{1}{4}r(p^{α}) = 1 si p ≡ 3 (mod 4) et α pair, \frac{1}{4}r(p^{α}) = α + 1 si p ≡ 1 (mod 4) (cf. [9], théorème 278).

Désignons par μ la fonction de Möbius. Un raisonnement classique montre que la fonction \frac{1}{4} ∑_{d^{2} | n} μ(d)r(n/d^{2}) est également multiplicative et que sa valeur sur les puissances de nombres premiers coïncide avec celle de ρ. On a donc

ρ(n) = \frac{1}{4} ∑_{d^{2} | n} μ(d)r(n/d^{2}).

Par le lemme 4, on a

Υ(x) = ∑_{n≤x} \frac{1}{4} ∑_{d^{2} | n} μ(d)r(n/d^{2}) = \frac{1}{4} ∑_{d≤\sqrt{x}} μ(d) ∑_{d′≤x/d^{2}} r(d′)

= \frac{1}{4} ∑_{d≤\sqrt{x}} μ(d) (π \frac{x}{d^{2}} + R̂_{1} (\frac{x}{d^{2}} )) = \frac{3x}{2π} + R̂_{2}(x)

avec

R̂_{2}(x) = −\frac{πx}{4} ∑_{d>\sqrt{x}} \frac{μ(d)}{d^{2}} + \frac{1}{4} ∑_{d≤\sqrt{x}} R̂_{1} (\frac{x}{d^{2}} ) .

Par le lemme 4 et (2.16), on obtient

|R̂_{2}(x)| ≤ \frac{πx}{4} (\frac{1}{x} + ∫_{√\overline{x}}^{+∞} \frac{dt}{t^{2}}) + \frac{1}{4} ∑_{d≤\sqrt{x}} 9\frac{\sqrt{x}}{d}

≤ \frac{π\sqrt{x}}{2} + \frac{9}{4}\sqrt{x} (1 + \frac{1}{2} log x) ≤ (\frac{9}{8} log x + 4) \sqrt{x}.

(ii) Compte tenu de la valeur de ρ(2^{α}) dans (2.12), on a

∑_{\begin{matrix}1≤n≤x \\ n pair \end{matrix}} ρ(n) = ∑_{\begin{matrix}1≤n≤x \\ n≡2 (mod 4) \end{matrix}} ρ(n) = ∑_{\begin{matrix}1≤n≤x/2 \\ n impair \end{matrix}} ρ(n)

= ∑_{1≤n≤x/2} ρ(n) − ∑_{\begin{matrix}1≤n≤x/2 \\ n pair \end{matrix}} ρ(n).

En réitérant l’argument, on obtient

Υ^{∗}(x) = ∑_{j=0}^{k}(−1)^{j}Υ (\frac{x}{2^{j}} )

où k est l’entier défini par 2^{k} ≤ x < 2^{k+1}. En appliquant (i), il vient

Υ^{∗}(x) = ∑_{j=0}^{k}(−1)^{j} (\frac{3x}{2^{j+1}π} + R̂_{2} (\frac{x}{2^{j}} )) = \frac{x}{π} + R̂_{3}(x)

avec

R̂_{3}(x) = −\frac{3}{2π} ∑_{j=k+1}^{+∞}(−1)^{j} \frac{x}{2^{j}} + ∑_{j=0}^{k}(−1)^{j}R̂_{2} (\frac{x}{2^{j}} ) .

On a

|R̂_{3}(x)| ≤ \frac{3}{2π} ∑_{j=k+1}^{+∞} \sqrt{\frac{x}{2^{j}}} + (\frac{9}{8} log x + 4) ∑_{j=0}^{k} \sqrt{\frac{x}{2^{j}}}

≤ (2 + \sqrt{2}) (\frac{9}{8} log x + 4) \sqrt{x} ≤ (4 log x + 14)\sqrt{x}.

(iii) La fonction \frac{4 log t+14}{\sqrt{t}} est décroissante pour t ≥ 1 et elle est inférieure à 1/10 pour t ≥ 500000 ; (iii) résulte donc de (ii) pour x ≥ 500000. Le calcul numérique de Υ^{∗}(x) pour x entier inférieur à 500000 complète la preuve de (iii). □

Lemme 6. Soient deux nombres réels u et v satisfaisant 1 ≤ u ≤ v. Soit F une fonction continûment dérivable de [u, v] dans ℝ, et ρ défini par (2.11). On pose ∥F ∥ = ∥F ∥_{[u,v]} = max_{u≤t≤v} |F (t)|. Alors on a

∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ρ(d)F (d) = \frac{1}{π} ∫_{u}^{v} F (t)dt + R̂_{0}(u, v; F)

avec

|R̂_{0}(u, v; F)| ≤ (4 log v + 14)\sqrt{v} (2 ∥F ∥ + \frac{2}{3}v ∥F′∥) .

Démonstration. Par le lemme 5 (ii), on a, en utilisant l’intégrale de Stiltjes

∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ρ(d)F (d) = ∫_{u^{−}}^{v} F (t)d[Υ^{∗}(t)] = \frac{1}{π} ∫_{u}^{v} F (t)dt + R̂_{0}(u, v; F)

avec, par intégration par parties,

R̂_{0}(u, v; F) = ∫_{u^{−}}^{v} F (t)d[R̂_{3}(t)] = F (v)R̂_{3}(v) − F (u)R̂_{3}(u) − ∫_{u}^{v} F′(t)R̂_{3}(t)dt

et

|R̂_{0}(u, v; F)| ≤ 2 ∥F ∥ (4 log v + 14)\sqrt{v} + ∥F′∥ (4 log v + 14) ∫_{u}^{v} \sqrt{t} dt

et comme ∫_{u}^{v} \sqrt{t} dt ≤ ∫_{0}^{v} \sqrt{t} dt = \frac{2}{3}v^{3/2} cela achève la preuve du lemme 6.

2.4 Sommes de Kloosterman.

Soit a ∈ ℤ, b ∈ ℤ et m un entier positif. Si ℓ est premier avec m, on notera \overline{ℓ} un entier vérifiant ℓ\overline{ℓ} ≡ 1 (mod m). La somme de Kloosterman K(a, b; m) est définie par

(2.18)  K(a, b; m) = ∑_{\begin{matrix}0<ℓ≤m \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπ(aℓ + b\overline{ℓ})}{m}·

Grâce aux travaux de A. Weil, on sait majorer cette somme, et l’on a l’inégalité (cf. [21], [11], p. 35 ou [13], p. 61)

(2.19)  |K(a, b; m)| ≤ τ(m)\sqrt{m}\{(a, b, m)\}^{1/2}, a, b, m ∈ ℤ, m ≥ 1,

où τ(m) = ∑_{d|m} 1 désigne le nombre de diviseurs de m et (a, b, m) le pgcd

des trois nombres a, b et m. On peut déduire de (2.19) une majoration de la somme de Kloosterman incomplète :

Lemme 7 (cf. [11], Lemma 6, p. 36 et [3], p. 433). Soit m ≥ 1 un entier, et b ∈ ℤ. Soit ξ et ξ′ deux nombres entiers vérifiant 1 ≤ ξ ≤ m et 1 ≤ ξ′ ≤ m. On a

(2.20)  | ∑_{\begin{matrix}ξ≤ℓ≤ξ′ \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m}| ≤ τ(m)\sqrt{m}\{(b, m)\}^{1/2}γ(m)

où

(2.21)  γ(m) = 1 + \frac{2}{π} log \frac{4m}{π} = 1.153 … + 0.6366 … log m.

Démonstration. Si ξ′ < ξ, la somme dans (2.20) est nulle et le lemme est démontré ; on peut donc supposer ξ ≤ ξ′.

En observant que le crochet ci-dessous vaut 1 si n ≡ ℓ (mod m) (ce qui équivaut à n = ℓ) et 0 sinon, il vient

∑_{\begin{matrix}ξ≤ℓ≤ξ′ \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m} = ∑_{\begin{matrix}0<ℓ≤m \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m} ∑_{ξ≤n≤ξ′} [\frac{1}{m} ∑_{1≤a≤m} e^{\frac{2iπa(n−ℓ)}{m}} ]

= ∑_{1≤a≤m} K(−a, b; m) \{\frac{1}{m} ∑_{ξ≤n≤ξ′} exp \frac{2iπan}{m}\} ,

ce qui, en utilisant (2.19), entraîne (2.22)

| ∑_{\begin{matrix}ξ≤ℓ≤ξ′ \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m}| ≤ τ(m)\sqrt{m}\{(b, m)\}^{1/2} ∑_{1≤a≤m} \{|\frac{1}{m} ∑_{ξ≤n≤ξ′} exp \frac{2iπan}{m}|\} .

La quantité dans l’accolade vaut, pour a = m, |ξ′ − ξ + 1|/m ≤ 1, et pour 1 ≤ a < m, elle vaut

|\frac{exp \frac{2iπaξ}{m} − exp \frac{2iπa(ξ′+1)}{m}}{m (exp \frac{2iπa}{m} − 1)} | ≤ \frac{1}{m sin \frac{πa}{m}} ·

La somme en a de (2.22) est donc majorée par

(2.23)  1 + \frac{1}{m} ∑_{a=1}^{m−1} \frac{1}{sin \frac{πa}{m}} ·

Mais une fonction f convexe sur l’intervalle [a−1/2, a+1/2] satisfait f(a) ≤ ∫_{a−1/2}^{a+1/2} f(t)dt. En remarquant que la fonction t ↦ \frac{1}{sin \frac{πt}{m}} est convexe sur l’intervalle [1/2, m − 1/2], on a

∑_{a=1}^{m−1} \frac{1}{sin \frac{πa}{m}} ≤ ∫_{1/2}^{m−1/2} \frac{1}{sin \frac{πt}{m}} dt = \frac{m}{π} [log tan \frac{πt}{2m}]_{1/2}^{m−1/2}
(2.24)  = \frac{2m}{π} log cot \frac{π}{4m} ≤ \frac{2m}{π} log \frac{4m}{π}

et (2.20) résulte de (2.22), (2.23) et (2.24). □

Lemme 8 (cf. [11], p. 38). Nous conservons les notations du lemme 7. Soit une fonction complexe Φ(t) continûment dérivable définie sur l’intervalle réel [0, m]. On suppose que, pour tout t ∈ [0, m], on a |Φ(t)| ≤ M_{0} et |Φ′(t)| ≤ M_{1}. Alors, on a

| ∑_{\begin{matrix}ξ≤ℓ≤ξ′ \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m}Φ(ℓ)| ≤ τ(m)\sqrt{m}\{(b, m)\}^{1/2}γ(m)[|ξ′ − ξ|M_{1} + M_{0}].

Démonstration. Comme dans le lemme 7, nous pouvons supposer ξ ≤ ξ′. Il est commode de poser, pour 0 ≤ t ≤ m

(2.25)  g(t) = ∑_{\begin{matrix}ξ≤ℓ≤t \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m}

et, par le lemme 7, on a

(2.26)  |g(t)| ≤ τ(m)\sqrt{m}\{(b, m)\}^{1/2}γ(m).

Par la méthode de la sommation d’Abel, on écrit :

∑_{\begin{matrix}ξ≤ℓ≤ξ′ \\ (ℓ,m)=1 \end{matrix}} exp \frac{2iπb\overline{ℓ}}{m}Φ(ℓ) = g(ξ)Φ(ξ) + ∑_{ℓ=ξ+1}^{ξ′}(g(ℓ) − g(ℓ − 1))Φ(ℓ)

(2.27)  = ∑_{ℓ=ξ}^{ξ′−1} g(ℓ)(Φ(ℓ) − Φ(ℓ + 1)) + g(ξ′)Φ(ξ′).

On applique le théorème des accroissements finis à Φ(ℓ + 1) − Φ(ℓ), et le lemme suit de (2.27) et (2.26). □

3 Démonstration du théorème 2.

3.1 Le polynôme de Bernoulli.

Soit d ≠ 1 un nombre impair ; avec la définition de E_{d} donnée par (2.2), en choisissant ν entre 1 et d − 1, on a

(3.1) ∑_{\begin{matrix}1≤A≤f(d) \\ 4A^{2}≡−1 (mod d) \end{matrix}} 1 = ∑_{ν ∈ E_{d}}  ∑_{\begin{matrix}1≤A≤f(d) \\ A≡ν (mod d) \end{matrix}} 1 = ∑_{ν∈E_{d}} (⌊\frac{f(d) − ν}{d} ⌋ + 1) .

On remplace dans (3.1) la partie entière par son expression en fonction du polynôme de Bernoulli : B_{1}(t) = t − ⌊t⌋ − 1/2 ; il vient

(3.2)  ∑_{\begin{matrix}1≤A≤f(d) \\ 4A^{2}≡−1 (mod d) \end{matrix}} 1 = ∑_{ν∈E_{d}} (−B_{1} (\frac{f(d) − ν}{d} ) + \frac{f(d)}{d} − \frac{ν}{d} + \frac{1}{2}) .

En associant les deux éléments ν et d − ν de E_{d} (qui sont distincts, car d est impair), les deux derniers termes de (3.2) disparaissent, et, par (2.13), on obtient

(3.3)  ∑_{\begin{matrix}1≤A≤f(d) \\ 4A^{2}≡−1 (mod d) \end{matrix}} 1 = \frac{f(d)ρ(d)}{d} − ∑_{ν∈E_{d}} B_{1} (\frac{f(d) − ν}{d} ) .

On peut ainsi écrire (1.26) où S_{0}(u, v; f) a été défini en (1.27) et

(3.4)  S_{1}(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ∑_{ν∈E_{d}} B_{1} (\frac{f(d) − ν}{d} ) .

Il nous faut maintenant majorer |S_{1}(u, v; f)|.

3.2 La formule de J. Vaaler.

Pour majorer S_{1}(u, v; f) nous commençons par approcher la fonction B_{1}(t) par un polynôme trigonométrique. Nous noterons e(t) = e^{2iπt}, et nous utiliserons le lemme ci-dessous de J. Vaaler.

Lemme 9. Soit ω ∈ ℕ, h ∈ ℤ, 1 ≤ |h| ≤ ω et

(3.5) 0 < b_{ω}(h) =^{def} π \frac{|h|}{ω + 1} (1 − \frac{|h|}{ω + 1}) cot (π \frac{|h|}{ω + 1}) + \frac{|h|}{ω + 1} < 1.

Alors, en posant

(3.6)  B_{ω}^{∗}(t) = −\frac{1}{2iπ} ∑_{1≤|h|≤ω} \frac{b_{ω}(h)}{h}e(ht)

on peut écrire

(3.7)  B_{1}(t) = B_{ω}^{∗}(t) + R_{ω}^{∗}(t)

avec, pour tout t ∈ ℝ,

(3.8) |R_{ω}^{∗}(t)| ≤ \frac{1}{2ω + 2} ∑_{0≤|h|≤ω} (1 − \frac{|h|}{ω + 1}) e(ht) = \frac{sin^{2} π(ω + 1)t}{2(ω + 1)^{2} sin^{2} πt}·

Démonstration. Pour t ∉ ℤ, (3.8) est l’inégalité (7.14) de Vaaler (cf. [20], cf. aussi le théorème A.6 de [7] et [8]). Pour t ∈ ℤ, les deux membres de (3.8) sont égaux à 1/2, et le résultat est encore vrai. □

En utilisant (3.7), pour une valeur de ω que l’on précisera plus tard, (3.4) devient

(3.9)  S_{1}(u, v; f) = S_{2}(u, v; f) + S_{3}(u, v; f)

avec, par (3.6),

S_{2}(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ∑_{ν∈E_{d}} B_{ω}^{∗} (\frac{f(d) − ν}{d} )

(3.10)  = −\frac{1}{2iπ} ∑_{1≤|h|≤ω} \frac{b_{ω}(h)}{h} ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} e (\frac{hf(d)}{d}) ∑_{ν∈E_{d}} e (−\frac{hν}{d} )

et

(3.11)  S_{3}(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ∑_{ν∈E_{d}} R_{ω}^{∗} (\frac{f(d) − ν}{d} ) .

Par (3.8), on a

(3.12)  |S_{3}(u, v; f)| ≤ S_{4}(u, v; f)

en posant (3.13)

S_{4}(u, v; f) = \frac{1}{2ω + 2} ∑_{0≤|h|≤ω} (1 − \frac{|h|}{ω + 1}) ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} e (\frac{hf(d)}{d}) ∑_{ν∈E_{d}} e (−\frac{hν}{d} ) ·

Il est commode de poser, pour h ≠ 0,

(3.14)  P = P (h, u, v, f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} e (\frac{hf(d)}{d}) ∑_{ν∈E_{d}} e (−\frac{hν}{d} )

de telle sorte que (3.10) et (3.13) deviennent

(3.15)  S_{2}(u, v; f) = −\frac{1}{2iπ} ∑_{1≤|h|≤ω} \frac{b_{ω}(h)}{h}P (h, u, v, f)

et (3.16)

S_{4}(u, v; f) = \frac{1}{2ω + 2} ( ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} ρ(d) + ∑_{1≤|h|≤ω} (1 − \frac{|h|}{ω + 1}) P (h, u, v, f)) .

Il nous faut maintenant majorer |P (h, u, v, f)|.

3.3 Evaluation de P(h, u, v, f).

Pour évaluer P (h, u, v, f), nous utiliserons la bijection Θ entre S_{d} et E_{d} étudiée dans la proposition 1. Par cette bijection, on déduit de (3.14)

(3.17)  P (h, u, v, f) = ∑_{\begin{matrix}u≤r^{2}+4s^{2}≤v \\ r impair, r>0, (r,s)=1 \end{matrix}} e (\frac{hf(r^{2} + 4s^{2})}{r^{2} + 4s^{2}} − \frac{νh}{r^{2} + 4s^{2}} )

où ν = Θ(r, s) est donné par l’une des formules (2.3) ou (2.4). Nous coupons la somme (3.17) en quatre parties suivant que |s| < r ou |s| > r et s > 0 ou s < 0 (Remarquons que |s| = r ou s = 0 entraînerait r = (r, s) = 1 ce qui est incompatible avec r^{2} + 4s^{2} ≥ u, pour u > 5). Ainsi dans la somme P_{1}, on impose 1 ≤ s < r ce qui entraîne

u ≤ r^{2} + 4s^{2} < 5r^{2}  et  r^{2} < r^{2} + 4s^{2} ≤ v

et encore

(3.18)  \sqrt{u/5} < r < \sqrt{v};

pour r fixé dans l’intervalle (3.18), les inégalités u ≤ r^{2}+4s^{2} ≤ v et 1 ≤ s < r entraînent l’existence (cf. Fig. 2) de deux nombres entiers ξ_{1} = ξ_{1}(r) et ξ′_{1} = ξ′_{1}(r) vérifiant 1 ≤ ξ_{1} ≤ r − 1 et 1 ≤ ξ′_{1} ≤ r − 1 et tels que

u ≤ r^{2} + 4s^{2} ≤ v et 1 ≤ s < r ⟺ ξ_{1} ≤ s ≤ ξ′_{1}.

Les valeurs de ξ_{1} et ξ′_{1} sont données par :

ξ_{1} = 1 si r ≥ \sqrt{u} et ξ_{1} = ⌈\sqrt{\frac{u − r^{2}}{4}} ⌉ si r < \sqrt{u}

ξ′_{1} = r − 1 si r ≤ \sqrt{\frac{v}{5}} et ξ_{1} = ⌊\sqrt{\frac{v − r^{2}}{4}} ⌋ si r > \sqrt{\frac{v}{5}}.

On a ainsi à partir de (3.17) et (2.3)

(3.19)  P_{1} = P_{1}(h, u, v, f) = ∑_{\begin{matrix}\sqrt{u/5}<r<\sqrt{v} \\ r impair \end{matrix}} ∑_{\begin{matrix}ξ_{1}≤s≤ξ′_{1} \\ (r,s)=1 \end{matrix}} e (\frac{−h\overline{4}\overline{s}}{r}) Φ_{1}(s)

avec, par (1.24),

Φ_{1}(s) = exp (2iπhF (r^{2} + 4s^{2}) − \frac{2iπhs}{r(r^{2} + 4s^{2})}) .

On calcule la dérivée logarithmique de Φ_{1} :

\frac{Φ′_{1}}{Φ_{1}} (s) = \frac{2iπh}{r} (8rsF′(r^{2} + 4s^{2}) − \frac{r^{2} − 4s^{2}}{(r^{2} + 4s^{2})^{2}} )

et l’on a, en observant que |r^{2} − 4s^{2}| ≤ r^{2} + 4s^{2} et 4|rs| ≤ r^{2} + 4s^{2}

|Φ′_{1}(s)| = |\frac{Φ′_{1}}{Φ_{1}} (s)| ≤ \frac{2π|h|}{r} (2(r^{2} + 4s^{2})|F′(r^{2} + 4s^{2})| + \frac{1}{u}) .

r s  r = s r = −s^{r^{2} + 4s^{2} = v}^{r^{2} + 4s^{2} = u}  \sqrt{\frac{v}{5}} \sqrt{\frac{u}{5}}  \sqrt{u}  \sqrt{v} P_{1} P_{2} P_{3} P_{4}

Fig. 2 – Découpage en quatre zones On pose b = −h\overline{4}, où, rappelons le, \overline{4} est un inverse de 4 modulo r. On a (b, r) = (h, r) (car r est impair), |ξ′_{1} − ξ_{1}| ≤ r et le lemme 8 donne

| ∑_{\begin{matrix}ξ_{1}≤s≤ξ′_{1} \\ (r,s)=1 \end{matrix}} e (\frac{−h\overline{4}\overline{s}}{r}) Φ_{1}(s)| ≤ τ(r)\sqrt{r}\{(h, r)\}^{1/2}γ(r)M(h, r)

avec, par (1.23)

M(h, r) = 2π|h| (2 ∥tF′(t)∥ + \frac{1}{u}) + 1.

En notant que u ≥ 7 et en utilisant (1.25), il vient

M(h, r) ≤ 4π|h| (∥tF′(t)∥ + \frac{1}{2u} + \frac{1}{4π} ) ≤ 4π|h|M.

En reportant dans (3.19) on obtient

(3.20)  |P_{1}| ≤ 4π|h|M ∑_{\begin{matrix}\sqrt{u/5}<r<\sqrt{v} \\ r impair \end{matrix}} τ(r)\sqrt{r}\{(h, r)\}^{1/2}γ(r).

Dans la somme P_{2}, on met les termes de (3.17) avec −r < s ≤ −1. On a

P_{2} = P_{2}(h, u, v, f) = ∑_{\begin{matrix}\sqrt{u/5}<r<\sqrt{v} \\ r impair \end{matrix}} ∑_{\begin{matrix}−ξ′_{1}≤s≤−ξ_{1} \\ (r,s)=1 \end{matrix}} e (\frac{−h\overline{4}\overline{s}}{r}) Φ_{1}(s)

(3.21)  = ∑_{\begin{matrix}\sqrt{u/5}<r<\sqrt{v} \\ r impair \end{matrix}} ∑_{\begin{matrix}ξ_{1}≤s≤ξ′_{1} \\ (r,s)=1 \end{matrix}} e (\frac{h\overline{4}\overline{s}}{r}) Φ_{1}(−s).

Par application du lemme 8, on trouve pour |P_{2}| la même majoration que pour |P_{1}|, et l’on a, par (3.20) :

(3.22)  |P_{1}| + |P_{2}| ≤ 8π|h|M ∑_{\begin{matrix}\sqrt{u/5}<r<\sqrt{v} \\ r impair \end{matrix}} τ(r)\sqrt{r}\{(h, r)\}^{1/2}γ(r).

La somme P_{3} contient les termes de la somme (3.17), avec ν donné par (2.4), satisfaisant 1 ≤ r < s. Il existe deux nombres entiers ξ_{3} et ξ′_{3} tels que

(3.23)  1 ≤ ξ_{3} ≤ s  et  1 ≤ ξ′_{3} ≤ s

tels que

(3.24)  P_{3} = P_{3}(h, u, v, f) = ∑_{\sqrt{u/5}<s< \frac{\sqrt{v}}{2}} ∑_{\begin{matrix}ξ_{3} ≤ r ≤ ξ′_{3} \\ (r,4s)=1 \end{matrix}} e (\frac{−h\overline{r}}{4s}) Φ_{3}(r)

avec

Φ_{3}(r) = exp (2iπhF (r^{2} + 4s^{2}) + \frac{iπhr}{2s(r^{2} + 4s^{2})}) .

On a comme précédemment,

|Φ′_{3}(r)| = |\frac{Φ′_{3}}{Φ_{3}} (r)| ≤ \frac{π|h|}{s} ((r^{2} + 4s^{2})|F′(r^{2} + 4s^{2})| + \frac{1}{2u}) .

On applique le lemme 8 avec m = 4s et b = −h; par (3.23), on a |ξ′_{3} −ξ_{3}| ≤ s et il s’ensuit

| ∑_{\begin{matrix}ξ_{3}≤r≤ξ′_{3} \\ (r,4s)=1 \end{matrix}} e (\frac{−h\overline{r}}{4s})Φ_{3}(r)| ≤ π|h|Mτ(4s)\sqrt{4s}\{(h, 4s)\}^{1/2}γ(4s).

Par (3.24), on déduit que

|P_{3}| ≤ π|h|M ∑_{\begin{matrix}4\sqrt{u/5} < m < 2\sqrt{v} \\ 4 | m \end{matrix}} τ(m)\sqrt{m}\{(h, m)\}^{1/2}γ(m).

La même majoration est valable pour la somme P_{4}, où l’on compte les termes de (3.17) avec s < 0 et 1 ≤ r ≤ −s, et l’on déduit de (3.22)

|P | = |P_{1} + P_{2} + P_{3} + P_{4}| ≤ 8π|h|M ∑_{m<2\sqrt{v}} τ(m)\sqrt{m}\{(h, m)\}^{1/2}γ(m).

Par (2.21) et le lemme 2, il suit

|P | ≤ 8π|h|Mγ(2\sqrt{v})\sqrt{2}v^{1/4} ∑_{m≤2\sqrt{v}} τ(m)\{(h, m)\}^{1/2}

≤ 8|h|M\sqrt{2} (log v + π + 2 log \frac{8}{π} ) (log v + 2 + 2 log 2)v^{3/4}ψ(|h|)

≤ 8|h|M\sqrt{2}(log v + 4)^{2}v^{3/4}ψ(|h|) (3.25)

où ψ(|h|) est défini en (2.17).

3.4 Choix de ω.

Par (3.15) et (3.5), on a

|S_{2}(u, v; f)| ≤ \frac{1}{2π} ∑_{1≤|h|≤ω} \frac{1}{|h|}|P |

et par (3.16) et le lemme 5 (iii), on a

|S_{4}(u, v; f)| ≤ \frac{3v}{14(ω + 1)} + \frac{1}{2ω + 2} ∑_{1≤|h|≤ω} |P |
≤ \frac{3v}{14(ω + 1)} + \frac{1}{2} ∑_{1≤|h|≤ω} \frac{1}{|h|}|P |

de sorte que, par (3.9) et (3.12) on a

|S_{1}(u, v; f)| ≤ |S_{2}(u, v; f)| + |S_{4}(u, v; f)|
≤ \frac{3v}{14(ω + 1)} + \frac{1}{2} (\frac{1}{π} + 1) ∑_{1≤|h|≤ω} \frac{1}{|h|}|P |.

Par (3.25) et le lemme 3, en tenant compte des valeurs négatives de h, il suit

(3.26) |S_{1}(u, v; f)| ≤ \frac{3v}{14(ω + 1)} + (\frac{1}{π} + 1) 8\sqrt{2}M(log v + 4)^{2}v^{3/4}(7ω).

On pose

(3.27)  ω_{0} = \frac{1}{14}\sqrt{\frac{3π}{4\sqrt{2}M(π + 1)}} \frac{v^{1/8}}{log v + 4}

et l’on choisit ω

(3.28)  ω = ⌊ω_{0}⌋ .

Par (3.26), il vient

|S_{1}(u, v; f)| ≤ \frac{3v}{14ω_{0}} + 56\sqrt{2} (\frac{1}{π} + 1) (log v + 4)^{2}v^{3/4}ω_{0}M
= 4\sqrt{3\sqrt{2}(1 + 1/π)}(log v + 4)v^{7/8}\sqrt{M}

et comme 4\sqrt{3\sqrt{2}(1 + 1/π)} = 9.4599 …, cela achève la démonstration du théorème 2. □

4 Démonstration du théorème 1.

Dans ce paragraphe, pour les calculs numériques, nous supposerons

(4.1)  λ = 2  et  N ≥ 1000.

Compte tenu de (1.26) nous écrivons (1.22)

(4.2)  Q̂(N, λ) = Q_{0}(N, λ) − Q_{1}(N, λ)

avec, pour i = 0 ou 1 (4.3) Q_{i}(N, λ) = S_{i}(u_{0}, v_{0}; f_{1}) − S_{i}(u_{0}, v_{0}; N − 1) − S_{i}(u_{1}, v_{0}; f_{2}) + S_{i}(u_{1}, v_{0}; N − 1).

Nous évaluerons successivement Q_{0}(N, λ) et Q_{1}(N, λ) ; mais il nous faut d’abord définir quelques nouvelles variables.

4.1 Les quantités approchées.

Nous utiliserons les trois quantités linéaires en N

(4.4) v̂_{0} = λ(2 − \sqrt{2})N, û_{0} = 2(λ − \sqrt{λ^{2} − 1})N, û_{1} = 2(\sqrt{2} − 1)N,

comme des approximations des nombres v_{0}, u_{0} et u_{1} définis en (1.14), (1.16) et (1.17). En utilisant les relations

(4.5)  \sqrt{a} ≤ \sqrt{a + t} ≤ \sqrt{a} + \frac{t}{2\sqrt{a}},  a > 0, t ≥ 0

et (4.6)

\sqrt{a} − \frac{t}{\sqrt{a}} = \sqrt{a} (1 − \frac{t}{a}) ≤ \sqrt{a}\sqrt{1 − \frac{t}{a}} = \sqrt{a − t} ≤ \sqrt{a}, a > 0, 0 ≤ t ≤ a

on obtient les inégalités (rappelons que λ > \sqrt{2} et N ≥ 1) (4.7)

v̂_{0} ≤ v_{0} = 2λN − \frac{1}{2}\sqrt{8λ^{2}N^{2} − 2} ≤ v̂_{0} + \frac{1}{2\sqrt{2}λN} < v̂_{0} + \frac{1}{4N} < v̂_{0} + 1 ≤ 2λN,

(4.8)

û_{0} < u_{0} = 2λN −\sqrt{4(λ^{2} − 1)N^{2} − 1} ≤ û_{0} + \frac{1}{2\sqrt{λ^{2} − 1}N} < û_{0} + \frac{1}{2N} < û_{0} +1

et

(4.9)  û_{1} < u_{1} = \sqrt{8N^{2} + 1} − 2N ≤ û_{1} + \frac{1}{4\sqrt{2}N} < û_{1} + 1.

Nous approcherons les fonctions

(4.10)  f_{1}(t) = \frac{1}{2}\sqrt{t(4λN − t) − 1} et f_{2}(t) = \frac{1}{2} (t + \sqrt{2t^{2} − 1})

définies en (1.13) et (1.12) par

(4.11)  f̂_{1}(t) = \frac{1}{2}\sqrt{t(4λN − t)} et f̂_{2}(t) = \frac{1 + \sqrt{2}}{2}t.

Par (4.6), on a, pour 1 ≤ t ≤ 4λN − 1, N ≥ 1 et λ > \sqrt{2} (4.12)

f̂_{1}(t) − \frac{1}{4} ≤ f̂_{1}(t) − \frac{1}{2\sqrt{4λN − 1}} ≤ f̂_{1}(t) − \frac{1}{2\sqrt{t(4λN − t)}} ≤ f_{1}(t) ≤ f̂_{1}(t)

et, toujours par (4.6), on a, pour t ≥ 1

(4.13)  f̂_{2}(t) − \frac{1}{2} ≤ \frac{1}{2} (t + \sqrt{2}t − \frac{1}{\sqrt{2}t}) ≤ f_{2}(t) ≤ f̂_{2}(t).

4.2 Les termes secondaires de reste.

Pour estimer Q_{0}(N, λ) défini par (4.3), on utilise (1.27) et le lemme 6

(4.14)  S_{0}(u, v; f) = ∑_{\begin{matrix}u≤d≤v \\ d impair \end{matrix}} \frac{ρ(d)f(d)}{d} = J(u, v; f) + R̂_{0}(u, v; F)

où l’on a posé F (t) = f(t)/t et

(4.15)  J(u, v; f) = \frac{1}{π} ∫_{u}^{v} F (t)dt = \frac{1}{π} ∫_{u}^{v} \frac{f(t)}{t}dt.

Nous écrirons

(4.16)  Q_{0}(N, λ) = Q_{2}(N, λ) + Q_{3}(N, λ)

avec (4.17) Q_{2}(N, λ) = J(u_{0}, v_{0}; f_{1}) − J(u_{0}, v_{0}; N − 1) − J(u_{1}, v_{0}; f_{2}) + J(u_{1}, v_{0}; N − 1)

et

Q_{3}(N, λ) = R̂_{0}(u_{0}, v_{0}; F_{1}) − R̂_{0} (u_{0}, v_{0}; \frac{N − 1}{t})

−R̂_{0}(u_{1}, v_{0}; F_{2}) + R̂_{0} (u_{1}, v_{0}; \frac{N − 1}{t}) . (4.18)

Dans ce paragraphe nous majorerons les quatre termes de reste R̂_{0}(u, v; F) et la valeur absolue de leur somme Q_{3}(N, λ) tandis que, dans le paragraphe suivant, nous traiterons les termes principaux J(u, v; f) et Q_{2}(N, λ).

Le premier terme R̂_{0}(u_{0}, v_{0}; F_{1}). Posons par (4.10)

(4.19)  F_{1}(t) = \frac{f_{1}(t)}{t} = \frac{\sqrt{t(4λN − t) − 1}}{2t}·

Avec l’aide de MAPLE, nous dérivons :

(4.20)  F′_{1}(t) = \frac{−2λNt + 1}{2t^{2}\sqrt{t(4λN − t) − 1}} = \frac{−2λNt + 1}{4t^{2}f_{1}(t)},

(4.21)  F′′_{1}(t) = \frac{4t^{2}λN(3λN − t − 3/t) + 3t^{2} + 2}{2t^{3}(t(4λN − t) − 1)^{3/2}}·

Pour λ > \sqrt{2}, N ≥ 1 et t ≥ 1, on a 2λNt > 1 et, par (4.20), on voit que F′_{1}(t) < 0. La quantité 3λN − t − 3/t est minimale en t = \sqrt{3} et vaut 3λN − 2\sqrt{3} > 0 ; par (4.21), F′′_{1}(t) > 0 pour tout t > 0 et donc

(4.22)  F_{1}(t) = \frac{f_{1}(t)}{t} est décroissante et convexe pour 1 ≤ t ≤ v_{0}.

Par (4.8) et (4.4), si l’on choisit N ≥ λ, on a u_{0} ≥ û_{0} = \frac{2N}{λ+\sqrt{λ^{2}−1}} ≥ \frac{2N}{2λ} ≥ 1 ; par (4.22), F_{1} est décroissante sur [u_{0}, v_{0}] et par (1.16) on obtient

(4.23) ∥F_{1}∥ = ∥F_{1}∥_{[u_{0},v_{0}]} = \frac{f_{1}(u_{0})}{u_{0}} = \frac{N}{u_{0}} ≤ \frac{N}{û_{0}} = \frac{λ + \sqrt{λ^{2} − 1}}{2} < 1.87

tandis que, par (4.22), (4.20), (1.16), (4.8) et (4.4), on a

∥F′_{1}∥ = ∥F′_{1}∥_{[u_{0},v_{0}]} = −F′_{1}(u_{0}) = \frac{2λNu_{0} − 1}{4u_{0}^{2}f_{1}(u_{0})} = \frac{2λNu_{0} − 1}{4u_{0}^{2}N}

< \frac{2λNu_{0}}{4u_{0}^{2}N} = \frac{λ}{2u_{0}} < \frac{λ}{2û_{0}} = \frac{λ(λ + \sqrt{λ^{2} − 1})}{4N} < \frac{1.87}{N}· (4.24)

Par le lemme 6, on obtient, pour λ = 2

(4.25)  |R̂_{0}(u_{0}, v_{0}; F_{1})| ≤ (4 log v_{0} + 14)\sqrt{v_{0}} (3.74 + 1.25\frac{v_{0}}{N} ) .

Le deuxième terme R̂_{0} (u_{0}, v_{0}; \frac{N−1}{t}). On a en utilisant (4.8) et (4.4)

(4.26)  ∥\frac{N − 1}{t}∥_{[u_{0},v_{0}]} = \frac{N − 1}{u_{0}} < \frac{N}{u_{0}} ≤ \frac{N}{û_{0}} = \frac{λ + \sqrt{λ^{2} − 1}}{2} < 1.87

et

∥−\frac{N − 1}{t^{2}} ∥_{[u_{0},v_{0}]} = \frac{N − 1}{u_{0}^{2}} ≤ \frac{N}{u_{0}^{2}} ≤ \frac{N}{û_{0}^{2}} = \frac{(λ + \sqrt{λ^{2} − 1})^{2}}{4N} < \frac{3.49}{N}·

Par le lemme 6, il suit pour λ = 2

(4.27)  |R̂_{0} (u_{0}, v_{0}; \frac{N − 1}{t})| ≤ (4 log v_{0} + 14)\sqrt{v_{0}} (3.74 + 2.33\frac{v_{0}}{N} ) .

Le troisième terme R̂_{0}(u_{1}, v_{0}; F_{2}). Par (4.10), on a pour t ≥ 1

(4.28)  F_{2}(t) = \frac{f_{2}(t)}{t} = \frac{1}{2} (\frac{t + \sqrt{2t^{2} − 1}}{t}) ≤ \frac{1 + \sqrt{2}}{2}

et donc

(4.29)  ∥F_{2}∥ = ∥F_{2}∥_{[u_{1},v_{0}]} ≤ \frac{1 + \sqrt{2}}{2} ≤ 1.21.

Pour t ≥ 1, on a 2t^{2} − 1 ≥ 1 et

F′_{2}(t) = \frac{1}{2t^{2}\sqrt{2t^{2} − 1}} ≤ \frac{1}{2t^{2}} ·

Donc, par (4.9) et (4.4)

(4.30)  ∥F′_{2}∥ = ∥F′_{2}∥_{[u_{1},v_{0}]} ≤ \frac{1}{2u_{1}^{2}} ≤ \frac{1}{2û_{1}^{2}} = \frac{1}{8(\sqrt{2} − 1)^{2}N^{2}} ≤ \frac{0.73}{N^{2}}·

Par le lemme 6, il suit pour λ = 2

(4.31)  |R̂_{0}(u_{1}, v_{0}; F_{2})| ≤ (4 log v_{0} + 14)\sqrt{v_{0}} (2.42 + 0.49\frac{v_{0}}{N^{2}} ) .

Le quatrième terme R̂_{0}(u_{1}, v_{0}; \frac{N−1}{t}). On a par (4.9) et (4.4)

(4.32) ∥\frac{N − 1}{t}∥_{[u_{1},v_{0}]} = \frac{N − 1}{u_{1}} < \frac{N}{u_{1}} < \frac{N}{û_{1}} = \frac{1}{2(\sqrt{2} − 1)} = \frac{1 + \sqrt{2}}{2} < 1.21

et

∥−\frac{N − 1}{t^{2}} ∥_{[u_{1},v_{0}]} = \frac{N − 1}{u_{1}^{2}} ≤ \frac{N}{u_{1}^{2}} ≤ \frac{N}{û_{1}^{2}} = \frac{1}{4(\sqrt{2} − 1)^{2}N} < \frac{1.46}{N}·

Par le lemme 6, on a pour λ = 2

(4.33)  |R̂_{0} (u_{1}, v_{0}; \frac{N − 1}{t})| ≤ (4 log v_{0} + 14)\sqrt{v_{0}} (2.42 + 0.98\frac{v_{0}}{N} ) .

On a donc, par (4.18), en ajoutant les inégalités (4.25), (4.27), (4.31) et (4.33),

|Q_{3}(N, 2)| ≤ (4 log v_{0} + 14)\sqrt{v_{0}} (12.32 + 4.56\frac{v_{0}}{N} + 0.49\frac{v_{0}}{N^{2}} ) .

Maintenant par (4.7) et (4.4), on a, pour N ≥ 1000 et λ = 2,

(4.34) v_{0} ≤ v̂_{0} + \frac{1}{4N} = λ(2 − \sqrt{2})N (1 + \frac{1}{4λ(2 − \sqrt{2})N^{2}} ) ≤ 1.18N,

ce qui entraîne log v_{0} ≤ log N + log 1.18 ≤ log N + 0.17 et v_{0}/N^{2} ≤ 1.18/N ≤ 0.002. On obtient ainsi

(4.35)  |Q_{3}(N, 2)| ≤ (77 log N + 283)\sqrt{N}.

4.3 Les termes principaux.

Considérons un quadruplet de nombres réels {û, u, v̂, v} satisfaisant

(4.36)  \frac{N}{λ} ≤ û ≤ u ≤ û + 1 < v̂ ≤ v ≤ v̂ + 1 ≤ 2λN

et un couple de fonctions {f, f̂} continues de l’intervalle [û, v] dans ℝ et satisfaisant

(4.37) ∥f̂− f∥_{[û,v]} ≤ 1  et  ∥f∥_{[û,v]} ≤ ∥f̂∥_{[û,v]} ≤ λ(1 + \sqrt{2})N.

Alors on a

(4.38)  ∫_{u}^{v} \frac{f(t)}{t}dt = ∫ v̂ ; û \frac{f̂(t)}{t}dt + Ĵ

avec

Ĵ = ∫ v̂ ; û \frac{f(t) − f̂(t)}{t}dt − ∫ u ; û \frac{f(t)}{t}dt + ∫ v ; v̂ \frac{f(t)}{t}dt

et par (4.36) et (4.37)

(4.39)  Ĵ ≤ log \frac{v̂}{û} + λ(1 + \sqrt{2})N (log \frac{u}{û} + log \frac{v}{v̂})
≤ log \frac{2λN}{N/λ} + λ(1 + \sqrt{2})N (\frac{u − û}{û} + \frac{v − v̂}{v̂})
≤ log(2λ^{2}) + λ(1 + \sqrt{2})N (\frac{1}{N/λ} + \frac{1}{N/λ})
= log(2λ^{2}) + 2λ^{2}(1 + \sqrt{2}) ≤ 21.40  (pour λ = 2).

Nous appliquerons quatre fois l’égalité (4.38) complétée par l’inégalité (4.39). Observons d’abord que, par (4.8), (4.7), (4.9) et (4.4), les quadruplets {û_{0}, u_{0}, v̂_{0}, v_{0}} et {û_{1}, u_{1}, v̂_{0}, v_{0}} satisfont (4.36) : l’inégalité û_{0} +1 ≤ û_{1} +1 < v̂_{0} est vérifiée, à partir de (4.4), pour N > \frac{2+\sqrt{2}}{2(λ−\sqrt{2})}. Observons ensuite que

les couples de fonctions {f_{1}, f̂_{1}}, {f_{2}, f̂_{2}} et {N − 1, N} vérifient (4.37) sur l’intervalle [û_{0}, v_{0}] en utilisant (4.11), (4.12), (4.13) et (4.7).

Alors, par (4.15) et (4.38), (4.17) s’écrit (4.40)

Q_{2}(N, λ) = \frac{1}{π} (∫ v̂_{0} ; û_{0} \frac{f̂_{1}(t)}{t}dt − ∫ v̂_{0} ; û_{0} \frac{N}{t} dt − ∫ v̂_{0} ; û_{1} \frac{f̂_{2}(t)}{t}dt + ∫ v̂_{0} ; û_{1} \frac{N}{t} dt) + Q_{4}

avec, par (4.39),

(4.41)  |Q_{4}| = |Q_{4}(N, λ)| ≤ \frac{4}{π} 21.40 ≤ 28.

Par (4.4), (4.11) et le changement de variable y = \sqrt{\frac{4λN}{t} − 1}, on calcule

∫ v̂_{0} ; û_{0} \frac{f̂_{1}(t)}{t}dt = \frac{1}{2} ∫_{2(λ−\sqrt{λ^{2}−1})N}^{λ(2−\sqrt{2})N} \sqrt{\frac{4λN}{t} − 1} dt = 4λN ∫_{1+\sqrt{2}}^{λ+\sqrt{λ^{2}−1}} \frac{y^{2}dy}{(1 + y^{2})^{2}}
= λN (\frac{π}{4} − arcsin \frac{1}{λ}) − N(1 + \sqrt{2})

en notant que arctan(λ+\sqrt{λ^{2} − 1}) = \frac{1}{2} (π − arcsin \frac{1}{λ}) qui, en substituant \sqrt{2} à λ, donne arctan(1 + \sqrt{2}) = \frac{3π}{8}.

Par (4.4) et (4.11), (4.40) se réécrit

(4.42)  Q_{2}(N, λ) = α(λ)N + Q_{4}(N, λ)

où α(λ) a été défini en (1.4).

On peut remarquer, par (4.40) que

α(λ)N = \frac{1}{π} ∫∫_{D} \frac{dxdt}{t}

où D est le domaine des points (x, t) satisfaisant N ≤ x ≤ \frac{λN}{\sqrt{2}} et situés entre l’ellipse t^{2} −4λNt+4x^{2} = 0 et la droite t = 2(\sqrt{2}−1)x. En intégrant d’abord en t, on obtient

α(λ)N =∫N^{\frac{λN}{\sqrt{2}}}dx ∫_{2(λN−\sqrt{λ^{2}N^{2}−x^{2}})}^{2(\sqrt{2}−1)x} \frac{dt}{πt} = \frac{1}{π} ∫N^{\frac{λN}{\sqrt{2}}} log \frac{2(\sqrt{2} − 1)x}{2 (λN − \sqrt{λ^{2}N^{2} − x^{2}})}dx.

4.4 Le terme principal de reste.

Pour estimer Q_{1}(N, λ) défini par (4.3), nous appliquerons quatre fois le théorème 2. Pour cela, nous supposerons que N ≥ 7λ de façon que, par (4.8), (4.9) et (4.4), on aît u_{0} ≥ û_{0} ≥ 7 et u_{1} ≥ û_{1} ≥ 7. Rappelons que M(u, v; f) est défini en (1.25).

Le premier terme M(u_{0}, v_{0}; f_{1}). On pose F_{1}(t) = f_{1}(t)/t. A partir de (4.20), on calcule

\frac{d}{dt}(tF′_{1}(t)) = \frac{2λNt^{2}(2λN − t − 3/t) + 2t^{2} + 1}{2t^{2}(t(4λN − t) − 1)^{3/2}}·

La quantité 2λN − t − 3/t est positive pour λ > \sqrt{2}, N ≥ 2 et pour tout t > 0. En remarquant que F′_{1}(t) est négative et en utilisant (4.24), il vient

∥tF′_{1}(t)∥_{[u_{0},v_{0}]} = −u_{0}F′_{1}(u_{0}) < \frac{λ}{2} ·

Il s’ensuit par (1.25) que, pour λ = 2

(4.43)  M(u_{0}, v_{0}; f_{1}) ≤ 1 + \frac{2}{5} = 1.4 < (1.19)^{2}.

Le deuxième terme M(u_{0}, v_{0}; N − 1). Posons f(t) = N − 1, F (t) = (N − 1)/t; on a tF′(t) = −\frac{N−1}{t}, et par (1.25) et (4.26) (4.44)

M(u_{0}, v_{0}; N − 1) = ∥\frac{N − 1}{t}∥_{[u_{0},v_{0}]} + \frac{2}{5} < \frac{λ + \sqrt{λ^{2} − 1}}{2} + \frac{2}{5} < 2.27 < (1.51)^{2}.

Le troisième terme M(u_{1}, v_{0}; f_{2}). On pose F_{2}(t) = f_{2}(t)/t. On a par (4.30) et (4.7)

∥tF′_{2}(t)∥_{[u_{1},v_{0}]} ≤ \frac{v_{0}}{8(\sqrt{2} − 1)^{2}N^{2}} ≤ \frac{2λN}{8(\sqrt{2} − 1)^{2}N^{2}} = \frac{λ}{4(\sqrt{2} − 1)^{2}N} ≤ \frac{1.46}{N}

et, pour N ≥ 1000,

(4.45)  M(u_{1}, v_{0}; f_{2}) ≤ \frac{1.46}{N} + \frac{2}{5} ≤ 0.41 ≤ (0.64)^{2}.

Le quatrième terme M(u_{1}, v_{0}; N − 1). Posons f(t) = N − 1, F (t) = (N − 1)/t; on a tF′(t) = −\frac{N−1}{t}, et par (1.25) et (4.32) (4.46)

M(u_{1}, v_{0}; N − 1) = ∥\frac{N − 1}{t}∥_{[u_{1},v_{0}]} + \frac{2}{5} ≤ \frac{1 + \sqrt{2}}{2} + \frac{2}{5} < 1.61 < (1.27)^{2}.

En conclusion, on peut majorer |Q_{1}(N, 2)| défini par (4.3) à l’aide de (1.28) et, en ajoutant (4.43), (4.44), (4.45) et (4.46), on obtient (4.47) |Q_{1}(N, 2)| ≤ 9.5(log v_{0}+4)v_{0}^{7/8}(1.19+1.51+0.64+1.27) = 43.8(log v_{0}+4)v_{0}^{7/8}.

En utilisant (4.34), (4.47) entraîne

(4.48) |Q_{1}(N, 2)| ≤ 43.8(log(1.18N)+4)(1.18N)^{7/8} ≤ (211+51 log N)N^{7/8}.

4.5 Récapitulation.

Par (1.18), (4.2), (4.16) et (4.42), il vient

Q(N, λ) = α(λ)N + R̃(N, λ)

avec

(4.49)  R̃(N, λ) = −Q_{1}(N, λ) + Q_{3}(N, λ) + Q_{4}(N, λ) + ε(N, λ)

et (1.8) résulte de (4.48), (4.35), (4.41) et (1.32).

La méthode utilisée pour obtenir (4.48), (4.35) et (4.41) montre que, pour tout λ fixé, λ > \sqrt{2}, on a Q_{1}(N, λ) = O_{λ}(N^{7/8}(log N)), Q_{3}(N, λ) = O_{λ}(N^{1/2}(log N)), Q_{4}(N, λ) = O_{λ}(1), et, par (1.31), on a ε(N, λ) = O_{λ}(1) ; ainsi, par (4.49), (1.6) est démontré, ce qui achève la preuve du théorème 1.

TABLE 1^{\begin{matrix}k & N = 2^{k} & Q(N, 2) & Q(N, 2)/N & Q(N, 2) − α(2)N \\ 4 & 16 & 1 & 0.06250000 & 0.55 \\ 5 & 32 & 2 & 0.06250000 & 1.10 \\ 6 & 64 & 2 & 0.03125000 & 0.21 \\ 7 & 128 & 3 & 0.02343750 & −0.59 \\ 8 & 256 & 7 & 0.02734075 & −0.17 \\ 9 & 512 & 21 & 0.04101062 & 6.66 \\ 10 & 1024 & 29 & 0.02832031 & 0.31 \\ 11 & 2048 & 60 & 0.02929688 & 2.62 \\ 12 & 4096 & 122 & 0.02978516 & 7.25 \\ 13 & 8192 & 245 & 0.02990723 & 15.49 \\ 14 & 16384 & 460 & 0.02807617 & 0.99 \\ 15 & 32768 & 944 & 0.02880859 & 25.98 \\ 16 & 65536 & 1806 & 0.02755737 & −30.05 \\ 17 & 131072 & 3639 & 0.02776337 & −33.10 \\ 18 & 262144 & 7347 & 0.02802658 & 2.81 \\ 19 & 524288 & 14756 & 0.02814484 & 67.61 \\ 20 & 1048576 & 29576 & 0.02820587 & 199.23 \\ 21 & 2097152 & 58698 & 0.02798939 & −55.55 \\ 22 & 4194304 & 117372 & 0.02798367 & −135.09 \\ 23 & 8388608 & 235082 & 0.02802396 & 67.81 \\ 24 & 16777216 & 470241 & 0.02802855 & 212.62 \\ 25 & 33554432 & 939804 & 0.02800834 & −252.76 \\ 26 & 67108864 & 1880297 & 0.02801861 & 183.48 \\ 27 & 134217728 & 3761402 & 0.02802463 & 1174.97 \\ 28 & 268435456 & 7521153 & 0.02801844 & 698.94 \\ 29 & 536870912 & 15040659 & 0.02801541 & −249.12 \\ 30 & 1073741824 & 30080525 & 0.02801467 & −1291.25 \\ 31 & 2147483648 & 60153965 & 0.02801137 & −9667.50 \\ 32 & 4294967296 & 120332158 & 0.02801701 & 4893.01 \\ 33 & 8589934592 & 240660303 & 0.02801655 & 5773.02 \\ 34 & 17179869184 & 481315101 & 0.02801622 & 6041.03 \\ 35 & 34359738368 & 962578706 & 0.02801473 & −39413.94 \\ 36 & 68719476736 & 1925208869 & 0.02801547 & −27370.87 \\ 37 & 137438953472 & 3850396279 & 0.02801532 & −76200.75 \\ 38 & 274877906944 & 7701008772 & 0.02801610 & 63812.49 \\ 39 & 549755813888 & 15401833428 & 0.02801577 & −56491.01 \\ 40 & 1099511627776 & 30803795356 & 0.02801589 & 15517.96 \\ 41 & 2199023255552 & 61607438724 & 0.02801582 & −120952.07 \end{matrix}}

36

Références

[1] H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.

[2] R. Crandall and C. Pomerance, Prime Numbers A Computational Perspective, Springer-Verlag, 2001.

[3] H. Daboussi et J. Rivat, Explicit upper bounds for exponential sums over primes, Math. Comp. 70, 2001, 431-447

[4] J.-M. Deshouillers and H. Iwaniec, On the greatest prime factor of n^{2}+1, Ann. Inst. Fourier, 32, n^{o}4, 1982, 1-11.

[5] L.E. Dickson, Studies in the theory of numbers, The University of Chicago Press, 1930.

[6] L.E. Dickson, History of the theory of numbers, t. 3, Chelsea Publishing Company, 1971.

[7] S. Graham and G. Kolesnik, Van der Corput’s Method of Exponential Sums, London Mathematical Society Lecture Note Series 126, Cambridge University Press, 1991.

[8] G. Hanrot, J. Rivat, G. Tenenbaum and P. Zimmermann, Density results on floating-point invertible numbers, prépublication.

[9] G.H. Hardy and E.M. Wright, An introduction to the theory of numbers, 4th edition, Oxford at the Clarendon Press, 1964.

[10] C. Hooley, On the greatest prime factor of a quadratic polynomial, Acta. Math. 117, 1967, 281-299.

[11] C. Hooley, Applications of sieve methods to the theory of numbers, Cambridge tracts in Mathematics n^{o} 70, Cambridge University Press, 1976.

[12] M.N. Huxley, Exponential sums and lattice points, III, à paraître, Proc. London Math. Soc.

[13] H. Iwaniec, Topics in Classical Automorphic Forms, Graduate Studies in Mathematics, vol. 17, Amer. Math. Soc., 1991.

[14] Le système MAPLE de calcul formel, http ://www.maplesoft.com/ [15] J.-M. Muller, Elementary Functions, Algorithms and Implementations,

Birkhäuser, 1997.

[16] A. Nitaj, L’algorithme de Cornacchia, Expositiones Mathematicæ 13, 1995, 358-365.

[17] Le système PARI/GP, http ://www.parigp-home.de

[18] W. Sierpinski, Sur un problème du calcul des fonctions asymptotiques, Prace mat.-fiz., 17, 1906, 77-118 ; et Œuvres Choisies, vol. 1, 73-108.

[19] H.J.S. Smith, The collected mathematical papers of Henry John Stephen Smith, vol. 1, Chelsea Publishing Company, 1965.

[20] J. Vaaler, Some extremal functions in Fourier analysis, Bull. Amer. Math. Soc., 12, 1985, 183-216.

[21] A. Weil, On some exponentials sums, Proc. Nat. Acad. Sci. U.S.A., 34, 1948, 204-207.

Jean-Michel Muller Laboratoire d’Informatique du Parallélisme, UMR 5668 Ecole Normale Supérieure de Lyon 46 Allée d’Italie, F-69364 Lyon cedex 07

e-mail : Jean-Michel.Muller@ens-lyon.fr

Jean-Louis Nicolas, Xavier-François Roblot Institut Girard Desargues, UMR 5028, Bâtiment Doyen Jean Braconnier, Université Claude Bernard (Lyon 1), 21 Avenue Claude Bernard, F-69622 Villeurbanne, France

e-mail : jlnicola@in2p3.fr, roblot@euler.univ-lyon1.fr