## Erdos Conjecture

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Erdos Conjecture

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.

tomtom2357
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

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
mfb

Posts: 824
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Erdos Conjecture

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 an=3m+an-(2^m), where m is selected such that 2m<n<2m+1. I have no idea how to find the complete sum, I have just been using Microsoft Excel the whole time.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

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.
Timefly

Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

### Re: Erdos Conjecture

Timefly wrote: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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

Alright. Never mind.
Timefly

Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

### Re: Erdos Conjecture

tomtom2357 wrote: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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Erdos Conjecture

mike-l wrote:
tomtom2357 wrote: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
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

tomtom2357 wrote:
mike-l wrote:
tomtom2357 wrote: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

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?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Erdos Conjecture

mike-l wrote:
tomtom2357 wrote:
mike-l wrote:
tomtom2357 wrote: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

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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

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,...}?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Erdos Conjecture

tomtom2357 wrote: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.

Proginoskes

Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Erdos Conjecture

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.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20294
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: Erdos Conjecture

mike-l wrote: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. an 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 an. Now let bn be a sequence with no arithmetic progressions of length 3. By definition, bn>=an, so therefore the sum of the reciprocals of bn converges if the sum of the reciprocals of an converges. Now I only have to prove the convergence of the reciprocals of an.

Note: an may contain arithmetic progressions of length 3, I am using it because of its nice property stated above.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Erdos Conjecture

mike-l wrote: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 an>=x^1.5, that would prove its convergence.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Erdos Conjecture

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.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

antonfire

Posts: 1770
Joined: Thu Apr 05, 2007 7:31 pm UTC

### Re: Erdos Conjecture

tomtom2357 wrote:
mike-l wrote: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 an>=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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC