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:
- every line has $q+1$ points
- every point lies on $q+1$ lines
- every 2 points lie on a unique line
- 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?
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.