Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
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 A5 and S5 of the quintic they are 2<3 and 3<4, and A5 is the smallest group with a gap. For the Galois group Sn of the general equation of degree n, they coincide exactly when n≤ 4, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group PSL(2,8) has no gap. For linear, orthogonal and unitary maps of ℝd or ℂ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.
Related
- The dimension-free threshold for maximal sections of ℓp
- Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
- A Model-threshold Dimension Bound and Sharp Critical Ends for Smooth Singular Sets of Constant Positive σk-curvature Metrics
- A threshold for full packing dimension of Hölder images of sets and measures
- Sharp dimension threshold for unique FKPP steady states and BBM recurrence
BibTeX
@misc{li2026learning,
title = {{Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension}},
author = {Xiaoyu Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18154},
eprint = {2610.18154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18154},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
AU - Xiaoyu Li
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18154
UR - https://arxiv.org/abs/2610.18154
AB - 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≤ 4, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group PSL(2,8) has no gap. For linear, orthogonal and unitary maps of ℝ^d or ℂ^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.
ER -