5 ms·

The Erdos discrepancy problem

83 points by robinhouston 11y ago

sampo 11y ago
> f: N → {−1,+1} taking values in {−1,+1} Is there a need to mention the {−1,+1} twice?
- arsenide 11y ago
  No, but does it hurt? It emphasizes the main focus of the problem
  - re501 11y ago
    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.
- vortico 11y ago
  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.
jballanc 11y ago
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.
mrcactu5 11y ago
it was a conjecture only a few days ago https://terrytao.wordpress.com/2015/09/11/the-erdos-discrepancy-problem-via-the-elliott-conjecture/ https://terrytao.wordpress.com/2015/09/11/the-erdos-discrepa...
myle 11y ago
It looks like another success story for the polymath project. Maybe the way research is done at least in some fields is time to change?
- privong 11y ago
  > It looks like another success story for the polymath project. Maybe the way research is done at least in some fields is time to change? https://en.wikipedia.org/wiki/Polymath_Project 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.
jacobolus 11y ago
For anyone wondering what this problem is, see http://michaelnielsen.org/polymath1/index.php?title=The_Erdős_discrepancy_problem http://michaelnielsen.org/polymath1/index.php?title=The_Erdő...
kittenfluff 11y ago
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.
- jsprogrammer 11y ago
  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).
rjmunro 11y ago
Good explanation of the problem here: https://www.youtube.com/watch?v=pFHsrCNtJu4 https://www.youtube.com/watch?v=pFHsrCNtJu4

83 points by robinhouston 11y ago

sampo 11y ago

> f: N → {−1,+1} taking values in {−1,+1} Is there a need to mention the {−1,+1} twice?

arsenide 11y ago
No, but does it hurt? It emphasizes the main focus of the problem
- re501 11y ago
  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.
vortico 11y ago
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.

jballanc 11y ago

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.

mrcactu5 11y ago

it was a conjecture only a few days ago https://terrytao.wordpress.com/2015/09/11/the-erdos-discrepancy-problem-via-the-elliott-conjecture/ https://terrytao.wordpress.com/2015/09/11/the-erdos-discrepa...

myle 11y ago

It looks like another success story for the polymath project. Maybe the way research is done at least in some fields is time to change?

privong 11y ago
> It looks like another success story for the polymath project. Maybe the way research is done at least in some fields is time to change? https://en.wikipedia.org/wiki/Polymath_Project 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.

jacobolus 11y ago

For anyone wondering what this problem is, see http://michaelnielsen.org/polymath1/index.php?title=The_Erdős_discrepancy_problem http://michaelnielsen.org/polymath1/index.php?title=The_Erdő...

kittenfluff 11y ago

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.

jsprogrammer 11y ago
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).

rjmunro 11y ago

Good explanation of the problem here: https://www.youtube.com/watch?v=pFHsrCNtJu4 https://www.youtube.com/watch?v=pFHsrCNtJu4