# Questions tagged [additive-combinatorics]

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.

337 questions
Filter by
Sorted by
Tagged with
1 vote
0 answers
24 views

• 839
5 votes
0 answers
59 views

### Maximum element of two integer sets with distinct pairwise sums?

Let $A, B \in Z^+$ be two sets where $|A|=m, |B|=n$. If all pairwise sums $a+b (a\in A, b\in B)$ are distinct, a.k.a. $|A+B|=|A||B|$, what would be the minimum value of $max(A\cup B)$? A trivial bound ...
0 votes
0 answers
20 views

### Highest-sum seeding path through a 2^n NCAA tournament?

This discussion came up among Purdue fans discussing their path to the Final 4 and comparing it to Houston's from last year. Purdue, if they can get by St. Peter's and #8 North Carolina beats #4 UCLA, ...
• 374
0 votes
1 answer
35 views

### If $G, H$ are approximate groups that $2G\cap 2H$ is also approximate group

Let $G$ be a $K$-approximate group in an ambient group $Z$, and let $H$ be a $K'$-approximate group in $Z$. Show that $2G\cap 2H$ is a $(KK')^3$-approximate group. Attempt of proof: First of all it is ...
• 14.7k
3 votes
1 answer
79 views

### Problem 2.4.8 rom Tao-Vu book

For each $j=1,2,3,$ let $G_j$ be a $K_j$-approximate group in an ambient group $Z$. Using the Ruzsa triangle inequality, show that $$|G_1+G_2+G_3|\leq K_2\dfrac{|G_1+G_2||G_2+G_3|}{|G_2|}.$$ Conclude ...
• 14.7k
3 votes
1 answer
78 views

### Exercise 2. 3. 8 from Tao-Vu's Additive Combinatorics

Problem: Let $A$ be an additive set in an additive group $Z$ and let $G$ be a finite subgroup of $Z$. Show that $$\sigma[A + G] \leq \frac{|3A|}{|A|}.$$ Conclude that if $\pi: Z \to Z'$ is a group ...
0 votes
1 answer
63 views

### Corollary 2.24 from Tao-Vu on asymmetric sum set inequalities

I am trying to solve exercise 2.4.3 from Tao-Vu book Prove Corollary 2.24. What value of the implicit constant in the $O()$ notation do you get? Corollary 2.24 (Asymmetric sum set inequalities, ...
• 14.7k
1 vote
0 answers
40 views

5 votes
1 answer
82 views

### Is there an examble of a non additive base of natural numbers with ratio of two consecutive terms goes to 1?

Here $\mathbb{N}=\{1,2,3,\dots\}$. We say that a set $A\subset\mathbb{N}$ is an additive base of natural numbers if there is a positive integer $h\in \mathbb{N}$ such that every natural number can be ...
1 vote
1 answer
252 views

• 7,119
8 votes
2 answers
172 views

• 13
2 votes
0 answers
106 views

### Reference for solved exercises in additive combinatorics

I am aware that additive combinatorics is a relatively new subject and there are not many books available. I will be grateful if anybody can tell me about some source where I can find a few solved ...
• 1,270
0 votes
1 answer
74 views

• 75
5 votes
0 answers
44 views

### Number of lines of $3$ points in an arrangement of points and lines

It is well known that a finite set of $n$ points cannot form more than $$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1$$ lines that include $3$ points. Would this result still hold if we assume that ...