Quasi-Injectivity of Some Arithmetic Functions

Prapanpong Pongsriiam Department of Mathematics Faculty of Science Silpakorn University Nakhon Pathom 73000 Thailand

                  pongsriiam p@silpakorn.edu
                     prapanpong@gmail.com

Abstract

Let a and b be positive integers and f an arithmetic function. In this article, we investigate whether or not a certain condition on the value of f implies a = b. For example, if f is the sum of divisors function and f(an) = f(bn) for all positive integers n, then a = b.

1 Introduction

Let φ be the Euler function, which counts the number of positive integers k ≤ n with (k, n) = 1. For each nonnegative integer s and a positive integer n, let σ_{s}(n) = ∑_{d|n} d^{s}, where d runs over the positive divisors of n, σ(n) = σ_{1}(n), and τ(n) = σ_{0}(n). Problems on the ranges of arithmetic functions have been a popular area of research. For example, it is easy to see that if n is a prime, then φ(n) = n−1; Lehmer asked whether φ(n) | n−1 implies that n is a prime, but this question is still open. In addition, Carmichael’s longstanding open problem on the range of φ states that if φ(x) = n, then there exists y ∈ ℕ distinct from x such that φ(y) = n too. Moreover, whether or not there are infinitely many n ∈ ℕ with σ(n) = 2n has been an open question for a very long time.

Many mathematicians have worked on these problems and made some progress. For example, Pomerance [7] obtained a result concerning the maximal order of A(n), where A(n) is the number of solutions to φ(x) = n. Ford [1] gave a comprehensive study of the range of φ including A(n). In particular, Ford [2] solved Sierpiński’s conjecture, and partially solved Carmichael’s problem stated above. That is, Ford showed that for each integer k ≥ 2, there exists a positive integer n for which the equation φ(x) = n has exactly k solutions. Furthermore, Ford, Luca, and Pomerance [3] completely answered Erdös’ question on the range of φ and σ by showing that φ(x) = σ(y) has infinitely many solutions in x, y ∈ ℕ. Ford and Pollack [4] also gave a result complementary to that of Ford, Luca, and Pomerance [3]. For more information on the range of φ and σ, we refer the reader to the sequences \underline{A000010}, \underline{A007617}, and \underline{A000396} in OEIS [10]. Finally, in a recent Thailand Online Mathematical Olympiad TOMO 2021, an interesting arithmetic problem [9] was to show that if a, b ∈ ℕ and τ(τ(an)) = τ(τ(bn)) for all n ∈ ℕ, then a = b. This naturally suggests various generalizations, where τ may be replaced by σ_{s} or by other arithmetic functions.

Definition 1. We call a function f : ℕ → ℂ a quasi-injective function if for all a, b ∈ ℕ, the condition f(an) = f(bn) for all n ∈ ℕ implies a = b. In addition, if f : ℕ → ℕ and ℓ ∈ ℕ, then we say that f is quasi-injective of order ℓ if f, f^{(2)}, f^{(3)}, …, f^{(ℓ)} are quasi-injective, that is, for any a, b, k ∈ ℕ with 1 ≤ k ≤ ℓ,

if f^{(k)}(an) = f^{(k)}(bn) for all n ∈ ℕ, then a = b.  (1)

In the above definition and throughout this article, if k ∈ ℕ, then f^{(k)} is the k-fold composition of f. In addition, ℕ is the set of positive integers but we may need to replace ℕ by the set ℕ_{0} of nonnegative integers. Therefore, the problem in TOMO 2021 mentioned above asks to show that (1) holds when k = 2 and f = τ. In fact, (1) also holds when k = 1 and f = τ. So τ is quasi-injective of order 2. In general, if f is quasi-injective of order ℓ, then it is also quasi-injective of order m ≤ ℓ. For the concept of quasi-injectivity in algebra, see, for example, the articles by Yavari [11] and Yavari and Ebrahimi [12].

In this article, we study quasi-injectivity of f when f = σ_{s} and other popular arithmetic functions such as the Euler totient function, the Jordan totient function, functions counting prime divisors, the Möbius function, and the Alladi-Erdös function. We also give some open problems at the end of this paper.

2 Preliminaries and lemmas

In this section, we recall some basic terminologies and give some useful results for the reader’s convenience. From this point on, p is always a prime, s and n are positive integers, μ is the Möbius function, φ is the Euler totient function, ω(n) is the number of distinct prime factors of n, Ω(n) is the number of prime divisors of n counted with multiplicity, and J_{s} is the Jordan totient function. So J_{s}(n) is the number of s-tuples (a_{1}, a_{2}, …, a_{s}) such that 1 ≤ a_{i} ≤ n for all i = 1, 2, …, s and (a_{1}, a_{2}, …, a_{s}, n) = 1. Therefore φ = J_{1}. Furthermore, it is well known that

φ(n) = n ∏_{p|n} (1 − \frac{1}{p}) and J_{s}(n) = n^{s} ∏_{p|n} (1 − \frac{1}{p^{s}} ) .

An arithmetic function f is called multiplicative if f is not the zero function and f(mn) = f(m)f(n) for all m, n ∈ ℕ with (m, n) = 1; and f is called additive if f(mn) = f(m) + f(n) for all m, n ∈ ℕ with (m, n) = 1. In addition, μ(1) = 1, μ(n) = (−1)^{ω(n)} if n is squarefree, and μ(n) = 0 if n is not squarefree. It is well known that the functions τ, σ_{s}, μ, and J_{s} are multiplicative, while ω and Ω are additive. Furthermore,

if c ∈ ℕ, then σ_{s}(p^{c}) = \frac{p^{(c+1)s} − 1}{p^{s} − 1}.

For more details about this, see for instance, the books by Hardy and Wright [5] and Mc-Carthy [6].

Recall that the p-adic valuation of n, denoted by v_{p}(n), is the exponent of p in the prime factorization of n. A useful formula for v_{p}(x^{n} − y^{n}), sometimes called the “Lifting the Exponent Lemma”, is well known and popular among students taking mathematical Olympiad exams. For the proof, see, for example, [8, pp. 14–15].

Lemma 2 (“Lifting the Exponent Lemma”). Let x, y ∈ ℤ, n ∈ ℕ, and let p be a prime such that p ∤ x and p ∤ y. Then the following statements hold:

(i) If p is odd and p | x − y, then v_{p}(x^{n} − y^{n}) = v_{p}(x − y) + v_{p}(n).

(ii) If p is odd, n is odd, and p | x + y, then v_{p}(x^{n} + y^{n}) = v_{p}(x + y) + v_{p}(n).

When p = 2 (so x and y are odd integers), we have

(iii) if n is odd, then v_{2}(x^{n} − y^{n}) = v_{2}(x − y) and v_{2}(x^{n} + y^{n}) = v_{2}(x + y);

(iv) if n is even, then v_{2}(x^{n} − y^{n}) = v_{2}(x^{2} − y^{2}) + v_{2}(n) − 1.

The conditions (A), (B), (C) in the following lemma are used throughout this article.

Lemma 3. Let a, b ∈ ℕ and let f : ℕ → ℕ be a multiplicative function satisfying the following conditions:

(A) f(p^{k}) > f(p^{r}) for all primes p and nonnegative integers k > r;

(B) for any prime p and nonnegative integers x, y, c_{1}, c_{2}, if c_{1} ≠ c_{2} and f(p^{x+c_{2}})f(p^{y+c_{1}}) = f(p^{y+c_{2}})f(p^{x+c_{1}}), then x = y;

(C) for each prime p dividing ab, there are c_{1}, c_{2} ∈ ℕ ∪ {0} such that c_{1} ≠ c_{2} and f(ap^{c}) = f(bp^{c}) for c ∈ {c_{1}, c_{2}}.

Then a = b.

Proof. Since f : ℕ → ℕ, f(n) ≥ 1 for all n. If a = 1 but b ≥ 2, then there are a prime p and k ∈ ℕ such that b = p^{k}b_{1}, p ∤ b_{1}, and so by the condition (C), there exists c ∈ ℕ such that

f(p^{c}) = f(ap^{c}) = f(bp^{c}) = f(p^{c+k}b_{1}) = f(p^{c+k})f(b_{1}) ≥ f(p^{c+k}) > f(p^{c}),

which is a contradiction. So if a = 1, then b = 1 = a. Similarly, if b = 1, then a = 1 = b. So assume throughout that a, b ≥ 2. Let

a = p_{1}^{a_{1}}p_{2}^{a_{2}} … p_{k}^{a_{k}} and b = p_{1}^{b_{1}}p_{2}^{b_{2}} … p_{k}^{b_{k}},

where p_{1}, p_{2}, …, p_{k} are distinct primes and a_{1}, a_{2}, …, a_{k}, b_{1}, b_{2}, …, b_{k} are nonnegative integers with a_{j}^{2} + b_{j}^{2} ≠ 0 for any j = 1, 2, …, k. To show that a = b, it suffices to show that a_{j} = b_{j} for all j. So let j ∈ {1, 2, …, k} and p = p_{j}. Then p | ab. By the condition (C), there are c_{1}, c_{2} ∈ ℕ ∪ {0} such that c_{1} ≠ c_{2}, f(ap^{c_{1}}) = f(bp^{c_{1}}), and f(ap^{c_{2}}) = f(bp^{c_{2}}). Then

f(p_{j}^{a_{j}+c_{1}}) ∏_{\begin{matrix}1≤i≤k \\ i≠j \end{matrix}} f (p_{i}^{a_{i}}) = f(p_{j}^{b_{j}+c_{1}}) ∏_{\begin{matrix}1≤i≤k \\ i≠j \end{matrix}} f (p_{i}^{b_{i}})  (2)

f(p_{j}^{a_{j}+c_{2}}) ∏_{\begin{matrix}1≤i≤k \\ i≠j \end{matrix}} f (p_{i}^{a_{i}}) = f(p_{j}^{b_{j}+c_{2}}) ∏_{\begin{matrix}1≤i≤k \\ i≠j \end{matrix}} f (p_{i}^{b_{i}})  (3)

Dividing (3) by (2) gives

\frac{f(p_{j}^{a_{j}+c_{2}})}{f(p_{j}^{a_{j}+c_{1}})} = \frac{f(p_{j}^{b_{j}+c_{2}})}{f(p_{j}^{b_{j}+c_{1}})}  (4)

By (4) and the condition (B), we obtain a_{j} = b_{j}, as required.

The next lemma is used in the calculation of the p-adic valuation of σ_{s}(n).

Lemma 4. Assume that p and q are primes, q ≡ 1 (mod p), and c ∈ ℕ ∪ {0}. Then the following statements hold.

(i) If p is odd, then v_{p}(σ_{s}(q^{c})) = v_{p}(c + 1).

(ii) If p = 2 and s is even, then v_{p}(σ_{s}(q^{c})) = v_{p}(c + 1).

(iii) If p = 2, s is odd, and c is odd, then v_{p}(σ_{s}(q^{c})) = v_{p}(c + 1) + v_{p}(q + 1) − 1.

(iv) If p = 2, s is odd, and c is even, then v_{p}(σ_{s}(q^{c})) = 0.

Proof. Since p ∤ q, p ∤ 1, and p | q − 1, we obtain by Lemma 2 that if p is odd, then

v_{p}(σ_{s}(q^{c})) = v_{p}(q^{(c+1)s} − 1) − v_{p}(q^{s} − 1)
= (v_{p}(q − 1) + v_{p}((c + 1)s)) − (v_{p}(q − 1) + v_{p}(s)) = v_{p}(c + 1).

Similarly, if p = 2 and s is even, then

v_{p}(σ_{s}(q^{c})) = (v_{2}(q^{2} − 1) + v_{2}((c + 1)s) − 1) − (v_{2}(q^{2} − 1) + v_{2}(s) − 1) = v_{2}(c + 1);

if p = 2, s is odd, and c is odd, then

v_{p}(σ_{s}(q^{c})) = v_{2}(q^{2} − 1) + v_{2}((c + 1)s) − 1 − v_{2}(q − 1)
= v_{2}(c + 1) + v_{2}(q + 1) − 1;

and if p = 2, s is odd, and c is even, then v_{p}(σ_{s}(q^{c})) = 0. This completes the proof.

3 Main results

Theorem 5. Let a, b, s ∈ ℕ. Then the functions τ and σ_{s} satisfy the conditions (A) and (B) in Lemma 3.

Proof. If k > r, then every divisor of p^{r} is also a divisor of p^{k} while p^{k} is not a divisor of p^{r}. From this, it is easy to see that τ and σ_{s} satisfy the condition (A). Let p be a prime, x, y, c_{1}, c_{2} ∈ ℕ ∪ {0}, and c_{1} ≠ c_{2}. Suppose that

τ(p^{x+c_{2}})τ(p^{y+c_{1}}) = τ(p^{y+c_{2}})τ(p^{x+c_{1}}).

Then (x+c_{2}+1)(y+c_{1}+1) = (y+c_{2}+1)(x+c_{1}+1). Dividing both sides by (y+c_{1}+1)(x+c_{1}+1), subtracting both sides by 1, and then dividing both sides by c_{2}−c_{1} leads to x = y, as required. Next, suppose that

σ_{s}(p^{x+c_{2}})σ_{s}(p^{y+c_{1}}) = σ_{s}(p^{y+c_{2}})σ_{s}(p^{x+c_{1}}).  (5)

Let x_{1} = x + c_{1} + 1, x_{2} = x + c_{2} + 1, y_{1} = y + c_{1} + 1, and y_{2} = y + c_{2} + 1. Then (5) implies that

\frac{p^{x_{2}s} − 1}{p^{x_{1}s} − 1} = \frac{p^{y_{2}s} − 1}{p^{y_{1}s} − 1}.  (6)

Observing that y_{2} − y_{1} = c_{2} − c_{1} = x_{2} − x_{1} and subtracting both sides of (6) by 1, we obtain

\frac{p^{x_{1}s}(p^{(c_{2}−c_{1})s} − 1)}{p^{x_{1}s} − 1} = \frac{p^{y_{1}s}(p^{(c_{2}−c_{1})s} − 1)}{p^{y_{1}s} − 1}.  (7)

Dividing both sides of (7) by p^{(c_{2}−c_{1})s} − 1, and then subtracting both sides by 1 leads to p^{x_{1}s} = p^{y_{1}s}. Therefore x_{1} = y_{1}, which implies x = y, as required. This shows that τ and σ_{s} satisfy the condition (B).

Corollary 6. Let a, b ∈ ℕ and f = τ or f = σ_{s}. Suppose that for each prime p | ab, we can find distinct nonnegative integers c_{1}, c_{2} such that f(ap^{c}) = f(bp^{c}) for c ∈ {c_{1}, c_{2}}. Then a = b. In particular, if f(an) = f(bn) for all n ∈ ℕ, then a = b. In other words, τ and σ_{s} are quasi-injective.

Proof. By Theorem 5, f satisfies the conditions (A) and (B), and the above supposition is, in fact, the condition (C). Therefore a = b, as required.

Modifying the proof of Theorem 5, we see that τ is in fact quasi-injective of order ℓ for any ℓ ∈ ℕ, as shown in the next theorem.

Theorem 7. If m, a, b are positive integers and τ^{(m)}(an) = τ^{(m)}(bn) for all n ∈ ℕ, then a = b.

Proof. We prove by induction on m. If m = 1, the result follows from Corollary 6. So let m ≥ 2 and assume that the result holds for m − 1. Let a, b ∈ ℕ and

τ^{(m)}(an) = τ^{(m)}(bn) for all n ∈ ℕ.  (8)

Let k ∈ ℕ and d ∈ ℕ ∪ {0}. Choosing a prime p ∤ abk and substituting n = p^{d}k in (8), we obtain

τ^{(m−1)}((d + 1)τ(ak)) = τ^{(m−1)}(τ(an)) = τ^{(m−1)}(τ(bn)) = τ^{(m−1)}((d + 1)τ(bk)). (9)

Since (9) holds for all d ∈ ℕ∪{0}, we obtain by the induction hypothesis that τ(ak) = τ(bk). Since k is arbitrary, we obtain by Corollary 6 that a = b.

We now know that if τ^{(m)}(an) = τ^{(m)}(bn) for all n, then a = b; and if σ_{s}(an) = σ_{s}(bn) for all n, then a = b. We would like to extend the result for σ_{s} to σ_{s}^{(m)} for any m but it seems much more complicated than that of τ^{(m)}, so we do it only for σ_{s}^{(2)}. We conjecture that the result holds for m ≥ 3 as well but we currently do not have a proof.

Theorem 8. For each positive integer x ≥ 2 and for each prime p dividing x, there are positive integers m, n, c_{1}, c_{2}, A, B such that c_{2} > c_{1}, (ABmn, x) = 1, σ_{s}(m) = p^{c_{1}}A, and σ_{s}(n) = p^{c_{2}}B.

Proof. Let x = p_{1}^{a_{1}}p_{2}^{a_{2}} … p_{k}^{a_{k}}, where p_{1}, p_{2}, …, p_{k} are distinct primes and a_{1}, a_{2}, …, a_{k} are positive integers. Let p be a prime dividing x, say p = p_{j} for some j ∈ {1, 2, …, k}. Let

M = ∏_{1≤i≤k} p_{i} and M_{j} = \frac{M}{p} .

By Dirichlet’s theorem for primes in arithmetic progressions, there exists a prime q ≡ 1 (mod M). To find the integers m, n, c_{1}, c_{2}, A, B as above, we divide the calculation into two cases:

Case 1: p_{i} is odd for all i ≠ j. By the Chinese remainder theorem, there exists a positive integer w such that

w ≡ −1 (mod p) and w ≡ 0 (mod M_{j}).  (10)

Let L be a positive integer larger than v_{p}(w +1)+v_{p}(q +1). Applying the Chinese remainder theorem again to obtain y ∈ ℕ such that

y ≡ −1 (mod p^{L}) and y ≡ 0 (mod M_{j}).  (11)

Let m = q^{w} and n = q^{y}. By Lemma 4, we obtain

v_{p_{i}}(σ_{s}(m)) = v_{p_{i}}(σ_{s}(q^{w})) = v_{p_{i}}(w + 1) = 0 for all i ≠ j.

In addition, if p is odd or if p = 2 and s is even, then v_{p}(σ_{s}(m)) = v_{p}(σ_{s}(q^{w})) = v_{p}(w+1) > 0; if p = 2 and s is odd, then w is odd, q is odd, v_{p}(q + 1) ≥ 1, and

v_{p}(σ_{s}(m)) = v_{p}(σ_{s}(q^{w})) = v_{p}(w + 1) + v_{p}(q + 1) − 1 > 0.

This shows that v_{p}(σ_{s}(m)) > 0 and v_{p_{i}}(σ_{s}(m)) = 0 for all i ≠ j. Let c_{1} = v_{p}(σ_{s}(m)). Then c_{1} ∈ ℕ and σ_{s}(m) = p^{c_{1}}A, where A ∈ ℕ and (A, x) = 1. Similarly, we obtain v_{p_{i}}(σ_{s}(n)) = 0 for all i ≠ j and

v_{p}(σ_{s}(n)) ≥ v_{p}(y + 1) ≥ L > v_{p}(w + 1) + v_{p}(q + 1) ≥ v_{p}(σ_{s}(m)).

Let c_{2} = v_{p}(σ_{s}(n)). Then c_{2} ∈ ℕ, c_{2} > c_{1}, and σ_{s}(n) = p^{c_{2}}B, where B ∈ ℕ and (B, x) = 1. Since (m, x) = (n, x) = (A, x) = (B, x) = 1, we obtain (mnAB, x) = 1.

Case 2: p_{i} = 2 for some i ≠ j. Without loss of generality, assume that p_{1} = 2. We still choose w, L, y, m = q^{w} and n = q^{y} as in Case 1 and apply Lemma 4 to calculate the p-adic valuation of σ_{s}(m) and σ_{s}(n). If i ≠ 1, then p_{i} is odd and so

v_{p_{i}}(σ_{s}(m)) = v_{p_{i}}(w + 1) = 0, v_{p_{i}}(σ_{s}(n)) = v_{p_{i}}(y + 1) = 0.

In addition, p is odd, and so

v_{p}(σ_{s}(m)) = v_{p}(w + 1) > 0, v_{p}(σ_{s}(n)) = v_{p}(y + 1) ≥ L > v_{p}(σ_{s}(m)).

Since p_{1} = 2 and w, y ≡ 0 (mod M_{j}), w and y are even. If s is even, then v_{p_{1}}(σ_{s}(m)) = v_{2}(w + 1) = 0 = v_{2}(y + 1) = v_{p_{1}}(σ_{s}(n)). If s is odd, then v_{p_{1}}(σ_{s}(m)) and v_{p_{1}}(σ_{s}(n)) are also zero. This shows that v_{p}(σ_{s}(n)) > v_{p}(σ_{s}(m)) > 0 and v_{p_{i}}(σ_{s}(m)) = v_{p_{i}}(σ_{s}(n)) = 0 for all i ≠ j. Therefore we can choose c_{1}, c_{2}, A, B as in the previous case. This completes the proof.

Theorem 9. Let a and b be positive integers and

σ_{s}(σ_{s}(an)) = σ_{s}(σ_{s}(bn)) for all n ∈ ℕ.  (12)

Then a = b.

Proof. Let p be a prime dividing ab and d ∈ ℕ ∪ {0}. Let n_{1} be a positive integer such that (n_{1}, ab) = 1. Substituting n = p^{d}n_{1} in (12), we obtain

σ_{s}(σ_{s}(ap^{d})σ_{s}(n_{1})) = σ_{s}(σ_{s}(bp^{d})σ_{s}(n_{1})),  (13)

which holds for any n_{1} ∈ ℕ with (n_{1}, ab) = 1. Next, let a_{1} = σ_{s}(ap^{d}), b_{1} = σ_{s}(bp^{d}), x = aba_{1}b_{1} and let q be a prime dividing a_{1}b_{1}. Then q | x. By Theorem 8, there are positive integers m, n, c_{1}, c_{2}, A, B such that c_{2} > c_{1}, (ABmn, x) = 1, σ_{s}(m) = q^{c_{1}}A, and σ_{s}(n) = q^{c_{2}}B. Since (13) holds for any n_{1} ∈ ℕ with (n_{1}, ab) = 1 and (m, ab) = (n, ab) = 1, we can substitute n_{1} = m and n_{1} = n in (13) to obtain

σ_{s}(a_{1}q^{c_{1}}A) = σ_{s}(b_{1}q^{c_{1}}A) and σ_{s}(a_{1}q^{c_{2}}B) = σ_{s}(b_{1}q^{c_{2}}B).  (14)

Since (AB, x) = 1, we see that (A, qa_{1}b_{1}) = (B, qa_{1}b_{1}) = 1. Therefore (14) reduces to

σ_{s}(a_{1}q^{c_{1}})σ_{s}(A) = σ_{s}(b_{1}q^{c_{1}})σ_{s}(A) and σ_{s}(a_{1}q^{c_{2}})σ_{s}(B) = σ_{s}(b_{1}q^{c_{2}})σ_{s}(B),

which imply

σ_{s}(a_{1}q^{c_{1}}) = σ_{s}(b_{1}q^{c_{1}}) and σ_{s}(a_{1}q^{c_{2}}) = σ_{s}(b_{1}q^{c_{2}}).  (15)

This shows that for any prime q | a_{1}b_{1}, we can find distinct c_{1}, c_{2} ∈ ℕ such that (15) holds. By Corollary 6, we obtain a_{1} = b_{1}. Therefore

σ_{s}(ap^{d}) = σ_{s}(bp^{d}).  (16)

Since (16) holds for each prime p | ab and each d ∈ ℕ ∪ {0}, we apply Corollary 6 again to obtain a = b. This completes the proof.

Before proceeding to the case of J_{s}, we give an example to show that ω, Ω, and μ are not quasi-injective.

Example 10. Let k ≥ 2, p_{1}, p_{2}, …, p_{k} distinct primes, c = p_{1}p_{2} … p_{k}, a = p_{1}c, and b = p_{2}c. Then ω(a) = ω(b), Ω(a) = Ω(b), and μ(a) = μ(b). Since Ω is completely additive, that is, Ω(mn) = Ω(m) + Ω(n) for all m, n ∈ ℕ, we see that Ω(an) = Ω(bn) for all n ∈ ℕ but a ≠ b. Therefore Ω is not quasi-injective. Similarly, it is not difficult to see that ω(an) = ω(bn) and μ(an) = μ(bn) for all n ∈ ℕ but a ≠ b, and so ω and μ are not quasi-injective.

We can generalize the idea in Example 10 as follows.

Theorem 11. Let f : ℕ → ℂ be completely additive. Then f is quasi-injective if and only if f is injective.

Proof. Suppose f is quasi-injective, a, b ∈ ℕ, and f(a) = f(b). Then for each n ∈ ℕ, we have

f(an) = f(a) + f(n) = f(b) + f(n) = f(bn).  (17)

Since (17) holds for all n ∈ ℕ and f is quasi-injective, we obtain a = b, as required. The converse is obvious.

Example 12. Let A be the Alladi-Erdös function defined by A(n) = ∑_{p^{α}∥n} αp. It is easy to verify that A is completely additive, that is, A(mn) = A(m) + A(n) for all m, n ∈ ℕ. In addition, A(2^{3}) = 6 = A(3^{2}), so A is not injective. By Theorem 11, A is not quasi-injective.

A variation of Alladi-Erdös function can defined by A_{0}(n) = ∑_{p|n} p. Then A_{0}(6) = 2 + 3 = 5 = A_{0}(12), and it is not difficult to see that A_{0}(6n) = A_{0}(12n) for all n ∈ ℕ. Therefore A_{0} is not quasi-injective.

Theorem 13. Suppose that f : ℕ → ℂ is strongly additive, that is, f is additive and f(p^{k}) = f(p) for all primes p and positive integers k. If there are distinct positive integers a, b ≥ 2 such that f(a) = f(b) and a, b have the same prime factors, then f is not quasiinjective.

Proof. Since a and b have the same prime factors, we write

a = p_{1}^{a_{1}}p_{2}^{a_{2}} … p_{k}^{a_{k}} and b = p_{1}^{b_{1}}p_{2}^{b_{2}} … p_{k}^{b_{k}},

where p_{1}, p_{2}, …, p_{k} are distinct primes and a_{1}, a_{2}, …, a_{k}, b_{1}, b_{2}, …, b_{k} are positive integers. We show that f(an) = f(bn) for all n ∈ ℕ. For each n ≥ 2, we write n = p_{1}^{n_{1}}p_{2}^{n_{2}} … p_{k}^{n_{k}}m, where m ∈ ℕ, (m, ab) = 1, and n_{1}, n_{2}, …, n_{k} are nonnegative integers, and so

f(an) = f(p_{1}^{a_{1}+n_{1}}p_{2}^{a_{2}+n_{2}} … p_{k}^{a_{k}+n_{k}}m) = f(a)f(m) = f(b)f(m) = f(bn).

Therefore f(an) = f(bn) for all n ∈ ℕ but a ≠ b. This completes the proof.

Theorem 14. Let a, b, c, k, m, s be positive integers. Then the following statements hold.

(i) If a | b, then J_{s}(ab) = a^{s}J_{s}(b).

(ii) If a | c and b | c, then b^{s}J_{s}(ac) = a^{s}J_{s}(bc).

(iii) If a | b, then J_{s}^{(m)}(a) | J_{s}^{(m)}(b).

(iv) J_{s}(a^{k}b) = a^{(k−1)s}J_{s}(ab).

(v) If k ≥ m + 1, then J_{s}^{(m)}(a^{k}b) = a^{s^{m}}J_{s}^{(m)}(a^{k−1}b).

(vi) If k ≥ m + 1, then a^{s^{m}} | J_{s}^{(m)}(a^{k}).

(vii) If k ≥ m + 1 and c ≥ m + 1, then a^{s^{m}} | J_{s}^{(m)}(a^{k}b^{c}) and b^{s^{m}} | J_{s}^{(m)}(a^{k}b^{c}).

Proof. For (i) and (iii), assume that a | b. Then p | ab if and only if p | b. Therefore

J_{s}(ab) = (ab)^{s} ∏_{p|ab} (1 − \frac{1}{p^{s}} ) = a^{s}b^{s} ∏_{p|b} (1 − \frac{1}{p^{s}} ) = a^{s}J_{s}(b),

which proves (i). If a = 1, then (iii) is obvious. So assume that a ≥ 2. Let a = p_{1}^{a_{1}}p_{2}^{a_{2}} … p_{k}^{a_{k}} and b = p_{1}^{b_{1}}p_{2}^{b_{2}} … p_{k}^{b_{k}}b_{0}, where p_{1}, p_{2}, …, p_{k} are distinct primes, a_{i}, b_{i}, b_{0} ∈ ℕ, b_{i} ≥ a_{i} for all i = 1, 2, …, k, and (b_{0}, p_{1}p_{2} … p_{k}) = 1. Then

J_{s}(a) = ∏_{i=1}^{k} (p_{i}^{(a_{i}−1)s}) ∏_{i=1}^{k} (p_{i}^{s} − 1) ,

J_{s}(b) = ∏_{i=1}^{k} (p_{i}^{(b_{i}−1)s}) ∏_{i=1}^{k} (p_{i}^{s} − 1) J_{s}(b_{0}).

From this, it is easy to see that J_{s}(a) | J_{s}(b). So (iii) is proved for m = 1. If m ≥ 2, we can apply the result when m = 1 repeatedly and obtain the chain of implication as follows:

a | b ⇒ J_{s}(a) | J_{s}(b) ⇒ J_{s}^{(2)}(a) | J_{s}^{(2)}(b) ⇒ ⋯ ⇒ J_{s}^{(m)} | J_{s}^{(m)}(b).

Therefore (iii) is proved for every m ≥ 1. For (ii), if a | c and b | c, then we obtain by (i) that

b^{s}J_{s}(ac) = b^{s}a^{s}J_{s}(c) = a^{s}b^{s}J_{s}(c) = a^{s}J_{s}(bc).

Next, we prove (iv) by induction on k. If k = 1, then (iv) is obvious. So let k ≥ 1 and assume that (iv) holds for k. Since a | a^{k}b, we obtain by (i) that

J_{s}(a^{k+1}b) = J_{s}(a(a^{k}b)) = a^{s}J_{s}(a^{k}b) = a^{ks}J_{s}(ab),

where the last equality is obtained from the induction hypothesis. Next, we prove (v) by induction on m. If m = 1 and k ≥ 2, then we obtain by (i) that J_{s}^{(m)}(a^{k}b) = J_{s}(a · a^{k−1}b) = a^{s}J_{s}(a^{k−1}b). So let m ≥ 1 and assume that the result holds for m. Suppose k ≥ m + 2. By the induction hypothesis, we obtain

J_{s}^{(m+1)}(a^{k}b) = J_{s}(J_{s}^{(m)}(a^{k}b)) = J_{s}(a^{s^{m}}J_{s}^{(m)}(a^{k−1}b)).  (18)

Since k − 1 ≥ m + 1, we apply the induction hypothesis again to conclude that a^{s^{m}} | J_{s}^{(m)}(a^{k−1}b). Then (i) implies that the right-hand side of (18) is equal to a^{s^{m+1}}J_{s}^{(m+1)}(a^{k−1}b). Therefore (18) becomes

J_{s}^{(m+1)}(a^{k}b) = a^{s^{m+1}}J_{s}^{(m+1)}(a^{k−1}b),

which proves (v). Then (vi) is a special case of (v) when b = 1. For (vii), if k ≥ m + 1 and c ≥ m + 1, then we use (vi) and (iii) to obtain

a^{s^{m}} | J_{s}^{(m)}(a^{k}) | J_{s}^{(m)}(a^{k}b^{c}) and b^{s^{m}} | J_{s}^{(m)}(b^{c}) | J_{s}^{(m)}(a^{k}b^{c}).

Here x | y | z means that x | y and y | z. Hence the proof is complete.

Theorem 15. Let a, b, m, s ∈ ℕ and J_{s}^{(m)}(an) = J_{s}^{(m)}(bn) for all n ∈ ℕ. Then a = b. In other words, J_{s} is quasi-injective of any order.

Proof. Substituting n = a^{m}b^{m} in the above condition, we have J_{s}^{(m)}(a^{m+1}b^{m}) = J_{s}^{(m)}(b^{m+1}a^{m}). By (v) of Theorem 14, we obtain

J_{s}^{(m)}(a^{m+1}b^{m}) = a^{s^{m}}J_{s}^{(m)}(a^{m}b^{m}) and J_{s}^{(m)}(b^{m+1}a^{m}) = b^{s^{m}}J_{s}^{(m)}(b^{m}a^{m}).

Therefore

a^{s^{m}}J_{s}^{(m)}(a^{m}b^{m}) = b^{s^{m}}J_{s}^{(m)}(b^{m}a^{m}),

which implies a = b. This completes the proof.

4 Conclusion and some open problems

We have proved that τ and J_{s} are quasi-injective of order m for any m ∈ ℕ while we only show that σ_{s} is quasi-injective of order 2. We believe that it can be extended to any order. In addition, Example 10 shows that μ, ω, and Ω are not quasi-injective. This leads us to the following problems. Question 16. If a, b, m, s ∈ ℕ, m ≥ 3, and σ_{s}^{(m)}(an) = σ_{s}^{(m)}(bn) for all n ∈ ℕ, can we conclude that a = b? Question 17. For each m ≥ 2, is there a function f : ℕ → ℕ such that f is quasi-injective of order m − 1 but not of order m?

We may also consider the mix between τ, σ_{s}, and J_{s}. Question 18. Let a, b, k, m, s ∈ ℕ. Are the functions τ^{(m)} ∘ σ_{s}^{(k)}, σ_{s}^{(k)} ∘ τ^{(m)}, τ^{(m)} ∘ J_{s}^{(k)}, J_{s}^{(k)} ∘ τ^{(m)}, σ_{s}^{(m)} ∘ J_{s}^{(k)}, and J_{s}^{(k)} ∘ σ_{s}^{(m)} quasi-injective? That is, if f is one of the above functions and f(an) = f(bn) for all n, can we show that a = b? This may be easy when k or m is less than 3. Can we say something when both k and m are larger than 2? Question 19. Suppose f and g are quasi-injective. Is the composition f ∘ g quasi-injective? Can we categorize those functions f and g for which f ∘ g must be quasi-injective? An obvious sufficient condition for f ∘ g to be quasi-injective is that g is both surjective and completely multiplicative, but there may be a weaker condition.

For each n ∈ ℕ and b ≥ 2, let S_{b}(n) be the sum of digits of n in base b, and let S(n) = S_{10}(n) be the sum of the decimal digits of n. Question 20. If a, c ∈ ℕ and S(an) = S(cn) for all n ∈ ℕ, is it true that a = c? More generally, if a, c, m ∈ ℕ and S^{(m)}(an) = S^{(m)}(cn) for all n ∈ ℕ, can we prove that a = c? Can we replace S by S_{b} for any b ≥ 2?

5 Acknowledgments

The author’s research project was funded jointly by the Faculty of Science Silpakorn University, and the National Research Council of Thailand (NRCT), Grant Number NRCT5-RSA63021-02. The author would also like to show support for the group of students who organized Thailand Online Mathematical Olympiad TOMO 2021. This article, in particular, the author hopes, is evidence that they put an interesting arithmetic problem in the exam and that they organized the contest very well. Finally, the author is grateful to the referee for his or her suggestions that improved the quality and exposition of this paper.

References

[1] K. Ford, The distribution of totients, Ramanujan J. 2 (1998), 67–151.

[2] K. Ford, The number of solutions of φ(x) = m, Ann. Math. 150 (1999), 1–29.

[3] K. Ford, F. Luca, and C. Pomerance, Common values of the arithmetic functions ϕ and σ, Bull. Lond. Math. Soc. 42 (2010), 478–488.

[4] K. Ford and P. Pollack, On common values of φ(n) and σ(n) II, Algebra Number Theory 6 (2012), 1669–1696.

[5] G. H. Hardy and E. M. Wright , An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008.

[6] P. J. McCarthy, Introduction to Arithmetical Functions, Universitext, Springer, 1986.

[7] C. Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), 84–89.

[8] P. Pongsriiam, Introduction to Analytic Number Theory, Silpakorn University, Printing House, 2021.

[9] Problem 9, Thailand Online Mathematical Olympiad TOMO 2021. Available at

    https://www.facebook.com/ThailandOnlineMO2021/posts/124440203032292.

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

    at https://oeis.org.

[11] M. Yavari, Quasi injectivity and θ-internal order sum in partially ordered acts, Quaest. Math. 42 (2019), 407–422.

[12] M. Yavari and M. M. Ebrahimi, Quasi-injectivity of partially ordered acts, J. Algebra

    Appl., to appear, 2021. Available at https://doi.org/10.1142/S0219498822500475.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A05. Keywords: divisor function, Euler’s function, Jordan’s function, multiplicative function, additive function.

Received June 24 2021; revised version received November 8 2021. Published in Journal of Integer Sequences, November 8 2021. (Concerned with sequences \underline{A000010}, \underline{A000396}, and \underline{A007617}.) Return to Journal of Integer Sequences home page.