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.”

ebooks
ebookA delicious collection of 50 meaty main courses
Life and Style
ebookNow available in paperback
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

    Ashdown Group: Data Scientist - London - £50,000 + bonus

    £35000 - £50000 per annum + generous bonus: Ashdown Group: Business Analytics ...

    Ashdown Group: IT Project Coordinator (Software Development) - Kingston

    £45000 - £50000 per annum: Ashdown Group: IT Project Coordinator (Software Dev...

    SThree: Trainee Recruitment Consultant - Bristol

    £18000 - £23000 per annum + Uncapped OTE: SThree: SThree Trainee Recruitment C...

    SThree: Trainee Recruitment Consultant - Birmingham

    £18000 - £23000 per annum + Uncapped OTE: SThree: SThree Trainee Recruitment C...

    Day In a Page

    General Election 2015: Ed Miliband's unlikely journey from hapless geek to heart-throb

    Miliband's unlikely journey from hapless geek to heart-throb

    He was meant to be Labour's biggest handicap - but has become almost an asset
    General Election 2015: A guide to the smaller parties, from the the National Health Action Party to the Church of the Militant Elvis Party

    On the margins

    From Militant Elvis to Women's Equality: a guide to the underdogs standing in the election
    Amr Darrag: Ex-Muslim Brotherhood minister in exile still believes Egypt's military regime can be replaced with 'moderate' Islamic rule

    'This is the battle of young Egypt for the future of our country'

    Ex-Muslim Brotherhood minister Amr Darrag still believes the opposition can rid Egypt of its military regime and replace it with 'moderate' Islamic rule, he tells Robert Fisk
    Why patients must rely less on doctors: Improving our own health is the 'blockbuster drug of the century'

    Why patients must rely less on doctors

    Improving our own health is the 'blockbuster drug of the century'
    Sarah Lucas is the perfect artist to represent Britain at the Venice Biennale

    Flesh in Venice

    Sarah Lucas has filled the British pavilion at the Venice Biennale with slinky cats and casts of her female friends' private parts. It makes you proud to be a woman, says Karen Wright
    11 best anti-ageing day creams

    11 best anti-ageing day creams

    Slow down the ageing process with one of these high-performance, hardworking anti-agers
    Juventus 2 Real Madrid 1: Five things we learnt, including Iker Casillas is past it and Carlos Tevez remains effective

    Juventus vs Real Madrid

    Five things we learnt from the Italian's Champions League first leg win over the Spanish giants
    Ashes 2015: Test series looks a lost cause for England... whoever takes over as ECB director of cricket

    Ashes series looks a lost cause for England...

    Whoever takes over as ECB director of cricket, says Stephen Brenkley
    Fishing for votes with Nigel Farage: The Ukip leader shows how he can work an audience as he casts his line to the disaffected of Grimsby

    Fishing is on Nigel Farage's mind

    Ukip leader casts a line to the disaffected
    Who is bombing whom in the Middle East? It's amazing they don't all hit each other

    Who is bombing whom in the Middle East?

    Robert Fisk untangles the countries and factions
    China's influence on fashion: At the top of the game both creatively and commercially

    China's influence on fashion

    At the top of the game both creatively and commercially
    Lord O’Donnell: Former cabinet secretary on the election and life away from the levers of power

    The man known as GOD has a reputation for getting the job done

    Lord O'Donnell's three principles of rule
    Rainbow shades: It's all bright on the night

    Rainbow shades

    It's all bright on the night
    'It was first time I had ever tasted chocolate. I kept a piece, and when Amsterdam was liberated, I gave it to the first Allied soldier I saw'

    Bread from heaven

    Dutch survivors thank RAF for World War II drop that saved millions
    Britain will be 'run for the wealthy and powerful' if Tories retain power - Labour

    How 'the Axe' helped Labour

    UK will be 'run for the wealthy and powerful' if Tories retain power