Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

2
votes
2answers
60 views

What is the probability that $\exists N \in \mathbb{N}$ such that $\forall n > N$, $2n \in C + C$?

Suppose $C$ is a random subset of $\mathbb{N}\setminus\{1, 2\}$, such that $\forall n \in \mathbb{N}\setminus\{1, 2\}$, $P(n \in C) = \frac{1}{\ln(n)}$ and the events of different numbers belonging to ...
0
votes
1answer
28 views

If $P \in V$ is a polynomial with maximal support $\Sigma$, then $|\Sigma| \geq dim(V)$

I was wondering if anyone could help me understand a statement in the proof of Theorem 4 of this paper: https://www.jstor.org/stable/pdf/24906443.pdf. I'm aiming to prove the theorem for $q=3$ and $\...
2
votes
2answers
89 views

Number of n-tuples in $\{0, 1, 2\}$ with sum less than or equal to $d$.

I would like to know if there is an expression for the number of n-tuples of $\mathbb{Z}$, where each component is an integer between $0$ and $2$, and the sum of the components is less than or equal ...
2
votes
1answer
46 views

Each one in $\mathbb Z_p$ is some sum

Let $p$ be a prime and let $a_1, \ldots, a_{p-1}$ be natural numbers such that no $a_i$ is divisible by $p$. For a subset $I$ of $\{1, \ldots, p-1\}$, write $a_I$ to denote $\sum_{i\in I}a_i$, where $...
1
vote
0answers
32 views

On the cardinality of the set $ A(m) := \{ (a, b) \in \mathbb{N}^2 : \; N \leq a \leq 2 N, \; a^2 - b^2 = m \}, $

Question: Consider the set $$ A(m) := \{ (a, b) \in \mathbb{N}^2 : \; N \leq a \leq 2 N, \; a^2 - b^2 = m \}, $$ where $ \mathbb{Z} \ni m < 0$ and $N \in \mathbb{N} \setminus \{ 0 \}$. Then ...
2
votes
2answers
80 views

Reaching higher even numbers in Goldbach's conjecture, using lower even numbers.

Let $n \in \Bbb{N}, n \gt 1$. Let $\Bbb{P} = $ the prime numbers in $\Bbb{N}$. Define \begin{align*} A_n &= \{ (p,q) \in \Bbb{P}^2 : p + q = 2n\}, \\ B_n &= \{ (p, q) : p - q = 2n \}. \end{...
2
votes
2answers
74 views

Show that there exists $i\in \lbrace 1, 2, 3 \rbrace $ s.t. there exists $a, b\in A_i $ s.t. $a+b\in B $.

Let $A=\lbrace 1, 2, 3,..., 2019\rbrace= A_1\cup A_2\cup A_3$, where $A_1\cap A_2=A_2\cap A_3= A_1\cap A_3=\emptyset $ and $B=\lbrace 672, 1008, 1344, 1680, 2016\rbrace $. Show that there exists $i\...
0
votes
2answers
42 views

Combinatorial problem discrete math

Find the no of ways of placing 6 identical balls into 3 distinct boxes in such a way that first box contains 0,1 or 2 objects,2bd box contains 1,2,3 objects and 3rd one contains 3 or 5 objects. Ans- ...
6
votes
1answer
70 views

Subsets of $\mathbb Z/n\mathbb Z$ disjoint with some of its shifts

Are there any descriptions of all subsets $X$ of $\mathbb Z/n\mathbb Z$ with the following property: there exists $a\ne 0$ in $\mathbb Z/n\mathbb Z$ such that $X$ is disjoint with $X + a = \{x + a \...
2
votes
1answer
35 views

Subsets of $\mathbb Z/n\mathbb Z$ that remain disjoint with themselves under shifts

Are there any descriptions of all subsets $X$ of $\mathbb Z/n\mathbb Z$ such that for any $a\ne 0$ in $\mathbb Z/n\mathbb Z$, $X$ is disjoint with $X + a = \{x + a \pmod n\mid x \in X\}$?
2
votes
1answer
39 views

Prove that if $|A+A| \leq K|A|$ then $2A - 2A$ is a $K^{16}$-approximate group.

Let $A$ be a finite subset of an abelian group, $G$ (call the operation addition). We say $A$ is a $K$-approximate group if: 1) $e_G \in A$ 2) $A^{-1} = \{ a^{-1} \mid a \in A \} = A$ 3) $\exists X ...
1
vote
0answers
15 views

Lower-bounding the density of 3A in terms of that of 2A

Let $A\subset\mathbb{N}$ and $2A=A+A=\{a+b \lvert a,b\in A\}$ and $3A=2A+A$. I wonder how small the density of $3A$ can be, knowing that the density of $2A$ is, say, $\beta >0$, but not knowing ...
2
votes
2answers
82 views

Making 12 by adding 1, 3, and 5

It is given 3 numbers : 1, 3, and 5, you were told to write numbers by adding those 3 numbers, for example: There are 8 ways of writing the number 6 6 = 1 + 5 6 = 5 + 1 6 = 3 + 3 6 = 1 + 1 + 1 + 3 ...
3
votes
1answer
44 views

Lemma 2.1 of “A SUM-PRODUCT ESTIMATE IN FINITE FIELDS, AND APPLICATION”, by Bourgain, Katz and Tao

I am trying to understand Lemma 2.1 of this paper: https://arxiv.org/pdf/math/0301343.pdf. Can anyone explain to me explicitly the reason why we can assume WLOG that $|A||B|\leqslant |F|/2$? Many ...
2
votes
1answer
68 views

monochromatic solution to $xy=z$

Is it true that for any $k \geq 2$, there is an integer $n=n(k)$ such that for any $k$-coloring of $\{1,...,n\},$ the equation $xy=z$ has a monochromatic solution?
4
votes
2answers
142 views

How to show that $\gcd(a_1,a_2,\cdots,a_k) = 1$ implies that there exist a non-negative solution to $\sum_{i=1}^{n}a_ix_i = n$ for large $n.$

I was reading about the Coin-problem and I am unable to fully understand the following argument: On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a ...
3
votes
1answer
172 views

Understanding compact extensions and almost-periodic functions

This question comes from my attempt to understand theorem $7.21$ in E-W. This concerns the dichotomy between relatively weak-mixing extensions and compact extensions. I cannot understand the proof as ...
7
votes
0answers
266 views

Clarification on a proof of Roth's theorem

Roth's theorem is stated in the book by Einsiedler and Ward, theorem 7.14 page 191 as: Let $(X,\mathscr{B},\mu,T)$ be a measure-preserving probability system. Then, for any functions $f_1,f_2 \in L^{\...
5
votes
0answers
113 views

Odd of the form $a^2+b^2+c^2+ab+ac+bc$.

The computation below shows that (for $a,b,c \in \mathbb{N}$) the form $$a^2+b^2+c^2+ab+ac+bc$$ covers every odd integer less than $10^5$ except those in $$I= \{ 5, 15, 23, 29, 41, 53, 59, 65, ...
1
vote
0answers
33 views

Existence of coprime numbers in simultaneous generalized arithmetic progressions

Let $a_i,b_i,c_i (i=1,2)$ be integers such that the greatest common divisor $\gcd(a_i,b_i,c_i)=1$ for each $i$. Moreover suppose the triple $(a_1,b_1,c_1)$ is not a scale of $(a_2,b_2,c_2)$ i.e. there ...
8
votes
2answers
128 views

Compressing the primes using simple addition?

Consider the sets of integers $$ A = \{1, 3, 7, 13, 27\} \\ B = \{4, 10, 16, 40, 100\} $$ Elementwise addition of sets $A, B$ looks like $A + B := \{ a + b: a \in A, b \in B\}$. Now elementwise-add ...
1
vote
0answers
33 views

Growth in Groups / Helfgott paper (2013)

I'm currently working on this paper by Helfgott for a small project: https://arxiv.org/abs/1303.0239. After Lemma 3.1 (Ruzsa inequality) he says (and shows partially) that for any finite subset $A$ of ...
1
vote
1answer
48 views

Can the set of odd primes be decomposed into $\Bbb{P} = A + B, $ for some $A,B \subset \Bbb{Z}$?

Can there ever exist infinite sets of integers $A, B$ such that $A + B = \{ a + b: a \in A, b \in B\} = \Bbb{P}$? Where $\Bbb{P}$ is the set of odd primes? You can include $0$ and / or $\pm$ odd ...
0
votes
1answer
36 views

The Density of a Linear Combination

I have been working on the following problem for a while, but seem to be at an impasse. My limited knowledge of additive combinatorics does not help. Suppose we have two positive real numbers $\alpha$ ...
0
votes
0answers
33 views

What will be the upper bound of $k$?

Consider the sets $A_i \subset \{1,2, \cdots, n \}, 1 \leq i \leq k$ such that $A_i \cap A_j \neq \emptyset$ for $i \neq j$. Give an upper bound of $k$. I have found sets $A_i = \{j : 1 \leq j \...
3
votes
0answers
43 views

Product set in a finite field

For a finite nonempty subset $A$ of a ring $X=(X,+,\cdot)$, let us denote the set $\{a \cdot b \colon a, b \in X\}$. If $X=\mathbb{Z}$, it is not difficult to show that $$|AA| \leq \frac{|A|^{2}+|...
2
votes
0answers
126 views

What interesting properties does $A^3$ have?

Suppose $G$ is a finitely generated group. Suppose $A^1$ is a finite subset of $G$, such that $\langle A^1 \rangle = G$. Let’s define $A^n \subset G$ for $n \in \mathbb{N}$ using the recurrent ...
32
votes
0answers
425 views

What is $\tau(A_n)$?

Suppose G is a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$. What is $\tau(A_n)$? Similar problems for ...
1
vote
0answers
56 views

Is there a way to evaluate $\min\{k |\forall A \subset G \text{ if }|A| > k\text{, then } AAA = \langle A \rangle \}$?

Suppose, $G$ is a finite group, $H \triangleleft G$, $G/H = K$. Suppose, $a=\min\{k |\forall A \subset H \text{ if }|A| > k\text{, then } AAA = \langle A \rangle \}$ Suppose, $b=\min\{k |\forall B \...
1
vote
1answer
177 views

Additive basis of order $2$ (II)

Can we find, using elementary ways, an additive basis of order $2$, $(u_n)_{n\geqslant1}$, such that $\lim\limits_{n\rightarrow+\infty}(u_{n+1}-u_n)=+\infty$ ? If $\alpha\in\left]1,\frac32\right[$, ...
2
votes
0answers
39 views

Where can I find this article by I. Ruzsa?

Title says it all. Have tried googling and my college library, but no success so far. I. Ruzsa, On the cardinality of $A + A$ and $A − A$. In Combinatorics (Keszthely, 1976), Coll. Math. Soc. Bolyai ...
2
votes
1answer
178 views

Additive basis of order $2$ (I)

Can we find $\alpha>1$ such that $u=(\lfloor n^\alpha\rfloor)_{n\geqslant0}$ is an additive basis of order $2$ (i.e. $\forall x\in\mathbb{N}, \exists(n,m)\in\mathbb{N}^2, x=u_n+u_m$) ? Update : I ...
0
votes
0answers
62 views

Uniformity and linear equations in finite fields

I am currently trying to digest Ben Green's paper "Finite Field Models in Arithmetic Combinatorics" (https://arxiv.org/pdf/math/0409420.pdf), and I'm having a hard time understanding the proof of ...
1
vote
0answers
45 views

Assumption in Erdos' B+C conjecture

The Erdos' B+C conjecture states that any set $A \subseteq \mathbb{N}$ satisfying $$\underline{d}(A) := \liminf_{N \rightarrow \infty} \frac{|A \cap \{1, \dots, N\}|}{N} > 0$$ contains a set of the ...
6
votes
1answer
82 views

Is it always true, that $\lim_{n \to \infty} \frac{|A_n \cap H|}{|A_n|} = \frac{1}{[G:H]}$?

Suppose, $G$ is a finitely generated group. Suppose $A_1$ is a finite symmetric generating set. (That means $A_1 \subset G$, $|A_1|$ is finite, $\langle A_1 \rangle = G$, $e \in A_1$, $\forall a \in ...
6
votes
1answer
307 views

What do Tao & Vu mean by “additive set”?

On page 4 of Terence Tao & Van H. Vu's Additive Combinatorics there is the following theorem: Let $A$ be an additive set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $|...
1
vote
1answer
16 views

number of sums in $\mathbb{Z}_{p^r}$ which are coprime to $p^r$

We look at the ring of integers modulo a prime power, say $p^r$ and $r>1$. Eulers totient formula says that there are $p^r-p^{r-1}$ elements in this ring $\mathbb{Z}_{p^r}$ that are coprime to $p^r$...
1
vote
1answer
57 views

Does Haar measure have such property?

Suppose, $G$ is a locally compact topological group. $\mu$ is Haar measure on that group. $A$ and $B$ are Borel subsets of $G$, such that $\mu(A)$ and $\mu(B)$ are finite. Does the inequality $\mu(\{...
0
votes
0answers
36 views

Is that specific function additive under disjoint union?

Suppose, $G$ is an arbitrary group. Define $$F_G = \{ B \subset G | \exists \text{ finite } C \subset G \text{ such that } CB = \{cb|c \in C, b \in B\} = G\}$$ and $$I(A,B)=\min\{ |C||A \subset CB\}...
1
vote
0answers
42 views

On Gowers' approach of Green-Tao Theorem ($\mathcal{D}f$s span $L^q(\mathbb{Z}_N)$).

I am trying to understand the Gowers' approach to the Green-Tao Theorem, and so far I am doing well. Although, there is one point that I am not understanding. Here comes: Let $f:\mathbb{Z}_N\...
0
votes
1answer
77 views

A combinatoric solution (closed expression) for $\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$

I am trying to find a combinatoric solution for $\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$. i.e. write it as a closed function (and not as a sum). I know that in generating functions one can for ...
2
votes
0answers
54 views

show that $[n \sqrt{3}]$ is an approximate group

I have been reading about the notion of an approximate group. These are subsets of groups that are still somewhat symmetric: $A \subseteq G$ is a $K$ - approximate group if it's symmetric ...
4
votes
0answers
125 views

Show that $|A+A| < 2.5 |A| $ with $A = \{ [n \sqrt{2}] : 1 \leq n \leq N \}$

Let $A = \{ [n \sqrt{2}] : 1 \leq n \leq N \}$ then can we estimate the size of the sumset $A+A$ ? $$ A+A = \big\{ [m \sqrt{2}] + [n \sqrt{2}] : 1 \leq m \leq N, 1 \leq n \leq N \big\} $$ Here are ...
1
vote
0answers
40 views

Asymptotic formula for the integral sequence s(n)

Prove that there exists a sequence $A_{0}, A_{1}$, . . . of rational polynomials $A_{i}(x)\in \mathrm{Q}[x]$ with $A_{i}$ of degree $i$ such that $$ s(n)=\frac{n^{n-1}}{(1-\log 2)^{n-1/2}e^{n}}(\sum_{...
2
votes
0answers
138 views

Sorting on non-additive ratios

We are trying to aggregate and sort records by ratios (CTR = clicks/impressions). For some obscure reasons the technology we are using does not allow us to do this. We can group and sort on additive ...
2
votes
0answers
40 views

Advantage of Fourier transform on $\mathbb{Z}_N$

I ran into the following phylosophical question when I was working out Roth's Theorem: Let $A$ be a subset of $\{1,2,\dots, N\}$. We can associate $A$ as a subset of cyclic additive group $\mathbb{Z}...
3
votes
2answers
56 views

Show that $A+B$ contains at least $m+n-1$ elements.

Let $A,B \subset \mathbb Z$ such that $|A|=m$ and $|B|=n$. Then show that $|A+B| \geq m+n-1$. How can I proceed? I have tried to proceed by using law of trichotomy but I only managed to find $\mathrm ...
3
votes
2answers
111 views

Exercise 1.1.6 in Additive Combinatorics

I'm having trouble understanding Exercise 1.1.6 in Additive Combinatorics by Tao and Vu. 1.1.6 Consider a set $A$ as above. Show that there exists a subset $\{v_1, \ldots, v_d\}$ of $Z$ with $d = O(...
3
votes
0answers
45 views

Maximal number of subsets of $n$ real numbers that have the same sum, when $2^{n-2}$ of subsets have “unique” sums

I've recently found a problem that I still can't solve: Dependency of the properties of numbers' subsets concerning subsets' sums of $n$ real numbers. A problem linked with it, that may be ...
0
votes
1answer
60 views

Dependency of the properties of numbers' subsets

Let $a$ be the number of different sums of all the subsets of a set $A$ of $n$ real numbers (let's suppose the sum of an empty set is $0$). Let $b$ be the number of ordered pairs of the subsets of $A$ ...