When subset-sums do not cover all the residues modulo \(p\). (English) Zbl 1048.11077

If \({\mathcal A}\) is a subset of some group, \(S_{\mathcal A}\) denotes the sum of the elements of \({\mathcal A}\) and \({\mathcal A}^*= \{S_{\mathcal B},\,{\mathcal B}\subset{\mathcal A}\}\).
In [Acta Arith. 9, 149–159 (1964; Zbl 0156.04801)], P. Erdős and H. Heilbronn proved that every subset \({\mathcal A}\subset\mathbb{Z}/p\mathbb{Z}\setminus \{0\}\) such that \(|{\mathcal A}|\geq 3\sqrt{6p}\) satisfies \({\mathcal A}^*= \mathbb{Z}/p\mathbb{Z}\). They conjectured that the conclusion still holds if we replace the coefficient \(3\sqrt{6}\) by \(2\). Olson proved it and finally, Dias da Silva and ould Hamidoune proved a best possible result of this form.
The present paper looks for subsets \({\mathcal A}\subset \mathbb{Z}/p\mathbb{Z}\) such that \(|{\mathcal A}|\) is large and \({\mathcal A}^*\neq \mathbb{Z}/p\mathbb{Z}\).
Observe that as soon as \(\sum_{a\in{\mathcal A}}\| a/p\|< 1-1/p\) \((\| z\|= \min_{n\in\mathbb{Z}}| z-n|)\), \({\mathcal A}^*\neq \mathbb{Z}/p\mathbb{Z}\) must hold. More generally, if for some non-zero modulo \(p\) integer \(s\), \(\sum_{a\in{\mathcal A}}\| sa/p\|< 1-1/p\), then \({\mathcal A}^*\neq \mathbb{Z}/p\mathbb{Z}\) must hold.
The present paper looks for a kind of converse statement for this criterion. The following theorem is proved: Let \(c> \sqrt{2}\) and \(p\) be a prime. Let \({\mathcal A}\subset \mathbb{Z}/p\mathbb{Z}\), with \(|{\mathcal A}|\geq c\sqrt{p}\). If we assume \({\mathcal A}^*\neq \mathbb{Z}/p\mathbb{Z}\) then \(\sum_{a\in{\mathcal A}}\| as/p\|< 1+ O(p^{-1/4}\log p)\) for some integer \(s\) that is, non-zero modulo \(p\).


11P70 Inverse problems of additive number theory, including sumsets
11B25 Arithmetic progressions


Zbl 0156.04801
Full Text: DOI


[1] Chaimovich, M., New algorithm for dense subset sum problem, Astérisque, 258, 363-373 (1999) · Zbl 0987.90061
[2] Dias da Silva, J. A.; Hamidoune, Y. O., Cyclic spaces for Grassman derivatives and additive theory, Bull. London Math. Soc., 26, 140-146 (1994) · Zbl 0819.11007
[3] Erdős, P.; Heilbronn, H., On the addition of residue classes mod \(p\), Acta Arithmetica, 9, 149-159 (1964) · Zbl 0156.04801
[4] Freiman, G. A., New analytical results in subset sum problem, Discrete Math., 114, 205-217 (1993) · Zbl 0849.11015
[5] Galil, Z.; Margalit, O., An almost linear-time algorithm for the dense subset sum problem, SIAM J. Comput., 20, 6, 1157-1189 (1991) · Zbl 0736.68041
[6] Olson, J., An addition theorem modulo \(p\), J. Combin. Theory, 5, 45-52 (1968) · Zbl 0174.05202
[7] Sárközy, A., Finite addition theorems II, J. Number Theory, 48, 2, 197-218 (1994) · Zbl 0808.11011
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.