Friday, February 21, 2014

ARR, MoAR! On computers and proofs.

so today i learned what a "discrepancy" is:
"Adding up the numbers in a sub-sequeηce gives a figure called the discrepaηcy, which acts as a measure of the structure of the sub-sequeηce .."

~ from " Wikipedia-size maths proof too big for humans to check" @newscientist
as for how this came up ..
Erdös thought that for any infinite sequeηce, it would always be possible to find a finite sub-sequeηce summing to a number larger than any you choose - but couldn't prove it.

It is relatively easy to show by hand that any way you arrange 12 +'s and -'s always has a sub-sequeηce whose sum exceeds 1. That means that anything longer – including any infinite sequeηce – must also have a discrepaηcy of 1 or more. But extending this method to showing that higher discrepaηcies must always exist is tough as the number of possible sub-sequeηces to test quickly balloons.

Now Konev and Lisitsa have used a computer to move things on. They have shown that an infinite sequeηce will always have a discrepaηcy larger than 2. In this case the cut-off was a sequeηce of length 1161, rather than 12. Establishing this took a computer nearly 6 hours and generated a 13-gigabyte file detailing its working.

No comments: