Let $P(x)$ be the product of all primes less or equal to $x$. The probability of $(n, P(\sqrt{x})) \leq x$ for an arbitrary $n$ is then given exactly by $$ \prod_{p\mid P(\sqrt{x})}{\left(1-\frac{1}{p}\right)} \sum_{ \substack{ {d \mid P(\sqrt{x}) } \\ {d\leq x} } } \prod_{p\mid d}(p-1)^{-1}. $$

Q: Is there a known asymptotic estimate for this expression? (Or does someone know how to prove one?)

ADDED: Since I got one answer suggesting the asymptotic estimate lying close to 1, I'll add a few comments here as to why I anticipate the asymptotic estimate to converge to zero. First of all, the number of divisors of $P(\sqrt{x})$ grows as $2^{\pi(\sqrt{x})}$. The number of these divisors that are smaller than $x$ only grows polynomially (presumably read this on Terence Tao's blog, but might be wrong—anyhow seems consistent with numerical data), so that eventually, this subset of divisors has measure zero compared to the full set. Also, for any fixed divisor $d$, the probability of $(n, P(\sqrt{x})) = d$ is
$$ \prod_{p\mid P(\sqrt{x})}{\left(1-\frac{1}{p}\right)} \prod_{p\mid d}(p-1)^{-1}, $$ which goes to zero as $x$ goes to infinity. It therefore seems reasonable that the probability of $(n, P(\sqrt{x})) \leq x$ should tend to zero, albeit slowly. This result would also seem in accordance with the Erdös-Kac theorem, stating the number of divisors of $n$ has asymptotic mean equal to $\log \log n$. I've added some numerics below that might be suggestive in the direction I've described.

enter image description here

  • $\begingroup$ I must be a bit dense, but how come the expression has no $n$? $\endgroup$ – kodlu Jul 11 '16 at 0:38
  • 2
    $\begingroup$ It's the probability that a random $n$ is coprime to $P(x)$ [that is, the limit as $N \to\infty$ of the probability that a number $n$ chosen uniformly at random from $\{1,2,3,\ldots,N\}$ is coprime to $P(x)$]. $\endgroup$ – Noam D. Elkies Jul 11 '16 at 1:27
  • $\begingroup$ What if $x$ was slowly growing with $N$ say $x(N)=\log N$, or even $x(N)=\log \log N$, what would happen then? I apologise if this is inappropriate for a comment and can post a separate question in that case. $\endgroup$ – kodlu Jul 11 '16 at 3:30
  • $\begingroup$ [correction: $n$ not necessarily coprime to $P(x)$ $-$ or rather, to $P(\sqrt x)$ $-$ but having no common factor larger than $x$. $\endgroup$ – Noam D. Elkies Jul 12 '16 at 16:00

Denote $f_p(n)=\log(p)\cdot {\textbf 1}_{p|n}$. Your event is $\sum_{p^2<x} f_p<\log x$. The random variables $f_p$ are independent, so this is a sort of law of large numbers for not identically distributed, but still independent random variables.Sum of means grows as $\log(x)/2$, thus your probability should be close to 1.

UPDATE. My intuition got wrong, since the sum of our random variables has really huge variance. Namely, the expectation equals $$M:=\sum_{p<\sqrt{x}} \frac{\log p}p\sim \frac{\log(x)}2$$, and the variance equals $$\sigma^2=\sum_{p< \sqrt{x}} \frac{\log^2 p}p-\frac{\log^2p}{p^2}\sim \frac{\log^2x}8.$$ If CLT holds in this situation (I hope so, please check), then the probability of the event $\sum f_p(n)\geqslant \log x\sim M+\sqrt{2}\sigma$ should tend to $$ \frac1{\sqrt{2\pi}}\int_{\sqrt{2}}^\infty e^{-t^2/2}dt={\rm erfc}(1)/2=0.0786\dots, $$ thus your probability tends to $0.921\dots=1-{\rm erfc(1)/2}$.

| cite | improve this answer | |
  • $\begingroup$ The events "$n\le x$ is a multiple of $p$" for various $p$ are perhaps approximately independent for $p\ll x$ wrt to the uniform prob measure on $[1,x]$ (whatever the precise meaning of that might be), but not exactly. $\endgroup$ – Christian Remling Jul 11 '16 at 0:53
  • $\begingroup$ @ChristianRemling If we consider residues modulo $P(\sqrt{x})$, they are independent. It is a usual understanding of such things. $\endgroup$ – Fedor Petrov Jul 11 '16 at 4:18
  • $\begingroup$ Perhaps I'm not understanding the setup properly. But I don't seem to be able to come with a prob space + measure that makes your $f_p$ independent rv's. $\endgroup$ – Christian Remling Jul 11 '16 at 16:31
  • $\begingroup$ PS: Or are you not making a technical claim at all, just describing an intuitive model? $\endgroup$ – Christian Remling Jul 11 '16 at 16:34
  • $\begingroup$ Probability space is the (finite) set of residues modulo $P(\sqrt{x})$, all residues have equal probability. $\endgroup$ – Fedor Petrov Jul 11 '16 at 18:12

We can show at least that your expression tends to a constant strictly greater than $0$. (Well, what we'll actually show is that its lim inf is positive.)

First we claim that $$ \sum_{d\le w} \frac{\mu^2(d)}{\phi(d)} \sim \log w. $$ This follows from standard tools for sums of multiplicative functions; for example, you can apply Proposition A.3(a) of my paper with $g(n) = \mu^2(n) n/\phi(n)$ (but this result certainly isn't due to me; it can be found in Friedlander/Iwaniec's Opera de Cribro, for example).

In particular, $$ \sum_{\substack{d\mid P(\sqrt x) \\ d\le x}} \prod_{p\mid d} \frac1{p-1} \ge \sum_{\substack{d \text{ squarefree} \\ d\le \sqrt x}} \prod_{p\mid d} \frac1{p-1} = \sum_{d\le \sqrt x} \frac{\mu^2(d)}{\phi(d)} \sim \log \sqrt x. $$ Since of course $$ \prod_{p\mid P(\sqrt x)} \bigg( 1-\frac1p \bigg) = \prod_{p\le\sqrt x} \bigg( 1-\frac1p \bigg) \sim \frac1{e^\gamma \log\sqrt x} $$ by Mertens, we conclude that $$ \prod_{p\mid P(\sqrt x)} \bigg( 1-\frac1p \bigg) \sum_{\substack{d\mid P(\sqrt x) \\ d\le x}} \prod_{p\mid d} \frac1{p-1} \gtrsim \frac{\log\sqrt x}{e^\gamma \log\sqrt x} = e^{-\gamma} > 0. $$

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.