Sign in: Staff/Students
Dr Boris Konev and Dr Alexei Lisitsa are now running software in an attempt to find a result for discrepancy 3
University of Liverpool academics made significant progress towards solving an 80 year old maths puzzle using a computer programme, but the resulting proof is so massive it’s impossible for any human to check.
Computer scientists, Dr Boris Konev and Dr Alexei Lisitsa successfully cracked ErdÅ‘s discrepancy problem (for a particular discrepancy bound C=2) and in the process produced more data than the entire written contents of Wikipedia.
The riddle was proposed in the 1930s by the Hungarian mathematician Paul ErdÅ‘s, who offered $500 for its solution.
ErdÅ‘s was fascinated by the extent to which an infinite sequence of numbers containing nothing but +1s and -1s contains internal patterns. One way to measure that is to cut the infinite sequence off at a certain point, and then create finite sub-sequences within that part of the sequence, such as considering only every third number or every fourth.
Dr Konev and Dr Lisitsa took a sequence 1,161 numbers long and managed to demonstrate that an infinite sequence will always have a discrepancy larger than two. The resulting proof generated is an enormous 13 gigabytes.
The pair compared this to the size of Wikipedia, the text of which is a 10-gigabyte download. It is probably the longest proof ever and dwarfs another famously huge proof, the Classification Theorem of Finite Groups, which totalled 15,000 pages.
But, although checking this is beyond the reach of humans, they suggest future developments could change the landscape.
Dr Lisitsa, from the University’s School of Electrical Engineering, Electronics and Computer Science, said: “On the one hand, it is true that our computer-generated solution is beyond the reach of humans to fully understand. On the other, all we can say for now is that at the moment there is no known ‘better’ human-comprehensible solution – but it does not mean that such a solution could not (or will not) be found in the future.”
Spot a pattern
Dr Konev added: “ErdÅ‘s’ hypothesis was that a discrepancy of any value can always be found, a far cry from the discrepancies of 1 and 2 that have now been proven. Our software has been running for weeks in an attempt to find a result for discrepancy 3. But even if subsequent programs show that higher and higher discrepancies exist for any infinite sequence, a computer cannot check the infinity of all numbers.”
Instead, Dr Lisitsa suggests, it is likely that computer-assisted proofs for specific discrepancies will eventually enable a human to spot a pattern and come up with a proof for all numbers.
You must be logged in to post a comment.
All recent news
School of Law and Social Justice announces opportunities for students to train at the European Court of Human Rights
Winner of the John McGahern Book Prize announced
Termites may have a larger role in future ecosystems
Team Sport Liverpool Blog: Cheerleading
Keeping healthy at university
. @CourtneyPine1 and @zoe_rahman are here 🤩
They’re reunited for a string of live shows to celebrate and debut new material from Courtney's forthcoming album 'Spirituality' tonight at The Tung Auditorium.
Can't wait for our new season to begin. Tix 👉https://bit.ly/3Rx5ssc
New international study involving Prof @FunkyAnt finds that termites may have a larger role in future ecosystems http://bit.ly/3dJQNM2
An exciting opportunity for @LivUniSLSJ graduates to undertake paid Traineeships @ECHR_CEDH has been announced. We're delighted to join a small number of universities worldwide who can select our students for this invaluable experience. Read more here 👉 https://news.liverpool.ac.uk/2022/09/23/school-of-law-and-social-justice-announces-opportunities-for-students-to-train-at-the-european-court-of-human-rights/