  In this work, we formally prove that, under certain conditions, if a neural
network is invariant to a finite group then its weights recover the Fourier
transform on that group. This provides a mathematical explanation for the
emergence of Fourier features -- a ubiquitous phenomenon in both biological and
artificial learning systems. The results hold even for non-commutative groups,
in which case the Fourier transform encodes all the irreducible unitary group
representations. Our findings have consequences for the problem of symmetry
discovery. Specifically, we demonstrate that the algebraic structure of an
unknown group can be recovered from the weights of a network that is at least
approximately invariant within certain bounds. Overall, this work contributes
to a foundation for an algebraic learning theory of invariant neural network
representations.
