4 ms·

Interestingly, these attempts are about the same as what pops up when I try to remember the proof: - It's a proof by contradiction - The key step is in taking

Interestingly, these attempts are about the same as what pops up when I try to remember the proof: - It's a proof by contradiction - The key step is in taking the finite list of primes, multiplying them together, and adding 1 I then try to flesh out the details, it might take a second to realize that this new number is also prime, and then a few moments more to remember the exact rationale why. Along the way the proof lives in a kind of superposition where I'm not clear on the exact details. The "proofs" you gave here seem to be serializations of a similar superposition! GPT-3 seems to remember the proof about as well as I do, but it's missing the final sanity check which tweaks the proof until all the pieces correctly fit together. In this case, you seem to be performing a version of this sanity check by running the prompt multiple times until a correct answer comes out. I wonder if it's possible to prove something more obscure using a similar process: GPT-3 comes up with ideas and the human sanity checks.

ctoth 5y ago
I believe this recent paper demonstrates a method for allowing these large language models to perform this "sanity check" automatically[0]. [0]: Self-Consistency Improves Chain of Thought Reasoning in Language Models https://arxiv.org/abs/2203.11171 https://arxiv.org/abs/2203.11171
Banana699 5y ago
>this new number is also prime Not necessarily, it might be composite, but in this case one of it's prime factors will necessarily not lie in the supposed list of primes, therefore also a contradiction. The first counter example to "If L := {P0,P1,..,Pn} is a list of primes, then prod(L)+1 is prime" is {2,3,5,7,11,13}, their product is 30030, and 30031 is a composite of 2 primes, none of which are in the list.
- falcor84 5y ago
  It's somewhat silly semantics, but I believe it is a valid deductive step on the way to the contradiction - if the number is not divisible by any other prime, then it must be a new prime, ⊥.
  - ivegotnoaccount 5y ago
    The issue is that it is not divisible by any other prime *from the list*. The two cases (prime or composite) must be handled separately since they do not use the same logic to infer there is one more prime. For instance, 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509.
    - ravi-delia 5y ago
      But to get the contradiction, you assume a finite number of primes. As each of them does not divide the new one, the new one is not divisible by a prime. It seems like your method is some kind of induction? Which probably gets a little closer to the "reason" for it, but isn't the standard proof I've seen.
      - Tainnor 5y ago
        These are really just logically equivalent ways of getting at the same result. You can either prove the statement "for every finite list of primes, there exists a prime not in this list" directly from the axioms of arithmetic, or you can add its negation "there are finitely many primes" as an assumption, derive a contradiction, and therefore conclude the negation of that new assumption. Nothing substantially changes about the proof either way.
        ravi-delia 5y ago
        I mean, yeah? It's still true you don't need to prove the composite case separately if you structure it a little different. Plus the original comment was clearly angling for the contradiction, so pivoting without warning to induction is just misleading
        Tainnor 5y ago
        There is no induction involved (I mean, yes, for some of the lemmas about divisibility, probably you'll need induction, but not for the main proof).
actually_a_dog 5y ago
The thing I find interesting about the proof attempts in the GP comment is that they very much resemble what you'd expect to see coming from a hypothetical somewhat confused undergrad. I think that ties into what you say about the proof living "in a kind of superposition where I'm not clear on the exact details," because that's where I imagine said hypothetical confused undergrad's understanding being.
- mr_toad 5y ago
  It’s imitation rather than true understanding. Still, even imitation is a remarkable ability for a computer.
mannykannot 5y ago
I feel that calling the final step a "sanity check" underrates its significance. To me, it implies that you essentially have the proof, and you are just looking for confirmation that it is sound and whether there are some edge cases to finish off. In contrast, I would say that it is the first point at which you understand how the half-remembered fragments of the proof can be put together to make an unassailable case for the proposition. Until then, it is as if you are groping around in the dark, trying to remember what the room looked like when the light was on (I know what it's like, as I have frequently been in that situation!) These answers are the sort one might expect from something that has a vast memory for what it has seen before, and an ability to draw huge networks of syntax-level associations and generalizations from all that text, but is not so strong on semantic associations and generalizations that are not manifest at the level of syntax. What surprises me is how successful that has been.

ctoth 5y ago

I believe this recent paper demonstrates a method for allowing these large language models to perform this "sanity check" automatically[0]. [0]: Self-Consistency Improves Chain of Thought Reasoning in Language Models https://arxiv.org/abs/2203.11171 https://arxiv.org/abs/2203.11171

Banana699 5y ago

>this new number is also prime Not necessarily, it might be composite, but in this case one of it's prime factors will necessarily not lie in the supposed list of primes, therefore also a contradiction. The first counter example to "If L := {P0,P1,..,Pn} is a list of primes, then prod(L)+1 is prime" is {2,3,5,7,11,13}, their product is 30030, and 30031 is a composite of 2 primes, none of which are in the list.

falcor84 5y ago
It's somewhat silly semantics, but I believe it is a valid deductive step on the way to the contradiction - if the number is not divisible by any other prime, then it must be a new prime, ⊥.
- ivegotnoaccount 5y ago
  The issue is that it is not divisible by any other prime *from the list*. The two cases (prime or composite) must be handled separately since they do not use the same logic to infer there is one more prime. For instance, 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509.
  - ravi-delia 5y ago
    But to get the contradiction, you assume a finite number of primes. As each of them does not divide the new one, the new one is not divisible by a prime. It seems like your method is some kind of induction? Which probably gets a little closer to the "reason" for it, but isn't the standard proof I've seen.
    - Tainnor 5y ago
      These are really just logically equivalent ways of getting at the same result. You can either prove the statement "for every finite list of primes, there exists a prime not in this list" directly from the axioms of arithmetic, or you can add its negation "there are finitely many primes" as an assumption, derive a contradiction, and therefore conclude the negation of that new assumption. Nothing substantially changes about the proof either way.
      - ravi-delia 5y ago
        I mean, yeah? It's still true you don't need to prove the composite case separately if you structure it a little different. Plus the original comment was clearly angling for the contradiction, so pivoting without warning to induction is just misleading
        Tainnor 5y ago
        There is no induction involved (I mean, yes, for some of the lemmas about divisibility, probably you'll need induction, but not for the main proof).

actually_a_dog 5y ago

The thing I find interesting about the proof attempts in the GP comment is that they very much resemble what you'd expect to see coming from a hypothetical somewhat confused undergrad. I think that ties into what you say about the proof living "in a kind of superposition where I'm not clear on the exact details," because that's where I imagine said hypothetical confused undergrad's understanding being.

mr_toad 5y ago
It’s imitation rather than true understanding. Still, even imitation is a remarkable ability for a computer.

mannykannot 5y ago

I feel that calling the final step a "sanity check" underrates its significance. To me, it implies that you essentially have the proof, and you are just looking for confirmation that it is sound and whether there are some edge cases to finish off. In contrast, I would say that it is the first point at which you understand how the half-remembered fragments of the proof can be put together to make an unassailable case for the proposition. Until then, it is as if you are groping around in the dark, trying to remember what the room looked like when the light was on (I know what it's like, as I have frequently been in that situation!) These answers are the sort one might expect from something that has a vast memory for what it has seen before, and an ability to draw huge networks of syntax-level associations and generalizations from all that text, but is not so strong on semantic associations and generalizations that are not manifest at the level of syntax. What surprises me is how successful that has been.