{"id":"arxiv/2610.38535","url":"https://arxiv.org/abs/2610.38535","tags":["cs.SC","math.NT"],"score":0,"title":"On the Complexity of Computing with p-adic Lattices","domain":"cs.SC","source":"arxiv","authors":["Pierre Fromonot","Mercedes Haiech","Tristan Vaccon"],"reviews":0,"subject":"cs.SC","summary":"We study the complexity of two fundamental problems attached to p-adic lattices: computing an N-orthogonal basis, and deciding whether a given basis is N-orthogonal. When the norm is supplied through an explicit diagonal representation, both problems are polynomial. However, in the black-box model, where the ultrametric norm N is fixed and only accessible through an evaluation oracle, we prove that both problems require $Ω$(p^{v-1} ) queries in the worst case, where v $\\le$ n is the largest multiplicity of a commensurability class of N and n is the dimension of the ambient vector space. We…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-28","reactions":{}}