Questions tagged [sumsets]

The tag has no usage guidance.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11 votes
0 answers
813 views

Cliques in the Paley graph and a problem of Sarkozy

The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously ...
Seva's user avatar
  • 22.8k
9 votes
0 answers
263 views

If $A+A+A$ contains the extremes, does it contain the middle?

Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers). Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
Alufat's user avatar
  • 805
4 votes
0 answers
149 views

Dividing a finite arithmetic progression into two sets of same sum: always the same asymptotics?

This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$. The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\...
Wolfgang's user avatar
  • 13.2k
4 votes
0 answers
126 views

Restricted addition analogue of Freiman's $(3n-4)$-theorem

There is a well-known theorem of Freiman saying that if $A$ is a finite set of integers with $|2A| \le 3|A|-4$, then $A$ is contained in an arithmetic progression with at most $|2A|-|A|+1$ terms. Is ...
user93878's user avatar
4 votes
0 answers
215 views

Subgroup cliques in the Paley graph

It is a famous open problem to estimate non-trivially, for a prime $p\equiv 1\pmod 4$, the largest size of a subset $A\subset{\mathbb F}_p$ such that the difference of any two elements of $A$ is a ...
Seva's user avatar
  • 22.8k
3 votes
0 answers
93 views

Origins of the ``baby Freiman'' theorem

It is a basic folklore fact from the area of additive combinatorics that a subset $A$ of an abelian group satisfies $|2A|<\frac32\,|A|$ if and only if $A$ is contained in a coset of a (finite) ...
Seva's user avatar
  • 22.8k
3 votes
0 answers
133 views

Is there some sort of formula for $t(S_n)$?

Let $G$ be a finite group. Define $t(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > t(G)$ and $\langle X \rangle = G$, then $XXX = G$. Is there some sort of formula for $t(S_n)...
Chain Markov's user avatar
  • 2,618
3 votes
0 answers
64 views

What's known about $X$ when $|X(n) + X(n)| < kn$, $n \in \mathbb{N}$, absolute constant $k$?

Let $X$ be an infinite sequence of integers$$x_1 < x_2 < x_3 < \ldots,$$and let $X(n)$ be the set$$\{x_1, x_2, \ldots, x_n\}.$$ Question. What is known about $X$ when we have$$|X(n) + X(n)| &...
user106208's user avatar
2 votes
0 answers
173 views

Component-wise sums of permutations

Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...
Talesseed's user avatar
2 votes
0 answers
112 views

Restricted sumsets - the origins?

The sumset of the subsets $A$ and $B$ of an additively written group is defined by $A+B:=\{a+b\colon a\in A,\ b\in B\}$. The basic idea to add sets has been around since Cauchy at least. Erdős and ...
Seva's user avatar
  • 22.8k
2 votes
0 answers
39 views

Weighted unrestricted Golomb rulers?

A set of integers ${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}\quad a_{1}<a_{2}<...<a_{m}} $ is a Golomb ruler if and only if ${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},a_{i}...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
137 views

The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in X$

Let $H$ be a multiplicatively written monoid with identity $1_H$. Given $x \in H$, we take ${\sf L}_H(x) := \{0\}$ if $x = 1_H$; otherwise, ${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for ...
Salvo Tringali's user avatar
2 votes
0 answers
183 views

Doubling for Sumset of the same set

Let $G$ ($G=\mathbb{Z}^n_2$ for my case) be a additive group and $A$ be a subset of $G$. For any set $S\subseteq G$ define its doubling as $$\sigma (S)=\dfrac{|S+S|}{|S|}$$ Suppose $A$ has small ...
yue's user avatar
  • 21
1 vote
0 answers
202 views

Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Subset

I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed. ...
Moni's user avatar
  • 11
1 vote
0 answers
116 views

Lower bound for sumset in discrete cube

Suppose $A\subset\{0,1\}^d$ for some $d\geq 1$. Then how large must $A+A=\{a+b:a,b\in A\}$ be?
sumsetproblem's user avatar
0 votes
0 answers
67 views

Bounds on these numbers

Let $[n]$ be the set of natural numbers $1,2,3 \cdots n$ and $k$ be a natural number. Define $S(n,k) = \# \{ A \subset [n] \mid \displaystyle\sum_{i \in A} i =k \}$. My question is; Are there any ...
mukhujje's user avatar
  • 281
0 votes
0 answers
58 views

How large must "weak Besicovitch" subsets of groups be?

Consider a group $G$; let call $A\subset G$ a weak Besicovitch subset whenever every element of $G$ can be written under the form $gh^{-1}$, where $g,h\in A$. General question: how large must a weak ...
Benoît Kloeckner's user avatar
0 votes
0 answers
122 views

An exercise about sum-product estimate

I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform". Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
Sei's user avatar
  • 11
0 votes
0 answers
139 views

Additive energy and uniquely representable elements

Suppose that $A$ is a finite, nonempty set in an abelian group. If there is a group element with a unique representation as $a-b$ with $a,b\in A$, then none of $A-A$ and $2A$ are small: $$ \min\{|A-A|,...
Seva's user avatar
  • 22.8k
0 votes
0 answers
152 views

General asymptotic result in additive combinatorics (sums of sets)

Let $S_1,\cdots,S_k$ be $k$ infinite sets of positive integers. Let $N_i(z)$ be the numbers of elements in $S_i$ that are less or equal to $z$. Let us further assume that $$N_i(S) \sim \frac{a_i z^{...
Vincent Granville's user avatar
0 votes
0 answers
58 views

Rewriting a set of integers to get rid of repetition but keeping subset sum ordering

Say, I have a set of 6 +ve integers sorted in ascending order: $A = \{2,4,4,4,5,7\}$ Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them: $\therefore B= ...
Moni's user avatar
  • 11