The Erdos discrepancy problem | Hacker News Reader

The Erdos discrepancy problem

arxiv.org

83 pointsrobinhouston12 comments

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.

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

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?

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

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

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

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.

> f: N → {−1,+1} taking values in {−1,+1}

Is there a need to mention the {−1,+1} twice?

No, but does it hurt? It emphasizes the main focus of the problem

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.

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.

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

Reply on news.ycombinator.com