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
ebookPart of The Independent’s new eBook series The Great Composers
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
Independent Dating
and  

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

ES Rentals

    iJobs Job Widget
    iJobs Gadgets & Tech

    SThree: Trainee Recruitment Consultant

    £20000 - £25000 per annum + uncapped commission : SThree: Hello! I know most ...

    Recruitment Genius: Project / Account Manager and IT Support

    £20000 - £25000 per annum: Recruitment Genius: This world leader in Online Pro...

    Ashdown Group: Business Analyst - Kent - up to £33,000

    £30000 - £33000 per annum + bonus and pension: Ashdown Group: Business Analyst...

    Recruitment Genius: Web Content Administrator

    £14000 per annum: Recruitment Genius: A Web Content Administrator is required ...

    Day In a Page

    Syrian conflict is the world's first 'climate change war', say scientists, but it won't be the last one

    Climate change key in Syrian conflict

    And it will trigger more war in future
    How I outwitted the Gestapo

    How I outwitted the Gestapo

    My life as a Jew in wartime Berlin
    The nation's favourite animal revealed

    The nation's favourite animal revealed

    Women like cuddly creatures whilst men like creepy-crawlies
    Is this the way to get young people to vote?

    Getting young people to vote

    From #VOTESELFISH to Bite the Ballot
    Poldark star Heida Reed: 'I don't think a single bodice gets ripped'

    Poldark star Heida Reed

    'I don't think a single bodice gets ripped'
    The difference between America and Israel? There isn’t one

    The difference between America and Israel? There isn’t one

    Netanyahu knows he can get away with anything in America, says Robert Fisk
    Families clubbing together to build their own affordable accommodation

    Do It Yourself approach to securing a new house

    Community land trusts marking a new trend for taking the initiative away from developers
    Head of WWF UK: We didn’t send Cameron to the Arctic to see green ideas freeze

    David Nussbaum: We didn’t send Cameron to the Arctic to see green ideas freeze

    The head of WWF UK remains sanguine despite the Government’s failure to live up to its pledges on the environment
    Author Kazuo Ishiguro on being inspired by shoot-outs and samurai

    Author Kazuo Ishiguro on being inspired by shoot-outs and samurai

    Set in a mythologised 5th-century Britain, ‘The Buried Giant’ is a strange beast
    With money, corruption and drugs, this monk fears Buddhism in Thailand is a ‘poisoned fruit’

    Money, corruption and drugs

    The monk who fears Buddhism in Thailand is a ‘poisoned fruit’
    America's first slavery museum established at Django Unchained plantation - 150 years after slavery outlawed

    150 years after it was outlawed...

    ... America's first slavery museum is established in Louisiana
    Kelly Clarkson: How I snubbed Simon Cowell and become a Grammy-winning superstar

    Kelly Clarkson: How I snubbed Simon Cowell and become a Grammy-winning superstar

    The first 'American Idol' winner on how she manages to remain her own woman – Jane Austen fascination and all
    Tony Oursler on exploring our uneasy relationship with technology with his new show

    You won't believe your eyes

    Tony Oursler's new show explores our uneasy relationship with technology. He's one of a growing number of artists with that preoccupation
    Ian Herbert: Peter Moores must go. He should never have been brought back to fail again

    Moores must go. He should never have been brought back to fail again

    The England coach leaves players to find solutions - which makes you wonder where he adds value, says Ian Herbert
    War with Isis: Fears that the looming battle for Mosul will unleash 'a million refugees'

    The battle for Mosul will unleash 'a million refugees'

    Aid agencies prepare for vast exodus following planned Iraqi offensive against the Isis-held city, reports Patrick Cockburn