Lattices over Polynomial Rings and Applications to Function Fields

This paper deals with lattices $(L,\mathrm{\parallel }\mathrm{\parallel })$ over polynomial rings, where $L$ is a finitely generated module over $k[t]$, the polynomial ring over the field $k$ in the indeterminate $t$, and $\mathrm{\parallel }\mathrm{\parallel }$ is a discrete real-valued length function on $L{\otimes }_{k[t]}k(t)$. A reduced basis of $(L,\mathrm{\parallel }\mathrm{\parallel })$ is a basis of $L$ whose vectors attain the successive minima of $(L,\mathrm{\parallel }\mathrm{\parallel })$. We develop an algorithm which transforms any basis of $L$ into a reduced basis of $(L,\mathrm{\parallel }\mathrm{\parallel })$. By identifying a divisor $D$ of an algebraic function field with a lattice $(L,\mathrm{\parallel }\mathrm{\parallel })$ over a polynomial ring, this reduction algorithm can be addressed to the computation of the Riemann-Roch space of $D$ and the successive minima of $(L,\mathrm{\parallel }\mathrm{\parallel })$, without the use of any series expansion.