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

400 questions
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)$ ...
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 ...
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 ...
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 ...
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}.$$ ...
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$. ...
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?
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$$ ...
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 ...
0answers
180 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ (...
0answers
51 views

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 ...
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 ...
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\}.$$ ...
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 ...
1answer
83 views

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$: ...
3answers
269 views

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