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.
665
questions
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$ ...
2
votes
2
answers
227
views
Monochromatic solution to $x+y=z^2$
Does anyone know any references/hints for the following problem?
For any $k \geq 1$ there is a threshold, $n_{0}=n_{0}(k)$ such that if $n \geq n_{0}$ then any $k$ -colouring of the first $n$ ...
- 389
2
votes
0
answers
39
views
Weighted unrestricted Golomb rulers?
A set of integers
${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}\quad a_{1}<a_{2}<...<a_{m}} $
is a Golomb ruler if and only if
${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},a_{i}...
- 13.7k
2
votes
0
answers
219
views
For any finite subset $A \subset \mathbb{R}$ we have that $\left| \frac{A+A}{A+A}\right| \gg |A|^2 $
I am trying to understand how sumset theory is actually used in other parts of math or within additive combinatorics. Here are some results I have found in this paper from 2018 ([1], [2]):
Thm (...
- 22.6k
6
votes
1
answer
260
views
Is there some sort of formula for $\tau(S_n)$?
Let $G$ be a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$.
Is there some sort of formula for $\tau(S_n)$, ...
- 2,618
12
votes
4
answers
2k
views
Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?
Let $V$ be a set of positive integers whose natural density is 1. Is it necessarily true that $V$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $a,b,\nu$ with ...
- 1,266
3
votes
1
answer
180
views
Some sums related to a quadratic polynomial over $\mathbb{F}_2^n$
For any $c \in \mathbb{F}_2^n$ define $\sigma_c: \mathbb{F}_2^n \to \mathbb{F}_2$ the quadratic polynomial defined for $v = (v_1,v_2,...,v_n)$ by:
$$ \sigma_c (v) = \sum_{i=1}^n v_iv_{i+1} + c_iv_i $...
- 1,020
2
votes
0
answers
139
views
Primality radii and Sidon sets
I learned tonight what a Sidon set is, in a book about Erdős. This notion inspires me the following question :
For $n$ a large enough composite integer, say $r>0$ is a primality radius of $n$ if ...
- 6,932
5
votes
2
answers
1k
views
Cardinality of certain subsets in vector spaces over finite fields
Assume that you have an $n$-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and $F$ is a subset of this vector space which contains $m$ ...
- 228
1
vote
2
answers
157
views
Distribution of a knapsack problem
I am considering a special knapsack problem. The knapsack capacity is $M$. There are $N$ items ($N≥M$). The weight of each item is 1. The profit for each item i is $p(i)≥0$. Thus, $M$ items can be ...
- 13
2
votes
2
answers
287
views
Calculating the number of solutions of integer linear equations
Let $N$ be a natural number. Consider the following set of matrices whose entries are non-negative integers:
$$X_N:=\left\{(c_{ij})_{i,j=1}^4\in M_4(\mathbb{Z}_{\geq 0})\bigg| \sum_j c_{1j} = \sum_i ...
- 4,979
4
votes
1
answer
719
views
Trick for the sum-product problem
Yesterday I read the Quanta article How a Strange Grid Reveals Hidden Connections Between Simple Numbers about the sum-product problem:
Let $A$ be a set of integers. Erdös and Szemerédi conjectured ...
- 2,539
3
votes
1
answer
200
views
Gowers norms and three-term arithmetic progressions in the mean
Let $f:\mathbb{Z}^+\to \mathbb{C}$ be bounded. Say we are interested in studying how $f$ behaves in short three-term arithmetic progressions. It is very well-known that we can bound
$$\sum_{h\leq H} \...
- 535
1
vote
0
answers
72
views
Unit-product sets in finite decomposable sets in groups
A non-empty subset $D$ of a group is called decomposable if each element $x\in D$ can be written as the product $x=yz$ for some $y,z\in D$.
Problem. Let $D$ be a finite decomposable subset of a ...
- 40.9k
5
votes
0
answers
173
views
Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles
Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
- 19.1k
6
votes
1
answer
496
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 ...
- 2,039
13
votes
2
answers
2k
views
Positive integers written as $\binom{w}2+\binom{x}4+\binom{y}6+\binom{z}8$ with $w,x,y,z\in\{2,3,\ldots\}$
Let $\mathbb N=\{0,1,2,\ldots\}$. Recall that the triangular numbers are those natural numbers
$$T_x=\frac {x(x+1)}2\quad \text{with}\ x\in\mathbb N.$$
As $T_x=\binom{x+1}2$, Gauss' triangular number ...
- 14.5k
4
votes
1
answer
197
views
Bound of size $X\subset \mathbb{Z}/N\mathbb{Z}$ which satisfies $X+X=\mathbb{Z}/N\mathbb{Z}$
(Sorry for my poor english skill..)
Let $N$ be a large integer and the set $X$ be the subset of $\mathbb{Z}/N\mathbb{Z}$. For two sets $A$ and $B$, we define
\begin{equation}
A+B:=\{a+b : a\in A, b\...
- 661
3
votes
0
answers
68
views
A notion of largeness somewhere between $\mathrm{IP}_+$ and $\mathrm{IP}_+^*$
It is a well known fact that a set $A \subset \mathbb{N}$ is $\mathrm{IP}$ if and only if there exists an idempotent $p \in \beta \mathbb{N}$ (i.e., $p+p=p$) such that $A \in p$. Similarly, $B \subset ...
- 1,762
2
votes
0
answers
203
views
Concerning the identity in sums of Binomial coefficients [closed]
Consider the following identity
$$\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=0}^{n-1}\binom{k+1}{2}=\sum_{k=1}^{n}k(n-k)=\sum_{k=0}^{n-1}k(n-k)=\frac16(n+1)(n-1)n$$
As we can see the partial sums of binomial ...
- 167
0
votes
1
answer
177
views
A question on "SUM-PRODUCT...VIA KLOOSTERMANN SUMS", by Hart, Iosevich and Solymosi
In this paper https://arxiv.org/pdf/math/0609426.pdf, the authors, state, as a consequence of Theorem 1.1, the following sum-product estimate.
Theorem 1.1 says that for all $A\subset\mathbb{F}_q$, we ...
- 291
0
votes
0
answers
100
views
Number of $b$-separated Sidon sets with pairwise difference set intersection bounds
Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ call a set of $m$ integers $a_1<\dots<a_m$ in the interval $(p^\alpha,p-p^\alpha)$ to be $b$-separated Sidon if:
$a_i-a_j\...
- 13.7k
4
votes
2
answers
381
views
An extremal combinatorics problem
Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ what is the largest $m$ we have such that in the interval $(p^\alpha,p-p^\alpha)$ there are $m$ integers $a_1<\dots<a_m$ ...
- 13.7k
2
votes
0
answers
172
views
On an exercise in The Probabilistic Method : random dilate of a set in a finite field
This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:
Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
- 21
62
votes
5
answers
9k
views
Jean Bourgain's relatively lesser known significant contributions
Jean Bourgain passed away on December 22, 2018.
A great mathematician is no longer with us.
Terry Tao has blogged about Bourgain's death and mentioned some of his more recent significant contributions,...
10
votes
2
answers
610
views
Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$
Suppose $f:\mathbf{N} \to [0,1]$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $x,y$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ ...
- 9,195
1
vote
1
answer
251
views
Largest cardinality $n$ of a subset $A$ of $\{1,2,\ldots,M\}$ such that $(A+A) \cap A$ is empty
Assume that the set $A$ does not have simple structures (such as the case that when all elements are odd numbers in $[1,M/2]$ then all sums are even thus there are no solutions, as pointed out by @...
- 10.1k
4
votes
0
answers
152
views
Inequalities about tripling and doubling sumsets
Let $A$ be a set of vectors in $\mathbb Z^d$ who $\mathbb R$-span is the whole $\mathbb R^d$. Let $s_i(A)$ denote the size of $A+A+\dots A$ ($i$ times). I am interested in the following:
Question 1:...
- 30.3k
3
votes
0
answers
281
views
A new combinatorial problem for finite groups
In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...
- 14.5k
11
votes
0
answers
526
views
Cyclic and prime factorizations of finite groups
A tuple $(A_1,\dots,A_n)$ of subsets of a finite group $G$ is called a factorization of $G$ if $G=A_1\cdots A_n$ and $|A_1|\cdots|A_n|=G$.
In Cryptology factorizations of groups are known as ...
- 40.9k
0
votes
1
answer
284
views
Discrepancy in non-homogeneous arithmetic progressions
I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies
$ \left | \...
10
votes
3
answers
543
views
Is each finite group multifactorizable?
Definition. A finite group $G$ is called multifactorizable if for any positive integer numbers $a_1,\dots,a_n$ with $a_1\cdots a_n=|G|$ there are subsets $A_1,\dots,A_n\subset G$ such that $A_1\cdots ...
- 40.9k
12
votes
2
answers
876
views
Factorizable groups
Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,B\subset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.
Problem 1. ...
- 40.9k
1
vote
0
answers
154
views
On the set $\{\sum_{k=1}^n \lambda_ka_k:\ a_1,\ldots,a_k\ \text{are distinct elements of}\ A\}$
For a field $F$ let $p(F)=p$ if the characteristic of $F$ is a prime $p$, and $p(F)=+\infty$ if $F$ is of characteristic zero.
In 2007 I considered the linear extension of the Erdos-Heilbronn ...
- 14.5k
3
votes
0
answers
190
views
A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$
Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
- 14.5k
6
votes
0
answers
123
views
Sets $X,Y$ of natural numbers such that any natural $n$ writes uniquely $n=x+y$ [duplicate]
There are many pairs $X, Y$ of infinite subsets of $\mathbb{N}:=\{0,1,2\dots\}$ such that any $n\in\mathbb{N}$ writes uniquely as $n=x+y$, with $x\in X$ and $y\in Y$. An example of such a pair is $(X,...
- 56.6k
5
votes
0
answers
336
views
Lower bound for some sums of roots of unity
Let $n$ be a positive integer (assume $n$ is prime for simplicity), and let $x_k = \pm1$, for $k = 0,1,2,..., n-1$. Let $\rho$ be an $n-$th primitive root of unity, I am interested in a lower bound ...
- 1,020
1
vote
0
answers
49
views
Has anyone studied Golomb rulers having a spectrum with a minimal $L^2$ norm?
A Golomb ruler can be described as a set of marks on a line having integer positions, such that no two pairs of marks are separated by the same distance. Call the spectrum of a ruler the (multi-)set ...
- 2,143
0
votes
2
answers
151
views
Analytical result of a combination like generating function
Here is the generating function I'm studying.
$f=\prod^N_{j=1}\left(1+e^{i\cdot j\varphi}z\right)$.
$\varphi$ is a phase related to a quantum optics problem.
And I want to know the analytical ...
- 11
6
votes
0
answers
334
views
Legendre's three-square theorem and squared norm of integer matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...
- 25.9k
3
votes
1
answer
344
views
Lower bound for k-fold Sidon Sets
k-fold Sidon set is defined in http://www.combinatorics.org/ojs/index.php/eljc/article/view/v10i1r25/pdf (page #4, paragraph 4)
Does anyone know what the best known lower bound construction is for the ...
- 389
11
votes
2
answers
402
views
Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$
Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
- 25.9k
35
votes
3
answers
2k
views
Lagrange four squares theorem
Lagrange's four square theorem states that every non-negative integer is a sum of squares of four non-negative integers. Suppose $X$ is a subset of non-negative integers with the same property, that ...
- 1,651
6
votes
1
answer
242
views
A combinatorial property of uncountable groups
Let $A,B$ be two uncountable sets in a group $G$ such that for any elements $x,y\in G$ the intersection $xA\cap yB$ is finite. Let $\Phi:G\to 2^G$ be a function assigning to each element $x\in G$ some ...
- 40.9k
3
votes
1
answer
150
views
On decomposition of finite Abelian groups
It is easy to see that for any finite Abelian group $G$ and any numbers $a,b$ with $|G|=ab$ there exist a subgroup $A\subset G$ and a subset $B\subset G$ such that $|A|=a$, $|B|=b$ and $G=A+B$, where $...
- 40.9k
3
votes
1
answer
246
views
Sidon Sets and Diophantine Equation
Suppose $X$ is a subset of $\{1, \cdots, n\}$ such that the equation $ax_i+bx_j=cx_k+dx_{\ell}$ where $a+b=c+d,$ $a,b,c,d \in \mathbb{N}$ and $x_i, x_j, x_k, x_{\ell} \in X,$ has only trivial solution....
- 389
3
votes
0
answers
78
views
A Freiman-type of question for sets with small doubling costant
I start by saying that I have posted a similar question a few years back, but now I have refined the question a bit more. I have stumbled on this working in finite group theory. The question reminds ...
- 886
16
votes
1
answer
451
views
Escaping from a centralizer
Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$.
By Stirling's ...
- 19.4k
2
votes
0
answers
95
views
Polynomials passing through points with tangential conditions
In corollary here http://math.mit.edu/~lguth/Exposition/erdossurvey.pdf on polynomial methods it is said "(Parameter counting) If $S\subset\mathbb F^n$ is a finite set, then there is a non-zero ...
- 13.7k
1
vote
0
answers
84
views
Equivalent condition for Poincare polynomial
I have found a statement in the introduction of the paper 'Sets of Recurrence and Generalized Polynomials' by Bergelson & Haland, which is
Result: Given a polynomial $p \in \mathbb{R}[x]$ such ...
- 73