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
1answer
22 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
40 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
35 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
24 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
75 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
66 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
38 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
40 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
61 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
82 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
55 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
63 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
42 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
48 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
53 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
70 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
100 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
33 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
225 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
180 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
45 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
65 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
25 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
103 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
59 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
38 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
20 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
56 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
65 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
152 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
60 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
58 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
72 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
275 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
152 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
58 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
85 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
29 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
214 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
129 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
49 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
79 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
148 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
57 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 ...