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

Sport
sportSo, how closely were you paying attention during 2014?
Arts and Entertainment
Dennis speaks to his French teacher
tvThe Boy in the Dress, TV review
News
One father who couldn't get One Direction tickets for his daughters phoned in a fake bomb threat and served eight months in a federal prison
people... (and one very unlucky giraffe)
Arts and Entertainment
Joel Edgerton, John Turturro and Christian Bale in Exodus: Gods and Kings
film
PROMOTED VIDEO
Life and Style
ebookNow available in paperback
ebooks
ebookPart of The Independent’s new eBook series The Great Composers
News
i100
Arts and Entertainment
The Plaza Theatre in Atlanta, Georgia was one of the 300 US cinemas screening
filmTim Walker settles down to watch the controversial gross-out satire
Arts and Entertainment
Amy Adams and Christoph Waltz in Tim Burton's Big Eyes
film reviewThis is Tim Burton’s most intimate and subtle film for a decade
Life and Style
Mark's crab tarts are just the right size
food + drinkMark Hix cooks up some snacks that pack a punch
Arts and Entertainment
Jack O'Connell stars as Louis Zamperini in Angelina Jolie's Unbroken
film review... even if Jack O'Connell is excellent
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: Moodle Developer (PHP ,Linux, Apache, MySQL, Moodle)

    £35000 - £45000 per annum: Ashdown Group: Moodle Developer (PHP ,Linux, Apache...

    Recruitment Genius: Web Developer

    £17000 - £30000 per annum: Recruitment Genius: This is a fantastic opportunity...

    Recruitment Genius: Junior .NET Web Developer - Winform / MVC

    £21000 - £26000 per annum: Recruitment Genius: This Award-winning pharma softw...

    Recruitment Genius: Senior Java Developer

    £30000 - £45000 per annum: Recruitment Genius: A Senior Java Developer is requ...

    Day In a Page

    Aren’t you glad you didn’t say that? The worst wince-and-look-away quotes of the year

    Aren’t you glad you didn’t say that?

    The worst wince-and-look-away quotes of the year
    Hollande's vanity project is on a high-speed track to the middle of nowhere

    Vanity project on a high-speed track to nowhere

    France’s TGV network has become mired in controversy
    Sports Quiz of the Year

    Sports Quiz of the Year

    So, how closely were you paying attention during 2014?
    Alexander Armstrong on insulting Mary Berry, his love of 'Bargain Hunt', and life as a llama farmer

    Alexander Armstrong on insulting Mary Berry and his love of 'Bargain Hunt'

    From Armstrong and Miller to Pointless
    Sanchez helps Gunners hold on after Giroud's moment of madness

    Sanchez helps Gunners hold on

    Olivier Giroud's moment of madness nearly costs them
    A Christmas without hope: Fears grow in Gaza that the conflict with Israel will soon reignite

    Christmas without hope

    Gaza fears grow that conflict with Israel will soon reignite
    After 150 years, you can finally visit the grisliest museum in the country

    The 'Black Museum'

    After 150 years, you can finally visit Britain's grisliest museum
    No ho-ho-hos with Nick Frost's badass Santa

    No ho-ho-hos with Nick Frost's badass Santa

    Doctor Who Christmas Special TV review
    Chilly Christmas: Swimmers take festive dip for charity

    Chilly Christmas

    Swimmers dive into freezing British waters for charity
    Veterans' hostel 'overwhelmed by kindness' for festive dinner

    Homeless Veterans appeal

    In 2010, Sgt Gary Jamieson stepped on an IED in Afghanistan and lost his legs and an arm. He reveals what, and who, helped him to make a remarkable recovery
    Isis in Iraq: Yazidi girls killing themselves to escape rape and imprisonment by militants

    'Jilan killed herself in the bathroom. She cut her wrists and hanged herself'

    Yazidi girls killing themselves to escape rape and imprisonment
    Ed Balls interview: 'If I think about the deficit when I'm playing the piano, it all goes wrong'

    Ed Balls interview

    'If I think about the deficit when I'm playing the piano, it all goes wrong'
    He's behind you, dude!

    US stars in UK panto

    From David Hasselhoff to Jerry Hall
    Grace Dent's Christmas Quiz: What are you – a festive curmudgeon or top of the tree?

    Grace Dent's Christmas Quiz

    What are you – a festive curmudgeon or top of the tree?
    Nasa planning to build cloud cities in airships above Venus

    Nasa planning to build cloud cities in airships above Venus

    Planet’s surface is inhospitable to humans but 30 miles above it is almost perfect