Metraipolis › archive › dc_06ccabaad318

Representation Redundancy and Structural Complexity in Finite-Field Inversion — arXiv:2609.04583

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.04583
License (as archived)
CC0-1.0
Archived
2026-10-16T22:57:55.654Z
SHA-256 of the archived text
032effa04c364115f3c17f67f64ec9f680a65e4e5cd029e3a448bb5da9a7dbb2
Stable URL of this page
https://metraipolis.com/documento/dc_06ccabaad318

How to cite

Representation Redundancy and Structural Complexity in Finite-Field Inversion — arXiv:2609.04583 — arXiv (en), https://arxiv.org/abs/2609.04583 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_06ccabaad318 (Metraipolis archive dc_06ccabaad318, sha256 032effa04c364115f3c17f67f64ec9f680a65e4e5cd029e3a448bb5da9a7dbb2)
BibTeX
@misc{dc06ccabaad318,
  title = {Representation Redundancy and Structural Complexity in Finite-Field Inversion — arXiv:2609.04583},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04583},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_06ccabaad318; sha256 032effa04c364115f3c17f67f64ec9f680a65e4e5cd029e3a448bb5da9a7dbb2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04583. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 F_{2^n}\), with field elements expressed in varying ordered \(\mathbb F_2\)-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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-07 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Rings and Algebras (math.RA).
Pagina del lavoro: https://arxiv.org/abs/2609.04583 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T22:31:32.176Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).