In number theory, the prime omega functions ${\displaystyle \omega (n)}$ and ${\displaystyle \Omega (n)}$ count the number of prime factors of a natural number ${\displaystyle n.}$ Thereby ${\displaystyle \omega (n)}$ (little omega) counts each distinct prime factor, whereas the related function ${\displaystyle \Omega (n)}$ (big omega) counts the total number of prime factors of ${\displaystyle n,}$ honoring their multiplicity (see arithmetic function). That is, if we have a prime factorization of ${\displaystyle n}$ of the form ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$ for distinct primes ${\displaystyle p_{i}}$ (${\displaystyle 1\leq i\leq k}$), then the respective prime omega functions are given by ${\displaystyle \omega (n)=k}$ and ${\displaystyle \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 ${\displaystyle \omega (n)}$ is additive and ${\displaystyle \Omega (n)}$ is completely additive.

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

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

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

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

${\displaystyle \Omega (n)\geq \omega (n)}$

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

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

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

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

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

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

${\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}}},}$

where ${\displaystyle B_{1}\approx 0.26149721}$ is the Mertens constant and ${\displaystyle \gamma _{j}}$ are the Stieltjes constants.

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

${\displaystyle \sum _{d\mid n}|\mu (d)|=2^{\omega (n)}}$

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

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

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

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

${\displaystyle \sum _{\stackrel {1\leq k\leq 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})}$

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (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:^[4]

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

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

${\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],}$

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

${\displaystyle s_{n,k}=[q^{n}](q;q)_{\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 ${\displaystyle s_{o/e}(n,k)}$ which respectively denote the number of ${\displaystyle k}$'s in all partitions of ${\displaystyle n}$ into an odd (even) number of distinct parts.^[6]

Continuation to the complex plane

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

${\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)}$

Average order and summatory functions

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

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

where ${\displaystyle B_{1}\approx 0.2614972128}$ is the Mertens constant and the constant ${\displaystyle B_{2}}$ is defined by

${\displaystyle B_{2}=B_{1}+\sum _{p{\text{ prime}}}{\frac {1}{p(p-1)}}\approx 1.0345061758.}$

Other sums relating the two variants of the prime omega functions include ^[11]

${\displaystyle \sum _{n\leq x}\left\{\Omega (n)-\omega (n)\right\}=O(x),}$

and

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

Dirichlet series

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

${\displaystyle \sum _{n\geq 1}{\frac {2^{\omega (n)}}{n^{s}}}={\frac {\zeta ^{2}(s)}{\zeta (2s)}},\ \Re (s)>1.}$

We can also see that

${\displaystyle \sum _{n\geq 1}{\frac {z^{\omega (n)}}{n^{s}}}=\prod _{p}\left(1+{\frac {z}{p^{s}-1}}\right),|z|<2,\Re (s)>1,}$

${\displaystyle \sum _{n\geq 1}{\frac {z^{\Omega (n)}}{n^{s}}}=\prod _{p}\left(1-{\frac {z}{p^{s}}}\right)^{-1},|z|<2,\Re (s)>1,}$

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

Lemma. Suppose that ${\displaystyle f}$ is a strongly additive arithmetic function defined such that its values at prime powers is given by ${\displaystyle f(p^{\alpha }):=f_{0}(p,\alpha )}$, i.e., ${\displaystyle 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 ${\displaystyle p_{i}}$ and exponents ${\displaystyle \alpha _{i}\geq 1}$. The Dirichlet series of ${\displaystyle f}$ is expanded by

${\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)>\min(1,\sigma _{f}).}$

Proof. We can see that

${\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).}$

This implies that

${\displaystyle {\begin{aligned}\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{aligned}}}$

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

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

${\displaystyle {\begin{aligned}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{aligned}}}$

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

The distribution of the difference of prime omega functions

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

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

These cardinalities have a corresponding sequence of limiting densities ${\displaystyle d_{k}}$ such that for ${\displaystyle x\geq 2}$

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

These densities are generated by the prime products

${\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).}$

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

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

Compare to the definition of the prime products defined in the last section of ^[14] 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

• 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". MathWorld. Retrieved 22 April 2018.

External links

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