Skip to main content
Added upper bound.
Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

Here is a slightly better lower bound. If there are fewer than $2q^2$ points then there is some line that hits the set at most once. Consider the $q+1$ planes containing a line containing one point. There must be at least $2q-2$ other points in each of those planes to meet all lines in the plane, for a total of $1+(q+1)(2q-2) = 2q^2-1$ points. So, $2q^2-1 \le s(q)$. This is sharp for $q=2$.


Here is a very slightly better upper bound: $s(q) \le 3q^2-3q$ for $q\ge 3$. This is sharp for $q=3$. Consider parallel hyperplanes $H_1,...,H_q$ and a transverse line $\ell$ intersecting $H_1$ at the point $P$. Consider the $q+1$ lines through $P$ contained in $H_1$. Together with $\ell$, these span $q+1$ planes $K_1,...,K_{q+1}$. Choose $q-1$ pairs $\{K_{i,1},K_{i,2}\}$ so that every plane is chosen at least once, which is possible when $2q-2 \ge q+1,$ or $q \ge 3$.

Include $H_1 \setminus \{P\}$. Include two lines through $\ell \cap H_i$: $H_i \cap K_{i,1}$ and $H_i \cap K_{i,2}$.

This has one fewer point than three hyperplanes intersecting at a point, and it meets all lines. So, for $q \ge 3, s(q) \le 3q^2-3q$.

Here is a slightly better lower bound. If there are fewer than $2q^2$ points then there is some line that hits the set at most once. Consider the $q+1$ planes containing a line containing one point. There must be at least $2q-2$ other points in each of those planes to meet all lines in the plane, for a total of $1+(q+1)(2q-2) = 2q^2-1$ points. So, $2q^2-1 \le s(q)$.

Here is a slightly better lower bound. If there are fewer than $2q^2$ points then there is some line that hits the set at most once. Consider the $q+1$ planes containing a line containing one point. There must be at least $2q-2$ other points in each of those planes to meet all lines in the plane, for a total of $1+(q+1)(2q-2) = 2q^2-1$ points. So, $2q^2-1 \le s(q)$. This is sharp for $q=2$.


Here is a very slightly better upper bound: $s(q) \le 3q^2-3q$ for $q\ge 3$. This is sharp for $q=3$. Consider parallel hyperplanes $H_1,...,H_q$ and a transverse line $\ell$ intersecting $H_1$ at the point $P$. Consider the $q+1$ lines through $P$ contained in $H_1$. Together with $\ell$, these span $q+1$ planes $K_1,...,K_{q+1}$. Choose $q-1$ pairs $\{K_{i,1},K_{i,2}\}$ so that every plane is chosen at least once, which is possible when $2q-2 \ge q+1,$ or $q \ge 3$.

Include $H_1 \setminus \{P\}$. Include two lines through $\ell \cap H_i$: $H_i \cap K_{i,1}$ and $H_i \cap K_{i,2}$.

This has one fewer point than three hyperplanes intersecting at a point, and it meets all lines. So, for $q \ge 3, s(q) \le 3q^2-3q$.

Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

Here is a slightly better lower bound. If there are fewer than $2q^2$ points then there is some line that hits the set at most once. Consider the $q+1$ planes containing a line containing one point. There must be at least $2q-2$ other points in each of those planes to meet all lines in the plane, for a total of $1+(q+1)(2q-2) = 2q^2-1$ points. So, $2q^2-1 \le s(q)$.