INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A19

THE GENERAL GCD-PRODUCT FUNCTION

Andrew D. Loveless

Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195-4350, USA

                        aloveles@math.washington.edu

Received: 2/28/06, Revised: 4/25/06, Accepted: 6/19/06, Published: 7/6/06

Abstract

For a given arithmetic function h(x), we consider the function g(n; h) = ∏_{j=1}^{n} h((j, n)), where (j, n) is the greatest common divisor of j and n. We give evaluations in terms of prime powers, Dirichlet series, and asymptotics involving g(n; h). The Dirichlet series lead to several identities involving the Riemann Zeta function. One such result is the following: For real numbers α and β, we have \frac{∑_{n=1}^{∞} ∑_{j=1}^{n}(j,n)^{α}n^{−s}}{∑_{n=1}^{∞} ∑_{j=1}^{n}(j,n)^{β}n^{−s}} = \frac{ζ(s−α)}{ζ(s−β)} for Re(s) > max\{2, α+1, β+1\}. We finish by discussing bounds along with asymptotics for the special case g(n) = g(n; e) where e(x) := x.

Mathematical Subject Classifications: 11A05, 11A25, 11M06, 11N37, 11Y60, 11Y11

1. Introduction

For an arithmetic function, h(x), we define the General gcd-Product Function as follows:

g(n; h) := ∏_{j=1}^{n} h((j, n)),

where (j, n) := gcd(j, n) is the greatest common divisor of j and n. We also define

g(n) := ∏_{j=1}^{n}(j, n).

Defining e(x) := x, note that g(n) = g(n; e). In this study, we investigate various properties of these functions.

Evaluations and asymptotics for the expression ∑_{j=1}^{n}(j, n) are discussed by Broughan [2]. A general development for sums of the form ∑_{i,j=1}^{n} h((i, j)) is given in several publications by Cohen [3], [4], [5]. Since log[g(n; exp ∘ h)] = ∑_{j=1}^{n} h((j, n)), many of our results will generalize the previous studies. For clarification, (exp ∘ h)(x) = e^{h(x)}.

We begin by briefly mentioning two applications related to these functions. For a positive integer n, the number of distinct solutions modulo n to the congruence x^{n−1} ≡ 1 (mod n) is given by the formula ∏_{p|n}(p−1, n−1), where the product is over all distinct primes dividing n (a proof of this formula is given by Baillie and Wagstaff [1]). Formulas like this one are commonly used in the study of probabilistic primality testing. For instance, this author [6] gave a probabilistic primality test which never fails for Carmichael numbers by studying formulas involving products of the form ∏_{p|n}[(p±1, n±1)−2]. These formulas do not easily submit to a general study. Thus, we hope the general theory of the simpler function g(n; h) will shed some light on the growth and behavior of other formulas involving gcd products.

Another application arises in the study of lattice points on lines in the plane. Given two integer lattice points P (a, b) and Q(c, d), the number of lattice points on the segment connecting P and Q is given by (a − c, b − d) + 1. Given several different line segments, the formula for the number of ways to choose one lattice point from each segment will involve products of gcd values. In such instances, information about the function g(n) can be useful.

The current study includes:

1. Evaluations, identities, and properties of g(n; h).
2. Dirichlet series and asymptotics for log[g(n; h)].
3. Bounds and asymptotics for the special case g(n).

2. Evaluations, Identities and Properties

In the following discussion we assume that h(x) is an arithmetic function. When we want h(x) to have more properties, like the multiplicative property, we will be explicit. First we consider the values of g(n; h) at prime powers. Observe, if p is a prime, then

g(p; h) = ∏_{j=1}^{p} h((j, p)) = h(p)h(1)^{p−1}.

Theorem 1. If p is a prime and a is a positive integer, then

g(p^{a}; h) = \frac{h(p^{a})}{h(p^{a−1})}g(p^{a−1}; h)^{p}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A19 3

Proof.

g(p^{a}; h) = ∏_{j=1}^{p^{a}} h((j, p^{a}))
= ∏_{j=1}^{p^{a−1}} h((j, p^{a})) ∏_{j=p^{a−1}+1}^{2p^{a−1}} h((j, p^{a})) … ∏_{j=(p−1)p^{a−1}+1}^{p^{a}} h((j, p^{a}))
= \frac{h(p^{a})}{h(p^{a−1})} ∏_{j=1}^{p^{a−1}} h((j, p^{a−1})) ∏_{j=1}^{p^{a−1}} h((j, p^{a−1})) … ∏_{j=1}^{p^{a−1}} h((j, p^{a−1}))
= \frac{h(p^{a})}{h(p^{a−1})}g(p^{a−1}; h)^{p}.

We can now give the evaluation at prime powers by induction. Theorem 2. If p is a prime and a is a positive integer, then

g(p^{a}; h) = h(p^{a}) ∏_{j=0}^{a−1} h(p^{j})^{(p−1)p^{a−j−1}}.

Proof. When a = 1, we get the appropriate value h(p)h(1)^{p−1}.

Assume the result is true for k. Then

g(p^{k+1}; h) = \frac{h(p^{k+1})}{h(p^{k})}g(p^{k}; h)^{p}
= \frac{h(p^{k+1})}{h(p^{k})} (h(p^{k}) ∏_{j=0}^{k−1} h(p^{j})^{(p−1)p^{k−j−1}})^{p}
= h(p^{k+1})h(p^{k})^{p−1} ∏_{j=0}^{k−1} h(p^{j})^{(p−1)p^{k−j}}
= h(p^{k+1}) ∏_{j=0}^{k} h(p^{j})^{(p−1)p^{k−j}}
= h(p^{k+1}) ∏_{j=0}^{k} h(p^{j})^{(p−1)p^{(k+1)−j−1}}.

The result holds by induction.

This is not a miraculous result, but note that it holds for h(x) in general. For example,

∏_{j=1}^{17^{2}} \sqrt{\sqrt{(j, 17^{2})} + (j, 17^{2})}
= \sqrt{\sqrt{17^{2}} + 17^{2}}\sqrt{\sqrt{17} + 17}^{17−1}\sqrt{1 + 1}^{(17−1)17}
= \sqrt{306}(\sqrt{17} + 17)^{8}2^{8∗17}
= 2^{136}\sqrt{306} (\sqrt{17} + 17)^{8} .

In the theory of arithmetic functions, the typical next step is to prove that the function is multiplicative. However, g(n; h) and g(n) are not multiplicative in general. Even so, we can prove the following relationship for relatively prime integers.

Theorem 3. If h(x) is multiplicative and m and n are integers with (m, n) = 1, then

g(mn; h) = [g(m; h)]^{n}[g(n; h)]^{m}.

Proof. For (m, n) = 1 and j any positive integer, observe that h((j, mn)) = h((j, n)(j, m)) = h((j, n))h((j, m)). Then

g(mn; h) = ∏_{j=1}^{mn} h((j, mn))
= [∏_{j=1}^{mn} h((j, m))] [∏_{j=1}^{mn} h((j, n))]
= [∏_{j=1}^{m} h((j, m))]^{n} [∏_{j=1}^{n} h((j, n))]^{m}
= [g(m; h)]^{n}[g(n; h)]^{m}.

Now define

f(n; h) := g(n; h)^{1/n}.

We can immediately give analogous results for f. Notice that this definition of f(n; h) was chosen to yield the multiplicative property when h(x) is multiplicative.

Theorem 4. If h(x) is multiplicative, then the function f(n; h) = g(n; h)^{1/n} satisfies the following properties:

1. If p is a prime and a is a positive integer, then

f(p^{a}; h) = h(p^{a})^{p^{−a}} ∏_{j=0}^{a−1} h(p^{j})^{(p−1)p^{−j−1}}.

2. If m and n are positive integers with (m, n) = 1, then

f(mn; h) = f(m; h)f(n; h) (f is multiplicative).

Proof. The first statement is a direct application of Theorem 2 and the definition of f. For the second statement, using Theorem 3, observe that

f(mn; h) = g(mn; h)^{1/(mn)} = [g(m; h)^{n}]^{1/(mn)}[g(n; h)^{m}]^{1/(mn)}
= f(m; h)f(n; h).

Finally, we have the general evaluations of g(n; h) and f(n; h) based on the prime factorization of an integer n when h(x) is multiplicative.

Corollary 1. (Evaluations of f(n; h) and g(n; h).) If n = ∏_{i=1}^{k} p_{i}^{a_{i}} is the prime factorization of n and h(x) is multiplicative, then

f(n; h) = ∏_{i=1}^{k} [h(p_{i}^{a_{i}})^{p_{i}^{−a_{i}}} ∏_{j=0}^{a_{i}−1} h(p_{i}^{j})^{(p_{i}−1)p_{i}^{−j−1}}] and

g(n; h) = (∏_{i=1}^{k} [h(p_{i}^{a_{i}})^{p_{i}^{−a_{i}}} ∏_{j=0}^{a_{i}−1} h(p_{i}^{j})^{(p_{i}−1)p_{i}^{−j−1}}])^{n} .

Taking h(x) := x, we get all the same results for g(n) and f(n) as corollaries.

Corollary 2. The functions f(n) and g(n), where f(n) = g(n)^{1/n}, satisfy the following properties:

1. If p is a prime and a is a positive integer, then

g(p^{a}) = p^{\frac{p^{a}−1}{p−1}} and f(p^{a}) = p^{\frac{1−p^{−a}}{p−1}} .

2. If m and n are positive integers with (m, n) = 1, then

f(mn) = f(m)f(n) (f is multiplicative).

Proof. Letting h(x) = e(x) := x in Theorem 4, we get

g(p^{a}) = g(p^{a}; e) = p^{a} ∏_{j=0}^{a−1}(p^{j})^{(p−1)p^{a−j−1}}
= p^{a}p^{(p−1)p^{a−1} ∑_{j=0}^{a−1} j(\frac{1}{p})^{j}}
= p^{a}p^{(p−1)p^{a−1} \frac{(a−1)/p^{a}−a/p^{a−1}+1}{p(1−1/p)^{2}}}
= p^{a}p^{(p−1) \frac{a−1−ap+p^{a}}{(p−1)^{2}}}
= p^{a+ \frac{a−1−ap+p^{a}}{p−1}} = p^{\frac{p^{a}−1}{p−1}} .

The result for f(p^{a}) is now immediate.

Corollary 3. (Evaluations of f(n) and g(n).) If n = ∏_{i=1}^{k} p_{i}^{a_{i}} is the prime factorization of n, then

f(n) = ∏_{i=1}^{k} pi^{\frac{1−p{−a_{i} \atop i}}{p_{i}−1}} and g(n) = [∏_{i=1}^{k} pi^{\frac{1−p{−a_{i} \atop i}}{p_{i}−1}} ]^{n} .

3. Identities involving ϕ(n)

Here we will give identities that relate g(n; h) to the function ϕ(n). Not only are these identities interesting in their own right, but they will be essential to our derivation of Dirichlet series.

For a positive integer k, the Euler ϕ-function, ϕ(k), is defined to be the number of integers j with 1 ≤ j ≤ n such that (j, k) = 1. For a divisor e of n, we have (j, n) = e if and only if e|j and (\frac{j}{e}, \frac{n}{e}) = 1. Thus, the number of integers j with 1 ≤ j ≤ n such that (j, n) = e, is given by the formula ϕ(n/e). Using this basic observation we can evaluate the function g(n; h) in terms of ϕ(d), where d ranges over the divisors of n, as follows:

g(n; h) = ∏_{j=1}^{n} h((j, n)) = ∏_{e|n} h(e)^{ϕ(n/e)} = ∏_{d|n} h(n/d)^{ϕ(d)} .

Taking the logarithm of these equations yields the identity below.

Theorem 5. If n is a positive integer, then

log[g(n; h)] = ∑_{e|n} ϕ(n/e) log[h(e)] = ∑_{d|n} ϕ(d) log[h(n/d)].

For h(x) := x, we can conclude a little more.

Theorem 6. If n is a positive integer, then g(n) = n^{n} ∏_{d|n} \frac{1}{d^{ϕ(d)}} .

Proof. Using the relationship from Theorem 5 and the property ∑_{d|n} ϕ(d) = n, we have

g(n) = ∏_{d|n} (\frac{n}{d})^{ϕ(d)} = n^{∑_{d|n} ϕ(d)} ∏_{d|n} \frac{1}{d^{ϕ(d)}} = n^{n} ∏_{d|n} \frac{1}{d^{ϕ(d)}} .

4. Dirichlet Series

Define the Dirichlet series for log[g(n; h)] by

G(s; h) = ∑_{n=1}^{∞} \frac{log[g(n; h)]}{n^{s}} = ∑_{n=1}^{∞} \frac{∑_{j=1}^{n} log[h((j, n))]}{n^{s}}

for s ∈ A_{h}, where A_{h} ⊆ ℂ is the set of values for which the sum converges depending on h. Now we give the evaluation of G(s; h) in terms of the Reimann zeta function and the series ∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}}.

Before we proceed, we give a brief discussion of convergence of the series ∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}}. For a given function, h(x), we define the set S_{h} and the constant c_{h} by

S_{h} = {α ∈ ℝ| log[h(n)] = O(n^{α}) as n → ∞} and c_{h} = max{2, 1 + inf S_{h}},

where ‘inf’ denotes the greatest lower bound. We restrict our attention to those functions h(x) such that S_{h} is non-empty. The 2 in the maximum part of the definition of c_{h} is required so that \frac{ζ(s−1)}{ζ(s)} converges as a sum (this expression is important in the following theorems).

Theorem 7. The Dirichlet series for G(s; h) converges for Re(s) > c_{h} and is given by

(\frac{ζ(s − 1)}{ζ(s)}) (∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}}) ,

where ζ(s) is the Riemann zeta function.

Proof. From Theorem 5,

log[g(n; h)] = ∑_{d|n} ϕ(d) log[h(n/d)] = (ϕ ∗ (log ∘ h))(n),

where the product ∗ is the Dirichlet convolution.

Hence, given the required convergence, we have

G(s; h) = ∑_{n=1}^{∞} \frac{log[g(n;h)]}{n^{s}}
= (∑_{n=1}^{∞} \frac{ϕ(n)}{n^{s}}) (∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}})
= (\frac{ζ(s−1)}{ζ(s)}) (∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}}) .

Observe that definition of c_{h} is necessary to ensure convergence for the sum ∑_{n=1}^{∞} \frac{ϕ(n)}{n^{s}} = \frac{ζ(s−1)}{ζ(s)} and the sum ∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}}.

For the following discussion, we define the class of functions h^{(α)}(x) = x^{α}. Considering the two special cases G(s; h^{(α)}) and G(s; exp ∘ h), respectively, we immediately conclude

∑_{n=1}^{∞} \frac{∑_{j=1}^{n} log[(j, n)^{α}]}{n^{s}} = −\frac{αζ(s − 1)ζ′(s)}{ζ(s)} for s > 2 and  (1)

∑_{n=1}^{∞} \frac{∑_{j=1}^{n} h((j, n))}{n^{s}} = \frac{ζ(s − 1)}{ζ(s)} (∑_{n=1}^{∞} \frac{h(n)}{n^{s}}) for s > c_{exp(h(x))}.  (2)

Using (1) and (2), we can obtain a multitude of intriguing identities. We collect several such results in the following corollary.

Corollary 4. The following relationships hold for all α, β ∈ ℝ:

(i) ∑_{n=1}^{∞} \frac{∑_{j=1}^{n}(j, n)^{α}}{n^{s}} = \frac{ζ(s − 1)ζ(s − α)}{ζ(s)} for Re(s) > max\{2, α + 1\}.

(ii) \begin{matrix}∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n} h((j,n))}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{h(n)}{n^{s}} \end{matrix} = \frac{ζ(s − 1)}{ζ(s)} for Re(s) > c_{exp(h(x))}.

(iii) \begin{matrix}∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n} h_{1}((j,n))}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n} h_{2}((j,n))}{n^{s}} \end{matrix} = \begin{matrix}∑ & {∞ \atop n=1} & \frac{h_{1}(n)}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{h_{2}(n)}{n^{s}} \end{matrix} for Re(s) > max\{c_{exp(h_{1}(x))}, c_{exp(h_{2}(x))}\}.

(iv) \begin{matrix}∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n}(j,n)^{α}}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n}(j,n)^{β}}{n^{s}} \end{matrix} = \frac{ζ(s − α)}{ζ(s − β)} for Re(s) > max\{2, α + 1, β + 1\}.

(v) ∑_{n=1}^{∞} \frac{∑_{j=1}^{n} ϕ((j, n))}{n^{s}} = \frac{ζ^{2}(s − 1)}{ζ^{2}(s)} for Re(s) > 2.

Proof. Identity (i) is equation (2) with h^{(α)}(x) = x^{α}. Identity (ii) is a restatement of Theorem 7. Setting up two equations of the form in equation (2) with h_{1}(x) and h_{2}(x), and then dividing the equations, yields identity (iii). Identity (iv) is a special case of (iii), with h_{1}(x) = x^{α} and h_{2}(x) = x^{β}. Finally, letting h_{1}(x) = ϕ(x) in equation (2) and using the well-known identity ∑_{n=1}^{∞} \frac{ϕ(n)}{n^{s}} = \frac{ζ(s−1)}{ζ(s)}, we get identity (v).

Note that identities (ii) and (iv) suggest possible ways to evaluate the zeta function. For

example, if we could choose a function h(x) in such a way that ^{\begin{matrix}∑ & {∞ \atop n=1} & \frac{∑{n \atop j=1} h((j,n))}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{h(n)}{n^{s}} \end{matrix}} could be

evaluated in closed form, then we would have an evaluation for \frac{ζ(s−1)}{ζ(s)}. That is, we would have a way to inductively evaluate the ζ(s) function at integer values. Such a solutions could give evaluations for ζ(3), ζ(5), etc.

Since we have closed form evaluations for ζ(2k) when k is a positive integer, we can give evaluations for certain ratios of the form in identity (iv). For example, with s = 8, α = 2, and β = 4 we have:

\begin{matrix}∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n}(j,n)^{2}}{n^{8}} \\ ∑ & {∞ \atop n=1} & \frac{∑_{j=1}^{n}(j,n)^{4}}{n^{8}} \end{matrix} = \frac{ζ(6)}{ζ(4)} = \frac{2π^{2}}{21} .

We can use the results of Theorem 7 and Corollary 4 to give identities involving infinite series of zeta function values.

Theorem 8. If h(x) is a function such that log(h(x)) admits an infinite series representation log[h(x)] = ∑_{k=1}^{∞} a_{k} (\frac{1}{x})^{k} that converges uniformly for x ≥ 1 and for Re(s) > c_{h}, we have

∑_{n=1}^{∞} \frac{∑_{j=1}^{n} log[h((j, n))]}{n^{s}} = (\frac{ζ(s − 1)}{ζ(s)}) (∑_{k=1}^{∞} a_{k}ζ(s + k)) .

Proof. Using the infinite series expansions, we have

∑_{n=1}^{∞} \frac{∑_{j=1}^{n} log[h((j, n))]}{n^{s}} = (\frac{ζ(s − 1)}{ζ(s)}) (∑_{n=1}^{∞} \frac{log[h(n)]}{n^{s}})

= (\frac{ζ(s − 1)}{ζ(s)}) (∑_{n=1}^{∞} \frac{∑_{k=1}^{∞} a_{k} (\frac{1}{n})^{k}}{n^{s}} ) = (\frac{ζ(s − 1)}{ζ(s)}) (∑_{k=1}^{∞} a_{k} ∑_{n=1}^{∞} \frac{1}{n^{s+k}} )

= (\frac{ζ(s − 1)}{ζ(s)}) (∑_{k=1}^{∞} a_{k}ζ(s + k)) .

Corollary 5. If Re(s) > 2, then

− ∑_{n=1}^{∞} \frac{∑_{j=1}^{n} log[1 − \frac{1}{2(j,n)}]}{n^{s}} = (\frac{ζ(s − 1)}{ζ(s)}) (∑_{k=1}^{∞} \frac{ζ(s + k)}{2^{k}k}) .

Proof. Apply Theorem 8 with h(x) = \frac{1}{1− \frac{1}{2x}}, so that log[h(x)] = − log(1−\frac{1}{2x}) = ∑_{k=1}^{∞} \frac{1}{k} (\frac{1}{2x})^{k} =

∑_{k=1}^{∞} \frac{1}{2^{k}k} (\frac{1}{x})^{k} for x > 1/2, and a_{k} = \frac{1}{2^{k}k}.

Now we give asymptotic formulas for ∑_{n≤x} log[g(n; h)]. For the following development, we only consider the case h(n) = O(n^{α}) for n sufficiently large and α a fixed non-negative real number. Including a larger class of functions would considerably increase the length of this study. We first need a standard estimate from analytic number theory. Tenenbaum [7] gives the following estimate in his book:

Φ_{0}(x) := ∑_{n≤x} ϕ(n) = \frac{x^{2}}{2ζ(2)} + O(x log(x)).

We also need the following lemma.

Lemma 1. If x and y are real numbers such that x ≥ y > 1, then

log (\frac{x}{y}) < \frac{log(x)}{log(y)} .

Proof. Fix x > 1 and consider the function a_{x}(y) = \frac{log(x)}{log(y)} − log(\frac{x}{y}) on the domain (1, x]. Taking the derivative with respect to y gives

a′_{x}(y) = −\frac{log(x)}{y log^{2}(y)} − \frac{1}{y} = −\frac{1}{y} [\frac{1}{log^{2}(y)} + 1] .

Thus, a_{x}(y) is monotonically decreasing on the domain. If y = x, then the a_{x}(x) = \frac{log(x)}{log(x)} − log(\frac{x}{x}) = 1. Hence a_{x}(y) ≥ 1 for all y ∈ (1, x]. Since x was arbitrary, the result holds.

Theorem 9. If h(x) satisfies the relationship h(n) = O(n^{α}) for n sufficiently large and α a fixed non-negative real number, then the following asymptotic relationship holds

∑_{n≤x} log[g(n; h)] = \frac{H_{h}}{2ζ(2)}x^{2} + O(x log^{2}(x)) for x sufficiently large,

where H_{h} = ∑_{k=1}^{∞} \frac{log[h(k)]}{k^{2}}.

Proof. From the well-known bound, we have Φ_{0}(x) ≤ \frac{x^{2}}{2ζ(2)} + cx log(x) for some positive constant c and x sufficiently large.

Therefore, using Theorem 6 and Lemma 1, we have

∑_{n≤x} log[g(n; h)] = ∑_{n≤x} ∑_{d|n} log[h(d)]ϕ(n/d)
≤ ∑_{d≤x} log[h(d)]Φ_{0}(x/d)
≤ ∑_{d≤x} log[h(d)] [\frac{x^{2}/d^{2}}{2ζ(2)} ] + ∑_{d≤x} log[h(d)][cx/d log(x/d)]
≤ [\frac{x^{2}}{2ζ(2)} ∑_{d≤x} \frac{log[h(d)]}{d^{2}}] + cx log(x) ∑_{d≤x} \frac{log[h(d)]}{d log(d)}
≤ [\frac{x^{2}}{2ζ(2)} ∑_{d≤x} \frac{log[h(d)]}{d^{2}}] + O(x log(x) ∑_{d≤x} \frac{α log(d)}{d log(d)})
= \frac{H_{h}}{2ζ(2)}x^{2} + O(x log^{2}(x)) .

Corollary 6. If h(x) satisfies the relationship h(n) = O(n^{α}) for n sufficiently large and α a fixed non-negative real number, then the following asymptotic relationship holds

∏_{n≤x} g(n; h) = O(x^{x log(x)})e^{\frac{H_{h}}{2ζ(2)} x^{2}} for x sufficiently large,

where H_{h} = ∑_{k=1}^{∞} \frac{log[h(k)]}{k^{2}}.

5. The Special Case g(n)

In this section, we focus only on the expression g(n) = ∏_{j=1}^{n}(j, n) and its multiplicative counterpart f(n) = g(n)^{1/n}. First, we give some bounds.

For positive integers x_{1}, x_{2}, …, x_{n}, we have the well-known arithmetic-geometric mean inequality (x_{1}x_{2} ⋯ x_{n})^{1/n} ≤ \frac{x_{1}+x_{2}+···+x_{n}}{n}. In terms of our function f, we have f(n) =

(∏_{j=1}^{n}(j, n))^{1/n} ≤ ^{\frac{∑_{j=1}^{n}(j,n)}{n}}.

Theorem 10. The function f satisfies the inequalities

max(n^{1/υ(n)}, n^{τ(n)/(2n)}) ≤ f(n) ≤ 27 (\frac{log(n)}{ω(n)})^{ω(n)} ,

where n is any positive integer, ω(n) is the number of distinct prime divisors of n, τ(n) is the number of divisors of n, and υ(n) is the largest prime power divisor of n.

Proof. The upper bound is a direct application of the arithmetic-geometric mean and Theorem 3.1 of Broughan [2]. For the first part of the lower bound, we first note that \frac{1−p^{−a}}{p−1} = \frac{p^{a}−1}{p^{a}(p−1)} > \frac{1}{p^{a}} (p^{a−1} + p^{a−2} + ⋯ + p + 1) ≥ \frac{a}{p^{a}}. Thus, we have

f(n) = ∏_{p^{a}||n} p^{\frac{1−p^{−a}}{p−1}} ≥ ∏_{p^{a}||n} p^{a/p^{a}} ≥ ∏_{p^{a}||n} p^{a/υ(n)} = n^{1/υ(n)}.

For the second part of the lower bound, note

\begin{aligned}(∏_{d|n} d)^{2} & = & (∏_{d|n} d) (∏_{e|n} e) = (∏_{d|n} d) (∏_{d|n} \frac{n}{d}) \\ & = & ∏_{d|n} d\frac{n}{d} = ∏_{d|n} n = n^{τ(n)}. \end{aligned}

So we have

f(n) = (∏_{j=1}^{n}(j, n))^{1/n} ≥ (∏_{d|n} d)^{1/n} = n^{τ(n)/(2n)}.

Corollary 7. The function g satisfies the inequalities

n ≤ max(n^{n/υ(n)}, n^{τ(n)/2}) ≤ g(n) ≤ 27 (\frac{log(n)}{ω(n)})^{nω(n)} ,

with g(n) = n if and only if n is a prime. Therefore, for all ϵ > 0, we have

log[g(n)] = O(n^{1+ϵ}) for n sufficiently large.

Proof. This corollary directly follows from previous theorems. Note that if n is composite, then ∏_{j=1}^{n}(j, n) > n since (n, n) = n and (j, n) > 1 for at least one j value less than n.

The Dirichlet series for log[g(n)] is given as a corollary of Theorem 7 with h(x) := x. So we define G(s) = ∑_{n=1}^{∞} \frac{log[g(n)]}{n^{s}}. Note that ∑_{n=1}^{∞} \frac{log[f(n)]}{n^{s}} = G(s + 1).

Corollary 8. The Dirichlet series for G(s) converges absolutely for Re(s) > 2 and is given by the formula

−\frac{ζ(s − 1)ζ′(s)}{ζ(s)} .

Proof. Taking h(x) := x in Theorem 7 yields G(s; h) = \frac{ζ(s−1)}{ζ(s)}H_{h}, where H_{h} = ∑_{n=1}^{∞} \frac{log(n)}{n^{s}} = −ζ′(s).

The asymptotic development is similar to the general case ∑_{n≤x} log[g(n)]. However, we can do a little more in the case of log[f(n)]. Along with the estimate for Φ_{0}(x) := ∑_{n≤x} ϕ(n) = \frac{x^{2}}{2ζ(2)} + O(x log(x)), we will also need the estimate Φ_{1}(x) := ∑_{n≤x} \frac{ϕ(n)}{n} = \frac{x}{ζ(2)} + O(log(x)).

Theorem 11. The following asymptotic relationships hold

∑_{n≤x} log[g(n)] = −\frac{ζ′(2)}{2ζ(2)}x^{2} + O(x log^{2}(x)) for x sufficiently large, and
∑_{n≤x} log[f(n)] = −\frac{ζ′(2)}{ζ(2)}x + O(log^{2}(x)) for x sufficiently large.

Proof. Using Theorem 9, we have H_{x} = ∑_{k=1}^{∞} \frac{log(k)}{k^{2}} = −ζ′(2). For f(n) = g(n)^{1/n}, we note that log[f(n)] = \frac{1}{n} ∑_{d|n} ϕ(n/d) log(d) = ∑_{d|n} \frac{ϕ(n/d)}{n/d} \frac{log(d)}{d}.

Therefore, for x sufficiently large and some constant c, the known bounds give

∑_{n≤x} log[f(n)] = ∑_{n≤x} ∑_{d|n} \frac{log(d)}{d} \frac{ϕ(n/d)}{n/d}
≤ ∑_{d≤x} \frac{log(d)}{d} [\frac{x/d}{ζ(2)}] + ∑_{d≤x} \frac{log(d)}{d}[c log(x/d)]
≤ [\frac{x}{ζ(2)} ∑_{d≤x} \frac{log(d)}{d^{2}}] + c log(x) ∑_{d≤x} \frac{1}{d}
= [\frac{x}{ζ(2)} ∑_{d≤x} \frac{log(d)}{d^{2}}] + O(log^{2}(x)) .

Corollary 9. The following asymptotic relationships hold

∏_{n≤x} g(n) = O(x^{x log(x)})e^{− \frac{ζ′(2)}{2ζ(2)} x^{2}} for x sufficiently large, and
∏_{n≤x} f(n) = O(x^{log(x)})e^{− \frac{ζ′(2)}{ζ(2)} x} for x sufficiently large.

6. Conclusion

We hope that the function g(n; h) will be a useful tool in the study of lattice points and solutions to equations in finite fields. The author was intrigued by the fact that the ratio \begin{matrix}∑ & {∞ \atop n=1} & \frac{h((j,n))}{n^{s}} \\ ∑ & {∞ \atop n=1} & \frac{h(n)}{n^{s}} \end{matrix} is always the same as the ratio \frac{ζ(s−1)}{ζ(s)}. Hopefully this identity, along with the others of this study, will be useful in the theory of the Riemann zeta function.

The function g(n; h) seems to be worthy of study, not only because of its connections with known concepts in number theory, but also for the elegance of the formulas and identities in which it appears.

Acknowledgements

My thanks to the reviewer of this article whose suggestions and comments greatly improved the clarity of this exposition.

References

[1] R. Baillie, S.S. Wagstaff, Jr., Lucas Pseudoprimes, Math. Comp. 35 (1980), 152, 1391-1417.

[2] K.A. Broughan, The gcd-sum function, Journal of Integer Sequences, Vol. 4 (2001), Article 01.2.2.

[3] E. Cohen, Arithmetical functions of greatest common divisor. I., Proc. Amer. Math. Soc. 11 (1960).

[4] E. Cohen, Arithmetical functions of greatest common divisor. II, An alternative approach., Boll. Un. Mat. Ital. (3) 17, (1962), 329-356.

[5] E. Cohen, Arithmetical functions of greatest common divisor. III. Cesáro’s divisor problem, Proc. Glasgow Math. Assoc. 5 (1961), 67-75.

[6] A.D. Loveless, A Compositeness Test that Never Fails for Carmichael Numbers, Math. of Comp., preprint.

[7] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Great Britain: Cambridge University Press, 1995.