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
1answer
90 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, ...
11
votes
1answer
341 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) ...
9
votes
1answer
424 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
317 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 ...
7
votes
1answer
867 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 ...
22
votes
1answer
694 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 ...
9
votes
1answer
298 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 ...
4
votes
0answers
210 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 ...
4
votes
0answers
50 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) ...
6
votes
1answer
304 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 ...
3
votes
1answer
144 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
144 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 ...
3
votes
1answer
214 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 ...
2
votes
1answer
54 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 ...
4
votes
1answer
251 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 ...
3
votes
2answers
100 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$ ...
2
votes
1answer
89 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
74 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
65 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
48 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
140 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
175 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 ...
7
votes
0answers
251 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 ...
12
votes
1answer
744 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
161 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 ...
5
votes
0answers
176 views

Is $AA+A$ always at least as large as $A/A$?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A/A|$? In the line above, $AA+A:=\{ab+c:a,b,c \in A \}$, while $A/A:=\{a/b:a,b \in A, b\neq 0 \}$ is the ratio set. ...
6
votes
1answer
244 views

Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...
42
votes
3answers
3k views

Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
6
votes
2answers
246 views

Additive energy of Piatetski-Shapiro sequences

Let $c>1$, and let $A$ denote the set $$ \Big\{ \lfloor n^c \rfloor, \quad 1 \leq n \leq N \Big\}. $$ Thus $A$ consists of the first $N$ elements of a so-called Piatetski-Shapiro sequence. The ...
1
vote
1answer
150 views

limit and combinatorics

Given $x \in (0,\frac{1}{2})$ and $y \in (0,\frac{1}{2}]$, what is the value of the following limit: $\lim_{n\rightarrow \infty}\sum_{k=0}^{n}{n \choose k}|x^{n-k}(1-x)^{k}-y^{n-k}(1-y)^{k}|?$ When ...
2
votes
0answers
111 views

Additive combinatorics and a Diophantine equation

Let $(n_k)_{1 \leq k \leq N}$ be a sequence of distinct positive integers. For $v \in \mathbb{Z}$ set $$ A_N(v) = \# \Big\{ (k,\ell) \in \{1, \dots, N\}^2, ~k \neq \ell:\quad n_k - n_\ell = v \Big\}. ...
20
votes
1answer
661 views

Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$ In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$ only when we sum the last summand? For ...
13
votes
1answer
488 views

Erdös-Turán via Hardy-Littlewood circle method?

For any set $B\subseteq \mathbb{N}$ one can associate the formal series $$f_B(z) = \sum_{b\in B}z^b$$ and obtain $$f_B(z)^k = \sum_{n\geqslant 0} r_{B,k}(n)z^n,$$ where $r_{B,k}(n) = ...
3
votes
2answers
306 views

Is the sumset or the sumset of the square set always large?

Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$. Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity: $$\max ...
11
votes
2answers
736 views

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression. I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid ...
3
votes
0answers
155 views

On covering by smooth numbers

Denote $P(n)=\mathsf{greatest}\mbox{ }\mathsf{prime}\mbox{ }\mathsf{factor}\mbox{ }\mathsf{of}\mbox{ }n$. Denote $S(x,y)=\{n<x: P(n)<y\}$. Denote $S_t(x,y)=\sum_{i=1}^tS(x,y)$ as $t$-fold ...
18
votes
0answers
485 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
4
votes
0answers
207 views

Area defined with $\pm$ closedness

Denote $B_n\subset\Bbb R^n$ to be unit ball at origin. Denote $S\subset B_n$ to region of type $\mathsf I$ if it satisfies $$s\in S\iff\forall t\in S, s+t\in S\mbox{ or }s-t\in S$$ I am convinced ...
6
votes
1answer
266 views

What pairs of sets have additive energy?

In an abelian group, the additive energy between two sets is $$E(A,B)=|\{(a_1,a_2,b_1,b_2) \in A\times A\times B\times B:a_1+b_1=a_2+b_2\}|$$ which is ranges from $|A||B|$ to $(|A||B|)^{3/2}$. What I ...
2
votes
1answer
77 views

Elaboration of a certain section of a paper by Thanigasalam

In section 11 of this paper by Thanigasalam, it says "... we get $G(10)\le 105$, and this implies that $H(10) \le 107$". However, it is very unclear how this follows. Why is it the case that $G(10)\le ...
0
votes
0answers
102 views

Determing signs of Taylor coefficients in entire functions

This is a continuation of Determining when combinatorial sums are zero Suppose $f(x)$ is an entire function approximated by polynomials with only negative real zeros. Suppose further that ...
6
votes
2answers
279 views

Determining when combinatorial sums are zero

To keep things simple with a specific example, we ask: Prove that $\displaystyle\ a_n:=\frac{1}{n!}\sum_{k=0}^n \binom{n}{k} \frac{1}{k!} (-1)^{n-k}$ is zero if and only if $n=1$. (Or find a ...
2
votes
1answer
196 views

On the upper Banach density of the set of positive integers whose base-$b$ representation misses at least one prescribed digit

Let $b$ be a fixed integer $\ge 2$ and $A$ a proper subset of $\{0, \ldots, b-1\}$. Then define $X$ to be the set of all positive integers whose base-$b$ representation consists only of digits from ...
7
votes
0answers
153 views

Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
3
votes
0answers
130 views

Goldbach's problem in algebraic number fields [duplicate]

Are there any results on the representation of numbers in algebraic number fields as the sum of primes in the ring of integers in that field? There are some results for Waring's problem in other ...
5
votes
3answers
508 views

Any rigorous way to claim that sums with repeat summands are few?

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...
3
votes
1answer
179 views

When are the powers of 2 sum-free mod n?

I've encountered the following question in my research: Let $A$ be a subset of $\mathbb{Z}/n\mathbb{Z}$. Let me call $A$ "sum-free" if there is no solution to $x+y=z$ for $x,y,z \in A$ with distinct ...
3
votes
1answer
180 views

higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$. Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...
4
votes
1answer
250 views

Ref. request: Additive probability measure on $\mathcal P({\bf N})$ supplies subset of $\mathbf R$ without Baire property

ZFC proves, among the other things, the existence of a (finitely) additive probability measure $\theta: \mathcal P(\mathbf N) \to \mathbf R$ on the power set of $\mathbf N$ such that $\theta(X) = 0$ ...
5
votes
1answer
167 views

Unicity of additive, $(-1)$-homogeneous, and shift invariant probability measures on $\mathbf N^+$

Let $\mathcal D$ be the set of all (finitely) additive probability measures $\mu^\ast: \mathcal P(\mathbf N^+) \to [0,\infty[$ such that $\mu^\ast(k \cdot X + h) = \frac{1}{k} \mu^\ast(X)$ for all $X ...