gmalivuk wrote: tomtom2357 wrote:
Now if c doesn't exist, then there is a sequence with no arithmetic progression of length 3 whose reciprocals diverge
Why do you think this?
Yes, finding c would prove the conjecture, but the conjecture could also be true even if there is no such c, just as 1/r^n converges for all r<1 but can have an arbitrarily high limit by choosing r arbitrarily close to 1.
For some reason (despite this thread being quite old), today I was thinking about this conjecture and recalled this thread. I have a proof of tomtom's claim, that the statements (using "large set" to mean one whose sum of reciprocals diverges):
For any large set, there is an arithmetic progression (AP) of length n.
There exists a finite c greater than the sum of the reciprocals of any set free of APs of length n.
Are equivalent. It's pretty obvious that the latter implies the former, so we only need to show that the former implies the latter. For convenience, let R(S) = sum 1/s for all s in S. To do this, we assume the inverse of the second statement: For any positive c, there exists a set S(c) such that R(S(c)) > c. We use this to construct a set P which is large and which is free from AP of length n, but which is large.
In particular, we will construct an infinite series of pairwise disjoint sets p(k) for natural k, each of which will satisfy R(p(k)) > 1. The set P will be the union of these over all the naturals, and will thus obviously have R(P) be infinite. Obviously, none of the sets p(k) in the union contain AP of length n, but this does not mean their union does not; we require a specialized construction for that. In particular:
Let the first term of some sequence N be N(1)=1. Consider the set S(1). Since the sum of its reciprocals is strictly greater than one, it must be possible to choose a natural N(2) such that R(S(1)∩[1,N(2)])>1. This forms p(1)=S(1)∩[1,N(2)]. Next, consider the set S'(2) = 2N(2)*S(2N(2)), where the scalar 2N(2) scales every member of S(2N(2)). Note that R(S')>1, so we can similarly choose a natural N(3) such that R(S'∩[2N(2),N(3)])>1. Set p(2)=S'(2)∩[2N(2),N(3)]. We would then consider an S'(3)=2N(3)*S(2N(3)) and so on to construct all the p.
To show that no arithmetic progression of length n exist in P, consider the sequence P(1) = p(1) and P(k+1) = P(k)∪p(k+1). Suppose k is the smallest natural such that P(k) contains an arithmetic progression of length n. Obviously, neither P(k-1) nor p(k) contain such a progression, and so the progression must span across both of those sets. To show that this is impossible, we use the fact that, by construction, there must exist an N such that any p in P(k-1) has p<=N and any p in p(k) has 2N divides p. Thus, we split into two cases (which are not necessarily distinct, but which certainly cover any possibility):
1. There are two or more terms of the progression in P(k-1). In this case, let the highest two terms in P(k-1). Call these 1<=a<b<=N. The term after a and b would be 2b-a<=2N-1. This is less than any element of p(k) therefore must, since b was the greatest element in P(k-1), not be in P(k). This quickly implies that the whole progression in question is contained in P(k-1) and thus cannot be of length n.
2. There are two or more terms of the progression in p(k). This further implies there are two adjacent terms of the progression on p(k). Note that 2N divides anything in p(k) and thus also the difference between any two elements in p(k). Therefore, 2N divides all members of the arithmetic progression. However, 2N divides no member of P(k-1), thus the progression is contained wholly within p(k) and cannot be of length n.
This implies no such k exists, and inducting on the fact that P(1) does not contain any AP of length n, we find that no P(k) does and therefore that P does not. Thus, we have constructed a large set P containing no AP of length n, from the assumption that there is no finite upper bound to the sum of reciprocals R of a set not containing AP of length n. This proves the desired equivalence.
I think this is interesting, though I have a hard time believing such a c exists (and I guess, a hard time believing Erdos' conjecture to be true)