Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the ...

learn more… | top users | synonyms

-3
votes
0answers
38 views

MDAS solution glitch [on hold]

I always get confused with this kind of math problem, How do we solve this problem? Example: 1 * 5 - 10 + 2 = ? Solution 1 [My solution]: Of couse I use MDAS ...
4
votes
0answers
37 views

Number of classes $\pmod p$ represented by $b_1s^{n-1} + \dots + b_n$ where $ord_p(s) = n$

Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ ...
0
votes
0answers
48 views

When are these sums consecutive integers? [closed]

It is possible to construct $\frac{n(n-1)}{2}$ sums which each contain two distinct summands chosen from a set $n$ numbers. For which $n\geq 3$ do there exist a set of $n$ (distinct) integers such ...
8
votes
1answer
114 views

Small set such that $\{1 , \ldots , n\} \cdot A = \mathbb{Z} / p \mathbb{Z}$

Let $p$ be a large prime and $n < p$. What is the smallest size of a set $A \subset \mathbb{Z} / p \mathbb{Z}$ such that $A \cdot \{1 , \ldots , n\} = \mathbb{Z} / p \mathbb{Z}$? Here $\cdot$ ...
1
vote
1answer
256 views

Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$. Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...
0
votes
0answers
20 views

Is budget-additive function a modular set function?

We know that budget-additive function $$ f(S) = \min\{B,\sum_{i \in S}w_i\} $$ where $w_i$ is positive constant and $B \ge 0$ is called additive budget. Is it also a modular set function?
1
vote
1answer
320 views

On Sylvester's coin problem for geometric progressions

Given $a,b\in\Bbb N$ we know from http://www.emis.ams.org/journals/INTEGERS/papers/i33/i33.pdf that the smallest number that cannot be written as a non-negative linear combination of integers with ...
1
vote
1answer
206 views

Approximation of sets

Is the following true? For every $\varepsilon>0$ there is a finite subset $W$ of $\mathbb{N}\times \mathbb{N}\times \mathbb{N}$, such that $$|p_1(W)\cap p_2(W)\cap \{p_1(x)+p_2(x):x\in W\}\cap \{...
9
votes
1answer
1k views

Coin problem with permutations

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers. It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c \mathbb{N}...
8
votes
0answers
261 views

What is intuition behind sets with more sums than differences?

There exist finite sets $A$ in, say, $\mathbb{Z}$, such that $|A+A|>|A-A|$. The minimal such set contains 8 elements and consists of, say, 0, 2, 3, 4, 7, 11, 12, 14. How should I find such an ...
4
votes
0answers
98 views

Restricted addition analogue of Freiman's $(3n-4)$-theorem

There is a well-known theorem of Freiman saying that if $A$ is a finite set of integers with $|2A| \le 3|A|-4$, then $A$ is contained in an arithmetic progression with at most $|2A|-|A|+1$ terms. Is ...
0
votes
0answers
40 views

When does the equality hold in Dias da Silva - Hamidoune Theorem?

Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
0
votes
1answer
107 views

Sumset achieving extreme upper bound [closed]

It is trivial that $|A_1 + \cdots + A_h| \leq |A_1|\cdots |A_h|$, where $h \geq 2$ and $A_i \subseteq \mathbb{Z}$ are nonempty finite sets and $A_1 + \cdots + A_h :=\{a_1 + \cdots + a_h : a_i \in A_i ~...
3
votes
1answer
124 views

Lower bound construction for Multidimensional Szemerédi's Theorem

The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement. Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is ...
1
vote
0answers
52 views

On structure of patterns of subset sums?

There are roughly $2^{nm}$ choices of sets of $m$ distinct integers in $[-2^n,2^n]$ (after fixing ordering). Each set of $m$ integers has $2^m$ subsets. Suppose we assign $\{0,1\}$ value to each ...
6
votes
1answer
214 views

Is the exponent $2$ sharp in the Balog-Szemerédi-Gowers Theorem?

The Balog-Szemerédi-Gowers theorem can be stated in the following form: let $A,B$ be subsets of $\mathbb{Z}/n\mathbb{Z}$ (say) with equal cardinality, such that $$ \|1_A*1_B\|_2 \ge K^{-1} \|1_A\|_1 \|...
11
votes
3answers
1k views

When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

As a natural (and expectable) extension of my earlier question: How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, ...
15
votes
1answer
336 views

Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6) Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each ...
7
votes
1answer
516 views

A variation of Minkowski sum

I have to work with the following variation of Minkowski sum: Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$. Set $$K^+=\{\\,x+y\in\mathbb E\mid(x,...
2
votes
0answers
178 views

Generalized arithmetic progressions contained in Bohr sets

Recall that a generalized arithmetic progression of dimension $d$ is, by definition, a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...
3
votes
1answer
178 views

Find a subset such that its sum is divisible by $n$

It is said that the following proposition is true. $\forall S \subset \mathbb{Z}, |S| = 2n-1.\ \exists A \subset S, |A| = n$ which satisfies $$ n \ | \ \sum_{a \in A}a. $$ Could someone gives a ...
8
votes
0answers
144 views

Sets of natural numbers which are almost closed under addition

I am interested in a classification of sets $A \subseteq \mathbb{N}$ such that for all $k \in A$, $d( A+k \cap \mathbb{N} \setminus A) = 0$ where $d$ is the asymptotic density and $A+k = \{n \in \...
6
votes
1answer
112 views

Are the extremal points of a certain set of functions $\mathcal P(\mathbf N) \to \bf R$ weakly additive?

Let an upper density (on $\mathbf N$) be a (set) function $f: \mathcal P(\mathbf N) \to \mathbf R$ such that, for all $X, Y \subseteq \bf N$ and $h,k \in \mathbf N^+$, the following hold: (F1) $f(\...
13
votes
3answers
1k views

A seemingly simple combinatorial object that must have an easy generating function

One more question related to my earlier "Special" meanders. I am trying to isolate simplest problems related to it. Here is one. For a composition (i. e. a tuple of natural numbers) $\...
4
votes
1answer
180 views

“Pseudo-random” subsets of additive bases

We say that a subset $B \subset \mathbb{N}$ is an (asymptotic) additive basis of order $k$ if the set $kB = B + \cdots + B = \mathbb{N} \setminus C$, where $C$ is a finite set of positive integers. ...
0
votes
0answers
79 views

Embedding a cancellative monoid into another in such a way that $|X-x|=|X|$, where $X$ is a fixed finite set and $x\in X$

Preliminaries. Let $\mathbb A = (A, +)$ be a possibly non-commutative semigroup. For $X, Y \subseteq A$ we set $$ X - Y := \{a \in A: a + y \in X\text{ for some }y \in Y\}, $$ which is just the usual ...
5
votes
1answer
240 views

Zero-sum sets in union-closed families

The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ ...
10
votes
2answers
344 views

Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems: Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le \frac{|AA|^n}{|A|^n}|...
1
vote
1answer
93 views

Does positive relative density imply asymptotic additive basis behaviour?

First definitions: let $A, B \ \subset \mathbb{Z_{>0}}$ and $1\in A, 1\in B$. We define the relative density of $A$ with respect to $B$ to be $$rel(A, B) = \inf_n \frac{|A \cap [1,n]|}{| B \cap [1,...
9
votes
1answer
286 views

Largeness and arithmetic progression properties of generic reals

Consider the following properties for a subset $A$ of $\mathbb{N}$: (1) $A$ is large: $\sum_{n \in A}$$ 1\over n$$=\infty,$ (2) $A^\infty=\limsup \frac{|A \cap \{ 1, \dots, n\}|}{n} >0$, (3) $A_\...
3
votes
1answer
127 views

3-dimensional vectors satisfying certain equalities

Question: Are there 5 distinct vectors $u,v,w,x,y \in \mathbb{R}^3$, all on the unit sphere (i.e. $||u||=||v||=||w||=||x||=||y||=1$), such that: $||u+v+x||=||u+v+y||=||u+w+x||=||u+w+y||=1$ ? Also, ...
9
votes
1answer
447 views

Who was/were the first to note that if $\sum_{x \in X} \frac{1}{x} < \infty$ then the natural density of $X$ is zero?

It is a result of folklore that the natural density of a set $X$ of positive integers such that $\sum_{x \in X} \frac{1}{x} < \infty$ is zero. This is reproved, e.g., in T. Šalát's paper: ...
7
votes
1answer
358 views

Does $|A+A|$ concentrate near its mean?

Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...
22
votes
1answer
717 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
4
votes
0answers
228 views

The original proof of Szemerédi's Theorem

Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...
6
votes
1answer
314 views

Additivity of upper densities with respect to arithmetic progressions of integers

Let $\mathsf{d}^\star$ be the asymptotic upper density, defined on the power set of positive integers $\mathbf{N}^+$, so that $$ \mathsf{d}^\star\colon \mathcal{P}(\mathbf{N}^+) \to\mathbf{R}\colon X\...
3
votes
1answer
164 views

Freiman-isomorphic sets

Haw can we prove that an arbitrary set $A$ of $n$ positive integers is 2-Freiman isomorphic to a subset of {$ 1,2,...,4^{n}$} and $4^{n}$ cannot be improved to $2^{n}$?
4
votes
1answer
165 views

Reference to a variant of Abel's summation formula

Edit. A stronger version of the formula is true (details follow). Let $(a_n)_{n \ge 1}$ be a sequence of complex numbers, $(\lambda_n)_{n \ge 1}$ a nondecreasing sequence of positive reals such that $...
2
votes
1answer
58 views

l-wise t-intersecting families of shifts of finite sets of integers

Let $A$ be a finite set of non-negative integers and write $I_k$ for the set ${0,1,\ldots,k-1}$. Form all possible l-wise intersections $(A+k_1)\cap \ldots \cap (A+k_l)$, where each $k_i$ runs through ...
3
votes
1answer
267 views

Problem related to Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$. Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if, for any $r,s,u,...
3
votes
2answers
119 views

Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes,...
2
votes
1answer
100 views

Intersections of translates of finite sets of integers

I am searching for a result in the literature that I am sure must be known, but I just fail to find it. Let us starts with a simple example: Let $A, B\subset \mathbb{Z}$ be a finite sets of integers ...
1
vote
0answers
84 views

Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
5
votes
0answers
71 views

Some questions about the Lévy monoid of certain densities

Let $\bf H$ be a set, $f: \mathcal P({\bf H}) \rightharpoonup \bf R$ a partial function, and $\mathcal{D}$ the domain of $f$. Next, denote by $\mathcal M(f)$ the set of all (total) functions $\theta: ...
0
votes
0answers
55 views

$\mathsf{GCD}$s of random linear form

Given $a,b\in\Bbb N_{<M}$ where $M\in\Bbb N_{>\exp(18)}$ is arbitrary with $(a,b)=1$, the probability that $\mathsf{gcd}(ax_1+by_1,ax_2+by_2)=1$ where $x_1,x_2,y_1,y_2\in\Bbb N_{>\ln M}$ is ...
3
votes
1answer
148 views

Exact statistics in the Frobenius coin problem

The Frobenius coin problem guarantees that if $(a,b)=1$, then $$ax+by$$ does not represent exactly $\frac{(a-1)(b-1)}2$ numbers all below $g(a,b)=ab-a-b$ if $x,y\geq0$ holds. Assume $m\in[0,ab-a-b]$ ...
8
votes
0answers
216 views

An abstract zero-sum problem

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
9
votes
0answers
301 views

A characterization of quadratics similar to an inverse sieve problem

Suppose $\mathscr{A} \subset \mathbb{N}$ enjoys for all large enough cutoffs $X$ the following properties: $|\mathscr{A} \cap [1,X]| > \sqrt{X}/10$; and the discriminant $\prod_{\alpha \neq \beta}...
12
votes
1answer
831 views

Where did the term “additive energy” originate?

A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...
8
votes
0answers
217 views

Partition regularity in the squares

A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...