Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show by a sieve argument that the number of square free integers not exceeding $x$ is less than $$x\prod_p\left(1-\frac{1}{p^2}\right)+o(x),$$where the product extends over all primes.

I happened to see this exercise this morning, and still fail to prove it. Could you give me a proof?

share|improve this question
    
Do you mean "sum" in "where the product extends"? –  Dimitrije Kostic Dec 8 '11 at 2:42
    
@DimitrijeKostic Sorry, it should be product. –  Kou Dec 8 '11 at 2:51
    
@AndréNicolas Sorry, you are right. –  Kou Dec 8 '11 at 2:52
add comment

1 Answer 1

Rough sketch: Have you seen the Wikipedia section on the distribution of squarefree integers? It essentially gives your solution. All you need to notice is that for large $n$, the "probability" that an integer has $p^2$ as a factor is $\frac{p^2-1}{p^2} = \left( 1 - \frac{1}{p^2}\right)$. Since the probability that $n$ has $p^2$ as a factor is roughly independent of the fact it has $q^2$ where $p$ and $q$ are distinct primes, this implies that

$$ \frac{Q(x)}{x} \approx \prod_p \left( 1 - \frac{1}{p^2} \right). $$

I will leave it to you to make this precise.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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