New Korkin-Zolotarev Inequalities

R. A. Pendavingh (rudiwin.tue.nl)
S. H. M. van Zwam (svzwamwin.tue.nl)

Abstract: Korkin and Zolotarev showed that if $$\sum_i A_i(x_i-\sum_{j>i} \alpha_{ij}x_j)^2$$ is the Lagrange expansion of a Korkin--Zolotarev reduced positive definite quadratic form, then $A_{i+1}\geq \frac{3}{4} A_i$ and $A_{i+2}\geq \frac{2}{3}A_i$. They showed that the implied bound $A_{5}\geq \frac{4}{9}A_1$ is not attained by any KZ-reduced form. We propose a method to optimize numerically over the set of Lagrange expansions of Korkin--Zolotarev reduced quadratic forms. Applying these methods, we show among other things that $A_{i+4}\geq (\frac{15}{32}-2 \cdot 10^{-5})A_i$ for any KZ-reduced quadratic form, and we give a form with $A_{5}= \frac{15}{32}A_1$. We use the method to find bounds on Hermite's constant, and to compute estimates of the quality of $k$-block KZ-reduced lattice bases.

Keywords: quadratic forms, branch and bound, semidefinite optimization, Hermite's constant, lattice basis reduction

Category 1: Applications -- Science and Engineering

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Other Topics (Other )

Citation: This is a preprint. Final version is published at SIAM Journal of Optimization, Vol. 18, No. 1, pp. 364-378.

Download: [Postscript][PDF]

Entry Submitted: 04/28/2006
Entry Accepted: 04/28/2006
Entry Last Modified: 05/07/2007

Modify/Update this entry