Prime omega function

Template:Short description In number theory, the prime omega functions $\omega (n)$ and $\mathrm{\Omega }(n)$ count the number of prime factors of a natural number $n.$ The number of distinct prime factors is assigned to $\omega (n)$ (little omega), while $\mathrm{\Omega }(n)$ (big omega) counts the total number of prime factors with multiplicity (see arithmetic function). That is, if we have a prime factorization of $n$ of the form $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ for distinct primes $p_i$ ($1\le i\le k$), then the prime omega functions are given by $\omega (n)=k$ and $\mathrm{\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 $\mathrm{\Omega }(n)$ is completely additive. Little omega has the formula

$\omega (n)=\sum _{p\mid n}1,$

where notation Template:Math indicates that the sum is taken over all primes Template:Mvar that divide Template:Mvar, without multiplicity. For example, $\omega (12)=\omega (2^{2}3)=2$.

Big omega has the formulas

$\mathrm{\Omega }(n)=\sum _{p^{\alpha }\mid n}1=\sum _{p^{\alpha }\parallel n}\alpha .$

The notation Template:Math indicates that the sum is taken over all prime powers Template:Math that divide Template:Mvar, while Template:Math indicates that the sum is taken over all prime powers Template:Math that divide Template:Mvar and such that Template:Math is coprime to Template:Math. For example, $\mathrm{\Omega }(12)=\mathrm{\Omega }(2^2{3}^1)=3$.

The omegas are related by the inequalities Template:Math and Template:Math, where Template:Math is the divisor-counting function. If Template:Math, then Template:Mvar is squarefree and related to the Möbius function by

$\mu (n)=(-1{)}^{\omega (n)}=(-1{)}^{\mathrm{\Omega }(n)}.$

If $\omega (n)=1$ then $n$ is a prime power, and if $\mathrm{\Omega }(n)=1$ then $n$ is prime.

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

$\frac{1}{n}\sum _{k=1}^n\omega (k)\sim \log \log n+B_1+\sum _{k\ge 1}(\sum _{j=0}^{k-1}\frac{{\gamma }_j}{j!}-1)\frac{(k-1)!}{(\log n{)}^k},$

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:

$\sum _{d\mid n}|\mu (d)|=2^{\omega (n)}$ is the number of unitary divisors. Template:Oeis

$\sum _{d\mid n}|\mu (d)|k^{\omega (d)}=(k+1{)}^{\omega (n)}$

$\sum _{r\mid n}{2}^{\omega (r)}=d(n^2)$

$\sum _{r\mid n}{2}^{\omega (r)}d\left(\frac{n}{r}\right)=d^2(n)$

$\sum _{d\mid n}(-1{)}^{\omega (d)}=\prod _{p^{\alpha }||n}(1-\alpha )$

$\sum _{\stackrel{1\le k\le m}{(k,m)=1}}\gcd (k^2-1,m_1)\gcd (k^2-1,m_2)=\phi (n)\sum _{\stackrel{d_1\mid m_1}{d_2\mid m_2}}\phi (\gcd (d_1,d_2))2^{\omega (\mathrm{lcm}(d_1,d_2))},m_1,m_2\text{ odd},m=\mathrm{lcm}(m_1,m_2)$

$\sum _{\stackrel{1\le k\le n}{\gcd (k,m)=1}}1=n\frac{\phi (m)}{m}+O\left(2^{\omega (m)}\right)$

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

${\chi }_{\mathbb{P}}(n)=(\mu \ast \omega )(n)=\sum _{d|n}\omega (d)\mu (n/d).$

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

$\omega (n)={\log }_2[\sum _{k=1}^n\sum _{j=1}^k(\sum _{d\mid k}\sum _{i=1}^{d}p(d-ji))s_{n,k}\cdot |\mu (j)|],$

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

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

in terms of the infinite q-Pochhammer symbol and the restricted partition functions $s_{o/e}(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 $\mathrm{sinc}$ function $\mathrm{sinc}(x)=\frac{\sin (\pi x)}{\pi x}$ is used.

$\omega (z)={\log }_2(\sum _{n=1}^{\lceil Re(z)\rceil }\mathrm{sinc}\left(\prod _{m=1}^{\lceil Re(z)\rceil +1}(n^2+n-mz)\right))$

This is closely related to the following partition identity. Consider partitions of the form

$a=\frac{2}{c}+\frac{4}{c}+\dots +\frac{2(b-1)}{c}+\frac{2b}{c}$

where $a$, $b$, and $c$ are positive integers, and $a>b>c$. The number of partitions is then given by $2^{\omega (a)}-2$.

Average order and summatory functions

An average order of both $\omega (n)$ and $\mathrm{\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{\log n}{\log \log n}$

on average order. When $n$ is a power of 2, then $\mathrm{\Omega }(n)={\log }_2(n).$

Asymptotics for the summatory functions over $\omega (n)$, $\mathrm{\Omega }(n)$, and powers of $\omega (n)$ are respectively

$\begin{array}{cc}\sum _{n\le x}\omega (n)& =x\log \log x+B_{1}x+o(x)\\ \sum _{n\le x}\mathrm{\Omega }(n)& =x\log \log x+B_{2}x+o(x)\\ \sum _{n\le x}\omega (n{)}^2& =x(\log \log x{)}^2+O(x\log \log x)\\ \sum _{n\le x}\omega (n{)}^k& =x(\log \log x{)}^k+O(x(\log \log x{)}^{k-1}),k\in {\mathbb{Z}}^{+},\end{array}$

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

$B_2=B_1+\sum _{p\text{ prime}}\frac{1}{p(p-1)}\approx 1.0345061758.$

The sum of number of unitary divisors is

$\sum _{n\le x}{2}^{\omega (n)}=(x\log x)/\zeta (2)+O(x)$ Template:OEIS

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

$\sum _{n\le x}\{\mathrm{\Omega }(n)-\omega (n)\}=O(x),$

and

$\mathrm{\#}\{n\le x:\mathrm{\Omega }(n)-\omega (n)>\sqrt{\log \log x}\}=O\left(\frac{x}{(\log \log x{)}^{1/2}}\right).$

Example I: A modified summatory function

In this example we suggest a variant of the summatory functions $S_{\omega }(x):=\sum _{n\le x}\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_{\omega }(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_{\mathrm{odd}}(x):=\sum _{n\le x}\omega (n)[n\text{ odd}],$

where $[\cdot ]$ denotes Iverson bracket. Then we have that

$S_{\mathrm{odd}}(x)=\frac{x}{2}\log \log x+\frac{(2B_1-1)x}{4}+\left\{\frac{x}{4}\right\}-[x\equiv 2,3mod4]+O\left(\frac{x}{\log x}\right).$

The proof of this result follows by first observing that

$\omega (2n)=\{\begin{array}{cc}\omega (n)+1,& \text{if }n\text{ is odd; }\\ \omega (n),& \text{if }n\text{ is even,}\end{array}$

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

$\begin{array}{cc}{S}_{\omega }(x)& =S_{\mathrm{odd}}(x)+\sum _{n\le \lfloor \frac{x}{2}\rfloor }\omega (2n)\\ & =S_{\mathrm{odd}}(x)+\sum _{n\le \lfloor \frac{x}{4}\rfloor }(\omega (4n)+\omega (4n+2))\\ & =S_{\mathrm{odd}}(x)+\sum _{n\le \lfloor \frac{x}{4}\rfloor }(\omega (2n)+\omega (2n+1)+1)\\ & =S_{\mathrm{odd}}(x)+S_{\omega }\left(\lfloor \frac{x}{2}\rfloor \right)+\lfloor \frac{x}{4}\rfloor .\end{array}$

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)\{\omega (n)-1\},$

by estimating the product of these two component omega functions as

$\omega (n)\{\omega (n)-1\}=\sum _{\stackrel{pq\mid n}{\stackrel{p\ne 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.$

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 _{n\ge 1}\frac{2^{\omega (n)}}{n^s}=\frac{{\zeta }^2(s)}{\zeta (2s)},\mathrm{\Re }(s)>1.$

We can also see that

$\sum _{n\ge 1}\frac{z^{\omega (n)}}{n^s}=\prod _p(1+\frac{z}{p^s-1}),|z|<2,\mathrm{\Re }(s)>1,$

$\sum _{n\ge 1}\frac{z^{\mathrm{\Omega }(n)}}{n^s}=\prod _p{(1-\frac{z}{p^s})}^{-1},|z|<2,\mathrm{\Re }(s)>1,$

The function $\mathrm{\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 $\mathrm{\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^{\alpha }):=f_0(p,\alpha )$, i.e., $f(p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k})=f_0(p_1,{\alpha }_1)+\cdots +f_0(p_k,{\alpha }_k)$ for distinct primes $p_i$ and exponents ${\alpha }_i\ge 1$. The Dirichlet series of $f$ is expanded by

$\sum _{n\ge 1}\frac{f(n)}{n^s}=\zeta (s)\times \sum _{p\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}}(1-p^{-s})\cdot \sum _{n\ge 1}{f}_0(p,n)p^{-ns},\mathrm{\Re }(s)>\min (1,{\sigma }_f).$

Proof. We can see that

$\sum _{n\ge 1}\frac{u^{f(n)}}{n^s}=\prod _{p\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}}(1+\sum _{n\ge 1}{u}^{f_0(p,n)}{p}^{-ns}).$

This implies that

$\begin{array}{cc}\sum _{n\ge 1}\frac{f(n)}{n^s}& =\frac{d}{du}\left[\prod _{p\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}}(1+\sum _{n\ge 1}{u}^{f_0(p,n)}{p}^{-ns})\right]{|}_{u=1}=\prod _p(1+\sum _{n\ge 1}{p}^{-ns})\times \sum _p\frac{\sum _{n\ge 1}{f}_0(p,n)p^{-ns}}{1+\sum _{n\ge 1}{p}^{-ns}}\\ & =\zeta (s)\times \sum _{p\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}}(1-p^{-s})\cdot \sum _{n\ge 1}{f}_0(p,n)p^{-ns},\end{array}$

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

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

$\begin{array}{cc}{D}_{\omega }(s)& :=\sum _{n\ge 1}\frac{\omega (n)}{n^s}=\zeta (s)P(s)\\ & =\zeta (s)\times \sum _{n\ge 1}\frac{\mu (n)}{n}\log \zeta (ns)\\ D_{\mathrm{\Omega }}(s)& :=\sum _{n\ge 1}\frac{\mathrm{\Omega }(n)}{n^s}=\zeta (s)\times \sum _{n\ge 1}P(ns)\\ & =\zeta (s)\times \sum _{n\ge 1}\frac{\varphi (n)}{n}\log \zeta (ns)\\ D_h(s)& :=\sum _{n\ge 1}\frac{h(n)}{n^s}=\zeta (s)\log \zeta (s)\\ & =\zeta (s)\times \sum _{n\ge 1}\frac{\epsilon (n)}{n}\log \zeta (ns),\end{array}$

where $P(s)$ is the prime zeta function, $h(n)=\sum _{p^k|n}\frac{1}{k}=\sum _{p^k||n}{H}_k$ where $H_k$ is the $k$-th harmonic number and $\epsilon$ is the identity for the Dirichlet convolution, $\epsilon (n)=\lfloor \frac{1}{n}\rfloor$.

The distribution of the difference of prime omega functions

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

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

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

$N_k(x)=d_k\cdot x+O({\left(\frac{3}{4}\right)}^k\sqrt{x}(\log x{)}^{\frac{4}{3}}).$

These densities are generated by the prime products

$\sum _{k\ge 0}{d}_k\cdot z^k=\prod _p(1-\frac{1}{p})(1+\frac{1}{p-z}).$

With the absolute constant $\hat{c}:=\frac{1}{4}\times \prod _{p>2}{(1-\frac{1}{(p-1{)}^2})}^{-1}$, the densities $d_k$ satisfy

$d_k=\hat{c}\cdot 2^{-k}+O(5^{-k}).$

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

• Template:Cite book
• Template:Cite book
• Template:Cite arXiv
• Template:Cite web

External links

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