  Sphere packings in high dimensions interest mathematicians and physicists and
have direct applications in communications theory. Remarkably, no one has been
able to provide exponential improvement on a 100-year-old lower bound on the
maximal packing density due to Minkowski in $d$-dimensional Euclidean space
$\Re^d$. The asymptotic behavior of this bound is controlled by $2^{-d}$ in
high dimensions. Using an optimization procedure that we introduced earlier
\cite{To02c} and a conjecture concerning the existence of disordered sphere
packings in $\Re^d$, we obtain a provisional lower bound on the density whose
asymptotic behavior is controlled by $2^{-0.7786... d}$, thus providing the
putative exponential improvement of Minkowski's bound. The conjecture states
that a hard-core nonnegative tempered distribution is a pair correlation
function of a translationally invariant disordered sphere packing in $\Re^d$
for asymptotically large d if and only if the Fourier transform of the
autocovariance function is nonnegative. The conjecture is supported by two
explicit analytically characterized disordered packings, numerical simulations
in low dimensions, known necessary conditions that only have relevance in very
low dimensions, and the fact that we can recover the forms of known rigorous
lower bounds. A byproduct of our approach is an asymptotic lower bound on the
average kissing number whose behavior is controlled by $2^{0.2213... d}$, which
is to be compared to the best known asymptotic lower bound on the individual
kissing number of $2^{0.2075... d}$. Interestingly, our optimization procedure
is precisely the dual of a primal linear program devised by Cohn and Elkies
\cite{Co03} to obtain upper bounds on the density, and hence has implications
for linear programming bounds.
