Return to 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.

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.

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.

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.

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

$$ trdeg_{\mathbb{F}(x_1,...,x_j)}\{f_1...,f_n\} = r$$

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

$$ Pr_{z_1,...,z_j}[trdeg_{\mathbb{F}}\{ f_1(z_1,..,z_j,x_{j+1},..,x_m),...,f_n(z_1,...,z_j,x_{j+1},..,x_m) \} = r ]?$$

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.

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.