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

3
votes
0answers
122 views

Why is $\sigma[U]\approx 1 $?

I was reading Ben Green's notes on additive combinatorics and there he writes the following proposition : Suppose $U,V$ be subsets in some ambient abelian group $G$. Suppose that $U \sim V$. Then $U ...
5
votes
0answers
168 views

Understanding an example of a prime-like non-finite additive basis

In this answer on MO, the user Gene S. Kopp gives an example of a relatively "big" set $A\subset \mathbb{N}$ with relatively "small" gaps that fails to be an asymptotic finite basis. I'm having a ...
1
vote
3answers
94 views

Probability addition rule over 100 percent?

In Texas holdem, one is dealt a Decent Hand (Any pocket pair or any two broadway cards) ~15 percent of the time. If there are three people left in the hand, I can use the probability addition rule to ...
6
votes
1answer
66 views

Is there any general method for solving $(a_1+a_2+..a_n)^2=a_1^3+a_2^3+…+a_n^3$ in positive integers $a_1,a_2,…a_n$?

We know the identity $(1+2+...+n)^2=1^3+2^3+...+n^3$ . So I was thinking , for given $n\in \mathbb N$ , is there any general method for solving $(a_1+a_2+..a_n)^2=a_1^3+a_2^3+...+a_n^3$ in positive ...
1
vote
0answers
22 views

Rusza triangle inequality and approximate groups.

Feel free to scroll down to the "Question" section if you're familiar with the notation of Tao and Vu's Additive Combinatorics, which I believe is standard notation for the field. Notation Let $Z$ ...
0
votes
0answers
36 views

Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and their applications.

While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem: Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$. I came across with ...
1
vote
0answers
73 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
1
vote
2answers
36 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...
0
votes
1answer
46 views

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes?

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes ?
3
votes
1answer
43 views

Is it true that every sufficiently large positive integer can be written as a sum of a square free number and a perfect square ?

Is it true that $\exists k \in \mathbb Z^+$ such that every integer $n >k$ can be written as a sum of a square free number and a perfect square ?
1
vote
1answer
27 views

Possible configurations on the subset problem

Let $A=\left\{ a_{i}\right\} $ be a sequence of $n$ positive numbers such that $\sum a_{i}=1$. We define $C\left(A\right)=\left\{ \left\{ b_{i}\right\} \subset\left\{ 1,2..,n\right\} :\sum ...
3
votes
1answer
81 views

To determine number of arrangements of 4 letters in a word so that the transitions remains conserved

A 10 letter word is composed of $A,\ B,\ C,\ D$. The problem is to find the number of arrangements of these alphabets which could lead to fixed number of transitions between each pair of alphabets. ...
2
votes
1answer
38 views

Sufficient conditions such that $A+xB= \mathbb{Z}/n\mathbb{Z} $

I'm working in an exercise and I need some results about additive theory of numbers, I encountered this problem: Given an element $x\in \mathbb{Z}/n\mathbb{Z}$ and two subsets $A$ and $B$ of $ ...
3
votes
1answer
69 views

Asymptotic expression for $3$ term arithmetic progression in the primes

I have found an asymptotic for the following sum using the circle method: \begin{align} R(n)=\sum_{\substack{p_1,p_2,p_3 \le n \\p_1+p_2=2p_3 }} \log (p_1) \log (p_2) \log ...
2
votes
1answer
43 views

Inequality of sizes of finite sets

For a set $A\subset \mathbb N$, define $$A+c\cdot A=\{a+c\cdot a'|a,a'\in A\}$$ Is it true that for every such finite set $A$ $$\frac{|A+2A|}{|A|}\leq\left(\frac{|A+A|}{|A|}\right)^3$$?
1
vote
1answer
44 views

Approximate groups

I am reading the article "The structure of approximate groups" by Breuillard, Green and Tao. At some point they state the following theorem 1.6: Let A be a K-approximate subgroup of a group G. Then ...
1
vote
1answer
66 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
90 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 ...
1
vote
0answers
58 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
70 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
43 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
49 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
58 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
73 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 ...
4
votes
1answer
109 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
34 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
302 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
184 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
26 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
49 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
71 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
27 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$, ...
1
vote
2answers
99 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
107 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
63 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
52 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
21 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
61 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
66 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 ...
23
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
155 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 ...
1
vote
0answers
65 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
64 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
77 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
365 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
24 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
29 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
156 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
60 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
89 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 ...