Skip to content
DraconiticResearch
Search Sources API
186,631 studies31 sourcesUpdated 45 min ago
PreprintCC BY 4.0HAL

On the Complexity of Computing with p-adic Lattices

  • Pierre Fromonot
  • Mercedes Haiech
  • Tristan Vaccon
Open at sourcePDFDOICite

Abstract

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 ≤ n is the largest multiplicity of a commensurability class of N and n is the dimension of the ambient vector space. We then analyse the optimality of these bounds by providing explicit algorithms. Our results answer formally an open question of Zhang, Deng and Wang and refine the recent results of Duan and Wu by providing pointwise query bounds depending on the norm's structure, in addition to uniform bounds.

Related

  1. The complexity of computing the covering radius of a Euclidean lattice
    Frank Vallentin
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  2. Coordinate systems and maximal order complexity in Banach lattices
    A. Avilés, C. Rosendal, M. A. Taylor +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  3. The Computational Complexity of the Ungar Games on Distributive Lattices
    Kengo Hashimoto
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On Special Arithmetic Gamma Values and Thakur's Gauss Sums: From ∞-adic to v-adic
    Ting-Wei Chang
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Parallel transport for Higgs bundles over p-adic curves
    Daxin Xu
    Mathematische AnnalenPeer-reviewedLicence not statedFull text8 citedGeometry & topologyOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{fromonot2026complexity,
  title = {{On the Complexity of Computing with p-adic Lattices}},
  author = {Pierre Fromonot and Mercedes Haiech and Tristan Vaccon},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38535},
  eprint = {2610.38535},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05830370v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Complexity of Computing with p-adic Lattices
AU  - Pierre Fromonot
AU  - Mercedes Haiech
AU  - Tristan Vaccon
PY  - 2026
DA  - 2026/10/27
PB  - HAL
DO  - 10.48550/arxiv.2610.38535
UR  - https://hal.science/hal-05830370v1
AB  - 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 ≤ n is the largest multiplicity of a commensurability class of N and n is the dimension of the ambient vector space. We then analyse the optimality of these bounds by providing explicit algorithms. Our results answer formally an open question of Zhang, Deng and Wang and refine the recent results of Duan and Wu by providing pointwise query bounds depending on the norm's structure, in addition to uniform bounds.
ER  -