# Convergence Craziness

• May 19th 2009, 01:15 PM
Media_Man
Convergence Craziness
Take some infinite subset of natural numbers $\displaystyle A \subset \mathbb{N}$ . Define $\displaystyle \sigma_A= \sum_{n\in A} \frac{1}{n}$ . For some sets A, $\displaystyle \sigma$ diverges, like the primes $\displaystyle P=\{2,3,5,7,11,13...\}$ and for other sets, $\displaystyle \sigma$ converges, like the squares $\displaystyle S=\{1,4,9,16,25,36,49,64...\}$ . One could say the more "dense" a set A is, the more likely it is to diverge. One could also compare the "density" of two subsets of $\displaystyle \mathbb{N}$ by looking at the asymptotes of their counting functions, i.e. the primes are "denser" than the square numbers because there are more primes under an arbitrarily large x than there are square numbers. But is there such a thing as a "least dense" divergent series?

Question: Let A be a sequence of natural numbers, such that $\displaystyle \sigma_A$ diverges. Does there exist such an A where no matter how we partition it into two mutually exclusive subsets ($\displaystyle A_1 \cup A_2 =A$ but $\displaystyle A_1 \cap A_2$ =null) either $\displaystyle \sigma_{A_1}$ or $\displaystyle \sigma_{A_2}$ must converge? Find such a set A or prove none exists. Conjecture: None exists. For any divergent series A, you will be able to find two mutually exclusive, divergent subsets $\displaystyle A_1$ and $\displaystyle A_2$ .
• May 19th 2009, 02:10 PM
TheAbstractionist
Quote:

Originally Posted by Media_Man
Take some infinite subset of natural numbers $\displaystyle A \subset \mathbb{N}$ . Define $\displaystyle \sigma_A= \sum_{n\in A} \frac{1}{n}$ . For some sets A, $\displaystyle \sigma$ diverges, like the primes $\displaystyle P=\{2,3,5,7,11,13...\}$ and for other sets, $\displaystyle \sigma$ converges, like the squares $\displaystyle S=\{1,4,9,16,25,36,49,64...\}$ . One could say the more "dense" a set A is, the more likely it is to diverge. One could also compare the "density" of two subsets of $\displaystyle \mathbb{N}$ by looking at the asymptotes of their counting functions, i.e. the primes are "denser" than the square numbers because there are more primes under an arbitrarily large x than there are square numbers. But is there such a thing as a "least dense" divergent series?

Question: Let A be a sequence of natural numbers, such that $\displaystyle \sigma_A$ diverges. Does there exist such an A where no matter how we partition it into two mutually exclusive subsets ($\displaystyle A_1 \cup A_2 =A$ but $\displaystyle A_1 \cap A_2$ =null) either $\displaystyle \sigma_{A_1}$ or $\displaystyle \sigma_{A_2}$ must converge? Find such a set A or prove none exists. Conjecture: None exists. For any divergent series A, you will be able to find two mutually exclusive, divergent subsets $\displaystyle A_1$ and $\displaystyle A_2$ .

Hi Media_Man.

This is my idea. Pick any number $\displaystyle n_1$ from $\displaystyle A$ and let $\displaystyle k$ be the largest integer such that $\displaystyle 2^k\le n_1$. Thus $\displaystyle n_1<2^{k+1}$ but since $\displaystyle A$ is infinite we can pick $\displaystyle n_2\in A\setminus\{n_1\}$ such that $\displaystyle 2^{k+1}\le n_2.$ Then pick $\displaystyle n_3\in A\setminus\{n_1,n_2\}$ such that $\displaystyle 2^{k+2}\le n_3,$ then $\displaystyle n_4\in A\setminus\{n_1,n_2,n_3\}$ such that $\displaystyle 2^{k+3}\le n_4,$ and so on ad infinitum.

Thus $\displaystyle \frac1{n_1}+\frac1{n_2}+\frac1{n_3}+\cdots\le\frac 1{2^k}+\frac1{2^{k+1}}+\frac1{2^{k+2}}+\cdots$ and since the RHS converges, so must the LHS.
• May 19th 2009, 07:45 PM
Media_Man
Hmm...
I think I understand what you are saying. You are suggesting that given an arbitrary set A, define $\displaystyle A_1=\{n_1,n_2,n_3,...\}$ as per your algorithm and $\displaystyle A_1$ is guaranteed to converge. This is true. But what I am asking is to find a divergent set A that cannot be partitioned into two divergent subsets.

Lemma: If $\displaystyle \sigma_A$ diverges, and $\displaystyle A_1, A_2$ partition A, then we have one of three cases:
(i) $\displaystyle \sigma_{A_1}$ diverges but $\displaystyle \sigma_{A_2}$ converges
(ii) $\displaystyle \sigma_{A_1}$ converges but $\displaystyle \sigma_{A_2}$ diverges
(iii) Both diverge.

What I am looking for is a set A for which no subsets $\displaystyle A_1,A_2$ exist satisfying (iii).

Examples:

Let A be the naturals $\displaystyle \{1,2,3,4,5,6,7,...\}$, which diverge. Letting $\displaystyle A_1$ be evens, and $\displaystyle A_2$ be odds, it is easily shown that case (iii) follows.

More clever...

Let P denote the primes $\displaystyle \{2,3,5,7,11,13,...\}$ . Euler and Goldbach independently showed that $\displaystyle \sigma_P$ diverges. Now let $\displaystyle A_1$ be primes of the form $\displaystyle 4k+1$ and $\displaystyle A_2$ be primes of the form $\displaystyle 4k+3$ . Since $\displaystyle A_1$ and $\displaystyle A_2$ are equinumerous (Modular Prime Counting Function -- from Wolfram MathWorld), and they cannot both be convergent (as $\displaystyle \sigma_A=\sigma_{A_1}+\sigma_{A_2}$), they must both be divergent.

Therefore, can you think of a divergent set that cannot be split into two smaller divergent sets like this? *It seems to me that none would exist because just as in the last example, any divergent set can be partitioned perfectly in half, but can this be shown rigorously? If $\displaystyle \sum_{n=1}^\infty \frac{1}{a_n}$ diverges, does that imply that $\displaystyle \sum_{n=1}^\infty \frac{1}{a_{2n}}$ also diverges, for $\displaystyle 1\leq a_1 < a_2 <a_3 < ...$ ???
• May 20th 2009, 05:08 AM
SimonM
Quote:

Originally Posted by Media_Man
If $\displaystyle \sum_{n=1}^\infty \frac{1}{a_n}$ diverges, does that imply that $\displaystyle \sum_{n=1}^\infty \frac{1}{a_{2n}}$ also diverges, for $\displaystyle 1\leq a_1 < a_2 <a_3 < ...$ ???

Yes; rewording the question to a strictly (eventually) decreasing sequence of positive numbers.

$\displaystyle \sum_{n=1}^{\infty} a_{2n-1} \geq \sum_{n=1}^{\infty} a_{2n} \geq \sum_{n=1}^{\infty} a_{2n+1}$

Suppose $\displaystyle \sum_{n=1}^\infty a_{2n}$ converges, then $\displaystyle \sum_{n=1}^\infty a_{2n+1}$ converges, and hence

$\displaystyle \sum_{n=1}^\infty a_{2n-1}$ converges (adding an constant)

Therefore $\displaystyle \sum_{n=1}^\infty a_{2n-1} + \sum_{n=1}^\infty a_{2n} = \sum_{n=1}^{\infty} a_n$ converges. Contradiction
• May 20th 2009, 10:16 AM
Media_Man
Implications...
Okay, this would imply that given any sequence of natural numbers $\displaystyle 1 \leq a_1 < a_2 < a_3 < ...$ for which $\displaystyle \sigma_A$ diverges, it is possible to construct a subset of A, called B, for which the partial sums as L gets large, $\displaystyle \sum_{n=1}^L \frac{1}{b_n} \approx \frac{1}{2}\sum_{n=1}^L \frac{1}{a_n}$ . Likewise we can find a divergent subset of B that grows approximately $\displaystyle \frac{1}{4}$ as quickly as A and so on. Iterating, given any arbitrarily large integer k, there exists a subset of the natural numbers, $\displaystyle A_k$ whose asymptotic growth is approximately $\displaystyle \sum_{n=1}^L \frac{1}{a_n} \approx \frac{1}{2^k}\sum_{n=1}^L \frac{1}{n}$

Therefore there is no such thing as a "least dense" divergent series. A sequence of natural numbers can always be found for which $\displaystyle \sigma=\sum_{n=1}^\infty \frac{1}{a_n}$ diverges arbitrarily slowly.

The reason I am interested is that it seems to me that the power set of $\displaystyle \mathbb{N}$ is well-ordered. Though uncountable, you can always take two elements of $\displaystyle \mathbb{P}(\mathbb{N})$, say A and B, and say that the partial sums for $\displaystyle \sigma$ when L is greater than some arbitrarily large number are:
(i) $\displaystyle \sigma_A > \sigma_B$ (A is less dense)
(ii) $\displaystyle \sigma_A < \sigma_B$ (B is less dense)
(iii) $\displaystyle \sigma_A \approx \sigma_B$ (A and B are equinumerous)

The same can be said for converging elements of $\displaystyle \mathbb{P}(\mathbb{N})$ . Now here is the big question: Picking an element at random, what is the probability that it converges? What portion of sequences of natural numbers are "large sets" ($\displaystyle \sigma$ diverges) vs. "small sets" ($\displaystyle \sigma$ converges)? And can we get any kind of handle of a line that can be drawn between them?
• May 21st 2009, 05:27 AM
Laurent
Quote:

Originally Posted by Media_Man
Now here is the big question: Picking an element at random, what is the probability that it converges? What portion of sequences of natural numbers are "large sets" ($\displaystyle \sigma$ diverges) vs. "small sets" ($\displaystyle \sigma$ converges)? And can we get any kind of handle of a line that can be drawn between them?

Here's my answer about the last part.

There are natural probability measures on $\displaystyle \mathcal{P}(\mathbb{N})=\{0,1\}^{\mathbb{N}}$ (with product $\displaystyle \sigma$-algebra), namely the distributions that consist in picking each number independently with some probability $\displaystyle p\in(0,1)$. This gives random infinite subsets of $\displaystyle \mathbb{N}$ (that have asymptotic density $\displaystyle p$). Moreover, every natural number plays the same role (the measure is shift-invariant), so that these measures appear to be analogs of a "uniform measure". Choosing $\displaystyle p=1/2$ would additionally give a symmetry between the random subset and its complement (they would be distributed alike), but I don't need this assumption in the following.

In other words, let $\displaystyle p\in(0,1)$ and let $\displaystyle (X_n)_{n\geq 0}$ be independent random variables distributed according to $\displaystyle P(X_n=1)=p$ and $\displaystyle P(X_n=0)=1-p$. The random subset would be $\displaystyle A=\{n\in\mathbb{N}\ \mid\ X_n=1\}$. And the question is:

What is the probability that the sum $\displaystyle S=\sum_{n=1}^\infty \frac{X_n}{n}$ is finite?

The answer is..., wait for it,... zero. Disappointingly. But not surprisingly if you know Kolmogorov's 0-1 law, which tells that the answer has to be either 0 or 1.

I've come up with various proofs but no fully elementary one. One possibility is to use Paley-Zygmund inequality (this is an easy one, don't get scared by the name!) for partial sums to get that, taking a limit, $\displaystyle P(S\geq\frac{1}{2}\mathbb{E}(S))>0$ which, given Kolmogorov's 0-1 law, leads to the conclusion since $\displaystyle \mathbb{E}[S]=\sum_{n=1}^\infty \frac{p}{n}=\infty$.

Another possibility (without K's 0-1 law) is to write $\displaystyle Y_k=\sum_{n=k^2+1}^{(k+1)^2}X_n$. We notice that almost-surely $\displaystyle Y_k\sim_{k\to\infty} (2k+1)p$ because of the law of large numbers (Not quite: in fact there is a subtelty, but nevermind, it can be made to work). Then

$\displaystyle S_{k^2}=\sum_{i=0}^{k-1}\sum_{n=i^2+1}^{(i+1)^2}\frac{X_n}{n}$ $\displaystyle \geq\sum_{i=0}^{k-1}\sum_{n=i^2+1}^{(i+1)^2}\frac{X_n}{(i+1)^2}=\sum _{i=0}^{k-1}\frac{Y_i}{(i+1)^2}$,

and almost-surely $\displaystyle \frac{Y_i}{(i+1)^2}\sim_{i\to\infty} \frac{(2i+1)p}{(i+1)^2}\sim_{i\to\infty} \frac{2p}{i}$, so that the right-hand side sum diverges almost-surely as $\displaystyle k\to\infty$.

As a conclusion: for almost-every subset $\displaystyle A$ of $\displaystyle \mathbb{N}$ (according to the previous measures), $\displaystyle \sigma_A=\infty$. The second proof (almost) only uses the fact that a random set has a positive asymptotic density.

--
About this "frontier" thing, here is something you might like (but maybe you know it already): for any $\displaystyle k\geq 1$, the series

$\displaystyle \sum_n\frac{1}{n\log n \log\log n\cdots \log\log\cdots\log n}$

(with successively $\displaystyle 1, 2, 3,\ldots, k$ nested logs) diverges, while for any $\displaystyle \varepsilon>0$, for any $\displaystyle k\geq 1$, the series

$\displaystyle \sum_n\frac{1}{n\log n\log\log n\cdots (\log\log\cdots\log n)^{1+\varepsilon}}$

(only the last function is raised to the power $\displaystyle 1+\varepsilon$) converges. For a given $\displaystyle \varepsilon>0$, the higher $\displaystyle k$ is, the slower the converging series decays. This gives an intuition (not a theorem) of how fast a decreasing sequence should at least decay for making a convergent series.
• May 21st 2009, 06:20 AM
Media_Man
Cool
Awesome, Laurent.

I had a feeling such. I pictured flipping a weighted coin that came up heads if a number was in the set, and tails otherwise. Regardless of how unfair the coin was, the set would still diverge. If you got heads 1% of the time, you'd get a set containing approximately one of every 100 natural numbers, for example. This would be equinumerous to the set $\displaystyle k\mathbb{N}$, which diverges, as $\displaystyle \sum_{n=1}^\infty \frac{1}{kn}=k\sum_{n=1}^\infty \frac{1}{n}=\infty$ . I was just having trouble showing this rigorously. This is bordering topology more than my better understood subject of number theory.

Consider this: For some subset of the naturals $\displaystyle A \in \mathcal{P}(\mathbb{N})$ , define $\displaystyle \alpha(A)=\sum_{a\in A} \frac{1}{2^a}$ . I believe this is a well-defined homomorphism from $\displaystyle \mathcal{P}(\mathbb{N}) \rightarrow [0,1]$ . Defining $\displaystyle C \subset \mathcal{P}(\mathbb{N})$ as the set of converging elements of $\displaystyle \mathcal{P}(\mathbb{N})$ (with the restriction that elements of C be infinite) , we can actually plot C on [0,1] and express the set visually. I believe C is uncountably infinite (proof?) but if the probability that a random element of $\displaystyle \mathcal{P}(\mathbb{N})$ is in C is zero, then it is a totally disconnected set of infinite points with no "length" . This results in some sort of fractal structure with Hausdorff dimension $\displaystyle \in (0,1)$ , doesn't it?
• May 21st 2009, 06:49 AM
Laurent
Quote:

Originally Posted by Media_Man
Consider this: For some subset of the naturals $\displaystyle A \in \mathcal{P}(\mathbb{N})$ , define $\displaystyle \alpha(A)=\sum_{a\in A} \frac{1}{2^a}$ . I believe this is a well-defined homomorphism from $\displaystyle \mathcal{P}(\mathbb{N}) \rightarrow [0,1]$ .

This also amounts to seeing the series of flipped coins as the expansion of a real number is base 2 (1 for heads, 0 for tails). A little care should be taken on "unproper" expansions like 0.0111111... which equals 0.10000..., but this is only countably many points.

Quote:

Defining $\displaystyle C \subset \mathcal{P}(\mathbb{N})$ as the set of converging elements of $\displaystyle \mathcal{P}(\mathbb{N})$ (with the restriction that elements of C be infinite) , we can actually plot C on [0,1] and express the set visually. I believe C is uncountably infinite (proof?)
One simple reason why: take an element $\displaystyle A$ of $\displaystyle C$, then every subset of $\displaystyle A$ is in $\displaystyle C$ as well! And the set of subsets of $\displaystyle A$ is in bijection with $\displaystyle \mathcal{P}(\mathbb{N})$.

Quote:

but if the probability that a random element of $\displaystyle \mathcal{P}(\mathbb{N})$ is in C is zero, then it is a totally disconnected set of infinite points with no "length" . This results in some sort of fractal structure with Hausdorff dimension $\displaystyle \in (0,1)$ , doesn't it?
This set should indeed have a complex topological structure. If a number $\displaystyle x=0.a_1a_2\cdots$ is in $\displaystyle C$, then all translates $\displaystyle 0.\ast\ast\ast a_1a_2\cdots$ are in $\displaystyle C$. In particular, there are two important subsets of $\displaystyle C$ that can be seen as copies of $\displaystyle C$: the one made of sequences not containing 1 (i.e. of the form $\displaystyle 0.0a_2a_3\cdots$) and the one made of sequences containing 1 (i.e. of the form $\displaystyle 0.1a_2a_3\cdots$). Heuristically, these copies have half the (euclidian) size of $\displaystyle C$ and there are two of them. I think (not even 10% sure) this should imply that the Hausdorff dimension is either 0 or 1, again... I can't remember enough of fractal theory to conclude...
• May 21st 2009, 07:13 AM
Media_Man
Quote:

This also amounts to seeing the series of flipped coins as the expansion of a real number is base 2 (1 for heads, 0 for tails). A little care should be taken on "unproper" expansions like 0.0111111... which equals 0.10000..., but this is only countably many points.
Yes, I neglected to mention that until later in my post. The set $\displaystyle \{1,2,3\}$ is most certainly not equal to $\displaystyle \{1,2,4,5,6,7,8,...\}$, so this homomorphism really only maps $\displaystyle \mathcal{P}(\mathbb{N}) - F \rightarrow (0,1]$ , where F represents finite elements of $\displaystyle \mathcal{P}(\mathbb{N})$ , or terminating decimals. And yes, as F is countable, it does not pose much of a problem, but I do not know enough about topology to correct this flaw.

Quote:

I think (not even 10% sure) this should imply that the Hausdorff dimension is either 0 or 1, again...
I'll have to look into it. It would be impossible to actually "see" this fractal as prescribed here because $\displaystyle \alpha$ converges so quickly, but I believe any function of the form $\displaystyle \alpha_\epsilon(A)=\sum_{a\in A} \frac{1}{(1+\epsilon)^a}$ would work equally well, slowing the convergence enough to be able to distinguish two points who only differ at, say, the 100th or 1000th digit. Also, I know that if a set is countable, it has a Hausdorff dimension of zero - is the converse true?
• May 21st 2009, 08:12 AM
Laurent
It would be impossible to actually "see" this fractal as prescribed here because $\displaystyle \alpha$ converges so quickly, but I believe any function of the form $\displaystyle \alpha_\epsilon(A)=\sum_{a\in A} \frac{1}{(1+\epsilon)^a}$ would work equally well, slowing the convergence enough to be able to distinguish two points who only differ at, say, the 100th or 1000th digit.
You won't see anything in any way: the fact that $\displaystyle x$ belongs to $\displaystyle C$ is an asymptotic property, you can't tell it given ANY finite number of digits. This is exactly like you would want to picture the set of rational numbers...