2
$\begingroup$

I face an exercise : Find asymptotic formular for the $n^{th}$ square-free number with the error $O(n^{1/2}).$

I don't quite understand the question. What is the $n^{th}$ square-free number ? I guess it is primorial ? Like $2$ is the first, $2 \times 3$ second, $2 \times 3 \times 5$ third , ... (although I do not sure if it includes the number like $2 \times 5$ since $3$ is missing, and if it includes, what should be the third square-free number ? $2 \times 3 \times 5$ or $2 \times 5$.)

Let assume that I want to find an asymptotic formula for $p_1...p_k$ where $p_k$ is the $k^{th}$ prime. So I need to find $g$ such that $$\lim_{x \rightarrow \infty} \frac{\prod_{p \leq x} p}{g(x)} = 1.$$

Basically, asymptotic $\sim$ can be related to little $o$, but this question mention something about error term $O(n^{1/2})$. How can asymptotic relate to big $O$ ?

That makes me confused.

For the method, I see that the primorial can be related to $e^{\theta(x)}$, where $\theta$ is the Chebyshev function. But I do not know how to do $\sim$ with big $O(n^{1/2}).$

$\endgroup$
  • 1
    $\begingroup$ The $n$-th primorial is around $e^n$ by the PNT. The $n$-th square-free number, on the other hand, is around $\frac{\pi^2}{6}n$. The difference between such magnitudes is huge! $\endgroup$ – Jack D'Aurizio Oct 4 '16 at 19:14
  • 1
    $\begingroup$ Maybe first solve the inverse problem: How many numbers $\le N$ are square-free? From originally $N$, you need to subtract about $\frac N4$ numbers divisible by $2^2$, as ell as about $\frac N9$ numbers divisible by $3^2$ - but then you subtracted those divisible by $6^2$ twice, so add back $\frac N{36}$. And so on. You should end up with abou $N(1-\frac 14)(1-\frac 19)(1-\frac 1{25})\cdots(1-\frac 1{p^2})$ with $p\approx \sqrt N$. $\endgroup$ – Hagen von Eitzen Oct 4 '16 at 20:04
6
$\begingroup$

By definition of the Möbius function we have that $n$ is squarefree iff $\mu^2(n)=1$. Thefore, the function $\eta(x)=\sum_{n\leq x}\mu(n)^2$ counts the number of squarefree integers less or equal to $x$. Now recall the following elementary property of $\mu^2$:

$$\mu^2(n)=\sum_{d^2|n}\mu(d),$$

where the sum is extended over all the divisors $d$ of $n$ such that $d^2|n$. Thus,

$$\eta(x)=\sum_{n\leq x}\mu^2(n)=\sum_{n\leq x}\sum_{d^2|n}\mu(d).$$

Write $n=d^2q$. Then $n\leq x$ iff $d^2\leq x$ (i.e., $d\leq\sqrt x$) and $q\leq x/d^2$, so

$$\sum_{n\leq x}\sum_{d^2|n}\mu(d)=\sum_{d\leq\sqrt x}\sum_{q\leq x/d^2}\mu(d)=\sum_{d\leq\sqrt x}\mu(d)\left(\frac x{d^2}+O(1)\right) =x\sum_{d\geq1}\frac{\mu(d)}{d^2}-x\sum_{d\geq\sqrt x}\frac{\mu(d)}{d^2}+O(\sqrt x).$$

But

$$\sum_{d\geq\sqrt{x}}\frac{\mu(d)}{d^2}=O\left(\sum_{d\geq\sqrt x}\frac1{d^2}\right)=O\left(\frac1{\sqrt{x}}\right)$$

so

$$x\sum_{d\geq1}\frac{\mu(d)}{d^2}-x\sum_{d\geq\sqrt x}\frac{\mu(d)}{d^2}+O(\sqrt x) =x\sum_{d\geq1}\frac{\mu(d)}{d^2}+O(\sqrt{x}).$$

Finally, since $\sum_{d\geq1}\frac{\mu(d)}{d^2}=1/\zeta(2)$, we conclude that

$$\eta(x)=\frac{x}{\zeta(2)}+O(\sqrt x)=\frac{6x}{\pi^2}+O(\sqrt x).\tag{$*$}\label{eq:1}$$

EDIT: from the above we have that $\eta(x)\sim \frac{x}{\zeta(2)}$, because

$$\eta(x)=\frac{x}{\zeta(2)}+O(\sqrt x)=\frac{6x}{\pi^2}+o(x)=\frac{6x}{\pi^2}(1+o(1))$$

since $\sqrt{x}=o(x)$ (i.e., $\lim_{x\to\infty}\sqrt{x}/x=0$.) Nevertheless, we have proved something better. Let us write \eqref{eq:1} in the following equivalent form:

$$\frac{\eta(x)}{x/\zeta(2)}=1+O\left(\frac1{\sqrt{x}}\right).$$

We see that the function $\frac{\eta(x)}{x/\zeta(2)}$ approaches to $1$ at least as fast as $\frac1{\sqrt{x}}$ approaches to zero. This provides us more information than simply saying that $\frac{\eta(x)}{x/\zeta(2)}$ converges to $1$. For example, consider the question "What is the value of $\lim_{x\to\infty}\sqrt[3]{x}(\frac{\eta(x)}{x/\zeta(2)}-1)$?" You can answer it if you know that $\frac{\eta(x)}{x/\zeta(2)}-1=O(1/\sqrt{x})$.

$\endgroup$
  • $\begingroup$ Okay, then $$\eta(n) \sim \frac{6x}{pi^2} ?$$ I do not unders tand when I want to solve "find asymptotic formular" it refers to $\sim$ or can be in the form $$f(x) + O(g(x))$$ for some functions $f, g.$ $\endgroup$ – Both Htob Oct 4 '16 at 21:58
  • $\begingroup$ @BothHtob come on, with $A$ the set of squarefree numbers, $\eta(x) = \displaystyle\sum_{n < x, n \in A} 1 \sim x/\zeta(2)$ so you get that $\eta(x) = k \implies x \sim k \zeta(2)$ and this is the asymptotics you want for the $k$th squarefree number $\endgroup$ – reuns Oct 5 '16 at 2:11
  • $\begingroup$ @user1952009 Sorry, but I really do not get what are you doing. From the result above, how do you obtain $$\eta(x) \sim \frac{x}{\zeta(2)} ?$$ I try to understand why $$\lim_{x \rightarrow \infty} \eta(x)/(x/\zeta(2)) = 1 ?$$ That $O(x^{1/2})$ does not goes to $1$ as $x \rightarrow \infty$. I do not understand what is going on. Please be patient, I am very new to this subject. These estimate stuff $O, o, \sim$ are new to me too. $\endgroup$ – Both Htob Oct 5 '16 at 2:40
  • $\begingroup$ @BothHtob $\eta(x)$ is the number of square free numbers $< x$. Iqcd showed in quite an elementary way that $\eta(x) = \frac{x}{\zeta(2)} + \mathcal{O}(\sqrt{x})$ that is there is a $C$ such that $|\eta(x)-\frac{x}{\zeta(2)}| < C \sqrt{x}$ implying $\frac{\eta(x)}{x/\zeta(2)} \to 1$ i.e. $\eta(x) \sim \frac{x}{\zeta(2)}$. So you should work on the asymptotic comparison $\sim,o,\mathcal{O}$ $\endgroup$ – reuns Oct 5 '16 at 2:50
  • $\begingroup$ @BothHtob to be clear $f(x) \sim g(x)$ is the same as $f(x) = g(x) + o(g(x))$ and $f(x) = a x + \mathcal{O}(\sqrt{x})$ is much stronger than $f(x) = a x+o(x)$ itself the same as $f(x) \sim a x$ $\endgroup$ – reuns Oct 5 '16 at 2:55
3
$\begingroup$

Hint:

$\mu(n)^2$, where $\mu(n)$ is the Moebius function, is the characteristic function of square-free numbers.
By convolution of Dirichlet series and summation by parts, it is not difficult to show that $$ \sum_{n\leq x}\mu(n)^2 \approx \frac{x}{\zeta(2)} = \frac{6x}{\pi^2} \tag{1}$$ i.e. the square-free integers form a subset of the natural numbers with positive density. By $(1)$, it follows that the $n$-th square-free natural number is close to $\color{red}{\frac{\pi^2 n}{6}}$. How close depends on a explicit error term for $(1)$.

$\endgroup$
  • $\begingroup$ Can you explain when I encouter "asymototic formula" it means to $\sim$ ? The book does not give a definition about it. So I dont know what is it actually. Wikipedia provides something (en.wikipedia.org/wiki/Asymptotic_formula) but normally big $O$ has nothing to do with $\sim.$ This confusing make me not sure where should I start. Is this kind of question just want to find estimate for a sum with error terms, regradless of its form $\sim$, big $o$, littlt $o$. Just choose one is fine ? $\endgroup$ – Both Htob Oct 4 '16 at 22:08
  • $\begingroup$ @BothHtob: I was a bit vague on purpose here. $a\approx b$ above just means that $a$ is close to $b$; I leave to you the task to replace $(1)$ by something with some rigor like $\sum_{n\leq x}\mu(n)^2=\frac{x}{\zeta(2)}+O(\sqrt{x})$, then prove your claim. Which approximations are fine for our purposes? is another question left open for you on purpose. $\endgroup$ – Jack D'Aurizio Oct 5 '16 at 16:15
0
$\begingroup$

A square-free number is one with no square divisors (other than 1).

They're not the same as primorial numbers: 3 is square-free but not primorial. Here's a list of the first square-free numbers, at the On-Line Encyclopedia of Integer Sequences.

Does that get you unstuck?

$\endgroup$
  • $\begingroup$ Then how should I represent it ? Just $$n|\mu(n)| ?$$ Well, is there a formular for it ? $\endgroup$ – Both Htob Oct 4 '16 at 12:08
  • $\begingroup$ But that formula does not help anything in finding asymptotic, or I overlook some important information ? $\endgroup$ – Both Htob Oct 4 '16 at 12:33

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.