Additive combinatorics is about giving combinatorial estimates of addition and subtraction operations on Abelian groups or other algebraic objects. Key words: sum set estimates, inverse theorems, graph theory techniques, crossing numbers, algebraic methods, Szemerédi’s theorem.

learn more… | top users | synonyms

1
vote
0answers
43 views

How to prove such inequality?

I have some problems with proof of the inequality: A - is a set. I tried to use Plünnecke-Ruzsa inequality but didn't get any result. It will be great if someone help a little wuth this problem
1
vote
2answers
53 views

Ex. 1.3.10 in Tao's Additive Combinatorics

For $k \geq 2$ and $B \subset \mathbb N$ set $r_{k,B}(n) = |\{ (x_1,\dots,x_k) \in B^k: \sum x_i = n\}|$. The problem at hand is to show that it can not happen that for some $m \geq 1$ that ...
0
votes
0answers
42 views

additive number theory: sums and products of subsets of integers

Suppose that $A$, $B$ are finite subsets of the integers. Consider the subset $E$ of $A+B$ consisting of all elements $s$ of $A+B$ that can be written uniquely as $s=a+b$, where $a\in A$ and $b\in B$, ...
5
votes
1answer
61 views

Find the constant c > 0?

Find a constant c > 0 such that for every finite set of integers B not containing 0, there is a subset A of B such that A is sum-free and |A| ≥ c|B|, where |A| means the number of elements of A.
0
votes
2answers
37 views

Choosing sets yielding large sumsets

I am working on a problem which basically boils down to wanting to choose sets $A_1, \ldots, A_m$ over a group $G=(\mathbb{Z}_C,+)$, where $C$ and $m$ are constants, such that the sumsets defined with ...
2
votes
3answers
44 views

How many ways are there of choosing $k$ distinct items from a set of $n$?

Specifically, say I have the integers $1,2,3,\dots,n$ (a set of $n$ integers). I want to select numbers one after another (not at the same time) until I have $k$ distinct numbers. How many ways are ...
1
vote
0answers
43 views

Tilde Notation in Additive Combinatorics

A, B are some finite subsets of a abelian group. |A + B| ~ |A| The problem is I couldn't precisely understand what does ~ mean in that case. For example, it could be found in notes of Tao's ...
2
votes
2answers
65 views

I need a set that enables me to identify specific containing elements by any summation of any of its subsets (see example to understand)

My question is more practically understood by example. I need a set A that behaves like the one below: Set A: {1,3,5} Set B (all subsets of A): {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5} Set C ...
3
votes
1answer
89 views

How can the smallest set of integers be generated such that the sums cover a given set?

I have a set of positive integers S. I want to generate a set of positive integers T such that every member of S is the sum of some combination of members from T. I am looking for the smallest ...
0
votes
1answer
29 views

Cardinality of finite sets: if $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$, then $|C|^2\ge |A||B|$

Let A be a finite set of real numbers. Suppose $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$. Prove that $|C|^2\ge |A||B|$. I tried to solve this in this way: We claim that the function ...
4
votes
2answers
132 views

Sum of two squares modulo p

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How ...
7
votes
1answer
173 views

Are there any “nontrivial” sets with small difference sets?

I'm trying to find finite sets $S$ of natural numbers with "small" difference sets. One option is just taking an arithmetic progression $S = \{0, , \ldots, n-1\}$. Then $|S - S| = 2 |S| - 1$, which ...
1
vote
0answers
24 views

“Spanning” the difference set of $S$

Suppose that $S$ is a finite set of natural numbers, and $\{(x_i, y_i)\}$ is a set of tuples of numbers in $S$ with $$ \{x_i - y_i\} = S - S := \{a - b \mid a, b \in S\} $$ that is, $\{(x_i, y_i)\}$ ...
1
vote
0answers
41 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...
2
votes
1answer
40 views

What is Vandermonde's formula with multisets?

I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$ ...
1
vote
0answers
22 views

Szemeredi Trotter and additive combinatorics on A+AA

I am trying to get a lower bound on $|A+AA|$ where $A$ is a set, and $A+AA=\{a+bc: a,b,c \in A\}$ using Szemeredi Trotter. I would think we need to form lines of the form $y=ax+b$ where $a,b \in A$, ...
0
votes
0answers
21 views

Generating finite additive groups using sumsets

Let $G$ be a finite additive group and let $A,B \subset G$. The sumset $A+B$ is defined as $A+B = \{a+b \mid a \in A, b \in B\}$, where addition is in $G$. We use $kA$ for short of $A+A+\ldots+A$ with ...
1
vote
2answers
98 views

Looking for references

I am looking for reference on the following problem. Let $S= \{ ax_1+bx_2 \mid x_1 \in X_1 , x_2 \in X_2, \}$ where $X_1,X_2\subseteq \mathbb{R}^n$ and $a,b \in \mathbb{R}$. Note that $a$ and $b$ ...
4
votes
0answers
100 views

Multiplicative subgroup of a finite field with prescribed trace.

Any suggestions/methods/estimates for the following problem would be very appreciated. $l,p$ are primes with $p \equiv 1 \!\! \pmod l$. $r$ is a positive integer with $r \equiv 1 \!\! \pmod p$ and $q ...
5
votes
1answer
55 views

Inequalities that show if a distribution decays slowly

Often, one is often interested in theorems/inequalities of the following kind: Let $X$ be a random variable then the probability that $X$ is close to typically $\mu$ (or larger than some constant) is ...
0
votes
1answer
30 views

Cardinality of sum-set of two arithmetic progressions

Suppose that sum-set $A+B$ between sets $A$ and $B$ is defined as $A+B=\{a+b|a \in A, b \in B \}$. We further assume that $A=\{d_az|z \in \mathbb{Z} \}$ and $B=\{d_bz|z \in \mathbb{Z} \}$ where $d_a$ ...
1
vote
0answers
18 views

Finding an imperfect finite difference set for large N

I want to find a set of integers $N$ for which there always exists a pair of numbers $(a, b)$ both $\in N$ such that $a-b = x$ for all $0<x<2^{32}$. Obviously one possible set N is all the ...
2
votes
1answer
51 views

Sumset magnification ratio strictly smaller for subset.

Do there exist sets $X \subset A \subset \mathbb{Z}$ such that $$\frac{|A+X|}{|X|} < \frac{|A+A|}{|A|} $$? I would also be happy if one can replace $\mathbb{Z}$ with any other abelian group.
2
votes
1answer
63 views

$|(A+x) \cap A| \leq 1$, for all $x \in \mathbb{Z}_n$, $x \neq 0$.

Let $n$ be a positive integer. If $k$ is an integer such that $2^{k+1} \leq n$, then $A=\{1,2,2^2,...,2^{k-1},2^k\}$ is a subset in $\mathbb{Z}_n$ such that $|(A+x) \cap A| \leq 1$, for all $x \in ...
22
votes
5answers
1k 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 ...
3
votes
2answers
136 views

Number-Theoretic Coin Puzzle

There are three piles of coins. You are allowed to move coins from one pile to another, but only if the number of coins in the destination pile is doubled. For example, if the first pile has 6 coins ...
0
votes
0answers
23 views

Proving that any sufficiently large sequence of vectors has zero-summed subsequence

Given $k,d$ I want to prove that any sufficiently large sequence of vectors over ${\pm 1, 0}$ whose sum is in $[-k,k]^d$ has a nonempty proper subsequence whose sum is $\bar 0$. Using probabilisitic ...
1
vote
0answers
58 views

Intersection of subsets of additive groups

Given two subsets $A$ and $B$ of a finite additive group $Z$, how can one show that there exists an element $x$ in $Z$ such that $$1 - \frac{|A \cap (B + x)|}{|Z|} \le \left(1 - ...
0
votes
1answer
50 views

Bounds on cardinality of sum-sets. [duplicate]

Let $X\subset \mathbb{R}$ and $Y \subset \mathbb{R}$ where X and Y have finite cardinalities. Let also, $a,b \in \mathbb{R}/0$. What can we say about cardinality $|aX+bY|=????$ For example we can ...
1
vote
0answers
65 views

Cardinality of sum-set

Let $X\subset R$ and $Y \subset R$ where X and Y have finite cardinalities. Let also, $a,b \in R$. How to show that $|aX+bY|=|X||Y|$ almost everywhere (measure of $(a,b) \subset R^2$ such that ...
8
votes
1answer
202 views

Is the Green-Tao theorem a consequence of the Euler's theorem?

The Erdős-Turán conjecture states that If $A\subset\mathbb{N}$ is such that $$ \sum_{n\in A} \frac{1}{n} = \infty,$$ then $A$ contains arithmetic progressions of any given length. I'm ...
1
vote
1answer
23 views

Testing density with a countable family

Let $d$ denote the lower density on $\mathbb{N}$, $a>0, $ $\mathbb{N}_{a}:=\left\{ B\subset\mathbb{N}:{d}(B)\geq1-a\right\} $ and $A\subset\mathbb{N}$. If $A\cap B\neq\emptyset$ for every ...
2
votes
1answer
26 views

Reasoning about Schnirelmann Density: Proving that $d(C) \ge d(A) + d(B)$

I am taking this argument from Gelfond & Linnik's Elementary Methods in the Analytic Theory of Numbers. They state if for every $n \ge 1$, there exists $m \in [1,n]$ where $C(n) - C(n-m) \ge ...
2
votes
1answer
134 views

Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $ |f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...
2
votes
2answers
55 views

4 squares almost in an arithmetic progression

It is well known that the exists no arithmetic progression of squares of length $4$. But consider the following arithmetic progression of length $5$: $49,169,289,409,529$. All terms apart from the ...
1
vote
0answers
77 views

Rate of convergence of $n$-fold convolution over $\mathbb{Z}_p$.

Suppose that $\mu$ is a probabilist measure on $\mathbb{Z}_p$ such that $d_{TV}(\mu,\mu_U)\leqslant \delta < 1$. What are the best upper bound on $$ d_{TV}(\underbrace{\mu*\mu*\ldots*\mu}_{n ...
0
votes
1answer
25 views

Bounds on an additive combinatorics problem (just looking for references)

I'm looking for known results of a problem, but i don't know the right terms to look for. What is the minimal number $a$, s.t. any subset $A\subseteq \mathbb{Z}_3^n$ $\ \ \ |A|\ge a$, contains 3 ...
12
votes
2answers
208 views

Special subdivision of numbers from 1 to 99

I've been lately working on a problem I still can't solve. The problem is: Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the ...
2
votes
1answer
113 views

Cauchy-Davenport theorem and its extension

According to Cauchy-Davenport Theorem, if $A,B$ are subsets of a prime field ($F_p$) then we have the following bound on the number of elements within the sumset $A + B = \left\{ {\left. {a + b} ...
1
vote
0answers
46 views

Maximal size of an almost-disjoint linearly independent family in $K^{\mathbb{N}}$

Let $K$ be a field, say infinite, and denote by $L$ the $K$-vector space $K^{\mathbb{N}}$. What is the maximal cardinality of a $K$-linearly independent subset $X$ of $L$ such that any two distinct ...
0
votes
1answer
76 views

Lower bound for quotient sets

Exercise 2.8.6 from Tao and Vu's Additive Combinatorics asks: Given a subset $A\subset\mathbb{F}_p$ with size $|A|>p^\frac{1}{k}$ $(k\geq 2)$, show $\frac{A-A}{A-A}$ has size at least ...
5
votes
1answer
141 views

Show there’s at most $n\choose \left \lfloor\frac{n}{2} \right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that ...
3
votes
0answers
54 views

Cubic sum of Gauss integers

It's known that any Gauss integer can be represented as the sum of three Gauss integer squares. (See my another problem.) Let $A$ be a set, define $nA=\{x\mid x=a_1+a_2+\cdots a_k,a_i\in A,1\leq ...
6
votes
2answers
107 views

Quadratic sum of Gauss integers

Let $A$ be a set, define $nA=\{x\mid x=a_1+a_2+\cdots a_k,a_i\in A,1\leq k\leq n\}$. Denote $G=\{z\mid z=(a+bI)^2,a,b\in \mathbb Z,I=\sqrt{-1}\},K=\{z\mid z=a+2bI,a,b\in \mathbb Z,I=\sqrt{-1}\}$ ...
1
vote
1answer
759 views

The number of solutions for $x+y+z=n$ [duplicate]

How do I approach this problem? I know the formula but do not how it had come. Could you please explain to me the procedure, with examples if possible. stars and bars theorem
1
vote
1answer
176 views

Learning roadmap for additive combinatorics

I have read Calculus by Michael Spivak. Now I want to learn additive combinatorics though I have no experience with combinatorics or probability theory. To my understanding, there is a book on the ...
1
vote
0answers
81 views

Learning roadmap for additive combinatorics

I have read Calculus by Michael Spivak. Now I want to learn additive combinatorics though I have no experience with combinatorics or probability theory. To my understanding, there is a book on the ...
3
votes
1answer
64 views

Sum of two finite sets in torsion-free abelian groups

Suppose $G$ is a torsion-free abelian group (written additively) and $A$ and $B$ are two nonempty finite subsets (not subgroups) of $G$. Is it true that there is an element of $G$ which may be ...
0
votes
1answer
104 views

Property of finite basis free abelian group

I am trying to understand the following (from Munkres) Thm: If G, a free abelian group, has basis $\{a_1,...,a_n\}$, then $n$ is uniquely determined by G. What does this mean ? What exactly is being ...
22
votes
2answers
372 views

About translating subsets of $\Bbb R^2.$

I'm looking for a pair of sets $A,B$ of points in $\Bbb R^2$ such that $A$ is a union of translated (only translations are allowed) copies of $B;$ $B$ is a union of translated copies of $A;$ $A$ is ...