Optimization Online


New Korkin-Zolotarev Inequalities

R. A. Pendavingh (rudi***at***win.tue.nl)
S. H. M. van Zwam (svzwam***at***win.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society