Questions tagged [additive-combinatorics]

Additive combinatorics is about giving combinatorial estimates of addition and subtraction operations on Abelian groups or other algebraic objects. Key words: sum set estimates, inverse theorems, graph theory techniques, crossing numbers, algebraic methods, Szemerédi’s theorem.

Filter by
Sorted by
Tagged with
2
votes
2answers
57 views

$\pm 1$ valued vectors in an arbitrary subspace.

In a paper I have read on random Bernoulli matrices it was stated that for any subspace $V\subseteq \mathbb{R}^n$ of dimension at most $l$ one has: $$|V\cap \{\pm 1\}^n|\leq 2^l$$ With no proof. A ...
2
votes
1answer
44 views

Meaning of “non-trivial three-term arithmetic progressions”

In this paper "ON ROTH’S THEOREM ON PROGRESSIONS" by Tom Sanders, the author gives a bound related to "non-trivial three-term arithmetic progressions", but what exactly means "...
0
votes
0answers
33 views

Bounds and algorithms for graph vertex mapping with distinct edge differences

Given a finite graph $G = (V,E)$ let $F$ be the set of all functions $f : v \to \mathbb{N}$ where $$\#(\{\lvert f(a) - f(b)\rvert \mid (a,b)\in E\})=\#(E)$$ (i.e., vertex mappings where the ...
1
vote
1answer
34 views

What are some good resources to learn arithmetic combinatorics?

I have been very intrigued by the theory of arithmetic combinatorics after the result regarding primes in arithmetic progressions proven by Tao and Green. PAPERS ARE OK. I notice that most people ...
1
vote
1answer
36 views

A property for subsets of real numbers with the condition $\mathbb{Q}^++A\subseteq A$

Consider the additive group $(\mathbb{R},+)$ and let $A$ be a subset such that $\mathbb{Z}^++A\subseteq A$ (equivalently $1+A\subseteq A$, and if and only if $$ \cdots \subseteq 3+A \subseteq 2+A \...
1
vote
0answers
24 views

Given a set $A$, find a set $B$ that is Frieman 2-Isomorphic to $A$ with the smallest diameter.

Let $A,B\subseteq \mathbb{N}$. We say that $A\sim B$ if there exists a bijection $f:A\to B$ such that: $$\forall a_1,a_2\in A,\quad b_1,b_2\in B\quad a_1+a_2 = b_1+b_2 \iff f(a_1)+f(a_2) = f(b_1)+f(...
3
votes
0answers
23 views

Using wavelet decompositions to solve Problems in additive combinatorics

Fourier analysis is used in additive combinatorics as a way to detect structure in sets(Roth’s theorem, Szemeredi’s Theorem, Erdos-Szemeredi conjecture, Green-Tao Theorem etc). In particular(from what ...
3
votes
1answer
58 views

Finding generating series

I am not able to figure out this problem based on Combinatorics - How many integer compositions of n, where $n ≥ 0$, are there where every part is even, and there are at least three parts? How should ...
3
votes
1answer
47 views

Understanding Arithmetic Progression in $[N]$ vs. $\mathbb{Z}_N$

For a set $A$ with some underlying addition operator, $r_k(A)$ is the size of the maximum subset of $A$ that does not contain a $k$-term arithmetic progression. Exercise 10.0.1 in Tao-Vu's Additive ...
1
vote
1answer
115 views

Purely Combinatorial Proof that Thick Sets are Poincaré

We have the following definitions: Definition 1. A set $P \subset \mathbb{N}$ is said to be a Poincaré sequence if for every finite measure-preserving system $(X, \mathcal{S}, \mu, T)$ and any set $A ...
6
votes
2answers
93 views

Two sets having the same subset sums.

I was trying to prove the following Proposition: Let $A=\{a_1,\ldots, a_k\}$ and $B=\{b_1,\ldots, b_k\}$ be two multisets (repetition is allowed) with $|A|=|B|=k$. Also $0\le a_1\le a_2\le\ldots \le ...
9
votes
1answer
129 views

Properties of subsets for which $\sum 1/k$ diverges

The well-known Erdos-Turan conjecture is the following. Let $V \subset \mathbb{N}$ be such that $\sum_V k^{-1}$ diverges. Then $V$ contains arithmetic progressions of every possible length. A recent ...
11
votes
1answer
287 views

If an infinite set $S$ of positive integers is equidistributed, is $S+S$ also equidistributed?

By $S+S$, I mean $\{x+y,$ with $x,y \in S\}$. By equidistributed, I mean equidistributed in residue classes, as defined here (the definition is very intuitive, and examples of such equidistributed ...
35
votes
0answers
924 views

A Nice Problem In Additive Number Theory

$\color{red}{\mathrm{Problem:}}$ $n\geq3$ is a given positive integer, and $a_1 ,a_2, a_3, \ldots ,a_n$ are all given integers that aren't multiples of $n$ and $a_1 + \cdots + a_n$ is also not a ...
3
votes
1answer
111 views

Determine the structure of all finite sets $A$ of integers such that $|A| = k$ and $|2A| = 2k + 1$.

An exercise in Nathanson's text: Additive Number Theory, Inverse problems and the geometry of sumsets is the following (Excercise 16, P.No.37): Determine the structure of all finite sets $A$ of ...
3
votes
1answer
94 views

$4$ vectors in $\mathbb{Z_4}^9$that sum to $0$. [duplicate]

Problem: Given $2018$ elements not necessarily distinct from $\mathbb{Z_4}^9=\mathbb{Z_4} \times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{...
2
votes
1answer
79 views

Largest set $B$ such that $|A\cap (B-B)|=p$

In a preprint I was reading the following was claimed without proof: Let $A$ be a subset of $[n]:=\{1,2,\dots n\}$ where $|A|<\frac{n}{k}$ for some integer $k$. Then there exists a set $B\subset [...
6
votes
0answers
84 views

How to solve arithmetic problems involving infinite sets of integers such as this one?

Let $A\subset \mathbb{N}$ be an infinite set. Let $N = 10^{2020}$. Prove that : $$ \exists(n,m)\in A^2,\quad \exists p \;\text{prime} \geq N,\quad p|n+m$$ I couldn't manage to solve this problem. How ...
5
votes
0answers
49 views

Szemerédi Regularity Lemma - finding regular pairs of “large” size

The Szemerédi Regularity Lemma states that for every $\epsilon>0$, there exists a constnat $M$ (dependent only on $\epsilon$) such that every graph $G$ has a $\epsilon$-regular partition of its ...
3
votes
0answers
94 views

Goldbach conjecture and other problems in additive combinatorics

The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance: $S = T$ is the set ...
2
votes
1answer
75 views

Understanding the step in the proof about additive energy

I'm reading a paper on arXiv on additive combinatorics, and I have trouble understanding a step in the proof on page 16. Suppose $\Gamma \subseteq F^\times_p $ is a multiplicative subgroup of integers ...
7
votes
1answer
54 views

Density in $\mathbb{Z}^2$

I am self-studying topics in additive combinatorics and am working on a problem. One way to define density of a subset $A$ in $\mathbb{Z}^2$ is the so called upper density, defined as $$\limsup\...
1
vote
1answer
66 views

For $N$ large, if $A\subseteq[N]^d$ with $|A|\ge\delta N^d$ there is $S'=S+a$ of a finite $S\subseteq\mathbb{Z}^d$ with $|S'\cap A|\ge (\delta/2)|S|$

Let $S\subseteq\mathbb{Z}^d$ be a finite set. Then there is a positive integer $N$ such that for any $A\subseteq[N]^d$ with $|A|\ge\delta N^d$ there is a translate $S'=S+a$, with $a\in[\mathbb{Z}]^d$ ...
1
vote
1answer
121 views

Estimating Fourier transform of an indicator function

Given a multiplicative subgroup $ \Gamma \subseteq F^*_p $ (multiplicative group of integers modulo prime $ p $), its indicator function $ \Gamma(x) $, and the Fourier transform of a function $ f: F_p ...
1
vote
0answers
24 views

Properties of the Complement of a Sumset

Let $(G, +)$ be a finite abelian group. Let $A, B$ be subsets of $G$. Then we define the sumset (or Minkowski sum) as: $$A + B = \{a + b\mid a\in A, b\in B\}$$ Fix a subset $C\subseteq G$. For any $A\...
1
vote
0answers
32 views

On subsets of $\mathbb N^2$ with elements not comparable w.r.t. componentwise order

Let $\mathbb N$ denote the set of nonnegative integers . For $(a,b);(c,d)\in \mathbb N^2$, define $(a,b)\le (c,d)$ iff $a\le c$ and $b\le d$. Let us call call a subset $S\subseteq \mathbb N^2$ to ...
0
votes
1answer
35 views

Finding large solution-free sets

(posted on Stack Overflow, but was suggested to post here instead) Is there any nice way to check if a given set has any (nontrivial) solutions to a fixed linear equation? My goal is to find the ...
7
votes
0answers
195 views

A Goldbach-like conjecture for Ramanujan primes

Few days ago I wondered if it is known a variant of Goldbach's conjecture but just using Ramanujan primes (in the spirit of the following conjecture). The related articles from Wikipedia are Goldbach'...
0
votes
1answer
45 views

Gowers norm in the case $d=1$

I have a question about these definitions: Let $d \geq 0$ be a dimension. We let $\{0, 1\}^d$ be the standard discrete d-dimensional cube, consisting of d-tuples $\omega=(\omega_1,\dots,\omega_d)$ ...
2
votes
1answer
80 views

Asymptotic number of $3$-AP's in a set $A\subseteq\mathbb{F}_{p}^{n}$ of density $\epsilon$.

Problem: Let $p$ be an odd prime number and consider the $n$-dimensional vector space over the field with $p$ elements. I want to prove that the number of $3$-term arithmetic progressions in a subset $...
4
votes
2answers
73 views

Density of full $k$-dimensional affine subspaces of $\mathbb{F}_{p}^{n}$.

Let $p$ be an odd prime and let $\mathbb{F}_{p}^{n}$ be the $n$-dimensional vector space over the field of $p$ elements. Consider a subset $A\subseteq \mathbb{F}_{p}^{n}$ with density at least $\...
4
votes
1answer
85 views

Can $q^2 \alpha \,(\text{mod } 1)$ be made arbitrarily small?

We have the standard Dirichlet approximation theorem that states that, for $\alpha \in (0,1)$, $$ \min_{1 \leqslant q \leqslant n} q \alpha \,(\text{mod } 1)\, \xrightarrow{unif.} 0 $$ uniformly in ...
1
vote
1answer
79 views

Set $A$ with $|2A| \geq 100|A|$ but $|3A| < 1000|A|$

Let $kA$ denote the sumset $\{ a_1 + \cdots + a_k \mid a_i \in A \}$. I want to show that $|2A| \geq 100|A|$ does not imply $|3A| \geq 1000|A|$. [I know this to be true experimentally, but am ...
2
votes
1answer
98 views

Subset of $[N]$ with given density $\alpha$ contains at least $\Theta(N^2)$ 3-term arithmetic progressions

Let $\alpha > 0$. Prove that there is a constant $b>0$ such that any subset $A$ of $\{1,\ldots, N\}$ of size at least $\alpha N$ contains at least $bN^2$ three-term arithmetic progressions (each ...
1
vote
1answer
45 views

Relatively maximal sum-free subsets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ sum-free iff $\forall a, b \in S$ we have $ab \notin S$. What is the value of $c := \sup\{\frac{|A|}{|G|}| $G$ \text{ is a finite group, } A \...
2
votes
0answers
51 views

Finite concatenation-free languages

Suppose, $A$ is a finite alphabet. $L \subset A^*$ is a language. Let's call $L$ concatenation-free iff $\forall u, v \in L$ we have $uv \notin L$. Does there exist some function $c: \mathbb{N} \...
1
vote
1answer
185 views

Existence of thin bases

Suppose $A$ is a finite alphabet. Let’s call a formal language $L$ over $A$ a base of order k iff $|A^* \setminus L^k| < \infty$. The following statement is true: If $|A| \geq 2$ and $L$ is a ...
0
votes
2answers
81 views

On a sum of binomial coefficients and inequalities

Let $n\ge d\ge 3$ be positive integers. Is there a closed form formula for $\sum_{i=0}^d \binom {n-d+i-1}{i}$ ? For what conditions on $n$ and $d$ can we say $\sum_{i=0}^d \binom {n-d+i-1}{i} \le ...
5
votes
1answer
180 views

Sum-free sets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ sum-free iff $\forall a, b \in S$ we have $ab \notin S$. Do there exist such $\epsilon > 0$, such that every sufficiently large finite group $G$...
0
votes
1answer
46 views

Multiplication of a set by a multiplicative subgroup of $ F^*_p $ [closed]

Suppose that $ \Gamma \subset F^*_p $ (integers modulo a prime number $p$) is a multiplicative subgroup. $ A \subset F^*_p$ is a set and $ A $ is smaller than $ \Gamma $. Also $$ A\Gamma = \{a\gamma: ...
3
votes
1answer
79 views

Prove $|A + B| ≥ |A| + |B| - 1$

Let A and B be two non-empty sets of real numbers. Define A + B to be the set $$A+B = \{ a + b : a ∈ A, b ∈ B\}$$ For instance, if $A =\{1,3,4\}$ and $B = \{1,3\}$, then $A + B =\{2,4,5,6,7\}$. show ...
0
votes
1answer
48 views

Subsets $A$ of rational numbers with $| \Bbb{Q} \setminus (A-A)|=2m$

Fix a positive integer $m$ and let $\mathbb{Q} \cap (m, +\infty) = \{ r_k \}_{k \ge m}$. If $$A:= \left\{ m+r_m+\sum_{k=m}^n r_k : n \ge m-1\right\},$$ then we know that $A-A= \Bbb{Q} \setminus ([-m,m]...
2
votes
0answers
77 views

What is the maximum size of a subset $A\subset \Bbb Z_n$ such that $A+A \subset \Bbb Z_n^*$

My question, as in the title: What is $f(n)$ the maximum size of a subset $A\subset \Bbb Z_n$ such that $A+A \subset \Bbb Z_n^*$ where $\Bbb Z_n=\{0,1,....,n-1\}$ the ring of integers modulo $n$, $...
2
votes
1answer
62 views

A conjecture about a subset of integers

Fix a positive integer $m$ and put $$A_m:= \{ \sum_{k=m+1}^n k: n \ge m\}=\{\frac{1}{2}n^2+\frac{1}{2}n-\frac{1}{2}m^2-\frac{1}{2}m: n \ge m\}= \{\frac{1}{2}(n-m)(n-m+1): n \ge m\} $$ It is not ...
0
votes
1answer
11 views

Calculate the sum of geometric progression.

How to calculate the sum of $(14/3I)^n+C^n_1(14/3I)^{(n-1)}+C^n_2.(14/3I)^{(n-2)}+.......+1.$ where $n$ is a positive integer and $I$ is identity Matrix.
0
votes
1answer
32 views

Say p $> 7$ be a prime such that p $\equiv$ 1 (3). Show that the set of cubic residues (including zero) do not form an arithmetic progression.

I already know that $\mathbb{Z}/p\mathbb{Z}$ - $\{0\}$ is partitioned into C$_{p}$, $x C_{p}$ and $ x^{2}C_{p}$ , where 'x' is a non-cubic-residue. This means that the cardinality of set of cubic ...
2
votes
0answers
43 views

Behrend's theorem

A subset $A$ of $\{1,...,n\}$ is called primitive if it has the property that no element of $A$ is a multiple of any other element in $A$. Behrend's theorem states that the logarithmic density of any ...
4
votes
0answers
86 views

Sidon sets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...
2
votes
0answers
58 views

Additive structure of polynomial rings

I've been wondering recently about results for irreducibility that use the "additive structure" of the polynomial ring at hand. For instance, can we say anything about the irreducibility of a sum of ...
2
votes
1answer
53 views

Maximal size of bounded “sparse” sets of natural numbers

Let’s call $A \subset \mathbb{N}$ sparse iff for all quadruples of distinct numbers $(a, b, c, d)$ from $A$ it is true, that $a + b \neq c + d$. What is the maximal possible size of a sparse set $A$, ...

1
2 3 4 5 6