\documentstyle{article} \newlength{\textwidthextra} \setlength{\textwidthextra}{1in} \addtolength{\textwidth}{1\textwidthextra} \addtolength{\evensidemargin}{-.5\textwidthextra} \addtolength{\oddsidemargin}{-.5\textwidthextra} \newlength{\textheightextra} \setlength{\textheightextra}{1in} \addtolength{\textheight}{1\textheightextra} \addtolength{\topmargin}{-.5\textheightextra} \tolerance=500 \newcommand{\fr}[2]{\frac{\displaystyle{#1}}{\displaystyle{#2}}} \newcommand{\cl}{\cline{2-4}} \def\vhack#1{{\!{\scriptstyle{#1}}\atop{\vphantom0}}} \newcommand{\r}{{\bf R}} \newcommand{\z}{{\bf Z}} \newcommand{\rn}{\r^\vhack{n}} \newcommand{\rk}{\r^\vhack{k}} \newcommand{\rl}{\r^\vhack{l}} \newcommand{\rmm}{\r^\vhack{m}} \newcommand{\rki}{\r^{k_i}} \newcommand{\zk}{\z^\vhack{k}} \newcommand{\ra}{\rightarrow} \newcommand{\zn}{\z^\vhack{n}} \newcommand{\bx}{{\bf x}} \newcommand{\bone}{1,1,\ldots,1} \newcommand{\lp}{\left(} \newcommand{\rp}{\right)} \newcommand{\lb}{\biggl(} \newcommand{\rb}{\biggr)} \newcommand{\rbb}{\, \Bigr\}} \newcommand{\lbb}{\Bigl\{ \,} \newcommand{\sto}{+ \cdots +} \newcommand{\cto}{ , \ldots ,} \newcommand{\ints}{\displaystyle{\int\!\!\! \int\!\! \cdots\! \int}} \newcommand{\mints} {\mathop{\displaystyle{\int\!\!\! \int\!\! \cdots\! \int}}} % The following \intsargs is plain Tex: \newcommand{\intsargs}[3] {\matrix{ {#1} & {\ints} & {#2} \cr {\,} & {\scriptstyle{#3}} & {\,} \cr }} \newcommand{\stack}[2] {\scriptstyle{#1} \atop \scriptstyle{#2}} \newcommand{\h}{{H}} \newcommand{\g}{{G}} \newcommand{\q}{{Q}} \newcommand{\gnorm}[1]{\big\| #1 \big\|_{\g}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\half}{\frac{1}{2}} \newcommand{\xone}{x_1} \newcommand{\xn}{x_n} \newcommand{\xk}{x_k} \newcommand{\xveck}{\xone , \ldots , \xk} \newcommand{\cp}{ {\cal P}} \newcommand{\mx}{{\mit\Xi}} \newcommand{\mph}{{\mit\Phi}} \newcommand{\mo}{{\mit\Omega}} \newcommand{\mop}{{\mo}_p} \newcommand{\md}{{\mit\Delta}} \newcommand{\la}{{\mit\Lambda}} \newcommand{\s}{\sigma} \newcommand{\ga}{{\mit\Gamma}} \newcommand{\gf}[2]{\fr{\ga (1+{#1}) \,\ga (1+{#2})} {\ga (1+{#1}+{#2})} } \newcommand{\gff}[2]{\fr{\ga (1+{#1}) \cdots \ga (1+{#2})} {\ga (1+{#1} \sto {#2})} } \newcommand{\xvecn}{\xone , \ldots , \xn} \newcommand{\card}{\mathop{\rm card}\nolimits} \newcommand{\inter}{\z^\vhack{n} \cap r \g} \newcommand{\interr}{\z^\vhack{n} \cap p \q \cap ( p \z^\vhack{n} + r \g )} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\bea}{\begin{eqnarray}} \newcommand{\eea}{\end{eqnarray}} \newcommand{\vol}{\mathop{\rm Vol}\nolimits} \newcommand{\volp}{{\vol}_{{}_{+}}} \newcommand{\infmu}{\inf_{\mu \geq 0}} \newcommand{\dxn}{dx_1 \cdots dx_n} \newcommand{\dxk}{dx_1 \cdots dx_k} \newcommand{\dst}{\displaystyle} \newcommand{\vsp}{\vspace{.25in}} \newcommand{\hpm}{\frac{p-1}{2}} \newcommand{\nc}[1]{\newcommand{#1}} \nc{\open}{\mathop{\rm int}\nolimits} \nc{\maca}{\card \big( \la \cap \open ( \g ) \big) } \nc{\mt}{{\mit\Theta}} % \newcommand{\yk}{y_{k}} \newcommand{\xrho}{x_{\rho}} \newcommand{\delt}{{\mit\delta}} \newcommand{\dl}{{\mit\delta}_{L}} \newcommand{\dlg}{\dl ( \g )} \newcommand{\macl} {\stack{x_1 \cto x_s \geq 0} {x_1^\tau \sto x_s^\tau \leq 1}} \newcommand{\yone}{y_{1}} \newcommand{\zone}{z_{1}} \newcommand{\zs}{z_{s}} \newcommand{\ys}{y_{s}} \newcommand{\phione}{\phi_{1}} \newcommand{\phis}{\phi_{s}} \newcommand{\mone}{m_{1}} \newcommand{\ms}{m_{s}} \newcommand{\vone}{V_{1}} \newcommand{\vs}{V_{s}} \newcommand{\none}{n_{1}} \newcommand{\nk}{n_{k}} \newcommand{\nj}{n_{j}} \newcommand{\pj}{p_{j}} \newcommand{\sigone}{\sigma_{1}} \newcommand{\sigk}{\sigma_{k}} \newcommand{\sigj}{\sigma_{j}} \newcommand{\fsig}{f_{\sigma}} \newcommand{\thsig}{\theta_{\sigma}} \newcommand{\psisig}{\psi_{\sigma}} \newcommand{\macb}{{n( \maca )}} \newcommand{\macc}{2^{-{c_{\sigma} \macb } } } \newcommand{\macd}{2^{- \macb}} \newcommand{\mace}{2^{-c \macb}} \newcommand{\macf}{\abs{\xone}^\s + \cdots + \abs{\xn}^\s} \newcommand{\macg}{\abs{\xone}^\s + \cdots + \abs{\xk}^\s} \newcommand{\mach}{\phione^\tau + \cdots + \phis^\tau} \newcommand{\cube}{\max \big( \abs{\xone} , \ldots , \abs{\xn} \big) } \newcommand{\maci}{\abs{\xone}^2 + \abs{x_2}^2 } \newcommand{\macj}{(\maci )^2 + \abs{x_3}^4 + \abs{x_4}^4 } \newcommand{\mack}{\big( \macj \big)^2 + \abs{x_5}^8 } \newcommand{\xir}{\xi (r)} \newcommand{\xipr}{\xi' (r)} \newcommand{\xiz}{\xi (z)} \newcommand{\xipz}{\xi' (z)} \newcommand{\xippr}{\xi'' (r)} \newcommand{\macm} { \lp r_j \dst\prod_{m=1}^{n_j-1} \sin (\theta_{j,m}) \rp^{2 / \s_j} & \hbox{ for } i=1 , } \newcommand{\macn} { \lp r_j \cos (\theta_{j,{i -1}}) \dst\prod_{m=i}^{n_j -1} \sin (\theta_{j,m}) \rp^{2 / \s_j} & \hbox{ for } 2 \leq i \leq n_j -1 , } \newcommand{\maco} {\lp r_j \cos (\theta_{j,{n_j -1}}) \rp^{2 / \s_j} & \hbox{ for } i=n_j . } \newcommand{\macp} {x_1= \big( r_1 \sin (\theta_1) \big)^{2 / \eta} , } \newcommand{\macq} {x_2= \big( r_1 \cos (\theta_1) \big)^{2 / \eta} , } \newcommand{\macr} {x_3= \big( r_2 \sin (\theta_2) \big)^{2 / \zeta} , } \newcommand{\macs} {x_4= \big( r_2 \cos (\theta_2) \big)^{2 / \zeta} . } \newcommand{\yzk}{\sum_{y \in \z^\vhack{k}}} \newcommand{\yzn}{\sum_{y \in \z^\vhack{n}}} \newcommand{\xrk}{\displaystyle\int_{x \in \r^\vhack{k}}} \newcommand{\xrn}{\displaystyle\int_{\r^\vhack{n}}} \newcommand{\fxs}{f(x)^\s} \newcommand{\fys}{f(y)^\s} \newcommand{\gks}{\g \Bigl( 1+ \fr{k}{\s} \Bigr)^{-1} } \newcommand{\gns}{\g \big( 1+ \fr{n}{\s} \big)^{-1} } \newcommand{\lzm}{\lim_{z \ra 1-}} \newcommand{\sni}{\sum_{n=-\infty}^{\infty}} \newcommand{\lz}{\ln 1/z} \newcommand{\ns}{\frac{n}{\s}} \newcommand{\nss}{n/ \s} \newcommand{\vj}{\vol (J)} \newcommand{\pr}{\varphi (r)} \newcommand{\gs}{ \g \Big( 1+\frac{k}{\s} \Big) } \newcommand{\lr}{ \ln \frac{1}{r} } \newcommand{\lt}{\ln \frac{1}{t}} \newcommand{\llt}{\ln \lt} \newcommand{\ls}{\ln ( c \s /k)} \newcommand{\lls}{\ln \ls} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \title{On the packing densities of superballs and other bodies} \date{September 24, 1990\\ (revised January 14, 1991)} \author{N.D. Elkies\thanks{Supported by the Harvard Society of Fellows and NSF Grant DMS-87-18965.} \\Department of Mathematics \\Harvard University \\One Oxford Street \\ Cambridge, Massachusetts 02138, U.S.A. \\ e-mail: elkies@zariski.harvard.edu \and A.M. Odlyzko \\AT\&T Bell Laboratories \\600 Mountain Avenue \\ Murray Hill, New Jersey 07974%-2070 , U.S.A.\\ e-mail: amo@research.att.com \and J.A. Rush\thanks{Supported by a Seggie-Brown research fellowship.} \\Department of Mathematics \\University of Edinburgh \\James Clerk Maxwell Building \\Edinburgh EH9 3JZ, Scotland, U.K. \\e-mail: jar@castle.edinburgh.ac.uk} \begin{document} \maketitle \newpage \begin{abstract} A method of obtaining improvements to the Minkowski-Hlawka bound on the lattice-packing density for many convex bodies symmetrical through the coordinate hyperplanes, described by Rush \cite{Lower}, is generalized so that centrally symmetric convex bodies can be treated as well. The lower bounds which arise are very good. %We apply the technique to various shapes, including the The technique is applied to various shapes, including the classical $l_\s$-ball, \[ \big\{ x \in \rn : \abs{x_1}^\s + \abs{x_2}^\s \sto \abs{x_n}^\s \leq 1 \big\}, \] for $\s \geq 1$. This generalizes the earlier work of Rush and Sloane \cite{RandS} in which $\s$ was required to be an integer. The superball above can be lattice packed to a density of $(b/2)^{n+o(1)}$ for large $n$, where \[ b=\sup_{t>0} \, \frac{\int_{x=-\infty}^\infty e^{-\abs{tx}^\s} dx} {\sum_{k=-\infty}^\infty e^{-\abs{tk}^\s} } . \] This is as good as the Minkowski-Hlawka bound for $1 \leq \s \leq2$, and better for $\s > 2$. %We establish an analogous density bound for superballs An analogous density bound is established for superballs of the shape \[ \big \{ x \in \rn : f(x_1 \cto x_k)^\s +f(x_{k+1} \cto x_{2k})^\s \sto f(x_{n-k+1} \cto x_n )^\s \leq 1, \quad k|n \big\} , \] where $f$ is the Minkowski distance function associated with a bounded, convex, centrally symmetric, $k$-dimensional body. Finally, we consider generalized superballs for which the defining inequality need not even be homogeneous. For these bodies as well, it is often possible to improve on the Minkowski-Hlawka bound. \end{abstract} \newpage \section{Introduction} %[Jason:] %Historical notes about packing, and the state of %knowledge prior to this paper, and some very specific %examples, with numbers, along the %lines of section 1 of "Superballs, products of baseballs, etc." %but taking into account Noam's improvements of my examples. %[Noam:] I've put in some further improvements obtained by %regarding some of these bodies as mixed superballs which %happen to have the same exponents, and explicitly maximized %functions instead of asking for zeros of their log-derivatives. For our purposes, {\em bodies\/} will always be closed, bounded, convex subsets of $\rn$, centrally symmetric, and with positive volume. A basic problem in the geometry of numbers is the estimation of the maximum lattice-packing density $\dl$ of a given body. This is the problem of maximizing the fraction of $\rn$ which is occupied by a lattice $\la$ of disjoint translates of the body. Overlap on the boundaries is disregarded. For a body $\g$, \[ \dlg = \fr{\vol ( G )}{\inf \det ( \la )}, \] the infimum being taken over packing lattices $\la$ of $\g$. Under a nonsingular linear transformation, $\dl$ is preserved, since the volume of the body and the determinant of the packing lattice change proportionally. The quantity $\dl$ is known exactly for only a few bodies; and the %greater the dimension $n$, the fewer the bodies. greater the dimension $n$, the fewer the bodies for which it is known. For spheres, $\dl$ is known in dimensions $1$ through $8$. Usually we can only hope for an estimate. The first major lower bound on lattice-packing density, valid in any number of dimensions, was Minkowski's bound \[ \dlg \geq 2^{1-n} \zeta (n) , \] which he proved by a tour de force in his own reduction theory of quadratic forms, in the case that $\g$ is an $n$-dimensional sphere. Hlawka \cite{Hlawka} proved that this holds not only for spheres but for all bodies (as we define them), thus verifying a previously unproven assertion of Minkowski. This is the famous {\em Minkowski-Hlawka bound\/} \cite[p.175]{Cassels}, \cite[p.199]{GandL}, \cite[p.145]{Lek}, \cite{RogersEx}. Rogers \cite{RogersEx} proved that for spheres \[ \dl \geq \fr{n 2^{1-n} \zeta (n)} {e (1-e^{-n} )} , \] improving on Minkowski's bound by a factor approaching $n/e$ for large $n$. Rush and Sloane \cite{RandS} found that the $l_\s$-balls having $\s = 3,4,5 $, etc., have \[ \dl \geq \gamma_\s^n , \] in which each $\gamma_\s$ exceeds $1/2$. This was the first {\em essential\/} improvement, i.e., improvement by a factor exponential in $n$, for these bodies. The article \cite{Lower} mentioned in the abstract described a code-theoretic method, based on Construction A of Leech and Sloane \cite{LandS}, giving rise to dense lattice packings of what were called {\em bodies of type} $\h$. Such a body is compact, convex, symmetric through the coordinate hyperplanes, and has the unit vectors \[ e_1 = (1,0 \cto 0) ,\; e_2 \cto e_n \] %on its surface. Often (so it was claimed in the introduction to that %paper) the method yields asymptotic densities on its surface. It was claimed in the introduction to that paper that often the method yields asymptotic densities much higher than \[ 2^{-n+o(n)} , \] as assured by the Minkowski-Hlawka bound. However, there has been no published evidence for this alleged oftenness; and considering the scarcity, indeed the veritable absence, of such examples\footnote{Granted, examples can be improvised, say as gently jostled tilings, or by nestling a body snugly within each tile. But we exclude such artful contrivances, which violate the spirit of the packing problem: Given a {\em body\/} find a dense {\em packing\/} thereof, not vice versa.} in the literature, the shapes discussed hereinafter with very high packing densities will be of interest. Here are some bodies and our estimates for their lattice-packing densities $\dl$ as $ n \ra \infty$. All the error factors $\exp o(1)$ can be removed by allowing nonlattice packings. \vspace{.25in} {\em Bodies defined by Cartesian products\/}. Suppose that $J$ is a bounded, convex, centrally symmetric body with maximum lattice-packing density $\dl (J)$ in $\rk$, centered at the origin, and let $f(x)=\infmu \{ \mu : x \in \mu J \}$. The $n$-dimensional body given by \[ \max \big( f( \xveck ) , f( x_{k+1} \cto x_{2k} ) \cto f( x_{n-k+1} \cto x_n ) \big) \leq 1 , \quad k|n , \] can be packed to a density $\dl (J)^{n/k + o(n)}$. The result itself is not surprising, indeed one gets density $\dl (J)^{n/k}$ by using the orthogonal sum of $n/k$ copies of the closest-packing lattice for $J$. But it is interesting that our method gives essentially the same bound. It would be nice to know whether $\dl (J)^{n/k}$ is the best possible. (See the third open problem in Section 9.) \vsp {\em Cross polytopes, Euclidean spheres, and other $l_\s$% -balls\/}.\footnote{This example from \cite{RandS}, \cite{Lower}, is not appearing here for the first time, though the exponent in those papers had an error term $O(n/\ln n)$ that is improved here to $o(1)$ and eliminated entirely for nonlattice packings. The bodies called {\em superballs} there are here called $l_\s$-balls, and are subsumed as a special case. We shall use the term superball in a wider sense. (See Section 3.)} If $\s \geq 1$ and \[ \g = \big\{ x = ( \xvecn ) \in \rn : \macf \leq 1 \big\} \] then \[ \dlg \geq 2^{-c_\s n + o(1)} \quad {\rm as} \quad n \ra \infty \] for certain constants $c_\s$. It will be found that $c_\s$ is less than one whenever $\s>2$, resulting in an improvement over the Minkowski-Hlawka bound for all such $l_\s$-balls. As $\epsilon \ra 0+$, \[ \epsilon^{-1} (\ln 1/\epsilon)^{3/2} (1-c_{2+\epsilon}) \ra \fr{\sqrt{\pi}\zeta(3)}{2\ln 2} \] which shows the behavior of the bound near $\s = 2$. Some numerical values of $c_\s$ are given in Table 1. \begin{table}[htbp] %\vspace{0.2cm} \begin{center} \begin{tabular}{|c|c|} \hline $\s$ & $c_\s$ \\ \hline $1 \leq \s \leq 2$ & 1 \\ 2.001&.9999641166\\ 2.01&.999438314\\ 2.1 & .989213040 \\ 3 & .822600380 \\ 4 & .674242663 \\ 5 & .569240536 \\ 50 & .074523381 \\ $\phantom{\biggl|}\s \ra \infty\phantom{\biggr|}$ & $\dst{c_\s \sim \fr{\ln \ln \s}{\s \ln 2} \ra 0}$ \\ \hline \end{tabular} \end{center} \caption{Truncated decimal values of $c_\s$ for some $l_\s$-balls.} \end{table} \vsp {\em Minkowskian complex superballs\/}. These bodies were of interest to Minkowski \cite[I, p.\ 261]{MinkGessam} in connection with discriminants of algebraic number fields. Let $\g \subseteq \rn = \r^\vhack{\rho + 2 s}$ be given by the inequality \[ \abs{\xone}^\s +\cdots+ \abs{x_\rho}^\s + \big( \yone^2 + \zone^2 \big)^{\s / 2} + \cdots + \big( \ys^2 + \zs^2 \big)^{\s / 2} \leq 1 \] where $\s \geq 1$. (See \cite[p.\ 411]{GandL}.) Let $\rho / n = a_1$ and $2s / n = a_2$, so that $a_1 + a_2 = 1$. Then $\dlg \geq 2^{-c_\s n + o(1)}$, where \bea c_\s &=& 1 + a_1 \log_2 \lb \Big( \ln \fr{1}{r_1} \Big)^{1 / \s} \fr{\thsig (r_1)}{2 \ga ( 1+1/ \s )} \rb \nonumber\\ &&\mbox{}+ \fr{a_2}{2} \log_2 \lb \Big( \ln \fr{1}{r_2} \Big)^{2 / \s} \fr{ \sqrt{3} \, \psisig (r_2)}{2 \pi \ga (1+2/ \s )} \rb \label{Minkbd} \eea in which \[ \ga (1+z) = z ! = \int_0^{\infty} t^z e^{-t} dt\;\; \hbox{ for } \;\;z>0 , \] \[ \thsig (z) = \sum_{m=-\infty}^{\infty} z^{\abs{m}^\s} , \] \[ \psisig (z) = \sum_{k=-\infty}^{\infty}\,\, \sum_{l=-\infty}^{\infty} z^{ {( k^2 + k l + l^2 )}^{\s / 2} } , \] and $r_1,r_2$ are positive numbers chosen to minimize $c_\s$ in~(\ref{Minkbd}). \vsp {\em Bodies based on the diamond shape\/}. Let $\g \subseteq \rn = \r^\vhack{\rho + 2 s}$ be given by the inequality \[ \abs{\xone}^\s +\cdots+ \abs{x_\rho}^\s + \big( \abs{\yone} + \abs{\zone} \big)^\s + \cdots + \big( \abs{\ys} + \abs{\zs} \big)^\s \leq 1 \] where $\s \geq 1$. Let $\rho / n = a_1$ and $2s / n = a_2$, so that $a_1 + a_2 = 1$. Then $\dlg \geq 2^{-c_\s n + o(1)}$, where \bea c_\s& =& 1 + a_1 \log_2 \lb \Big( \ln \fr{1}{r_1} \Big)^{1 / \s} \fr{\thsig (r_1)}{2 \ga ( 1+1/ \s )} \rb \nonumber\\ &&\mbox{}+ \fr{a_2}{2} \log_2 \lb \Big( \ln \fr{1}{r_2} \Big)^{2 / \s} \fr{ \psisig (r_2)}{4 \ga (1+2/ \s )} \rb \label{Diambd} \eea in which $\thsig (z)$ is as in the previous example, \[ \psisig (z) = \sum_{k=-\infty}^{\infty}\,\, \sum_{l=-\infty}^{\infty} z^{{\max ( \abs{k}, \abs{l} ) }^{\s } } =1+ \sum_{m=1}^\infty 8m z^{m^{\s}} , \] and $r_1,r_2$ are positive numbers chosen to minimize $c_\s$ in~(\ref{Diambd}). It was mentioned in \cite{Lower} that the case $a_1 = 0$, $a_2 =1$ of the above body admitted an essential improvement to the Minkowski-Hlawka bound for $\s =6,7,8$, etc. Here we do even better. By considering instead the body \[ \max ( \abs{x_1}, \abs{x_2} )^\s \sto \max ( \abs{x_{n-1}}, \abs{x_n} )^\s \leq 1 , \] which, being linearly equivalent, has the same lattice-packing density, we can improve on both the Minkowski-Hlawka bound and its cited improvement, for all $\s$ greater than about $2.134485$. \vsp {\em Bodies based on the cube\/}. Let $\g \subseteq \rn = \r^\vhack{\rho + 3 s}$ be given by the inequality \[ \abs{w_1}^\s +\cdots+ \abs{w_\rho}^\s + \max \big( \abs{\xone},\abs{\yone} , \abs{\zone} \big)^{\s } + \cdots + \max \big( \abs{x_s},\abs{\ys} , \abs{\zs} \big)^{\s } \leq 1 \] where $\s \geq 1$. Let $\rho / n = a_1$ and $3s / n = a_2$, so that $a_1 + a_2 = 1$. Then $\dlg \geq 2^{-c_\s n + o(1)}$, where \bea c_\s& =& 1 + a_1 \log_2 \lb \Big( \ln \fr{1}{r_1} \Big)^{1 / \s} \fr{\thsig (r_1)}{2 \ga ( 1+1/ \s )} \rb \nonumber\\ &&\mbox{}+ \fr{a_2}{3} \log_2 \lb \Big( \ln \fr{1}{r_2} \Big)^{3 / \s} \fr{ \psisig (r_2)}{8 \ga (1+3/ \s )} \rb \label{Cubebd} \eea in which $\thsig (z)=\sum_{k \in \z} z^{\abs{k}^\s}$, \[ \psisig (z) = \sum_{(j,k,l) \in \z^\vhack{3}} z^{{\max ( \abs{j} , \abs{k}, \abs{l} ) }^{\s } } =1+\sum_{m=1}^\infty \big( (2m+1)^3-(2m-1)^3 \big) z^{m^\s} , \] and $r_1,r_2$ are positive numbers chosen to minimize $c_\s$ in~(\ref{Cubebd}). \vsp {\em Bodies based on the sphere\/}. Let $\g \subseteq \rn = \r^\vhack{\rho + 3 s}$ be given by \[ \abs{w_1}^\s +\cdots+ \abs{w_\rho}^\s + \big( \xone^2+\yone^2 + \zone^2 \big)^{\s /2 } + \cdots + \big( x_s^2+\ys^2 + \zs^2 \big)^{\s /2} \leq 1 \] where $\s \geq 1$. Let $\rho / n = a_1$ and $3s / n = a_2$, so that $a_1 + a_2 = 1$. Then $\dlg \geq 2^{-c_\s n + o(1)}$, where \bea c_\s& =& 1 + a_1 \log_2 \lb \Big( \ln \fr{1}{r_1} \Big)^{1 / \s} \fr{\thsig (r_1)}{2 \ga ( 1+1/ \s )} \rb \nonumber\\ &&\mbox{}+ \fr{a_2}{3} \log_2 \lb\Big( \ln \fr{1}{r_2} \Big)^{3 / \s} \fr{ 3 \sqrt{2} \, \psisig (r_2)}{8 \pi \ga (1+3/ \s )} \rb \label{Sphbd} \eea in which $\thsig (z)=\sum_{k \in \z} z^{\abs{k}^\s}$, \[ \psisig (z) = \sum_{(j,k,l) \in \z^\vhack{3}} z^{{( j^2 + k^2+ l^2 +jk +kl) }^{\s /2 } } , \] and $r_1,r_2$ are positive numbers chosen to minimize $c_\s$ in~(\ref{Sphbd}). %arithmetic minimum is unity. \vsp {\em Bodies based on the hypercube\/}. Let $\g \subseteq \rn = \r^\vhack{\rho + 4 s}$ be given by \[ \abs{v_1}^\s +\cdots+ \abs{v_\rho}^\s + \max \big( \abs{w_1}, \abs{\xone},\abs{\yone} , \abs{\zone} \big)^{\s } + \cdots + \max \big( \abs{w_s}, \abs{x_s},\abs{\ys} , \abs{\zs} \big)^{\s } \leq 1 \] where $\s \geq 1$. Let $\rho / n = a_1$ and $4s / n = a_2$, so that $a_1 + a_2 = 1$. Then $\dlg \geq 2^{-c_\s n + o(1)}$, where \bea c_\s& =& 1 + a_1 \log_2 \lb \Big( \ln \fr{1}{r_1} \Big)^{1 / \s} \fr{\thsig (r_1)}{2 \ga ( 1+1/ \s )} \rb \nonumber\\ &&\mbox{}+ \fr{a_2}{4} \log_2 \lb\Big( \ln \fr{1}{r_2} \Big)^{4 / \s} \fr{ \psisig (r_2)}{16 \ga (1+4/ \s )} \rb \label{Hypcubd} \eea in which $\thsig (z)=\sum_{k \in \z} z^{\abs{k}^\s}$, \[ \psisig (z) = \sum_{(i,j,k,l) \in \z^\vhack{4}} z^{{\max ( \abs{i}, \abs{j} , \abs{k}, \abs{l} ) }^{\s } } =1+\sum_{m=1}^\infty \big( (2m+1)^4 - (2m-1)^4 \big) z^{m^\s} , \] and $r_1,r_2$ are positive numbers chosen to minimize $c_\s$ in~(\ref{Hypcubd}). \vsp Table 2 lists some numerical values of these $c_\s$. \begin{table}[htbp] %\vspace{0.2cm} \begin{center} \begin{tabular}{|c|c|c|c|} \hline bodies based on the & $\s$ & $a_1$ & $c_\s$ \\ \hline \hline circle &$1\leq \s \leq 2$& 0 & 1 \\ (Minkowskian complex & 3 &0 & .860949908 \\ superballs) & 3 & 1/2 & .843869375 \\ & 4 & 0 & .729110596 \\ & 4 & 1/2 & .703515560 \\ & 10 & 0 & .392842258 \\ & $ \phantom{\biggl(} \infty \phantom{\biggr)}$ & $0 \leq a_1 \leq 1$ & $\displaystyle{1 - a_1 + \fr{a_2}{2} \log_2 \Bigl( \fr{\sqrt{3}}{2 \pi} \, \Bigr)} $ \\ \hline diamond & $1 \leq \s \leq 2.134485793$ & 0 & 1 \\ & 3&0& .832284542 \\ & 4&0& .685724360 \\ & 4&1/2 &.686104293 \\ & 5&0& .581353081 \\ & $\infty$ & $0 \leq a_1 \leq 1$& 0 \\ \hline cube & $1 \leq \s \leq 2.212882112 $& 0&1 \\ & 3&0&.845323587 \\ &3&$1/2$&.864968538 \\ & 4&0&.698698206 \\ & 5&0& .594016546 \\ & $\infty$& $0 \leq a_1 \leq 1$& 0 \\ \hline sphere&$1 \leq \s \leq 2$& 0& 1 \\ &3&0&.895000891 \\ &3&$1/2$&.863338582 \\ & 4&0& .780495356 \\ & 5&0&.692044379 \\ & 6&0&.624274637 \\ & $\phantom{\biggl(} \infty \phantom{\biggr)}$&$ 0 \leq a_1 \leq 1 $& $\displaystyle{1-a_1+\fr{a_2}{3} \log_2 \Bigl( \fr{3 \, \sqrt{2}}{8 \pi}\, \Bigr)}$ \\ \hline hypercube& $1\leq \s \leq 2.285497723$&0&1 \\ &3&0&.858882563 \\ &3&$1/2$&.903475529 \\ &4&0&.711485684 \\ & $\infty$&$0 \leq a_1 \leq 1$&0 \\ \hline \end{tabular} \end{center} \caption{Numerical values of $c_\s$ for bodies based on various shapes. Decimals are truncated, and $a_2 = 1-a_1$.} \end{table} All the foregoing examples are special or limiting cases of Theorem \ref{thsup0}, whose statement and proof we shall withhold until the sixth section, ``The packing densities of superballs''. In that section we also give an argument along the lines of~\cite{RandS} and~\cite{Lower} which gives slightly weaker bounds, with the same exponential growth but with error $\exp o(n)$ rather than $\exp o(1)$. Although the error term is worse, the method provides more information on how to find a dense lattice packing (Theorem~\ref{thsup}), by specifying the parameter $r$ in the $[n,k,r,p,\g]$ codes to which Construction A is applied. Theorems \ref{thsup0} and~\ref{thsup} depend for their proofs upon the intermediate results of Sections 2 through 5. These contain versions of our density bound valid for bodies generally, the definition of a superball, expressions for the volume of a superball, and a bound on the number of lattice points in a superball, respectively. Section 7 is devoted to the $l_\s$-ball, and Section 8 is concerned with the generalization of superballs to the inhomogeneous case of mixed exponents. In Section 9 we state some questions left unanswered by this paper. Besides the various references already cited throughout this introduction, see the articles \cite{KandL}, \cite{LandT}, \cite{Selfdual}, \cite{Recent}, \cite{Cross}, \cite{Thin} and the books \cite{Erdos}, \cite{MinkGeom}, \cite{PandC} for related work. \section{Two general versions of the bound} A lattice $\la$ is said to be {\em admissible} for the body $\g$, or to be $\g$-admissible, if the body is centered at the origin of $\la$, and has no further points of $\la$ in its interior $\open (\g )$. Although the usage is nonstandard, it is sometimes syntactically convenient to interchange $\g$ and $\la$. Thus, under the foregoing circumstances, we refer to $\g$ as a $\la$-admissible body. The results of this paper can be obtained from either of the two following theorems, which are asymptotically of the same strength. %[Noam:] I'd like to also point out the following: Indeed the proofs are based on the same fundamental idea, but with different emphases: as usual in the geometry of numbers one has the dual choices of fixing either a lattice (Theorem \ref{th1}) or a body (Theorem \ref{th2}). \begin{theorem} \label{th1} Let $p$ be an odd prime, and $0 \leq r\leq p$. A body $\g \subseteq \rn$, admissible for the lattice of integer points $\zn$, can be lattice packed with density \[ \fr{2^{1-n} r^n \vol (\g)} {(p-1) \card \big( \interr \big) } \] where $Q$ is the unit hypercube \[ \big\{ x \in \rn : \max ( \abs{x_1} \cto \abs{x_n} ) \leq 1/2 \big\} . \] \end{theorem} {\em Proof\/}: We give only the merest sketch. Provided \[ kk$. In Section 8 we shall introduce {\em generalized superballs\/}, in which a variety of $\s$'s and $f$'s may occur within one body. \section{Volume of a superball} In order to apply the density bounds of Section 2 to the superballs of Section 3, we need to determine their volume. The following theorem provides three important volume formulas. \begin{theorem} \label{th4} Let $\phi_j : \r^{m_j} \ra \r$ be distance functions, $m_1 \sto m_s =n$, $\s >0$, and \[ V_j = \vol \big\{ x \in \r^{m_j} : \phi_j (x) \leq 1 \big\} , \quad \quad j=1 , 2 \cto s . \] Then the volume of the superball $f(\xvecn ) \leq 1$, where $f$ is the distance function \[ f= \sqrt[\tau]{\phi_1^\tau \sto \phi_s^\tau} , \] is given by each of the following three expressions: \be \label{eqrere} V_1 V_2 \cdots V_s \, \fr{\ga (1+m_1/\tau ) \ga (1+m_2 / \tau) \cdots \ga (1+m_s / \tau)} {\ga (1+ n/ \tau)} , \ee \be \label{eqfff} \intsargs{\ga (1+n/\s )^{-1} \! \! \! \! } { \! \! \! e^{-f(x)^\s} dx_1 \cdots dx_n ,}{x \in \rn} \ee and \be \label{eq5} \ga (1+n/ \s )^{-1} \lim_{t \ra 0+} t^{n/\s} \sum_{x \in \zn} e^{-tf(x)^\s } . \ee \end{theorem} {\em Proof\/}: By means of the disk method from calculus, we can establish the first formula. Let $V$ be the desired volume of $f \leq 1$. We approximate the superball by a finite number of disks \[ x_1 (j_1) \leq \phi_1 \leq x_1 (j_1 + 1) \cto x_s (j_s) \leq \phi_s \leq x_s (j_s +1) \] where \[ 0 \leq x_1 \leq 1 ,\; 0 \leq x_2 \leq \sqrt[\tau]{1-x_1^\tau} \;\cto\; 0 \leq x_s \leq \sqrt[\tau]{1-x_1^\tau - \cdots -x_{s-1}^\tau} , \] of volumes \[ \prod_{i=1}^s \Big( x_i (j_i+1)^{m_i} V_i - x_i (j_i )^{m_i} V_i \Big) . \] For $i=1 \cto s$ we let the largest of the ${\mit\Delta} x_i ( j_i ) = x_i(j_i +1) - x_i ( j_i )$ approach zero, and find that \begin{eqnarray*} V & = & \int_{x_1=0}^1 \int_{x_2=0}^{\sqrt[\;\tau]{1-x_1^\tau}} \cdots \int_{x_s=0}^{\sqrt[\;\tau]{1-x_1^\tau - \cdots -x_{s-1}^\tau}} d \lp V_1 x_1^{m_1} \rp \cdots d \lp V_s x_s^{m_s} \rp \\ & \raise1.8ex\hbox{=} & \intsargs{ V_1 \cdots V_s \! \! \! \! \! \! \! } { \! \! \! \! \! m_1 x_1^{m_1 -1} \cdots m_s x_s^{m_s -1} d x_1 \cdots d x_s } { \macl } \\ & = & V_1 \cdots V_s \, m_1 \cdots m_s \, \tau^{-s} \fr{\ga (m_1 / \tau) \cdots \ga (m_s / \tau) } {\ga (1+ m_1 / \tau \sto m_s / \tau) } \\ & = & V_1 \cdots V_s \, \frac {\ga (1+m_1 / \tau) \cdots \ga (1+m_s / \tau)} {\ga (1+n / \tau)} . \end{eqnarray*} (It may be helpful to consult \cite[pages 620-625]{GandR} wherein multiple integrals of this and similar sorts are tabulated.) This proves the first expression for $V$. The second expression actually represents the volume $V$ of $f \leq 1$ for {\em any\/} distance function $f : \rn \ra \r$, not just this particular one, as we can see in the following way. \begin{eqnarray*} \int_{x \in \rn} e^{-f(x)^\s} dx_1 \cdots dx_n &=& \int_{x \in \rn} \lp \int_{ \stack{y \in \r}{y \geq f(x)^\s} } e^{-y} dy \rp dx_1 \cdots dx_n \\ &=& \int_{y=0}^\infty e^{-y} \lp \int_{ \stack{x \in \rn}{f(x)^\s \leq y} } dx_1 \cdots dx_n \rp dy \\ &=& \int_{y=0}^\infty e^{-y} y^{n/\s} \, \vol (f \leq 1) \, dy \\ &=& V \ga ( 1 + n/{\s} ) . \end{eqnarray*} %[Noam:] Is the following really necessary? It would seem that %\ref{eq5} is just the definition of the the integral formula %\ref{eq4} as a limit of Riemann sums. But then again the %Poisson inversion formula as introduced here does play an %important role later... Now for the third volume formula, which is really just the definition of the second volume formula as the limit of a Riemann sum. We prove it using some Poisson inversion machinery which will be crucial later. The expression (\ref{eq5}) is understood to mean that $t \ra 0$ from above. Let $t>0$ be fixed for the time being. We begin by writing the periodic function \[ \yzk e^{-tf(y+u)^\s} , \] for $u \in \rk$, as a Fourier series \[ \yzk e^{2 \pi i(u_1 y_1 \sto u_k y_k )} \xrk e^{-t \fxs} e^{-2 \pi i(x_1 y_1 \sto x_k y_k) } \dxk . \] This is justified since $\exp ( -t f(y)^\s )$ and all its partial derivatives decay rapidly as $y$ moves away from the origin. Setting $u=0$ we get a version of the Poisson summation formula \cite[I, p.35]{Terras}, \[ \yzk e^{-t \fys} = \yzk \xrk e^{-t \fxs -2 \pi i(x_1 y_1 \sto x_k y_k) } \dxk . \] Replacing $x$ with $t^{-1/ \s} x$ we obtain \[ \yzk e^{-t \fys} = t^{-k/ \s} \yzk \xrk e^{-\fxs -2 \pi i t^{-1/ \s} (x_1 y_1 \sto x_k y_k) } \dxk . \] Multiplying both sides by $t^{k/ \s}$, we get \[ t^{k/ \s} \yzk e^{-t \fys} = \xrk e^{-\fxs} \dxk \] \[ + \sum_{\stack{y \in \zk}{y \neq 0}} \xrk e^{-\fxs -2 \pi i t^{-1/ \s} (x_1 y_1 \sto x_k y_k) } \dxk . \] Let $t \ra 0$ along the positive real axis. The sum over nonzero lattice points vanishes by the Riemann-Lebesgue lemma, so \[ \lim_{t \ra 0+} t^{k/ \s} \yzk e^{-t \fys} = \xrk e^{-\fxs} \dxk . \] By applying the second volume formula to the right-hand side, we complete the proof of the third expression, and so of Theorem \ref{th4}. \section{The number of lattice points in a superball} The following theorem will enable us to get a useful upper bound on the denominators of the density bounds in Theorems \ref{th1} and \ref{th2}. The simplicity of the proof belies the power of the result. Mazo and Odlyzko \cite{MandO} discuss the method in the case of ordinary spheres. %[Jason:]Andrew's lemma and proof, %reference to the paper with Mazo, %and any other relevant stuff. %[Noam:] This looks like the natural place %to put my estimate. \begin{theorem} \label{th5} Let $f:\rk \ra \r$ be a distance function, and $s$ a positive number.\\ i) The $n$-dimensional superball of positive radius $r$ given by \[ f(x_1 \cto x_k)^\s +f(x_{k+1} \cto x_{2k})^\s \sto f(x_{n-k+1} \cto x_n )^\s \leq r^\s, \quad k|n, \] contains no more than \be e^{sr^\s} \biggl( \, \sum_{x \in \z^\vhack{k}} e^{-sf(x)^\s } \biggr)^{n/k} \label{amobd} \ee points of $\zn$.\\ ii) For some $r>0$ the number of points of~$\zn$ in this radius-$r$ superball is at most \be \Biggl(\biggl( \, \sum_{x \in \zk} e^{-sf(x)^\s } \biggr)\bigg/ \biggl(\mints_{x\in\rk} e^{-sf(x)^\s} dx_1 \cdots dx_k \biggr)\Biggr)^{n/k} \label{ndebd} \ee times its volume. \end{theorem} {\em Proof\/}: i) Let $N_y$ be the number of lattice points on the boundary of the superball of radius $y$, centered at the origin. Then \be \sum_{\stack{y \geq 0}{N_y \neq 0}} N_y e^{-sy^\s} = \biggl( \, \sum_{x \in \zk} e^{-sf(x)^\s } \biggr)^{n/k} . \label{amosum} \ee But then \begin{eqnarray*} \sum_{y \leq r} N_y & \leq & \sum_{\stack{y \geq 0}{N_y \neq 0}} N_y e^{sr^\s -sy^\s} \\ & = & e^{sr^\s} \biggl( \, \sum_{x \in \zk} e^{-sf(x)^\s } \biggr)^{n/k}, \end{eqnarray*} which yields the bound~(\ref{amobd}). ii) Let $U_r$ be the number of lattice points in the interior of the superball of radius~$r$, so \[ U_r=\sum_{\stack{y 0$. Mazo and Odlyzko \cite{MandO} showed that for Euclidean spheres ($k = 1$ and $ \s = 2$ in Theorem~\ref{th5}), the infimum of~(\ref{amobd}) over $s > 0$ gives the correct estimate (to within a factor of $\exp o(n)$ ) for the number of lattice points in the ball. Their proof can be easily extended to cover the cases of the other superballs. Thus Theorem~\ref{th5} does not give away much, and for our method to give a result better than the Minkowski-Hlawka bound, we need to find an~$r$\/ for which the bound of part (i) of Theorem~\ref{th5} is small. Now consider any superball as in Theorem~\ref{th5}, or more generally, any body. As we move the center of the superball around, the number of points of~$\zn$ inside equals the volume of the superball, if we average over all possible positions of the center. Therefore a basic question is whether the number of points of $\zn$ inside a superball is minimized when the superball is centered at the origin or not. In the case of the Euclidean sphere ($k = 1, \s = 2$, and $r = cn^{1/\s}$ for a constant $c>0$, as usual), Mazo and Odlyzko~\cite{MandO} showed that centering the ball at the origin maximizes the number of lattice points inside (to within factors of $\exp o(n))$, no matter what $c$\/ is. Therefore our method cannot improve on the Minkowski-Hlawka bound for Euclidean spheres. We now sketch a proof that this is also true for all $l_\s$-balls with $ 0 < \s \leq 2$. By the method of~\cite{MandO}, the problem can be reduced to showing that if $s > 0$ and \[ g(y) = \sum_{k=-\infty}^\infty \exp(-s\abs{k-y}^\s), \] then $g(y)$ is maximized for $y = 0$. By the proof of the third volume formula of Theorem~\ref{th4}, this will follow if we show that the Fourier transform of $\exp(-s\cdot\abs{u}^\s)$ is nonnegative for $0 < \s \leq 2$. There are proofs of this result in the literature, but they are quite cumbersome. We present here a very nice proof due to B.~F.~Logan, which comes from his unpublished work on completely monotonic functions. It follows easily from the following lemma (also due to Logan): %[Noam:] "Lemma B" in Andrew's patch \begin{lemma} \label{Logan} Let $s > 0$, $0 < \s \leq 2$, and $h(u) = \exp(-s\cdot\abs{u}^\s)$. Then \[ h(u) = \int_{t=0}^\infty \exp(-tu^2) d\alpha(t), \] where $\alpha(t)$ is bounded and non-decreasing and the integral converges for all~$u$. \end{lemma} {\em Proof\/}: It suffices to prove this for $s = 1$, since the general case will then follow by a change of variables. Let $\beta = \s/2$, so that $0 < \beta \leq 1$, and for $x \geq0$, let $H(x) = \exp(-x^\beta)$. We first show that $H(x)$ is completely monotonic~\cite{Widder} on $(0, \infty)$; i.e., that $(-1)^k {d^k H(x)}/{dx^k}$ is nonnegative for all $k \geq 0$ and all $x > 0$. We use the induction hypothesis that \[ \fr{d^k H(x)}{dx^k} = (-1)^k \sum_{j=1}^k c(k,j) x^{j\beta-k} H(x), \] where the $c(k,j)$ are $\geq0$. This is clearly true for $k = 0$. If it's true for $k$, though, differentiating that expression term by term shows that it is also true for $k+1$, since all the exponents $j\beta-k$ are $\leq0$. This proves the complete monotonicity of~% $H(x)$, and so by a theorem of Bernstein \cite[Theorem~12a]{Widder}, we find that \[ H(x) = \int_{t=0}^\infty e^{-xt} d\alpha(t), \] where $\alpha(t)$ is bounded and non-decreasing and the integral converges for $0 \leq x < \infty$. We now make the substitution $x = u^2$, and obtain the claim of Lemma~\ref{Logan}. Since $e^{-tx^2}$ has a nonnegative Fourier transform for all $t > 0$, we see immediately that the Fourier transform of $h(u)$ is $\geq0$, which establishes our main claim. In fact, we can find out more from Lemma~\ref{Logan}. Mazo and Odlyzko showed that the number of lattice points in a Euclidean sphere is minimized (within factors of $\exp o(n)$ again, and for $r$\/ on the order of $n^{1/\s}$) when the center of the ball is placed at the point $(1/2,\ldots,1/2)$. Combining their method of proof with Lemma~\ref{Logan} we see that this also holds for $l_\s$-balls with $ 0 < \s \leq 2$. When $\s > 2$ (but $k = 1$ still), the situation changes. As will be shown later, one can always choose a~$c$ so that for $r = cn^{1/\s}$ the number of lattice points inside the $l_\s$-ball is smaller than the volume by a factor exponential in~$n$. However, this is not true for all~$c$. It can be shown by the method of~\cite{MandO} that the positions for the center of the $l_\s$-ball where the number of lattice points is maximized or minimized (to within factors of $\exp o(n)$) are always of the form $(x,x,...,x)$ for some fixed~$x$, but the values of~$x$ vary depending on~$c$. In many cases the extreme values of~$x$ are~0 and~$1/2$ (but in some cases 0 maximizes the number of lattice points, in other cases it minimizes this number). In other cases different behavior occurs. For example, for $\s = 3$, there are at least 2 intervals of values of~$c$ for which the value of~$x$ that maximizes the number of lattice points inside the $l_\s$-ball is neither $x = 0$ nor $x = 1/2$. \section{The packing densities of superballs} Either of the next two theorems supplies a result promised in the abstract. They are related in the same way that Theorems \ref{th1} and \ref{th2} are related to each other. \begin{theorem} \label{thsup0} Let $f : \rk \ra \r$ be the distance function of a body $\{x : f(x) \leq 1 \}$, and $\s \geq 1$. The $n$-dimensional superball given by \[ f(x_1 \cto x_k)^\s \sto f(x_{n-k+1} \cto x_n )^\s \leq 1 , \quad k|n , \] can be lattice packed with density at least \[ \lp \! \half \, \sup_{\la} \, \lp { \fr {\int_{x \in \rk} e^{-f( x )^\s } dx_1 \cdots dx_k } {\det(\la) \sum_{x \in \la} e^{-f( x )^\s } } } \rp^{1/k} \,\,\, \rp^{n + o(1)} \] as $n \ra \infty$. Here the supremum is taken over all lattices $\la$ in~$\rk$, and the $o(1)$ correction in the exponent can be removed by allowing nonlattice packings. \end{theorem} {\em Proof\/}: We apply the version~(\ref{ndebd2}) of the second part of Theorem~\ref{th5} to an arbitrary lattice $\la$ in~$\rk$, setting $s=1$. (We could use any other $s$, but that would give the same result as taking $s=1$ and scaling $\la$ by a factor $s^{1/\s}$.) We obtain some $r$\/ such that the number $M_n(r)$ of points of $\la^{n/k}$ contained in the $n$-dimensional superball of radius~$r$\/ is bounded by $M_n(r)\leq A\cdot V_r$, where again $A$\/ is given by~(\ref{ndebd2}) and $V_r=r^n V_1$ is the volume of that superball. By Theorem~\ref{th2} it follows that disjoint translates of that superball (and thus also of the radius-1 superball) pack $\rn$ with density at least $(2\sqrt[k]{A\det\la}\,)^{-n}$. Now if $M_k(r)=1$, so $\la$ is admissible for the $k$\/-dimensional superball of radius~$r$, clearly also $M_n(r)=1$ and our packing is already the lattice packing with lattice $2\la^{n/k}$. Otherwise we have $M_n(r)\geq 1 + (n/k)(M_k(r)-1) \ra\infty$ as~$n\ra\infty$, so there exists a prime $p\geq M_n(r)-1$ with $p=(1+o(1))M_n(r)$; thus from Theorem~\ref{th2} we obtain a lattice packing of the dimension-$n$ superball with density at least $(1-o(1))(2\sqrt[k]{A\det\la}\,)^{-n}$, Q.E.D. We next apply the methods of \cite{RandS} and \cite{Lower} to obtain a nearly identical bound (weaker only by a factor of $\exp o(n)$) while also obtaining a specific choice for~$r$\/ as a function of~$n$ by using the first part of Theorem~$\ref{th5}$. By a linear transformation of $\rk$ we can make the lattice $\la$ of Theorem~$\ref{thsup0}$ homothetic to~$\zk$, and will do this to conform with the practice of~\cite{RandS} and~\cite{Lower}. \begin{theorem} \label{thsup} Let $f : \rk \ra \r$ be the distance function of a $\zk$-admissible body $\{x : f(x) \leq 1 \}$, and $\s \geq 1$. The $n$-dimensional superball $\g$ given by \[ f(x_1 \cto x_k)^\s \sto f(x_{n-k+1} \cto x_n )^\s \leq 1 , \quad k|n , \] can be lattice packed with density at least \[ \lp \! \half \, \sup_{s > 0} \, \lp { \fr{\int_{x \in \rk} e^{-sf( x )^\s } dx_1 \cdots dx_k } {\sum_{x \in \zk} e^{-sf( x )^\s } } } \rp^{1/k} \,\,\, \rp^{n + o(n)} \] as $n \ra \infty$. \end{theorem} {\em Proof\/}: Our starting point is Theorem \ref{th1}. If there is any point of $\zn$ at which two different translates of $r \g$ by vectors of $p \zn$ overlap, then \[ \card \big( \interr \big) < \card \big( \inter \big) , \] and if there is no such lattice point, then we instead have equality. In any event, the left-hand side never exceeds the right. Consequently \[ \dlg \geq \fr{2^{1-n} r^n \, \vol ( \g ) } {(p-1) \card \big( \inter \big) } . \] Let $p$ be the smallest prime greater than $r$, where \[ r = \Bigl( \frac{n}{ \s s} \Bigr)^{1/ \s } , \] and $s$ is a positive constant at our disposal. Then \[ r < p \leq 2r+3, \qquad 2/(p-1) = e^{o(n)} , \] and it follows that \be \label{eqstar0} \fr{\ln \dlg}{n} \geq \frac{1}{n} \ln \biggl( \fr{2^{-n} r^n \, \vol (\g )}{ \card ( \inter ) } \biggr) + o(1) \ee for large $n$. Using (\ref{eqrere}) of Theorem \ref{th4}, we get \[ \vol ( \g ) = \ga ( 1+k/ \s )^{n/k} \ga ( 1+n/ \s )^{-1} \, \vol ( f \leq 1 )^{n/k} , \] in which \[ { \ga ( 1+n/ \s )} = n^{n/ \s} ( \s e )^{-n/ \s } e^{o(n)} \quad {\rm as} \quad n \ra \infty \] by Stirling's formula. Hence \be \label{eqstar1} \ln \big( r^n \, \vol ( \g ) \big) = n \ln \lb \Bigl( \frac{e}{s} \Bigr)^{1/ \s } \, \sqrt[k]{ \ga (1+k/ \s ) \vol (f \leq 1) } \, \rb + o(n) . \ee The first part of Theorem \ref{th5} gives \be \label{eqstar2} \card ( \inter ) \leq e^{n/ \s } \biggl( \, \sum_{x \in \z^\vhack{k}} e^{-sf(x)^\s } \biggr)^{n/k} . \ee Substituting the estimates (\ref{eqstar1}) and (\ref{eqstar2}) into the density bound (\ref{eqstar0}), we find that \[ \frac{ \ln \dlg}{n} \geq \ln \Biggl( \half \, s^{-1/ \s} \, \biggl( \frac{ \ga ( 1+k/ \s ) \vol (f \leq 1) } { \sum_{x \in \zk} e^{-sf(x)^\s } } \, \biggr)^{1/k} \, \Biggr) + o(1) . \] But by (\ref{eqfff}) from Theorem \ref{th4}, \begin{eqnarray*} s^{-k/ \s} \ga (1+k/ \s ) \vol (f \leq 1) & = & s^{-k/ \s} \int_{x \in \r^\vhack{k}} e^{-f(x)^\s} \dxk \\ & = & \int_{x \in \r^\vhack{k}} e^{-sf(x)^\s} \dxk , \end{eqnarray*} and the proof of Theorem \ref{thsup} is complete. Let us now investigate how Theorem \ref{thsup} behaves in the three limiting cases $s \ra \infty$, $s \ra 0+$, and $\s \ra \infty$. The expression \[ \lp { \fr{\int_{x \in \rk} e^{-sf( x )^\s } dx_1 \cdots dx_k } {\sum_{x \in \zk} e^{-sf( x )^\s } } } \rp^{1/k} = \,\,\,\, h(s,\s) , \] say, whose supremum is taken, approaches 0 as $s \ra \infty$, making the bound weak. But $h$ approaches 1 as $\ s \ra 0+$, so that the bound is of the same asymptotic strength as the Minkowski-Hlawka bound in that case. If there is some positive $s$ which makes $h$ greater than one, then we obtain an essential improvement on the Minkowski-Hlawka bound. Next we ascertain the limiting form of Theorem \ref{thsup} as $\s\rightarrow\infty$. The superball (\ref{eqsupdef}) becomes \[ \g = \big\{ x \in \rn : \max \big( f( \xveck ) \cto f( x_{n-k+1} \cto x_n ) \big) \leq 1 \big\} , \] a Cartesian product of $k$-dimensional bodies $f \leq 1$. Let $z=e^{-s}$, \[ \xiz = \sum_{x \in \zk} z^{f(x)^\s} , \] and $u(z)=h(s,\s)$. Instead of $s >0$, we seek a positive $z <1$ to optimize the density bound. Setting the logarithmic derivative of $u(z)$ equal to zero, we get \be \label{eq888} - \s = \frac{k \xiz}{z \xipz \ln z} . \ee Let $c$ be the number of points of $\zk$ on the surface $f=1$. Since \be \label{eq395} \xiz = 1+cz+O(z^2) \ra 1 \ee and \[ \xipz = c + O(z) \ra c , \] equation (\ref{eq888}) behaves like \be \label{eq40} \frac{c \s}{k} = \frac{1}{z \lz} \ee for small positive $z$. Note that \[ \lim_{z \ra 0+} \frac{1}{z \lz} = + \infty . \] So if $\s$ is large, there is some small % % $\rho>0$ such that (\ref{eq888}) has $z=\rho$ as its smallest positive root. Let us determine the asymptotic behavior of this $\rho$ as $\s \ra \infty$. Thus we seek the asymptotic behavior of the smaller solution $\rho$ (there are two solutions as $\s \ra \infty$ but the larger one is an artifact) of (\ref{eq40}) or equivalently the larger solution $x$ of \be \label{eq42} x e^{-x} = t \ee as $t \ra 0$. Here we have set $x = \ln 1/\rho$ and $t = k / (c \s )$. Following the example of de Bruijn \cite[p.25]{Brui} we write (\ref{eq42}) as \be \label{eq43} x = \lt + \ln x . \ee If $t>0$ is sufficiently small, then \[ \lt < x < 2 \lt \] and so $\ln x = O( \ln \ln 1 / t )$ as $t \ra 0$. By (\ref{eq43}), \[ x= \lt + O \Bigl( \llt \Bigl) = \lb 1+\frac {O ( \ln \ln 1/t )}{\ln 1/t} \rb \lt = \lp 1+O \Bigl( \frac{\ln \ln 1/t}{\ln 1/t} \Bigr) \rp \lt . \] So \[ \ln x = \llt + \ln \lp 1+ O \Bigl( \frac{\ln \ln 1/t}{\ln 1/t} \Bigr) \rp =\llt + O \lp \frac{\ln \ln 1/t}{\ln 1/t} \rp . \] Using this in (\ref{eq43}) we get \[ x= \lt + \llt + O \lp \frac{\ln \ln 1/t}{\ln 1/t} \rp , \] or, going back to the original variables, we find that the optimal $s$ is \be \label{eq46} s = \ln \frac{1}{\rho} = \ls + \lls + O \lp \frac{\lls}{\ls} \rp \ee as $\s \ra \infty$. We could refine these estimates by successive substitution into (\ref{eq43}), but (\ref{eq46}) is already more accurate than we need. Now we can obtain the limiting form of Theorem \ref{thsup} as $\s \ra \infty$. %Don't start lines with "From"; the mailer changes this %to ">From" which comes out funny. {}From (\ref{eq46}) we see that $\rho \ra 0$ and so from (\ref{eq395}), $\xi (\rho) \ra 1$. Clearly $\ga (1+k/ \s) \ra 1$. And again using (\ref{eq46}) we find that $( \ln 1/\rho )^{1/ \s} \ra 1$. So $u(z)=h(s,\s)$ approaches $ \vol (f \leq 1)^{1/k} . $ The limiting form of Theorem \ref{thsup} is therefore as follows: \begin{theorem} \label{th8} Let $f:\rk \ra \r$ be the distance function of a $\zk$-admissible body $J$. Suppose that $k$ divides $n$, and that $\g$ is the Cartesian product of $n/k$ copies of $J$, that is \[ \g = \big\{ x \in \rn : \max \big( f( \xveck ) \cto f(x_{n-k+1} \cto x_n ) \big) \leq 1 \big\} . \] Then the maximum lattice-packing density $\dl$ of $\g$ satisfies \[ \dlg \geq \gamma^{n+o(n)} \] as $n \ra \infty$ where \[ \gamma = \half \max \big( 1 , \sqrt[k]{\vj}\,\, \big) . \] If $\,\vj > 1$ then this is stronger than the Minkowski-Hlawka bound. \end{theorem} Suppose that $\zk$ is a closest-packing lattice for $J/2$. Then the bound $\dl (G) \geq \dl (J)^{n/k+o(n)}$ given by Theorem \ref{th8} is essentially the same as one gets by using an orthogonal sum of closest-packing lattices for $J$. This justifies the example given in the introduction, concerning bodies defined by Cartesian products. A careful justification of the passage to the limit which gave rise to Theorem~\ref{th8} can be given as follows: Inside the body \[ \g_\s = \big\{ x \in \rn : \big( f( \xveck )^\s \sto f( x_{n-k+1} \cto x_n )^\s \big)^{1/ \s} \leq 1 \big\} \] inscribe a ball $\mu \g$, \[ \g = \g_\infty = \big\{ x \in \rn : \max \big( f( \xveck ) \cto f( x_{n-k+1} \cto x_n ) \big) \leq 1 \big\} , \] with $\mu < 1$ as large as possible. Then apply Construction A to $[n,k,r,p, \g_\s]$ codes. This gives packings of $\mu \g$ whose density is $ \delta \vol ( \mu \g ) / \vol ( \g_\s ) $ where $\delta$ is the density of the associated packing of $\g_\s$. It is obvious that if $\s$ becomes infinite quickly enough, as a function of $n$, then ${ \vol ( \mu \g ) }/{\vol ( \g_\s ) } \ra 1$ as $n \ra \infty$. Thus we obtain packings of $\mu \g$ (and so of $\g$, since the density is independent of scale) whose asymptotic densities are those of Theorem~\ref{th8}. \section{The case of the classical $l_\s$-ball} We assume, since we need convexity, that $\s \geq 1$. \begin{theorem} \label{lpb} The $l_\s$-ball \[ \abs{x_1}^\s + \abs{x_2}^\s \sto \abs{x_n}^\s \leq 1 \] can be lattice packed with density at least $(b/2)^{n+o(1)}$ as $n \ra \infty$, where \be b=\sup_{t>0} \, \frac{\int_{x=-\infty}^\infty e^{-\abs{tx}^\s} dx} {\sum_{k=-\infty}^\infty e^{-\abs{tk}^\s} } . \label{ratio} \ee When $1 \leq \s \leq 2$, this gives $b=1$, as in the Minkowski-Hlawka bound. But when $\s >2$, we obtain $b>1$, an essential improvement. As $\epsilon$ tends to $0+$, $b$ is asymptotically \be 1+ \frac{\sqrt\pi}{2}\zeta(3)\epsilon(\ln 1/\epsilon)^{-3/2} \big(1+o(1)\big) \label{asymp} \ee for $\s = 2 + \epsilon$. As $\s \ra \infty$, $\ln (2/b) \sim ( \ln \ln \s ) / \s$. \end{theorem} {\em Proof\/}: The first statement is proved by setting $k=1$ in Theorem \ref{thsup0}, and letting $f$\/ be the one-variable distance function $f(x)= \abs{x}$. For the second, rewrite the ratio in~(\ref{ratio}) as \[ \biggl(\int_{x=-\infty}^\infty e^{-\abs{x}^\s} dx\biggr)\bigg/ \biggl( t \sum_{k=-\infty}^\infty e^{-\abs{tk}^\s}\biggr), \] that is, as the ratio between the integral $\int_{-\infty}^\infty \exp(-\abs{x}^\s) dx$ and a Riemann sum for the integral; in particular as the mesh size~$t$\/ approaches zero the Riemann sum tends to the integral, showing that $b\geq1$. By the Poisson inversion theorem the difference between the sum and the integral is $2\sum_{m=1}^\infty g_\s(m/t)$, where $g_\s(w)$ is the Fourier transform \[ g_\s(w) = \int_{v=-\infty}^\infty \exp (-\abs{v}^\s ) e^{2 \pi i w v} dv; \] in particular, if $\s\leq2$ we have already seen that $g_\s(w)>0$ for all~$w$ (Lemma~\ref{Logan}), so the sum always exceeds the integral and $b=1$. For $\s>2$ it is easy to see that $g_\s$ must take negative values for some~$w$ by borrowing a trick from analytic number theory: if $g_\s(w)$ were nonnegative we would have \[ 3-4\exp(-\abs{v}^\s)+\exp(-\abs{2v}^\s)= 8\int_{w=-\infty}^\infty g_\s(w) \sin^4(\pi w v) dw >0 \] for all~$v$, but this inequality fails for sufficiently small positive $v$ once $\s>2$. While this does not in itself show that $b>1$, it would follow from Poisson that $b>1$ if $g_\s(w)$ were known to be negative for all $\abs{w}$ sufficiently large, for then the integral could be made to exceed its Riemann sum by taking $t$\/ sufficiently small. We will obtain below an asymptotic formula for $g_\s(w)$ as $\abs{w}\ra\infty$ (first part of Lemma~\ref{Fourier}) that will show that $g_\s(w)<0$ for large~$\abs{w}$ provided $\s$ lies in an open interval $(4m+2,4m+4)$ for some $m=0,1,2,\ldots$; in particular this will give $b>1$ for $2<\s<4$. But for $\s$ sufficiently large we can simply take $t=1$, when as a function of~$\s$ the Riemann sum $\sum_{k=-\infty}^\infty \exp(-\abs{k}^\s)$ decreases to~$1+2/e$ and $\int_{x=-\infty}^\infty \exp(-\abs{x}^\s) = 2\ga(1+1/\s)$ increases to $2>1+2/e$, and in fact numerical computation shows that (say) $\s>3$ is large enough to obtain $\sum_{k=-\infty}^\infty \exp(-\abs{k}^\s)<\ga(1+1/\s)$. Combining these two estimates we conclude that indeed $b>1$ for all $\s>2$. It remains to estimate~$b$\/ for $\s=2+\epsilon$ and $\s\ra\infty$. For the former we use the second estimate in Lemma~\ref{Fourier} below and apply the Poisson inversion theorem to obtain \[ t \biggl( \, \sum_{k=-\infty}^\infty \exp(-\abs{tk}^{2+\epsilon}) \biggr) -2\ga\Bigl(1+\frac1{2+\epsilon}\Bigr) \] \be =\,2\sqrt{\pi} \biggl(\, \sum_{m=1}^\infty e^{-(\pi m/t)^2}\ \biggr) -\frac{\zeta(3)t^3}{2\pi^2} \epsilon + O(\epsilon^2 t^2 + \epsilon t^4); \label{mess} \ee here the constant implied in $O(\epsilon^2 t^2 + \epsilon t^4)$ is absolute provided $\epsilon$ is small enough and~$t$\/ is bounded (and $t$\/ clearly must be bounded, say by $2\ga(1+1/(2+\epsilon))$, to be of any use to us). Next note that for fixed~$t$\/ the right-hand side of~(\ref{mess}) is positive for $\epsilon$ small enough, so as $\epsilon\ra0$, the optimal~$t$\/ must tend to zero as well. Thus the error $O(\epsilon t^4)$ is negligible and the sum $2\sqrt{\pi}\sum_{m=1}^\infty e^{-(\pi m/t)^2}$ is dominated by its first term $2e^{-(\pi/t)^2}$. It is then clear that the optimal~$t$\/ is $(1-o(1))\pi(\ln 1/\epsilon)^{-1/2}$ (note that this decreases very slowly with~$\epsilon$ --- indeed computations show that the optimal $t$\/ exceeds~1 for all $\s>2.011$ !); thus (\ref{mess}) is asymptotic to \[ \frac{\pi}{2}\zeta(3)\epsilon(\ln 1/\epsilon)^{-3/2}, \] and dividing by $2\ga(1+1/(2+\epsilon))=\sqrt{\pi}+O(\epsilon)$ we obtain the estimate~(\ref{asymp}). Finally, for the behavior of~$b$\/ as $\s\ra\infty$ (which was established in~\cite[equation (32)]{RandS}), use equation (\ref{eq46}) with $k=1$ and $c=2$. %set $k=1$ in Theorem~\ref{th8}. Thus Theorem~\ref{lpb} is proved modulo the following lemma on the behavior of $g_\s(w)$: \begin{lemma} \label{Fourier} i) For fixed $\s>0$, the Fourier transform \[ g_\s(w) = \int_{v=-\infty}^\infty \exp (-\abs{v}^\s ) e^{2 \pi i w v} dv \] of $\exp ( -\abs{v}^\s )$ has the asymptotic expansion \be g_\s(w)\sim 2\sum_{m=0}^\infty \frac{(-1)^{m+1}}{m!}\sin \Bigl(\frac{m\pi\s}{2}\Bigr)\ga(m\s+1) (2\pi\abs{w})^{-m\s-1} \label{asymp1} \ee as $\abs{w} \ra \infty$. ii) For $\s=2+\epsilon$, with $0<\epsilon<1$ and $|w|>1$, we have \be g_\s(w)=\sqrt{\pi}e^{-(\pi w)^2} - \big(1+O(\abs{w}^{-1})\big) \frac{\epsilon}{4\pi^2\abs{w}^3} +O\big((\epsilon/w)^2\big), \label{asymp2} \ee where the constants implied by the $O$\/-notation are absolute. \end{lemma} It is not crucial that $\epsilon<1$ and $|w|>1$, only that $\epsilon$ be positive and bounded, and $w$ bounded away from~0; changing the bounds on $\epsilon$ and~$w$ only changes the implicit $O$\/-constants in~(\ref{asymp2}). {\em Proof of Lemma \ref{Fourier}\/}\,: i) The basic idea is that $\exp(-\abs{v}^\s)$ is smooth for all $v\neq0$ so only the singularity at the origin can contribute polynomial terms to the asymptotic behavior of~$g_\s(w)$ at infinity. We prove by induction that for each $M=0,1,2,\ldots$ \bea g_\s(w)&=& 2\sum_{\stack{m}{m\s0$ (use contour integration to change the path of integration to the positive imaginary axis, or see the definite integrals \#3.761 in~\cite{GandR}); it is easy to check that this completes the induction step in~(\ref{ind}) and the proof of the asymptotic formula~(\ref{asymp1}). ii) Expand $\exp(-\abs{v}^\s)$ in powers of $\epsilon=\s-2$, obtaining \[ e^{-\abs{v}^\s}=e^{-v^2}-\epsilon\, e^{-v^2} v^2\ln\abs{v} +\epsilon^2 E(v) \] where $E(v)\!=\!E_\epsilon(v)$ and its first derivative are both continuous and bounded by (say) $c\exp(-v^2/2)$ for some absolute constant~$c$ independent of~$v$ and~$\epsilon$, whence the Fourier transform of $E(v)$ is $O(w^{-2})$ for $|w|>1$. (The exponent $-2$ can be improved but it suffices for our purposes.) Now the Fourier transform of $e^{-v^2}$ is well known to be $\sqrt\pi e^{-(\pi w)^2}$; and the Fourier transform of $e^{-v^2}v^2\ln\abs{v}$ can be estimated as before: replace $e^{2\pi i w v}$ by $\cos(2\pi w v)$ and integrate by parts three times to obtain \[ \big(1+O(\abs{w}^{-1})\big) \frac2{(2\pi w)^3} \int_{v=0}^\infty \frac2v \sin(2\pi w v) dv = \frac{1+O(\abs{w}^{-1})}{4\pi^2\abs{w}^3} \] (recall that $\int_0^\infty \sin(wv) dv/v = (\pi/2) {\rm \,sgn\,} w$), Q.E.D. {\em Note}\/: When $\sigma$ is an even integer $\geq4$, $\sin(m\pi\s/2)=0$ for all integers~$m$, so part (i) of the above result tells us only that the Fourier transform $g_\s(w)$ of $\exp(-|v|^\s)$ decreases faster than any negative power of~$|w|$, which is clear anyway because for such $\s$ the function $\exp(-|v|^\s)$ is an entire function of~$v$. In this case it can be shown by using contour integration and the saddle-point method that $g_\s(w)$ has infinitely many real zeros and that its absolute magnitude decreases approximately as $\exp (-C|w|^{\s/(\s-1)})$ for a constant $C=C(\s)$ as $|w|\rightarrow\infty$. \section{Generalization to mixed exponents} Our definition of a superball, (\ref{eqsupdef}), did not include mixed-exponent bodies such as the one given by the inequality \be %\big\{ x \in \rn : %\sum_{i=1}^{r_1}\abs{x_i}^{\s_1} + %\sum_{i=r_1+1}^{r_1+r_2(=n)}\abs{x_i}^{\s_2} %\leq1 \big\}. \abs{x_1}^{\s_1} \sto \abs{x_{ \rho_1}}^{\s_1} + \abs{x_{\rho_1 +1}}^{\s_2} \sto \abs{x_{\rho_1 + \rho_2}}^{\s_2} \leq 1 \label{sampleball} \ee where $\rho_1 + \rho_2 = n$. But our methods can be easily adapted to give lower bounds on the packing densities of bodies defined by inequalities on sums of homogeneous functions with different exponents. For example, the body~(\ref{sampleball}) can be packed with density at least $2^{-n}b_1^{\rho_1}b_2^{\rho_2}$ where $b_i/2=2^{c_{\s_i}}$ ($c_\s$ as defined in the introduction); this improves on Minkowski-Hlawka if either $\s_1$ or $\s_2$ exceeds~2. In this section we give the most general such bound readily obtainable by these methods: Let $\{k_i\}_{i\in I}$ be a finite collection of positive integers, and $n=\sum_{i\in I}k_i$ their sum. For each $i\in I$ let $\s_i\geq1$ be some real number and let $F_i=f_i^{\s_i}$ be the $\s_i$-th power of some distance function $f_i$ on~$\rki$. For any $r=\{r_i\}$ with each $r_i>0$, define the {\em generalized superball of radius~$r$}, $B(r)\subset\rn=\oplus_i\rki$, to be the body \[ B(r)=\Bigl\{ (\bx_i)\in\rn:\sum_{i\in I}F_i(\bx_i/r_i)\leq1 \Bigr\}. \] Note that for any~$r$ the generalized superball $B(r)$ may be obtained from the one of unit radius $B(\bone)$ by a linear transformation, specifically scaling each coordinate $\bx_i$ by the factor~$r_i$. As in Section~4 we have \be \prod_i\mints_{\r^\vhack{k_i}} e^{-F_i(\bx_i)} d\bx_i =\int_{y=0}^\infty e^{-y} V_y dy, \label{prod1} \ee where $V_y$ is the volume of $B(\{y^{1/\s_i}\})$. Note that $V_y=y^sV_1=y^s\vol(B(\bone))$ where $s=\sum_i k_i/\s_i$; this yields a formula for $\vol(B(\bone))$ generalizing the second formula of Theorem~\ref{th4}: \be \vol\big(B(\bone)\big)=\frac {\prod_i\mints_{\rki} e^{-F_i(\bx_i)} d\bx_i}{\ga\big(1+\sum_i k_i/\s_i\big)}= \frac {\prod_i\Bigl(\ga(1+k_i/\s_i)\vol\big(B_i(1)\big)\Bigr)}{\ga\big(1+\sum_i k_i/\s_i\big)} \label{vol+} \ee where $B_i(1)=\{\bx_i\in\rki:F_i(\bx_i)\leq1\}$. Also, if for each $i$ we take a lattice $\la_i$ in $\rki$ and let $U_y$ be the number of points of the lattice $\la=\oplus_i\la_i\subset\rn$ in $B(\{y^{1/\s_i}\})$, we have as in Section~5 \be \prod_i\left(\sum_{\bx_i\in\la_i} e^{-F_i(\bx_i)}\right) =\int_{y=0}^\infty e^{-y} U_y dy. \label{prod2} \ee We can thus generalize Theorem~\ref{th5} as follows: \begin{theorem} \label{th5+} i) For all positive real numbers $y$, \be U_y0$ such that \be U_y\leq\left(\prod_i\frac {\sum_{\bx_i\in\la_i} e^{-F_i(\bx_i)}} {\mints_{\!\rki} e^{-F_i(\bx_i)} d\bx_i} \right)V_y. \label{ndebd+} \ee \end{theorem} {\em Proof\/}: i) Since $U_y$ is positive and increasing, the right-hand side of~(\ref{prod2}) is greater than \[ \int_{t=y}^\infty e^{-t} U_t dt > U_y \int_{t=y}^\infty e^{-t} dt = e^{-y} U_y \] whence (\ref{amobd+}) follows. ii) As in Theorem~\ref{th4} this is evident upon comparison of the integrals (\ref{prod1}) and~(\ref{prod2}). We can now mimic the proof of Theorem~\ref{thsup0}. (We could also use (\ref{vol+}) and~(\ref{amobd+}) to generalize Theorem~\ref{thsup}, but we would have to worker harder only to obtain the same or slightly worse estimates.) %[Noam:] Unless you want to work it out your way and include %it here as well... Let $b_i$ be the supremum over lattices $\la_i\in\rki$ of \be \biggl (\mints_{\bx_i\in\r^\vhack{k_i}} e^{-F_i(\bx_i)} d\bx_i \biggr) \bigg/ \biggl( \det(\la_i) \sum_{\bx_i \in \la_i} e^{-F_i(\bx_i)} \biggr). \label{bidef} \ee Note that $b_i\geq1$. Then we have: \begin{theorem} \label{thsup1} There exist enough translates of $B(\bone)$ by vectors of~$\rn$ to pack $\rn$ with density at least $2^{-n}\prod_i b_i$. \end{theorem} {\em Proof\/}: Let $\la_i$ be arbitrary lattices in~$\rki$, and $\la$ their direct sum in~$\rn$. Apply Theorem~\ref{th2} to the lattice~$\la$ and the body $B(\{y^{1/\s_i}\})$, and apply a linear transformation to obtain a packing of $B(\bone)$ of density at least $2^{-n}\prod_i b_i - \epsilon$ for $\epsilon$ arbitrarily small. It is easy to see that this $\epsilon$ can be removed by partitioning $\rn$ into ever thicker spherical shells and putting in the $m$-th shell a chunk of the density-$(2^{-n}\prod_i b_i - \epsilon_m)$ packing of $B(\bone)$ for some sequence $\epsilon_m\ra0$, giving the desired density $2^{-n}\prod_i b_i$. {\em Note}\/: As usual with Theorem~2, this packing will in general not be a lattice packing, but by the second part of Theorem~2 we can also obtain a lattice packing whose density is at most smaller by a bounded factor, and even a factor $(1-o(1))$ can be obtained if it can be established as in the proof of Theorem~\ref{lpb} that $\card(\la\cap\open B(\{y^{1/\s_i}\}))\ra\infty$. \section{Open problems} We conclude with three questions suggested by the above work: i) For any distance function~$f$\/ we can only improve on Minkowski-Hlawka once $\s$ exceeds some critical value $\s_0$. In all cases we have computed, $\s_0\geq2$, with equality only when~$f$\/ is equivalent to the Euclidean distance function. Is there any distance function for which $b>1$, giving by our methods essential improvements on Minkowski-Hlawka, for some $\s<2$? ii) If two or more of the $\s_i$ of Section~8 are equal (as happens for the superballs of Sections 2--7), say $\s_1=\s_2=\cdots=\s_j$, we can replace $F_1,\ldots,F_j$ by a single homogeneous function $F=\sum_{i=1}^j F_i$ on $\rk$ with $k=\sum_{i=1}^j k_i$. The ratio~(\ref{bidef}) obtained from this~$F$\/ is certainly no worse than the product of the $b_i$ of the component~$F_i$'s, as may be seen by using lattices $\oplus_{i=1}^j\la_i$; but conceivably the ratio might be increased by using lattices that are not direct sums of this form. We have not found an example where this occurs, but neither can we prove that the optimal lattice must always be a direct sum. %[Noam: any ideas?] iii) Let $g: \rk \ra \r$ and $h: \rmm \ra \r$ be the distance functions of bodies $G$ and $H$ respectively. Consider the Cartesian product body $G \times H \subseteq \rn$, where $n=k+m$, with distance function $\max (g,h)$. It can be lattice packed with density $\dl (G) \dl (H)$ by using the orthogonal sum of closest-packing lattices for $G$ and $H$. Are there bodies $G$, $H$ for which a denser lattice packing of $G \times H$ is possible? Similarly, it is obvious that $\delt (G \times H) \geq \delt (G) \delt (H)$, where $\delt$ denotes the maximum density by a packing of translates. Does the strict inequality ever hold? \vspace{1ex} \noindent{\bf Acknowledgement:} The authors thank B. F. Logan for permission to include his proof of Lemma~\ref{Logan}, and P. M. Gruber for comments concerning the third problem in Section 9. \vspace{1ex} \noindent{\footnotesize By the time of publication the third author's address will be: Department of Mathematics GN-50, University of Washington, Seattle, WA 98195, U.S.A. (e-mail: jar@math.washington.edu).} \begin{thebibliography}{99} \bibitem{Brui} de Bruijn, N.G. {\em Asymptotic Methods in Analysis}, Dover, N.Y., 1981 (reprint). \bibitem{Cassels} Cassels, J.W.S. {\em An Introduction to the Geometry of Numbers}, Springer-Verlag, N.Y., 1959. \bibitem{CandS} Conway, J.H. and Sloane, N.J.A. {\em Sphere Packings, Lattices and Groups}, Springer-Verlag, N.Y., 1987. \bibitem{Erdos} Erd\H{o}s, P., Gruber, P.M. and Hammer, J. {\em Lattice Points}, Pitman Monograph 39, Longman Scientific, with John Wiley \& Sons, N.Y., 1989. \bibitem{GandR} Gradshteyn, I.S. and Ryzhik, I.M. {\em Table of Integrals, Series and Products}, Academic Press, New York, 1980 (Translated from Russian). \bibitem{GandL} Gruber, P.M. and Lekkerkerker, C.G. {\em Geometry of Numbers}, Elsevier, North-Holland, Amsterdam, 1987 (This is an updated version of \cite{Lek}). % \bibitem{Hlawka} Hlawka, E. Zur Geometrie der Zahlen, {\em Math. Zeitschr.}, {\bf 49}, 285-312 (1943). \bibitem{KandL} Kabatiansky, G.A. and Levenshtein, V.I. Bounds for packings on a sphere and in space (in Russian) {\em Problemy Peredachy Informatsii}, {\bf 14} (No. 1, 1978), 3-25; English translation in {\em Problems of information transmission}, {\bf 14} (1978), 1-17. \bibitem{LandS} Leech, J. and Sloane, N.J.A. Sphere packing and error-correcting codes, {\em Canad. J. Math.}, {\bf 23}, 718-745 (1971). \bibitem{Lek} Lekkerkerker, C.G. {\em Geometry of Numbers}, Wolters-Noordhoff, Groningen, 1969. % \bibitem{LandT} Litsin, S.N. and Tsfasman, M.A. Algebraic-geometric and number-theoretic packings of spheres (in Russian), {\em Uspekhi Mat. Nauk}, {\bf 40}, 185-186 (1985). \bibitem{MandO} Mazo, J.E. and Odlyzko, A.M. Lattice points in high-dimensional spheres, {\em Monatsh. Math.}, {\bf 110}, 47-61 (1990). \bibitem{MinkGeom} Minkowski, H. {\em Geometrie der Zahlen}, I. Leipzig, B.G. Teubner, 1896. \bibitem{MinkGessam} Minkowski, H. {\em Gesammelte Abhandlungen}, Chelsea, N.Y. (reprint), 1969. % \bibitem{PandC} Rogers, C.A. {\em Packing and Covering}, Cambridge University Press, 1964. \bibitem{RogersEx} Rogers, C.A. Existence Theorems in the Geometry of Numbers, {\em Ann. Math.} (2), {\bf 48}, 994-1002 (1947). \bibitem{RandS} Rush, J.A. and Sloane, N.J.A. An improvement to the Minkowski-Hlawka bound for packing superballs, {\em Mathematika}, {\bf 34}, 8-18 (1987). \bibitem{Lower} Rush, J.A. A lower bound on packing density, {\em Invent. math.}, {\bf 98}, 499-509 (1989). \bibitem{Thin} Rush, J.A. Thin lattice coverings, (submitted). \bibitem{Cross} Rush, J.A. Constructive packings of cross polytopes, (submitted). \bibitem{Selfdual} Sloane, N.J.A. Self-dual codes and lattices, in Relations Between Combinatorics and Other Parts of Mathematics. {\em Proc. Sympos. Pure Math.}, {\bf 34}, 273-308 (1979). % \bibitem{Recent} Sloane, N.J.A. Recent bounds for codes, sphere packings and related problems obtained by linear programming and other methods. {\em Contemp. Math.}, {\bf 9}, 153-185 (1982). % \bibitem{Terras} Terras, A. {\em Harmonic Analysis on Symmetric Spaces and Applications}, Springer-Verlag, N.Y. (2 volumes) Vol I, 1985 and Vol II, 1988. % \bibitem{Widder} Widder, D.V. {\em The Laplace Transform}, Princeton University Press, 1941. \end{thebibliography} \end{document}