- 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/2006Entry Accepted: 04/28/2006Entry Last Modified: 05/07/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.