Representation Redundancy and Structural Complexity in Finite-Field Inversion

Zheng Zhang; Na Zhang

cs.LGSep 4, 2026

Representation Redundancy and Structural Complexity in Finite-Field Inversion

Authors: Zheng Zhang, Na Zhang

Organizations: Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA.

Abstract

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.

Figures & tables

$n$	Formulation	Degree	Min. positive degree	Joint leap	$N(G)$
3	reference	2	1	1	9
3	mixed representation	4	2	2	45
3	complete raw	6	3	3	168
4	reference	3	1	1	27
4	mixed representation	6	2	2	552
4	complete raw	9	4	4	7008

Table 1: Exact ANF statistics for the three formulations. Here

N(G)

counts ANF monomials across output coordinates with multiplicity;

|\mathcal{A}(G)|

is reported in Table 8 .

Figure 1: Held-out exact accuracy for the lifted reference, mixed representation, and complete raw formulations. Rows correspond to $n=3,4$ , and each line represents one of five random seeds.

$n$	Formulation	Exact accuracy	Bit accuracy
3	reference	$1.0000\pm 0.0000$	$1.0000\pm 0.0000$
3	mixed representation	$0.6274\pm 0.0367$	$0.8304\pm 0.0205$
3	complete raw	$0.2661\pm 0.0378$	$0.6079\pm 0.0226$
4	reference	$1.0000\pm 0.0000$	$1.0000\pm 0.0000$
4	mixed representation	$0.5905\pm 0.0477$	$0.8385\pm 0.0154$
4	complete raw	$0.1528\pm 0.0031$	$0.5928\pm 0.0026$

Table 2: Final test performance across the three formulations under matched conditions. Results are means

\pm

sample standard deviations over five random seeds.

$n$	Split	Exact accuracy	Bit accuracy
3	random basis	$0.3089\pm 0.0250$	$0.6388\pm 0.0180$
3	orbit disjoint	$0.2857\pm 0.0096$	$0.6284\pm 0.0211$
4	random basis	$0.1591\pm 0.0035$	$0.5980\pm 0.0022$
4	orbit disjoint	$0.1589\pm 0.0040$	$0.5974\pm 0.0032$

Table 3: Generalization under random-basis and Galois-orbit-disjoint splits for the complete raw formulation. Results are means

\pm

sample standard deviations over ten random seeds.

Figure 2: Mean held-out exact accuracy at $n=4$ across model widths and training fractions. Error bars show sample standard deviations over four seeds.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

$n$	Formulation	Degree profile $\ell:c$
3	reference	$1:6,\;2:3$
3	mixed representation	$2:18,\;3:9,\;4:18$
3	complete raw	$3:24,\;4:66,\;5:42,\;6:36$
4	reference	$1:10,\;2:12,\;3:5$
4	mixed representation	$2:40,\;3:48,\;4:164,\;5:180,\;6:120$
4	complete raw	$4:168,\;5:792,\;6:1440,\;7:2280,\;8:1608,\;9:720$

Appendix

Table 4: Complete ANF degree profiles. Counts are summed over the output coordinates.

Formulation	Output	Degree profile $\ell:c$	Monomials
reference	$0$	$1:3,\;2:1$	4
reference	$1$	$1:1,\;2:1$	2
reference	$2$	$1:2,\;2:1$	3
mixed representation	$0$	$2:9,\;3:3,\;4:6$	18
mixed representation	$1$	$2:3,\;3:3,\;4:6$	12
mixed representation	$2$	$2:6,\;3:3,\;4:6$	15

Appendix

Table 5: Coordinate-level ANF statistics for

n=3

Formulation	Output	Degree profile $\ell:c$	Monomials
reference	$0$	$1:4,\;2:2,\;3:2$	8
reference	$1$	$1:1,\;2:4,\;3:1$	6
reference	$2$	$1:2,\;2:3,\;3:1$	6
reference	$3$	$1:3,\;2:3,\;3:1$	7
mixed representation	$0$	$2:16,\;3:8,\;4:32,\;5:72,\;6:48$	176
mixed representation	$1$	$2:4,\;3:16,\;4:52,\;5:36,\;6:24$	132

Appendix

Table 6: Coordinate-level ANF statistics for

n=4

$n$	Step	Support set	Newly introduced variables	Count
3	1	$\{p_{01},p_{10},u_{0}\}$	$\{p_{01},p_{10},u_{0}\}$	3
3	2	$\{p_{00},p_{11},u_{1}\}$	$\{p_{00},p_{11},u_{1}\}$	3
3	3	$\{p_{12},p_{20},u_{2}\}$	$\{p_{12},p_{20},u_{2}\}$	3
3	4	$\{p_{02},p_{21},p_{22},u_{2}\}$	$\{p_{02},p_{21},p_{22}\}$	3
4	1	$\{p_{02},p_{10},p_{33},u_{3}\}$	$\{p_{02},p_{10},p_{33},u_{3}\}$	4
4	2	$\{p_{03},p_{11},p_{32},u_{2}\}$	$\{p_{03},p_{11},p_{32},u_{2}\}$	4

Appendix

Table 7: Explicit joint ANF leap certificates for the complete raw formulation. Each listed support set belongs to

\mathcal{A}(f_{\mathrm{raw}})

$n$	Formulation	$\|\mathcal{A}(G)\|$	Joint ANF leap	Certificate length
3	reference	6	1	3
3	mixed representation	36	2	6
3	complete raw	168	3	4
4	reference	14	1	4
4	mixed representation	368	2	10
4	complete raw	6504	4	5

Appendix

Table 8: Exact verification of the joint ANF leap. The column

|\mathcal{A}(G)|

gives the cardinality of the deduplicated joint ANF support.

Boolean Function Learning

Boolean function learning studies how to infer rules mapping binary inputs to outputs from examples or queries, with guarantees on accuracy and efficiency.

See all 36 papers

From Symmetry to Invariance: Learning Galois Equivalent Representations in Finite Fields
Aug 23, 2026Zheng Zhang, Na ZhangInvariant Representation Learning Equivariant Representation Learning
Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA
Grokking Finite-Dimensional Algebra
Feb 23, 2026Pascal Jr Tikeng Notsawo, Guillaume Dumas, Guillaume RabusseauGrokking Neural Network Generalization
Université de Montréal · Mila, Montréal · CHU Sainte-Justine Research Center, Montréal +1
The Order Is The Message
Mar 24, 2026Jordan LeDouxData-Efficient Learning Training Data Curation
Independent Researcher

Aug 23, 2026J/K move · Enter open · S save

From Symmetry to Invariance: Learning Galois Equivalent Representations in Finite Fields

Zheng Zhang, Na Zhang

Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA

Invariant Representation Learning Equivariant Representation Learning Transfer Learning

Open paper AskPDF arXiv

Neural networks can learn algebraic operations from finite examples, but it remains unclear whether this ability transfers across mathematically equivalent representations of the same operation. We study this question through multiplication in finite fields under changes of basis. The Galois action organizes basis representations into orbits, and bases in the same orbit induce the same coordinate multiplication map. This structure allows us to separate learning multiplication from transferring it to basis representations that are not used for training. We examine several ways of providing or recovering the relevant orbit structure, including invariant labels, basis matrices, orbit recognition, and algebraic decomposition. Our main approach trains a model to predict the Galois action between basis representations. Repeated applications of the learned transformation are then used to construct a canonical representative for each orbit, which supports multiplication on held-out bases through exact canonical matching. This provides a concrete mechanism for converting a learned algebraic symmetry into an invariant representation that can be used for transfer.

Abstract

Boolean Function Learning

Explore similar work

From Symmetry to Invariance: Learning Galois Equivalent Representations in Finite Fields

Grokking Finite-Dimensional Algebra

The Order Is The Message