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
33 views

Need to define additive union and additive intersection in sets

If I have two sets: $ A=\{1, 2, 3, 4, 5\}$ and $B=\{4, 5, 6 , 7, 8, 9\}$ I know that the union of these sets will include all nine elements, and that the intersection will results in a set $\{4, ...
3
votes
1answer
97 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
133 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
35 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
35 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
44 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
59 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
119 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
103 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
55 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
29 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
161 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
181 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
126 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
76 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
29 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
59 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
74 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
49 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
50 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
50 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
32 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
94 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
41 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
79 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
47 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
45 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
70 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
111 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
68 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
73 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
54 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
63 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
74 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
124 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 ...
0
votes
1answer
38 views

Cardinality of finite sets: if $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$, then $|C|^2\ge |A||B|$

Let A be a finite set of real numbers. Suppose $B=\{a-b \mid a,b \in A\}$ and $C=\{a+b \mid a,b \in A\}$. Prove that $|C|^2\ge |A||B|$. I tried to solve this in this way: We claim that the function ...
6
votes
2answers
407 views

Sum of two squares modulo p

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How ...
7
votes
1answer
190 views

Are there any “nontrivial” sets with small difference sets?

I'm trying to find finite sets $S$ of natural numbers with "small" difference sets. One option is just taking an arithmetic progression $S = \{0, , \ldots, n-1\}$. Then $|S - S| = 2 |S| - 1$, which ...
1
vote
0answers
28 views

“Spanning” the difference set of $S$

Suppose that $S$ is a finite set of natural numbers, and $\{(x_i, y_i)\}$ is a set of tuples of numbers in $S$ with $$ \{x_i - y_i\} = S - S := \{a - b \mid a, b \in S\} $$ that is, $\{(x_i, y_i)\}$ ...
1
vote
0answers
51 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...
2
votes
1answer
77 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
32 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$, ...
1
vote
2answers
102 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
110 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 ...
5
votes
1answer
69 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
75 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
22 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
67 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.