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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
42 views

Can we bound the lower and upper asymptotic density of these subsets of $\mathbb N$?

Suppose we partition the powers of $2$ into two sets in the following manner: $$A = \{1\}, \quad B = \{2,4,8,16,\dots\}$$ Now suppose that, for each odd positive integer $t$, we select either $tA$ or $...
tuna's user avatar
  • 547
1 vote
1 answer
90 views

Problems regarding the denseness of $a\mathbb{Z}+\mathbb{Z}$

I came across a problem related to the denseness of $a\mathbb{Z}+\mathbb{Z}$. Explicitly, the problem asks: Let $a$ be irrational. (a) For any $y \in [0,1]$, prove that there are infinitely many $n \...
Lab's user avatar
  • 563
1 vote
1 answer
59 views

Sum-free sequence but multiset

The question is: Show that if $S$ is a set of natural numbers such that no number in S can be expressed as a sum of other (not necessarily distinct) numbers in S, then $\sum_{ s \in S} \frac{1}{s} \...
Joseph Bendy's user avatar
1 vote
0 answers
51 views

When is $\overline{d}(A \cap A/2)>0$?

Let $A \subset \mathbb{N}$ have $\overline{d}(A):= \limsup_{N\to \infty} \frac{|A\cap \{1,\ldots,N\}|}{N} >2/3$. Is it true that $\overline{d}(A \cap A/2)>0$? What I can show is that this holds ...
User's user avatar
  • 434
0 votes
0 answers
52 views

How many different ways can positions be filled out with overlapping candidates?

Suppose I am trying to fill up positions $A,B,C$ with candidates $\{1,2,3,4,5,6\}$ and each candidate can only be in one position at most. Each position has a set of candidates who have applied, for ...
wjmccann's user avatar
  • 3,057
0 votes
0 answers
34 views

doubt about volume packing lemma for intersection of convex bodies and lattices

Lemma 3.24 of Additive Combinatorics by Tao and Vu states the following: Let $\Gamma \subset \mathbb{R}^d$ be a lattice of full rank, let $V$ be a bounded open subset of $\mathbb{R}^d$, and let $P$ ...
aba's user avatar
  • 45
0 votes
0 answers
26 views

On indistinguishability and addition/convolution

Happy new year. I'd like some help with this problem: Let $p,d \in {[0,1]}^{n}$ so that ${||p||}_{L1} = {||d||}_{L1}=1$ i.e p,d are probability distributions over Z/nZ. '$\star$' is the operator of ...
alon's user avatar
  • 1
0 votes
0 answers
44 views

``Anti-Freiman'' homomorphisms - Reference request

For two additive sets $A,B$ with respective ambient groups $G,F$, an order $2$ Freiman homomorphism from $A$ to $B$ is a map $\phi:A\to B$ with the property that, $$a_1+a_2=a'_1+a'_2 \Longrightarrow \...
Thomas Lesgourgues's user avatar
0 votes
0 answers
59 views

What is the maximum range of a convex finite additive 2-basis of cardinality k?

Conjecture: Given any $d \in \mathbb{Z}_{\geq 2}$ and $k=2d-2$, we have \begin{align*} \max \{ n : (\exists &f \in \{ \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0} \})\\ &[((\forall i \in \...
Michael Chu's user avatar
0 votes
1 answer
35 views

Fourier transform of a random subset of $Z_n$

I have been watching a lecture about introduction to additive combinatorics. Starting from minute 16:00 or so, the speaker makes a claim which I do not understand. I included all the details here. ...
Johana T's user avatar
0 votes
0 answers
35 views

Schnirelmann density and bases of finite order

Let $\mathcal{A}$ be an additive set. We know that if the Schnirelmann density $\sigma_{\mathcal{A}}$ is positive then it is a basis of finite order. But it it not a necessary condition. My question ...
user avatar
2 votes
0 answers
50 views

Sums of a square and a cube

I’ve recently found this problem, and I have no idea how to solve it. I would be grateful for any ideas. Let $f(n)$ denote the number of non-negative integers that can be represented as the sum of a ...
math-hedgehog's user avatar
1 vote
1 answer
97 views

How many subsets $S$ of integer interval $[0,n]$ such that $n, n-1 \not \in S+S$?

Conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(...
Michael Chu's user avatar
1 vote
1 answer
82 views

Bohr sets and lattice in $\mathbb{R}^k$

I was watching Gowers' lectures on additive combinatorics, and in them, he proved some structural theorems about Bohr sets. You can find the lectures here. Before I ask my question, let me provide ...
RFZ's user avatar
  • 16.7k
8 votes
1 answer
242 views

Growth of powers of symmetric subsets in a finite group

Let $G$ be a finite group, and let $A$ be a symmetric subset of $G$ containing the identity (i.e., $A^{-1}=A$ and $1\in A$). Then the powers of $A$ will form a chain $A\subsetneq A^2\subsetneq A^3\...
Thomas Browning's user avatar
3 votes
1 answer
91 views

Imre Ruzsa Generalisation of Kneser's theorem proof

According to this post here, there is a theorem by Ruzsa (2009) that for any group $G$ and $A,B\subset G$, $|A+B| \ge \min\{ p(G), |A|+|B|-1\}$ where $p(G)$ is the size of the smallest subgroup of $G$....
settheory's user avatar
1 vote
0 answers
41 views

Arithmetic Triangle Removal Lemma

Here is the problem: Here is my approach: I attempted the following: I constructed a graph on $[N]=\{1,\cdots,N\}$, adding an edge between $a,b$ in $[N]$ iff $|a-b| \in A.$ Then each $(x,y,x+y) \in A^...
Kai Wang's user avatar
  • 713
1 vote
0 answers
87 views

Cauchy Davenport in mod $n$

The Cauchy-Davenport inequality on an additive group $G$ is: For all $A,B\subseteq G$, $$|A+B|\ge \min\{|G|,|A|+|B|-1\}$$ The Cauchy-Davenport inequality fails in mod $n$ ($n$ composite) because we ...
settheory's user avatar
1 vote
1 answer
80 views

If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$?

If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$? Where $AA=\{a_{1} \cdot a_2:a_1,a_2 \in A\}$, and $p$ is prime. Writing out ...
yellowcat's user avatar
  • 196
0 votes
0 answers
34 views

Bound on the number of distinct subset-sums of a given set

I am interested in characterizing sets for which the number of different subset-sums is bounded by a polynomial in the size of the set. Formally: Let $A = \langle a_1, a_2, \dots, a_m \rangle$ be a ...
ashtavakra's user avatar
1 vote
1 answer
30 views

Erdos-Szemeredi conjecture orginal paper

I am looking for a link to the original paper published by Erdos and Szemeredi where they prove that $$\max(|A+A|,|A \cdot A|) \gg |A|^{1+\epsilon}$$ for $A$ a finite subset of $\mathbb{R}$ and $+$ ...
settheory's user avatar
1 vote
0 answers
33 views

Showing that a set of equations have positive density of solutions

Consider the following set of equations $$a_{0}b_{0} \neq 0, \hspace{3mm} a_{0}b_{1}+a_{1}b_{0} = 0, \hspace{3mm} \text{ and } a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0} = 0 $$ in the variables $\vec{a} = (a_{0}...
Gafar Maulik's user avatar
1 vote
0 answers
60 views

About Hahn-Banach Theorem assumption

Currently I am trying to understand the proof of the following lemma which appear in the book Additive combinatorics of Tao and Vu (Chapter 5, page 212, in the 2006 edition). Lemma 5.14 Let $A, B$ be ...
Brien Navarro's user avatar
4 votes
1 answer
252 views

Is there an exponential lower bound for the chromatic number?

Let $n$ be a positive integer. Define the Hamming distance $d_H(x,y)$ of $x,y\in\{0,1\}^n$ by $$d_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$ For integers $n>1$ and $k$ with $1\leq k&...
Simd's user avatar
  • 387
1 vote
0 answers
21 views

When is the Frobenius number of a numerical semigroup larger than the maximum of the minimal generating set

Let $S$ be a numerical semigroup (https://en.m.wikipedia.org/wiki/Numerical_semigroup). Let $A$ be the minimal generating set for $S$. As standard, let $e(S)$, $m(S)$ and $F(S)$ stand respectively ...
Muni's user avatar
  • 65
1 vote
0 answers
71 views

Additive Combinatorics: Dyson's transform

My uni is conducting a short lecture series on Additive Combinatorics (it's mostly concerned about sumsets and Number Theory) whence I came across Dyson's transform and Cauchy-Devenport theorem. $\...
Nothing special's user avatar
1 vote
0 answers
63 views

Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $1-|A\cap (B+x)|/|Z|\leq(1-|A|/|Z|)(1-|B|/|Z|)$

Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $$1-\frac{|A\cap (B+x)|}{|Z|}\leq \left(1-\frac{|A|}{|Z|}\right)\left(1-\frac{|B|}{|Z|}\right)$$ ...
Ishigami's user avatar
  • 1,535
3 votes
1 answer
206 views

Expectation of r.v. in the proof of crossing number inequality

I was reading the proof of crossing number inequality and there was one step in the proof which I cannot prove rigorously. Firstly, let me remind the definition of the crossing number and then I ...
RFZ's user avatar
  • 16.7k
3 votes
3 answers
158 views

If $\vert A + A \vert = 2\vert A \vert - 1,$ then is $A$ an arithmetic progression?

For $n\in\mathbb{N},$ define $[n]:= \{ 0, 1, 2,\ldots, n-1\}.$ Suppose $A$ is a finite subset of $\mathbb{Z}$ such that $\vert A + A \vert = 2\vert A \vert - 1,$ where $\ A+B$ means the Minkowski ...
Adam Rubinson's user avatar
0 votes
1 answer
53 views

On writing every integer from $(a-1)(b-1)$ onwards as a sum of two non-zero integers from the semigroup generated by $a,b$

Let $\mathbb N$ be the semigroup (even a monoid) of non-negative integers. Let $a<b$ be relatively prime integers such that $2< a$. Let $S :=\mathbb N a +\mathbb N b$ be the semigroup generated ...
Muni's user avatar
  • 65
2 votes
2 answers
103 views

Is the stronger form of Dirichlet's theorem on arithmetic progressions strong enough to prove Goldbach's (asymptotic) conjecture?

The stronger form of Dirichlet's conjecture states that, for example, $$\lim_{N\to\infty} \frac{\text{ the number of primes } \leq N \text{ of the form } 1+8k }{\text{ the number of primes } \leq N \...
Adam Rubinson's user avatar
0 votes
0 answers
61 views

How many ways are there to place a set of chess pieces on the first row of chessboard?

How many ways are there to place a set of chess pieces on the first row of chessboard when the set contains 1 king, 1 queen, 2 identical rooks, 2 identical bishops and 2 identical knights. With the ...
sagi eisenberg's user avatar
0 votes
0 answers
37 views

At most two elements give 1 to n

Fix a positive integer $m$. Let $n$ ( $= n(m)$) be the largest positive integer for which there exists some subset $\{a_1,\ldots,a_m\} \subseteq \{1,2,\ldots,n\}$ of $m$ positive integers between $1$ ...
Andyqian7's user avatar
3 votes
2 answers
203 views

Pairs promoting diversity

Let $p$ be a prime number at least three and let ${k}$ be a positive integer smaller than $p$. Given ${a}_1, \ldots, {a}_{{k}} \in \mathbb{F}_p$ and distinct elements ${b}_1, \ldots, {b}_{{k}} \in \...
Snowball's user avatar
  • 1,064
3 votes
1 answer
129 views

Representation of integers by $A = B^{\frac{5}{4}} + C^{\frac{5}{4}}$

Let $n>-1$ be an integer and $f(n)$ be the integer part of $n^{\frac{5}{4}}$. And to avoid confusion define $f(0)=0,f(1)=1$ and all $f(n)$ as the integer part of the positive real values for $n^{\...
mick's user avatar
  • 15.9k
0 votes
1 answer
16 views

Estimation cardinality of certain classes of sets in $\mathbb{N}^{n}$

Consider the following sets in $\mathbb{N}^{n}$ $$ F_{n} := \{ (x_1,..,x_n) \in \mathbb{N}^{n}: \sum_{i=1}^{i=n}x_i \ge A_n, \quad \max_{1\le i \le n}x_i \le B_n\} $$ where for simplicity one can ...
YOTAL's user avatar
  • 91
9 votes
1 answer
220 views

Is there a way to characterize sets $S \subseteq \mathbb{N}$ where $S + S = \mathbb{N}$?

I came across the following problem after a colleague and I were discussing nonregular languages whose concatenation is regular. If $A, B \in P(\mathbb{N})$, we can define their Minkowski sum as $$A + ...
templatetypedef's user avatar
2 votes
0 answers
54 views

Does a Freiman $2$-isomorphism have to send $0$ to $0$?

Let $A$ and $B$ be subsets of abelian groups. A Freiman $2$-homomorphism is a function from $\phi:A\to B$ such that if $a_1 + a_2 = b_1 + b_2$, then $\phi(a_1)+\phi(a_2) = \phi(b_1) + \phi(b_2)$. If $\...
marcelgoh's user avatar
  • 1,794
1 vote
0 answers
45 views

Clarification of the key theorem for proving Roth's theorem

I have recently been reading Terence Tao's paper on the Szemeredi's original proof of Szemeredi's theorem (https://terrytao.files.wordpress.com/2017/09/szemeredi-proof1.pdf) and I have come upon this ...
sgvozdic's user avatar
0 votes
0 answers
21 views

The longest possible sequence of the first n numbers so consecutive elements can't be split in equal sums

A secuence $S$ has an additive reflection if consecutive elements $S_n, S_{n+1},...., S_{n+m}$ can be split so that $$S_n+ S_{n+1}+....+S_{n+i-1} =S_{n+i}, S_{n+i+1}+....+ S_{m}$$ If a secuence doesn'...
AndroidBeginner's user avatar
2 votes
1 answer
58 views

Can we arrange the first n natural numbers consecutive numbers can't be split in equal sums

For some set S, define a reflection as a subset of consecutive elements that can be split in a way so that the sums of both sides are equal. The set ${1,2,...,7,8} $ has reflections $1+2 =3$ and $4+5+...
AndroidBeginner's user avatar
0 votes
0 answers
30 views

Some conjectures on additive and subtractive bases

I came up with a few problems about additive bases that might be interesting, would love to see if someone can prove or disprove them. Let S be a set of whole numbers so that every natural can be ...
AndroidBeginner's user avatar
1 vote
0 answers
33 views

Proving Lagrange four square theorem from the "sum of three triangle" theorem

It was proven by Gauss that every integer is the sum of at most three triangle numbers, and by Lagrange that every integer is the sum of at most four squares. The triangles are the set $\big\{1,3,6,...
AndroidBeginner's user avatar
0 votes
1 answer
68 views

Equivalent formulations of finitistic Szemerédi's theorem

I've been reading about Szemerédi's theorem recently and I'm stuck at its equivalent formulations, namely the ones called finitistic. There are in fact two versions of it that I have seen and I'm not ...
sgvozdic's user avatar
25 votes
2 answers
520 views

Metric spaces where each point sees each distance exactly once

Let $M$ be a metric space, and $S=\{d(x,y):x,y\in M\}$ be the set of all distances between points in $M$. Let's call $M$ a unique distance space if for all $x\in M$ and all $r\in S$, there exists a ...
Jonathan Love's user avatar
4 votes
0 answers
52 views

What is the largest value of $e_{k}(x_1,\cdots,x_n)$ not obtainable over $(\mathbb{N}^+)^n$?

Let $k,n\in\mathbb{N}^+$, $\vec{x}=\langle x_1,\cdots,x_n\rangle$ be an $n$-tuple, and let $e_k(\vec{x})$ be the elementary symmetric polynomial of degree $k$ over $n$ variables (clearly with $k\le n$)...
Integrand's user avatar
  • 8,457
2 votes
0 answers
119 views

How sparse/"thin" (asymptotically) can additive bases of order $2$ be?

A subset $B$ is called an (asymptotic) additive basis of order $2$ if every sufficiently large natural number $n$ can be written as the sum of at most $2$ elements of $B.$ How small/sparse can such ...
Adam Rubinson's user avatar
1 vote
1 answer
94 views

Representation of number as a sums and differences of natural numbers

Lets consider all the combinations of: $$1+2+3+4=10,\ \ 1+2+3-4=2,\ \ 1+2-3+4=4,\ \ 1+2-3-4=-4, $$ $$1-2+3+4=6,\ \ 1-2+3-4=-2,\ \ 1-2-3+4=0,\ \ 1-2-3-4=-8,$$ $$-1+2+3+4=8,\ \ -1+2+3-4=0,\ \ -1+2-3+4=2,...
Gevorg Hmayakyan's user avatar
2 votes
1 answer
274 views

Behrend's construction on large 3-AP-free set

Theorem (Behrend's construction) There exists a constant $C>0$ such that for every positive integer $N$, there exists a $3$-AP-free $A\subseteq[N]$ with $|A|\geq Ne^{-C\sqrt{\log N}}$. Proof. Let $...
RFZ's user avatar
  • 16.7k
0 votes
0 answers
95 views

Magic Squares of Squares

Let $A =$ $\{a_1, a_2, ..., a_n\}$ and $B =$ $\{b_1, b_2, ..., b_m\}$ be two sets of integers. If $a + b$ is a square for all $ a ∈ A $ and $ b ∈ B $. $A$ and $ B $ are then said to be Square Additive ...
user967210's user avatar

1
2 3 4 5
8