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.
430 questions
8
votes
1
answer
177
views
Coefficients of $\prod\limits_{i=1}^k (1-z^{s_i})$: Additive combinatorics, inequality, or just simple observations?
Let $s_1$, $s_2$, ..., $s_k$ be $k$ nonzero integers (not necessarily positive or distinct). Let $P(z) := \prod\limits_{i=1}^k (1-z^{s_i})$. Prove that there exists $z$ on the unit circle (i.e., $|z| =...
- 1,108
7
votes
2
answers
356
views
Finding a sum that is always divisible by $1+2+\dots+n$.
There are $๐$ consecutive integers $๐,๐+1,\dots,๐+๐โ1$. Prove that you can choose some nonempty subset of these numbers whose sum is divisible by $1+2+\dots+๐ $.
Edit: Okay, so here is what I ...
- 109
1
vote
1
answer
60
views
Use the sampling argument to prove density Szemeredi (supersaturation) problem
This Exercise comes from Graph Theory and Additive Combinatorics (Yufei Zhao). I have tried for several days but end up with no idea.
Exercise 1.3.7. (Density Szemeredi). Let $k\geq 3$. Assuming ...
- 105
15
votes
0
answers
407
views
+100
Determining whether $A\subset X = \left\{0,1,\ldots,n\right\}$ can be written as $A=B+C$
Let $A$ be a nonempty subset of $X=\left\{0,1,\ldots,n\right\}$. We may ask whether $A$ can be written as $A=B+C$, where $B,C$ are also nonempty subsets of $X=\left\{0,1,\ldots,n\right\}$. Here, $B+C$ ...
- 1,371
3
votes
1
answer
76
views
Understanding a step in Erdลs's bound $2^{g(x)}\leq x\cdot g(x) \implies g(x)<\frac{\log{x}}{\log{2}} + [1+o(1)]\frac{\log{\log{x}}}{\log{2}}$
I'm looking at the problem 6. of an old Erdลs paper Problems and results in additive number theory and I'm having trouble to understand a derivation he does.
The problem starts with
Some time ago ...
0
votes
0
answers
72
views
Sums of a quadratic-generated odd sequence and coverage of the even integers
For $\alpha > 0$, let
$$
A(\alpha) = \{ R_{\text{up-odd}}((\alpha x)^2 + \alpha x + 1) : x \in \mathbb{Z}_{\ge 0} \},
$$
where $R_{\text{up-odd}}(t)$ means: take the ceiling $\lceil t\rceil$; if it ...
- 1,403
3
votes
3
answers
258
views
Do the set of coprimes of a number form an additive basis?
For any positive integer $n,$ define $X:= \{ a: (a,n) = 1,\ 1\leq a < n \}.$ Let $(X+X)^*:= \{ (x+y)\pmod n: x,y\in X \}.$
Conjecture: If $n$ is even, then $(X+X)^*= \{ 0,2,4,\ldots,n-2\}.$ If $n$ ...
- 25.2k
2
votes
0
answers
149
views
$n$ divisors of $n$ guarantees a subset sum of divisors adding up to $n$
Problem:
Let $n$ be a positive integer, and let $D$ be a multiset of $n$ positive divisors of $n$. Prove that there must exist a subset of $D$, with sum equal to $n$.
By multiset, I mean that, some ...
- 41
1
vote
0
answers
42
views
Unsure about a step in the proof of Pollard's generalisation of the Cauchy-Davenport theorem
In J.M. Pollard's A generalisation of the theorem of Cauchy and Davenport (1974), Pollard shows that for a prime $p$ and $A,B \subseteq \mathbb{Z}/p\mathbb{Z}$, if $N_r$ denotes the number of elements ...
- 11
0
votes
0
answers
43
views
Lattice of the sum of 2 elements belonging to a chain in a partially ordered finite abelian group
In a finite partially ordered abelian group, if we are given a chain $a<b<c<d...,$ we can construct a "generic" poset with only the necessary orders for the sum of $2$ distinct ...
- 99
5
votes
1
answer
101
views
3APs implies large additive energy
I am trying to solve Exercise 4.2 in Julia Wolf's Additive Combinatorics Notes. Let $G$ be any finite abelian group, but say $G = (\mathbb{Z} / 3\mathbb{Z})^n$ so that 3APs $(x, y, z)$ satisfy $x + y +...
- 3,914
2
votes
2
answers
96
views
How to show that a set in $\mathbb{F}_5^{2n}$ is $3$-progression-free
Let $$D = \left\{ (0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (3, 2), (2, 3) \right\} \subset \mathbb{F}_5^2,$$
let $ n $ be a multiple of $ \lvert D \rvert = 10 $, and define the ...
- 4,414
1
vote
0
answers
51
views
Where is the assumption $0\in B$ used in Nathanson's generalization of Cauchy-Davenport (Theorem 2.1)?
I'm studying Theorem 2.1 from Additive Number Theory by Melvyn Nathanson (GTM 165), which extends the Cauchy-Davenport Theorem to composite modulus $n$, under the additional assumptions that:
$0\in B$...
- 11
2
votes
1
answer
92
views
How to generalise Behrend's construction to 4-APs?
In Behrend's classical paper a bound lower bound for the maximum size of $3$-free sets is constructed. I wonder, whether it is possible to generalise this approach to $4$-free sets.
My thoughts on ...
- 4,414
0
votes
0
answers
43
views
On counterexamples of the converse of Szmeredi's theorem
I am looking for a counterexample to prove that the converse of Szemeredi's theorem on arithmetic progressions does not hold. Whilst the Green-Tao theorem provides an interesting counterexample, I was ...
