Recently I watched a famous youtube video of talk given by Terry Tao on Erdős Discrepancy Problem https://www.youtube.com/watch?v=QauoO0j9Y9Y.

I never heard of this problem before his announcement of proof, quite a beginner, right?

In the beginning of this talk, he gave an equivalent statement of the problem, which I can't really think out why, namely

Given an infinite sequence $f(1),f(2),\dotsc\in\{-1,1\}$ and $C>0$, there are $n$, $d$ such that


the above statement is equivalent to

Given $C>0$, there is $N$ such that for every finite sequence $f(1),f(2),\dotsc,f(N)\in\{-1,1\}$ there are $n$, $d$ with $nd\leq N$ such that


What flummoxes me is that how the above one implies the below one. If the above one is true (once conjecture but now proven theorem), does there have some properties telling us that it won't be too large the first $n$, $d$ (smallest $nd$) for every chosen sequence $f(1),f(2),\dotsc$ under a given $C$?

Perhaps this is obvious to most people. Or maybe my understanding of the statement is wrong. Hope someone will help out. Thanks.

  • $\begingroup$ Assuming that the second statement is wrong, fix $C>0$ such that for each $N>0$, there is a sequence $(f_1,\dotsc,f_N)$ with $\left|\sum_{j=1}^n f_{jd}\right|\le C $ whenever $nd\le N$. Since there are only two possible values of $f_1$, among these finite sequences there are infinitely many sharing the same value of $f_1$. Among them, there are infinitely many sharing the same value of $f_2$, etc. Acting in this way, you construct an infinite sequence $(f_1,f_2,\ldots)$ which inherits the small discrepancy property from the finite sequences used o construct it. $\endgroup$ – Seva Dec 18 '15 at 8:50
  • $\begingroup$ Thanks a lot for the construction!! Now I find out the "sequence" that counters the Terry's theorem (kidding). $\endgroup$ – randy76 Dec 18 '15 at 18:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.