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.

2
votes
0answers
134 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
112 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
118 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$. ...
2
votes
1answer
254 views

Partition set into equal-sum subsets

What is known about how to divide $\{1,4,9,16,...,81^2\}$ into $3$ equal-sum subsets with $27$ elements per subset?
2
votes
1answer
132 views

Properties of Zero Line-Sum Matrices

By a Zero Line-Sum (ZLS) matrix I mean matrices with the property, that each row sum and each column sum equals zero: $$A\in\mathbb{R}^{m\times n}:\ \sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{m}a_{ij}=0$$ ...
1
vote
0answers
85 views

large arithmetic progression modulo p (II)

Is it possible to construct a $B$ $\subseteq$ $Z_p(=Z/pZ)$ of cardinal $cp^{\frac{1}{3}}$, for some constant $c$, such that there exists an arithmetic progression of size $c_1p^{\frac{2}{3}}$, for ...
6
votes
0answers
180 views

A formula for Frobenius number of certain numerical semigroups

The old formula for the Frobenius number of a numerical semigroup generated by two elements can be stated as follows: assume $\gcd\{a+1,b+1\}=1$, then the Frobenius number of $S= \left<a+1,b+1\...
1
vote
1answer
106 views

Large arithmetic progression modulo $p$

Let $B$ be a subset of $Z_p(=\mathbb{Z}/p\mathbb{Z})$ of cardinal $Cp^{\frac{1}{3}}$, for some constant $C$. How to construct an arithmetic progression of length $C_1p^{\frac{2}{3}}$ where $C_1$ is ...
13
votes
1answer
383 views

Near-linear mappings from $\mathbb F_p$ to $\mathbb R$

$\newcommand{\F}{{\mathbb F}}$ $\newcommand{\R}{{\mathbb R}}$ $\renewcommand{\phi}{\varphi}$ Let $p\ge 5$ be a prime. If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
5
votes
1answer
146 views

Disjoint union of affine subspaces contains a larger affine subspace

I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some ...
5
votes
0answers
590 views

Increasing sequences in polynomial progressions modulo p

In a random permutation on $n$ elements one expects the largest increasing and decreasing sequences to have size $(2+o(1))\sqrt{n}$. Is it known if this same property holds in sequences given by ...
10
votes
1answer
458 views

Which of these sums appear most often?

Let $N=\{1,2,3,\ldots, n\}$. We sum all the elements of every nonempty subset of $N$. Which sum(s) appears most often? (Let's call this sum a champion). Using a simple pigeonhole argument a champion ...
4
votes
1answer
88 views

Smallest size of integral vector with certain inner product

Let $v =(r,s,t) \in \mathbb{N}^3$ be a vector such that $\gcd(r,s,t)=1$. We know that there are vectors $x= (x_1,x_2,x_3) \in \mathbb{Z}^3 $ such that $v.x =1$. For each $v$, let $O(v)$ be the ...
6
votes
1answer
329 views

Binary weight of shifted integers

Suppose $n_2$ denotes the binary representation of the integer number $n$. Let $X_2(n)=[1_22_2\ldots n_2]$,$n\geq3$, be a binary vector which is obtained by concatenating of binary representation of ...
3
votes
0answers
41 views

Questions on “The condition number of a randomly perturbed matrix”

This question is about the two vectors $w'$ and $y$ that are necessary for the argument in section $7$ (page 6) of this paper by Terence Tao and Van Vu, https://arxiv.org/abs/math/0703307 (that ...
2
votes
1answer
130 views

A question about finite free convolution

For any square matrix $Y$ let $\chi_x(Y) = det(xI -Y)$ denote its characteristic polynomial. Say $A$ and $B$ are two $n-$dimensional symmetric matrices with constant row sums $a$ and $b$. Lets ...
3
votes
1answer
153 views

Large submatrices of circulant matrices

What properties of circulant matrices are inherited by their principal submatrices? To be more specific: Given a square (zero-one) matrix $M$ of order $n$ with all elements on its main diagonal ...
5
votes
1answer
321 views

A question about the paper “The Condition Number of a Randomly Perturbed Matrix”

My question pertains to this paper by Terence Tao and Van Vu, https://arxiv.org/abs/math/0703307 Both my questions pertain to the argument presented in this paper in its section 6 (page 5). We are ...
1
vote
0answers
26 views

Generating larger atoms from smaller ones in a simple $\text{C}_0$-monoid

Let $P$ be a finite set, $\mathscr F(P)$ the free abelian monoid with basis $P$ (which I'll write multiplicatively), $H$ a submonoid of $\mathscr F(P)$, and $\mathcal A(H)$ the set of atoms of $H$ (...
3
votes
0answers
51 views

On finite subsets of set of integers, which lies in its sum-set , whose sum of elements equals $0$ [duplicate]

Let $n>1$ be an integer and $S \subseteq \mathbb Z$ be such that $|S|=n$ and $S \subseteq S+S:=\{a+b : a,b \in S\}$ ; then does there exist $T \subseteq S$ with $1 \le |T| \le n/2$ such that $\...
11
votes
1answer
573 views

Optimality of the Plünnecke-Ruzsa Inequality

The Plünnecke–Ruzsa Inequality states that for a finite subset $A$ of an abelian group $G$ with small doubling $|A+A|\le K|A|$, the iterated sum and difference sets are also small: $|tA-sA| \le K^{t+...
5
votes
2answers
159 views

Maximum-sized product sets in infinite groups

Let $A$ be a finite subset of the group $H$. I am interested in sets with the property that (1)$\qquad\qquad |\{ab\ \colon\ (a,b)\in A\times A\}| = |A|^{2}$. Thus $A$ has property (1) if the product ...
3
votes
1answer
222 views

Are there unique additive decompositions of the reals?

Given $b\in \mathbb{R}_{>1}$ is there $U\subseteq\mathbb{R}_{\ge 0}$ such that $U+bU=\mathbb{R}_{\ge 0}$ and $(U-U)\cap b(U-U)=\{0\}$ (or equivalently: $u+bv=u'+bv' \implies u=u', v=v'$)? Here is ...
2
votes
1answer
115 views

The product of the clique and independence numbers in the Cayley sum graph

For a finite abelian group $G$ and a subset $S\subseteq G$ with $0\in S=-S$, let $$ \alpha(S):=\max\{|A|\colon(A-A)\cap S=\varnothing\} $$ and $$ \omega(S):=\max\{|A|\colon A-A\subseteq S\}. $$ ...
10
votes
3answers
364 views

Positive integer combination of non-negative integer vectors

A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and ...
2
votes
1answer
83 views

Large additive energy, and numbers having many representations as differences

Let $A$ be a set of $N$ distinct positive integers. For every integer $n$, write $rep(n)$ for the number of representations of $n$ as a difference of two elements of $A$. Then the additive energy of $...
39
votes
4answers
993 views

Sets of unit fractions with sum $\leq 1$

Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number. ...
4
votes
1answer
235 views

Upper Bound on minimum number of lattice points

How to derive an upper bound on the minimum number $n(k,d)$ of lattice points in $d$-dimensions such that there are some $k$ of these points which have a lattice point centroid.
12
votes
1answer
258 views

Partition of [3n] into summoids

Let $ [n] $ be the set $ \{1,2,\ldots n\}$. A summoid is a subset $ A \subset [n] $ of the form $ \{a,b,a+b\} $ (you can choose a better name, if it doesn't exist already). Now, I developed by ...
6
votes
0answers
158 views

Growth in a vector space

I am interested in "growth" in finite vector spaces. I have been wondering about the veracity of the following statement: Statement: For every $\varepsilon>0$ there exists $b\in\mathbb{Z}^+$ ...
5
votes
1answer
215 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 ...
2
votes
0answers
233 views

sum over partitions

Let $\mathcal{P}_{n,k}$ be the set of unordered partitions of a positive integer $n$ into $k$ parts $\mathbf{n}:=(n_1,n_2,\ldots,n_k)$, i.e. such that $n=n_1+n_2+\ldots+n_k$. Are there known results ...
4
votes
0answers
139 views

Linear combination of characters

For each $i \in \mathbb{N}$, let $G_{i}$ be a finite abelian group and $\widehat{G_{i}}$ the $\overline{\mathbb{Q}}$-valued character group of $G_{i}$. Suppose that $|G_{i}| \rightarrow \infty$ as $i \...
5
votes
1answer
214 views

Divisibility labeling on a boolean lattice and nonzero Euler totient

Let $B_n$ be the subset lattice of $\{1,2, \dots , n \}$, also called the boolean lattice of rank $n$. A labeling $f: B_n \to \mathbb{N}_{\ge 1}$ is called acceptable if $\forall a,b \in B_n$: ...
5
votes
3answers
269 views

Request for reference for some proofs about Gowers' norm

For any map $f : \mathbb{F}_2^n \rightarrow \mathbb{C}$ we define its $d^{th}-$Gowers' Norm (for $1 \leq d \leq n$) as, $\|f\|_{U^d(\mathbb{F}_2^n)}^{2^d} = \mathbb{E}_{L : \mathbb{F}_2^d \rightarrow \...
18
votes
3answers
421 views

Decomposing a finite group as a product of subsets

My friend Wim van Dam asked me the following question: For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? ...
4
votes
0answers
143 views

On point sets with many distinct distances

Let $P$ be a set of $n$ points in the plane and let $D$ be the set of Euclidean distances determined by the pairs of points in $P$. Suppose that for each $d \in D$ there are at most $5$ (unordered) ...
2
votes
0answers
132 views

The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in X$

Let $H$ be a multiplicatively written monoid with identity $1_H$. Given $x \in H$, we take ${\sf L}_H(x) := \{0\}$ if $x = 1_H$; otherwise, ${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for ...
6
votes
0answers
141 views

Large cubes in sum/difference sets

If $A$ is a subset of an abelian group with $|A+A|\leq K|A|$ then one can show that $A$ contains a large cube of size depending on $K$. Here a cube is a set of the form $$C=\{a_0+\sum_{i=1}^d e_ia_i:...
2
votes
0answers
60 views

Additive basis of subexponential growth

The affirmative solution to the Waring problem says that every $A_k = \{n^k|n\in \mathbb{N}\}$ is an additive basis for any choice of $k$. Of course, $B_k = \{k^n| n \in \mathbb{N}\}$ is not an ...
6
votes
1answer
206 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 ...
3
votes
0answers
57 views

What's known about $X$ when $|X(n) + X(n)| < kn$, $n \in \mathbb{N}$, absolute constant $k$?

Let $X$ be an infinite sequence of integers$$x_1 < x_2 < x_3 < \ldots,$$and let $X(n)$ be the set$$\{x_1, x_2, \ldots, x_n\}.$$ Question. What is known about $X$ when we have$$|X(n) + X(n)| &...
3
votes
1answer
211 views

Limit measuring failure of sum-set cancellability

Suppose $A$, $B$ are finite sets of positive integers. Let $$\mathcal{S}_n = \{C \subset [1,n] \, : \, A+C = B+C \}, $$ and denote $a_n = |\mathcal{S}_n|$. Note that for any $X \in \mathcal{S}_n$ ...
1
vote
0answers
41 views

In how many different ways can the sumset of a Sidon set be ordered?

Suppose that (a) is a set of n integers a_1> a_2>...>a_n >0 and that the sumset, the set of pairwise sums a_i + a_j , (i<=j), are all different. In how many ways can the sumset be ordered? For ...
4
votes
1answer
121 views

Difference bases in simple cyclic groups

A subset $B$ of an abelian group $G$ is called a difference-basis if $B-B=G$. For a finite group $G$ by $\Delta(G)$ we denote the smallest cardinality of a difference basis of $G$. Let $C_n=\{z\in\...
1
vote
0answers
87 views

Lower bound for sumset in discrete cube

Suppose $A\subset\{0,1\}^d$ for some $d\geq 1$. Then how large must $A+A=\{a+b:a,b\in A\}$ be?
14
votes
1answer
321 views

What is the smallest cardinality of a self-linked set in a finite cyclic group?

A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$. For a finite group $G$ denote by $sl(G)$ the smallest ...