The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
230 views

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

Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...
2
votes
4answers
107 views

Show that the Minkowski sum of two triangles in 3D is the union of Minkowski sums of each triangle along the other's edges?

I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all ...
3
votes
2answers
99 views

Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ ...
3
votes
2answers
261 views

Sumsets with distinct numbers, upper bound for maximum element

Let $A$ be a finite set of positive natural numbers with $n$ elements, $|A|=n$, with the property that all sums of two (not necessarily different) elements are distinct, or in the usual notation for ...
0
votes
1answer
58 views

Set of number with unique sums of elements [closed]

Is it possible to construct a set of numbers of arbitrary size such that any calculation involving addition and subtraction, on any combination of those numbers, produces a unique result? For ...
4
votes
2answers
310 views

Can you simplify (or approximate) $\sum_{n=0}^{N-1}\begin{pmatrix}N-1\\n\end{pmatrix}\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\begin{pmatrix}x\\y\end{pmatrix}$ be the binomial coefficient. I am trying to get a better understanding of the sum \begin{equation} ...
0
votes
1answer
35 views

determine elements of a sum given set

Is it possible to efficiently find the elements that make up a sum $S$ given a set of number sets which determine the sum elements? It seems like an NP-Complete problem, though I might miss something. ...
2
votes
1answer
189 views

Asymptotic of a sum involving binomial coefficients

Good evening, I'm trying to find an asymptotic of this sum: $$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - ...
3
votes
2answers
306 views

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

Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$. Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity: $$\max ...
0
votes
0answers
74 views

Distortion of the Hausdorff dimension of sums of Cantor sets under local scaling

The following question deals with possible distortion of the Hausdorff dimension of sums of Cantor sets as one "zooms in" on the sum around any given point. Let us assume that $C_1$ and $C_2$ are two ...
9
votes
1answer
298 views

Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems: Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...
10
votes
2answers
403 views

Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?

The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly. Is it true that for any finite set $A$ of real numbers, and any real ...
5
votes
1answer
206 views

Element with unique representation in A+B

Let $A, B \subseteq \mathbb{Z}$ be finite subsets of the integers. Then there exists an element in $A+B$ with a unique representation as a sum of an element in $A$ and an element in $B$, namely ...
2
votes
1answer
119 views

On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let $$ Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}. $$ I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then $$ ...
13
votes
1answer
401 views

Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$. I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...
12
votes
1answer
224 views

Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$). If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...
3
votes
0answers
154 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 ...
3
votes
3answers
350 views

How to find an integer set, s.t. the sums of at most 3 elements are all distinct?

How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different. Example with $|A|=3$: Out of the set $A ...
1
vote
0answers
50 views

$B_k[1]$ sets with smallest possible $m = max B_k[1]$ for given $k$ and $n = |B_k[1]|$ elements

Sidon sets are sets $A \subset \mathbb{N}$ such that for all $a_j,b_j \in A$ holds $$a_1+a_2=b_1+b_2 \iff \{a_1,a_2\}=\{b_1,b_2\}$$ Thus if you know the sum of two elements, you know which elements ...
7
votes
1answer
217 views

Sumsets and a bound

Let $q$ be a positive integer. Is it true there exists a constant $C_q$ such that the following inequality holds for any finite set $A$ of reals: $$\displaystyle |A+qA|\ge (q+1)|A|-C_q\qquad (1)$$ I ...
24
votes
1answer
509 views

Distribution of $a^2+\alpha b^2$

It is well known that size of the set of positive integers up to $n$ that can be written as $a^2+b^2$ is asymptotic to $C \frac{n}{\sqrt{\log n}}$. Here I'm interested mostly in the weaker fact that ...
20
votes
3answers
662 views

A sumset inequality

A friend asked me the following problem: Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$ ...
20
votes
4answers
2k views

Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 ...
8
votes
1answer
468 views

Lower bounds for $|A+A|$ if $A$ contains only perfect squares

Let $A$ a set with $|A|=n$ that contains only perfect squares of integers. What lower bounds can we give for $|A+A|$? I think the lower bound $\gg \frac{n^2}{\sqrt{log \,n}}$ holds (this would be ...
2
votes
0answers
132 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 ...
4
votes
2answers
247 views

Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think. I am interested in anything (ideas, references) related to the following problem: Suppose that $A ...
4
votes
1answer
355 views

A problem related with 'Postage stamp problem'

A friend of mine taught me this question. I found that it is related with 'Postage stamp problem' (though it does not seem to be same). Let $m,a_1\lt a_2\lt \cdots\lt a_n$ be natural numbers. Now let ...
13
votes
1answer
485 views

Size of a certain sumset in $\mathbb{Z}/p^2\mathbb{Z}$

We are interested in estimating the size of a certain sumset in $\mathbb{Z}/p^2\mathbb{Z}$. Let $p$ be an odd prime, $g$ a primitive root modulo $p^2$, and $A=\langle g^p\rangle$ the unit subgroup of ...
8
votes
2answers
541 views

A sum-product estimate in Z/p^2Z

We are interested in a sum-product type estimate. Let $p$ be an odd prime, and let $A$ be the order $p-1$ subgroup of $(\mathbb{Z}/p^2\mathbb{Z})^\times$. That is, let $A = \langle g^p \rangle$, where ...
1
vote
3answers
273 views

how to proof this Stirling related equation

here is what I need to proof, have no idea were to start. I know there is some connection with the Stirling theorem. $$ \sum_{i=0}^{d}\binom{m}{i} \leq \left ( \frac{em}{d} \right )^{d} $$ I tried ...
1
vote
1answer
173 views

unique sums in a finite direct product of sets of integers

I am an algebraist, and I am wondering if there is a definition for the following: Let $A_1$, $A_2$, $\ldots, A_n$ be sets of integers (or more generally, subsets of a group $G$). Say that (for the ...
3
votes
1answer
376 views

Additive set with small sum set and large difference set

I have a question! Can someone explain how (the intuition, method?) one can try to construct an additive set of cardinality $N$ with a small sum set (around $N$) and a very large difference set ...
9
votes
0answers
579 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 ...
1
vote
1answer
183 views

Find an approximate expression of a sum of a product using the average of each item

Is it possible to find an approximate expression of $\frac{\sum_{i=1}^{n} k_i x_i}{\sum_{i=1}^{n} k_i}$ using $\langle k \rangle$, $\langle k^2 \rangle$, $\langle x \rangle$, and $n$? Alternatively if ...
4
votes
1answer
462 views

Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now. The most ...
15
votes
1answer
519 views

The hypercube: $|A {\stackrel2+} E| \ge |A|$?

I have a good motivation to ask the question below, but since the post is already a little long, and the problem looks rather natural and appealing (well, to me, at least), I'd rather go straight to ...