Mathematics Stack Exchange
Mathematics Stack Exchange

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.

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.

393 questions
4
votes
1 answer

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.
Murtuza Vadharia
  • 1,616
4
votes
0 answers

Shapness in a theorem of Schnirelmann

A famous theorem due to Schnirelmann says that: Suppose that $A,B \subset \mathbb{N}_0$, $0 \in A,B$ and $\sigma A + \sigma B \geq 1$. Then $A + B = \mathbb{N}_0$. where $\sigma X := \inf_{n} \frac{|X \cap [1,n]|}{n}$, and $X + Y = \{x + y \ : \ x…
Jakub Konieczny
  • 12,588
3
votes
1 answer

Is every finite set of reals Freiman isomorphic to a set of integers

I believe I remember reading the following claim in a paper (the relevant definitions are recalled below): If $(A,+_A)$ is a torsion-free abelian group and $(\Bbb{Z},+_{\Bbb{Z}})$ is the integers equipped with addition, then for every finite $Z…
Zach Hunter
  • 1,828
3
votes
2 answers

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 ...
Bakshinder
  • 39
3
votes
1 answer

How to obtain a lower bound on the volume of a progression which contains translates of another progression?

I am trying to solve a problem in Tao's Additive Combinatorics(Problem 3.2.2). For any additive set $A$ and a natural number $d$(rank of progression), for vectors ($v_1$,$\cdots$,$v_d$)$\in A^d$, $a\in A$ and collection of natural numbers…
Sai Teja
  • 819
3
votes
0 answers

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 \sim -V$, $|U|\approx |V|$ and $\sigma[U]\approx…
user96343
2
votes
3 answers

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 there of doing this? Someone told me $nPk$ but I…
Dr Dank
  • 21
2
votes
1 answer

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.
Mathemagician
  • 1,112
2
votes
1 answer

$|(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 \mathbb{Z}_n$, $x \neq 0$. Indeed, if $y,z \in…
francis-jamet
  • 2,254
2
votes
0 answers

Does a Freiman $2$-isomorphism have to send $0$ to $0$?

Let $A$ and $B$ be subsets of abelian groups. A Freiman $2$-homomorphism is a function from $\phi:A\to B$ such that if $a_1 + a_2 = b_1 + b_2$, then $\phi(a_1)+\phi(a_2) = \phi(b_1) + \phi(b_2)$. If $\phi$ has an inverse that is also a Freiman…
marcelgoh
  • 1,794
2
votes
0 answers

Ruzsa's covering lemma from Tao-Vu book and some clarification to the statement

I would like to discuss the Ruzsa's covering lemma from Tao-Vu book. The proof given in the book skips some details and I've decided to write all the details just to be sure that I understand everyhting in a correct way. Please read my proof and let…
RFZ
  • 16,814
2
votes
1 answer

Covering almost all naturals by translates of a set

Suppose $A \subseteq \mathbb N^+$ is any arbitrary set. I want to determine under which conditions some finite set of translates $\{A + k_i : 1 \leq i \leq n\}$ of $A$ cover almost all of $\mathbb N^+$, i.e. when there is a finite set of natural…
feralin
  • 1,693
1
vote
1 answer

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 $p^\frac{1}{k-1}$. It gives the hint that the lower bound on…
user38504
1
vote
0 answers

Trivial estimate for iterated sumsets $nA=A+\dots+A$

Let $A$ be an additive set with common ambient group $Z$. Then for any integer $n\geq 1$, we have $$|nA|\leq \binom{|A|+n-1}{n}|A|, \quad \quad (*)$$ where $nA:=\underbrace{A+\dots+A}_{n\ \text{times}}.$ Proof: We argue by induction on $|A|$. If…
RFZ
  • 16,814
1
vote
0 answers

Exercise 2.4.2 from Tao-Vu book

Let $A$ be an additive set in a group $Z$, and let $\phi:Z\to Z'$ be a group homomorphism. Establish the inequalities $$|A|\leq |\phi(A)|\sup \limits_{x\in Z'}|A\cap \phi^{-1}(x)|\leq |2A|.$$ Hint: use the Ruzsa covering lemma to cover $A$ by…
RFZ
  • 16,814
1
2