Prime omega function

Short description: Number of prime factors of a natural number n

In number theory, the prime omega functions [math]\displaystyle{ \omega(n) }[/math] and [math]\displaystyle{ \Omega(n) }[/math] count the number of prime factors of a natural number [math]\displaystyle{ n. }[/math] Thereby [math]\displaystyle{ \omega(n) }[/math] (little omega) counts each distinct prime factor, whereas the related function [math]\displaystyle{ \Omega(n) }[/math] (big omega) counts the total number of prime factors of [math]\displaystyle{ n, }[/math] honoring their multiplicity (see arithmetic function). That is, if we have a prime factorization of [math]\displaystyle{ n }[/math] of the form [math]\displaystyle{ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} }[/math] for distinct primes [math]\displaystyle{ p_i }[/math] ([math]\displaystyle{ 1 \leq i \leq k }[/math]), then the respective prime omega functions are given by [math]\displaystyle{ \omega(n) = k }[/math] and [math]\displaystyle{ \Omega(n) = \alpha_1 + \alpha_2 + \cdots + \alpha_k }[/math]. These prime factor counting functions have many important number theoretic relations.

Properties and relations

The function [math]\displaystyle{ \omega(n) }[/math] is additive and [math]\displaystyle{ \Omega(n) }[/math] is completely additive.

[math]\displaystyle{ \omega(n)=\sum_{p\mid n} 1 }[/math]

If [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ n }[/math] at least once we count it only once, e.g. [math]\displaystyle{ \omega(12)=\omega(2^2 3)=2 }[/math].

[math]\displaystyle{ \Omega(n) =\sum_{p^\alpha\mid n} 1 =\sum_{p^\alpha\parallel n}\alpha }[/math]

If [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ n }[/math] [math]\displaystyle{ \alpha \geq 1 }[/math] times then we count the exponents, e.g. [math]\displaystyle{ \Omega(12)=\Omega(2^2 3^1)=3 }[/math]. As usual, [math]\displaystyle{ p^\alpha\parallel n }[/math] means [math]\displaystyle{ \alpha }[/math] is the exact power of [math]\displaystyle{ p }[/math] dividing [math]\displaystyle{ n }[/math].

[math]\displaystyle{ \Omega(n) \ge \omega(n) }[/math]

If [math]\displaystyle{ \Omega(n)=\omega(n) }[/math] then [math]\displaystyle{ n }[/math] is squarefree and related to the Möbius function by

[math]\displaystyle{ \mu(n) = (-1)^{\omega(n)} = (-1)^{\Omega(n)} }[/math]

If [math]\displaystyle{ \omega(n) = 1 }[/math] then [math]\displaystyle{ n }[/math] is a prime power, and if [math]\displaystyle{ \Omega(n)=1 }[/math] then [math]\displaystyle{ n }[/math] is a prime number.

It is known that the average order of the divisor function satisfies [math]\displaystyle{ 2^{\omega(n)} \leq d(n) \leq 2^{\Omega(n)} }[/math].

Like many arithmetic functions there is no explicit formula for [math]\displaystyle{ \Omega(n) }[/math] or [math]\displaystyle{ \omega(n) }[/math] but there are approximations.

An asymptotic series for the average order of [math]\displaystyle{ \omega(n) }[/math] is given by

[math]\displaystyle{ \frac{1}{n} \sum\limits_{k = 1}^n \omega(k) \sim \log\log n + B_1 + \sum_{k \geq 1} \left(\sum_{j=0}^{k-1} \frac{\gamma_j}{j!} - 1\right) \frac{(k-1)!}{(\log n)^k}, }[/math]

where [math]\displaystyle{ B_1 \approx 0.26149721 }[/math] is the Mertens constant and [math]\displaystyle{ \gamma_j }[/math] are the Stieltjes constants.

The function [math]\displaystyle{ \omega(n) }[/math] is related to divisor sums over the Möbius function and the divisor function including the next sums.

[math]\displaystyle{ \sum_{d\mid n} |\mu(d)| = 2^{\omega(n)} }[/math]

[math]\displaystyle{ \sum_{d\mid n} |\mu(d)| k^{\omega(d)} = (k+1)^{\omega(n)} }[/math]

[math]\displaystyle{ \sum_{r\mid n} 2^{\omega(r)} = d(n^2) }[/math]

[math]\displaystyle{ \sum_{r\mid n} 2^{\omega(r)} d\left(\frac{n}{r}\right) = d^2(n) }[/math]

[math]\displaystyle{ \sum_{d\mid n} (-1)^{\omega(d)} = \prod\limits_{p^{\alpha}||n} (1-\alpha) }[/math]

[math]\displaystyle{ \sum_{\stackrel{1\le k\le m}{(k,m)=1}} \gcd(k^2-1,m_1)\gcd(k^2-1,m_2) =\varphi(n)\sum_{\stackrel{d_1\mid m_1} {d_2\mid m_2}} \varphi(\gcd(d_1, d_2)) 2^{\omega(\operatorname{lcm}(d_1, d_2))},\ m_1, m_2 \text{ odd}, m = \operatorname{lcm}(m_1, m_2) }[/math]

[math]\displaystyle{ \sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right ) }[/math]

The characteristic function of the primes can be expressed by a convolution with the Möbius function:

[math]\displaystyle{ \chi_{\mathbb{P}}(n) = (\mu \ast \omega)(n) = \sum_{d|n} \omega(d) \mu(n/d). }[/math]

A partition-related exact identity for [math]\displaystyle{ \omega(n) }[/math] is given by

[math]\displaystyle{ \omega(n) = \log_2\left[\sum_{k=1}^n \sum_{j=1}^k \left(\sum_{d\mid k} \sum_{i=1}^d p(d-ji) \right) s_{n,k} \cdot |\mu(j)|\right], }[/math]

where [math]\displaystyle{ p(n) }[/math] is the partition function, [math]\displaystyle{ \mu(n) }[/math] is the Möbius function, and the triangular sequence [math]\displaystyle{ s_{n,k} }[/math] is expanded by

[math]\displaystyle{ s_{n,k} = [q^n] (q; q)_\infty \frac{q^k}{1-q^k} = s_o(n, k) - s_e(n, k), }[/math]

in terms of the infinite q-Pochhammer symbol and the restricted partition functions [math]\displaystyle{ s_{o/e}(n, k) }[/math] which respectively denote the number of [math]\displaystyle{ k }[/math]'s in all partitions of [math]\displaystyle{ n }[/math] into an odd (even) number of distinct parts.

Continuation to the complex plane

A continuation of [math]\displaystyle{ \omega(n) }[/math] has been found, though it is not analytic everywhere. Note that the normalized [math]\displaystyle{ \operatorname{sinc} }[/math] function [math]\displaystyle{ \operatorname{sinc}(x) = \frac{\sin(\pi x)}{\pi x} }[/math] is used.

[math]\displaystyle{ \omega(z) = \log_2\left(\sum_{x=1}^{\lceil Re(z) \rceil} \operatorname{sinc} \left(\prod_{y=1}^{\lceil Re(z) \rceil+1} \left( x^2+x-yz \right) \right) \right) }[/math]

Average order and summatory functions

An average order of both [math]\displaystyle{ \omega(n) }[/math] and [math]\displaystyle{ \Omega(n) }[/math] is [math]\displaystyle{ \log\log n }[/math]. When [math]\displaystyle{ n }[/math] is prime a lower bound on the value of the function is [math]\displaystyle{ \omega(n) = 1 }[/math]. Similarly, if [math]\displaystyle{ n }[/math] is primorial then the function is as large as [math]\displaystyle{ \omega(n) \sim \frac{\log n}{\log\log n} }[/math] on average order. When [math]\displaystyle{ n }[/math] is a power of 2, then [math]\displaystyle{ \Omega(n) \sim \frac{\log n}{\log 2} }[/math] .

Asymptotics for the summatory functions over [math]\displaystyle{ \omega(n) }[/math], [math]\displaystyle{ \Omega(n) }[/math], and [math]\displaystyle{ \omega(n)^2 }[/math] are respectively computed in Hardy and Wright as

[math]\displaystyle{ \begin{align} \sum_{n \leq x} \omega(n) & = x \log\log x + B_1 x + o(x) \\ \sum_{n \leq x} \Omega(n) & = x \log\log x + B_2 x + o(x) \\ \sum_{n \leq x} \omega(n)^2 & = x (\log\log x)^2 + O(x \log\log x) \\ \sum_{n \leq x} \omega(n)^k & = x (\log\log x)^k + O(x (\log\log x)^{k-1}), k \in \mathbb{Z}^{+}, \end{align} }[/math]

where [math]\displaystyle{ B_1 \approx 0.2614972128 }[/math] is the Mertens constant and the constant [math]\displaystyle{ B_2 }[/math] is defined by

[math]\displaystyle{ B_2 = B_1 + \sum_{p\text{ prime}} \frac{1}{p(p-1)} \approx 1.0345061758. }[/math]

Other sums relating the two variants of the prime omega functions include

[math]\displaystyle{ \sum_{n \leq x} \left\{\Omega(n) - \omega(n)\right\} = O(x), }[/math]

and

[math]\displaystyle{ \#\left\{n \leq x : \Omega(n) - \omega(n) \gt \sqrt{\log\log x}\right\} = O\left(\frac{x}{(\log\log x)^{1/2}}\right). }[/math]

Example I: A modified summatory function

In this example we suggest a variant of the summatory functions [math]\displaystyle{ S_{\omega}(x) := \sum_{n \leq x} \omega(n) }[/math] estimated in the above results for sufficiently large [math]\displaystyle{ x }[/math]. We then prove an asymptotic formula for the growth of this modified summatory function derived from the asymptotic estimate of [math]\displaystyle{ S_{\omega}(x) }[/math] provided in the formulas in the main subsection of this article above.

To be completely precise, let the odd-indexed summatory function be defined as

[math]\displaystyle{ S_{\operatorname{odd}}(x) := \sum_{n \leq x} \omega(n) [n\text{ odd}], }[/math]

where [math]\displaystyle{ [\cdot] }[/math] denotes Iverson bracket. Then we have that

[math]\displaystyle{ S_{\operatorname{odd}}(x) = \frac{x}{2} \log\log x + \frac{(2B_1-1)x}{4} + \left\{\frac{x}{4}\right\} - \left[x \equiv 2,3 \bmod{4}\right] + O\left(\frac{x}{\log x}\right). }[/math]

The proof of this result follows by first observing that

[math]\displaystyle{ \omega(2n) = \begin{cases} \omega(n) + 1, & \text{if } n \text{ is odd; } \\ \omega(n), & \text{if } n \text{ is even,} \end{cases} }[/math]

and then applying the asymptotic result from Hardy and Wright for the summatory function over [math]\displaystyle{ \omega(n) }[/math], denoted by [math]\displaystyle{ S_{\omega}(x) := \sum_{n \leq x} \omega(n) }[/math], in the following form:

[math]\displaystyle{ \begin{align} S_\omega(x) & = S_{\operatorname{odd}}(x) + \sum_{n \leq \left\lfloor\frac{x}{2}\right\rfloor} \omega(2n) \\ & = S_{\operatorname{odd}}(x) + \sum_{n \leq \left\lfloor\frac{x}{4}\right\rfloor} \left(\omega(4n) + \omega(4n+2)\right) \\ & = S_{\operatorname{odd}}(x) + \sum_{n \leq \left\lfloor\frac{x}{4}\right\rfloor} \left(\omega(2n) + \omega(2n+1) + 1\right) \\ & = S_{\operatorname{odd}}(x) + S_{\omega}\left(\left\lfloor\frac{x}{2}\right\rfloor\right) + \left\lfloor\frac{x}{4}\right\rfloor. \end{align} }[/math]

Example II: Summatory functions for so-termed factorial moments of ω(n)

The computations expanded in Chapter 22.11 of Hardy and Wright provide asymptotic estimates for the summatory function

[math]\displaystyle{ \omega(n) \left\{\omega(n)-1\right\}, }[/math]

by estimating the product of these two component omega functions as

[math]\displaystyle{ \omega(n) \left\{\omega(n)-1\right\} = \sum_{\stackrel{pq\mid n} {\stackrel{p \neq q}{p,q\text{ prime}}}} 1 = \sum_{\stackrel{pq\mid n}{p,q\text{ prime}}} 1 - \sum_{\stackrel{p^2\mid n}{p\text{ prime}}} 1. }[/math]

We can similarly calculate asymptotic formulas more generally for the related summatory functions over so-termed factorial moments of the function [math]\displaystyle{ \omega(n) }[/math].

Dirichlet series

A known Dirichlet series involving [math]\displaystyle{ \omega(n) }[/math] and the Riemann zeta function is given by

[math]\displaystyle{ \sum_{n \geq 1} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta^2(s)}{\zeta(2s)},\ \Re(s) \gt 1. }[/math]

We can also see that

[math]\displaystyle{ \sum_{n \geq 1} \frac{z^{\omega(n)}}{n^s} = \prod_p \left(1 + \frac{z}{p^s-1}\right), |z| \lt 2, \Re(s) \gt 1, }[/math]

[math]\displaystyle{ \sum_{n \geq 1} \frac{z^{\Omega(n)}}{n^s} = \prod_p \left(1 - \frac{z}{p^s}\right)^{-1}, |z| \lt 2, \Re(s) \gt 1, }[/math]

The function [math]\displaystyle{ \Omega(n) }[/math] is completely additive, where [math]\displaystyle{ \omega(n) }[/math] is strongly additive (additive). Now we can prove a short lemma in the following form which implies exact formulas for the expansions of the Dirichlet series over both [math]\displaystyle{ \omega(n) }[/math] and [math]\displaystyle{ \Omega(n) }[/math]:

Lemma. Suppose that [math]\displaystyle{ f }[/math] is a strongly additive arithmetic function defined such that its values at prime powers is given by [math]\displaystyle{ f(p^{\alpha}) := f_0(p, \alpha) }[/math], i.e., [math]\displaystyle{ f(p_1^{\alpha_1} \cdots p_k^{\alpha_k}) = f_0(p_1, \alpha_1) + \cdots + f_0(p_k, \alpha_k) }[/math] for distinct primes [math]\displaystyle{ p_i }[/math] and exponents [math]\displaystyle{ \alpha_i \geq 1 }[/math]. The Dirichlet series of [math]\displaystyle{ f }[/math] is expanded by

[math]\displaystyle{ \sum_{n \geq 1} \frac{f(n)}{n^s} = \zeta(s) \times \sum_{p\mathrm{\ prime}} (1-p^{-s}) \cdot \sum_{n \geq 1} f_0(p, n) p^{-ns}, \Re(s) \gt \min(1, \sigma_f). }[/math]

Proof. We can see that

[math]\displaystyle{ \sum_{n \geq 1} \frac{u^{f(n)}}{n^s} = \prod_{p\mathrm{\ prime}} \left(1+\sum_{n \geq 1} u^{f_0(p, n)} p^{-ns}\right). }[/math]

This implies that

[math]\displaystyle{ \begin{align} \sum_{n \geq 1} \frac{f(n)}{n^s} & = \frac{d}{du}\left[\prod_{p\mathrm{\ prime}} \left(1+\sum_{n \geq 1} u^{f_0(p, n)} p^{-ns}\right)\right] \Biggr|_{u=1} = \prod_{p} \left(1 + \sum_{n \geq 1} p^{-ns}\right) \times \sum_{p} \frac{\sum_{n \geq 1} f_0(p, n) p^{-ns}}{ 1 + \sum_{n \geq 1} p^{-ns}} \\ & = \zeta(s) \times \sum_{p\mathrm{\ prime}} (1-p^{-s}) \cdot \sum_{n \geq 1} f_0(p, n) p^{-ns}, \end{align} }[/math]

wherever the corresponding series and products are convergent. In the last equation, we have used the Euler product representation of the Riemann zeta function. [math]\displaystyle{ \boxdot }[/math]

The lemma implies that for [math]\displaystyle{ \Re(s) \gt 1 }[/math],

[math]\displaystyle{ \begin{align} D_{\omega}(s) & := \sum_{n \geq 1} \frac{\omega(n)}{n^s} = \zeta(s) P(s) \\ & \ = \zeta(s) \times \sum_{n \geq 1} \frac{\mu(n)}{n} \log \zeta(ns) \\ D_{\Omega}(s) & := \sum_{n \geq 1} \frac{\Omega(n)}{n^s} = \zeta(s) \times \sum_{n \geq 1} P(ns) \\ & \ = \zeta(s) \times \sum_{n \geq 1} \frac{\phi(n)}{n} \log\zeta(ns) \\ D_{\Omega\lambda}(s) & := \sum_{n \geq 1} \frac{\lambda(n) \Omega(n)}{n^s} = \zeta(s) \log \zeta(s), \end{align} }[/math]

where [math]\displaystyle{ P(s) }[/math] is the prime zeta function and [math]\displaystyle{ \lambda(n) = (-1)^{\Omega(n)} }[/math] is the Liouville lambda function.

The distribution of the difference of prime omega functions

The distribution of the distinct integer values of the differences [math]\displaystyle{ \Omega(n) - \omega(n) }[/math] is regular in comparison with the semi-random properties of the component functions. For [math]\displaystyle{ k \geq 0 }[/math], define

[math]\displaystyle{ N_k(x) := \#(\{n \in \mathbb{Z}^{+}: \Omega(n) - \omega(n) = k\} \cap [1, x]). }[/math]

These cardinalities have a corresponding sequence of limiting densities [math]\displaystyle{ d_k }[/math] such that for [math]\displaystyle{ x \geq 2 }[/math]

[math]\displaystyle{ N_k(x) = d_k \cdot x + O\left(\left(\frac{3}{4}\right)^k \sqrt{x} (\log x)^{\frac{4}{3}}\right). }[/math]

These densities are generated by the prime products

[math]\displaystyle{ \sum_{k \geq 0} d_k \cdot z^k = \prod_p \left(1 - \frac{1}{p}\right) \left(1 + \frac{1}{p-z}\right). }[/math]

With the absolute constant [math]\displaystyle{ \hat{c} := \frac{1}{4} \times \prod_{p \gt 2} \left(1 - \frac{1}{(p-1)^2}\right)^{-1} }[/math], the densities [math]\displaystyle{ d_k }[/math] satisfy

[math]\displaystyle{ d_k = \hat{c} \cdot 2^{-k} + O(5^{-k}). }[/math]

Compare to the definition of the prime products defined in the last section of in relation to the Erdős–Kac theorem.

See also

• Additive function
• Arithmetic function
• Erdős–Kac theorem
• Omega function (disambiguation)
• Prime number
• Square-free integer

References

• G. H. Hardy and E. M. Wright (2006). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. 
• H. L. Montgomery and R. C. Vaughan (2007). Multiplicative number theory I. Classical theory (1st ed.). Cambridge University Press. 
• Schmidt, Maxie (2017). "Factorization Theorems for Hadamard Products and Higher-Order Derivatives of Lambert Series Generating Functions". arXiv:1712.00608 [math.NT].
• Weisstein, Eric. "Distinct Prime Factors". http://mathworld.wolfram.com/DistinctPrimeFactors.html. 

External links

• OEIS Wiki for related sequence numbers and tables
• OEIS Wiki on Prime Factors