{"id":"arxiv/2610.08280","url":"https://arxiv.org/abs/2610.08280","tags":["cs.DS","math.GR"],"score":0,"title":"Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups","domain":"cs.DS","source":"arxiv","authors":["Nader H. Bshouty"],"reviews":0,"subject":"cs.DS","summary":"We study isomorphism decision and basis construction for finite Abelian groups of known order $n$. We measure complexity by the number of additions performed in the groups and by the total running time. We give a randomized isomorphism decision algorithm that performs $\\tilde O(n^{1/4})$ group additions and runs in $\\tilde O(n^{1/4})$ time. This improves the $\\tilde O(\\sqrt n)$ upper bound of Chen and Fu and matches Bshouty $Ω(n^{1/4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2/3$ requires $Ω(\\sqrt n)$ group additions…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}