New Korkin-Zolotarev Inequalities

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.


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



View New Korkin-Zolotarev Inequalities