A quadratic lower bound for subset sums

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004962" target="_blank" >RIV/00216208:11320/07:00004962 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A quadratic lower bound for subset sums
Original language description
Let A be a finite nonempty subset of an additive abelian group G, and let Sigma(A) denote the set of all group elements representable as a sum of some subset of A. We prove that |Sigma(A)| >= |H| + 1/64 |A H|^2 where H is the stabilizer of Sigma(A). Our result implies that Sigma(A) = Z/nZ for every set A of units of Z/nZ with |A| ge 8 sqrt{n}. This consequence was first proved by ErdH{o}s and Heilbronn for n prime, and by Vu (with a weaker constant) for general n.
Czech name
Kvadratický dolní odhad pro součty podmnožiny
Czech description
Označme A konečnou podmnožinu aditivní abelovské grupy G, a Sigma(A) množinu všech prvků grupy reprezentovatelných jako součet podmnožiny A. Dokážeme, že |Sigma(A)| >= |H| + 1/64 |A H|^2, kde H je stabilizer Sigma(A). Odtud plyne, že Sigma(A) = Z/nZ pro každou množinu A invertibilních prvků v Z/nZ$, když |A| ge 8 sqrt{n}. Tento důsledek dokázali Erdos a Heilbronn pro n prvočíslo, a Vu (se slabší konstantou) pro obecné n.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)