When subset-sums do not cover all the residues modulo \(p\). (Q1427982): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4256495 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cyclic Spaces for Grassmann Derivatives and Additive Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the addition of residue classes mod p / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New analytical results in subset-sum problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An addition theorem modulo p / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite addition theorems. II / rank | |||
Normal rank |
Latest revision as of 15:38, 6 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | When subset-sums do not cover all the residues modulo \(p\). |
scientific article |
Statements
When subset-sums do not cover all the residues modulo \(p\). (English)
0 references
14 March 2004
0 references
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\).
0 references
subset sums
0 references
arithmetic progression
0 references
inverse problems of additive number theory
0 references