We really don't have a good terminology for distinguishing between efficient constructive proofs (those corresponding to efficient algorithms) and inefficient ones...
We really don't have a good terminology for distinguishing between efficient constructive proofs (those corresponding to efficient algorithms) and inefficient ones...
This is thus more a property of the theorem than a distinctive property of the proof. But, yes, the theorem is valid even in intuitionistic mathematics.
This is not a very helpful way to think about these things though. What I meant is that all principles used in this proof are constructive. You could, for example, literally translate this proof into a proof in type theory.
In some sense, this is just what you were saying, but my point is, this phenomenon ends up arising inevitably from the nature of the proposition being proven itself, and isn't surprising or distinctive for any particular proof of it (even if phrased ostensibly classically, such a proof might well be regarded as implicitly constructive regardless).
You could rewrite this proof using some results from point set topology which typically require choice (the article even gives an outline on how to do this, weirdly enough). This rewritten proof would be non-constructive in a more precise sense, in that you couldn't translate it step-by-step.
So there is no surprise that this particular statement's proof is constructive, given that it is classically provable at all [again, technically, I am referring to classical provability in PA, but it would be shocking if Fermat's old proof, or any other anyone bothered with for a statement of this sort, had somehow relied on anything beyond PA]. For other more quantifier-complex classical theorems, it would be of more note to observe whether a particular proof could be made constructive (in the mere sense of intuitionistic mathematics) or not, but for this one, there's nothing to it.
Anyway, I think I'm arguing pedantically about something there's no reason for me to argue about at all. Sorry about that! I think we're both in agreement that this is great, its constructiveness is great, math is great. Hooray!
You are arguing that this usage of "constructive" is basically meaningless for statements like this. It could only make a difference for artificial examples or artificially complicated proofs. This is definitely true.
To be honest, I shouldn't have brought this up in the first place. I know what the author meant by claiming the proof is non-constructive (it doesn't give a formula for computing x,y such that x^2 + y^2 = p), and this is the idiomatic usage of the word non-constructive for this particular field. It's just different from the rest of the world, but that's nothing new.
"Note that the proof is not constructive: it does not give a method to actually find the representation of p as a sum of two squares"
We do: the complexity classes P and NP. Ok, technically this is a polynomial time decidable language (does there exist etc. etc.), so perhaps consider FP and FNP (the function variants of P & NP).
I'm only nitpicking here, because I'm seeing this a lot...