3 Results
Let \(X\) be a set with at most \(\frac{q^{n+1}-q}{q-1}\) elements. If \(f_{1}, \ldots , f_{k} \in \mathrm{Map}(X,{\mathbb {F}_{q}})\) for some \(k{\gt}n\) then there exist \(g_{1}, \ldots , g_{n} \in \mathrm{Span}(f_{1}, \ldots , f_{k})\) such that \(\mathrm{Z}(g_{1}, \ldots , g_{n})=\mathrm{Z}(f_{1}, \ldots , f_{k})\).
This theorem is best possible with respect to the cardinality of \(X\). Indeed, we have the following.
For every field \({\mathbb {F}_{q}}\) and every positive integer \(n\) there are a set \(X_{n}\) of cardinality \(\frac{q^{n+1}-q}{q-1}+1\), and maps \(f_{1}, \ldots , f_{n+1} \in \mathrm{Map}(X_{n},{\mathbb {F}_{q}})\) such that \(\mathrm{Z}(f_{1}, \ldots , f_{n+1})=\emptyset \) but \(\mathrm{Z}(g_{1}, \ldots , g_{n})\ne \emptyset \) for any \(g_{1}, \ldots , g_{n} \in \mathrm{Span}(f_{1}, \ldots , f_{n+1})\).
We have two immediate corollaries of Theorem 1 of interest in algebraic geometry.
Let \(n {\gt} 0\) and let \(\phi \colon \mathcal{F} \to \mathrm{Map}(\mathbb {A}^{n}({\mathbb {F}_{q}}),{\mathbb {F}_{q}})\) be a homomorphism of vector spaces over \({\mathbb {F}_{q}}\). Any subset of \(\mathbb {A}^{n}({\mathbb {F}_{q}})\) defined by some members of \(\mathcal{F}\) (i.e., the zero locus of their images via \(\phi \)) can be defined using at most \(n\) members of \(\mathcal{F}\).
The space \(\mathcal{F}\) can be, for example, a space of polynomials in \(n\) variables of bounded total degree.
Let \(n \ge 0\) and let \(\phi \colon \mathcal{F} \to \mathrm{Map}(\mathbb {P}^{n}({\mathbb {F}_{q}}),{\mathbb {F}_{q}})\) be a homomorphism of vector spaces over \({\mathbb {F}_{q}}\). Any nonempty subset of \(\mathbb {P}^{n}({\mathbb {F}_{q}})\) defined by some members of \(\mathcal{F}\) (i.e., the zero locus of their images via \(\phi \)) can be defined using at most \(n\) members of \(\mathcal{F}\).
The space \(\mathcal{F}\) can be a space of homogeneous polynomials in \(n+1\) variables of bounded total degree, the space of quadratic (or higher degree) forms in \(n+1\) variables, the space of diagonal forms in \(n+1\) variables, etc.
Before we present the proofs of Theorem 1 and Proposition 2, we separately state their following ingredient.
Let \(\mathbb {K}\) be an arbitrary field, and \(n\) be a positive integer. Denote by \(\mathcal{M}_{n}\) the set of all matrices in \(M_{n, n+1}(\mathbb {K})\) in reduced row echelon form having the rank equal to \(n\), by \(N(M)\) the null space of a matrix \(M\), by \(\theta \) the zero vector in \(\mathbb {K}^{n+1}\), and by \(\sim \) the equivalence relation which identifies points lying on the same line through the origin.
The map
is bijective. [BN:Aristotle formalized a slightly different version of this lemma]
Denote by \(\mathcal{N}_{n}\) the set of all matrices in \(M_{n, n+1}(\mathbb {K})\) having the rank equal to \(n\). For every \(M \in \mathcal{N}_{n}\) the dimension of the vector space \(N(M) {\lt} \mathbb {K}^{n+1}\) equals \(1\) by the rank–nullity theorem, so \((N(M)\setminus \left\lbrace \theta \right\rbrace )_{\sim } \in \mathbb {P}^{n}(\mathbb {K})\). We thus have the map
Since matrices of the same size have equal null spaces if and only if they are row equivalent, the induced map
is well-defined and injective. It is also surjective, since every vector subspace of \(\mathbb {K}^{n+1}\) having dimension equal to \(1\) is the null space of a matrix in \(\mathcal{N}_{n}\).
Since the canonical map
is bijective, the lemma follows.
It is enough to prove the statement for \(k=n+1\) since we may apply induction.
Denote
By Lemma 5 every element \(s\) of \(S\) defines a unique matrix in \(\mathcal{M}_{n}\); denote this matrix by \(M_{s}\). Examine the set
By Lemma 5 the number of elements in \(\mathcal{M}_{n}\) equals the cardinality of \(\mathbb {P}^{n}({\mathbb {F}_{q}})\), i.e., \(\frac{q^{n+1}-1}{q-1}\). The number of elements in \(S\) is at most the cardinality of \(X\), i.e., \(\frac{q^{n+1}-q}{q-1}\). Hence the cardinality of \(T\) is at least \(\frac{q^{n+1}-1}{q-1}-\frac{q^{n+1}-q}{q-1}=1\). So choose a matrix \(M\in T\). Our \(g_{1}, \ldots , g_{n}\) are defined by
Indeed, the inclusion \(\mathrm{Z}(f_{1}, \ldots , f_{n+1}) \subset \mathrm{Z}(g_{1}, \ldots , g_{n})\) is obvious, and by the definition of \(T\) the set \(\mathrm{Z}(g_{1}, \ldots , g_{n})\) is disjoint from \(X \setminus \mathrm{Z}(f_{1}, \ldots , f_{n+1})\), i.e., \(\mathrm{Z}(g_{1}, \ldots , g_{n}) \subset \mathrm{Z}(f_{1}, \ldots , f_{n+1})\).
In order to prove Proposition 2 we need the following.
Let \(\mathbb {K}\) be an arbitrary field. For any matrix \(A \in M_{n, m}(\mathbb {K})\) where \(n\le m\) there exist a matrix \(M \in M_{n, m}(\mathbb {K})\) in reduced row echelon form having the rank equal to \(n\), and a matrix \(B \in M_{n, n}(\mathbb {K})\) such that \(A=BM\).
Denote by \(I_{r, k, l}\) the matrix in \(M_{k, l}(\mathbb {K})\) having \(x_{11}=\ldots =x_{rr}=1\) and all remaining entries equal to 0. Denote the rank of \(A\) by \(r\). Let \(G_{1} \in GL_{n}(\mathbb {K})\) and \(G_{2} \in GL_{m}(\mathbb {K})\) be matrices transforming \(A\) into \(I_{r, n, m}\), i.e., \(G_{1} A G_{2} = I_{r, n, m}\). Since \(I_{r, n, m}=I_{r, n, n}I_{n, n, m}\), we get \(A=G_{1}^{-1}I_{r, n, n}I_{n, n, m}G_{2}^{-1}\). Let \(G_{3} \in GL_{n}(\mathbb {K})\) be the matrix transforming \(I_{n, n, m}G_{2}^{-1}\) into reduced row echelon form. We have
Put \(B=G_{1}^{-1}I_{r, n, n}G_{3}^{-1}\) and \(M= G_{3}^{}I_{n, n, m}G_{2}^{-1}\).
For every point \(P \in \mathbb {P}^{n}({\mathbb {F}_{q}})\) choose a set of homogeneous coordinates for \(P\) and denote it by \(c_{P}\). Define \(X_{n}=\left\lbrace c_{P} \colon P \in \mathbb {P}^{n}({\mathbb {F}_{q}}) \right\rbrace \). The cardinality of \(X_{n}\) is \(\frac{q^{n+1}-1}{q-1}=\frac{q^{n+1}-q}{q-1}+1\). Consider \(f_{1}, \ldots , f_{n+1} \in \mathrm{Map}(X_{n},{\mathbb {F}_{q}})\) defined in the following way: for every \(x\in X_{n}\) put
We have \(\mathrm{Z}(f_{1}, \ldots , f_{n+1})=\emptyset \).
Let \(g_{1}, \ldots , g_{n} \in \mathrm{Span}(f_{1}, \ldots , f_{n+1})\), i.e.,
for some matrix \(A \in M_{n, n+1}({\mathbb {F}_{q}})\). By Lemma 6 there exist a matrix \(M \in M_{n, n+1}({\mathbb {F}_{q}})\) in reduced row echelon form having the rank equal to \(n\), and a matrix \(B \in M_{n, n}({\mathbb {F}_{q}})\) such that \(A=BM\). Hence by Lemma 5 we get that there is \(x \in X_{n}\) belonging to \(\mathrm{Z}(g_{1}, \ldots , g_{n})\).
For any positive integer \(n\) we have \(\frac{q^{n+1}-q}{q-1}\ge q^{n}=\left| \mathbb {A}^{n}({\mathbb {F}_{q}})\right|\). Applying Theorem 1 and some elementary algebra, we get the assertion.
It has been suggested by the reviewer of this paper to include the following example to demonstrate that although the bound \(\frac{q^{n+1}-q}{q-1}\ge q^{n}\) used in the proof of Corollary 3 is rather crude, the result is sharp for any \(q\). Consider the system of \(n\) polynomials \(f_{i}(x_{1}, \ldots , x_{n})=x_{i}\). While \(\mathrm{Z}(f_{1}, \ldots , f_{k})=\left\lbrace \theta \right\rbrace \), any system of \(n-1\) combinations of them has at least \(q\) common zeros.
Let \(\left\lbrace f_{1}, \ldots , f_{k}\right\rbrace \) be the image via \(\phi \) of a subset of \(\mathcal{F}\). Let \(\alpha \in \mathrm{Z}(f_{1}, \ldots , f_{k})\). Denote by \(\bar{f_{1}}, \ldots , \bar{f_{k}}\) the images of \(f_{1}, \ldots , f_{k}\) via the restriction homomorphism
For any positive integer \(n\) we have
So we apply Theorem 1 to get \(\bar{g_{1}}, \ldots , \bar{g_{n}}\in \mathrm{Span}(\bar{f_{1}}, \ldots , \bar{f_{k}})\) such that \(\mathrm{Z}(\bar{g_{1}}, \ldots , \bar{g_{n}}) =\mathrm{Z}(\bar{f_{1}}, \ldots , \bar{f_{k}})\). Let \(A \in M_{k, n}({\mathbb {F}_{q}})\) be such that
Define \(g_{1}, \ldots , g_{n} \in \mathrm{Map}(\mathbb {P}^{n}({\mathbb {F}_{q}}),{\mathbb {F}_{q}})\) by
We are done, since