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 G acting with finite orbits on a countable set Ω, from examples (x, gx). After a sample on a set A of points, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer G_(A), and the sample forces exactly the labels of the points that G_(A) fixes; for a Galois group, these points form the field generated by the data. Through this Galois correspondence, the multiclass dimensions become invariants of permutation groups. The DS and graph dimensions are the height H, the largest size of a set of points each of which can be moved while all the others stay fixed; the Littlestone and teaching dimensions are the length of the longest irredundant sequence and the minimal base size, two classical notions for permutation groups; and the list DS dimension is a list version of the height. In the realizable model, every consistent learner, however it breaks ties, has expected error at most H/(m + 1) after m examples, within a factor 16 of the minimax error when 2 ≤ H < ∞ and m ≥ max(2, H − 1). On nondegenerate classes it attains the optimal deterministic sample complexity Θ((H + log(1/δ))/ε), and every consistent online learner attains the optimal deterministic mistake bound. In the agnostic model, every ERM uses O((H + log(1/δ))/ε²) examples, at most a factor O(DS/Nat), the ratio of the DS and Natarajan dimensions, above the known lower bound for deterministic learners. Our main new results concern this ratio for Galois groups. For the Galois group of a finite Galois extension of a countable field, the Natarajan dimension equals a group invariant, the coset-cube number: the largest t for which some subgroups V_1, …, V_t and cosets k_iV_i ≠ V_i have a common element for each of the 2^t ways of choosing V_i or k_iV_i. It is at least the number of complemented factors of any chief series of any subgroup. Consequently the two dimensions coincide for every solvable Galois group, while for the groups A₅ and S₅ of the quintic they are 2 < 3 and 3 < 4, and A₅ is the smallest group with a gap. For the Galois group S_n of the general equation of degree n, the two dimensions coincide if and only if n ≤ 4, that is, in characteristic zero, exactly when the equation is solvable by radicals. Our proof of the gap for n ≥ 5 uses the independent generating sets of S_n, not its non-solvability, and for arbitrary groups the implication is one-way: the simple group PSL(2, 8) has no gap. For the generic quartic, a root, a root of the resolvent cubic and the square root of the discriminant, three quantities from the classical solution by radicals, form a Natarajan-shattered set. We also show that for the Galois group of a finite Galois extension L/K of a countable field with L ≠ K the teaching dimension is 1, and the DS and Littlestone dimensions are the largest size of an independent subset and the length of the longest subgroup chain of the group; that for linear, orthogonal and unitary maps of ℝ^d or ℂ^d the Natarajan and DS dimensions both equal d; and that a two-fibered pseudo-cube, one in which every vector has a unique neighbor in each coordinate, is a disjoint union of Natarajan cubes exactly when the group generated by its neighbor maps is abelian. For a permutation group of a finite set, learned on the whole set, the Natarajan dimension is at least half the DS dimension when the closure that sends a sample to its forced points is a matroid closure; we conjecture this bound for every such group.