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.
631
questions
0
votes
0
answers
36
views
Sets avoiding fixed differences
I'm aware of the well-known work on sets avoiding arithmetic progressions. Are there non-trivial results on sets of positive integers satisfying rules such as $(A \cap (A -4)) \cup (A \cap (A -15)) \...
- 1
2
votes
0
answers
107
views
Counting $A+A-A$ with partial multiplicity
A recent question asked whether, given a finite set of positive numbers $A$, it is always the case that the set $A+A-A$ has more positive than negative elements. Terry Tao showed that this is false (...
- 4,819
58
votes
2
answers
3k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 633
0
votes
0
answers
97
views
Additive combinatorics [closed]
How to use fixed points of group actions on Cartesian powers on the set to prove the existence of arithmetic progressions in this set?
For example, having a sequence of integer numbers ($a<b<c$),...
2
votes
0
answers
78
views
Trapezoid-free subsets of the plane obtained by deleting lines
Let $A,B,C \subseteq \mathbb{Z}_n$. Suppose that for any $a' \in A, b' \in B, c' \in C$,
\begin{align*}
|(A+b') \cap (B+a') \cap -C| &\le 1,\\
|(A+c') \cap -B \cap (C+a')| &\le 1,\\
|-\hspace{-...
- 358
3
votes
0
answers
126
views
Szemerédi’s theorem in really dense sets
This question is inspired by Tao’s answer in this post. I have thought about this occasionally for several months without anything concrete.
Question:
Given $\delta>0$ and $k\ge 3$, let $N= N_k(\...
- 2,322
3
votes
1
answer
194
views
Bins-and-primes (prime divisors of $\prod(a_i-a_j)$, II)
This is a refined version of a question I have recently posted.
For a prime $p$, let $\varphi_p\colon\mathbb Z\to\mathbb Z/p\mathbb Z$ denote the canonical homomorphism from the integers onto the ...
- 22.2k
2
votes
1
answer
142
views
Prime divisors of $\prod(a_i-a_j)$
For a prime $p$, let $\varphi_p\colon\mathbb Z\to\mathbb Z/p\mathbb Z$ denote the canonical homomorphism from the integers onto the group of order $p$.
Given an integer $n\ge 3$, what is the smallest ...
- 22.2k
0
votes
0
answers
30
views
Non-isolating group labeling of a hypergraph
Let $(G,+,0)$ be an abelian group, $H=(V,\mathcal{E})$ is a $r$-uniform hypergraph. Let $\ell:V\to G$ be a labelling of the vertices. The label of an edge is the sum of the label of the vertices, so $\...
- 573
3
votes
0
answers
72
views
Dimension of a kernel of a cocycle map
Inspired by a previous question (Dimension of a kernel of a linear map) and some of the answers I was given I thought wheter I can generalize the question to the following:
Compute the kernel (or at ...
- 169
0
votes
0
answers
68
views
Number-picking combinatorial sorting problem [closed]
So let's say we have a pool of infinitely many real numbers, varying in the range of 1.1 to 20, with repeats. We need to pick a bunch of numbers, with the maximum being 500 such that these numbers can ...
- 1
8
votes
1
answer
295
views
The growth rate of a commutator set in a non-elementary group
Let $G$ be a non-elementary group generated by a finite set $S$. Here, a group is called non-elementary if it is not virtually abelian. Denote $S^{\le n}:=\{g\in G: |g|_S\le n\}$ for any $n\in \mathbb ...
- 145
1
vote
0
answers
105
views
A representation problem involving strict partition numbers
For each positive integer $n$, let $q(n)$ denote the number of ways to write $n$ as a sum of distinct positive integers. We call those $q(n)\ (n=1,2,3,\ldots)$ strict partition numbers.
The sequence $...
- 13.7k
0
votes
0
answers
29
views
Partitioning vectors from Z^k into bundles preserving their additive properties
Let $B_1, B_2, \dots, B_m$ be disjoint subsets of $\mathbb{Z}^k$ and $B$ denote their union.
Also suppose that $k$ upper bounds the $\ell^\infty$-norm of every vector in $B$.
A set $V \subseteq B$ of ...
- 33
14
votes
2
answers
879
views
A sum-product phenomenon on reciprocals
Let $A \subset \mathbb F_p \setminus \{0\} $ and let $A+1/A = \{x+1/y:x,y \in A\}$.
Question: For fixed $c>0$, if $|A| \geq cp$, is $|A+1/A|$ at least $(1-o(1))p$ when $p \rightarrow \infty$?
Known:...
- 9,108
1
vote
1
answer
339
views
Dimension of a kernel of a linear map
Let $\mathbb{F}$ be a field of characteristic $2$, $n$ be a positive integer and $f_n:\bigoplus\limits_{i=1}^n\mathbb{F}\sigma_{i}\mapsto \bigoplus\limits_{i,j=1,i<j}^n\mathbb{F}\sigma_{i,j}$ be a ...
- 169
1
vote
1
answer
75
views
Counting the number of summands in a vector space over characteristic $2$ to get a direct sum
Let $\mathbb{F}$ be a field of characteristic $2$ and define $S$ to be the set of all triples $(i,j,k)\in\lbrace 1,\dotsc,n\rbrace^3$ with $\left|i-j\right|=1$, $\left|i-k\right|>1$, and $\left|j-k\...
- 169
3
votes
0
answers
75
views
On fractional parts and Behrend’s construction
Given $\theta \in \Bbb{T}^D := \Bbb{R}^D/\Bbb{Z}^D$, write $f_\theta$ for the homomorphism from $\Bbb{Z}\to \Bbb{T}^D$ induced by $1\mapsto \theta$.
For $x\in \Bbb{T}^D$, let $||x||$ be the smallest $\...
- 2,322
3
votes
0
answers
143
views
What is the density of numbers which have at least two divisors whose sum is a perfect square?
Note: This question was posted in MSE about two years ago but it not receive an answer. Hence posting in MO.
A positive integer is said to have square-sum divisors if it has at least two divisors ...
- 4,416
0
votes
0
answers
10
views
Existence of a specific family of functions on an abelian group with vanishing properties on rank 2 subgroups
Fix a prime $p$, and let $W_0\subset W$ be an inclusion of a codimension one $\mathbb{F}_p$ vector spaces. Let $W_e$ denote a fixed nontrivial coset of $W_0$ in $W$.
The question is whether there ...
- 1,607
2
votes
1
answer
346
views
Sets with certain property concerning density of sumsets
I am working with subsets of $[n]$ of the form $(A+B)\cap A$, where $A+B$ is a sumset. Namely, I am interested if there are nonempty sets $B$ such that whenever $A$ covers a positive proportion of $[n]...
- 705
7
votes
2
answers
366
views
Decomposition of a natural number as sum of positive integers
Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such ...
- 215
5
votes
0
answers
95
views
Multidimensional van der Waerden, bounds for squares
Given $r$, let $f(r)$ be the smallest $N$ such that for any $r$-coloring $C:\{1,\dots,N\}^2 \to \{1,\dots,r\}$, there exists $x,y,d\neq 0$ such that $C((x,y)) = C((x+d,y))= C((x,y+d))=C((x+d,y+d))$.
I ...
- 2,322
3
votes
1
answer
166
views
Decomposing a set of integers as a union of well-separated (discrete) intervals
Let a discrete interval be a set of the form $\{x \in \mathbb Z \colon a \le x \le b\}$ with $a, b \in \mathbb Z \cup \{\pm \infty\}$. Then define the boxing dimension $\text{bim}(S)$ of a set $S \...
- 9,020
1
vote
0
answers
146
views
Difficulty understanding a step in the proof of multiset version of Cauchy-Davenport Theorem
In a paper "G. Kós, L. Rónyai, Alon’s Nullstellensatz for multisets, Combinatorica, 32(5) (2012) 589-605", the authors prove a multiset version of the Cauchy-Davenport Theorem (please see ...
- 167
0
votes
1
answer
73
views
Maximum number of vectors with bounds on inner products (follow up question)
This is a follow-up question from my previous question.
Suppose there are (2n+1) vectors $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$ in $R^{k+1}$. $m_i$ are weakly positive vectors. $p_i$ ...
- 23
3
votes
1
answer
168
views
Infinite constructions in additive combinatorics
A huge part of the investigation in the area of additive combinatorics asks for the answer of the following question: given an arithmetic pattern (for instance, $x+y=2z$, or $x+y=z+t$, or $x+y=z$), ...
- 1,463
4
votes
1
answer
237
views
Lower bounds for the density variant of the Hilbert cube problem
Given $\delta>0$ and positive integers $k$, write $h(\delta;k)$ for the smallest $N$ such that for any $S\subset [N]:=\{1,\dots,N\}$ of size $\ge \delta N$, there exists non-zero integers $n_0,d_1,\...
- 2,322
4
votes
0
answers
102
views
On Behrend's construction
Fix $\alpha>0$. Does there exist $\epsilon = \epsilon(\alpha)>0$ such that if $S\subset [N]:=\{1,\dots,N\}$ has $\ge \alpha N$ elements, then for any function $f:S\to [0,1]$, there exist some ...
- 2,322
1
vote
1
answer
159
views
Maximum number of vectors with bounds on inner products
Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy:
$$m_i \mu_j \leq 0, \quad \forall i\neq j $...
- 23
3
votes
0
answers
255
views
Approximate versions of Segre's Theorem
Consider projective $2$-space over a finite field of odd prime characteristic $p$. We say a set of points, $A$, in this space is an arc if any line meets it in at most two points. We say that an arc ...
- 11.5k
1
vote
1
answer
100
views
Cardinality of $\{ n_i + i^k: i \in \mathbb{N} \} \cap [1,T]$ where $\{n_i \}$ is all natural numbers in some order
Let $n_1, n_2, ...$ be a sequence of natural numbers such that $\{n_i: i \in \mathbb{N}\}$ as a set is all of natural numbers. Let $k$ be a positive integer. Is is possible to obtain a lower bound of ...
- 3,373
0
votes
0
answers
119
views
Difference set of difference set II (special Golomb rulers)
In
Difference set of difference set
I asked if a certain set is possible. And if O(n²) as the maximum integer-value in the set would be possible. User Emil Jeřábek (sorry dont know how to put a user-...
- 63
3
votes
0
answers
169
views
Behrend's construction vs. Triangle removal lemma
I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand.
Theorem 2.3.1 (Triangle removal lemma) For all $\...
- 246
4
votes
1
answer
323
views
Does Szemerédi's theorem hold for sets with positive upper Banach density?
We say that a set of natural numbers $A\subseteq \omega$ has positive upper density if $$\lim\sup_{n\to\infty}\frac{|A\cap n|}{n+1} > 0.$$
Szeméredi's theorem states that every $A\subseteq \omega$ ...
- 42.5k
11
votes
2
answers
640
views
$\mathbb Z/p\mathbb Z=A\cup(A-A)$?
$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$
Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, ...
- 22.2k
0
votes
0
answers
59
views
Bounds on these numbers
Let $[n]$ be the set of natural numbers $1,2,3 \cdots n$ and $k$ be a natural number. Define $S(n,k) = \# \{ A \subset [n] \mid \displaystyle\sum_{i \in A} i =k \}$. My question is; Are there any ...
- 281
3
votes
0
answers
152
views
Green-Tao's "Polylogarithmic bound for $r_4(N)$"
On P.23 of https://arxiv.org/pdf/1705.01703.pdf, they seemed to suggest that by the non-negativity of $\psi\big(\frac{k}{N}\big)$ for all $k$,
$$
K_N(\xi_0 n)\left[1-\cos\bigg(\frac{2\pi\xi_0 n}{p}\...
- 31
1
vote
0
answers
87
views
Reference request for a result in additive combinatorics
Let $p$ be a prime number and $[p-1]=\{1, 2, \ldots, p-1\}$.
The following proposition is proved: (but I cannot find out where)
Proposition: The non-empty subset sums of $[p-1]$ are equally ...
- 3,736
2
votes
0
answers
64
views
Bounds for Szemerédi’s theorem for GAP’s
Let a $(k,D)$-AP refer to sets of the form $\{n_0+l_1n_1+\dotsb +l_Dn_D: l_1,\dotsc,l_D \in [k]\}$ with cardinality $k^D$ (i.e. a proper $D$-dimensional GAP with width $k$).
Let $r(N,k,D)$ be the ...
- 2,322
4
votes
0
answers
52
views
Diameter of Cayley graphs whose generators intersect all large cosets
Let $G = G_n= \Bbb{F}_2^n$. We say $A\subset G$ is $t$-blocking, if it has non-empty intersection with all cosets $C\subset G$ with codimension at most $t$.
Given a group $G$ and set $A\subset G$, we ...
- 2,322
5
votes
2
answers
199
views
Progressions in sumset or complement
Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware ...
- 2,322
5
votes
0
answers
156
views
Is it true that the $\mathbb{F}_p$-rank of a linear combination of matrices is usually not smaller than its $\mathbb{Q}$-rank?
Consider fixed $3 \times 3$ integer matrices $A_1,A_2,A_3$ and the $\sim H^3$ linear combination matrices $A(\mathbf{h})=h_1A_1+h_2A_2+h_3A_3$ where $h_1,h_2,h_3$ are integers with $\vert h_i\vert \le ...
2
votes
2
answers
136
views
Additive basis of a set union the square of the set
Recall a set of integers $S$ is said to be an additive basis for the natural numbers if there is a $k$ such that every positive integer is expressible as a sum of at most $k$ elements of $S$. ...
- 4,919
13
votes
2
answers
749
views
Sylvester–Gallai theorem for small sets in a finite field
The well-known Sylvester–Gallai Theorem states that a set of $n>2$ points in $R^2$ not all on a line contains two points such that the line passing through these two points does not contain a third ...
- 11.5k
7
votes
2
answers
349
views
Sum of two $n$th powers in finite fields
Let $q$ be a prime power, let $n$ be a positive integer and let $\mathbb{F}_q$ be the finite field of cardinality $q$. I have some computational evidence that the set $$\{x^n+(-1)^nay^n:x,y\in\mathbb{...
- 782
2
votes
0
answers
54
views
Capset problem but considering differences with bounded support
For any dimension $D\ge 1$, we define the homomorphism $\phi: \Bbb{Z}^D\to (\Bbb{Z}/3\Bbb{Z})^D; \xi\mapsto \xi+3\Bbb{Z}^D$.
Given a set $A \subset \{0,1,2\}^D$, we define $S_A$ to be the set of $v \...
- 2,322
0
votes
0
answers
51
views
How large must "weak Besicovitch" subsets of groups be?
Consider a group $G$; let call $A\subset G$ a weak Besicovitch subset whenever every element of $G$ can be written under the form $gh^{-1}$, where $g,h\in A$.
General question: how large must a weak ...
- 13.9k
3
votes
0
answers
94
views
Arithmetic progressions and removal lemmas for graphs in arithmetic combinatorics
As it is well known, one can gets a proof of Roth's Theorem concerning arithmetic progressions of length 3 (APs for short) by using the celebrated Ruzsa-Szemerédi triangle removal lemma for graphs.
In ...
- 1,463
7
votes
0
answers
150
views
Circles with many points from an additive subgroup of $\mathbb{R}^2.$
Given a point set in the plane, defined by three distinct, non-zero vectors $v_1,v_2,v_3\in \mathbb{R}^2.$
$$L_n=\{a_1v_1+a_2v_2+a_3v_3 | a_1,a_2,a_3\in\{0,1,\ldots,n\}\}$$ What is the largest ...
