×

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.

MSC:

11B13 Additive bases, including sumsets
05B40 Combinatorial aspects of packing and covering
11B75 Other combinatorial number theory
Full Text: DOI

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.