I've been going through the Erdos proof that the sum of the reciprocals of primes is divergent. I'm having trouble understanding why there are 2^k possible ways to write the square free part.

Printable View

- Nov 20th 2010, 03:32 PMgrandunificationErdos proof Sum of Reciprocals of Primes
I've been going through the Erdos proof that the sum of the reciprocals of primes is divergent. I'm having trouble understanding why there are 2^k possible ways to write the square free part.

- Nov 20th 2010, 04:33 PMBruno J.
Well, the set of squarefree natural numbers having all of their prime divisors in the set $\displaystyle \{p_1, \dots, p_k\}$ is in bijective correspondence with the collection of subsets of $\displaystyle \{p_1, \dots, p_k\}$; and this collection has $\displaystyle 2^k$ elements.

- Nov 21st 2010, 10:15 AMgrandunification
Yes, but I don't see why we should include the empty set in counting. So I think it should be 2^k-1. Is it because in n =rm^2 we need to also throw in the possibility that no prime occurs in the factorization of r because r = 1? Also, I would like to see a proof that n can always be written as rm^2. That's not clear to me.

- Nov 21st 2010, 02:29 PMBruno J.
The empty set corresponds to the empty product, which is equal to $\displaystyle 1$.

As for representation of integers as the product of a squarefree integer and a square : Suppose $\displaystyle n=p_1^{a_1}\dots p_k^{a_k}$ is the canonical representation of $\displaystyle n$ as a product of prime-powers. Using the division algorithm, write $\displaystyle a_j = 2q_j+r_j$, $\displaystyle 0\leq r_j <2$, for $\displaystyle j=1,\dots,k$. Then $\displaystyle n=rm^2$, where $\displaystyle r=p_1^{r_1}\dots p_k^{r_k}$ is squarefree and $\displaystyle m=p_1^{q_1}\dots p_k^{q_k}$. I'll let you show that this representation is unique.

If you know a bit about algebra, we can state this situation in more abstract terms. Consider $\displaystyle (\mathbb{N}, \times)$ (excluding $\displaystyle 0$) as a commutative monoid. The set of $\displaystyle u^{th}$ powers $\displaystyle S_u=\{j^u : j \in \mathbb{N}\}$ is a sub-monoid, and the quotient monoid $\displaystyle \mathbb{N}/S_u$ is isomorphic to to $\displaystyle (\mathbb{Z}/u\mathbb{Z})^\mathbb{N}$ (this is actually a group, since every element in this monoid has finite order at most $\displaystyle u$). In the case $\displaystyle u=2$, which is your case, the monoid $\displaystyle \mathbb{N}/S_2$ can in fact be considered as a countably infinite vector space over the field with two elements. - Nov 27th 2010, 11:07 AMgrandunification
Thanks! That clears up all of my problems. Now, I'm studying another proof of Erdos. This time, the proof of Bertrand's postulate. I'm following wikipedia's outline of the argument. I've made it quite far without getting confused. However, I don't understand the part that says " When p > sqrt(2n), the number (2n, n) has at most one factor of p. I would like to see a proof of that. Second, I don't see how that plays into the following argument using Lemma 2.

- Nov 27th 2010, 01:36 PMgrandunification
I just figured out the answers to my own questions. Nevermind.