ID: 0707.2707

A superadditivity and submultiplicativity property for cardinalities of sumsets

July 18, 2007

View on ArXiv
Katalin Gyarmati, Imre Z. Ruzsa, Mate Matolcsi
Mathematics
Combinatorics
Commutative Algebra

For finite sets of integers $A_1, A_2 ... A_n$ we study the cardinality of the $n$-fold sumset $A_1+... +A_n$ compared to those of $n-1$-fold sumsets $A_1+... +A_{i-1}+A_{i+1}+... A_n$. We prove a superadditivity and a submultiplicativity property for these quantities. We also examine the case when the addition of elements is restricted to an addition graph between the sets.

Similar papers 1

Extremal problems and the combinatorics of sumsets

October 27, 2023

88% Match
Melvyn B. Nathanson
Number Theory

This is a survey of old and new problems and results in additive number theory.

Find SimilarView on arXiv

Generalized H-fold sumset and Subsequence sum

January 13, 2024

86% Match
Mohan, Ram Krishna Pandey
Number Theory

Let $A$ and $H$ be nonempty finite sets of integers and positive integers, respectively. The generalized $H$-fold sumset, denoted by $H^{(r)}A$, is the union of the sumsets $h^{(r)}A$ for $h\in H$ where, the sumset $h^{(r)}A$ is the set of all integers that can be represented as a sum of $h$ elements from $A$ with no summand in the representation appearing more than $r$ times. In this paper, we find the optimal lower bound for the cardinality of $H^{(r)}A$, i.e., for $|H^{(r)...

Find SimilarView on arXiv
Ilya D. Shkredov
Combinatorics
Number Theory

We develop the theory of the additive dimension ${\rm dim} (A)$, i.e. the size of a maximal dissociated subset of a set $A$. It was shown that the additive dimension is closely connected with the growth of higher sumsets $nA$ of our set $A$. We apply this approach to demonstrate that for any small multiplicative subgroup $\Gamma$ the sequence $|n\Gamma|$ grows very fast. Also, we obtain a series of applications to the sum--product phenomenon and to the Balog--Wooley decomposi...

The Cardinality of Sumsets: Different Summands

September 9, 2013

85% Match
Brendan Murphy, Eyvindur Ari Palsson, Giorgis Petridis
Combinatorics

Let $h$ be a positive integer and $A, B_1, B_2,\dots, B_h$ be finite sets in a commutative group. We bound $|A+B_1+...+B_h|$ from above in terms of $|A|, |A+B_1|,\dots,|A+B_h|$ and $h$. Extremal examples, which demonstrate that the bound is asymptotically sharp in all the parameters, are furthermore provided.

Find SimilarView on arXiv

On a sumset problem for integers

November 24, 2010

85% Match
Shan-Shan Du, Hui-Qin Cao, Zhi-Wei Sun
Combinatorics
Number Theory

Let $A$ be a finite set of integers. We show that if $k$ is a prime power or a product of two distinct primes then $$|A+k\cdot A|\geq(k+1)|A|-\lceil k(k+2)/4\rceil$$ provided $|A|\geq (k-1)^{2}k!$, where $A+k\cdot A=\{a+kb:\ a,b\in A\}$. We also establish the inequality $|A+4\cdot A|\geq 5|A|-6 $ for $|A|\geq 5$.

Find SimilarView on arXiv

A Note on Sumsets and Restricted Sumsets

June 8, 2021

85% Match
Jagannath Bhanja
Combinatorics
Number Theory

In this note we find the optimal lower bound for the size of the sumsets $HA$ and $H\,\hat{}A$ over finite sets $H, A$ of nonnegative integers, where $HA = \bigcup_{h\in H} hA$ and $H\,\hat{}A = \bigcup_{h\in H} h\,\hat{}A$. We also find the underlying algebraic structure of the sets $A$ and $H$ for which the size of the sumsets $HA$ and $H\,\hat{}A$ is minimum.

Find SimilarView on arXiv

Upper Bounds on the Cardinality of Higher Sumsets

January 26, 2011

84% Match
Giorgis Petridis
Combinatorics
Number Theory

Let A and B be finite sets in a commutative group. We bound |A+hB| in terms of |A|, |A+B| and h. We provide a submultiplicative upper bound that improves on the existing bound of Imre Ruzsa by inserting a factor that decreases with h.

Find SimilarView on arXiv

A Walk Through Some Newer Parts of Additive Combinatorics

November 3, 2022

84% Match
Bela Bajnok
Number Theory

In this survey paper we discuss some recent results and related open questions in additive combinatorics, in particular, questions about sumsets in finite abelian groups.

Find SimilarView on arXiv

Sums, Differences and Dilates

February 28, 2024

84% Match
Jonathan Cutler, Luke Pebody, Amites Sarkar
Combinatorics

Given a set of integers $A$ and an integer $k$, write $A+k\cdot A$ for the set $\{a+kb:a\in A,b\in A\}$. Hanson and Petridis showed that if $|A+A|\le K|A|$ then $|A+2\cdot A|\le K^{2.95}|A|$. At a presentation of this result, Petridis stated that the highest known value for $\frac{\log(|A+2\cdot A|/|A|)}{\log(|A+A|/|A|)}$ (bounded above by 2.95) was $\frac{\log 4}{\log 3}$. We show that, for all $\epsilon>0$, there exist $A$ and $K$ with $|A+A|\le K|A|$ but with $|A+2\cdot A|...

Find SimilarView on arXiv

On the size of $k$-fold sum and product sets of integers

September 3, 2003

84% Match
Jean Bourgain, Mei-Chu Chang
Combinatorics
Number Theory

We prove the following theorem: for all positive integers $b$ there exists a positive integer $k$, such that for every finite set $A$ of integers with cardinality $|A| > 1$, we have either $$ |A + ... + A| \geq |A|^b$$ or $$ |A \cdot ... \cdot A| \geq |A|^b$$ where $A + ... + A$ and $A \cdot ... \cdot A$ are the collections of $k$-fold sums and products of elements of $A$ respectively. This is progress towards a conjecture of Erd\"os and Szemer\'edi on sum and product sets.

Find SimilarView on arXiv