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
1 vote
0 answers
24 views

Sidorenko's conjecture for $K_{2,2}$ graphs

I was reading Gowers's Weblog about the proofs of particular cases of Sidorenko's conjecture. Sidorenko's conjecture. Let $H$ be a bipartite graph with vertex sets $\{a_1,\dots,a_r\}$ and $\{b_1,\...
user avatar
  • 14.7k
1 vote
0 answers
29 views

Additive basis for polynomials of degree exactly $n$

I introduce some work I have done below, and the questions are at the end. For some $n>1$ fixed, let $Q_n$ be the set (not vector space) of polynomials with integer coefficients of degree exactly $...
user avatar
5 votes
0 answers
59 views

Maximum element of two integer sets with distinct pairwise sums?

Let $A, B \in Z^+$ be two sets where $|A|=m, |B|=n$. If all pairwise sums $a+b (a\in A, b\in B)$ are distinct, a.k.a. $|A+B|=|A||B|$, what would be the minimum value of $max(A\cup B)$? A trivial bound ...
user avatar
0 votes
0 answers
20 views

Highest-sum seeding path through a 2^n NCAA tournament?

This discussion came up among Purdue fans discussing their path to the Final 4 and comparing it to Houston's from last year. Purdue, if they can get by St. Peter's and #8 North Carolina beats #4 UCLA, ...
user avatar
  • 374
0 votes
1 answer
35 views

If $G, H$ are approximate groups that $2G\cap 2H$ is also approximate group

Let $G$ be a $K$-approximate group in an ambient group $Z$, and let $H$ be a $K'$-approximate group in $Z$. Show that $2G\cap 2H$ is a $(KK')^3$-approximate group. Attempt of proof: First of all it is ...
user avatar
  • 14.7k
3 votes
1 answer
79 views

Problem 2.4.8 rom Tao-Vu book

For each $j=1,2,3,$ let $G_j$ be a $K_j$-approximate group in an ambient group $Z$. Using the Ruzsa triangle inequality, show that $$|G_1+G_2+G_3|\leq K_2\dfrac{|G_1+G_2||G_2+G_3|}{|G_2|}.$$ Conclude ...
user avatar
  • 14.7k
3 votes
1 answer
78 views

Exercise 2. 3. 8 from Tao-Vu's Additive Combinatorics

Problem: Let $A$ be an additive set in an additive group $Z$ and let $G$ be a finite subgroup of $Z$. Show that $$\sigma[A + G] \leq \frac{|3A|}{|A|}.$$ Conclude that if $\pi: Z \to Z'$ is a group ...
user avatar
0 votes
1 answer
63 views

Corollary 2.24 from Tao-Vu on asymmetric sum set inequalities

I am trying to solve exercise 2.4.3 from Tao-Vu book Prove Corollary 2.24. What value of the implicit constant in the $O()$ notation do you get? Corollary 2.24 (Asymmetric sum set inequalities, ...
user avatar
  • 14.7k
1 vote
0 answers
40 views

Trivial estimate for iterated sumsets $nA=A+\dots+A$

Let $A$ be an additive set with common ambient group $Z$. Then for any integer $n\geq 1$, we have $$|nA|\leq \binom{|A|+n-1}{n}|A|, \quad \quad (*)$$ where $nA:=\underbrace{A+\dots+A}_{n\ \text{times}...
user avatar
  • 14.7k
1 vote
0 answers
63 views

Exercise 2.4.2 from Tao-Vu book

Let $A$ be an additive set in a group $Z$, and let $\phi:Z\to Z'$ be a group homomorphism. Establish the inequalities $$|A|\leq |\phi(A)|\sup \limits_{x\in Z'}|A\cap \phi^{-1}(x)|\leq |2A|.$$ Hint: ...
user avatar
  • 14.7k
0 votes
0 answers
54 views

Proposition 2.18 from Tao-Vu

I was reading the proof of the Proposition 2.18 from Tao-Vu book but one moment is really confusing. Question 1: I did not understand how the authors obtained ineqality which I highlighted by green ...
user avatar
  • 14.7k
1 vote
1 answer
54 views

Green-Ruzsa covering lemma

I am trying to understand the proof of Green-Ruzsa covering lemma from Tao-Vu book but in my humble opinion the proof is written so unclearly that I was not able to comprehend some moments even after ...
user avatar
  • 14.7k
2 votes
0 answers
20 views

Ruzsa's covering lemma from Tao-Vu book and some clarification to the statement

I would like to discuss the Ruzsa's covering lemma from Tao-Vu book. The proof given in the book skips some details and I've decided to write all the details just to be sure that I understand ...
user avatar
  • 14.7k
1 vote
0 answers
82 views

About a proof or disproof of a statement concerning additive bases of natural numbers.

Here $\mathbb{N}=\{1,2,3,\dots\}$. We say that a set $A\subset\mathbb{N}$ is an additive base of natural numbers if there is a positive integer $h$ such that every natural number can be written as $...
user avatar
5 votes
1 answer
82 views

Is there an examble of a non additive base of natural numbers with ratio of two consecutive terms goes to 1?

Here $\mathbb{N}=\{1,2,3,\dots\}$. We say that a set $A\subset\mathbb{N}$ is an additive base of natural numbers if there is a positive integer $h\in \mathbb{N}$ such that every natural number can be ...
user avatar
1 vote
1 answer
252 views

Minimizing the number of different values of $\frac{f(c)-f(d)}{c-d}$ for integers $c,d$ and polynomial $f$

I am looking for the following quantity $\mathcal{E}:=\min \Big( \#\Big\{ \frac{f(c)-f(d)}{c-d}:\text{$f$ is a polynomial s.t. $\text{deg}(f)\ge 2$}, c,d\in A\subseteq \mathbb{Z}~~\text{and}~~|A|\ge ...
user avatar
0 votes
0 answers
29 views

Is this true for a sumset?

We let $A,B\subseteq \mathbb{Z}$ such that $|A|=|B|=n$. I am trying to show that $|A+B|\ge 2n-4$ for large $n$ where we define $A+B=\{a+b:a\in A, b\in B\}$. If this is not true, I'd like to see a ...
user avatar
1 vote
1 answer
54 views

Application of Ruzsa's covering lemma to iterated sum sets

Lemma 2.14 (Ruzsa's covering lemma) For any additive sets $A,B$ with common ambient group $Z$, there exists an addtitive set $X_+\subseteq B$ with $$B\subseteq A-A+X_+;\quad |X_+|\leq \dfrac{|A+B|}{|...
user avatar
  • 14.7k
0 votes
1 answer
26 views

Question about additive combinatorics proof regarding probability estimate

I was hoping someone could explain the meaning of $loglogx$ = $loglogn$ $+$ O(1) and how that statement has probability $1$ $-$ $o$(1). In terms of first attempts, I know that loglogx - loglogn = O(1) ...
user avatar
  • 909
6 votes
0 answers
116 views

Lower bound for the size of a product-set

I recently realised (rather late in life) that I don't have a good grasp of the following: Let $G$ be a finite non-abelian group and let $A, B$ be subsets of $G$. (Neither $A$ nor $B$ is required to ...
user avatar
  • 5,677
3 votes
0 answers
53 views

The number of solutions to $a+b=1$ in a multiplicative subgroup of a finite field $GF(q)$

I have been wondering what is the number of solutions to $a+b=1$ in an arbitrary multiplicative subgroup $H$ (order $r$) of some finite field $GF(q)$, where $q=p^n$ is a prime power and $a, b \in H$. ...
user avatar
  • 33
1 vote
1 answer
43 views

An analytic inequality in the proof of Roth's theorem on arithmetic progressions

When I read the artical A new proof of Roth's theorem on arithmetic progressions, I met an analystic inequality: $$|\Lambda(f)-\Lambda(g)|\leq|\widehat{f}(r)-\widehat{g}(r)|.$$ Here $f,g:\mathbb{F}_p\...
user avatar
  • 324
2 votes
1 answer
51 views

Maximal cardinality of Sidon set

I was trying to solve the following problem from Tao-Vu. Let $A$ be any additive set. Show that a Sidon set contained in $A$ can have cardinality at most $\sqrt{2\sigma[A]|A|}.$ Suppose that $S$ is ...
user avatar
  • 14.7k
0 votes
0 answers
53 views

Lemma 2.11 from Tao-Vu book

I was reading Tao-Vu book on additive combinatorics and came across the following lemma and the book has the proof and I got its general idea but I am bit confused. Lemma 2.11 Let $A,B$ be additive ...
user avatar
  • 14.7k
0 votes
1 answer
52 views

Triangle inequality for Ruzsa distance

Suppose that $Z$ is an additive group, i.e. $Z$ is an abelian group under addition. Let $A$ be an additive set, i.e. $A$ is a non-empty finite subset of $Z$. For any two additive sets $A$ and $B$ in $...
user avatar
  • 14.7k
0 votes
0 answers
32 views

Pigeonhole principle on an integral

This question is from the Lemma 1.2.8 of the book Higher order fourier analysis by T. Tao. We use the following notations: $[N]:=\{1,2,\cdots,N\}$ $\mathbb{E}_{n\in [N]}f = \frac{1}{N}\sum_{n \in [N]}...
user avatar
2 votes
0 answers
29 views

Fourier in $\mathbb{Z}^d$ and use of Pigeonhole principle (Prop. $1.1.13$, HOFA by T. Tao)

We use the following notation: $$[N]:=\{1,2,3,\cdots,N\}$$ $$\mathbb{E}_{n\in [N]}f(x) : = \frac{1}{N}\sum_{n \in [N]}f(x)$$ This doubt is from the book titled Higher Order Fourier Analysis by T. Tao. ...
user avatar
3 votes
1 answer
86 views

How to understand the operation "choose a random subset" in combinatorics?

Hello I'm reading Tao and Vu's book additive combinatorics,and I can not fully convince myself to believe the proof of Theorem 1.13. In the proof, they constructed a set by the following way(It seems ...
user avatar
0 votes
0 answers
36 views

Generating restricted finite additive $2$-bases from doubly-eager bit-strings

A bit-string is any finite sequence of $1$s and $0$s. For example, $1011011$, $1011010$, and $000110$ are bit-strings. In this post, I will refer to bit-strings as strings, to be concise. I now ...
user avatar
0 votes
0 answers
37 views

sum sets of exponents of polynomials over finite fields

In the course of working on a problem from algebraic number theory regarding Fermat's Last Theorem over certain cyclotomic fields, I've stumbled upon the following curious problem which I think would ...
user avatar
0 votes
0 answers
18 views

Coefficient of a term in a several variable polynomial multipled with Vandermonde determinant

Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying $$c_1 + ...
user avatar
  • 614
0 votes
1 answer
67 views

How many subsets $S$ of integer interval $[0,n]$ such that $k \not \in S+S$?

After a bit of experimentation, I thought of the following conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$ and $k \in [0,2n]$, we have $$|\{S : (S \subseteq [0,n]) \land (k \not \in S+S)\}| = 2^{|n-...
user avatar
2 votes
1 answer
197 views

Proof verification and improvement - lower bound for the sum product problem

Thinking about the sum product conjecture, if we consider a set of distinct elements $A=\{a_1,a_2,\dots,a_n\}$, $\forall a_i\in \mathbb Z^+$, I have derived the following lower bound: $$\max\{|A+A|,|A•...
user avatar
0 votes
0 answers
25 views

What does it mean by a subset of an arbitrary group is $O(K^9)$-approximate subset?

Let $G$ be any group and $A,B\subset G$ are finite subsets of $G$. We define $AB:=\{ab |a \in A, b\in B\}$. In a similar fashion we can define $A^2, A^3, \dotsc, A^n,\dotsc$. Now, we say $A$ is a $K$-...
user avatar
2 votes
1 answer
50 views

Finite-index subgroups of dense additive subgroups of $\mathbb R$

Let $A$ be a dense additive subgroup of $\mathbb R$ and let $B\le A$ be a subgroup such that $[A:B]=r<\infty$. I wonder if we have that $B$ is dense in $\mathbb R$ as well. My thoughts: Write $A=\...
user avatar
  • 7,119
8 votes
2 answers
172 views

Syndeticity- and thickness-preserving bijections of $\mathbb N$

Let me recall some definitions: a set $A \subseteq \mathbb N$ is: syndetic if it intersects every large enough interval, i.e. if $\exists \ell \in \mathbb N^* : \forall k \in \mathbb N, A \cap ⟦ k, ...
user avatar
  • 8,525
1 vote
0 answers
46 views

Proof of Roth-Bourgain Theorem

The following question is from Tao and Vu's Additive combinatorics, at which I am stuck and would appreciate some help.These questions are from the proof of Proposition 10.32 (page 392): (Page 394) ...
user avatar
3 votes
2 answers
123 views

Proof of Roth's theorem due to Heath -Brown and Szemeredi

The following question (statement) is from Tao and Vu's Additive combinatorics, at which I am stuck and would appreciate some help. I wish to prove Theorem 10.27 (page 390) using Proposition 10.28 ...
user avatar
2 votes
1 answer
55 views

non-uniformity implies density increment

The following is the proof of Lemma 10.25 (page 388) from Tao and Vu's Additive combinatorics, which I'm stuck at and I could really use some help. The proof begins by taking $P=[1,N]$ and then we use ...
user avatar
0 votes
2 answers
48 views

Sumsets : optimality of two basic inequalities

One can prove that for $A$ and $B$ subsets of $\mathbb{Z}$ one has $$ |A|+|B|-1 \leq |A+B| \leq |A|\times |B| $$ where $A+B = \left\{ a+b,a\in A \text{ and } b \in B \right\}$ and, for $X$ a finite ...
user avatar
  • 3,841
0 votes
1 answer
34 views

Characters of a finite abelian group form pairwise independent random variables.

Z is a finite additive group with a fixed symmetric non-degenerate bilinear form. Let $x$ be an element of $Z$ chosen uniformly at random. Show that the random variables $\{e_{\xi} (x): \xi \in Z\}$ ...
user avatar
  • 1,503
3 votes
1 answer
47 views

Estimation of order of sum-covering subset

This question is from Tao and Vu's book, Exercise 1.1.7., which is part of the chapter "The probabilistic method". The problem is: Problem. Consider a nonempty subset $A$ of finite abelian ...
user avatar
3 votes
0 answers
72 views

Meager or measure zero $A\subset \mathbb R$ with $A+A=A$ and $A-A=\mathbb R$

Is there a meager or measure zero set $A\subset \mathbb R$ with $A+A=A$ and $A-A=\mathbb R$? I am using sumset notation $$A+A=\{a+b:a,b\in A\}$$ $$A-A=\{a-b:a,b\in A\}$$ In more algebraic terms, $A$ ...
user avatar
  • 1,460
1 vote
1 answer
58 views

Roth's Theorem Finitary and Infinitary forms are equal

Theorem1 Let A be a subset of positive integers with positive upper density then A contains a 3 term arithmetic progression. Theorem2 For any $\delta>0$ there exists $N_{0}$ such that for every $N\...
user avatar
  • 13
2 votes
0 answers
106 views

Reference for solved exercises in additive combinatorics

I am aware that additive combinatorics is a relatively new subject and there are not many books available. I will be grateful if anybody can tell me about some source where I can find a few solved ...
user avatar
0 votes
1 answer
74 views

Bipartite graph with density $1/2$ can not be regular

Let $G=(V,E)$ be a (undirected and simplicial) graph and let $A,B\subseteq V$ be two subsets. The density of a pair of subsets $(X,Y)\subseteq A \times B$ is defined as $$d(X,Y):=\frac{|\{\text{edges ...
user avatar
2 votes
1 answer
50 views

Does this combinatorical condition characterize the (kernels of) non-degenerate quadratic forms $q:V\to \mathbb{F}_2$?

Let $V$ be an finite-dimensional vector space over $\mathbb{F}_2$ and let $f:{V\choose 2}\to V$ be the addition map defined by $f(\{x,y\})=x+y$. We are looking for subsets $X\subseteq V$ for which ...
user avatar
  • 7,532
4 votes
1 answer
92 views

Two properties of the set of Bernoulli numbers

Let $\mathcal{B}$ be the set of all Bernoulli numbers. We are looking for an answer for one of the following (or both) questions. (a) Is there an infinite subset $S$ of rationals such that $(\mathcal{...
user avatar
1 vote
0 answers
42 views

Size of translated random subset of an abelian group

Let $Z$ be some finite abelian group. Suppose that we pick a random subset $X$ of $Z$ of size $d$, and define the set $$X^+ = \{\epsilon_1 x_1 + \epsilon_2x_2 + \ldots+\epsilon_dx_d | \forall i\in [d]:...
user avatar
5 votes
0 answers
44 views

Number of lines of $3$ points in an arrangement of points and lines

It is well known that a finite set of $n$ points cannot form more than $$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1 $$ lines that include $3$ points. Would this result still hold if we assume that ...
user avatar

1
2 3 4 5
7