1
$\begingroup$

Let $F$ be a finite field of order $n$, and let $d$ be an integer. A line in $F^d$ is a function $\ell: F \to F^d$ given by $\ell(t) = x + t*h$, where $x,h \in F^d$, $h \neq 0$, and $t*h = (tx_1, \ldots, tx_d)$.

For $3 \le k \le n$, how many uniformly chosen points in $F^d$ are needed to be drawn such that with high probability (say $2/3$), the set of drawn points contains $k$ different points from (any) line?

Clarification: the last line refers to a set that contain at least one line (not all lines).

Edit: a rough estimation regarding the number of draws needed (e.g., $O(n^d)$, $O(n^{d/2})$, $poly(d \log n)$, $O(d \log n)$, etc.) would also be very helpful.

$\endgroup$
6
  • $\begingroup$ I think you want $h\ne0$. $\endgroup$
    – joriki
    Commented Aug 24, 2015 at 16:22
  • $\begingroup$ @joriki right, thanks. $\endgroup$
    – Anonymous
    Commented Aug 24, 2015 at 17:46
  • $\begingroup$ The geometry you are referring to is often called the affine space $\mathrm{AG}(d,q)$. You would usually associate a line with a pointset $\ell = \{\vec{x} + t\cdot\vec{h}\ : \ t \in F\}$, where $\vec{t}, \vec{h} \in F^{d}$ (with $\vec{h} \neq \vec{0}$). And you would almost always say your finite field has order $q$ (this is just a notational thing, where $p$ is always assumed to be a prime and $q$ to be a prime power). $\endgroup$
    – xxxxxxxxx
    Commented Aug 24, 2015 at 21:29
  • $\begingroup$ Just clarifying -- you want to draw enough points so that, with high probability, there exists a line containing at least $k$ of the points you drew. Is that right? $\endgroup$
    – Tad
    Commented Aug 25, 2015 at 1:40
  • $\begingroup$ The special case $n=81$ (i.e. a $4$-dimensional field over $\mathbb{F}_3$) with $k=3$ corresponds to the game of Set. There's a card for each element of the field; each line (called a Set) contains $3$ points, and the question is: what's the probability that a given collection of $r$ cards contains at least one Set. See math.stackexchange.com/questions/202862/… for a detailed discussion. (If you're sampling points with replacement, the question is slightly different, but I don't think it's easier.) $\endgroup$
    – Tad
    Commented Aug 25, 2015 at 3:36

1 Answer 1

Reset to default
2
$\begingroup$

I think you need to consider arcs (when $d=2$) or caps (when $d>3$). The normal definition of an cap is a collection of points, no three on a common line (an arc actually only coincides with this definition in a plane). What you are interested in are the number of $(s,k-1)$-caps (common literature will refer to $(k,d)$-arcs in planes, this is a generalization); this will be a set of $s$ points such that no more than $k-1$ are on a common line. Any set of size $s$ will either be a $(s,k-1)$-cap, or else have the property you are interested in.

Unfortunately the best reference I can find is mangled in the postscript conversion (weak).

[Old answer refers to the problem of ensuring every line contains at least $k$ points]

This is not an easy problem at all. The first question would be, how many points do you need in a set $\mathcal{S}$ for it to even be possible that every line contains at least $k$ points of $\mathcal{S}$? Such a set is called a $k$-fold blocking set (with respect to lines). You can see some details here. I think this type of problem is more difficult in affine spaces than in projective spaces. To do an analysis of the probability, you would need to know how many $k$-fold blocking sets of size $s$ there were, and you could compare that to ${q^d \choose s}$.

Unfortunately I can't give you an answer, just point out that these are well-studied objects (with lots of related open problems). Probably the most interesting (and well studied) area of research is on small blocking sets in projective planes (a search on google scholar for the term "blocking sets" will turn up lots of results).

$\endgroup$
4
  • $\begingroup$ I'm afraid my question was ambiguous. I meant how many points are needed such that w.h.p. they will contain at least one line. I'll edit it accordingly (sorry for the confusion). $\endgroup$
    – Anonymous
    Commented Aug 24, 2015 at 22:21
  • $\begingroup$ Thanks Morgan, I'll try to see whether I can find something helpful in the literature. Do you perhaps have a rough estimation regarding the number of draws needed? $O(n^d)$? $O(n^{d/2})$? $poly(d \log n)$? $O(d \log n)$? $\endgroup$
    – Anonymous
    Commented Aug 25, 2015 at 13:39
  • $\begingroup$ Thanks Morgan! It seemed to me like the type of problems for which one can get an asymptotic bound via elementary combinatorics/probability tools (e.g., compute the expected number of draws to hit a line and then use tail bounds -- a bit like the coupon collector problem) -- but all my attempts thus far failed. $\endgroup$
    – Anonymous
    Commented Aug 25, 2015 at 17:52
  • $\begingroup$ By the way, regarding the every line contains at least $k$ points variant -- it seems closely related to Kakeya sets: cs.princeton.edu/~zdvir/papers/Dvir09.pdf $\endgroup$
    – Anonymous
    Commented Aug 25, 2015 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .