Erdos Conjecture
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 18
 Joined: Sun Jan 27, 2008 5:20 pm UTC
Erdos Conjecture
So, today's comic led me to the wikipedia page on Paul Erdos, and from there to the page on "Erdős conjecture on arithmetic progressions". My question is what restrictions are there on the set in the problem? I am not too familiar with sets outside of the problem, so I am probably missing something not unique to this question, but something about sets in general.
I ask because the set: 1, 2, 1, 2, 1, 2, ... Is only positive integers, the sum of the reciprocals clearly diverges, and I don't think it has an arithmetic progression for anything greater than 2. It shouldn't be too hard to find a function to return those values, if that's one of the requirements for a set.
Anyways, thanks in advance.
I ask because the set: 1, 2, 1, 2, 1, 2, ... Is only positive integers, the sum of the reciprocals clearly diverges, and I don't think it has an arithmetic progression for anything greater than 2. It shouldn't be too hard to find a function to return those values, if that's one of the requirements for a set.
Anyways, thanks in advance.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Erdos Conjecture
A set has no repetitions. Your sequence has lots.
So, for instance, {1, 4, 9, 25, 36,..., n^{2}, ...} is a set, and so is {1, 2}, but not {1, 2, 1, 2, 1, 2, 1, ...}.
So, for instance, {1, 4, 9, 25, 36,..., n^{2}, ...} is a set, and so is {1, 2}, but not {1, 2, 1, 2, 1, 2, 1, ...}.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Erdos Conjecture
Generic Goon wrote:It shouldn't be too hard to find a function to return those values, if that's one of the requirements for a set.
Your question's already been answered, but what do you think a "function" is? A function doesn't have to be defined by a formula. What you've written down is a sequence, which already defines a function.
Re: Erdos Conjecture
jestingrabbit wrote:A set has no repetitions. Your sequence has lots.
So, for instance, {1, 4, 9, 25, 36,..., n^{2}, ...} is a set, and so is {1, 2}, but not {1, 2, 1, 2, 1, 2, 1, ...}.
Just a nitpick:
The more common definition is that {1, 2, 1, 2, 1, 2, 1, ...} IS a set but it is equal to the set {1,2}.
Re: Erdos Conjecture
Erdos's conjecture, copied from wikipedia, is "If the sum of the reciprocals of a sequence of integers diverges, then the sequence contains arithmetic progressions of arbitrary length."
The sequence 1,2,1,2,1,2,1,2, ... does satisfy the condition that the sum of the reciprocals diverges. You can get an arithmetic subsequence of arbitrary lenth just by letting the common difference be 0 and picking as many 1's or 2's as you like.
The sequence 1,2,1,2,1,2,1,2, ... does satisfy the condition that the sum of the reciprocals diverges. You can get an arithmetic subsequence of arbitrary lenth just by letting the common difference be 0 and picking as many 1's or 2's as you like.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Erdos Conjecture
leachboy wrote:Erdos's conjecture, copied from wikipedia, is "If the sum of the reciprocals of a sequence of integers diverges, then the sequence contains arithmetic progressions of arbitrary length."
Huh?
http://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions wrote:Erdős' conjecture on arithmetic progressions, often incorrectly referred to as the Erdős–Turán conjecture, is a conjecture in additive combinatorics due to Paul Erdős. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.
The only link searching for your sentence turns up is an invalid subject on a radiohead forum...
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Erdos Conjecture
General_Norris: Taking pride in your nation is taking pride in the division of humanity.
Pirate.Bondage: Let's get married. Right now.
Pirate.Bondage: Let's get married. Right now.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Erdos Conjecture
jestingrabbit wrote:leachboy wrote:Erdos's conjecture, copied from wikipedia, is "If the sum of the reciprocals of a sequence of integers diverges, then the sequence contains arithmetic progressions of arbitrary length."
Huh?http://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions wrote:Erdős' conjecture on arithmetic progressions, often incorrectly referred to as the Erdős–Turán conjecture, is a conjecture in additive combinatorics due to Paul Erdős. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.
The only link searching for your sentence turns up is an invalid subject on a radiohead forum...
Does it matter whether we work with sets or sequences? The two statements are obviously equivalent. If your sequence contains terms which are repeated arbitrarily often, then it contains arithmetic progressions of arbitrary length. Otherwise, the sum of the reciprocals of the sequence diverges iff the sum of the reciprocals of the set of numbers appearing in the sequence diverges, and one contains arithmetic progressions of arbitrary length iff the other does.
It is quite possible that Wikipedia changed from one version of the statement to the other, equivalent version.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: Erdos Conjecture
skeptical scientist wrote:It is quite possible that Wikipedia changed from one version of the statement to the other, equivalent version.
Nah, the article has only been edited three times this year, and none of them changed "set" to "sequence" or viceversa; they were all pretty unrelated to the wording of the opening paragraph.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Erdos Conjecture
skeptical scientist wrote:Does it matter whether we work with sets or sequences?
If you allow degenerate arithmetic progressions you might believe that the result is trivially true for all non empty sets. Obviously that's not the intention so it makes more sense to me to talk about arithmetic progressions in sets and expect the reader to understand that all the numbers in the progression must be different.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Erdos Conjecture
jestingrabbit wrote:leachboy wrote:Erdos's conjecture, copied from wikipedia, is "If the sum of the reciprocals of a sequence of integers diverges, then the sequence contains arithmetic progressions of arbitrary length."
Huh?
I was quoting the wikipedia page on Paul Erdos, where it erroneously uses the word "sequence" in place of "set".

 Posts: 77
 Joined: Mon Apr 20, 2009 7:56 pm UTC
Re: Erdos Conjecture
sje46 wrote:Some light. Harri doesn't get the new xkcd.
I can try to explain the new xkcd...
well Paul Erdos came up with a system of, titles for mathematicians and what not. Paul Erdos himself had the title of Erdos 0. From there, anyone who worked directly with him, would have the title Erdos 1 (very respected in the math world). Then people who worked with people who worked with Erdos would have the title Erdos 2, ect.
Now when Paul Erdos died, all hopes of obtaining Erdos 1 was lost...since he was dead. But now that the Dead are walking again, the comic shows the guy running into the math department having everyone sign some work and then getting Paul Erdos to sign it so they would all have the title of Erdos 1, a great success!
Re: Erdos Conjecture
silvermace wrote:well Paul Erdos came up with a system of, titles for mathematicians and what not. Paul Erdos himself had the title of Erdos 0. From there, anyone who worked directly with him, would have the title Erdos 1 (very respected in the math world). Then people who worked with people who worked with Erdos would have the title Erdos 2, ect.
No, Erdos did not come up with it. His friends came up with it as a joking reference to his immense amount of collaborators and publications.
 Yakk
 Poster with most posts but no title.
 Posts: 11128
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Erdos Conjecture
And it is typically called your Erdos number.
The alttext is about ErdosBacon numbers, which are harder to get.
The alttext is about ErdosBacon numbers, which are harder to get.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 1
 Joined: Fri Jul 24, 2009 6:58 pm UTC
Re: Erdos Conjecture
I just read that Erdos has cash rewards for certain unsolved problems of varying difficulty. Now that he's dead, you can still solve one of the unsolved problems for the prize which will be paid by someone administering the contests, but you can instead receive the original check signed by Erdos himself which cannot be cashed. So if Erdos were to come to life, you could have one of the cashed checks that had lacked the signature of Erdos signed by Erdos despite the fact that you previously opted for the cash instead of his original signed check. Who writes this stuff?
Re: Erdos Conjecture
If Erdos came back to life, you could just cash one of the checks he did write. The only thing stopping you from cashing it is the fact that he's dead.
Re: Erdos Conjecture
And that the account the cheque is drawn on is long closed, and that cheques are typically only valid for six months.
When will we win the war on memes?
Who is online
Users browsing this forum: No registered users and 8 guests