Properties of lattices -- A semidefinite programming approach

Lattices and quadratic forms have been studied for hundreds of years. We present some clas-sical results, with an emphasis on the methods of Korkin and Zolotarev [KZ73], as described by Ryshkov and Baranovskii [RB79]. We introduce a semidenite programming formulation that is a relaxation of the denition of a KZ-reduced quadratic form, and describe a branch-and-bound technique to approximate KZ-reduced forms as closely as desired. This formulation is then applied to nd minimal nite descriptions of KZ-reduced bases (verifying and improving on the results of Novikova [Nov83]) and to nd linear bounds on the outer coecients of a KZ-reduced form. An improved bound is found numerically for the fth outer coecient, which gives a better quality estimate for Schnorr's block KZ-reduction [Sch87]