A Sauer-Shelah-Perles lemma for sumsets (Q1627216): Difference between revisions

Summary: We show that any family of subsets \(A\subseteq 2^{[n]}\) satisfies \(|A|\leq O(n^{\lceil{d}/{2}\rceil})\), where \(d\) is the VC dimension of \(\{S\triangle T \,|\, S,T\in A\}\), and \(\triangle\) is the symmetric difference operator. We also observe that replacing \(\triangle\) by either \(\cup\) or \(\cap\) fails to satisfy an analogous statement. Our proof is based on the polynomial method; specifically, on an argument due to [\textit{E. Croot} et al., Ann. Math. (2) 185, No. 1, 331--337 (2017; Zbl 1425.11019)].