Given a lattice $L \subseteq \mathbb{Q}^n$ we can define the height of a given element $v = (v_1,\ldots,v_n)\in L$ to be $$ \operatorname{ht}(v) = \sum_{i=1}^n \operatorname{ht}(v_i)$$ where as usual the height of an individual rational number $p/q$ is given by $$ \operatorname{ht}(p/q) := \max(|p|,|q|)$$ provided $p/q$ is written in lowest terms. Does there exist an algorithm which, given a basis for the lattice $L$, will return an element of $L$ of low height.

More informally I am interested in knowing whether there exists a systematic way of producing elements in a rational lattice with relatively simple entries (i.e. the entries are suppose to be rational numbers of small height compared to the entries of the basis elements). Ideally I would of course like to find the element with simplest possible entries, but any thoughts on the matter/partial results would be of interest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.