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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$ Commented Aug 14, 2017 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-TsenCommented Aug 14, 2017 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$ Commented Aug 15, 2017 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$ Commented Aug 15, 2017 at 10:16