A generalization of an addition theorem of Shatrowsky (Q1197620): Difference between revisions

The Cayley-Davenport theorem states that if \(A\) and \(B\) are proper subsets of \(\mathbb Z_n\) with \(A+B\neq\mathbb Z_n\), then \(| A+B|\geq| A|+| B|-1\) for a prime \(n\). Chowla generalized this result to composite \(n\) and a further generalization was obtained by Shatrowsky [\textit{L. I. Shatrovskiĭ}, C. R. (Dokl.) Acad. Sci. URSS, n. Ser. 45, 315--317 (1944; Zbl 0063.06948)]. After a thorough introduction to directed graphs, the author uses Cayley graphs to generalize Shatrowsky's theorem as follows: Let \(A\) and \(B\) be two proper finite subsets of a group \(G\) such that \(A\neq AB\cup A\langle B\rangle\). Then \(| A\cup AB|\geq| A|+\min\{| B|,\;\nu(B)\}\) where \(\langle B\rangle\) denotes the subgroup generated by \(B\) and \(\nu(B)\) is the minimal order of an element of \(B\).