6 ms·

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 coun

by mturmon 11y 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 11y 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 11y 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 11y 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
  - thaumasiotes 11y ago
    The 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 ago
      Might one say it's a constructive proof of the non-existence of a finite group of primes?
      - thaumasiotes 11y ago
        You can't have a constructive non-existence proof. What would it mean to construct something that doesn't exist?
    - OscarCunningham 11y ago
      It 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.
      - thaumasiotes 11y ago
        I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
        ColinWright 11y ago
        There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
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 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).
- mturmon 11y 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 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 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.

by mturmon 11y ago

furyofantares 11y 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 11y 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 11y 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
- thaumasiotes 11y ago
  The 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 ago
    Might one say it's a constructive proof of the non-existence of a finite group of primes?
    - thaumasiotes 11y ago
      You can't have a constructive non-existence proof. What would it mean to construct something that doesn't exist?
  - OscarCunningham 11y ago
    It 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.
    - thaumasiotes 11y ago
      I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
      - ColinWright 11y ago
        There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.

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 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).
mturmon 11y 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 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 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.