Chapter 43: The Polynomial Method

Can a low-degree polynomial rule out a large configuration?

Six points need not require six unrelated equations. Over the rational numbers, consider

$$S=\{(0,0),(1,0),(2,0),(0,1),(1,1),(2,1)\}.$$

The quadratic $f(X,Y)=Y(Y-1)$ vanishes at all six points because they lie on two horizontal lines. Now suppose a third line, not one of those two, contained three distinct points of $S$. Parametrize it as $(X,Y)=a+tv$, where $a$ is a point and $v\ne0$ is a direction vector. Substitution makes $f(a+tv)$ a polynomial in one variable of degree at most two. Its three distinct roots would force it to be identically zero. But a nonhorizontal line has nonconstant $Y$, so neither factor vanishes identically; another horizontal line has constant $Y$ different from zero and one. Both alternatives are impossible. Thus every other line contains at most two points of $S$.

This is the polynomial method in miniature: encode the configuration in a polynomial, extract a consequence of vanishing, and use degree to restrict what can occur. A nonzero univariate polynomial of degree $D$ over any field has at most $D$ distinct roots. Indeed, each root contributes a linear factor by polynomial division, and more than $D$ such factors would exceed its degree. Repeated roots count only once for this elementary statement.

In several variables, total degree is the largest sum of exponents in an appearing monomial. The polynomials of total degree at most $D$ in $n$ variables form a vector space of dimension $\binom{n+D}{n}$. Each requirement $f(s)=0$ is a homogeneous linear equation in its coefficients. Fewer points than coefficients therefore guarantee a nonzero vanishing polynomial. Exactly as many points as coefficients may still leave a solution, as the six-point quadratic illustrates, but dimension counting alone no longer guarantees it.

A second route converts polynomials into a rank certificate. Evaluate a collection of polynomials at a collection of points. If the evaluation matrix is diagonal with nonzero diagonal, its columns are independent. The number of columns is then bounded by the dimension of the polynomial space. The advanced sections develop this principle for intersection families and replace matrices by three-variable arrays for cap sets.

The root bound, coefficient-space argument, and explicit six-point instance are the chapter foundation. The numbered sections are optional research extensions, and the core investigation below uses only these supplied facts. Earlier connections are extremal set theory, additive combinatorics, geometric combinatorics, and finite geometry.

43.1 Polynomial interpolation and finite-field algebra

Optional extension; not required to complete the chapter foundation.

Let $F$ be a field, let $A\subset F$ consist of $m$ distinct elements, and prescribe values $h(a)$ for $a\in A$. The interpolation polynomial

$$H(X)=\sum_{a\in A}h(a)\prod_{b\in A\setminus\{a\}}\frac{X-b}{a-b}$$

has degree at most $m-1$ and takes the desired values. Denominators are nonzero because the nodes are distinct. Uniqueness follows by applying the root bound to the difference of two interpolants. Products of these basis polynomials interpolate on Cartesian grids in several variables.

Over $\mathbb F_q$, the formal polynomial $X^q-X$ is nonzero but its evaluation function is zero. Replacing powers using $X_i^q=X_i$ gives each polynomial function a representative of degree at most $q-1$ in each variable. This representative is unique. To prove uniqueness, induct on the number of variables: after fixing all but the last coordinate, a polynomial of degree less than $q$ has $q$ roots, so all its coefficients vanish; induction applies to those coefficient polynomials. Formal degree and functional complexity are different invariants.

Solved example. In $\mathbb F_3$, interpolate values $h(0)=1,h(1)=0,h(2)=0$. The result is $H(X)=1-X^2$. Its values are $1,0,0$ because both nonzero elements square to one. The function detects zero, and its product across coordinates detects the zero vector.

A useful established zero-count bound is: if nonzero $f\in\mathbb F_q[X_1,\ldots,X_n]$ has total degree $D$, it has at most $Dq^{n-1}$ zeros in the full grid. Proof sketch: if $D\ge q$, the bound is immediate from the grid size. Otherwise write $f$ as a degree-$k$ polynomial in the last variable with nonzero leading coefficient of degree at most $D-k$. Inductively at most $(D-k)q^{n-2}$ choices of the first coordinates annihilate that coefficient. Each remaining fiber has at most $k$ roots, and each exceptional fiber has at most $q$. Combining gives the claim; when $D\ge q$, the displayed upper bound may be vacuous. The one-variable base case is the root bound. No other prerequisite is omitted.

The interpolation and grid-uniqueness machinery also appears in Alon's original Combinatorial Nullstellensatz paper. All facts used here are established elementary algebra; no conjectural uniqueness or interpolation statement is invoked.

Exercise. Count the zeros of $XY$ in $\mathbb F_3^2$ and compare with the degree bound. Hint: use the union of the coordinate axes. Solution: there are $3+3-1=5$ zeros; the total-degree-two bound is $2\cdot3=6$. A general bound need not be attained by every polynomial.

43.2 Combinatorial Nullstellensatz

Optional extension; not required to complete the chapter foundation.

A polynomial can have variable degrees too large for grid uniqueness yet still have a top coefficient that forces a nonzero grid value. The established coefficient form of Combinatorial Nullstellensatz, due to Alon, says the following. Let $t_1,\ldots,t_n$ be nonnegative integers, let $f\in F[X_1,\ldots,X_n]$ have total degree at most $t_1+\cdots+t_n$, and suppose the coefficient of $X_1^{t_1}\cdots X_n^{t_n}$ is nonzero. For finite sets $A_i\subset F$ with $\lvert A_i\rvert\gt t_i$, some point in $A_1\times\cdots\times A_n$ satisfies $f\ne0$.

Here is a proof by a coefficient functional. Shrink each $A_i$ to size $t_i+1$. For $a\in A_i$, put $w_i(a)=\prod_{b\in A_i\setminus\{a\}}(a-b)$. Univariate interpolation gives

$$\sum_{a\in A_i}\frac{a^r}{w_i(a)}=0\quad(0\le r\lt t_i),\qquad \sum_{a\in A_i}\frac{a^{t_i}}{w_i(a)}=1.$$

Apply the product of these functionals to each monomial of $f$. A monomial other than the target, with total degree at most the target degree, has some exponent below the corresponding $t_i$, so it contributes zero. The target contributes one. Consequently

$$\operatorname{coeff}_{X_1^{t_1}\cdots X_n^{t_n}}f=\sum_{a_i\in A_i}\frac{f(a_1,\ldots,a_n)}{\prod_i w_i(a_i)}.$$

A nonzero left-hand side forces some nonzero summand. This is a complete proof of the form used here, not a proof of every ideal-theoretic variant bearing the same name.

Exercise. Why can the same top-coefficient argument not be used for $(X-Y)^2$ over $\mathbb F_2$ with $t_1=t_2=1$? Hint: inspect the mixed coefficient. Solution: $-2=0$ in characteristic two. The polynomial still has nonzero values at unequal pairs, but this particular sufficient certificate disappears. Failure of a coefficient hypothesis does not prove that all evaluations vanish.

43.3 Alon's polynomial method

Optional extension; not required to complete the chapter foundation.

The coefficient tool becomes combinatorics when zero factors encode forbidden outcomes. Let $p$ be prime and $A,B\subseteq\mathbb F_p$ be nonempty. Their sumset is $A+B=\{a+b:a\in A,b\in B\}$. A polynomial application proves the established Cauchy–Davenport bound

$$\lvert A+B\rvert\ge\min\{p,\lvert A\rvert+\lvert B\rvert-1\}.$$

Write $r=\lvert A\rvert$, $s=\lvert B\rvert$. If $r+s\gt p$, the sets $A$ and $c-B$ intersect for every $c$, so every field element is a sum. Otherwise, suppose $\lvert A+B\rvert\le r+s-2$ and enlarge that sumset to $C$ of size $r+s-2$. The polynomial

$$f(X,Y)=\prod_{c\in C}(X+Y-c)$$

vanishes on $A\times B$. Its coefficient of $X^{r-1}Y^{s-1}$ is $\binom{r+s-2}{r-1}$, nonzero modulo $p$ because all involved factorials have arguments smaller than $p$. Section 43.2 supplies the contradiction. These are the algebraic application and hypotheses, rather than a second statement of the Nullstellensatz. A primary source for this polynomial treatment is Alon's paper.

Solved example. In $\mathbb F_5$, let $A=\{0,1\}$ and $B=\{0,2\}$. Their grid sums are $0,2,1,3$, so the sumset has four elements and exceeds the lower bound three. If only two sums were available, a quadratic product of two sum factors would vanish on the grid but have $XY$ coefficient two, impossible. The diagram shows both the actual arithmetic and the hypothetical certificate; it does not assert equality in the bound.

A parallel application is list coloring. For a graph with vertices $1,\ldots,n$, the graph polynomial $\prod_{ij\in E,\ i\lt j}(X_i-X_j)$ is nonzero at an assignment exactly when adjacent colors differ. A nonzero top coefficient therefore certifies a proper coloring from lists larger than its exponents. The difficult part in general is finding that coefficient, not defining the polynomial.

Exercise. For the path $1$–$2$–$3$, inspect $(X_1-X_2)(X_2-X_3)$ and give a sufficient list-size condition. Hint: use the coefficient of $X_1X_3$. Solution: it is $-1$, nonzero over every field, with exponents $(1,0,1)$. Any lists of distinct field elements of sizes at least $(2,1,2)$ admit a proper coloring. This is a proved sufficient condition, not an assertion about the optimal condition for every graph.

43.4 Polynomial-method proofs in extremal set theory

Optional extension; not required to complete the chapter foundation.

Encode a set $A\subseteq[n]=\{1,\ldots,n\}$ by its characteristic vector $\mathbf1_A\in\{0,1\}^n$. For another set $B$, the linear form $\sum_{i\in A}X_i$ evaluates at $\mathbf1_B$ to $\lvert A\cap B\rvert$. An intersection restriction can therefore become a zero condition.

Let $L$ be a set of $s$ allowed real intersection sizes. Suppose a family $\mathcal F$ satisfies $\lvert A\cap B\rvert\in L$ for distinct members and $\lvert A\rvert\notin L$ for every member. Define

$$f_A(X)=\prod_{\ell\in L}\left(\sum_{i\in A}X_i-\ell\right).$$

Its evaluation on $B$ is zero unless $B=A$, where it is nonzero. Thus the $f_A$ are independent as functions on the family's vectors: evaluate any alleged linear dependence at one vector to isolate its coefficient. On the Boolean cube replace every positive power $X_i^j$ by $X_i$. This preserves values and does not increase degree, leaving only squarefree monomials indexed by subsets of size at most $s$. Therefore

$$\lvert\mathcal F\rvert\le\sum_{j=0}^{\min(s,n)}\binom nj.$$

This is an established elementary polynomial bound with a complete proof here. Stronger uniform-family bounds require additional structure, developed next in the Frankl–Wilson intersection-theorem framework; the displayed sum should not be silently replaced by a single binomial coefficient without that extra argument.

Solved example. On $[4]$, consider the three sets $\{1,2\},\{1,3\},\{1,4\}$. Their distinct intersections have size one. With $L=\{1\}$, their polynomials are $X_1+X_2-1$, $X_1+X_3-1$, and $X_1+X_4-1$. Their three-by-three evaluation matrix is the identity. The degree-one Boolean space has dimension five, so the elementary bound gives at most five members; the actual three-member family need not saturate that bound.

Exercise. What breaks if $L$ contains the size of a member? Hint: examine the diagonal evaluation. Solution: its own polynomial also vanishes at that member, so the diagonal matrix may be singular and the independence argument fails. Off-diagonal vanishing alone is insufficient for a rank certificate.

43.5 Frankl–Wilson intersection theorem

Optional extension; not required to complete the chapter foundation.

Here is the uniform modular form of the established Frankl–Wilson theorem. Let $p$ be prime, let $L\subseteq\mathbb F_p$ have $s$ residues, and let $\mathcal F$ be a family of $k$-element subsets of $[n]$. Assume $s\le k$, $k\bmod p\notin L$, and $\lvert A\cap B\rvert\bmod p\in L$ for all distinct members. Then

$$\lvert\mathcal F\rvert\le\binom ns.$$

All sets have the same size, and the modulus is prime; neither qualification is decorative. Residues may collapse distinct integer intersection sizes, and diagonal nonvanishing still has to survive that collapse.

Proof mechanism and scope. Over $\mathbb F_p$, the polynomials from section 43.4 again yield a nonzero diagonal evaluation matrix. In the special case $k\lt p$, their multilinear reductions can be represented on the entire $k$-uniform layer by polynomials homogeneous of degree $s$. To see the degree-raising step explicitly, a squarefree monomial $X_T=\prod_{i\in T}X_i$ of degree $t\lt s$ obeys, on that layer,

$$\sum_{j\notin T}X_{T\cup\{j\}}=(k-t)X_T.$$

If $k-t$ is invertible, this raises degree by one. If it is zero, reduction needs the more careful uniform-layer argument of the original theorem. For a transparent fully proved special case, assume also $k\lt p$; then every $k-t$ for $t\lt s\le k$ is nonzero and repeated degree-raising proves that the restricted polynomial space has dimension at most $\binom ns$. Independence finishes the proof. Omitted prerequisite for the full stated theorem: the uniform-layer reduction when some $k-t$ vanishes modulo $p$. The simple division argument does not prove that case, and is not being presented as if it did.

Solved example. Take $p=3,k=2,s=1,L=\{1\}$ on $[4]$. A pairwise-intersecting family of two-element sets has distinct intersection size one, while diagonal size two is excluded from $L$. The theorem gives $\lvert\mathcal F\rvert\le4$. For a member $A$, the polynomial $\sum_{i\in A}X_i-1$ can be made homogeneous on the two-uniform layer by replacing $1$ with $2\sum_iX_i$, since $2\cdot2=1$ modulo three. This displays the additional dimension reduction from five affine coefficients to four linear coefficients. The example's three-set star is admissible; the theorem need not be sharp for these parameters.

Exercise. May a family of three-element subsets be treated with $p=3,L=\{0\}$ when all distinct intersections have size divisible by three? Hint: test the diagonal residue. Solution: no: the diagonal size also has residue zero, violating $k\bmod p\notin L$. This is a hypothesis failure, not a counterexample to the theorem.

43.6 Polynomial ham-sandwich methods

Optional extension; not required to complete the chapter foundation.

Real polynomials can divide space by sign rather than vanish on a prescribed set. Let $\mathcal P_D(\mathbb R^d)$ be the space of degree-at-most-$D$ polynomials, of dimension $M=\binom{d+D}{d}$. A polynomial bisects a finite point set if each of its strict positive and strict negative regions contains at most half the points; points on its zero set count toward neither side.

The established discrete polynomial ham-sandwich statement says that any $M-1$ finite point sets in $\mathbb R^d$ admit a single nonzero polynomial of degree at most $D$ simultaneously bisecting them. Lift a point to its vector of nonconstant monomial values, in $\mathbb R^{M-1}$. A hyperplane there pulls back to a polynomial here. The ordinary ham-sandwich theorem in that dimension gives the simultaneous cut. Proof sketch and omitted prerequisite: the ordinary ham-sandwich theorem follows from Borsuk–Ulam; its topological proof is not reproduced. For finite sets, approximate points by small balls, bisect their measures, normalize the coefficients, and take a convergent subsequence. Points with a strictly positive or negative limiting value eventually have that sign, giving the asserted weak cardinality inequalities. See the primary partitioning application of Guth and Katz.

Solved example. Let $P_1=\{(-2,0),(2,0)\}$ and $P_2=\{(-1,1),(1,1)\}$ in $\mathbb R^2$. The degree-one polynomial $f=X$ bisects both, placing one point of each on either side and none on the zero line. Here $M=3$, so two simultaneous sets match the theorem's guarantee.

For comparison, three points lying on the line $X=0$ are also bisected by $X$: both strict sides contain zero points. Bisection alone does not guarantee that points avoid the cut. This boundary issue becomes central in partitioning.

Exercise. How many finite sets can the theorem simultaneously bisect using quadratics in the plane? Hint: count coefficients. Solution: the monomials $1,X,Y,X^2,XY,Y^2$ give $M=6$, hence five sets. The theorem is an existence statement; this count does not supply an efficient algorithm for finding the coefficients.

43.7 Polynomial partitioning

Optional extension; not required to complete the chapter foundation.

For a finite point set $P\subset\mathbb R^d$ and an integer $r\ge2$, polynomial partitioning supplies a nonzero polynomial $f$ of degree $O_d(r^{1/d})$ such that every connected component of $\mathbb R^d\setminus Z(f)$ contains at most $\lvert P\rvert/r$ points. Here $Z(f)=\{x:f(x)=0\}$, and the subscript on $O_d$ means its constant may depend on the fixed dimension. The theorem of Guth and Katz is established; it makes no corresponding occupancy promise for points lying on $Z(f)$.

Proof sketch. Repeatedly bisect all current sign classes at once. At stage $j$, there are at most $2^{j-1}$ classes, so a polynomial of degree $O_d(2^{j/d})$ has enough coefficients to bisect them. Multiply the stage polynomials. After $J$ stages, every surviving sign class has at most $\lvert P\rvert/2^J$ points; choose $2^J\ge r$. Summing the stage degrees is a geometric series of order $r^{1/d}$. A connected component avoiding the product's zero set has a fixed sign for every factor and therefore lies in one sign class. Dependencies: section 43.6's ham-sandwich theorem; no bound on the number of connected components is required for this occupancy proof. Such a component bound is an additional real algebraic-geometric input when analyzing algorithms or incidences.

Solved example. For the sixteen points $P=\{1,2,3,4\}^2$, choose

$$f(X,Y)=(X-5/2)(Y-5/2).$$

Its zero set consists of two lines. The four connected components each contain four points, so this is an explicit partition for $r=4$. The positive region has two disconnected quadrants; a sign value is not the same thing as a connected component. No grid point lies on these particular cuts.

A line not wholly contained in $Z(f)$ meets it at most $\deg f$ times and therefore visits at most $\deg f+1$ complementary components. This elementary crossing bound is one reason a balanced algebraic partition is useful in geometric divide-and-conquer.

Exercise. Replace the cut $X=5/2$ by $X=2$ in the example. What happens to the four points with first coordinate two? Hint: evaluate the product. Solution: they lie on $Z(f)$ and enter none of the complementary components. They must be retained as a boundary subproblem; deleting them would make an incidence count incorrect.

43.8 Finite-field Kakeya problems

Optional extension; not required to complete the chapter foundation.

A Kakeya set $K\subseteq\mathbb F_q^n$ contains an affine line $a+tv$, $t\in\mathbb F_q$, in every nonzero direction $v$. Scalar multiples give the same direction, and the base point $a$ may vary. Dvir's primary paper established that such sets have size at least a positive dimension-dependent constant times $q^n$. The classical interpolation argument below gives the explicit bound

$$\lvert K\rvert\ge\binom{q+n-1}{n}.$$

This is an established lower bound; it is not presented as the optimal constant or the most recent refinement. The finite-field theorem is proved, and nothing here asserts a solution to the distinct real Euclidean Kakeya problem.

Proof. A smaller set admits a nonzero vanishing polynomial of degree at most $q-1$ by coefficient counting. Let its degree be $d$ and its homogeneous top part be $f_d$. The degree is positive since $K$ is nonempty. On every line supplied by the Kakeya condition, the restriction has $q$ roots and degree less than $q$, so it is identically zero. Its coefficient of $t^d$ is $f_d(v)$, forcing that value to vanish in every nonzero direction. It also vanishes at zero by homogeneity. The grid-uniqueness argument of section 43.1 forces $f_d=0$, a contradiction. All prerequisites for this proof have been supplied.

Solved example. In $\mathbb F_2^2$, the three points $(0,0),(1,0),(0,1)$ form a Kakeya set: their three pairs give the directions $(1,0),(0,1),(1,1)$. The bound is $\binom32=3$, hence this set is minimum. In this field a line has only two points, so a three-point triangle already realizes every direction; drawing long Euclidean segments would obscure that fact.

Exercise. Explain why counting all possible affine lines would impose an unnecessarily strong condition. Hint: distinguish direction from position. Solution: Kakeya requires one line per direction, not every parallel translate. In the binary example there are six affine lines but only three directions, and the three-point set contains three lines rather than all six.

43.9 Slice rank and the cap-set theorem

Optional extension; not required to complete the chapter foundation.

A cap set $A\subseteq\mathbb F_3^n$ has no three distinct points satisfying $x+y+z=0$. If two entries in such an equation coincide, the third coincides too, since the characteristic is three. Thus all solutions in a cap set are diagonal.

For a function $T:A^3\to F$, a slice is a term of one of the forms $u(x)v(y,z)$, $u(y)v(x,z)$, or $u(z)v(x,y)$. Its slice rank is the minimum number of slices needed to express $T$. The established diagonal lemma says that a tensor supported exactly on $(a,a,a)$, with nonzero values there, has slice rank $\lvert A\rvert$. Omitted prerequisite: the lower-bound proof of this tensor lemma, an extension of matrix-rank linear algebra, is not reproduced; see Tao's original symmetric formulation. A matrix flattening alone does not prove a slice-rank lower bound.

Define $m(n,d)$ as the number of exponent vectors in $\{0,1,2\}^n$ with coordinate sum at most $d$. The established Ellenberg–Gijswijt cap-set theorem, in slice-rank form, gives

$$\lvert A\rvert\le3m\bigl(n,\lfloor2n/3\rfloor\bigr).$$

Proof sketch. The polynomial function

$$T(x,y,z)=\prod_{i=1}^n\bigl(1-(x_i+y_i+z_i)^2\bigr)$$

is the indicator of $x+y+z=0$. On $A^3$ it is diagonal with value one. Every monomial in its expansion has total degree at most $2n$ and exponent at most two in each coordinate variable. At least one of the three variable blocks has degree at most $2n/3$. Assign each monomial to one such block, breaking ties consistently, and group by that block's monomial. This produces at most $m(n,\lfloor2n/3\rfloor)$ slices for each block, hence at most three times that number overall. Apply the diagonal lemma. That lemma is the sole omitted algebraic prerequisite in this sketch.

For any real $0\lt t\lt1$, a generating-function bound gives

$$m\bigl(n,\lfloor2n/3\rfloor\bigr)\le t^{-2n/3}(1+t+t^2)^n.$$

Indeed, each counted exponent vector contributes a weight at least $t^{2n/3}$ to the full expansion. Taking $t=1/2$ gives $\lvert A\rvert\le3c^n$ with $c=(7/4)2^{2/3}\lt3$. The strict inequality follows by cubing: $c^3=343/16\lt27$. This explicit classical exponential bound is sufficient here; no sharp-growth or current-record claim is being made.

Solved example. For $n=1$, $A=\{0,1\}$ is a maximum cap set: the full field contains the distinct zero-sum triple $0,1,2$. On this two-element set the tensor is supported on $(0,0,0)$ and $(1,1,1)$, so it has slice rank two. The theorem's general bound is three and is not sharp for this instance.

Exercise. Compute $m(2,1)$ and check the bound for $A=\{0,1\}^2$. Hint: list exponent vectors and reason coordinatewise. Solution: the vectors are $(0,0),(1,0),(0,1)$, so $m=3$ and the bound is nine. The four-point set is a cap: in each coordinate a zero sum among binary entries in $\mathbb F_3$ forces all three entries equal, hence the three vectors coincide. A loose small-dimensional bound can still imply a strong asymptotic theorem.

43.10 Polynomial-method applications to incidence geometry

Optional extension; not required to complete the chapter foundation.

Let $P\subset F^2$ be a finite point set, $\mathcal L$ a finite set of distinct affine lines, and $I(P,\mathcal L)$ the number of incident point-line pairs. Suppose a nonzero polynomial $f$ of degree $D$ vanishes on $P$. A line not contained in $Z(f)$ contains at most $D$ points of $P$, because its restriction is a nonzero univariate polynomial. Over a finite field this is informative only if $D$ is smaller than the number of available points on the line.

Over an infinite field, a line on which the restriction vanishes identically has its defining linear equation as a factor of $f$. To prove this, make an invertible affine coordinate change taking the line to $Y=0$; a polynomial vanishing identically there has zero constant coefficient as a polynomial in $Y$, so $Y$ divides it. Distinct contained lines give distinct linear factors, and therefore at most $D$ such lines occur.

If $\mathcal L_0$ denotes those contained lines, the resulting elementary bound is

$$I(P,\mathcal L)\le D\lvert\mathcal L\setminus\mathcal L_0\rvert+\sum_{\ell\in\mathcal L_0}\lvert P\cap\ell\rvert.$$

The exceptional term is essential. The complete elementary argument above illustrates the vanishing-polynomial part of incidence methods. Stronger real-plane incidence results combine this with partitioning and boundary analysis; a primary polynomial treatment is Kaplan, Matoušek, and Sharir. No sharp general incidence theorem is asserted or proved by this elementary inequality alone.

Solved example. Return to the six-point rational set $S$ and $f=Y(Y-1)$. Take four lines $Y=0$, $Y=1$, $X=0$, and $X=2$. The two contained horizontal lines contribute three incidences each; the two other lines contribute two each. Thus $I=10$, and the displayed bound is exactly $2\cdot2+3+3=10$. Omitting the exceptional lines would have incorrectly suggested a uniform two-point bound.

Partitioning gives a different certificate: a degree-$D$ real polynomial organizes points into cells, and a noncontained line crosses at most $D+1$ of them. The point occupancy, crossing budget, and zero-set contribution have to be analyzed together. These ideas also underlie geometric range-searching decompositions; Matoušek and Patáková's primary paper treats the boundary issue with multilevel partitions. This is a cross-disciplinary algorithmic application, not an efficiency guarantee for every polynomial construction.

Exercise. If $P$ lies on an irreducible real conic and $\mathcal L$ contains $m$ distinct lines, prove $I\le2m$. Hint: a conic with a line factor would be reducible. Solution: no line is contained, so every restriction is a nonzero polynomial of degree at most two. Each line contributes at most two points, and summing yields the bound.

Construct a vanishing polynomial and justify a rank or incidence bound

This investigation turns interpolation into two certificates: an exact evaluation rank and an incidence bound with exceptional lines. The core work requires only the foundation. The optional extension explores a tensor indicator over a finite field, showing how a related coefficient budget governs a different extremal problem.