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 ...

1
vote
0answers
68 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
197 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
147 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
80 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
391 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
498 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
138 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
153 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
109 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
151 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
27 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
134 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
202 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
229 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
364 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
193 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
112 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
51 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
268 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
84 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
78 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
173 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
222 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
171 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
262 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
157 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
176 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
164 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
233 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
90 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
210 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
165 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
286 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
90 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 ...
2
votes
0answers
131 views

Inequality in the proof of Roth's theorem on progressions

I was working out through the proof of Roth's theorem on arithmetic progression. I ran into the following inequality which is not clear to me: Let $A\subset \mathbb{Z}_N$ and $M_A:=A\cap [N/3,2N/3)$ ...
3
votes
1answer
111 views

Bounding the size of certain sumsets in the plane

Let $A$ be a finite set in $\mathbb{R}^2$ of $k^2$ elements and consider a set $B=\{x_1,x_2,x_3,x_4\}$ such that the points in $B$ are in general position (no three points on a line). Question 1: Is ...
1
vote
0answers
120 views

Lemma towards Roth's theorem

I am trying to work out the proof of the following lemma which is used in the proof Roth's theorem. However, I guess that this lemma has some flaws in the proof and I would be very grateful is ...
3
votes
1answer
199 views

Separating points of shifts of a finite set in the plane

Let $A\subset \mathbb{R^2}$ be a finite set such that $|A|=k^2$. Let $x_i\in \mathbb{R^2}$, $i=1,2,3,4$, be four points in the plane in general position (no three lie on any line). Let us form the ...
5
votes
1answer
116 views

Density of intersection with shifted sets

Given a subset $S$ of the positive integers $\mathbf{N}$, let $\mathrm{d}^\star(S)$ be its upper asymptotic density, that is, $$ \mathrm{d}^\star(S)=\limsup_{n\to \infty}\frac{|S \cap [1,n]|}{n}. $$ ...
2
votes
1answer
84 views

Smallest $k$ such that every vector is a linear combination of at most $k$ generators

Let $V$ be a finite dimensional vector space over a finite field $\mathbb{F}_q$ (the most interesting case to me is $q=O(1)$). Let $A$ be an arbitrary subset of $V$ that spans $V$ over $\mathbb{F}_q$. ...