Incidences on a projective plane

To give an idea of some bounds, let's quickly sketch some simple ones:

• A lower bound is clearly $c = 1$ , since we can have each point incident to its own line for $n$ incidences, so $I(n) \ge n$ .
• An upper bound is clearly $c = 2$ , since there are only $n^2$ possible incidence pairs, so $I(n) \le n^2$ .

As it turns out, the answer is $c = \boxed{\frac{3}{2}}$ , precisely in the middle. We will give a proof.

---

First, we show $c \le \frac{3}{2}$ . Surprisingly, this is not very difficult, although the ideas might not come easily. The idea is to double-count the number of pairs of points incident to the same line, putting an upper bound on it and converting it to an upper bound on the number of incidences.

Let $d_i$ be the number of points of $P$ incident to the $i$ -th line. Note that the total number of incidences $S$ is then $\sum d_i$ . Thus if we can bound $\sum d_i$ from above, we also obtain the same bound for $I(n)$ .

Let's consider triples $\{p_1, p_2, l\}$ where $p_1, p_2 \in P$ and $l \in L$ , such that $p_1, p_2$ lie on $l$ (that is, they are incident to $l$ ). We will count the number of such triples, call it $N$ .

On one hand, it's easy to do this: for each line $l_i$ , it has $d_i$ points lying on it. We can pick any two points to obtain a triple, so line $l_i$ contributes $\binom{d_i}{2}$ triples. In total, $N = \sum \binom{d_i}{2}$ .

On the other hand, we can put an upper bound on this number of triples. We claim that for any two points $p_1, p_2$ , they may only appear together in one triple. Indeed, suppose there are two triples $\{p_1, p_2, l_1\}, \{p_1, p_2, l_2\}$ containing them. Then line $l_1$ passes $p_1, p_2$ , and line $l_2$ also passes the same points, contradicting that through any two points there exists a unique line (or otherwise any two lines can only intersect at one point). Thus the claim is proven, which means $N \le \binom{n}{2}$ .

Together, this means $\sum \binom{d_i}{2} \le \binom{n}{2}$ . Multiplying both sides by 2 and collecting terms, we obtain $\sum d_i^2 - \sum d_i \le n(n-1)$ . Using QM-AM inequality (note that $d_i \ge 0$ for all $i$ ), we know $\sum d_i^2 \ge \frac{1}{n} (\sum d_i)^2$ , thus we have

$\begin{aligned} \sum d_i^2 - \sum d_i &\le n(n-1) \\ \frac{1}{n} (\sum d_i)^2 - \sum d_i &\le n(n-1) \\ \frac{1}{n} S^2 - S &\le n(n-1) \\ S^2 - nS &\le n^3 - n^2 \end{aligned}$

If you're familiar with Big O notation, you can immediately tell that $S^2 = O(n^3)$ and so $S = O(n^{3/2})$ , giving $c \le \frac{3}{2}$ . If not, we can also spell it out. Suppose $S \le C_2 \cdot n^c$ , as in the statement. Then $S^2 - nS \le n^3 - n^2$ , or $S^2 - nS - (n^3 - n^2) \le 0$ . We can solve the quadratic inequality to obtain that

$\begin{aligned} S &\le \frac{n + \sqrt{n^2 + 4(n^3 - n^2)}}{2} \\ &= \frac{n}{2} \cdot (1 + \sqrt{4n-3}) \end{aligned}$

Now, to obtain a concrete (if weak) $C_2$ , we can weaken the inequality:

$\begin{aligned} S &\le \frac{n}{2} \cdot (1 + \sqrt{4n-3}) \\ &\le \frac{n}{2} \cdot 2 \sqrt{4n-3} \\ &\le \frac{n}{2} \cdot 2 \sqrt{4n} \\ &= 2n^{3/2} \end{aligned}$

The second line is because $\sqrt{4n-3} \ge 1$ for $n \ge 1$ . The third line is because $\sqrt{4n} \ge \sqrt{4n-3}$ for all $n$ . So we can take $N \ge 1, C_2 = 2$ .

---

It remains to prove the lower bound. To do this, we need to exhibit an example.

There are objects called finite projective planes , in which the numbers of points and lines are finite. These are almost like our $P, L$ , except that it's required that every pair of points do actually have a line passing through it, and every pair of lines do actually have a point in common. There is a construction that, given prime $p$ , can produce a finite projective plane with $p^2 + p + 1$ points and $p^2 + p + 1$ lines, with each point lying on $p+1$ lines (and each line passing through $p+1$ points); such plane is called a finite projective plane of order $p$ .

We will first outline the construction, then we will prove that this gives a lower bound. The construction needs some knowledge in linear algebra; if you want to accept the existence of this finite projective plane without needing any proof, you can skip down to the proof of this being a lower bound for $I(n)$ .

The construction can be obtained from linear algebra. Let $\mathbb{F}_p$ be the field of $p$ elements (we can take this as the integers modulo $p$ , with the usual addition and multiplication). We consider $\mathbb{F}_p^3$ , formed by triples of elements in $\mathbb{F}_p$ . Let $P$ be the set of 1-dimensional subspaces and $L$ be the set of 2-dimensional subspaces of $\mathbb{F}_p^3$ , and $p \in P$ and $l \in L$ are incident exactly when $p \subset l$ . We claim that:

• $|P| = |L| = p^2 + p + 1$
• Each point is incident to exactly $p+1$ lines, and each line is incident to exactly $p+1$ points
• Through two distinct points there exists exactly one line incident to both, and among two distinct lines there exists exactly one point incident to both

The first point is relatively easy. There are $p^3 - 1$ elements of $\mathbb{F}_p^3$ other than $(0,0,0)$ . Each 1-dimensional subspace contains $(0,0,0)$ and $p-1$ other elements. Each element is contained in exactly one 1-dimensional subspace. Thus there are $\frac{p^3-1}{p-1} = p^2+p+1$ 1-dimensional subspaces, so $|P| = p^2+p+1$ . To prove $|L| = |P|$ , just note that each 2-dimensional subspace is normal to exactly one 1-dimensional subspace, so we can make a bijection between 1-dimensional subspaces and 2-dimensional subspaces.

The second point is also pretty simple. To prove each line is incident to exactly $p+1$ points, simply note that a 2-dimensional subspace has $p^2-1$ nonzero elements, so it contains $\frac{p^2-1}{p-1} = p+1$ 1-dimensional subspaces, so a line contains $p+1$ points. Proving the other part uses the normality as well: each 1-dimensional subspace $x$ is normal to a 2-dimensional subspace $x^T$ , which contains $p+1$ 1-dimensional subspaces $y^T$ , each of which is normal to a 2-dimensional subspace $y$ . Because $y^T \subset x^T$ , we have $x \subset y$ , so each point $x$ is incident to $p+1$ lines $y$ .

The third point can be shown using linear algebra again. If we have two different 1-dimensional subspaces, they together span a 2-dimensional subspace. So any two distinct points span a single line, and so there exists exactly one line that contains two points. Again, the other part uses normality; this is left as an exercise to the reader.

Thus we have shown that for any prime $p$ , there exists a finite projective plane of order $p$ . We will now show that this will give a lower bound for $I(n)$ .

Since there are $p^2+p+1$ points and each point is incident to $p+1$ lines, there are $(p^2+p+1)(p+1)$ incidences in total. Since $p+1 \ge \sqrt{p^2+p+1}$ , there are at least $(p^2+p+1)^{3/2}$ incidences. So if there are $n$ points where $n = p^2+p+1$ , we have at least $n^{3/2}$ incidences: take $P, L$ as given by the finite projective plane.

Unfortunately we need that $n$ is indeed in the form $p^2+p+1$ . However, we can take the largest prime $p$ so that $p^2+p+1 \le n$ ; now, for $p^2+p+1$ points of them, we put them as in the finite projective plane, while we just throw away the remaining points and lines (put them arbitrarily, no need to make any incidences).

We will now make a formal proof that this is in fact good enough. Assume that $n \ge 64 = 4^3$ . Let $k$ be an integer such that $4^k \le n < 4^{k+1}$ ; by the above, we have $k \ge 3$ . By Bertrand's postulate , there exists a prime $p$ such that $2^{k-1} < p < 2^k - 1$ (because $2^{k-1} \ge 4$ ). Since $p^2 < p^2+p+1 < (p+1)^2$ , we have $4^{k-1} < p^2+p+1 < 4^k$ . Since $4^k \le n$ and $4^{k-1} = \frac{1}{16} 4^{k+1} > \frac{1}{16} n$ , we have $\frac{1}{16} n < p^2+p+1 < n$ .

Let $s = p^2+p+1$ and $S$ be the number of incidences. Since $s < n$ , we can indeed construct a finite projective plane of order $p$ from our $n$ points, so we obtain at least $s^{3/2}$ incidences; that is, $S \ge s^{3/2}$ . Since $s > \frac{1}{16} n$ , we have $S \ge s^{3/2} > \frac{1}{64} n^{3/2}$ . Thus $S \ge \frac{1}{64} n^{3/2}$ . And by definition, $I(n) \ge S$ , so we can take $N \ge 64, C_1 \ge \frac{1}{64}$ in our claim above.

---

The two results above are summarized here:

• $I(n) \le 2 n^{3/2}$ for all $n > 1$
• $I(n) \ge \frac{1}{64} n^{3/2}$ for all $n > 64$

Thus, we can take $c = \frac{3}{2}, N = 64, C_1 = \frac{1}{64}, C_2 = 2$ into the problem. This proves that $c = \frac{3}{2} = 1.5000$ or $I(n) = \Theta(n^{3/2})$ .

---

Note that we have been working on projective planes. Can our construction actually be exhibited on the standard Euclidean plane? The answer turns out to be no. And in fact, on the Euclidean plane we have an even lower exponent: there are at most $\Theta(n^{4/3})$ incidences (and this can be achieved in some configurations). This is Szemerédi–Trotter theorem ; the proof is not very difficult, but it needs some bright ideas. Note that this problem proves that finite projective planes of large order (order greater than 1, in fact) cannot be realized on the Euclidean plane, since we get $\Theta(n^{3/2})$ incidences in that plane but we know that on the Euclidean plane we cannot have more than $O(n^{4/3})$ incidences.