Counting Tuples Restricted by Pairwise Coprimality Conditions

Juan Arias de Reyna Facultad de Matemáticas Universidad de Sevilla c/. Tarfia, s/n 41012-Sevilla Spain

                      arias@us.es

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

                  randell@unsw.edu.au

Abstract

Given a subset A of the set {1, …, v}^{2} we say that (a_{1}, …, a_{v}) exhibits pairwise coprimality over A if gcd(a_{i}, a_{j}) = 1 for all (i, j) ∈ A. For a given positive x and a given set A we give an asymptotic formula for the number of (a_{1}, …, a_{v}) with 1 ≤ a_{1}, …, a_{v} ≤ x that exhibit pairwise coprimality over A. This problem has been studied before by Hu.

1 Introduction

We study tuples whose elements are positive integers of maximum value x and impose certain coprimality conditions on pairs of elements. Pairwise coprimality has a long history. It is a requirement of the Chinese remainder theorem which has been known for at least 1,700 years (see the book by Katz [9, pp. 131–132]). The Chinese remainder theorem is important in many areas of modern day mathematics. Some applications in modular multiplication, bridging computations, coding theory and cryptography can be found in the book by Ding, Pei, and Salomaa [2, pp. 33–184] and some comments regarding modular multiplication applications can be found in the book by Knuth [10, pp. 285–292]. To date pairwise coprimality calculations have also been necessary for quantifying v-tuples that are totally pairwise noncoprime, that is, gcd(a_{i}, a_{j}) > 1 for all 1 ≤ i, j ≤ v (see articles by Hu and the second author [8, 6], and the comments by Moree [11] regarding the manuscript of Freiberg [4]).

Tóth [12] used an inductive approach to give an asymptotic formula for the number of height-constrained tuples that exhibit totally pairwise coprimality (that is, gcd(a_{i}, a_{j}) = 1 for all 1 ≤ i, j ≤ v). See also the article by Cai and Bach [1, Theorems 4 and 5] for another approach to asymptotic results regarding total pairwise coprimality. Recently Fernández and Fernández [3] and in subsequent discussions with the second author, have shown how to calculate the asymptotic proportion of v random positive integers that exhibit coprimality across given pairs. They give only an asymptotic value without information about the error term. Their approach is non-inductive. Hu [8] was the first to estimate the number of (a_{1}, …, a_{v}) with 1 ≤ a_{1}, …, a_{v} ≤ x that satisfy general coprimality conditions on pairs of elements of a v-tuple. His inductive approach gives an asymptotic formula with an upper bound on the error term of O(x^{v−1} log^{v−1} x).

Our result gives an upper bound of the error term of O(x^{v−1} log^{d} x) where d is the maximum number of pairwise coprimality conditions that involve a given index. In many cases d < v − 1, and in these cases our main result gives a better error term than that in the article by Hu [8]. Unlike Hu [8], our approach is non-inductive. In this paper we focus exclusively on pairwise coprimality conditions, but readers interested in the generalization from pairwise to k-wise coprimality can see another article by Hu [7].

We use a graph to represent the required primality conditions as follows. Let G = (V, E) be a graph with v vertices and e edges. The set of vertices, V, is given by V = {1, …, v}, while the set of edges of G, denoted by E, is a subset of the set of pairs of elements of V. That is, E ⊂ {{1, 2}, {1, 3}, …, {r, s}, …, {v − 1, v}}. We admit isolated vertices (that is, vertices that are not adjacent to any other vertex). An edge is always of the form {r, s} with r ≠ s and {r, s} = {s, r}. For each real x > 0 we define the set of all tuples that satisfy the primality conditions by

G(x) := {(a_{1}, …, a_{v}) ∈ ℕ^{v} : a_{r} ≤ x, gcd(a_{r}, a_{s}) = 1 if {r, s} ∈ E}.

We also let g(x) = card(G(x)), and denote with d the maximum degree of the vertices of G. Finally, let Q_{G}(z) = 1 + B_{2}z^{2} + ⋯ + B_{v}z^{v} be the polynomial associated with the graph G defined in Section 2.

Our main result is as follows.

Theorem 1. For real x > 0 we have

g(x) = x^{v}ρ_{G} + O(x^{v−1} log^{d} x),

where

ρ_{G} = ∏_{p prime} Q_{G} (\frac{1}{p}) .

The quantity ρ_{G} gives the asymptotic proportion of v random positive integers that exhibit the given pairwise coprimality conditions. When combined with Section 2 the formula is explicit. For example, consider the ‘square’ 4-tuple. That is, 4-tuples with gcd(a_{1}, a_{2}) = gcd(a_{2}, a_{3}) = gcd(a_{3}, a_{4}) = gcd(a_{4}, a_{1}) = 1. Then the asymptotic proportion of such 4-tuples is given by

ρ_{G} = ∏_{p prime} (1 − \frac{4}{p^{2}} + \frac{4}{p^{3}} − \frac{1}{p^{4}} ) = 0.217778 ⋯

Further details can be found in Section 4.

2 Preparations

As usual, for any integer n ≥ 1, let ω(n) and σ(n) be the number of distinct prime factors of n and the sum of divisors of n, respectively (we also set ω(1) = 0). We also use μ to denote the Möbius function, that is, μ(n) = (−1)^{ω(n)} if n is squarefree, and μ(n) = 0 otherwise. P^{+}(n) denotes the largest prime factor of the integer n > 1. By convention P^{+}(1) = 1. We recall that the notation U = O(V) is equivalent to the assertion that the inequality |U| ≤ c|V | holds for some constant c > 0. We use A ⊂ B to indicate that A is a subset of B.

For each F ⊂ E, a subset of the edges of G, let v(F) be the number of non-isolated vertices of F. We define two polynomials Q_{G}(z) and Q_{G}^{+}(z) by

Q_{G}(z) = ∑_{F ⊂E}(−1)^{card(F)}z^{v(F)}, Q_{G}^{+}(z) = ∑_{F ⊂E} z^{v(F)}.

In this way we associate two polynomials with each graph. It is clear that the only F ⊂ E for which v(F) = 0 is the empty set. Thus the constant term of Q_{G}(z) and Q_{G}^{+}(z) is always 1. If F is non-empty then there is some edge a = {r, s} ∈ F so that v(F) ≥ 2. Therefore the coefficient of z in Q_{G}(z) and Q_{G}^{+}(z) is zero. Since we do not allow repeated edges the only case in which v(F) = 2 is when F consists of one edge. Thus the coefficient of z^{2} in Q_{G}^{+}(z) is e, that is, the number of edges e in G. The corresponding z^{2} coefficient in Q_{G}(z) is −e.

As a matter of notation we shall sometimes use r and s to indicate vertices. The letter v always denotes the last vertex and the number of vertices in a given graph. Edges are sometimes denoted by a or b. As previously mentioned, we use d to denote the maximum degree of any vertex and e to denote the number of edges. We use terms like e_{j} to indicate the j-th edge.

We associate several multiplicative functions with any graph. To define these functions we consider functions E → ℕ, that is, to any edge a in the graph we associate a natural number n_{a}. We call any of these functions, a ↦ n_{a}, an edge numbering of the graph. Given an edge numbering we assign a corresponding vertex numbering function r ↦ N_{r} by the rule N_{r} = lcm(n_{b_{1}}, …, n_{b_{u}}), where E_{r} = {b_{1}, …, b_{u}} ⊂ E is the set of edges incident to r. We note that in the case where r is an isolated vertex we have E_{r} = ∅ and N_{r} = 1. With this notation we define

f_{G}(m) = ∑_{N_{1}N_{2}···N_{v}=m} μ(n_{1}) ⋯ μ(n_{e}), f_{G}^{+}(m) = ∑_{N_{1}N_{2}···N_{v}=m} |μ(n_{1}) ⋯ μ(n_{e})|.

In this and similar summations in this paper, the summation is extended to all edge numberings (that is, for all 1 ≤ n_{1}, …, n_{e} < ∞) satisfying the condition written under the summation symbol, usually expressed in terms of the corresponding vertex numberings.

The following is interesting in its own right, but will also be used to prove Theorem 1.

Proposition 2. Let f : ℕ → ℂ be a multiplicative function. For any graph G the function

g_{f,G}(m) = ∑_{N_{1}N_{2}···N_{v}=m} f(n_{1}) ⋯ f(n_{e})

is multiplicative.

Proof. Let m = m_{1}m_{2}, where gcd(m_{1}, m_{2}) = 1. Let us assume that for a given edge numbering of G we have N_{1} ⋯ N_{v} = m. For any edge a = {r, s} we have n_{a}|N_{r} and n_{a}|N_{s}. Therefore n_{a}^{2}|m. It follows that we may express n_{a} as n_{a} = n_{1,a}n_{2,a} with n_{1,a}|m_{1} and n_{2,a}|m_{2}. In this case gcd(n_{1,a}, n_{2,a}) = 1, and we have

N_{r} = lcm(n_{b_{1}}, …, n_{b_{v}}) = lcm(n_{1,b_{1}}, …, n_{1,b_{v}}) lcm(n_{2,b_{1}}, …, n_{2,b_{v}}),
f(n_{1}) ⋯ f(n_{e}) = f(n_{1,1}) ⋯ f(n_{1,e}) · f(n_{2,1}) ⋯ f(n_{2,e}).

Since each edge numbering n_{a} splits into two edge numberings n_{1,a} and n_{2,a}, we have

m_{1} = N_{1,1} ⋯ N_{1,v}, m_{2} = N_{2,1} ⋯ N_{2,v}.

Thus

g_{f,G}(m_{1}m_{2}) = g_{f,G}(m)

= ∑_{N_{1}N_{2}···N_{v}=m} f(n_{1}) ⋯ f(n_{e})

= ∑_{N_{1,1}···N_{1,v}·N_{2,1}···N_{2,v}=m_{1}m_{2}} f(n_{1,1}) ⋯ f(n_{1,e}) · f(n_{2,1}) ⋯ f(n_{2,e})

= ∑_{N_{1,1}···N_{1,v}=m_{1}} f(n_{1,1}) ⋯ f(n_{1,e}) ∑_{N_{2,1}···N_{2,v}=m_{2}} f(n_{2,1}) ⋯ f(n_{2,e})

= g_{f,G}(m_{1})g_{f,G}(m_{2}),

which completes the proof.

We now draw the link between f_{G}^{+}(p^{k}) and Q_{G}^{+}(z).

Lemma 3. For any graph G and prime p the value f_{G}^{+}(p^{k}) is equal to the coefficient of z^{k} in Q_{G}^{+}(z). In the same way the value of f_{G}(p^{k}) is equal to the coefficient of z^{k} in Q_{G}(z).

Proof. First we consider the case of f_{G}(p^{k}). Recall that

Q_{G}(z) = ∑_{F ⊂E}(−1)^{card(F)}z^{v(F)}, f_{G}(p^{k}) = ∑_{N_{1}···N_{v}=p^{k}} μ(n_{1}) ⋯ μ(n_{e}),

where the last sum is on the set of edge numberings of G. In the second sum we shall only consider edge numberings of G giving a non-null term. This means that we only consider edge numberings with n_{a} squarefree numbers. Notice also that if N_{1} ⋯ N_{v} = p^{k}, then each n_{a} | p^{k}. So the second sum extends to all edge numbering with n_{a} ∈ {1, p} for each edge a ∈ E and satisfying N_{1} ⋯ N_{v} = p^{k}.

We need to prove the equality

∑_{F ⊂E, v(F)=k}(−1)^{card(F)} = ∑_{N_{1}···N_{v}=p^{k}} μ(n_{1}) ⋯ μ(n_{e}).  (1)

To this end we shall define for each F ⊂ E with v(F) = k a squarefree edge numbering σ(F) = (n_{a}) with N_{1} ⋯ N_{v} = p^{k}, n_{a} ∈ {1, p} and such that (−1)^{card(F)} = μ(n_{1}) ⋯ μ(n_{e}). We will show that σ is a bijective mapping between the set of F ⊂ E with v(F) = k and the set of edge numberings (n_{a}) with N_{1} ⋯ N_{v} = p^{k}. Thus equality (1) will be established and the proof finished.

Assume that F ⊂ E with v(F) = k. We define σ(F) as the edge numbering (n_{a}) defined by

n_{a} = p for any a ∈ F , n_{a} = 1 for a ∈ E ∖ F .

In this way it is clear that μ(n_{1}) ⋯ μ(n_{e}) = (−1)^{card(F)}. Also N_{r} = p or N_{r} = 1. We have N_{r} = p if and only if there is some a = {r, s} ∈ F. So that N_{1} ⋯ N_{v} = p^{v(F)} because by definition v(F) is the cardinality of the union ⋃_{{r,s}∈F} {r, s}.

The map σ is invertible. For let (n_{a}) be an edge numbering of squarefree numbers with N_{1} ⋯ N_{v} = p^{k} and n_{a} ∈ {1, p}. If σ(F) = (n_{a}) necessarily we have F = {a ∈ E : n_{a} = p}. It is clear that defining F in this way we have v(F) = k and σ(F) = (n_{a}).

Therefore the coefficient of z^{k} in Q_{G}(z) coincides with the value of f_{G}(p^{k}).

The proof for f_{G}^{+} is the same, observing that for σ(F) = (n_{a}) we have 1 = |(−1)^{card(F)}| = |μ(n_{1}) ⋯ μ(n_{e})|.

3 Proof of Theorem 1

We prove the theorem in the following steps:

1. We show that

g(x) = ∑_{n_{1},...,n_{e}} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} ⌊\frac{x}{N_{r}} ⌋.

2. We show that

g(x) = x^{v} ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}} + R + O (x^{v−1} log^{d} x) ,

where

|R| ≤ x^{v−1} ∑_{j=1}^{e} ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{j−1}=1}^{∞} ∑_{n_{j}>x} ∑_{n_{j+1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}} .

3. We show that |R| = O(x^{v−1} log^{d} x). We start with the following sieve result which generalizes the sieve of Eratosthenes. Lemma 4. Let X be a finite set, and let A_{1}, A_{2}, …, A_{k} ⊂ X. Then

card (X\ ⋃_{j=1}^{k} A_{j}) = ∑_{J⊂{1,2,...,k}}(−1)^{card(J)} card(A_{J}),

where A_{∅} = X, and for J ⊂ {1, 2, …, k} non-empty

A_{J} = ⋂_{j∈J} A_{j}.

To prove Theorem 1 let X be the set

X = {(a_{1}, …, a_{v}) ∈ ℕ^{v} : a_{r} ≤ x, 1 ≤ r ≤ v}.

Our set G(x), associated with the graph G, is a subset of X. Now for each prime p ≤ x and each edge a = {r, s} ∈ G define the following subset of X.

A_{p,a} = {(a_{1}, …, a_{v}) ∈ X : p|a_{r}, p|a_{s}}.

Therefore the tuples in A_{p,a} are not in G(x). In fact it is clear that

G(x) = X\ ⋃_{\begin{matrix}a∈E \\ p≤x \end{matrix}} A_{p,a},

where E denotes the set of edges in our graph G. We note that we have an A_{p,a} for each prime number less than or equal to x and each edge a ∈ E. Denoting P_{x} as the set of prime numbers less than or equal to x we can represent each A_{p,a} as A_{j} with j ∈ P_{x} × E. We now apply Lemma 4 and obtain

g(x) = ∑_{J⊂P_{x}×E}(−1)^{card(J)} card(A_{J}).  (2)

We compute card(A_{J}) and then card(J). For card(A_{J}) we have

J = {(p_{1}, e_{1}), …, (p_{m}, e_{m})}, A_{J} = ⋂_{j=1}^{m} A_{p_{j},e_{j}}.

Therefore (a_{1}, …, a_{v}) ∈ A_{J} is equivalent to saying that p_{j}|a_{r_{j}}, p_{j}|a_{s_{j}} for all 1 ≤ j ≤ m, where e_{j} = {r_{j}, s_{j}}. We note that if p_{i_{1}}, …, p_{i_{ℓ}} are the primes associated in J with a given edge a = {r, s}, then the product of p_{i_{1}} ⋯ p_{i_{ℓ}} must also divide the values a_{r} and a_{s} associated with the vertices of a. Let T_{a} ⊂ P_{x} consist of the primes p such that (p, a) ∈ J. In addition we define

n_{a} = ∏_{p∈T_{a}} p,

observing that when T_{a} = ∅ we have n_{a} = 1. Then (a_{1}, …, a_{v}) ∈ A_{J} is equivalent to saying that for each a = {r, s} appearing in J we have n_{a} | a_{r} and n_{a} | a_{s}. In this way we can define J by giving a number n_{a} for each edge a. We note that n_{a} is always squarefree, and all its prime factors are less than or equal to x. We also note that (a_{1}, …, a_{v}) ∈ A_{J} is equivalent to saying that n_{a}|a_{r} for each edge a that joins vertex r with another vertex.

Then for each vertex r, consider all the edges a joining r to other vertices, and denote the least common multiple of the corresponding n_{a}’s by N_{r}. So (a_{1}, …, a_{v}) ∈ A_{J} is equivalent to saying that N_{r}|a_{r}. The number of multiples of N_{r} that are less than or equal to x is ⌊x/N_{r}⌋, so we can express the number of elements of A_{J} as

card(A_{J}) = ∏_{r=1}^{v} ⌊\frac{x}{N_{r}} ⌋.  (3)

We now compute card(J). This is the total number of prime factors across all the n_{j}. As mentioned before n_{j} is squarefree, so

(−1)^{card(J)} = (−1)^{∑j=1^{e} ω(n_{j})} = μ(n_{1}) ⋯ μ(n_{e}),  (4)

where the summations are over all squarefree n_{j} with P^{+}(n_{j}) ≤ x. Substituting (3) and (4) into (2) yields

g(x) = ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} ⌊\frac{x}{N_{r}} ⌋.

At first the sum extends to the (n_{1}, …, n_{e}) that are squarefree and have all prime factors less than or equal to x. But we may extend the sum to all (n_{1}, …, n_{e}), because if these conditions are not satisfied then the corresponding term is automatically 0. In fact we may restrict the summation to the n_{a} ≤ x, because otherwise for a = {r, s} we have n_{a} | N_{r} and ⌊x/N_{r}⌋ = 0. Therefore

g(x) = ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} ⌊\frac{x}{N_{r}} ⌋.

We now seek to express g(x) as a multiple of x^{v} plus a suitable error term. Observe that for all real z_{1}, z_{2}, z_{3} > 0,

⌊z_{1}⌋⌊z_{2}⌋⌊z_{3}⌋ = z_{1}z_{2}z_{3} − z_{1}z_{2}{z_{3}} − z_{1}{z_{2}}⌊z_{3}⌋ − {z_{1}}⌊z_{2}⌋⌊z_{3}⌋,

where {y} denotes the fractional part of a number y.

Applying a similar procedure, with v factors instead of 3, we get

g(x) = ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{x}{N_{r}}

− ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e})\{\frac{x}{N_{1}} \} ∏_{r=2}^{v} ⌊\frac{x}{N_{r}} ⌋

− ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e})\frac{x}{N_{1}} \{\frac{x}{N_{2}} \} ∏_{r=3}^{v} ⌊\frac{x}{N_{r}} ⌋

⋯

− ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e})\frac{x}{N_{1}} ⋯ \frac{x}{N_{v−1}} \{\frac{x}{N_{v}} \}

= x^{v} ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}} + ∑_{k=1}^{v} R_{k},  (5)

where for 1 ≤ k ≤ v,

R_{k} = − ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e})\frac{x}{N_{1}} ⋯ \frac{x}{N_{k−1}} \{\frac{x}{N_{k}} \}⌊\frac{x}{N_{k+1}} ⌋ ⋯ ⌊\frac{x}{N_{v}} ⌋,

with the obvious modifications for j = 1 and j = v. We then have

|R_{k}| ≤ ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} |μ(n_{1}) ⋯ μ(n_{e})|\frac{x}{N_{1}} ⋯ \frac{x}{N_{k−1}} \frac{x}{N_{k+1}} ⋯ \frac{x}{N_{v}}

≤ x^{v−1} ∑_{P^{+}(m)≤x} \frac{C_{G,k}(m)}{m},

where

C_{G,k}(m) = ∑ ; m=∏_{1≤r≤v,r≠k} N_{r} |μ(n_{1}) ⋯ μ(n_{e})|.

By similar reasoning to that of Proposition 2 the function C_{G,k}(m) can be shown to be multiplicative. The numbers C_{G,k}(p^{α}) = C_{G,k,α} do not depend on p, and C_{G,k}(p^{α}) = C_{G,k,α} = 0 for α > v. So we have

∑_{P^{+}(m)≤x} \frac{C_{G,k}(m)}{m} ≤ ∏_{p≤x} (1 + \frac{C_{G,k,1}}{p} + \frac{C_{G,k,2}}{p^{2}} + ⋯ \frac{C_{G,k,v}}{p^{v}} )
= O(log^{C_{G,k,1}} x),

where C_{G,k}(m) is the number of solutions (n_{1}, …, n_{e}), with n_{j} squarefree, to

∏_{1≤r≤v,r≠k} N_{r} = m.

Let h_{k} denote the degree of vertex k. It is easy to see that for a prime p we have C_{G,k,1} = C_{G,k}(p) = h_{k}. The solutions are precisely those with all n_{j} = 1, except one n_{ℓ} = p, where ℓ should be one of the edges meeting at vertex k. Therefore the maximum number of solutions occurs when k is one of the vertices of maximum degree. So if we let d be this maximum degree, then the maximum value of C_{G,k}(p) is d. Therefore

|R_{k}| = O(x^{v−1} log^{d} x).  (6)

Substituting (6) into (5) we obtain

g(x) = x^{v} ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}} + O(x^{v−1} log^{d} x).  (7)

We require the following lemma.

Lemma 5.

lim_{x→∞} ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} < +∞.

Proof. We have

lim_{x→∞} ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} = ∑_{m=1}^{∞} \frac{f_{G}^{+}(m)}{m},  (8)

where

f_{G}^{+}(m) = ∑ ; m=∏_{r=1}^{v} N_{r} |μ(n_{1}) ⋯ μ(n_{e})|.

We note that f_{G}^{+}(m) is multiplicative by Proposition 2. It is clear that f_{G}^{+}(1) = 1. Also, each edge joins two vertices r and s and thus n_{j}|N_{r} and n_{j}|N_{s}. This means that

n_{j}^{2}| ∏_{r=1}^{v} N_{r}.

It follows that

∏_{r=1}^{v} N_{r} ≠ p,

for any prime p and so f_{G}^{+}(p) = 0. We also note that a multiple (n_{1}, …, n_{e}) only counts in f_{G}^{+}(m) if |μ(n_{1}) ⋯ μ(n_{e})| = 1. Therefore each n_{j} is squarefree. So each factor in

∏_{r=1}^{v} N_{r}  (9)

brings at most a p. So the greatest power of p that can divide (9) is p^{v}. So f_{G}^{+}(p^{α}) = 0 for α > v. Recall that f_{G}^{+}(p^{α}) is equal to the coefficient of z^{α} in Q_{G}^{+}(z). So, by Lemma 3, we note that f_{G}^{+}(p^{α}) depends on α but not on p. Putting all this together we have

∑_{m=1}^{∞} \frac{f_{G}^{+}(m)}{m} = ∏_{p prime} (1 + \frac{f_{G}^{+}(p^{2})}{p^{2}} + … + \frac{f_{G}^{+}(p^{v})}{p^{v}}) < +∞.  (10)

Substituting (10) into (8) completes the proof.

Returning to (7) it is now clear from Lemma 5 that

ρ_{G} = lim_{x→∞} ∑_{1≤n_{1}≤x} ⋯ ∑_{1≤n_{e}≤x} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}}

is absolutely convergent. In fact,

g(x) = x^{v}ρ_{G} + R + O(x^{v−1} log^{d} x),  (11)

where

ρ_{G} = ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} μ(n_{1}) ⋯ μ(n_{e}) ∏_{r=1}^{v} \frac{1}{N_{r}} ,

and

|R| ≤ x^{v−1} ∑_{j=1}^{e} ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{j−1}=1}^{∞} ∑_{n_{j}>x} ∑_{n_{j+1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} .

Now

ρ_{G} = ∑_{m=1}^{∞} \frac{1}{m} ∑_{N_{1}···N_{v}=m} μ(n_{1}) ⋯ μ(n_{e}) = ∑_{m=1}^{∞} \frac{f_{G}(m)}{m}.

We note that f_{G}(m) is multiplicative by Proposition 2. In a similar way to Lemma 5 we have f_{G}(1) = 1, f_{G}(p) = 0 and f_{G}(p^{α}) = 0, for all α > v. Thus, by the multiplicativity,

ρ_{G} = ∑_{m=1}^{∞} \frac{f_{G}(m)}{m} = ∏_{p prime} (1 + \frac{f_{G}(p^{2})}{p^{2}} + … + \frac{f_{G}(p^{v})}{p^{v}}) ,

Therefore, by Lemma 3, we have

ρ_{G} = ∏_{p prime} Q_{G} (\frac{1}{p}) .  (12)

Substituting (12) into (11), it only remains to show that |R| = O(x^{v−1} log^{d} x). We have

|R| ≤ x^{v−1} ∑_{j=1}^{e} ∑_{n_{1}=1}^{∞} ⋯ ∑_{n_{j−1}=1}^{∞} ∑_{n_{j}>x} ∑_{n_{j+1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} .

All terms in the sum on j are analogous; so assuming that the first is the largest, we have

|R| ≤ C_{1}x^{v−1} ∑_{n_{1}>x} ∑_{n_{2}=1}^{∞} ∑_{n_{j+1}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} ,

where C_{1} is a function of e and not x. So it suffices to show that

R_{1} := ∑_{n_{1}>x} ∑_{n_{2}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} |μ(n_{1}) ⋯ μ(n_{e})| ∏_{r=1}^{v} \frac{1}{N_{r}} = O(log^{d} x).  (13)

We treat an edge e_{1} = {r, s} differently from the other edges. For a given (n_{1}, …, n_{e}) of squarefree numbers we have two special N_{r},

N_{r} = lcm(n_{1}, n_{α_{1}}, … n_{α_{k}}), N_{s} = lcm(n_{1}, n_{β_{1}}, … n_{β_{k}}).

We also remark that we may have N_{r} = lcm(n_{1}) or N_{s} = lcm(n_{1}).

For any edge e_{j} with 2 ≤ j ≤ e we define d_{j} = gcd(n_{1}, n_{j}). Since the n_{j} are squarefree, we have

n_{j} = d_{j}n′_{j}, d_{j}|n_{1}, gcd(n_{1}, n′_{j}) = 1.

Then it is clear that

N_{r} = lcm(n_{1}, d_{α_{1}}n′_{α_{1}}, …, d_{α_{k}}n′_{α_{k}}) = n_{1} lcm(n′_{α_{1}}, …, n′_{α_{k}}),
N_{s} = n_{1} lcm(n′_{β_{1}}, …, n′_{β_{l}}).

For any other vertex with t ≠ r and t ≠ s, we have

N_{t} = lcm(n_{t_{1}}, …, n_{t_{m}}) = lcm(d_{t_{1}}n′_{t_{1}}, …, d_{t_{m}}n′_{t_{m}})
= lcm(d_{t_{1}}, …, d_{t_{m}}) lcm(n′_{t_{1}}, …, n′_{t_{m}}),

where m varies with t. Substituting the equations for N_{r}, N_{s} and N_{t} into the definition of R_{1} in (13) we obtain

R_{1} = ∑_{n_{1}>x} ∑_{n_{2}=1}^{∞} ⋯ ∑_{n_{e}=1}^{∞} |μ(n_{1}) ⋯ μ(n_{e})|\frac{1}{N_{r}} \frac{1}{N_{s}} ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{N_{t}}

= ∑_{n_{1}>x} \frac{|μ(n_{1})|}{n_{1}^{2}} ∑_{d_{2}|n_{1}} ⋯ ∑_{d_{e}|n_{1}} ∑_{n′_{2}=1}^{∞} ⋯ ∑_{n′_{e}=1}^{∞} \frac{|μ(n_{2}) ⋯ μ(n_{e})|}{lcm(n′_{α_{1}}, …, n′_{α_{k}}) lcm(n′_{β_{1}}, …, n′_{β_{l}})}

× ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(d_{t_{1}}, …, d_{t_{m}}) lcm(n′_{t_{1}}, …, n′_{t_{m}})}

= ∑_{n_{1}>x} \frac{|μ(n_{1})|}{n_{1}^{2}} ∑_{d_{2}|n_{1}} ⋯ ∑_{d_{e}|n_{1}} ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(d_{t_{1}}, …, d_{t_{m}})}

× ∑_{n′_{2}=1}^{∞} ⋯ ∑_{n′_{e}=1}^{∞} \frac{|μ(d_{2}n′_{2}) ⋯ μ(d_{e}n′_{e})|}{lcm(n′_{α_{1}}, …, n′_{α_{k}}) lcm(n′_{β_{1}}, …, n′_{β_{l}})} ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(n′_{t_{1}}, …, n′_{t_{m}})}

≤ ∑_{n_{1}>x} \frac{|μ(n_{1})|}{n_{1}^{2}} ∑_{d_{2}|n_{1}} ⋯ ∑_{d_{e}|n_{1}} |μ(d_{2}) ⋯ μ(d_{e})| ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(d_{t_{1}}, …, d_{t_{m}})}

× ∑_{n′_{2}=1}^{∞} ⋯ ∑_{n′_{e}=1}^{∞} \frac{|μ(n′_{2}) ⋯ μ(n′_{e})|}{lcm(n′_{α_{1}}, …, n′_{α_{k}}) lcm(n′_{β_{1}}, …, n′_{β_{l}})} ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(n′_{t_{1}}, …, n′_{t_{m}})}.

The product

∑_{n′_{2}=1}^{∞} ⋯ ∑_{n′_{e}=1}^{∞} \frac{|μ(n′_{2}) ⋯ μ(n′_{e})|}{lcm(n′_{α_{1}}, …, n′_{α_{k}}) lcm(n′_{β_{1}}, …, n′_{β_{l}})} ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(n′_{t_{1}}, …, n′_{t_{m}})}

is finite by Lemma 5 (but this time considering the graph G without the edge {r, s}). Thus, for some constant C_{1}, we have

R_{1} ≤ C_{2} ∑_{n_{1}>x} \frac{|μ(n_{1})|}{n_{1}^{2}} ∑_{d_{2}|n_{1}} ⋯ ∑_{d_{e}|n_{1}} |μ(d_{2}) ⋯ μ(d_{e})| ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(d_{t_{1}}, …, d_{t_{m}})}

= C_{2} ∑_{n_{1}>x} \frac{|μ(n_{1})|}{n_{1}^{2}}f_{G,e}(n_{1}),  (14)

where the arithmetic function f_{G,e} is defined as follows.

f_{G,e}(n) = ∑_{d_{2}|n} ⋯ ∑_{d_{e}|n} |μ(d_{2}) ⋯ μ(d_{e})| ∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} \frac{1}{lcm(d_{t_{1}}, …, d_{t_{m}})}.

We note that there is a factor lcm(d_{t_{1}}, …, d_{t_{m}}) for each vertex other than r or s. The function f_{G,e} is a multiplicative function. We have f_{G,e}(p^{k}) = f_{G,e}(p) for any power of a prime p with k ≥ 2, because in the definition of f_{G,e}(p^{k}) only the divisors 1 and p of p^{k} give non-null terms. When n = p we have

f_{G,e}(p) = 1 + \frac{A_{1}}{p} + ⋯ + \frac{A_{v−2}}{p^{v−2}} ,

where A_{i} is the number of ways that

∏_{\begin{matrix}1≤t≤v \\ t≠r, t≠s \end{matrix}} |μ(d_{2}) ⋯ μ(d_{e})| lcm(d_{t_{1}}, …, d_{t_{m}}) = p^{i},

where every divisor in the product d_{h} | n = p can only be 1 or p. Clearly A_{i} ≤ 2^{e−1} do not depend on p, and so there must be a number w, independent of p, such that

f_{G,e}(p^{k}) = f_{G,e}(p) ≤ (1 + \frac{1}{p})^{w} .

Since f_{G,e} is multiplicative we have, for any squarefree n,

f_{G,e}(n) ≤ ∏_{p|n} (1 + \frac{1}{p})^{w} = (\frac{σ(n)}{n})^{w} , |μ(n)| = 1.  (15)

Substituting (15) into (14) yields

R_{1} ≤ C_{2} ∑_{n>x}^{∞} \frac{|μ(n)|}{n^{2}} (\frac{σ(n)}{n})^{w} ≤ C_{2} ∑_{n>x}^{∞} \frac{1}{n^{2}} (\frac{σ(n)}{n})^{w} .

It is well known that σ(n) = O(n log log n) (see, for example, the article by Gronwall [5]), and thus

R_{1} = O (\frac{(log log x)^{w}}{x} ) .  (16)

Comparing (16) with (13) completes the proof of Theorem 1.

4 Calculations

We calculate the asymptotic proportion that 4 random positive integers exhibit ‘square’ pairwise coprimality conditions. That is, 4-tuples with

gcd(a_{1}, a_{2}) = gcd(a_{2}, a_{3}) = gcd(a_{3}, a_{4}) = gcd(a_{4}, a_{1}) = 1.

Here G(V, E) be given by

V = {1, 2, 3, 4}, E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}.

As shown in Theorem 1 and using Section 2,

Q_{G} (\frac{1}{p}) = ∑_{F ⊂E}(−1)^{card(F)} (\frac{1}{p})^{v(F)} ,

where v(F) is the number of non-isolated vertices of F.

Next we examine each F ⊂ E to compute its contribution to Q_{G}(z). This is shown in the following table:

Table 1: Subsets of edges and the polynomial Q_{G}(z)

F ⊂ E  card(F) v(F) term = (−1)^{card(F)}z^{v(F)}
∅  0  0  1
{{1, 2}}, {{2, 3}}, {{3, 4}}, {{4, 1}}  1  2  −4z^{2}

\begin{matrix}\{\{1, 2\}, \{2, 3\}\}, \\ \{\{2, 3\}, \{3, 4\}\}, \\ \{\{3, 4\}, \{4, 1\}\}, \\ \{\{4, 1\}, \{1, 2\}\} \end{matrix}  2  3  4z^{3}

\begin{matrix}\{\{1, 2\}, \{3, 4\}\}, \\ \{\{2, 3\}, \{4, 1\}\}, \end{matrix}  2  4  2z^{4}

\begin{matrix}\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}, \\ \{\{2, 3\}, \{3, 4\}, \{4, 1\}\}, \\ \{\{3, 4\}, \{4, 1\}, \{1, 2\}\}, \\ \{\{4, 1\}, \{1, 2\}, \{2, 3\}\} \end{matrix}  3  4  −4z^{4}

E  4  4  z^{4}
Q_{G}(z) = 1 − 4z^{2} + 4z^{3} − z^{4}

Putting this all together we have

ρ_{G} = ∏_{p prime} (1 − \frac{4}{p^{2}} + \frac{4}{p^{3}} − \frac{1}{p^{4}} ) .

This gives ρ_{G} as an Euler product. As shown in the article by Wrench [13], Euler products such as ρ_{G} can be computed to high precision.

5 Acknowledgement

The authors would like to thank Igor Shparlinski and an anonymous referee for some useful comments. The second author would like to thank the first author and his colleagues for their hospitality during a pleasant visit to Seville. The first author is supported by MINECO grant MTM2012-30748.

References

[1] J. -Y. Cai and E. Bach, On testing for zero polynomials by a set of points with bounded precision, in COCOON 2001, Lect. Notes Comput Sci., Vol. 2108, Springer-Verlag 2001, pp. 473–482.

[2] C. Ding, D. Pei, and A. Salomaa, The Chinese Remainder Theorem, World Scientific, 1996.

[3] J. L. Fernández and P. Fernández, Equidistribution and coprimality. Preprint, 2013,

   available at http://arxiv.org/abs/1310.3802.

[4] T. Freiberg, The probability that 3 positive integers are pairwise noprime, (unpublished manuscript).

[5] T. H. Gronwall, Some asymptotic expressions in the theory of numbers, Trans. Amer. Math. Soc. 14 (1913), 113–122.

[6] R. Heyman, Pairwise non-coprimality of triples. Preprint, 2013, available at

   http://arxiv.org/abs/1309.5578.

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

[8] J. Hu, Pairwise relative primality of positive integers. Preprint, 2014, available at

   http://arxiv.org/abs/1406.3113.

[9] V. J. Katz, A History of Mathematics (Brief Edition), Pearson/Addison-Wesley, 2003.

[10] D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1998.

[11] P. Moree, Counting carefree couples. Preprint, 2014, available at

   http://arxiv.org/abs/math/0510003.

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

[13] J. W. Wrench Jr., Evaluation of Artin’s constant and the twin prime conjecture, Math Comp. 15 (1961), 396–398.

2010 Mathematics Subject Classification: Primary 11N25; Secondary 11N36, 11N37, 11A25. Keywords: pairwise coprimality, arithmetic function.

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

Received April 1 2015; revised versions received September 10 2015; September 16 2015. Published in Journal of Integer Sequences, September 16 2015.

Return to Journal of Integer Sequences home page.