\documentstyle[11pt]{article}
\textwidth = 15cm
\textheight = 20cm
\hoffset -1.cm
%\voffset -2.4cm
\topmargin0pt
\headheight0pt
\headsep0pt
\parskip = 0.8 em plus 0.1 em minus 0.2 em
%\renewcommand{\baselinestretch}{1.5}

%\frenchspacing
\sloppy

\newcommand{\ZZ}{\mbox{$Z \hskip -4.8pt Z$}}
\newsavebox{\rational}
\savebox{\rational}{
   {\hskip -11pt}
   \setlength{\unitlength}{1mm}
   \begin{picture}(2.65,2)
       \put(0,0){\mbox{Q}}
       \thicklines
       \put(1.1,0.25){\line(0,1){2.2}} %2.5 --> 2.2
   \end{picture}
}
\newcommand{\QQ}{\usebox{\rational}}
\newcommand{\rem}{\mbox{\em rem}}
\newtheorem{lemma}{Lemma}[section]
%\input amssym.def
%\input amssym.tex
\parskip 2ex

%************************* fuer die Korrektur-Version *************************
\renewcommand{\baselinestretch}{2}
%******************************************************************************
\begin{document}

\renewcommand{\baselinestretch}{.9}
{\small
\title{Short Proofs for Nondivisibility of Sparse Polynomials 
       under the Extended Riemann Hypothesis 
       %\thanks{A version of this paper submitted to the AAECC Journal}
       }
\author{
Dima Yu. Grigoriev\\
Max Planck Institute of Mathematics\\
5300 Bonn 1\\
\\
Marek Karpinski\thanks{Supported in part by the Leibniz Center for
Research in Computer Science, by the DFG Grant KA 673/4--1 and by the
SERC Grant GR--E 68297}\\
Dept. of Computer Science\\
University of Bonn\\
5300 Bonn 1 \\
\small{and}\\
International Computer Science Institute\\
Berkeley, California\\
\\
Andrew M. Odlyzko\\
AT\&T Bell Laboratories\\
Murray Hill, NJ 07974}
\date{}
\maketitle
}

\vspace*{-2ex}
\renewcommand{\baselinestretch}{1}
\begin{abstract}

Symbolic manipulation of sparse polynomials, given as lists of 
exponents and nonzero 
coefficients, appears to be much more complicated than dealing with
polynomials in dense encoding (see e.g. \cite{GKS,KT,Pla,Pla1}).
The first results in this direction are due to Plaisted \cite{Pla,Pla1}, 
who proved, in
particular, the NP-completeness of divisibility of a polynomial $x^n-1$ 
by a product of
sparse polynomials.
On the other hand, essentially nothing nontrivial is known
about the complexity of the divisibility problem of two sparse integer 
polynomials.
(One can easily prove that it is in PSPACE with the help of \cite{Mul}.)
Here we prove that nondivisibility of two sparse multivariable polynomials 
is in NP, 
provided that the Extended Riemann Hypothesis (ERH) holds (see e.g. \cite{LO}).

The divisibility problem is closely related to the rational interpolation problem 
(whose decidability and complexity bound are determined in \cite{GKS}).
In this setting we assume that a rational function is given by a black box 
for evaluating it.
We prove also that the problem of deciding whether a rational function given by
a black box equals a polynomial belongs to the parallel class NC (\cite{KR88}), 
provided 
the ERH holds and moreover, 
that we know the degree of some sparse rational representation of it.

\end{abstract}

\pagebreak

\section{Nondivisibility problem for sparse polynomials}

Let $f = \sum_{1 \leq i \leq t} a_i X^{J_i}$,
$g = \sum_{1 \leq i \leq t} b_i X^{K_i} \in \ZZ [X_1 , \ldots , X_n ]$
be two at most $t$-sparse polynomials.
Assume that every degree $\deg_{x_j} (f)$,
$\deg_{x_j} (g) < d$,
$1 \leq j \leq n$ and the bit-size $l( a_i )$, $l ( b_i )$ of each integer coefficient 
$a_i$, $b_i$ is less than $M$.
The problem is to test, whether $g$ divides $f$.
Observe that the bit-size of input data
is
$O( t(M+ n \, \log \, d ))$.

First, we consider the case $n=1$ of one-variable polynomials 
$f = \sum_{1 \leq i \leq t} a_i x^{j_i}$,
$g = \sum_{1 \leq i \leq t} b_i x^{k_i}$.

\noindent
{\bf Lemma 1.} \quad
{\em Any nonzero root of $g$ (also of $f$) has multiplicity less than $t$.}

\noindent
{\bf Proof.} \quad
Assume the contrary and let $x_0 \neq 0$
be a root of $g$ with multiplicity at least $t$.
Then $g( x_0) = g^{(1)} (x_0) = \cdots = g^{(t-1)} (x_0) = 0$.
Hence the $t \times t$ matrix
%
\begin{eqnarray*}
1 & \cdots & 1 \\
k_1 & \cdots & k_t \\
k_1(k_1 -1) & \cdots & k_t ( k_t -1 ) \\
k_1 ( k_1-1) (k_1-2) & \cdots & k_t ( k_t-1) ( k_t-2 )\\
\vdots~~~~~~~~~~~ &   & \\
k_1(k_1 -1 ) \cdots ( k_1 - t+2) & \cdots & k_t ( k_t-1) \cdots ( k_t -t+2 )
\end{eqnarray*}
is singular.
This leads to a contradiction since this matrix by elementary transformations 
of its rows can be reduced to a Vandermonde matrix.$~~~\Box$

Assume that $g$ does not divide $f$.
Then there exists a factor $h \in \ZZ [x]$ of $g$
that is irreducible over $\QQ$, and such that its multiplicity $m_g$ in $g$
is larger than its multiplicity $m_f$ in $f$. The Lemma~1 above shows $m_g < t$.

There exist polynomials $u, v \in \QQ [x]$ with $\deg(u)$, $\deg(v) < d$ such that
$1= uh + v \left( \frac{f}{h^{m_f}} \right)$. Taking into account the bounds
$l(h)$, $l \left( \frac{f}{h^{m_f}} \right) \leq M+d$ that apply to factors of $g$, $f$, 
respectively, we obtain $l(u)$, $l(v) \leq Md^{O(1)}$ by virtue of the bounds on the 
bit-size of minors of the Sylvester matrix (see e.g. \cite{CG,Loo,Mig}).
Let us rewrite the equality in the following way:
$w_0 = u_0 h+ v_0 \left( \frac{f}{h^{m_f}} \right)$, where
$w_0 \in \ZZ$, $u_0$, $v_0 \in \ZZ [x]$.
There exist at most $M \cdot d^{O(1)}$ primes which divide $w_0$.
Therefore, there exists a prime $p \leq N = (Md)^{O(1)}$ (provided the ERH holds 
\cite{LO,Wei}) which does not divide any of $w_0$, the leading coefficient $lc(g)$ of $g$
and the discriminant of $h$, and moreover the polynomial 
$h( \bmod p ) \in {\rm GF}(p) [x]$ has a root in ${\rm GF}(p)$.
Then the multiplicity of this root in $f$ equals $m_f$ and in $g$ is at least $m_g$.

The nondeterministic procedure under construction guesses a prime $p \leq N$ 
and an element $\alpha \in {\rm GF}(p)$ and tests whether for some $0 \leq i \leq t-1$
one has $g( \alpha ) = g^{(1)} ( \alpha ) = \cdots = g^{(i)} ( \alpha ) = 0$,
$f^{(i)} ( \alpha ) \neq 0$, $lc(g) \neq 0$ in ${\rm GF}(p)$.

One can easily see that if such $p$, $\alpha$ exist then $g$ does not divide $f$.
Indeed, in the opposite case, $( lc (g))^s f = ge$ for some integer $s$ and a polynomial 
$e \in \ZZ [x]$. Reducing this equation $\bmod~ p$, one gets a contradiction.

Now we return to the multivariate case. Suppose again that $g$ does not divide $f$.
Let $h \in \ZZ [ X_1 , \ldots , X_n ]$ have a similar property to the $h$ in the 
univariate case. Assume without loss of generality that a variable $X_1$
occurs in $h$. Then $g$ also does not divide $f$ in the ring
$\QQ ( X_2 , \ldots , X_n ) [ X_1 ]$ by the Gauss lemma.
Consider division of $f$ by $g$ with remainder in the latter ring:
$f= g \mu + \theta$.
Then $\deg_{X_i} ( \mu )$, $\deg_{X_i} ( \theta ) < d^2$,
$2 \leq i \leq n$ (cf.~\cite{Loo}) and the denominators of $\mu$, $\theta$ 
are the powers of $lc_{X_1} (g) \in \ZZ [ X_2 , \ldots X_n ]$.
Hence for some integers $0 \leq x_2 , \ldots , x_n \leq d^2 +d$ we have
$( lc_{X_1} (g) \cdot lc_{X_1} ( \theta )) ( x_2 , \ldots , x_n ) \neq 0$.
Therefore, the polynomial $g( X_1, x_2 , \ldots , x_n ) \in \ZZ [X_1]$ does not
divide
$f( X_1, x_2 , \ldots , x_n ) \in \ZZ [ X_1]$ in the ring $\QQ [X_1]$.

The nondeterministic procedure guesses an index $1 \leq i \leq n$, thus $X_i$ 
(in our argument above its role was played by $X_1$), the integers 
$0 \leq x_2 , \ldots , x_n \leq d^2 + d$ and applies the nondeterministic procedure
described before to one-variable polynomials
$g( X_1, x_2 , \ldots , x_n )$,
$f( X_1 , x_2 , \ldots , x_n )$. Thus, we have proved the following 

\noindent
{\bf PROPOSITION~1.} \quad
Nondivisibility of sparse multivariate polynomials belongs to NP provided 
the Extended Riemann Hypothesis holds.

\section{Divisibility problem for sparse rational function given by a black box}


The Proposition~1 can be improved if $t$-sparse $f$,
$g \in \ZZ [X_1 , \ldots , X_n ]$ are not explicitely given,
but we only have a black box (see e.g. \cite{GK,GKS})
for the rational function $f/g$ provided that $lc_{X_1} (g) =1$,
%*********************** Korrektur von 26.02.92 ************************
i.e. $g=X_1^m + \sum\limits_{0 \leq i \leq m-1} g_i X_1^i$    
where the polynomials $g_i \in \ZZ[X_2, \ldots, X_n]$,
%***********************************************************************
and a bound on $d$ 
is given. This is due to the fact that in the one-variable case we need only a bound 
on $M$ which one can compute by the parallel NC-algorithm from a black box 
relying on the construction from \cite{GK}. 
To do this we proceed as follows. \\
Assume that $f = \sum\limits_{1 \leq i \leq t_1} a_i x^{j_i}$, 
            $g = \sum\limits_{1 \leq i \leq t_2} b_i x^{k_i}$, $t_1,t_2 \leq t$ and
$g$ has a minimal possible degree for any $t$-sparse representation of the rational
function $q = f/g$. \\
Let $M = \max\limits_{i} \{ l(a_i), l(b_i) \} + 1$.

Take successive primes $p_1, \cdots ,p_t$ and for each $p$ among them calculate
(by black box) $q(p), q(p^2), \cdots ,q(p^{2t^2+1})$. For at least one $p$ all these
values are defined, i.e. $g$ does not vanish in these points. Let us fix such $p$.

\noindent
{\bf Lemma 2.} \quad
{\em At least one of $q(p), q(p^2), \cdots ,q(p^{2t^2+1})$ has absolute value 
greater than $2^{M/2t} / t^{4dt^2}$.}

\noindent
{\bf Proof.} \quad
Denote ${\cal N} = \max \{ |q(p)|, \cdots ,|q(p^{2t^2+1})| \}$. The homogenous 
linear system in the indeterminates $A_i, \; B_i$
\[
 \sum\limits_{1 \leq i \leq t_1} A_i p^{sj_i} = 
(\sum\limits_{1 \leq i \leq t_2} B_i p^{sk_i})q(p^s), \quad 1 \leq s \leq 2t^2+1
\]
has a unique solution since the polynomials $f, \: g$ provide a minimal $t$-sparse
representation of $q$, hence 
$(\sum\limits_{1 \leq i \leq t_1} A_i x^{j_i}) / 
 (\sum\limits_{1 \leq i \leq t_2} B_i x^{k_i}) = q(x)$.
Therefore, each $a_i, \: b_i$ equals to a quotient of a suitable pair of
$(t_1+t_2-1) \times (t_1+t_2-1)$ minors of this linear system.
Then $\max \{ |a_i|, |b_i| \} \leq ({\cal N} p^{2t^2d} \dot 2t)^{2t} 
                              \leq ({\cal N} t^{4dt^2})^{2t}$.
The lemma is proved. $~~~\Box$

One can construct (by an NC-algorithm) the integer $t^{4dt^2}$ 
(see, e.g., \cite{12}), then by Lemma~2 
an integer larger than $2^{M/2t}$ and again using \cite{12} an integer larger than
$2^M$.

%In the multivariate case, one has
%$lc_{X_1} (h) =1$ for any factor $h$ of $g$ and one can take $X_1$ as
%the main variable in the reduction from multivariate case to
%one-variable one that is described above.

Then the algorithm constructs an integer $N_0 > 36 \cdot 2^{3M} \cdot
d^5 \;$.
Finally, the algorithm yields the number $N = q(q(N_0))$. 
We claim that $N$ is big enough (see \cite{GK}), namely, divide with
the remainder $f = eg + \rem (f,g)$, then for each integer $N_1 \geq
N$ we have $0 < | \frac{\rem (f,g)}{g} (N_1) | < \frac{1}{2}$,
provided that $\rem (f,g) \neq 0$.

Let us prove the claim.
Denote $d_1=\deg (f)$, $d_0=\deg (g)$.
Without loss of generality, assume that $lc(f) > 0$. Then $f(N_0) > N_0^{d_1} - d
N_0^{d_1-1} 2^M > \frac{1}{2} N_0^{d_1}$, $0 < g(N_0) < N_0^{d_0} + d
N_0^{d_o-1} 2^M < \frac{3}{2} N_0^{d_0}$, hence $q(N_0) > \frac{1}{3}
N_0^{d_1-d_0}$.
On the other hand $f(N_0) < 2^M d N_0^{d_1}$, $g(N_0) > N_0^{d_0} -
2^M d N_0^{d_0-1} > \frac{1}{2} N_0^{d_0}$, therefore $q(N_0) < 2^{M+1}
d N_0^{d_1-d_0}$.
We get that $q(N_0) < \frac{1}{3} N_0$ if and only if $d_1 = d_0$. In this case
$g$ divides $f$ if and only if $f/g \equiv \mbox{\em const}$; arguing
as in the proof of Lemma~2 the latter identity is equivalent to the
equalities $q(p) = \cdots = q(p^{2t^2+1})$.
So, we assume now that $d_1 -d_0 > 0$. Notice that 
the absolute value of each coefficient of $\rem (f,g)$ is at most 
$((d_1-d_0+2)2^M)^{d_1-d_0+2}$ (see e.g.~\cite{Loo}). In a similar way 
$N=q(q(N_0)) > \frac{1}{3} (q(N_0))^{d_1-d_0} > 3^{d_0-d_1-1}
N_0^{(d_1-d_0)^2}$ and $g(N) > N^{d_0} - 2^M d_0 N^{d_0-1} >
\frac{1}{2} N^{d_0}$.
Hence $0 < |\rem (f,g) (N)| < ((d_1-d_0+2)2^M)^{d_1-d_0+2} d_0
N^{d_0-1} < \frac{1}{4} N^{d_0}$.
This proves the claim.

So, divisibility $g|f$ is equivalent to $(f/g)(N)$ being an integer.
The number of 
%*********************** Korrektur vom 26.2.92 *******************
the black box evaluations and
%*****************************************************************
arithmetic operations of the exhibited algorithm is at
most $(t \log d)^{O(1)}$ with the depth $O(\log t \log \log d)$.
Thus, the divisibility problem for one-variable rational function
given by a black box, is in NC.

In the multivariate case divide with the remainder $f = eg + \rem
(f,g)$ with respect to the variable $X_1$, namely in the ring $\QQ(X_2, \cdots
,X_n)[X_1]$, thus $e, \rem (f,g) \in \QQ[X_1, \cdots ,X_n]$ since
$lc_{X_1}(g) = 1$.
After substituting $X_1 = X^{d^{n-1}}, \; X_2 = X^{d^{n-2}}, \cdots
,X_n = X^{d^0}$, we get an equality $\overline{f} = \overline{e} \,
\overline{g} + \overline{\rem (f,g)}$ for %nonvanishing identically
polynomials $\overline{f}, \overline{e}, \overline{g}, \overline{\rem
(f,g)} \in \QQ[X]$ that do not vanish identifically and an inequality 
$\deg_X (\overline{g}) = d^{n-1} \deg_{X_1} (g) > \deg_X \overline{\rem (f,g)}$.
Therefore $0 \neq \overline{\rem (f,g)} = \rem
(\overline{f},\overline{g})$ and we conclude that $g$ divides $f$ if and only if
$\overline{g}$ divides $\overline{f}$.
So, we apply the divisibility test for one-variable case exhibited
above to the rational function $\overline{q} = \overline{f} /
\overline{g}$.

Hence the number of arithmetic operations can be bounded by 
$(tn \log d)^{O(1)}$ with the depth $O(\log (tn) \log \log d)$ invoking 
the bounds for one-variable case.

\noindent
{\bf PROPOSITION~2.} \quad
The problem of testing whether a sparse multivariate rational function, given by
a black box, equals to a polynomial, belongs to NC, provided that a bound on the 
degree of some $t$-sparse representation $f/g$ is given such that $lc_{X_1}(g)=1$.

\pagebreak
\noindent
{\bf Acknowledgements.} 

\noindent
The authors thank Mike~Singer for the interesting discussions.

%\clearpage
%\vspace*{2cm}
\begin{thebibliography}{MMM 99}

\bibitem[BCH 86]{12}
Beame,~P.~W., Cook,~S.~A., Hoover,~H.~J.,
{\em LOG Depth Circuit for Division and Related Problems},
SIAM~J.~Comput.~{\bf 15} (1986), pp.~994-1003.

\bibitem[CG 82]{CG}
A.~L. Chistov and D.~Yu. Grigoriev,
{\em Polynomial-time factoring multivariate polynomials over a global field},
Preprint LOMI, E-5-82, Leningrad, 1982.

\bibitem[GK 91]{GK}
D.~Yu Grigoriev and M. Karpinski,
{\em Algorithms on sparse rational interpolation},
Submitted to ISSAC 1991.

\bibitem[GKS 90]{GKS}
D.~Yu. Grigoriev, M. Karpinski, and M. Singer,
{\em Interpolation of sparse rational functions without knowing bounds on exponents},
{\em Proc. 31 FOCS}, IEEE, 1990, pp. 840-846.

\bibitem[KT 88]{KT}
E. Kaltofen, and B. Trager,
{\em Computing with polynomials given by black boxes for their evaluation:
GCD, factorization separation of numerators and denominators},
Proc. 29 FOCS, IEEE, 1988, pp.\ 296-305.

\bibitem[KR 88]{KR88}
Karp, R.~M., and Ramachandran, V.~L.,
{\em A Survey of Parallel Algorithms for Shared-Memory Machines},
Research~Report No.~UCB/CSD88/407, University of California, Berkeley (1988); 
also in Handbook of Theoretical Computer Science~A, North Holland 1990, pp.~870-941.

\bibitem[K 89]{k89}
Karpinski, M.,
{\em Boolean Circuit Complexity of Algebraic Interpolation Problems},
Technical Report~TR-89-027, International Computer Science Institute,
Berkeley (1989); in Proc. CSL~'88 Lecture Notes in Computer Science,
Vol.~385 (1989), pp.~138-147.

\bibitem[LO 77]{LO}
J.~C. Lagarias and A.~M. Odlyzko,
{\em Effective versions of the Chebotarev density theorem},
in Algebraic Number Fields, A. Fr\"ohlich, ed.,
Academic Press, 1977, pp. 409-464.

\bibitem[L 82]{Loo}
R. Loos,
{\em Generalized polynomial remainder sequences},
in Computer Algebra: Symbolic and Algebraic Computation,
B. Buchberger, G.~E. Collins, and R. Loos, eds.,
Springer, 1982, pp. 115-137.

\bibitem[M 82]{Mig}
M. Mignotte,
{\em Some useful bounds}, in
Computer Algebra: Symbolic and Algebraic Computation,
B. Buchberger, G.~E. Collins, and R. Loos, eds.,
Springer, 1982, pp. 259-263.

\bibitem[M 86]{Mul}
K. Mulmuley,
{\em A fast parallel algorithm to compute the rank of a matrix over an arbitrary field},
Proc. 18 STOC, ACM, 1986, pp.~338-339.

\bibitem[P 77a]{Pla}
D. Plaisted,
{\em Sparse complex polynomials and polynomial reducibility},
J. Comput. Syst. Sci., 14, 1977, pp. 210-221.

\bibitem[P 77b]{Pla1}
D. Plaisted,
{\em New NP-hard and NP-complete polynomial and integer divisibility problems},
Proc. 18 FOCS, IEEE, 1977, pp.\ 241-253.

\bibitem[W 72]{Wei}
P.~J. Weinberger,
{\em On Euclidean rings of algebraic integers},
%in Analytic Number Theory,
%H.~G. Diamond, ed., Amer. Math. Soc., 1972, pp.~321-332.
%************************ Korrektur vom 26.2.92 *********************
J. Algorithms, vol.~5 (1984), pp.~180-186. % fuer die beiden letzten Zeilen
%********************************************************************

\end{thebibliography}

\end{document}