Erdos Conjecture

[tomtom2357]

I know that the Erdos Conjecture on Arithmetic progressions has been covered before on this forum (http://forums.xkcd.com/viewtopic.php?f=17&t=41066, but I have a new idea for the problem. First, so everyone knows what conjecture I'm talking about, the conjecture states that if the sum of the reciprocals of a sequence diverges, then it must contain arithmetic progressions of arbitrary length. For now I'll work on the case of an arithmetic progression of length 3, because it is a little easier, and this sub-problem also hasn't been solved yet.

So my idea is: If the conjecture is false, then there exists a sequence with no arithmetic progressions of length 3 such that the sum of the reciprocals of the series diverges. However, if the conjecture is in fact true, then no matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c. I had another idea that if we used the sequence defined by every number in the sequence being the smallest such that no arithmetic progression of length 3 exists so far in the sequence, then that will provide a good lower bound for this constant, and might be the sequence that converges (by this I mean that the sum of the reciprocals converges, but it is easier to just say converges) to c.

This is where you guys come in. I am hopeless at figuring out the summation, so I need one of you to compute it for me.

Thanks in advance!

tomtom2357

[mfb]

Finding this sequence might be very tricky on its own. But even if it is possible: It is not trivial that this sequence gives you an upper bound for the numbers. In fact, it is not clear whether such an upper bound even exists. The conjecture could be true, even if there are sets without arithmetic progressions where the sum of inverses can reach arbitrary large numbers (although I doubt that).

After getting some numbers by hand, OEIS found the sequence you are looking for: A003278

[tomtom2357]

After calculating the first 2^17 terms of the sequence, I have found that my sum (lets call it c') is >3.00545. I have found this by using an idea that the sequence a_n=3^m+a_n-(2^m), where m is selected such that 2^m<n<2^m+1. I have no idea how to find the complete sum, I have just been using Microsoft Excel the whole time.

[Timefly]

I'm not sure there's any basis for the following statement...

If the conjecture is false, then there exists a sequence with no arithmetic progressions of length 3 such that the sum of the reciprocals of the series diverges.

It could be that in every sum of the reciprocals of a series that diverges there is always an arithmetic progression of length 3 but not always one of length 4.

Correct me if I'm mistaken.

[tomtom2357]

I'm not sure there's any basis for the following statement...

If the conjecture is false, then there exists a sequence with no arithmetic progressions of length 3 such that the sum of the reciprocals of the series diverges.

It could be that in every sum of the reciprocals of a series that diverges there is always an arithmetic progression of length 3 but not always one of length 4.

Correct me if I'm mistaken.

I'm sorry, I am working on an easier version that is a subproblem of the original, so my new subconjecture is this: If the sum of the reciprocals of a sequence diverges, then there is an arithmetic progression of length 3. I will work on the full problem once I know that I can solve this. The subconjecture is also unproved, so I will test to see if my method works for l (l=length) 3, then extend to further results. Sorry for the misunderstanding.

[Timefly]

Alright. Never mind.

[mike-l]

No matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c.

Do you have any reason why that should be true? As an analogy, the sum of 1/r^n converges for any r less than 1, but there is no upper bound on what this can converge to. Finding such a c would indeed prove the conjecture, but the existence of such a c is a stronger statement than the conjecture itself.

[tomtom2357]

No matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c.

Do you have any reason why that should be true? As an analogy, the sum of 1/r^n converges for any r less than 1, but there is no upper bound on what this can converge to. Finding such a c would indeed prove the conjecture, but the existence of such a c is a stronger statement than the conjecture itself.

You are right if I extend this to arithmetic progressions of length more than three, as you can take infinitely many sequences with the limit sequence being {1,2,3,...} and since this goes to infinity (as in the sum of the reciprocals diverges), so does the limit of the sequences. However, I am trying to solve the problem for arithmetic progressions of length three, so this problem doesn't arise.

I have found that (using a shanks transformation of the series) that the series converges to about 3.0079

[mike-l]

No matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c.

Do you have any reason why that should be true? As an analogy, the sum of 1/r^n converges for any r less than 1, but there is no upper bound on what this can converge to. Finding such a c would indeed prove the conjecture, but the existence of such a c is a stronger statement than the conjecture itself.

You are right if I extend this to arithmetic progressions of length more than three, as you can take infinitely many sequences with the limit sequence being {1,2,3,...} and since this goes to infinity (as in the sum of the reciprocals diverges), so does the limit of the sequences. However, I am trying to solve the problem for arithmetic progressions of length three, so this problem doesn't arise.

I have found that (using a shanks transformation of the series) that the series converges to about 3.0079

You didn't answer my question.

I gave an example where a set of sequences all converge, but there was no upper bound on what they converged to. How do you know that this can't be the case here?

[tomtom2357]

No matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c.

Do you have any reason why that should be true? As an analogy, the sum of 1/r^n converges for any r less than 1, but there is no upper bound on what this can converge to. Finding such a c would indeed prove the conjecture, but the existence of such a c is a stronger statement than the conjecture itself.

You are right if I extend this to arithmetic progressions of length more than three, as you can take infinitely many sequences with the limit sequence being {1,2,3,...} and since this goes to infinity (as in the sum of the reciprocals diverges), so does the limit of the sequences. However, I am trying to solve the problem for arithmetic progressions of length three, so this problem doesn't arise.

I have found that (using a shanks transformation of the series) that the series converges to about 3.0079

You didn't answer my question.

I gave an example where a set of sequences all converge, but there was no upper bound on what they converged to. How do you know that this can't be the case here?

If you take the limit of a set of sequences that has no arithmetic progression of length three, then you get a sequence that has no arithmetic progression of length three. Now if c doesn't exist, then there is a sequence with no arithmetic progression of length 3 whose reciprocals diverge, and that means that the (sub)conjecture is false. So c only exists if the conjecture is true. So if I find c, then I have effectively proved the (sub)conjecture.

[mike-l]

Why are you taking limits?

You are talking about the set { {1/a_n} | a_n is an integer, there is no arithmetic progression of length 3 among the a_n}. You are claiming that if it's true that all members of this set have convergent sums, then the sums are bounded above.

I am talking about the set { {1/r^k} | r > 1 }. Now this set happens to have no arithmetic progressions of length 3 as well for all but countably many, so we can ignore those. So aside from the r^k need not be integers, this is similar to your set. Every member of this set converges, but the sums are not bounded. So it's not true in general that if a collection of sequences all converge, then their sums has an upper bound. The existence of such an upper bound is a stronger condition than the convergence.


So you think the set {1,2,4,5,10,...} has a reciprocal sum a little over 3.
Why does this tell you anything about the sequence {1,3,4,6,10,...}?

[Proginoskes]

if the conjecture is in fact true, then no matter what sequence you have that has no arithmetic progression, it will converge, and it will converge to a number at or below a specific constant. I will call this (hypothetical) constant c.

What makes you think c exists? I don't.

Suppose {a_1, a_2, a_3, ...} is a sequence like you suggest (no arithmetic progression of size 3), and the sum of 1 / a_i is less than r.

Then {a_1 / R, a_2 / R, a_3 / R, ... } is a sequence with no arithmetic progression of size 3, and the sum of its reciprocals is r*R. Now choose R to be arbitrarily big; then r*R > c.

EDIT (LATER): I know this is wrong. The terms have to be integers.

[gmalivuk]

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.

[tomtom2357]

Why are you taking limits?

You are talking about the set { {1/a_n} | a_n is an integer, there is no arithmetic progression of length 3 among the a_n}. You are claiming that if it's true that all members of this set have convergent sums, then the sums are bounded above.

I am talking about the set { {1/r^k} | r > 1 }. Now this set happens to have no arithmetic progressions of length 3 as well for all but countably many, so we can ignore those. So aside from the r^k need not be integers, this is similar to your set. Every member of this set converges, but the sums are not bounded. So it's not true in general that if a collection of sequences all converge, then their sums has an upper bound. The existence of such an upper bound is a stronger condition than the convergence.


So you think the set {1,2,4,5,10,...} has a reciprocal sum a little over 3.
Why does this tell you anything about the sequence {1,3,4,6,10,...}?

Okay then, I have another idea. a_n is the smallest integer such that you can construct a sequence of n integers (starting at 1) that have no arithmetic progression of length 3, and that the nth integer is a_n. Now let b_n be a sequence with no arithmetic progressions of length 3. By definition, b_n>=a_n, so therefore the sum of the reciprocals of b_n converges if the sum of the reciprocals of a_n converges. Now I only have to prove the convergence of the reciprocals of a_n.

Note: a_n may contain arithmetic progressions of length 3, I am using it because of its nice property stated above.

[mike-l]

Again, a_n converging is a stronger condition than your conjecture. In fact, that simply finds the c you were talking about before if it does.

Both methods you've suggested would prove your sub conjecture, but you haven't offered any idea on how to actually prove either of them.

[tomtom2357]

Again, a_n converging is a stronger condition than your conjecture. In fact, that simply finds the c you were talking about before if it does.

Both methods you've suggested would prove your sub conjecture, but you haven't offered any idea on how to actually prove either of them.

All I need to do is prove a lower bound on the series, such as a_n>=x^1.5, that would prove its convergence.

[antonfire]

All I need to do to prove the Riemann hypothesis is prove a lower bound for zeta(z) in the critical strip but away from the middle, such as |zeta(z)|>1.

[mike-l]

Again, a_n converging is a stronger condition than your conjecture. In fact, that simply finds the c you were talking about before if it does.

Both methods you've suggested would prove your sub conjecture, but you haven't offered any idea on how to actually prove either of them.

All I need to do is prove a lower bound on the series, such as a_n>=x^1.5, that would prove its convergence.

Yes, but you have no idea if that's even true, nor any idea on how to prove such a bound.