Re:The Erdos discrepancy problem
by kittenfluff on Friday September 18, 2015 @08:22AM
(#10238717)
My interpretation in layman's terms of what this paper has proved -
Take an infinite sequence of +1 and -1, for example
1, 1, -1, 1, -1, -1, -1, 1, 1, -1, ...
You get an evenly spaced subsequence by starting on the n'th element, and picking every n'th element after that (and stopping after finitely many terms). So for example, we could pick every 2nd element of this sequence and get
1 (stopping after 1 term)
1, 1 (stopping after 2 terms)
1, 1, -1 (stopping after 3 terms)
1, 1, -1, 1 (stopping after 4 terms)
1, 1, -1, 1, -1 (stopping after 5 terms)
The discrepancy of an evenly spaced subsequence is obtained by adding together all the members of the subsequence and taking the absolute value. So the discrepancies of the sequences above are 1, 2, 1, 2, and 1.
The challenge is to find an evenly-spaced subsequence with as large a discrepancy as possible. For example, in a given sequence, can you find an evenly-spaced subsequence with a discrepancy of 10? of 100? of a million?
The paper has (apparently) proved that for any sequence, there is no upper limit to the discrepancies of evenly spaced subsequences, i.e. no matter how large the discrepancy of a subsequence you have found, there is always one larger.
The amazing thing about this result, to me, is the fact that it holds for any sequence of +1 and -1. Even if you try to engineer a sequence whose subsequences all have very small discrepancy, in some sense "there isn't enough room". You are always doomed to come up with a sequence containing evenly-spaced subsequences of arbitrarily large discrepancy.
Re:The Erdos discrepancy problem
by jsprogrammer on Friday September 18, 2015 @01:19PM
(#10240506)
It seems it would come down to an under-sampling problem. You should be able to weave through the sequence any way you want, but if you weave through at a frequency different (ie. lower) than the frequency needed to sample the small discrepancy, you will begin to measure artifacts of the "original signal" (ie. your small discrepancy sequences).
Regarding your second sentence, could you elaborate? Research in many fields is already highly collaborative (e.g., particle physics), so I'm not sure what you are saying might/should change.
Re:The Erdos discrepancy problem
by jballanc on Friday September 18, 2015 @02:04PM
(#10240942)
Very interesting result, and it feels like this could be more important than it might seem at first glance. If this result could be further generalized for sampling any continuously integrable function, it could have interesting implications for Maxwell's Demon.
Re:The Erdos discrepancy problem
by vortico on Saturday September 26, 2015 @03:00AM
(#10282388)
That's his writing style, but I don't know why. I guess pushing out papers all the time deemphasizes the style in which he makes his argument, in favor of inventing the argument.
Re:The Erdos discrepancy problem
by re501 on Saturday September 26, 2015 @12:49PM
(#10283568)
Well since it's so obviously redundant you start to wonder that maybe it isn't redundant and maybe you're wrong and not getting something when in-fact you're right and it is redundant. To me it more annoying than emphasizing.
When you want to emphasize you should make it clear that you're emphasizing.
Take an infinite sequence of +1 and -1, for example
You get an evenly spaced subsequence by starting on the n'th element, and picking every n'th element after that (and stopping after finitely many terms). So for example, we could pick every 2nd element of this sequence and get The discrepancy of an evenly spaced subsequence is obtained by adding together all the members of the subsequence and taking the absolute value. So the discrepancies of the sequences above are 1, 2, 1, 2, and 1.The challenge is to find an evenly-spaced subsequence with as large a discrepancy as possible. For example, in a given sequence, can you find an evenly-spaced subsequence with a discrepancy of 10? of 100? of a million?
The paper has (apparently) proved that for any sequence, there is no upper limit to the discrepancies of evenly spaced subsequences, i.e. no matter how large the discrepancy of a subsequence you have found, there is always one larger.
The amazing thing about this result, to me, is the fact that it holds for any sequence of +1 and -1. Even if you try to engineer a sequence whose subsequences all have very small discrepancy, in some sense "there isn't enough room". You are always doomed to come up with a sequence containing evenly-spaced subsequences of arbitrarily large discrepancy.
https://en.wikipedia.org/wiki/Polymath_Project for those who aren't aware of the polymath project.
Regarding your second sentence, could you elaborate? Research in many fields is already highly collaborative (e.g., particle physics), so I'm not sure what you are saying might/should change.
Is there a need to mention the {−1,+1} twice?
When you want to emphasize you should make it clear that you're emphasizing.