12
$\begingroup$

Let $x$ be an integer picked uniformly at random from $1 \ldots N$. Write $x = r^2 t$ where $t$ is square-free. How does the expected value of $r$ scale with $N$? Is anything known about the variance of $r$?

$\endgroup$
22
$\begingroup$

The asymptotic frequency of square-free integers is known to be $6/\pi^2$, see [1].

Denote by $P_n$ the uniform distribution on $[1,n]$ and by $E_n$ the corresponding expectation. Then $$E_n(r)=\sum_{k \le \sqrt{n}} k P_n(r=k) \sim \sum_{k \le \sqrt{n}} k \cdot \frac{1}{k^2} \cdot\frac{6}{\pi^2} \sim \frac{3}{\pi^2} \log(n) \,,$$ where $A \sim B$ means that $A/B \to 1$ as $ n \to \infty$. (In particular for $n=10^{10}$ the mean $E_n(r)$ is close to 7.) Also, $$E_n(r^2)=\sum_{k \le \sqrt{n}} k^2 P_n(r=k) \sim \sum_{k \le \sqrt{n}} \frac{6}{\pi^2} \sim \frac{6\sqrt{n}}{\pi^2} \,, $$ so the variance of $r$ is asymptotic to $6\sqrt{n}/\pi^2$ as well.

[1] https://en.wikipedia.org/wiki/Square-free_integer

$\endgroup$
1
  • 3
    $\begingroup$ I have never seen $\log_e 10 \approx \frac{7}{30}\pi^2$ being useful before: both about $2.303$ $\endgroup$ – Henry Dec 23 '20 at 19:02
6
$\begingroup$

Just a little empirical data up to $N=10^{10}$, three superimposed random runs. Growing roughly linearly w.r.t. $\log_{10} N$ within that range.


     

$\endgroup$
2
  • $\begingroup$ What is the slope and how close to $6/\pi^2$ is it? $\endgroup$ – smci Dec 23 '20 at 10:36
  • 2
    $\begingroup$ @smci: Slope is about $0.71$, but I plotted w.r.t. $\log_{10}$. The constant in Yuval's $E_n(r)$ is $3/\pi^2$, and $(3/\pi^2) \log(10) \approx 0.70$; so that matches. And, as Yuval says, for $N=10^{10}$, the expected value of $r$ is about $7$, which accords with my chart, and with $0.70 \times 10 = 7$. $\endgroup$ – Joseph O'Rourke Dec 23 '20 at 14:15

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.