2
$\begingroup$

Given a sufficiently well-behaved function $1\le f(x)\le x$ and a multiset $S=\{\omega(n): 1\le n\le x\}$, what can be said about the asymptotics of the $f(x)$-th largest member of $S$? In other words, what is the maximum value of $\min(T)$ where $T\subseteq S$ and $|T|=f(x)$?

If $f(x):=1$ this is asking for the largest number of prime factors which a number up to $x$ can be divisible by, which is $\pi(\vartheta^{-1}(\log x)) \sim \log x/\log\log x$ by (two invocations of) the Prime Number Theorem. More generally you get $\pi(\vartheta^{-1}(\log(x/k))) \sim \log x/\log\log x$ for $f(x):=k$ with any fixed constant $k$.

If $f(x):=kx$ for some fixed $0<k<x$ then the Erdős-Kac theorem gives $$ \log\log x+c\sqrt{\log\log x} $$ with a constant $c=-\sqrt2\operatorname{erf}^{-1}(1-2k)$.

I'm interested in $f(x)$ between these two, for example $$ f(x):=x^{1-\frac{\log\log\log x}{\log\log x}}. $$ How is this usually treated? I would appreciate references to the literature -- I'm sure this isn't new and I don't want to reinvent the wheel.

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that the maximal order of $\omega(n)$ is $\sim \frac{\log x}{\log \log x}$, rather than $\log x$ as you claim. I would look in the literature for tail estimates of the distribution of $\omega(n)$—that is, bounds for the number of $n\le x$ for which $\omega(n) > \alpha \log\log x$ for fixed $\alpha>1$, for example. $\endgroup$
    – Greg Martin
    May 6, 2016 at 20:17
  • $\begingroup$ @GregMartin: Oops, I forgot $\pi(\cdot).$ I'll edit. $\endgroup$
    – Charles
    May 6, 2016 at 20:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.