Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 10 (Algebraic Methods in Incidence Theory)

(A) For a finite point set $P$ and a family $\mathcal{C}$ of distinct unit circles in ${\mathbb{R}}^2$, the Szemerédi–Trotter theorem for unit circles stateswith an absolute constant $C$. Here $I$ counts point-circle incidences. Distinctness matters: repeated copies of the same circle are not separate members of this geometric family. A dilation gives the same bound for circles of any one fixed positive radius, with the same constant.

(B) Write $N=|P|$ and $D=|\Delta (P)\setminus \{0\}|$. The comparison is a bound on the cardinality of the distinct-distance set, rather than on the set itself. For each positive distance $\rho$, take the $N$ circles of radius $\rho$ centred at points of $P$. Their incidences between points and curves count exactly the ordered pairs $(p,q)$ at distance $\rho$. After dilation by $1/\rho$, part (A) bounds this number byEvery ordered pair of distinct points contributes to exactly one of these counts. Thus the unit-circle method for a distinct-distance lower bound givesFor $N\ge 2$, $N-1\ge N/2$, soFor $N=1$ the distance set is $\{0\}$ and the conclusion holds after adjusting the absolute constant; the empty set causes no difficulty.

(C) A direct incidence bound from two-point multiplicity suffices. Put $M=|\mathcal{L}|=N^2$ and $k_{\gamma }=|P\cap \gamma |$. Count unordered pairs of distinct points on each curve. By double counting,Writing $I={\sum }_{\gamma }{k}_{\gamma }$, this givesThe Cauchy-Schwarz inequality now yieldsIf $x^2\le ax+b$ with $x,a,b\ge 0$, then $x\le a+\sqrt{b}$. ConsequentlyIn fact the argument proves the stronger $O(N^{9/4})$ bound. The two-point multiplicity hypothesis alone controls these incidences between points and curves; the algebraic degree bound is not needed for the requested estimate.

(A) Use the dimension of a bounded-total-degree polynomial space. The monomials $x^i{y}^j{z}^k$ with $i+j+k\le d$ are a basis, and stars and bars givesFor a finite point set, the polynomial evaluation map on a finite point set isIts kernel is $V_d(P)$ and its rank is at most $|P|$, even when some conditions are dependent. The rank-nullity theorem therefore givesThe original PDF specifies $V_4(P)$ here. With twelve points,No general-position assumption is required.

(B) Let $L=|\mathcal{L}|\ge 1$. We seek a polynomial vanishing on a finite set of spatial lines. For each line $\ell$, choose an affine parametrization ${\mathbf{a}}_{\ell }+t{\mathbf{v}}_{\ell }$ with ${\mathbf{v}}_{\ell }\ne 0$. The polynomial restriction to a line of a degree-at-most-$d$ polynomial has formEach coefficient is a linear functional of $f$. Setting all $d+1$ coefficients to zero is precisely the condition that $f$ vanish identically on $\ell$.

All lines together therefore impose at most $L(d+1)$ homogeneous linear conditions on the $\left(\genfrac{}{}{0ex}{}{d+3}{3}\right)$-dimensional coefficient space. A nonzero solution exists wheneverTake $d=\lceil \sqrt{6L}\rceil$. Then $d^2\ge 6L$, so this strict inequality holds. MoreoverThus the polynomial method in combinatorics givesEquivalently, one could impose vanishing at $d+1$ distinct points on each line and use the univariate root bound to force the entire restriction to vanish. For an empty line family, the constant polynomial one supplies vacuous vanishing; the strict degree comparison is understood for nonempty families.

An ordinary line contains exactly two points of the configuration. We give a cubic covering from few ordinary lines by using point-line duality, a defect count and cubic interpolation. Cubics may be reducible: a line with equation $L=0$ is contained in the cubic $L^3=0$, and a conic can be multiplied by a linear factor.

Pass to the real projective plane, which preserves collinearities and ordinary-line counts. If all points are collinear, one cubic already suffices. Otherwise dualize each point $p=[a:b:c]$ to the line $p^{\ast }:aX+bY+cZ=0$. The dual lines form an embedded graph $\Gamma$: its vertices are their intersections and its edges are the consecutive segments on each projective line. A vertex where $k$ dual lines meet has graph degree $2k$ and corresponds to a primal line containing $k$ points.

Let $t_k$ count vertices incident to exactly $k$ dual lines, and let $f_j$ count faces with $j$ sides. In particular $t_2<5n$. If $v,e,f$ are the graph's numbers of vertices, edges and faces, thenThe Euler characteristic of the projective plane is one, so $v-e+f=1$. Substituting the counts gives the Euler defect identity for a projective line arrangementThus both sums measuring departure from a degree-six triangular grid are $O(n)$.

Call an edge a good dual-arrangement edge if both endpoints have degree six and both adjacent faces are triangles; call it bad otherwise. Count all edge incidences at the defective vertices and faces. Since $k\le 4(k-3)$ for $k\ge 4$ and $j\le 4(j-3)$ for $j\ge 4$,This controls actual bad edges, not merely the number of defective vertices.

Strengthen the local condition: an edge is a safe dual-arrangement edge if every edge on every path of length at most two from either endpoint is good. The bounded-radius propagation of edge defects says that only $O(n)$ edges fail this test. Indeed, trace from an unsafe edge to the first bad edge. Every intervening edge is good, so the intermediate vertices have degree six. Reversing such paths offers only a bounded number of choices, at most a fixed constant times the bad-edge count. Every edge belongs to exactly one dual line, so the pigeonhole principle gives a dual line $p^{\ast }$ containing only $O(1)$ unsafe edges.

The algebraic input is cubic propagation along a triangular strip: a consecutive strip of safe edges on $p^{\ast }$ has all of its crossing dual lines represented by primal points on a single cubic. Here is the mechanism, rather than an appeal to the desired covering theorem. The triangles on either side extend two cells outward into three indexed line families. After dualizing back, their points $a_i,b_j,c_k$ satisfy collinearities whenever $i+j+k=0$. Adjacent three-by-three blocks are the eight-point cubic completion for two triples of lines configuration. A nonzero homogeneous cubic can be fitted to nine starting points because its coefficient space has dimension ten; each successive block has eight points already on that cubic and forces its remaining point onto it. Continuing along the strip keeps every crossing point on the same cubic. One concrete seed is $a_{-1},a_0,a_1,a_2,b_{-3},b_{-2},b_{-1},c_1,c_2$. The first overlapping block forces $c_3$, the next forces $b_{-4}$, and the next forces $c_4$; another block then forces $a_{-2}$. Alternating these completion steps extends the $b$ and $c$ families for the full length of the strip.

For clarity, the completion fact has a short algebraic proof. Let $F=L_1{L}_2{L}_3$ and $G=M_1{M}_2{M}_3$, with the two line triples meeting in nine distinct points, and let a cubic $H$ vanish at all but $L_3\cap M_3$. On $L_1$, both $H$ and $G$ have the same three zeros, so $H-\lambda G$ is divisible by $L_1$ for a suitable scalar $\lambda$. Its quadratic quotient vanishes at the three intersections on $L_2$, hence is divisible by $L_2$. The remaining linear quotient vanishes at the two known intersections on $L_3$, hence is a multiple of $L_3$. Thuswhich also vanishes at the ninth point. This is the line-triple case of the Cayley-Bacharach theorem. In the strip construction, degree-six vertices and the two-cell neighbourhood ensure that the local nine points are distinct; the initial nine-point interpolation and repeated completion provide the required cubic.

It remains to account for every point, including defects and degeneracies. If some dual line has at most two distinct intersection vertices, all other dual lines pass through one of them. Dualizing back covers $P$ by at most two primal lines, hence by cubics, and we are done. Otherwise every dual line has at least three vertices, and the local strip construction applies.

On the chosen $p^{\ast }$, cut the cyclic edge sequence at its $b=O(1)$ unsafe edges, adding one arbitrary cut if necessary. There are at most $b+1$ safe runs, each covered by a cubic via the strip argument. Intersection vertices incident to cut or unsafe edges number at most $2b+2$. At each such exceptional vertex $w$, all crossing dual lines represent primal points on the single primal line $w^{\ast }$, which is itself contained in a cubic. Include one further cubic through $p$ if it has not already been covered. Every other primal point is accounted for by where its dual line intersects $p^{\ast }$. ThereforeThe absolute bound on $b$ comes from $t_2<5n$ and does not depend on the number of points. This completes the requested proof sketch.