Answer to a 150-Year-Old Math Conundrum Brings More Mystery

http://www.wired.com/2015/06/answer-150-year-old-math-conundrum-brings-mystery/

by prostoalex • 11 years ago

148 33 11 years ago

mturmon3• 11 years ago

Sometimes my instinct is to scoff at the practical value of asymptotic existence results like this, but there's a quote in the article that provides a good counterpoint:

Keevash’s result will shift the mindset of mathematicians who are trying to find designs, Colbourn said. “Before, it wasn’t clear whether the focus should be on constructing designs or proving they don’t exist,” he said. “Now at least we know the effort should focus on constructing them.”

I only glanced at the paper, but perhaps this is analogous to Shannon's original proof of existence of codes meeting channel capacity -- which was also a non-constructive, asymptotic result.

That pointed the way for people to start working out channel codes, and after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.

furyofantares• 11 years ago

When doing math proof exercises as an undergrad I found problems of the form "Prove X" or "Disprove X" to be much easier than "Prove or disprove X" despite no noticeable difference in the difficulty of understanding the proof once constructed. I felt that prove/disprove was significantly more than twice as hard, actually. I thought I could trick myself into making it between 1 and 2 times as hard by attempting to force myself to believe the problem was one form or the other for set periods of time, and that did seem to help some, but not nearly to the extent I had hoped.

SilasX• 11 years ago

From my memory, they used this as a way to balance proof difficulty: for easier proofs, it would be a "prove of disprove", but for harder ones, they would reveal which one you can prove.

reagency• 11 years ago

At undergrad, a successful technique is to assume X exists and try to construct it. As you do so, you either find one or reach a contradiction to every possible class of structure.

Nonconstructive proofs of existence in rare, outside of logic classes. Most branches of undergrad math aren't interested in mere existence

beagle3• 11 years ago

after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.

But LDPC codes were shown by Gallager in 1963[0], and while they were not feasible to implement at the time, saying that the theory waited for turbo code discovery is wrong.

[0] https://en.wikipedia.org/wiki/Low-density_parity-check_code#...

darkmighty2• 11 years ago

Large good codes were always known to exist, the crux from when Shannon published his work (I believe) was to actually get good codes that are computationally viable (else you could even use Shannon's random code). LDPC codes were rediscovered only because decoding became viable due increased computational power (w.r.t the 60's) and, crucially, discovery of iterative decoding for them (belief propagation etc).

mturmon3• 11 years ago

I disagree completely. There is a theory of finding practical codes, and that theory took decades to elucidate.

A practical code must be not just computationally tractable, but also, the channel capacity must be approached quickly as block length increases, and decoding must not blow up for large block lengths. As you can read in Gallager's thesis, this was not known for LDPCs back in 1960.

Even in the mid-90s, when the connection between LDPC's and turbocodes became understood, it took more theoretical work to understand why some codes (those having short cycles) had poor performance -- because decoding them was fragile. (See the excellent http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf).

Similarly to the OP, there may be multiple ways to find designs, but some of the methods or the resulting designs may be clumsy or inefficient.

Incidentally, it turns out there is a deep connection between coding (i.e., the present analogy) and designs (the OP), see http://www.ces.clemson.edu/~keyj/psfiles/booktoc.html, and the follow-up article http://www.ces.clemson.edu/~keyj/Key/dccupdateb.pdf, especially chapter 7.

ColinWright4• 11 years ago

Non-constructive existence proofs are critical in random graph theory, and that in turn is producing all sorts of useful results about what's possible, what's not possible, and what might be possible but it's likely to be hard.

A specific example, I'm working with some people on producing instances of G3C that may lead to a new form of PKC that is expected to be securely based on a known NPC problem. Non- constructive asymptotic existence proofs are critical to proving these instances are difficult.

cromwellian• 11 years ago

You can see an old puzzle I concocted based on block designs and projective planes here: http://cromwellian.blogspot.com/search/label/puzzles

Solution at top, so scroll to the bottom first.

There are practical applications. :)

schoen• 11 years ago

This reads something like a classic Martin Gardner column -- clear, tantalizing, and presenting a highly technical math topic helpfully for non-specialists. Way to go, Erica Klarreich.

thret• 11 years ago

While it is trivial to find a single solution to the problem presented at the end of this article, does anyone have a nice general one? Please share if so.

selimthegrim• 11 years ago

IIRC Keevash used to teach at Caltech and was Rick Wilson's colleague.

Answer to a 150-Year-Old Math Conundrum Brings More Mystery

Related Stories