Source-linked AI summary
An incidence theorem in higher dimensions
Jozsef Solymosi, Terence Tao
TL;DR
The paper addresses incidence bounds for points and bounded-degree k-dimensional varieties in R^d under pseudoline-type conditions. It combines polynomial ham-sandwich partitioning with induction on dimension and point-set size, obtaining near-sharp bounds while incurring an epsilon loss in the exponents. The approach also yields a simpler near-sharp complex point-line result, but its sharpness is limited by the method’s treatment of high-degree partitioning boundaries.
Problem
The paper seeks near-sharp bounds for incidences between points and k-dimensional algebraic varieties in R^d under pseudoline-type hypotheses.
Method
The proof combines polynomial ham-sandwich cell decomposition with induction on dimension and on the size of the point set.
Results
The paper establishes near-sharp incidence bounds and a simpler near-sharp complex point-line bound, with a representative special-case estimate of 4(mD|P_i|)^2/3.
Takeaways & Limitations
The bounded-cell decomposition makes boundary contributions easier to handle, while induction substitutes for trivial interior bounds and supports incidence estimates for higher-dimensional varieties.
Takeaways & Limitations
The method loses an arbitrarily small epsilon in the exponents, and using higher-degree partitioning creates boundary terms that the paper’s simple arguments cannot adequately control in general.
Abstract
from arXiv · showhide
We prove almost tight bounds on incidences between points and $k$-dimensional varieties of bounded degree in $\R^d$. Our main tools are the Polynomial Ham Sandwich Theorem and induction on both the dimension and the number of points.
1. Introduction
The paper develops near-sharp incidence bounds for points and bounded-degree k-dimensional algebraic varieties in R^d under pseudoline-type hypotheses, using polynomial partitioning and induction. It also recovers a near-sharp complex point-line bound with a simpler but slightly weaker argument.
- Context: The classical Szemerédi–Trotter incidence bound extends from the plane to R^d by generic projection, and is sharp up to its constant.The higher-dimensional statement follows by projecting to R^2.
- Main goal: The paper targets near-sharp Szemerédi–Trotter-type bounds for incidences between points and k-dimensional algebraic varieties in R^d.The varieties satisfy pseudoline-type hypotheses, with the precise statement given in Theorem 2.1.
- Applications: The paper obtains a near-sharp point-line incidence bound in C^2 as a simpler, cheaper version of Tóth’s result, with slightly weaker bounds.The result supports applications of incidence bounds in mathematics and theoretical computer science, including sum-product, Kakeya, and distinct-distances problems.
- Method: The argument combines the polynomial method with induction on the point-set size.The inductive structure introduces an arbitrarily small epsilon loss in the exponents, while the resulting bounds are otherwise sharp.
- Method: Polynomial ham-sandwich partitioning divides the point set into a bounded number of cells, making incidences on bounded-degree boundaries easier to control.Cell interiors are handled using an induction hypothesis rather than trivial bounds, at the cost of an epsilon factor.
2. Main theorem
The main theorem gives near-sharp incidence bounds for points and bounded-degree k-dimensional varieties in R^d under pseudoline-type hypotheses. Its corollaries cover k-flats and several applications, including complex and quaternionic incidence problems, unit distances, sum-product, and rich affine transformations.
- Main theorem: Theorem 2.1 considers finite point sets and bounded-degree k-dimensional varieties in R^d with d ≥ 2k under five pseudoline-type axioms.The axioms constrain variety degree and dimension, pairwise incidences, smoothness, tangent spaces, and transversality.
- Applications: For k-flats in d ≥ 2k, the paper obtains a near-sharp Szemerédi–Trotter-type bound, with an ε loss and constants depending on ε and k.The result applies when any two k-dimensional affine subspaces intersect in at most one point.
- Applications: The framework yields cheap complex and quaternionic Szemerédi–Trotter bounds, including point-line incidences in C^2 and H^2.The complex-line result is presented as a cheap version of Tóth’s theorem.
- Applications: For complex unit circles, the paper derives a unit-distance bound for finite point sets in C^2 by applying the circle incidence estimate to circles centered at the points.Complex unit circles are real algebraic varieties of real dimension 2 and degree 4, with controlled intersections and point-determination properties.
3. A special case
The special-case proof combines polynomial partitioning with induction on the number of points, handling incidences inside cells and on the partitioning hypersurface separately. Crossing-number arguments control the boundary contribution, yielding the desired bound with an arbitrarily small epsilon loss.
- Polynomial partitioning: The proof uses polynomial partitioning in R^4 to divide the point set into M cells, each containing at most n/M points.A degree-D polynomial produces the decomposition R^4 = {Q = 0} ∪ Ω_1 ∪ ... ∪ Ω_M.
- Inductive split: Induction on the point set handles incidences inside cells, while direct estimates handle incidences on the partitioning hypersurface.The proof separates the cases according to whether most incidences lie outside or on {Q = 0}.
- Cell contributions: Each complex line intersects at most D^2 cells, allowing the total cell incidences to be bounded through the line-cell multiplicities.Restricting the partitioning polynomial to a parametrized line gives a degree-D polynomial in two real variables, whose complement has controlled connectivity.
- Boundary contribution: A smooth-point decomposition and crossing-number inequality bound incidences on the hypersurface, producing either a linear estimate or a 2/3-power estimate for each stratum.For each index i, the boundary incidences satisfy either |I_i| ≤ mD^2/2 + 4|P_i| or |I_i| ≤ 4(mD|P_i|)^2/3.
- Recursive perspective: The recursive viewpoint shows that repeatedly partitioning configurations creates about log_M n stages, while the induction loses only an arbitrarily small epsilon in the exponents.The resulting bounds are otherwise sharp up to this epsilon loss.
4. Some algebraic geometry
This section establishes the algebraic-geometric framework used later, relating varieties to polynomial equations, dimension, degree, smoothness, and controlled decompositions. It also clarifies how real varieties are represented through complex varieties and isolates lower-dimensional singular or exceptional pieces.
- Basic definitions: An algebraic set in C^d is a common zero locus of finitely many polynomials, and an irreducible algebraic set is called a variety.A hypersurface is the special case defined by one polynomial.
- Dimension and degree: The dimension of a variety is its maximal chain dimension, while its degree counts intersections with generic complementary affine subspaces.For an irreducible polynomial of degree D, the hypersurface it defines has degree D and dimension d − 1.
- Real and complex varieties: Real algebraic varieties are treated as the real points of associated complex varieties, allowing degree and dimension to be defined through the complex model.The authors note that distinct complex varieties can have the same real points, so the identification is technically non-unique.
- Complexity and degree: Bounded degree controls algebraic complexity: a degree-D variety can be defined using O_{d,D}(1) polynomials of degree at most D.Conversely, zero loci of finitely many bounded-degree polynomials decompose into O_{m,D,d}(1) varieties of controlled degree.
- Smoothness: Singular points of a bounded-degree k-dimensional variety lie in finitely many lower-dimensional bounded-degree varieties.Iterating this fact decomposes the variety into its smooth locus together with controlled lower-dimensional smooth pieces.
- Smoothness: The proofs use dimension reduction, projections, polynomial derivatives, and the implicit function theorem to establish smoothness outside controlled exceptional sets.These arguments support the later decomposition of real points and the treatment of tangent spaces.
5. Proof of main theorem
The proof proceeds by induction on dimension and the number of points, reducing higher-dimensional cases by generic projection and handling the sharp-dimension case with polynomial partitioning and auxiliary incidence bounds. The argument obtains the theorem but incurs an epsilon loss, while extensions to tangent cones and lower-dimensional varieties are handled inductively.
- Inductive setup: The proof uses induction on d+k, with the case k=0 handled directly because each point-variety contributes at most one incidence.The reduction then separates d>2k from the main case d=2k.
- Generic projection: For d>2k, a generic projection to R^2k preserves distinct points, varieties, incidences, degree bounds, smoothness, and tangent-space transversality.The induction hypothesis then applies to the projected configuration.
- Polynomial partitioning: A bounded-degree polynomial partitions R^d into O_d(D^d) cells, each containing O_d(|P|/D^d) points, while the boundary contribution is treated separately.The bounded number of cells makes the boundary varieties manageable in the induction.
- Sharpness and limitations: The inductive argument loses an arbitrarily small epsilon in the exponents, although the resulting bounds are otherwise sharp.A higher-degree partition could remove the epsilon loss in principle, but the resulting high-degree boundary is not controlled by the paper’s simple arguments.
- Inductive extensions: The proof closes the main theorem and extends its conclusions to settings using tangent cones, by decomposing singular portions into lower-dimensional varieties and applying induction.The tangent-cone formulation allows Axiom (iv) to be dropped.
Appendix A. Connected components of real semi-algebraic sets
Appendix A bounds the number of connected components where a bounded-degree polynomial does not vanish, first in Euclidean space and then on real algebraic sets. The proofs use induction, perturbation, and Bézout’s theorem to convert components into controlled critical points.
- O_d(D^d) bounds the connected components of {x ∈ R^d : P(x) ≠ 0} for a polynomial of degree at most D.
- The proof inducts on dimension, separates components meeting a cube boundary from interior components, and reduces the latter to critical points of a perturbed polynomial.
- Bézout’s theorem bounds generic fibers of the gradient map by (D − 1)^d = O(D^d), yielding the component estimate.
- O_{M,d,k}(D^k) bounds the connected components of {x ∈ V \ W : P(x) ≠ 0} when V has dimension k and bounded complexity.
- The general algebraic-set argument inducts on codimension, handles singular and boundary contributions inductively, and uses the normal bundle plus Bézout to count critical points.