A Generalization of the Gcd-Sum Function

Ulrich Abel, Waqar Awan, and Vitaliy Kushnirevych Fachbereich MND Technische Hochschule Mittelhessen University of Applied Sciences Wilhelm-Leuschner-Straße 13 61169 Friedberg Germany

                    Ulrich.Abel@mnd.thm.de
                    Waqar.Awan@stud.h-da.de
                Vitaliy.Kushnirevych@mnd.thm.de

Abstract In this paper we consider the generalization G_{d}(n) of the Broughan gcd-sum function, i.e., the sum of such gcd’s that are divisors of the positive integer d. Examples of Dirichlet series and asymptotic relations for G_{d} and related functions are given.

1 Introduction

In the recent article [5], Broughan studies the sum of the greatest common divisors of the first n positive integers with n, i.e., the arithmetic function

G(n) := ∑_{k=1}^{n} gcd(k, n).

This function arises in deriving asymptotic estimates for a lattice point counting problem [5, Sect. 5]. The function G has polynomial growth as n tends to infinity. For p ∈ ℙ (throughout the paper ℙ denotes the set of prime numbers) and α ∈ ℕ, it is not difficult to show that

G(p^{α}) = ∑_{j=0}^{α−1} \underbrace{(p − 1)p^{α−1−j}}_{number of gcd’s equal to p^{j}} p^{j} + 1 · p^{α} = (α + 1)p^{α} − αp^{α−1}.

(cf. [5, Th. 2.2]). Following [5, Cor. 2.1] G is a multiplicative function, i.e., G(mn) = G(m)G(n) for coprime m, n ∈ ℕ, that is, gcd(m, n) = 1. The corresponding Dirichlet series G (s) converges at all points of the complex plane, except at the zeros of the Riemann zeta function and the point s = 2, where it has a double pole. Moreover, Broughan derives asymptotic expressions for the partial sums of the Dirichlet series at all real values of s.

The following generalization of G (see [2]) arises in the study of distribution of determinant values in residue class rings.

For d ∈ ℕ, we introduce the function

G_{d}(n) := ∑_{\begin{matrix}k=1 \\ gcd(k,n)|d \end{matrix}}^{n} gcd(k, n).

Obviously, G(n) = G_{n}(n) and G_{1}(n) = φ(n), where φ is Euler’s totient function.

The purpose of this note is to study the function G_{d}. In the next section we present some elementary properties of G_{d}. Furthermore, we study the corresponding Dirichlet series G_{d} (s). Some of the results will be applied in a forthcoming paper on the distribution of determinant values in residue class rings and finite fields. As an example we mention that in the residue class ring ℤ_{n} (n ∈ ℕ), for r ∈ ℤ_{n},

H_{n}(r) = |{(i, j) ∈ ℤ_{n} × ℤ_{n} | i · j = r}|,

the number of products equal to r having precisely two factors in ℤ_{n}, is equal to

H_{n}(r) = \begin{cases}G_{n}(n) = G(n), & if r = 0; \\ G_{d}(n) = G_{gcd(r,n)}(n), & if r ≠ 0. \end{cases}

A similar problem as the calculation of the value H_{n}(r) in the domain of positive integers is the so-called multiplication table problem posed by Erdős (see [7]): how many integers can be written as a product i · j for a given positive integer n ∈ ℕ with positive integers i ⩽ n and j ⩽ n? Erdős ([7, 8]) gave the first estimates of this quantity. Tenenbaum [13] had made the results of Erdős more precise. Ford ([9, 10]) derived the exact order of magnitude of the n × n multiplication table size completely. Koukoulopolous [11, 12] presents a perfect overview of the actual situation and the further development of Ford-Erdős results.

2 Properties of G_{d}

The following lemma gathers some elementary properties of G_{d}(n).

Lemma 1.

(i) For m, n ∈ ℕ, we have G_{m}(n) = G_{gcd(m,n)}(n). In particular, for m, α ∈ ℕ, p ∈ ℙ, we have G_{gcd}_{(m,p^{α})}(p^{α}) = G_{m}(p^{α}); (ii) for coprime d, n ∈ ℕ, we have G_{d}(n) = φ(n);

(iii) for d = d_{1}d_{2} with gcd(d_{1}, n) = 1, we have G_{d}(n) = G_{d_{2}}(n).

Proof. (i) Since gcd(k, n) | gcd(m, n) ⟺ gcd(k, n) | m for all m, n, k ∈ ℕ, the first formula follows from the definition. One obtains the second one by substituting n = p^{α}.

(ii) If gcd(d, n) = 1, using (i) we get

G_{d}(n) = G_{1}(n) = φ(n).

(iii) Since gcd(d_{1}, n) = 1 ⇒ gcd(d_{1}d_{2}, n) = gcd(d_{2}, n), it follows that

G_{d}(n) = G_{d_{1}d_{2}}(n) = G_{gcd(d_{1}d_{2},n)}(n) = G_{gcd(d_{2},n)}(n) = G_{d_{2}}(n),

where we used (i) twice. The proof of the lemma is completed.

Let ρ_{d} denote the multiplicative function

ρ_{d}(w) = \begin{cases}w, & if w | d; \\ 0, & if w ∤ d. \end{cases}

Then we have the representation

G_{d} = ρ_{d} ∗ φ,  (1)

where ∗ denotes Dirichlet product. Indeed,

G_{d}(n) = ∑_{\begin{matrix}k=1 \\ gcd(k,n)|d \end{matrix}}^{n} gcd(k, n) = ∑_{\begin{matrix}w|d \\ w|n \end{matrix}} wφ (\frac{n}{w}) = ∑_{w|n} ρ_{d}(w)φ (\frac{n}{w}) = (ρ_{d} ∗ φ)(n).

Therefore, G_{d} is multiplicative as it is the Dirichlet product of multiplicative functions [1, Th. 2.5(c) and Th. 2.14].

Theorem 2. G_{d} is a multiplicative function, i.e., for coprime m, n ∈ ℕ, we have

G_{d}(mn) = G_{d}(m)G_{d}(n).

We also give a direct proof of the preceding theorem.

Proof. Let d | n_{1}n_{2} with coprime n_{1}, n_{2} ∈ ℕ. This implies d = d_{1}d_{2} with d_{1} | n_{1} and d_{2} | n_{2}, so that d_{1} and d_{2} are coprime. One has

G_{d}(n_{1}n_{2}) = G_{d_{1}d_{2}}(n_{1}n_{2}) = ∑_{w|d_{1}d_{2}} wφ (\frac{n_{1}n_{2}}{w} ) = ∑_{w_{1}|d_{1}} ∑_{w_{2}|d_{2}} w_{1}w_{2}φ (\frac{n_{1}n_{2}}{w_{1}w_{2}} ) .

Because φ is multiplicative and gcd (\frac{n_{1}}{w_{1}} , \frac{n_{2}}{w_{2}} ) = 1, one obtains

G_{d}(n_{1}n_{2}) = ∑_{w_{1}|d_{1}} w_{1}φ (\frac{n_{1}}{w_{1}} ) ∑_{w_{2}|d_{2}} w_{2}φ (\frac{n_{2}}{w_{2}} ) = G_{d_{1}} (n_{1}) G_{d_{2}} (n_{2}) = G_{d} (n_{1}) G_{d} (n_{2}) .

This completes the proof. Theorem 3. For n ∈ ℕ and for coprime d_{1}, d_{2} ∈ ℕ, we have

G_{d_{1}}(n) · G_{d_{2}}(n) = φ(n) · G_{d_{1}d_{2}}(n).

In particular, G_{d_{1}d_{2}}(n) | G_{d_{1}}(n)G_{d_{2}}(n). Proof. Let d = d_{1}d_{2} with gcd(d_{1}, d_{2}) = 1. By Equation (1) we have

G_{d}(n) = (ρ_{d} ∗ φ)(n) = ∑_{w|n} ρ_{d_{1}d_{2}}(w)φ (\frac{n}{w}) = ∑_{w_{1}|n} ∑_{w_{2}|n} ρ_{d_{1}}(w_{1})ρ_{d_{2}}(w_{2})φ (\frac{n}{w_{1}w_{2}} ) .

Now, decompose n = kn_{1}n_{2} in a product of three pairwise coprime factors k, n_{1}, n_{2} such that d_{i} | n_{i} (i = 1, 2). If w_{i} | d_{i} (i = 1, 2) we conclude that

φ (\frac{n}{w_{1}w_{2}} ) = φ(k)φ (\frac{n_{1}}{w_{1}} ) φ (\frac{n_{2}}{w_{2}} ) = φ(k) \frac{φ (\frac{n}{w_{1}} ) φ (\frac{n}{w_{2}} )}{φ(kn_{2})φ(kn_{1})} = \frac{φ (\frac{n}{w_{1}} ) φ (\frac{n}{w_{2}} )}{φ(n)}.

Hence, we obtain

φ (n) G_{d}(n) = ∑_{w_{1}|n} ρ_{d_{1}}(w_{1})φ (\frac{n}{w_{1}} ) ∑_{w_{2}|n} ρ_{d_{2}}(w_{2})φ (\frac{n}{w_{2}} ) = G_{d_{1}}(n) · G_{d_{2}}(n)

which is the desired formula.

We close this section with the following nice formula. Theorem 4. For all n ∈ ℕ, we have

∑_{i=1}^{n} G_{i}(n) = n^{2}.

Proof. Analogously to the proof of Theorem 2 one has

∑_{i=1}^{n} G_{i}(n) = ∑_{i=1}^{n} ∑_{w|n} ρ_{i}(w)φ (\frac{n}{w}) = ∑_{w|n} φ (\frac{n}{w}) ∑_{i=1}^{n} ρ_{i}(w)

= ∑_{w|n} φ (\frac{n}{w}) w ∑_{\begin{matrix}1⩽i⩽n \\ w|i \end{matrix}} 1 = ∑_{w|n} φ (\frac{n}{w}) w\frac{n}{w} = n ∑_{w|n} φ (w) = n^{2},

where we used that ∑_{w|n} φ (w) = n.

3 Evaluation of G_{d} at positive integers

In this section we consider the problem how to calculate the values of G_{d}(n) for positive integers. We start with the special case of prime powers. In the following δ_{αβ} denotes the

Kronecker symbol defined by δ_{αβ} = \begin{cases}1, & if α = β; \\ 0, & otherwise. \end{cases}

Proposition 5. For prime powers n = p^{α} (α ∈ ℕ) and d = p^{β}, β ⩽ α (β ∈ ℕ ∪ {0}), we have

G_{p^{β}}(p^{α}) = φ(p^{α}) (1 + β + \frac{δ_{αβ}}{p − 1}) .

For prime powers n = p^{α} (α ∈ ℕ) and d = p^{β}, β > α (β ∈ ℕ), we have

G_{p^{β}}(p^{α}) = G_{p^{α}}(p^{α}) = φ(p^{α}) (1 + α + \frac{1}{p − 1}) .

Proof. For 0 < β < α, we have

G_{p^{β}}(p^{α}) = ∑_{j=0}^{β}(p^{α−j} − p^{α−j−1})p^{j} = (p^{α} − p^{α−1})(1 + β) = φ(p^{α})(1 + β),

and, for β = α,

G_{p^{β}}(p^{α}) = G_{p^{α}}(p^{α}) = G(p^{α}) = (α + 1)p^{α} − αp^{α−1}
= (α + 1)(p^{α} − p^{α−1}) + p^{α−1} = φ(p^{α})(1 + β) + p^{α−1}.

In the case β = 0 application of Lemma 1 (ii) leads to G_{1}(p^{α}) = φ(p^{α}) = φ(p^{α})(1+β). Thus, for all 0 ⩽ β ⩽ α, one has

G_{p^{β}}(p^{α}) = φ(p^{α})(1 + β) + p^{α−1} · δ_{αβ} = φ(p^{α}) (1 + β + \frac{p^{α−1} · δ_{αβ}}{φ(p^{α})} ) .

Taking into account that φ(p^{α}) = p^{α} − p^{α−1} one obtains the first result. For β > α, we have gcd(k, p^{α}) | p^{β} ⟺ gcd(k, p^{α}) | p^{α}. Hence,

G_{p^{β}}(p^{α}) = ∑_{\begin{matrix}k=1 \\ gcd(k,p^{α})|p^{β} \end{matrix}}^{p^{α}} gcd(k, p^{α}) = ∑_{\begin{matrix}k=1 \\ gcd(k,p^{α})|p^{α} \end{matrix}}^{p^{α}} gcd(k, p^{α}) = G_{p^{α}}(p^{α})

and the second result follows by application of the first formula.

Remark 6. The result of Proposition 5 can be written in one single formula: for p ∈ ℙ, α ∈ ℕ and β ∈ ℕ ∪ {0}, we have

G_{p^{β}}(p^{α}) = φ(p^{α}) (1 + min(α, β) + \frac{δ_{α,min(α,β)}}{p − 1} ) .

Theorem 7. For n ∈ ℕ with prime powers decomposition n = p_{1}^{λ_{1}} · . . . · p_{t}^{λ_{t}} and positive integer d = c·p_{1}^{κ_{1}} ⋯ p_{t}^{κ_{t}} with p_{j} ∤ c for all j = 1, …, t, and 0 ⩽ κ_{j} we have the representation^{1}

G_{d}(n) = φ(n) · ∏_{j=1}^{t} (1 + min(κ_{j}, λ_{j}) + δ_{λ_{j},min(κ_{j},λ_{j})} \frac{1}{p_{j} − 1}) .

Proof. Because G_{d} is multiplicative, by Theorem 2, and applying Lemma 1 (iii), we obtain

G_{d}(n) = G_{d} (∏_{j=1}^{t} p_{j}^{λ_{j}})

= ∏_{j=1}^{t} G_{c·p_{1}^{κ_{1}}···p_{t}^{κ_{t}}} (p_{j}^{λ_{j}})

= ∏_{j=1}^{t} G_{p_{j}^{κ_{j}}} (p_{j}^{λ_{j}})

= ∏_{j=1}^{t} φ (p_{j}^{λ_{j}}) (1 + min(κ_{j}, λ_{j}) + \frac{δ_{λ_{j} min(κ_{j},λ_{j})}}{p_{j} − 1} ) ,

where the last equation is a consequence of Rem. 6.

We note that under the notation of Theorem 7 the equation

gcd(d, n) = p_{1}^{κ_{1}} ⋯ p_{t}^{κ_{t}}

defines unique numbers κ_{j} (j = 1, …, t) with 0 ⩽ κ_{j} ⩽ λ_{j}, such that the result can be written in the form

G_{d}(n) = G_{gcd(d,n)}(n) = φ(n) · ∏_{j=1}^{t} (1 + κ_{j} + δ_{λ_{j},κ_{j}} \frac{1}{p_{j} − 1}) .

4 Dirichlet series, averages and asymptotic properties

Some asymptotic formulas of the Broughan’s gcd-sum function were derived by Broughan [5] and Bordellès [4]. The average order of the Dirichlet series of the Broughan’s gcd-sum function was studied by Broughan [6] and Bordellès [3]. In this section we give some examples of Dirichlet series of arithmetic functions connected with G_{d}(n). We calculate the average functions and derive some asymptotic formulas for these examples.

1κ_{j} = 0 means that p_{j} is not present in the decomposition of d, i.e., p_{j} ∤ d.

The Dirichlet series for an arithmetic function f(n) is defined (see, e.g., [1, 11.1, p. 224]) by

F(s) := ∑_{n=1}^{∞} \frac{f(n)}{n^{s}}.

The most prominent example is the Riemann ζ function ζ(s) = ∑_{n=1}^{∞} \frac{1}{n^{s}}. It is clear, that ζ(s)

is the Dirichlet series associated to f(n) = 1, for all n ∈ ℕ.

For any prime number p, the Bell series [1, Sect. 2.15, p. 42ff] of an arithmetic function f is the formal power series

f_{p}(x) = ∑_{n=0}^{∞} f(p^{n})x^{n}.

If f is multiplicative the corresponding Dirichlet series is given by

F(s) = ∑_{n=1}^{∞} f(n)n^{−s} = ∏_{p} f_{p}(p^{−s})

provided that the Dirichlet series converges absolutely for Re s > a (see, e.g., [1, Th. 11.7, p. 231]).

The number e ∈ ℕ ∪ {0} is called the m-adic order of n ∈ ℕ (m ∈ ℕ), if m^{e} | n and m^{e+1} ∤ n. It is denoted by e = ν_{m}(n).

4.1 The arithmetic function G_{d}

4.1.1 Dirichlet series

Since G_{d} = ρ_{d} ∗ φ (see (1)) and

P_{d}(s) := ∑_{n=1}^{∞} \frac{ρ_{d}(n)}{n^{s}} = ∑_{n|d} \frac{1}{n^{s−1}} ;

Φ(s) := ∑_{n=1}^{∞} \frac{φ(n)}{n^{s}} = \frac{ζ(s − 1)}{ζ(s)} = ∏_{p} \frac{1 − p^{−s}}{1 − p^{1−s}} ,

([1, Ex. 4, p. 229 and p. 231]), we have according to [1, Th. 11.5]: for Re s > 2,

G_{d}(s) := ∑_{n=1}^{∞} \frac{G_{d}(n)}{n^{s}} = ∑_{n=1}^{∞} \frac{ρ_{d}(n) ∗ φ(n)}{n^{s}} = P_{d}(s)Φ(s),

so

G_{d}(s) = \frac{ζ(s − 1)}{ζ(s)} · ∑_{n|d} \frac{1}{n^{s−1}} = ∏_{p} \frac{1 − p^{−s}}{1 − p^{1−s}} · ∑_{n|d} \frac{1}{n^{s−1}} .

If d = 1 one obviously has G_{1}(s) = \frac{ζ(s − 1)}{ζ(s)} (cf. [1, Ex. 3, p. 231]). For d ∈ ℙ, one has

G_{d}(s) = \frac{ζ(s − 1)}{ζ(s)} (1 + \frac{1}{d^{s−1}} ) .

4.1.2 Average functions We study the asymptotic behaviour of the average function

G_{d}^{[α]} (x) := ∑_{n≤x} n^{−α}G_{d} (n)

as n tends to infinity. Taking advantage of the representation G_{d} = ρ_{d} ∗ φ we obtain

G_{d}^{[α]} (x) = ∑_{n≤x} ∑_{w|n} \frac{ρ_{d} (w)}{w^{α}} \frac{φ (\frac{n}{w})}{(\frac{n}{w})α}.

By application of [1, Th. 3.10, p. 65], we conclude that

G_{d}^{[α]} (x) = ∑_{n≤x} n^{−α}ρ_{d} (n) Φ^{[α]} (\frac{x}{n}) = ∑_{w|d} w^{−(α−1)}Φ^{[α]} (\frac{x}{w}) ,

where Φ^{[α]} denotes the average

Φ^{[α]} (x) := ∑_{n≤x} n^{−α}φ (n)

of Euler’s totient function φ. We distinguish 3 cases. Because, for α ≤ 1,

Φ^{[α]} (x) ∼ \frac{x^{2−α}}{2 − α}ζ^{−1} (2) + O (x^{1−α} log x) (x → ∞) ,

([1, Ex. 8, p. 71]), we have

G_{d}^{[α]} (x) ∼ \frac{x^{2−α}}{2 − α}ζ^{−1} (2) ∑_{w|d} \frac{1}{w} + O (x^{1−α} log x) (x → ∞) .

Because, for α > 1, α ≠ 2,

Φ^{[α]} (x) ∼ \frac{x^{2−α}}{2 − α}ζ^{−1} (2) + \frac{ζ (α − 1)}{ζ (α)} + O (x^{1−α} log x) (x → ∞) ,

([1, Ex. 7, p. 71]), we have

G_{d}^{[α]} (x) ∼ \frac{x^{2−α}}{2 − α}ζ^{−1} (2) ∑_{w|d} \frac{1}{w} + \frac{ζ (α − 1)}{ζ (α)} ∑_{w|d} w^{−(α−1)} + O (x^{1−α} log x) (x → ∞) .

Finally, for α = 2, we have

Φ^{[2]} (x) ∼ \frac{log x}{ζ (2)} + \frac{γ}{ζ (2)} − A + O (\frac{log x}{x}) (x → ∞) ,

where γ is Euler’s constant and A = ∑_{n=1}^{∞} μ (n) n^{−2} log n ([1, Ex. 6, p. 71]), and we conclude that

G_{d}^{[2]} (x) ∼ \frac{1}{ζ (2)} ∑_{w|d} \frac{log (x/w)}{w} + (\frac{γ}{ζ (α)} − A) ∑_{w|d} w^{−1} + O (\frac{log x}{x}) (x → ∞) .

4.2 The arithmetic function G_{n/ gcd(r,n)}(n)

Let r ∈ ℕ be given. Consider the arithmetic function

b^{(r)}(n) := G_{n/ gcd(r,n)}(n).

which is easily seen to be multiplicative. Let p be a prime number and put β = ν_{p}(r). According to Prop. 5 one has

b^{(r)}(p^{n}) = G_{p^{n}/ gcd(r,p^{n})}(p^{n}) = G_{p^{n−β}}(p^{n}) = φ(p^{n}) (1 + n − β + \frac{δ_{n,n−β}}{p − 1} ) .

So, if β = 0 one has δ_{n,n−β} = 1 and

b^{(r)}(p^{n}) = φ(p^{n}) (1 + n + \frac{1}{p − 1}) = (n + 1)p^{n} − np^{n−1}.

Therefore, for β = 0, the Bell series is given by

b_{p}^{(r)}(x) = ∑_{n=0}^{∞} b^{(r)}(p^{n})x^{n} = ∑_{n=0}^{∞} ((n + 1)p^{n} − np^{n−1}) x^{n} = \frac{1 − x}{(1 − px)^{2}} .

If β > 0 one has δ_{n,n−β} = 0 and

b_{p}^{(r)}(x) = ∑_{n=0}^{∞} b^{(r)}(p^{n})x^{n} = ∑_{n=0}^{∞} φ(p^{n})(1 + n − β)x^{n}

= ∑_{n=0}^{∞}(p^{n} − p^{n−1})(1 + n − β)x^{n} = \frac{(p − 1)(pxβ − β + 1)}{p(px − 1)^{2}}.

Hence, the Dirichlet series is given by

B^{(r)}(s) := \frac{ζ^{2}(s − 1)}{ζ(s)} ∏_{p|r} \frac{(p − 1)(1 − (1 − p^{1−s}) β (p))}{p − p^{1−s}} (Re s > 2) ,

where β (p) = ν_{p}(r).

4.3 The arithmetic function G_{n}(gcd(r, n)n)

Let r ∈ ℕ be given. Consider the arithmetic function

a^{(r)}(n) := G_{n}(gcd(r, n) · n)

which is easily seen to be multiplicative. Let p be a prime number and put β = ν_{p}(r). According to Remark 6 one has

a^{(r)}(p^{n}) = G_{p^{n}}(gcd(r, p^{n})p^{n}) = G_{p^{n}} (p^{n+min(β,n)})

= φ (p^{n+min(β,n)}) (1 + n + δ_{0,min(β,n)} \frac{1}{p − 1}) .

If β = 0, one has δ_{0,min(β,n)} = 1 and

a^{(r)}(p^{n}) = φ(p^{n}) (1 + n + \frac{1}{p − 1}) = (n + 1)p^{n} − np^{n−1}.

Therefore, for β = 0, the Bell series is given by

a_{p}^{(r)}(x) = ∑_{n=0}^{∞} a^{(r)}(p^{n})x^{n} = ∑_{n=0}^{∞} ((n + 1)p^{n} − np^{n−1}) x^{n} = \frac{1 − x}{(1 − px)^{2}} .

If β > 0 one has δ_{0,min(β,n)} = 0 and

a_{p}^{(r)}(x) = 1 + ∑_{n=1}^{∞}(1 + n)φ(p^{n+min(β,n)})x^{n}

= 1 + ∑_{n=1}^{β}(1 + n)φ(p^{2n})x^{n} + ∑_{n=β+1}^{∞}(1 + n)φ(p^{n+β})x^{n}

= 1 + ∑_{n=1}^{β}(1 + n)(p^{2n} − p^{2n−1})x^{n} + ∑_{n=β+1}^{∞}(1 + n)(p^{n+β} − p^{n+β−1})x^{n}

= 1 + \frac{p − 1}{p} ∑_{n=1}^{β}(n + 1)(p^{2}x)^{n} + p^{β−1}(p − 1) ∑_{n=β+1}^{∞}(n + 1)(px)^{n}

= 1 + \frac{(p − 1)px((β + 1)(p^{2}x)^{β+1} − (β + 2)(p^{2}x)^{β} − p^{2}x + 2)}{(p^{2}x − 1)^{2}}

− \frac{(p − 1)p^{2β}x^{β+1}((β + 1)px − (β + 2))}{(px − 1)^{2}}.

Hence, the Dirichlet series is given by

A^{(r)}(s) := \frac{ζ^{2}(s − 1)}{ζ(s)} ∏_{p|r} (\frac{(1 − p^{1−s})^{2}}{1 − p^{−s}} a_{p}^{(r)}(p^{−s})) (Re s > 2) .

where

a_{p}^{(r)}(p^{−s}) = 1 − \frac{(p − 1)p^{2β}p^{−s(β+1)}((β + 1)p^{1−s} − (β + 2))}{(1 − p^{1−s})^{2}}

+\frac{(p − 1)p^{1−s}((β + 1)p^{(2−s)(β+1)} − (β + 2)p^{(2−s)β} − p^{2}x + 2)}{(p^{2}x − 1)^{2}}

and β = β (p) = ν_{p}(r).

5 Acknowledgment

The authors are grateful to the referee for valuable remarks, in particular for pointing out the similarity of our function H_{n}(r) to the famous Erdős multiplication table problem.

References

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

[2] W. Awan, Werteverteilung der Determinanten von Matrizen über Restklassenringen und endlichen Körpern, Bachelor thesis, Friedberg, Germany, 2012.

[3] O. Bordellès, A note on the average order of the gcd-sum function, J. Integer Seq. 10 (2007), Article 07.3.3.

[4] O. Bordellès, An asymptotic formula for short sums of gcd-sum functions, J. Integer Seq. 15 (2012), Article 12.6.8.

[5] K. A. Broughan, The gcd-sum function, J. Integer Seq. 4 (2001), Article 01.2.2.

[6] K. A. Broughan, The average order of the Dirichlet series of the gcd-sum function, J. Integer Seq. 10 (2007), Article 07.4.2.

[7] P. Erdős, Some remarks on number theory, Riveon Lematematika 9 (1955), 45–48.

[8] P. Erdős, An asymptotic inequality in the theory of numbers, Vestnik Leningrad Univ. 15 (1960), 41–49.

[9] K. Ford, Integers with a divisor in (y, 2y] in J.-M. Koninck, A. Granville, F. Luca, eds., Anatomy of Integers, CRM Proc. and Lect. Notes 46, Amer. Math. Soc., Providence, RI, 2008, pp. 65–81.

[10] K. Ford, The distribution of integers with a divisor in a given interval, Annals of Math. 168 (2008), 367–433.

[11] D. Koukoulopolous, Generalized and restricted multiplication tables of integers, Ph.D. thesis, Univ. Illinois, 2010,

    http://dms.umontreal.ca/~koukoulo/documents/publications/phdthesis.pdf.

[12] D. Koukoulopolous, On the number of integers in a generalized multiplication table,

    preprint, http://arxiv.org/abs/1102.3236v3.

[13] G. Tenenbaum, Sur la probabilité qu’un entier possède un diviseur dans un intervalle donné, Compositio Math. 51 (1984), 243–263.

2010 Mathematics Subject Classification: Primary 11A05; Secondary 11A25, 11F66, 11N37, 11N56. Keywords: multiplicative structure, arithmetic function, one-variable Dirichlet series, asymptotic results on arithmetic functions.

Received February 6 2013; revised version received June 29 2013. Published in Journal of Integer Sequences, July 29 2013.

Return to Journal of Integer Sequences home page.