\input amstex
\documentstyle{amsppt}
\magnification 1200
\NoBlackBoxes
\pagewidth{40em}



\def \C  {\bold{C}}
\def \Q  {\bold{Q}}
\def \Z  {\bold{Z}}
\def \P  {\bold{P}}
\def \R  {\bold{R}}
\def \eps  {\varepsilon}
\def \|{\,|\,}
\def\vol{\operatorname{vol}}


%----------
\topmatter
\title       The volume of the Newton polytope of a discriminant
\endtitle
%----------
\author                        S.Yu.~Orevkov
\endauthor
%----------
\address     Steklov Math. Inst. of Russ. Acad. Sci.
                ul. Gubkina 8, Moscow, Russia
\endaddress
\endtopmatter
%----------

\document

\subsubhead 1. Statement of the result
\endsubsubhead
%
Let $D_n=D_n(x_0,...,x_n)$ be the {\it discriminant},
i.e. the polynomial in $x_0,\dots,x_n$, vanishing if and only if
the polynomial $\sum_{k=0}^n x_k t^k$ has a multiple root.
Example: $D_2(a,b,c)=b^2-4ac$.

The {\it Newton polytope} $\Delta(f)$ of a polynomial
$f=\sum a_u x_1^{u_1}\dots x_N^{u_N}$, where $u=(u_1,\dots,u_n)$,
is the convex hull in $\R^N$ of the set
$\{u\in\Z^N\,|\,a_u\ne 0\}$. If $V\in\R^N$ is the affine
$k$-plane such that the rank of the lattice $V\cap\Z^N$ equals $k$,
then the $k$-dimensional volume $\vol_k$ on the plane
$V$ will be normalized so that the volume of the fundamental
parallelepiped of the lattice is equal to one.

Denote $\Delta(D_n)$ by $Q_n$.
Because of the evident homogenity and quasihomogenity of the
discriminant,
$Q_n$ lies in the $(n-1)$-plane
%
% $$
%      \sum x_k=2(n-1),  \qquad   \sum kx_k = n(n-1).      \eqno(1)
% $$
%
$$
   u_0+\dots+u_n=2(n-1),\qquad u_1+2u_2+\dots+nu_n=n(n-1). \eqno(1)
$$

\proclaim{ Theorem 1 }
    $\vol_{n-1} Q_n = 2^{n-1} n^{n-2}/n!$.
\endproclaim


\proclaim{ ���६� 2 }
    $ \vol_{n-2} \Delta(\bar D_n) = (n+6)\,2^{n-3}n^{n-5}/(n-2)!$
for $n\ge 3$, where
$\bar D_n(y_0,\dots,y_{n-2})$ is the discriminant of
$t^n+y_{n-2} t^{n-2} + \dots + y_0$.
\endproclaim

Let $A\subset\Z^d$ be an $n$-point set, $P_A$ its convex hull,
$\dim P_A=d$.
Following [1], denote by $\C^A$ the space of Laurent polynomials
of the form $\sum_{a\in A} x_a t^a$, where
$t=(t_1,\dots,t_d)$,
$a=(a_1,\dots,a_d)$,
$t^a=t_1^{a_1}\dots t_d^{a_d}$, and
let us define the discriminant $D_A$ as the polynomial
in $n$ variables
$(x_a)_{a\in A}$, such that the equation $D_A=0$ defines
a hyperplane in $\C^A$, which is the closure of the set of all
polynomials $f$, for which the hypersurface
$\{f=0\}$ has a singularity in the torus $(\C\setminus0)^d$.
Respectively, the discriminant $E_A$ defines
the closure of the set of polynomials which have a degenerate
restriction at least to one face of $P_A$
(see details in [1]). Let $N=n-d-1=\dim\Delta(D_A)=\dim\Delta(E_A)$.

\proclaim{ Theorem 3 }
$\vol_N \Delta(E_A) > \big(\prod_{k=1}^d (k+1)^{i_k}\big)(N-c)!/N!$,
where $c=i_0-d-1$, and $i_k$ is the number of points in $A$,
which are the interior points of $k$-planes of $P_A$.
\endproclaim


\proclaim{ Corollary } For any $d$ there exist $C_0(d),C_1(d)>0$,
such that $\log\vol Q_{d,m} \ge C_0(d)+C_1(d) m^d$, where
$Q_{d,m}=\Delta(D_A)$ for $A=\{a\in\Z^d\| a_i\ge0,\, \sum a_i \le m\}$.
\endproclaim

This gives a negative answer to a question of E.I.~Shustin
about existence of constants $B_0(d)$, $B_1(d)$, such that
$\log( N! \vol Q_{d,m} ) \le B_0(d) + B_1(d) m^d$, where
$N = C_{n+d}^d-d-1 = \dim Q_{d,m}$.
An affirmative answer would provide an expected asymptotical
upper bound for the number of rigid isotopy types of projective
real hypersurfaces of degree $m$ as $m\to\infty$
(of the same order as the lower bound following from the
constructions by Viro's method).


\subsubhead 2. Notation
\endsubsubhead
%
For $k\in\Z$ set $\bar k=\{1,\dots,k\}$ ($\bar 0=\varnothing$).
By $S_n$ we denote the symmetric group:
$S_n=\{\sigma:\bar n\to\bar n \| \sigma(\bar n)=\bar n\}$;
by $\pi_n:\R^{n+1}\to\R^{n-1}$ we denote the projection
$(u_0,\dots,u_n)\mapsto(u_1,\dots,u_{n-1})$.
For a finite set $\alpha$, we denote its cardinality by
$\#\alpha$, and we set
$C_\alpha^k=\{\beta\subset\alpha\| \#\beta=k\}$
(then $\#C_\alpha^k=C_{\#\alpha}^k$ is the binomial coeficient).
For $\alpha\subset\Z$, let us denote by
$\mu_\alpha:\{1,\dots,\#\alpha\}\to\alpha$, the bijection such that
$\mu_\alpha(1)<\mu_\alpha(2)<\dots$.
The letter $m$ will always denote $n-1$.

\subsubhead 3. $Q_n$ as the secondary polytope
\endsubsubhead
%
According to a result due to Gelfand-Kapranov-Zelevinski [1],
$Q_n$ is combinatorially equivalent to the
$m$-cube (recall that $m=n-1$),
and its vertices are the points
$\{q_\alpha\}_{\alpha\subset\bar m}$, where the coordinates
$(q_0^\alpha,\dots,q_n^\alpha)$ of $q_\alpha$
are defined as follows.
%
%���ᬮ�ਬ ࠧ������ (�ਠ������) ��१�� $[0,n]$ �� ����訥 ��१��
%�窠�� ������⢠ $\alpha$. �᫨ $0<k<n$, � �� $k\not\in\alpha$
%������� $q_k^\alpha=0$, �� $k\in\alpha$ ������� $q_k$
%ࠢ�� ��ꥬ� ����� �窨 $k$ � �⮩ �ਠ����樨,
%� �� $k=0,n$ --- ��ꥬ� ������, 㬥��襭���� �� 1, � ����
%
%�᫨ $\alpha=\{k_1,\dots,k_a\}$, $0=k_0<k_1<\dots<k_a<k_{a+1}=n$, �
%$$
%  q_k^\alpha =
%        \cases  k_{i+1}-k_{i-1}, \qquad & k=k_i\in\alpha\\
%                k_1-1,                  & k=0           \\
%                n-k_a-1,                & k=n           \\
%                0,                      & k\not\in\alpha\cup\{0,n\}
%        \endcases
%$$
%
If $\alpha=\{k_1,\dots,k_a\}$,
$0=k_0 < k_1<\dots< k_a < k_{a+1}=n$, $k_{-1}=1$, $k_{a+2}=n-1$, then
$$
  q_k^\alpha =
        \cases  k_{i+1}-k_{i-1}, \qquad & k=k_i\in\alpha\cup\{0,n\} \\
                0,                      & k\not\in\alpha\cup\{0,n\}
        \endcases
$$

\subsubhead 4. Triangulation of a skew cube
\endsubsubhead
%
Let $p_\alpha=(p_1^\alpha,\dots,p_N^\alpha)$ be sets in $\R^N$,
indexed by subsets $\alpha\subset\bar N$, such that
$p_i^\alpha>0$ for $i\in\alpha$ and $p_i^\alpha=0$
for $i\not\in\alpha$.
For a $\sigma\in S_N$, we denote by $s_\sigma$ the simplex
spanned on the points $p_{\sigma(\bar k)}$, $k=0,\dots,N$.

\proclaim{ Lemma 1 }
%%%
a). $\{s_\sigma\}_{\sigma\in S_N}$ is a triangulation of some
(not necessarily convex) polyhedron $P$, homeomorphic to a cube
(hence, $\vol P=\sum\vol s_\sigma$).

b). If the convex hull $P'$ of the points $p_\alpha$
is combinatorially equivalent to a cube
(i.e. for any $i$, all the points$\{p_\alpha\}_{i\in\alpha}$
lye on the same $(N-1)$-face of $P'$), then $P'=P$.
\endproclaim

\demo{ Proof } Projecting from $p_{\bar N}$, let us define $P$
inductively as the union of the cones over the intersections
with the coordinate hyperplanes.
\qed\enddemo

Example: if $P$ is a cube then
$s_\sigma=\{(x_1,\dots,x_N)\in P \|
   x_{\sigma(1)} \ge x_{\sigma(2)} \ge\dots\ge x_{\sigma(N)} \}$.

\subsubhead 5. Recurrent relation
\endsubsubhead
%
Let $\{s_\sigma\}_{\sigma\in S_m}$ be a triangulation of $Q_n$ from
Sect.~4.

\proclaim{ Lemma 2 }
    $\vol \pi_n(s_\sigma) = \big(\prod_{k=1}^{n-1}
                            q_{\sigma(k)}^{\sigma(\bar{k})}\big)/(n-1)!$.
\endproclaim

\demo{ Proof } $\pi_n(q_{\sigma(\bar0)})=\pi_n(q_\varnothing)=0$.
Hence, $m! \vol \pi_n(s_\sigma)=|\det A_\sigma|$ where $A_\sigma$
is the matrix composed of the vectors
$\{q_{\sigma(\bar k)}\}_{k\in\bar m}$ written as columns.
It remains to note that $q_{\sigma(k)}^{\sigma(\bar{k})}$
is the $k$-th entry in the $\sigma(k)$-th row and all
the entries to the left of it vanish.
\qed\enddemo

\proclaim{ Lemma 3 }
     $v_n = n \sum_{k=1}^{n-1} C_{n-2}^{k-1} v_k v_{n-k}$,
     where $v_1=1$, $v_n = (n-1)! \vol \pi_n(Q_n)$.
\endproclaim

\demo{ Proof } This follows from Lemmas 1 and 2,
if we presents $\sum_{\sigma\in S_m}$ as
$\sum_{k\in\bar m}\sum_{\sigma\in S_m^k}$, where
$S_m^k = \{\sigma\|\sigma(1)=k\}$, and then replace the innermost
sum with the triple sum corresponding to the bijection
$ C_{\bar m\setminus\{1\}}^{k-1}  \times
                           S_{k-1} \times S_{m-k} \to S_m^k $,
$(\alpha,\sigma_1,\sigma_2)\mapsto\sigma$ where $\sigma(1)=k$,
$\sigma(i)=\mu_\alpha(\sigma(i))$  for  $i<k$,
$\sigma(i)=\mu_{\bar m\setminus(\alpha\cup\{k\})}(\sigma_2(i-k))$
for $i>k$.
\qed\enddemo

\subsubhead 6. Identity
\endsubsubhead
%
The Abel binomial identity can be written in the form [2; Sect.1.2.7]
$
    \alpha\beta\sum_{k=0}^n C_n^k (\alpha+k)^{k-1}(\beta+n-k)^{n-k-1}
                =(\alpha+\beta)(\alpha+\beta+n)^{n-1}.
$
Substituting $\beta=-\alpha$, dividing by $\alpha^2$
and taking the limit as $\alpha\to 0$, we get
$$
    \sum_{k=1}^{n-1} C_n^k k^{k-1} (n-k)^{n-k-1}=2(n-1)n^{n-2}.   \eqno(2)
$$

\subsubhead 7. Proof of the theorems
\endsubsubhead
%
From (2) and Lemma 3, we get by induction $v_n=2^{n-1}n^{n-2}$.
Let $V$ be the plane defined by (1).
Solving (1) with respect to $u_0$, $u_1$, we get a bijection
$j_n:\Z^{n-1}\to V\cap\Z^{n+1}$, moreover, $|\det(j_n\pi_n)|=n$.
Hence, $n\vol Q_n=\vol \pi_n(Q_n) = v_n/(n-1)!$. Theorem 1 is proved.
%
Theorem 2 is proved similarly: using the recurrent relation
$\bar v_n = n\sum_{k=2}^{n-1} C_{n-3}^{k-2}\bar v_k v_{n-k}$,
we find $\bar v_n = (n+6)\,2^{n-3}\,n^{n-4}$ where $\bar v_n/(n-2)!$
is the volume of the projection of
$\Delta(\bar D_n)$ onto the plane $y_n=0$.

Theorem 3 follows from Lemma 1(a). According to [1], $\Delta(E_A)$ is
the convex hull of the points in $\R^A$, corresponding to all
triangulations of $P_A$. Let $V$ be the set of the vertices of $P_A$
($i_0=\#V$).
For each $\alpha\subset A\setminus V$, let us consider any triangulation
whose set of vertices is $\alpha\cup V$.
The corresponding points $\{q_\alpha\}\subset\R^A$
lye on an $M$-plane ($M=N-c=\#A\setminus V$) and satisfy
the hypothesis of Lemma 1(a).
Hence, one can span $M!$ simplices on them so that the volume of
each one is
$\ge\prod(k+1)^{i_k}/M!$ (this follows from Lemma 2 and
the description of $Q_A$, given in [1]).
The points $\{q_\alpha\}$ lye on an $M$-dimensional section of
$Q_A$ ($\dim Q_A=N$), and this gives $M!/N!$.
\Refs

\ref\no1
\by I.M.~Gelfand, M.M.~Kapranov, A.V.~Zelevinskii
\book Discriminants, resultants and multidimensional determinants
\publ Birkh\"auser
\publaddr Boston
\yr 1994
\endref

\ref\no2\by I.P.~Goulden, D.M.~Jackson
\book Combinatirial enumeration
\publ John Wiley and Sons
\publaddr N.Y.
\yr 1983
\endref

\endRefs

\enddocument
