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
0answers
14 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 ...
-1
votes
0answers
68 views

A number related to rank

Given $n$ a natural number we know minimum $m$ over all choices of $v_i=\begin{bmatrix}a_{i1}\\\vdots\\a_{in}\end{bmatrix}\in\mathbb R^n$ such that $$I=\sum_{i=1}^mv_iv_i'$$ holds where $'$ is ...
2
votes
0answers
59 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
1answer
164 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
0answers
62 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
1answer
96 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\...
1
vote
0answers
91 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. ...
3
votes
1answer
159 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
1answer
143 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
1answer
158 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
1answer
245 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
3answers
509 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
1answer
173 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
1answer
95 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
1answer
111 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 $...
3
votes
1answer
277 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 $Cn\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
0answers
68 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 ...
1
vote
1answer
82 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 \...
5
votes
4answers
395 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
0answers
75 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
0answers
119 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
1answer
70 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
1answer
75 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 ...
7
votes
0answers
216 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
0answers
176 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. ...
3
votes
1answer
102 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. ...
9
votes
1answer
206 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
0answers
181 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
2answers
209 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
1answer
130 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 ...
6
votes
1answer
277 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
1answer
271 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
1answer
69 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)}{...
15
votes
3answers
534 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
0answers
87 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
1answer
107 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
0answers
131 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 ...
3
votes
1answer
172 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
0answers
62 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
1answer
138 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
0answers
107 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 \}|$) ...
5
votes
2answers
286 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$ ...
0
votes
0answers
57 views

On bounds for $|A+\operatorname{rad}(A)|$, where $A$ is a finite set of positive integers

In this post we denote the product of the distinct prime numbers dividing an integer as $m>1$ $$\operatorname{rad}(m)=\prod_{\substack{p\mid m\\p\text{ prime}}}p,$$ with the definition (it is a ...
1
vote
1answer
264 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
0answers
91 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$ ...
9
votes
2answers
599 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
0answers
124 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 ...
10
votes
0answers
129 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{...
5
votes
0answers
94 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 ...
7
votes
0answers
119 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 ...

1
2 3 4 5
10