Randomly fixing elements and transcendence degree

Question

Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$

$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,f_n\} = r$$

Let $z_1,\ldots,z_j$ be chosen uniformly and independently at random from $\mathbb{F}_q$ then what is

$$ {\Pr}_{z_1,\ldots,z_j}[\operatorname{trdeg}_{\mathbb{F}}\{ f_1(z_1,\ldots,z_j,x_{j+1},\ldots,x_m),\ldots,f_n(z_1,\ldots,z_j,x_{j+1},\ldots,x_m) \} = r ] \text{?} $$

Ideally is the probability large, i.e. not inverse-polynomial in n,m or worse? This probability would be very helpful in my research and any help is appreciated.

Context: I want an efficient way to compute $trdeg_{F(x_1,...,x_j)}\{f_1,...,f_j\}$ which is a key step in my research problem related to finding an efficient algorithm for algebraic independence testing. To solve this problem our idea was to randomly fix $x_1,...,x_j$ to field elements of a large enough field extension and reduce the number of variables. Thus this probability calculation is very crucial.

Edit 1: @Will Sawin solved the case when $\mathbb{F}_q(x_1,...,x_m)/ \mathbb{F}_q(f_1,...,f_n)$ is a seperable extension. I am especially interested in the case when the inseparable degree of extension is $exp(\mathcal{O}(n))$. Any possible idea to solve the high inseparable degree case would be very helpful to me. If we could get a probability bound in terms of $d,n,m, insep-degree$ it would be ideal. Thanks in advance.

Answer 1

Let me give a partial answer ignoring issues of inseparability. The map $\mathbb A^{m-j}_{\mathbb F_q(x_1,\dots,x_j)} \to \mathbb A^n_{\mathbb F_q(x_1,\dots,x_j)}$ has image of dimension $r$. If $\mathbb F_q(x_1,\dots,x_m)$ is a separable extension of $\mathbb F_q(f_1,\dots,f_n)$ then this map is generically smooth onto its image, so at a generic point its derivative has rank $r$. There must therefore exist a $r \times r$ submatrix of the $n \times m-j$ Jacobian matrix of this map such that the determinant of the submatrix is a polynomial in $x_1,\dots, x_m$ that is not identically zero.

If we specialize $x_1,\dots,x_j$ to values $z_1,\dots,z_j$, for the field generated by the specialized polynomials to have transcendence degree $r$, it suffices for the rank of this matrix to be at least $r$, so it suffices for the determinant of the $r \times r$ matrix to be not identically zero. Viewing this determinant as a polynomial in $x_j+1,\dots,x_m$ with coefficients polynomials in $x_1,\dots,x_j$, it suffices to choose a nonzero coefficient polynomial and check that it's non vanishing. The coefficient polynomial will have degree $\leq rd$ and thus the probability of being nonvanishing will be at least $1 - \frac{r(d-1)}{q}$ by Schwartz-Zippel.

This bound is sharp if we take $j=r$ and $f_i = x_{r+i} g_i$ for $g_1,\dots,g_r$ polynomials in $x_1,\dots,x_r$ whose product saturates the Schwartz-Zippel bound.