# Polynomial GCD exact complexity in terms of degree and number of variables

https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $$\mathbb F_p[x_1,x_2,\dots,x_n]$$ or over $$\mathbb Z[x_1,\dots,x_n]$$

Let $$f(x_1,\dots,x_n),g(x_1,\dots,x_n)\in R[x_1,\dots,x_n]$$ where $$R$$ is the ring $$\mathbb Z$$ or a finite field $$\mathbb F_q$$.

Let $$d$$ be the total degree of the polynomials.

Let $$d$$ and $$n$$ be fixed.

1. Is there a deterministic $$NC$$ algorithm in this case to compute $$GCD$$?

2. In general how does the parallel complexity scale in terms of $$d$$ and $$n$$?

• You can’t do that for $\mathbb Z[x_1,\dots,x_n]$ (at least with the current state of knowledge), as already the special case $d=n=0$ gives GCD over $\mathbb Z$. The question would be more interesting over $\mathbb Q[x_1,\dots,x_n]$. Sep 22, 2022 at 16:36
• I think that for $F[x_1,\dots,x_n]$ where $F=\mathbb Q$ or $F=\mathbb F_q$ with constant $d$ and $n$, you can compute it even in $\mathrm{TC}^0$. Prove it by induction on $n$. For $n=1$, the usual Euclidean algorithm computes the GCD using $\le d$ divisions. For $n+1$, given $f,g\in F[x_1,\dots,x_{n+1}]$, compute first their GCD in $(F(x_1,\dots,x_n))[x_{n+1}]$ (i.e., as univariate polynomials over the $n$-variate rational function field) using Euclidean algorithm as above. This is only defined up to multiplication by elements of $F(x_1,\dots,x_n)^\times$; thus you can clear denominators ... Sep 22, 2022 at 16:44
• ... to make the GCD an element $h\in(F[x_1,\dots,x_n])[x_{n+1}]$. Use the IH to compute GCD of the coefficients of $h$ in $F[x_1,\dots,x_n]$, say $d\in F[x_1,\dots,x_n]$, and the GCD of the coefficients of $f,g\in(F[x_1,\dots,x_n])[x_{n+1}]$, say $e\in F[x_1,\dots,x_n]$. Then using Gauss’s lemma, the GCD of $f$ and $g$ in $F[x_1,\dots,x_{n+1}]=(F[x_1,\dots,x_n])[x_{n+1}]$ is $eh/d$. Sep 22, 2022 at 16:50