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?



Point-Hyperplane incidence in finite projective spaces
$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}})$.


