38 votes
Accepted

What is the minimal density of a set A such that A+A = N?

Let $A_{\mathrm{even}}$ ($A_{\mathrm{odd}}$) be the set of integers whose binary expansion has $0$ at every even (odd, respectively) position, and $A=A_{\mathrm{even}}\cup A_{\mathrm{odd}}$. Then all ...
Emil Jeřábek's user avatar
32 votes

What is the minimal density of a set A such that A+A = N?

It is easy to see that quadratic density is both required and sufficient. The question is then of the leading coefficient. Let $A$ be such that $A+A = \mathbb{N}$, and let $A(n) = \lvert A \cap [0,n] \...
Jukka Kohonen's user avatar
17 votes
Accepted

what is the status of this problem? an equivalent formulation?

In a recent paper A set of 12 numbers is not determined by its set of 4-sums (in Russian), Isomurodov and Kokhas identify an error in the argument of Ewell (1968) and present two distinct sets of 12 ...
Max Alekseyev's user avatar
17 votes
Accepted

Sets that are not sum of subsets

There are three questions in the OP, and I'll try to address each of them in as comprehensive a way as I can. I'll be glad to add in further details (and references) if requested. ◇ Preliminaries on ...
Salvo Tringali's user avatar
17 votes
Accepted

Subsets of $(\mathbb{Z}/p)^{\times n}$

There is an alternative elementary way to prove this and see where the number $\frac{p^n-1}{p-1}+1$ comes from. Lemma: If $|A|\geq \frac{p^n-1}{p-1}+1$ then every point in $\mathbb F_p^n$ lies in a ...
Gjergji Zaimi's user avatar
16 votes
Accepted

Explicit constant in Green/Tao's version of Freiman's Theorem?

Even-Zohar (On sums of generating sets in $\mathbb{Z}_2^n$, Combin. Probab. Comput. 21 (2012), no. 6, 916–941, available at https://arxiv.org/abs/1108.4902) has proved a completely explicit and sharp ...
Thomas Bloom's user avatar
  • 6,608
16 votes

Subsets of $(\mathbb{Z}/p)^{\times n}$

From Theorem 10 of Bollobás, Béla; Leader, Imre, Sums in the grid, Discrete Math. 162, No. 1-3, 31-48 (1996). ZBL0872.11007. we know that if $A_1,\dots,A_k$ are subsets of $({\bf Z}/p)^{\times n}$ ...
Terry Tao's user avatar
  • 108k
14 votes
Accepted

Does $g+A\subseteq A+A$ imply $g\in A$?

This is not the case. Here is a counter example. Let $G =Z_m, \ \ m>20$ (say). Let $A = \{0, 1, 3, 4, 6\}; g=2$: Note that $g+A=\{2, 3, 5, 6, 8\} \subseteq \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12\}...
Christian Elsholtz's user avatar
14 votes

The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets

The keyword you are looking for is "zonotope", which is defined to be the Minkowski sum of line segments. An early reference for zonotope is: P. McMullen, “On zonotopes”, Transactions of the American ...
Abhishek Halder's user avatar
14 votes
Accepted

The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets

Let $M$ be the matrix whose rows are the vectors $\boldsymbol{h_i}$. Then the $r$-dimensional volume of $\mathcal{S}=\mathcal{S}_1+\cdots+\mathcal{S}_n$ is equal to the sum of the absolute values of ...
Richard Stanley's user avatar
14 votes

Decomposing a finite group as a product of subsets

This problem, first raised in 1937 by H. Rohrbach, has been considered, for instance, in the paper "On $h$-bases and $h$-decompositions of the finite solvable and alternating groups" (J. Number theory ...
Seva's user avatar
  • 22.8k
14 votes

Sets that are not sum of subsets

Sure, this has been studied, and various generalizations are known (infinite sets, three and more set summands, abelian groups other than the group of integers, asymptotic decompositions). You can ...
Seva's user avatar
  • 22.8k
12 votes

Is the sumset or the sumset of the square set always large?

Six years later it's hard to know if this is still a question of interest. For the record (since I stumbled across the question), the answer is yes and it's a consequence of a more general phenomenon. ...
Sophie Stevens's user avatar
12 votes
Accepted

Decomposing a finite group as a product of subsets

It was brought to my attention by Noga Alon that my previous answer (which I keep to avoid any confusion) was in fact incorrect: the Rohrbach conjecture got solved completely by Finkelstein, Kleitman, ...
Seva's user avatar
  • 22.8k
11 votes
Accepted

Size of sets with complete double

Let $S\subset [1,N]$ with $S+S=2N$. I will show that $S$ must have at least $(2.033 +o(1))\sqrt{N}$ elements for large $N$. The argument can certainly be improved, but I don't know what the right ...
Lucia's user avatar
  • 43.3k
11 votes
Accepted

Estimate of Minkowski sum

This is only a partial answer to your question; I believe there is more current work, and have forwarded your question to someone working in this area to see if they have more recent results. In ...
Terry Tao's user avatar
  • 108k
10 votes
Accepted

sum-sets in a finite field

It took me some effort to find the references you were requesting in your comment, but here they are eventually: Ordering subsets of the cyclic group to give distinct partial sums (posted to MO ...
Seva's user avatar
  • 22.8k
8 votes

Decomposing a finite group as a product of subsets

An update: following a lead from Seva's answer, I discovered in that their 2003 paper Communication Complexity of Simultaneous Messages, Babai, Gal, Kimmel, and Lokam (see Section 7, "Decompositions ...
Scott Aaronson's user avatar
8 votes

Minkowski sum of polytopes from their facet normals and volumes

There is no simple description. A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then $$ F_u(P+Q) = ...
Ivan Izmestiev's user avatar
8 votes
Accepted

Does $|A+A|$ concentrate near its mean?

If $\epsilon>1/6$ then $|A+A|=N$ with high probability. Suppose that $\epsilon<1/6$. Call a pair $(x,y) \in {\mathbb Z}/N{\mathbb Z} \times {\mathbb Z}/N{\mathbb Z} $ "bad" if $(x,y) \in A \...
Yuval Peres's user avatar
8 votes

Size of sets with complete double

For a fixed $n$, you can solve the problem via integer linear programming. For $j \in [n]$, let binary decision variable $x_j$ indicate whether $j\in S$. For $0\le j_1\le j_2 \le n$, let binary ...
RobPratt's user avatar
  • 5,159
8 votes
Accepted

Different sum combinations of $L$ identical lists of consecutive natural numbers

You are asking for the number of compositions of $s$ into $L$ parts, with largest part at most $N$. This is a classical problem, equivalent to finding the coefficient of $x^s$ in the polynomial $(x+x^...
Richard Stanley's user avatar
7 votes

Do Minkowski sums have anything like calculus?

A convenient way to think about it is to represent a convex body in terms of its support function (restricted to the unit sphere). Minkowski addition corresponds to the addition of support functions. ...
Ivan Izmestiev's user avatar
7 votes
Accepted

Trisecting $3$-fold sumsets, II: is the middle part ever thin?

The title and body are asking the question in opposite senses. For the title, the answer is "yes" (it can be thin), and for the body, the answer if "no" (it is not true that it is ...
Jukka Kohonen's user avatar
6 votes

Some question on haar measure for sumsets of closed subsets of profinite groups

Yes. Consider $H_1H_2$ as a subset of $H$. This is a $H_1\times H_2$ homogeneous space (for left-times-right action). On such a space there is a unique (up to scale) $H_1\times H_2$-invariant measure. ...
Uri Bader's user avatar
  • 11.4k
6 votes

sum-sets in a finite field

I first learned about this problem from Éric Balandraud (in 2013). So I wrote to him a couple of days ago, and he has just sent me an e-mail explaining that the question dates back (at least) to 1971. ...
Salvo Tringali's user avatar
6 votes
Accepted

Limit measuring failure of sum-set cancellability

$m(A,B)$ may be computed as follows. By translation we may assume that $A,B \subset [1,k]$ for some natural number $k$. Let $V = 2^{[1,k]}$ denote the power set of $[1,k]$. Observe that a subset $C$...
Terry Tao's user avatar
  • 108k
6 votes

Do Minkowski sums have anything like calculus?

There is a theory for convex bodies. If $A, B \subset \mathbb{R}^n$ are convex bodies, whose interiors contain the origin, you can use set addition to define $A+tB$, for any $t \ge 0$, and $$ V(A,B) = ...
Deane Yang's user avatar
  • 26.9k
6 votes

Probability of getting two subsets with the same sum

Assuming the two subsets are selected independently, the probability in question is $$p_n=a_n/2^{2n},$$ where $a_n$ the sum of the squares of the coefficients in the polynomial $$\prod_{k=1}^n (1+x^k)....
Iosif Pinelis's user avatar
6 votes
Accepted

Trisecting $3$-fold sumsets: is the middle part always thick?

No. Take $A = \{0,1,\ldots,9,10,20,30,\ldots,90,100,200,300,\ldots,900,1000\}$. Then $|C_1|=1001$, $|C_2|=272$ and $|C_3|=29$. A smaller counterexample in the same spirit is $\{0,1,2,3,4,5,10,15,20,25,...
Jukka Kohonen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible