Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [additive-combinatorics]

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 top-level tags nt.number-theory or co.combinatorics. Some additional tags are available for further specialization, including the tags sumsets and sidon-sets.

3
votes
1answer
142 views

A variance computation

Can you help me compute a variance? Let $(x_{i,j})_{(i,j)\in\mathbb{N}^2}$ be random variables with these two properties: for any $(i,j)\in\mathbb{N}, x_{i,j} = \overline{x_{j,i}}$ for any $(i,j) \...
4
votes
1answer
199 views

Which cyclic groups admit a difference set?

Problem 1. For which $n$ does the cyclic group $C_n$ admit a difference set $D\subset C_n$, i.e., a set such that each non-unit element $x\in C_n$ can be uniquely written as the difference $x=ab^{-1}$...
3
votes
1answer
217 views

Large gaps in Singer planar difference sets?

By a classical result of Singer (1938), for a prime number $p$ the cyclic group $C_n$ of order $n=1+p+p^2$ contains a subset $D$ of cardinality $|D|=1+p$ such that $DD^{-1}=C_n$. Such set $D$ is ...
11
votes
1answer
479 views

What is the smallest cardinality of a set A whose difference A-A contains $n$ consequtive integer numbers?

Problem. What is the smallest cardinality $d(n)$ of a set $A$ of integer numbers such that the difference set $A-A=\{a-b:a,b\in A\}$ contains $n$ consequtive integer numbers? It can be shown that $(1+...
15
votes
4answers
497 views

Are all partial consecutive harmonic subsums distinct?

Let $b \gt a \geq 0$ be integers, and as elsewhere let $H_n$ be $\sum^n_{i=1} 1/i$. A partial consecutive harmonic subsum is a number $H(a,b)$ of the form $H_b - H_a$ (with $ H_0=0$). If $c=a$ and $...
3
votes
0answers
83 views

Given a primitive finite set $A\subseteq\bf N$ with $0\in A$, find two more primitive sets $B,C\subseteq\bf N$ with $B\ne C$ and $A+B=A+C$

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of all finite subsets of $\mathbf N$ containing $0$ with the operation of set addition $$ (X, Y) \mapsto X + Y := \{x+y: x \in X \text{ and }y \...
4
votes
0answers
91 views

Two variants of the Littlewood-Offord theorem

I found two different looking things being called the Littlewood-Offord theorem, If $\vec{a} \in \mathbb{R}^k \setminus 0$ and $t \in \mathbb{R}$ then there are $O(\frac{2^k}{\sqrt{k}})$ points $x \...
2
votes
0answers
129 views

A set in Z/nZ which contains two elements, one of which is a small multiple of the other

While doing my research, I came across yet another problem in $\mathbb Z/n\mathbb Z$ (see my previous question on a related matter here). Let $n$ be a prime and let $k$ be an integer, $1 \leq k \leq ...
1
vote
1answer
167 views

Covering a finite ring with arithmetic progressions

Let $n\geq 2$ be a positive integer and $k$ be a number between $1$ and $n$. Recently, I came across the following question about $\mathbb Z/n\mathbb Z$ and I wonder if it was studied before. I'd be ...
1
vote
0answers
34 views

maximum subsets of a certain type contained in difference set

Explaining my question in words doesn't really make sense. I'll define a few concepts first. for a set $S \subseteq \mathbb{Z} $, define $||S||=\{|s| : s \in S ,\ |s|>0\}$ i.e. the set ...
2
votes
2answers
360 views

Playing leapfrog with primes

In connection with how primes jump (How do these primes jump?), I consider the following game. Let $R$ be a finite set of positive integers. For this question, I content myself with $R$ being the $k$ ...
3
votes
3answers
277 views

Computation of a series

NOTATIONS. Let $n\in\mathbb{N}$. We define the sets $\mathfrak{M}_{0}:=\emptyset$ and \begin{align} \mathfrak{M}_{n}&:=\left\{m=\left(m_{1},m_{2},\ldots,m_{n}\right)\in\mathbb{N}^{n}\mid1m_{1}+...
0
votes
1answer
94 views

Sets with $\mathrm{d}(h\mathscr{A}) = 1$ but s.t. $h\mathscr{A}$ doesn't contain all large integers

Given $\mathscr{A}\subseteq\mathbb{N}$ an infinite set, consider its $h$-fold sumsets $$h\mathscr{A}:=\left\{\sum_{i=1}^{h} k_i : k_1,\ldots, k_h\in \mathscr{A} \right\},$$ and let "$\simeq$" be the ...
3
votes
0answers
148 views

Probabilistic proof for “regularity”

In an old post, someone said that the Calderon-Zygmund decomposition "follows from a simple stopping time argument". I would like to see this probabilistic argument (should be something simple). I ...
4
votes
2answers
220 views

How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?

Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much ...
2
votes
1answer
297 views

What if $|A+A|$ is proportional to $|A|^{1 + \delta}$?

Let $A$ be a finite subset of the integers and $0 < \delta \leq 1/2$. Suppose that $$|A+A| \asymp |A|^{1+\delta}.$$ What examples of such an $A$ are known? Can we conclude anything in general ...
2
votes
0answers
76 views

Partitioning an interval into subsum-free sets

Let $F(n)$ be the largest integer $N$, such that the set $\{1, 2, \ldots, N\}$ can be partitioned into $n$ sets $A_1, \ldots, A_n$, such that for all $i$ and all sets $B\subseteq A_i$ with at least 2 ...
3
votes
2answers
377 views

Two equivalent statements about primes

Regarding to our hypothesis in https://math.stackexchange.com/questions/1918406/a-hypothesis-about-the-conjecture-every-even-number-is-the-difference-of-two-p , we guess that the following statements ...
6
votes
2answers
741 views

Gromov's pseudogroups and Tao's approximate groups

In his article Gromov, M. Almost flat manifolds. J. Differential Geom. 13 (1978), no. 2, 231–241 Gromov exploited a notion of a pseudogroup. In his book Tao, Terence. Hilbert's fifth problem and ...
1
vote
0answers
126 views

Growth of products of large sets in Lie groups

The Steinhaus Theorem states that if $A$ is a set of positive measure in a locally compact group $G$, then the set $A *A^{-1} := \{ab^{-1} | a,b \in A \}$ contains a ball around the identity in $G$. ...
3
votes
2answers
145 views

No Sidon sequence which is an asymptotic basis of order $2$

$\omega \subseteq \mathbb{R}^+$ is called a Sidon sequence, if all the sums $a + a' \ (a, a' \in \omega, a \leq a')$ are distinct, and it is an asymototic basis of order $2$, if any positive integer $...
3
votes
0answers
68 views

Strong criteria for additive non-basis

In Paragraph 7 of A. Stöhr's paper "Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I", there are several criteria to decide whether a given sequence $\mathscr{A}\subseteq \mathbb{...
4
votes
0answers
431 views

An inequality from Green-Tao “The primes contain arbitrary long arithmetic progressions”

I have been reading "The primes contain arbitrary long arithmetic progressions" by Green and Tao (The version on the ArXiv: https://arxiv.org/pdf/math/0404188v6.pdf) going through the details and ...
12
votes
1answer
305 views

Is there a strictly increasing sequence such that it is o(2^n) and any term cannot equal the sum of any unrepeated predecessors?

Does there exist a strictly increasing sequence $\{a_n\}_{n\in N}$ of natural numbers such that the following two requirements hold: 1, For all $n\in N$, there is NO subset $M$ of $\{0,\cdots ,n-1\}$ ...
1
vote
0answers
150 views

Are the Beatty primes asymptotically (Gowers) uniform?

A result of Green and Tao (initially conditional on two conjectures which were eventually settled by them and Ziegler) states that for any $s\in\mathbb N$, $$\lim_{w\to\infty}\limsup_{N\to\infty}\sup_{...
4
votes
0answers
117 views

Negative values of cosine sums

Consider real numbers $x_1, \dots, x_M$ such that $$\sum_{i=1}^{M} \frac{\cos(x_i t^2)}{e^{(x_it)^2}} \le -\frac{1}{2}, $$ for all $L< t <L^A,$ where L is a large number. What lower bound ...
1
vote
1answer
99 views

Invariant complementary sets modulo $p$

Let $p \ge 11$ be a prime number, $k,n$ be positive integers such that $n|gcd(p-1,k-1)$ and $p > k > n \ge 5$. Let $s \in \mathbb Z_p$ such that $ord_p(s) = n$. Is it possible that the sets $A = ...
0
votes
1answer
344 views

Geometric progression modulo p [closed]

Let $p\ge 11$ be a prime number, $n \ge 5$ be an odd positive divisor of $p-1$ and $s \in \mathbb Z_p$ such that $ord_p(s) = n$. Is it true that the geometric progression $\{s^k\}_{k \in \mathbb Z_n}$...
3
votes
1answer
186 views

(Extremal) arithmetic combinatorics in non-abelian groups

Roth's Theorem states that any subset $A$ of $\{1, \dots, n\}$ with no solution to the equation $$x + y = 2z,\, (x, y, z) \in A^3,\, x \neq y$$ has size $o(n)$. Similar results hold when dealing with ...
3
votes
0answers
68 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$ ...
11
votes
2answers
347 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$ ...
0
votes
1answer
199 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
410 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 \{...
0
votes
1answer
361 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 ...
8
votes
0answers
290 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
110 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 ...
2
votes
1answer
131 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
142 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
188 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 ...
6
votes
1answer
240 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 \|...
15
votes
1answer
414 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 $...
4
votes
1answer
355 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
178 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 \...
0
votes
0answers
114 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 ...
3
votes
1answer
122 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,...
8
votes
1answer
344 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_\...
6
votes
1answer
279 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]$ ...
3
votes
1answer
142 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, ...
14
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) $\...
7
votes
1answer
441 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 ...