Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
72 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\...
4
votes
2answers
298 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$ ...
2
votes
0answers
99 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$. ...
46
votes
5answers
4k views

Jean Bourgain's Relatively Lesser Known Significant Contributions

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, such as the proof of Vinogradov's conjecture ...
11
votes
2answers
516 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,$$ ...
1
vote
1answer
175 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 @...
3
votes
0answers
101 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:...
3
votes
0answers
230 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 ...
7
votes
0answers
153 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 ...
-1
votes
1answer
89 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
3answers
409 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 ...
12
votes
2answers
507 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 ...
2
votes
0answers
140 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 ...
3
votes
0answers
154 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,...
6
votes
0answers
112 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,...
4
votes
0answers
154 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
vote
0answers
28 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 ...
0
votes
2answers
137 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 ...
6
votes
0answers
203 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(...
3
votes
1answer
256 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 ...
11
votes
2answers
366 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 \...
34
votes
3answers
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 ...
6
votes
1answer
195 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 ...
3
votes
1answer
113 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 $...
3
votes
1answer
198 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....
3
votes
0answers
52 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 ...
12
votes
0answers
272 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 ...
2
votes
0answers
85 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 ...
1
vote
0answers
49 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 ...
0
votes
0answers
79 views

Infinite difference length of integer subsets

Let $A$ be a set of integers. In our recent researches, we've faced to the following property and definition: We say $A$ has infinite difference length, if (a) For every integer $n$ there exist a ...
6
votes
1answer
313 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 ...
5
votes
2answers
174 views

The number of co-circular four tuples

Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?
5
votes
1answer
224 views

Additive basis of order 2

Can we find $\alpha>1$ such that $u=(\lfloor n^\alpha\rfloor)_{n\geqslant0}$ is an additive basis of order $2$ (i.e. $\forall x\in\mathbb{N}, \exists(n,m)\in\mathbb{N}^2, x=u_n+u_m$) ? Remark : ...
3
votes
1answer
176 views

Density version of the Erdos-Graham conjecture

In 2003 E. S. Croot [Ann. of Math. 157(2)(2003), 545-556] proved the Erdos-Graham Conjecture which states that if $\{2,3,\ldots\}$ is partitioned into finitely many subsets then one of the subsets ...
6
votes
1answer
272 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,\...
3
votes
0answers
158 views

Does every $n\times n\times n$ Latin cube contain a Latin transversal?

In 1967 H. J. Ryser conjectured that every Latin square of odd order has a Latin transversal. Similar to Latin squares, we may consider Latin cubes. QUESTION: Let $n$ be any positive integer. Does ...
0
votes
0answers
56 views

Maximum-size sum sets

Let $A, B \subseteq G$ for abelian group $G$. It is obvious that $|A+B| \leq |A| \cdot |B|$. Is there an easy characterization of sets $A, B$ meeting this bound? I am especially interested in the case ...
4
votes
1answer
179 views

A permutation problem for finite subsets of an abelian group

Here I ask the following question in additive combinatorics. QUESTION: Let $A$ be any finite subset of an additive abelian group $G$ with $|A|=n>3$. Can we write $A$ as $\{a_1,\ldots,a_n\}$ so ...
7
votes
0answers
207 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 ...
4
votes
1answer
165 views

Balancing points with lines

$\newcommand{\F}{\mathbb F}$ Suppose that $p$ is a prime, and $k<p/2$ a positive integer. Consider a system of $k$ distinct directions in the affine plane $\F_p^2$, and the system of $k$ pencils ...
5
votes
0answers
132 views

Is every integer $n>1$ the sum of two triangular numbers and two powers of $5$?

Recall that the triangular numbers are those integers $$T_n=n(n+1)/2\ \ \ (n=0,1,2,\ldots).$$ In 1796 Gauss proved that each $n\in\mathbb N=\{0,1,2,\ldots\}$ is the sum of three triangular numbers, ...
4
votes
1answer
234 views

Asymptotic for number of partitions of $n$ into $k$ squares, uniform in $n,k \to +\infty$

Let $p^{(s)}(n)$ be the number of ways of writing the positive integer $n$ as a sum of perfect $s$-powers, where the order does not matter. For example, $p^{(2)}(9) = 4$ since $$9 = 1^2 + 1^2 + 1^2 + ...
3
votes
0answers
91 views

Decomposing a subset of $\mathbf Z$ into a sumset of irreducibles

We say that a subset $A$ of $\mathbf Z$ is irreducible if $|A| \ge 2$ and there do not exist $X, Y \subseteq \mathbf Z$ with $|X|, |Y| \ge 2$ such that $A = X + Y$. If $X \subseteq \mathbf Z$, we ...
5
votes
0answers
102 views

$m$-thick sets with small $n$-fold sumsets in finite cyclic groups

Problem. Is it true that for every positive integers $n,m$ there exists a subset $A_{n,m}$ of a finite cyclic group $G$ having the following two properties: $(\Sigma_n)$ the $n$-fold sum $A_{n,m}^{+...
15
votes
3answers
2k views

Is there an “analytical” version of Tao's uncertainty principle?

Let $p$ be a prime. For $f: \mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{C}$ let its Fourier transform be: $$\hat f(n) = \frac{1}{\sqrt{p}}\sum_{x \in \mathbb{Z}/p \mathbb{Z}} f(x)\, e\left(\frac{-xn}{...
1
vote
0answers
212 views

Prove A Skipping Prime Conjecture For Rio?

I am writing a paper to accompany a Short Communication I plan to give in Rio this August. The paper regards work on jumping primes, a project on which Jose Brox has been working with me. I was going ...
1
vote
1answer
168 views

Behrend's Construction

Consider the following statement due to F.Behrend (1946) Theorem: Let $N$ be a large integer. Then there exists a subset $A\subset [1,N]$ with $\frac{|A|}{N}\geq \exp(-4\sqrt{\ln N})$ which does not ...
1
vote
1answer
101 views

Existence of Arithmetic Progression from density inequality

Let $A\subset \{0,1,\dots, N-1\}$ such that $$|A\cap [0,N/3)|\geq \left(\delta+\dfrac{\delta}{8}\right)\cdot \dfrac{N}{3},$$ where $\delta\in (0,1]$. Prove that exists arithmetic progression $P$ with $...
4
votes
1answer
288 views

Sets $A$ stable under $(x,f(x))\mapsto x+f(x)$

Let $A$ be a finite set of real numbers or integers. We know how to characterize, broadly speaking, sets $A$ such that $A+A$ is not much larger than $A$ (Freiman's theorem). I have a question that ...
0
votes
0answers
93 views

Square weighted integer partition

As a part of my research I have arrived at the following generating function $\prod_{k=1}^{\infty}\left(\frac{1}{1-k^{2}x^{k}}\right)$ This is almost similar to the generating function of the ...