Computer cracks Erdős puzzle – but no human brain can check the answer

 

A puzzle that has confounded mathematicians for almost a century is closer than ever to being solved, it has emerged. But there’s one slight problem.

The calculations which prove a part of what’s known as “Erdős discrepancy problem” have been worked out by a computer. And the sheer amount of data – more than the entire contents of Wikipedia – is so vast that it would be practically impossible to be checked by a human brain.

The “discrepancy problem” was posed in the 1930s by renowned Hungarian mathematician Paul Erdős. It revolves around the properties of infinite sequences of numbers containing nothing but +1s and -1s. Patterns in such sequences can be measured by creating finite sub-sequences.

Professor Enrico Scalas, of the University of Sussex, explained the premise: “You have a sequence of 1s and -1s (for instance, generated by tossing a coin) and a constant C. One is looking for a finite subsequence long enough so that the sum of the elements of the subsequence is larger than C.”

The difficulty lies in actually proving this is the case mathematically. That’s where computers and their ability to perform complex calculations come in. With this aid, computer scientists Dr Alexei Lisitsa and Dr Boris Konev of the University of Liverpool managed to demonstrate that an infinite sequence will always have a discrepancy (the sum of the numbers in a sub-sequence) larger than two.

They took a sequence 1,161 numbers long and the resulting data was a 13-gigabyte file. That’s bigger than the 10GB estimated size of the entire written contents of Wikipedia. It is the start of solving the puzzle – but while computers have helped, they have not yet taken over from humans.

In a statement, the researchers told The Independent: “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.”

Mathematicians were philosophical about being beaten by a machine. Matt Parker, Public Engagement in Maths Fellow at Queen Mary, University of London, said: “The computer did the heavy-lifting, but it was the insight and creativity of its human programmers which made it possible.”

Chris Budd, Professor of Mathematics at the Royal Institution of Great Britain, added: “Computers are doing for maths what the printing press did for writing, in that they are opening up unlimited possibilities.”

Life and Style
ebookNow available in paperback
ebooks
ebookA delicious collection of 50 meaty main courses
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
SPONSORED FEATURES
Independent Dating
and  

By clicking 'Search' you
are agreeing to our
Terms of Use.

ES Rentals

    iJobs Job Widget
    iJobs Gadgets & Tech

    Recruitment Genius: Head of Support Services

    £40000 - £55000 per annum: Recruitment Genius: This is an exciting opportunity...

    Recruitment Genius: Business Development Manager / Sales - OTE £40,000

    £20000 - £40000 per annum: Recruitment Genius: This IT provider for the educat...

    Recruitment Genius: Front End Developer / Web Designer

    £20000 - £25000 per annum: Recruitment Genius: This leader in the e-cigarette ...

    Recruitment Genius: Web Developer - PHP

    £32000 - £40000 per annum: Recruitment Genius: With extensive experience and a...

    Day In a Page

    The Silk Roads that trace civilisation: Long before the West rose to power, Asian pathways were connecting peoples and places

    The Silk Roads that trace civilisation

    Long before the West rose to power, Asian pathways were connecting peoples and places
    House of Lords: Outcry as donors, fixers and MPs caught up in expenses scandal are ennobled

    The honours that shame Britain

    Outcry as donors, fixers and MPs caught up in expenses scandal are ennobled
    When it comes to street harassment, we need to talk about race

    'When it comes to street harassment, we need to talk about race'

    Why are black men living the stereotypes and why are we letting them get away with it?
    International Tap Festival: Forget Fred Astaire and Ginger Rogers - this dancing is improvised, spontaneous and rhythmic

    International Tap Festival comes to the UK

    Forget Fred Astaire and Ginger Rogers - this dancing is improvised, spontaneous and rhythmic
    War with Isis: Is Turkey's buffer zone in Syria a matter of self-defence – or just anti-Kurd?

    Turkey's buffer zone in Syria: self-defence – or just anti-Kurd?

    Ankara accused of exacerbating racial division by allowing Turkmen minority to cross the border
    Doris Lessing: Acclaimed novelist was kept under MI5 observation for 18 years, newly released papers show

    'A subversive brothel keeper and Communist'

    Acclaimed novelist Doris Lessing was kept under MI5 observation for 18 years, newly released papers show
    Big Blue Live: BBC's Springwatch offshoot swaps back gardens for California's Monterey Bay

    BBC heads to the Californian coast

    The Big Blue Live crew is preparing for the first of three episodes on Sunday night, filming from boats, planes and an aquarium studio
    Austin Bidwell: The Victorian fraudster who shook the Bank of England with the most daring forgery the world had known

    Victorian fraudster who shook the Bank of England

    Conman Austin Bidwell. was a heartless cad who carried out the most daring forgery the world had known
    Car hacking scandal: Security designed to stop thieves hot-wiring almost every modern motor has been cracked

    Car hacking scandal

    Security designed to stop thieves hot-wiring almost every modern motor has been cracked
    10 best placemats

    Take your seat: 10 best placemats

    Protect your table and dine in style with a bold new accessory
    Ashes 2015: Alastair Cook not the only one to be caught in The Oval mindwarp

    Cook not the only one to be caught in The Oval mindwarp

    Aussie skipper Michael Clarke was lured into believing that what we witnessed at Edgbaston and Trent Bridge would continue in London, says Kevin Garside
    Can Rafael Benitez get the best out of Gareth Bale at Real Madrid?

    Can Benitez get the best out of Bale?

    Back at the club he watched as a boy, the pressure is on Benitez to find a winning blend from Real's multiple talents. As La Liga begins, Pete Jenson asks if it will be enough to stop Barcelona
    Athletics World Championships 2015: Beijing witnesses new stage in the Jessica Ennis-Hill and Katarina Johnson-Thompson heptathlon rivalry

    Beijing witnesses new stage in the Jess and Kat rivalry

    The last time the two British heptathletes competed, Ennis-Hill was on the way to Olympic gold and Johnson-Thompson was just a promising teenager. But a lot has happened in the following three years
    Jeremy Corbyn: Joining a shrewd operator desperate for power as he visits the North East

    Jeremy Corbyn interview: A shrewd operator desperate for power

    His radical anti-austerity agenda has caught the imagination of the left and politically disaffected and set a staid Labour leadership election alight
    Isis executes Palmyra antiquities chief: Defender of ancient city's past was killed for protecting its future

    Isis executes Palmyra antiquities chief

    Robert Fisk on the defender of the ancient city's past who was killed for protecting its future