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.

0
votes
2answers
25 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
67 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
36 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
13 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
67 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
40 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
56 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
135 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
165 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
256 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
32 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
125 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
47 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
35 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
31 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
41 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
124 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 ...
31
votes
0answers
412 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
55 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
175 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
38 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
177 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
60 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
44 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
79 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
302 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
13 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
56 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
117 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 ...
0
votes
0answers
46 views

Modular properties of the integral sequence s(n)

Prove that there exists a sequence $$ \alpha_{0}=-1,\ \alpha_{1}=2,\ \alpha_{2}=0,\ \alpha_{3}=\frac{1}{3},\ \alpha_{4}=\frac{5}{18},\ \alpha_{5}=\frac{149}{540},\ \alpha_{6}=\frac{553}{2025}, $$ $$ \...
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
98 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$ ...
3
votes
1answer
120 views

Will terms in this sequence always have digital root 1?

A recreational math problem, dubbed "Insert and Add", asks: What is the least integer m that requires no less than n insertions of plus signs so that, after performing the addition(s), we arrive at a ...
18
votes
2answers
454 views

Sumset that covers $\mathbb{Z}/p\mathbb{Z}$.

Let $p$ be a prime. Let $S$ be a set of residues modulo $p$. Define $$S^2 = \{a \cdot b \mid a \in S, b \in S\}.$$ Question: How small can we make $|S|$ such that $\{0, 1, \cdots, p-2, p-1\} \in ...
0
votes
0answers
73 views

All possible combinations from a list to sum to X

I have a maths question I can't wrap my head around. Assume you have a container of volume X. You need to fill it with 4 types of boxes A, B, C, D of different sizes. A is the smallest box, B is ...
2
votes
2answers
54 views

Certain property of finite field $F_p$

Let $F_p$ be a finite field of order $p$ where $p$ is a prime number. Let $\{ \alpha_1, \ldots, \alpha_{p-1} \}$ be a multi-set with $\alpha_i \in F_p$ and each $\alpha_i$ non-zero. I want to show ...
2
votes
1answer
137 views

Generalization of an IMO 1985 Problem in Elementary Number Theory and Combinatorics.

The original problem of IMO $1985$ was as follows- Given any $1985$ positive integers all of which contains no prime factor $>23,$ prove that you can find four of them whose multiple is ...
5
votes
2answers
133 views

Is there any formula for this sum of power of positive integers? [duplicate]

I wonder if there is any formula for this sum. $$k^\gamma+(k-1)^\gamma+\cdots+1^\gamma,$$ where $k$ is positive integer and $\gamma\in(0,1)$. And how about $\gamma<0$? Or is there any known ...