4 ms·
The proof is not too bad in Lean4. I'm nothing special and I've got it down to 9 lines. But, maybe that is considered pretty tedious vs. what expectations one m
by drhodes 2y ago
The proof is not too bad in Lean4. I'm nothing special and I've got it down to 9 lines. But, maybe that is considered pretty tedious vs. what expectations one might have. In any case, it is an exercise in Heather MacBeth's free book: The Mechanics of Proof,
https://hrmacbeth.github.io/math2001/04_Proofs_with_Structure_II.html#id32 https://hrmacbeth.github.io/math2001/04_Proofs_with_Structur...
btw, that book is a lot of fun to work through.
- mathgradthrow 2y agoThe obvious proof term for isprime p is exponential compared to the size of p. The AKS proof term is polynomial, but still very bad.
- mathgradthrow 2y agohttps://en.m.wikipedia.org/wiki/Primality_certificate https://en.m.wikipedia.org/wiki/Primality_certificate