Erdos Conjecture

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

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.

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

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm 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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am 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.

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm 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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am 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.

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

Re: Erdos Conjecture

Alright. Never mind.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am 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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 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.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 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.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 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.

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

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.

gmalivuk
GNU Terry Pratchett
Posts: 26740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

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.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 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.

antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm 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?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am 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.

Moole
Posts: 93
Joined: Sun Jan 08, 2012 9:52 pm UTC

Re: Erdos Conjecture

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)
Mathematical hangover (n.): The feeling one gets in the morning when they realize that that short, elementary proof of the Riemann hypothesis that they came up with at midnight the night before is, in fact, nonsense.