# Representation Redundancy and Structural Complexity in Finite-Field Inversion

arXiv: https://arxiv.org/abs/2609.04583 · HTML: https://mlsanity.com/paper/2609.04583/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 21 references that are in the map.
- First posted on arXiv 4 Sep 2026.

## Builds on (most cited first, 12 of 12)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Theoretical Aspects of Group Equivariant Neural Networks](https://mlsanity.com/paper/2004.05154/) (2020)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs](https://mlsanity.com/paper/2403.15707/) (2024)
- [From Symmetry to Invariance: Learning Galois Equivalent Representations in Finite Fields](https://mlsanity.com/paper/2608.22513/) (2026)

## Abstract (arXiv)

The representation chosen for a mathematical operation can affect both its algebraic form and its empirical learning difficulty. We study this phenomenon for inversion over (mathbb F2n), with field elements expressed in varying ordered (mathbb F2)-bases. We prove that two ordered bases induce the same coordinate inversion map if and only if they belong to the same Galois orbit. Since every orbit has size (n), the correspondence between ordered bases and distinct inversion maps is exactly (n)-to-one. We then analyze three Boolean formulations of inversion. The reference formulation has algebraic degree (n-1) and joint ANF leap (1), the mixed representation formulation has degree (2(n-1)) and joint ANF leap (2), and the complete raw formulation has degree at most (3(n-1)) and joint ANF leap at least (n). Exhaustive computations agree with the theoretical results and bounds in the cases considered. Controlled experiments with multilayer perceptrons show the same ordering in learning difficulty, while Galois orbit redundancy provides only a limited generalization benefit under the tested conditions. These results show that exact redundancy among representations can coexist with changes in Boolean structure and learning behavior when the representation is exposed as part of the input.