A note on the addition of residues. (English) Zbl 0745.11009
Let \(A\) and \(B\) be two proper subsets of \(\mathbb{Z}_ n\) such that \(A+B\neq\mathbb{Z}_ n\). A theorem of Cauchy and Davenport states that \(A+B\geq| A|+| B|-1\) if \(n\) is a prime. Chowla generalized the Cauchy-Davenport theorem and proved that the same inequality holds if \(0\in B\) and \(\text{gcd}(x,n)=1\) for all nonzero \(x\in B\). The author proves in this paper that if \(0\in B\) and for all \(x,y\in B\backslash\{0\}\) such that \(x\neq y\) and \(\text{gcd}(x,y,n)=1\), then \(A+B\geq| A|+| B|-2\). Moreover, \(A+B\geq| A|+| B|-1\) unless \(| B|=2\) or there exists a \(b\in B\) such that \(B\backslash\{0,b\}\) is a union of cosets of modulo the cyclic generated by \(b\) in \(\mathbb{Z}_ n\). The proofs are based on some results on atoms in Cayley graphs proved earlier by the author some of which are listed in the paper.
Reviewer: X.-D.Jia (San Marcos)
MSC:
11B13 | Additive bases, including sumsets |
05B40 | Combinatorial aspects of packing and covering |
11B75 | Other combinatorial number theory |
References:
[1] | Cauchy, A.: Recherches sur les nombres, J. Ecole polytechnique9, 99–116 (1813) |
[2] | Chowla: A theorem on the addition of residue classes: Application to the number{\(\Gamma\)}(k) in Waring’s problem. Proc. Indian Acad. Sci.2, 242–243 (1935) · Zbl 0012.24701 |
[3] | Davenport, H.: On the addition of residue classes. J. London Math. Soc.10, 30–32 (1935) · Zbl 0010.38905 · doi:10.1112/jlms/s1-10.37.30 |
[4] | Hamidoune, Y.O.: Sur les atomes d’un graphe orienté. C.R. Acad. Sc. Paris A284, 1253–1256 (1977) · Zbl 0352.05035 |
[5] | Hamidoune, Y.O.: On the connectivity of Cayley digraphs. Europ. J. Comb.5, 309–312 (1984) · Zbl 0561.05028 |
[6] | Hamidoune, Y.O.: Sur la séparation dans les graphesz de Cayley Abeliens. Discrete Math.55, 323–326 (1985) · Zbl 0567.05027 · doi:10.1016/S0012-365X(85)80010-8 |
[7] | Hardy, D.H., Littlewood, J.E.: Some problems of ’Partitio Numerorum’: IV, Math Zischr.12, 161–168 (1922) · JFM 48.0146.01 · doi:10.1007/BF01482074 |
[8] | Mann, H.B.: Additions theorems. Interscience tracts 18. New York: John Wiley and sons 1965 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.