Boris Konev and Alexei Lisitsa are both researchers at the University of Liverpool, who work in Logic and Computation. They have recently made important progress on the Erd?s Discrepancy Problem using computer tools from logic. Unlike the approach of a PolyMath project on the problem, their proof comes from a single program that ran for just over 6 hours, a program administered only by them, but mostly not written by them.
Today Ken and I wish to talk about their paper and two consequences of it.
Their paper can be read at two levels. On the surface the paper is about the famous discrepancy conjecture of Paul Erd?s, which we have talked about before. I will state the precise conjecture in a moment, it was said that previously the best lower bound for a certain “constant” was 1 and they moved it to 2. Since Erd?s conjectured that…
View original post 1,694 more words