%E

% 2000 Math. Subject Class. 14Q15, 14M99, 12Y05, 12E05, 13P05
% ��� 513.6+518.5
% UDK 513.6+518.5

 % Filename:        bnz4mod.tex (LaTeX)
 % Title: A bound for the degree of a system of equations giving the
 % variety of reducible polynomials.
 % Type:                Paper
 % Main Style:        article
 % Input Files:        -
 % Remarks:        A.L.Chistov (author)
 %


\documentclass[a4paper]{article}
\usepackage{amssymb,amscd,amsmath}



\begin{document}

 \title{A Bound for the Degree of a System of Equations Giving the
Variety of Reducible Polynomials}
\author{Alexander L.~Chistov%
 \\[2ex]
St.~Petersburg Department of Steklov Mathematical Institute\\
of the Academy of Sciences of Russia\\
Fontanka 27, St.~Petersburg 191023, Russia,\\
e-mail: alch@pdmi.ras.ru }
\date{}



\maketitle

\begin{abstract}
{\footnotesize
Consider the affine space ${\Bbb A}^N(\overline{K})$
of homogeneous polynomials of degree $d$ in $n+1$ variables with coefficients
from an algebraic closure $\overline{K}$ of a field $K$ of arbitrary
characteristic, so $N={n+d\choose
n}$. We prove that the variety of all reducible polynomials from this affine
space can be given by a system of polynomial equations of
degree less than
$56d^7$  in $N$ variables.
Using this result we formulate an effective version of
the first Bertini theorem for the case of a hypersurface.
\let\thefootnote\relax\footnotetext{Key words and phrases:
absolute irreducibility, lattices, the Bertini theorem.}
\footnotetext{UDK 513.6+518.5}
\footnotetext{2000 Mathematics Subject Classification: 14Q15, 14M99,
12Y05, 12E05, 13P05.}
}
\end{abstract}




%\newpage
\section*{Introduction}

\medskip\noindent Let $K$ be an arbitrary field of characteristic
$\mbox{\rm char}(K)=p$
with an algebraic closure
$\overline{K}$
(in what follows for any field $E$ we denote by $\overline{E}$ an
algebraic closure of $E$).
Let $H$ be the primitive
field of characteristic $p$, i.e., $H={\Bbb Q}$
if $p=0$ or $H={\Bbb F}_p={\Bbb Z}/p{\Bbb Z}$
if $p>0$. We shall assume that $H\subset K$.



It is well known that
the discriminant $\Delta_f$
of a polynomial $f\in K[X_1]$
is a polynomial in the coefficients of $f$ and $\Delta_f\ne 0$ if and only
if
$f$ is square free in $\overline{K}[X_1]$, i.e., it does not have
multiple factors in the ring $\overline{K}[X_1]$ or which is the same
the polynomial $f$ is separable.
In the present paper we consider a polynomial $f=
\sum_{i_1,\ldots , i_n}f_{i_1,\ldots , i_n}X_1^{i_1}\cdot\ldots\cdot
X_n^{i_n}\in K[X_1,\ldots ,X_n]$, $n\geqslant2$,
all $f_{i_1,\ldots , i_n}\in K$,
of degree $\deg_{X_1,\ldots ,X_n}f=d\geqslant 2$ and
construct an analog $A_f$ of the discriminant $\Delta_f$ in the following
sense. The discriminant
$\Delta_f$ of the polynomial in one variable corresponds to the property
``$f$ is separable''.
In the similar way $A_f$ corresponds to the property
``$f$ is absolutely irreducible''.

The element $A_f\in K_{w,v,u}$ where
$K_{w,v,u}$ is a purely transcendental extension of the field $K$,
see Section~3. Here $w,v,u$ are families of transcendental elements over the
field $K$ and the field $K_{w,v,u}$ is generated over $K$ by all the
elements from these
families.
Actually $A_f\in K[w,v,u]$ where $K[w,v,u]$ is the ring of polynomials in
all the elements
from families $w,v,u$.

Further,
$A_f$ corresponds to $f$ canonically: it is a
polynomial in all the coefficients $f_{i_1,\ldots , i_n}$ of $f$.
The degree of this polynomial in $f_{i_1,\ldots , i_n}$ is
bounded from above by
$56d^7$, see a more precise estimate in Section~3. Finally, the main
property:
$A_f\ne 0$ if and only if
the polynomial $f$ is irreducible in the ring $\overline{K}[X_1,\ldots
,X_n]$.

Consider the affine space ${\Bbb A}^N(\overline{K})$, $N={n+d\choose
n}$,
(respectively ${\Bbb A}^{N_1}(\overline{K})$, $N_1={n+d-1\choose n-1}$)
of polynomials (respectively homogeneous polynomials) from
$\overline{K}[X_1,$ $\ldots ,X_n]$
of degree at most $d$ (respectively of degree $d$) in $n$ variables with
coefficients
from an algebraic closure $\overline{K}$ of a field $K$. In this paper we
regard $0$ as a reducible polynomial. Although $0$ belongs to the linear
space of the
homogeneous polynomial of degree $d$ by definition $\deg 0=-1$.
The set ${\cal U}_{d,n}$ of polynomials of degree $d$ from ${\Bbb
A}^N(\overline{K})$
is an
open in the Zariski topology subset of this affine space.
As a consequence of the construction for the element $A_f$ we get the
following result.

\par\medskip\noindent{\bf THEOREM~1}\hspace{0.1em} {\it  (i) Let
$n\geqslant2$ and $d\geqslant 1$ be integers.
The set ${\cal V}_{d,n}$ of all reducible polynomials from
$\overline{K}[X_1,\ldots ,X_n]$ of degree $d$ is closed in ${\cal
U}_{d,n}$ with
respect to Zariski topology and ${\cal V}_{d,n}$ can be given as a
set of all roots from ${\cal U}_{d,n}$ of a
system of polynomial equations with coefficients from a
primitive field $H$ in $N$ variables.
The degree of this system is less than $56d^7$.

(ii) Similarly the set ${\cal W}_{d,n}$ of all reducible
polynomials from the affine space ${\Bbb A}^{N_1}(\overline{K})$
of homogeneous polynomials of degree $d$ is closed
in ${\Bbb A}^{N_1}(\overline{K})$ with
respect to Zariski topology and ${\cal W}_{d,n}$ is a set of all
roots of a system of polynomial equations with coefficients from the
primitive field $H$ in $N_1$ variables.
The degree of this system is less than $56d^7$.
}\par\medskip


More precise statements
for $n\geqslant2$ and $d\geqslant 2$, see in Lemma~11 Section~3. Theorem~1
follows from
Lemma~11 immediately. The proof of Lemma~11 is reduced to the case of two
variables. This reduction is described in Section~3.

The case of two variables: $f\in K[X,T]$
is considered in
Section~2. We suggest here a criterion for absolute irreducibility:
$R_{\rho,f}\ne 0$,
see (15) and Lemma~6. To get this criterion
we describe a formal (or universal) version of the Hensel lemma, introduce
a lattice corresponding to $f$ over the ring of polynomials $\overline{K}[T]$
and consider a minimal vector in it.
We would like to emphasize that Lemma~5 from Section~2
is one of the most important in the paper.

Estimates for a minimal vector in an arbitrary
lattice over $K[T]$ are obtained in Section~1. The idea to consider
lattices for questions related to irreducibility of polynomials is
originated
from \cite{6} but in the present paper we have quite different accents.


\medskip As an application of Theorem~1 we get an efficient version of the
first Bertini theorem for the case of a hypersurface. Let
$f\in K[X_1,\ldots ,X_n,Y]$, $n\geqslant 2$, be a polynomial of degree
$\deg_Yf\geqslant 1$. Assume that $f$ is absolutely irreducible, i.e.,
irreducible in the ring
$\overline{K}[X_1,\ldots ,X_n,Y]$.
Suppose that its discriminant
with respect to the variable $Y$
$$
\Delta=\mbox{\rm Res}_Y\left(f,\frac{\partial f}{\partial
Y}\right)\ne 0,
\eqno (1)
$$
i.e., the polynomial $f$ is separable with respect to $Y$.
Denote by ${\cal K}$ the field of fractions of the ring
$\overline{K}[X_1,\ldots ,X_n,Y]/(f)$.

Let $L_1,L_2\in\overline{K}[X_1,\ldots ,X_n]$ be two linearly independent
over $\overline{K}$ linear forms in $X_1,\ldots ,X_n$.
Denote by $(L_1,L_2)\subset\overline{K}[X_1,\ldots ,X_n,Y]$ the ideal of the
last ring of polynomials generated by $L_1$ and
$L_2$.
Consider the following conditions.
\begin{enumerate} \renewcommand{\labelenumi}{(\alph{enumi})}
\item The polynomial $f\not\in(L_1,L_2)$ and for all
$\mu_1,\mu_2\in\overline{K}$ such that $\mu_1\ne0$ or $\mu_2\ne 0$ the
linear form
$\mu_1 L_1+\mu_2 L_2$
does not divide $\Delta$.
\item The discriminant $\Delta\not\in(L_1,L_2)$.
\end{enumerate}
The discriminant $\Delta$ is the the determinant of the Sylvester ma\-t\-rix
of the polynomials
$f,\partial f/\partial Y\in\overline{K}(X_1,\ldots ,X_n)[Y]$. Hence if
$f\in(L_1,L_2)$ then $\Delta\in(L_1,L_2)$.
Therefore, condition (b) implies (a).

\par\medskip\noindent{\bf THEOREM~2}\hspace{0.1em} {\it  Let
$f\in\overline{K}[X_1,\ldots ,X_n,Y]$, $n\geqslant 2$,
be an irreducible
polynomial such that $\deg_Yf\geqslant 1$,
$\deg_{X_1,\ldots ,X_n,Y}f\leqslant d$ for an integer $d\geqslant 1$ and
(1) is satisfied. Then the following assertions hold.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item Assume that condition (a) or condition (b) holds for
linearly independent linear forms $L_1,L_2$. Let $t^*\in\overline{K}$ and
$L=L_2-t^*L_1$. So the ring $\overline{K}[X_1,\ldots ,X_n]/(L)$ is
isomorphic to the ring of polynomials
in $n-1$ variables.
Then for all
$t^*\in\overline{K}$, except at most $56d^8$, the polynomial
$f\bmod L\in\overline{K}[X_1,\ldots ,X_n]/(L)[Y]$ is irreducible in the last
ring and $\Delta\bmod L\ne0$. This means that the intersection of the
hypersurface ${\cal Z}(f)$
and the hyperplane ${\cal Z}(L)$
in the affine space ${\Bbb A}^{n+1}(\overline{K})$ is transversal and
irreducible over $\overline{K}$.
\item Suppose that ${\cal L}$ is a linear subspace of
the space of all linear forms
in $X_1,\ldots ,X_n$ with coefficients from $\overline{K}$ and the dimension
$\dim{\cal L}\geqslant 3$ (hence also $n\geqslant 3$). Then there are
$L_1,L_2\in{\cal L}$ satisfying condition (b) (and therefore also (a)).
More precisely, let
$L'_1,L'_2,L'_3\in{\cal L}$ be three linearly
independent linear forms and $I\subset\overline{K}$ be a finite set
such that  the number of elements $\#I=1+\deg_{X_1,\ldots ,X_n}\Delta$. Then
there are $\alpha_1,\alpha_2\in I$ such that
$L_1=L'_1-\alpha_1 L'_3$, $L_2=L'_2-\alpha_2 L'_3$ satisfy condition (b).
\end{enumerate}
}\par\medskip


Let us describe how to prove this theorem.
Let $L_1,L_2,L_3,\ldots , L_n$ be a basis of the space of all
linear forms in $X_1,\ldots ,X_n$. Put $t=L_2/L_1$.
Then $f\not\in(L_1,L_2)$ if and only if the polynomial $f$ is irreducible in
the ring
$\overline{K}(t)[L_1,L_3\ldots , L_n,Y]$. This follows from
Lemma~12 with
$Y,L_3,\ldots , L_n,L_1,L_2$ in place of $X_1,\ldots ,X_{n+1}$
(in the sequel we refer in the Introduction also to Lemma~13, Lemma~14
and Corollary~3; one should do the similar replacement of variables there).

Further, assume that $f$ is irreducible in
the ring
$\overline{K}(t)[L_1,L_3,\ldots , L_n,Y]$. Then $f$ is an irreducible
element of
the ring
$\overline{K(t)}[L_1,L_3,\ldots , L_n,Y]$ if and only if the field
$\overline{K}(t)$ is algebraically
closed in the field ${\cal K}$, see \cite{7}, Lemma~4. We give a simple
direct independent
proof of this fact in Lemma~13.

In Lemma~14 we prove that
{\it if condition (a) or condition (b) is satisfied then
the field $\overline{K}(t)$ is algebraically closed in ${\cal K}$.}
In spite of the simplicity of this assertion probably this result is new.

Finally now assertion (i) follows from Corollary~3 of Lemma~14 immediately.
Let us prove assertion (ii). Performing a nondegenerate linear
transformation of
variables $X_1,\ldots ,X_n$ one can suppose without loss of generality
that $L'_1=X_{n-1}$, $L'_2=X_n$, $L'_3=X_1$. Then $\Delta\not\in(L_1,L_2)$
if and only if
$$
\Delta(X_1,\ldots , X_{n-2},\alpha_1 X_1,\alpha_2 X_1)\ne
0.
$$
Thus the required $\alpha_1,\alpha_2\in I$ exist. Theorem~2 is proved
(modulo Lemmas~12---14 and Corollary~3).

\par\medskip\noindent{\bf REMARK~1}\hspace{0.1em} {\it  {\em According to
the  construction described
Sections~1--3
the number of equations
in the polynomial system from
Theorem~1 (i) (respectively (ii))
is bounded from above by $d^{(d+n)^{O(1)}}$.

One can obtain a system with a smaller number of equations as follows.
Let us replace in the formulation of Theorem~1 the field $H$ by an
infinite extension $H_1$
of $H$. We assume that $H_1\subset\overline{K}$.
Then there is a modified system giving ${\cal V}_{d,n}$ (respectively
${\cal W}_{d,n}$)
similar to the one from
the statement (i) (respectively (ii)) of Theorem~1
 and consisting of
$N+1-\dim{\cal V}_{d,n}$ (respectively $N_1+1-\dim{\cal W}_{d,n}$)
polynomial equations with coefficients from $H_1$. To get the last system
it is sufficient to take linear combinations with coefficients from $H_1$ of
the initial equations from Theorem~1 (i) (respectively (ii)) in general
position. Still these linear combinations are given not efficiently.
It is
difficult to construct them.

On the other hand, using \cite{5} one can construct explicitly the
elements  $A_{i,f}\in K$,
$1\leqslant i\leqslant N_2=d^{O(n)}$ satisfying the following properties.
Every
$$
A_{i,f}=A_f|_{w=w^*_i,v=v^*_i,u=u^*_i}
$$
is obtained by the substitution
in $A_f$ some special values $w^*_i,v^*_i,u^*_i$ of families $w,v,u$
such that the elements of $w^*_i,v^*_i,u^*_i$ are from the field $H_1$.
The element $A_f\ne0$ if and only if  $A_{i,f}\ne0$ for some
$1\leqslant i\leqslant N_2$. If the field $K$ is finitely generated
over $H$ (of fixed transcendency degree) and given similarly to the ground
field from the Introduction of \cite{2}
then
for a polynomial $f$ one can compute all $A_{i,f}$ within the time polynomial
in the size of the polynomial
$f$ and $d^n$. We shall not prove and use this result in the present paper.}
}\par\medskip



\par\medskip\noindent{\bf REMARK~2}\hspace{0.1em} {\it  {\em It would be
interesting to improve the upper bound $56d^8$ from
assertion (i) of Theorem~2 (or the similar more precise upper bound from
Corollary~3) for an arbitrary characteristic of the
ground field. It is possible if $\mbox{\rm char}(K)=0$.
In this case one can replace $56d^8$ by $4d^4$. It can be deduced from
the Irreducibility Criterion given in the Introduction of \cite{4}.

Note also that in zero--characteristic one can not improve
the estimate $56d^7$ from Theorem~1 in the similar way.}
}\par\medskip


The present paper is important.
In future we hope to consider from the algorithmic point of view the
effective version of the
first Bertini theorem in general case and in arbitrary characteristic of the
ground field. Still there we are able to obtain only
less strong results than the ones
from \cite{4} in zero--characteristic.
As an application the main result of \cite{3} will be
improved for the case of a finite ground field.




\section{Estimates for a minimal vector in a lattice }\label{s1}

Let $K$ be an arbitrary field.
Let $A=(a_{i,j})_{1\leqslant i\leqslant n_1,\,1\leqslant j\leqslant n_2}$ be
an $(n_1\times n_2)$-ma\-t\-rix
with the elements $a_{i,j}$ from the ring $B=K[\,T\,]$ where $T$ is a
transcendental
element
over the field $K$. Let $a_i=(a_{i,1},\ldots , a_{i,n_2})\in B^{n_2}$,
$1\leqslant i\leqslant n_1$,
be the rows of the ma\-t\-rix $A$.
Denote by
$M$ the $B$-submodule of $B^{n_2}$
generated by all
the rows $a_i$ of the ma\-t\-rix $A$ (in other words $M$ is a lattice in
$B^{n_2}$).

For an element $b\in B$ set $|b|=\deg_Tb$ (we assume that $\deg_T0=-1$).
So $|a_{i,j}|=\deg_T
a_{i,j}$. Put $|A|=
\max_{1\leqslant i\leqslant n_1,\,1\leqslant j\leqslant n_2}|a_{i,j}|$
and for an arbitrary vector  $y=(y_1,\ldots , y_{n_2})\in B^{n_2}$  set
$|y|=\max_{1\leqslant j\leqslant n_2}|y_i|$.
We shall suppose in what follows in this section that $|A|=D$. Let
$r=\mbox{\rm rank}(A)$ be the rank of the ma\-t\-rix $A$.

The minimal vector of $M$ is an arbitrary nonzero element $q\in M$
such that $|q|=\min\{|y|\, :\, 0\ne y\in M\}$, i.e.,  $|q|$ is
minimal possible.

\par\medskip\noindent{\bf LEMMA~1}\hspace{0.1em} {\it  Let $q$ be an
arbitrary minimal vector of the lattice $M$. Then
$|q|\leqslant D$ and
one can represent
$$
q=\sum_{1\leqslant i\leqslant n_1}\lambda_i a_i,
\eqno (2)
$$
where $\lambda_i\in B$ and $|\lambda_i|\leqslant (2r+1)D$
for all $1\leqslant
i\leqslant n_1$.
}\par\medskip

\noindent{\bf PROOF}\quad Obviously $|q|\leqslant|A|=D$.
Permuting the columns of the ma\-t\-rix $A$ we
shall suppose without loss of
generality that
the first $r$ columns of the ma\-t\-rix $A$ are linearly independent over
the field $K(T)$.
Let us represent $A=(A_1,A_2)$ where the
ma\-t\-rix $A_1$ has $r$
columns and  $A_2$ has $n_2-r$ columns.
So $\mbox{\rm rank}(A_1)=r$. There is a ma\-t\-rix $A_3$ of the
size $n_1\times(n_1-r)$ such that
$\mbox{\rm rank}(A_1,A_3)=n_1$ and each column of the ma\-t\-rix
$A_3$ contains only one
nonzero entry and
this entry is equal to $1$ (if $r=n_1$ then $A_3$ has $0$ columns, i.e., it
is empty).
Hence $(A_1,A_3)=A_4$ is a nondegenerate square ma\-t\-rix, its
determinant
$\mbox{\rm det}(A_4)\ne 0$ and $|\mbox{\rm
det}(A_4)|\leqslant rD$.

The ring $B$ is Euclidean. Hence as it is well known there is a ma\-t\-rix
$Q\in {\rm GL}_{n_1}(B)$ (the ma\-t\-rix $Q$ is a product of the elementary
ma\-t\-ri\-ces over the ring $B$
corresponding to the some elementary transformations of the rows of the
ma\-t\-rix
$A_4$) such that $QA_4=A'=(a'_{i,j})_{1\leqslant i,j\leqslant n_1}$
is an upper triangular  ma\-t\-rix (this means that $a'_{i,j}=0$ for all
$1\leqslant j<i\leqslant n_1$). Moreover,
applying (if it is necessary)
elementary transformations of rows
to the obtained upper triangular  ma\-t\-rix
we shall suppose without loss of generality in the sequel that
$|a'_{i,j}|<|a'_{j,j}|$ for all
$1\leqslant i<j\leqslant n_1$.

Since $Q\in{\rm GL}_{n_1}(B)$
the determinant $\mbox{\rm det}(A')=\alpha\mbox{\rm
det}(A_4)$ for an element $0\ne\alpha\in K$. Hence
$$
\sum_{1\leqslant j\leqslant n_1}
\max_{1\leqslant i\leqslant n_1}\{|a'_{i,j}|\}=\sum_{1\leqslant
j\leqslant n_1}|a'_{j,j}|
=|\mbox{\rm det}(A_4)|\leqslant rD.
\eqno (3)
$$
This implies of course $|A'|\leqslant |\mbox{\rm det}(A_4)|$.
We have $Q=A_4^{-1} A'$. Put $\Delta_1=\mbox{\rm det}(A_4)$. Now
$$
|\Delta_1 Q|\leqslant|\Delta_1 A_4^{-1}|+|A'|\leqslant rD+|\Delta_1|.
$$
(if $n_2=n_1=r$ then one can replace here $rD$ by $(n_1-1)D$ but in
the next section
we have $n_1>n_2$; so we don't take into account this minor improvement).
Hence $|Q|\leqslant rD$.

Put
$QA=A''=(a''_{i,j})_{1\leqslant i\leqslant n_1,\,1\leqslant j\leqslant n_2}$.
Let $a''_1,\ldots ,
a''_{n_1}$
be the rows
of the ma\-t\-rix $A''$ and $A''_1$ be the ma\-t\-rix consisting of the
first $r$ rows of the ma\-t\-rix
$A''$. Now according to our construction $a''_1,\ldots ,
a''_r$ is the basis
of the mo\-du\-le $M$ (it is a free mo\-du\-le) over the ring $B$,
$a''_i=0$ for all $r+1\leqslant i\leqslant n_1$ and
$a''_{i,j}=a'_{i,j}$ for all $1\leqslant i,j\leqslant r$.

Therefore there are $\mu_i\in B$, $1\leqslant i\leqslant r$, such
that   $q=\sum_{1\leqslant i\leqslant r}\mu_i a''_i$. Henceforth
$$
q_j=\sum_{1\leqslant i\leqslant r}\mu_i a'_{i,j},\quad 1\leqslant
j\leqslant r.
$$
Notice that $\mbox{\rm det}((a'_{i,j})_{1\leqslant i,j\leqslant
r})\ne0$.
Therefore, using Cramer's rule and  (3) we get
$$
|\mu_i|\leqslant|q|+\sum_{1\leqslant j\leqslant
r}\max_{1\leqslant i\leqslant r}\{|a'_{i,j}|\}\leqslant
D+rD=(r+1)D.
$$

Let $Q_1$ be the ma\-t\-rix consisting of the first $r$
rows of the ma\-t\-rix $Q$. Then
$Q_1A=A''_1$ and
$(\mu_1,\ldots,\mu_r)Q_1A=q$. Put $(\lambda_1,\ldots
,\lambda_{n_1})=(\mu_1,\ldots,\mu_r)Q_1$. Now (2)
holds and for all $1\leqslant i\leqslant n_1$
$$
|\lambda_i|\leqslant\max_{1\leqslant i\leqslant
r}|\mu_i|+|Q_1|\leqslant(2r+1)D.
$$
The lemma is proved.

\medskip Under conditions of Lemma~1 let us represent
$\lambda_i=\sum_{0\leqslant \gamma\leqslant(2r+1)D}
\lambda_{i,\gamma}\,T^\gamma$,
$1\leqslant i\leqslant n_1$,
and $a_{i,j}=\sum_{0\leqslant \gamma\leqslant(2r+1)D}
a_{i,j,\gamma}\,T^\gamma$, $1\leqslant
i\leqslant n_1$, $1\leqslant j\leqslant n_2$,
where all the coefficients $\lambda_{i,\gamma}\in K$, $a_{i,j,\gamma}\in K$
(if $\gamma>D$ then $a_{i,j,\gamma}=0$ for all $i,j$).

Let $Z_{i,\nu}$, $1\leqslant i\leqslant n_1$, $0\leqslant
\nu\leqslant(2r+1)D$,
be new variables. Let $-1\leqslant\mu_0\leqslant D$ be an integer.
Consider the homogeneous linear system with coefficients from the field $K$
with respect to the variables $Z_{i,\nu}$
$$
\sum_{0\leqslant \nu\leqslant \mu}\sum_{1\leqslant i\leqslant
n_1}Z_{i,\nu}\,a_{i,j,\mu-\nu}=0,
\quad\mu_0<\mu\leqslant(2r+2)D,\,1\leqslant j\leqslant n_2.
\eqno (4)
$$


Let  $C_{A,-1}$ be the ma\-t\-rix of system (4) with $\mu_0=-1$. It has
$\nu_1=((2r+2)D+1)n_2$
rows and $\nu_2=((2r+1)+1)Dn_1$ columns. The rows (respectively columns) of
the
ma\-t\-rix $C_{A,-1}$
correspond to different pairs
$(\mu,j)$ (respectively $(i,\nu)$), see  (4).
We order pairs $(\mu,j)$ lexicographically: $(\mu_1,j_1)>(\mu_2,j_2)$ if and
only if
$\mu_1>\mu_2$ or $\mu_1=\mu_2$ and $j_1>j_2$. Similarly we order pairs
$(i,\nu)$.
Next, we identify the linear ordered set of pairs $(\mu,j)$ (respectively
$(i,\nu)$) and
$\{1,\ldots ,\nu_1\}$ (respectively $\{1,\ldots ,\nu_2\}$). Now the
ma\-t\-rix  $C_{A,-1}$
has the form $C_{A,-1}=(c_{i,j})_{1\leqslant i\leqslant\nu_1,\,1\leqslant
j\leqslant\nu_2}$ where elements
$c_{i,j}$ are uniquely defined by  (4) and these identifications of
linear ordered sets.
Let $c_1,\ldots , c_{\nu_1}$
be all the rows of the ma\-t\-rix $C_{A,-1}$.

Let $-1\leqslant\rho\leqslant D$ be an arbitrary integer. Then the
ma\-t\-rix $C_{A,\rho}$ of system (4) with $\mu_0=\rho$ is identified
with a submatrix
of $C_{A,-1}$.
Namely, $C_{A,\rho}$ consists of $((2r+2)D-\rho)n_2$ rows of ma\-t\-rix
$C_{A,-1}$.
These are rows $c_{\nu_3},\ldots , c_{\nu_1}$ where $\nu_3=
1+\nu_1-((2r+2)D-\rho)n_2=(\rho+1)n_2+1$.

Set $\nu_0=\max\{\nu_1,\nu_2\}$.
Let $u=\{u_{i,j}\}_{1\leqslant i\leqslant\nu_1+\nu_2,\,1\leqslant
j\leqslant\nu_0}$
be a family of
algebraically independent over the field  $K$ elements.
Denote by $K_u=K(u)$ the extension of the field
$K$ by all the elements from the family $u$. Hence the transcendency degree
of $K_u$ over $K$
is  $(\nu_1+\nu_2)\nu_0$.
Put
\begin{eqnarray*}
&&h_{i,j}=
\sum_{\nu_3\leqslant i_1\leqslant\nu_1,\,1\leqslant
j_1\leqslant\nu_2}u_{i,i_1}
u_{j+\nu_1,j_1}c_{i_1,j_1},\quad \nu_3\leqslant i\leqslant
\nu_1,\,1\leqslant j\leqslant \nu_2,\\
&&h'_{i,j}=
\sum_{1\leqslant i_1\leqslant\nu_1,\,1\leqslant j_1\leqslant\nu_2}u_{i,i_1}
u_{j+\nu_1,j_1}c_{i_1,j_1}, \quad 1\leqslant i\leqslant \nu_1,\,1\leqslant
j\leqslant \nu_2.
\end{eqnarray*}
So all $h_{i,j},h'_{i,j}\in K_u$. In other words the ma\-t\-rix
$(h'_{i,j})_{i,j}$ is obtained
from $C_{A,-1}$ in two steps. At first one takes $\nu_1$ generic linear
combinations
$c'_1,\ldots , c'_{\nu_1}$ of the rows of the ma\-t\-rix $C_{A,-1}$ and get
the
ma\-t\-rix $C'$ with the rows $c'_1,\ldots , c'_{\nu_1}$. After that one
takes $\nu_2$
generic linear combinations $c''_1,\ldots , c''_{\nu_2}$ of the columns of
the ma\-t\-rix $C'$
and get the ma\-t\-rix $C''=(h'_{i,j})_{i,j}$. In the similar way one obtains
the ma\-t\-rix $(h_{i,j})_{i,j}$ starting from $C_{A,\rho}$.


Let $0\leqslant \gamma\leqslant\min\{\nu_1-\nu_3+1,\nu_2\}=r_1$ be an
integer.
Put
$$
\Delta_{A,\rho,\gamma}=\mbox{\rm det}((h_{i,j})_{1\leqslant
i,j\leqslant
\gamma}),\quad\Delta'_{A,\gamma}=\mbox{\rm
det}((h'_{i,j})_{1\leqslant
i,j\leqslant
\gamma}).
$$
Set $\Delta'_{A,r_1+1}=0$.
We have $\mbox{\rm rank}(C_{A,-1})=\mbox{\rm
rank}(C_{A,\rho})=\gamma$ if and only if
$\Delta_{A,\rho,\gamma}\ne0$ and  $\Delta'_{A,\gamma+1}=0$.


\par\medskip\noindent{\bf LEMMA~2}\hspace{0.1em} {\it  Under conditions of
Lemma~1 let $q$ be a minimal vector
of the lattice $M$. Then $|q|>\rho$ if and only if every solution of system
(4) with $\mu_0=\rho$ is a solution of system (4) with $\mu_0=-1$,
i.e., if and only if there is $1\leqslant \gamma\leqslant r_1$ such that
$\Delta_{A,\rho,\gamma}\ne 0$ and
$\Delta'_{A,\gamma+1}=0$.

Assume additionally that $\mbox{\rm rank}(C_{A,-1})=r_0$. Then
$|q|>\rho$ if and only if
$\Delta_{A,\rho,r_0}\ne 0$.
}\par\medskip

\noindent{\bf PROOF}\quad This follows from the previous considerations and
Lemma~1. The lemma is proved.


\section{An irreducibility criterion: the case of two variables}\label{s2}

Let $K$, $T$, $B=K[\,T\,]$ be the same as in the previous section.
Let $X$ be a
variable
and $f\in K[\,X,T]$ be a polynomial such that the degree $0\leqslant\deg_Tf
\leqslant\rho$ for an integer $\rho\geqslant 1$. Further, let
$\deg_Xf=\deg_Xf(X,0)=m\geqslant 2$ and the leading coefficient $\mbox{\rm
lc}_Xf\in K$ (the last condition means that
$\deg_X(f-f(X,0))<\deg_Xf$).
Put
$$
\Delta_f=\mbox{\rm Res}_X(f(X,0),f'(X,0))\in K
\eqno (5)
$$
to be the discriminant of the polynomial $f(X,0)$.
We shall assume that $\Delta_f\ne 0$, i.e.,
the polynomial
$f(X,0)$ is has $m$ pairwise distinct roots in
the algebraic closure $\overline{K}$. We shall suppose that all these
conditions are satisfied throughout this section.


Set $n_2=m$.
Put the ring $B_1=\overline{K}[\,T\,]$, $B_2=B_1[Z]$ where $Z$ is a variable.
We shall identify the set of polynomials $g\in\overline{K}[\,X,T]$
(respectively $g\in\overline{K}[\,Z,X,T]$) of degree
$\deg_Xg<m$ with $B_1^{m}$ (respectively $B_2^{m}$). Under this
identification
$$
g=g_0+g_1X+\ldots + g_{m-1}X^{m-1}\mapsto(g_0,g_1,\ldots , g_{m-1}),
\eqno (6)
$$
here all $g_i\in B_1$ (respectively all $g_i\in B_2$).
We shall use the notation $|...|$ for polynomials, elements of $B_1^{m}$,
$B_2^{m}$, ma\-t\-ri\-ces and so on,
see the previous section.
So at present $|g|=\deg_Tg$ for any polynomial $g$.
We shall apply the results of the previous section for the ring $B_1$ in
place
of $B$.

Set $f_0=f(X,0)$. Let us represent $f_0=f_0(Z)+(X-Z)g_0$ for a polynomial
$g_0\in K[Z,X]$.
Notice that $g_0(Z,Z)=f'_0(Z)=\frac{d\, f_0}{d Z}$. Write $\delta=f'_0(Z)$.



Let us represent $f=\sum_{i\geqslant 0}f_i\,T^i$ where all $f_i\in K[X]$
(hence if $i>|f|$ then
$f_i=0$).
Set $\overline{f}_i=\delta^{2i-2}f_i$ for all $i\geqslant 1$.
Put $\overline{z}_0=Z$.

For all $i\geqslant 1$ let us define  recursively polynomials
$\overline{g}_{i,j}\in K[Z]$, $0\leqslant
j\leqslant m-2$, and $\overline{z}_i\in K[Z]$.
Put $\overline{g}_i=\sum_{0\leqslant
j\leqslant m-2}\overline{g}_{i,j}X^j\in K[Z,X]$.

Assume that
$\overline{g}_j$ and $\overline{z}_j$
are defined for all $0\leqslant j<i$ for some $i\geqslant 1$. Then
$$
(X-Z)\overline{g}_i -g_0\overline{z}_i
=\delta\Bigl(\overline{f}_i+\sum_{1\leqslant
w\leqslant i-1}\overline{g}_w\overline{z}_{i-w}\Bigr).
\eqno (7)
$$
Now to find all $\overline{g}_{i,j}\in K(Z)$, $0\leqslant
j\leqslant m-2$ and $-\overline{z}_i\in K(Z)$ one should solve
using (7) a linear
system with coefficients from
$K(Z)$ by Cramer's rule. The coefficients ma\-t\-rix of this system is the
Sylvester ma\-t\-rix of the polynomials
$X-Z$ and $g_0$. Its determinant is $\pm\delta$.
All the free terms of this system are divisible by $\delta$. Hence
actually all $\overline{g}_{i,j}\in K[Z]$ and $\overline{z}_i\in K[Z]$.
The recursive step for the definition of $\overline{g}_i$ and
$\overline{z}_i$ is described.



\par\medskip\noindent{\bf LEMMA~3}\hspace{0.1em} {\it  (i) For all
$i\geqslant 1$ the degrees
$$
\deg_Z\overline{g}_i\leqslant(2i-1)(2m-2),\quad
\deg_Z\overline{z}_i\leqslant(2i-1)(2m-2).
$$

(ii) Let us extend the field $K$ till the field $K(t)$ where $t$ is a new
variable. Assume that $f\in
K[t,X,T]$. Now $g_0\in K[t,Z,X]$ and using (7)
in the similar way as it was above
one can prove that $\overline{g}_i\in K[t,Z,X]$ ,
$\overline{z}_i\in K[t,Z]$ for all $i\geqslant 1$.
Assume additionally that $\deg_tf\leqslant s$ for an
integer $s$. Then for all $i\geqslant 1$ the degrees
$$
\deg_t\overline{g}_i\leqslant(3i-1)s,\quad
\deg_t\overline{z}_i\leqslant(3i-1)s.
$$
}\par\medskip

\noindent{\bf PROOF}\quad (i) The degrees with respect to $Z$ of all the
minors of the Sylvester ma\-t\-rix of
the polynomials $g_0,X-Z$ are bounded from above by $2m-3$. We have
$\deg_Z\overline{f}_i\leqslant(2i-2)(m-1)$.
Now the required assertion follows by the induction on $i$ using Cramer's
rule.

(ii) The degrees with respect to $t$ of all the
minors of the Sylvester ma\-t\-rix of
the polynomials $g_0,X-Z$ are bounded from above by $s$. We have
$\deg_t\overline{f}_i\leqslant(2i-1)s$.
Now the required assertion follows by the induction on $i$ using Cramer's
rule.  The lemma is proved.


\medskip Consider the separable $K$-al\-ge\-b\-ra
$K'=K[Z]/(f_0(Z))$.
Put $z=Z\bmod f_0(Z)\in K'$. Then $f_0=(X-z)g_0(z,X)$ where
$g_0(z,X)\in K'[X]$.
Notice that $\delta(z)=g_0(z,z)$ is an invertible element of $K'$ since the
polynomial $f_0$ is separable.
Let $K'[[\,T\,]]$
be the ring of formal power series in $T$
over the al\-ge\-b\-ra $K'$.
One can apply Hensel's lifting to the decomposition $f(X,0)=(X-z)g_0(z,X)$
and get
$$
f=\Bigl(X-\sum_{i\geqslant 0}z_i\,T^i\Bigr)
\Bigl(g_0(z,X)+\sum_{i\geqslant1}g_i\,T^i\Bigr)
\eqno (8)
$$
in the ring $K'[[\,T\,]][X]$. Here $z_0=z$, all $z_i\in K'$,
the polynomials $g_i\in K'[X]$, $\deg_Xg_i\leqslant m-2$, for all
$i\geqslant1$.

\par\medskip\noindent{\bf LEMMA~4}\hspace{0.1em} {\it  For all $i\geqslant 1$
$$
z_i=\frac{\overline{z}_i(z)}{\delta(z)^{2i-1}},\quad
g_i=\frac{\overline{g}_i(z,X)}{\delta(z)^{2i-1}}.
\eqno (9)
$$
}\par\medskip

\noindent{\bf PROOF}\quad Equality  (8) implies that
for all $i\geqslant 1$
the polynomials $g_i$ and the elements $z_i$
satisfy the
recursive relation
$$
(X-z)g_i -g_0(z,X) z_i
=f_i+\sum_{1\leqslant
w\leqslant i-1}g_w z_{i-w}.
\eqno (10)
$$
Now  (9) is obtained by the
induction on $i$ using  (10) and (7). The lemma is proved.

\par\medskip\noindent{\bf REMARK~3}\hspace{0.1em} {\it  {\em Similarly to
(8) and (9) one can obtain the
decomposition
$$
f-f_0(Z)=\biggl(X-Z-\sum_{i\geqslant 1}\frac{\overline{z}_i}{\delta^{2i-1}}
\,T^i\biggr)
\biggl(g_0+\sum_{i\geqslant1}\frac{\overline{g}_i}{\delta^{2i-1}}
\,T^i\biggr)
$$
in the ring $K(Z)[[T]][X]$. This is a formal (or universal) version of
the Hensel lemma.}
}\par\medskip


\medskip Set $D=(2m-1)\rho+1$ and
\setcounter{equation}{10} \begin{eqnarray}
&&\eta=\delta^{2D-3}X-\delta^{2D-3}\Bigl(Z+\sum_{1\leqslant i\leqslant
D-1}\frac{\overline{z}_i\,T^i}{\delta^{2i-1}}\Bigr)=\label{11} \\
&&\delta^{2D-3}X-\Bigl(\delta^{2D-3}Z+\sum_{1\leqslant i\leqslant
D-1}\overline{z}_i\delta^{2(D-1-i)}T^i\Bigr)\in K[\,Z,X,T],\nonumber
\end{eqnarray}


Let $x\in\overline{K}$ be a root of the polynomial
$f(X,0)$, i.e., $f(x,0)=0$. Put
$$
\begin{array}{lll}
a_i=\eta(x,X,T)X^{i-1}, & \widetilde{a}_i=
\eta X^{i-1},&1\leqslant i\leqslant m-1, \\
a_i=T^DX^{i-m}, & \widetilde{a}_i=T^DX^{i-m},&
m\leqslant i\leqslant 2m-1.
\end{array}
\eqno (12)
$$
Hence all $a_i\in B_1^{m}$, $\widetilde{a}_i\in B_2^{m}$ under
identification (6).
Put $n_1=2m-1$.
Let $A$ (respectively $\widetilde{A}$) be the ma\-t\-rix with the rows
$a_1,\ldots,a_{n_1}$ (respectively
$\widetilde{a}_1,\ldots,\widetilde{a}_{n_1}$).
Hence $D=|A|=|\widetilde{A}|$.
Let us apply the construction of Section~1 to the ma\-t\-ri\-ces $A$ and
$\widetilde{A}$ (replacing there
the ground field $K$ by $K[\,x\,]$ and $K(Z)$ respectively).
Now the following objects corresponding to $A$ and
$\widetilde{A}$ are
defined, see Section~1: the
integers $\nu_i$, $0\leqslant i\leqslant 3$,
$r_1$, the
ma\-t\-ri\-ces $C_{A,-1}$, $C_{A,\rho}$, $C_{\widetilde{A},-1}$,
$C_{\widetilde{A},\rho}$,
the determinants $\Delta_{A,\rho,i},\Delta'_{A,i+1}\in K_u[\,x\,]$,
$\Delta_{\widetilde{A},\rho,i},
\Delta'_{\widetilde{A},i+1}\in K_u[Z]$ for all $1\leqslant i\leqslant r_1$.
Notice that $r=\mbox{\rm rank}(A)=\mbox{\rm
rank}(\widetilde{A})=m$ by (12).

\par\medskip\noindent{\bf LEMMA~5}\hspace{0.1em} {\it  Let $f$ be a
polynomial satisfying all the conditions
formulated
at the beginning of the section and the ma\-t\-ri\-ces
$C_{A,-1}$, $C_{\widetilde{A},-1}$ correspond to $f$.
Then the ranks of ma\-t\-ri\-ces
$$
\mbox{\rm rank}(C_{A,-1})=
\mbox{\rm rank}(C_{\widetilde{A},-1})=((2m+2)D+1)m-D.
$$
Put $r_0=((2m+2)D+1)m-D$ (recall that
$D=(2m-1)\rho+1$).
}\par\medskip

\noindent{\bf PROOF}\quad We shall prove this assertion for the ma\-t\-rix
$C_{A,-1}$.
The proof for $C_{\widetilde{A},-1}$ is similar and left to the reader.
It is sufficient to show that $r_0$ is the maximal number of
linearly independent equations of system  (4) from Section~1 with
$\mu_0=-1$.
By (12) the last system has the form
$$
\left\{
\begin{array}{ll}
Z_{j+m-1,\mu-D}+&\\
\sum_{0\leqslant \nu\leqslant \mu}\sum_{1\leqslant
i\leqslant m-1}
Z_{i,\nu}a_{i,j,\mu-\nu}=0, &D\leqslant \mu\leqslant(2r+2)D,\,1\leqslant
j\leqslant m, \\
Z_{j-1,\mu}\delta^{2D-3}(x)=0, &0\leqslant \mu<D,\, j=m, \\
Z_{j-1,\mu}\delta^{2D-3}(x)+&\\
\sum_{0\leqslant \nu\leqslant
\mu}Z_{j,\nu}a_{j,j,\mu-\nu}=0, &
0\leqslant \mu<D,\,2\leqslant j\leqslant m-1,\\
\sum_{0\leqslant \nu\leqslant \mu}Z_{j,\nu}a_{j,j,\mu-\nu}=0,&
0\leqslant \mu<D,\, j=1.
\end{array}
\right.
\eqno (13)
$$
Let us delete from system (13) $D$ equations
$$
\sum_{0\leqslant\nu\leqslant\mu}Z_{1,\nu}a_{1,1,\mu-\nu}=0,\quad
0\leqslant\mu<D.
\eqno (14)
$$
and denote by (*) the new obtained system. Then system (*) has
the trapezoidal form (after a permutation of equations) with
the elements $Z_{j+m-1,\mu-D}$, $D\leqslant\mu\leqslant(2r+2)D$, $1\leqslant
j\leqslant m$; $Z_{j+1,\mu}\delta^{2D-3}(x)$, $0\leqslant\mu<D$, $2\leqslant
j\leqslant m-1$,
on the slanting side of the trapezoid.
Hence all the equations of system (*) are
linearly independent.
The number of equation of system (*) is $r_0$. Finally  (*) implies that
$Z_{j,\mu}=0$ for all $1\leqslant j\leqslant m-1$, $0\leqslant\mu<D$. Hence
equations  (14) are
linear combinations of the ones from system (*). The lemma is proved.

\medskip Let $f_1$ and $f_2$ be two polynomials in the variable $Z$.
Denote by $\mbox{\rm Res}_Z(f_1,f_2)$  the resultant
with respect to $Z$
of the polynomials
$f_1$ and $f_2$. This resultant is defined usually as the determinant of the
Sylvester ma\-t\-rix for
nonzero polynomials $f_1$, $f_2$
(in the case $\deg_Z f_1=\deg_Z f_2=0$ one obtains
the empty Sylvester ma\-t\-rix, its determinant is $1$ in the natural way).
If $f_1=0$ or $f_2=0$ then by definition
$\mbox{\rm Res}_Z(f_1,f_2)=0$.

Put
$$
R_{\rho,f}=
\mbox{\rm Res}_Z(\Delta_{\widetilde{A},\rho,r_0},f(Z,0))\in K_u.
\eqno (15)
$$
Thus $R_{\rho,f}$ depends on $\rho$ and the coefficients of the polynomial
$f\in K[X,T]$.
Denote by $M$ the lattice in $B_1^{m}$ generated by the rows of the
ma\-t\-rix $A$. The minimal vector of the lattice $M$ is defined as in
Section~1 (now with the ring $B_1$ in place of $B$).

\par\medskip\noindent{\bf LEMMA~6}\hspace{0.1em} {\it  Let $f\in K[X,T]$ be
a polynomial satisfying all the conditions
formulated at the beginning of the Section. Then the following
assertions hold true.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item Let $q$ be an arbitrary minimal vector of $M$. Then
$|q|>\rho$ if and only if the
polynomial $f$ is irreducible in the ring $\overline{K}[\,X,T]$.
\item The element $R_{\rho,f}\ne 0$ if and only
if the
polynomial $f$ is irreducible in the ring $\overline{K}[\,X,T]$.
\end{enumerate}
}\par\medskip

\noindent{\bf PROOF}\quad (i) Suppose that $f$ is reducible in
$\overline{K}[\,X,T]$. Then there is a divisor $g\in\overline{K}[\,X,T]$ of
$f$
such that the degree $1\leqslant\deg_Xg<m$
and $X-x$ divides $g(X,0)$. The definition of the lattice
$M$ and
the uniqueness of the the decomposition into the irreducibles in the ring
$K[x]((T))[X]$ (here $K((T))$ is the field of fractions of the ring $K[[T]]$)
imply that $g\in M$ (under
identification (6)).
We have $|q|\leqslant|g|\leqslant|f|\leqslant\rho$.

Conversely, suppose that $|q|\leqslant\rho$.
Consider the resultant
$$
R=\mbox{\rm Res}_X(q,f)\in K[\,x\,][\,T\,]
$$
of the
polynomials $q$ and $f$ with respect to $X$.
As it is well known there are polynomials $p_1,p_2\in K[\,x\,][\,X,T]$ such
that $R=p_1q+p_2f$. Since $q\in M$ the linear polynomial
$\eta(x,X,T)\bmod T^D$ divides
$q\bmod T^D$ in the ring $B_1/(T^D)[X]$.
By (8), (9) and (11) also $\eta(x,X,T)\bmod T^D$ divides
$f\bmod T^D$ in the ring $B_1/(T^D)[X]$.
Therefore, $\eta(x,X,T)\bmod T^D$ divides $R\bmod T^D$
in the last ring. But $\deg_XR\leqslant0$. Consequently $R\bmod T^D=0$ and
hence
$|R|\geqslant D$ or $R=0$.

On the other hand, the conditions $|f|\leqslant\rho$, $|q|\leqslant\rho$
imply
that $|z|\leqslant\rho$ for each element $z$ of the Sylvester ma\-t\-rix
of the resultant
$R$. The size of this ma\-t\-rix is bounded from above by $2m-1$.
Therefore, $|R|\leqslant(2m-1)\rho=D-1$.
Thus $R=0$. This means
that $\mbox{\rm G\,C\,D\,}(f,q)\ne 1$ in the ring
$K[\,x\,][\,X,T]$.
Hence $f$ is a reducible polynomial
in $\overline{K}[\,X,T]$ and (i) is proved.

(ii) Recall that $\Delta_{A,\rho,r_0}\in K_u[\,x\,]$,
$\Delta_{\widetilde{A},\rho,r_0}\in K_u[Z]$
and according to our definitions
$\Delta_{\widetilde{A},\rho,r_0}(x)=\Delta_{A,\rho,r_0}$.
By Lemma~2  (with the ring $B_1$ in place of $B$)
and Lemma~5 we have $\Delta_{A,\rho,r_0}\ne 0$ if
and only if
$|q|>\rho$ for a minimal vector $q$ of $M$. Hence by (i)
$\Delta_{A,\rho,r_0}=\Delta_{\widetilde{A},\rho,r_0}(x)\ne 0$
if and only if the polynomial $f$ is irreducible in the ring
$\overline{K}[\,X,T]$.
But $x$ is an arbitrary root of the polynomial $f_0(Z)$. Hence
$f$ is irreducible in the ring $\overline{K}[\,X,T]$ if and
only if the polynomials
$\Delta_{\widetilde{A},\rho,r_0}$ and $f_0(Z)$
are relatively prime in the ring
$K_u[Z]$, i.e.,
if and only if their resultant $R_{\rho,f}\ne 0$. Assertion (ii) and all the
lemma
are proved.

\par\medskip\noindent{\bf LEMMA~7}\hspace{0.1em} {\it  Let $f\in K[X,T]$ be
a polynomial satisfying all the conditions
formulated at the beginning of the Section.
Then the following assertions hold.

(i) The degree
\begin{eqnarray*}
&&\deg_Z\Delta_{\widetilde{A},\rho,r_0}\leqslant
2 (m-1) (4 m \rho -2 \rho -1)\times \\
&&\left(4 m^3 \rho +2 m^2 \rho +2 m^2-4 m \rho +3 m+\rho -1\right).
\end{eqnarray*}

(ii) Under conditions of assertion (ii) of Lemma~3 the degrees
\setcounter{equation}{15} \begin{eqnarray}
&&\deg_t\Delta_{\widetilde{A},\rho,r_0}\leqslant
s (6 m \rho -3 \rho -1)\times\label{16}\\
&&\left(4 m^3 \rho +2 m^2 \rho +2 m^2-4 m \rho +3 m+\rho
-1\right),\nonumber\\
&&\deg_tR_{\rho,f}\leqslant s \left(14 m^2 \rho -15 m \rho -3 m+4 \rho
+2\right)\times\label{17}\\
&&\left(4 m^3 \rho +2 m^2 \rho +2 m^2-4 m \rho +3
   m+\rho -1\right). \nonumber
\end{eqnarray}
Hence if $2\leqslant\deg_Xf=m=d$, $1\leqslant\deg_Tf\leqslant\rho
=d$,
$\deg_tf\leqslant s=d$ then
$$
\deg_tR_{\rho,f}\leqslant d \left(14 d^3-15 d^2+d+2\right)
\left(4 d^4+2 d^3-2 d^2+4 d-1\right).
\eqno (18)
$$
}\par\medskip

\noindent{\bf PROOF}\quad We shall suppose without loss of generality that
the conditions of assertion (ii)
of Lemma~3 hold. From Lemma~3 and (11) we get
$$
\deg_Z\eta\leqslant(2D-3)(2m-2),\quad
\deg_t\eta\leqslant(3D-4)s
\eqno (19)
$$

Let $C_{\widetilde{A},\rho}=(\widetilde{c}_{i,j})_{i,j}$
be the ma\-t\-rix corresponding to
$\widetilde{A}$.
According to (12) and (19) we have
also $\deg_Z\widetilde{c}_{i,j}\leqslant(2D-3)(2m-2)$,
$\deg_t\widetilde{c}_{i,j}\leqslant(3D-4)s$
for all $i,j$. Hence
$\deg_Z\Delta_{\widetilde{A},\rho,r_0}\leqslant
r_0(2D-3)(2m-2)$,
$\deg_t\Delta_{\widetilde{A},\rho}\leqslant r_0(3D-4)s$
(one can check direcly that $r_0$ is no more than
the number of the rows $((2r+2)D-\rho)m$ of the ma\-t\-rix
$C_{\widetilde{A},\rho}$ but we even do not use this).
This implies (i) and (16).

Finally considering the Sylvester ma\-t\-rix for the resultant of the
polynomials $\Delta_{\widetilde{A},\rho,r_0}$ and
$f_0(Z)$ we get
\begin{eqnarray*}
&&\deg_tR_{\rho,f}\leqslant
\deg_Z\Delta_{\widetilde{A},\rho,r_0}\cdot\deg_tf_0+\deg_Zf_0\cdot
\deg_t\Delta_{\widetilde{A},\rho,r_0}\leqslant \\
&&r_0(2D-3)(2m-2)s+m r_0(3D-4)s.
\end{eqnarray*}
This implies (17).


The right part of (17) is a monotone increasing function of $m$ and $\rho$
for $m\geqslant 2$, $\rho\geqslant 1$. Now substituting $m=d$ and $\rho=d$
in (17)
we get (18). The lemma is proved.

\par\medskip\noindent{\bf COROLLARY~1}\hspace{0.1em} {\it  Let $f$ be a
polynomial satisfying the conditions
of Lemma~7 and the ones from
assertion (ii) of Lemma~3.
Suppose that the polynomial $f\in K[t,X,T]$ is
irreducible in the ring
$\overline{K(t)}[X,T]$. Then there are at most
\setcounter{equation}{19} \begin{eqnarray}
&&\deg_t(\Delta_fR_{\rho,f})\leqslant s (2 m-1)+
s \left(14 m^2 \rho -15 m \rho -3 m+4 \rho
+2\right)\!\times\label{20}\\
&&\left(4 m^3 \rho +2 m^2 \rho +2 m^2-4 m \rho +3
   m+\rho -1\right) \nonumber
\end{eqnarray}
values $t^*\in\overline{K}$ of $t$ such that the polynomial $f(t^*,X,T)$ is
reducible in the ring
$\overline{K}[X,T]$ or $\Delta_f|_{t=t^*}=0$. Note that $\Delta_f|_{t=t^*}=0$
if and only if $\deg_Xf_0>\deg_Xf(t^*,X,0)$ or
the polynomial $f(t^*,X,0)$ is not separable.
}\par\medskip

\noindent{\bf PROOF}\quad Recall that $f_0=f(t,X,0)$.
There are at most $\deg_t\Delta_f\leqslant(2m-1)s$
values $t^*\in\overline{K}$ of $t$ such that $\Delta_f|_{t=t^*}=0$.
In what follows we shall assume that $\deg_Xf_0=\deg_Xf(t^*,X,0)$ and
$f(t^*,X,0)$ is separable. The
resultant $R_{\rho,f}\in
K[t]$ and according to
our definitions $R_{\rho,f}(t^*)=R_{\rho,f(t^*,X,T)}$. Now (20) follows
from Lemma~6 (ii) and (17). The corollary is proved.




\section{An irreducibility criterion: general case}\label{s3}

Let $K$ be an arbitrary field and
$f\in K[X_1,\ldots ,X_n]$, $n\geqslant 2$,
be a polynomial such that $\deg_{X_1,\ldots
,X_n}f=d\geqslant 2$. We shall suppose that these conditions hold throughout
this section

Let $v=\{v_i\}_{2\leqslant i\leqslant n}$ and
$w=\{w_{i,j}\}_{1\leqslant i\leqslant n,\,0\leqslant
j\leqslant n}$ be two families of transcendental elements over $K$
such that the field $K_{w,v,u}$
generated over
$K$ by all the elements from families $w,v,u$ has the maximal possible
transcendency degree $n-1+n(n+1)+
\nu_0(\nu_1+\nu_2)$, see Section~1 (the integers $\nu_i$, $0\leqslant
i\leqslant 2$,
will be specified in the definition of $A_f$ below).
Write $K_v=K(v_2,\ldots ,v_n)$,
$\overline{K}_v=\overline{K}(v_2,\ldots ,v_n)$. Denote by $K_w$
(respectively $K_{w,v}$) the
extension of the field $K$ by all the elements from the family $w$
(respectively families $w$ and $v$).
We shall denote by $K[w]$ (respectively $K[w,v]$;  $K[w,v,u]$) the ring of
polynomials in
all the transcendental elements from the family $w$ (respectively families
$w,v$;
$w,v,u$) with coefficients from $K$. We shall use the similar notation with
other
constant fields in place of $K$ and other families of transcendental
elements.

Set
$f_v=f(X,v_2T,\ldots ,v_nT)\in K_v[\,X,T]$.

\par\medskip\noindent{\bf LEMMA~8}\hspace{0.1em} {\it  Assume that the degree
$\deg_{X_1}f=\deg_{X_1}f(X_1,0,$ $\ldots ,0)=d$
and the polynomial
$f(X_1,0,\ldots , 0)$ has $d$ pairwise distinct roots in
the field $\overline{K}$.
The following assertions are equivalent.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item The polynomial $f$ is irreducible in the ring $\overline{K}[X_1,\ldots
,X_n]$.
\item The polynomial $f_v$ is irreducible in the ring
$\overline{K}_v[\,X,T]$.
\item The polynomial $f_v$ is irreducible in the ring
$\overline{K_v}[\,X,T]$ where $\overline{K_v}$ is the algebraic
closure of the field
$K_v$.
\end{enumerate}
}\par\medskip

\noindent{\bf PROOF}\quad Obviously (iii) implies (ii). Assume that
$f_v$ is reducible in the ring $\overline{K_v}[\,X,T]$ and a polynomial
$h\in\overline{K_v}[\,X,T]$ divides $f_v$,  $\deg_Xh<\deg_Xf_v$.
Then $h(X,0)$ divides $f_v(X,0)$. Hence multiplying $h$ by a nonzero
constant from $\overline{K_v}$
we can suppose without
loss of generality that $h(X,0)\in\overline{K}[X]$.
Now by the
uniqueness of the Hensel's lifting  $h\in \overline{K}_v[[\,T\,]][X]$.
Therefore $h\in \overline{K}_v[[\,T\,]][X]\cap\overline{K_v}[\,X,T]=
\overline{K}_v[\,X,T]$ where the last intersection
is taken in $\overline{K_v}[[\,T\,]][X]$. Thus,
$f_v$ is reducible in the ring $\overline{K}_v[\,X,T]$. Hence (ii)
implies
(iii).

Assume that $f_v$ is reducible
in the ring $\overline{K}_v[\,X,T]$. Then the polynomial  $f_v(X,1)$ is
reducible in the
ring $\overline{K}_v[X]$. By the Gauss lemma the polynomial
$f(X,v_2,\ldots
,v_n)$ is
reducible in the ring $\overline{K}[X,v_2,\ldots ,v_n]$. Hence (i) implies
(ii).

Conversely, if $f$ is reducible in the ring $\overline{K}[X_1,\ldots ,X_n]$
then $f_v$ is
reducible in the ring
$\overline{K}_v[\,X,T]$. Thus, (ii) implies (i). The lemma is proved.


\medskip Put the linear polynomials $W_i=w_{i,0}+\sum_{1\leqslant i\leqslant
n}w_{i,j}X_j$,
$1\leqslant i\leqslant n$.
Set
\begin{eqnarray*}
&&f_w=f(W_1,W_2,\ldots , W_n)\in K[w][X_1,\ldots
,X_n], \\
&&f_{w,v}=f_w(X,v_2T,\ldots , v_nT)\in K[w,v][\,X,T].
\end{eqnarray*}
Notice that $\deg_{X_1}f_w=\deg_{X_1,\ldots ,X_n}f_w=d$,
$\deg_Xf_{w,v}=\deg_Tf_{w,v}=\deg_{X,T}f_{w,v}$ $=d$.

\par\medskip\noindent{\bf LEMMA~9}\hspace{0.1em} {\it  The following
assertions are equivalent.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item The polynomial $f$ does not have multiple factors in
$\overline{K}[X_1,\ldots ,X_n]$.
\item The polynomial $f_w(X_1,0,\ldots , 0)$ does not have multiple
factors in
$\overline{K_w}[X_1]$.
\item The polynomial $f_{w,v}(X,0)$ does not have multiple
factors in
$\overline{K_{w,v}}[X]$.
\end{enumerate}
}\par\medskip

\noindent{\bf PROOF}\quad Assume that (i) is satisfied.
Then by the B\'ezout theorem the generic line
intersects the
hypersurface ${\cal Z}(f)$ (of all the roots of the polynomial $f$ in the
affine space ${\Bbb A}^n(\overline{K})$) in $d$ points. Hence the
polynomial
$f(w_{0,1}+w_{1,1}X_1,\ldots , w_{n,1}+w_{n,1}X_1)$ has $d$ pairwise
distinct roots in
$\overline{K_w}$. This implies the equivalence of (i) and (ii). The
equivalence of (ii) and
(iii) follows from the equality
$f_{w,v}(X,0)=f_w(X,0,\ldots , 0)$. The lemma is proved.

\medskip Put
$$
A_f=\Delta_{f_{w,v}}R_{d,f_{w,v}}\in K[w,v,u],
$$
see  (5), (15), now $\rho=d$ and the ground field is equal to
$K_{w,v}$ in place of
$K$.

\par\medskip\noindent{\bf LEMMA~10}\hspace{0.1em} {\it  Let $f\in
K[X_1,\ldots ,X_n]$,  $\deg_{X_1,\ldots ,X_n}f=d\geqslant
2$, $n\geqslant 2$. Then
the polynomial $f$ is
irreducible in the ring $\overline{K}[X_1,\ldots ,X_n]$ if and only if the
element $A_f\ne 0$.
}\par\medskip

\noindent{\bf PROOF}\quad Suppose that $f\in\overline{K}[X_1,\ldots,X_n]$ is
irreducible. Then the polynomial $f_{w,v}(X,0)$ does not have multiple
factors in
$\overline{K_{w,v}}[X]$ by Lemma~9. Therefore, $\Delta_{f_{w,v}}\ne 0$.
Further, the polynomial $f$ is
irreducible in the ring
$\overline{K_w}[X_1,\ldots ,X_n]$.
Hence also $f_w$ is
irreducible in the last ring.
By Lemma~8 with the ground field $K_w$ in
place of $K$
the polynomial $f_{w,v}$ is irreducible in the ring
$\overline{K_{w,v}}[X,T]$. Now by
Lemma~6 (ii) with the ground field $K_{w,v}$ in place of $K$ we have
$R_{d,f_{w,v}}\ne 0$.
Thus $A_f\ne 0$.

Conversely, let $A_f\ne 0$. Then $\Delta_{f_{w,v}}\ne 0$ and the polynomial
$f_{w,v}(X,0)$ does not have
multiple factors in
$\overline{K_{w,v}}[X]$. We have $R_{d,f_{w,v}}\ne 0$.
Hence by Lemma~6 (ii)
with the ground field $K_{w,v}$ in place of $K$
the polynomial $f_{w,v}\in\overline{K_{w,v}}[\,X,T]$ is irreducible.
Further by Lemma~8 with the ground field $K_w$ in
place of $K$ the polynomial $f_w\in\overline{K_w}[X_1,\ldots ,X_n]$ is
irreducible.
Therefore, the polynomial $f$ is irreducible in the ring
$\overline{K}[X_1,\ldots ,X_n]$.  The lemma is proved.

\medskip Put
$I_{d,n}=\{(i_1,\ldots , i_n)\in{\Bbb Z}^n\, :\, i_1+\ldots +
i_n\leqslant d;\,i_j\geqslant 0\,\forall j\}$ to be the set
of multiindices, and $J_{d,n}=I_{d,n}\setminus I_{d-1,n}$, $d\geqslant2$,
$n\geqslant 2$. Notice that the number of elements $\#I_{d,n}={n+d\choose
n}=N$, $\#J_{d,n}={n+d-1\choose n-1}=N_1$.
Now let $\Phi$ (respectively $\Psi$) be a generic polynomial
(respectively generic homogeneous polynomial) of degree $d$ in $n$
variables for a given characteristic $p$ of the ground field. This means that
$$
\Phi=\sum_{(i_1,\ldots , i_n)\in I_{d,n}}\varphi_{i_1,\ldots ,
i_n}X_1^{i_1}\cdot\ldots\cdot X_n^{i_n},\quad
\Psi=\sum_{(i_1,\ldots , i_n)\in J_{d,n}}\psi_{i_1,\ldots ,
i_n}X_1^{i_1}\cdot\ldots\cdot X_n^{i_n},
$$
where the family of coefficients $\varphi=\{\varphi_{i_1,\ldots,
i_n}\}_{(i_1,\ldots, i_n)\in I_{d,n}}$ (respectively
$\psi=\{\psi_{i_1,\ldots,
i_n}\}_{(i_1,\ldots, i_n)\in J_{d,n}}$) consists of ${n+d\choose n}$
(respectively ${n+d-1\choose n-1}$) algebraically independent over the field
$H$ elements (recall that $H$ is the primitive subfield of $K$).

We shall identify the set of all polynomial (respectively
the linear space of all homogeneous
polynomials) of degree $d$ from $\overline{K}[X_1,\ldots ,X_n]$
with an open in the Zariski topology subset ${\cal
U}_{d,n}\subset{\Bbb A}^{N}(\overline{K})$ (respectively with the
affine space ${\Bbb A}^{N_1}(\overline{K})$) where
${\Bbb A}^{N}(\overline{K})$ has the coordinate functions from the
family $\varphi$
(respectively ${\Bbb A}^{N_1}(\overline{K})$ has the coordinate functions
from the family $\psi$).

Recall that $H[\varphi]$ and $H[\psi]$ are the rings of polynomials with
coefficients from $H$
in all the variables from the families  $\varphi$ and $\psi$ respectively.
The polynomials $\Phi\in H[\varphi][X_1,\ldots ,X_n]$, $\Psi\in
H[\psi][X_1,\ldots ,X_n]$. The elements
$A_{\Phi}\in H[\varphi,w,v,u]$, $A_{\Psi}\in H[\psi,w,v,u]$.
One can uniquely represent
$$
A_{\Phi}=\sum_{\mu\in M_\Phi}A_{\Phi,\mu}\,\mu,\quad
A_{\Psi}=\sum_{\mu\in M_\Psi}A_{\Psi,\mu}\,\mu,
$$
where all $A_{\Phi,\mu}\in H[\varphi]$ (respectively$ A_{\Psi,\mu}\in
H[\psi]$)
are nonzero,
$\mu$ runs over
a set $M_\Phi$ (respectively $M_\Psi$) of pairwise distinct monomials with
the coefficient $1$
in the elements from
the families $w,v,u$.


Put $I=I_{d,n}$ (respectively $I=J_{d,n}$).
Now let
$$
f=\sum_{(i_1,\ldots , i_n)\in I}\lambda_{i_1,\ldots , i_n}
X_1^{i_1}\cdot\ldots\cdot X_n^{i_n}
$$
be an arbitrary polynomial
(respectively homogeneous polynomial) of degree $d$
with all coefficients $\lambda_{i_1,\ldots , i_n}\in K$.
Denote by $\lambda=\{\lambda_{i_1,\ldots , i_n}\}_{(i_1,\ldots , i_n)\in
I_{d,n}}$ (respectively
$\lambda'=\{\lambda_{i_1,\ldots , i_n}\}_{(i_1,\ldots , i_n)\in
J_{d,n}}$) the family of coefficients of this polynomial.
Then according to the given definitions
(we leave to check the details to the reader) for the case $I=I_{d,n}$
$$
A_f=A_\Phi|_{\varphi=\lambda}=A_\Phi|_{\varphi_{i_1,\ldots ,
i_n}=\lambda_{i_1,\ldots ,
i_n}\,\forall(i_1,\ldots , i_n)\in I_{d,n}},
\eqno (21)
$$
i.e., $A_f$ is obtained by the substitution in $A_\Phi$ the coefficients
$\lambda_{i_1,\ldots ,
i_n}$ in place of the transcendental elements $\varphi_{i_1,\ldots ,
i_n}$ for all multiindices $(i_1,\ldots , i_n)\in I_{d,n}$.
Similarly for the case of a nonzero homogeneous polynomial $f$ when
$I=J_{d,n}$
$$
A_f=A_\Psi|_{\psi=\lambda'}=A_\Psi|_{\psi_{i_1,\ldots ,
i_n}=\lambda_{i_1,\ldots ,
i_n}\,\forall(i_1,\ldots , i_n)\in J_{d,n}}.
\eqno (22)
$$
We have also $A_\Psi|_{\psi_{i_1,\ldots,
i_n}=0\,\forall(i_1,\ldots, i_n)\in J_{d,n}}=0$.



For an arbitrary polynomial $z\in H[\varphi,w,v,u]$,
(respectively $z\in H[\psi,w,v,u]$)
denote by
$\deg_\varphi z$ (respectively $\deg_\psi z$) the degree of $z$ with respect
to all the elements from the
family $\varphi$ (respectively $\psi$).


\par\medskip\noindent{\bf LEMMA~11}\hspace{0.1em} {\it  (i) Let
$n\geqslant2$ and $d\geqslant2$ be integers.
Then the set ${\cal V}_{d,n}$ of
all reducible polynomials from
$\overline{K}[X_1,\ldots ,X_n]$ of degree $d$
is identified with the intersection ${\cal U}_{d,n}\cap{\cal
Z}(\{A_{\Phi,\mu}\}_{\mu\in M_\Phi})$ where ${\cal
Z}(\{A_{\Phi,\mu}\}_{\mu\in M_\Phi})$ is the set of all common zeroes
in ${\Bbb
A}^{N}(\overline{K})$ of the
polynomials from the family $\{A_{\Phi,\mu}\}_{\mu\in M_\Phi}$.

Similarly the set ${\cal W}_{d,n}$ of all reducible
polynomials
from the affine space ${\Bbb A}^{N_1}(\overline{K})$ of homogeneous
polynomials of degree $d$
is identified with the closed with respect to Zariski topology subset
${\cal Z}(\{A_{\Psi,\mu}\}_{\mu\in M_\Psi})\subset{\Bbb
A}^{N_1}(\overline{K})$.

(ii) The degrees  $\deg_\varphi A_\Phi$, $\deg_\psi A_\Psi$; $\deg_\varphi
A_{\Phi,\mu}$,
$\mu\in M_\Phi$;
 $\deg_\psi A_{\Psi,\mu}$, $\mu\in M_\Psi$, are bounded
from above by
$$
56 d^7-32 d^6-54 d^5+96 d^4-72 d^3+15 d^2+9 d-3<56d^7.
\eqno (23)
$$
}\par\medskip

\noindent{\bf PROOF}\quad (i) This follows immediately from the given
definitions, Lemma~10
and  (21),  (22).

(ii) It is sufficient to prove the assertions related
to $\deg_\varphi A_\Phi$ and
$\deg_\psi A_\Psi$. Let us prove it for $\deg_\varphi A_\Phi$.
Let $t$ be a new variable.
We shall suppose without loss of generality that the ground field $K\supset
H[t,\varphi]$.
Consider the polynomial
$\widetilde{\Phi}=t\Phi\in H[t,\varphi]$. Then
the definitions imply immediately $\deg_t A_{\widetilde{\Phi}}=\deg_\varphi
A_\Phi$ and
$\deg_tA_{\widetilde{\Phi}}=
\deg_t(\Delta_{\widetilde{\Phi}_{w,v}}
R_{d,\widetilde{\Phi}_{w,v}})$ (at present in the definition of
$R_{d,\widetilde{\Phi}_{w,v}}$
the ground field is equal to $K_{w,v,u}(t)$ in place of $K$, see
(15)).
We can apply Corollary~1 to the polynomial $\widetilde{\Phi}_{w,v}$ over
the ground field $K_{w,v,u}(t)$.
Denote by $c(s,m,\rho)$ the right part of (20). Now $s=1$,
$m=\rho=d$.
Hence
$$
\deg_t(\Delta_{\widetilde{\Phi}_{w,v}}
R_{d,\widetilde{\Phi}_{w,v}})\leqslant c(1,d,d).
$$
This implies
(23) for $\deg_\varphi A_\Phi$. The proof of the estimate for
$\deg_\psi A_\Psi$ is similar.
The lemma is proved.

\par\medskip\noindent{\bf COROLLARY~2}\hspace{0.1em} {\it  Let $f\in
K[t,X_1,\ldots ,X_n]$, $n\geqslant 2$, be a polynomial
irreducible in the ring $\overline{K(t)}[X_1,\ldots ,X_n]$
with $\deg_tf\leqslant d$, $\deg_{X_1,\ldots ,X_n}f=d$ for an
integer $d\geqslant 2$.
Then there are at most
$$
\deg_tA_f\leqslant 56 d^8-32 d^7-54 d^6+96 d^5-72 d^4+15 d^3+9 d^2-3 d<56d^8
$$
values $t^*\in\overline{K}$ of $t$ such that the polynomial $f(t^*,X_1,\ldots
,X_n)$ is
reducible in the ring
$\overline{K}[X_1,\ldots ,X_n]$ or $\Delta_f|_{t=t^*}=0$.
Notice also
that $\Delta_f|_{t=t^*}=0$ if and only if $\deg_{X_1}f(t^*,X_1,\ldots
,X_n)<\deg_{X_1}f$ or
$\Delta_{f(t^*,X_1,\ldots ,X_n)}=0$.
}\par\medskip

\noindent{\bf PROOF}\quad We have
$A_f\in K_{w,v,u}[\,t\,]$ and if $A_f(t^*)\ne 0$ then
$A_f(t^*)=A_{f(t^*,X_1,\ldots ,X_n)}$.
By (21) the degree
$\deg_t A_f\leqslant d\deg_\varphi A_\Phi$. Now the required assertion
follows from Lemma~10 and  (23) immediately. The corollary is proved.


\section{Effective version of the first Bertini theorem: the case of a
hypersurface over a field of arbitrary characteristic}\label{s4}

The aim of this section is to prepare everything for the proof of
Theorem~2, see the Introduction.
Let $K$ be an arbitrary field and $f\in K[X_1,\ldots ,X_{n+1}]$, $n\geqslant
2$,
be a polynomial irreducible in the ring
$\overline{K}[X_1,\ldots ,X_{n+1}]$ and such that $\deg_{X_1}f>0$,
$\deg_{X_1,\ldots ,X_{n+1}}f=d$ and the discriminant of $f$
with respect to $X_1$
$$
\Delta=\mbox{\rm Res}_{X_1}\left(f,\,\frac{\partial f}{\partial
X_1}\right)\ne 0.
\eqno (24)
$$
We shall assume that all these conditions
are satisfied
throughout this section.


Put $t=X_{n+1}/X_n$. Then  $f=f(X_1,\ldots ,X_n,X_nt)\in K[t,X_1,\ldots
,X_n]$. Denote by $(X_n,X_{n+1})\subset K[X_1,\ldots ,X_{n+1}]$
the ideal generated by
$X_n,X_{n+1}$.

\par\medskip\noindent{\bf LEMMA~12}\hspace{0.1em} {\it  The polynomial  $f$
is irreducible in the ring
$\overline{K}(t)[X_1,\ldots
,X_n]$ if and only if $f\not\in(X_n,X_{n+1})$.
}\par\medskip

\noindent{\bf PROOF}\quad This follows from the Gauss lemma (we leave the
details to the reader). The lemma is proved.

\medskip The assertion of the following lemma follows from Lemma~4 \cite{7}.
Still at present it is useful to give
a simple direct independent proof of this fact
for the completeness (in the similar
way one can prove Lemma~4 \cite{7} in full generality).

\par\medskip\noindent{\bf LEMMA~13}\hspace{0.1em} {\it  Let $f$ be a
polynomial satisfying all the conditions
formulated
at the beginning of the section.
Suppose that the polynomial $f$ is irreducible in the ring
$\overline{K}(t)[X_1,$ $\ldots,X_n]$. Then the following conditions are
equivalent.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item The polynomial $f$ is reducible in the ring
$\overline{K(t)}[X_1,\ldots ,X_n]$.
\item The field $\overline{K}(t)$ is not
algebraically closed in the
field of fractions ${\cal K}$ of the ring $K[X_1,\ldots ,X_{n+1}]/(f)$,
i.e.,
there is an element
$\theta\in {\cal K}$ algebraic over $\overline{K}(t)$ and such that
$\theta\not\in
\overline{K}(t)$.
\end{enumerate}
More than that, if (i) and (ii) are satisfied then the element $\theta$ is
separable over the field
$\overline{K}(t)$.
}\par\medskip

\noindent{\bf PROOF}\quad Suppose that (i) is satisfied.
Let $f_1\in\overline{K(t)}[X_1,\ldots ,X_n]$ be a factor of  $f$ irreducible
in the last ring
such that some coefficient of $f_1$ is equal to $1$. Now for all $x_2,\ldots
, x_n\in\overline{K}(t)$
if $\Delta(x_2,\ldots , x_n,tx_n)\ne 0$ then the polynomial
$f(X_1,x_2,\ldots ,
x_n,tx_n)\in\overline{K}(t)[X_1]$ is separable,
$f_1(X_1,x_2,\ldots , x_n)$ divides  $f(X_1,x_2,\ldots , x_n,tx_n)$ and,
therefore, the coefficients of the polynomial
$f_1(X_1,x_2,$ $\ldots , x_n)$ are separable over the field
$\overline{K}(t)$.
From here using
the interpolation by the elements $x_2,\ldots , x_n$ we get that the
coefficients of the polynomial
$f_1$ from $\overline{K(t)}$ are separable over $\overline{K}(t)$.

This implies that
there is a finite Galois extension $E\supset \overline{K}(t)$
with the Galois group $\mbox{\rm
Gal}(E/\overline{K}(t))=G$
such that each absolutely irreducible factor of the polynomial $f$ is equal
to $\lambda\,\sigma(f_1)$
where $0\ne\lambda\in\overline{K(t)}$ and $\sigma\in G$. Hence the
decomposition of $f$ into the
absolute irreducible factors has the form $f=\lambda_0 f_1\cdot\ldots\cdot
f_\nu$, $\nu>1$, where
$f_1,\ldots, f_\nu\in E[X_1,\ldots ,X_n]$ are all pairwise distinct
conjugated to the polynomial $f_1$ over the field $\overline{K}(t)$ and
$0\ne\lambda_0\in\overline{K}(t)$.

Now
$E\otimes_{\overline{K}(t)}{\cal K}$ is a separable
$E$-al\-ge\-b\-ra and  $E\otimes_{\overline{K}(t)}{\cal
K}\simeq\prod_{1\leqslant
i\leqslant\nu}{\cal K}_i$ where
${\cal K}_i$ is a field of fractions of the ring $E[X_1,\ldots
,X_n]/(f_i)$. Hence
$E\otimes_{\overline{K}(t)}{\cal K}\supset\prod_{1\leqslant i\leqslant
\nu}E=E'$ and
$E'$ is a
finite dimensional $E$-al\-ge\-b\-ra which is
invariant with respect to the action of the Galois group $G$.

On the other hand, let us show (again it is known of course)
that every $E$-vector subspace $V\subset
E\otimes_{\overline{K}(t)}{\cal K}$ which is
invariant with respect to the action of the Galois group $G$
has the form  $V=E\otimes_{\overline{K}(t)}V^G$ where
$V^G\subset{\cal K}$
is a $\overline{K}(t)$-vector space
of the invariant with respect to the action of $G$ elements of $V$.
Indeed, suppose contrary.
Let $e_i$, $i\in I_1\cup I_2$, be a $\overline{K}(t)$-basis of  ${\cal
K}$ such that
$e_i$, $i\in I_2$
is a $\overline{K}(t)$-basis of  $V^G$. Since
$V\setminus(E\otimes_{\overline{K}(t)}V^G)=\widetilde{V}\ne\emptyset$
there is
a vector
$$
q=\sum_{1\leqslant j\leqslant\mu}q_je_{i_j}\in \widetilde{V}
\eqno (25)
$$
such that all $i_1,\ldots ,
i_\mu\in I_1$, all $0\ne q_j\in E$ and the integer $\mu$ is minimal possible.
We have $\mu\geqslant2$ and there is $1<\alpha\leqslant\mu$
such that $q_\alpha/q_1\not\in \overline{K}(t)$ since
otherwise we get a contradiction:  $q_1^{-1} q\in V^G$ is a nontrivial
linear combination of the elements $e_i$, $i\in I_1$, with coefficients from
$\overline{K}(t)$.

Therefore, there is $\sigma\in G$ such
that
$\sigma(q_\alpha/q_1)\ne q_\alpha/q_1$.
Put $\widetilde{q}=q_1^{-1} q-\sigma(q_1^{-1} q)$.
Then $0\ne\widetilde{q}\in\widetilde{V}$
and $\widetilde{q}$ has representation (25) with
$\mu'$ in place of $\mu$ such that $\mu'<\mu$. This is a contradiction.
Henceforth $V=E\otimes_{\overline{K}(t)}V^G$

Thus $E_1=(E')^G\subset{\cal K}$ is a field and the degree of the
extension
$[E_1:\overline{K}(t)]=\nu>1$. One can choose $\theta\in
E_1\setminus\overline{K}(t)$. Hence condition (ii) is fulfilled.


Conversely, suppose that condition (ii) holds true. Let $X_1\bmod f\in
\overline{K}[X_1,\ldots ,$ $X_{n+1}]/(f)\subset{\cal K}$.
Let
$E_1\supset\overline{K}(t)$ be an algebraic extension
of the field $\overline{K}(t)$ such that $E_1\subset{\cal K}$ and
$E_1\ne\overline{K}(t)$. Hence $\overline{K}(t)(X_2,\ldots, X_n)\ne
E_1(X_2,\ldots, X_n)\subset{\cal K}$ and the extention
$E_1\supset\overline{K}(t)$ is separable. Therefore the degree of the
minimal polynomial
of the element
$X_1\bmod f\in{\cal K}$ over the field
$E_1(X_2,\ldots, X_n)$
is less than $\deg_{X_1}f$. Henceforth using the Gauss lemma we get that
there is a polynomial
$f_1\in E_1[X_1,\ldots, X_n]$ such that $\deg_{X_1}f_1<\deg_{X_1}f$ and $f_1$
divides $f$
in the ring $E_1[X_1,\ldots, X_n]$. Thus condition (i) is fulfilled.
The lemma is proved.


\par\medskip\noindent{\bf LEMMA~14}\hspace{0.1em} {\it  Suppose that the
polynomial $f$ is irreducible in the ring
$\overline{K}(t)[X_1,$ $\ldots,X_n]$ but $f$ is reducible in the ring
$\overline{K(t)}[X_1,\ldots ,X_n]$. Then there are elements
$\mu_1,\mu_2\in\overline{K}$ such that
$(\mu_1,\mu_2)\ne(0,0)$ and $\mu_1 X_n+\mu_2 X_{n+1}$ divides the
discriminant $\Delta$.
}\par\medskip

\noindent{\bf PROOF}\quad By Lemma~2 there is a finite separable algebraic
extension of fields $E_1\supset\overline{K}(t)$ such that
the degree $[E_1:\overline{K}(t)]>1$ and $E_1$ is contained in the field
${\cal K}$. The extention of the fields
$E_1\supset\overline{K}(t)$ corresponds to the morphism
$C\rightarrow{\Bbb P}^1(\overline{K})$ of the
smooth projective curves
defined over the field $\overline{K}$. The degree of this morphism is
$\nu>1$.
The Hurwitz formula for the genus of the curve $C$ implies
that there is
a discrete valuation $v\, :\,\overline{K}(t)\rightarrow{\Bbb
Z}\cup\{+\infty\}$ of the field $\overline{K}(t)$ over
$\overline{K}$ (or which is the same $v$ is zero on
$\overline{K}\setminus\{0\}$) and a discrete valuation
$v_1$ which is an extension of $v$ to the field $E_1$ such that $v_1$ is
ramified over $v$, i.e., there is an element $\xi\in E_1$ with
$v_1(\xi)=1/e$ for an integer $e>1$.
The valuation $v$ is defined by a uniformizing element
$$
\pi=\frac{\mu_1 X_n+\mu_2 X_{n+1}}{\mu_3 X_n+\mu_4 X_{n+1}}
\eqno (26)
$$
such that $\mu_1,\mu_2,\mu_3,\mu_4\in\overline{K}$,
$\mu_1\mu_4-\mu_3\mu_2\ne0$ and $v(\pi)=1$.

The elements  $X_2,\ldots ,X_{n-1}$, $\mu_3 X_n+\mu_4 X_{n+1}$ are
algebraically independent over the field $E_1$.
Hence, see \cite{1}, there is a discrete valuation $v_2$ of the field
$E_1(X_2,\ldots
,$ $X_{n-1},\mu_3 X_n+\mu_4 X_{n+1})=E_2$
such that $v_2|_{E_1}=v_1$ and $v_2(X_i)=0$, $1\leqslant i\leqslant n-1$,
$v_2(\mu_3 X_n+\mu_4 X_{n+1})=0$.
Hence (26) implies $v_2(\mu_1 X_n+\mu_2 X_{n+1})=1$.
Notice that $E_2\supset\overline{K}(X_2,\ldots , X_{n+1})$.

The extension of fields
${\cal K}\supset \overline{K}(X_2,\ldots , X_{n+1})$ is finite separable
since $\Delta\ne 0$. Therefore the extension ${\cal K}\supset E_2$ is
also finite separable.
Hence there is a
discrete valuation $v_3$ of the field ${\cal K}$ such that
$v_3|_{E_2}=v_2$.
Denote by $v_4$ the restriction of $v_3$ to the field
$\overline{K}(X_2,\ldots,X_{n+1})$.
By the described construction $v_4(z)\geqslant 0$ for every
$z\in\overline{K}[X_2,\ldots ,X_{n+1}]$,
$v_4(\mu_1 X_n+\mu_2 X_{n+1})=1$ and
$v_4(\overline{K}(X_2,\ldots,X_{n+1})\setminus\{0\})={\Bbb Z}$, see
\cite{1}.
The valuation $v_3$ is ramified over $v_4$
since since $v_3(\xi)=v_1(\xi)=1/e$.
This implies that $\mu_1 X_n+\mu_2 X_{n+1}$ divides the discriminant
$\Delta$.
The lemma is proved.

\par\medskip\noindent{\bf COROLLARY~3}\hspace{0.1em} {\it  Let
$f\in\overline{K}[X_1,\ldots ,X_{n+1}]$, $n\geqslant 2$,
be an irreducible
polynomial such that $\deg_{X_1}f\geqslant 1$,
$\deg_{X_1,\ldots ,X_{n+1}}f\leqslant d$ for an integer $d\geqslant 1$ and
(24) is satisfied.
Suppose that $f$ is irreducible in the ring
$\overline{K}[X_1,$ $\ldots,X_{n+1}]$, the polynomial
$f$ does not belong to the ideal $(X_n,X_{n+1})$ and for all
$\mu_1,\mu_2\in\overline{K}$ such that $\mu_1\ne0$ or $\mu_2\ne 0$ the
linear form $\mu_1 X_n+\mu_2 X_{n+1}$
does not divide $\Delta$. Then for all
$t^*\in\overline{K}$, except at most
$$
56 d^8-32 d^7-54 d^6+96 d^5-72 d^4+15 d^3+9 d^2-3 d<56d^8
$$
the polynomial
$f(X_1,\ldots , X_n,t^*X_n)\in\overline{K}[X_1,\ldots ,X_n]$
is irreducible in the last ring.
}\par\medskip

\noindent{\bf PROOF}\quad This follows immediately from
Lemmas~12---14
and Corollary~2 from Section~3. The corollary is proved.






\begin{thebibliography}{88}

\bibitem{1}
 {\bf Bourbaki N.}, {\it ``Alg\`ebre commutative'', Chap.
 1--7\/} Actualit\'es Sci. Indust., nos. 1290, 1293, 1308, 1314, Paris
 1961, 1964, 1965.

\bibitem{2} {\bf Chistov A. L.:} {\it ``Polynomial complexity algorithm
 for factoring polynomials and constructing components of a variety in
 subexponential time''}, Zap. Nauchn. Semin. Leningrad.  Otdel. Mat.
 Inst. Steklov (LOMI) v.137 (1984), p.\ 124--188 (in Russian) [English
 transl.: J. Sov. Math. v.34, No.4, (1986) p.\ 1838--1882].

\bibitem{3} {\bf Chistov A. L.:} {\it ``Double-Exponential
Lower Bound for the Degree of
a System of Generators of a Polynomial Prime Ideal''},
Algebra i Analiz 20, (6), (2008) p. 186--213 (in Russian) [English
 transl.: St. Petersburg Math. J. v.20, (2009), p.\ 983--1001].

\bibitem{4} {\bf  Chistov A. L.:} {\it
``A deterministic  polynomial--time algorithm for the first
 Bertini theorem''},
Preprint of St.Petersburg
Mathematical Society (2004),
http://www.mathsoc.spb.ru/preprint/2004/index.html




\bibitem{5} {\bf Chistov A.L., Fournier H., Gurvits L.,  Koiran P.:}
 {\it ``Vandermonde Matrices, NP-Completeness, and Transversal
Subspaces''},
 Foundations of Computational Mathematics 3, (4), (2003) p.\
421--427.



\bibitem{6} {\bf Lenstra A. K., Lenstra H. W., Lovasz L.:}
 {\it ``Factoring Polynomials with Rational Coefficients''},
 Mathematische Annalen 261, (1982) p.\ 515--534.


\bibitem{7} {\bf Zariski O.:} {\it ``Pencils on an algebraic variety and
a new proof of a theorem of Bertini''}, Trans. Amer. Math. Soc., v. 50
(1941) p. 48--70.



\end{thebibliography}




\end{document}






























































