Prime Omega Function

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

Properties and relations

The function $\omega(n)$ is additive and $\Omega(n)$ is completely additive.

$\omega(n)=\sum_ 1$

If $p$ divides $n$ at least once we count it only once, e.g. $\omega(12)=\omega(2^2 3)=2$.

$\Omega(n) =\sum_ 1 =\sum_\alpha$

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

$\Omega(n) \ge \omega(n)$

If $\Omega(n)=\omega(n)$ then $n$ is squarefree and related to the Möbius function by

:$\mu(n) = (-1)^ = (-1)^$

If $\Omega(n)=1$ then $n$ is a prime number.

It is known that the average order of the divisor function satisfies $2^ \leq d(n) \leq 2^$.

Like many arithmetic functions there is no explicit formula for $\Omega(n)$ or $\omega(n)$ but there are approximations.

An asymptotic series for the average order of $\omega(n)$ is given by

:$\frac \sum\limits_^n \omega(k) \sim \log\log n + B_1 + \sum_ \left(\sum_^ \frac - 1\right) \frac,$

where $B_1 \approx 0.26149721$ is the Mertens constant and $\gamma_j$ are the Stieltjes constants.

The function $\omega(n)$ is related to divisor sums over the Möbius function and the divisor function including the next sums.

:$\sum_ , \mu(d), = 2^$
:$\sum_ , \mu(d), k^ = (k+1)^$
:$\sum_ 2^ = d(n^2)$
:$\sum_ 2^ d\left(\frac\right) = d^2(n)$
:$\sum_ (-1)^ = \prod\limits_ (1-\alpha)$
:$\sum_ \gcd(k^2-1,m_1)\gcd(k^2-1,m_2) =\varphi(n)\sum_ \varphi(\gcd(d_1, d_2)) 2^,\ m_1, m_2 \text, m = \operatorname(m_1, m_2)$
:$\sum_\stackrel \!\!\!\! 1 = n \frac + O \left ( 2^ \right )$

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

:$\chi_(n) = (\mu \ast \omega)(n) = \sum_ \omega(d) \mu(n/d).$

A partition-related exact identity for $\omega(n)$ is given by

:\omega(n) = \log_2\left \mu(j), \right

where $p(n)$ is the partition function, $\mu(n)$ is the Möbius function, and the triangular sequence $s_$ is expanded by

:s_ = ^n(q; q)_\infty \frac = s_o(n, k) - s_e(n, k),

in terms of the infinite q-Pochhammer symbol and the restricted partition functions $s_(n, k)$ which respectively denote the number of $k$'s in all partitions of $n$ into an ''odd'' (''even'') number of distinct parts.

Continuation to the complex plane

A continuation of $\omega(n)$ has been found, though it is not analytic everywhere. Note that the normalized $\operatorname$ function $\operatorname(x) = \frac$ is used.

:$\omega(z) = \log_2\left(\sum_^ \operatorname \left(\prod_^ \left( x^2+x-yz \right) \right) \right)$

Average order and summatory functions

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

Asymptotics for the summatory functions over $\omega(n)$, $\Omega(n)$, and $\omega(n)^2$
are respectively computed in Hardy and Wright as

:$\begin \sum_ \omega(n) & = x \log\log x + B_1 x + o(x) \\ \sum_ \Omega(n) & = x \log\log x + B_2 x + o(x) \\ \sum_ \omega(n)^2 & = x (\log\log x)^2 + O(x \log\log x) \\ \sum_ \omega(n)^k & = x (\log\log x)^k + O(x (\log\log x)^), k \in \mathbb^, \end$

where $B_1 \approx 0.2614972128$ is the Mertens constant and the constant $B_2$ is defined by

:$B_2 = B_1 + \sum_ \frac \approx 1.0345061758.$

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

:$\sum_ \left\ = O(x),$

and

:$\#\left\ = O\left(\frac\right).$

Example I: A modified summatory function

In this example we suggest a variant of the summatory functions $S_(x) := \sum_ \omega(n)$ estimated in the above results for sufficiently large $x$. We then prove an asymptotic formula for the growth of this modified summatory function derived from the asymptotic estimate of $S_(x)$ 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

:S_(x) := \sum_ \omega(n) \text

where cdot/math> denotes Iverson bracket. Then we have that

:S_(x) = \frac \log\log x + \frac + \left\ - \left \equiv 2,3 \bmod\right+ O\left(\frac\right).

The proof of this result follows by first observing that

:$\omega(2n) = \begin \omega(n) + 1, & \text n \text \\ \omega(n), & \text n \text \end$

and then applying the asymptotic result from Hardy and Wright for the summatory function over $\omega(n)$, denoted by $S_(x) := \sum_ \omega(n)$, in the following form:

:$\begin S_\omega(x) & = S_(x) + \sum_ \omega(2n) \\ & = S_(x) + \sum_ \left(\omega(4n) + \omega(4n+2)\right) \\ & = S_(x) + \sum_ \left(\omega(2n) + \omega(2n+1) + 1\right) \\ & = S_(x) + S_\left(\left\lfloor\frac\right\rfloor\right) + \left\lfloor\frac\right\rfloor. \end$

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

:$\omega(n) \left\,$

by estimating the product of these two component omega functions as

:$\omega(n) \left\ = \sum_ 1 = \sum_ 1 - \sum_ 1.$

We can similarly calculate asymptotic formulas more generally for the related summatory functions over so-termed factorial moments of the function $\omega(n)$.

Dirichlet series

A known Dirichlet series involving $\omega(n)$ and the Riemann zeta function is given by

:$\sum_ \frac = \frac,\ \Re(s) > 1.$

We can also see that
:$\sum_ \frac = \prod_p \left(1 + \frac\right), , z, < 2, \Re(s) > 1,$
:$\sum_ \frac = \prod_p \left(1 - \frac\right)^, , z, < 2, \Re(s) > 1,$

The function $\Omega(n)$ is completely additive, where $\omega(n)$ 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 $\omega(n)$ and $\Omega(n)$:

Lemma. Suppose that $f$ is a strongly additive arithmetic function defined such that its values at prime powers is given by $f(p^) := f_0(p, \alpha)$, i.e., $f(p_1^ \cdots p_k^) = f_0(p_1, \alpha_1) + \cdots + f_0(p_k, \alpha_k)$ for distinct primes $p_i$ and exponents $\alpha_i \geq 1$. The Dirichlet series of $f$ is expanded by
:$\sum_ \frac = \zeta(s) \times \sum_ (1-p^) \cdot \sum_ f_0(p, n) p^, \Re(s) > \min(1, \sigma_f).$
''Proof.'' We can see that
:$\sum_ \frac = \prod_ \left(1+\sum_ u^ p^\right).$
This implies that

: \begin
\sum_ \frac & =
\frac\left prod_ \left(1+\sum_ u^ p^\right)\right\Biggr, _
=
\prod_ \left(1 + \sum_ p^\right) \times \sum_ \frac \\
& = \zeta(s) \times \sum_ (1-p^) \cdot \sum_ f_0(p, n) p^,
\end

wherever the corresponding series and products are convergent. In the last equation, we have used the Euler product representation of the Riemann zeta function. $\boxdot$

The lemma implies that for $\Re(s) > 1$,

:$\begin D_(s) & := \sum_ \frac = \zeta(s) P(s) \\ & \ = \zeta(s) \times \sum_ \frac \log \zeta(ns) \\ D_(s) & := \sum_ \frac = \zeta(s) \times \sum_ P(ns) \\ & \ = \zeta(s) \times \sum_ \frac \log\zeta(ns) \\ D_(s) & := \sum_ \frac = \zeta(s) \log \zeta(s), \end$
where $P(s)$ is the prime zeta function and $\lambda(n) = (-1)^$ is the
Liouville lambda function.

The distribution of the difference of prime omega functions

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

:$N_k(x) := \#(\ \cap$, x.

These cardinalities have a corresponding sequence of limiting densities $d_k$ such that for $x \geq 2$

:$N_k(x) = d_k \cdot x + O\left(\left(\frac\right)^k \sqrt (\log x)^\right).$

These densities are generated by the prime products

:$\sum_ d_k \cdot z^k = \prod_p \left(1 - \frac\right) \left(1 + \frac\right).$

With the absolute constant $\hat := \frac \times \prod_ \left(1 - \frac\right)^$,
the densities $d_k$ satisfy

:$d_k = \hat \cdot 2^ + O(5^).$

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

Notes

References

*
*
*
*{{cite web, last1=Weisstein, first1=Eric, title=Distinct Prime Factors, url=http://mathworld.wolfram.com/DistinctPrimeFactors.html, website=MathWorld, access-date=22 April 2018

External links

OEIS Wiki for related sequence numbers and tables

OEIS Wiki on Prime Factors

Number theory
Prime numbers
Additive functions
Integer sequences