Erdos-Kac law state a typical number of magnitude $n$ has $\log\log n$ prime factors.

  1. What is magnitude and distribution of largest prime factor of typical magnitude $n$ natural number?

  2. What is magnitude and distribution of largest and second largest prime factor of typical magnitude $n$ natural number given than there is a prime factor $p|n$ of size $n^{0.25\pm\epsilon}$?

Assume $\epsilon\in(0,0.25)$ is fixed.

I am also interested in 1. and 2. for square-free scenario.

  • $\begingroup$ I'm no number theorist nor analyst, but my back-of-the-envelope calculation suggests that as long as $\alpha \leq 1$ is not too small, the probability that all prime factors of $n$ are $\leq n^\alpha$ should be about $\alpha$. $\endgroup$ – Tim Campion Jun 17 at 2:03
  • $\begingroup$ @TimCampion It might be a good heuristic. Mind elaborating? $\endgroup$ – Turbo Jun 17 at 2:04
  • 1
    $\begingroup$ Assuming that the events $p \mid n$ are independent for different primes, we want to calculate ($p$ ranging over primes) $\prod_{n^\alpha \leq p \leq n} (1-1/p) = \exp(\sum_{n^\alpha \leq p \leq n} \log(1-1/p)) \approx \exp(\int_{n^\alpha}^n (dx/\log x) \log(1-1/x))$. Keeping only the first (!) term of the Taylor expansion for $\log(1-1/x)$, $\alpha$ is the result, as long as I haven't made an elementary calculus mistake (which I wouldn't discount!). Even if one accepts the integral approximation, the Taylor approximation may well be losing a $\log \alpha$ factor or something. $\endgroup$ – Tim Campion Jun 17 at 2:11
  • 1
    $\begingroup$ What? No, there is no sense whatsoever in which this is a proof of anything. The independence assumption doesn't even literally make sense, since there's not really such a thing as "the probability that $n$ is prime". $\endgroup$ – Tim Campion Jun 17 at 2:44
  • 6
    $\begingroup$ @TimCampion: That guess is very much off base. The chance that a number $n$ has all prime factors below $n^{1/u}$ is given by the Dickman-de Bruijn function $\rho(u)$, which for large $u$ is about $u^{-u(1+o(1))}$. Thus this is very different from $1/u$ which the naive heuristic would suggest. The same story holds for the distribution of lengths of cycles in a random permutation. Google "smooth numbers". $\endgroup$ – Lucia Jun 17 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.