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.

Filter by
Sorted by
Tagged with
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 ...
Marcos's user avatar
  • 577
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\...
Marcos's user avatar
  • 577
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 $\...
Zach Hunter's user avatar
  • 3,393
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 ...
Nilotpal Kanti Sinha's user avatar
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]...
Marcel K. Goh's user avatar
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 ...
Puzzled's user avatar
  • 8,842
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 ...
Zach Hunter's user avatar
  • 3,393
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 \...
Salvo Tringali's user avatar
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 ...
Rajkumar's user avatar
  • 167
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$ ...
TanG's user avatar
  • 23
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$), ...
Johnny Cage's user avatar
  • 1,543
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,\...
Zach Hunter's user avatar
  • 3,393
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 ...
Zach Hunter's user avatar
  • 3,393
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 $...
TanG's user avatar
  • 23
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 ...
Mark Lewko's user avatar
  • 11.7k
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 ...
Johnny T.'s user avatar
  • 3,547
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 $\...
RFZ's user avatar
  • 298
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$ ...
Dominic van der Zypen's user avatar
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$, ...
Seva's user avatar
  • 22.8k
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 ...
mukhujje's user avatar
  • 281
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}\...
Jonathan Lam's user avatar
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 ...
Konstantinos Gaitanas's user avatar
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 ...
Zach Hunter's user avatar
  • 3,393
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 ...
Zach Hunter's user avatar
  • 3,393
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 ...
Zach Hunter's user avatar
  • 3,393
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 ...
Christian Bernert's user avatar
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$. ...
JoshuaZ's user avatar
  • 6,090
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 ...
Mark Lewko's user avatar
  • 11.7k
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{...
Pablo Spiga's user avatar
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 \...
Zach Hunter's user avatar
  • 3,393
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 ...
Benoît Kloeckner's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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 ...
Jozsef Solymosi's user avatar
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 ...
joro's user avatar
  • 24.2k
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}[...
joro's user avatar
  • 24.2k
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 ...
Lior Gishboliner's user avatar
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': ...
John Griesmer's user avatar
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{...
joro's user avatar
  • 24.2k
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 ...
Seva's user avatar
  • 22.8k
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,\, \...
Alufat's user avatar
  • 805
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 ...
Dylan C. Beck's user avatar
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 ...
Seva's user avatar
  • 22.8k
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 $\...
AMLimbach's user avatar
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 ...
Ivan Meir's user avatar
  • 4,782
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, $...
hui cj's user avatar
  • 79
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}$. ...
Sei's user avatar
  • 11
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 ...
e1c25ec7's user avatar
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 ...
Dylan C. Beck's user avatar
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 $...
Wei Zhan's user avatar
  • 203
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}$, $...
Thien's user avatar
  • 93

1
2
3 4 5
14