In today's newspaper NRC from The Netherlands a two-page article was dedicated to computer-aided mathematical proofs (sorry, paid link and in Dutch). Interesting in itself, but as an example it used the partial proof for divergence of the series consisting of a random distribution of $-1$ and $1$.
The Wikipedia lemma about Erdös conjecture shows this formula:
$$\left| \sum_{i=1}^k x_{i\cdot d} \right| > C$$
But I have trouble understanding that in common English and applying it to the text of the article, which translates as:
given an infinite sequence of $-1$ and $1$, take a finite set of terms at equal distance, i.e. the first, third and fifth, or the fifth, tenth and fifteenth term. Add all those terms together. How far can they differ from $0$? Erdös conjecture: infinitely far.
My misunderstanding comes from combining infinite, random and finite. I think that if the sequence is random, then any given finite set can potentially exist of only $1$ or only $-1$, meaning that the difference to zero is (potentially) equal to the amount of terms taken.
The article further explains that Boris Konev and Alexei Lisitsa have proven that within the first 1161 terms, the discrepancy is always at least $3$. But I can easily come up with a sequence that alternates on exactly the numbers taken, which would obviously result in a possible discrepancy of at most $1$ for at least some series or slices.
From the link, quote:
The proof that the computer came up with proves, the two researchers claim, "that no sequence of length $1161$ and discrepancy $2$ exists."
This seems contradictory, but no-one in the articles I found seem to wonder about this, and given that it requires so much research, I assume I simply misunderstand the problem.
I assume I am misunderstanding the problem, but can anybody explain me where I am going wrong?
First it's of utmost importance to understand the statement :
Now it seems obvious that the main misunderstanding you have lies in the contradiction between the sums of the form $$\sum_{i=1}^{k}x_{id}$$ (the correct interpretation ) and the quote from the newspaper :
These two interpretations don't agree obviously because the first term index must be also the common difference of the indices $d$ . (this is why $x_1+x_3+x_5$ isn't considered )
Now that you understand the statement let's look at the (already solved) cases $C=1$ and $C=2$ .
For simplicity I'll work for $C=1$ (the same works also for $C=2$) . We work by contradiction so we assume that :
There is an infinite sequence such that all the considered sums are at most $1$ in module
Now we take into account all the possible cases and start to build one hoping that eventually we'll reach a contradiction .
Start for example with $x_1=1$ .If we choose $x_2=1$ we have $x_1+x_2=2$ which exceeds $1$ so we must take $x_2=-1$ .Now it doesn't matter what we choose for $x_3$ so take $x_3=-1$ .
Now when we choose $x_4$ we should take care of the sums : $x_2+x_4$ and $x_1+x_2+x_3+x_4$ so $-1+x_4$ can't exceed $1$ in modulus which means that $x_4=1$ . It doesn't matter which $x_5$ we choose so take $x_5=1$ .
The sequence now looks like : $1,-1,-1,1,1$
When we choose $x_6$ we must take care of the sums : $x_1+x_2+x_3+x_4+x_5+x_6$ , $x_2+x_4+x_6$ and $x_3+x_6$ so $x_6+1$ , $x_6-1$ can't exceed $1$ in modulus which leaves no possibility to choose a candidate for $x_6$ :
If $x_6=1$ then $x_6+1=2$ which exceeds $1$. If $x_6=-1$ then $x_6-1=-2$ which exceeds $1$ (in module )
So we reached the desired contradiction .
If we work all the possibilities for the remaining cases (along the way we assumed that $x_3=-1$ and $x_5=1$ so there are more cases to handle ) then we'll reach contradictions in all cases so the assumed claim must be wrong and so the problem solved .
The same works for $C=2$ : Assuming there is such a sequence , we try to build it by trying all the possibilities satisfying the condition and when we reach a contradiction we're done .