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

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 …

#### Test? No problem

The entire proof is reduced to 1 nm depressions on the head of a pin which is dipped in hemlock and inserted in each author of the proof. If they live the proof is true if not well you get the picture.

A truly old English test is best.

#### Re: Test? No problem

The head of a pin is approx 1mm x 1mm. Assuming each bit is 1nm wide one can fit 10^12 bits on the head of a pin, so theoretically you can fit about 116 GB of data on the head of a pin. Each bit would be about 7 atoms across.

Your test is technically possible, carry on.

#### Re: Test? No problem

The head of a pin is pretty blunt. I can only assume you've no plans to pierce the authors' skin. Which orifice are you inserting it into?

#### Re: Test? No problem

Yes, but how many of those atoms could dance on the head of that pin?

#### Re: Test? No problem

There are two authors. If one lives and the other experiences the alternative outcome, is the proof true or not?

#### Re: Test? No problem

If one lives, he gets the pin once more. If he lives again, he got it out 2 out of 3, so the proof is false. Or the other way around.

#### Yes indeedy

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

I'm sure I had some paracetamol around here somewhere...

#### Re: Yes indeedy

I'm a mathematician, but this is based on a quick reading of this article alone so may be complete rubbish:

Imagine an endless list of random pluses and minuses.

Take any section of that list, or say every other symbol, or whatever kind of pattern you like from it. This gives you another list of pluses or minuses that you've plucked from the original list.

Work out whether you have more pluses than minuses in that or the other way around (or maybe an even number of both?). The difference is called the "discrepancy". A discrepancy of zero means there's the same number of pluses and minuses.

Using your (carefully-chosen) shorter list, and the discrepancy, you could then tell whether, for example, most of the pluses are in the beginning of your original list, or whether your list alternates between pluses and minuses, or whether it has a long run of pluses followed by a short run of minuses or whatever pattern you're looking for, just by looking at your short list extracted by a certain clever pattern. You can tell things about the infinite list just by carefully choosing the rule you use to extract the shorter list.

To translate the sentence: "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."

What I think he's saying is, you can always find a smaller list inside that infinite list that - if you choose it carefully - has a discrepancy (i.e. more pluses or minuses) bigger than the original infinite list. So you could always "fudge" the numbers by misrepresenting the larger list with a carefully-chosen pattern.

But, to be honest, it's not entirely clear and probably a LOT more complicated than even the article makes out.

And I'd be hard-pushed to come up with something practical out of it (though I'm sure there would be - this is the sort of maths that sits behind things like coding theory and, thus, sending messages, compression, error-correction, RAID, etc.)

#### Re: Yes indeedy

My understanding is that you can't pick any old pattern. It has to be every number, or every second number, or every third, etc. But that's just from Wikipedia.

#### Re: Yes indeedy

Suppose my finite sequence is the first 10 numbers in the list, and I pick 11.

Dammit, now I'm going to have to read this silly paper or I won't get any sleep.

#### Re: Yes indeedy

>>*"My understanding is that you can't pick any old pattern. It has to be every number, or every second number, or every third, etc. But that's just from Wikipedia."*

I think that's the classic version of the problem and is good because it is illustrative. But in theory the problem should apply to ANY pattern you come up with, so long as that pattern does not depend on foreknowledge of the numbers. I mean however complex your criteria for selection, there ought to be a subset that has greater discrepancy than it in an infinite sequence. No?

#### Re: Yes indeedy

Perhaps I don't understand it either.

Given some finite subsequence, there is an upper bound on its sum. That is, if the sequence selected happened to be a run of all '+', the sum will be equal to the length of that subsequence. It can't be bigger.

Now, given the original infinite subsequence, its sum is determined by probability. The most probable sum is zero, but there is some probability that it is greater (or less). And given most probability distributions (that I am familiar with), they approach but never reach a probability of 0 at a sum of +/- infinity. So there is a non-zero probability that there is a sequence sum larger than any bounded value that I can think of.

Or there's something about infinite series and probabilities that I'm missing.

#### Re: Yes indeedy

I think what's in Wikipedia is more likely to be correct, as it makes enough sense that I can understand exactly what it means. And it seems like such a deceptively simple problem that it's surprising a proof, not of the theorem, but only that the discrepancy must be bigger than 2, not any number you care to name, takes 13 gigabytes.

#### Re: Yes indeedy

Reading the Wikipedia definition of the problem seems to limit the scope a bit. The idea is for any sequence, there should be some values d, k and C, such that the summation of every dth element in the list from the first k elements in the list would yield a number (discrepancy) greater than C.

Neither of the definitions provide any limits on the type of infinite +1/-1 sequence, which would make the problem trivially false: with a sequence of all -1s, it would never be possible to create a positive discrepancy at all. Alternatively, a infinite sequence of "+1, -1" would never yield a discrepancy greater than 1.

As such, it's likely that the problem is more concerned with random sequences or at least sequences with an infinite number of +1s and -1s. Then the problem starts to look like a simple application of the statistical law of large numbers. For which we would conclude that, yes, for every sequence containing an infinite number of +1s, it must be possible to select every dth element from the first k, such that any given value C could be exceeded. More over, it must also be possible to find such a string given a fixed d, because any randomly chosen subsequence of a random sequence is itself a random sequence. Then all that's left is to find a k (> d*C) that sums to C+1, which would be a simple linear search through the infinite sequence. Of course, having invoked the law of large numbers, this can't be considered a formal proof. Trying to come up with a mathematical proof feels like looking at the proofs for infinite series in general, they're interesting, but all kinda weird.

Alternatively, Wikipedia and the New Scientist may just suck at explaining all the details of the problem.

#### Re: Yes indeedy

>>*Neither of the definitions provide any limits on the type of infinite +1/-1 sequence, which would make the problem trivially false: with a sequence of all -1s, it would never be possible to create a positive discrepancy at all."*

That's not an arbitrary pattern. That's a case of looking at the data first and then constructing a pattern to fit. The pattern must be independent of the random sequence. So you choose, e.g. every third number, and then apply it to a random string. Not study the string and construct a pattern.

#### Re: Yes indeedy

*And I'd be hard-pushed to come up with something practical out of it (though I'm sure there would be - this is the sort of maths that sits behind things like coding theory and, thus, sending messages, compression, error-correction, RAID, etc.)*

My understanding is that discrepancy theory has applications similar to Ramsay theory - it tells you how much structure will inevitably arise in a random distribution (well, it really puts a lower bound on the amount of such "accidental" structure), so it's useful for things like deciding what threshold constitutes a probable signal (rather than noise that looks like a signal) and that sort of thing.

I've seen Ramsay theory applied to some machine-learning problems to help filter out false correlations, for example.

"Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s."

Yes, I do that quite often. Usually when SWMBO starts one of her ... characteristics.

#### The answer isn't 42?

This is the sort of corollary that comes out of the full proof.

For every infinite string it is possible to define a finite substring with a discrepancy of any size.

If the discrepancy is 42, you know you have found a substring which fits the problems of the Adams universe.

I'd suggest, if it isn't, and you still have a problem, that you try a substring of different size if the discrepancy is positive, and use a different pattern if it goes in the wrong direction or is near-zero.

#### Been an issue ever since the 4 colour theorem proof came out.

Computer generated so too big to test by hand.

Yes as a puzzle it sounds a bit pants but "satisfiability" and +1/-1 are the sort of phrases that crop up in minimal digital logic design and custom logic layout for minimum surface area (and hence cost) on a chip.

That has **very** practical applications.

#### Fortunes to be made.....

.... publishing this in book form next Christmas.

In the mean time, hire a few Chinese students to read through it, or send it to Private Eye for a review.

As the complexity of proposed mathematical proofs increases, the likelihood of humans being able to fully understand it falls. The chances of mistakes in the proof that are not picked up by the reviewers increases.

Thus, mathematical proof isn't absolute proof, but merely probable truth.

#### I thought we were past all that!

For a writeup of the discussion of "Mathematics by computer!! MY GOODNESS, WHAT IS THIS WORLD COMING TO", see Peter Woit blogpost and pointers therein.

#### maths

You write a story about UK mathematicians and then have the nerve to put "math" (whatever that is) in the tag line. No merkin nonsense here please

#### Proof by induction

This is effectively 'proof by induction', where you say (sort of): if it's true for this, it must be true for that, and I've just shown it for this, so it must be true for all that. It works if you dig deeper into it. Proof by induction can get messy because you have to show (sometimes laboriously) that it is true for a certain case or cases.

#### wikipedia download too big?

Um. What about zipping it up. lots of +1 and -1 sounds like it should zip (or rar, or bzip, or etc.) fairly well.

Or, does wikipedia allow .torrent files? What about wikileaks? Private data that's not being made public? sounds like a sort of fit...

Ways and means exist.

#### Re: wikipedia download too big?

Actually truly random binary data would not compress well at all.

#### Re: wikipedia download too big?

"lots of +1 and -1 sounds like it should zip (or rar, or bzip, or etc.) fairly well" - really not sure where you got the idea; if you think of +1/-1 in terms of good old binary 0/1, you should be well aware that while some of it zips quite well, others such sequences (like JPEGs, MP4s etc.) don't compress practically at all. It really depends on how random your sequence already is...

#### @ lurker

"Actually truly random binary data would not compress well at all."

But this isn't "truly random data". What happened is that *someone's* pr0n collection accidentally got put into the archive.

#### Where did they get the numbers?

Serious question - where did they get (how did they generate) this sequence of +1's and -1's ?

I.e. assuming that their proof works by empirical testing rather than induction (which raises its own questions), how did they prove that the sequence they analysed was random.

If this little bit of coverage reaches any of the people involved, I'd love a quick reply clarifying.

*(icon because that's me right now)*

#### Re: Where did they get the numbers?

Wow - a downvote for a maths question? Some people really take discussions here personally, don't they? Someone who didn't like my comments elsewhere, presumably, or they really hate Paris Hilton. :D

#### Re: Where did they get the numbers?

Empirical testing? As in run a test on a random selection of data and assume if it gives a decent p value then the hypothesis can be considered correct?

That sort of thing doesn't cut it as mathemetical proof.

It might be good enough for sciences less pure than maths (e.g. sociology, physics, all other sciences), but even a a statistical proof - the probability of this being wrong is 0 - isn't enough for a mathematician.

#### Re: Where did they get the numbers?

>>*"Empirical testing? As in run a test on a random selection of data and assume if it gives a decent p value then the hypothesis can be considered correct? That sort of thing doesn't cut it as mathemetical proof."*

Well I agree. But look up what a SAT attack is. Unless I've misunderstood the article, they ran a SAT algorithm solver on a sufficiently large data set and "proved" it statistically. Hence my question about the randomness of the source data. Even if one accepts a proof by demonstration rather than induction (which you do not and I am reluctant to do), that remains a potentially serious flaw in the proof.

I am not a mathematician, hence my asking the question.

#### Re: Where did they get the numbers?

That's not that serious a question, unless you haven't read the article. The theorem isn't about one particular sequence of -1s and +1s, it's about any and all possible such sequences. No matter how hard you try, you shouldn't be able to construct a series so cannily arranged that, if you're allowed to choose between the absolute values of the partial sums of the series itself, every 2nd, every 3rd, every 4th, and so on, you can't make that result as large as you wish.

#### I smell snake oil .....

When the lottery started, I knew a guy who was convinced he could predict the numbers after a few draws. He created a speadsheet with a list of draws lowest ball to highest. He then worked out the average for each column. He then worked out the deviation from the average for each ball, and then worked out an average of that. He then used those derived averages to generate a list of numbers which he then played.

I wonder what became of him ....

#### Re: I smell snake oil .....

As we've not read about an individual winning the lottery five times over, I'd say he's probably still playing with his spreadsheet!

#### Re: I smell snake oil .....

Nah, he's successfully worked out that the probability of his winning the lottery is a near certainty if he buys 5x10^12 lottery cards and is now just saving up to buy them.

#### Not a new problem...

Surely this is hardly new. When Kenneth Appel and Wolfgang Haken proved the four colour theorem in 1976, it was originally not accepted by mathematicians as the computer-assisted proof was far to large to be proof-read by human beings. it gained a sort of grudging acceptance.

However, I always thought the objection was flawed in principle. Firstly, it's possible to consider a computer program (and the hardware on which it runs) as a mathematical entity which, itself, is subject to inspection and being proof-read. There have even been attempts to produce mathematically provable programs (although that is only possible in principle for some sorts of programs) and, even processors - anybody remember VIPER? Of course, any proof-reading of a program, especially one which cannot be mathematically verified, is open to human error. However, that is also true of human proof-reading of mathematical proofs. The possibility is always there of a human error, especially for very complex proofs.

It's therefore true, in principle, that the body of mathematics is open to human errors, albeit not on the scale of complex computer programs. It is therefore a problem of scale, and not principle.

#### Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s.

Somewhere within that sequence is a subset of numbers that contains a picture of a cat that wants a cheeseburger.

#### Re: Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s.

Unfortunately, it only occurs "at infinity".

#### Re: Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s.

And somewhere in that sequence is every other picture you could possibly imagine and, indeed, every other finite sequence you could imagine including arbitrary long sequences of 1's and 0's, the complete text of Wikipedia, the answer to the ultimate problem of life, the universe and everything etc., etc. However I wonder whether you could specify a sub-sequence in the sense of the proof by specifying its content or properties rather than its position? Such content addressability is an everyday aspect of computing, I wonder how this would affect the proof and/or how such a strategy would be excluded?

#### Re: Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s.

*And somewhere in that sequence is every other picture you could possibly imagine and, indeed, every other finite sequence you could imagine including arbitrary long sequences of 1's and 0's*

This is a popular claim, but it's incorrect, or more precisely the conditions you've specified are not sufficient to make it correct.

Consider the infinite sequence defined by the following:

1. A random finite number > 1 of +1s

2. A -1

3. Go to 1

This is infinite and random: if you are looking at one element of the sequence, and it is a +1, you cannot predict the next element; and if it's a -1, you cannot predict the element after the next. But it never contains the subsequence {-1,-1} (or any longer subsequence of -1s).

"Random and infinite sequence" does not imply "contains every possible subsequence".

Now, insofar as this sequence has some (non-accidental) structure - subsequences of -1s are restricted in length - it is not *purely* random. But no one in this thread said "purely random". Further, no finite subsequence of this not-purely-random sequence can be proven to not be a subsequence of a purely-random infinite sequence: you can't tell by inspection that it has non-accidental structure, only by definition.

#### Empirical proofs are the best.

Especially when Alexi Sayle proved to Jean Paul Sartre that he did really exist by head butting him in the throat.

#### Re: Empirical proofs are the best.

I don't think that JPS ever was in doubt about that.

"Existentialism" is not about whether you exist or not.