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

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

ES Rentals

    iJobs Job Widget
    iJobs Gadgets & Tech

    Recruitment Genius: Client IT Account Manager

    £25000 - £30000 per annum: Recruitment Genius: A Client IT Account Manager is ...

    Recruitment Genius: Windows Server Engineer - Compute Engineer

    £30000 - £35000 per annum: Recruitment Genius: The Compute Engineer role also ...

    SThree: Trainee Recruitment Consultant

    £13676.46 - £15864.28 per annum + Uncapped Commission: SThree: As a Trainee Re...

    Recruitment Genius: 3rd Line IT Support / Senior Engineer / Support Analyst

    £24000 - £32000 per annum: Recruitment Genius: An exciting opportunity has ari...

    Day In a Page

    No postcode? No vote

    Floating voters

    How living on a houseboat meant I didn't officially 'exist'
    Louis Theroux's affable Englishman routine begins to wear thin

    By Reason of Insanity

    Louis Theroux's affable Englishman routine begins to wear thin
    Power dressing is back – but no shoulderpads!

    Power dressing is back

    But banish all thoughts of Eighties shoulderpads
    Spanish stone-age cave paintings 'under threat' after being re-opened to the public

    Spanish stone-age cave paintings in Altamira 'under threat'

    Caves were re-opened to the public
    'I was the bookies’ favourite to be first to leave the Cabinet'

    Vince Cable interview

    'I was the bookies’ favourite to be first to leave the Cabinet'
    Election 2015: How many of the Government's coalition agreement promises have been kept?

    Promises, promises

    But how many coalition agreement pledges have been kept?
    The Gaza fisherman who built his own reef - and was shot dead there by an Israeli gunboat

    The death of a Gaza fisherman

    He built his own reef, and was fatally shot there by an Israeli gunboat
    Saudi Arabia's airstrikes in Yemen are fuelling the Gulf's fire

    Saudi airstrikes are fuelling the Gulf's fire

    Arab intervention in Yemen risks entrenching Sunni-Shia divide and handing a victory to Isis, says Patrick Cockburn
    Zayn Malik's departure from One Direction shows the perils of fame in the age of social media

    The only direction Zayn could go

    We wince at the anguish of One Direction's fans, but Malik's departure shows the perils of fame in the age of social media
    Young Magician of the Year 2015: Meet the schoolgirl from Newcastle who has her heart set on being the competition's first female winner

    Spells like teen spirit

    A 16-year-old from Newcastle has set her heart on being the first female to win Young Magician of the Year. Jonathan Owen meets her
    Jonathan Anderson: If fashion is a cycle, this young man knows just how to ride it

    If fashion is a cycle, this young man knows just how to ride it

    British designer Jonathan Anderson is putting his stamp on venerable house Loewe
    Number plates scheme could provide a licence to offend in the land of the free

    Licence to offend in the land of the free

    Cash-strapped states have hit on a way of making money out of drivers that may be in collision with the First Amendment, says Rupert Cornwell
    From farm to fork: Meet the Cornish fishermen, vegetable-growers and butchers causing a stir in London's top restaurants

    From farm to fork in Cornwall

    One man is bringing together Cornwall's most accomplished growers, fishermen and butchers with London's best chefs to put the finest, freshest produce on the plates of some of the country’s best restaurants
    Robert Parker interview: The world's top wine critic on tasting 10,000 bottles a year, absurd drinking notes and New World wannabes

    Robert Parker interview

    The world's top wine critic on tasting 10,000 bottles a year, absurd drinking notes and New World wannabes
    Don't believe the stereotype - or should you?

    Don't believe the stereotype - or should you?

    We exaggerate regional traits and turn them into jokes - and those on the receiving end are in on it too, says DJ Taylor