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

    Guru Careers: Software Developer / C# Developer

    £40-50K: Guru Careers: We are seeking an experienced Software / C# Developer w...

    Guru Careers: Software Developer

    £35 - 40k + Benefits: Guru Careers: We are seeking a Software Developer (JavaS...

    Ashdown Group: UI Developer - (UI, HTML, CSS, JavaScript, AngularJS)

    £25000 - £40000 per annum: Ashdown Group: UI Developer - (UI, JavaScript, HTML...

    Ashdown Group: Graduate UI Developer - HTML, CSS, Javascript

    £25000 - £30000 per annum: Ashdown Group: Graduate UI Application Developer - ...

    Day In a Page

    Sun, sex and an anthropological study: One British academic's summer of hell in Magaluf

    Sun, sex and an anthropological study

    One academic’s summer of hell in Magaluf
    From Shakespeare to Rising Damp... to Vicious

    Frances de la Tour's 50-year triumph

    'Rising Damp' brought De la Tour such recognition that she could be forgiven if she'd never been able to move on. But at 70, she continues to flourish - and to beguile
    'That Whitsun, I was late getting away...'

    Ian McMillan on the Whitsun Weddings

    This weekend is Whitsun, and while the festival may no longer resonate, Larkin's best-loved poem, lives on - along with the train journey at the heart of it
    Kathryn Williams explores the works and influences of Sylvia Plath in a new light

    Songs from the bell jar

    Kathryn Williams explores the works and influences of Sylvia Plath
    How one man's day in high heels showed him that Cannes must change its 'no flats' policy

    One man's day in high heels

    ...showed him that Cannes must change its 'flats' policy
    Is a quiet crusade to reform executive pay bearing fruit?

    Is a quiet crusade to reform executive pay bearing fruit?

    Dominic Rossi of Fidelity says his pressure on business to control rewards is working. But why aren’t other fund managers helping?
    The King David Hotel gives precious work to Palestinians - unless peace talks are on

    King David Hotel: Palestinians not included

    The King David is special to Jerusalem. Nick Kochan checked in and discovered it has some special arrangements, too
    More people moving from Australia to New Zealand than in the other direction for first time in 24 years

    End of the Aussie brain drain

    More people moving from Australia to New Zealand than in the other direction for first time in 24 years
    Meditation is touted as a cure for mental instability but can it actually be bad for you?

    Can meditation be bad for you?

    Researching a mass murder, Dr Miguel Farias discovered that, far from bringing inner peace, meditation can leave devotees in pieces
    Eurovision 2015: Australians will be cheering on their first-ever entrant this Saturday

    Australia's first-ever Eurovision entrant

    Australia, a nation of kitsch-worshippers, has always loved the Eurovision Song Contest. Maggie Alderson says it'll fit in fine
    Letterman's final Late Show: Laughter, but no tears, as David takes his bow after 33 years

    Laughter, but no tears, as Letterman takes his bow after 33 years

    Veteran talkshow host steps down to plaudits from four presidents
    Ivor Novello Awards 2015: Hozier wins with anti-Catholic song 'Take Me To Church' as John Whittingdale leads praise for Black Sabbath

    Hozier's 'blasphemous' song takes Novello award

    Singer joins Ed Sheeran and Clean Bandit in celebration of the best in British and Irish music
    Tequila gold rush: The spirit has gone from a cheap shot to a multi-billion pound product

    Join the tequila gold rush

    The spirit has gone from a cheap shot to a multi-billion pound product
    12 best statement wallpapers

    12 best statement wallpapers

    Make an impact and transform a room with a conversation-starting pattern
    Paul Scholes column: Does David De Gea really want to leave Manchester United to fight it out for the No 1 spot at Real Madrid?

    Paul Scholes column

    Does David De Gea really want to leave Manchester United to fight it out for the No 1 spot at Real Madrid?