  


New KorkinZolotarev Inequalities
R. A. Pendavingh (rudiwin.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 KorkinZolotarev 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 KZreduced form. We propose a method to optimize numerically over the set of Lagrange expansions of KorkinZolotarev 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 KZreduced 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 KZreduced 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 (Semidefinite 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. 364378. Download: [Postscript][PDF] Entry Submitted: 04/28/2006 Modify/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  