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
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
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
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
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 ...
Stanley Yao Xiao's user avatar
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 ...
Maarten Derickx's user avatar
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 ...
katana_0's user avatar
  • 353
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 ...
Mahdi Khosravi's user avatar
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,\...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Puzzled's user avatar
  • 8,842
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$ ...
Taras Banakh's user avatar
  • 40.8k
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 "...
user26147's user avatar
  • 133
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 ...
Keenan Pepper's user avatar
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 $[...
Seva's user avatar
  • 22.8k
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}$.
Andyqian7's user avatar
  • 165
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
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 $...
user6818's user avatar
  • 1,883
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,...
Anton Petrunin's user avatar
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 ...
Hsien-Chih Chang 張顯之's user avatar
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 ...
Nate River's user avatar
  • 4,822
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 ...
Taras Banakh's user avatar
  • 40.8k
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 \{...
user avatar
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 ...
Marcel K. Goh's user avatar
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
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 ...
Andreas Thom's user avatar
  • 25.3k
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 ...
BPP's user avatar
  • 665
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
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 ...
Mohammad Golshani's user avatar
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Igor Rivin's user avatar
  • 95.5k
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 ...
Stanley Yao Xiao's user avatar
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 \...
Yuichiro Fujiwara'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
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 ...
Stanley Yao Xiao's user avatar
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-...
Bobby Ocean's user avatar
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-...
Stanley Yao Xiao's user avatar
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} + \...
Nilotpal Kanti Sinha's user avatar
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$...
Per Alexandersson's user avatar
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 ...
vixenn's user avatar
  • 63
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-...
David's user avatar
  • 197
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 ...
Stanley Yao Xiao's user avatar
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 ...
Mikhail Katz's user avatar
  • 15.1k
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 ...
SJY's user avatar
  • 579
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 ...
Shahab's user avatar
  • 433
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 ...
zeraoulia rafik's user avatar
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 ...
James Baxter's user avatar
  • 2,029
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$ ...
Salvo Tringali's user avatar
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 ...
David's user avatar
  • 347
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|...
Ben Green's user avatar
  • 4,756
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 ...
Stanley Yao Xiao's user avatar

1 2 3
4
5
14