4
$\begingroup$

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of $P$, some point of $S$ is incident to some hyperplane of $S'$.

I believe I can prove $k=O( q^{\frac{d+1}2})$ fairly easily but I guess that this is far from optimal. Do you think a better upper bound can be obtained, for instance $q^{O(1)}$? Do you see any non-trivial lower bound?

$\endgroup$

1 Answer 1

3
$\begingroup$

$q^{\frac{d}{2}}$ is a lower bound. Assume $d=2e$, a $d$-dimensional projective space has $d+1=2e+1$ variables $x_0,x_1,\dots,x_e,x_{e+1},\dots,x_{2e}$. Let the points be all vectors with $x_0$ coordinate $1$, $x_1$ through $x_e$ arbitrary, and $x_{e+1}$ through $x_{2e}$ zero. Similarly, let the hyperplanes be vectors with $x_0$ coordinate $1$, $x_1$ through $x_e$ zero, and $x_{e+1}$ through $x_{2e}$ arbitrary. There are $q^e$ points and $q^e$ hyperplanes, and since the dot product between any point and hyperplane is $1$, they are not incident.

For $d=2e+1$ we can do the same thing, except allow $x_{2e+1}$ for both points and hyperplanes to vary in a fixed set with the property that if $x\neq 0$ is in the set, then $x^{-1}$ is not. Such a set can have size $(q-1)/2$. So for $d$ odd we get a lower bound of $O(q^{\frac{d+1}{2}})$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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