2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I must be a bit dense, but how come the expression has no $n$? $\endgroup$
    – kodlu
    Jul 11, 2016 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$ Jul 11, 2016 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, 2016 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$ Jul 12, 2016 at 16:00

2 Answers 2

3
$\begingroup$

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}$.

$\endgroup$
13
  • $\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$ Jul 11, 2016 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$ Jul 11, 2016 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$ Jul 11, 2016 at 16:31
  • $\begingroup$ PS: Or are you not making a technical claim at all, just describing an intuitive model? $\endgroup$ Jul 11, 2016 at 16:34
  • $\begingroup$ Probability space is the (finite) set of residues modulo $P(\sqrt{x})$, all residues have equal probability. $\endgroup$ Jul 11, 2016 at 18:12
6
$\begingroup$

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. $$

$\endgroup$

Your Answer

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

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