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

0
votes
0answers
11 views

When does the equality hold in Dias da Silva - Hamidoune Theorem?

Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
1
vote
0answers
33 views

Sumset achieving extreme upper bound.

It is trivial that $|A_1 + \cdots + A_h| \leq |A_1|\cdots |A_h|$, where $h \geq 2$ and $A_i \subseteq \mathbb{Z}$ are nonempty finite sets and $A_1 + \cdots + A_h :=\{a_1 + \cdots + a_h : a_i \in A_i ~...
2
votes
1answer
53 views

Proof of Lagrange's four square theorem using Cauchy-Davenport Theorem

Cauchy used the Cauchy-Davenport theorem to prove that $ax^2 + by^2 + c \equiv 0 \pmod p$ has solutions provided that $abc \neq 0$. Lagrange used this result to establish his four squares theorem. I ...
2
votes
1answer
24 views

Lower bound for arithmetic progressions in sumsets

I'm reading some lecture notes and get stuck on one detail. We wish to prove the following: (1) Let $\alpha > 0$ and $A \subseteq [N]$ be of size $\geq$ $\alpha N$. Then $A + A + A$ contains an ...
2
votes
3answers
133 views

Show that $|A+A|\geq (2n-1)$

Consider a set $A$ consisting of $n$ natural numbers $\{a_i\}_{i=1}^n$ such that $a_1<a_2 < \cdots <a_{n-1} < a_n$. Define the set $A+A$ such that it contains $a_i + a_j \ ; \ i \leq j$ as ...
2
votes
1answer
49 views

Additive combinatorics and $|S \cap (S+t)| \geq K |S|$ over $\mathbb{F}_2^n$

I don't know much about additive combinatorics, and I am wondering if there are results concerning the size of $|S \cap (S+t)|$ where $S \subset \mathbb{F}_2^n$ and $t \in \mathbb{F}_2^n$. Especially, ...
0
votes
1answer
80 views

Understanding Ziv's proof of zero sum problem .

I was going through the proof of zero sum problem in one dimension as provided by Abraham Ziv. The problem statement is to prove that given a set of $2n+1$ integers, we can find at least $n$ integers ...
1
vote
1answer
34 views

About finding formula for an additive-combinatorial quantity

The definitions: Let $n \in \mathbb{Z}^+$. A positive integer $L$ is called $n$ -magnificent if in every partition of $\{ 1, ... , L \}$ into $n$ non-empty parts, at least one part contains an ...
1
vote
1answer
24 views

A set such that $A$, $A+A$ have density zero but $A+A+A$ has positive density.

I have been thinking about Lagrange's theorem in terms of sumsets. Certainly the perfect squares $\square = \{ n^2: n \in \mathbb{Z}\} = \{ 0,1,4,9,\dots\}$ has density $0$. In fact, I think $$ \...
5
votes
0answers
51 views

Sets of natural numbers which are almost closed under addition

I am interested in a classification of sets $A \subseteq \mathbb{N}$ such that for all $k \in A$, $d( A+k \cap \mathbb{N} \setminus A) = 0$ where $d$ is the asymptotic density and $A+k = \{n \in \...
0
votes
0answers
10 views

Relation between support of a function and that of its DFT

Let $f : \mathbb{Z}_N \to \mathbb{C}$, let $\zeta_N$ be a primitive $N$-th root of unity and let $\hat{f} : \mathbb{Z}_N \to \mathbb{C}$ be the DFT of $f$ given by $\hat{f}(m) = \sum_{n \in \mathbb{Z}...
1
vote
0answers
15 views

Show that $ \sum_{\mathbb{Z}/N\mathbb{Z}} f(n) g(n+r)h(n+2r) = \sum_{a \in \mathbb{Z}/N\mathbb{Z}} \hat{f}(a)\hat{g}(-2a)\hat{h}(a)$

I found this Fourier series identity in a book on Harmonic analysis but the proof is inclear. Maybe it makes more sense using bra-ket formalism. $$ \sum_{r, n \in \mathbb{Z}/N\mathbb{Z}} f(n) g(n+r)...
2
votes
0answers
10 views

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} \...
2
votes
0answers
27 views

A linearly uniform but quadratically non-uniform set

I have been working on this problem for a while but have no clue at all. Fix a smooth cutoff function $\varphi: \mathbb R/\mathbb Z\rightarrow [0,1]$ supported on $[−\varepsilon-\delta, \...
0
votes
0answers
25 views

Additive combinatorics, moments, generating functions, Cauchy's formula and asymptotics

Let $A, B$ be finite sets of positive integers, let $$f(z) = \left(\sum_{a \in A} z^a\right)\left(\sum_{b \in B} z^b \right) = \sum_{m \geq 0} r_{A, B}(m) z^m,$$ where $r_{A, B}(m)$ is the number of ...
3
votes
1answer
38 views

A question concerning an exercise from Tao Vu

This is the exercise 4.1.5 from Tao Vu Additive Combinatorics. $Z$ is a finite additive group with a fixed symmetric non-degenerate bilinear form $\cdot$ Define $e: \mathbb{R}/\mathbb{Z} \to \mathbb{...
0
votes
0answers
34 views

Additive combinatorics: Switching $\mathbb{Z}/N\mathbb{Z}$ with $\mathbb{Z}$

For a positive integer $N$, denote $\mathbb{Z}_N = \mathbb{Z}/N\mathbb{Z}$. Now let $F$ be a field and let $f_1, \ldots, f_s : \mathbb{Z}_N \to F$. Can we find functions $\tilde{f_1}, \ldots, \tilde{...
0
votes
0answers
22 views

Number of ways, modulo a prime $p$, to write $n$ as a sum $n = x_1^k + x_2^k + \cdots + x_s^k$

Removing the restriction on $p$, this is known as Waring's problem. The circle method has been used successfully to tackle this. Using analysis, nice estimates can be given. I wonder what analytic ...
3
votes
0answers
31 views

Extremal set theory problem concerning translations of a set of integers

Let $A$ be a subset of $B = \{1, 2,\ldots,n\}$. Suppose that $F$ is a family of subsets of $B$, each of which is a translation of $A$ and no two of which intersect more than once. What is the maximum ...
3
votes
1answer
111 views

Sumset of a subset of a group

I am interested in the following which I believe is known: Let $S$ be a subset of a finite group $G$ containing more than half of $G$'s elements. Then $S+S = G$. I have been looking but can not ...
2
votes
1answer
147 views

Prove: A 9 element subset of ${1,2,…,99}$ must have two distinct subsets with the same sum.

APMO 2014 Problem 4: Prove: A 9 element subset of ${1,2,...,99}$ must have two distinct subsets with the same sum. I am having a lot of trouble with this problem. The official solution: https://...
2
votes
1answer
42 views

An additive combinatorics problem

Given $n,m\in\Bbb N$. We want to find two disjoint sets $A$ and $B$ such that $$|A|=|B|=n$$ $$\min\{a\in A,b\in B\}>m$$ $$|A+B|=2n$$ where $A+B=\{a+b:a\in A, b\in B\}$. What is the minimum ...
1
vote
0answers
38 views

Additive combinatorics in Hamming weights of addition of numbers modulo $2^n$ with prescribed Hamming weight

I wonder if anyone could point me to a reference about the following type of combinatorics problem: Fix $n $. For an integer $k \in [n] = \{1, \ldots, n\}$, let $A(k)$ be the set of integers in $[0, ...
1
vote
1answer
50 views

Convolution of indicator functions with values in a finite field

This is something I haven't seen online yet, indicator functions with values in a finite field. Probably for a good reason, but I would like to know why, and if there are still things that can be said....
0
votes
0answers
67 views

Contradiction in Frobenius coin problem

The Frobenius coin problem guarantees that if $(a,b)=1$, then $$ax+by$$ does not represent exactly $(a-1)(b-1)/2$ numbers all below $ab-a-b$ if $x,y\geq0$ holds. I am confused by following argument. ...
0
votes
1answer
126 views

Erdős and Szemerédi sums and producs

Erdős and Szemerédi proved that: $$\max(|A+A|,|A \cdot A|) \gg |A|^{1+\epsilon}$$ It might be that the work of Erdős and Szemerédi does not help me here at all, I did not have to deal with math much ...
1
vote
2answers
104 views

Is $1072$ the sum of $51$ cubes?

Inspired by this superb question Number writable as sum of cubes in $9$ "consecutive" ways I wonder, whether $1072$, being the sum of $2,3,4,...,50$ cubes, is also a sum of $51$ cubes. Of ...
1
vote
2answers
59 views

Number writable as sum of cubes in $9$ “consecutive” ways

Let's say that a given $n\in\mathbb{N}$ is writable as sum of cubes in $k$ consecutive ways if it can be written as sum of $j,j+1,\ldots, j+(k-1)$ nonzero cubes, for some $j\geqslant 1$. For ...
1
vote
0answers
31 views

Invariance of a set under permutations

Given a positive integer $n$, let $f$ be a function $$ \{1,\ldots,n\}^2 \to \{1,\ldots,n\}. $$ Then, it is possible that there exists a permutation $\{\sigma_1,\ldots,\sigma_n\}$ of $\{1,\ldots,n\}$ ...
7
votes
1answer
165 views

For what subset of the reals is the difference of any two elements always unique such that every real can be so represented?

I am looking for a subset $A$ of the real numbers such that given a real number $z$ not equal to $0$ there exists a unique $x,y \in A$ such that $x-y=z$. Or for any real number $z$ not equal to $0$, $...
3
votes
0answers
129 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
187 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
153 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 ...
5
votes
1answer
79 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
30 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$ ...
1
vote
1answer
81 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
75 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
52 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
53 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
61 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
33 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 a_{b_{i}}=\...
3
votes
1answer
96 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
43 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
83 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 (p_3)=\mathfrak{S}\frac{n^2}...
2
votes
1answer
48 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
48 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
75 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
2
votes
2answers
117 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 $r_{k,B}(...
1
vote
0answers
70 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
75 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.