Comment by jstanley | Hacker News Reader

Comment by jstanley | Hacker News Reader

Parent Full thread

> The conjecture by Erdős is the following: if A ⊂ ℕ is such that Σ_{n ∈ A} 1/n diverges, then A contains arbitrarily long arithmetic progressions

This is quite hard to understand for people who don't already know what it means (including me). I started trying to translate it but there were a few parts I didn't understand, starting with:

1.) Is ℕ integers >0 or >=0? Wikipedia says it can be either. Maybe it doesn't matter? Maybe it must be >0 otherwise 1/n makes no sense?

2.) When you ask whether the sum of 1/n for all n in A diverges, how do you know what order to sum them in? Does it diverge regardless of the order? Since A only contains positive integers doesn't sum of 1/n for all n in A always tend towards infinity?

EDIT: I see now that sum of positive integers doesn't always tend towards infinity, thanks to ColinWright's comment about powers of 2 (for which the sum of 1/n tends towards 1).

Also, since the numbers are all positive, it doesn't matter what order you sum them in, you're basically just asking whether the sum of 1/n for all the numbers in A is finite or not.

Dense math can often be complex to decipher. Sometimes it feels like reading an esoteric codebase to me!

1) Yes in this case 0 is not included in N. I’ve seen N defined both ways depending on the context, so it can be confusing when it’s not given explicitly.

2) By definition, a series sum is based on the limit of partial prefix sums. E.g 1/a_1, 1/a_1+1/a_2, ... It is an interesting question mathematically, if the sum stays the same when you arbitrarily rearrange the terms of the series. In general the answer is no (see Riemann rearrangement theorem), but as this series is only made up of positive reals, it can be rearranged arbitrarily without change in how it converges (or doesn’t).

To the second part of your question, take any geometric series, i.e. A = {1, r, r^2, ...}, then it will converge. There are other classes of series that will converge in this case, and the conjecture is basically asking to characterize sets with diverging series as needing to be “large and dense” in a certain sense.

Note that a geometric series can also be a multiple, e.g. (a, a r, a r^2, ...). It converges if and only if |r| < 1.

Good point, I was not being fully general there!

A dense APL codebase at that.

1. Yes, as you say it doesn't matter 2. Order of summation doesn't matter when all numbers are positive

> Since A only contains positive integers doesn't sum of 1/n for all n in A always tend towards infinity?

no, think for instance sum(1/n^2) EDIT: or sum(1/2^n) which solves Zeno's paradox (Achilles vs Tortoise)

Yeah, I would say that understanding conjectures often requires knowing some "background lemmas" in addition to knowing the definitions of the objects used in the definition, for this very reason. As another very simple example it can be shown that you can replace ℕ by the set of integers greater than 3, and the resulting conjecture is equivalent.

Ah, your Q&A made it much clearer for me. Thanks.

Reply on news.ycombinator.com