Extremal Orders of Certain Functions Associated with Regular Integers (mod n)

Brăduţ Apostol “Spiru Haret” Pedagogical High School 1 Timotei Cipariu St. RO — 620004 Focşani Romania

                   apo brad@yahoo.com

Lucian Petrescu “Henri Coandă” Technical College 2 Tineretului St. RO — 820235 Tulcea Romania

               petrescuandreea@yahoo.com

Abstract

Let V (n) denote the number of positive regular integers (mod n) that are ≤ n, and let V_{k}(n) be a multidimensional generalization of the arithmetic function V (n). We find the Dirichlet series of V_{k}(n) and give the extremal orders of some totients involving arithmetic functions which generalize the sum-of-divisors function and the Dedekind function. We also give the extremal orders of other totients regarding arithmetic functions which generalize the sum of the unitary divisors of n and the unitary function corresponding to ϕ(n), the Euler function. Finally, we study extremal orders of some compositions, involving the functions mentioned previously.

1 Introduction

Let n > 1 be an integer. An integer a is called regular (mod n) if there exists an integer x such that a^{2}x ≡ a (mod n) (sequence \underline{A143869} in Sloane’s Encyclopedia of Integer Sequences). Several authors investigated properties of regular integers (mod n). Alkam and Osba [1], using ring-theoretic considerations, rediscovered some of the statements proved by Morgado [6, 7], who showed that a > 1 is regular (mod n) if and only if gcd(a, n) is a unitary divisor of n. Tóth [15] gave direct proofs of some properties, because the proofs of [6, 7] were lengthy and those of [1] were ring-theoretical.

Let Reg_{n} = {a : 1 ≤ a ≤ n and a is regular (mod n)}, and V (n) = #Reg_{n}. The function V is multiplicative and V (p^{α}) = ϕ(p^{α}) + 1 = p^{α} − p^{α−1} + 1, where ϕ is the Euler function. Consequently, V (n) = ∑_{d∥n} ϕ(d), for every n ≥ 1, where d ∥ n means that d is a unitary divisor of n, that is, d | n and gcd(d, \frac{n}{d}) = 1. Also ϕ(n) < V (n) ≤ n, for every n > 1, and V (n) = n if and only if n is a squarefree; see [7, 15, 1]. Thus, the function V (n) is an analogue of the Euler function ϕ(n). The function ϕ(n) is the sequence \underline{A000010} in Sloane’s On-Line Encyclopedia of Integer Sequences. Also, the function V (n) is the sequence \underline{A055653}; see [12].

Apostol and Tóth [4] considered the multidimensional generalization of the function V (n), V_{k}(n), where k ≥ 1 is a fixed integer. The function V_{k}(n) is multiplicative and V_{k}(p^{α}) = ϕ_{k}(p^{α}) + 1 = p^{αk} − p^{(α−1)k} + 1, where ϕ_{k} is the Jordan function of order k. Consequently, V_{k}(n) = ∑_{d∥n} ϕ_{k}(d), for every n ≥ 1. Also ϕ_{k}(n) < V_{k}(n) ≤ n^{k}, for every n > 1 and V_{k}(n) = n^{k} if and only if n is squarefree; see [4].

Tóth [15] proved results concerning the minimal and maximal orders of the functions V (n) and V (n)/ϕ(n). Alkam and Osba [1] investigated the minimal order of V (n). Sándor and Tóth [10] and Apostol [2] studied the extremal orders of compositions of certain functions.

In Section 2 we present some notation and results involving arithmetical functions. Section 3 is devoted to the study of the Dirichlet series of V_{k}(n). Extremal orders of the function V_{k}(n) in connection with σ_{k}(n) and ψ_{k}(n) are given in Section 4.

In Section 5 we prove some results regarding V_{k}(n) and unitary analogues of the functions σ_{k}(n) and ϕ_{k}(n).

In Section 6 we give the extremal orders of some compositions of functions from above. Section 7 provides other limits of compositions of arithmetical functions. We also present

some open problems regarding extremal orders of these compositions.

2 Preliminaries

In what follows let n = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} > 1 be a positive integer and let k ≥ 1 be an integer. Throughout the paper we will use the following notation:

• p_{1}, p_{2}, … — the sequence of the primes;

• σ_{k}(n) — the generalization of σ(n), defined by σ_{k}(n) = ∏_{i=1}^{r} \frac{p_{i}^{(α_{i}+1)k}−1}{p_{i}^{k}−1} ; • ψ_{k}(n) — the generalization of ψ(n), defined by ψ_{k}(n) = n^{k} ∏_{p|n}(1 + \frac{1}{p^{k}}) ;

• ζ(s) — the Riemann zeta function, ζ(s) = ∏_{p}(1 − \frac{1}{p^{s}} )^{−1}, s = σ + it ∈ ℂ and σ > 1;

• ϕ(n) — the Euler function, ϕ(n) = n ∏_{p|n}(1 − \frac{1}{p});

• ϕ_{k}(n) — the Jordan function of order k, ϕ_{k}(n) = n^{k} ∏_{p|n}(1 − \frac{1}{p^{k}} );

• γ — the Euler constant, γ = lim_{n→∞}(1 + \frac{1}{2} + … + \frac{1}{n} − log n);

• ϕ^{∗}(n) — the unitary analogue of ϕ(n), ϕ^{∗}(n) = ∏_{i=1}^{k}(p_{i}^{α_{i}} − 1);

• σ^{∗}(n) — the unitary analogue of σ(n), σ^{∗}(n) = ∏_{i=1}^{k}(p_{i}^{α_{i}} + 1).

For other arithmetic functions defined by regular integers modulo n we refer to the papers [5, 14].

Let f(n) be a nonnegative real-valued multiplicative arithmetic function. Let

L = L(f) := lim sup_{n→∞} \frac{f(n)}{log log n}

and

ρ(p) = ρ(p, f) := sup_{α≥0} f(p^{α})

for primes p, and consider the product R = R(f) := ∏_{p}(1 − \frac{1}{p})ρ(p).

In order to prove the properties below we apply the following results:

Lemma 1. (Tóth and Wirsing [16, Corollary 1]). If f is a nonnegative real-valued multiplicative arithmetic function such that for each prime p,

(i) ρ(p) = sup_{α≥0}(f(p^{α})) ≤ (1 − \frac{1}{p})^{−1}, and

(ii) there is an exponent e_{p} = p^{o(1)} ∈ ℕ satisfying f(p^{e_{p}}) ≥ 1 + \frac{1}{p},

then lim sup_{n→∞} \frac{f(n)}{log log n} = e^{γ} ∏_{p}(1 − \frac{1}{p})ρ(p).

Lemma 2. (Tóth and Wirsing [16, Theorem 1]). Suppose that ρ(p) < ∞ for all primes p and the product R converges unconditionally (i.e., irrespectively of order), improper limits being allowed, then L ≤ e^{γ}R.

Lemma 3. (Tóth and Wirsing [16, Theorem 3]). Suppose that ρ(p) < ∞ for all primes p, that for each prime p there is an exponent e_{p} = p^{o(1)} ∈ ℕ such that ∏_{p} f(p^{e_{p}})ρ(p)^{−1} > 0 and that the product R converges, improper limits being allowed. Then L ≥ e^{γ}R.

3 Dirichlet series of V_{k}(n)

Apostol and Petrescu [3] studied the Dirichlet series of V_{1}(n) := V (n). In what follows we give the Dirichlet series of V_{k}(n) for k ≥ 2 and some results involving the Möbius function. Proposition 4. For every s = σ + it ∈ ℂ with σ > k + 1,

∑_{n≥1} \frac{V_{k}(n)}{n^{s}} = ζ(s − k)ζ(s) ∏_{p}(1 − \frac{p^{2s−k} + p^{s} − p^{s−k}}{p^{3s−k}} ).

Proof. Let f(n) = \frac{V_{k}(n)}{n^{s}}. We have

∑_{n≥1} |f(n)| ≤ ∑_{n≥1} \frac{1}{n^{σ−k}} < ∞,

so the series ∑_{n≥1} \frac{V_{k}(n)}{n^{s}} converges absolutely for σ > k + 1. Since V_{k} is multiplicative,

∑_{n≥1} \frac{V_{k}(n)}{n^{s}} = ∏_{p} \frac{1}{1 − \frac{1}{p^{s−k}}} · ∏_{p} \frac{1}{1 − \frac{1}{p^{s}}} · ∏_{p}(1 − \frac{p^{2s−k} + p^{s} − p^{s−k}}{p^{3s−k}} ),

and the claim follows. Corollary 5. Let s = σ + it ∈ ℂ, σ > k + 1. Then

∑_{n≥1} \frac{μ(n)V_{k}(n)}{n^{s}} = ∏_{p}(1 − \frac{1}{p^{s−k}} ) = \frac{1}{ζ(s − k)}.

Also,

∑_{n≥1} \frac{|μ(n)|V_{k}(n)}{n^{s}} = ∏_{p}(1 + \frac{1}{p^{s−k}} ) = \frac{ζ(s − k)}{ζ(2s − 2k)}.

Proof. Forf(n) = \frac{μ(n)V_{k}(n)}{n^{s}} the series ∑_{n≥1}|f(n)| converges absolutely, so

∑_{n≥1} \frac{μ(n)V_{k}(n)}{n^{s}} = ∏_{p}(1 − \frac{1}{p^{s−k}} ) = \frac{1}{ζ(s − k)}.

For the second assertion take f(n) = \frac{|μ(n)|V_{k}(n)}{n^{s}}.

4 Extremal orders concerning classical generalized arith-

metic functions

For the quotient \frac{σ_{k}(n)}{V_{k}(n)}, we notice that \frac{σ_{k}(n)}{V_{k}(n)} ≥ 1 for every n ≥ 1. Since

lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{σ_{k}(p)}{V_{k}(p)} = lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{p^{k} + 1}{p^{k}} = 1,

we get

lim inf_{n→∞} \frac{σ_{k}(n)}{V_{k}(n)} = 1;

hence the minimal order of \frac{σ_{k}(n)}{V_{k}(n)} is 1. Now consider the quotient

\frac{ψ_{k}(n)}{V_{k}(n)}.

Since

\frac{ψ_{k}(n)}{V_{k}(n)} ≥ 1

for every n ≥ 1 and

\frac{ψ_{k}(p)}{V_{k}(p)} = \frac{p^{k} + 1}{p^{k}}

for every prime p, it is immediate that

lim inf_{n→∞} \frac{ψ_{k}(n)}{V_{k}(n)} = 1.

Thus, the minimal order of \frac{ψ_{k}(n)}{V_{k}(n)} is 1. It is known that

lim sup_{n→∞} \frac{σ(n)}{V (n)(log log n)^{2}} = e^{2γ}

and

lim sup_{n→∞} \frac{ψ(n)}{V (n)(log log n)^{2}} = \frac{6}{π^{2}} e^{2γ};

see [2]. Proposition 6 shows that the maximal order of \frac{σ_{k}(n)}{V_{k}(n)} and \frac{ψ_{k}(n)}{V_{k}(n)} is \frac{6}{π^{2}} e^{2γ}(log log n)^{2}. Proposition 6. For k ≥ 2,

lim sup_{n→∞} \frac{σ_{k}(n)}{V_{k}(n)(log log n)^{2}} = lim sup_{n→∞} \frac{ψ_{k}(n)}{V_{k}(n)(log log n)^{2}} = \frac{6}{π^{2}} e^{2γ}.

Proof. Take f(n) = \sqrt{\frac{σ_{k}(n)}{V_{k}(n)}}. Then

f(p^{α}) = \sqrt{\frac{p^{(α+1)k} − 1}{(p^{k} − 1)(p^{αk} − p^{(α−1)k} + 1)}} ≤ \sqrt{\frac{p + 1}{p − 1}} = ρ(p) < (1 − \frac{1}{p})^{−1}

and

f(p^{2}) = \sqrt{\frac{p^{3k} − 1}{(p^{k} − 1)(p^{2k} − p^{k} + 1)}} ≥ 1 + \frac{1}{p}

for every prime p, so (ii) in Lemma 1 is satisfied. We obtain

lim sup_{n→∞} \frac{\sqrt{σ_{k}(n)}}{\sqrt{V_{k}(n)} log log n} = ∏_{p} \sqrt{1 − \frac{1}{p^{2}}} e^{γ} = \sqrt{\frac{6}{π^{2}}} e^{γ},

so

lim sup_{n→∞} \frac{σ_{k}(n)}{V_{k}(n)(log log n)^{2}} = \frac{6}{π^{2}} e^{2γ}.

Since ψ_{k}(n) ≤ σ_{k}(n) and for the primes p we have ψ_{k}(p) = σ_{k}(p) = p^{k} + 1, the result for \frac{ψ_{k}(n)}{V_{k}(n)(log log n)^{2}} follows from the previous one.

5 Extremal orders concerning unitary analogues of σ_{k} and ϕ_{k}

In what follows we consider the functions σ_{k}^{∗}(n) and ϕ_{k}^{∗}(n), representing the generalizations for the sum of the unitary divisors of n and the unitary analogue Euler function, respectively. Let k ≥ 1 be a fixed integer. We have σ_{k}^{∗}(n) = ∑_{d∥n} d^{k} and σ_{k}^{∗}(p^{α}) = p^{αk} + 1. Also,

ϕ_{k}^{∗}(n) := ∑_{gcd(a_{1},...,a_{k})∈\{1,2,...,n\}^{k} gcd(gcd(a_{1},a_{2},...,a_{k}),n)_{∗}=1} 1 = ∑_{d∥n} d^{k}μ^{∗}(\frac{n}{d}),

and hence ϕ_{k}^{∗}(p^{α}) = p^{αk} − 1. Note that

gcd(a, b)_{∗} = max{d : d|a, d ∥ b}

and μ^{∗}(n) is the unitary analogue of the Möbius function, given by μ^{∗}(n) = (−1)^{ω(n)}, where ω(n) is the number of distinct prime factors of n. The functions σ_{k}^{∗}(n) and ϕ_{k}^{∗}(n) are multiplicative. Let n = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} be the prime factorisation of n > 1. We obtain

ϕ_{k}^{∗}(n) = (p_{1}^{α_{1}k} − 1) ⋯ (p_{r}^{α_{r}k} − 1) and σ_{k}^{∗}(n) = (p_{1}^{α_{1}k} + 1) ⋯ (p_{r}^{α_{r}k} + 1).

Observe that σ_{k}^{∗}(n) = σ_{k}(n) and ϕ_{k}^{∗}(n) = ϕ_{k}(n) for all squarefree n. Furthermore, for every n ≥ 1,

ϕ_{k}(n) ≤ ϕ_{k}^{∗}(n) ≤ n^{k} ≤ σ_{k}^{∗}(n) ≤ σ_{k}(n).

Recall that an integer n > 1 is called powerful if it is divisible by the square of each of its prime factors. A powerful integer is also called a squarefull integer. We give extremal orders for the quotients \frac{σ_{k}^{∗}(n)}{V_{k}(n)} and \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)}, the minimal order of \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)} being studied for powerful

numbers. Since \frac{σ_{k}^{∗}(n)}{V_{k}(n)} ≥ 1 for every n ≥ 1 and lim_{p→∞} \frac{σ_{k}^{∗}(p)}{V_{k}(p)} = lim_{p→∞} \frac{p^{k}+1}{p^{k}} = 1 for prime

numbers p, it follows that lim inf_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n)} = 1.

If n is powerful, it is easy to see that \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)} ≥ 1, taking into account that \frac{ϕ_{k}^{∗}(p^{α})}{V_{k}(p^{α})} ≥ 1 for α ≥ 2. For prime numbers p, we notice that

lim_{p→∞} \frac{ϕ_{k}^{∗}(p^{2})}{V_{k}(p^{2})} = lim_{p→∞} \frac{p^{2k} − 1}{p^{2k} − p^{k} + 1} = 1,

which implies that

lim inf_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)} = 1,

so the minimal order of \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)} is 1.

For the maximal orders of these quotients we have

Proposition 7. For k ≥ 1,

lim sup_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n) log log n} = lim sup_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n) log log n} = e^{γ}.

Proof. Take f(n) = \frac{σ_{k}^{∗}(n)}{V_{k}(n)} in Lemma 2, which is a nonnegative real-valued multiplicative arithmetic function. We have

f(p^{α}) = \frac{p^{αk} + 1}{p^{αk} − p^{(α−1)k} + 1} ≤ (1 − \frac{1}{p})^{−1} = ρ(p) < ∞

and R = 1, so

lim sup_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n) log log n} ≤ e^{γ}.

Now let g(n) = \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)}. Here

g(p^{α}) = \frac{p^{αk} − 1}{p^{αk} − p^{(α−1)k} + 1} ≤ (1 − \frac{1}{p})^{−1} = ρ(p),

and

R = ∏_{p} g(p^{1})(ρ(p))^{−1} = ∏_{p}(p^{k} + 1) · \frac{p − 1}{p} > 0.

Hence, by Lemma 3 we have

lim sup_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n) log log n} ≥ e^{γ}.

It is obvious that ϕ_{k}^{∗}(n) ≤ σ_{k}^{∗}(n) for every n ≥ 1. We obtain

e^{γ} ≤ lim sup_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n) log log n} ≤ lim sup_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n) log log n} ≤ e^{γ},

which shows that

lim sup_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n) log log n} = lim sup_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n) log log n} = e^{γ},

as desired.

Corollary 8. The maximal order of both \frac{σ_{k}^{∗}(n)}{V_{k}(n)} and \frac{ϕ_{k}^{∗}(n)}{V_{k}(n)} is e^{γ} log log n.

6 Extremal orders regarding compositions of arithmetical functions

We now move to the study of extremal orders of some composite arithmetic functions. We start with V_{k}(V_{k}(n)) and ϕ_{k}(V_{k}(n)).

We know that V_{k}(n) ≤ n^{k} for every n ≥ 1, so

\frac{V_{k}(V_{k}(n))}{n^{k^{2}}} ≤ \frac{(V_{k}(n))^{k}}{n^{k^{2}}} ≤ \frac{(n^{k})^{k}}{n^{k^{2}}} = 1

and

lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{V_{k}(V_{k}(p))}{p^{k^{2}}} = lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{V_{k}(p^{k})}{p^{k^{2}}} = lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{p^{k^{2}} − p^{(k−1)k} + 1}{p^{k^{2}}} = 1,

so the maximal order of V_{k}(V_{k}(n)) is n^{k^{2}}. Since ϕ_{k}(n) ≤ n^{k} and V_{k}(n) ≤ n^{k} for any n ≥ 1, we

have \frac{ϕ_{k}(V_{k}(n))}{n^{k^{2}}} ≤ \frac{(V_{k}(n))^{k}}{n^{k^{2}}} ≤ 1. But lim\begin{matrix}p→∞ \\ p prime \end{matrix} \frac{ϕ_{k}(V_{k}(p))}{p^{k^{2}}} = lim_{p→∞} \frac{p^{k^{2}}−p^{(k−1)k}}{p^{k^{2}}} = 1, so the maximal

order of ϕ_{k}(V_{k}(n)) is n^{k^{2}}.

The maximal order of V (ϕ(n)) was investigated in [2]. Using the general idea of that proof, we show

Proposition 9. The maximal order of V_{k}(ϕ_{k}(n)) is n^{k^{2}}.

Proof. We will use Linnik’s theorem which states that if gcd(t, ℓ) = 1, then there exists a prime p such that p ≡ ℓ (mod t) and p ≪ t^{c}, where c is a constant (one can take c ≤ 11).

Let A = ∏\begin{matrix}k<p≤x \\ p prime \end{matrix} p. Since gcd(A^{2}, A + 1) = 1, by Linnik’s theorem there is a prime

number q such that q ≡ A + 1 (mod A^{2}) and q ≪ (A^{2})^{c} = A^{2c}, where c satisfies c ≤ 11. Also, q^{k} ≡ kA + 1 (mod A^{2}). Let q be the least prime satisfying the above condition. We have ϕ_{k}(q) = q^{k} − 1 = AB, where B = k + sA, for some s. Thus gcd(A, B) = 1, so B is free of prime factors ≤ x and > k. Since V_{k}(n) is multiplicative, we have

\frac{V_{k}(ϕ_{k}(q))}{q^{k^{2}}} = \frac{V_{k}(AB)}{(AB + 1)^{k}} = \frac{V_{k}(A)}{A^{k}} · \frac{V_{k}(B)}{B^{k}} · \frac{(AB)^{k}}{(AB + 1)^{k}} .  (1)

Here \frac{(AB)^{k}}{(AB+1)^{k}} → 1 as x → ∞, so it is sufficient to study \frac{V_{k}(A)}{A^{k}} and \frac{V_{k}(B)}{B^{k}}. Clearly,

\frac{V_{k}(A)}{A^{k}} = 1.  (2)

We have A = ∏_{k<p≤x} p ≤ ∏_{p≤x} p = e^{O(x)}. Since B ≪ A^{10} we obtain B ≪ e^{O(x)}, so

log B ≪ x.  (3)

If B = ∏_{i=1}^{r} q_{i}^{b_{i}} is the prime factorization of B, we obtain, taking into account that k ≥ 1 is a fixed integer, that log B = ∑_{i=1}^{r} b_{i} log q_{i} > (log x) ∑_{i=1}^{r} b_{i} for sufficiently large x. But ∑_{i=1}^{r} b_{i} ≥ r, so log B > k log x, implying that r < \frac{log B}{log x} ≪ \frac{x}{log x} (by (3)). Since

\frac{V_{k}(B)}{B^{k}} > ∏_{i=1}^{r}(1 − \frac{1}{q_{i}^{k}} ) ≥ ∏_{i=1}^{r}(1 − \frac{1}{q_{i}} ) > (1 − \frac{1}{x})^{r} ≥ (1 − \frac{1}{x})^{O( \frac{x}{log x})},

We obtain

\frac{V_{k}(B)}{B^{k}} > 1 + O(\frac{1}{log x}).  (4)

By (1), (2), (4) and \frac{(AB)^{k}}{(AB+1)^{k}} → 1 as x → ∞, we obtain

\frac{V_{k}(ϕ_{k}(q))}{q^{k^{2}}} > 1 + O(\frac{1}{log x}).  (5)

By relation (5), and since \frac{V_{k}(ϕ_{k}(n))}{n^{k^{2}}} ≤ \frac{(ϕ_{k}(n))^{k}}{n^{k^{2}}} ≤ 1, the claim follows.

The maximal order of V (ϕ^{∗}(n)) is n (see [2]). For the maximal order of V_{k}(ϕ^{∗}(n)) we give

Proposition 10.

lim sup_{n→∞} \frac{V_{k}(ϕ^{∗}(n))}{n^{k}} = 1.

Proof. We apply the following lemma:

If a is an integer, a > 1, p is a prime number and f(n) is an arithmetical function satisfying ϕ(n) ≤ f(n) ≤ σ(n), one has

lim_{p→∞} \frac{f(N(a, p))}{N(a, p)} = 1,  (6)

where N(a, p) = \frac{a^{p}−1}{a−1} (see, e.g., Suryanarayana [13]).

Since ϕ^{∗}(n) ≤ n, it follows that V_{k}(ϕ^{∗}(n)) ≤ (ϕ^{∗}(n))^{k} ≤ n^{k}, so

\frac{\sqrt[k]{V_{k}(ϕ^{∗}(n))}}{n} ≤ 1.  (7)

Obviously, \sqrt[k]{V_{k}(n)} meets the conditions of the lemma. We have

lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{\sqrt[k]{V_{k}(ϕ^{∗}(2^{p})})}{2^{p}} = lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{\sqrt[k]{V_{k}(2^{p} − 1)}}{2^{p} − 1} = lim_{\begin{matrix}p→∞ \\ p prime \end{matrix}} \frac{\sqrt[k]{V_{k}(N(2, p))}}{N(2, p)} = 1.  (8)

Now (7) and (8) imply lim sup_{n→∞} ^{\frac{\sqrt[k]{V_{k}(ϕ^{∗}(n))}}{n}} = 1, and we are done.

Apostol [2] proved that

lim sup_{n→∞} \frac{σ(ϕ^{∗}(n))}{V (ϕ^{∗}(n))(log log n)^{2}} = lim sup_{n→∞} \frac{σ(ϕ^{∗}(n))}{V (ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}} = e^{2γ}

and

lim sup_{n→∞} \frac{ψ(ϕ^{∗}(n))}{V (ϕ^{∗}(n))(log log n)^{2}} lim sup_{n→∞} \frac{ψ(ϕ^{∗}(n))}{V (ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}} = \frac{6}{π^{2}} e^{2γ}.

The maximal orders of \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))} and \frac{ψ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))} are given by

Proposition 11. For k ≥ 2 we have

(i) lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log n)^{2}} = lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}} = \frac{6}{π^{2}} e^{2γ},

(ii) lim sup_{n→∞} \frac{ψ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log n)^{2}} = lim sup_{n→∞} \frac{ψ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}} = \frac{6}{π^{2}} e^{2γ}.

Proof. (i) Let

l_{1} := lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log n)^{2}} and l_{2} := lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}} .

Since ϕ^{∗}(n) ≤ n for every n ≥ 1, we have

l_{1} = lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log n)^{2}}
≤ l_{2} = lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log ϕ^{∗}(n))^{2}}
≤ lim sup_{m→∞} \frac{σ_{k}(m)}{V_{k}(m)(log log m)^{2}} = \frac{6}{π^{2}} e^{2γ},

by Proposition 6. Since gcd(n, 1) = 1, by Linnik’s theorem, there exists a prime number p such that p ≡ 1 (mod n) and p ≪ n^{c}. Let p_{n} be the least prime such that p_{n} ≡ 1 (mod n), for every n. Then n | p_{n} − 1 and p_{n} ≪ n^{c}, so log log p_{n} ∼ log log n.

Observe that a | b implies \frac{σ_{k}(a)}{V_{k}(a)} ≤ \frac{σ_{k}(b)}{V_{k}(b)}. If p^{β} | p^{α} (β ≤ α), it is easy to see that

\frac{σ_{k}(p^{β})}{V_{k}(p^{β})} ≤ \frac{σ_{k}(p^{α})}{V_{k}(p^{α})}. The general case follows, taking into account that \frac{σ_{k}(n)}{V_{k}(n)} is multiplicative. So,

\frac{σ_{k}(ϕ^{∗}(p_{n}))}{V_{k}(ϕ^{∗}(p_{n}))(log log p_{n})^{2}} = \frac{σ_{k}(p_{n} − 1)}{V_{k}(p_{n} − 1)(log log p_{n})^{2}} ∼ \frac{σ_{k}(p_{n} − 1)}{V_{k}(p_{n} − 1)(log log n)^{2}} .

On the other hand,

\frac{σ_{k}(p_{n} − 1)}{V_{k}(p_{n} − 1)(log log n)^{2}} ≥ \frac{σ_{k}(n)}{V_{k}(n)(log log n)^{2}} .

Therefore,

lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))(log log n)^{2}} ≥ lim sup_{n→∞} \frac{σ_{k}(ϕ^{∗}(p_{n}))}{V_{k}(ϕ^{∗}(p_{n}))(log log p_{n})^{2}}

≥ lim sup_{n→∞} \frac{σ_{k}(n)}{V_{k}(n)(log log n)^{2}} = \frac{6}{π^{2}} e^{2γ}.

We obtain \frac{6}{π^{2}} e^{2γ} ≤ l_{1} ≤ l_{2} ≤ \frac{6}{π^{2}} e^{2γ}, and hence l_{1} = l_{2} = \frac{6}{π^{2}} e^{2γ}.

(ii) The proof is similar to the proof of (i), taking into account that a | b implies \frac{ψ_{k}(a)}{V_{k}(a)} ≤ \frac{ψ_{k}(b)}{V_{k}(b)}

and lim sup_{n→∞} \frac{ψ_{k}(n)}{V_{k}(n)(log log n)^{2}} = \frac{6}{π^{2}} e^{2γ}, by Proposition 6.

So, the maximal orders of both \frac{σ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))} and \frac{ψ_{k}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n))} are \frac{6}{π^{2}} e^{2γ}(log log n)^{2}.

In a similar manner, since

lim sup_{n→∞} \frac{σ_{k}^{∗}(n)}{V_{k}(n) log log n} = lim sup_{n→∞} \frac{ϕ_{k}^{∗}(n)}{V_{k}(n) log log n} = e^{γ}

(using Proposition 7), the fact that a | b implies \frac{σ_{k}^{∗}(a)}{V_{k}(a)} ≤ \frac{σ_{k}^{∗}(b)}{V_{k}(b)} and \frac{ϕ_{k}^{∗}(a)}{V_{k}(a)} ≤ \frac{ϕ_{k}^{∗}(b)}{V_{k}(b)}, respectively, it can be shown that

lim sup_{n→∞} \frac{σ_{k}^{∗}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n)) log log n} = lim sup_{n→∞} \frac{σ_{k}^{∗}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n)) log log ϕ^{∗}(n)} = e^{γ}

and

lim sup_{n→∞} \frac{ϕ_{k}^{∗}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n)) log log n} = lim sup_{n→∞} \frac{ϕ_{k}^{∗}(ϕ^{∗}(n))}{V_{k}(ϕ^{∗}(n)) log log ϕ^{∗}(n)} = e^{γ}.

7 Open Problems

Open Problem 12. Note that

lim inf_{n→∞} \frac{V_{k}(ϕ(n))}{n^{k}} = lim inf_{n→∞} \frac{V_{k}(ϕ^{∗}(n))}{n^{k}} = lim inf_{n→∞} \frac{ϕ_{k}^{∗}(V (n))}{n^{k}} = 0.

For n_{k} = p_{1} ⋯ p_{r} (the product of the first r primes), we have

\frac{V_{k}(ϕ(n_{r}))}{n_{r}^{k}} = \frac{V_{k}((p_{1} − 1) ⋯ (p_{r} − 1))}{p_{1}^{k} ⋯ p_{r}^{k}} ≤ \frac{(p_{1} − 1)^{k} ⋯ (p_{r} − 1)^{k}}{p_{1}^{k} ⋯ p_{r}^{k}} = ((1 − \frac{1}{p_{1}} ) ⋯ (1 − \frac{1}{p_{r}}))^{k},

so

lim_{r→∞} \frac{V_{k}(ϕ(n_{r}))}{n_{r}^{k}} = lim_{r→∞}((1 − \frac{1}{p_{1}} ) ⋯ (1 − \frac{1}{p_{r}}))^{k} = 0,

similarly the other relations. What are the minimal orders for the V_{k}(ϕ(n)), V_{k}(ϕ^{∗}(n)), and ϕ_{k}^{∗}(V (n)) ?

Open Problem 13. Taking n_{r} = p_{1} ⋯ p_{r} (the product of the first r primes),

\frac{σ_{k}^{∗}(V (n_{r}))}{n_{r}^{k}} = \frac{σ_{k}^{∗}(p_{1} ⋯ p_{r})}{p_{1}^{k} ⋯ p_{r}^{k}} = \frac{(p_{1}^{k} + 1) ⋯ (p_{r}^{k} + 1)}{p_{1}^{k} ⋯ p_{r}^{k}} = ((1 + \frac{1}{p_{1}} ) ⋯ (1 + \frac{1}{p_{r}}))^{k} → ∞

as r → ∞, so lim sup_{n→∞} \frac{σ_{k}^{∗}(V (n))}{n^{k}} = ∞. What is the maximal order for σ_{k}^{∗}(V (n)) ?

8 Acknowledgments

The authors would like to thank the referees for helpful suggestions.

References

[1] O. Alkam and E. Osba, On the regular elements in ℤ_{n}, Turk. J. Math. 32 (2008), 1–9.

[2] B. Apostol, Extremal orders of some functions connected to regular integers modulo n, An. Ştiinţ. Univ. “Ovidius” Constanţa, Ser. Mat. 21 (2013), to appear.

[3] B. Apostol and L. Petrescu, On the number of regular integers (mod n), J. Algebra Number Theory Acad. 2 (2012), 337–352.

[4] B. Apostol and L. Tóth, Some remarks on regular integers modulo n, preprint,

    http://arxiv.org/abs/1304.2699.

[5] P. Haukkanen and L. Tóth, An analogue of Ramanujan’s sum with respect to regular integers (mod r), Ramanujan J. 27 (2012), 71–88.

[6] J. Morgado, A property of the Euler ϕ-function concerning the integers which are regular modulo n, Portugal. Math. 33 (1974), 185–191.

[7] J. Morgado, Inteiros regulares módulo n, Gazeta de Matematica 33 (1972), 1–5.

[8] J. Sándor, Geometric Theorems, Diophantine Equations, and Arithmetic Functions, American Research Press, 2002.

[9] J. Sándor and B. Crstici, Handbook of Number Theory II, Kluwer Academic Publishers, 2004.

[10] J. Sándor and L. Tóth, Extremal orders of compositions of certain arithmetical functions, Integers 8 (2008), # A34.

[11] R. Sivaramakrishnan, Classical Theory of Arithmetic Functions, Marcel Dekker, 1989.

[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[13] D. Suryanarayana, On a class of sequences of integers, Amer. Math. Monthly 84 (1977), 728–730.

[14] L. Tóth, A gcd-sum function over regular integers modulo n, J. Integer Seq. 12 (2009), Article 09.2.5.

[15] L. Tóth, Regular integers (mod n), Annales Univ. Sci. Budapest., Sect Comp. 29 (2008), 263–275.

[16] L. Tóth and E. Wirsing, The maximal order of a class of multiplicative arithmetical functions, Annales Univ. Sci. Budapest., Sect Comp. 22 (2003), 353–364.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11N37. Keywords: arithmetical function, composition, regular integer (mod n), extremal order.

(Concerned with sequences \underline{A000010}, \underline{A000203}, \underline{A055653}, and \underline{A143869}.)

Received April 25 2013; revised versions received July 9 2013; July 30 2013; August 5 2013. Published in Journal of Integer Sequences, August 8 2013.

Return to Journal of Integer Sequences home page.