<p><a href="https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials</a> states multivariate polynomial GCDs may be defined over <span class="math-container">$\mathbb F_p[x_1,x_2,\dots,x_n]$</span> or over <span class="math-container">$\mathbb Z[x_1,\dots,x_n]$</span></p>
<p>Let <span class="math-container">$f(x_1,\dots,x_n),g(x_1,\dots,x_n)\in R[x_1,\dots,x_n]$</span> where <span class="math-container">$R$</span> is the ring <span class="math-container">$\mathbb Z$</span> or a finite field <span class="math-container">$\mathbb F_q$</span>.</p>
<p>Let <span class="math-container">$d$</span> be the total degree of the polynomials.</p>
<p>Let <span class="math-container">$d$</span> and <span class="math-container">$n$</span> be fixed.</p>
<ol>
<li><p>Is there a deterministic <span class="math-container">$NC$</span> algorithm in this case to compute <span class="math-container">$GCD$</span>?</p>
</li>
<li><p>In general how does the parallel complexity scale in terms of <span class="math-container">$d$</span> and <span class="math-container">$n$</span>?</p>
</li>
</ol>

CC BY-SA 4.0
2022-09-22T16:36:21.017Z
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]$.
Emil Jeřábek
CC BY-SA 4.0
2022-09-22T16:44:11.700Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2022-09-22T16:50:37.163Z
... 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$.
Emil Jeřábek
<cc.complexity-theory><polynomials><dc.parallel-comp><algebra><algebraic-complexity>
Polynomial GCD exact complexity in terms of degree and number of variables
Turbo
# Polynomial GCD exact complexity in terms of degree and number of variables

(Asked by: username_0 on 2022-09-21)

<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$?

**Tags:** cc.complexity-theory, polynomials, dc.parallel-comp, algebra, algebraic-complexity

> **Comments:**
> **username_1**: 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]$.  
> **username_1**: 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 ...  
> **username_1**: ... 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$.  

---

## 0 answers

