Joints

This chapter uses the counting lemma (2.2(a)), the univariate zeros bound (Lemma 2.5(v)), and, in place of the Schwartz–Zippel lemma, a minimality argument on the degree of the vanishing polynomial. The bridge is the gradient of the polynomial at a joint.

5.1 The problem

Definition 5.1. Let $\mathcal L$ be a finite set of lines in $\mathbb F^n$. A point $\mathbf x\in\mathbb F^n$ is a joint of $\mathcal L$ if it lies on $n$ lines of $\mathcal L$ whose direction vectors are linearly independent.

In $\mathbb R^3$ a joint is a point where three non-coplanar lines meet. The problem of bounding the number of joints of $L$ lines was raised by Chazelle and others (1992) in computational geometry. A grid of $k^3$ points with the $3k^2$ axis-parallel lines through them has $L=3k^2$ lines and $k^3=(L/3)^{3/2}$ joints, and it was conjectured that $O(L^{3/2})$ is the truth. Sharir (1994) proved $O(L^{7/4})$ and Feldman and Sharir (2005) improved the exponent slightly, by methods of combinatorial geometry. Guth and Katz (2010) proved $O(L^{3/2})$ with the polynomial method, and Kaplan, Sharir, and Shustin (2010) and Quilodrán (2010) independently simplified the argument and extended it to $\mathbb R^n$. Carbery and Iliopoulou (2014) extended it to arbitrary fields. The proof below follows the simplified argument.

5.2 Three lemmas

Lemma 5.2 (Pruning). Let $\mathcal L$ be a set of $L$ lines in $\mathbb F^n$ with a set $J$ of joints, $|J|=m\ge1$. Then there are $\mathcal L'\subseteq\mathcal L$ and $J'\subseteq J$ with $|J'|\ge m/2$ such that every point of $J'$ is a joint of $\mathcal L'$ and every line of $\mathcal L'$ contains at least $\dfrac{m}{2L}$ points of $J'$.

Proof. Start with $\mathcal L'=\mathcal L$, $J'=J$. While some line $\ell\in\mathcal L'$ contains fewer than $m/(2L)$ points of $J'$, remove $\ell$ from $\mathcal L'$ and remove the points of $J'$ on $\ell$ from $J'$. Each step removes fewer than $m/(2L)$ points and there are at most $L$ steps, so fewer than $m/2$ points are removed in all and $|J'|>m/2$ at the end. A point that survives was never on a removed line, so all $n$ independent lines through it survive, and it is a joint of $\mathcal L'$. When the process stops, every line of $\mathcal L'$ contains at least $m/(2L)$ points of $J'$. ∎

Lemma 5.3 (Gradient at a joint). Let $P\in\mathbb F[\mathbf x]$ vanish identically on $n$ lines through $\mathbf x_0$ with linearly independent directions $\mathbf v_1,\dots,\mathbf v_n$. Then every partial derivative $\partial_iP$ vanishes at $\mathbf x_0$.

Proof. For each $j$, the polynomial $P(\mathbf x_0+t\mathbf v_j)\in\mathbb F[t]$ is identically zero, hence so is its coefficient of $t$. By Definition 2.3 with $\mathbf y=t\mathbf v_j$, that coefficient is $\sum_{i}P^{(\mathbf e_i)}(\mathbf x_0)\,v_{j,i}=\nabla P(\mathbf x_0)\cdot\mathbf v_j$, where $\nabla P=(\partial_1P,\dots,\partial_nP)$ and $P^{(\mathbf e_i)}=\partial_iP$. So $\nabla P(\mathbf x_0)$ is orthogonal to $n$ linearly independent vectors, hence is zero. ∎

Lemma 5.4 (Vanishing gradient). Let $0\ne P\in\mathbb F[\mathbf x]$ with $\partial_iP=0$ for all $i$. (a) If $\operatorname{char}\mathbb F=0$, then $P$ is a nonzero constant. (b) If $\operatorname{char}\mathbb F=p>0$ and $\mathbb F$ is perfect (for instance finite or algebraically closed), then $P=Q^p$ for some $Q\in\mathbb F[\mathbf x]$ with $\deg Q=\deg P/p$.

Proof. Since $\partial_i\mathbf x^{\boldsymbol\alpha}=\alpha_i\mathbf x^{\boldsymbol\alpha-\mathbf e_i}$ and distinct monomials remain distinct under $\partial_i$, the condition $\partial_iP=0$ says that $\alpha_i=0$ in $\mathbb F$ for every monomial $\mathbf x^{\boldsymbol\alpha}$ of $P$. In characteristic $0$ this means every $\alpha_i=0$, so $P$ is constant. In characteristic $p$ it means $p\mid\alpha_i$ for all $i$ and all monomials, so $P=\sum_{\boldsymbol\beta}c_{\boldsymbol\beta}\mathbf x^{p\boldsymbol\beta}$. Since $\mathbb F$ is perfect, each $c_{\boldsymbol\beta}=b_{\boldsymbol\beta}^p$ for some $b_{\boldsymbol\beta}\in\mathbb F$, and because the Frobenius map $z\mapsto z^p$ is a ring homomorphism of $\mathbb F[\mathbf x]$ in characteristic $p$,

$$P=\sum_{\boldsymbol\beta}b_{\boldsymbol\beta}^p\,\mathbf x^{p\boldsymbol\beta}=\Big(\sum_{\boldsymbol\beta}b_{\boldsymbol\beta}\mathbf x^{\boldsymbol\beta}\Big)^p=Q^p.\qquad\blacksquare$$

5.3 The theorem

Theorem 5.5 (Guth and Katz 2010; Kaplan, Sharir, and Shustin 2010; Quilodrán 2010; Carbery and Iliopoulou 2014). Let $\mathbb F$ be any field and $n\ge2$. A set of $L$ lines in $\mathbb F^n$ has at most

$$C_n\,L^{\frac{n}{n-1}},\qquad C_n=\big(2\,(n!)^{1/n}\big)^{\frac{n}{n-1}},$$

joints. In particular $L$ lines in $3$-space have at most $\sqrt{48}\,L^{3/2}<6.93\,L^{3/2}$ joints.

Proof. Replacing $\mathbb F$ by its algebraic closure changes neither the lines, nor which points are joints (linear independence over a field is preserved by extension), nor $L$; so we may assume $\mathbb F$ is algebraically closed, hence perfect. Let $J$ be the set of joints, $|J|=m$; if $m=0$ there is nothing to prove. Apply Lemma 5.2 to get $\mathcal L'$ and $J'$ with $|J'|\ge m/2$, every point of $J'$ a joint of $\mathcal L'$, and every line of $\mathcal L'$ containing at least $m/(2L)$ points of $J'$.

Let $d_0$ be the least integer with $\binom{d_0+n}{n}>|J'|$; since $|J'|\ge1$, $d_0\ge1$. By Lemma 2.2(a) some nonzero polynomial of degree at most $d_0$ vanishes on $J'$. Among all nonzero polynomials vanishing on $J'$ choose $P$ of least degree $d^*$; then $1\le d^*\le d_0$ ($d^*\ge1$ because a nonzero constant does not vanish on the nonempty set $J'$).

Claim: $d^*\ge m/(2L)$. Suppose $d^*<m/(2L)$. Every line $\ell\in\mathcal L'$ contains at least $m/(2L)>d^*$ points of $J'$, at which $P$ vanishes; the restriction of $P$ to $\ell$ is a univariate polynomial of degree at most $d^*$ with more than $d^*$ roots, hence identically zero (Lemma 2.5(v)). So $P$ vanishes identically on every line of $\mathcal L'$. At each $\mathbf x_0\in J'$ there are $n$ lines of $\mathcal L'$ through $\mathbf x_0$ with independent directions, so by Lemma 5.3 every $\partial_iP$ vanishes at $\mathbf x_0$. Thus each $\partial_iP$ vanishes on $J'$ and has degree at most $d^*-1$; by the minimality of $d^*$, each $\partial_iP=0$. By Lemma 5.4, either $P$ is a nonzero constant, which is impossible, or $\operatorname{char}\mathbb F=p>0$ and $P=Q^p$ with $\deg Q=d^*/p<d^*$; but then $Q$ vanishes on $J'$ (as $Q(\mathbf x)^p=P(\mathbf x)=0$ implies $Q(\mathbf x)=0$), again contradicting minimality. This proves the claim.

Bounding $d_0$. By minimality of $d_0$, $\binom{d_0-1+n}{n}\le|J'|\le m$, and

$$\binom{d_0-1+n}{n}=\frac{(d_0+n-1)(d_0+n-2)\cdots d_0}{n!}\ge\frac{d_0^{\,n}}{n!},$$

so $d_0\le(n!\,m)^{1/n}$.

Combining, $\dfrac{m}{2L}\le d^*\le d_0\le(n!\,m)^{1/n}$, i.e. $m^{1-1/n}\le2(n!)^{1/n}L$, i.e. $m\le\big(2(n!)^{1/n}\big)^{n/(n-1)}L^{n/(n-1)}$. For $n=3$, $C_3=(2\cdot6^{1/3})^{3/2}=2^{3/2}\cdot6^{1/2}=\sqrt{48}$. ∎

Remark 5.6. The argument differs from the Kakeya argument of Chapter 4 in one structural respect. There, the contradiction came from the Schwartz–Zippel lemma: the top homogeneous part was shown to vanish on all of $\mathbb F_q^n$. Here there is no grid to vanish on, since the field may be infinite, and the contradiction comes instead from minimality of degree: the derivatives of the vanishing polynomial vanish on the same set with lower degree. The minimality trick is available whenever the set of vanishing polynomials is closed under an operation that lowers degree, and it is the second of the two ways in which the zeros principle enters the method (the Schwartz–Zippel bound being the first).

Remark 5.7. The pruning step is essential: without it, a line containing only one joint would not force $P$ to vanish on the line. The factor $2$ in $C_n$ comes from the pruning, and the factor $(n!)^{1/n}$ from the dimension count. Guth and Katz's original constant and those in the literature since are of the same order; the best constants have been the subject of subsequent work (see Tidor, Yu, and Zhao 2022 for the generalisation from lines to varieties), which I do not pursue.

5.4 Sharpness

The exponent $n/(n-1)$ is sharp. Take the grid $[k]^n\subseteq\mathbb F^n$ (any field with at least $k$ elements) and the $nk^{n-1}$ axis-parallel lines through its points. Every grid point is a joint, so $L=nk^{n-1}$ lines have $k^n=(L/n)^{n/(n-1)}$ joints, and the ratio of upper to lower bound is

$$C_n\,n^{n/(n-1)}=\big(2\,n\,(n!)^{1/n}\big)^{n/(n-1)},$$

which for $n=3$ is $\sqrt{48}\cdot3^{3/2}\approx36$. The exponent is right; the constant obtained from this argument is not.

Over a finite field the same example with $k=q$ gives $L=nq^{n-1}$ lines and $q^n$ joints, and the theorem is not vacuous there: it bounds the number of joints of any $L$ lines in $\mathbb F_q^n$ by $C_nL^{n/(n-1)}$ regardless of $q$. This is a genuinely different situation from the Kakeya problem, where the field size $q$ is the parameter and the polynomial's degree is compared with $q$. In the joints problem the degree is compared with the number of joints per line, and the field plays no role beyond supplying Lemma 5.4.