Appendices · Appendices

Every equation has a root: the winding proof

Appendix II 45 min

Appendix II, proof (A): follow the image of a square under ff, count how often it winds round 00, and trap a root in a chain of shrinking squares.

Why this matters

The fundamental theorem of algebra says that every polynomial equation

f(z)=a0zn+a1zn−1+⋯+an=0(a0≠0, n≥1),f(z) = a_0 z^n + a_1 z^{n-1} + \dots + a_n = 0 \qquad (a_0 \ne 0,\ n \ge 1),

with real or complex coefficients, has at least one complex root. Dividing out a root and repeating then shows that ff has exactly nn roots counted with multiplicity. Hardy uses the theorem in several places (partial fractions, for instance) but proves it only here. As he remarks, it belongs more to analysis than to algebra: no proof can avoid continuity somewhere. This lesson gives his first proof, which is a piece of topology: it follows how often a curve winds round the origin.

(The appendix has no section numbers. The proof rests on following the argument of a complex number continuously along a path, the idea behind the many values of log⁡z\log z in Chapter X (§231).)

The idea

Let zz run once round a closed path γ\gamma in the zz-plane. Then Z=f(z)Z = f(z) runs round a closed path Γ\Gamma in the ZZ-plane. If Γ\Gamma never passes through 00, we can follow the angle am⁡Z\operatorname{am} Z continuously along it. When ZZ returns to its starting point the angle has changed by a whole multiple of 2π2\pi: by 2π2\pi times the number of times Γ\Gamma winds round 00. Hardy writes this change as Δ(γ)\Delta(\gamma).

Two facts make the proof go.

  • A big square winds nn times. Far from the origin f(z)f(z) is almost a0zna_0 z^n, and as zz goes once round a big square, znz^n goes nn times round 00. So Δ(S)=2nπ≠0\Delta(S) = 2n\pi \ne 0.
  • A tiny square away from a root winds 00 times. If f(z0)=c≠0f(z_0) = c \ne 0, then on a very small square round z0z_0 the values f(z)f(z) all stay close to cc, so Γ\Gamma is a little loop near cc that cannot go round 00.

Between “big” and “tiny” the winding has to get lost somewhere, and the only places where it can be kept are near roots.

Explore Count the roots by watching the image

Try this. Drag the centre of the purple square and change its size. Watch the image Γ\Gamma on the right and count how many times it goes round the black dot Z=0Z = 0. Then turn on the roots and compare. Try squares containing zero, one, two and all of the roots.

f(z) = z3+(1+i)z+2−iz^3 + (1+i)z + 2 - i
z-plane: the square γ
xy
Z-plane: the image Γ = f(γ)
XY
  • square γ (drag its centre) and its image Γ
  • roots of f
  • Z = 0
Mode
Γ winds 1 time round 00, so Δ(γ)=2π\Delta(\gamma) = 2\pi. Roots inside the square: 1.
What to notice

The winding number of Γ\Gamma always equals the number of roots inside the square. A square with no root inside has an image that may wander but never encircles 00. When the square is large enough to contain every root, the image winds nn times (nn = degree), and it looks more and more like nn turns of a circle. If you push an edge exactly across a root, the image passes through 00 and the count jumps.

The widget computes the winding number numerically, by following the argument of ff along the edges in small steps. That the count equals the number of roots inside is Hardy’s first example at the end of the appendix (Exercise 2 below). The proof of the theorem needs much less: only that the winding of a big square is not 00, and that it splits over sub-squares.

Precise statements

Definition The increment Δ(γ)\Delta(\gamma) Hardy: Appendix II (A)

Let γ\gamma be a closed path in the zz-plane, described once in the positive (anticlockwise) sense, and suppose f(z)≠0f(z) \ne 0 on γ\gamma. Choose a value of am⁡f(z)\operatorname{am} f(z) at the starting point and follow it continuously as zz describes γ\gamma. The total change when zz returns to the start is a multiple of 2π2\pi; it is denoted Δ(γ)\Delta(\gamma), and Δ(γ)/2π\Delta(\gamma)/2\pi is the number of times the image Γ=f(γ)\Gamma = f(\gamma) winds round 00.

Lemma The big square Hardy: Appendix II (A)

Let SS be the square with sides on x=±Rx = \pm R, y=±Ry = \pm R, where RR is so large that

∣a1∣∣a0∣R+∣a2∣∣a0∣R2+⋯+∣an∣∣a0∣Rn<12.\frac{|a_1|}{|a_0|R} + \frac{|a_2|}{|a_0|R^2} + \dots + \frac{|a_n|}{|a_0|R^n} < \frac12.

Then f(z)≠0f(z) \ne 0 on SS and Δ(S)=2nπ\Delta(S) = 2n\pi.

Lemma Additivity Hardy: Appendix II (1)

Divide a square γ\gamma into four equal squares γ(1),…,γ(4)\gamma^{(1)}, \dots, \gamma^{(4)} by lines parallel to the axes, and suppose f≠0f \ne 0 on all their sides. Then

Δ(γ)=Δ(γ(1))+Δ(γ(2))+Δ(γ(3))+Δ(γ(4)).\Delta(\gamma) = \Delta(\gamma^{(1)}) + \Delta(\gamma^{(2)}) + \Delta(\gamma^{(3)}) + \Delta(\gamma^{(4)}).
Theorem The fundamental theorem of algebra Hardy: Appendix II

Every polynomial f(z)=a0zn+⋯+anf(z) = a_0 z^n + \dots + a_n with n≥1n \ge 1, a0≠0a_0 \ne 0 and real or complex coefficients has a root: there is a complex z0z_0 with f(z0)=0f(z_0) = 0.

Proofs

Proof The big square winds nn times
Strategy

Factor out the leading term: f(z)=a0zn(1+η)f(z) = a_0 z^n (1 + \eta) with η\eta small on SS. The factor 1+η1 + \eta stays near 11 and contributes no winding; the factor znz^n contributes nn turns.

Write f(z)=a0zn(1+η)f(z) = a_0 z^n(1 + \eta)

For z≠0z \ne 0, η=a1a0z+a2a0z2+⋯+ana0zn\eta = \dfrac{a_1}{a_0 z} + \dfrac{a_2}{a_0 z^2} + \dots + \dfrac{a_n}{a_0 z^n}. On SS we have ∣z∣≥R|z| \ge R, so by the choice of RR and the triangle inequality, ∣η∣<12|\eta| < \tfrac12 everywhere on SS. In particular f≠0f \ne 0 on SS.

The factor 1+η1 + \eta does not wind

1+η1 + \eta lies in the disc of radius 12\tfrac12 about 11, which lies in the half-plane Re⁡Z>0\operatorname{Re} Z > 0. A path in that half-plane cannot go round 00: its amplitude can be taken in (−12π,12π)(-\tfrac12\pi, \tfrac12\pi) all the way, so it returns to its initial value.

The factor znz^n winds nn times

As zz goes once round SS, which encloses 00, am⁡z\operatorname{am} z increases by 2π2\pi, so am⁡zn=nam⁡z\operatorname{am} z^n = n \operatorname{am} z increases by 2nπ2n\pi. The constant a0a_0 changes nothing.

Add the amplitudes

The amplitude of a product is the sum of the amplitudes, so Δ(S)=0+2nπ+0=2nπ\Delta(S) = 0 + 2n\pi + 0 = 2n\pi. All that is needed later is that this is not 00.

The additivity lemma is a bookkeeping argument, and it is the heart of the method. Go round the four small squares one after another, each anticlockwise. Each side of the big square is traversed exactly once, in the right direction. Each of the four inner half-lines (the pieces of the dividing cross) is traversed twice, once in each direction, as a side of the two small squares it separates; the two changes of amplitude along it cancel. So the four increments add up to the increment round the big square.

Now the hunt. Since the four increments add up to something nonzero, at least one of them is nonzero, and we can keep that quarter. Then we divide again.

Explore Hardy's hunt for a root

Try this. Press Subdivide repeatedly. Each time, the current square is cut into four, each quarter is labelled with its winding number Δ/2π\Delta/2\pi, and the first quarter (in the order of the quadrants I, II, III, IV) with a nonzero label is kept. Keep the roots hidden at first and guess where the squares are heading. Then try the quintic z5−13z−7z^5 - 13z - 7.

f(z) = z3+(1+i)z+2−iz^3 + (1+i)z + 2 - i
z-plane: the square γ (side 5)
xy
Z-plane: the image Γ = f(γ)
XY
  • current square and its image
  • its four quarters, labelled with Δ/2π
  • Z = 0
Mode
Γ winds 3 times round 00, so Δ(γ)=6π\Delta(\gamma) = 6\pi. This is Hardy's square SS with R=2.5R = 2.5: on it ∣η∣<12|\eta| < \tfrac12, so Δ(S)=2nπ\Delta(S) = 2n\pi with n=3n = 3. The quarter labels add up to 3; the first nonzero one is kept.
What to notice

The labels of the four quarters always add up to the label of the parent square, so one of them is nonzero. The squares close in on a single point, and the read-out shows ∣f∣|f| at the centre dropping towards 00: a root has been trapped without ever being computed. For the quintic, three roots are real, so they lie on the xx-axis, which is a dividing line: the images of the quarters pass through 00 at once. Hardy assumes this never happens, because if it did a root would already have been found.

Proof Every polynomial has a root (proof A)
Strategy

Build a nested sequence of squares S,S1,S2,…S, S_1, S_2, \dots, each a quarter of the previous one and each with Δ≠0\Delta \ne 0. They shrink to a point z0z_0. If f(z0)f(z_0) were not 00, continuity would make Δ=0\Delta = 0 on all sufficiently small squares near z0z_0, a contradiction.

If a root lies on a dividing line, we are done

Throughout, suppose that no image Γ\Gamma passes through 00. If one ever did, some point of a side would be a root, and there would be nothing left to prove.

Choose S1,S2,…S_1, S_2, \dots

By the lemma, Δ(S)=2nπ≠0\Delta(S) = 2n\pi \ne 0. By additivity, at least one quarter of SS has Δ≠0\Delta \ne 0; let S1S_1 be the first such. Repeating, we get squares SmS_m of side 21−mR2^{1-m}R, each inside the previous one, with Δ(Sm)≠0\Delta(S_m) \ne 0 for every mm.

The squares shrink to a point z0z_0

Let SmS_m have south-west corner (xm,ym)(x_m, y_m) and north-east corner (xm′,ym′)(x_m', y_m'). Then xmx_m increases, xm′x_m' decreases, and xm′−xm=21−mR→0x_m' - x_m = 2^{1-m}R \to 0, so both tend to a common limit x0x_0 (§69); similarly ym,ym′→y0y_m, y_m' \to y_0. The point z0=x0+iy0z_0 = x_0 + iy_0 lies in (or on the edge of) every SmS_m, and every point of SmS_m is within 21−mR22^{1-m}R\sqrt2 of z0z_0.

Suppose f(z0)=c≠0f(z_0) = c \ne 0

Let ρ=∣c∣>0\rho = |c| > 0. Since ff is continuous, there is a δ>0\delta > 0 with ∣f(z)−c∣<12ρ|f(z) - c| < \tfrac12\rho whenever ∣z−z0∣<δ|z - z_0| < \delta. Choose mm so large that every point of SmS_m is within δ\delta of z0z_0.

Then Δ(Sm)=0\Delta(S_m) = 0

On SmS_m write f(z)=c+σ=c(1+η)f(z) = c + \sigma = c(1 + \eta) with ∣σ∣<12ρ|\sigma| < \tfrac12\rho, so ∣η∣=∣σ∣/ρ<12|\eta| = |\sigma|/\rho < \tfrac12. As in the big-square lemma, 1+η1 + \eta cannot wind round 00, and cc is constant. So am⁡f\operatorname{am} f returns to its initial value: Δ(Sm)=0\Delta(S_m) = 0, contradicting the choice of SmS_m.

Conclude

Hence f(z0)=0f(z_0) = 0. (Incidentally z0z_0 is not on SS itself, since ∣f∣>0|f| > 0 there.)

The structure is the same as the bisection proofs of Chapter I and Chapter V (Weierstrass’s theorem, the intermediate value theorem): a property that is “inherited by at least one half” (here “by at least one quarter”) is chased down a nested sequence of intervals or squares to a single point, and continuity at that point gives the conclusion. Here the inherited property is “the winding number is not zero”.

Exercises

Exercise Where the roots can be ●○○ Hardy: Examples on Appendix II, 2

Show that if R>0R > 0 and ∣a1∣R+∣a2∣R2+⋯+∣an∣Rn<1\dfrac{|a_1|}{R} + \dfrac{|a_2|}{R^2} + \dots + \dfrac{|a_n|}{R^n} < 1, then every root of zn+a1zn−1+⋯+an=0z^n + a_1 z^{n-1} + \dots + a_n = 0 has ∣z∣<R|z| < R. Deduce that every root of z5−13z−7=0z^5 - 13z - 7 = 0 has ∣z∣<2.07|z| < 2.07.

Hint
For ∣z∣≥R|z| \ge R, compare ∣zn∣|z^n| with ∣a1zn−1+⋯+an∣|a_1 z^{n-1} + \dots + a_n|.
Hint
For the quintic, a4=−13a_4 = -13 and a5=−7a_5 = -7; the other aa‘s are 00. Compute R4R^4 and R5R^5 for R=2.07R = 2.07.

Solution

If ∣z∣≥R|z| \ge R then ∣aj∣∣z∣j≤∣aj∣Rj\dfrac{|a_j|}{|z|^j} \le \dfrac{|a_j|}{R^j}, so

∣zn+a1zn−1+⋯+an∣≥∣z∣n(1−∣a1∣∣z∣−⋯−∣an∣∣z∣n)>0.|z^n + a_1 z^{n-1} + \dots + a_n| \ge |z|^n\left(1 - \frac{|a_1|}{|z|} - \dots - \frac{|a_n|}{|z|^n}\right) > 0.

So no root has ∣z∣≥R|z| \ge R. For the quintic with R=2.07R = 2.07: R4=18.36…R^4 = 18.36\ldots and R5=38.00…R^5 = 38.00\ldots, so 13/R4+7/R5<0.709+0.185=0.894<113/R^4 + 7/R^5 < 0.709 + 0.185 = 0.894 < 1. (The bound is nearly sharp: the widget shows the roots, and the largest, a real root, has modulus about 2.0152.015.)

Exercise The winding counts the roots ●●○ Hardy: Examples on Appendix II, 1

Let γ\gamma be a simple closed path (one that does not cross itself), described once anticlockwise, on which ff has no root. Show that Δ(γ)/2π\Delta(\gamma)/2\pi equals the number of roots of ff inside γ\gamma, each counted as often as it is repeated.

Hint
Use the theorem (now proved) to write f(z)=a0(z−z1)(z−z2)⋯(z−zn)f(z) = a_0(z - z_1)(z - z_2)\cdots(z - z_n).
Hint
What is the change in am⁡(z−zj)\operatorname{am}(z - z_j) when zz goes round γ\gamma, if zjz_j is inside? outside?

Solution

By the fundamental theorem, applied nn times, f(z)=a0∏j(z−zj)f(z) = a_0 \prod_j (z - z_j). Along γ\gamma, am⁡f=am⁡a0+∑jam⁡(z−zj)\operatorname{am} f = \operatorname{am} a_0 + \sum_j \operatorname{am}(z - z_j) (each term followed continuously). If zjz_j is inside γ\gamma, the vector from zjz_j to zz turns once round as zz goes round γ\gamma, so am⁡(z−zj)\operatorname{am}(z - z_j) increases by 2π2\pi. If zjz_j is outside, am⁡(z−zj)\operatorname{am}(z - z_j) returns to its initial value. So Δ(γ)=2π×\Delta(\gamma) = 2\pi \times (number of zjz_j inside).

How much of this have we proved? For a square, or any convex path, both facts are clear: seen from an inside point zjz_j, the direction of z−zjz - z_j turns steadily one way and comes round once; from an outside point the whole path lies in an open half-plane through zjz_j, where am⁡(z−zj)\operatorname{am}(z - z_j) can be chosen continuous and single-valued. For a general simple closed path the two facts are still true, but proving them is a piece of topology (the Jordan curve theorem) that we assume rather than prove.

Exercise A disc rather than a square ●○○

Why does a path lying entirely in the disc ∣Z−1∣<12|Z - 1| < \tfrac12 have no winding round 00? Give an explicit continuous choice of am⁡Z\operatorname{am} Z on the disc.

Hint
Where is the real part of ZZ?

Solution

If ∣Z−1∣<12|Z - 1| < \tfrac12 then Re⁡Z>12>0\operatorname{Re} Z > \tfrac12 > 0. On the right half-plane the principal amplitude am⁡Z=arctan⁡(Y/X)\operatorname{am} Z = \arctan(Y/X), with values in (−12π,12π)(-\tfrac12\pi, \tfrac12\pi), is continuous. Following it along the path gives the continuous amplitude, and since it is a function of the point ZZ alone, it takes the same value at the end as at the start. So the increment is 00.

Exercise The cancelling edges ●○○

Let ℓ\ell be a segment from PP to QQ on which f≠0f \ne 0, and let δ\delta be the change of am⁡f\operatorname{am} f as zz goes from PP to QQ along ℓ\ell. Show that the change from QQ to PP along ℓ\ell is −δ-\delta, and explain how this gives the additivity lemma.

Hint
Following a continuous function backwards along the same path…

Solution

If θ(t)\theta(t) is a continuous amplitude of ff at the point P+t(Q−P)P + t(Q - P), 0≤t≤10 \le t \le 1, then θ(1−s)\theta(1 - s) is a continuous amplitude along the reversed segment, and its change is θ(0)−θ(1)=−δ\theta(0) - \theta(1) = -\delta. (Any other continuous choice differs by a constant multiple of 2π2\pi, which does not affect the change.) When the four small squares are described, each inner edge is described once each way, contributing δ−δ=0\delta - \delta = 0; the outer edges together make up the big square once, anticlockwise. The changes along successive pieces of a path add, so the four increments add to Δ\Delta of the big square.

Exercise A small perturbation does not change the count ●●○ Hardy: Examples on Appendix II, 11

Let ff and ϕ\phi be polynomials and γ\gamma a closed path on which ∣ϕ(z)∣<∣f(z)∣|\phi(z)| < |f(z)|. Show that ff and f+ϕf + \phi have the same number of roots inside γ\gamma. Use this to show that z5+5z+1z^5 + 5z + 1 has exactly one root with ∣z∣<1|z| < 1.

Hint
Write f+ϕ=f (1+ϕ/f)f + \phi = f\,(1 + \phi/f) and look at where 1+ϕ/f1 + \phi/f lies.
Hint
For the example take f(z)=5zf(z) = 5z on the circle ∣z∣=1|z| = 1.

Solution

On γ\gamma, f≠0f \ne 0 and ∣ϕ/f∣<1|\phi/f| < 1, so 1+ϕ/f1 + \phi/f lies in the disc ∣W−1∣<1|W - 1| < 1, which lies in Re⁡W>0\operatorname{Re} W > 0; as in the previous exercise it contributes no winding. Hence Δ\Delta for f+ϕf + \phi equals Δ\Delta for ff, and f+ϕf + \phi has no root on γ\gamma. By Exercise 2, both have the same number of roots inside. (So the result is fully proved for squares, circles and other convex paths; for a general simple closed path it rests on the topological facts assumed in Exercise 2.)

For the example, on ∣z∣=1|z| = 1: ∣z5+1∣≤2<5=∣5z∣|z^5 + 1| \le 2 < 5 = |5z|. So z5+5z+1=5z+(z5+1)z^5 + 5z + 1 = 5z + (z^5 + 1) has as many roots inside the unit circle as 5z5z, namely one.

Exercise Why squares? ●●○

Hardy uses squares only because they are easy to subdivide and to shrink. Which steps of the proof would change if we used the circle ∣z∣=R|z| = R for the first path, and which property of squares is used in the hunt that circles do not have?

Solution

The big-square lemma works unchanged for the circle ∣z∣=R|z| = R: there too ∣z∣≥R|z| \ge R, ∣η∣<12|\eta| < \tfrac12 and am⁡zn\operatorname{am} z^n increases by 2nπ2n\pi. The hunt, however, needs a region that can be cut into finitely many pieces of the same kind, each of diameter half (or a fixed fraction) of the original, so that the additivity argument applies again at the next stage. A square splits into four squares; a disc does not split into discs. Any shape that tiles itself (triangles, rectangles) would do.

Check yourself

Check yourself Enter a number

For a quartic ff, the big square SS has Δ(S)=8π\Delta(S) = 8\pi. Its quarters have Δ/2π\Delta/2\pi equal to 11, 00 and 22 for the first three. What is Δ/2π\Delta/2\pi for the fourth?

Why

The four quarter increments add up to Δ(S)\Delta(S), so the labels add up to Δ(S)/2π=4\Delta(S)/2\pi = 4: the fourth is 4−1−0−2=14 - 1 - 0 - 2 = 1. In the widget the labels always add to the parent’s label.

Check yourself Choose one

Why is Δ(S)=2nπ\Delta(S) = 2n\pi for the big square SS?

Why

The first answer is true, but it uses the theorem we are trying to prove (it presupposes that there are nn roots). Large ∣f∣|f| alone says nothing about winding: a large loop far from 00 need not go round it. What matters is that ff is close to a0zna_0 z^n in ratio.

Check yourself True or false?

In Hardy’s hunt, the nested squares always close in on the root of largest modulus.

Why

False. Which root is found depends on the order in which the quarters are tried (Hardy takes “the first which is not zero”) and on where the roots lie. Try different polynomials in the widget: the squares go to whichever root lies in the first quarter with nonzero winding.

Check yourself Choose one

In the last step, why does f(z0)=c≠0f(z_0) = c \ne 0 force Δ(Sm)=0\Delta(S_m) = 0 for large mm?

Why

Shortness is not the point: a short loop near 00 could still go round it. The proof needs the image to stay in a disc about cc that excludes 00, which continuity at z0z_0 provides. The last option assumes that winding counts roots, which is more than the proof uses.

Hardy’s language

The theorem that ‘every algebraical equation has a root’ is usually called ‘the fundamental theorem of algebra’, but it belongs more properly to analysis, since it cannot be proved without appeal somewhere to considerations of continuity.

— G. H. Hardy, Appendix II

Summary

Summary
  • Δ(γ)\Delta(\gamma), the total change of am⁡f(z)\operatorname{am} f(z) round a closed path, is 2π2\pi times the winding number of the image about 00; it counts the roots inside.
  • On a big square f=a0zn(1+η)f = a_0 z^n(1 + \eta) with ∣η∣<12|\eta| < \tfrac12, so Δ=2nπ≠0\Delta = 2n\pi \ne 0.
  • Δ\Delta is additive over the four quarters, so some quarter keeps Δ≠0\Delta \ne 0; nested quarters shrink to a point z0z_0.
  • If f(z0)≠0f(z_0) \ne 0, continuity keeps the image of a tiny square in a disc avoiding 00, so Δ=0\Delta = 0: contradiction. Hence f(z0)=0f(z_0) = 0.
  • The pattern is the bisection argument of Chapters I and V, in two dimensions, with “winding number ≠0\ne 0” as the inherited property.