Prime omega function

Uses your system voice; voice and rate in settings.

Snapshot

≈ 11 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In number theory, the prime omega functions \omega(n) and \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 \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 \leq i \leq k ), then the 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.

In number theory, the prime omega functions \omega(n) and \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 \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 \leq i \leq k ), then the 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. Little omega has the formula \omega(n)=\sum_{p\mid n} 1, where notation indicates that the sum is taken over all primes that divide , without multiplicity. For example, \omega(12)=\omega(2^2 3)=2 . Big omega has the formulas \Omega(n) =\sum_{p^\alpha\mid n} 1 =\sum_{p^\alpha\parallel n}\alpha. The notation indicates that the sum is taken over all prime powers that divide , while indicates that the sum is taken over all prime powers that divide and such that is coprime to . For example, \Omega(12)=\Omega(2^2 3^1)=3 . The omegas are related by the inequalities and , where is the divisor-counting function. If , then is squarefree and related to the Möbius function by \mu(n) = (-1)^{\omega(n)} = (-1)^{\Omega(n)}. If \omega(n) = 1 then n is a prime power, and if \Omega(n)=1 then n is prime. An asymptotic series for the average order of \omega(n) is \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 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. \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\limits_{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) \sum_\stackrel{1\le k\le 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: \chi_{\mathbb{P}}(n) \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 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)_\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 \operatorname{sinc} function \operatorname{sinc}(x) = \frac{\sin(\pi x)}{\pi x} is used. \omega(z) = \log_2\left(\sum_{n=1}^{\lceil Re(z) \rceil} \operatorname{sinc} \left(\prod_{m=1}^{\lceil Re(z) \rceil+1} \left( n^2+n-mz \right) \right) \right) This is closely related to the following partition identity. Consider partitions of the form a= \frac{2}{c} + \frac{4}{c} + \ldots + \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 \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 \Omega(n) = \log_2(n). Asymptotics for the summatory functions over \omega(n) , \Omega(n) , and powers of \omega(n) are respectively \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} 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) Other sums relating the two variants of the prime omega functions include \sum_{n \leq x} \left\{\Omega(n) - \omega(n)\right\} = O(x), and \#\left\{n \leq x : \Omega(n) - \omega(n) > \sqrt{\log\log x}\right\} = 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 \leq 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_{\operatorname{odd}}(x) := \sum_{n \leq x} \omega(n) [n\text{ odd}], where [\cdot] denotes Iverson bracket. Then we have that 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). The proof of this result follows by first observing that \omega(2n) = \begin{cases} \omega(n) + 1, & \text{if } n \text{ is odd; } \\ \omega(n), & \text{if } n \text{ is even,} \end{cases} and then applying the asymptotic result from Hardy and Wright for the summatory function over \omega(n) , denoted by S_{\omega}(x) := \sum_{n \leq x} \omega(n) , in the following form: \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}

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\{\omega(n)-1\right\}, by estimating the product of these two component omega functions as \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. 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 \geq 1} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta^2(s)}{\zeta(2s)},\ \Re(s) > 1. We can also see that \sum_{n \geq 1} \frac{z^{\omega(n)}}{n^s} = \prod_p \left(1 + \frac{z}{p^s-1}\right), |z| 1, \sum_{n \geq 1} \frac{z^{\Omega(n)}}{n^s} = \prod_p \left(1 - \frac{z}{p^s}\right)^{-1}, |z| 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^{\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 \geq 1 . The Dirichlet series of f is expanded by \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 \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 \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} 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_h(s) & := \sum_{n \geq 1} \frac{h(n)}{n^s} = \zeta(s) \log \zeta(s) \\ & \ = \zeta(s) \times \sum_{n \geq 1} \frac{\varepsilon(n)}{n} \log \zeta(ns), \end{align} 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 \varepsilon is the identity for the Dirichlet convolution, \varepsilon (n) = \lfloor\frac{1}{n}\rfloor . N_k(x) := \#(\{n \in \mathbb{Z}^{+}: \Omega(n) - \omega(n) = k\} \cap [1, 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{3}{4}\right)^k \sqrt{x} (\log x)^{\frac{4}{3}}\right). These densities are generated by the prime products \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 \hat{c} := \frac{1}{4} \times \prod_{p > 2} \left(1 - \frac{1}{(p-1)^2}\right)^{-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.

Notes

References

External links

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378748356 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.