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.
664
questions
1
vote
1
answer
394
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 ...
1
vote
1
answer
90
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\...
2
votes
0
answers
86
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 $\...
3
votes
0
answers
157
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 ...
2
votes
1
answer
381
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]...
7
votes
2
answers
589
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 ...
4
votes
0
answers
129
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 ...
3
votes
1
answer
178
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 \...
1
vote
0
answers
152
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 ...
0
votes
1
answer
88
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$ ...
2
votes
1
answer
206
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$), ...
4
votes
1
answer
257
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,\...
3
votes
0
answers
152
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 ...
1
vote
1
answer
191
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 $...
3
votes
0
answers
274
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 ...
1
vote
1
answer
115
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
votes
0
answers
235
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 $\...
4
votes
1
answer
339
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$ ...
11
votes
2
answers
656
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$, ...
0
votes
0
answers
67
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 ...
3
votes
0
answers
162
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}\...
1
vote
0
answers
98
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 ...
1
vote
0
answers
75
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 ...
4
votes
0
answers
65
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 ...
5
votes
2
answers
240
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 ...
5
votes
0
answers
189
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
178
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$. ...
14
votes
2
answers
828
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 ...
7
votes
2
answers
391
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{...
2
votes
1
answer
108
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 \...
0
votes
0
answers
58
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 ...
3
votes
0
answers
112
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 ...
7
votes
0
answers
154
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 ...
1
vote
2
answers
200
views
Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs
This might be related to counting hamiltonian cycles.
@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is
not directly applicable to this question.
Given ...
1
vote
0
answers
138
views
Counting Hamiltonian cycles in graph and finding a coefficient of polynomial
Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[...
4
votes
0
answers
149
views
Large subsets of groups with no solution to linear equations
Is there a (sequence of finite nonabelian) group(s) $G$ and a (sequence of corresponding) subset(s) $S \subseteq G$, $|S| = |G|^{1-o(1)}$, such that there is no solution to $xy^{-1}z = zy^{-1}x$ with ...
2
votes
0
answers
137
views
Chromatic numbers of Cayley graphs induced by Hamming balls
The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': ...
2
votes
1
answer
172
views
Only trivial solution to a pair of constrained linear diophantine equations
Given positive integer $n$, we are looking for a set
of $n$ positive integers $a_i$.
The following linear integer program must have only
the trivial integer solution of all ones.
$0 \le x_i \le \frac{...
4
votes
0
answers
101
views
Visiting zero-sum triples in a vector space
Is it true that for any set $A\subset\mathbb F_5^n$ satisfying $A\cap(-A)=\varnothing$, there is a subset $A'\subseteq A$ such any triple $(a,b,c)\in A\times A\times A$ with $a+b+c=0$ has exactly one ...
9
votes
0
answers
263
views
If $A+A+A$ contains the extremes, does it contain the middle?
Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers).
Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
2
votes
1
answer
115
views
On the maximum elements of a numerical semigroup that have order between $n$ and $2n$
Let $S$ be a submonoid of the non-negative integers $\mathbb Z_{\geq 0}.$ If $\mathbb Z_{\geq 0} \setminus S$ is finite, we say that $S$ is a numerical semigroup. Let $S^*$ denote the collection of ...
15
votes
1
answer
972
views
Sets with both additive and multiplicative gaps
I feel that the following problem should have a clean and simple solution, but so far I couldn't find one.
Suppose that $p$ is a prime, and that $A\subseteq\mathbb Z/p\mathbb Z$ is a set such that
...
2
votes
1
answer
93
views
What are the n-ary subsemigroups of $\mathbb{N}$?
There is a well-known result about the subsemigroups of $\mathbb{N}$ stating that the additive subsemigroup generated by a (finite) set $A$ of $\mathbb{N}$ is cofinite in $\mathbb{N}$ if and only if $\...
5
votes
0
answers
77
views
Maximum size of difference sets with a bounded number of prime divisors
Call a subset $S\subset \mathbb{Z}$ $r$-smooth if the difference set $S-S$ contains numbers whose prime divisors lie in a set $P$ of distinct primes with $|P|=r$. Let $f(r)$ be the maximum size of any ...
7
votes
2
answers
790
views
Distance among integer set
Given an integer set, if the distances between integers in the set are still in the set, what mathematical term should be used to describe that nature? Or what nature does the set have?
For example, $...
1
vote
1
answer
162
views
A sum-product estimate in Z/pZ
There is an exercise in a paper by George Shakan
George Shakan, Discrete Fourier Transform
say that
Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
4
votes
2
answers
229
views
Existence of m infinite subsets in an arbitrary group such that all products of one element from each (in order) are distinct
Is it true that for every infinite group $G$ and every $m\in\mathbb{N}$ there are infinite subsets $A_0,\dots,A_{m-1}$ such that all the products $a_0\cdot\dots\cdot a_{m-1}$ with $a_i\in A_i$ are ...
3
votes
2
answers
162
views
On the Hilbert function of a numerical semigroup
Recall that a numerical semigroup $S$ is a submonoid of the non-negative integers $\mathbb Z_{\geq 0}$ whose relative complement $\mathbb Z_{\geq 0} \setminus S$ is finite. Observe that the collection ...
3
votes
0
answers
188
views
Density Hales-Jewett for product sets
Let $k\geq 3$ and $A\subseteq[k]^n$ be a subset of density $\delta=|A|/k^n$. The density Hales-Jewett theorem states that if $\delta\geq1/\alpha(n)$, then $A$ must contain a combinatorial line, where $...
9
votes
1
answer
628
views
Number of Laurent monomials of n variables with degree at most d
Introduction: We have a question of how to calculate the number of $n$-variables Laurent monomials of degree at most $d$.
For example: If $n=2$, $d=2$ then we have 19 monomials, which are:
$x^{-2}$, $...