Best-case teaching dimension against VC dimension on at most five points: the joint census, the least domain for a gap at VC dimension three, and where the greedy teaching-set algorithm first fails
Abstract
For a finite concept class C, the best-case teaching dimension TSₘᵢₙ(C) is the least number of domain points on which some concept of C differs from every other concept of C; whether TSₘᵢₙ(C)=O(VCD(C)) is open, and everything known about the two parameters together is asymptotic. We report the exact joint distribution of (VCD,TSₘᵢₙ) over every concept class on at most five points — all 4 294 967 295 nonempty classes on five — and hence the table M(n,d)=max{TSₘᵢₙ(C):VCD(C)=d} for n ≤ 5, whose last row reads 0,1,3,4,4,5. Two cells lie above the diagonal. One is Warmuth's class (VCD=2, TSₘᵢₙ=3), which on five points is unique up to relabelling and complementation of points. The other consists of classes with VCD=3 and TSₘᵢₙ=4 on five points — three orbits, of 20, 21 and 22 concepts — whereas the standard construction, the disjoint union of Warmuth's class with a two-concept class, needs six; by a theorem of Doliwa, Fan, Simon and Zilles five is the least possible domain size, and each of the three contains a copy of Warmuth's class. Second, the greedy teaching-set algorithm whose limitations Compton, Pabbaraju and Zhivotovskiy study is already suboptimal on four points and returns twice the optimum on five, under every tie-breaking; the largest gap on n ≤ 5 points is 0,0,0,1,2. The witness classes, their parameters and the one-step correctness of the algorithm are verified in Lean 4 against Mathlib by kernel reduction; the censuses are external computations and are labelled as such. The four extremal orbits also arise in a companion paper, under an equivalent condition; what is new here is their TSₘᵢₙ values, the joint census, the greedy analysis and the machine-checked witnesses.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
d24636b6503f2402383a4a7871130892d495465903c418037c0ddff78771a7f5
Claim ledger
Stated results
TC1known data2026-09-04
Warmuth's class C_W on five points has VCD 2 and TSₘin 3, kernel-checked from the definitions of arXiv:2505.03223 v1
TC2candidate2026-09-04
A concept class on FIVE points with VCD 3 and TSₘin 4 exists (three orbits, |C| = 20, 21, 22, kernel-checked), so five is the least domain size on which TSₘin exceeds VCD at VC dimension 3 – the disjoint-union construction needs six; and each of the three contains a copy of Warmuth's class
TC3measurement2026-09-04
The exact table M(n,d) = maxTSₘin(C): C on n points, VCD(C) = d for n <= 5 – rows 0,1 / 0,1,2 / 0,1,2,3 / 0,1,2,3,4 / 0,1,3,4,4,5 – together with the full joint (VCD, TSₘin) census of all 4,294,967,295 non-empty classes on five points
This ledger entry is reported in prose and is not bound to a Lean theorem.TC4candidate2026-09-04
The greedy algorithm of arXiv:2505.03223 Algorithm 1 at k = 1 is already suboptimal on four points (TSₘin 2, output 3 under every tie-breaking) and off by two on five (TSₘin 2, output 4 under every tie-breaking); one restriction costs at most one point of teaching set, so the gap is well defined and non-negative
TC5measurement2026-09-04
The exact largest gap between the output of Algorithm 1 at k = 1 and TSₘin, over every concept class on n points, is 0, 0, 0, 1, 2 for n = 1..5; with the full gap-by-TSₘin census (3,408 classes at n = 4, 275,040 classes at gap 2 on n = 5)
This ledger entry is reported in prose and is not bound to a Lean theorem.TC6known data2026-09-04
The rectangle construction of arXiv:2505.03223 Theorem 1 reproduced at N <= 3: greedy returns exactly N and TSₘin = 2, and this already happens with w = (1,1,1) on a nine-point domain, where the paper's own level-domination inequality fails at every level and its stated wᵢ = 2¹⁰ⁱ would need about 2.1e9 points
This ledger entry is reported in prose and is not bound to a Lean theorem.TC7routine2026-09-04
The elementary layer over the source's definitions: TSₘin(C) <= |X| for every non-empty class, TSₘin(C) = 0 iff |C| = 1, VCD(C) >= 1 iff |C| >= 2, and hence TSₘin(C) <= VCD(C) whenever VCD(C) = 0
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Let X be a finite domain and C a family of subsets of X (a *concept class*; a concept is the set of points it labels 1). A teaching set for c ∈ C is a set S ⊆ X on which c differs from every other concept of C — equivalently, c is the only concept of C with that trace on S. Write TS(c, C) for the least size of one, and
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7