Timeline for Behavior of biggest prime divisor of $n$ as $n$ grows large
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2021 at 20:05 | comment | added | Dominic van der Zypen | Thanks Ofir for taking the time to write this up! (It would have deserved an additional answer.) | |
| Aug 14, 2021 at 19:07 | comment | added | Ofir Gorodetsky | (cont.) $\Psi(x,y) \ll (x/\log x) (1 + \sum_{p \le y} \log p /p) \ll x (\log y / \log x)$ (where the estimate $\sum_{p \le y} \log p/ p \ll \log y$ is due to Mertens). Throughout $p$ is a prime. This implies that the probability that $\alpha \le c$ decays like $O(c)$. The truth is closer to $(1/c)^{-1/c}$. | |
| Aug 14, 2021 at 19:00 | comment | added | Ofir Gorodetsky | (cont.) Just to give an alternative source with a slightly different argument: Koukoulopoulos' "The Distribution of Prime Numbers", Theorem 14.5. For the weaker result we can argue as follows: We start with an elementary identity of Hildebrand, $\Psi(x,y) \log x = \int_{1}^{x} \Psi(t,y) \frac{dt}{t} + \sum_{p^m \le x, \, p \le y} \Psi(x/p^m, y) \log p$ where $\Psi(x,y)$ counts integers up to $x$ whose prime factors are $\le y$. The trivial bound $\Psi(t,y) \le t $ applied to the RHS leads to (continued in next comment) | |
| Aug 14, 2021 at 18:47 | comment | added | Ofir Gorodetsky | @DominicvanderZypen This result dates back to Karl Dickman's 1930 paper (in fact, the history is more complicated, and Pieter Moree wrote a great survey on it titled "Integers without large prime factors: from Ramanujan to de Bruijn"). A modern treatment can be found in Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" (in the 1st edition this is in Chapter III.5, p. 367, Theorem 6). However, results such as "the probability that $\alpha<c$ tends to 0 as $c \to 0$" are much easier, see e.g. p. 359, Theorem 1 in the same book. (continued in next comment) | |
| Aug 14, 2021 at 16:56 | comment | added | Dominic van der Zypen | That's an interesing angle - thanks @OfirGorodetsky! Do you have a reference on this? | |
| Aug 14, 2021 at 16:56 | vote | accept | Dominic van der Zypen | ||
| Aug 14, 2021 at 13:16 | comment | added | Ofir Gorodetsky | @DominicvanderZypen You might be interested in the following result. Writing $L(n) = n^{\alpha(n)}$, the random variable $\alpha \in [0,1]$ has a continuous limiting distribution if $n$ is randomly sampled from $[1,x]\cap \mathbb{Z}$ and $x \to \infty$. | |
| Aug 14, 2021 at 9:49 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
MathJax: \mid for divisibility
|
| Aug 14, 2021 at 9:41 | answer | added | Carl-Fredrik Nyberg Brodda | timeline score: 3 | |
| Aug 13, 2021 at 20:06 | comment | added | Dominic van der Zypen | Thanks for your comments. Please post one as an answer so we can close this thread. @Carl-FredrikNybergBrodda - the context was a silly one: I saw a car with a license plate "AB 639" and noticed that $639 = 3 \cdot 3 \cdot 71$ where 71 is much higher than the square root of 639. So I was wondering how "common" this phenomenon was and tried to put this hand-wavy question into some solid-ish mathematics. | |
| Aug 13, 2021 at 14:13 | comment | added | mathworker21 | suffices to show average is $0$. Can upper bound average by $\frac{1}{n}\sum_{2 \le m \le n} \frac{1}{m}\sum_{p \mid m} p = \frac{1}{n} \sum_p p \sum_{2 \le m \le n \\ p \mid m} \frac{1}{m} = \frac{1}{n}\sum_p p\sum_{1 \le k \le n/p} \frac{1}{pk} \le \frac{1}{n} \sum_{1 \le k \le n} \frac{1}{k} C\frac{n}{\log(n/k)} \le 2C/\log n$. So all we needed really was that primes have $0$ density (which is also necessary for the median/mean to be $0$). | |
| Aug 13, 2021 at 12:33 | comment | added | Carl-Fredrik Nyberg Brodda | What is the context for asking this question? It seems like a very random function. | |
| Aug 13, 2021 at 12:28 | comment | added | Carl-Fredrik Nyberg Brodda | The number of distinct prime divisors of $n$ grows on average as $\log \log n$. This should give you that $\lim_{n \to \infty} M(n) = 0$. | |
| Aug 13, 2021 at 11:32 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |