# Arithmetical Functions Associated with the k-ary Divisors of an Integer.

1. Introduction

Let n be a positive integer and denote the set of divisors of n by D(n). The set of unitary divisors of n, denoted by [D.sup.1](n), are the divisors d of n which satisfy D(d) n D(n/d) = {1}; in other words, (d, n/d) = 1. The biunitary divisors of n are the divisors d of n which satisfy [D.sup.1](d) [intersection] [D.sup.1] (n/d). This differs from some definitions of biunitary divisibility in the literature (e.g., ) but is consistent with others (e.g., ). In general, we may define the k-ary divisors of an integer n to be the set

[mathematical expression not reproducible], (1)

where we define the greatest common k-ary divisor of m and n by

[(m, n).sub.k] := max {[D.sup.k] (m) [intersection] [D.sup.k] (n)}. (2)

We write d[|.sub.k]n if d [member of] [D.sup.k](n).

The k-ary divisibility relations as defined above were first introduced by Cohen  and have been studied more recently by Haukkanen  and Steuding et al. . An alternative definition can be seen in Suryanarayana .

One easily verifies the following basic properties: (i)

(i) 1 [member of] [D.sup.k](n) and n [member of] [D.sup.k](n) for all n.

(ii) If n and m are coprime, then [D.sup.k](nm) = [D.sup.k](n) x [D.sup.k](m), where A x B := {ab \ a [member of] A, b [member of] B}.

(iii) If d [member of] [D.sup.k](n),then n/d [member of] [D.sup.k](n).

For example, the set of unitary divisors of a prime power [p.sup.a] are [D.sup.1] ([p.sup.a]) = {1, [p.sup.a]}. On the other hand, the biunitary divisors of a prime power [p.sup.a] are given by D([p.sup.a]) when a is odd and D([p.sup.a]) \ {[p.sup.a/2]} when a is even. We may then form the unitary and biunitary divisors of a positive integer n by "multiplying" the prime-power divisor sets that form the prime decomposition of n.

By viewing the sets [D.sup.k] as representing some of the A-convolutions of Narkiewicz , we may define the k-ary convolution of arithmetic functions f and g:

(f * [sub.k]0)(n) : [summation over (d[|.sub.k]n]) f(d) g(n/d). (3)

The following properties of k-ary convolution can be found in :

(i) The k-ary convolution is commutative.

(ii) The function [iota](n), which takes on value of 1 if n = 1 and 0 otherwise, is the identity under k-ary convolution.

(iii) If an arithmetic function f satisfies f(1) [not equal to] 0, then f possesses a unique inverse under k-ary convolution.

(iv) If f and g are multiplicative functions, then f * [sub.k]g is multiplicative as well.

By choosing f and g appropriately, we may obtain multiplicative k-ary analogues to the following classical functions from number theory in terms of the k-ary convolution:

(i) Let f(n) = g(n) = 1 for all n. Then [[tau].sub.k](n) := (f * [sub.k]g)(n) is the number of k-ary divisors of n.

(ii) Let f(n) = n and g(n) = 1 for all n. Then [[sigma].sub.k](n) := (f * [sub.k]g)(n) is the sum of the k-ary divisors of n.

(iii) Let f(n) = n and g(n) = [[mu].sub.k](n) for all n, where [[mu].sub.k] is the unique inverse of the function U(n) = 1 under the k-ary convolution. Then [[phi].sub.k](n) := (f * [sub.k]g)(n) is the analogue of the Euler totient function.

(iv) Let f(n) = n and g(n) = [absolute value of [[mu].sub.k](n)]. Then [[psi].sub.k](n) := (f * [sub.k]g)(n) is the analogue of the Dedekind [psi]-function.

Note that while [phi](n) counts the totatives of n, in general [psi]k does not count the k-ary totatives of n.

In this paper, we prove results concerning the structure of k-ary divisibility relations and use that to obtain formulae for the number of integers m less than or equal to n which satisfy [(m, n).sub.k] = 1. We then apply this result to obtain asymptotics for the summatory functions of k-ary generalizations of the classical functions mentioned above.

2. The Behavior of k-Ary Divisibility Relations

Let [D.sup.[infinity]](n) be the set of infinitary divisors of n introduced and studied by Cohen [3, 7]. The infinitary divisibility relation can be thought of as the end behavior of the recursion defining the k-ary divisibility relations. It satisfies

(i) All properties of k-ary divisibility relations listed above

(ii) d [member of] [D.sup.[infinity]](n) if and only if [D.sup.[infinity]](d) [intersection] [D.sup.[infinity]](n/d) = {1}

(iii) [D.sup.[infinity]] being transitive; that is, for all n, if d [member of] [D.sup.[infinity]](n), then [D.sup.[infinity]](d) [subset or equal to] [D.sup.[infinity]](n).

Additionally, the following reformulation of Theorem 1 from  characterizes in what sense k-ary divisibility relations "approach" the infinitary divisibility relation as k increases.

Theorem 1. Let k [greater than or equal to] 0 be given, and suppose that n [member of] N is such that, for every prime p, [v.sub.p](n) [less than or equal to] k + 1, where [v.sub.p](n) is the exponent of the prime p in the prime decomposition of n (0 if p does not divide n). Then [D.sup.k](n) = [D.sup.[infinity]](n).

Proof. We proceed by induction on k. We need to only show the result for prime powers [p.sup.a], since by the second property listed above we obtain our theorem by multiplicative construction, akin to the treatment of multiplicative arithmetical functions. Therefore, we may speak of a set prime p and consider [p.sup.a], with a [less than or equal to] k + 1. For k = 0, we have [D.sup.[infinity]](p) = D(p) and [D.sup.[infinity]](1) = D(1).

Now assume that the result holds up to some K-1. Then consider [D.sup.K]([p.sup.a]) = {d [member of] D([p.sup.a]) | [D.sup.K-1](d) [intersection] [D.sup.K-1] ([p.sup.a]/d) = {1}}, with a such that a [less than or equal to] K + 1. Notice that all divisors d of [p.sup.a], except [p.sup.a] itself, satisfy d = [p.sup.b], with b [less than or equal to] K-1. Then, for d [not equal to] [p.sup.a], we have [D.sup.K-1](d) = [D.sup.[infinity]](d) and, for d [not equal to] 1, we have [D.sup.K-1] ([p.sup.a]/d) = [D.sup.[infinity]]([p.sup.a]/d). So, for d not equal to 1 or [p.sup.a], d [member of] [D.sup.K]([p.sup.a]) [??] [D.sup.[infinity]](d) [intersection] [D.sup.[infinity]]([p.sup.a]/d). But 1 and [p.sup.a] are in [D.sup.K]([p.sup.a]) as well, so [D.sup.K]([p.sup.a]) = [D.sup.[infinity]]([p.sup.a]), and by the second property of [D.sup.k] and [D.sup.[infinity]] listed above, we are done.

Theorem 2. For all n [member of] N, k [greater than or equal to] 0, [D.sup.[infinity]](n) [subset or equal to] [D.sup.2k+2](n) [subset or equal to] [D.sup.2k](n), and [D.sup.2k+1](n) [subset or equal to] [D.sup.2k+3](n) [subset or equal to] [D.sup.[infinity]](n).

Proof. We will again use induction. One can immediately verify that [D.sup.[infinity]](n) [subset or equal to] [D.sup.2](n) [subset or equal to] D(n) and [D.sup.1](n) [subset or equal to] [D.sup.3](n) [subset or equal to] [D.sup.[infinity]](n); [D.sup.3]([p.sup.a]) only differs from [D.sup.1]([p.sup.a]) at a =3 and a = 6, where we have [D.sup.3]([p.sup.3]) = [D.sup.[infinity]]([p.sup.3]) and [D.sup.3]([p.sup.6]) = [D.sup.[infinity]](p6). Assuming that the theorem holds up to some K, observe that for each divisor d of n the condition [D.sup.2K+3] (d) [intersection] [D.sup.2K+3] (n/d) = {1} implies that [D.sup.2K+1](d) [intersection] [D.sup.2K+1](n/d) = {1}} on account of [D.sup.2K+1](d) [subset or equal to] [D.sup.2K+3](d) for each d. Then [D.sup.2K+4](n) [subset or equal to] [D.sup.2K+2](n). But then, by the same reasoning, [D.sup.2K+3](n) [subset or equal to] [D.sup.2K+5](n).

To see that [D.sup.[infinity]](n) is ordered according to the theorem, consider the statement [D.sup.[infinity]](n) [subset or equal to] D(n) for all n. Using the argument from above and the fact that [D.sup.[infinity]](n) = {d [member of] D(n) | [D.sup.[infinity]](d) [intersection] [D.sup.[infinity]](n/d) = {1}}, we conclude that, for all k, [D.sup.2k+1] (n) [subset or equal to] [D.sup.[infinity]] (n) [subset or equal to] [D.sup.2k](n) and hence our relations hold.

We observe that when looking at the k-ary divisors of the powers of a specific prime number, there is always an integer after which, for each a, the k-ary divisors of [p.sup.a] will be either [D.sup.2]([p.sup.a]) or [D.sup.1]([p.sup.a]).

Theorem 3. Let k > 2 be given. Then there is an integer [N.sub.k] such that, for all a > [N.sub.k] and all primes p, [D.sup.k]([p.sup.a]) = [D.sup.1]([p.sup.a]) if k is odd, and [D.sup.k]([p.sup.a]) = [D.sup.2]([p.sup.a]) if k is even.

Proof. We note first that, for k = 1 and k = 2, we have that [N.sub.1] = 1 and [N.sub.2] = 3 trivially suffice for bounds. Now assume that such an [N.sub.k] exists for all k = M-1. We consider the cases even M and odd M, respectively.

For even M, take a > 2[N.sub.M-1] and let b [less than or equal to] a/2. Then [D.sup.k]([p.sup.a-b]) [intersection] [D.sup.k]([p.sup.b]) = {1}, since [D.sup.k]([p.sup.a-b]) = [D.sup.1]([p.sup.a-b]) and b < a-b. For 2b = a, we have [p.sup.b] [not member of] [D.sup.M]([p.sup.a]) as desired. Since k-ary divisions are symmetric, this argument holds for b' = a-b as well. We see then that we may take [N.sub.M] = 2[N.sub.M-1] for even M.

For odd M, take a > 3[N.sub.M-1]. Let b be such that 0 [less than or equal to] b [less than or equal to] (2/3)a. Then [D.sup.M-1] ([p.sup.a-b]) [intersection] [D.sup.M-1] ([p.sup.b]) = {1} if [p.sup.b] [member of] [D.sup.M-1] ([p.sup.a-b]). This occurs for all b and a satisfying a [not equal to] 3b. If a = 3b, then b > N[M.sub.-1], so [D.sup.k](pb) = D2(pb). In either case, [D.sup.M-1] ([p.sup.a-b]) [intersection] [D.sup.M-1] ([p.sup.b]) = {1}, so that [D.sup.M-1] ([p.sup.a]) = [D.sup.1] ([p.sup.a]). We then see that we may take [N.sub.M] > 3[N.sub.M-1] for odd M.

Definition 4. We denote by [N.sup.*.sub.k] the least [N.sub.k] for a given k.

Our next section concerns itself with k-ary analogues of some classical results on summatory functions.

3. Summatory Functions

Let k > 0 be given and let f(n) be an arithmetical function constructed as follows:

f(n) := [summation over (d[member of][D.sup.k](n)] g(d)[(n/d).sup.r] > (4)

where r is a positive integer and g(n) is a function such that g(n) = O([n.sup.r-1]). We wish to explore the end behavior of the summatory function of f:

S(f)(x) := [summation over (n[less than or equal to]x)] f (n) (5)

We will employ techniques already used in [7, 8] to derive the result for the infinitary and unitary cases, respectively.

Definition 5. Let k [greater than or equal to] 0 and r > 0. We introduce the following function:

[mathematical expression not reproducible]. (6)

For r = 0, this function counts the number of integers m that are less than x and k-ary coprime to n. It is known that, for k = 0, [[phi].sub.0,0](x, n) = x([phi](n)/n) + O([tau](n)). The summatory functions for [[phi].sub.k,0] maybe broken into the case of even k or odd k, in accordance with whether [D.sup.k](n) [subset or equal to] [D.sup.[infinity]](n) or [D.sup.[infinity]](n) [subset or equal to] [D.sup.k](n).

Theorem 6. Let k > 0 be an integer. Then, for even k, [[phi].sub.k,0](x, n) = x([phi](n)/n) [K.sub.k](n) + O[[??].sub.k](n)[tau](n)), with

[mathematical expression not reproducible] (7)

and

[mathematical expression not reproducible]; (8)

for odd k,

[mathematical expression not reproducible], (9)

with the following:

(i) [[tau].sub.1](n) is the number of elements (divisors) in [D.sup.1](n).

(ii) [[mu].sub.1] (n) is the Mobius function corresponding to [D.sup.1]: [[mu].sub.1](n) = [(-1).sup.[omega](n)] where [omega](n) is the number of distinct prime factors of n, counted without multiplicity.

(iii)

[mathematical expression not reproducible]. (10)

(iv)

[mathematical expression not reproducible]. (11)

Proof. First note that [K.sub.k](n) and [[??].sub.k](n) are well defined: by Theorem 3, for even k, the number of integers m satisfying the condition [(m, n).sub.k] = 1 for a given integer n must be finite, whereas for odd k and for each maximal prime power dividing n, the number of integers satisfying [mathematical expression not reproducible] must be finite, and hence the product over sums of prime powers k-ary-coprime to n must be finite. Therefore, the sums are finite. We will prove the result for even k first.

Let k be even and consider

[mathematical expression not reproducible] (12)

where

[mathematical expression not reproducible] (13)

is the square-free part of the integer [m.sup.2], from . Here we have split each m uniquely into a part that has no common divisor with n and a part whose prime decomposition uses only the primes of n (note that there is no restriction on the prime powers used; e.g., [m.sub.2] = [n.sup.2] may appear in this decomposition for large enough x).

We proceed:

[mathematical expression not reproducible], (14)

using the fact that the behavior of [[phi].sub.0,0](x, n) is known. Pulling out the constants with respect to the sum then immediately gives us our result.

For odd k, we proceed in a different manner:

[mathematical expression not reproducible]. (15)

We then analyze the term

[mathematical expression not reproducible]: (16)

We wish to split m into [m.sub.1][m.sub.2] as before. However, this should be done in such a way as to be both unique and useful in dealing with the requirement that [(m,n).sub.k] > 1. For each divisor d of n, let m = [m.sub.1][m.sub.2], with [mathematical expression not reproducible]. We invoke the principle of inclusion-exclusion, enabling us to write

[mathematical expression not reproducible], (17)

where

[mathematical expression not reproducible], (18)

with [p.sub.l] being an appropriately indexed set of primes, and we use the fact that, for d = 1, the sum is 0.

This simplifies to

[mathematical expression not reproducible], (19)

and our result follows.

We let [L.sub.k](n) be the coefficient appearing in front of the "x" term in [[phi].sub.k,0](x, n) and let [E.sub.k](n) be the function in the error term, so that [[phi].sub.k,0](x, n) = x[L.sub.k](n) + O(E(n)).

Remark 7. Regarding the function [[??].sub.k](n), we may estimate that [[??].sub.k](n) [less than or equal to] [N.sup.*.sub.k] through the following reasoning: for even k, consider a [less than or equal to] [N.sup.*.sub.k] (see Definition 4). If b [less than or equal to] [N.sup.*.sub.k], then [([p.sup.b], [p.sup.a]).sub.k] = 1 for at most [N.sup.*.sub.k]-1 such b (excluding b = a). If b > [N.sup.*.sub.k], then [([p.sup.b], [p.sup.a]).sup.k] = 1 for at most 1 such b (the case of [D.sup.k]([p.sup.a]) = {1, [p.sup.a]} and b = 2a > [N.sup.*.sub.k], as here [D.sup.k]([p.sup.b]) = [D.sup.2]([p.sup.b])). Thus, [[??].sup.k]([p.sup.a]) [less than or equal to] [N.sup.*.sub.k] for a [less than or equal to] [N.sup.*.sub.k]. For a > [N.sup.*.sub.k], [D.sup.k]([p.sup.a]) = [D.sup.2]([p.sup.a]), and so [([p.sup.b], [p.sup.a]).sub.k] = 1 for at most 2 such b by the above comments.

For odd k, a similar argument gives [([p.sup.b], [p.sup.a]).sub.k] > 1 for at most [N.sup.*.sub.k] choices of b when a [less than or equal to] [N.sup.*.sub.k], and precisely 2 choices of b when a > [N.sup.*.sub.k]; namely, b = 0 and b = a. So [N.sup.*.sub.k] bounds [[tau].sub.k] ([p.sup.a]) for all a.

Now, [[tau].sub.k](p) = 2 for all k, and for some [mathematical expression not reproducible]. Thus, since [[tau].sub.k]([p.sup.a]) [greater than or equal to] 2 for all a > 0, we have that [mathematical expression not reproducible]. In particular, there is a least [B.sub.k] such that, for all n, [mathematical expression not reproducible]. We will use this [B.sub.k] in our asymptotic estimates.

We immediately get the following result as a consequence of Theorem 6.

Corollary 8. [[phi].sub.k,r](x, n) = ([x.sup.r]/(r + 1)) [[phi].sub.k,0](x, n) for r [member of] N.

Proof. The case r = 0 is trivially true. We prove for each r > 0 using Stieltjes Integration. Then

[mathematical expression not reproducible],

where the error term from the integral is absorbed by O([x.sup.r][E.sub.k](n)).

Theorem 9. Let k [greater than or equal to] 0. Suppose that an arithmetical function f is of the form

f(n) = [summation over (d[|.sub.k]n)] g(d) [(n/d).sup.r], (21)

with k > 0 and r [member of] N and g(n) is O([n.sup.s]), with s [less than or equal to] r-1. Then

[mathematical expression not reproducible] (22)

Proof. Let k, r, and 5 be given. Then

[mathematical expression not reproducible]. (23)

By our remark above, we may find [B.sub.k] such that [mathematical expression not reproducible] for all n, which enables us to estimate

[mathematical expression not reproducible], (24)

where we use the fact that g is O([n.sup.s]) with s [less than or equal to] r-1. Also,

[mathematical expression not reproducible], (25)

and since g is O([n.sup.s]) and [L.sub.k](n) is bounded, the infinite sums converge, but

[x.sup.r+1]/r + 1 [summation over (n>x)] = g(n) [L.sub.k](n)/[n.sup.r+1] = O ([x.sup.s+1]), (26)

and s < r, so this is absorbed into our error term and we have our result.

Note that, for each k and for all [epsilon] > 0, we may state our error term for the summatory function as O([x.sup.r+[epsilon]), where the multiplicative constant implied by the Big-Oh notation depends only on [member of] and k. This enables us to achieve roughly the same error as Cohen , albeit not as asymptotically strong as [mathematical expression not reproducible]. However, as k tends to infinity, our error becomes unbounded, and so we cannot achieve Cohen's result for the infinitary case.

We recall that [[mu].sub.k], the k-ary analogue of the Mobius function, is defined recursively via

[mathematical expression not reproducible], (27)

which is extended to all n by making [[mu].sub.k] multiplicative. We then have the following.

Lemma 10. Let k be given. Then there is a constant [C.sub.k] depending only on k such that, for each k, [mathematical expression not reproducible].

Proof. By Theorem 3, for each prime p and each k, there is an [N.sup.*.sub.k] that ensures [D.sup.k]([p.sup.a]) = [D.sup.1]([p.sup.a]) or [D.sup.2]([p.sup.a]), depending on the parity of k, for all a > [N.sup.*.sub.k]. The values of [absolute value of [[mu].sub.k] ([p.sup.a])] for a [less than or equal to] 2[N.sup.*.sub.k] are finite, being generated from a finite recursion. For odd k with a > [N.sup.*.sub.k], [[mu].sub.k] ([p.sup.a]) = -1. For even k and even a, with a > 2[N.sup.*.sub.k] + 1,

[mathematical expression not reproducible], (28)

since [D.sup.k]([p.sup.a]) = [D.sup.2]([p.sup.a]) and [D.sup.k]([p.sup.a-1]) = [D.sup.2]([p.sup.a-1]) = D([p.sup.a-1]), as a -1 is odd. But

[mathematical expression not reproducible], (29)

so [[mu].sub.k]([p.sub.a] = [[mu].sub.k]([p.sup.a/2]. Also,

[mathematical expression not reproducible], (30)

so

[[mu].sub.k]([p.sub.a]) = [[mu].sub.k]([p.sub.a/2]) = -[[mu].sub.k]([p.sub.a+1]) (31)

for even a. Hence, [[mu].sub.k]([p.sub.a]) is bounded in absolute value for each k-call this bound [mathematical expression not reproducible] and we are done.

We will analyze the summatory functions for the k-ary analogues of several well-known families of arithmetical functions:

(i) The k-ary divisor sum functions:

[[sigma].sub.k,r] (n) := [summation over d[|.sub.k]n] [d.sup.r] (32)

(ii) The k-ary Jordan totient functions:

[J.sub.k,r] (n) [summation over d[|.sub.k]n] [[mu].sub.k] (n/d) [d.sup.r] (33)

(iii) The k-ary Dedekind functions:

[[psi].sub.k,r] (n) := [summation over d[|.sub.k]n] [absolute value of [[mu].sub.k] (n/d)] [d.sup.r] (34)

Here r denotes a positive integer. By Lemma 10, we may apply Theorem 9 to the Jordan and Dedekind functions of order r > 0 without issue, since [[mu].sub.k](n) is logarithmic in n; the summatory functions for the divisor sum functions carry no special restriction on r aside from it being a positive integer:

(i)

[mathematical expression not reproducible] (35)

(ii)

[mathematical expression not reproducible] (36)

(iii)

[mathematical expression not reproducible] (37)

By Theorems 2 and 3, for each n, the sequence [{[L.sub.2k](n)}.sup.[infinity].sub.k=0] (resp., [{[L.sub.2k+1](n)}.sup.[infinity].sub.k=0]) is monotonically increasing (resp., decreasing). Both sequences must have the same limit, [L.sub.[infinity]](n), which one can identify with the function [K.sub.[infinity]](n) from Cohen's manuscript. However, we cannot obtain the function [[phi].sub.[infinity],0] (x, n) via a limit as k tends to infinity of [[phi].sub.k,0] (x, n), as the error term grows without bound in fc. A new approach will likely be needed in order to unify the infinite case with the finite cases.

https://doi.org/10.1155/2018/9349245

Data Availability

All data used either was obtained via the cited sources or is derived explicitly from first principles.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

The authors would like to acknowledge the Department of Mathematical Sciences at The University of Texas at Dallas for providing them with funding for this endeavor. They would also like to thank Dr. Paul Stanford for his numerous revisions and for inspiring and teaching them all.

References

 P. Haukkanen, "Basic properties of the bi-unitary convolution and the semi-unitary convolution," Indian Journal of Mathematics, vol. 40, no. 3, pp. 305-315, 1998.

 P. Haukkanen, "On the k-ary Convolution of Arithmetical Functions," The Fibonacci Quarterly, vol. 38, no. 5, pp. 440-445, 2000.

 G. L. Cohen, "On an integer's infinitary divisors," Mathematics of Computation, vol. 54, no. 189, pp. 395-411, 1990.

 R. Steuding, J. Steuding, and L. Toth, "A modified Mobius [mu]-function. Rendiconti del Circolo Matematico di Palermo," Rendiconti del Circolo Matematico di Palermo Serie II, vol. 60, no. 1-2, pp. 13-21, 2011.

 D. Suryanarayana, "The number of k-ary divisors of an integer," Monatshefte fUr Mathematik, vol. 72, pp. 445-450, 1968.

 W. Narkiewicz, "On a class of arithmetical convolutions," Colloquium Mathematicum, vol. 10, pp. 81-94, 1963.

 G. L. Cohen and J. Hagis, "Arithmetic functions associated with the infinitary divisors of an integer," International Journal of Mathematics and Mathematical Sciences, vol. 16, no. 2, pp. 373-383, 1993.

 E. Cohen, "Arithmetical functions associated with the unitary divisors of an integer," Mathematische Zeitschrift, vol. 74, pp. 66-80, 1960.

Joseph Vade Burnett (iD), Sam Grayson, Zachary Sullivan, Richard Van Natta, and Luke Bang

The University of Texas at Dallas, 800 W Campbell Rd, Richardson, TX, USA