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?

  • $\begingroup$ 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. $\endgroup$ – Jeremy Dover Nov 29 '17 at 18:27
  • $\begingroup$ @JeanMarie positive integer $\endgroup$ – xixumei Nov 30 '17 at 1:03
  • $\begingroup$ @JeremyDover Get it. Thanks! $\endgroup$ – xixumei Nov 30 '17 at 1:06
  • $\begingroup$ For readers that are not aware of this rich field : take a look at (arxiv.org/pdf/1603.05333.pdf) $\endgroup$ – Jean Marie Nov 30 '17 at 6:50
  • $\begingroup$ @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. $\endgroup$ – MvG Nov 30 '17 at 23:32

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.