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

2
votes
1answer
31 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
17 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
20 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
90 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
97 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 ...
4
votes
1answer
43 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
26 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
17 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
45 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
61 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
115 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
21 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
55 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
42 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
56 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 ...
7
votes
1answer
146 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
22 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
112 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
54 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
61 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
22 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
197 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
93 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
44 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
0answers
31 views

Lower bounds exercise on 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 ...
0
votes
1answer
73 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
133 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 ...
2
votes
0answers
45 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
99 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
416 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
0
votes
0answers
47 views

2-colorings of arithmetic progression

Consider the following classical result: $\forall r \in \mathbb N : \exists N\in \mathbb N$ such that every 2-colored arithmetic progression of length N contains a monochromatic arithmetic ...
1
vote
1answer
152 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
68 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
62 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
151 views

Combination problem

There are N advertisement boards of which M consecutive boards should have at least K advertisements. How to find number of ways in which this is possible keeping cost minimum. Eg: N=6,M=3,K=2 which ...
0
votes
1answer
88 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
345 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 ...
3
votes
2answers
98 views

Combinatorics Catastrophe

How will you solve $$\sum_{i=1}^{n}{2i \choose i}\;?$$ I tried to use Coefficient Method but couldn't get it! Also I searched for Christmas Stocking Theorem but to no use ...
2
votes
2answers
144 views

Converse of the Erdős Conjecture on Arithmetic Progressions

Clearly, the question of whether large sets always contain arbitrarily long arithmetic progressions is an open question. So my question is not about this conjecture. Instead, it is about the ...
3
votes
1answer
67 views

Minimal set with same Schnirelmann Density

Define the Schnirelmann density of a set of integers by $\sigma(A) = \inf_{n \in \mathbb N} \frac{A(n)}{n}$ where $A(n)$ is the number of elements of $A$ which are $\le n$. I would like a proof that ...
0
votes
1answer
48 views

definition of $l$-equivalence

In the following paper http://www.math.ucsd.edu/~ronspubs/74_01_van_der_waerden.pdf, just in the first paragraph the author defines what $l$-equivalence for two m-tuples $\in [0,l]^m$ means. Can ...
4
votes
0answers
393 views

Has Erdős conjecture on arithmetic progressions been proved?

The conjecture states that if $A$ is a set of natural numbers and $$\sum_{n\in A}\frac1n=\infty,$$ then $A$ contains arbitratily long arithmetic progressions. I wonder has it been proved?
3
votes
2answers
133 views

A lower bound for Waring's Problem for sufficiently large numbers: $G(k) \ge k+1$

I need to show that, if $G(k)$ is the solution to Waring's Problem for $k$ and for sufficiently large $n$, then: $$G(k) \ge k + 1$$ So I need to establish that: $$x_1^k + x_2^k + \dots + x_k^k = n ...
3
votes
1answer
68 views

$ x_1 + x_2 + x_3 +\cdots + x_m = k $

What I'm tyring to show is the number of solutions to the equation of natural numbers; $$ x_1 + x_2 + x_3 +\cdots + x_m = k $$ is equal to $$ \binom{m + k - 1} m $$ To be blunt, I have no idea ...
0
votes
1answer
77 views

Simple Additive Combinatorics problem

In Terence Tao's book, Additive Combinatorics, page 70, it says: For instance, if one knows that $$ A + B \subseteq A + X $$ then one can immediately deduce that $$ A + n B \subseteq ...
2
votes
0answers
129 views

Discete Fourier Transform-Additive Combinatorics

Although I am not completely familiar with the subject but I have met two 'dual' definitions of the Discrete Fourier Transform of a function $ f: \mathbb{Z} / N \mathbb{Z} \rightarrow \mathbb{C} $ , ...
1
vote
1answer
149 views

Exact inverse sum set theorem from Terence Tao's book

There is a theorem In Terence Tao's Additive Combinatorics: Proposition 2.2 (Exact inverse sum set theorem) Suppose that $A$, $B$ are additive sets with common ambient group Z . Then the ...
1
vote
1answer
99 views

The number of subset sum

If we have that $S=\{1,2,3,4,5,6,7,8,9,10\}$,how to know the number of subset sum T from :S in which for every $x\in T$ and for every $2x\in S $ then: $2x \in T$