Fourier Circuits in Neural Networks: Unlocking the Potential of Large
  Language Models in Mathematical Reasoning and Modular Arithmetic
Jiuxiang Gu Chenyang Li Yingyu Liang Zhenmei Shi Zhao Song Tianyi Zhou
In the evolving landscape of machine learning, a pivotal challenge lies in
deciphering the internal representations harnessed by neural networks and
Transformers. Building on recent progress toward comprehending how networks
execute distinct target functions, our study embarks on an exploration of the
underlying reasons behind networks adopting specific computational strategies.
We direct our focus to the complex algebraic learning task of modular addition
involving $k$ inputs. Our research presents a thorough analytical
characterization of the features learned by stylized one-hidden layer neural
networks and one-layer Transformers in addressing this task.
  A cornerstone of our theoretical framework is the elucidation of how the
principle of margin maximization shapes the features adopted by one-hidden
layer neural networks. Let $p$ denote the modulus, $D_p$ denote the dataset of
modular arithmetic with $k$ inputs and $m$ denote the network width. We
demonstrate that a neuron count of $ m \geq 2^{2k-2} \cdot (p-1) $, these
networks attain a maximum $ L_{2,k+1} $-margin on the dataset $ D_p $.
Furthermore, we establish that each hidden-layer neuron aligns with a specific
Fourier spectrum, integral to solving modular addition problems.
  By correlating our findings with the empirical observations of similar
studies, we contribute to a deeper comprehension of the intrinsic computational
mechanisms of neural networks. Furthermore, we observe similar computational
mechanisms in the attention matrix of the Transformer. This research stands as
a significant stride in unraveling their operation complexities, particularly
in the realm of complex algebraic tasks.