On p-adic Gram–Schmidt Orthogonalization Process

Abstract

In his famous book “Basic Number Theory”, Weil proved several theorems about the existence of norm-orthogonal bases in finite-dimensional vector spaces and lattices over local fields. In this paper, we transform Weil’s proofs into algorithms for finding out various norm-orthogonal bases. These algorithms are closely related to the recently introduced closest vector problem (CVP) in p-adic lattices and will terminate within finitely many steps. To the best of our knowledge, these are the first algorithms for computing norm-orthogonal bases in p-adic spaces, which can be viewed as p-adic analogues of Gram–Schmidt orthogonalization process in Euclidean spaces. Furthermore, we show that, given any norm, there is an orthogonal basis with respect to this norm in any p-adic lattice of rank two. This is a completely different phenomenon comparing with Euclidean lattices and we conjecture that the same phenomenon holds in p-adic lattices of arbitrary rank.

Keywords

Orthogonalization / p-adic lattice / local field / CVP / LVP