A Sauer-Shelah-Perles lemma for sumsets (Q1627216)

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)].