7.3 Assouad’s dual VC bound
Lemma
7.7
Dual-to-primal shattering coding
Lean: BinaryMatrix.transpose_shatters_imp_shatters
If \(M^\top \) shatters \(S \subseteq \mathrm{Fin}\, m\) with \(|S| \ge 2^{d+1}\), then \(M\) shatters some \(T \subseteq \mathrm{Fin}\, n\) with \(|T| = d + 1\). Proof by a bitstring-coding argument: over \((d+1)\)-bit patterns on \(S\), each pattern must be realized by a distinct column, giving \(d + 1\) distinguishing columns that \(M\) shatters [ 2 , Thm 2.13 ] .
Theorem
7.8
Assouad’s bound: \(\mathrm{VCdim}(M^\top ) \le 2^{d+1} - 1\)
Lean: BinaryMatrix.assouad_transpose_vcDim
If \(\mathrm{VCdim}(M) \le d\) then \(\mathrm{VCdim}(M^\top ) \le 2^{d+1} - 1\) [ 2 , Thm 2.13 ] . The bound is tight at small \(d\); no strengthening is known for general \(d\) without additional structure.