$x{log}^{2}x=O\left({\displaystyle \sum \mathrm{@}\mathrm{@}\mathrm{@}{\mathrm{@}}_{n\le x}{2}^{\mathrm{\Omega }(n)}}\right)$

Within this entry, $\mathrm{\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$, $\mathrm{\ell }$, $m$, and $n$ refer to positive integers.

Theorem.

$x{\log }^{2}x=O\left({\displaystyle \sum _{n\le x}}{2}^{\mathrm{\Omega }(n)}\right)$

Proof.

${\displaystyle \sum _{n\le x}}{2}^{\mathrm{\Omega }(n)}$	$={\displaystyle \sum _{\begin{array}{c}{2}^{k}m\le x\\ m\text{ is odd}\end{array}}}{2}^{\mathrm{\Omega }(2^{k}m)}$
	$={\displaystyle \sum _{2^k\le x}}{2}^{\mathrm{\Omega }(2^k)}{\displaystyle \sum _{\begin{array}{c}m\le \frac{x}{2^k}\\ m\text{ is odd}\end{array}}}{2}^{\mathrm{\Omega }(m)}$ since $2^{\mathrm{\Omega }}$ is multiplicative
	$\ge {\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}{2}^k{\displaystyle \sum _{\begin{array}{c}m\le \frac{x}{2^k}\\ m\text{ is odd}\end{array}}}\tau (m)$
	$\ge {\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}{2}^k{\displaystyle \sum _{\begin{array}{c}d\le \frac{x}{2^k}\\ d\text{ is odd}\end{array}}}{\displaystyle \sum _{\begin{array}{c}\mathrm{\ell }\le \frac{x}{2^{k}d}\\ \mathrm{\ell }\text{ is odd}\end{array}}}1$ by the convolution method
	$\ge {\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}{2}^k{\displaystyle \sum _{\begin{array}{c}d\le \frac{x}{2^k}\\ d\text{ is odd}\end{array}}}{\displaystyle \frac{x}{2^{k+2}d}}$
	$\ge {\displaystyle \frac{x}{4}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}{\displaystyle \sum _{\begin{array}{c}d\le \frac{x}{2^k}\\ d\text{ is odd}\end{array}}}{\displaystyle \frac{1}{d}}$
	$\ge {\displaystyle \frac{x}{4}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}\left({\displaystyle \frac{1}{x}}{\displaystyle \sum _{\begin{array}{c}d\le \frac{x}{2^k}\\ d\text{ is odd}\end{array}}}1-{\displaystyle {\int }_1^{\frac{x}{2^k}}}{\displaystyle \frac{-1}{t^2}}\left({\displaystyle \sum _{\begin{array}{c}d\le t\\ d\text{ is odd}\end{array}}}1\right)𝑑t\right)$ by summation by parts (http://planetmath.org/AbelsLemma)
	$\ge {\displaystyle \frac{x}{4}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}\left({\displaystyle \frac{1}{x}}\cdot {\displaystyle \frac{x}{2^{k+2}}}+{\displaystyle {\int }_1^{\frac{x}{2^k}}}{\displaystyle \frac{1}{t^2}}\cdot {\displaystyle \frac{t}{2}}𝑑t\right)$
	$\ge {\displaystyle \frac{x}{4}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}\left({\displaystyle \frac{1}{2^{k+2}}}+{\displaystyle \frac{1}{2}}{\displaystyle {\int }_1^{\frac{x}{2^k}}}{\displaystyle \frac{1}{t}}𝑑t\right)$
	$\ge {\displaystyle \frac{x}{4}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}\left({\displaystyle \frac{1}{2^{k+2}}}+{\displaystyle \frac{1}{2}}\log \left({\displaystyle \frac{x}{2^k}}\right)\right)$
	$\ge {\displaystyle \frac{x}{16}}{\displaystyle \sum _{k\le \frac{\log x}{\log 2}}}\left({\displaystyle \frac{1}{2^k}}+\log x-k\log 2\right)$
	$\ge {\displaystyle \frac{x}{16}}\left({\displaystyle \frac{1}{2}}\left({\displaystyle \frac{1-{\left(\frac{1}{2}\right)}^{\lfloor \frac{\log x}{\log 2}\rfloor +1}}{1-\frac{1}{2}}}\right)+\log x\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor -\log 2\left({\displaystyle \frac{{\lfloor \frac{\log x}{\log 2}\rfloor }^2+\lfloor \frac{\log x}{\log 2}\rfloor }{2}}\right)\right)$
	$\ge {\displaystyle \frac{x}{16}}\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor \left(\log x-{\displaystyle \frac{1}{2}}\log 2\left(\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor +1\right)\right)$
	$\ge {\displaystyle \frac{x}{16}}\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor \left(\log x-{\displaystyle \frac{1}{2}}\log 2\left({\displaystyle \frac{\log x}{\log 2}}+1\right)\right)$
	$\ge {\displaystyle \frac{x}{16}}\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor \left(\log x-{\displaystyle \frac{1}{2}}\log x-{\displaystyle \frac{1}{2}}\log 2\right)$
	$\ge {\displaystyle \frac{x}{32}}\lfloor {\displaystyle \frac{\log x}{\log 2}}\rfloor \log \left({\displaystyle \frac{x}{2}}\right)$

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

Title	$x{log}^{2}x=O\left({\displaystyle \sum \mathrm{@}\mathrm{@}\mathrm{@}{\mathrm{@}}_{n\le x}{2}^{\mathrm{\Omega }(n)}}\right)$
Canonical name	displaystyleXlog2xOleftsumnleX2Omeganright
Date of creation	2013-03-22 16:09:18
Last modified on	2013-03-22 16:09:18
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	16
Author	Wkbj79 (1863)
Entry type	Theorem
Classification	msc 11N37
Related topic	AsymptoticEstimate
Related topic	ConvolutionMethod
Related topic	DisplaystyleYOmeganOleftFracxlogXy12YRightFor1LeY2