Insights into Polynomials Vanishing on Cartesian Products and the 3POL Problem
This joint work explores polynomials vanishing on Cartesian products, focusing on the 3POL problem involving three sets of points and a 6-variate polynomial. It discusses the running time of solving the explicit 3POL problem and compares it to the well-studied 3SUM problem in theoretical computer science. The complexity of 3POL is analyzed in both uniform and non-uniform models, shedding light on the optimal bounds and advancements in solving the problem efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Polynomials Vanishing On Cartesian Products Esther Ezra joint work with Boris Aronov and Micha Sharir
The 3POL problem 3POL: A, B, C three sets of points in the plane, |A|=|B|=|C| = n. F a 6-variate polynomial of constant degree. Goal: Decide if there is a triple a A, b B, c C, s.t. F (a, b, c) = 0 . A restricted variant of this problem: Explicit 3POL: A, B two sets of points in the plane, |A|=|B |= n. C - a set of n real numbers. F a 4-variate polynomial of constant degree. Goal: Decide if there is a triple a A, b B, c C, s.t. c = F (a, b) .
Running time Solving (explicit) 3POL: Easy to do in ~n 2time: Sort all values F(a, b) in ~n 2time, then apply a binary search on each c C . Can we solve 3POL in subquadratic time? It is strongly believed that one cannot make it in n 2 time, > 0. Resort to non-uniform algorithms (count only a specific type of operations). Can we solve 3POL in subquadratic time in a non-uniform model?
3POL vs. 3SUM When A, B, C are one-dimensional, F is the sum function, 3POL becomes 3SUM: 3SUM: A, B, C three sets of n real numbers each. Can be solved in ~O(n 2) time. Goal: Decide if there is a triple a A, b B, c C, s.t. a + b + c = 0 . A well studied problem in theoretical computer science. [Gajentaan, Overmars 95]: On a class of n2-hard problems Introduced the notion of 3SUM-hardness (n2-hardness). Showed many problems to be 3SUM-hard.
3SUM-hard problems: Examples Given a set of (non-intersecting, axis- parallel) line segments, is there a line that separates them into two non-empty subsets? Given a set of (infinite) strips in the plane, do they fully cover the unit square? Given a set of points in the plane decide if three of them are collinear? Collinearity testing
3SUM in the non-uniform model 3SUM can be solved in O(n 2) number of comparisons of the form a + b < , > = c . 3-linear decision tree model. . Theorem [Erickson 1999, Ailon & Chazelle 2005]: This bound is optimal if we allow only such comparisons. So for many years it was believed that 3SUM requires quadratic time. Then in 2014 Gr nlund and Pettie showed a dramatic development: 3SUM can be solved with only n 3/2 ??? ?comparisons of the form a + b < , > = c + d . In 2015 Gold and Sharir improved bound to n 3/2. 4-linear decision tree model. .
Linear (algebraic) decision tree model The input data is expensive to access. Count only sign tests of linear (constant-degree polynomial) expressions f (x), evaluated on the input x (set of numbers, points, etc.) All other operations are for free (But are not allowed to touch the input explicitly) v f (x) A popular model in theoretical computer science. (Can solve NP-hard problems in polynomial time, e.g., SUBSETSUM) > 0 < 0 = 0 YES / NO
Current state of the art In 2017 Kane, Lovett, and Moran showed a breakthrough result: In the linear decision tree model 3SUM can be solved in only O(n log 2 n ) comparisons! (In fact, they showed this bound holds for k-SUM.) Number of variables in sign tests is larger. This result is based on a point-location mechanism in high-dimensional hyperplane arrangements (dim = n). So O(n log 2 n ) is the bound on the number of linear sign tests required to locate a query point in the arrangement. Works when hyperplanes have low complexity : Their coefficients are integers, and their L1-norm is small.
Current state of the art For hyperplanes with arbitrary coefficients, the mechanism of [E. Sharir 2017] yields O(n 2 log n ) linear sign tests. Beyond the scope of 3SUM: In d # tests ~ d 2. But both techniques of [Kane-Lovett-Moran 2017] and [E. Sharir 2017] are difficult to generalize to non-linear tests. This is the situation in the 3POL problem. Hyperplanes are replaced with algebraic surfaces. 3POL, a reminder: A, B, C three sets of points in the plane, |A|=|B|=|C| = n. F a 6-variate polynomial of constant degree. Goal: Decide if there is a triple a A, b B, c C, s.t. F (a, b, c) = 0 .
Collinearity testing A special and important case of 3POL is collinearity testing. To test whether a, b, c are collinear: Test whether (orientation test) 1 1 1 ?? ?? ?? ?? ?? ?? = 0 Input: a point in 6n (three sets A, B, C each with 2n variables). Determinant: a 6-variate quadratic polynomial (in 6 of the 6n coordinates) Need an algebraic decision tree model. Sign tests are polynomials of degree 2.
Collinearity testing: State of the art Recall that collinearity testing is 3SUM-hard. Still, it was much less studied than 3SUM. Previous work: [Erickson Seidel 1993]: If one allows to use only orientation tests, then (n 2) tests are needed in the worst case. More general algebraic sign tests? - This was considered by [Barba et al. 2017] when A, B, C are one- dimensional (e.g., each set lies on an algebraic curve).
The work of Barba et al. One-dimensional 3POL: A, B, C three sets of n real number. F a trivariate polynomial of constant degree. Goal: Decide if there is a triple a A, b B, c C, s.t. F (a, b, c) = 0 . [Barba at al 2017]: one-dim 3POL can be solved in O (n 12/7 + ) algebraic sign test. Corollary [Barba at al 2017]: When each of A , B, C is contained in a constant-degree polynomial curve in the plane, collinearity testing can be solved in O (n 12/7 + ) algebraic sign test.
The purely combinatorial state of the art The Elekes-Ronyai-Szabo Theory: A, B, C three sets of n real number. F a trivariate polynomial of constant degree. Question: At how many points of the grid A B C can Fvanish? (i.e., for how many triples a A, b B, c C, we have F (a, b, c) = 0 ?) Obvious answer: O (n 2) . Roughly speaking, for any pair a A, b B there is only a constant number of values c C, for which F (a, b, c) = 0 . Example: A = B = C = {1, 2, . . . , n} and F(a, b, c) is c (a + b).
The Elekes-Ronyai-Szabo Theory: But the question is what properties should F = F(x,y,z) have in order to have a subquadratic number of triples. Problem has been studied in two batches: The bivariate case: F(x, y, z) = z f (x, y) [Elekes and R onyai, 1999, 2000] . (Simplified and) improved: [Raz, Sharir and Solymosi, 2016] The general case: [Elekes and Szabo, 2012] . (Simplified and) improved: [Raz, Sharir and de Zeeuw, 2016]
The bivariate case: Theorem ([Elekes-R onyai, 2000], [Raz, Sharir, Solymosi 2016]): If z f(x, y) vanishes on (n 2) points of some A B C, with |A| = |B| = |C| = n , then f must have the special form f (x, y) = p (q(x) +r(y) ) or f (x, y) = p (q(x) r(y) ) , for suitable univariate polynomialsp, q, r . If f does not have the special form, then the number of zeros is always O (n 11/6) . Examples of special form: A = B = C = {1, 2, . . . , n} and F(x, y) = x + y . A = B = C = {1, 2, 4, . . . , 2n} and F(x, y) = x y .
The general case: Theorem ([Elekes-Szabo, 2012], [Raz, Sharir, de Zeeuw 2016]): If F = F(x, y, z) does not have a special form, then the number of zeros is always O (n 11/6) . Special form is technical and complicated to describe (we do not present it here). Back to Collinearity Claim: There are sets A, B, C of points |A|=|B|=|C|=n, in the plane that form (n 2) collinear triples.
Number of collinear triples There are many constructions that yield (n 2) collinear triples. All of them fall into the special form of Elekes and Szabo. We present one of them based on point-line incidences constructions: [Elekes and Szabo, 2012] The sets A, B, C lie on the lines x = 0, 1, 2, The y-coordinates are 1, 2, n . The lines y = ax +b have integer coefficients, 0 a n/4, 1 b n/2 , each of them contains a collinear triple.
Number of collinear triples There are point structures for which a subquadratic number of collinear triples is guaranteed: Theorem [Raz, Sharir, de Zeeuw 2016]: Any n points on an (irreducible) algebraic curve of constant degree determine ~O (n 11/6) proper collinear triples, unless the curve is a line or a cubic. There is a matching result for three sets of points In spite of this progress, these results are merely combinatorial. Open problem: Can one answer collinearity testing in subquadratic time (in the RAM model) if the points do not lie on a line of a cubic?
Collinearity testing Still, in the algebraic decision tree model, one can answer collinearity testing in subquadratic time when A, B, C lie on algebraic curves. [Barba at al 2017]. We describe the algorithm of [Barba at al 2017]. For simplicity, consider the bivariate case z = f (x, y) . Approach: Implicitly sort f (A,B) = { f (a, b) | a A, b B} , and search through the sorted list with each c C . Na ve sorting takes quadratic time, but the implicit sorting would be much faster!
Algorithm: based on Fredmans trick. g > 0 a partition parameter. Partition A and B into n/g blocks of size g : A1, . . . ,An/g , B1, . . . ,Bn/g. Sort f (Ai, Bj) for every i and j, using Fredman s trick: Consider quadruples, a, a A , b, b B , compare f (a, b) with f (a , b ) : Define a curve b,b = { (a, a ) | f (a, b) = f (a , b ) } b,b partitions the plane into positive region, where f (a, b) > f (a , b ) and negative region, where f (a, b) < f (a , b ) Locating (a, a ) among these regions gives the outcome of the comparison
Implicit sorting becomes point location Collect all the curves b,b for (b, b ) Bj , over all j . Obtain a set of O (g 2 (n / g) ) = O (ng) curves. Form the set of ng points P = { (a, a ) | a, a Aj , over all j } . Locate the ng points of P in the arrangement A( ) of ng curves. Get the answers to all comparisons. Given these comparisons, sort all values f (a, b)for free. This is the implicit (non-uniform) sorting. Search with the points of C .
Implicit sorting become point location Point location: Lemma: Locating the ng points of P in the arrangement of the ng curves of takes O( (ng) 4/3+ ) time. Not true in general, but true here, exploiting symmetry between points and curves, and geometric duality (a standard range searching mechanism).
Point location and range searching Searching with C: Main issue: For c C, How many pairs Ai , Bjare such that c is in the range of f (Ai , Bj ) ? Claim: c is relevant for only O(n/g) pairs Ai, Bj . Indeed, the curve f (x, y) = c crosses each of the 2n /g grid lines that separate the Ai s or the Bj s in O (1) points. ? log ? ? Find these pairs and search in each: O time. ?2log ? ? Running time over all c C : O
The overall cost ?2 4 3+ ?+ ? ?? ?log? Balance with g n 2/7 and get O (n 12/7+ ) .
Our results Can do collinearity testing for A B C , with O (n 28/15 + ) polynomial sign tests, where A is two dimensional, B, C are one dimensional (each lying on a curve) . This bound is extended to higher dimensions. A, B, C are two dimensional. We can test whether some triple in A B C satisfy two polynomial equalities, with O (n 24/13 + ) polynomial sign tests. As a result, we can test whether some triple in A B C spans a triangle similar to a given one, with O (n 24/13 + ) sign tests.
Our results We extend the steps in the algorithm of [Barba at al 2017] to Cartesian products of planar point sets. Main tool: Cartesian products of polynomial partitioning. Polynomial Partioning for planar point sets: A decomposition of the plane into open (simply-shaped) cells, s.t. each cell meets a small fraction of the points.
Polynomial partitioning for points Polynomial ham sandwich theorem [Guth Katz 2015]: Let P be a set of n point in R2. Let D > 0 be a real parameter. Then there is a polynomial f of degree D , whose zero set Z (f ) partitions P into O (D 2) sets with at most n / D 2points in each. Each set lies in a distinct connected component (open cell) of Rd \ Z(f ) . f is called a partitioning polynomial. Based on the polynomial ham-sandwich theorem of [Stone-Tukey 42] for finite volume open sets. By Warren s Theorem: #cells = O(D 2 ). A potential issue: Number of points in P that lie on Z(f ) can be arbitrarily large. However, for points in the plane this can be easily handled. [Solymosi and de Zeeuw 2018]
Polynomial partitioning: An illustration A partitioning polynomial f of degree D. A line l meets Z(f ) in at most D points (unless l Z(f ) ) . Black curve = Z(f )
