PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zheng Zhang, Na Zhang

arXiv:2608.22513v1cs.LG

TL;DR

The paper asks whether learned multiplication transfers across mathematically equivalent basis representations. It compares ways to expose or recover Galois-orbit structure, especially learned transformations and canonicalization, finding strong transfer in F8 but less reliable constructive procedures in F16.

  • Problem

    The paper studies whether learning multiplication in one coordinate presentation transfers to mathematically equivalent presentations under changes of basis.

  • Method

    The main approach trains a model to predict the Frobenius transformation between equivalent basis matrices and repeatedly composes it to construct canonical representatives for exact matching.

  • Results

    In F8, learned Galois-action transformations support almost exact canonicalization and near perfect downstream multiplication on held-out bases, while F16 procedures are less reliable.

  • Takeaways & Limitations

    Learning an algebraic operation and transferring it across equivalent representations are distinct problems whose success depends on how equivalence structure is presented and used.

  • Takeaways & Limitations

    Exact learned canonicalization is sensitive to entrywise prediction errors and becomes less reliable and more variable in F16 than in F8.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether neural networks learn algebraic structure that transfers across equivalent coordinate representations, rather than merely memorizing finite operation tables. It studies this question in finite-field multiplication using Galois orbits and learned transformations to construct invariant representatives.

  • Motivation: Prior work shows neural networks can learn discrete operations, but it remains unclear whether generalization reflects mathematical structure or finite-table memorization.This question has been studied across modular arithmetic, finite groups, and finite-dimensional algebras.
  • Research question: The paper studies whether multiplication learned in one coordinate presentation transfers to a mathematically equivalent presentation under a change of basis.This shifts the focus from learning structure within one representation to exploiting equivalences across representations.
  • Mathematical setting: Finite-field bases are organized into Galois orbits, and bases in one orbit induce the same coordinate multiplication map.This provides an exact characterization of equivalent representations for separating rule learning from representation transfer.
  • Experimental approach: The experiments compare invariant labels, basis matrices, orbit recognition, and algebraic decomposition as ways to provide or recover orbit structure.They examine both direct identification and relational recognition of equivalent representations.
  • Constructive approach: The main constructive approach learns the Galois action, repeatedly applies it, and uses canonical representatives for multiplication transfer on held-out bases.In F8, learned canonicalization supports near perfect multiplication under exact canonical matching.

2 Mathematical Framework

The mathematical framework represents finite-field multiplication in coordinates relative to arbitrary ordered bases and characterizes equivalent multiplication maps through the Galois action. In F8, 168 ordered bases form 56 orbits, each corresponding to one distinct coordinate multiplication map.

  • Coordinate representations: The finite field F = F2^n is an n-dimensional vector space over F2, so multiplication has a basis-dependent coordinate representation while the underlying operation remains fixed.A polynomially defined reference basis is used to describe other ordered bases.
  • Coordinate multiplication: Each ordered basis B has coordinate vectors and an associated multiplication map mB that returns coordinates for the product xy.The framework defines xB, yB, and the coordinate representation of xy relative to B.
  • Basis changes: The basis matrix PB converts coordinates relative to B into reference-basis coordinates, while P_B^-1 performs the reverse conversion.Multiplication in basis B can therefore be implemented by converting operands, multiplying in reference coordinates, and converting back.
  • F8 specialization: In F8, 168 ordered bases form 56 Galois orbits, corresponding to 56 distinct coordinate multiplication maps.This orbit structure underlies the experimental train–test construction.
  • Galois action: The Frobenius automorphism acts componentwise on ordered bases and partitions them into Galois orbits of exactly n bases.The action is free, so repeated Frobenius applications return to the starting basis after n steps.
  • Equivalent representations: Two ordered bases induce the same coordinate multiplication rule if and only if they belong to the same Galois orbit.Thus, each orbit corresponds to one distinct coordinate multiplication map.

3 Problem Setting

The problem setting uses F8 basis representations and Galois-orbit structure to test multiplication transfer across held-out bases. Models receive different combinations of operands, orbit labels, basis matrices, controls, or relational and constructive objectives.

  • Dataset construction: The F8 experiments use 168 ordered bases grouped into 56 size-three Galois orbits, with an extension to 50 sampled orbits in F16.The three bases in each F8 orbit induce the same coordinate multiplication map.
  • Dataset construction: For each orbit, two bases are used for training and one is held out, yielding 112 training bases and 56 test bases.The split is seed-dependent, so seeds vary both model initialization and the reserved basis.
  • Evaluation target: Held-out bases introduce new representations but not unseen multiplication rules, because the other orbit members and their shared coordinate map appear in training.The evaluation therefore measures transfer across equivalent representations of known rules.
  • Multiplication task: Each training basis contributes the complete coordinate multiplication table from all 64 ordered operand pairs in F2^3.The same 112/56 basis split is used throughout the experiments.
  • Input conditions: Orbit labels directly identify multiplication rules, whereas basis matrices uniquely identify bases but require the model to recover orbit information.The study also compares combined labels and matrices with constant-token and shuffled-matrix controls.
  • Orbit objectives: Separate classification tasks test orbit-label transfer and pairwise recognition of whether two bases belong to the same orbit.Pairwise recognition does not require predicting an orbit label or constructing a canonical representative.
  • Constructive pipeline: The constructive pipeline learns the Frobenius transformation between basis matrices and uses repeated predictions to build canonical representatives for downstream multiplication.Its evaluation excludes held-out matrices as training inputs, although they may appear as targets for training bases from the same orbit.
  • Constructive pipeline: The decomposed multiplication experiment supplies the algebraic decomposition in advance and trains separate models for its two operations.It therefore tests composition of learned operations, not discovery of the decomposition itself.

4 Experimental Setup

The experiments represent finite-field objects as token sequences and train a shared Transformer backbone across multiplication, Galois-action, orbit-recognition, and decomposed-pipeline tasks. Evaluation uses task-specific output heads and metrics, with results aggregated across seeds and exact lookup failures included in downstream accuracy.

  • All experiments use F8 with the 112/56 split of bases unless otherwise stated.
  • Galois-action prediction maps the nine binary entries of PB to the nine binary entries of Pσ(B).
  • The shared architecture has two pre-normalized self-attention layers, residual feedforward blocks, and a flattened one-hidden-layer readout with task-specific output heads.
  • Basis-conditioned and downstream multiplication use eight-class softmax outputs, orbit identification uses 56 classes, and pairwise orbit recognition uses one binary logit.
  • Exact accuracy requires the complete field-element output, while decomposed multiplication additionally reports bit accuracy and exact accuracy requiring all three predicted bits to be correct.
  • Downstream test accuracy includes both multiplication errors and exact-canonical-lookup failures, with an unmatched held-out basis contributing 64 incorrect predictions.

5 Experimental Results and Analysis

Basis-conditioned multiplication is highly sensitive to the information provided and varies substantially across seeds. Pairwise orbit recognition and the learned Galois-action pipeline transfer more reliably to held-out bases than direct orbit identification or basis-conditioned multiplication alone.

  • Basis-conditioned multiplication: Orbit labels alone yield perfect training and held-out accuracy because bases within each orbit share the same coordinate multiplication table.Held-out inputs correspond to multiplication rules already represented during training.
  • Basis-conditioned multiplication: Without orbit labels, operands alone reach 0.3438 exact accuracy, matching most-frequent-target prediction because identical operand pairs can have different orbit-dependent targets.Providing PB without the orbit label produces nearly the same result under the reported architecture and training protocol.
  • Basis-conditioned multiplication: Adding PB to the orbit label reaches 0.6795 ± 0.2659 held-out exact accuracy, below the perfect accuracy obtained from orbit labels and operands alone.The combined condition also reaches 0.7295 ± 0.3038 training exact accuracy and is more variable.
  • Learning dynamics: The true PB condition has the highest mean held-out accuracy among equal-length conditions, exceeding constant tokens by approximately 0.12 and shuffled matrices by approximately 0.10.These differences are small relative to seed variation, and strong runs also occur in both control conditions.
  • Learning dynamics: Held-out accuracy varies significantly across seeds, with some runs at the 0.3438 floor and one true-PB run returning from high intermediate accuracy to the floor.Strong intermediate performance does not necessarily persist to the final epoch.
  • Orbit recognition: Direct orbit identification reaches 0.0179 ± 0.0196 held-out accuracy, approximately the 1/56 ≈ 0.0179 random-guessing level, despite perfect training accuracy.Pairwise orbit recognition instead reaches 0.8688 ± 0.0362 overall held-out accuracy, with 0.9286 ± 0.0196 on positive pairs and 0.8089 ± 0.0546 on negative pairs.
  • Decomposed multiplication: The decomposed pipeline reaches 0.9116 ± 0.0977 held-out exact accuracy and 0.9560 ± 0.0502 bit accuracy on held-out bases.Four of five runs exceed 0.92 exact accuracy, including one perfect run, while Seed 1 reaches 0.7221.
  • Canonicalization and downstream multiplication: The learned Galois transformation achieves 0.9964 ± 0.0071 exact accuracy after one, two, and three applications, producing identical canonical representatives in 279 of 280 orbit evaluations.Four seeds succeed for all 56 held-out bases; Seed 0 succeeds for 55.

6 Discussion

The discussion finds that learned canonicalization can transfer multiplication across equivalent basis representations, but its reliability depends on exact transformation prediction and field size. The conclusions are limited to transfer among representations of known rules, with broader scope and data-separation constraints.

  • Constructive invariance: In F8, learned canonicalization combines predicted Frobenius transformations with exact matching to support near-perfect multiplication on held-out bases.The canonical representative and identifier are constructed deterministically after the learned transformation is predicted.
  • Constructive invariance: Direct Galois-orbit-label prediction remains near chance in F8, whereas canonicalization transfers through structured basis transformations rather than predicting the label directly.The constructed identifier is retrieved by exact matching to the canonical representative.
  • Input conditions: More informative basis matrices do not guarantee better learning: the orbit label alone supports perfect accuracy, while adding or substituting basis-matrix inputs is less reliable.True basis matrices have higher mean held-out accuracy than controls, but seed variation produces overlapping results.
  • Scope and scaling: The experiments test transfer across unseen basis representations of known multiplication rules, not generalization to unseen multiplication rules.Held-out bases belong to Galois orbits represented during training and share their coordinate multiplication tables.
  • Scope and scaling: The learned-action evaluation excludes held-out bases as predictor inputs but may include those matrices as targets for training examples from the same orbit.Thus, it establishes generalization to held-out predictor inputs, not complete exclusion of the matrix from training roles.
  • Scope and scaling: F16 preserves effective explicit-label and pairwise-recognition transfer, but decomposed prediction, repeated composition, and learned canonicalization become less reliable than in F8.The F16 evaluation uses a fixed sample of 50 Galois orbits rather than exhaustive orbit coverage.

7 Conclusion

The paper shows that learning multiplication and transferring it across equivalent basis representations are distinct problems. In F8, orbit information and learned Galois transformations support transfer, while F16 reveals reduced reliability in more demanding settings.

  • In F8, explicit Galois orbit labels support perfect transfer because bases in one orbit share a coordinate multiplication table.
  • Galois orbit identification fails on held-out basis representations, whereas pairwise orbit recognition transfers successfully.
  • A decomposed pipeline combines learned matrix-vector transformation with learned reference-basis multiplication under strict separation of training and evaluation transformations.
  • The learned Galois action generalizes almost perfectly to held-out predictor inputs and preserves two-step composition and three-step cycle closure.
  • In F16, learned constructive procedures become less reliable as the setting grows, while ground-truth canonicalization remains successful.
  • The comparison shows that transfer depends on how equivalence structure is presented and used, and does not automatically extend to more demanding settings.

A.2 Proof of Theorem 1

The theorem proof establishes that equivalent ordered bases induce the same coordinate multiplication map, while the F16 experiment samples Galois orbits and holds out one basis from each sampled orbit.

  • A.2 Proof of Theorem 1: Bases B and C are represented by ordered basis vectors, with coordinate maps defined relative to each basis.
  • A.2 Proof of Theorem 1: If B and C lie in the same Galois orbit, applying a Frobenius automorphism shows that their coordinate multiplication maps are identical.
  • A.2 Proof of Theorem 1: The transition map T between the coordinate systems is an F2-linear bijection that preserves multiplication, making it an F2-algebra automorphism.
  • A.2 Proof of Theorem 1: Conversely, the proof identifies the relevant Frobenius power and concludes that B and C belong to the same Galois orbit.
  • B.1 F16 setting: F16 contains 20,160 ordered F2-bases partitioned into 5,040 Galois orbits of four bases, from which 50 orbits are sampled.
  • B.1 F16 setting: Each sampled F16 orbit contributes three training bases and one held-out basis, yielding 150 training bases and 50 held-out bases.
  • B.1 F16 setting: The sampled orbits and split are fixed across experimental seeds, while results are generally reported over five seeds.

B.2 Basis conditioned multiplication

In F16 basis-conditioned multiplication, orbit labels nearly solve transfer, operands alone remain at the floor, and basis matrices without labels fail to transfer reliably across held-out bases.

  • Orbit labels without basis matrices achieve held-out exact accuracy of 0.9791 ± 0.0301.
  • Without orbit labels or basis matrices, exact accuracy remains at 0.2350 ± 0.0006 because coordinate operand pairs can map to different outputs across orbits.
  • Basis matrices without orbit labels yield training exact accuracy of 0.5805 ± 0.2474 but held-out exact accuracy of 0.2576 ± 0.0439.
  • Figure 2 compares held-out exact-accuracy trajectories for three equal-length conditions against the operands-alone baseline of 0.2350.
  • The true basis-matrix condition has the lowest mean held-out accuracy and greatest variation, while constant tokens and shuffled matrices have higher means but remain seed-sensitive.
  • Differences between F16 and F8 cannot be attributed solely to field or matrix dimension because orbit coverage, dataset size, split variation, and training schedule also differ.

B.3 Orbit recognition

In F16, pairwise orbit recognition transfers strongly to held-out bases, whereas direct orbit identification transfers poorly; decomposed multiplication is possible but highly seed-dependent.

  • Orbit identification: Direct orbit identification reaches perfect training accuracy but only 0.1720 ± 0.0299 held-out accuracy, above the 1/50 chance level of 0.0200.
  • Orbit identification: The orbit-identification gap concerns a new basis representation from each known orbit, not new classes or unseen orbits.
  • Pairwise orbit recognition: Pairwise orbit recognition achieves 0.9997 ± 0.0007 training accuracy and 0.9093 ± 0.0274 held-out accuracy.
  • Pairwise orbit recognition: Held-out pairwise accuracy is higher for positive pairs, at 0.9667 ± 0.0193, than negative pairs, at 0.8520 ± 0.0396.
  • Comparison with F8: Mean held-out pairwise accuracy is approximately 0.87 in F8 and 0.91 in F16, with positive-pair accuracy exceeding negative-pair accuracy in both fields.
  • Decomposed multiplication: The decomposed multiplication pipeline reaches 0.9008 exact accuracy for one seed, but the remaining seeds range from 0.0586 to 0.2338.
  • Decomposed multiplication: The mean held-out multiplication accuracy is 0.3106 ± 0.3006, reflecting widely different outcomes across seeds.
  • Decomposed multiplication: The matrix-vector module is the principal limitation in F16 because it transforms both operands and converts the product back to the held-out basis.

B.5 Learning the Galois action

In F16, the learned transformation captures individual matrix entries well but generalizes poorly when exact full-matrix Galois actions and cycle closure are required. Training fits the transformations, yet held-out exact accuracy remains low and weaker than in F8.

  • Evaluation setup: The evaluation tests one-step prediction, two- and three-step composition, and four-step cycle closure on 50 held-out basis matrices after training on 150 bases.The four-step cycle corresponds to the order-four Galois group Gal(F16/F2).
  • Held-out prediction: Held-out bit accuracy reaches 0.9295 ± 0.0096, while exact 4 × 4 matrix accuracy after one application is 0.3280 ± 0.0722.Most entries are correct, but a few errors often prevent exact matrix recovery.
  • Held-out prediction: Exact accuracy rises from 0.3280 after one application to 0.4280 after four, but fewer than half of inputs return exactly to the original basis.The stepwise increase reflects trajectories reaching the correct orbit position after earlier errors, not reliable reproduction of the full action.
  • Training and held-out behavior: Training exact accuracy reaches 1.0 within approximately 20 epochs for every seed, whereas held-out one-step exact accuracy ranges from 0.2200 to 0.4400.The contrast indicates a large generalization gap rather than failure to fit the training transformations.
  • Comparison with F8: F16 generalizes less reliably than F8: individual matrix-entry prediction remains strong, but exact matrix prediction, repeated composition, and cycle closure are much weaker.In F8, one-step prediction, repeated composition, and three-application cycle closure are nearly exact.

B.6 Canonicalization and downstream multiplication

In F16, learned canonicalization enables downstream multiplication but is substantially less reliable than exact canonicalization. Hamming-distance recovery improves held-out accuracy when exact canonical lookup fails, while errors in canonical construction and downstream modeling remain limiting factors.

  • Exact canonical matching and downstream multiplication: Learned canonicalization achieves a 0.6720 ± 0.0652 exact canonical match rate and 0.7253 ± 0.1382 primary held-out exact multiplication accuracy.The downstream multiplication model reaches 0.9065 ± 0.1367 training exact accuracy.
  • Recovery using Hamming distance: Hamming-distance recovery increases downstream held-out exact accuracy from 0.7253 ± 0.1382 to 0.8014 ± 0.1269.The recovery procedure selects the stored representative with the smallest Hamming distance when exact lookup fails.
  • Ground truth canonicalization: Ground truth canonicalization reaches a 1.0000 exact match rate and 0.9728 ± 0.0221 downstream exact accuracy on both training and held-out sets.The remaining error is attributed to the downstream multiplication model rather than canonical lookup.
  • Behavior across seeds: Across five seeds, Hamming-distance recovery improves every learned-canonicalization run, but ground truth canonicalization remains more accurate for all seeds.Learned canonicalization shows greater variation, with Seed 4 producing the lowest learned downstream training and primary held-out accuracy.
  • Comparison with F8: Canonicalization is less reliable in F16 than F8, where learned representatives almost always match exactly and primary downstream multiplication is nearly perfect.In F16, primary downstream multiplication is lower and more variable.
  • Limitation: The main limitation is reliably constructing exact canonical representatives from the learned Galois action, with downstream multiplication errors also contributing to final performance.Exact canonical representatives still support accurate downstream multiplication in F16 under ground truth canonicalization.

C.1 Basis conditioned multiplication

Basis-conditioned multiplication succeeds when supplied with the Galois orbit label, while basis matrices alone or no orbit information do not provide stable transfer. Orbit identification also generalizes poorly despite perfect training accuracy, whereas pairwise orbit recognition performs well on balanced held-out pairs.

  • Baseline conditions: The Galois orbit label without PB reaches perfect training and held-out exact accuracy across seeds, while providing neither label nor PB remains at the accuracy floor.Providing PB without the label fails to produce stable improvement, although some seeds show temporary increases.
  • Equal-length conditions: With equal sequence length, true basis matrices, constant tokens, and shuffled matrices show substantially different loss and accuracy trajectories across seeds.Several runs remain at the floor; final accuracies are reported in Table 4.
  • Orbit recognition: Galois orbit identification reaches perfect training accuracy rapidly, but held-out accuracy remains near the 1/56 chance level.Pairwise orbit recognition instead achieves high held-out accuracy on the balanced pair set.
  • Decomposed multiplication: The decomposed multiplication pipeline trains a matrix-vector module on a strictly filtered transformation set and a reference-basis multiplication module on the complete fixed-basis multiplication table.Both modules reach high training exact accuracy across seeds, while complete-pipeline held-out performance is reported separately.
  • Training and evaluation reporting: The reported figures separately track training histories for decomposed multiplication, learned Galois action, canonicalization, and downstream multiplication, with held-out outcomes reported in corresponding tables.The canonicalization pipeline also reports exact lookup and Hamming-distance recovery results separately.
Loading 2608.22513v1…