PaperlayerView exact revision on arXiv

Source-linked AI summary

Representation Redundancy and Structural Complexity in Finite-Field Inversion

Zheng Zhang, Na Zhang

arXiv:2609.04583v1cs.LGmath.RA

TL;DR

The paper asks how changing coordinates affects redundancy, algebraic structure, and learnability for finite-field inversion. It proves exact Galois-orbit equivalence, analyzes three Boolean formulations, and tests the resulting ordering with exhaustive computations and controlled MLP experiments. Exact redundancy coexists with increased raw-map complexity and only limited generalization gains under the tested conditions.

  • Problem

    The paper examines how much variation among coordinate representations is redundant and how exposing representation variables changes the algebraic structure and learnability of finite-field inversion.

  • Method

    The study characterizes coordinate inversion maps over varying ordered F2-bases, analyzes three Boolean formulations by algebraic degree and joint ANF leap, and evaluates them with exhaustive computations and controlled learning experiments.

  • Results

    The reference, mixed representation, and complete raw formulations show increasing algebraic structure and learning difficulty, while Galois-orbit redundancy yields only modest generalization benefit for n = 3 and no clear benefit for n = 4 under the tested conditions.

  • Takeaways & Limitations

    Exact equivalence among representations does not by itself make the raw joint formulation algebraically simple or easy for a standard learner to use.

  • Takeaways & Limitations

    Exact computations cover n = 3 and n = 4, learning uses a standard MLP without explicit Galois symmetry, and the scaling experiment fixes the number of epochs.

Abstract

from arXiv · show

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.

1 Introduction

The paper separates exact redundancy among coordinate representations from the algebraic complexity of the joint map when representation variables are exposed. For finite-field inversion, it characterizes Galois-orbit redundancy and shows that basis inclusion changes ANF structure across three formulations.

  • Research questions: The study asks how representation choice affects both redundancy among equivalent maps and the algebraic structure of the resulting Boolean joint map.The algebraic question concerns the ANF structure of the map from representation and operand variables to the output, not inversion's computational complexity.
  • Approach: The paper combines exact theoretical characterization, exhaustive finite-case computation, and controlled learning experiments to examine redundancy and representation-dependent structure.The representation space is finite and enumerable for small n, allowing structural quantities to be checked without sampling.
  • Exact representation redundancy: Two ordered bases induce the same coordinate inversion map if and only if they belong to the same Galois orbit.Each orbit contains exactly n bases, yielding an exact n-to-one redundancy between ordered bases and distinct inversion maps.
  • Algebraic complexity under representation change: The reference inversion map has degree n −1, the mixed representation map has degree 2(n −1), and the complete raw map has degree at most 3(n −1).Including the basis matrix at the input transformation stage doubles the algebraic degree relative to the reference formulation.
  • Algebraic complexity under representation change: The joint ANF leap is 1 for the reference map, 2 for the mixed representation map, and at least n for the complete raw map.This measure captures stepwise variable introduction alongside interaction order, complementing algebraic degree.

2 Coordinates over Finite Fields and Galois Orbits

The paper defines inversion in varying ordered F2-bases through change-of-basis coordinates and characterizes exact task equivalence by Galois orbits. Each orbit contains n bases, so ordered bases map to coordinate inversion maps exactly n-to-one.

  • 2.1 Finite-field coordinates and change of basis: A fixed reference basis E defines the baseline coordinate inversion map Jn for F=F2^n.Each field element has unique coordinates in the chosen basis, with inversion extended using the paper’s convention.
  • 2.1 Finite-field coordinates and change of basis: For an ordered basis B, the change-of-basis matrix PB converts B-coordinates to reference coordinates and determines the basis-dependent inversion map.The computation converts the input with PB, applies Jn, and converts the output back with PB^-1.
  • 2.2 Frobenius action and Galois orbits: The Galois group acts componentwise on ordered bases through the Frobenius automorphism, producing the relevant Galois orbits.Because Frobenius is an F2-linear automorphism, it maps ordered F2-bases to ordered F2-bases.
  • 2.2 Frobenius action and Galois orbits: InvB = InvB′ if and only if B′ belongs to the Galois orbit O(B).Thus, equality of coordinate inversion maps is exactly characterized by the Galois action on ordered bases.
  • 2.2 Frobenius action and Galois orbits: Every Galois orbit contains exactly n ordered bases, yielding an exact n-to-one correspondence between ordered bases and distinct coordinate inversion maps.The resulting number of distinct maps is |GLn(F2)|/n, with exact redundancy factor n.

3 Algebraic Complexity of the Inversion Formulations

The paper compares reference, mixed, and complete raw inversion formulations by algebraic degree and joint ANF leap. Exposing the basis transformation increases both measures, while exact representation redundancy remains distinct from joint-map complexity.

  • 3 Algebraic Complexity of the Inversion Formulations: The three formulations are compared using algebraic degree and joint ANF leap, which measure interaction order and newly introduced variables, respectively.The joint ANF leap is defined from the optimally ordered support of all output-coordinate ANFs.
  • 3.1 Algebraic Normal Form and Degree: The reference inversion formulation has algebraic degree n−1.This follows from the binary Hamming weight characterization of finite-field power maps applied to inversion.
  • 3.1 Algebraic Normal Form and Degree: Treating the input matrix P and operand u jointly gives the mixed formulation Jn(Pu), whose algebraic degree is 2(n−1).The input transformation contributes degree two in the joint variables, doubling the reference degree.
  • 3.2 Joint ANF support and joint ANF leap: The complete raw formulation has joint ANF leap at least n, establishing linear growth with field dimension.Unlike the preceding exact values, this result is a lower bound.
  • 3.2 Joint ANF support and joint ANF leap: Exact redundancy concerns basis-fixed function slices, whereas structural complexity concerns the full joint map in (P,u), so redundancy does not imply algebraic simplicity.The paper explicitly distinguishes these properties and does not claim that redundancy causes the observed complexity.

4 Experiments

The experiments combine exhaustive ANF computations with controlled MLP studies to compare three inversion formulations, their algebraic structure, learning behavior, and generalization across Galois orbits. Across the tested cases, the formulations retain the theoretical ordering, while representation redundancy yields only limited performance benefits.

  • 4.1 Experimental setup: The learning experiments use fully connected MLPs with ReLU hidden layers, matched inputs, splits, architecture, and optimization budgets across formulations.The inputs flatten the basis matrix and concatenate it with the operand; outputs are n logits for the target coordinates.
  • 4.2 Experiment 0: Exact ANF computation: Exhaustive computations for n = 3 and n = 4 agree with the theoretical ANF results and show increasing minimum positive monomial degree and total monomial count across the formulations.The complete raw formulation reaches the stated upper bound in both field sizes, making both bounds sharp for these cases.
  • 4.2 Experiment 0: Exact ANF computation: The lifted reference preserves the reference map’s algebraic degree, degree profile, and joint ANF leap.This follows because its ANF contains the same monomials as the reference formulation and no matrix variable appears in those monomials.
  • 4.3 Experiment 1: Learning across the three formulations: The learning ordering is lifted reference > mixed representation > complete raw for both n = 3 and n = 4, including bit accuracy.The lifted reference reaches perfect test accuracy, the mixed formulation is intermediate, and the complete raw formulation is hardest, especially for n = 4.
  • 4.3 Experiment 1: Learning across the three formulations: As algebraic degree and joint ANF leap increase, observed learning accuracy decreases under the tested conditions.The authors report that this empirical pattern is consistent with the exact ANF results for n = 3 and n = 4.
  • 4.4 Experiment 2: Generalization and representation redundancy: Galois-orbit overlap improves mean exact accuracy by 0.0232 for n = 3 but changes it by approximately 0.0002 for n = 4, with no clear benefit at n = 4.The n = 4 differences are smaller than variation across random seeds, so the exact redundancy factor n does not necessarily yield a large test-performance improvement.
  • 4.5 Experiment 3: Scaling with data and model width: With the full training set, increasing width from 128 to 512 raises mixed-formulation exact accuracy from 0.6688 ± 0.0413 to 0.9546 ± 0.0084.The corresponding complete-raw increase is from 0.1655 ± 0.0027 to 0.2566 ± 0.0100, and it remains much harder over the tested range.
  • 4.5 Experiment 3: Scaling with data and model width: The scaling results should be interpreted as a five-epoch training protocol, because training fraction changes the number of optimization steps.Therefore, the effects of additional data cannot be separated completely from the effects of additional optimization.

5 Discussion

The study separates exact representation redundancy from the algebraic structure and learnability of inversion when basis information is exposed. Exact Galois-orbit redundancy does not automatically yield strong generalization, while the three formulations show an ordered relationship between ANF complexity and learning difficulty.

  • Exact redundancy and empirical generalization: Each coordinate inversion task has exactly n basis representations, with equivalence classes given by Galois orbits.This exact task-family property does not imply that learners can identify or exploit the equivalence from raw basis matrices.
  • Exact redundancy and empirical generalization: A modest generalization improvement appears for n = 3, but no clear improvement appears for n = 4 when orbit-related bases occur in both training and test sets.The tested learner is a standard MLP, and the results suggest that explicit representation of the Galois action may be needed for more effective use of redundancy.
  • ANF structure and learning difficulty: The reference formulation is easiest to learn, the mixed representation is intermediate, and the complete raw formulation is hardest under the tested conditions.For n = 3 and n = 4, exact ANF computations assign the largest degree and joint ANF leap to the complete raw formulation, which also has the lowest learning accuracy.
  • ANF structure and learning difficulty: The mixed formulation uses P only for input transformation, whereas the complete raw formulation also converts the output back to the original basis.Theoretical bounds are attained for n = 3 and n = 4, and learning experiments separate the formulations more clearly as training fraction and model width increase.
  • Scope of the evidence: The experiments connect algebraic degree and joint ANF leap with learning behavior but are not direct applications of existing learning guarantees.Joint ANF leap is defined from vector-valued Boolean-map support, while prior staircase and leap results concern Fourier support and specific learning settings.
  • Scope of the evidence: The ANF analysis uses an adjugate-based polynomial extension over the full Boolean matrix space, while learning experiments use only invertible basis matrices.An intrinsic ANF-complexity notion for the restricted domain remains future work.

6 Conclusion

The paper proves an exact Galois-orbit characterization of redundant coordinate representations and quantifies how exposing basis transformations changes inversion’s Boolean structure. Experiments support the theoretical ordering while showing that redundancy alone yields limited generalization gains under the tested conditions.

  • Exact redundancy: Two ordered bases induce the same coordinate inversion map if and only if they belong to the same Galois orbit.Because the Galois action is free, every inversion task has exactly n basis representations.
  • ANF structure: The reference formulation has degree n −1 and joint ANF leap 1, while the mixed formulation has degree 2(n −1) and leap 2.The complete raw formulation has algebraic degree at most 3(n −1) and joint ANF leap at least n.
  • Experiments: Exact computations for n = 3 and n = 4 attain the raw degree and joint ANF leap bounds.Learning accuracy decreases from the lifted reference to the mixed representation and complete raw formulations.
  • Experiments: More training data and model width greatly improve the mixed formulation, while the complete raw formulation remains more difficult over the tested range.Orbit redundancy gives only a modest generalization benefit for n = 3 and no clear benefit for n = 4 under the tested conditions.
  • Limitations: The exact computations reported are limited to n = 3 and n = 4, and the learning experiments use a standard MLP without explicit Galois symmetry.The scaling experiment also fixes the number of epochs, limiting conclusions about additional data and model width.

A Additional exact ANF results

The appendix defines exact ANF-counting quantities for vector-valued Boolean maps and explains how the reported profiles and supports are computed. Counts are obtained coordinate-wise from complete truth tables using the Boolean Möbius transform.

  • ANF computation: The appendix introduces a vector-valued Boolean map with coordinate ANFs as the object whose degree profiles and monomial supports are counted.The displayed definitions organize the analysis around coordinate-level ANF coefficients.
  • ANF counting definitions: For 0 ≤ℓ≤d, Nℓ(G) denotes the total number of ANF monomials of degree ℓ across all output coordinates.A monomial appearing in multiple coordinates is counted once for each coordinate in which it appears.
  • ANF counting definitions: The coordinate-level monomial count sums ANF monomials across output coordinates, preserving repeated appearances by coordinate.This provides the basis for the total counts reported in the appendix.
  • ANF computation: Each output coordinate’s ANF coefficients are recovered from the complete truth table on the ambient Boolean domain using the Boolean Möbius transform.The appendix states that all reported values are exact.

A.1 Degree profiles

The degree-profile results show that representation changes affect the breadth of ANF interactions, not only the maximum degree. For n = 3 and n = 4, the complete raw formulation has especially large coordinate-level and aggregate monomial counts.

  • Degree-profile comparison: The degree profiles show that formulation differences extend beyond the largest degrees to wider monomial degree ranges.The complete raw formulation has no monomial below degree n for either field size.

A.2 Coordinate-level ANF statistics

Coordinate-level ANF statistics show that representation changes substantially alter monomial counts, especially for the complete raw formulation. The observed coordinate-profile equality for the complete raw formulation is limited to the n = 3 and n = 4 computations.

  • The coordinate-level statistics report each coordinate’s degree profile and total ANF monomial count, with entries written as degree: monomial count.
  • For n = 3, total monomial counts are 9, 45, and 168 for the reference, mixed representation, and complete raw formulations, respectively.
  • For n = 3, each complete raw output coordinate has the same degree profile and contains 56 monomials.
  • For n = 4, total monomial counts are 27, 552, and 7008 for the reference, mixed representation, and complete raw formulations, respectively.
  • For n = 4, each complete raw output coordinate has the same degree profile and contains 1752 monomials.
  • The complete raw coordinate-profile equality is observed for n = 3 and n = 4, without a claim for arbitrary n or every reference basis.

A.3 Joint ANF leap verification

Joint ANF leap verification combines theoretical lower bounds with explicit support-set certificates. The resulting exact leaps are 1, 2, and 3 for n = 3, and 1, 2, and 4 for n = 4.

  • The minimum positive monomial degree supplies a lower bound because the first nonempty support set must introduce at least that many variables.
  • Explicit certificate sequences verify that the complete raw lower bound is attained for n = 3 and n = 4.
  • For n = 3, four support sets cover all 12 input variables while introducing at most 3 new variables per step.
  • For n = 4, five support sets cover all 20 input variables, and the final set introduces only 4 new variables.
  • The exact joint ANF leaps are 1, 2, and 3 for n = 3, and 1, 2, and 4 for n = 4.
Loading 2609.04583v1…