## Erdos Conjecture

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Generic Goon
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.

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,..., n2, ...} 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.

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

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

Lul Thyme
Posts: 68
Joined: Sun Apr 13, 2008 1:43 pm UTC

### Re: Erdos Conjecture

jestingrabbit wrote:A set has no repetitions. Your sequence has lots.

So, for instance, {1, 4, 9, 25, 36,..., n2, ...} 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}.

leachboy
Posts: 3
Joined: Mon Jun 22, 2009 3:50 am UTC

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

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.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

sje46
Posts: 4730
Joined: Wed May 14, 2008 4:41 am UTC
Location: New Hampshire

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

skeptical scientist
closed-minded 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.

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

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 vice-versa; they were all pretty unrelated to the wording of the opening paragraph.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

Lul Thyme
Posts: 68
Joined: Sun Apr 13, 2008 1:43 pm UTC

### Re: Erdos Conjecture

Nvm

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.

leachboy
Posts: 3
Joined: Mon Jun 22, 2009 3:50 am UTC

### 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".

silvermace
Posts: 77
Joined: Mon Apr 20, 2009 7:56 pm UTC

### Re: Erdos Conjecture

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!

auteur52
Posts: 165
Joined: Sun Mar 23, 2008 11:08 pm UTC

### 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 alt-text is about Erdos-Bacon 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.

skepileptic
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?

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

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

u38cg
Posts: 187
Joined: Thu Jul 23, 2009 5:11 pm UTC
Location: Edinburgh, Scotland
Contact:

### 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?