Degree of extension of root of a polynomial system

Question

Let $f_1, \ldots, f_m \in \mathbb{F}[x_1, \ldots, x_n]$ be degree d polynomials and assume $n =O(1)$. Consider the following system, \begin{equation}\label{1} f_1(\bar{x})=0, f_2(\bar{x})=0, \ldots, f_m(\bar{x})=0 \end{equation}.

If the above system has a solution in $\bar{\mathbb{F}}$, what's the minimum degree of extension where we can guarantee to find a solution? I think that it should be $poly(m,d)$ (note, I am assuming $n$ is constant).

Answer 1

We proceed by induction on the number of variables. The following lemma is the cornerstone of the proof.

Lemma 1. Let $f_1, \ldots, f_m \in \mathbb{F}[\bar{X}]$ be a system of equations of degree at most $d$ which has solutions in $\bar{\mathbb{F}}^n$. There exists $\alpha \in \bar{\mathbb{F}}$ such that $[\mathbb{F}(\alpha) : \mathbb{F}] \leqslant \mathrm{poly}(d)$ and the system of equations $$ f_1(\alpha, \bar{Y}) = \cdots = f_m(\alpha, \bar{Y}) = 0\ \mbox{ with } \bar{Y} = (X_2, \ldots, X_n) $$ has a solution in $\bar{\mathbb{F}}^{n-1}$.

The desired result derives from Lemma 1 by a straightforward induction on $n$. I might miss something but my bound depends only on $n$ and $d$. Before proving the above lemma, I recall a classical result of algebra.

The main theorem of the Elimination Theory. Let $Z \subset (\mathbb{P}^r \times \mathbb{P}^s)(\bar{\mathbb{F}})$ be a closed algebraic set defined by a system of $m$ equations in $\mathbb{F}[\bar{X}, \bar{Y}]$ of degree at most $d$ and homogeneous in $\bar{X}$ and $\bar{Y}$. Then the image of $Z$ by the projection $\pi_s : \mathbb{P}^r \times \mathbb{P}^s \to \mathbb{P}^r$ is a closed algebraic set defined by $\mathrm{poly}(m)$ homogeneous equations in $\mathbb{F}[\bar{X}]$ of degree at most $\mathrm{poly}(d)$.

The above theorem is well-known but I didn't find a reference given the upper estimate of the complexity of the elimination ideal in terms of the complexity of $Z$. So I give a proof based on a sketch proof in Complex Projective Varieties by Mumford (see p.35).

Proof. We follow the classical proof based on resultants. By an inductive scheme describes by Mumford, we can assume that $s = 1$, which means we eliminate only one variable. Let $g_1, \ldots, g_m \in \mathbb{F}[\bar{X}, Y]$ be a system of equations defining $Z$ as in the hypotheses. Consider the homogeneous resultant $$ R = \mathrm{Res}_Y (\sum_{i=1}^m U_i g_i, \sum_{i=1}^m V_i g_i) \in \mathbb{F}[U_i, V_i][\bar{X}].$$ Expanding this resultant as a polynomial in $U_i, V_i$, we got $$ R = \sum_{\alpha, \beta} R_{\alpha \beta} U^{\alpha} V^{\beta} \mbox{ with } R_{\alpha\beta} \in \mathbb{F}[\bar{X}]. $$ The length of this sum is bounded by $\mathrm{poly}(m)$ and each $R_{\alpha\beta}$ is a homogeneous polynomial of degree at most $\mathrm{poly}(d)$. Now, we can prove that $\bar{x} \in \bar{\mathbb{F}}^r$ lie in $\pi_1(Z)$ if and only if $\bar{x}$ satisfies the system of equations $R_{\alpha\beta}$ (see 1 for details).

Proof of Lemma 1. Let $g_i$ be the homogenization of $f_i$ in $X_0$ and $\bar{Y}$ the apply the theorem with $Z = \mathcal{Z}(g_1, \ldots, g_m)$ and $r = 1$ and $s = n-1$. Pick $\beta \in \pi_{n-1}(Z)$. We can assume $\beta = [\alpha : 1]$. Then $\alpha$ vanishes a univariate polynomial of degree at most $\mathrm{poly}(d)$ with coefficients in $\mathbb{F}$.