5 ms·
Answer to a 150-Year-Old Math Conundrum Brings More Mystery
- selimthegrim 11y agoIIRC Keevash used to teach at Caltech and was Rick Wilson's colleague.
- not_with_retard 11y agoI can't even read the article because of that floating sidebar on the right-hand side.
- mturmon 11y agoSometimes 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 11y agoWhen 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 11y agoFrom 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 11y agoAt 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
- thaumasiotes 11y agoThe famous proof that the primes are infinite is a nonconstructive existence proof. And weirdly, it proceeds entirely by trying to construct a new prime. It just fails to do so (well, sort of) while still invalidating the idea of an upper bound.
- darkmighty 11y agoMight one say it's a constructive proof of the non-existence of a finite group of primes?
- thaumasiotes 11y agoYou can't have a constructive non-existence proof. What would it mean to construct something that doesn't exist?
- OscarCunningham 11y agoIt is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you reach a prime. And so when you consider all the parts of the proof you find that you have in fact constructed another prime.
- beagle3 11y 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#History https://en.wikipedia.org/wiki/Low-density_parity-check_code#...
- darkmighty 11y agoLarge 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).
- mturmon 11y agoI 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 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 http://www.ces.clemson.edu/~keyj/psfiles/booktoc.html, and the follow-up article http://www.ces.clemson.edu/~keyj/Key/dccupdateb.pdf http://www.ces.clemson.edu/~keyj/Key/dccupdateb.pdf, especially chapter 7.
- ColinWright 11y agoNon-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 11y agoYou can see an old puzzle I concocted based on block designs and projective planes here: http://cromwellian.blogspot.com/search/label/puzzles http://cromwellian.blogspot.com/search/label/puzzles Solution at top, so scroll to the bottom first. There are practical applications. :)
- schoen 11y agoThis 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 11y agoWhile 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.
- deleted 11y ago[deleted]