# Bound of the size of point set in projective plane.

For those familiar with combinatorial design, a projective plane is a $(q^2+q+1, q+1, 1)$ design. Geometrically, a projective plane of order $q$ is a set of points and lines through these points. There are $q^2+q+1$ points and $q^2+q+1$ lines in total. They satisfy the following condition:

1. every line has $q+1$ points
2. every point lies on $q+1$ lines
3. every 2 points lie on a unique line
4. every 2 lines meet at a unique point

Let $S$ be a set of points in a projective plane of order $q$. Suppose that no three points of $S$ lie on a line. Prove that $|S|\le q+1$ if $q$ is odd and $|S| \le q+2$ if $q$ is even.

Fix a point $x$ in $S$. For $y\in S$ and $y\ne x$, x and y lie on one of $q+1$ lines through $x$ and these lines must be different for different $y$. Thus we have $|S|\le q+2, \forall q \in \mathbb{N}$.

I'm having trouble showing that $|S| = q+2$ is impossible for odd number $q$. Any ideas?

• From what you have, it is easy to show that if $|S| = q+2$, then every line meets $|S|$ in 0 or 2 points. Now, pick a point $P$ not in $S$, and count the points of $S$ in terms of how the $q+1$ lines through $P$ meet $S$. Think in terms of parity. – Jeremy Dover Nov 29 '17 at 18:27
• @JeanMarie positive integer – xixumei Nov 30 '17 at 1:03
• @JeremyDover Get it. Thanks! – xixumei Nov 30 '17 at 1:06
• For readers that are not aware of this rich field : take a look at (arxiv.org/pdf/1603.05333.pdf) – Jean Marie Nov 30 '17 at 6:50
• @JeremyDover: I think you should expand this comment to an answer, since you did answer the question quite nicely. A quick argument as to why all the lines through a point in $S$ would need to pass through a second point in $S$ might be appreciated; it took me a minute to work this out. – MvG Nov 30 '17 at 23:32

## 1 Answer

A set of points in a projective plane such that no three points are collinear is called an arc. Suppose $S$ is an arc of size $q+2$ in a projective plane of order $q$, with $q \ge 2$. We claim $q$ must be even.

First note that every line $\ell$ of the plane meets $S$ in either 0 or 2 points. Letting $P$ be a point of $S$, count the set of flags (incident point-line pairs) $${\cal Z} = \{(Q,\ell):Q \in S \setminus \{P\} \; {\rm and} \; P,Q \in \ell\}$$ Picking $Q$ first, there are $q+1$ options, and then a single choice for $\ell$, so we have $|{\cal Z}| = q+1$. On the other hand, any line $\ell$ in a flag $(Q,\ell)$ contained in ${\cal Z}$ must meet $S$ in exactly two points, namely $P$ and $Q$, since $\ell$ cannot meet $S$ in more than two points. Once $\ell$ is selected, there is a unique point $Q$ such that $(Q,\ell) \in {\cal Z}$. Thus $|{\cal Z}|$ is exactly the number of 2-secants to $S$ through $P$, namely $q+1$. Since $P$ lies on $q+1$ lines, this shows that every line containing a point of $S$ meets $S$ in exactly two points, showing that every line of the plane meets $S$ in 0 or 2 points.

With that proven, let $R$ be a point off $S$, which exists since $q^2+q+1 \gt q+2$ for all $q \ge 2$. Let $x$ be the number of 2-secants to $S$ through $R$. Every point of $S$ lies on exactly one line through $R$, so we find that $|S| = 2x$. But $|S| = q+2$, which forces $q$ to be even.