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
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, $...
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$ ...
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{...
7
votes
2
answers
2k
views
Recent results on the Gauss circle problem?
Possible Duplicate:
What is the status of the Gauss Circle Problem?
The Gauss circle problem is the following: Let $N(r)$ denote the number of solutions in integer pairs $(i,j)$ to the inequality ...
7
votes
1
answer
481
views
Subgroups of the multiplicative group of a finite field satisfying a certain additive property
Let $G \subseteq \mathbb F_p^*$ be a subgroup. Then $G$ is called almost trivial if $G \cap (2-G)$ consists of the element 1.
Then I am wondering how big $G$ can be in terms of $p$. If $G$ is a random ...
7
votes
2
answers
452
views
The soccer splitting problem in arbitrary commutative ring
There's a folklore problem:
Let $x_1, \cdots, x_{23} \in \mathbb{Z}$ be the weights of $23$ soccer players. Now Master Yoda want's to form two soccer teams with $11$ players each. Turns out for ...
7
votes
1
answer
721
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
7
votes
1
answer
495
views
A permutation problem
Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
7
votes
2
answers
587
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 ...
7
votes
3
answers
493
views
Product-one sets in non-commutative groups
A nonempty subset $D$ of a group $G$ is called
$\bullet$ decomposable if $D\subseteq DD$, that is every element $x\in D$ is can be written as the product $x=yz$ of some elements $y,z\in D$;
$\bullet$ ...
7
votes
2
answers
613
views
Elementary Proof of Basis of Order k
Context
According to the FAQ, questions of the form "the sorts of questions you come across when you're writing or reading articles or graduate level books" are acceptable. This falls into the "...
7
votes
1
answer
829
views
Minimum cardinality of a difference set in $R^n$
Cross-posted from https://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn.
Given a finite set $S$ of $m$ points in $\mathbb R^n$ that do not all lie in the ...
7
votes
1
answer
192
views
Trisecting $3$-fold sumsets, II: is the middle part ever thin?
This is a refined version of the question I asked yesterday.
Let $A$ be a finite set of integers with the smallest element $0$ and the largest element $l$. The sumset $C:=3A$ resides in the interval $[...
7
votes
1
answer
263
views
$p-1$ elements in $\mathbb{Z}_p\times\mathbb{Z}_p$ with a sum $(0,0)$
Given prime $p\ge 11$, $S$ is a subset of $\mathbb{Z}_p\times\mathbb{Z}_p$ with $3p-3$ elements. Prove: $S$ has a subset $T$ with $p-1$ elements, such that$\sum_{x\in T}x\equiv (0,0)\pmod{p}$.
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} \...
7
votes
2
answers
251
views
What methods do we have to understand the spectrum of matrices with restricted entries?
Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $...
7
votes
1
answer
610
views
A variation of Minkowski sum
I have to work with the following variation of Minkowski sum:
Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$.
Set
$$K^+=\{\\,x+y\in\mathbb E\mid(x,...
7
votes
1
answer
561
views
Upper bound for size of subsets of a finite group that contains a sum-full set
Problem
I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:
Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we
define $k(G)$ be ...
7
votes
1
answer
303
views
Does any subset of a finitely generated group with positive upper density contain three points in arithmetic progression?
Let $G$ be a countable finitely generated group, with word metric $d_S$ induced by some generating set $S$. Let $B_r$ be the ball of radius $r$ around the identity under $d_S$.
We say that $A \subset ...
7
votes
1
answer
316
views
Large gaps in Singer's difference sets
This question is related to the question I asked earlier.
For a natural number $n$, a set $D$ of integer numbers is called a $n$-cyclic difference set if each integer number $x\notin n\mathbb Z$ can ...
7
votes
3
answers
661
views
Polynomial expressions of roots of unity with integer norm
Say a nonconstant polynomial $p(z)$ is $k$-magical if it satisfies the following properties:
$p$ is of the form $$p(z) = a_{k-1} z^{k-1} + a_{k-2} z^{k-2} + \cdots + a_1 z + 1$$ where each $a_i \in \{...
7
votes
1
answer
250
views
Analogue to Szemerédi's theorem for non-monotone sequences
Szemerédi's theorem states that a strictly increasing sequence of positive integers $a_0, a_1, \ldots$ whose range has positive density contains arbitrarily long arithmetic progressions (as ...
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 $...
7
votes
1
answer
1k
views
Additive combinatorics and large Fourier coefficients
Elon Lindenstrauss explains in his talk at the MSRI in Fall 2008 (the relevant comment is at minute 41 of the video) that the set of large Fourier coefficients of a probability measure $\mu$ on the ...
7
votes
1
answer
192
views
Sets of residues with only a single intersection under translation
A combinatorial game I am studying has given rise to the following question. Consider the group $\Bbb Z/n\Bbb Z$. What is the largest $m$ such that there exist $k$ sets of $m$ residues such that the ...
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 ...
7
votes
0
answers
189
views
Primitive recursive bounds for the the Gallai-Witt theorem
Let me first recall some facts:
By the work of Gowers, the Van der Waerden numbers belong to class $\mathcal{E}^3$ of the Grzegorczyk hierarchy
By the work of Shelah, the Hales-Jewett numbers belong ...
7
votes
0
answers
116
views
A conjecture on circular permutations of n elements in an abelian group of odd order
In 2013 I formulated the following conjecture in additive combinatorics.
Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...
7
votes
0
answers
261
views
Is every integer $n>1$ the sum of two squares and two central binomial coefficients?
Those integers $\binom{2n}n\ (n=0,1,2,\ldots)$ are called central binomial coefficients. By Stirling's formula,
$$\binom{2n}n\sim \frac{4^n}{\sqrt{n\pi}}\ \ \ \ (n\to+\infty).$$
Of course, the ...
7
votes
0
answers
239
views
Distribution of trivial subset sums
Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
7
votes
0
answers
311
views
Other applications of the 'increment' approach
I would like to hear about other instances of the so-called 'increments' approach, first used by Roth to prove that a subset of $\mathbb{N}$ of positive upper density contained infinitely many ...
7
votes
0
answers
719
views
Largest set of integers without 3-term arithmetic progressions mod $n$
I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b \...
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-...
6
votes
2
answers
993
views
Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density
It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...
6
votes
2
answers
319
views
Determining when combinatorial sums are zero
To keep things simple with a specific example, we ask:
Prove that $\displaystyle\ a_n:=\frac{1}{n!}\sum_{k=0}^n \binom{n}{k} \frac{1}{k!} (-1)^{n-k}$ is zero if and only if $n=1$. (Or find a counter-...
6
votes
2
answers
465
views
The density of numbers of the form $p + 2^k$
In 1934, Romanoff proved that the following set has positive lower density:
$$\displaystyle \mathcal{R}(x)= \{n \in \mathbb{N} : n \leq x, n = p + 2^k \}$$
where $p$ is a prime and $k \geq 0$ is a non-...
6
votes
3
answers
734
views
A simple looking problem in partitions that became increasingly complex
I began with problem which looked simple in the beginning but became increasingly complex as I dug deeper.
Main questions: Find the number of solutions $s(n)$ of the equation
$$
n = \frac{k_1}{1} + \...
6
votes
1
answer
383
views
Normal polytopes - counterexample?
An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points.
I am looking for an example $P$...
6
votes
1
answer
418
views
Complete residue system modulo n (permutation of numbers 0 to n-1) such that
I have a task:
Find all $n\ \epsilon \ N, \ n > 1$ for which a permutation $a_1,\ a_2,\ ...,\ an\ $ of numbers $ 0,1, ..., n - 1$ exists such that $a_1,\ a_1+a_2,\ ...,\ a_1+a_2+\ ...\ +an\ $ form ...
6
votes
1
answer
899
views
Relationship between Erdos and Falconer distance problems
Given a set $E \subset \mathbb{R}^d$, define the distance set of $E$
$$
\Delta(E) = \lbrace|x-y| : x,y \in E \rbrace,
$$
where $|\cdot |$ is the usual Euclidean distance.
$\bullet$ The Erdos-...
6
votes
2
answers
365
views
Known additive bases with irregular counting function
For $A \subset \mathbb{N}$ and positive integer $h > 0$, define $r_{A,h}(n)$ to be the number of ways to write $n$ as the sum of $h$ (not necessarily distinct) elements of $A$. We say $A$ is an ...
6
votes
2
answers
873
views
Gromov's pseudogroups and Tao's approximate groups
In his article
Gromov, M. Almost flat manifolds. J. Differential Geom. 13 (1978), no. 2, 231–241
Gromov exploited a notion of a pseudogroup. In his book
Tao, Terence. Hilbert's fifth problem and ...
6
votes
5
answers
927
views
What makes a set random?
There are many results in number theory, where the existence
of some $B \subseteq \mathbb{N}$ with certain properties is proved by
a probabilistic argument employing "random sets". One such ...
6
votes
2
answers
1k
views
Acyclic matching property in $\mathbb{Z}/p\mathbb{Z}$
Let $B$ be a finite subset of the group $G$ which does not contain the neutral element. For any subset $A$ in $G$ with the same cardinality as $B$, a matching from $A$ to $B$ is defined to be a ...
6
votes
1
answer
1k
views
Is there any relationship between Szemerédi's theorem and Sunflower conjecture?
I have observed some similar things between a reformulation of the Sunflower conjecture (see also conjecture 1.3 in Improved bounds for the sunflower lemma) and Szemerédi's theorem such that for ...
6
votes
1
answer
494
views
How are the fields of dynamical systems, stochastic processes and additive combinatorics, inter-related?
Currently I’m interested in a couple of fields, namely dynamical systems, stochastic processes, and additive combinatorics. I was wondering if it’s feasible to keep pursuing all 3, and whether I can ...
6
votes
1
answer
466
views
Ref. request: Additive probability measure on $\mathcal P({\bf N})$ supplies subset of $\mathbf R$ without Baire property
ZFC proves, among the other things, the existence of a (finitely) additive probability measure $\theta: \mathcal P(\mathbf N) \to \mathbf R$ on the power set of $\mathbf N$ such that $\theta(X) = 0$ ...
6
votes
3
answers
640
views
Conditions for an analogue of Cauchy-Davenport for simple groups
What conditions would be sufficient for a generalization of Cauchy-Davenport for simple groups? I can see two possible difficulties with a generalization for general groups:
The sets could both be ...
6
votes
1
answer
808
views
Additive Combinatorics - reference request
Let $A$ be a finite set of integers with $|A \hat{+} A| \leq K|A|$, where the $\hat{+}$ denotes restricted sumset: the set of all $a_1 + a_2$ with $a_1, a_2 \in A$ and $a_1 \neq a_2$.
Claim: $|A + A|...
6
votes
3
answers
555
views
Any rigorous way to claim that sums with repeat summands are few?
Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...