The Counting Bound

Throughout this chapter $\mathcal L$ is an $r$-fold configuration in $AG(2,q)$ with union $U$ and multiplicities $m_P$, $1\le r\le q$.

3.1 Incidence identities

Lemma 3.1. (a) $\displaystyle\sum_{P\in U}m_P=rq(q+1)$. (b) $\displaystyle\sum_{P\in U}\binom{m_P}2=r^2\binom{q+1}2$. (c) For every line $\ell\in\mathcal L$, $\displaystyle\sum_{P\in\ell}(m_P-1)=rq$.

Proof. (a) counts incidences: $r(q+1)$ lines with $q$ points each. (b) counts pairs of lines meeting in a point: two lines of $\mathcal L$ meet iff they are not parallel, and there are $\binom{r(q+1)}2-(q+1)\binom r2=\frac{q+1}2\big(r^2(q+1)-r-r(r-1)\big)=r^2\frac{q(q+1)}2$ such pairs, each contributing $1$ to exactly one $\binom{m_P}2$. (c) The lines of $\mathcal L$ other than $\ell$ that meet $\ell$ are those not parallel to it, $r(q+1)-r=rq$ in number, and each meets $\ell$ in one point. ∎

3.2 The variance identity

Theorem 3.2 (Theorem A). For every $r$-fold configuration,

$$|U|=\frac{r}{r+1}\,q(q+1)+\frac{1}{(r+1)^2}\sum_{P\in U}\big(m_P-(r+1)\big)^2.\tag{3.1}$$

In particular $|U|\ge\frac r{r+1}q(q+1)$, with equality if and only if $m_P=r+1$ for every $P\in U$.

Proof. From Lemma 3.1, $\sum m_P=rq(q+1)$ and $\sum m_P^2=\sum m_P+2\sum\binom{m_P}2=rq(q+1)+r^2q(q+1)=r(r+1)q(q+1)$. Hence

$$\sum_{P\in U}(m_P-r-1)^2=\sum m_P^2-2(r+1)\sum m_P+(r+1)^2|U|=r(r+1)q(q+1)-2r(r+1)q(q+1)+(r+1)^2|U|,$$

i.e. $\sum(m_P-r-1)^2=(r+1)^2|U|-r(r+1)q(q+1)$, which rearranges to (3.1). The sum of squares is nonnegative and vanishes iff every $m_P$ equals $r+1$. ∎

The identity says that the "excess" of a configuration over the bound is a variance: the multiplicities have mean $\bar m=\sum m_P/|U|$ and, since $\sum m_P^2/\sum m_P=r+1$ exactly, the value $r+1$ is the mean of $m_P$ weighted by $m_P$; the configuration is extremal iff the multiplicities are constant. For $r=1$ the identity reads $|U|=\binom{q+1}2+\frac14\sum(m_P-2)^2$, which is the Bonferroni inequality $|U|\ge\sum|\ell|-\sum|\ell\cap\ell'|$ with an exact error term; the companion dissertation writes the same quantity as $\binom{q+1}2+\sum_P\binom{m_P-1}2$, and the two forms agree because of Lemma 3.1.

Write

$$\Delta(\mathcal L)=|U|-\frac r{r+1}q(q+1)=\frac1{(r+1)^2}\sum_{P\in U}d_P^2,\qquad d_P=m_P-(r+1),$$

for the deficiency of a configuration and $\Delta_r(q)=\kappa_r(q)-\frac r{r+1}q(q+1)$ for the deficiency of the extremal problem. Two constraints on the deviations $d_P$ will be useful.

Lemma 3.3. (a) $\sum_{P\in U}d_P=-\frac1{r+1}\sum_{P\in U}d_P^2$. (b) For every $\ell\in\mathcal L$, $\sum_{P\in\ell}d_P=0$.

Proof. (a) $\sum d_P=\sum m_P-(r+1)|U|=rq(q+1)-(r+1)|U|=-(r+1)\Delta(\mathcal L)$, and $\Delta=\sum d_P^2/(r+1)^2$. (b) By Lemma 3.1(c), $\sum_{P\in\ell}(d_P+r)=\sum_{P\in\ell}(m_P-1)=rq$ and $\ell$ has $q$ points. ∎

Part (b) says that on every line of the configuration the multiplicities are balanced around $r+1$: a point of multiplicity above $r+1$ on $\ell$ must be compensated by points of multiplicity below $r+1$ on the same line. Part (a) says that globally the deviations are negative on average, by an amount fixed by the deficiency.

3.3 Integrality

Since $|U|$ is an integer, $\kappa_r(q)\ge\lceil\frac r{r+1}q(q+1)\rceil$, and when $(r+1)\nmid q(q+1)$ the bound of Theorem A cannot be attained for arithmetic reasons alone. This is weaker than Theorem B, which excludes attainment for every odd $q$, but it explains some of the small values: for $q=4$, $r=2$ the bound is $13\frac13$ and $\kappa_2(4)=14$; for $q=5$, $r=3$ the bound is $22\frac12$ and $\kappa_3(5)=23$; for $q=7$, $r=4$ the bound is $44\frac45$ and $\kappa_4(7)=46$. In the first two cases the ceiling is attained; in the third it is not. A configuration with $|U|=\lceil\frac r{r+1}q(q+1)\rceil$ has $\sum d_P^2=(r+1)^2\big(\lceil\cdot\rceil-\frac r{r+1}q(q+1)\big)<(r+1)^2$, so its multiplicities are tightly concentrated about $r+1$: in the first two examples every $m_P$ lies in $\{r,r+1,r+2\}$, while in the third, where the ceiling is not attained, three points have multiplicity $r-1$ (§6.4). These near-extremal configurations are the objects one would like to understand in the odd case (Chapter 6).