On the Asymptotic Density of k-tuples of Positive Integers with

Pairwise Non-Coprime Components

László Tóth Department of Mathematics University of Pécs Ifjúság útja 6 7624 Pécs Hungary

                ltoth@gamma.ttk.pte.hu

Abstract

We use the convolution method for arithmetic functions of several variables to deduce an asymptotic formula for the number of k-tuples of positive integers with components which are pairwise non-coprime and ≤ x. More generally, we obtain asymptotic formulas on the number of k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} such that at least r pairs (n_{i}, n_{j}), respectively exactly r pairs are coprime. Our results answer the questions raised by Moree (2005, 2014), and generalize and refine related results obtained by Heyman (2014) and Hu (2014).

1 Introduction and motivation

Let ℕ = {1, 2, …} and let k ∈ ℕ, k ≥ 2. It is well-known that the asymptotic density of the ktuples (n_{1}, …, n_{k}) ∈ ℕ^{k} having relatively prime (coprime) components is 1/ζ(k). This result goes back to the work of Cesàro, Dirichlet, Mertens and others. See, e.g., [4, 6, 12, 14, 15]. More exactly, one has the asymptotic estimate

∑_{\begin{matrix}n_{1},...,n_{k}≤x \\ gcd(n_{1},...,n_{k})=1 \end{matrix}} 1 = \frac{x^{k}}{ζ(k)} + \begin{cases}O(x log x), & if k = 2; \\ O(x^{k−1}), & if k ≥ 3. \end{cases}  (1)

The asymptotic density of the k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} with pairwise coprime components is

A_{k} = ∏_{p} (1 − \frac{1}{p})^{k−1} (1 + \frac{k − 1}{p}) = ∏_{p} (1 + ∑_{j=2}^{k}(−1)^{j−1}(j − 1)\binom{k}{j}\frac{1}{p^{j}} ) ,  (2)

and we have the asymptotic formula

∑_{\begin{matrix}n_{1},...,n_{k}≤x \\ gcd(n_{i},n_{j})=1 \\ 1≤i<j≤k \end{matrix}} 1 = A_{k}x^{k} + O(x^{k−1}(log x)^{k−1}),  (3)

valid for every fixed k ≥ 2, proved by the author [15] using an inductive process on k. The value of A_{k} was also deduced by Cai and Bach [3, Thm. 3.3] using probabilistic arguments. Formula (3) has been reproved by the author [17], in a more general form, namely by investigating m-wise relatively prime integers (that is, every m of them are relatively prime) and by using the convolution method for functions of several variables. Note that the asymptotic formula for m-wise coprime integers was first proved by Hu [8] by the inductive method with a weaker error term.

Now consider pairwise non-coprime positive integers n_{1}, …, n_{k}, satisfying gcd(n_{i}, n_{j}) ≠ 1 for all 1 ≤ i < j ≤ k. Let β = β_{k} : ℕ^{k} → {0, 1} denote the characteristic function of k-tuples having this property, that is,

β(n_{1}, …, n_{k}) = \begin{cases}1, & if n_{1}, …, n_{k} are pairwise non-coprime; \\ 0, & otherwise. \end{cases}  (4)

Moree [10, 11] and Heyman [7] raised the question of finding the asymptotic density C_{k} of k-tuples with pairwise non-coprime components. If k = 2, then the answer is immediate by (1): C_{2} = 1 − 1/ζ(2). Heyman [7] obtained the value C_{3} and deduced an asymptotic formula for the sum ∑_{n_{1},n_{2},n_{3}≤x} β(n_{1}, n_{2}, n_{3}) by using functions of one variable and the inclusionexclusion principle. The method in [7] cannot be applied if k ≥ 4. Using the inductive approach of the author [15] and the inclusion-exclusion principle, Hu [9] gave a formula for the asymptotic density C_{k} (k ≥ 3), with an incomplete proof.

Moree [10, 11] also formulated as an open problem to compute the density of k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} such that at least (respectively, exactly) r pairs (n_{i}, n_{j}) are coprime. A correct answer to this problem, but with some incomplete arguments has been given by Hu [9, Cor. 3]. In fact, Hu [9, Thm. 1] also deduced a related asymptotic formula with remainder term concerning certain arbitrary coprimality conditions. See Theorem 1. Arias de Reyna and Heyman [2] used a different method, based on certain properties of arithmetic functions of one variable, and improved the error term by Hu [9].

See Sections 2 and 4 for some more details on the above results.

In this paper we use a different approach to study these questions. Applying the convolution method for functions of several variables we first reprove Theorem 1. To do this we need a careful study of the Dirichlet series of the corresponding characteristic function. See Theorem 7. Our result concerning the related asymptotic formula, with the same error term as obtained in [2], and with new representations of the constant A_{G} is contained in Theorem 9. Then we deduce asymptotic formulas with remainder terms on the number of k-tuples such that at least r pairs (n_{i}, n_{j}), respectively exactly r pairs are coprime. See Theorem 11. In particular, we obtain an asymptotic formula for the function β = β_{k}, for every k ≥ 2. See Corollary 12. Our results generalize and refine those by Heyman [7] and Hu [9].

Basic properties of arithmetic functions of k variables are presented in Section 3.1. Some lemmas related to the principle of inclusion-exclusion, used in the proofs are included in Section 3.2. The proofs of our main results are similar to those in [17], and are given in Section 5. Some numerical examples are presented in Section 6.

2 Previous results

Heyman [7] proved the asymptotic formula

∑_{n_{1},n_{2},n_{3}≤x} β(n_{1}, n_{2}, n_{3}) = C_{3}x^{3} + O(x^{2}(log x)^{2}),

where the constant C_{3} is

C_{3} = 1 − 3 ∏_{p} (1 − \frac{1}{p^{2}} ) + 3 ∏_{p} (1 − \frac{2}{p^{2}} + \frac{1}{p^{3}} ) − ∏_{p} (1 − \frac{3}{p^{2}} + \frac{2}{p^{3}} ) .  (5)

Hu [9] gave a formula for the asymptotic density C_{k} of k-tuples with pairwise non-coprime components, where k ≥ 3. See (25). It recovers (5) for k = 3, and for k = 4 it can be written as

C_{4} = 1 − 6 ∏_{p} (1 − \frac{1}{p^{2}} ) + 3 ∏_{p} (1 − \frac{1}{p^{2}} )^{2} + 12 ∏_{p} (1 − \frac{2}{p^{2}} + \frac{1}{p^{3}} )  (6)

− 4 ∏_{p} (1 − \frac{3}{p^{2}} + \frac{3}{p^{3}} − \frac{1}{p^{4}} ) − 16 ∏_{p} (1 − \frac{3}{p^{2}} + \frac{2}{p^{3}} )

+ 15 ∏_{p} (1 − \frac{4}{p^{2}} + \frac{4}{p^{3}} − \frac{1}{p^{4}} ) − 6 ∏_{p} (1 − \frac{5}{p^{2}} + \frac{6}{p^{3}} − \frac{2}{p^{4}} )

+ ∏_{p} (1 − \frac{6}{p^{2}} + \frac{8}{p^{3}} − \frac{3}{p^{4}} ) .

Related to identity (6) we note that there are two typos in [9], namely ∏_{p}(1 − 1/p)^{2}(1 − 2/p) on pages 7 and 8 should be ∏_{p}(1 − 1/p)^{2}(1 + 2/p).

For a fixed k ≥ 2 let V = {1, 2, …, k}, let E be an arbitrary subset of the set {(i, j) : 1 ≤ i < j ≤ k}, and let take the coprimality conditions gcd(n_{i}, n_{j}) = 1 for (i, j) ∈ E.

Following Hu [9] and Arias de Reyna and Heyman [2], it is convenient and suggestive to consider the corresponding simple graph G = (V, E), we call it coprimality graph, with set of vertices V and set of edges E. Therefore, we use the notation E ⊆ V^{(2)} := {{i, j} : 1 ≤ i < j ≤ k}, where the edges of G are denoted by {i, j} = {j, i}, and adopt some related graph terminology.

Let δ_{G} denote the characteristic function attached to the graph G, defined by

δ_{G}(n_{1}, …, n_{k}) = \begin{cases}1, & if gcd(n_{i}, n_{j}) = 1 for every \{i, j\} ∈ E; \\ 0, & otherwise, \end{cases}  (7)

and note that if E = ∅, that is, the graph G has no edges, then δ_{G}(n_{1}, …, n_{k}) = 1 for every (n_{1}, …, n_{k}) ∈ ℕ^{k}.

Furthermore, let i_{m}(G) be the number of independent sets S of vertices in G (i.e., no two vertices of S are adjacent in G) of cardinality m. Also, for F ⊆ E let v(F) denote the number of distinct vertices appearing in F.

Theorem 1. Let G = (V, E) be an arbitrary graph. With the above notation,

∑_{n_{1},...,n_{k}≤x} δ_{G}(n_{1}, …, n_{k}) = A_{G}x^{k} + O(x^{k−1}(log x)^{ϑ_{G}}),  (8)

where the constant A_{G} is given by

A_{G} = ∏_{p} (∑_{m=0}^{k} \frac{i_{m}(G)}{p^{m}} (1 − \frac{1}{p})^{k−m})  (9)

= ∏_{p} (∑_{F ⊆E} \frac{(−1)^{|F |}}{p^{v(F)}} ) ,  (10)

and ϑ_{G} = d_{G} := max_{j∈V} deg(j), denoting the maximum degree of the vertices of G.

Here A_{G} is representing the asymptotic density of k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} such that gcd(n_{i}, n_{j}) = 1 for {i, j} ∈ E. Theorem 1 was first proved by Hu [9] with the weaker exponent ϑ_{G} = k − 1 for every subset E and with identity (9) for the constant A_{G}. Arias de Reyna and Heyman [2] deduced Theorem 1 by a different method, with the given exponent ϑ_{G} = d_{G} and identity (10) for the constant A_{G}.

Note that if we have the complete coprimality graph, namely if E = V^{(2)}, then δ_{G} is the characteristic function of the set of k-tuples with pairwise coprime components (see (12)), and (8) recovers formula (3).

3 Preliminaries

3.1 Arithmetic functions of k variables

The Dirichlet convolution of the functions f, g : ℕ^{k} → ℂ is defined by

(f ∗ g)(n_{1}, …, n_{k}) = ∑_{d_{1}|n_{1},...,d_{k}|n_{k}} f(d_{1}, …, d_{k})g(n_{1}/d_{1}, …, n_{k}/d_{k}).  (11)

Let μ = μ_{k} : ℕ^{k} → {−1, 0, 1} denote the Möbius function of k variables, defined as the inverse of the constant 1 function under the convolution (11). We have μ(n_{1}, …, n_{k}) = μ(n_{1}) ⋯ μ(n_{k}) for every n_{1}, …, n_{k} ∈ ℕ, which recovers for k = 1 the classical (one variable) Möbius function.

The Dirichlet series of a function f : ℕ^{k} → ℂ is given by

D(f; s_{1}, …, s_{k}) := ∑_{n_{1},...,n_{k}=1}^{∞} \frac{f(n_{1}, …, n_{k})}{n_{1}^{s_{1}} ⋯ n_{k}^{s_{k}}}.

If D(f; s_{1}, …, s_{k}) and D(g; s_{1}, …, s_{k}) are absolutely convergent, where s_{1}, …, s_{k} ∈ ℂ, then D(f ∗ g; s_{1}, …, s_{k}) is also absolutely convergent and

D(f ∗ g; s_{1}, …, s_{k}) = D(f; s_{1}, …, s_{k})D(g; s_{1}, …, s_{k}).

We recall that a nonzero arithmetic function of k variables f : ℕ^{k} → ℂ is said to be multiplicative if

f(m_{1}n_{1}, …, m_{k}n_{k}) = f(m_{1}, …, m_{k})f(n_{1}, …, n_{k})

holds for all m_{1}, n_{1} …, m_{k}, n_{k} ∈ ℕ such that gcd(m_{1} ⋯ m_{k}, n_{1} ⋯ n_{k}) = 1. If f is multiplicative, then it is determined by the values f(p^{ν_{1}}, …, p^{ν_{k}}), where p is prime and ν_{1}, …, ν_{k} ∈ ℕ ∪ {0}. More exactly, f(1, …, 1) = 1 and for all n_{1}, …, n_{k} ∈ ℕ,

f(n_{1}, …, n_{k}) = ∏_{p} f(p^{ν_{p}(n_{1})}, …, p^{ν_{p}(n_{k})}),

where we use the notation n = ∏_{p} p^{ν_{p}(n)} for the prime power factorization of n ∈ ℕ, the product being over the primes p and all but a finite number of the exponents ν_{p}(n) are zero. Examples of multiplicative functions of k variables are the GCD and LCM functions gcd(n_{1}, …, n_{k}), lcm(n_{1}, …, n_{k}) and the characteristic functions

ϱ(n_{1}, …, n_{k}) = \begin{cases}1, & if gcd(n_{1}, …, n_{k}) = 1; \\ 0, & otherwise, \end{cases}

ϑ(n_{1}, …, n_{k}) = \begin{cases}1, & if gcd(n_{i}, n_{j}) = 1 for every 1 ≤ i < j ≤ k; \\ 0, & otherwise. \end{cases}  (12)

If the function f is multiplicative, then its Dirichlet series can be expanded into a (formal) Euler product, that is,

D(f; s_{1}, …, s_{k}) = ∏_{p} ∑_{ν_{1},...,ν_{k}=0}^{∞} \frac{f(p^{ν_{1}}, …, p^{ν_{k}})}{p^{ν_{1}s_{1}+···+ν_{k}s_{k}}},  (13)

the product being over the primes p. More exactly, for f multiplicative, the series D(f; s_{1}, …, s_{k}) with s_{1}, …, s_{k} ∈ ℂ is absolutely convergent if and only if

∑_{p} ∑_{\begin{matrix}ν_{1},...,ν_{k}=0 \\ ν_{1}+···+ν_{k}≥1 \end{matrix}}^{∞} \frac{|f(p^{ν_{1}}, …, p^{ν_{k}})|}{p^{ν_{1}ℜs_{1}+···+ν_{k}ℜs_{k}}} < ∞

and in this case equality (13) holds.

The mean value of a function f : ℕ^{k} → ℂ is

M(f) := lim_{x_{1},...,x_{k}→∞} \frac{1}{x_{1} ⋯ x_{k}} ∑_{n_{1}≤x_{1},...,n_{k}≤x_{k}} f(n_{1}, …, n_{k}),

provided that this limit exists. As a generalization of Wintner’s theorem (valid in the one variable case), Ushiroya [18, Thm. 1] proved the next result.

Theorem 2. If f is a function of k variables, not necessary multiplicative, such that

∑_{n_{1},...,n_{k}=1}^{∞} \frac{|(μ ∗ f)(n_{1}, …, n_{k})|}{n_{1} ⋯ n_{k}} < ∞,

then the mean value M(f) exists, and

M(f) = ∑_{n_{1},...,n_{k}=1}^{∞} \frac{(μ ∗ f)(n_{1}, …, n_{k})}{n_{1} ⋯ n_{k}}.

For multiplicative functions the above result can be formulated as follows. See [16, Prop. 19], [18, Thm. 4].

Theorem 3. Let f : ℕ^{k} → ℂ be a multiplicative function. Assume that

∑_{p} ∑_{\begin{matrix}ν_{1},...,ν_{k}=0 \\ ν_{1}+···+ν_{k}≥1 \end{matrix}}^{∞} \frac{|(μ ∗ f)(p^{ν_{1}}, …, p^{ν_{k}})|}{p^{ν_{1}+···+ν_{k}}} < ∞.

Then the mean value M(f) exists, and

M(f) = ∏_{p} (1 − \frac{1}{p})^{k} ∑_{ν_{1},...,ν_{k}=0}^{∞} \frac{f(p^{ν_{1}}, …, p^{ν_{k}})}{p^{ν_{1}+···+ν_{k}}}.

See, e.g., Delange [5] and the survey by the author [16] for these and some other related results on arithmetic functions of several variables. If k = 1, i.e., in the case of functions of a single variable we recover some familiar properties.

3.2 The functions δ_{G} and β

Consider the function δ_{G} defined by (7).

Lemma 4. For every subset E, the function δ_{G} is multiplicative.

Proof. This is a consequence of the fact that the gcd function gcd(m, n) is multiplicative, viewed as a function of two variables. To give a direct proof, let m_{1}, n_{1}, …, m_{k}, n_{k} ∈ ℕ such that gcd(m_{1} ⋯ m_{k}, n_{1} ⋯ n_{k}) = 1. Then we have

δ_{G}(m_{1}n_{1}, …, m_{k}n_{k}) = \begin{cases}1, & if gcd(m_{i}n_{i}, m_{j}n_{j}) = 1 for all \{i, j\} ∈ E; \\ 0, & otherwise; \end{cases}

= \begin{cases}1, & if gcd(m_{i}, m_{j}) gcd(n_{i}, n_{j}) = 1 for all \{i, j\} ∈ E; \\ 0, & otherwise; \end{cases}

= \begin{cases}1, & if gcd(m_{i}, m_{j}) = 1 for all \{i, j\} ∈ E; \\ 0, & otherwise; \end{cases}

× \begin{cases}1, & if gcd(n_{i}, n_{j}) = 1 for all \{i, j\} ∈ E; \\ 0, & otherwise; \end{cases}

= δ_{G}(m_{1}, …, m_{k})δ_{G}(n_{1}, …, n_{k}),

finishing the proof.

The function β given by (4) is not multiplicative. However, by the inclusion-exclusion principle it can be written as an alternating sum of certain multiplicative functions δ_{G}.

More generally, for r ≥ 0 we define the functions β_{r} = β_{k,r} and β′_{r} = β′_{k,r} by

β_{r}(n_{1}, …, n_{k}) = \begin{cases}1, & if exactly r pairs (n_{i}, n_{j}) with 1 ≤ i < j ≤ k are coprime; \\ 0, & otherwise, \end{cases} (14)

β′_{r}(n_{1}, …, n_{k}) = \begin{cases}1, & if at least r pairs (n_{i}, n_{j}) with 1 ≤ i < j ≤ k are coprime; \\ 0, & otherwise. \end{cases} (15)

If r = 0, then β_{0} = β.

Lemma 5. Let k ≥ 2 and r ≥ 0. For every n_{1}, …, n_{k} ∈ ℕ,

β_{r}(n_{1}, …, n_{k}) = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j}{r} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} δ_{G}(n_{1}, …, n_{k}),  (16)

β(n_{1}, …, n_{k}) = ∑_{j=0}^{k(k−1)/2}(−1)^{j} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} δ_{G}(n_{1}, …, n_{k}).  (17)

Proof. Given n_{1}, …, n_{k} ∈ ℕ, assume that for 1 ≤ i < j ≤ k condition gcd(n_{i}, n_{j}) = 1 holds for t times, where 0 ≤ t ≤ k(k − 1)/2. Then the right hand side of (16) is

N_{r} := ∑_{j=r}^{t}(−1)^{j−r}\binom{j}{r}\binom{t}{j}.

If t < r, then this is the empty sum, and N_{r} = 0 = β_{r}(n_{1}, …, n_{k}). If t ≥ r, then

N_{r} = \binom{t}{r} ∑_{j=r}^{t}(−1)^{j−r}\binom{t − r}{j − r} = \binom{t}{r} ∑_{m=0}^{t−r}(−1)^{m}\binom{t − r}{m} = \begin{cases}1, & if t = r; \\ 0, & if t > r, \end{cases}

which is exactly β_{r}(n_{1}, …, n_{k}).

In the case r = 0 we obtain identity (17).

Lemma 6. Let k ≥ 2 and r ≥ 1. For every n_{1}, …, n_{k} ∈ ℕ,

β′_{r}(n_{1}, …, n_{k}) = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j − 1}{r − 1} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} δ_{G}(n_{1}, …, n_{k}).  (18)

Proof. We have by using (16),

β′_{r}(n_{1}, …, n_{k}) = ∑_{t=r}^{k(k−1)/2} β_{t}(n_{1}, …, n_{k})

= ∑_{t=r}^{k(k−1)/2} ∑_{j=t}^{k(k−1)/2}(−1)^{j−t}\binom{j}{t} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} δ_{G}(n_{1}, …, n_{k})

= ∑_{j=r}^{k(k−1/2}(−1)^{j} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} δ_{G}(n_{1}, …, n_{k}) ∑_{t=r}^{j}(−1)^{t}\binom{j}{t},

where the inner sum is (−1)^{r}\binom{j−1}{r−1}, finishing the proof.

The above identities are similar to some known generalizations of the principle of inclusion-exclusion. See, e.g., the books by Aigner [1, Sect. 5.1] and Stanley [13, Ch. 2].

4 Main results

Given a graph G = (V, E), the asymptotic density A_{G} of the of k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} such that gcd(n_{i}, n_{j}) = 1 for {i, j} ∈ E is the mean value of the characteristic function δ_{G} defined by (7). According to Theorem 2, A_{G} = D(μ∗δ_{G}, 1, …, 1), provided that this series is absolutely convergent. We show this by a careful study of the Dirichlet series of the function δ_{G}.

To formulate our results we need the following additional notation. For a graph G = (V, E) let I be the set of non-isolated vertices of G, and J be a (minimum) vertex cover of G, that is, a set of vertices that includes at least one endpoint of every edge (of smallest possible size). The notation ∑L⊆J^{′} means the sum over independent subsets L of J (no two vertices of L are adjacent in G). Also, let N(j) denote the neighbourhood of a vertex j, and for a subset L of V let N(L) = ∪_{j∈L}N(j).

Theorem 7. Let k ≥ 2 and G = (V, E) be an arbitrary graph. Then, with the above notation,

∑_{n_{1},...,n_{k}=1}^{∞} \frac{δ_{G}(n_{1}, …, n_{k})}{n_{1}^{s_{1}} ⋯ n_{k}^{s_{k}}} = ζ(s_{1}) ⋯ ζ(s_{k})D′_{G}(s_{1}, …, s_{k}),

where

D′_{G}(s_{1}, …, s_{k}) = ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} ∏_{i∈(J\L)∪(N(L)\J)} (1 − \frac{1}{p^{s_{i}}} ) )  (19)

= ∏_{p} (1 − ∑_{\{i,j\}∈E} \frac{1}{p^{s_{i}+s_{j}}} + ∑_{j=3}^{|I|} ∑_{\begin{matrix}i_{1},...,i_{j}∈I \\ i_{1}<···<i_{j} \end{matrix}} \frac{c(i_{1}, …, i_{j})}{p^{s_{i_{1}}+···+s_{i_{j}}}}),

where c(i_{1}, …, i_{j}) are some integers, depending on i_{1}, …, i_{j}, but not on p.

Furthermore, D′(s_{1}, …, s_{k}) with s_{1}, …, s_{k} ∈ ℂ is absolutely convergent provided that ℜ(s_{i_{1}} + ⋯ + s_{i_{j}}) > 1 for every i_{1}, …, i_{j} ∈ I with i_{1} < ⋯ < i_{j}, 2 ≤ j ≤ |I|.

Remark 8. By choosing J = I or J = {1, …, k} the sum over L in identity (19) has more terms than in the case of a minimum vertex cover J of G. However, if J = I, then N(L) \ I = ∅ for every L, and (19) takes the slightly simpler form

D′_{G}(s_{1}, …, s_{k}) = ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆I \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} ∏_{i∈I\L} (1 − \frac{1}{p^{s_{i}}} ) ),

and similarly if J = {1, …, k}.

Next we prove by the convolution method the asymptotic formula already given in Theorem 1. This approach leads to new representations of the constant A_{G}.

Theorem 9. Asymptotic formula (8) holds with the exponent ϑ_{G} = d_{G} in the error term, and with the constant

A_{G} = ∑_{n_{1},...,n_{k}=1}^{∞} \frac{(μ ∗ δ_{G})(n_{1}, …, n_{k})}{n_{1} ⋯ n_{k}}

= ∏_{p} (1 − \frac{1}{p})^{k} ∑_{ν_{1},...,ν_{k}=0}^{∞} \frac{δ_{G}(p^{ν_{1}}, …, p^{ν_{k}})}{p^{ν_{1}+···+ν_{k}}}

= ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} \frac{1}{p^{|L|}} (1 − \frac{1}{p})^{|J\L|+|N(L)\J|} ).  (20)

Remark 10. If J = I, then N(L) \ I = ∅ for every L, and (20) gives

A_{G} = ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆I \end{matrix} \frac{1}{p^{|L|}} (1 − \frac{1}{p})^{|I\L|} )

= ∏_{p} ( ∑_{m=0}^{|I|} \frac{i_{m}(G, I)}{p^{m}} (1 − \frac{1}{p})^{|I|−m} ),

where i_{m}(G, I) denotes the number of independent subsets of I of cardinality m in the graph G. Similarly, by choosing J = {1, …, k}, (20) reduces to identity (9) by Hu [9].

Now consider the functions β_{r} and β′_{r} defined by (14) and (15).

Theorem 11. Let k ≥ 2. Then for r ≥ 0 we have

∑_{n_{1},...,n_{k}≤x} β_{r}(n_{1}, …, n_{k}) = C_{r}x^{k} + O(x^{k−1}(log x)^{k−1}),  (21)

and for r ≥ 1,

∑_{n_{1},...,n_{k}≤x} β′_{r}(n_{1}, …, n_{k}) = C′_{r}x^{k} + O(x^{k−1}(log x)^{k−1}),  (22)

where

C_{r} = C_{k,r} = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j}{r} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} A_{G},  (23)

and

C′_{r} = C′_{k,r} = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j − 1}{r − 1} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} A_{G}  (24)

are the asymptotic densities of the k-tuples (n_{1}, …, n_{k}) ∈ ℕ^{k} such that gcd(n_{i}, n_{j}) = 1 occurs exactly r times, respectively at least r times, with A_{G} given in Theorems 1 and 9.

We remark that identities (23) and (24) have been obtained by Hu [9, Cor. 3] with an incomplete proof.

Corollary 12. (r = 0) We have

∑_{n_{1},...,n_{k}≤x} β(n_{1}, …, n_{k}) = C_{k}x^{k} + O(x^{k−1}(log x)^{k−1}),

where

C_{k} = C_{k,0} = ∑_{n_{1},...,n_{k}=1}^{∞} \frac{(μ ∗ β)(n_{1}, …, n_{k})}{n_{1} ⋯ n_{k}}

= ∑_{j=0}^{k(k−1)/2}(−1)^{j} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} A_{G}.  (25)

Identity (25) has been obtained by Hu [9, Cor. 3].

Note that if G and G′ are isomorphic graphs then the corresponding densities A_{G} and A_{G′} are equal. The asymptotic densities C_{k,r}, C′_{k,r} and C_{k} can be computed for given values of k and r from identities (23), (24) and (25), respectively by determining the cardinalities of the isomorphism classes of graphs G with k vertices and j edges (0 ≤ j ≤ k(k − 1)/2) and by computing the corresponding values of A_{G}. In particular, C_{3} and C_{4} given by (5) and (6) can be obtained in this way.

5 Proofs

We first prove the key result of our treatment.

Proof of Theorem 7. We have

D(δ_{G}; s_{1}, …, s_{k}) = ∑_{n_{1},...,n_{k}=1}^{∞} \frac{δ_{G}(n_{1}, …, n_{k})}{n_{1}^{s_{1}} ⋯ n_{k}^{s_{k}}} = ∑_{\begin{matrix}n_{1},...,n_{k}=1 \\ gcd(n_{i_{1}},n_{i_{2}})=1 \\ \{i_{1},i_{2}\}∈E \end{matrix}}^{∞} \frac{1}{n_{1}^{s_{1}} ⋯ n_{k}^{s_{k}}} .

Let I denote the set of non-isolated vertices of G. Then

D(δ_{G}; s_{1}, …, s_{k}) = ∏_{i∉I} ζ(s_{i}) ∑_{\begin{matrix}n_{i}≥1, i∈I \\ gcd(n_{i_{1}},n_{i_{2}})=1, \{i_{1},i_{2}\}∈E \end{matrix}} ∏_{i∈I} \frac{1}{n_{i}^{s_{i}}}

= ∏_{i∉I} ζ(s_{i}) ∏_{p} ( ∑_{\begin{matrix}ν_{i}≥0, i∈I \\ ν_{i_{1}}ν_{i_{2}}=0, \{i_{1},i_{2}\}∈E \end{matrix}} \frac{1}{p^{∑_{i∈I} ν_{i}s_{i}}} )

=: ∏_{i∉I} ζ(s_{i}) ∏_{p} S_{p},

say, using that the function δ_{G} is multiplicative by Lemma 4.

Now choose a (minimum) vertex cover J. Then ν_{j} (j ∈ J) cover all the conditions ν_{i_{1}}ν_{i_{2}} = 0 with {i_{1}, i_{2}} ∈ E, that is, for every {i_{1}, i_{2}} ∈ E there is j ∈ J such that j = i_{1} or j = i_{2}. Group the terms of the sum S_{p} according to the subsets L = {ℓ ∈ J : ν_{ℓ} ≥ 1} of J. Here ν_{j} = 0 for every j ∈ J \ L. Note that L cannot contain any two adjacent vertices. Also, for such a fixed subset L ⊆ J let M be the set of indexes m such that ν_{m} is forced to be zero by L. More exactly, let M = {m ∈ I \ J : there is ℓ ∈ L with {m, ℓ} ∈ E}. If m ∈ M, then ν_{m}ν_{ℓ} = 0 for some ℓ ∈ L. Since ν_{ℓ} ≥ 1, we obtain ν_{m} = 0. Here M = N(L) \ J, where N(L) is set of vertices adjacent to vertices in L.

Let ∑L⊆J^{′} denote the sum over subsets L of J that have no adjacent vertices. We obtain

S_{p} = \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∑_{\begin{matrix}ν_{ℓ}≥1, ℓ∈L \\ ν_{j}=0, j∈J\L \\ ν_{m}=0, m∈M \\ ν_{i}≥0, i∈I\(J∪M) \end{matrix}} \frac{1}{p^{∑_{i∈I} ν_{i}s_{i}}}

= \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∑_{ν_{ℓ}≥1, ℓ∈L} \frac{1}{p^{∑_{ℓ∈L} ν_{ℓ}s_{ℓ}}} ∑_{ν_{i}≥0, i∈I\(J∪M)} \frac{1}{p^{∑_{i∈I\(J∪M)} ν_{i}s_{i}}}

= \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} (1 − \frac{1}{p^{s_{ℓ}}} )^{−1} ∏_{i∈I\(J∪M)} (1 − \frac{1}{p^{s_{i}}} )^{−1}

= ∏_{i∈I} (1 − \frac{1}{p^{s_{i}}} )^{−1} \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} ∏_{i∈(J\L)∪M} (1 − \frac{1}{p^{s_{i}}} )

=: ∏_{i∈I} (1 − \frac{1}{p^{s_{i}}} )^{−1} T_{p},

say. We deduce that

∏_{p} S_{p} = ∏_{i∈I} ζ(s_{i}) ∏_{p} T_{p},

which shows that

D(δ_{G}; s_{1}, …, s_{k}) = ( ∏_{i=1}^{k} ζ(s_{i}))D′(s_{1}, …, s_{k}),

where

D′(s_{1}, …, s_{k}) = ∏_{p} T_{p} = ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} ∏_{i∈(J\L)∪M} (1 − \frac{1}{p^{s_{i}}} ) ).  (26)

Let us investigate the terms of the sum ∑L⊆J^{′} in (26). If L = ∅, that is, ν_{j} = 0 for every j ∈ J, then M = ∅ and we have

∏_{i∈J} (1 − \frac{1}{p^{s_{i}}} ) = 1 − ∑_{i∈J} \frac{1}{p^{s_{i}}} + ∑_{i,j∈J, i<j} \frac{1}{p^{s_{i}+s_{j}}} − · · · .  (27)

If L = {i_{0}} for some fixed i_{0} ∈ J, then obtain, with M = M_{i_{0}} := N(i_{0}) \ J,

\frac{1}{p^{s_{i_{0}}}} ∏_{\begin{matrix}i∈J∪M_{i_{0}} \\ i≠i_{0} \end{matrix}} (1 − \frac{1}{p^{s_{i}}} ) = \frac{1}{p^{s_{i_{0}}}} − ∑_{\begin{matrix}i∈J∪M_{i_{0}} \\ i≠i_{0} \end{matrix}} \frac{1}{p^{s_{i_{0}}+s_{i}}} + ∑_{\begin{matrix}i,j∈J∪M_{i_{0}} \\ i_{0}≠i<j≠i_{0} \end{matrix}} \frac{1}{p^{s_{i_{0}}+s_{i}+s_{j}}} − · · · .

Here if i_{0} = t runs over J, then we have the terms

∑_{t∈J} \frac{1}{p^{s_{t}}} − ∑_{\begin{matrix}i∈J∪M_{t} \\ t∈J \\ i≠t \end{matrix}} \frac{1}{p^{s_{t}+s_{i}}} + ∑_{\begin{matrix}i,j∈J∪M_{t} \\ t∈J,i≠t,j≠t \\ i<j \end{matrix}} \frac{1}{p^{s_{t}+s_{i}+s_{j}}} − · · · .  (28)

If L = {i_{0}, i′_{0}} with some fixed i_{0}, i′_{0} ∈ J, i_{0} < i′_{0}, which are not adjacent, then obtain, with M = M_{i_{0},i′_{0}} := N({i_{0}, i′_{0}}) \ J,

\frac{1}{p^{s_{i_{0}}+s_{i′_{0}}}} ∏_{\begin{matrix}i∈J∪M_{i_{0},i′_{0}} \\ i≠i_{0},i′_{0} \end{matrix}} (1 − \frac{1}{p^{s_{i}}} ) = \frac{1}{p^{s_{i_{0}}+s_{i′_{0}}}} − ∑_{\begin{matrix}i∈J∪M_{i_{0},i′_{0}} \\ i≠i_{0},i′_{0} \end{matrix}} \frac{1}{p^{s_{i_{0}}+s_{i′_{0}}+s_{i}}} + · · · .  (29)

If i_{0} = t, i′_{0} = v run over J, then we obtain from (29),

∑_{t,v∈J t<v t,v not adjacent} \frac{1}{p^{s_{t}+s_{v}}} − ∑_{i∈J∪M_{t,v} t,v∈J not adjacent i≠t,v} \frac{1}{p^{s_{t}+s_{v}+s_{i}}} + · · · .  (30)

Putting together (27), (28) and (30) we obtain the sum S, where

S = 1 − ∑_{i∈J} \frac{1}{p^{s_{i}}} + ∑_{i,j∈J, i<j} \frac{1}{p^{s_{i}+s_{j}}} + ∑_{t∈J} \frac{1}{p^{s_{t}}} − ∑_{\begin{matrix}i∈J∪M_{t} \\ t∈J \\ i≠t \end{matrix}} \frac{1}{p^{s_{t}+s_{i}}}

+ ∑_{t,v∈J t<v t,v not adjacent} \frac{1}{p^{s_{t}+s_{v}}} ± other terms

= 1 − ∑_{i,t∈J ; i,t adjacent} \frac{1}{p^{s_{t}+s_{i}}} ± other terms,

where the terms ±1/p^{i} with i ∈ J cancel out. Also the terms ±1/p^{s_{i}+s_{j}} with i, j ∈ J (each appearing twice) cancel out, excepting when i, j are adjacent. Here for the “other terms”, including the terms obtained if L has at least three elements, the exponents of p are sums of at least three distinct values s_{i}, s_{j}, s_{ℓ} with i, j, ℓ ∈ I.

Hence the infinite product (26) is absolutely convergent provided the given condition.

Remark 13. It turns out that the function μ ∗ δ_{G} is multiplicative (in general not symmetric in the variables) and for all prime powers p^{ν_{1}}, …, p^{ν_{k}},

(μ∗δ_{G})(p^{ν_{1}}, …, p^{ν_{k}}) = \begin{cases}1, & if ν_{1} = ⋯ = ν_{k} = 0; \\ c(ν_{1}, …, ν_{k}), & if ν_{1}, …, ν_{k} ∈ \{0, 1\}, j := ν_{1} + ⋯ + ν_{k} ≥ 2; \\ 0, & otherwise, \end{cases} (31)

where c(ν_{1}, …, ν_{k}) are some integers, depending on ν_{1}, …, ν_{k}, but not on p.

Note that (μ ∗ δ_{G})(p^{ν_{1}}, …, p^{ν_{k}}) = 0 provided that ν_{i} ≥ 2 for at least one 1 ≤ i ≤ k, or ν_{1}, …, ν_{k} ∈ {0, 1} and ν_{1} + ⋯ + ν_{k} = 1. If ν_{1}, …, ν_{k} ∈ {0, 1} and ν_{1} + ⋯ + ν_{k} = 2, say ν_{i_{0}} = ν_{i′_{0}} = 1 and ν_{i} = 0 for i ≠ i_{0}, i′_{0}, then (μ ∗ δ_{G})(p^{ν_{1}}, …, p^{ν_{k}}) = −1 if i_{0} and i′_{0} are adjacent in the graph G and 0 otherwise.

Proof of Theorem 9. Write

∑_{n_{1},...,n_{k}≤x} δ_{G}(n_{1}, …, n_{k}) = ∑_{n_{1},...,n_{k}≤x} ∑_{d_{1}|n_{1},...,d_{k}|n_{k}}(μ ∗ δ_{G})(d_{1}, …, d_{k})

= ∑_{d_{1},...,d_{k}≤x}(μ ∗ δ_{G})(d_{1}, …, d_{k}) ⌊\frac{x}{d_{1}} ⌋ ⋯ ⌊\frac{x}{d_{k}} ⌋

= ∑_{d_{1},...,d_{k}≤x}(μ ∗ δ_{G})(d_{1}, …, d_{k}) (\frac{x}{d_{1}} + O(1)) ⋯ (\frac{x}{d_{k}} + O(1))

= x^{k} ∑_{d_{1},...,d_{k}≤x} \frac{(μ ∗ δ_{G})(d_{1}, …, d_{k})}{d_{1} ⋯ d_{k}} + R_{k}(x),  (32)

with

R_{k}(x) ≪ ∑_{u_{1},...,u_{r}} x^{u_{1}+···+u_{k}} ∑_{d_{1},...,d_{k}≤x} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1}^{u_{1}} ⋯ d_{k}^{u_{k}}},

where the first sum is over u_{1}, …, u_{k} ∈ {0, 1} such that at least one u_{i} is 0. Let u_{1}, …, u_{k} be fixed and assume that u_{i_{0}} = 0. Since (x/d_{i})^{u_{i}} ≤ x/d_{i} for every i (1 ≤ i ≤ k) we have

A := x^{u_{1}+···+u_{k}} ∑_{d_{1},...,d_{k}≤x} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1}^{u_{1}} ⋯ d_{k}^{u_{k}}}

≤ x^{k−1} ∑_{d_{1},...,d_{k}≤x} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{∏_{1≤i≤k,i≠i_{0}} d_{i}}

≤ x^{k−1} ∏_{p≤x} ∑_{ν_{1},...,ν_{k}=0}^{∞} \frac{|(μ ∗ δ_{G})(p^{ν_{1}}, …, p^{ν_{k}})|}{p^{∑_{1≤i≤k,i≠i_{0}} ν_{i}}}

= x^{k−1} ∏_{p≤x} (1 + \frac{c_{i_{0},1}}{p} + \frac{c_{i_{0},2}}{p^{2}} + ⋯ + \frac{c_{i_{0},k−1}}{p^{k−1}} ) ,  (33)

cf. (31), where c_{i_{0},j} (1 ≤ j ≤ k − 1) are certain non-negative integers. Here c_{i_{0},1} = deg(i_{0}), the degree of i_{0}, according to Remark 13. We obtain that

A ≪ x^{k−1} ∏_{p≤x} (1 + \frac{1}{p})^{deg(i_{0})} ≪ x^{k−1}(log x)^{deg(i_{0})}

by Mertens’ theorem. This shows that

R_{k}(x) ≪ x^{k−1}(log x)^{max deg(i_{0})}.  (34)

Furthermore, for the main term of (32) we have

∑_{d_{1},...,d_{k}≤x} \frac{(μ ∗ δ_{G})(d_{1}, …, d_{k})}{d_{1} ⋯ d_{k}}

= ∑_{d_{1},...,d_{k}=1}^{∞} \frac{(μ ∗ δ_{G})(d_{1}, …, d_{k})}{d_{1} ⋯ d_{k}} − ∑_{∅≠I⊆\{1,...,k\}} ∑_{\begin{matrix}d_{i}>x, i∈I \\ d_{j}≤x, j∉I \end{matrix}} \frac{(μ ∗ δ_{G})(d_{1}, …, d_{k})}{d_{1} ⋯ d_{k}},  (35)

where the series is convergent by Theorem 7 and its sum is D(μ ∗ δ_{G}; 1, …, 1) = A_{G}. Let I be fixed with |I| = t. We estimate the sum

B := ∑_{\begin{matrix}d_{i}>x, i∈I \\ d_{j}≤x, j∉I \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1} ⋯ d_{k}}.

Case I. Assume that |I| = t ≥ 3. If 0 < ε < 1/2, then

B = ∑_{\begin{matrix}d_{i}>x, i∈I \\ d_{j}≤x, j∉I \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})| ∏_{i∈I} d_{i}^{ε−1/2}}{∏_{i∈I} d_{i}^{1/2+ε} ∏_{j∉I} d_{j}}

≤ x^{t(ε−1/2)} ∑_{d_{1},...,d_{k}=1}^{∞} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{∏_{i∈I} d_{i}^{1/2+ε} ∏_{j∉I} d_{j}}

≪ x^{t(ε−1/2)},

since the series is convergent (for t ≥ 1). Using that t(ε−1/2) < −1 for 0 < ε < (t−2)/(2t), here we need t ≥ 3, we obtain B ≪ \frac{1}{x}.

Case II. t = 1: Let d_{i_{0}} > x, d_{i} ≤ x for i ≠ i_{0}, and consider a prime p. If p | d_{i} for some i ≠ i_{0}, then p ≤ x. If p | d_{i_{0}} and p > x, then p ∤ d_{i} for every i ≠ i_{0}, and (μ ∗ δ_{G})(d_{1}, …, d_{k}) = 0, cf.

Remark 13. Hence it is enough to consider the primes p ≤ x. We deduce

B < \frac{1}{x} ∑_{\begin{matrix}d_{i_{0}}>x \\ d_{i}≤x,i≠i_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{∏_{i≠i_{0}} d_{i}}

≤ \frac{1}{x} ∏_{p≤x} ∑_{ν_{1},...,ν_{k}=0}^{∞} \frac{|(μ ∗ δ_{G})(p^{ν_{1}}, …, p^{ν_{k}})|}{p^{∑_{i≠i_{0}} ν_{i}}}

≪ \frac{1}{x}(log x)^{max deg(i_{0})},

similar to the estimate (34). Case III. t = 2: Let d_{i_{0}} > x, d_{i′_{0}} > x. We split the sum B into two sums, namely

B = ∑_{\begin{matrix}d_{i_{0}}>x,d_{i′_{0}}>x \\ d_{i}≤x,i≠i_{0},i′_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1} ⋯ d_{k}}

= ∑_{\begin{matrix}d_{i_{0}}>x^{3/2},d_{i′_{0}}>x \\ d_{i}≤x,i≠i_{0},i′_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1} ⋯ d_{k}} + ∑_{\begin{matrix}x^{3/2}≥d_{i_{0}}>x,d_{i′_{0}}>x \\ d_{i}≤x,i≠i_{0},i′_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{1} ⋯ d_{k}}
=: B_{1} + B_{2},

say, where

B_{1} = ∑_{\begin{matrix}d_{i_{0}}>x^{3/2},d_{i′_{0}}>x \\ d_{i}≤x,i≠i_{0},i′_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{i_{0}}^{1/3} ∏_{i≠i_{0}} d_{i}} \frac{1}{d_{i_{0}}^{2/3}}

< \frac{1}{x} ∑_{d_{1},...,d_{k}=1}^{∞} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{d_{i_{0}}^{1/3} ∏_{i≠i_{0}} d_{i}}

≪ \frac{1}{x},

since the latter series is convergent. Furthermore,

B_{2} < \frac{1}{x} ∑_{\begin{matrix}x^{3/2}≥d_{i_{0}},d_{i′_{0}}>x \\ d_{i}≤x,i≠i_{0},i′_{0} \end{matrix}} \frac{|(μ ∗ δ_{G})(d_{1}, …, d_{k})|}{∏_{i≠i′_{0}} d_{i}},

and consider a prime p. For the last sum, if p | d_{i} for some i ≠ i′_{0} then p ≤ x^{3/2}. If p | d_{i′_{0}} and p > x^{3/2}, then p ∤ d_{i} for every i ≠ i′_{0} and (μ ∗ δ_{G})(d_{1}, …, d_{r}) = 0, cf. Remark 13. Hence it is enough to consider the primes p ≤ x^{3/2}. We deduce, similar to (33), (34) that

B_{2} < \frac{1}{x} ∏_{p≤x^{3/2}} ∑_{ν_{1},...,ν_{r}=0}^{∞} \frac{|(μ ∗ δ_{G})(p^{ν_{1}}, …, p^{ν_{k}})|}{p^{∑_{i≠i′_{0}} ν_{i}}} ≪ \frac{1}{x}(log x^{3/2})^{d_{G}} ≪ \frac{1}{x}(log x)^{d_{G}},

with d_{G} = max_{i∈G} deg(i).

Hence given any |I| = t ≥ 1 we have B ≪ \frac{1}{x}(log x)^{d_{G}}. Therefore, by (35),

∑_{d_{1},...,d_{r}≤x} \frac{(μ ∗ δ_{G})(d_{1}, …, d_{k})}{d_{1} ⋯ d_{k}} = A_{G} + O(x^{−1}(log x)^{d_{G}}).  (36)

The proof is complete by putting together (32), (34) and (36).

Proof of Theorem 11. According to identities (16) and (18) we have

∑_{n_{1},...,n_{k}≤x} β_{r}(n_{1}, …, n_{k}) = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j}{r} ∑_{\begin{matrix}E⊆V^{(2)} \\ |E|=j \end{matrix}} ∑_{n_{1},...,n_{k}≤x} δ_{G}(n_{1}, …, n_{k}), (37)

and

∑_{n_{1},...,n_{k}≤x} β′_{r}(n_{1}, …, n_{k}) = ∑_{j=r}^{k(k−1)/2}(−1)^{j−r}\binom{j − 1}{r − 1} ∑_{\begin{matrix}E⊆S \\ |E|=j \end{matrix}} ∑_{n_{1},...,n_{k}≤x} δ_{G}(n_{1}, …, n_{k}).  (38)

Now for the inner sums ∑_{n_{1},...,n_{k}≤x} δ_{G}(n_{1}, …, n_{k}) of identities (37) and (38) use asymptotic formula (8). For the complete coprimality graph with E = V^{(2)}, corresponding to all coprimality conditions, the error term is O(x^{k−1}(log x)^{k−1}), and this is the final error term in both cases. This proves asymptotic formulas (21) and (22).

Proof of Corollary 12. Apply formula (21) for r = 0, with the constant C_{k,0} given by (23).

6 Examples

To illustrate identities (19) and (20) let us work out the following examples.

Example 14. Let k = 4 and G = (V, E) with V = {1, 2, 3, 4}, E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}, that is, gcd(n_{1}, n_{2}) = 1, gcd(n_{2}, n_{3}) = 1, gcd(n_{3}, n_{4}) = 1, gcd(n_{4}, n_{1}) = 1. See Figure 1.

Here I = {1, 2, 3, 4} and choose the minimum vertex cover J = {1, 3}. According to (19),

D′_{G}(s_{1}, s_{2}, s_{3}, s_{4}) = ∏_{p} ( \begin{matrix}∑ & ′ \\ L⊆J \end{matrix} ∏_{ℓ∈L} \frac{1}{p^{s_{ℓ}}} ∏_{i∈(J\L)∪(N(L)\J)} (1 − \frac{1}{p^{s_{i}}} ))  (39)

1 2 4 3

Figure 1: Graph of Example 14

\begin{matrix}L & N(L) & (J \ L) ∪ (N(L) \ J) & S_{L} \\ ∅ & ∅ & \{1, 3\} & (1 − x_{1})(1 − x_{3}) \\ \{1\} & \{2, 4\} & \{2, 3, 4\} & x_{1}(1 − x_{2})(1 − x_{3})(1 − x_{4}) \\ \{3\} & \{2, 4\} & \{1, 2, 4\} & x_{3}(1 − x_{1})(1 − x_{2})(1 − x_{4}) \\ \{1, 3\} & \{2, 4\} & \{2, 4\} & x_{1}x_{3}(1 − x_{2})(1 − x_{4}) \end{matrix}

Table 1: Terms of the sum in Example 14

Write the terms of the sum in (39), see Table 1, where x_{i} = 1/p^{s_{i}} (1 ≤ i ≤ 4). Note that all subsets of J are independent.

We obtain

D′_{G}(s_{1}, …, s_{4}) = ∏_{p} (S_{∅} + S_{{1}} + S_{{3}} + S_{{1,3}})

= ∏_{p} (1 − \frac{1}{p^{s_{1}+s_{2}}} − \frac{1}{p^{s_{1}+s_{4}}} − \frac{1}{p^{s_{2}+s_{3}}} − \frac{1}{p^{s_{3}+s_{4}}} + \frac{1}{p^{s_{1}+s_{2}+s_{3}}}

+\frac{1}{p^{s_{1}+s_{2}+s_{4}}} + \frac{1}{p^{s_{1}+s_{3}+s_{4}}} + \frac{1}{p^{s_{2}+s_{3}+s_{4}}} − \frac{1}{p^{s_{1}+s_{2}+s_{3}+s_{4}}} ) .

Observe that the terms ±1/p^{i} with i ∈ J = {1, 3} cancel out, and we have the terms −1/p^{s_{i}+s_{j}} with {i, j} ∈ E, according to the edges of G. Hence the infinite product is absolutely convergent provided that ℜ(s_{i_{1}} + ⋯ + s_{i_{j}}) > 1 for every i_{1}, …, i_{j} ∈ {1, 2, 3, 4} with i_{1} < ⋯ < i_{j}, 2 ≤ j ≤ 4.

The asymptotic density of 4-tuples (n_{1}, …, n_{4}) ∈ ℕ^{4} such that gcd(n_{i}, n_{j}) = 1 with {i, j} ∈ E is

D′_{G}(1 …, 1) = ∏_{p} (1 − \frac{4}{p^{2}} + \frac{4}{p^{3}} − \frac{1}{p^{4}} ) .

This asymptotic density has been obtained using identity (10) by de Reyna and Heyman [2, Sect. 4].

Example 15. Now let k = 7 and G = (V, E) with V = {1, 2, 3, 4, 5, 6, 7} and

E = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}},

that is, gcd(n_{1}, n_{2}) = 1, gcd(n_{1}, n_{3}) = 1, gcd(n_{2}, n_{4}) = 1, gcd(n_{2}, n_{5}) = 1, gcd(n_{3}, n_{4}) = 1, gcd(n_{4}, n_{5}) = 1. See Figure 2.

1 2 3 4 5 6 7

Figure 2: Graph of Example 15

Here I = {1, 2, 3, 4, 5}, since the variables n_{6}, n_{7} do not appear in the constraints. Choose the minimum vertex cover J = {1, 2, 4}. Consider the subsets L of J and write the corresponding terms S_{L} of the sum in (19), see Table 2, where x_{i} = p^{−s_{i}} (1 ≤ i ≤ 5). The subsets L = {1, 2} and L = {2, 4} do not appear in the sum, since 1, 2 and 2, 4 are adjacent vertices.

\begin{matrix}L & N(L) & (J \ L) ∪ (N(L) \ J) & S_{L} \\ ∅ & ∅ & \{1, 2, 4\} & (1 − x_{1})(1 − x_{2})(1 − x_{4}) \\ \{1\} & \{3\} & \{2, 3, 4\} & x_{1}(1 − x_{2})(1 − x_{3})(1 − x_{4}) \\ \{2\} & \{5\} & \{1, 4, 5\} & x_{2}(1 − x_{1})(1 − x_{4})(1 − x_{5}) \\ \{4\} & \{3, 5\} & \{1, 2, 3, 5\} & x_{4}(1 − x_{1})(1 − x_{2})(1 − x_{3})(1 − x_{5}) \\ \{1, 4\} & \{3, 5\} & \{2, 3, 5\} & x_{1}x_{4}(1 − x_{2})(1 − x_{3})(1 − x_{5}) \end{matrix}

Table 2: Terms of the sum in Example 15

It follows that

D′_{G}(s_{1}, …, s_{7}) = ∏_{p} (S_{∅} + S_{{1}} + S_{{2}} + S_{{4}} + S_{{1,4}})

= ∏_{p} (1 − \frac{1}{p^{s_{1}+s_{2}}} − \frac{1}{p^{s_{1}+s_{3}}} − \frac{1}{p^{s_{2}+s_{4}}} − \frac{1}{p^{s_{2}+s_{5}}} − \frac{1}{p^{s_{3}+s_{4}}} − \frac{1}{p^{s_{4}+s_{5}}}

+\frac{1}{p^{s_{1}+s_{2}+s_{3}}} + \frac{1}{p^{s_{1}+s_{2}+s_{4}}} + \frac{1}{p^{s_{1}+s_{2}+s_{5}}} + \frac{1}{p^{s_{1}+s_{3}+s_{4}}} + \frac{1}{p^{s_{2}+s_{3}+s_{4}}}

+\frac{2}{p^{s_{2}+s_{4}+s_{5}}} + \frac{1}{p^{s_{3}+s_{4}+s_{5}}} − \frac{1}{p^{s_{1}+s_{2}+s_{3}+s_{4}}} − \frac{1}{p^{s_{1}+s_{2}+s_{4}+s_{5}}} − \frac{1}{p^{s_{2}+s_{3}+s_{4}+s_{5}}} ) .

Observe that the terms ±1/p^{i} with i, j ∈ {1, 2, 4} cancel out, and we have the terms −1/p^{s_{i}+s_{j}} with {i, j} ∈ E, according to the edges of G. Here the infinite product is absolutely convergent provided that ℜ(s_{i_{1}} + ⋯ + s_{i_{j}}) > 1 for every i_{1}, …, i_{j} ∈ {1, 2, 3, 4, 5} with i_{1} < ⋯ < i_{j}, 2 ≤ j ≤ 5.

The asymptotic density of 7-tuples (n_{1}, …, n_{7}) ∈ ℕ^{7} with the corresponding constraints gcd(n_{i}, n_{j}) = 1 with {i, j} ∈ E is

D′_{G}(1 …, 1) = ∏_{p} (1 − \frac{6}{p^{2}} + \frac{8}{p^{3}} − \frac{3}{p^{4}} ) .

Application of identity (10) by de Reyna and Heyman [2] is more laborious here, since G has six edges and there are 2^{6} = 64 subsets of E.

Example 16. Now consider the case of pairwise coprime integers with E = {{i, j} : 1 ≤ i < j ≤ k}. For k = 4 the graph is in Figure 3.

1 2 4 3

Figure 3: Graph to Example 16

Here I = {1, …, k} and choose the minimum vertex cover J = {1, …, k − 1}. The only independent subsets L of J are L = ∅ and L = {1}, ..., L = {k − 1} having one single element.

If L = ∅, then N(L) = ∅, (J \L)∪(N(L)\J) = J and obtain, with x_{i} = p^{−s_{i}} (1 ≤ i ≤ k),

S_{∅} = (1 − x_{1}) ⋯ (1 − x_{k−1}).

If L = {ℓ}, ℓ ∈ J, then N(L) = {k}, (J \ L) ∪ (N(L) \ J) = {1, …, k} \ {ℓ}, and have

S_{\{ℓ\}} = x_{ℓ} ∏_{\begin{matrix}j=1 \\ j≠ℓ \end{matrix}}^{k}(1 − x_{j}).

We need to evaluate the sum

S := S_{∅} + ∑_{ℓ=1}^{k−1} S_{{ℓ}}.  (40)

Let e_{j}(x_{1}, …, x_{k}) = ∑_{1≤i_{1}<...<i_{j}≤k} x_{i_{1}} ⋯ x_{i_{j}} denote the elementary symmetric polynomials in x_{1}, …, x_{k} of degree j (j ≥ 0). By convention, e_{0}(x_{1}, …, x_{k}) = 1.

Consider the polynomial

P (x) = ∏_{j=1}^{k}(x − x_{j}) = ∑_{j=0}^{k}(−1)^{j}e_{j}(x_{1}, …, x_{k})x^{k−j}.

Its derivative is

P′(x) = ∑_{j=0}^{k−1}(−1)^{j}(k − j)e_{j}(x_{1}, …, x_{k})x^{k−j−1},

and on the other hand

P′(x) = ∑_{j=1}^{k} ∏_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k}(x − x_{i}).

We obtain that the sum (40) is

S = ∏_{j=1}^{k−1}(1 − x_{j}) + ∑_{j=1}^{k−1} x_{j} ∏_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k}(1 − x_{i})

= ∑_{j=1}^{k} ∏_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k}(1 − x_{i}) − (k − 1) ∏_{j=1}^{k}(1 − x_{j})

= P′(1) − (k − 1)P (1)

= 1 + ∑_{j=2}^{k}(−1)^{j−1}(j − 1)e_{j}(x_{1}, …, x_{k}),

that is,

∑_{\begin{matrix}n_{1},...,n_{k}=1 \\ gcd(n_{i},n_{j})=1, 1≤i<j≤k \end{matrix}}^{∞} \frac{1}{n_{1}^{s_{1}} ⋯ n_{k}^{s_{k}}} = ∏_{p} (1 + ∑_{j=2}^{k}(−1)^{j−1}(j − 1)e_{j}(p^{−s_{1}}, …, p^{−s_{k}})) .

For s_{1} = ⋯ = s_{k} = 1 this gives identity (2), representing the asymptotic density of k-tuples with pairwise relatively prime components.

References

[1] M. Aigner, A Course in Enumeration, Graduate Texts in Mathematics, Vol. 238, Springer, 2007.

[2] J. Arias de Reyna and R. Heyman, Counting tuples restricted by pairwise coprimality conditions, J. Integer Sequences 18 (2015), Article 15.10.4.

[3] J.-Y. Cai and E. Bach, On testing for zero polynomials by a set of points with bounded precision, Theoret. Comp. Sci. 296 (2003), 15–25.

[4] J. Christopher, The asymptotic density of some k-dimensional sets, Amer. Math. Monthly 63 (1956), 399–401.

[5] H. Delange, On some sets of pairs of positive integers, J. Number Theory 1 (1969), 261–279.

[6] J. L. Fernández and P. Fernández, Divisibility properties of random samples of integers, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 115 (2021), no. 1, Paper No. 26.

[7] R. Heyman, Pairwise non-coprimality of triples, arXiv preprint arXiv:1309.5578

[math.NT], May 7 2014. Available at https://arxiv.org/abs/1309.5578.

[8] J. Hu, The probability that random positive integers are k-wise relatively prime, Int. J. Number Theory 9 (2013), 1263–1271.

[9] J. Hu, Pairwise relative primality of positive integers, ArXiv preprint, arXiv:1406.3113 [math.NT], June 12 2014. Available at https://arxiv.org/abs/1406.3113.

[10] P. Moree, Counting carefree couples, ArXiv preprint arXiv:math/0510003 [math.NT], September 30 2005. Revision, July 4 2014. Available at https://arxiv.org/abs/math/

0510003.

[11] P. Moree, Counting carefree couples, Mathematics Newsletter 24 (2014), no. 4, 103–110.

[12] J. E. Nymann, On the probability that k positive integers are relatively prime, J. Number Theory 4 (1972), 469–473.

[13] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Univ. Press, Cambridge, 1997.

[14] L. Tóth, On the asymptotic densities of certain subsets of ℕ^{k}, Riv. Mat. Univ. Parma (6) 4 (2001), 121–131.

[15] L. Tóth, The probability that k positive integers are pairwise relatively prime, Fibonacci Quart. 40 (2002), 13–18.

[16] L. Tóth, Multiplicative arithmetic functions of several variables: a survey, in Th. M. Rassias and P. Pardalos, eds., Mathematics Without Boundaries, Surveys in Pure Mathematics, Springer, 2014, pp. 483–514.

[17] L. Tóth, Counting r-tuples of positive integers with k-wise relatively prime components, J. Number Theory 166 (2016), 105–116.

[18] N. Ushiroya, Mean-value theorems for multiplicative arithmetic functions of several variables, Integers 12 (2012), 989–1002.

2020 Mathematics Subject Classification: Primary 11A25; Secondary 11N25, 11N37, 05A15, 05C07. Keywords: pairwise coprime integers, pairwise non-coprime integers, asymptotic density, asymptotic formula, multiplicative function of several variables, inclusion-exclusion principle, simple graph, vertex cover.

(Concerned with sequences \underline{A229099}, \underline{A256390}, \underline{A256391}, and \underline{A256392}.)

Received March 19 2024; revised version received September 11 2024. Published in Journal of Integer Sequences, November 29 2024.

Return to Journal of Integer Sequences home page.