How large a subset of $\mathbb{F}_q^d$ can determine all determinants?

Question

Denote by $\mathbb{F}_q$ a finite field with $q$ elements. For $\mathcal{P}$ be arbitrary subset of $\mathbb{F}_q^d.$ We define the set

$$S:= \left\{ \det([x_1,x_2,\dots,x_d]): x_1,x_2,\dots,x_d \in \mathcal{P}\right\},$$

where $[x_1,x_2,\dots,x_d]$ is $d \times d$ matrix with $d$ column vectors $x_1,x_2,\dots,x_d.$

What is the largest cardinality of $\mathcal{P}$ such that $S \neq \mathbb{F}_q$?

(equivalently, What is the minimum value of $|\mathcal{P}|$ to make sure that $S=\mathbb{F}_q?$)

Comment: If we consider a subset $\mathcal{Q}$ of $M_d(\mathbb{F}_q)$ and $$S:=\left\{\det(A): A \in \mathcal{Q}\right\}.$$ Then, the minimum of cardinality of $\mathcal{Q}$ such that $S=\mathbb{F}_q$ for sure is $$N = q^{d^2} - \dfrac{|\mathrm{GL}_d(\mathbb{F}_q)|}{q-1} + 1.$$

How about the previous question?

Answer 1

This answer gives an upper bound of size

$$\frac{ q^{d-2}(q^d-1)}{(q^{d-1}-1)}+ \frac{ (q^d-1) q^{\frac{d-1}{2}} (q-1)^{\frac{5}{2}} } { 2 (q^{d-1}-1) \sqrt{ q^d-1- q(q-1)^3} } + 1 = q^{d-1} +\frac{ q^3}{2} + o(q^3) $$

Because Nguyễn Văn Thế gave a lower bound of $q^{d-1}$ in the comments, it is close to sharp for large $d$. The gap can be improved by a factor of $\frac{q^{1/2}}{2}$ by just doing more calculations at the end.

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 \frac{ q^{d-2}(q^d-1)}{(q^{d-1}-1)}+ \frac{ (q^d-1) q^{\frac{d-1}{2}} (q-1)^{\frac{5}{2}} } { 2 (q^{d-1}-1) \sqrt{ q^d-1- q(q-1)^3} } + 1 $.

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} $$

$$ \leq \frac{ (q-1) (q^{d-1} - q^{d-2} )}{ 4} $$

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) \leq \frac{ q^{d-1} (q-1)^5}{4( (q^d-1)- q(q-1)^3) } $$

which gives

$$\mathbb E[X] \leq q^{d-2} + \frac{ q^{\frac{d-1}{2}} (q-1)^{\frac{5}{2}} } { 2 \sqrt{ q^d-1- q(q-1)^3} }$$

$$ |\mathcal P'| \leq \frac{ q^{d-2}(q^d-1)}{(q^{d-1}-1)}+ \frac{ (q^d-1) q^{\frac{d-1}{2}} (q-1)^{\frac{5}{2}} } { 2 (q^{d-1}-1) \sqrt{ q^d-1- q(q-1)^3} }$$

$$|\mathcal P| \leq\frac{ q^{d-2}(q^d-1)}{(q^{d-1}-1)}+ \frac{ (q^d-1) q^{\frac{d-1}{2}} (q-1)^{\frac{5}{2}} } { 2 (q^{d-1}-1) \sqrt{ q^d-1- q(q-1)^3} } + 1$$

QED

Answer 2

Based on a conversation with Lspice, here is an idea to play with to (for large q) get away with much fewer than q+d vectors. I will show a non optimal example.

Let d be at least 4, and q sufficiently large (bigger than 1000). I pick q=1009. The first row will have ten powers of two, from 1 to 512. The second will have seven powers of three, from 1 to 729. The third row will have powers of five from 1 to 625. (Each of these are really the power times the ith basis vector). The last row will have the remaining primes, and where needed, products of smaller primes. This will be 165 primes, about a similar number of products of two primes, and a smattering (less than four hundred all told) of products of three primes, not necessarily distinct. This gives less than 500 vectors to give positive determinants up to 1008.

Of course one needs d distinct vectors to give a nonzero determinant, but not much more to get all values of the field as determinants. And this is computing determinants as if they were integer matrices. Further savings can be realized if one does the determinant computation over the field itself.

I do not have a good sense of asymptotic or even a good lower bound for this. I imagine one needs a quantity like k(q^(1/k)) involved, but I can't show that is a lower bound.

Gerhard "Has Got This Party Started" Paseman, 2019.11.26.