A Summation Involving the Divisor and GCD Functions

Randell Heyman School of Mathematics and Statistics University of New South Wales High Street Kensington, N.S.W. 2052 Australia

                      randell@unsw.edu.au

Abstract Let N be a positive integer. Dudek asked for an asymptotic formula for the sum of τ(gcd(a, b)) for all a and b with ab ≤ N. We give an asymptotic result. The approach is partly geometric and differs from the approach used in many recent gcd-sum results.

1 Introduction

Euclid’s lemma states that if p is a prime number, and p divides ab, then p divides a or p divides b (see, for example, Hardy and Wright [4, Theorem 3]). In 2017, Dudek [3] quantified the lemma’s truth when the prime number requirement is relaxed. He suggested it would be interesting to see an asymptotic formula for

S(N) := ∑_{ab≤N} τ (gcd(a, b)) .

Let N be a positive integer throughout. An asymptotic formula does indeed exist, as we show in our theorem as follows: Theorem 1. Let N be a positive integer. Then

S(N) = ζ(2)N log N + ((2γ − 1)ζ(2) − 2θ)N + O (\sqrt{N}) ,

where

θ = ∑_{d<∞} \frac{log d}{d^{2}}.

There has been considerable interest in gcd-sum functions (see Tóth [6] and Haukkanen [5] for surveys). We note that results for a related summation,

∑_{a≤N} (∑_{b=1}^{N} τ(gcd(b, N))) ,

can be inferred from the work of Bordellès [2]. Our theorem is proven differently from the works of Bordellès [2], Haukkanen [5], and Tóth [6] in that we use geometric techniques.

2 Notation and preparatory lemmas

We use the cartesian plane with the normal x and y axes. Throughout the term ‘on and under the curve’ will be above but not including the x-axis, and to the right but not including the y-axis.

For any integer n ≥ 1, we let τ(n) denote the number of divisors of n. As usual the Riemann zeta function is given by

ζ(s) = ∑_{j=1}^{∞} \frac{1}{j^{s}} ,

for all complex numbers s whose real part is greater than 1. We recall that the notation f(x) = O(g(x)) is equivalent to the assertion that there exists a constant c > 0 such that |f(x)| ≤ c|g(x)| for all x. Finally, we use |A| to denote the cardinality of a set A.

We will require the following lemmas:

Lemma 2. Let a and b be positive integers with ab ≤ N. Then

τ(gcd(a, b)) = ∑_{d≤\sqrt{N}} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1.  (1)

Proof. Let τ(gcd(a, b)) = k for some positive integer k. So

τ(gcd(a, b)) = |{d_{1}, …, d_{k} : d_{i}| gcd(a, b)}|.

If d_{i}| gcd(a, b) then, by the properties of the greatest common divisor, d|a and d|b. Therefore {d_{i}, i = 1, …, k : d_{i}| gcd(a, b)} ⊆ {d : d|a, d|b} and so

τ(gcd(a, b)) ≤ ∑_{d≤\sqrt{N}} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1.  (2)

Conversely, suppose that d_{i} ∈ {d : d|a, d|b}. Then d|a and d|b. So d divides gcd(a, b) from the definition of the greatest common divisor. So

{d_{i}, … d_{k} : d_{i}| gcd(a, b)} ⊇ {d : d|a, d|b}.

Therefore

τ(gcd(a, b)) ≥ ∑_{d≤\sqrt{N}} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1,

which proves the lemma.

The divisor summatory function have been well studied. For our purposes it will suffice to use the following (see, for example, Hardy and Wright [4, Notes to Chapter XVIII]):

Lemma 3.

∑_{x≤N} τ(x) = N log N + (2γ − 1)N + O (N^{κ}) ,

where 1/4 ≤ κ < 1/2 for sufficiently large N.

The final lemma formalizes the key insight; every point (x, y) on and under the curve xy ≤ N contributes exactly 1 to the right hand side of (1).

Lemma 4. Fix both N and d ≤ N positive numbers. Then

∑_{ab≤N} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1 = ∑_{c≤N/d^{2}} τ(c).

Proof. Let

J = {(a, b) : ab ≤ N, d|a, d|b}

and

K = {r : r|c for some c ≤ N/d^{2}}.

It suffices to show that |J| = |K|. Suppose (a, b) ∈ J. So a = rd and b = sd where r and s and both positive integers. Since ab ≤ N we have 1 ≤ rsd^{2} ≤ N and so 1 ≤ rs ≤ N/d^{2} (noting that rs is an integer and so 1/d^{2} ≤ rs implies 1 ≤ rs). So the point (r, s) is an integer point on and under the curve xy = N/d^{2}. Thus r divides some c with 1 ≤ c ≤ N/d^{2}. So r ∈ K from which it follows that |J| ≤ |K|. The argument can be reversed. This proves the lemma.

3 Proof of Theorem 1

Using Lemma 2 we have

S(N) = ∑_{ab≤N} ∑_{d≤\sqrt{N}} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1

= ∑_{d≤\sqrt{N}} ∑_{ab≤N} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1.  (3)

From Lemma 4 we have, for a fixed d, that

∑_{ab≤N} ∑_{\begin{matrix}d|a \\ d|b \end{matrix}} 1 = ∑_{c≤N/d^{2}} τ(c).

Substituting into (3) and then using Lemma 3, we obtain

S(N) = ∑_{d≤\sqrt{N}} ∑_{c≤N/d^{2}} τ(c)

= ∑_{d≤\sqrt{N}} (\frac{N}{d^{2}} log (\frac{N}{d^{2}} ) + \frac{(2γ − 1)N}{d^{2}} + O ((\frac{N}{d^{2}} )^{κ}))

= (N log N + (2γ − 1)N) ∑_{d≤\sqrt{N}} \frac{1}{d^{2}} − 2N ∑_{d≤\sqrt{N}} \frac{log d}{d^{2}} + ∑_{d≤\sqrt{N}} O ((\frac{N}{d^{2}} )^{κ}) . (4)

We point out that we have introduced some inefficiency here. We would expect the actual error terms to average out over the summation. But we have resorted to summing upper bounds. Next (see, for example, Apostol [1, Theorem 3.2(b)]) we have

∑_{d≤\sqrt{N}} \frac{1}{d^{2}} = ζ(2) − \frac{1}{\sqrt{N}} + O (\frac{1}{N} ) .

So

(N log N + (2γ − 1)N) ∑_{d≤N} \frac{1}{d^{2}} = (N log N + (2γ − 1)N) (ζ(2) − \frac{1}{\sqrt{N}} + O (\frac{1}{N} ))
= ζ(2)N log N − \sqrt{N} log N + (2γ − 1)ζ(2)N + O (log N) .

(5)

Next, since we have absolute convergence,

−2N ∑_{d≤\sqrt{N}} \frac{log d}{d^{2}} = −2N (∑_{d<∞} \frac{log d}{d^{2}} − ∑_{d>\sqrt{N}} \frac{log d}{d^{2}} ) .

Recall that

θ = ∑_{d<∞} \frac{log d}{d^{2}} throughout.

Then, using Euler’s summation formula, we have

∑_{d>\sqrt{N}} \frac{log d}{d^{2}} = \frac{log N}{2\sqrt{N}} + \frac{1}{\sqrt{N}} + O (\frac{log N}{N} ) .

So

−2N ∑_{d≤\sqrt{N}} \frac{log d}{d^{2}} = −2Nθ + \sqrt{N} log N + 2\sqrt{N} + O(log N).

Finally, using Apostol [1, Theorem 3.2], we have

∑_{d≤\sqrt{N}} O ((\frac{N}{d^{2}} )^{κ}) = N^{κ}O ( ∑_{d≤\sqrt{N}} \frac{1}{d^{2κ}} )
= N^{κ}O (N^{1/2−κ})
= O (\sqrt{N}) .  (6)

Substituting (5) and (6) into (4) completes the proof.

4 Acknowledgment

The author thanks the editor and referee for their suggestions which, amongst other things, led to an improvement in the error term.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[2] O. Bordellès, The composition of the GCD and certain arithmetic functions, J. Integer Sequences 13 (2010), Article 10.7.1.

[3] A. Dudek, On the success of mishandling Euclid’s lemma, Amer. Math. Monthly 123 (2016), 924–927.

[4] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2008.

[5] P. Haukkanen, On a gcd-sum function, Aequationes Math. 76 (2008), 168–178.

[6] L. Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1.

2010 Mathematics Subject Classification: Primary 11N56. Keywords: arithmetic function, divisor function, greatest common divisor.

(Concerned with sequence \underline{A268732}.)

Received April 1 2020; revised versions received April 19 2020; May 1 2020; June 17 2020; June 30 2020. Published in Journal of Integer Sequences, October 16 2020. Minor corrections, February 2 2021.

Return to Journal of Integer Sequences home page.