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
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 ...
Olivia L's user avatar
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{...
Subhayan's user avatar
  • 221
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 + \...
user avatar
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(...
VS.'s user avatar
  • 1,816
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\...
user avatar
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. ...
Yijun Yuan's user avatar
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 ...
Seva's user avatar
  • 22.8k
-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 ...
zeraoulia rafik's user avatar
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$, ...
Matt Groff's user avatar
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$?
Seva's user avatar
  • 22.8k
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 ...
Junsukim's user avatar
  • 141
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} \...
Chain Markov's user avatar
  • 2,618
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 ...
BerndM's user avatar
  • 101
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 $...
richarddedekind's user avatar
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 ...
Johan Aspegren's user avatar
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 ...
user avatar
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 \...
Bartosz Bartmanski's user avatar
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-...
wonderich's user avatar
  • 10.3k
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) = |...
Zach Hunter's user avatar
  • 3,393
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 ...
Chain Markov's user avatar
  • 2,618
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]$ ...
Chain Markov's user avatar
  • 2,618
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 ...
user3193861's user avatar
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 ...
Tristan Shin's user avatar
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. ...
Jie Wang's user avatar
  • 133
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. ...
combimateur's user avatar
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 ...
Johnny T.'s user avatar
  • 3,547
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 ...
VS.'s user avatar
  • 1,816
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 ...
Ryan Alweiss's user avatar
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 ...
Dan's user avatar
  • 111
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 $...
Luis Ferroni's user avatar
  • 1,879
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 ...
Hailong Dao's user avatar
  • 30.3k
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)}{...
Konstantinos Gaitanas's user avatar
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 ...
Hailong Dao's user avatar
  • 30.3k
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 ...
MCS's user avatar
  • 1,256
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 ...
wlad's user avatar
  • 4,823
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 ...
Seva's user avatar
  • 22.8k
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....
Ken Berner's user avatar
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$...
boink's user avatar
  • 213
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 $...
Joseph Vandehey's user avatar
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 \}|$) ...
Daira-Emma Hopwood's user avatar
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$ ...
Henri Cohen's user avatar
  • 11.5k
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 ...
Lviv Scottish Book's user avatar
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$ ...
fil's user avatar
  • 51
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$.
Pascal Ochem's user avatar
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 ...
Taras Banakh's user avatar
  • 40.8k
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{...
Pietro Majer's user avatar
  • 56.5k
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 ...
Jakub Konieczny's user avatar
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 ...
Joachim Worthington's user avatar
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)...
Chain Markov's user avatar
  • 2,618
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$ ...
Ruhollah Majdoddin's user avatar

1
3 4
5
6 7
14