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.

389 questions
Filter by
Sorted by
Tagged with
42 views

• 563
1 vote
59 views

• 1,064
129 views

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^{\... • 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 ... • 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 + ... • 10.2k 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 \... • 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 ... • 11 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'... 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+... 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 ... 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,... 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 ... • 11 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 ... 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)... • 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 ... • 19.8k 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,... • 1,676 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$...
• 16.7k
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 ...