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)

and

\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.

— 1. Proof of theorem —

The first step is to cover {S} by a single, reasonably low-degree curve, which is a trick which also underlies the polynomial method in incidence combinatorics. Let {D} be the first natural number such that {\frac{(D+1)(D+2)}{2} > N}, thus {D = O(\sqrt{N})}. The space of all polynomials in two variables of degree at most {D} is {\frac{(D+1)(D+2)}{2}}, while the requirement that such a polynomial vanishes at every point of {S} comprises {N} linear constraints (not necessarily independent). By linear algebra, we conclude that there exists a non-zero polynomial {P \in k[x,y]} of degree at most {D = O(\sqrt{N})} which vanishes at every point of {S}.

Let {P'_1,\ldots,P'_n} denote the distinct irreducible factors of {P}, and {d'_j} the degree of each {P'_j}, thus

\displaystyle \sum_{j=1}^n d'_j \ll \sqrt{N}

and

\displaystyle S \subset \bigcup_{j=1}^n \{ (x,y) \in k^2: P'_j(x,y) = 0 \}.

In particular, we can partition {S} into {S_1 \cup \ldots \cup S_n}, where

\displaystyle S_j \subset \{ (x,y) \in k^2: P'_j(x,y) = 0 \}

for each {j=1,\ldots,n}, with the {S_1,\ldots,S_n} being disjoint.

Fix an {j}. By applying a generic linear change of variables, we may assume that the {y^{d'_j}} coefficient of {P'_j} is non-zero. (Geometrically, we are changing coordinates so that the point at infinity on the {y}-axis does not lie on the zero locus of {P'_j}.) Observethat for any {D_j > 0}, the space of polynomials in the ring {k[x,y]/(P'_j)} of degree at most {D_j+d'_j} is at least {D_j d'_j}, since the monomials {x^a y^b} for {0 \leq a < D_j} and {0 \leq b < d'_j} are linearly independent. Setting {D_j} to be the first natural number with {D_j d'_j > |S_j|}, we conclude that we can find a polynomial {Q'_j \in k[x,y]} that is not a multiple of {P'_j}, which vanishes on {S_j}, and has degree

\displaystyle \hbox{deg}(Q'_i) \leq D_j + d'_j \ll \frac{|S_j|}{d'_j} + d'_j. \ \ \ \ \ (3)

By construction, we have

\displaystyle S \subset \bigcup_{j=1}^n \{ (x,y) \in k^2: P'_j(x,y) = Q'_j(x,y) = 0 \}.

This is getting close to what we want, except that we have far too many pairs {P'_j, Q'_j}; the quantity {n} could be potentially as large as {\sqrt{N}}, whereas we would like a logarithmic number instead. However, we can resolve this problem simply by dyadic pigeonholing on the quotient appearing in (3). Namely, for every integer {-10 \log N \leq i \leq 10 \log N} (say), let {J_i} be the set of indices {j \in \{1,\ldots,n\}} such that

\displaystyle 2^i \leq \frac{|S_j|}{d'_j} < 2^{i+1},

then the {J_i} partition {\{1,\ldots,n\}}. For each {i}, we then set

\displaystyle P_i := \prod_{j \in J_i} P'_j

and

\displaystyle Q_i := \sum_{j \in J_i} Q'_j \prod_{j' \in J_i: j' \neq j} P'_{j'}.

Observe that {P_i, Q_i} are coprime polynomials with

\displaystyle \bigcup_{j \in J_i} S_j \subset \{ (x,y) \in k^2: P_i(x,y) = Q_i(x,y) = 0 \}

thus giving (1) (after some relabeling). Also, for each {i} we have

\displaystyle \hbox{deg}(P_i) = \sum_{j \in J_i} d'_j

and

\displaystyle \hbox{deg}(Q_i) \ll \sup_{j \in J_i} ( \frac{|S_j|}{d'_j} + d'_j + \sum_{j' \in J_i: j' \neq j} d'_j)

\displaystyle \ll 2^i + \sum_{j \in J_i} d'_j

and thus

\displaystyle \hbox{deg}(P_i) \hbox{deg}(Q_i) \ll \sum_{j \in J_i} 2^i d'_j + (\sum_{j \in J_i} d'_j)^2

\displaystyle \ll \sum_{j \in J_i} |S_j| + (\sum_{j \in J_i} d'_j)^2.

Summing in {i}, we conclude that

\displaystyle \sum_i \hbox{deg}(P_i) \hbox{deg}(Q_i) \ll \sum_{j=1}^n |S_j| + \sum_i (\sum_{j \in J_i} d'_j)^2

\displaystyle \ll |S| + (\sum_i \sum_{j \in J_i} d'_j)^2

\displaystyle = n + (\sum_{j=1}^n d'_j)^2

\displaystyle \ll n + O(\sqrt{n})^2

\displaystyle \ll n

and (2) follows.

Remark 1 The above argument implicitly relied on some estimates on the Hilbert polynomial of the ring {k[x,y]/(P'_j)}. These Hilbert polynomials become more complicated in higher dimensions (especially given that the intersection of multiple hypersurfaces need not be a complete intersection in higher dimensions), and so I do not see immediately how to extend the above result to higher dimensions.