Source-linked AI summary
Discrepancy of geometric incidences
Azem Adibelli, István Tomon
TL;DR
The paper studies how evenly finite point sets can be colored with respect to hyperplanes and bounded-complexity affine algebraic sets. It develops algebraic and linear-algebraic methods yielding improved real-incidence bounds and communication-complexity applications, while leaving sharpness unresolved in higher dimensions.
Problem
The paper asks for the order of magnitude of discrepancy for hyperplanes and affine algebraic sets of bounded dimension and degree.
Method
The paper combines algebraic geometry with analytic and linear-algebraic techniques, including γ2-norm lower bounds for dense point-hyperplane incidence matrices and totally real number fields.
Results
Real algebraic sets achieve an improvement over the baseline 1/2 − 1/(2(D+1)), while algebraic-integer point-hyperplane matrices can have R(M) = O(1) and γ2(M) ≥ n^1/2−ε.
Takeaways & Limitations
The results show that the VC-dimension baseline can be improved for real algebraic sets, and the methods yield communication-complexity separations through point-hyperplane incidence matrices.
Takeaways & Limitations
The authors believe the lower bound is sharp but prove weaker upper bounds for d ≥ 3, leaving the gap open.
Abstract
from arXiv · showhide
We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.
1 Introduction
The paper asks how evenly point sets can be colored for hyperplanes and bounded-complexity algebraic sets, overcoming higher-dimensional obstacles. It proves improved upper bounds, near-matching hyperplane lower bounds, and a communication-complexity separation.
- Background: Combinatorial discrepancy minimizes the largest red-blue imbalance over a set system by choosing an appropriate coloring.Geometric discrepancy applies this framework to ranges and point sets in Euclidean space.
- Problem: The central problem is to determine discrepancy orders for hyperplanes and affine algebraic sets of dimension at most D and degree at most k.The ambient dimension for algebraic sets can be reduced to D+1 by projection.
- Lower bounds: Higher-dimensional hyperplane discrepancy is difficult because planar point-line arguments do not extend, and simple incidence sparsity already fails in dimension d≥3.For points on a line and hyperplanes containing it, the incidence graph can have degeneracy n.
- Upper bounds: Every n-point set admits discrepancy at most n^(1/2−1/(2(D+1))−ε) for affine algebraic sets of dimension at most D and degree at most k.Here ε depends on D and k, improving the VC-dimension baseline ˜O(n^(1/2−1/(2(D+1)))).
- Communication complexity: The methods yield Boolean matrices with randomized communication cost O_c(1) and γ2-norm at least n^(1/2−c), producing an extreme communication-complexity separation.The construction extends point-line incidence matrices to high-dimensional point-hyperplane incidence matrices.
2 Preliminaries
The preliminaries define discrepancy and hereditary discrepancy through set systems and incidence matrices, then introduce γ2-norm tools used to estimate these quantities.
- 2.1 Discrepancy: Hereditary discrepancy is the maximum discrepancy over all restrictions of the set system to subsets of the ground set.For extremal range-space behavior, discrepancy and hereditary discrepancy differ little, while the hereditary version is easier to estimate algebraically.
- 2.1 Discrepancy: An incidence matrix has columns indexed by ground-set elements, rows indexed by sets, and entry 1 exactly when the element belongs to the set.This matrix viewpoint connects coloring discrepancy with matrix norms.
- 2.1 Discrepancy: A set system’s discrepancy is the minimum, over red-blue colorings, of the maximum red-blue count difference across its sets.For incidence matrix M, this is written as min χ∈{−1,1}^X ||Mχ||∞.
- 2.2 Factorization norms: γ2 is defined through factorizations M=UV, controlling the maximum row ℓ2-norm of U and maximum column ℓ2-norm of V.The preliminaries also record trace-norm, tensor-product, direct-sum, blow-up, and degeneracy inequalities.
- 2.2 Factorization norms: The γ2-norm approximates hereditary discrepancy up to logarithmic factors, and bounded VC-dimension permits replacing log m by log n.This relationship motivates using γ2 as an algebraically tractable proxy.
- 2.2 Factorization norms: A concatenation lemma bounds γ2 when each block has bounded γ2 and every row is nonzero in at most t blocks.The proof concatenates block factorizations and controls the resulting row and column norms.
3 Lower bounds
The lower-bound framework uses trace and γ2-norm inequalities to turn incidence-matrix structure into discrepancy lower bounds, first in dimension three and then in higher dimensions. A four-dimensional orthogonality construction yields γ2(M) ≥ Ω(n^1/4/√log n), while a Fourier-based approach extends the construction to higher-dimensional point-hyperplane incidences.
- Trace bound: The trace bound and related γ2-norm inequality derive lower bounds from the Schatten norms of an incidence matrix.For Boolean matrices, the Schatten 2-norm counts one-entries, while the Schatten 4-norm counts four-cycle homomorphisms.
- Trace bound: C4-free incidence matrices make these inequalities effective, recovering the point-line discrepancy lower bound Ω(n^1/6).Point-line incidence matrices are C4-free, and the extremal Szemerédi-Trotter configuration supplies the relevant construction.
- Dimension 3 via four-cycles: In dimension three, the orthogonality matrix on Q = {−m, ..., m}^4 \ {0} is a blow-up of a point-hyperplane incidence matrix in R3.A generic projection converts the projective incidence representation into at most n points and n hyperplanes without changing the γ2-norm.
- High dimension via Fourier transform: The proof counts orthogonal lattice-vector pairs and rational subspaces using primitivity, Plücker vectors, and bounds on four-tuples.Key estimates include O_d(T^(d−1)/q) orthogonal vectors for a primitive vector and O(T^4) two-dimensional subspaces with bounded Plücker coordinates.
4 Upper bound — Hyperplanes
The hyperplane upper-bound proof combines simplicial space partitioning with a three-way decomposition of incidences, yielding recursive γ2-norm bounds and improved exponents in every dimension.
- Partitioning: Simplicial partitioning produces at most 2r subsets, each of size between n/(2r) and n/r, with every hyperplane crossing O(r^(1−1/d)) cells.Each subset lies in the relative interior of a possibly lower-dimensional simplex.
- Incidence decomposition: The incidence matrix is decomposed into degenerate, spanning, and hybrid matrices whose γ2-norms are bounded separately.The decomposition is M = Mdeg + Mspn + Mhyb.
- Component bounds: Degenerate incidences reduce to an incidence matrix on generic representatives, while spanning incidences are controlled by affinely independent point sets that uniquely determine hyperplanes.For degenerate incidences, γ2 is bounded by the lower-dimensional function f_d(q); spanning columns contain O((n/r)^(d−1)) entries.
- Component bounds: Hybrid incidences reduce after projection to lower-dimensional hyperplane incidences, and crossing sparsity enables a matrix-concatenation bound.Combining the three bounds yields a recursive inequality for f_d(n).
- Exponents: The resulting exponents include α_2 = 1/6, α_3 = 2/7, and α_4 = 63/178.The paper states that further calculations give the general-dimensional exponent.
5 Upper bound — Algebraic sets
For bounded-complexity algebraic sets, the proof replaces simplicial partitions with polynomial partitioning and uses projection, incidence categories, and crossing bounds to obtain an improved discrepancy exponent.
- Algebraic preliminaries: Affine Bézout bounds and real-locus containment transfer algebraic dimension and degree control to the real incidence problem.The argument uses complex varieties defined over R and applies the resulting bounds to their real points.
- Projection: A projection lemma maps D-dimensional irreducible varieties into R^(D+1) as irreducible hypersurfaces without changing incidences with the finite point set and without increasing degree.The projection is injective on the finite point set and preserves incidence equivalence.
- Main result: Theorem 5.3 establishes an ε = Ω(D^-2 …) improvement for incidence matrices of affine algebraic sets of dimension at most D and degree at most k.The supplied theorem statement is truncated after the dependence on D and k.
- Polynomial partitioning: Polynomial partitioning cuts n points into O(T^d) cells, each containing O(n/T^d) points, while bounded-degree varieties intersect only O(T^D) cells.The partition is induced by the zero set of a polynomial of degree at most T.
- Cell crossing: A hypersurface of degree at most k intersects at most O_{d,k}(T^(d−1)) cells cut by a degree-T polynomial.This is the cell-crossing bound used in the partitioning argument.
- Polynomial partitioning: The proof separately tracks points on the partition zero set through multiple rounds, forming a partition tree for the exceptional incidences.This addresses the main difficulty introduced by polynomial partitioning.
- Incidence categories: The incidence matrix is split into four categories, including zero-set, spanning, and non-spanning cell incidences, and the four resulting matrices are bounded individually.The figure distinguishes spanning from non-spanning incidences inside cells.
6 Communication complexity
The communication-complexity application constructs high-dimensional point-hyperplane incidence matrices with very large γ2-norm but low randomized communication cost, producing an extreme deterministic-versus-randomized separation.
- Setup: The paper studies the gap between randomized communication cost R(M) and deterministic equality-oracle cost DEQ(M), which is controlled by the γ2-norm.Public-coin protocols allow error probability at most 1/3, while equality-oracle queries cost one unit.
- Prior work: Point-line incidence matrices previously achieved R(M) = O(1), DEQ(M) = Ω(m), and γ2(M) ≥ n^(1/6−ε).The paper seeks to extend this phenomenon to point-hyperplane incidences.
- Main result: For every c > 0, the paper constructs n × n Boolean matrices with R(M) = O_c(1) and γ2(M) ≥ n^(1/2−c), near the maximum possible γ2-norm O(n^(1/2)).These matrices arise from point-hyperplane incidences over grids of algebraic integers.
- Main result: Theorem 6.1 provides incidence matrices of at most n points and n hyperplanes in R^d achieving the stated lower-bound regime for infinitely many n.The displayed quantitative statement in the supplied passage is truncated.
- Construction: The construction follows Goh and Hatami’s strategy, using totally real number fields, generating characters, and a new γ2 lower bound for dense point-hyperplane incidence matrices.Analytic and linear-algebraic techniques replace the C4-free argument used for point-line incidences.
- Randomized protocol: The randomized protocol samples a shared embedding index and communicates rounded coordinate evaluations using O(d(log d + log R)) bits.The protocol distinguishes zero and nonzero inner products with probability at least 2/3.
Declaration on the use of AI
The authors disclose that ChatGPT 5.5 and 5.6-Sol assisted with extending an upper-bound proof and proving a lemma, with all suggestions reviewed by the authors.
- Disclosure: ChatGPT 5.5 and 5.6-Sol contributed to extending Theorem 4.1 to Theorem 5.3 and to proving Lemma 6.6.The authors state that they reviewed all AI-generated suggestions and retain responsibility for correctness and originality.