Where parity dimension parts from DS dimension: explicit witnesses, and the threshold at dimension three

Abstract

A finite nonempty set Q ⊆ Y^(D) of patterns is a pseudo-cube on the finite index set D when every point of Q has, at every coordinate, a second point of Q agreeing with it off that coordinate and differing there; the largest |D| for which a function class has a pseudo-cube in its trace on D is its DS dimension, the invariant that characterises multiclass PAC learnability. Li (arXiv:2607.07423) refines the notion over 𝔽₂: Q is an even pseudo-cube when it carries a nonzero η ∈ 𝔽₂^(Q) all of whose coordinate-deletion marginals vanish, and the resulting invariant, the parity dimension, is what survives an autoregressive rollout. Li proves ParDim ≤ DSdim with equality on binary classes, and that the inequality can be strict — but the strictness is derived indirectly, no pseudo-cube without an even certificate is exhibited, and nothing there says at which dimension the two invariants can first part. We prove that every pseudo-cube on at most two coordinates carries an even certificate, for an arbitrary label set; hence ParDim(H) ≥ min(DSdim(H),2), and the two dimensions agree whenever the DS dimension is at most 2. At dimension three they need not: we exhibit a 24-point minimal pseudo-cube inside a 3 × 3 × 4 grid, no nonempty subclass of which carries an even certificate. Three is therefore the least dimension at which parity dimension and DS dimension can differ. We also verify Li's separation directly on the 28-row table its construction produces, independently of the rollout non-increase theorem from which that paper derives it. The computations rest on an elementary normal form — a finite class carries an even certificate exactly when some nonempty subclass has all of its own coordinate-deletion fibres of even cardinality — which makes parity dimension a decidable combinatorial condition on a finite table. Every theorem below is machine-checked in Lean 4 over Mathlib, in its finite-table form and with no appeal to native evaluation; the exhaustive searches, and the elementary observation that carries the finite tables back to Li's rollout class, lie outside the formal development and are marked as such.

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

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   580302638e7af99cb718c6b73c4bcdf740a441d35b8f72a55463c6dcdcc43dac