New Korkin-Zolotarev Inequalities

Last update: May 9, 2007

The paper New Korkin-Zolotarev Inequalities by Rudi Pendavingh and Stefan van Zwam gives, together with the accompanying technical report, a systematic way of exploring the cone of outer coefficients of KZ-reduced quadratic forms. Knowledge of this cone has important applications, the most tantalizing of which is the determination of Hermite's constant. This website provides up-to-date information about the progress made on this.

The computer code

Last update: April 27, 2006

The current version of the code does not implement the cutting plane approach hinted at in the paper and report.

The cone of outer coefficients

Information about a cone comes in two guises: vectors that are in the cone, and inequalities valid for the cone (which are described by vectors in the polar cone). A cone is determined completely when the two descriptions coincide. On this site we give quadratic forms that give interesting points in the cone, and inequalities on the quadratic forms that cut off a certain portion. We invite contributions to this survey. Please send any request for a contribution to Stefan van Zwam. A method for transferring the data can then be set up. Please do not send large attachments to the address above. Naturally you will be acknowledged on this page for any contribution you make.

Dimension 3

This situation is completely clear. A generating set for the cone is { (0,0,1),(0,1,3/4),(1,3/4,2/3),(1,8/9,2/3)}. Its polar cone follows from the first and second KZ-inequalities, and is { (1,0,0), (-3,4,0),(0,-3,4),(-2,0,3)}.

Dimension 4

Last update: April 27, 2006

Vectors in the cone:

Inequalities:

Only those that do not follow from lower dimensions are listed. The zip file linked contains a certificate of an approximate version of the inequality listed here. The accompanying file info.txt gives the precision and the version of the software with which this was established.

Dimension 5

Last update: May 4, 2006

Vectors in the cone:

For a vector to be listed here it has to be in some sense extremal, or it must violate an inequality in the polar of the cone spanned by its predecessors.

Inequalities:

Only those that do not follow from lower dimensions are listed. The zip file linked contains a certificate of an approximate version of the inequality listed here. The accompanying file info.txt gives the precision and the version of the software with which this was established. An interesting first question seems to be this: what is the highest value of c such that (0,0,-3,4,0) + c(-1,0,0,0,2) is a valid inequality?

How did this research start?

This research was originally the subject of Stefan's Master thesis. Originally he intended to research ways to speed up the LLL algorithm, but the main idea, splitting the basis in segments and doing local reduction first, was already treated in great detail by Koy and Schnorr. After some wandering through literature he finally settled on reproducing results posed without proof by Novikova. This led to the development of a semidefinite programming formulation. In his thesis he obtained only numerical results. He had not looked into rounding yet. It takes the thesis much longer to get to the point than the paper and report listed above, so it may not be the ideal introduction. On the other hand, it may be a bit more gentle if you just got started with all this.

Other interesting destinations

These websites list many interesting lattices which may help in your research. The first has several other computer programs as well.

Reference: R.A. Pendavingh and S. H. M. van Zwam, New Korkin-Zolotarev Inequalities. Siam J. Optim. Vol. 18, No. 1, pp. 364 - 378 (2007). .pdf file.