You are currently browsing the tag archive for the ‘Bezout’s theorem’ tag.

One of the first non-trivial theorems one encounters in classical algebraic geometry is Bézout’s theorem, which we will phrase as follows:

Theorem 1 (Bézout’s theorem) Let {k} be a field, and let {P, Q \in k[x,y]} be non-zero polynomials in two variables {x,y} with no common factor. Then the two curves {\{ (x,y) \in k^2: P(x,y) = 0\}} and {\{ (x,y) \in k^2: Q(x,y) = 0\}} have no common components, and intersect in at most {\hbox{deg}(P) \hbox{deg}(Q)} points.

This theorem can be proven by a number of means, for instance by using the classical tool of resultants. It has many strengthenings, generalisations, and variants; see for instance this previous blog post on Bézout’s inequality. Bézout’s theorem asserts a fundamental algebraic dichotomy, of importance in combinatorial incidence geometry: any two algebraic curves either share a common component, or else have a bounded finite intersection; there is no intermediate case in which the intersection is unbounded in cardinality, but falls short of a common component. This dichotomy is closely related to the integrality gap in algebraic dimension: an algebraic set can have an integer dimension such as {0} or {1}, but cannot attain any intermediate dimensions such as {1/2}. This stands in marked contrast to sets of analytic, combinatorial, or probabilistic origin, whose “dimension” is typically not necessarily constrained to be an integer.

Bézout’s inequality tells us, roughly speaking, that the intersection of a curve of degree {D_1} and a curve of degree {D_2} forms a set of at most {D_1 D_2} points. One can consider the converse question: given a set {S} of {N} points in the plane {k^2}, can one find two curves of degrees {D_1,D_2} with {D_1 D_2 = O(N)} and no common components, whose intersection contains these points?

A model example that supports the possibility of such a converse is a grid {S = A \times B} that is a Cartesian product of two finite subsets {A, B} of {k} with {|A| |B| = N}. In this case, one can take one curve to be the union of {|A|} vertical lines, and the other curve to be the union of {|B|} horizontal lines, to obtain the required decomposition. Thus, if the proposed converse to Bézout’s inequality held, it would assert that any set of {N} points was essentially behaving like a “nonlinear grid” of size {N}.

Unfortunately, the naive converse to Bézout’s theorem is false. A counterexample can be given by considering a set {S = S_1 \cup S_2} of {2N} points for some large perfect square {N}, where {P_1} is a {\sqrt{N}} by {\sqrt{N}} grid of the form described above, and {S_2} consists of {N} points on an line {\ell} (e.g. a {1 \times N} or {N \times 1} grid). Each of the two component sets {S_1, S_2} can be written as the intersection between two curves whose degrees multiply up to {N}; in the case of {S_1}, we can take the two families of parallel lines (viewed as reducible curves of degree {\sqrt{N}}) as the curves, and in the case of {S_2}, one can take {\ell} as one curve, and the graph of a degree {N} polynomial on {\ell} vanishing on {S_2} for the second curve. But, if {N} is large enough, one cannot cover {S} by the intersection of a single pair {\gamma_1, \gamma_2} of curves with no common components whose degrees {D_1,D_2} multiply up to {D_1 D_2 = O(N)}. Indeed, if this were the case, then without loss of generality we may assume that {D_1 \leq D_2}, so that {D_1 = O(\sqrt{N})}. By Bézout’s theorem, {\gamma_1} either contains {\ell}, or intersects {\ell} in at most {O(D_1) = O(\sqrt{N})} points. Thus, in order for {\gamma_1} to capture all of {S}, it must contain {\ell}, which forces {\gamma_2} to not contain {\ell}. But {\gamma_2} has to intersect {\ell} in {N} points, so by Bézout’s theorem again we have {D_2 \geq N}, thus {D_1 = O(1)}. But then (by more applications of Bézout’s theorem) {\gamma_1} can only capture {O(\sqrt{N})} of the {N} points of {S_1}, a contradiction.

But the above counterexample suggests that even if an arbitrary set of {N} (or {2N}) points cannot be covered by the single intersection of a pair of curves with degree multiplying up to {O(N)}, one may be able to cover such a set by a small number of such intersections. The purpose of this post is to record the simple observation that this is, indeed, the case:

Theorem 2 (Partial converse to Bézout’s theorem) Let {k} be a field, and let {S} be a set of {N} points in {k} for some {N > 1}. Then one can find {m = O(\log N)} and pairs {P_i,Q_i \in k[x,y]} of coprime non-zero polynomials for {i=1,\ldots,m} such that

\displaystyle  S \subset \bigcup_{i=1}^m \{ (x,y) \in k^2: P_i(x,y) = Q_i(x,y) = 0 \} \ \ \ \ \ (1)


\displaystyle  \sum_{i=1}^m \hbox{deg}(P_i) \hbox{deg}(Q_i) = O( N ). \ \ \ \ \ (2)

Informally, every finite set in the plane is (a dense subset of) the union of logarithmically many nonlinear grids. The presence of the logarithm is necessary, as can be seen by modifying the {P_1 \cup P_2} example to be the union of logarithmically many Cartesian products of distinct dimensions, rather than just a pair of such products.

Unfortunately I do not know of any application of this converse, but I thought it was cute anyways. The proof is given below the fold.

Read the rest of this entry »

An algebraic (affine) plane curve of degree {d} over some field {k} is a curve {\gamma} of the form

\displaystyle  \gamma = \{ (x,y) \in k^2: P(x,y) = 0 \}

where {P} is some non-constant polynomial of degree {d}. Examples of low-degree plane curves include

  • Degree {1} (linear) curves {\{ (x,y) \in k^2: ax+by=c\}}, which are simply the lines;
  • Degree {2} (quadric) curves {\{ (x,y) \in k^2: ax^2+bxy+cy^2+dx+ey+f=0\}}, which (when {k={\bf R}}) include the classical conic sections (i.e. ellipses, hyperbolae, and parabolae), but also include the reducible example of the union of two lines; and
  • Degree {3} (cubic) curves {\{ (x,y) \in k^2: ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j=0\}}, which include the elliptic curves {\{ (x,y) \in k^2: y^2=x^3+ax+b\}} (with non-zero discriminant {\Delta := -16(4a^3+27b^2)}, so that the curve is smooth) as examples (ignoring some technicalities when {k} has characteristic two or three), but also include the reducible examples of the union of a line and a conic section, or the union of three lines.
  • etc.

Algebraic affine plane curves can also be extended to the projective plane {{\Bbb P} k^2 = \{ [x,y,z]: (x,y,z) \in k^3 \backslash 0 \}} by homogenising the polynomial. For instance, the affine quadric curve {\{ (x,y) \in k^2: ax^2+bxy+cy^2+dx+ey+f=0\}} would become {\{ [x,y,z] \in {\Bbb P} k^2: ax^2+bxy+cy^2+dxz+eyz+fz^2=0\}}.

One of the fundamental theorems about algebraic plane curves is Bézout’s theorem, which asserts that if a degree {d} curve {\gamma} and a degree {d'} curve {\gamma'} have no common component, then they intersect in at most {dd'} points (and if the underlying field {k} is algebraically closed, one works projectively, and one counts intersections with multiplicity, they intersect in exactly {dd'} points). Thus, for instance, two distinct lines intersect in at most one point; a line and a conic section intersect in at most two points; two distinct conic sections intersect in at most four points; a line and an elliptic curve intersect in at most three points; two distinct elliptic curves intersect in at most nine points; and so forth. Bézout’s theorem is discussed in this previous post.

From linear algebra we also have the fundamental fact that one can build algebraic curves through various specified points. For instance, for any two points {A_1,A_2} one can find a line {\{ (x,y): ax+by=c\}} passing through the points {A_1,A_2}, because this imposes two linear constraints on three unknowns {a,b,c} and is thus guaranteed to have at least one solution. Similarly, given any five points {A_1,\ldots,A_5}, one can find a quadric curve passing through these five points (though note that if three of these points are collinear, then this curve cannot be a conic thanks to Bézout’s theorem, and is thus necessarily reducible to the union of two lines); given any nine points {A_1,\ldots,A_9}, one can find a cubic curve going through these nine points; and so forth. This simple observation is one of the foundational building blocks of the polynomial method in combinatorial incidence geometry, discussed in these blog posts.

In the degree {1} case, it is always true that two distinct points {A, B} determine exactly one line {\overleftrightarrow{AB}}. In higher degree, the situation is a bit more complicated. For instance, five collinear points determine more than one quadric curve, as one can simply take the union of the line containing those five points, together with an arbitrary additional line. Similarly, eight points on a conic section plus one additional point determine more than one cubic curve, as one can take that conic section plus an arbitrary line going through the additional point. However, if one places some “general position” hypotheses on these points, then one can recover uniqueness. For instance, given five points, no three of which are collinear, there can be at most one quadric curve that passes through these points (because these five points cannot lie on the union of two lines, and by Bézout’s theorem they cannot simultaneously lie on two distinct conic sections).

For cubic curves, the situation is more complicated still. Consider for instance two distinct cubic curves {\gamma_0 = \{ P_0(x,y)=0\}} and {\gamma_\infty = \{P_\infty(x,y)=0\}} that intersect in precisely nine points {A_1,\ldots,A_9} (note from Bézout’s theorem that this is an entirely typical situation). Then there is in fact an entire one-parameter family of cubic curves that pass through these points, namely the curves {\gamma_t = \{ P_0(x,y) + t P_\infty(x,y) = 0\}} for any {t \in k \cup \{\infty\}} (with the convention that the constraint {P_0+tP_\infty=0} is interpreted as {P_\infty=0} when {t=\infty}).

In fact, these are the only cubics that pass through these nine points, or even through eight of the nine points. More precisely, we have the following useful fact, known as the Cayley-Bacharach theorem:

Proposition 1 (Cayley-Bacharach theorem) Let {\gamma_0 = \{ P_0(x,y)=0\}} and {\gamma_\infty = \{P_\infty(x,y)=0\}} be two cubic curves that intersect (over some algebraically closed field {k}) in precisely nine distinct points {A_1,\ldots,A_9 \in k^2}. Let {P} be a cubic polynomial that vanishes on eight of these points (say {A_1,\ldots,A_8}). Then {P} is a linear combination of {P_0,P_\infty}, and in particular vanishes on the ninth point {A_9}.

Proof: (This proof is based off of a text of Husemöller.) We assume for contradiction that there is a cubic polynomial {P} that vanishes on {A_1,\ldots,A_8}, but is not a linear combination of {P_0} and {P_\infty}.

We first make some observations on the points {A_1,\ldots,A_9}. No four of these points can be collinear, because then by Bézout’s theorem, {P_0} and {P_\infty} would both have to vanish on this line, contradicting the fact that {\gamma_0, \gamma_\infty} meet in at most nine points. For similar reasons, no seven of these points can lie on a quadric curve.

One consequence of this is that any five of the {A_1,\ldots,A_9} determine a unique quadric curve {\sigma}. The existence of the curve follows from linear algebra as discussed previously. If five of the points lie on two different quadric curves {\sigma,\sigma'}, then by Bezout’s theorem, they must share a common line; but this line can contain at most three of the five points, and the other two points determine uniquely the other line that is the component of both {\sigma} and {\sigma'}, and the claim follows.

Now suppose that three of the first eight points, say {A_1,A_2,A_3}, are collinear, lying on a line {\ell}. The remaining five points {A_4,\ldots,A_8} do not lie on {\ell}, and determine a unique quadric curve {\sigma} by the previous discussion. Let {B} be another point on {\ell}, and let {C} be a point that does not lie on either {\ell} or {\sigma}. By linear algebra, one can find a non-trivial linear combination {Q = aP + bP_0 + cP_\infty} of {P,P_0,P_\infty} that vanishes at both {B} and {C}. Then {Q} is a cubic polynomial that vanishes on the four collinear points {A_1,A_2,A_3,B} and thus vanishes on {\ell}, thus the cubic curve defined by {Q} consists of {\ell} and a quadric curve. This curve passes through {A_4,\ldots,A_8} and thus equals {\sigma}. But then {C} does not lie on either {\ell} or {\sigma} despite being a vanishing point of {Q}, a contradiction. Thus, no three points from {A_1,\ldots,A_8} are collinear.

In a similar vein, suppose next that six of the first eight points, say {A_1,\ldots,A_6}, lie on a quadric curve {\sigma}; as no three points are collinear, this quadric curve cannot be the union of two lines, and is thus a conic section. The remaining two points {A_7, A_8} determine a unique line {\ell = \overleftrightarrow{A_7A_8}}. Let {B} be another point on {\sigma}, and let {C} be another point that does not lie on either {\ell} and {\sigma}. As before, we can find a non-trivial cubic {Q = aP + bP_0+cP_\infty} that vanishes at both {B, C}. As {Q} vanishes at seven points of a conic section {\sigma}, it must vanish on all of {\sigma}, and so the cubic curve defined by {Q} is the union of {\sigma} and a line that passes through {A_7} and {A_8}, which must necessarily be {\ell}. But then this curve does not pass through {C}, a contradiction. Thus no six points in {A_1,\ldots,A_8} lie on a quadric curve.

Finally, let {\ell} be the line through the two points {A_1,A_2}, and {\sigma} the quadric curve through the five points {A_3,\ldots,A_7}; as before, {\sigma} must be a conic section, and by the preceding paragraphs we see that {A_8} does not lie on either {\sigma} or {\ell}. We pick two more points {B, C} lying on {\ell} but not on {\sigma}. As before, we can find a non-trivial cubic {Q = aP + bP_0+cP_\infty} that vanishes on {B, C}; it vanishes on four points on {\ell} and thus {Q} defines a cubic curve that consists of {\ell} and a quadric curve. The quadric curve passes through {A_3,\ldots,A_7} and is thus {\sigma}; but then the curve does not pass through {A_8}, a contradiction. This contradiction finishes the proof of the proposition. \Box

I recently learned of this proposition and its role in unifying many incidence geometry facts concerning lines, quadric curves, and cubic curves. For instance, we can recover the proof of the classical theorem of Pappus:

Theorem 2 (Pappus’ theorem) Let {\ell, \ell'} be two distinct lines, let {A_1,A_2,A_3} be distinct points on {\ell} that do not lie on {\ell'}, and let {B_1,B_2,B_3} be distinct points on {\ell'} that do not lie on {\ell}. Suppose that for {ij=12,23,31}, the lines {\overleftrightarrow{A_i B_j}} and {\overleftrightarrow{A_j B_i}} meet at a point {C_{ij}}. Then the points {C_{12}, C_{23}, C_{31}} are collinear.

Proof: We may assume that {C_{12}, C_{23}} are distinct, since the claim is trivial otherwise.

Let {\gamma_0} be the union of the three lines {\overleftrightarrow{A_1 B_2}}, {\overleftrightarrow{A_2 B_3}}, and {\overleftrightarrow{A_3 B_1}} (the purple lines in the first figure), let {\gamma_1} be the union of the three lines {\overleftrightarrow{A_2 B_1}}, {\overleftrightarrow{A_3 B_2}}, and {\overleftrightarrow{A_1 B_3}} (the dark blue lines), and let {\gamma} be the union of the three lines {\ell}, {\ell'}, and {\overleftrightarrow{C_{12} C_{23}}} (the other three lines). By construction, {\gamma_0} and {\gamma_1} are cubic curves with no common component that meet at the nine points {A_1,A_2,A_3,B_1,B_2,B_3,C_{12},C_{23},C_{31}}. Also, {\gamma} is a cubic curve that passes through the first eight of these points, and thus also passes through the ninth point {C_{31}}, by the Cayley-Bacharach theorem. The claim follows (note that {C_{31}} cannot lie on {\ell} or {\ell'}). \Box

The same argument gives the closely related theorem of Pascal:

Theorem 3 (Pascal’s theorem) Let {A_1,A_2,A_3,B_1,B_2,B_3} be distinct points on a conic section {\sigma}. Suppose that for {ij=12,23,31}, the lines {\overleftrightarrow{A_i B_j}} and {\overleftrightarrow{A_j B_i}} meet at a point {C_{ij}}. Then the points {C_{12}, C_{23}, C_{31}} are collinear.

Proof: Repeat the proof of Pappus’ theorem, with {\sigma} taking the place of {\ell \cup \ell'}. (Note that as any line meets {\sigma} in at most two points, the {C_{ij}} cannot lie on {\sigma}.) \Box

One can view Pappus’s theorem as the degenerate case of Pascal’s theorem, when the conic section degenerates to the union of two lines.

Finally, Proposition 1 gives the associativity of the elliptic curve group law:

Theorem 4 (Associativity of the elliptic curve law) Let {\gamma := \{ (x,y) \in k^2: y^2 = x^3+ax+b \} \cup \{O\}} be a (projective) elliptic curve, where {O := [0,1,0]} is the point at infinity on the {y}-axis, and the discriminant {\Delta := -16(4a^3+27b^2)} is non-zero. Define an addition law {+} on {\gamma} by defining {A+B} to equal {-C}, where {C} is the unique point on {\gamma} collinear with {A} and {B} (if {A,B} are disjoint) or tangent to {A} (if {A=B}), and {-C} is the reflection of {C} through the {x}-axis (thus {C, -C, O} are collinear), with the convention {-O=O}. Then {+} gives {\gamma} the structure of an abelian group with identity {O} and inverse {-}.

Proof: It is clear that {O} is the identity for {+}, {-} is an inverse, and {+} is abelian. The only non-trivial assertion is associativity: {(A+B)+C = A+(B+C)}. By a perturbation (or Zariski closure) argument, we may assume that we are in the generic case when {O,A,B,C,A+B,B+C,-(A+B), -(B+C)} are all distinct from each other and from {-((A+B)+C), -(A+(B+C))}. (Here we are implicitly using the smoothness of the elliptic curve, which is guaranteed by the hypothesis that the discriminant is non-zero.)

Let {\gamma'} be the union of the three lines {\overleftrightarrow{AB}}, {\overleftrightarrow{C(A+B)}}, and {\overleftarrow{O(B+C)}} (the purple lines), and let {\gamma''} be the union of the three lines {\overleftrightarrow{O(A+B)}}, {\overleftrightarrow{BC}}, and {\overleftrightarrow{A(B+C)}} (the green lines). Observe that {\gamma'} and {\gamma} are cubic curves with no common component that meet at the nine distinct points {O, A, B, C, A+B, -(A+B), B+C, -(B+C), -((A+B)+C)}. The cubic curve {\gamma''} goes through the first eight of these points, and thus (by Proposition 1) also goes through the ninth point {-((A+B)+C)}. This implies that the line through {A} and {B+C} meets {\gamma} in both {-(A+(B+C))} and {-((A+B)+C)}, and so these two points must be equal, and so {(A+B)+C=A+(B+C)} as required. \Box

One can view Pappus’s theorem and Pascal’s theorem as a degeneration of the associativity of the elliptic curve law, when the elliptic curve degenerates to three lines (in the case of Pappus) or the union of one line and one conic section (in the case of Pascal’s theorem).

Classically, the fundamental object of study in algebraic geometry is the solution set

\displaystyle  V = V_{P_1,\ldots,P_m} := \{ (x_1,\ldots,x_d) \in k^d: P_1(x_1,\ldots,x_d) = \ldots \ \ \ \ \ (1)

\displaystyle  = P_m(x_1,\ldots,x_d) = 0 \}

to multiple algebraic equations

\displaystyle  P_1(x_1,\ldots,x_d) = \ldots = P_m(x_1,\ldots,x_d) = 0

in multiple unknowns {x_1,\ldots,x_d} in a field {k}, where the {P_1,\ldots,P_m: k^d \rightarrow k} are polynomials of various degrees {D_1, \ldots, D_m}. We adopt the classical perspective of viewing {V} as a set (and specifically, as an algebraic set), rather than as a scheme. Without loss of generality we may order the degrees in non-increasing order:

\displaystyle  D_1 \geq D_2 \geq \ldots \geq D_m \geq 1.

We can distinguish between the underdetermined case {m < d}, when there are more unknowns than equations; the determined case {m=d} when there are exactly as many unknowns as equations; and the overdetermined case {m>d}, when there are more equations than unknowns.

Experience has shown that the theory of such equations is significantly simpler if one assumes that the underlying field {k} is algebraically closed , and so we shall make this assumption throughout the rest of this post. In particular, this covers the important case when {k={\bf C}} is the field of complex numbers (but it does not cover the case {k={\bf R}} of real numbers – see below).

From the general “soft” theory of algebraic geometry, we know that the algebraic set {V} is a union of finitely many algebraic varieties, each of dimension at least {d-m}, with none of these components contained in any other. In particular, in the underdetermined case {m<d}, there are no zero-dimensional components of {V}, and thus {V} is either empty or infinite.

Now we turn to the determined case {d=m}, where we expect the solution set {V} to be zero-dimensional and thus finite. Here, the basic control on the solution set is given by Bezout’s theorem. In our notation, this theorem states the following:

Theorem 1 (Bezout’s theorem) Let {d=m=2}. If {V} is finite, then it has cardinality at most {D_1 D_2}.

This result can be found in any introductory algebraic geometry textbook; it can for instance be proven using the classical tool of resultants. The solution set {V} will be finite when the two polynomials {P_1,P_2} are coprime, but can (and will) be infinite if {P_1,P_2} share a non-trivial common factor.

By defining the right notion of multiplicity on {V} (and adopting a suitably “scheme-theoretic” viewpoint), and working in projective space rather than affine space, one can make the inequality {|V| \leq D_1 D_2} an equality. However, for many applications (and in particular, for the applications to combinatorial incidence geometry), the upper bound usually suffices.

Bezout’s theorem can be generalised in a number of ways. For instance, the restriction on the finiteness of the solution set {V} can be dropped by restricting attention to {V^0}, the union of the zero-dimensional irreducible components of {V}:

Corollary 2 (Bezout’s theorem, again) Let {d=m=2}. Then {V^0} has cardinality at most {D_1 D_2}.

Proof: We factor {P_1, P_2} into irreducible factors (using unique factorisation of polynomials). By removing repeated factors, we may assume {P_1, P_2} are square-free. We then write {P_1 = Q_1 R}, {P_2 = Q_2 R} where {R} is the greatest common divisor of {P_1,P_2} and {Q_1,Q_2} are coprime. Observe that the zero-dimensional component of {\{ P_1=P_2 = 0\}} is contained in {\{ Q_1 = Q_2 = 0\}}, which is finite from the coprimality of {Q_1,Q_2}. The claim follows. \Box

It is also not difficult to use Bezout’s theorem to handle the overdetermined case {m > d=2} in the plane:

Corollary 3 (Bezout’s theorem, yet again) Let {m \geq d=2}. Then {V^0} has cardinality at most {D_1 D_2}.

Proof: We may assume all the {P_i} are square-free. We write {P_1 = Q_2 R_2}, where {Q_2} is coprime to {P_2} and {R_2} divides {P_2} (and also {P_1}). We then write {R_2 = Q_3 R_3}, where {Q_3} is coprime to {P_3} and {R_3} divides {P_3} (and also {P_1,P_2}). Continuing in this fashion we obtain a factorisation {P_1 = Q_2 Q_3 \ldots Q_m R_m}. One then observes that {V^0} is contained in the set {\bigcup_{i=2}^m \{ Q_i = P_i = 0 \}}, which by Theorem 1 has cardinality at most {\sum_{i=2}^m \hbox{deg}(Q_i) D_i}. Since {D_i \leq D_2} and {\sum_{i=2}^m \hbox{deg}(Q_i) \leq \hbox{deg}(P_1) = D_1}, the claim follows. \Box

Remark 1 Of course, in the overdetermined case {m>d} one generically expects the solution set to be empty, but if there is enough degeneracy or numerical coincidence then non-zero solution sets can occur. In particular, by considering the case when {P_2=\ldots=P_m} and {D_2=\ldots=D_m} we see that the bound {D_1 D_2} can be sharp in some cases. However, one can do a little better in this situation; by decomposing {P_m} into irreducible components, for instance, one can improve the upper bound of {D_1 D_2} slightly to {D_1 D_m}. However, this improvement seems harder to obtain in higher dimensions (see below).

Bezout’s theorem also extends to higher dimensions. Indeed, we have

Theorem 4 (Higher-dimensional Bezout’s theorem) Let {d=m \geq 0}. If {V} is finite, then it has cardinality at most {D_1 \ldots D_d}.

This is a standard fact, and can for instance be proved from the more general and powerful machinery of intersection theory. A typical application of this theorem is to show that, given a degree {D} polynomial {P: {\bf R}^d \rightarrow {\bf R}} over the reals, the number of connected components of {\{ x \in {\bf R}^d: P(x) \neq 0 \}} is {O(D^d)}. The main idea of the proof is to locate a critical point {\nabla P(x) = 0} inside each connected component, and use Bezout’s theorem to count the number of zeroes of the polynomial map {\nabla P: {\bf R}^d \rightarrow {\bf R}^d}. (This doesn’t quite work directly because some components may be unbounded, and because the fibre of {\nabla P} at the origin may contain positive-dimensional components, but one can use truncation and generic perturbation to deal with these issues; see my recent paper with Solymosi for further discussion.)

Bezout’s theorem can be extended to the overdetermined case as before:

Theorem 5 (Bezout’s inequality) Let {m \geq d \geq 0}. Then {V^0} has cardinality at most {D_1 \ldots D_d}.

Remark 2 Theorem 5 ostensibly only controls the zero-dimensional components of {V}, but by throwing in a few generic affine-linear forms to the set of polynomials {P_1,\ldots,P_m} (thus intersecting {V} with a bunch of generic hyperplanes) we can also control the total degree of all the {i}-dimensional components of {V} for any fixed {i}. (Again, by using intersection theory one can get a slightly more precise bound than this, but the proof of that bound is more complicated than the arguments given here.)

This time, though, it is a slightly non-trivial matter to deduce Theorem 5 from Theorem 4, due to the standard difficulty that the intersection of irreducible varieties need not be irreducible (which can be viewed in some ways as the source of many other related difficulties, such as the fact that not every algebraic variety is a complete intersection), and so one cannot evade all irreducibility issues merely by assuming that the original polynomials {P_i} are irreducible. Theorem 5 first appeared explicitly in the work of Heintz.

As before, the most systematic way to establish Theorem 5 is via intersection theory. In this post, though, I would like to give a slightly more elementary argument (essentially due to Schmid), based on generically perturbing the polynomials {P_1,\ldots,P_m} in the problem ; this method is less powerful than the intersection-theoretic methods, which can be used for a wider range of algebraic geometry problems, but suffices for the narrow objective of proving Theorem 5. The argument requires some of the “soft” or “qualitative” theory of algebraic geometry (in particular, one needs to understand the semicontinuity properties of preimages of dominant maps), as well as basic linear algebra. As such, the proof is not completely elementary, but it uses only a small amount of algebraic machinery, and as such I found it easier to understand than the intersection theory arguments.

Theorem 5 is a statement about arbitrary polynomials {P_1,\ldots,P_m}. However, it turns out (in the determined case {m=d}, at least) that upper bounds on {|V^0|} are Zariski closed properties, and so it will suffice to establish this claim for generic polynomials {P_1,\ldots,P_m}. On the other hand, it is possible to use duality to deduce such upper bounds on {|V^0|} from a Zariski open condition, namely that a certain collection of polynomials are linearly independent. As such, to verify the generic case of this open condition, it suffices to establish this condition for a single family of polynomials, such as a family of monomials, in which case the condition can be verified by direct inspection. Thus we see an example of the somewhat strange strategy of establishing the general case from a specific one, using the generic case as an intermediate step.

Remark 3 There is an important caveat to note here, which is that these theorems only hold for algebraically closed fields, and in particular can fail over the reals {{\bf R}}. For instance, in {{\bf R}^3}, the polynomials

\displaystyle  P(x,y,z) = z

\displaystyle  Q(x,y,z) = z

\displaystyle  R(x,y,z) = (\prod_{j=1}^N (x-j))^2 + (\prod_{j=1}^N (y-j))^2

have degrees {1, 1, 2N} respectively, but their common zero locus {\{ (x,y,0): x,y \in \{1,\ldots,N\}\}} has cardinality {N^2}. In some cases one can safely obtain incidence bounds in {{\bf R}} by embedding {{\bf R}} inside {{\bf C}}, but as the above example shows, one needs to be careful when doing so.

Read the rest of this entry »

I have blogged a number of times in the past about the relationship between finitary (or “hard”, or “quantitative”) analysis, and infinitary (or “soft”, or “qualitative”) analysis. One way to connect the two types of analysis is via compactness arguments (and more specifically, contradiction and compactness arguments); such arguments can convert qualitative properties (such as continuity) to quantitative properties (such as bounded), basically because of the fundamental fact that continuous functions on a compact space are bounded (or the closely related fact that sequentially continuous functions on a sequentially compact space are bounded).

A key stage in any such compactness argument is the following: one has a sequence {X_n} of “quantitative” or “finitary” objects or spaces, and one has to somehow end up with a “qualitative” or “infinitary” limit object {X} or limit space. One common way to achieve this is to embed everything inside some universal space and then use some weak compactness property of that space, such as the Banach-Alaoglu theorem (or its sequential counterpart). This is for instance the idea behind the Furstenberg correspondence principle relating ergodic theory to combinatorics; see for instance this post of mine on this topic.

However, there is a slightly different approach, which I will call ultralimit analysis, which proceeds via the machinery of ultrafilters and ultraproducts; typically, the limit objects {X} one constructs are now the ultraproducts (or ultralimits) of the original objects {X_\alpha}. There are two main facts that make ultralimit analysis powerful. The first is that one can take ultralimits of arbitrary sequences of objects, as opposed to more traditional tools such as metric completions, which only allow one to take limits of Cauchy sequences of objects. The second fact is Los’s theorem, which tells us that {X} is an elementary limit of the {X_\alpha} (i.e. every sentence in first-order logic which is true for the {X_\alpha} for {\alpha} large enough, is true for {X}). This existence of elementary limits is a manifestation of the compactness theorem in logic; see this earlier blog post for more discussion. So we see that compactness methods and ultrafilter methods are closely intertwined. (See also my earlier class notes for a related connection between ultrafilters and compactness.)

Ultralimit analysis is very closely related to nonstandard analysis. I already discussed some aspects of this relationship in an earlier post, and will expand upon it at the bottom of this post. Roughly speaking, the relationship between ultralimit analysis and nonstandard analysis is analogous to the relationship between measure theory and probability theory.

To illustrate how ultralimit analysis is actually used in practice, I will show later in this post how to take a qualitative infinitary theory – in this case, basic algebraic geometry – and apply ultralimit analysis to then deduce a quantitative version of this theory, in which the complexity of the various algebraic sets and varieties that appear as outputs are controlled uniformly by the complexity of the inputs. The point of this exercise is to show how ultralimit analysis allows for a relatively painless conversion back and forth between the quantitative and qualitative worlds, though in some cases the quantitative translation of a qualitative result (or vice versa) may be somewhat unexpected. In an upcoming paper of myself, Ben Green, and Emmanuel Breuillard (announced in the previous blog post), we will rely on ultralimit analysis to reduce the messiness of various quantitative arguments by replacing them with a qualitative setting in which the theory becomes significantly cleaner.

For sake of completeness, I also redo some earlier instances of the correspondence principle via ultralimit analysis, namely the deduction of the quantitative Gromov theorem from the qualitative one, and of Szemerédi’s theorem from the Furstenberg recurrence theorem, to illustrate how close the two techniques are to each other.

Read the rest of this entry »