On the decomposition of lattices
Boris Hemkemeier, Frank Vallentin · 1998
. A lattice in euclidean space which is an orthogonal sum of nontrivial sublattices is called decomposable. We present an algorithm to construct a lattice's decomposition into indecomposable sublattices. Similar methods are used to prove a covering theorem for generating systems of lattices and to speed up variations of the LLL algorithm for the computation of lattice bases from large generating systems. 1. INTRODUCTION Let L be a lattice on euclidean n-dimensional space (V; (\\Gamma; \\Gamma)); i.e. L = Zb 1 + : : : + Zbn for a basis fb 1 ; \\Delta \\Delta \\Delta ; b n g of V: L is called integral if (b i ; b j ) 2 Z holds for all 1 6 i; j 6 n: Definition 1.1. A nontrivial lattice L on V is called decomposable if there exist (proper) sublattices L 1 ; L 2 ae L such that L = L 1 \\Phi L 2 and (L 1 ; L 2 ) = 0; otherwise indecomposable. Throughout this paper we denote an inner direct, orthogonal sum with \\Phi: The norm of a shortest nonzero lattice vector in L is called min L: For each...