Reconstructing Rational Functions on Finite Abelian Groups with Higher Autocorrelations

Summary · qwen2.5:32b

The paper presents an algorithm for reconstructing rational-valued functions on finite Abelian groups from their higher-order autocorrelations, proving that autocorrelations up to order $3r+3$ are sufficient for reconstruction up to translation, where $r$ is the group's rank. This work has implications for various fields including X-ray crystallography and computer vision systems. The study also identifies a sharp upper bound on the separating degree of the regular representation in terms of the group’s rank, highlighting that functions are not determined by autocorrelations up to order $3r+2$.

Excerpt

arXiv:2503.21022v2 Announce Type: replace-cross Abstract: The higher-order autocorrelations of integer-valued or rational-valued functions on finite Abelian groups appear naturally in X-ray crystallography, and have applications in computer vision systems, correlation tomography, correlation spectroscopy, and pattern recognition. In this paper, we consider the problem of reconstructing a rational-valued function on finite Abelian groups from its higher-order autocorrelations. We describe an explicit reconstruction algorithm, and prove that the autocorrelations up to order $3r+3$ are always sufficient to determine the data up to translation, where $r$ is the rank of the group. We also provide examples of rational-valued functions on finite Abelian group which are not determined by their autocorrelations up to order $3r+2$. In particular, we provide a sharp upper bound on the separating degree of the regular representation of a finite Abelian group in terms of its rank.