0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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]$. $\endgroup$
    – Emil Jeřábek
    Sep 22, 2022 at 16:36
  • 2
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Sep 22, 2022 at 16:44
  • 2
    $\begingroup$ ... 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$. $\endgroup$
    – Emil Jeřábek
    Sep 22, 2022 at 16:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy