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 be a field, and let be non-zero polynomials in two variables with no common factor. Then the two curves and have no common components, and intersect in at most 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 or , but cannot attain any intermediate dimensions such as . 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 and a curve of degree forms a set of at most points. One can consider the converse question: given a set of points in the plane , can one find two curves of degrees with and no common components, whose intersection contains these points?
A model example that supports the possibility of such a converse is a grid that is a Cartesian product of two finite subsets of with . In this case, one can take one curve to be the union of vertical lines, and the other curve to be the union of 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 points was essentially behaving like a “nonlinear grid” of size .
Unfortunately, the naive converse to Bézout’s theorem is false. A counterexample can be given by considering a set of points for some large perfect square , where is a by grid of the form described above, and consists of points on an line (e.g. a or grid). Each of the two component sets can be written as the intersection between two curves whose degrees multiply up to ; in the case of , we can take the two families of parallel lines (viewed as reducible curves of degree ) as the curves, and in the case of , one can take as one curve, and the graph of a degree polynomial on vanishing on for the second curve. But, if is large enough, one cannot cover by the intersection of a single pair of curves with no common components whose degrees multiply up to . Indeed, if this were the case, then without loss of generality we may assume that , so that . By Bézout’s theorem, either contains , or intersects in at most points. Thus, in order for to capture all of , it must contain , which forces to not contain . But has to intersect in points, so by Bézout’s theorem again we have , thus . But then (by more applications of Bézout’s theorem) can only capture of the points of , a contradiction.
But the above counterexample suggests that even if an arbitrary set of (or ) points cannot be covered by the single intersection of a pair of curves with degree multiplying up to , 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:
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 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 by a single, reasonably low-degree curve, which is a trick which also underlies the polynomial method in incidence combinatorics. Let be the first natural number such that , thus . The space of all polynomials in two variables of degree at most is , while the requirement that such a polynomial vanishes at every point of comprises linear constraints (not necessarily independent). By linear algebra, we conclude that there exists a non-zero polynomial of degree at most which vanishes at every point of .
Let denote the distinct irreducible factors of , and the degree of each , thus
In particular, we can partition into , where
for each , with the being disjoint.
Fix an . By applying a generic linear change of variables, we may assume that the coefficient of is non-zero. (Geometrically, we are changing coordinates so that the point at infinity on the -axis does not lie on the zero locus of .) Observethat for any , the space of polynomials in the ring of degree at most is at least , since the monomials for and are linearly independent. Setting to be the first natural number with , we conclude that we can find a polynomial that is not a multiple of , which vanishes on , and has degree
By construction, we have
This is getting close to what we want, except that we have far too many pairs ; the quantity could be potentially as large as , 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 (say), let be the set of indices such that
then the partition . For each , we then set
Observe that are coprime polynomials with
thus giving (1) (after some relabeling). Also, for each we have
Summing in , we conclude that
and (2) follows.
Remark 1 The above argument implicitly relied on some estimates on the Hilbert polynomial of the ring . 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.