Real Algebraic Geometry · Study tools

Step-throughBasu–Pollack–Roy, Ch. 1: Algebraically Closed Fields

Remainders and elimination over ℂ

Do two polynomials have a common complex root? You can answer without finding a single root: divide, keep the remainder, and repeat. When the coefficients depend on parameters, the same computation describes the set of parameters for which a solution exists, and that is the whole idea behind elimination over $\C$ .

The idea

Euclidean division. For polynomials

P, Q

over a field with

Q\neq 0

there are unique

A, R

with

P = AQ + R

and

\deg R < \deg Q

. The remainder sequence starts

R_0=P,\ R_1=Q

and continues

R_{i+1}=\operatorname{Rem}(R_{i-1},R_i)

until a remainder is

0

. The last nonzero

R_i

is

\gcd(P,Q)

up to a constant.

Common roots. Because

\C

is algebraically closed,

P

and

Q

(not both zero) have a common root in

\C

if and only if

\deg\gcd(P,Q)\ge 1

, and the common roots are exactly the roots of the gcd. In particular

P

has

\deg P-\deg\gcd(P,P')

distinct complex roots.

Every common root of $R_{i-1}$ and $R_i$ is a root of $R_{i+1}=R_{i-1}-A_iR_i$ , and conversely, so the common roots never change along the sequence. Only the degrees drop.

Constructible set. A subset of

\C^k

defined by a boolean combination of polynomial equations

P=0

. In

\C

these are exactly the finite sets and their complements.

Projection theorem. The projection of a constructible subset of

\C^{k+1}

to

\C^k

is constructible. Equivalently, every formula built from polynomial equations,

\wedge,\vee,\neg

and quantifiers over

\C

is equivalent to a quantifier-free one, and (transfer) a sentence with coefficients in a field

K

is true in one algebraically closed field containing

K

exactly when it is true in all of them.

The proof runs the remainder sequence with coefficients that are polynomials in the parameters, branching on whether each leading coefficient vanishes. There are finitely many branches, and each is described by equations and inequations in the parameters.

Not over ℝ.

x^2+1

and

x^3+x

have gcd

x^2+1

: two common complex roots, no common real root. Real questions need inequalities, which is where the rest of this page goes.

Explore

roots of P roots of Q roots of gcd(P, Q), in the complex plane

P(x) Q(x)

Parameter a (type the letter a in P or Q)

Examples

Worked example

For which complex numbers $a$ do $P=x^2+ax+1$ and $Q=x^2+x+a$ have a common root? (This is the last example in the explorer.)

Do the first division. What is $R_2$ ?

Both are monic of degree 2, so the quotient is $1$ and $R_2 = P-Q = (a-1)x+(1-a) = (a-1)(x-1)$ .
The next step depends on $a$ . What happens when $a=1$ ?

Then $R_2=0$ , so the gcd is $Q=x^2+x+1$ . In fact $P=Q$ : two common roots, the primitive cube roots of unity.
Now take $a\neq1$ . Divide $Q$ by $R_2$ .

$R_2$ is a nonzero multiple of $x-1$ , and the remainder of $Q$ on division by a multiple of $x-1$ is the constant $Q(1)=2+a$ . So $R_3=2+a$ .
Finish: describe the set of $a$ with a common root, as a formula without $x$ .

If $a\neq 1$ and $a\neq-2$ , $R_3$ is a nonzero constant and the gcd is $1$ . If $a=-2$ , the gcd is $x-1$ and the common root is $x=1$ (check: $1-2+1=0$ and $1+1-2=0$ ). So

$\exists x\ \big(P(x)=0\wedge Q(x)=0\big)\iff (a-1)(a+2)=0 .$

The projection of the curve $\{(a,x): P=Q=0\}$ to the $a$ -line is the finite set $\{1,-2\}$ : constructible, as the theorem promises. The branches of the computation ( $a=1$ , $a=-2$ , the rest) are exactly the cases in the answer.

Check your understanding

Two real polynomials $P, Q$ have $\gcd(P,Q)=x^2+1$ . What can you conclude?

They have exactly two common roots in $\C$ , namely $\pm i$ , and no common real root.
They have a common real root.The common roots are the roots of the gcd, and $x^2+1$ has no real roots.
They have no common root at all, since the gcd has no real root.Over $\C$ the gcd's roots are common roots of $P$ and $Q$ : divisibility doesn't care which field you look for roots in.

x^2+1

divides both, so

\pm i

are common roots, and any common root is a root of the gcd. The gcd test answers the complex question; the real question needs the tools of the next modules.

Which of these subsets of $\C$ is constructible?

$\Z$ A constructible subset of $\C$ is finite or has finite complement. $\Z$ is infinite and so is its complement.
$\C\smallsetminus\{0,1\}$
The unit circle $\{z: |z|=1\}$ $|z|^2=z\bar z$ is not a polynomial in $z$ . The circle is infinite with infinite complement, so it can't be constructible.

\C\smallsetminus\{0,1\}

is defined by

\neg\big(z(z-1)=0\big)

. In one variable a single nonzero polynomial has finitely many roots, which is why constructible subsets of

\C

are finite or cofinite.

Over $\C$ , the formula $\exists x\ (x^2+a=0)$ with parameter $a$ is equivalent to which quantifier-free formula?

$a\le 0$ There is no order on $\C$ to write this with. That is the answer over $\R$ .
$a\neq 0$ $a=0$ has the solution $x=0$ .
$0=0$ , that is, "true" for every $a$

Every complex number has a square root, so the projection is all of

\C

. Over

\R

the answer

a\le0

is an inequality: real elimination produces semi-algebraic sets, not constructible ones.

Practice

Counting distinct rootsgcd with the derivative

Let $P=x^4-2x^3+2x-1$ . Compute $\gcd(P,P')$ and deduce the number of distinct complex roots of $P$ . Then find them.

Hint

Run the remainder sequence of $P$ and $P'=4x^3-6x^2+2$ , or type both into the explorer. A root of multiplicity $m$ of $P$ is a root of multiplicity $m-1$ of the gcd.

Solution

$\gcd(P,P')=(x-1)^2$ , so $P$ has $4-2=2$ distinct roots and $1$ is a root of multiplicity 3. Dividing, $P=(x-1)^3(x+1)$ : the roots are $1$ (triple) and $-1$ .

Eliminating a variableA parameter in one polynomial

For which $a\in\C$ do $x^3-a$ and $x^2-1$ have a common root? Answer with the remainder sequence, then check directly.

Hint

$x^3-a = x\,(x^2-1) + (x-a)$ .

Solution

The sequence is $x^3-a,\ x^2-1,\ x-a,\ a^2-1$ (the last is the value of $x^2-1$ at $x=a$ ). So there is a common root iff $a^2=1$ . Directly: a common root is $\pm1$ , and $(\pm1)^3=a$ gives $a=\pm1$ .

More practice: Basu–Pollack–Roy, Exercises 1.2 and 1.9.

InteractiveBasu–Pollack–Roy, Ch. 2: Real Closed Fields

Descartes' law of signs

The signs of the coefficients already bound the number of positive roots. Build a polynomial from its roots, watch the signs of its coefficients, and see why the overcount is always even.

The idea

Real closed field. An ordered field

R

in which every positive element is a square and every polynomial of odd degree has a root. Equivalently, polynomials over

R

satisfy the intermediate value theorem.

\R

is one; so are the real algebraic numbers and the field of real Puiseux series (module 4). Everything on this page works over any real closed field.

Sign variations. For a sequence of numbers,

\operatorname{Var}

is the number of sign changes after deleting the zeros. For

P=a_px^p+\dots+a_0

, write

\operatorname{Var}(P)=\operatorname{Var}(a_p,\dots,a_0)

and

\operatorname{pos}(P)

for the number of positive roots counted with multiplicity.

Descartes' law of signs.

\operatorname{Var}(P)\ge\operatorname{pos}(P)

, and

\operatorname{Var}(P)-\operatorname{pos}(P)

is even.

Budan–Fourier. Let

\operatorname{Der}(P)=(P,P',\dots,P^{(p)})

. For

a<b

, the number

\operatorname{Var}(\operatorname{Der}(P);a)-\operatorname{Var}(\operatorname{Der}(P);b)

is at least the number of roots in

(a,b]

counted with multiplicity, and the difference is even. Descartes is the case

a=0

,

b=+\infty

: the signs of

P^{(k)}(0)

are the signs of the coefficients.

The parity part is easy to see when $a_0\neq 0$ : $\operatorname{Var}(P)$ is odd exactly when $a_0$ and $a_p$ have opposite signs, which is exactly when $P(0)$ and $P(+\infty)$ have opposite signs, which is exactly when $P$ has an odd number of positive roots.

When it is exact. If all roots of

P

are real, then

\operatorname{Var}(P)=\operatorname{pos}(P)

. The overcount comes only from non-real roots.

Explore

real roots (drag along the axis) a complex pair (drag the upper one) · P is the monic polynomial with these roots

Examples

Coefficients of P, leading first (⇅ marks a sign change)

Worked example

How many positive and negative roots does $P=x^3-x^2+2$ have?

What does Descartes' law say about positive roots?

The coefficients are $1,-1,0,2$ , with signs $+,-,+$ after deleting the zero: $\operatorname{Var}(P)=2$ . So $P$ has 2 or 0 positive roots.
Apply it to $P(-x)$ for the negative roots.

$P(-x)=-x^3-x^2+2$ has signs $-,-,+$ : one variation, so exactly one negative root. (One variation can't overcount: the excess would have to be even and nonnegative, and $1-0$ is odd.)
Find the negative root and settle the positive ones.

$P(-1)=-1-1+2=0$ , and $P=(x+1)(x^2-2x+2)$ . The quadratic has discriminant $4-8<0$ , so its roots $1\pm i$ are not real. $P$ has no positive roots: here Descartes overcounts by 2.
Where do the two "phantom" sign changes come from?

From the factor $x^2-2x+2$ , whose coefficients $+,-,+$ already have two variations. Its roots $1\pm i$ have positive real part, close to the positive axis. Make "A complex pair" in the explorer and drag the pair well into the left half-plane: the phantom variations disappear (close to the imaginary axis they can persist).

Check your understanding

A polynomial of degree 4 has coefficient signs $+,-,-,+,-$ (leading first, none zero). How many positive roots can it have?

Exactly 3Descartes gives an upper bound and a parity. It is exact only when all roots are real.
3 or 1
0, 1, 2 or 3The overcount $\operatorname{Var}-\operatorname{pos}$ is even, so the parity is fixed.

The signs change three times, so

\operatorname{pos}\in\{3,1\}

. In particular there is at least one positive root, which you can also see from

P(0)<0<P(+\infty)

.

How many real roots does $x^5+1$ have?

0An odd-degree real polynomial always has a real root.
1
5Count the variations of $P$ and of $P(-x)$ .
3There are no positive roots and exactly one negative one.

\operatorname{Var}(x^5+1)=0

: no positive roots.

\operatorname{Var}(-x^5+1)=1

: exactly one negative root. And

0

is not a root. So there is one real root,

-1

, and two complex pairs.

$P$ has degree 6, all its roots are real, $P(0)\neq0$ , and $\operatorname{Var}(P)=4$ . How many negative roots does it have?

Exactly 2
2 or 0With all roots real Descartes is exact: there are exactly 4 positive roots.
Not enough informationYou know the degree, that 0 is not a root, and the exact number of positive roots.

All roots real gives

\operatorname{pos}(P)=4

, and since

0

is not a root the other

6-4=2

roots are negative.

Practice

One real rootDescartes plus a little calculus

Show that $x^5-x+1$ has exactly one real root, and that it is negative.

Hint

Descartes leaves two possibilities for the positive roots. Rule out 2 by finding the minimum of the polynomial on $(0,\infty)$ .

Solution

$\operatorname{Var}(P)=2$ and $\operatorname{Var}(P(-x))=\operatorname{Var}(-x^5+x+1)=1$ : one negative root, and 0 or 2 positive ones. On $(0,\infty)$ , $P'=5x^4-1$ vanishes only at $x_0=5^{-1/4}\approx0.669$ , where $P(x_0)=1-\tfrac45x_0\approx0.465>0$ . So $P>0$ on $(0,\infty)$ , and the only real root is the negative one.

Budan–Fourier on intervalsCounting in (0, 1] and (1, 2]

For $P=x^3-3x+1$ , use Budan–Fourier at $x=0,1,2$ to show that $P$ has exactly one root in $(0,1]$ and exactly one in $(1,2]$ .

Hint

$\operatorname{Der}(P)=(x^3-3x+1,\ 3x^2-3,\ 6x,\ 6)$ . A count of 1 is exact, because the excess is even.

Solution

At 0: $(1,-3,0,6)$ , signs $+,-,+$ , two variations. At 1: $(-1,0,6,6)$ , signs $-,+,+$ , one variation. At 2: $(3,9,12,6)$ , no variation. So the bound for $(0,1]$ is $2-1=1$ and for $(1,2]$ it is $1-0=1$ . Each bound is exact: the true count is the bound minus an even number, and it can't be negative, so from 1 it must be 1. (The roots are about 0.347 and 1.532.)

More practice: Basu–Pollack–Roy, Exercise 2.12.

InteractiveBasu–Pollack–Roy, Ch. 2: Real Closed Fields

Sturm sequences

Descartes gives a bound. Sturm's theorem gives the exact number of real roots in any interval: evaluate a short sequence of polynomials at the two endpoints and count sign changes. Drag the endpoints and watch the count follow the roots.

The idea

Sturm sequence. The signed remainder sequence of

P

and

P'

:

P_0=P,\ P_1=P'

and

P_{i+1}=-\operatorname{Rem}(P_{i-1},P_i)

, stopping before the first zero remainder. For a point

x

,

\operatorname{Var}(x)

is the number of sign changes in

P_0(x),P_1(x),\dots

, and at

\pm\infty

one uses the signs of the leading terms.

Sturm's theorem. If

a<b

(possibly

\pm\infty

) are not roots of

P

, then the number of distinct real roots of

P

in

(a,b)

is

\operatorname{Var}(a)-\operatorname{Var}(b)

.

Why: $\operatorname{Var}$ can only change where some $P_i$ vanishes. If $P_i(c)=0$ with $i\ge1$ , then $P_{i-1}(c)=-P_{i+1}(c)\neq0$ , so the triple $P_{i-1},P_i,P_{i+1}$ has one sign change on both sides of $c$ . If $P(c)=0$ , then $P$ and $P'$ have opposite signs just left of a simple root and equal signs just right of it: one change is lost. A multiple root is handled by noticing that every $P_i$ is divisible by $\gcd(P,P')$ , the last term.

Cauchy index and Tarski queries. The Cauchy index

\operatorname{Ind}(Q/P;a,b)

counts the jumps of

Q/P

from

-\infty

to

+\infty

minus the jumps from

+\infty

to

-\infty

at poles in

(a,b)

. The signed remainder sequence of

P

and

Q

computes it the same way. With

Q=P'Q_0

it gives the Tarski query

\operatorname{TaQ}(Q_0,P)=\sum_{x\in\R,\ P(x)=0}\operatorname{sign}Q_0(x)=\operatorname{Ind}\!\left(\frac{P'Q_0}{P}\right),

the number of roots of $P$ where $Q_0>0$ minus those where $Q_0<0$ . Tarski queries for $Q_0=1,\ Q_0,\ Q_0^2$ determine how many roots have each sign of $Q_0$ . That is the engine of the projection theorem for semi-algebraic sets later in Chapter 2.

Explore

P(x)

Examples

Drag the endpoints a and b. roots inside (a, b). The vertical scale is compressed, but signs are kept.

Worked example

Locate the real roots of $P=x^3-3x+1$ using its Sturm sequence.

Compute the Sturm sequence.

$P_1=3x^2-3$ . Dividing, $P=\tfrac x3(3x^2-3)+(-2x+1)$ , so $P_2=2x-1$ . Then the remainder of $3x^2-3$ by $2x-1$ is its value at $x=\tfrac12$ , namely $-\tfrac94$ , so $P_3=\tfrac94$ .
How many real roots are there?

At $-\infty$ the signs are $-,+,-,+$ : three changes. At $+\infty$ : $+,+,+,+$ , none. So $P$ has $3-0=3$ real roots.
How many lie in $(0,1)$ ?

At 0: $1,-3,-1,\tfrac94$ , signs $+,-,-,+$ , two changes. At 1: $-1,0,1,\tfrac94$ , signs $-,+,+$ after dropping the zero, one change. Exactly $2-1=1$ root in $(0,1)$ .
Place the other two.

At 2: $3,9,3,\tfrac94$ , no change, so one root in $(1,2)$ . At $-2$ : $-1,9,-5,\tfrac94$ , three changes, so one root in $(-2,0)$ . The roots are about $-1.879$ , $0.347$ , $1.532$ : pick the first example in the explorer to check.

Check your understanding

$x$ passes a root $c$ of $P_i$ for some $i\ge1$ , and $P(c)\neq0$ . Why does $\operatorname{Var}$ not change?

Because $P_i$ does not change sign at $c$ .It may well change sign. What matters is its two neighbours.
Because $P_{i-1}(c)=-P_{i+1}(c)\neq0$ , so whatever the sign of $P_i$ , the three of them have exactly one sign change near $c$ .
Because the theorem only counts roots of $P$ .That is what has to be proved: sign changes elsewhere must not disturb the count.

The defining relation

P_{i-1}=A_iP_i-P_{i+1}

at a root of

P_i

gives

P_{i-1}(c)=-P_{i+1}(c)

. These are nonzero, since otherwise all later terms would vanish at

c

, including

\gcd(P,P')

, and

c

would be a root of

P

.

The Sturm sequence of $x^2+1$ is $x^2+1,\ 2x,\ -1$ . What is $\operatorname{Var}(-\infty)-\operatorname{Var}(+\infty)$ ?

0
2At $-\infty$ the signs are $+,-,-$ , only one change.
1At $+\infty$ the signs are $+,+,-$ , which also has one change.

One change at each end, so no real roots, as expected. Note that

\operatorname{Var}

itself need not be 0 at the ends; only the difference counts.

$P=x^3-x$ and $Q=x$ . What is the Tarski query $\operatorname{TaQ}(Q,P)$ ?

3That's $\operatorname{TaQ}(1,P)$ , the number of real roots.
2The root $0$ contributes $\operatorname{sign}Q(0)=0$ , and $-1$ contributes $-1$ .
0

The roots are

-1,0,1

, where

Q

has signs

-,0,+

. The sum is

0

: one root with

Q>0

, one with

Q<0

. Together with

\operatorname{TaQ}(1,P)=3

and

\operatorname{TaQ}(Q^2,P)=2

this pins down the counts

1,1,1

.

Practice

A Sturm sequence by handDegree 4

Compute the Sturm sequence of $x^4-2x^2-1$ and use it to count the real roots.

Hint

$P=\tfrac x4\,(4x^3-4x)-(x^2+1)$ .

Solution

The sequence is $x^4-2x^2-1,\ 4x^3-4x,\ x^2+1,\ 8x,\ -1$ . Signs at $-\infty$ : $+,-,+,-,-$ , three changes. At $+\infty$ : $+,+,+,+,-$ , one change. So there are 2 real roots, $\pm\sqrt{1+\sqrt2}$ .

Signs of Q at the roots of PThree Tarski queries

Let $c_+,c_-,c_0$ be the numbers of real roots of $P=x^3-3x+1$ at which $Q=x$ is positive, negative, zero. Express $\operatorname{TaQ}(1,P)$ , $\operatorname{TaQ}(Q,P)$ , $\operatorname{TaQ}(Q^2,P)$ in terms of them and solve, given that these queries are $3, 1, 3$ .

Hint

Each root contributes $\operatorname{sign}Q$ , $\operatorname{sign}Q^2$ or $1$ to the sums.

Solution

$c_++c_-+c_0=3$ , $c_+-c_-=1$ , $c_++c_-=3$ . So $c_0=0$ , $c_+=2$ , $c_-=1$ , matching the roots $-1.879,\ 0.347,\ 1.532$ . The matrix of this linear system is invertible, which is why sign determination works for any number of polynomials (by taking tensor powers of it).

More practice: Basu–Pollack–Roy, Exercise 2.13.

InteractiveBasu–Pollack–Roy, Ch. 2: Real Closed Fields · Ch. 3: Semi-Algebraic Sets

Infinitesimals and Puiseux series

Many algorithms in this subject perturb a problem by an infinitely small $\varepsilon$ to make it generic. The roots of the perturbed polynomial are Puiseux series in $\varepsilon$ , and a picture called the Newton polygon reads off how big each root is.

The idea

Puiseux series. Series

a=\sum_{i\ge i_0}a_i\,\varepsilon^{i/q}

with a fixed positive integer

q

and coefficients in

R

. Those that are algebraic over

R(\varepsilon)

form a field

R\langle\varepsilon\rangle

. It is ordered by the sign of the leading coefficient

a_{i_0}

, so

\varepsilon>0

but

\varepsilon<r

for every positive

r\in R

:

\varepsilon

is infinitesimal.

Theorem. If

R

is real closed, so is

R\langle\varepsilon\rangle

, and

C\langle\varepsilon\rangle=R\langle\varepsilon\rangle[i]

is algebraically closed. So every polynomial in

x

with coefficients in

R[\varepsilon]

factors into linear terms over Puiseux series.

An element is bounded over $R$ when it has no negative exponents. Then its constant term is its limit $\lim_\varepsilon a\in R$ . This is how algorithms come back from a perturbed problem to the original one.

Germs (Ch. 3). A Puiseux series can be read as the germ at

0^+

of a continuous semi-algebraic function

t\mapsto f(t)

, with

\varepsilon

standing for

t

itself. A statement holds in

R\langle\varepsilon\rangle

exactly when it holds for all small enough positive

t

. That is what the log–log plot below shows numerically.

Newton polygon. Write

P=\sum a_{ij}\varepsilon^ix^j

and mark the points

(j,i)

with

a_{ij}\neq0

. Each edge of the lower convex hull, of slope

-q

and width

\ell

, accounts for

\ell

roots of order

\varepsilon^{q}

. Their leading coefficients are the nonzero roots

c

of the edge equation

\sum_{(j,i)\text{ on the edge}}a_{ij}c^{\,j}=0

.

Reason: substitute $x=c\varepsilon^q$ . The terms on the edge all have the same, lowest, power of $\varepsilon$ , so they must cancel among themselves.

Explore

P(ε, x)

ε (log scale)

Newton polygon: a dot for each term εⁱx^j, with its coefficient. lower edges

|roots| against ε, both on log scales. real complex predicted |c|·ε^q

Worked example

Find the orders and leading terms of the roots of $P=x^3-\varepsilon x^2-\varepsilon^4$ , and decide which roots lie in the real closed field $\R\langle\varepsilon\rangle$ .

Plot the Newton points and find the lower hull.

The terms give the points $(3,0)$ , $(2,1)$ , $(0,4)$ . The lower hull runs $(0,4)\to(2,1)\to(3,0)$ , with slopes $-\tfrac32$ and $-1$ . (The slopes increase, so the hull is convex there.)
What does each edge predict?

Edge $(0,4)$ – $(2,1)$ : width 2, so two roots of order $\varepsilon^{3/2}$ . Edge $(2,1)$ – $(3,0)$ : width 1, one root of order $\varepsilon$ .
Solve the edge equations.

First edge: the terms $-\varepsilon x^2$ and $-\varepsilon^4$ give $-c^2-1=0$ , so $c=\pm i$ . Second edge: $x^3$ and $-\varepsilon x^2$ give $c^3-c^2=0$ , nonzero root $c=1$ .

$x_1=\varepsilon+\cdots,\qquad x_{2,3}=\pm i\,\varepsilon^{3/2}+\cdots$
Which roots are real Puiseux series? Are they infinitesimal?

Only $x_1$ : the other two are complex conjugates. $x_1$ is positive and infinitesimal, with $\lim_\varepsilon x_1=0$ . Numerically at $\varepsilon=10^{-3}$ the roots are about $0.001001$ and $-5\cdot10^{-7}\pm3.16\cdot10^{-5}i$ , and $\varepsilon^{3/2}\approx3.16\cdot10^{-5}$ .

Check your understanding

In $\R\langle\varepsilon\rangle$ , which is larger: $\varepsilon^{1/2}$ or $1000\,\varepsilon$ ?

$\varepsilon^{1/2}$
$1000\,\varepsilon$ Compare leading terms: a smaller exponent beats any constant factor.
It depends on the value of $\varepsilon$ . $\varepsilon$ is not a number to plug in; the order is decided by the leading term of the difference.

\varepsilon^{1/2}-1000\varepsilon=\varepsilon^{1/2}(1-1000\,\varepsilon^{1/2})

has leading coefficient

1>0

. As a germ: for all small enough

t>0

,

\sqrt t>1000t

.

Which of these elements is bounded over $\R$ , and what is its limit?

$1/\varepsilon$ It is larger than every real number.
$2+\varepsilon^{1/3}$ , with limit 2
$\varepsilon^{-1/2}+3$ A negative exponent makes it unbounded.

Bounded means no negative exponents; the limit is the constant term. Taking

\lim_\varepsilon

of a perturbed solution is how one recovers a solution of the unperturbed problem.

What are the orders of the two roots of $\varepsilon^2x^2+x+1$ ?

$\varepsilon^0$ and $\varepsilon^{-2}$
$\varepsilon^0$ and $\varepsilon^{2}$ The second edge goes up from $(1,0)$ to $(2,2)$ : positive slope, so the exponent is negative and the root is large.
Both of order $\varepsilon^{-1}$ The polygon has two edges with different slopes.

Edges

(0,0)

–

(1,0)

(slope 0, edge equation

c+1=0

) and

(1,0)

–

(2,2)

(slope 2, edge equation

c^2+c=0

). So the roots are about

-1

and

-\varepsilon^{-2}

; their product is

\varepsilon^{-2}

, as it should be.

Practice

Two terms of each rootBeyond the leading term

Find the first two nonzero terms of both roots of $x^2-2\varepsilon x-\varepsilon$ . Which is positive?

Hint

The quadratic formula works in a real closed field. Expand $\sqrt{\varepsilon+\varepsilon^2}=\varepsilon^{1/2}(1+\varepsilon)^{1/2}$ .

Solution

$x=\varepsilon\pm\sqrt{\varepsilon+\varepsilon^2}=\pm\varepsilon^{1/2}+\varepsilon\pm\tfrac12\varepsilon^{3/2}+\cdots$ . The Newton polygon has one edge $(0,1)$ – $(2,0)$ (the point $(1,1)$ lies above it), predicting $\pm\varepsilon^{1/2}$ . The root $\varepsilon^{1/2}+\varepsilon+\cdots$ is positive and the other negative; both are infinitesimal.

Signs and sizesWorking in the ordered field

Decide the sign of $-\varepsilon^3+10^6\varepsilon^4$ and of $\dfrac{\varepsilon-\varepsilon^2}{\varepsilon^2+\varepsilon^3}$ , and say whether each is infinitesimal, bounded but not infinitesimal, or unbounded.

Solution

$-\varepsilon^3+10^6\varepsilon^4=\varepsilon^3(-1+10^6\varepsilon)$ : negative and infinitesimal, whatever the size of $10^6$ . The fraction equals $\varepsilon^{-1}(1-\varepsilon)(1+\varepsilon)^{-1}=\varepsilon^{-1}-2+2\varepsilon-\cdots$ : positive and unbounded.

More practice: Basu–Pollack–Roy, Exercises 2.4 and 2.19.

InteractiveBasu–Pollack–Roy, Ch. 4: Algebra

Discriminants and Hermite's form

Whether a cubic has one real root or three is decided by the sign of a single polynomial in its coefficients. Hermite's quadratic form goes further, in every degree: its rank counts the distinct complex roots and its signature the distinct real ones. Drag the cubic across its discriminant curve and watch two real roots collide and leave the real line.

The idea

Discriminant. If

P=a_p\prod_{i=1}^p(x-x_i)

over

\C

, then

\operatorname{Disc}(P)=a_p^{2p-2}\prod_{i<j}(x_i-x_j)^2

. It is a polynomial in the coefficients of

P

and vanishes exactly when

P

has a multiple root. For

x^3+px+q

it is

-4p^3-27q^2

.

For real $P$ with distinct roots, each pair of conjugate roots $z,\bar z$ contributes $(z-\bar z)^2=(2i\operatorname{Im}z)^2<0$ , and all the other factors pair up into positive numbers. So $\operatorname{sign}\operatorname{Disc}(P)=(-1)^{\#\text{conjugate pairs}}$ .

Resultant and subresultants.

\operatorname{Res}(P,Q)

is the determinant of the Sylvester matrix of

P

and

Q

; it vanishes iff they have a common root (or both leading coefficients vanish).

\operatorname{Disc}(P)=(-1)^{p(p-1)/2}\operatorname{Res}(P,P')/a_p

. The subresultant coefficients

\operatorname{sRes}_j

are certain minors of the same matrix, and

\deg\gcd(P,Q)

is the smallest

j

with

\operatorname{sRes}_j\neq0

.

Hermite's quadratic form. With Newton sums

N_k=\sum_i x_i^k

(roots counted with multiplicity),

\operatorname{Her}(P)

is the form on polynomials

f

of degree

<p

\operatorname{Her}(P)(f)=\sum_{i=1}^p f(x_i)^2,\qquad\text{matrix } \big(N_{j+k}\big)_{0\le j,k<p}.

The $N_k$ are rational functions of the coefficients (Newton's identities), so the matrix is computable without the roots.

Hermite's theorem. The rank of

\operatorname{Her}(P)

is the number of distinct roots of

P

in

\C

, and its signature is the number of distinct roots in

\R

.

Each distinct real root $x$ contributes the square $f(x)^2$ of a real linear form. A conjugate pair contributes $f(z)^2+f(\bar z)^2=2(\operatorname{Re}f(z))^2-2(\operatorname{Im}f(z))^2$ : one positive and one negative square. The forms for distinct roots are independent (a Vandermonde argument).

Explore

The cubic x³ + px + q as a point (p, q). Drag it. Disc = 0, a cusp. The point snaps onto the curve when close.

Its roots in the complex plane. real complex

Worked example

Write down Hermite's form for $P=x^2+bx+c$ and check the theorem in every case.

Compute $N_0,N_1,N_2$ .

$N_0=2$ (the degree), $N_1=x_1+x_2=-b$ , and $N_2=(x_1+x_2)^2-2x_1x_2=b^2-2c$ .
Write the matrix and its determinant.

$\operatorname{Her}(P)=\begin{pmatrix}2&-b\\-b&b^2-2c\end{pmatrix},\qquad \det=2b^2-4c-b^2=b^2-4c=\operatorname{Disc}(P).$
Find the signature when $b^2-4c>0$ and when $b^2-4c<0$ .

The top-left entry is $2>0$ . If $\det>0$ , both eigenvalues are positive: signature 2, two real roots. If $\det<0$ , the eigenvalues have opposite signs: signature 0, rank 2, two complex roots.
And when $b^2=4c$ ?

$\det=0$ and the entry 2 is nonzero, so the rank is 1 and the signature 1: one distinct root, and it is real (the double root $-b/2$ ).

Check your understanding

A real cubic has $\operatorname{Disc}<0$ . What are its roots like?

One real root and a pair of complex conjugate roots.
Three real roots, one of them double.A multiple root makes the discriminant 0, not negative.
No real roots.An odd-degree real polynomial always has a real root.

The sign is

(-1)^{\#\text{pairs}}

: negative means exactly one conjugate pair. In the explorer, the unshaded region is

\operatorname{Disc}<0

.

$P$ has degree 4 and roots $1,1,i,-i$ . What are the rank and signature of $\operatorname{Her}(P)$ ?

Rank 4, signature 2Both numbers count distinct roots: multiplicity doesn't add anything.
Rank 3, signature 1
Rank 3, signature 2The double root $1$ is one distinct real root.

Distinct complex roots:

1, i, -i

, so rank 3. Distinct real roots: just

1

, so signature 1. The form is

2f(1)^2+f(i)^2+f(-i)^2

, and the pair gives one positive and one negative square.

A real polynomial of degree 4 with distinct roots has $\operatorname{Disc}>0$ . What can you conclude?

All four roots are real.Two conjugate pairs also give $(-1)^2=+1$ .
It has either 4 or 0 real roots.
It has exactly 2 real roots.That is one conjugate pair, which makes the discriminant negative.

The sign only records the parity of the number of conjugate pairs. To tell 4 from 0 you need more, for instance the signs of further subdiscriminants (the other principal minors of the Hermite matrix), or its signature.

Practice

The discriminant as a resultantA 3 × 3 Sylvester determinant

For $P=ax^2+bx+c$ , compute $\operatorname{Res}(P,P')$ as the determinant of the Sylvester matrix and compare with $b^2-4ac$ .

Hint

The rows are the coefficients of $P$ (once, since $\deg P'=1$ ) and of $P'=2ax+b$ (twice, shifted).

Solution

\det\begin{pmatrix}a&b&c\\2a&b&0\\0&2a&b\end{pmatrix}=ab^2-2ab^2+4a^2c=-a(b^2-4ac).

With $p=2$ , $(-1)^{p(p-1)/2}\operatorname{Res}(P,P')/a=b^2-4ac$ , the familiar discriminant.

Hermite's form of x⁴ − 1A 4 × 4 Hankel matrix

Compute the Newton sums $N_0,\dots,N_6$ of $x^4-1$ , write $\operatorname{Her}(P)$ , and find its rank and signature.

Solution

The roots are $\pm1,\pm i$ , so $N_k=4$ if $4\mid k$ and $0$ otherwise: $N_0=N_4=4$ , the rest 0. The matrix has $4$ at positions $(0,0)$ , $(2,2)$ , $(1,3)$ , $(3,1)$ . Its eigenvalues are $4,4,4,-4$ : rank 4 (four distinct roots), signature 2 (two real roots).

More practice: Basu–Pollack–Roy, Exercise 4.1.

InteractiveBasu–Pollack–Roy, Ch. 5: Decomposition of Semi-Algebraic Sets

Cylindrical decomposition

Any finite family of polynomials cuts $\R^k$ into finitely many cells on which each polynomial has constant sign, stacked in cylinders over a decomposition of $\R^{k-1}$ . In the plane you can watch the whole construction: project to find the critical values, cut the line, lift.

The idea

Semi-algebraic set. A subset of

R^k

defined by a boolean combination of conditions

P>0

and

P=0

with polynomials

P

.

Cylindrical decomposition. A sequence of partitions of

R^1,R^2,\dots,R^k

into cells. In

R^1

the cells are points and open intervals. Over each cell

C

of

R^{i}

there are continuous semi-algebraic functions

\xi_1<\dots<\xi_\ell

on

C

, and the cells of

R^{i+1}

above

C

are their graphs (sections) and the bands between consecutive ones (sectors, with

\xi_0=-\infty

,

\xi_{\ell+1}=+\infty

). It is adapted to a family

\mathcal P

if every

P\in\mathcal P

has constant sign on every cell.

Theorem. Every finite family of polynomials has an adapted cylindrical decomposition. Hence every semi-algebraic set is a finite union of cells.

In the plane, with $P,Q\in R[x][y]$ : over an interval of $x$ avoiding the real roots of the following, the real roots in $y$ move continuously and keep their number and order:

the leading coefficients in $y$ (a root escapes to infinity),
the discriminants in $y$ (two roots of the same polynomial meet),
the resultant of $P$ and $Q$ in $y$ (a root of $P$ meets a root of $Q$ ).

In higher degree the projection uses all the subresultant coefficients, which also detect, say, when two roots become a double root before turning complex. Then one recurses on the polynomials in $x$ .

Consequences. A semi-algebraic set has finitely many connected components, each semi-algebraic; its dimension is the largest dimension of a cell in it; closed and bounded ones can be triangulated (all in Ch. 5).

Explore

P = 0 Q = 0 · dashed lines: the critical values ξ · dots: one sample point per cell (bigger dots are 0-cells). Point at a cell to highlight it.

Polynomials

Parameter Show a sample point in every cell

Worked example

Build a cylindrical decomposition of $\R^2$ adapted to $P=x^2+y^2-1$ , count its cells, and describe the closed disk $P\le0$ as a union of cells.

Project: which values of $x$ are critical?

The leading coefficient in $y$ is 1, with no roots. The discriminant in $y$ of $y^2+(x^2-1)$ is $-4(x^2-1)$ , with roots $x=\pm1$ . So the line is cut into $(-\infty,-1)$ , $\{-1\}$ , $(-1,1)$ , $\{1\}$ , $(1,\infty)$ .
Lift: how many cells lie over each of the five?

Over $|x|>1$ : no roots in $y$ , so one cell (the whole strip). Over $x=\pm1$ : one root $y=0$ , so three cells (a point and two vertical half-lines). Over $(-1,1)$ : two roots $\pm\sqrt{1-x^2}$ , so five cells (three sectors, two arcs). In all $1+3+5+3+1=13$ .
Which cells make up the closed disk?

The two points $(\pm1,0)$ , the lower and upper open arcs over $(-1,1)$ , and the sector between them: five cells, on each of which $P\le0$ .
A check that comes back in the next module: add up $(-1)^{\dim}$ over these cells.

$2$ points $-\,2$ arcs $+\,1$ open disk $=1$ , the Euler characteristic of a closed disk. For the circle alone (points and arcs) you get $0$ .

Check your understanding

Why does the projection of $\{P,Q\}$ include the resultant of $P$ and $Q$ in $y$ ?

To find the vertical asymptotes.Roots escaping to infinity are detected by the leading coefficients.
To find where the curve $P=0$ has a vertical tangent or a singular point.Those come from the discriminant of $P$ .
At its roots a root of $P$ can meet a root of $Q$ in the fiber, which changes the order of roots and the sign pattern.

Without it, over an interval the curves of

P

and

Q

could cross, and a sector above that interval would contain points where

Q

has different signs. Try "Circle and line": the crossings sit exactly over roots of the resultant. Its roots can also be harmless, for example where the common root in

y

is not real: try "Two circles" with the circles apart.

What are the dimension and the number of connected components of $\{x^2+y^2<1\}\cup\{(2,0)\}$ ?

Dimension 2, two components
Dimension 2, one componentThe point $(2,0)$ is not connected to the disk.
It has no well-defined dimension, because it mixes a disk and a point.The dimension is the largest dimension of a cell, here 2.

A cylindrical decomposition adapted to

x^2+y^2-1

and

(x-2)^2+y^2

shows the set as a union of one 2-cell and one 0-cell. Connected components are unions of cells.

Over an open interval of the $x$ -axis the curves have 3 points above every $x$ . How many cells of the decomposition lie above that interval?

3Those are the sections; the bands between them are cells too.
4Those are the sectors; the curves themselves are cells too.
7

3 sections (1-dimensional) and 4 sectors (2-dimensional):

2\ell+1

cells for

\ell

roots.

Practice

A parabola and a lineCounting cells

Build a decomposition adapted to $P=y-x^2$ and $Q=y-1$ . How many cells are there, and what happens to the order of the two roots in each fiber?

Solution

Both are of degree 1 in $y$ with constant leading coefficients; the resultant is $\pm(x^2-1)$ , so the critical values are $\pm1$ . Over the three open intervals there are two roots ( $y=x^2$ and $y=1$ ), giving 5 cells each; over $x=\pm1$ the roots coincide, giving 3 cells each. Total $15+6=21$ . For $|x|>1$ the line is below the parabola, for $|x|<1$ above it.

Why leading coefficients matterA root running away

For $P=xy-1$ , find the projection, the cells, and explain what goes wrong if you don't cut the $x$ -axis at $0$ .

Solution

The leading coefficient in $y$ is $x$ , with root 0 (there is no discriminant for degree 1). Over $x\neq0$ there is one root $y=1/x$ : 3 cells over each half-line; over $x=0$ there is none: 1 cell. Total 7. Over all of $\R$ the number of roots is not constant, because the root escapes to infinity as $x\to0$ , so no single stack of cells would work.

Draw it yourselfBasu–Pollack–Roy, Ch. 6: Elements of Topology

Homology and the Euler characteristic

Betti numbers count components, independent loops and cavities. For a space built from triangles they come from linear algebra, and their alternating sum is $V-E+F$ . Build complexes on the grid and watch the numbers.

The idea

Simplicial homology. For a simplicial complex

K

, the chain space

C_i

is the

\mathbb Q

-vector space with a basis of oriented

i

-simplices. The boundary map is

\partial[v_0v_1]=v_1-v_0

,

\partial[v_0v_1v_2]=[v_1v_2]-[v_0v_2]+[v_0v_1]

, and so on, with

\partial\circ\partial=0

. Then

H_i(K)=\ker\partial_i/\operatorname{im}\partial_{i+1}

and

b_i=\dim H_i

.

$b_0$ is the number of connected components; $b_1$ the number of independent loops that do not bound; $b_2$ the number of enclosed cavities.

Euler–Poincaré.

\chi(K)=\sum_i(-1)^i\#\{i\text{-simplices}\}=\sum_i(-1)^ib_i

. This is rank–nullity applied to each

\partial_i

.

For semi-algebraic sets. A closed and bounded semi-algebraic set has a semi-algebraic triangulation (Ch. 5), and its homology is defined through it. It doesn't depend on the triangulation, and it is invariant under semi-algebraic homotopy equivalence. For sets that are only locally closed, Borel–Moore homology gives an Euler characteristic that is additive:

\chi(S)=\sum_C(-1)^{\dim C}

over the cells of any decomposition. So

\chi(\text{point})=1

and

\chi(\text{open interval})=-1

.

Mayer–Vietoris. For closed

A,B

:

\chi(A\cup B)=\chi(A)+\chi(B)-\chi(A\cap B)

, coming from a long exact sequence relating the homology of

A

,

B

,

A\cap B

and

A\cup B

.

Explore

Click or drag across triangles to fill them; click close to an edge or a vertex to add just that. Clicking something already there removes it, with everything it is a face of.

Start from

Worked example

Compute the homology of the boundary of a triangle (vertices $a,b,c$ , edges $ab,bc,ca$ ), then of the filled triangle.

Write the matrix of $\partial_1:C_1\to C_0$ and find its rank.

$\partial[ab]=b-a$ , $\partial[bc]=c-b$ , $\partial[ca]=a-c$ . The three images add to 0, and any two are independent, so the rank is 2.
Deduce $b_0$ and $b_1$ for the boundary.

$b_0=\dim C_0-\operatorname{rank}\partial_1=3-2=1$ . $b_1=\dim\ker\partial_1=3-2=1$ (there is no $\partial_2$ ), spanned by the cycle $[ab]+[bc]+[ca]$ . It is a circle.
Add the 2-simplex $[abc]$ . What changes?

$\partial[abc]=[bc]-[ac]+[ab]=[ab]+[bc]+[ca]$ , exactly the cycle. So $\operatorname{im}\partial_2$ kills it: $b_1=0$ . And $\ker\partial_2=0$ , so $b_2=0$ . A disk.
Check Euler–Poincaré both times.

Boundary: $3-3=0=1-1$ . Filled: $3-3+1=1=1-0+0$ . Draw both in the explorer (the "Circle" and "Disk" starts give bigger versions of the same thing).

Check your understanding

A connected graph has 7 vertices and 9 edges. What is $b_1$ ?

2For a graph $\chi=V-E=b_0-b_1$ , with $b_0=1$ .
3
9Edges in a spanning tree don't create loops.

b_1=b_0-\chi=1-(7-9)=3

. A spanning tree uses 6 edges, and each of the other 3 closes one independent loop.

With the additive (Borel–Moore) Euler characteristic, what is $\chi$ of the open interval $(0,1)$ ?

1That's the closed interval. The additive $\chi$ is not a homotopy invariant for sets that aren't closed and bounded.
$-1$
0Use additivity: $[0,1]$ is two points and the open interval.

\chi([0,1])=1=\chi(\{0\})+\chi(\{1\})+\chi((0,1))=2+\chi((0,1))

. In general an open

d

-cell has

\chi=(-1)^d

, which is what makes

\chi

computable from a cylindrical decomposition.

The boundary of a tetrahedron is a triangulation of the sphere $S^2$ . What is $\chi(S^2)$ ?

2
0Count: 4 vertices, 6 edges, 4 triangles.
1That's the disk. The sphere has $b_2=1$ : the cavity inside.

4-6+4=2=b_0-b_1+b_2=1-0+1

. A complex in the plane, like the ones in the explorer, can never enclose a cavity, so there

b_2=0

.

Practice

The annulus by Mayer–VietorisGluing two contractible pieces

Write the closed annulus $1\le x^2+y^2\le4$ as the union of its upper half $A$ ( $y\ge0$ ) and lower half $B$ ( $y\le0$ ). Find $\chi$ and $b_1$ .

Solution

$A$ and $B$ are contractible, so $\chi=1$ each. $A\cap B$ is two disjoint segments on the $x$ -axis, $\chi=2$ . So $\chi(A\cup B)=1+1-2=0$ . The annulus is connected, so $b_1=b_0-\chi=1$ (and $b_2=0$ ).

χ from cellsOpen disk, closed disk, circle

Using the 13-cell decomposition of the worked example in the previous module, compute the additive $\chi$ of the open disk, the circle, and the closed disk, and check that the first two add up to the third.

Solution

Open disk: one 2-cell, $\chi=1$ . Circle: two points and two arcs, $\chi=2-2=0$ . Closed disk: all five, $\chi=1$ . Indeed $1+0=1$ . (For the open disk, $1$ agrees with $\chi_{BM}(\R^2)=(-1)^2$ .)

More practice: Basu–Pollack–Roy, Exercises 6.1 and 6.3.

Interactive sweepBasu–Pollack–Roy, Ch. 7: Quantitative Semi-algebraic Geometry

Morse theory and Betti number bounds

How complicated can the zero set of a polynomial of degree $d$ be? Sweep a line across a curve: the topology of the part already swept changes only at critical points of the sweep. Counting those points bounds the Betti numbers, and Bézout's theorem counts them.

The idea

Critical points of a projection. Let

Z=\{Q=0\}\subset\R^k

be bounded and non-singular (

\nabla Q\neq0

on

Z

), and let

\pi

be the projection to the

x_1

-axis. A point of

Z

is critical for

\pi

when

\partial Q/\partial x_2=\dots=\partial Q/\partial x_k=0

there: the tangent space is vertical.

\pi

is a Morse function if these points are non-degenerate (and their values distinct).

Morse lemmas. If

[a,b]

contains no critical value,

Z_{\le a}=Z\cap\{x_1\le a\}

and

Z_{\le b}

are (semi-algebraically) homotopy equivalent. Passing a non-degenerate critical point of index

\lambda

attaches a

\lambda

-cell, which changes one Betti number by one.

Consequence: $b(Z)=\sum_ib_i(Z)\le$ the number of critical points of $\pi$ on $Z$ . For a curve in the plane: each oval contributes $b_0=b_1=1$ , and has at least two critical points, its leftmost and rightmost.

Oleinik–Petrovskii, Thom, Milnor. An algebraic set in

\R^k

defined by polynomials of degree at most

d

has

b\le d(2d-1)^{k-1}

.

The proof perturbs the set into a bounded non-singular hypersurface (with infinitesimals from module 4), then counts the critical points, which are the solutions of a system of $k$ polynomial equations, with Bézout's theorem. Similar arguments bound the Betti numbers of sets defined by $s$ polynomials by $(O(sd))^k$ : a single exponential in $k$ .

Explore

the part with x ≤ t critical points of x on the curve (red once passed)

Curve f(x, y) = c

Level c Sweep line x = t

Worked example

For the curve $(x^2-1)^2+y^2=c$ ("Double well"), find the critical points of $x$ and compare their number with $b_0+b_1$ , for $0<c<1$ and for $c>1$ .

Write the condition for a critical point of $x$ on the curve.

With $Q=(x^2-1)^2+y^2-c$ , the condition is $Q=0$ and $\partial Q/\partial y=2y=0$ . So $y=0$ and $(x^2-1)^2=c$ .
Solve it for $0<c<1$ .

$x^2=1\pm\sqrt c$ , both positive, so four points $x=\pm\sqrt{1+\sqrt c},\ \pm\sqrt{1-\sqrt c}$ on the $x$ -axis.
What is the topology, and is the bound sharp?

Two ovals, one around each well: $b_0=b_1=2$ , so $b_0+b_1=4$ , equal to the number of critical points. Each oval has exactly its leftmost and rightmost point.
Now $c>1$ . And how does this compare with Milnor's bound?

Only $x^2=1+\sqrt c$ is positive: 2 critical points, one oval, $b_0+b_1=2$ . Milnor's bound for degree 4 in the plane is $4\cdot7=28$ : true but generous. Sweep the line in the explorer and watch the left part change only at the critical points.

Check your understanding

A smooth bounded curve in the plane has 10 critical points for the projection to $x$ . At most how many ovals can it have?

5
10One critical point per oval is impossible: $x$ has both a maximum and a minimum on each.
20Each oval uses up at least two critical points, not half of one.

x

attains a minimum and a maximum on each compact oval, and they are different points. So ovals

\le10/2

. In Betti terms,

b_0+b_1=2\cdot\#\text{ovals}\le10

.

You sweep $x=t$ across a smooth curve. Between two consecutive critical values, what can happen to the part with $x\le t$ ?

A new arc can appear at any moment.A new arc starts at a leftmost point of an oval, which is a critical point.
Nothing topological: it only stretches.
Two arcs can join into one.Two arcs meet at a rightmost point of an oval, again a critical point.

That is the first Morse lemma: without critical values in

[a,b]

the parts below

a

and below

b

are homotopy equivalent. All changes happen at critical points.

Which bound on $b_0+b_1$ holds for every curve in $\R^2$ defined by one polynomial of degree $d$ ?

$d$ The "Four wells" curve has degree 4 and $b_0+b_1=8$ at small levels.
$d(2d-1)$
None in terms of $d$ alone.The Milnor bound depends only on $d$ and the dimension.

With

k=2

,

d(2d-1)^{k-1}=d(2d-1)

. For curves there are sharper classical results (Harnack's bound on the number of ovals), but this bound has the right shape in every dimension.

Practice

Four wellsCritical points and ovals

For $(x^2-1)^2+(y^2-1)^2=c$ with $0<c<1$ , find all critical points of $x$ on the curve and the Betti numbers of the curve.

Solution

$\partial/\partial y=4y(y^2-1)=0$ gives $y\in\{0,\pm1\}$ . With $y=0$ : $(x^2-1)^2=c-1<0$ , nothing. With $y=\pm1$ : $(x^2-1)^2=c$ , so $x^2=1\pm\sqrt c$ : four values of $x$ for each, 8 points. The curve is four ovals around $(\pm1,\pm1)$ : $b_0+b_1=8$ , equal to the count.

Which Betti number changesThe index of a critical point

Sweep $x=t$ across the circle $x^2+y^2=1$ . Describe the part with $x\le t$ for $t<-1$ , $-1<t<1$ , $t>1$ , and say which Betti number changes at each critical point.

Solution

Empty, then an arc (contractible: $b_0=1$ ), then the whole circle ( $b_0=b_1=1$ ). At $(-1,0)$ , a minimum (index 0), a point is born: $b_0$ goes from 0 to 1. At $(1,0)$ , a maximum (index 1 for a curve), the two ends of the arc are joined by a 1-cell: $b_1$ goes from 0 to 1.

More practice: Basu–Pollack–Roy, Exercises 7.1 and 7.2.

SimulatorBasu–Pollack–Roy, Ch. 8: Complexity of Basic Algorithms

Subresultants and bit size

Counting arithmetic operations is not the whole story. Euclid's algorithm on integer polynomials can produce numbers with exponentially many digits. Subresultants compute the same sequence, up to constant factors, with numbers whose size grows only linearly. Generate random pairs and compare.

The idea

Complexity. The arithmetic complexity of an algorithm counts additions, multiplications and comparisons in the ring of coefficients. The bit complexity also accounts for the size of the numbers: with integer inputs of bitsize

\tau

, one wants the intermediate numbers to stay of size polynomial in

\tau

and the degree.

Hadamard's bound.

|\det M|\le\prod_i\lVert M_i\rVert

, the product of the Euclidean lengths of the rows. So an

n\times n

integer determinant with entries of bitsize

\tau

has bitsize at most about

n\tau+\tfrac n2\log_2n

.

Bareiss elimination. Gaussian elimination where step

k

replaces

m_{ij}

by

(m_{kk}m_{ij}-m_{ik}m_{kj})/p

, with

p

the previous pivot. The division is exact, and every intermediate entry is a minor of the original matrix, so Hadamard's bound controls all of them.

Subresultants. The

j

-th subresultant of

P

and

Q

is a polynomial of degree at most

j

whose coefficients are determinants of submatrices of the Sylvester matrix. The structure theorem says each signed remainder of

P

and

Q

is a constant multiple of one of them, and the constants (with their signs) are known along the way. So Sturm sequences and Cauchy indices can be computed from subresultants.

Cost. All subresultants of two polynomials of degree at most

p

take

O(p^2)

arithmetic operations, and each coefficient, being a determinant, has bitsize

O(p(\tau+\log p))

.

Explore

Degree of A (B has one less) Coefficient size

Size of the largest number in each remainder R_k (log scale). Euclid over ℚ (numerator + denominator) pseudo-remainders primitive parts (dashed) subresultants

Worked example

Compute $\det\begin{pmatrix}2&1&3\\1&3&2\\3&2&1\end{pmatrix}$ by Bareiss elimination, and compare with Hadamard's bound.

First step, pivot $2$ , previous pivot $1$ . Compute the new lower-right $2\times2$ block.

$m_{22}=2\cdot3-1\cdot1=5$ , $m_{23}=2\cdot2-1\cdot3=1$ , $m_{32}=2\cdot2-3\cdot1=1$ , $m_{33}=2\cdot1-3\cdot3=-7$ .
Second step, pivot $5$ , previous pivot $2$ .

$m_{33}=(5\cdot(-7)-1\cdot1)/2=-36/2=-18$ . The division is exact, and $-18$ is the determinant.
Why are the divisions always exact?

After step $k$ , the entry $m_{ij}$ equals the minor of the original matrix on rows $1,\dots,k,i$ and columns $1,\dots,k,j$ (Sylvester's identity). For instance $m_{22}=5=\det\begin{pmatrix}2&1\\1&3\end{pmatrix}$ . Minors are integers.
Compare with Hadamard's bound.

Every row has length $\sqrt{14}$ , so $|\det|\le14^{3/2}\approx52.4$ . Indeed $18\le52.4$ , and no intermediate entry can exceed the corresponding bound for its minor.

Check your understanding

Why do pseudo-remainder sequences over $\Z$ blow up?

Because they introduce denominators.Pseudo-division is designed to avoid denominators: it multiplies by a power of the leading coefficient first.
Each step multiplies by a power of a leading coefficient, and these factors compound from step to step.
Because the degrees go up.Degrees go down at every step, in every version of the algorithm.

The factor

\operatorname{lc}(B)^{\deg A-\deg B+1}

enters the next remainder, which becomes the next divisor, whose leading coefficient is raised to a power again. Sizes roughly double per step. Subresultants divide out exactly the predictable part of these factors.

An $n\times n$ integer matrix has entries of bitsize at most $\tau$ . About how big can its determinant be?

About $n\tau+\tfrac n2\log_2 n$ bits
About $\tau^n$ bitsSizes add when you multiply numbers; they don't multiply.
About $2^n\tau$ bitsExponential growth in bitsize is the pseudo-remainder disease, not a property of determinants.

Each row has length at most

\sqrt n\,2^\tau

, and Hadamard's bound multiplies

n

of them. That is why algorithms whose intermediate numbers are minors, like Bareiss and subresultants, have polynomial bit complexity.

How are the subresultants of $P$ and $Q$ related to the signed remainder sequence?

Each signed remainder is a known constant multiple of a subresultant, so the subresultants carry the same information with small coefficients.
Only the last subresultant, the resultant, is related to the remainders.The structure theorem relates every remainder to a subresultant, not only the last one.
They have different degrees, so they compute different things.The degrees match: a subresultant proportional to a remainder has the same degree.

In the explorer all four methods produce the same sequence up to scaling; the curves differ only in how big the numbers are.

Practice

Three sequences for one pairPseudo-remainders and subresultants

For $A=x^3+x+1$ and $B=3x^2+1$ , compute the pseudo-remainder sequence and the subresultant sequence. (In the Collins–Brown form of the subresultant algorithm, with all degree gaps equal to 1, the first pseudo-remainder is kept and the second is divided by $\operatorname{lc}(B)^2$ .) Compare the last term with $\operatorname{Res}(A,B)$ .

Hint

$\operatorname{prem}(A,B)$ is the remainder of $3^2A$ by $B$ .

Solution

$\operatorname{prem}(A,B)=9A-3x\,B=6x+9$ , then $\operatorname{prem}(B,6x+9)=36\,B(-\tfrac32)=279$ . The subresultant sequence keeps $6x+9$ and divides $279$ by $3^2$ : it gives $31$ . And $\operatorname{Res}(A,B)=31$ ( $\operatorname{Disc}(A)=-31$ ). Primitive parts would give $2x+3$ and $31$ , at the price of gcd computations.

Bounding a resultantHadamard on a Sylvester matrix

$P$ and $Q$ are quadratics with integer coefficients of absolute value at most 10. Bound $|\operatorname{Res}(P,Q)|$ .

Solution

The Sylvester matrix is $4\times4$ and each row contains the three coefficients of $P$ or of $Q$ and a zero, so each row has length at most $\sqrt{300}$ . Hadamard gives $|\operatorname{Res}|\le300^2=90000$ .

More practice: Basu–Pollack–Roy, Exercises 8.1 and 8.2.

InteractiveBasu–Pollack–Roy, Ch. 9: Cauchy Index and Applications

Cauchy index and stability

A linear system is stable when every root of its characteristic polynomial has negative real part. You can decide that from the coefficients alone: restricted to the imaginary axis, the question becomes a Cauchy index, a real root counting problem, and the Routh array computes it.

The idea

Cauchy index.

\operatorname{Ind}(Q/P;a,b)

is the number of poles in

(a,b)

where

Q/P

jumps from

-\infty

to

+\infty

, minus the number where it jumps from

+\infty

to

-\infty

. For instance

\operatorname{Ind}(P'/P)

is the number of distinct real roots of

P

.

Computing it. If

a,b

are not roots of

P

,

\operatorname{Ind}(Q/P;a,b)=\operatorname{Var}(a)-\operatorname{Var}(b)

for the signed remainder sequence of

P

and

Q

. (Sturm's theorem is the case

Q=P'

.)

Hankel form. Expand

Q/P=\sum_{k\ge0}s_k\,x^{-k-1}

at infinity. The quadratic form with Hankel matrix

(s_{j+k})_{0\le j,k<p}

has signature

\operatorname{Ind}(Q/P;-\infty,+\infty)

. With

Q=P'

the

s_k

are Newton sums: that is Hermite's form again.

Stability. Write

P(iy)

, for real

y

, in terms of its real and imaginary parts, two real polynomials built from the even and the odd coefficients of

P

. If

P

has no root on the imaginary axis, the difference between the numbers of roots with negative and with positive real part is (up to a sign convention) the Cauchy index of their ratio on

(-\infty,+\infty)

.

Routh's rule. For real

P=a_0s^n+a_1s^{n-1}+\dots+a_n

with

a_0>0

, build rows

(a_0,a_2,\dots)

,

(a_1,a_3,\dots)

, and each new row

(c_0,c_1,\dots)

from the two rows

(u_0,u_1,\dots)

and

(v_0,v_1,\dots)

just above it by

c_j=(v_0u_{j+1}-u_0v_{j+1})/v_0

(missing entries count as 0). If no entry of the first column is

0

, the number of sign changes down the first column is the number of roots with positive real part.

A quick necessary condition. A stable real polynomial is a product of factors

s+r

and

s^2+2us+u^2+v^2

with

r,u>0

, so all its coefficients have the same sign.

Explore

real roots complex pairs · the shaded side is Re s > 0

Examples

Worked example

For which real $k$ is $P=s^3+2s^2+3s+k$ stable?

Write the first two rows of the Routh array.

$(1,\ 3)$ and $(2,\ k)$ .
Compute the remaining rows.

Third row: $(2\cdot3-1\cdot k)/2=(6-k)/2$ . Fourth row: $\big(\tfrac{6-k}2\cdot k-2\cdot0\big)/\tfrac{6-k}2=k$ (when $k\neq6$ ). First column: $1,\ 2,\ \tfrac{6-k}2,\ k$ .
Read off the condition.

No sign change iff $6-k>0$ and $k>0$ : stable exactly for $0<k<6$ . For $k>6$ the column is $+,+,-,+$ : two roots with positive real part. For $k<0$ : $+,+,+,-$ , one.
What happens at $k=6$ ?

A zero appears in the first column. Indeed $s^3+2s^2+3s+6=(s+2)(s^2+3)$ , with roots $\pm i\sqrt3$ on the imaginary axis: exactly the boundary between stable and unstable.

Check your understanding

A real cubic has coefficients $1,3,-2,5$ (leading first). Can it be stable?

No: the coefficients don't all have the same sign.
Yes, if the Routh array has no sign change.With a negative coefficient that cannot happen; stability forces all coefficients positive.
You can't tell without computing the roots.The quick necessary condition already settles it.

Multiplying factors

s+r

and

s^2+2us+u^2+v^2

with

r,u>0

only produces positive coefficients.

The first column of a Routh array is $1,4,-1,2,3$ . How many roots have positive real part?

1Going into the negative entry is one change and coming out of it is another.
2
3Count the sign changes, not the entries.

+,+,-,+,+

has two sign changes. Degree 4, so the other two roots have negative real part (no zero appeared, so none is on the axis).

For $P=(x-1)^2(x+3)$ , what is $\operatorname{Ind}(P'/P;-\infty,+\infty)$ ?

3Multiplicity changes the size of the pole of $P'/P$ , not the direction of its jump.
2
1Both roots are poles of $P'/P$ with a jump from $-\infty$ to $+\infty$ .

Near a root

c

of multiplicity

m

,

P'/P\approx m/(x-c)

: it jumps from

-\infty

to

+\infty

for every

m\ge1

. So the index counts distinct real roots.

Practice

Degree twoStability by hand

Show that $s^2+a_1s+a_2$ (real coefficients) is stable iff $a_1>0$ and $a_2>0$ , first from the roots and then from the Routh array.

Solution

Roots: their sum is $-a_1$ and their product $a_2$ . Two real roots are both negative iff the sum is negative and the product positive. A complex pair has real part $-a_1/2$ , negative iff $a_1>0$ , and then $a_2=|z|^2>0$ automatically. Routh: the rows are $(1,a_2)$ , $(a_1)$ , $(a_2)$ , and the column $1,a_1,a_2$ has no sign change iff $a_1,a_2>0$ .

A quarticPositive coefficients are not enough

How many roots of $s^4+2s^3+3s^2+4s+5$ have positive real part?

Solution

Rows: $(1,3,5)$ , $(2,4)$ , $(1,5)$ , $(-6)$ , $(5)$ . The first column $1,2,1,-6,5$ changes sign twice: two roots with positive real part (numerically $0.288\pm1.416i$ ), although every coefficient is positive.

More practice: Basu–Pollack–Roy, Exercise 9.3.

Step-throughBasu–Pollack–Roy, Ch. 10: Real Roots

Isolating real roots

To compute with a real algebraic number you have to pin it down: an interval with rational endpoints that contains it and no other root. Bisection guided by Descartes' rule does this with exact rational arithmetic only. Step through it.

The idea

Cauchy bound. Every complex root of

P=a_px^p+\dots+a_0

satisfies

|x|<1+\max_{i<p}|a_i/a_p|

. So all real roots lie in a known interval

(-B,B)

.

Descartes on an interval. The map

x\mapsto(\ell+rx)/(1+x)

sends

(0,\infty)

onto

(\ell,r)

. Put

T(x)=(1+x)^pP\big((\ell+rx)/(1+x)\big)

. Its positive roots correspond to the roots of

P

in

(\ell,r)

, so

\operatorname{Var}(T)

bounds their number, with even excess. The coefficients of

T

are, up to positive factors, the Bernstein coefficients of

P

on

[\ell,r]

.

Theorem of three circles. For

P

without multiple roots: if no complex root lies in the open disk with diameter

[\ell,r]

, then

\operatorname{Var}(T)=0

; if exactly one root lies in the union of the two open disks bounded by the circumcircles of the two equilateral triangles with side

[\ell,r]

, then

\operatorname{Var}(T)=1

.

So bisection terminates: small intervals far from every root give 0, and small intervals around a single real root give 1. Its cost is governed by how close distinct roots can be, which for integer polynomials is bounded below in terms of the degree and the bitsize.

Multiple roots. Near a double root

\operatorname{Var}

never drops below 2. So one first replaces

P

by its square-free part

P/\gcd(P,P')

, which has the same roots, all simple.

Thom encodings and sign determination. A real root can also be named exactly by the signs of

P',P'',\dots

at it (module 14). With Tarski queries (module 3) one determines the sign of another polynomial

Q

at each root of

P

, without ever approximating the roots.

Explore

P(x)

Examples

Top: P (compressed vertical scale). Below: the intervals tested, one row per bisection depth, labelled with Var. exactly one root no root bisect waiting

Worked example

Isolate the real roots of $P=x^2-2$ by the bisection method.

Find a starting interval.

The Cauchy bound is $1+2=3$ ; round up to a power of 2: $(-4,4)$ .
Test $(-4,4)$ .

$T=(1+x)^2P\big(\tfrac{-4+4x}{1+x}\big)=(4x-4)^2-2(1+x)^2=14x^2-36x+14$ . Signs $+,-,+$ : $\operatorname{Var}=2$ . Inconclusive, so bisect at 0, which is not a root.
Test $(-4,0)$ and $(0,4)$ .

On $(-4,0)$ : $T=16-2(1+x)^2=-2x^2-4x+14$ , signs $-,-,+$ , $\operatorname{Var}=1$ . On $(0,4)$ : $T=16x^2-2(1+x)^2=14x^2-4x-2$ , signs $+,-,-$ , $\operatorname{Var}=1$ . Each contains exactly one root.
What has been computed, and what would you do to get more digits?

Isolating intervals $(-4,0)\ni-\sqrt2$ and $(0,4)\ni\sqrt2$ . To refine, bisect an isolating interval and keep the half where $P$ changes sign: $P(2)=2>0$ , $P(1)=-1<0$ , so $\sqrt2\in(1,2)$ , and so on.

Check your understanding

On some interval the transformed polynomial has $\operatorname{Var}=2$ . What do you know?

There are exactly 2 roots in the interval.Descartes gives a bound with even excess, not an exact count.
There is at least one root in the interval. $2-2=0$ is allowed: a complex pair near the interval can produce both variations.
There are 0 or 2 roots there, so the interval must be bisected.

Only

\operatorname{Var}=0

and

\operatorname{Var}=1

are conclusive. For example

x^2+1

on

(-2,2)

gives

T=(2x-2)^2+(1+x)^2=5x^2-6x+5

:

\operatorname{Var}=2

, and no real root at all.

Why does the method work with the square-free part of $P$ ?

Because Descartes' rule is false for polynomials with multiple roots.It holds, counting multiplicities; that's exactly why a double root keeps $\operatorname{Var}\ge2$ .
Because near a multiple root the count never drops to 1, so bisection would never stop.
Because the square-free part has smaller coefficients.It often does not; the point is termination.

P/\gcd(P,P')

has the same roots, each simple. Try

(x^2-2)(x-1)^2

: the explorer uses

(x^2-2)(x-1)

.

What is the Cauchy bound for $2x^3-6x+1$ ?

4
7Divide by the leading coefficient first: the ratios are $3$ and $\tfrac12$ .
3It is 1 plus the largest ratio.

1+\max(|{-6}/2|,|1/2|)=1+3=4

. All roots (in fact about

-1.81

,

0.17

,

1.64

) lie in

(-4,4)

.

Practice

The golden ratioOne test per root

For $P=x^2-x-1$ , compute $\operatorname{Var}(T)$ on $(0,2)$ and on $(-1,0)$ .

Solution

On $(0,2)$ : $T=(1+x)^2P\big(\tfrac{2x}{1+x}\big)=4x^2-2x(1+x)-(1+x)^2=x^2-4x-1$ , $\operatorname{Var}=1$ : one root, $\tfrac{1+\sqrt5}2\approx1.618$ . On $(-1,0)$ : $T=1+(1+x)-(1+x)^2=-x^2-x+1$ , $\operatorname{Var}=1$ : one root, $\tfrac{1-\sqrt5}2\approx-0.618$ .

Naming roots by derivative signsThom encodings

The roots of $P=x^3-3x+1$ are about $-1.879$ , $0.347$ , $1.532$ . Give the signs of $P'$ and $P''$ at each, and check that no two roots get the same pair.

Solution

$P'=3x^2-3$ is positive at $-1.879$ and $1.532$ , negative at $0.347$ . $P''=6x$ is negative at $-1.879$ and positive at the other two. Codes: $(+,-)$ , $(-,+)$ , $(+,+)$ , all different. The "A cubic and its derivative" example in module 14 shows this table.

InteractiveBasu–Pollack–Roy, Ch. 11: Cylindrical Decomposition Algorithm · Ch. 14: Quantifier Elimination

Quantifier elimination

Tarski's theorem: every statement about real numbers built from polynomial equations, inequalities, logical connectives and quantifiers is equivalent to one without quantifiers. Here is the smallest interesting case, a quadratic with two parameters, and four questions about it.

The idea

Tarski–Seidenberg. For every formula

\Phi(Y)

of the language of ordered fields (with quantified variables

X

and free variables

Y

) there is a quantifier-free formula

\Psi(Y)

equivalent to it over every real closed field. Geometrically: the projection of a semi-algebraic set is semi-algebraic (Ch. 2). In particular the truth of sentences is decidable, and the same in every real closed field.

By cylindrical decomposition (Ch. 11). Decompose the space of

(Y,X)

cylindrically, with

Y

first, adapted to the polynomials of

\Phi

. On each cell the quantifier-free part of

\Phi

has a constant truth value. Then, over each cell of

Y

-space,

\exists X

holds iff it holds at some cell above, and

\forall X

iff at all of them: one sample point per cell decides.

\Psi

is the union of the good

Y

-cells, described by sign conditions on the projection polynomials.

Cost. Cylindrical decomposition takes

(sd)^{2^{O(k)}}

operations for

s

polynomials of degree

d

in

k

variables: doubly exponential. Some doubly exponential cost is unavoidable for quantifier elimination in general, because there are formulas whose shortest quantifier-free equivalent is that long (Davenport and Heintz, 1988).

Critical point methods (Ch. 14). Deciding a sentence whose

k

variables are split into

\omega

blocks of sizes

k_1,\dots,k_\omega

(alternating

\exists

and

\forall

) costs

s^{(k_\omega+1)\cdots(k_1+1)}d^{O(k_\omega)\cdots O(k_1)}

. With few alternations this is singly exponential in

k

. Quantifier elimination has a similar bound, with the free variables counted as one more block.

Explore

Question about f(x) = x² + bx + c

Parameters (b, c): drag the point. where the formula is true. The curves are the projection polynomials: b² − 4c c 1 + b + c b, b + 2

The quadratic for the current (b, c). The shaded strip is the range of x the formula talks about. a witness a counterexample

Worked example

Eliminate the quantifier in $\exists x\ (x>0\wedge x^2+bx+c=0)$ .

What is needed for any real root at all?

$b^2-4c\ge0$ . The two roots then have product $c$ and sum $-b$ .
Case $c<0$ .

Then $b^2-4c>0$ automatically, and the product of the roots is negative: one is positive. The formula holds.
Cases $c>0$ and $c=0$ .

$c>0$ : the roots (if real) have the same sign, the sign of their sum $-b$ . So we need $b<0$ and $b^2-4c\ge0$ . $c=0$ : the roots are $0$ and $-b$ , so we need $b<0$ (and then $b^2-4c=b^2\ge0$ ).
Combine, and compare with what a decomposition would see.

$\exists x\ (x>0\wedge x^2+bx+c=0)\iff c<0\ \vee\ (b<0\wedge b^2-4c\ge0).$

Only the signs of $b^2-4c$ , $c$ and $b$ appear: the discriminant, the value at the boundary point $x=0$ , and the coefficient that locates the vertex. Their zero sets cut the $(b,c)$ -plane into cells on which the answer is constant. Choose the third question in the explorer to see them.

Check your understanding

Over $\R$ , $\forall x\ (x^2+bx+c\ge0)$ is equivalent to:

$b^2-4c<0$ When $b^2=4c$ the parabola touches 0 but stays $\ge0$ , so the boundary belongs.
$b^2-4c\le0$
$c\ge0$ That's the condition at $x=0$ only: necessary, not sufficient.

The minimum is

c-b^2/4

, at

x=-b/2

. Strict versus non-strict inequalities in the quantified formula show up as strict versus non-strict in the answer.

Why does one sample point per cell suffice to decide a formula?

Because cells are convex.They need not be; the arcs of a circle are cells.
Because every polynomial in the formula has constant sign on each cell, so the quantifier-free part has a constant truth value there.
Because the formula is linear in the parameters.Here the answer involves $b^2-4c$ ; nothing is linear.

Truth of the quantifier-free part depends only on the signs of its polynomials. Being adapted to those polynomials is exactly what the decomposition guarantees, and cylindricity lets you read off

\exists

and

\forall

fiber by fiber.

For a sentence with a single block of $k$ existential variables, what do critical point methods gain over cylindrical decomposition?

A cost of $s^{k+1}d^{O(k)}$ , singly exponential in $k$ , instead of doubly exponential.
Polynomial time in $k$ .Still exponential in $k$ , just not doubly so.
Nothing for a fixed number of variables.For fixed $k$ both are polynomial in $s$ and $d$ , but the exponents are very different: $O(k)$ against $2^{O(k)}$ .

With

\omega=1

the general bound reads

s^{k+1}d^{O(k)}

. The price of each extra quantifier alternation is another factor in the exponent.

Practice

Positive on an intervalNegating a formula

Eliminate the quantifier in $\forall x\ \big(0\le x\le1\Rightarrow x^2+bx+c>0\big)$ . Use the fourth question of the explorer.

Hint

This is the negation of $\exists x\ (0\le x\le1\wedge x^2+bx+c\le0)$ .

Solution

The explorer's answer for the existential formula is $c\le0\vee1+b+c\le0\vee(-2\le b\le0\wedge b^2-4c\ge0)$ : the minimum on $[0,1]$ is at $0$ , at $1$ , or at the vertex $-b/2$ . Negating:

c>0\ \wedge\ 1+b+c>0\ \wedge\ \big(b<-2\ \vee\ b>0\ \vee\ b^2-4c<0\big).

Two sentencesEliminate the inner quantifier first

Decide $\forall y\ \exists x\ (x^2+xy+1=0)$ and $\exists y\ \forall x\ (x^2+xy+1>0)$ .

Solution

$\exists x\,(x^2+yx+1=0)\iff y^2-4\ge0$ , and $\forall y\,(y^2\ge4)$ is false (take $y=0$ ). $\forall x\,(x^2+yx+1>0)\iff y^2-4<0$ , and $\exists y\,(y^2<4)$ is true. Each step is a one-variable elimination, which is what the algorithm does recursively.

More practice: Basu–Pollack–Roy, Exercises 2.14 and 14.1.

Worked exampleBasu–Pollack–Roy, Ch. 12: Polynomial System Solving

Solving polynomial systems

When a system has finitely many complex solutions, everything you want to know about them, their coordinates, how many are real, the sign of another polynomial at each, can be read off from linear algebra in a finite-dimensional ring. This module works one system through in full.

The idea

Gröbner basis. Fix a monomial order. A finite

G\subset I

is a Gröbner basis of the ideal

I

if the leading monomials of

G

generate the ideal of leading monomials of

I

. Then division by

G

gives a unique remainder (normal form), and

f\in I

iff its normal form is 0.

Zero-dimensional ideals.

I\subset K[X_1,\dots,X_k]

has finitely many solutions in

\C^k

iff

A=K[X]/I

is a finite-dimensional vector space. A basis is given by the monomials not divisible by any leading monomial of

G

, and

\dim A

is the number of solutions counted with multiplicity.

Stickelberger. Let

L_f:A\to A

be multiplication by

f

(its matrix is a multiplication table). The eigenvalues of

L_f

are the values

f(z)

at the complex solutions

z

, each repeated according to multiplicity.

Univariate representation. A linear form

u

is separating if it takes different values at different solutions. Then the characteristic polynomial of

L_u

has one root per solution, and each coordinate can be written as a rational function of that root. This reduces a system to one univariate polynomial, where the earlier modules apply.

Multivariate Hermite. The form

f\mapsto\operatorname{Tr}(L_{f^2Q})

on

A

has rank equal to the number of distinct complex solutions with

Q(z)\neq0

, and signature

\sum_{z\text{ real}}\operatorname{sign}Q(z)

. With

Q=1

: the signature is the number of real solutions.

Worked example

Solve the system $x^2+y^2=5,\ xy=2$ by these methods: find a Gröbner basis, the multiplication tables, the solutions, the number of real solutions, and how many have $x+y>0$ . Then see what changes for $x^2+y^2=1,\ xy=2$ .

Eliminate $y$ : find a polynomial in $x$ alone in the ideal.

Multiply the first equation by $x^2$ and use $(xy)^2=4$ : $x^4+4-5x^2$ . So $x^4-5x^2+4\in I$ .
Express $y$ in terms of $x$ modulo $I$ , and give a basis of $A$ .

From $x^4-5x^2+4=0$ we get $x(5x-x^3)=4$ , and $xy=2$ , so $y=(5x-x^3)/2$ . Indeed, for lex order with $y>x$ , a Gröbner basis is

$G=\{\,x^4-5x^2+4,\ \ 2y+x^3-5x\,\}.$

The leading monomials are $x^4$ and $y$ , so the monomials $1,x,x^2,x^3$ form a basis of $A$ : $\dim A=4$ .
Write $L_x$ in this basis and find its eigenvalues. Then get $y$ .

$x\cdot x^3=x^4=5x^2-4$ in $A$ , so $L_x$ is the companion matrix of $x^4-5x^2+4=(x^2-1)(x^2-4)$ , with eigenvalues $\pm1,\pm2$ . Since $L_y=(5L_x-L_x^3)/2$ , its eigenvalue on each eigenvector is $(5x-x^3)/2$ : the solutions are

$(1,2),\quad(2,1),\quad(-1,-2),\quad(-2,-1).$

Here $x$ happens to be separating, so this is already a univariate representation.
Count the real solutions with Hermite's form, without the solutions.

The entries are $\operatorname{Tr}(L_{x^{j+k}})=\sum_zx^{j+k}=N_{j+k}$ , here $4,0,10,0,34,0,130$ (from the companion matrix, or Newton's identities):

$\begin{pmatrix}4&0&10&0\\0&10&0&34\\10&0&34&0\\0&34&0&130\end{pmatrix}$

It splits into the blocks $\begin{pmatrix}4&10\\10&34\end{pmatrix}$ and $\begin{pmatrix}10&34\\34&130\end{pmatrix}$ , both with positive trace and determinants $36$ and $144$ . All four eigenvalues are positive: signature 4, so four real solutions.
How many solutions have $x+y>0$ ? Use the Tarski query of $Q=x+y$ .

The signature of $f\mapsto\operatorname{Tr}(L_{f^2Q})$ is $\sum\operatorname{sign}(x+y)=1+1-1-1=0$ , and $Q$ vanishes at no solution. With $c_++c_-=4$ and $c_+-c_-=0$ : $c_+=2$ . Only signs of traces were needed.
Now take $x^2+y^2=1,\ xy=2$ . What does Hermite's form say?

The same steps give $x^4-x^2+4$ and a basis $1,x,x^2,x^3$ . The Newton sums are $4,0,2,0,-14,0,-22$ , and the blocks $\begin{pmatrix}4&2\\2&-14\end{pmatrix}$ , $\begin{pmatrix}2&-14\\-14&-22\end{pmatrix}$ have negative determinants: one positive and one negative eigenvalue each. Signature 0: no real solutions, four complex ones. (Geometrically, $x^2+y^2\ge2|xy|=4$ on the hyperbola.)

Check your understanding

A zero-dimensional ideal $I\subset\mathbb Q[x,y]$ has $\dim\mathbb Q[x,y]/I=6$ . What do you know about its complex solutions?

There are exactly 6 distinct ones.Multiple solutions count more than once in the dimension.
There are 6 counted with multiplicity, so at most 6 distinct ones.
There are 6 real ones.The dimension counts complex solutions; the real ones need a signature.

The rank of the trace form tells you the number of distinct solutions, and its signature the number of real ones.

The eigenvalues of the multiplication matrix $L_f$ on $A$ are:

the values $f(z)$ at the complex solutions $z$
the coordinates of the solutionsThat is the special case $f=x$ or $f=y$ .
the coefficients of $f$ The coefficients of $f$ enter $L_f$ , but its eigenvalues are values of $f$ .

If

v

is the evaluation at

z

seen as a linear form on

A

, then

v(fg)=f(z)v(g)

: it is an eigenvector of the transpose of

L_f

with eigenvalue

f(z)

.

For some zero-dimensional system the trace form $f\mapsto\operatorname{Tr}(L_{f^2})$ has rank 6 and signature 2. How many solutions are real?

6The rank counts distinct complex solutions.
2, out of 6 distinct complex ones
4The signature itself is the number of real solutions; it doesn't need to be subtracted.

Each real solution gives a positive square; each conjugate pair a positive and a negative one. 6 distinct solutions: 2 real and 2 pairs.

Practice

A family of systemsWhen do real solutions appear?

For which real $r$ does $x^2+y^2=r,\ xy=2$ have real solutions, and how many?

Solution

Eliminating $y$ gives $x^4-rx^2+4=0$ , so $x^2=\big(r\pm\sqrt{r^2-16}\big)/2$ . For $r>4$ both values are positive: 4 real solutions. For $r=4$ : $x^2=2$ , two real solutions $(\sqrt2,\sqrt2)$ , $(-\sqrt2,-\sqrt2)$ , each of multiplicity 2. For $r<4$ : none (for $r\le-4$ the values of $x^2$ are negative, for $|r|<4$ they are not real).

A separating elementUnivariate representation

In the worked example, is $u=x+y$ separating? Find a linear form that is, and the characteristic polynomial of $L_u$ for it.

Solution

$x+y$ takes the values $3,3,-3,-3$ : not separating, since $(1,2)$ and $(2,1)$ collide. $u=x+2y$ takes $5,4,-5,-4$ : separating, with characteristic polynomial $(T^2-25)(T^2-16)=T^4-41T^2+400$ .

InteractiveBasu–Pollack–Roy, Ch. 10: Real Roots · Ch. 13: Existential Theory of the Reals

Sign conditions and Thom encodings

Deciding whether a system of polynomial conditions has a real solution means finding which sign conditions on the polynomials are realizable. On the line you can see all of them at once, and there are far fewer than the $3^s$ conceivable ones. The same bookkeeping names each real root exactly.

The idea

Sign condition. For a family

\mathcal P=\{P_1,\dots,P_s\}

, a sign condition is a choice

\sigma\in\{-,0,+\}^s

. Its realization is

\{x:\operatorname{sign}P_i(x)=\sigma_i\text{ for all }i\}

, and

\sigma

is realizable if that set is nonempty.

The existential theory of the reals asks whether $\exists x\ \Phi(x)$ holds for a quantifier-free $\Phi$ . Since the truth of $\Phi$ only depends on the signs of its polynomials, it is enough to list the realizable sign conditions and test $\Phi$ on each.

Few sign conditions. For

s

polynomials of degree at most

d

in

k

variables, the number of realizable sign conditions, and even of connected components of their realizations, is at most

(O(sd))^k

, much less than

3^s

when

s

is large. On the line: at most

sd

roots, hence at most

2sd+1

cells.

Sample points (Ch. 13). A set of points meeting every connected component of every realizable sign condition can be computed with

s^{k+1}d^{O(k)}

arithmetic operations. The method takes critical points of a well-chosen function on perturbed sets, with infinitesimals (module 4) to make everything bounded and non-singular, and is singly exponential in

k

, unlike a cylindrical decomposition.

Thom's lemma. For a univariate

P

of degree

p

, every sign condition on

P,P',\dots,P^{(p)}

is realized by an interval, a point, or nothing. Consequently two distinct real roots of

P

have different sign vectors on

P',\dots,P^{(p-1)}

. That vector is the Thom encoding of the root: an exact name, and two encoded numbers can be compared by sign determination.

Explore

P₁(x) P₂(x) P₃(x) (optional)

Examples

One row per polynomial: its graph (compressed) and its sign, positive negative. Dashed lines: roots of the product. Drag the blue marker along the line.

Worked example

Find the realizable sign conditions of $\mathcal P=\{x^2-1,\ x^2-4x+3\}$ , decide whether $x^2<1\wedge x^2-4x+3<0$ has a solution, and give the Thom encodings of the roots of the second polynomial.

Find the roots of the product and the cells of the line.

$x^2-1$ has roots $\pm1$ ; $x^2-4x+3=(x-1)(x-3)$ has roots $1,3$ . The product's roots are $-1,1,3$ , so there are 7 cells: $(-\infty,-1)$ , $\{-1\}$ , $(-1,1)$ , $\{1\}$ , $(1,3)$ , $\{3\}$ , $(3,\infty)$ .
Compute the sign vector on each cell.

Using sample points $-2,\ -1,\ 0,\ 1,\ 2,\ 3,\ 4$ : $(+,+)$ , $(0,+)$ , $(-,+)$ , $(0,0)$ , $(+,-)$ , $(+,0)$ , $(+,+)$ .
Which sign conditions are realizable, and is the system solvable?

Six of the nine: $(+,+)$ , $(0,+)$ , $(-,+)$ , $(0,0)$ , $(+,-)$ , $(+,0)$ . The condition $(-,-)$ is not among them, so $x^2<1\wedge x^2-4x+3<0$ has no real solution. Neither do $(-,0)$ and $(0,-)$ .
Give the Thom encodings of the roots $1$ and $3$ of $x^2-4x+3$ .

The derivative is $2x-4$ : negative at 1, positive at 3. The encodings $(-)$ and $(+)$ differ, as Thom's lemma guarantees. "Shared roots" in the explorer is a variant of this example.

Check your understanding

Three polynomials of degree 2 in one variable. At most how many sign conditions are realizable?

27That's $3^3$ , all conceivable ones; most can't occur.
13
7Three quadratics can have up to 6 roots in total, so up to 13 cells.

At most

sd=6

roots cut the line into at most

2\cdot6+1=13

cells, and each cell realizes one sign condition. In the explorer the first example has 5 distinct roots and 11 cells.

Why can two different real roots of $P$ never have the same Thom encoding?

Because all roots of $P$ are simple. $P$ may have multiple roots; the encoding still tells them apart.
The set where $P',\dots,P^{(p)}$ have the given signs is an interval or a point, and on it $P$ is strictly monotone or the set is a single point, so $P$ vanishes there at most once.
Because $P'$ is nonzero at every root.At a multiple root $P'$ vanishes, and the encoding then records a 0.

This is Thom's lemma applied to

P'

: the realization of a sign condition on all derivatives is connected. If it is an interval,

P'

has a constant nonzero sign on it, so

P

is strictly monotone there.

To decide $\exists x\ (P(x)>0\wedge Q(x)<0)$ in one variable, it suffices to:

check whether the sign condition $(+,-)$ is realized, for example at one sample point in each cell cut out by the roots of $PQ$
evaluate $P$ and $Q$ at the roots of $PQ$ onlyA strict condition like this one is realized on intervals between the roots, not at them.
check whether $P-Q>0$ somewhereThat is a different condition: $P=3$ , $Q=1$ satisfies it.

Signs are constant on each cell, so finitely many sample points decide every quantifier-free condition in one variable. The algorithms of Ch. 13 do the same in

k

variables, with sample points meeting every connected component.

Practice

Thom encodings of a quarticSigns of three derivatives

$P=x^4-4x^2+1$ has the four real roots $\pm\sqrt{2\pm\sqrt3}\approx\pm1.932,\ \pm0.518$ . Find their Thom encodings (signs of $P',P'',P'''$ ) and check they are distinct. Then use the "Thom encodings" example in the explorer.

Solution

$P'=4x^3-8x$ , $P''=12x^2-8$ , $P'''=24x$ . At $-1.932$ : $(-,+,-)$ . At $-0.518$ : $(+,-,-)$ . At $0.518$ : $(-,-,+)$ . At $1.932$ : $(+,+,+)$ . All different. Note that $P'''$ alone separates the negative from the positive roots, and $P''$ then separates the two of each sign.

One polynomial, many cellsCells versus sign conditions

Show that a single polynomial realizes at most 3 sign conditions however many roots it has. Can two polynomials of degree 2 realize all 9 sign conditions in $\{-,0,+\}^2$ ?

Hint

How many cells can two quadratics make, and how many of them are points?

Solution

One polynomial only has the values $-,0,+$ . For two quadratics there are at most 4 roots and 9 cells, but at most 4 of the cells are points, while the conditions $(0,0)$ , $(0,\pm)$ , $(\pm,0)$ (five of them) can only be realized at roots. So at most 4 of those five occur, and all 9 is impossible. With $(0,0)$ realized, some root is shared, which leaves even fewer cells.