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

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
0answers
23 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
33 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
23 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
50 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
9 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 ...
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) ...
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
26 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
24 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 ...
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, ...
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
30 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
103 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
142 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: ...
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
37 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
48 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 ...
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
125 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
30 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
164 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
136 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
77 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
76 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
60 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 ...
3
votes
1answer
95 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 ...
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
46 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
74 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
116 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
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.
0
votes
2answers
48 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
55 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
65 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
75 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
128 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 ...