When subset-sums do not cover all the residues modulo \(p\).
type: Item
instance of: scholarly article
title: When subset-sums do not cover all the residues modulo \(p\).
zbMATH Open document ID: 1048.11077
author: Jean-Marc Deshouillers
author: G. A. Freiman
published in: Journal of Number Theory
publication date: 2004-03-14T00:00:00Z
review text: 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)], \textit{P. Erdős} and \textit{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\).
reviewed by: Alain Plagne
Mathematics Subject Classification ID: 11P70
Mathematics Subject Classification ID: 11B25
zbMATH DE Number: 2056167
zbMATH Keywords: subset sums
zbMATH Keywords: arithmetic progression
zbMATH Keywords: inverse problems of additive number theory
MaRDI profile type: Publication
full work available at URL: j.jnt.2003.08.009
OpenAlex ID: W2085480084
cites work: Q4256495
cites work: Cyclic Spaces for Grassmann Derivatives and Additive Theory
cites work: On the addition of residue classes mod p
cites work: New analytical results in subset-sum problem
cites work: An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
cites work: An addition theorem modulo p
cites work: Finite addition theorems. II
DOI: 10.1016/J.JNT.2003.08.009
description: scientific article; zbMATH DE number 2056167