Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

Xiaoyu Li

cs.LGOct 13, 2026

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

Authors: Xiaoyu Li

Organizations: University of New South Wales

Abstract

We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$ . After a sample on $A$ , the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$ , and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups $A_5$ and $S_5$ of the quintic they are $2<3$ and $3<4$ , and $A_5$ is the smallest group with a gap. For the Galois group $S_n$ of the general equation of degree $n$ , they coincide exactly when $n\le 4$ , i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group $\mathrm{PSL}(2,8)$ has no gap. For linear, orthogonal and unitary maps of $\mathbb R^d$ or $\mathbb C^d$ both dimensions equal $d$ , and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.

Figures & tables

Figure 1: Overview. (a) Learning an automorphism

\sigma

L=\mathbb{Q}(\sqrt{2},\sqrt{3})

over

\mathbb{Q}

from examples

(\alpha,\sigma\alpha)

. After the example

\sqrt{2}\mapsto-\sqrt{2}

, the consistent hypotheses form a coset of the pointwise stabilizer

G_{(A)}=\Gal(L/\mathbb{Q}(\sqrt{2}))

of the sample set

A=\{\sqrt{2}\}

; the forced labels are exactly those of the elements of its fixed field

\mathbb{Q}(\sqrt{2})

(green), for instance

1+\sqrt{2}\mapsto 1-\sqrt{2}

, while

\sqrt{3}

keeps the

[\mathbb{Q}(\sqrt{2})(\sqrt{3}):\mathbb{Q}(\sqrt{2})]=2

candidate labels

\pm\sqrt{3}

(red; Lemmas 3.1 and 5.2 ). (b) Learning dimensions as invariants of a group class with finite orbits and of the Galois group

\Gamma

of a finite Galois extension

L/K

of a countable field with

L\neq K

( Theorems 3.3 , 5.2 , 6.1 , 7.1 and 4.3 ). The height, the irredundant length and the base size are defined in Definition 2.6 ;

\mu(\Gamma)

is the largest size of an independent subset of

\Gamma

\ell(\Gamma)

the length of a longest subgroup chain, and

N(\Gamma)

the coset-cube number ( Sections 5 and 7 ). On nondegenerate classes (some element fixes one domain point and moves another) every ERM is rate-optimal in the realizable model among deterministic learners ( Theorem 4.1 ); its agnostic sample complexity is within a factor

O(\dimDS/\dimN)

, the ratio of the DS and Natarajan dimensions, of the lower bound of Daniely et al. (2015) ( Proposition 4.3 ). (c) For the Galois group

S_{n}

of the general equation of degree

n

over a countable field, the DS dimension is

n-1

, and the Natarajan dimension equals it exactly when

n\leq 4

; in characteristic zero these are the degrees in which the equation is solvable by radicals ( Theorems 7.2 and 7.3 ). Squares are proved values; for

9\leq n\leq 12

the bars show the open range from

\lfloor 3n/4\rfloor

n-2

Panel of Figure 2 — Figure 2: Commuting and non-commuting moves. An edge labeled $s_{i}$ joins two words that differ only in coordinate $i$ ; $s_{i}$ maps each word to its unique $i$ -neighbor ( Definition 8.1 ). Left: on a Natarajan square the two moves commute and generate $C_{2}\times C_{2}$ , where $C_{n}$ is the cyclic group of order $n$ . Right: the restriction of the $S_{3}$ class to $(1,2)$ ( Section 3 ). Every word has exactly one neighbor in each coordinate (the pseudo-cube is two-fibered ), so $\dimDS=2$ , but the moves generate $S_{3}$ and the hexagon contains no Natarajan square. By Theorem 8.2 (d), a two-fibered pseudo-cube is a union of Natarajan cubes exactly when its moves commute.

Learning notion	Invariant of $(G,X)$	$\Gamma=\Gal(L/K)$ on $L$	$S_{n}$ on $[n]$	$\Gamma\cong S_{n}$	Result
Labels forced by a sample on $A$	$\cl_{X}(A)=\Fix(G_{(A)})\cap X$	$K(A)$	$A$ if $\|A\|\leq n-2$ ; else $[n]$	$K(A)$	3.1 , 5.2
Labels at $x$ consistent with the sample	$\|G_{(A)}\,x\|$	$[K(A)(x):K(A)]$	$n-\|A\|$ if $x\notin A$	$[K(A)(x):K(A)]$	3.1 , 5.2
DS dimension	height $\mathsf{H}_{X}(G)$	$\mu(\Gamma)$	$n-1$	$n-1$	3.3 , 5.2
$k$ -DS dimension	$k$ -height $\mathsf{H}^{k}_{X}(G)$	–	$n-k$	–	3.3
Littlestone dimension	$\mathsf{I}_{X}(G)$	$\ell(\Gamma)$	$n-1$	$\lceil 3n/2\rceil-b(n)-1$	3.3 , 5.2
Teaching dimension	$\mathsf{b}_{X}(G)$	$1$	$n-1$	$1$	3.3 , 5.2

Table 1: The dictionary between learning notions and Galois invariants. The DS and

k

-DS rows assume ( F ), which holds in the last three columns. In the Galois columns,

L/K

is a finite Galois extension of a countable field,

A\subseteq L

is finite, the teaching row assumes

\Gamma\neq 1

\mu

is the largest size of an independent subset of

\Gamma

(not necessarily generating) and

\ell

the length of a longest subgroup chain ( Section 5 );

b(n)

is the number of ones in the binary expansion of

n

. The

S_{n}

columns assume

n\geq 2

, and the

k

-DS entry assumes

1\leq k\leq n-1

( Example 3.6 ). A dash marks a value we do not determine. The last column points to the result that proves the row.

Panel of Figure 3 — Figure 3: Coset cubes. (a) A coset cube of dimension $2$ in $C_{2}\times C_{2}=\{e,a,b,ab\}$ : the cosets of $V_{1}$ (columns) and of $V_{2}$ (rows) cut the group into four nonempty cells $k_{1}^{\varepsilon_{1}}V_{1}\cap k_{2}^{\varepsilon_{2}}V_{2}$ . (b) The lifting step of Theorem 7.1 (iii). Let $(V_{i},k_{i})$ be a cube in a complement $Q$ of $M$ (front face; the cell $\varepsilon$ contains $g_{\varepsilon}\in Q$ ). The coordinates $(MV_{i},k_{i})$ together with $(Q,k_{0})$ , where $k_{0}\in M\setminus\{1\}$ , form a cube in $M\rtimes Q$ of one more dimension. The back face consists of the translates $k_{0}g_{\varepsilon}$ , which lie in $k_{0}Q$ and, since $M$ is normal, in every $k_{i}^{\varepsilon_{i}}MV_{i}$ . Inducting down a chief series gives Theorem 7.1 (iv).

Panel of Figure 4 — Figure 4: The quartic. Each factor of the chief series $1<V_{4}<A_{4}<S_{4}$ , where $V_{4}$ is the Klein four-group, is complemented, in the sense of Section 7 , by the subgroup $C=S_{3}$ , $D_{4}$ (dihedral of order $8$ ) or $A_{4}$ , and each complement is the stabilizer of a quantity in the classical solution of the quartic by radicals. Each complemented factor contributes one coordinate of a coset cube ( Theorem 7.1 (iii),(iv)), so the three quantities are Natarajan-shattered. For the groups of the quintic the two dimensions separate ( Theorem 7.2 (b)); every subgroup of $A_{5}$ has at most two complemented chief factors, fewer than $\mu(A_{5})=3$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Galois theory	learning	where
the field $K(A)$ generated by the sample points	the points whose label is forced, $\cl(A)$	Theorem 5.2 (i), Lemma 3.1 (iii)
the group $\Gal(L/K(A))$	the version space is a coset of it	Lemma 3.1 (i)
the conjugates $\beta$ of $\alpha$ over $K(A)$	the possible labels $\sigma\beta$ of $\alpha$	Theorem 5.2 (v)
a primitive element $\theta$ , $\Gamma_{\theta}=1$	a teaching set of size one	Theorem 5.2 (ii)
independent subsets of $\Gamma$ , $\mu(\Gamma)$	DS and graph dimension	Theorem 5.2 (iii), Proposition 4.3 (a)
longest chain of subgroups, $\ell(\Gamma)$	Littlestone dimension	Theorem 5.2 (iv)

Appendix

Table 2: The Galois dictionary.

Panel of Figure 5 — Figure 5: The orthogonality rules (R1)–(R3) of the proof of Theorem 7.3 (a), drawn in the notation of that proof. The thick edge is $s=(a\,b)$ and the thin edges are other edges of the tree $T$ . An arrow from $x_{t}$ to $y^{\prime}_{t}$ depicts the vector $d_{t}=\mathbf{1}_{y^{\prime}_{t}}-\mathbf{1}_{x_{t}}$ of an unbalanced edge $t\neq s$ , and Lemma G.4 requires $\langle d_{t},d_{t^{\prime}}\rangle=0$ for distinct such edges. The three configurations in red violate this. For $n\geq 5$ no tree survives: by (R2) every edge other than $s$ touches $s$ , by (R1) at most two do, and there are $n-2\geq 3$ (a balanced edge is excluded separately). For $n=4$ the path on the right satisfies all three rules, consistent with $N(S_{4})=3$ .

group	solvable	$\mu$	$\max_{\Delta}c(\Delta)$	$N=\dimN$	$\dimN=\dimDS$ ?
$C_{2},\ C_{4}$	yes	1	1	1	yes
$C_{6},\ S_{3},\ D_{4},\ D_{5},\ D_{8},\ Q_{8},\ A_{4},\ \mathrm{SL}(2,3)$	yes	2	2	2	yes
$C_{2}^{3},\ D_{6},\ C_{3}\times S_{3},\ S_{4},\ D_{4}\times C_{2},\ A_{4}\times C_{2}$	yes	3	3	3	yes
$C_{2}^{4},\ S_{3}\times S_{3},\ C_{2}\times S_{4}$	yes	4	4	4	yes
$A_{5}$	no	3	2	2	no
$S_{5},\ A_{5}\times C_{2},\ \mathrm{PSL}(2,7)$	no	4	3	3	no

Appendix

Table 3: Coset-cube numbers of small groups, computed by exhaustive search with independent programs;

C_{2}^{2}

(with

\mu=N=2

) is omitted.

Explore similar work

Oct 11, 2026

Sample-Optimal Multi-Group Learning with an ERM Oracle

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses

\tilde{O}((d_G+d_H)/\varepsilon^2)

samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where

d_G

and

d_H

are the VC dimensions of the group and hypothesis classes and

\varepsilon

bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of

Ω((d_G+d_H)/\varepsilon^2)

samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most

k

groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with

\tilde{O}((d_H+\log k)/\varepsilon^2)

samples in the agnostic setting and

\tilde{O}((d_H+\log k)/\varepsilon)

samples when every group has a hypothesis that is correct on it.

Princewill Okoroafor

Harvard University

Statistical Learning Theory

Ask PDF

Sep 7, 2026

Efficient Learning and Symmetry Discovery under Exact Invariances

Learning with group invariances is central to many scientific and geometric learning problems, yet its computational foundations remain poorly understood. Even for classical supervised regression settings, it has been unclear whether one can efficiently compute a regression function that is exactly invariant to a given group action. Recent work showed that exact invariance can be enforced in polynomial time when the underlying group is finite and known, but left open the cases of infinite groups and unknown symmetries. In this paper, we resolve both challenges. First, we present the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups. The runtime is polynomial in the data dimension and sample size, and independent of the group, while achieving strong generalization guarantees. This provides a computational explanation for the empirical success of invariant and equivariant methods in geometric machine learning and partially answers a recent open question in the literature. Second, we study learning in the symmetry discovery setting, where the invariance group is unknown. Focusing on the subgroup lattice of a finite group, we show that exact symmetries can be identified from data and exploited for learning in polynomial time. For regression over finite-dimensional feature spaces, our algorithm provably recovers the underlying symmetry, matches the minimax-optimal sample complexity of the known-symmetry setting, and runs in time polynomial in the data dimension and sample size. Our analysis relies on tools from random Cayley graphs and expander theory, which may be of independent interest.

Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet +1

MIT Laboratory for Information and Decision Systems (LIDS) · Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA · Technical University of Munich (CIT, MCML, MDSI) and MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

Invariant Representation Learning Statistical Learning Theory

Ask PDF

Mar 24, 2026

A One-Inclusion Graph Approach to Multi-Group Learning

We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite

b

-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's

\log n / n

convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal

1/n

convergence rate under group-realizability.

Noah Bergam, Samuel Deng, Daniel Hsu

Columbia University

Statistical Learning Theory

Ask PDF