Consider the projectivization $\mathbb P\mathbb F_p^n$ of $\mathbb F_p^n$. How large a set $B \subseteq \mathbb P \mathbb F_p^n$ can I pick so that no three points of $B$ lie on the same line?


The term for such sets is "caps". The problem you ask was posed by Bose ("Mathematical theory of the symmetrical factorial design", Sankhyā 8 (1947) 107–166), and is important in relation to coding theory: see Hill, A first course in coding theory (1986), around figure 14.9. At least at the time of Hill's book from which the following values are taken, the maximal size was known just for $p=2$ (it is $2^n$), for $n=2$ (it is $p+1$ for $p$ odd, $p+2$ for $p$ a power of $2$), for $n=3$ (it is $p^2+1$) and in the further cases $(n,p)=(4,3)$ and $(n,p)=(5,3)$ (where it is $20$ and $56$ respectively). (Some of these results are due to Bose himself.)

PS: It might also be worth while to point out that for $n=2$, caps are also known as "arcs", and a theorem of B. Segre states that (for $p$ odd), an arc of maximal size (also, "oval") is necessarily a conic.

  • $\begingroup$ Thank you! A great answer. Is anything non-trivial known about upper bounds? $\endgroup$ Aug 14 '17 at 23:01
  • $\begingroup$ @user193072 This paper (Storme, Thas & Vereecke, "New Upper bounds for the sizes of caps in finite projective spaces" J. Geometry 73 (2002) 176–193) seems to be about this, although I will admit that this is just what Google turned up and I looked no further than the abstract). $\endgroup$
    – Gro-Tsen
    Aug 14 '17 at 23:20
  • 1
    $\begingroup$ Yes that paper is about the same things. $PG(n,q)$ is what the OP calls "$\mathbb{PF}_q^n$". See also this very recent paper from JA Thas arxiv.org/abs/1702.01097 $\endgroup$ Aug 15 '17 at 6:31
  • 1
    $\begingroup$ Also worth noting if you want to search for papers, that often they are called k-arcs (for n=2) or k-caps (for n > 2). $\endgroup$ Aug 15 '17 at 10:16

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.