# $\displaystyle x\mathop{log}\nolimits^{2}x=O\left(\sum@\slimits@@@_{n\leq x}2^{% \Omega(n)}\right)$

Within this entry, $\Omega$ refers to the number of (nondistinct) prime factors  function  (http://planetmath.org/NumberOfNondistinctPrimeFactorsFunction), $\tau$ refers to the divisor function    , $\mu$ refers to the Möbius function, $\lfloor\,\cdot\,\rfloor$ refers to the floor function, $\log$ refers to the natural logarithm   , $p$ refers to a prime, and $d$, $k$, $\ell$, $m$, and $n$ refer to positive integers.

###### Theorem.

$\displaystyle x\log^{2}x=O\left(\sum_{n\leq x}2^{\Omega(n)}\right)$

###### Proof.
$\displaystyle\sum_{n\leq x}2^{\Omega(n)}$ $\displaystyle=\sum_{\begin{subarray}{c}2^{k}m\leq x\\ m\text{ is odd}\end{subarray}}2^{\Omega(2^{k}m)}$ $\displaystyle=\sum_{2^{k}\leq x}2^{\Omega(2^{k})}\sum_{\begin{subarray}{c}m% \leq\frac{x}{2^{k}}\\ m\text{ is odd}\end{subarray}}2^{\Omega(m)}$ since $2^{\Omega}$ is multiplicative $\displaystyle\geq\sum_{k\leq\frac{\log x}{\log 2}}2^{k}\sum_{\begin{subarray}{% c}m\leq\frac{x}{2^{k}}\\ m\text{ is odd}\end{subarray}}\tau(m)$ $\displaystyle\geq\sum_{k\leq\frac{\log x}{\log 2}}2^{k}\sum_{\begin{subarray}{% c}d\leq\frac{x}{2^{k}}\\ d\text{ is odd}\end{subarray}}\,\sum_{\begin{subarray}{c}\ell\leq\frac{x}{2^{k% }d}\\ \ell\text{ is odd}\end{subarray}}1$ by the convolution method $\displaystyle\geq\sum_{k\leq\frac{\log x}{\log 2}}2^{k}\sum_{\begin{subarray}{% c}d\leq\frac{x}{2^{k}}\\ d\text{ is odd}\end{subarray}}\frac{x}{2^{k+2}d}$ $\displaystyle\geq\frac{x}{4}\sum_{k\leq\frac{\log x}{\log 2}}\sum_{% \begin{subarray}{c}d\leq\frac{x}{2^{k}}\\ d\text{ is odd}\end{subarray}}\frac{1}{d}$ $\displaystyle\geq\frac{x}{4}\sum_{k\leq\frac{\log x}{\log 2}}\left(\frac{1}{x}% \sum_{\begin{subarray}{c}d\leq\frac{x}{2^{k}}\\ d\text{ is odd}\end{subarray}}1-\int_{1}^{\frac{x}{2^{k}}}\frac{-1}{t^{2}}% \left(\sum_{\begin{subarray}{c}d\leq t\\ d\text{ is odd}\end{subarray}}1\right)\,dt\right)$ by summation by parts  (http://planetmath.org/AbelsLemma) $\displaystyle\geq\frac{x}{4}\sum_{k\leq\frac{\log x}{\log 2}}\left(\frac{1}{x}% \cdot\frac{x}{2^{k+2}}+\int_{1}^{\frac{x}{2^{k}}}\frac{1}{t^{2}}\cdot\frac{t}{% 2}\,dt\right)$ $\displaystyle\geq\frac{x}{4}\sum_{k\leq\frac{\log x}{\log 2}}\left(\frac{1}{2^% {k+2}}+\frac{1}{2}\int_{1}^{\frac{x}{2^{k}}}\frac{1}{t}\,dt\right)$ $\displaystyle\geq\frac{x}{4}\sum_{k\leq\frac{\log x}{\log 2}}\left(\frac{1}{2^% {k+2}}+\frac{1}{2}\log\left(\frac{x}{2^{k}}\right)\right)$ $\displaystyle\geq\frac{x}{16}\sum_{k\leq\frac{\log x}{\log 2}}\left(\frac{1}{2% ^{k}}+\log x-k\log 2\right)$ $\displaystyle\geq\frac{x}{16}\left(\frac{1}{2}\left(\frac{1-\left(\frac{1}{2}% \right)^{\left\lfloor\frac{\log x}{\log 2}\right\rfloor+1}}{1-\frac{1}{2}}% \right)+\log x\left\lfloor\frac{\log x}{\log 2}\right\rfloor-\log 2\left(\frac% {\left\lfloor\frac{\log x}{\log 2}\right\rfloor^{2}+\left\lfloor\frac{\log x}{% \log 2}\right\rfloor}{2}\right)\right)$ $\displaystyle\geq\frac{x}{16}\left\lfloor\frac{\log x}{\log 2}\right\rfloor% \left(\log x-\frac{1}{2}\log 2\left(\left\lfloor\frac{\log x}{\log 2}\right% \rfloor+1\right)\right)$ $\displaystyle\geq\frac{x}{16}\left\lfloor\frac{\log x}{\log 2}\right\rfloor% \left(\log x-\frac{1}{2}\log 2\left(\frac{\log x}{\log 2}+1\right)\right)$ $\displaystyle\geq\frac{x}{16}\left\lfloor\frac{\log x}{\log 2}\right\rfloor% \left(\log x-\frac{1}{2}\log x-\frac{1}{2}\log 2\right)$ $\displaystyle\geq\frac{x}{32}\left\lfloor\frac{\log x}{\log 2}\right\rfloor% \log\left(\frac{x}{2}\right)$

Since, for $x$ sufficiently large, $\displaystyle\log x=O\left(\log\left(\frac{x}{2}\right)\right)$ and $\displaystyle\log x=O\left(\left\lfloor\frac{\log x}{\log 2}\right\rfloor\right)$, it follows that $\displaystyle x\log^{2}x=O\left(\sum_{n\leq x}2^{\Omega(n)}\right)$. ∎

Title $\displaystyle x\mathop{log}\nolimits^{2}x=O\left(\sum@\slimits@@@_{n\leq x}2^{% \Omega(n)}\right)$ displaystyleXlog2xOleftsumnleX2Omeganright 2013-03-22 16:09:18 2013-03-22 16:09:18 Wkbj79 (1863) Wkbj79 (1863) 16 Wkbj79 (1863) Theorem msc 11N37 AsymptoticEstimate ConvolutionMethod DisplaystyleYOmeganOleftFracxlogXy12YRightFor1LeY2