Skip to main content
1 of 2
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

This answer is a work in progress, but I think it gives an upper bound on the order of $|\mathcal P| \leq q^{d-1}+ O(q^3)$, which given the $q^{d-1}$ lower bound, is quite close to sharp for $d$ large.

Lemma 1: If $|\mathcal P| > q^{d-1}$ and $| \wedge^{d-1}(\mathcal P^{d-1} )|\geq q (q-1)^2 $ then $| \wedge^d (\mathcal P^{d})| = q$.

Proof: Let $\mathcal Q= \wedge^{d-1}(\mathcal P^{d-1} )$, viewed as a subset of $\mathbb F_q^d$. Since $\wedge^d (\mathcal P^d)$ is the image of $\mathcal P\times \mathcal Q$ under the dot product, it suffices to show that for all $\alpha \in \mathbb F_q$, $\alpha = a \cdot b$ for some $a \in \mathcal P, b \in \mathcal Q$. To do this, we use Fourier analysis

$$\left| \left\{ a\in \mathcal P, b \in \mathcal Q | a \cdot b = \alpha \right\}\right| = \sum_{ \psi: \mathbb F_q \to \mathbb C^\times}\frac{ \overline{\psi(\alpha)} }{ q} \sum_{a \in \mathcal P} \sum_{b \in \mathcal Q} \psi(ab) $$

The term for $\psi=1 $ has size $\frac{ |\mathcal P| |\mathcal Q|}{q}$. Assuming for contradiction that the sum vanishes, the remaining $q-1$ terms must cancel this one, so one must have size at least $$\frac{ |\mathcal P| |\mathcal Q|}{(q-1) q}$$ which implies

$$ \frac{ |\mathcal P| |\mathcal Q|}{q-1}\geq \left| \sum_{a \in \mathcal P} \sum_{b \in \mathcal Q} \psi(ab) \right| = \sqrt{ |\mathcal P|} \sqrt{ \sum_{a \in \mathbb F_q^d} \left| \sum_{b \in \mathcal Q} \psi(ab) \right|^2}= \sqrt{ |\mathcal P | |\mathcal Q| q^d}$$ by Caucy-Schwarz and the Plancherel formula.

Squaring both sides and cancelling, we get $|\mathcal P | |\mathcal Q| \geq q^d (q-1)^2$, contradicting our assumptions. QED

Lemma 2: $| \wedge^{d-1}(\mathcal P^{d-1} )|$ is at least the number of codimension $1$ linear subspaces of $\mathbb F_q^d$ that contain at least $q^{d-2}$ nonzero elements of $\mathbb F_q^d$.

Proof: For each such linear subspace, not all its elements lie in a codimension $2$ linear subspace, or else there would be $q^{d-2}-1$ nonzero elements, so there must be $d-1$ linearly independent, whose $\wedge^{d-1}$ produces a nonzero vector perpendicular to that subspace. Because we never have a nonzero vector perpendicular to two subspaces, the vectors in $\wedge^{d-1} (\mathcal P)$ produced this way are distinct for distinct subspaces. QED

Lemma 3: If there are less than $q (q-1)^2$ codimension $1$ linear subspaces with at least $q^{d-2}$ nonzero elements of $\mathcal P$, then $|\mathcal P| \leq q^{d-1} + \dots $.

Proof: Let $\mathcal P'= \mathcal P \setminus \{0\}$. Consider a random variable $X$ where we pick a random codimension $1$ linear subspace $H$ and count its intersection with $\mathcal P'$. We have $ \mathbb E[X] = \frac{ |\mathcal P'| (q^{d-1}-1)}{(q^d-1)}$ and $$\mathbb E[X^2] = \sum_{x, y \in \mathcal P'} \mathbb P( x, y \in H) = \frac{ |\mathcal P'|^2 (q^{d-2}-1)}{q^{d}- 1} + \sum_{x, y \in \mathcal P'}\left( \mathbb P( x, y \in H)- \frac{ q^{d-2}-1}{q^d-1} \right) $$

$$ =\frac{ |\mathcal P'|^2 (q^{d-2}-1)}{q^{d}-1} + \sum_{ \substack{ x, y\in \mathcal P'\\ y = cx } } \left( \frac{ q^{d-1}-1}{q^d-1} - \frac{q^{d-2}-1}{q^{d}-1} \right) $$ $$ \leq \frac{ |\mathcal P'|^2 (q^{d-2}-1)}{q^{d}-1} + \frac{ |\mathcal P'| (q-1) (q^{d-1} -q^{d-2} )} { q^d-1}$$

so $$\operatorname{Var}(X) \leq \frac{ |\mathcal P'| (q-1) (q^{d-1} -q^{d-2} )} { q^d-1}- \frac{ |\mathcal P'|^2 ( (q^{d-1}-1)^2 - (q^{d-2}-1)(q^d-1)) }{(q^{d}-1)^2} = \frac{ |\mathcal P'| (q-1) (q^{d-1} -q^{d-2} )} { q^d-1}- \frac{ |\mathcal P'|^2 (q-1) (q^{d-1} - q^{d-2} ) }{ (q^d-1)^2}. $$

And thus, by Cantelli's inequality, the probability that $X$ is at least $q^{d-2}$ is at least $ \frac{ ( \mathbb E[X] - q^{d-2} )^2 }{ ( \mathbb E[X] - q^{d-2} )^2+ \operatorname{Var}(X) }$. Because the number of such linear subspaces is at most $q (q-1)^2$, this probability is at most $\frac{ q(q-1)^3}{(q^d-1)}$, and so $$\frac{ ( \mathbb E[X] - q^{d-2} )^2 }{ ( \mathbb E[X] - q^{d-2} )^2+ \operatorname{Var}(X) } \leq \frac{ q(q-1)^3}{(q^d-1)}$$ that is $$ ( \mathbb E[X] - q^{d-2} )^2 \leq \frac{ q(q-1)^3}{(q^d-1)- q(q-1)^3} \operatorname{Var}(X)$$

which gives

$$ \left( \frac{ |\mathcal P'| (q^{d-1}-1)}{(q^d-1)} - q^{d-2} \right) ^2 \leq \frac{ q(q-1)^3}{(q^d-1)- q(q-1)^3} \left( \frac{ |\mathcal P'| (q-1) (q^{d-1} -q^{d-2} )} { q^d-1}- \frac{ |\mathcal P'|^2 (q-1) (q^{d-1} - q^{d-2} ) }{ (q^d-1)^2} \right) $$

which gives some explicit bound by the quadratic formula.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563