Annales de la Faculté des Sciences de Toulouse

Martin de Borbon

Dmitri Panov

Dunkl connections on $\mathbb{C}^2$ and spherical metrics

Jacques Sauloy

Classification analytique locale des équations aux $q$-différences de pentes arbitraires

Alexei Borodin

Sergei Korotkikh

Inhomogeneous spin $q$-Whittaker polynomials

Rodolphe Richard

Manin–Mumford topologique fort

Arnoldo Rojas

Xiao Wen

Yinong Yang

Sufficient conditions for rescaling expansivity

Bernard Malgrange

Deux lettres de Bernard Malgrange sur la théorie de Galois différentielle non-linéaire

Stéphane Druel

Projectively flat log smooth pairs

Laurence Halpern

Jeffrey B. Rauch

Perfectly Matched Layers on Cubic Domains for Pauli’s Equations

Stefan Barańczuk

C EN T R E
MER S ENN E
Publication membre du centre
Mersenne pour l’édition scientifique ouverte
http://www.centre-mersenne.org/
e-ISSN : 2258-7519
STEFAN BARAŃCZUK
Reducing the number of equations defining a subset of the n-space over a
finite field
Tome XXXIII, no 1 (2024), p. 177–182.
https://doi.org/10.5802/afst.1766
© les auteurs, 2024.
Les articles des Annales de la Faculté des Sciences de Toulouse sont mis
à disposition sous la license Creative Commons Attribution (CC-BY) 4.0
http://creativecommons.org/licenses/by/4.0/
Annales de la faculté des sciences de Toulouse Volume XXXIII, no 1, 2024
pp. 177-182
Reducing the number of equations defining a subset of
the n-space over a finite field (∗)
Stefan Barańczuk (1)
ABSTRACT. — Let f1, . . . , fk be polynomials defining an algebraic set in affine
n-space over a finite field. Suppose k > n. We prove that there exists a system of
polynomials g1, . . . , gn, each being a linear combination with scalar coefficients of
f1, . . . , fk, defining the same algebraic set. In particular, one reduces the number of
equations without increasing the total degree. We also have the corresponding result
for systems of homogeneous polynomials defining algebraic sets in projective spaces.
RÉSUMÉ. — Soient f1, . . . , fk des polynômes définissant un ensemble algébrique
dans un n-espace affine sur un corps fini. Supposons k > n. Nous montrons qu’il
existe un système de polynômes g1, . . . , gn, chacun étant un combinaison linéaire de
f1, . . . , fk, avec des coefficients scalaires, définissant le même ensemble algébrique.
En particulier, on réduit le nombre d’équations sans augmenter le degré total. Nous
avons aussi le résultat correspondant pour des systèmes de polynômes homogènes
définissant des ensembles algébriques dans des espaces projectifs.
The theorem that any algebraic set in n-dimensional space is the inter-
section of n hypersurfaces(a) has been proved independently by Storch ([2]),
and Eisenbud and Evans ([1]); both short proofs are ring-theoretic, i.e., one
reduces the number of generators of radical ideals.
In this note we examine closer the finite fields case of the problem. If just
the number of equations needed to describe an algebraic set is in question,
then the answer is immediate: it is easy to construct a single polynomial
defining it. If, however, the nature of defining polynomials (e.g., their total
degree) is to be preserved, this problem becomes more interesting.
(*) Reçu le 27 juillet 2021, accepté le 15 février 2022.
Keywords: finite fields; algebraic sets; defining polynomials; reduction.
2020 Mathematics Subject Classification: 11G25, 14A25.
(1) Collegium Mathematicum, Adam Mickiewicz University, ul. Uniwersytetu
Poznańskiego 4, 61-614, Poznań, Poland — stefbar@amu.edu.pl
Article proposé par Damian Rössler.
(a) The problem dates back to Kronecker. Its rather dramatic story is briefly presented
in [1]; for much more detailed vivid account consult N. Schappacher’s available online
presentation Political Space Curves.
– 177 –
Stefan Barańczuk
It turns out that we can avoid dealing with rings; the vector space struc-
ture is sufficient and, as in the theorem cited above, our result again produces
n equations; moreover, we show that these new equations can be chosen to
be linear combinations with scalar coefficients of the old ones, so, roughly
speaking, they remain of the same type (see Corollaries 3 and 4, with ac-
companying examples), and our proof is surprisingly elementary.
We fix the following notation:
Fq the finite field with q elements;
Map(X,Fq) the vector space of all functions f : X → Fq
for a given set X;
Z(f1, . . . , fk) the set of common zeros of f1, . . . , fk ∈ Map(X,Fq);
Span(f1, . . . , fk) the subspace of Map(X,Fq) generated by f1, . . . , fk;
An(K) the affine n-space over a field K;
Pn(K) the projective n-space over a field K;
[α1 : . . . : αn+1] a set of homogeneous coordinates for a point inPn(K).
Theorem 1. — Let X be a set with at most q
n+1−q
q−1 elements. If
f1, . . . , fk ∈ Map(X,Fq) for some k > n then there exist g1, . . . , gn ∈
Span(f1, . . . , fk) such that Z(g1, . . . , gn) = Z(f1, . . . , fk).
This theorem is best possible with respect to the cardinality of X. Indeed,
we have the following.
Proposition 2. — For every field Fq and every positive integer n there
are a set Xn of cardinality q
n+1−q
q−1 +1, and maps f1, . . . , fn+1 ∈ Map(Xn,Fq)
such that Z(f1, . . . , fn+1) = ∅ but Z(g1, . . . , gn) ̸= ∅ for any g1, . . . , gn ∈
Span(f1, . . . , fn+1).
We have two immediate corollaries of Theorem 1 of interest in algebraic
geometry.
Corollary 3. — Let n > 0 and let ϕ : F → Map(An(Fq),Fq) be a
homomorphism of vector spaces over Fq. Any subset of An(Fq) defined by
some members of F (i.e., the zero locus of their images via ϕ) can be defined
using at most n members of F .
The space F can be, for example, a space of polynomials in n variables
of bounded total degree.
Corollary 4. — Let n ⩾ 0 and let ϕ : F → Map(Pn(Fq),Fq) be a
homomorphism of vector spaces over Fq. Any nonempty subset of Pn(Fq)
defined by some members of F (i.e., the zero locus of their images via ϕ)
can be defined using at most n members of F .
– 178 –
Reducing the number of equations over a finite field
The space 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 sepa-
rately state their following ingredient.
Let K be an arbitrary field, and n be a positive integer. Denote by Mn
the set of all matrices in Mn,n+1(K) in reduced row echelon form having the
rank equal to n, by N(M) the null space of a matrix M , by θ the zero vector
in Kn+1, and by ∼ the equivalence relation which identifies points lying on
the same line through the origin.
Lemma 5. — The map
Mn −→ Pn(K)
M 7−→ (N(M) \ {θ})∼
is bijective.
Proof. — Denote by Nn the set of all matrices in Mn,n+1(K) having the
rank equal to n. For every M ∈ Nn the dimension of the vector space
N(M) < Kn+1 equals 1 by the rank-nullity theorem, so (N(M) \ {θ})∼ ∈
Pn(K). We thus have the map
Nn −→ Pn(K)
M 7−→ (N(M) \ {θ})∼
Since matrices of the same size have equal null spaces if and only if they are
row equivalent, the induced map
Nn/GLn(K) −→ Pn(K)
is well-defined and injective. It is also surjective, since every vector subspace
of Kn+1 having dimension equal to 1 is the null space of a matrix in Nn.
Since the canonical map
Mn −→ Nn/GLn(K)
is bijective, the lemma follows. □
Proof of Theorem 1. — It is enough to prove the statement for k = n+1
since we may apply induction.
Denote
S = {[f1(x) : . . . : fn+1(x)] : x ∈ X \ Z(f1, . . . , fn+1)} .
By Lemma 5 every element s of S defines a unique matrix in Mn; denote
this matrix by Ms. Examine the set
T = Mn \ {Ms : s ∈ S} .
– 179 –
Stefan Barańczuk
By Lemma 5 the number of elements in Mn equals the cardinality of Pn(Fq),
i.e., q
n+1−1
q−1 . The number of elements in S is at most the cardinality of X,
i.e., q
n+1−q
q−1 . Hence the cardinality of T is at least
qn+1−1
q−1 −
qn+1−q
q−1 = 1. So
choose a matrix M ∈ T . Our g1, . . . , gn are defined by g1...
gn
 = M
 f1...
fn+1
 .
Indeed, the inclusion Z(f1, . . . , fn+1) ⊂ Z(g1, . . . , gn) is obvious, and by the
definition of T the set Z(g1, . . . , gn) is disjoint from X \ Z(f1, . . . , fn+1), i.e.,
Z(g1, . . . , gn) ⊂ Z(f1, . . . , fn+1). □
In order to prove Proposition 2 we need the following.
Lemma 6. — Let K be an arbitrary field. For any matrix A ∈ Mn,m(K)
where n ⩽ m there exist a matrix M ∈ Mn,m(K) in reduced row echelon form
having the rank equal to n, and a matrix B ∈ Mn,n(K) such that A = BM .
Proof. — Denote by Ir,k,l the matrix in Mk,l(K) having x11 = · · · =
xrr = 1 and all remaining entries equal to 0. Denote the rank of A by r. Let
G1 ∈ GLn(K) and G2 ∈ GLm(K) be matrices transforming A into Ir,n,m, i.e.,
G1AG2 = Ir,n,m. Since Ir,n,m = Ir,n,nIn,n,m, we get A = G−11 Ir,n,nIn,n,mG
−1
2 .
Let G3 ∈ GLn(K) be the matrix transforming In,n,mG−12 into reduced row
echelon form. We have
A = G−11 Ir,n,nG
−1
3 G3In,n,mG
−1
2 .
Put B = G−11 Ir,n,nG
−1
3 and M = G3In,n,mG
−1
2 . □
Proof of Proposition 2. — For every point P ∈ Pn(Fq) choose a set of
homogeneous coordinates for P and denote it by cP . Define Xn =
{cP : P ∈ Pn(Fq)}. The cardinality of Xn is q
n+1−1
q−1 =
qn+1−q
q−1 + 1. Con-
sider f1, . . . , fn+1 ∈ Map(Xn,Fq) defined in the following way: for every
x ∈ Xn put
fi(x) = the ith coordinate of x.
We have Z(f1, . . . , fn+1) = ∅.
Let g1, . . . , gn ∈ Span(f1, . . . , fn+1), i.e., g1...
gn
 = A
 f1...
fn+1

for some matrix A ∈ Mn,n+1(Fq). By Lemma 6 there exist a matrix M ∈
Mn,n+1(Fq) in reduced row echelon form having the rank equal to n, and a
– 180 –
Reducing the number of equations over a finite field
matrix B ∈ Mn,n(Fq) such that A = BM . Hence by Lemma 5 we get that
there is x ∈ Xn belonging to Z(g1, . . . , gn). □
Proof of Corollary 3. — For any positive integer n we have q
n+1−q
q−1 ⩾
qn = |An(Fq)|. Applying Theorem 1 and some elementary algebra, we get
the assertion. □
Remark 7. — It has been suggested by the reviewer of this paper to
include the following example to demonstrate that although the bound
qn+1−q
q−1 ⩾ 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 fi(x1, . . . , xn) = xi.
While Z(f1, . . . , fk) = {θ}, any system of n − 1 combinations of them has at
least q common zeros.
Proof of Corollary 4. — Let {f1, . . . , fk} be the image via ϕ of a subset
of F . Let α ∈ Z(f1, . . . , fk). Denote by f1, . . . , fk the images of f1, . . . , fk via
the restriction homomorphism
r : Map(Pn(Fq),Fq) −→ Map(Pn(Fq) \ {α} ,Fq)
f 7−→ f |Pn(Fq)\{α}.
For any positive integer n we have
|Pn(Fq) \ {α}| = |Pn(Fq)| − 1 =
qn+1 − 1
q − 1 − 1 =
qn+1 − q
q − 1 .
So we apply Theorem 1 to get g1, . . . , gn ∈ Span(f1, . . . , fk) such that
Z(g1, . . . , gn) = Z(f1, . . . , fk). Let A ∈ Mk,n(Fq) be such that g1...
gn
 = A
 f1...
fk
 .
Define g1, . . . , gn ∈ Map(Pn(Fq),Fq) by g1...
gn
 = A
 f1...
fk
 .
We are done, since
Z(f1, . . . , fk) = {α} ∪ Z(f1, . . . , fk),
and Z(g1, . . . , gn) = {α} ∪ Z(g1, . . . , gn). □
– 181 –
Stefan Barańczuk
Acknowledgements
We are grateful to Grzegorz Banaszak and Bartosz Naskręcki for dis-
cussions and suggestions. We wish to thank an anonymous referee for many
improvements; in particular, for suggesting the concise formulation and proof
of Lemma 5.
Bibliography
[1] D. Eisenbud & E. G. Evans, Jr, “Every algebraic set in n-space is the intersection
of n hypersurfaces”, Invent. Math. 19 (1973), p. 107-112.
[2] U. Storch, “Bemerkung zu einem Satz von M. Kneser”, Arch. Math. 23 (1972),
p. 403-404.
– 182 –


Reducing the number of equations defining a subset of the $n$-space over a finite field

Jiafu Ning

Zhiwei Wang

Xiangyu Zhou

On the extension of Kähler currents on compact Kähler manifolds: holomorphic retraction case

Not a member yet

Dunkl connections on $\mathbb{C}^2$ and spherical metrics

Classification analytique locale des équations aux $q$ -différences de pentes arbitraires

Inhomogeneous spin $q$ -Whittaker polynomials

Manin–Mumford topologique fort

Sufficient conditions for rescaling expansivity

Deux lettres de Bernard Malgrange sur la théorie de Galois différentielle non-linéaire

Projectively flat log smooth pairs

Perfectly Matched Layers on Cubic Domains for Pauli’s Equations

Reducing the number of equations defining a subset of the $n$ -space over a finite field

On the extension of Kähler currents on compact Kähler manifolds: holomorphic retraction case

1,744

1,836