Re: fundamental theorem of algebra

Re: fundamental theorem of algebra

[Vaughan Pratt]

John Baez wrote:

> I really doubt those authors were unaware of the topological proof
> of the fundamental theorem of calculus in 1987.  After all, it's

Right, both my claim and its premises needed a fair bit of tuning (as
with my recent question about the quasivariety "groups+free monoids" --
this is a good list to get corrective feedback from).  (But a neat piece
of historical research there, John.)

The issue seems to be coming down to Mike Barr's question, which if I
can paraphrase it without changing its intent, was, what is the proper
status of an appeal to the very plausible in a proof?   My suggestion in
my last message to Peter Freyd was that the prover should point out the
gap, its cause (lack of a simple proof), and its plausibility
notwithstanding.

This suggestion raises more questions than it answers.

1.  Is a proof with a gap more acceptable for expository purposes when
the bridgability of the gap is more plausible?  (The case in point being
an extreme example.)

2.  How is plausibility to be judged?  By consensus, or are there
objective criteria?

3.  It is certainly not necessary to prove A before B merely because B
depends on A; indeed one common-sense practice when proving a two-lemma
proof is to get the easier lemma out of the way first, even if it
depends on the harder one.  Is it kosher to truncate such a proof after
the first lemma (or in this case the final result), call it an
exposition, and point to the literature for the second lemma?

Regarding 3, the authors of the Britannica article seemed not to think
so, but perhaps this just reflects Garrett Birkhoff's attitude that "I
don't consider this algebra, but this doesn't mean that algebraists
can't use it" cited by Michael Artin when proving FTAlg in his 1991 book
"Algebra".  Who on this list considers the fundamental theorem of
algebra "not algebra"?

These questions are probably more appropriate for a philosophy of
mathematics list than this one.  What makes FTAlg such an interesting
case study for those with something at stake in such questions is that
the tensions here are so extreme.  The final result (FTAlg) is not at
all obvious, whereas the lemma it rests on, whether it be that |P(z)|
attains its minimum, or that circles around a hole don't retract, or the
intermediate value theorem, or the existence of a root for a real
polynomial of odd degree, seems self-evident.  Yet the one that is hard
to see is easy to prove, while the one that is easy to see is hard to prove.

If seeing is believing, what is proof?  In the real world, when
something is easy to see it is up to the opposition to demonstrate that
it is nonetheless false.  How did mathematics evolve to play by a
different rule book?

Vaughan Pratt

Re: fundamental theorem of algebra

[Michael Barr]

Perhaps the moral is not to bother with the Britannica.  Wikipedia has
several proofs including the winding number argument and the one I
outlined using the symmetric function argument.  Then a couple of analytic
ones.  Of course, Wiki has no size limitations.

Perhaps we have flogged this particular horse enough.

On Sun, 2 Apr 2006, Vaughan Pratt wrote:

> Fred E.J. Linton wrote:
> > First, in Birkhoff & Mac Lane (my own undergraduate algebra text),
> > Section 3 of Chapter V of the 1953 ("revised") edition offers a
> > proof along winding number lines on pp. 107-109.
>
> Thanks, Fred, I wish I'd noticed that before.  I have the sixth printing
> (1948) of the 1941 edition, which says, "Many proofs...are known; ...we
> have selected one whose non-algebraic part is *especially plausible
> intuitively*."  (My emphasis.)  Then they give the proof "I like".
>
> To administer one more lash to this dead horse, the wording in the
> Britannica article implies that the absence of an elementary algebraic
> argument was the reason for omission of a proof of FTAlg.  Whence the
> change of heart about arguments that are "especially plausible
> intuitively?"  If they're good enough for an algebra text they should be
> even more acceptable for an encyclopaedia article.
>
> Vaughan Pratt
>
>

Re: fundamental theorem of algebra

[John Baez]

Vaughan writes:

> However I've been reflecting on just what is behind the very uniform
> insistence on the distinction between an algebraic proof and an analytic
> one.  Since algebra is descended from analysis, it seems unkind for
> algebra to deny its parentage in this way.

I thought people knew how to add before they knew how to take limits.  :-)

> But I see now that this denial is logically necessary.  For consider the
> algebraic plane, the least algebraically closed subfield of the complex
> plane, consisting of the algebraic numbers.  The FTAlg is by definition
> true there, so it ought to be provable there.

Hmm.  How do you propose to show there *exists* an algebraically closed
subfield of the complex numbers?  I would do it using the fundamental
theorem of algebra - the usual one, for the complex numbers.  Unless
you have some other way, I don't understand how you hope to circumvent
the use of analysis by introducing such an entity.

Indeed, the usual proof that the real numbers contains a square root
of 2 uses the completeness of the real numbers, which also counts as
"analysis".

> It is ironic that a theorem of algebra about an algebraic domain that
> itself has no element of analysis to it, being just the algebraic
> closure of the rationals, a small and totally disconnected space, should
> require analysis, the parent of algebra, for its proof.

That the rational numbers has an algebraic closure is a purely algebraic
result, with no mention of topology in either the statement or proof.

That the complex numbers is algebraically closed is not an algebraic result:
it has topology built into the statement, and also the proof(s).

That the algebraic closure of the rationals embeds in the complex
numbers has topology in the statement - and I bet also in every proof.

Best,
jb

Re: fundamental theorem of algebra

[Vaughan Pratt]

Fred E.J. Linton wrote:
> First, in Birkhoff & Mac Lane (my own undergraduate algebra text),
> Section 3 of Chapter V of the 1953 ("revised") edition offers a
> proof along winding number lines on pp. 107-109.

Thanks, Fred, I wish I'd noticed that before.  I have the sixth printing
(1948) of the 1941 edition, which says, "Many proofs...are known; ...we
have selected one whose non-algebraic part is *especially plausible
intuitively*."  (My emphasis.)  Then they give the proof "I like".

To administer one more lash to this dead horse, the wording in the
Britannica article implies that the absence of an elementary algebraic
argument was the reason for omission of a proof of FTAlg.  Whence the
change of heart about arguments that are "especially plausible
intuitively?"  If they're good enough for an algebra text they should be
even more acceptable for an encyclopaedia article.

Vaughan Pratt

Re: fundamental theorem of algebra

[Fred E.J. Linton]

For the bookworms among the readers of this FToA thread, let me
offer four older references to undergraduate-accessible expositions
of proofs along the lines already mentioned:

First, in Birkhoff & Mac Lane (my own undergraduate algebra text),
Section 3 of Chapter V of the 1953 ("revised") edition offers a
proof along winding number lines on pp. 107-109.

Next, in the 1975 MIR English edition of Kurosh's Higher Algebra
(described as the "second printing"), section 23 of Chapter 5 offers a
proof relying on the D'Alembert Lemma (on pp. 142-151).

In the same Kurosh volume, moreover, section 55 of Chapter 11 offers a
proof along symmetric function lines on pp. 337-340.

Finally, one may find the Artinian proof in the real-closed fields
section of van der Waerden's pre-WWII classic, Modern[e] Algebra.

I refrain from citing other textbooks, and I remark that numberings
(of pages, sections, chapters) may differ in other editions.

Cheers,

-- Fred

Prof. Peter Johnstone wrote:
> On Thu, 30 Mar 2006, Vaughan Pratt wrote:
>
>
>>Regarding 3, the authors of the Britannica article seemed not to think
>>so, but perhaps this just reflects Garrett Birkhoff's attitude that "I
>>don't consider this algebra, but this doesn't mean that algebraists
>>can't use it" cited by Michael Artin when proving FTAlg in his 1991 book
>>"Algebra".  Who on this list considers the fundamental theorem of
>>algebra "not algebra"?
>>
>
> The theorem is algebra, but its proof isn't: any proof has to involve
> some topological input (though that can be reduced to the Intermediate
> Value Theorem). Vaughan seems to have a problem with the phrase
> "elementary algebraic proof": of course, not all elementary proofs
> are algebraic (and not all algebraic proofs are elementary), and it is
> the word "algebraic" that matters here.
>
> Incidentally, I used that Birkhoff quote in the Introduction to
> "Stone Spaces" (1982). Did Mike Artin get it from me, or did he
> discover it independently?
>
> Even more incidentally, the first published proof of the Fundamental
> Theorem is not by Gauss. It appears in the only mathematical paper
> (in Phil. Trans. Roy. Soc. volume 88, 1798) of the Reverend James
> Wood, who was then a Fellow (and subsequently Master) of St John's
> College, Cambridge. (His other publications were all theological
> -- he was a Doctor of Divinity.) Wood's argument is essentially the
> same as Gauss's second proof (1816); by modern standards, what he
> writes in the paper doesn't constitute a rigorous proof, but (to
> quote the late Frank Smithies) "anyone reading Wood's paper must
> end up with the conviction that there is a proof somewhere there".
>
> Peter Johnstone
>
>
>

Re: fundamental theorem of algebra

[Vaughan Pratt]

Even in my original posting starting this thread I acknowledged that
contractibility of the circle was not elementary:

> Except, that is, for the theorem that a loop wound d times around the
> hole in the punctured plane cannot be continuously retracted to a point,
> which was tacitly smuggled in there.   But that statement is less
> intimidating than anything based on holomorphic functions.

I haven't at any time claimed that it was not necessary to prove this,
nor that the proof was easy.

What I have been claiming is that the result has a certain self-evident
quality to it that, it seemed to me, qualified the argument as at least
sufficiently "morally elementary" as to qualify it for inclusion in the
Britannic article on algebra.  How could the definitive encyclopedia
article on algebra not give at least a hint as to why that subject's
fundamental theorem was true?

However I've been reflecting on just what is behind the very uniform
insistence on the distinction between an algebraic proof and an analytic
one.  Since algebra is descended from analysis, it seems unkind for
algebra to deny its parentage in this way.

But I see now that this denial is logically necessary.  For consider the
algebraic plane, the least algebraically closed subfield of the complex
plane, consisting of the algebraic numbers.  The FTAlg is by definition
true there, so it ought to be provable there.  One can carry out the
same proof, and it all goes through in the same way (using circles of
growing algebraic radius, all of which are dense in their complex
completion to a connected circle) right up to the last step when we
claim that the wildly growing loop that is the image of the tamely
growing circle must eventually collide with the origin, d times in fact
for a degree d polynomial.

And indeed it does, all d times, exactly as with the complex numbers,
and with the same roots (the coefficients of the polynomial necessarily
being algebraic in this domain).

But now analysis has nothing to do with it, since these circles and
their image loops while dense are totally disconnected.  For all we know
the origin could have missed the loop by going through any of its
uncountably many gaps.  Indeed the loop has measure zero, so the chances
  of the origin colliding with it even once are less than Buckley's.

But with aim that would be the envy of any sniper the origin hit the
loop with every one of its d shots.

And how do we know this?  Using analysis.  The consensus would seem to
be that there is no other way.  Logic alone cannot help.  If that's the
case, then without analysis there is no algebraic plane.  Without the
huge continuum to support it, that tiny countable set would not exist!

It is ironic that a theorem of algebra about an algebraic domain that
itself has no element of analysis to it, being just the algebraic
closure of the rationals, a small and totally disconnected space, should
require analysis, the parent of algebra, for its proof.

The fundamental theorem of algebra is like a student calling home for
more money.  It takes a continuum to raise an algebraic number.

Vaughan Pratt

Re: fundamental theorem of algebra

[jim stasheff]

Yet the one that is hard
to see is easy to prove, while the one that is easy to see is hard to
prove.

Ain't that the truth
or as Rene Thom once remarked about one of his assertions
Very easy to see, very had to prove

jim


Vaughan Pratt wrote:
[...]
>
> These questions are probably more appropriate for a philosophy of
> mathematics list than this one.  What makes FTAlg such an interesting
> case study for those with something at stake in such questions is that
> the tensions here are so extreme.  The final result (FTAlg) is not at
> all obvious, whereas the lemma it rests on, whether it be that |P(z)|
> attains its minimum, or that circles around a hole don't retract, or the
> intermediate value theorem, or the existence of a root for a real
> polynomial of odd degree, seems self-evident.  Yet the one that is hard
> to see is easy to prove, while the one that is easy to see is hard to
> prove.
>
> If seeing is believing, what is proof?  In the real world, when
> something is easy to see it is up to the opposition to demonstrate that
> it is nonetheless false.  How did mathematics evolve to play by a
> different rule book?
>
> Vaughan Pratt
>

re: fundamental theorem of algebra

[Michael Barr]

Let me reiterate this: There can in principle be no purely algebraic proof
of the FToA because the reals have no purely algebraic definition.
(Unless you define them as a real closed field of transcendence degree c,
but that leaves the FToA as a trivial consequence and cannot be what is
wanted.)  The proof I outlined, which someone showed me 45 years ago, uses
only the fact that R is a complete ordered field.  Given that that is the
analytic definition of R, it is impossible to avoid.  That fact is, of
course, at the heart of the fact that the circle is not contractible in a
punctured plane.

Incidentally, even constructivists (well even Errett Bishop, anyway) agree
that odd order real polynomials have a real root and that positive numbers
have square roots, since there are obvious constructions for these things.
Their real line is not complete (it is countable, but the missing numbers
are not constructible), but these roots are there anyway.

The argument I outlined is elementary, even if not especially easy.  First
you have to construct the reals, the least elementary part of the
argument.  Then comes the theorem on symmetric functions.  It is not a
deep result; it needs a careful proof, but a student can follow it without
knowing anything sophisticated.  The construction of a splitting field
(without getting into UFDs) is a bit tricky.  To adjoin a root to an
irreducible polynomial p of degree n, you start with a vector space whose
basis is called 1, u, u^2,..., u^{n-1} and define a multiplication, by
having p(u) = 0.  This is analogous to how you get from R to C.  Of
course, you use the division algorithm to show you get a field.

Michael

Re: fundamental theorem of algebra

[Prof. Peter Johnstone]

On Thu, 30 Mar 2006, Vaughan Pratt wrote:

> Regarding 3, the authors of the Britannica article seemed not to think
> so, but perhaps this just reflects Garrett Birkhoff's attitude that "I
> don't consider this algebra, but this doesn't mean that algebraists
> can't use it" cited by Michael Artin when proving FTAlg in his 1991 book
> "Algebra".  Who on this list considers the fundamental theorem of
> algebra "not algebra"?
>
The theorem is algebra, but its proof isn't: any proof has to involve
some topological input (though that can be reduced to the Intermediate
Value Theorem). Vaughan seems to have a problem with the phrase
"elementary algebraic proof": of course, not all elementary proofs
are algebraic (and not all algebraic proofs are elementary), and it is
the word "algebraic" that matters here.

Incidentally, I used that Birkhoff quote in the Introduction to
"Stone Spaces" (1982). Did Mike Artin get it from me, or did he
discover it independently?

Even more incidentally, the first published proof of the Fundamental
Theorem is not by Gauss. It appears in the only mathematical paper
(in Phil. Trans. Roy. Soc. volume 88, 1798) of the Reverend James
Wood, who was then a Fellow (and subsequently Master) of St John's
College, Cambridge. (His other publications were all theological
-- he was a Doctor of Divinity.) Wood's argument is essentially the
same as Gauss's second proof (1816); by modern standards, what he
writes in the paper doesn't constitute a rigorous proof, but (to
quote the late Frank Smithies) "anyone reading Wood's paper must
end up with the conviction that there is a proof somewhere there".

Peter Johnstone

re: fundamental theorem of algebra

[John Baez]

A couple of mistakes.  I wrote:

>I really doubt those authors were unaware of the topological proof
>of the fundamental theorem of calculus in 1987.

I meant "fundamental theorem of algebra".

>Gauss argues that far from the origin, S and T are smooth curves.
>Because the leading term of the polynomial dominates the rest,
>each of these curves intersects any sufficiently large circle
>transversely at n points.

Should be: any sufficiently large circle centered at the origin.

Best,
jb

re: fundamental theorem of algebra

[John Baez]

Dear Vaughan -

You write:

> As a case in point, just now I checked a relatively recent Brittanica
> article on algebra (1987 ed.), which states flatly (p.260a) that "No
> elementary algebraic proof of [the FTAlg] exists, and the result is not
> proved here."  (Not even "is known" but "exists"; an expository article
> should not assume that the reader knows the jargon meaning of this term
> as "exists in the literature".)  The authors taking responsibility for
> this claim were Garrett Birkhoff, Marshall Hall, Pierre Samuel, Peter
> Hilton, and Paul Cohn.  They go into detail to show that z^n = a has n
> roots, starting with the geometry of addition and multiplication in the
> Argand diagram, so it's not as if their exposition was at too elementary
> a level to talk in terms of mapping circles, or that "algebraic" ruled
> out simple geometric arguments.
>
> I submit their nonexistence claim as prima facie evidence for my claim
> that the very few who knew this argument weren't even letting the likes
> of Birkhoff, Hall, etc. in on it, let alone "the rest of us."

I really doubt those authors were unaware of the topological proof
of the fundamental theorem of calculus in 1987.  After all, it's
exercise H.5 in chapter 1 of Spanier's "Algebraic Topology", copyright
1966.  This book used to be the canonical textbook on algebraic
topology, and Peter Hilton is a darn good algebraic topologist.

I think I learned this topological proof sometime in grad school,
around 1986.  So, I don't think it was any sort of secret by then.

I don't know what counts as an "elementary algebraic proof", but
people often say that there is no "purely algebraic proof" of the
fundamental theorem of calculus.   After all, this theorem is about
the complex numbers, which are often defined in terms of the real
numbers, which are often defined as a topological completion of the
rational numbers.  I hope this is what the Encyclopedia article
was trying to say.

There are some so-called "algebraic proofs":

http://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra

that use a bare minimum of topology.  These proofs tend to have
a purely algebraic core, namely "if odd-degree polynomials
and the polynomial x^2 + 1 have roots in some field, this
field is algebraically closed".  But, they use the intermediate
value theorem for continuous functions f: [0,1] -> R to show
that C meets these conditions.  So, I wouldn't call them "purely
algebraic".

It's sort of ironic that the so-called "fundamental theorem of
algebra" doesn't have a purely algebraic proof.

Gauss is famous for having given a proof of the fundamental
theorem of algebra in his dissertation back in 1799.  On the
St. Andrews math history website they write:

  Gauss's proof of 1799 is topological in nature and has some
  rather serious gaps.  It does not meet our present day
  standards required for a rigorous proof.

They don't say how the proof went.  So, I decided to find out!
I was hoping I could irritate you by showing that it was just
the topological proof you claim is so new.  There's a discussion
of it here:

Hans Willi Siegberg
Some Historical Remarks Concerning Degree Theory,
American Mathematical Monthly, 88 (1981), 125-139.
(Available on JSTOR, or via Google Scholar.)

As the title hints, Gauss' proof uses ideas closely related
to the winding number.  Unfortunately, it's slightly different
than the proof you like.

The idea is to take a polynomial of degree n, say

P: C -> C

break it into real and imaginary parts

P = U + iV,

see where they vanish:

S = {z: U(z) = 0}
T = {z: V(z) = 0}

and show that the intersection of S and T is nonempty.

Gauss argues that far from the origin, S and T are smooth curves.
Because the leading term of the polynomial dominates the rest,
each of these curves intersects any sufficiently large circle
transversely at n points.

If we go around the circle these intersection points alternate:
first a point in S, then one in T, then one in S, and so on.

Moreover, the curves I'm talking about can't just disappear as we
follow them into the disk, since they separate the region where U
(resp. V) is positive from the region where it's negative.  They
may become singular, or intersect, but they can't just end!

"So", S and T must intersect somewhere.

This is true, but it takes more topology to prove it rigorously than
was available to Gauss.

Gauss knew his proof wasn't completely rigorous, so he invented some
other arguments.  The "winding number" idea you like is lurking in
Gauss' third proof, which he wrote up in 1816 - but he only gave this
winding number proof explicitly in 1840.  According to Siegberg,

  Indeed, in a lecture "Theorie der imaginaeren Groessen (1840),
  Gauss mentioned [see Fraenkel, 1922] that his third proof of
  the fundamental theorem of the algebra originated from his first
  one, and he gave the function-theoretic argument that the winding
  number W(P|S, 0) equals n [the degree of the polynomial], whereas
  the winding number of any map F: (B,S) -> (R^2, R^2 - {0}) vanishes
  if there is no zero of F in B [see Fraenkel, 1922].  However,
  this argument cannot be found explicitly in [Gauss, 1816].

So, I guess that except perhaps for Gauss, nobody knew the proof
you're talking about until 1840.

Best,
jb