77
votes
Accepted
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
Here is a counterexample. We first need a "more sums than differences" construction:
Lemma. For any $\varepsilon>0$ there exists a cyclic group ${\bf Z}/N{\bf Z}$ and a non-empty subset ...
- 114k
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 ...
- 47.1k
33
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] \...
- 4,219
18
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 ...
- 10.5k
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 ...
- 34.3k
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 ...
- 85.6k
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 ...
- 7,003
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}$ ...
- 114k
15
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 ...
- 23k
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\}...
- 2,705
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 ...
- 1,538
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 ...
- 50.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 ...
- 23k
13
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, ...
- 23k
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.
...
- 121
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 ...
- 43.7k
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 ...
- 114k
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 ...
- 23k
9
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 ...
- 9,823
9
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) = ...
- 6,337
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 ...
- 5,429
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^...
- 50.8k
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. ...
- 6,337
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 ...
- 4,219
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$...
- 114k
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. ...
- 10.5k
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) = ...
- 27.5k
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)....
- 128k
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,...
- 4,219
6
votes
Accepted
Existence of m infinite subsets in an arbitrary group such that all products of one element from each (in order) are distinct
Yes, such infinite subsets $A_0, \dots, A_{m-1}$ of an infinite group $G$ always exist. We can show this by wedging the problem into one of two polar opposite cases: abelian and ICC (i.e. every non-...
- 3,736
Only top scored, non community-wiki answers of a minimum length are eligible