Feeds

Mathematicians spark debate with 13 GB proof for Erdős problem

Try fitting THAT in the margins, math wonks

5 things you didn’t know about cloud backup

When Pierre de Fermat famously complained that he didn't have space to write the proof of his famous “Fermat's Last Theorem”, he only ran out of space of the margin of a book. Now, a pair of mathematicians at the University of Liverpool in the UK have produced a 13GB proof that's sparked a debate about how to test it.

The mathematicians, Alexei Lisitsa and Boris Konev, were looking at what's called the “Erdős discrepancy problem” (it's appropriate to point to Wikipedia, for reasons you'll catch in a minute).

New Scientist describes the problem like this:

“Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s. Erdős was fascinated by the extent to which such sequences contain internal patterns. One way to measure that is to cut the infinite sequence off at a certain point, and then create finite sub-sequences within that part of the sequence, such as considering only every third number or every fourth. Adding up the numbers in a sub-sequence gives a figure called the discrepancy, which acts as a measure of the structure of the sub-sequence and in turn the infinite sequence, as compared with a uniform ideal.”

For any sequence, Paul Erdős believed, you could find a finite sub-sequence that summed to a number bigger than any than you could choose – but he couldn't prove it.

In this Arxiv paper, the University of Liverpool mathematicians set a computer onto the problem in what they call “a SAT attack” using a Boolean Satisfiability (SAT) solver. They believe they've produced a proof of the Erdős discrepancy problem, but there's a problem.

After six hours, the machine they used – an Intel i5-2500 running at 3.3 GHz with 16 GB of RAM – produced what they offer as a proof, but it's inconveniently large, at 13 GB. A complete Wikipedia (see, I told you it was relevant) download is only 10 GB.

As New Scientist points out, that raises a different problem: how can humans ever check the proof. However, at least one mathematician NS spoke to said “no problem”: after all, other computers can always be deployed to test the proof. ®

Build a business case: developing custom apps

More from The Register

next story
Vulture 2 takes a battering in 100km/h test run
Still in one piece, but we're going to need MORE POWER
Boffins ID freakish spine-smothered prehistoric critter: The CLAW gave it away
Bizarre-looking creature actually related to velvet worms
TRIANGULAR orbits will help Rosetta to get up close with Comet 67P
Probe will be just 10km from Space Duck in October
CRR-CRRRK, beep, beep: Mars space truck backs out of slippery sand trap
Curiosity finds new drilling target after course correction
ANU boffins demo 'tractor beam' in water
The current state of the art, apparently
China to test recoverable moon orbiter
I'll have some rocks and a moon cheese pizza please, home delivery
What does a flashmob of 1,024 robots look like? Just like this
Sorry, Harvard, did you say kilobots or KILLER BOTS?
NASA's rock'n'roll shock: ROLLING STONE FOUND ON MARS
No sign of Ziggy Stardust and his band
Why your mum was WRONG about whiffy tattooed people
They're a future source of RENEWABLE ENERGY
prev story

Whitepapers

Endpoint data privacy in the cloud is easier than you think
Innovations in encryption and storage resolve issues of data privacy and key requirements for companies to look for in a solution.
Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Top 8 considerations to enable and simplify mobility
In this whitepaper learn how to successfully add mobile capabilities simply and cost effectively.
Solving today's distributed Big Data backup challenges
Enable IT efficiency and allow a firm to access and reuse corporate information for competitive advantage, ultimately changing business outcomes.
Reg Reader Research: SaaS based Email and Office Productivity Tools
Read this Reg reader report which provides advice and guidance for SMBs towards the use of SaaS based email and Office productivity tools.