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
3
votes
0
answers
62
views
Almost quadratic difference sets
Does there exist a characterization of sets $S$ such that $|S-S|$ is "almost quadratic" in $|S|$? For instance, what are some examples of sets such that $|S-S|$ is on the order of $\frac{{|S|}^2}{\log ...
2
votes
0
answers
161
views
On norms of Boolean functions
Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$.
Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{...
6
votes
1
answer
361
views
Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$
Fix $k \in \mathbb{N}$, $k \ge 2.$
Does there exist a subset $A \subset \mathbb{F}_2^n$ such that $|A| \ge c 2^{n/k}$ with some absolutely positive constant $c,$ and satisfying
$$ a_1 + a_2 + \...
2
votes
0
answers
101
views
Sumset of $k$-smooth numbers
Take the set $T(k,n)=M_1(k,n)$ of all $k$ smooth numbers less than $n$.
What is the cardinality of $$\{1,\dots,n\}\cap M_2(k,n)$$ where every integer in $M_2(k,n)$ is the sum of two integers in $M_1(...
5
votes
1
answer
172
views
Computational version of inverse sumset question
Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\...
2
votes
1
answer
185
views
Bell polynomial with variables 1 and 0
Let $B_{n,k}(x_1,\cdots,x_{n-k+1})$ be the Bell polynomial.
If $x_1=\cdots=x_{n-k+1}=1$, we know that $B_{n,k}(x_1,\cdots,x_{n-k+1})=S(n,k)$, where $S(n,k)$ is the Stirling number of second kind.
...
4
votes
1
answer
256
views
Unique representation and sumsets
Let $A$ be a finite, nonempty subset of an abelian group, and let $2A:=\{a+b\colon a,b\in A\}$ and $A-A:=\{a-b\colon a,b\in A\}$ denote the sumset and the difference set of $A$, respectively.
If ...
-2
votes
1
answer
337
views
What are the consequence of Snevily's conjecture to analytic number theory if really there is a connection between them? [closed]
Snevily's conjecture it is an open conjecture in Group theory for non cyclic Group and it were proved for abelian groups of prime order using a fairly standard application of the Alon-Tarsi ...
1
vote
1
answer
206
views
Average size of iterated sumset modulo $p-1$,
Given a prime $p$, what is the average size of the iterated sumset, $|kA|$, modulo $p-1$, with $p$ a prime, and $k$ given, with $A$ chosen at random?
You can pick any type of prime you like for $p$, ...
1
vote
1
answer
299
views
Does $g+A\subseteq A+A$ imply $g\in A$?
Suppose that $A$ is a subset of a (large) finite cyclic group such that $|A|=5$ and $|A+A|=12$. Given that $g$ is a group element with $g+A\subseteq A+A$, can one conclude that $g\in A$?
9
votes
3
answers
624
views
Does the expression $x^4 +y^4$ take on all values in $\mathbb{Z}/p\mathbb{Z}$?
As the title asks: does there exist $N$ such that, for any prime $p$ larger than $N$, the expression $x^4 +y^4$ takes on all values in $\mathbb{Z}/p\mathbb{Z}$?
I have been thinking about this ...
7
votes
1
answer
193
views
Finite concatenation-free languages
Suppose, $A$ is a finite alphabet. $L \subset A^*$ is a language. Let's call $L$ concatenation-free iff $\forall u, v \in L$ we have $uv \notin L$.
Does there exist some function $c: \mathbb{N} \...
2
votes
1
answer
155
views
Well-spread (weak Sidon) sets
Does anybody have access to the paper
A. Kotzig: On well spread sets of integers, 1972,
or does anybody know the proof of $\sigma^*(n)\geq 4+\binom{n-1}2$ for $n\geq7$
(as cited in Marr,Wallis: Magic ...
3
votes
1
answer
253
views
Asymptotic number of $3$-AP's in a set $A\subseteq\mathbb{F}_{p}^{n}$ of density $\epsilon$
Problem: Let $p$ be an odd prime number and consider the $n$-dimensional vector space over the field with $p$ elements. I want to prove that the number of $3$-term arithmetic progressions in a subset
$...
4
votes
1
answer
545
views
Why should it be hard to generalize Dvir's proof of the finite field Kakeya conjecture to the Euclidean case?
Let $q$ be prime and let
$q\delta \sim 1.$ Let $K$ be any set of $C_n\delta$-separated tubes in $B(0,2)$, where $C_n$ is some constant depending on $n$. Let us consider a grid of $q^n$ points scaled ...
2
votes
0
answers
70
views
Does there exist a subset $E \in \mathbb{Z}_{p^2}^4$ such that $\Pi(E) \neq \mathbb{Z}_p$?
Denote $\mathbb{Z}_{p^2}$ be the ring residues modulo $p^2,$ i.e
$$ \mathbb{Z}_{p^2} = \left\{ 0,1,2,\dots, p^2-1\right\}.$$
$$\mathbb{Z}_{p^2}^{d} = \underbrace{\mathbb{Z}_{p^2} \times \dots \times ...
2
votes
1
answer
109
views
Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$
Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...
6
votes
4
answers
600
views
Request for an exact formula related to a partition in number theory
The Frobenius equation is the Diophantine equation $$
a_1 x_1+\dots+a_n x_n=b,$$
where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$
must consist of non-...
1
vote
0
answers
80
views
Packing almost-subgroups into a group
We consider a group finite $G$. We say a set $A\subset G$ injects a set $B$ if $|A+B| = |A||B|$, and let $I(B) = \max \{|A| :A\text{ injects } B\}$.
For a subgroup $H$, it is well-known that $I(H) = |...
1
vote
0
answers
226
views
Sidon sets in finite groups
Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...
1
vote
1
answer
76
views
What is the minimal possible size of a subset of this semigroup satisfying the following conditions?
Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:
$\forall a \in P[A]$ ...
0
votes
1
answer
235
views
Set of numbers with unique results from sums [closed]
I need to create a set of numbers where any amount of them can be added together and each result will always give a unique answer, so we always know that the result was created from adding exactly ...
16
votes
1
answer
743
views
Corners theorem in finite fields
The corners theorem of Ajtai and Szemerédi states that if $A\subseteq[N]^2$ is corner-free, i.e. there are no $x,y,h\in\mathbb{N}$ with all of $(x,y),(x+h,y),(x,y+h)$ in $A$, then $|A|=o(N^2)$. The ...
4
votes
0
answers
193
views
A conjecture on the cardinality of minimal mediated sequences
For a sequence of integer numbers $A=\{0,q_1,\ldots,q_m,p\}$ (arranged from small to large), if every $q_i$ is an average of two distinct numbers in $A$, then we say $A$ is a mediated sequence.
...
4
votes
1
answer
208
views
weak piecewise syndetic property for positive upper banach density set
I wonder if a set of integers $A$ given by an increasing sequence of integers $A=(a_k)_k$ with positive upper density
$\limsup_n\frac{\sharp A\cap [0,n]}{n}>0$ satisfies the following property.
...
10
votes
1
answer
492
views
Sidon sets of $\mathbb{Z}/p\mathbb{Z}$
A set $S \subseteq \mathbb{Z}/p\mathbb{Z}$ is called a Sidon set if given $a, b, c, d \in S$ and $a+ b = c+ d$, then $\{a, b\} = \{c,d\}$. I was interested in knowing about the largest possible Sidon ...
0
votes
0
answers
188
views
A gap problem in elementary additive combinatorics
Given $a,b\in\mathbb N$ define the set $$\chi(a,b)=\{M\in\{0,1\}^{n^a\times n^b}:\mbox{ every row of }M\mbox{ is distinct}\}.$$
Also given ${\bf{x}}=(x_1,\dots,x_{n^b})\in\mathbb Z^{n^b}$ define the ...
5
votes
2
answers
349
views
Nontrivial expansion in sumsets
Let $A \subset \mathbb{Z}/p$, let $f$ be a function on $\mathbb{Z}/p$ and let $B:=\{f(a): a \in A\}$.
Can we conclude that $|A+B|$ is large if $f$ is a sufficiently "nice" function? For instance say ...
1
vote
1
answer
158
views
Results on additive structure of polynomial rings?
Cross-posted from Math.SE.
I've been wondering recently about results for irreducibility that use the "additive structure" of the polynomial ring at hand. For instance, can we say anything about the ...
7
votes
1
answer
296
views
Sum of two $n$-th powers, of two $m$-th powers, but not of two $mn$-th powers
Let $m$ and $n$ be two coprime numbers. Let $S_n$ denote the set of integers that are a sum of two $n$-th powers of integers, for example $7\in S_3$ given $7=2^3+(-1)^3$. Analogously define $S_m$ and $...
10
votes
1
answer
283
views
Freiman inequality for projective space?
This question is suggested by some results in a paper I am writing. I would like to write it down there but want to make sure that it is not known or at least MO-hard.
Freiman's inequality states ...
2
votes
1
answer
80
views
Chain of sequences, such that $a_{k+1}(n)$ completes $a_k(n)$
We say that the sequence $a_{k+1}(n)$ is a complete sequence of $a_k(n)$ if:
(1) Every term of $a_k(n)$ can be written as a sum of distinct terms of $a_{k+1}(n)$.
(2) $\lim_{n\to\infty} \frac{a_k(n)}{...
19
votes
4
answers
856
views
Size of sets with complete double
Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
1
vote
0
answers
93
views
Is every positive-density set of positive integers almost rational?
(All the sets in this discussion are sets of positive integers.) I say a set $V$ is “rational” if it satisfies one of the following conditions:
I. $V$ is finite (possibly empty);
II. $V$ can be ...
5
votes
1
answer
118
views
Maximum size of a critical set that sums to $n$
Say that a set $S \subset \mathbb Z^+$ can express $n$ if there is some way to add elements of $S$ (possibly more than once) to equal $n$. Call $S$ critical if moreover no proper subset of $S$ can ...
6
votes
0
answers
145
views
When is $\{s_2-s_1,s_3-s_2,s_1-s_3\}\cap S$ non-empty for any $s_1,s_2,s_3\in S$?
A subset $S$ of an abelian group is a subgroup if and only if it is closed under taking differences; that is, the difference of any two elements of $S$ is in $S$. Suppose, however, that we only know ...
5
votes
1
answer
352
views
Sum-product estimate in finite fields
There is a paper by Bourgain, Katz and Tao
Bourgain, Jean; Katz, N.; Tao, Terence C., A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14, No. 1, 27-57 (2004). ZBL1145....
0
votes
0
answers
71
views
Number of nontrivial solutions to equations of given genus (Ruzsa)
I am working on Ruzsa's paper "Solving a linear equation in a set of integers I," which is here: http://matwbn.icm.edu.pl/ksiazki/aa/aa65/aa6537.pdf.
Consider a linear equation $a_1x_1+\dots+a_kx_k=0$...
5
votes
1
answer
160
views
Eccentricity in the number of representations for sets too large to be Sidon sets
Let $A=\{a_1<a_2<a_3<\dots< a_k\}\subset\{1,2,\dots,N\}$ be a set of integers. Let $r_A(n)=\#\{(a_i,a_j):a_i+a_j=n\}$ be the number of representations of $n$ as a sum of two elements from $...
3
votes
0
answers
140
views
Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?
Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$.
Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
7
votes
2
answers
361
views
$|(A+B)(X)|=o(X)$ if $|A(X)|=O(X^{1/2})$ and $|B(X)|=O(X^{1/2})$?
Sorry if this is trivial: it is well-known that the number of sums of two
squares less than $X$ is asymptotic to $CX/\log(X)^{1/2}$ for some $C$.
Is this a general phenomenon ? More precisely, if $A$ ...
2
votes
1
answer
310
views
Representing natural numbers as sums of powers of distinct numbers
Find the smallest number $n$ such that almost all natural numbers can be represented as the sum $$a_1^{a_{p(1)}}+a_2^{a_{p(2)}}+\dots+a_n^{a_{p(n)}}$$where $a_1,\dots,a_n$ are pairwise distinct ...
5
votes
0
answers
114
views
Low-rank approximation over finite fields
Consider the finite field $\mathbb{F}_p$ with prime $p$. Let $I=\{ 0,1,2,...,|I|-1 \}\subset \mathbb{F}_p$ be an "interval".
What can be the largest size $|I|$, such that there exists a $2\times 2$ ...
10
votes
2
answers
669
views
Sets A such that A+A contains the largest set [0,1,..,t]
I look for a reference for the following problem.
Given an integer $k$, find a set $A\subset\mathbb{N}$ with $|A|=k$
that maximizes $t$ such that $\left[0,1,..,t\right]\subset A+A$.
3
votes
0
answers
135
views
A question on a result of Imre Ruzsa concerning sum-sets
Th main result of this preprint of Imre Ruzsa implies the following
Corollary (Ruzsa): For every $r\in\mathbb N$ there exists a real number $\alpha<1$ and a positive integer $m$ such that for ...
11
votes
0
answers
159
views
Bijections $\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ with vanishing local means
This is just a summer-time curiosity arisen after a recent question by Dominic van der Zypen.
For a finite subset $S$ of $\mathbb{Z}\times\mathbb{Z}$ and a function $f$ on $\mathbb{Z}\times\mathbb{...
12
votes
0
answers
193
views
What is the "right" notion of exponentiation in $\beta \mathbb N$?
The Stone–Čech compactification $\beta \mathbb N$ of the positive integers has extensive applications in combinatorial number theory.
A feature of $\beta \mathbb N$ that makes these applications ...
8
votes
0
answers
140
views
Minimum length of sequence such that every integer from 1 to n can be achieved as the sum of some contiguous subsequence
This question literally came to me in a fever dream last night, and it's frustrating me to no end. I'll try to explain it as best I can, but there may not be a satisfying answer; the best outcome ...
3
votes
0
answers
133
views
Is there some sort of formula for $t(S_n)$?
Let $G$ be a finite group. Define $t(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > t(G)$ and $\langle X \rangle = G$, then $XXX = G$.
Is there some sort of formula for $t(S_n)...
2
votes
1
answer
159
views
How many tuples in $\{0,\ldots, k\}^{\log n}$ that sum of its elements is $n$?
For integers $n \ge 0$ and $k \ge 2$, define $E^k_n$ as the set of tuples $b \in \{0,\ldots, k\}^{\log n}$, such that
$n = \sum_{0 \le i \le \log n} b_i 2 ^i.$
Note that the only element of $E^1_n$ ...