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

learn more… | top users | synonyms

1
vote
2answers
88 views

Generalization of Rado's Single Equation theorem

Yesterday I came up with a problem: Can we color each point of the plane with finitely many colors such that there doesn't exist any monochromatic regular polygonal? But I found the problem is too ...
0
votes
0answers
228 views

Greedy sequences without k-term arithmetic progressions

If $S_k$ is the greedy sequence with no length-k arithmetic subsequence, (ie $S_3$ = A003278 , $S_4$ = A005837 , $S_5$ = A020655 ), is it guaranteed that any other sequence $a$ with no length-k ...
5
votes
1answer
466 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
3
votes
1answer
154 views

Non-asymptotically densest progression-free sets

For the context of this question, a progression-free set is a subset of integers that does not contain length-three arithmetic progressions. For large $N$, it is known that $[N] = \{1, \ldots, N\}$ ...
4
votes
1answer
176 views

Set of small numbers with distinct $k$-sums

Let $A$ be a set of $n$ positive integers with distinct $k$-sums. In other words, if $a_1\le\cdots\le a_k$ and $b_1\le\cdots\le b_k$ are elements of $A$ such that $a_1+\cdots+a_k=b_1+\cdots+b_k$, then ...
1
vote
1answer
276 views

Karolyi's theorem for finite groups and its extensions

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the ...
3
votes
0answers
101 views

Closest sumset to a set

Suppose $A$ is a subset of the finite field with $p$ elements. What is the best approximation of $A$ by a sumset $B+C$ in the sense that $|A\Delta (B+C)|$ is minimal? Of course if $B=A-x$ and ...
22
votes
2answers
1k views

The Erdős-Turán conjecture or the Erdős' conjecture?

This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics: Conjecture: If $A\subset \mathbb{N}$ ...
3
votes
2answers
121 views

A measure of closure under sumset?

Let $G$ be an Abelian group. Let $A \subseteq G$. In additive combinatorics, one of the primary measures of the additive structure of $A$ is its additive energy, defined as $E(A) = ...
4
votes
2answers
413 views

Average involving the Euler phi function

Does $$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$ converges or not when $N$ goes to infinity?
1
vote
1answer
162 views

Distribution of colors in the number of integer partitions of n

Given an integer $n$ the number of partitions of $n$ into two colors can be represented as $$p_2(n)=\sum_{k=0}^n p(k)p(n-k)$$ where $p(k)$ counts the number of ordinary partitions of $k.$ What is the ...
5
votes
1answer
462 views

Additive Combinatorics - reference request

Let $A$ be a finite set of integers with $|A \hat{+} A| \leq K|A|$, where the $\hat{+}$ denotes restricted sumset: the set of all $a_1 + a_2$ with $a_1, a_2 \in A$ and $a_1 \neq a_2$. Claim: $|A + ...
1
vote
0answers
155 views

Estimates for the size of the product set [n].[n] [duplicate]

Possible Duplicate: Number of elements in the set {1,…,n}*{1,..,n} Writing $[n]$ for the set $\lbrace1,2,...,n\rbrace$, let $P_n$ denote the product set $[n].[n]$, i.e. $$ P_n = ...
0
votes
2answers
249 views

Solution in distinct elements for a system of $n$ equations over finite fields

The following problem is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. Problem: Let $\{y_1 , y_2 , \dots, y_n \}$ be arbitrary (distinct) ...
13
votes
1answer
747 views

On the $L^1$-norm of certain exponential sums.

I am stuck with an elementary-looking problem, which does not belong to my usual field of research so I eventually decided to ask it on MO. Let $S$ be a finite set of integers. For $P$ a subset of ...
3
votes
1answer
146 views

existence of arithmetic progression of nonzero density

This is a stronger version to Szemerédi's theorem. Let $C : \mathbb{N}\rightarrow 2^{\mathbb{N}}$ be a choice function such that $C(n)$ is a subset of $\{1,...,n\}$ with size at least $\frac{n}{M}$ ...
0
votes
0answers
32 views

Minimum number of solutions in a system of equalities and non-equalities

Let $k<N$ and $P_1, ..., P_{2k+1}, \lambda_1, ..., \lambda_k$ be elements of a finite group $G$ of size $N$. Find the minimum number of solution of the system $$P_{2i} + P_{2i+1} = \lambda_i, ...
1
vote
1answer
313 views

About a sumset in $\mathbb{Z}_{2k}$

Suppose $U\subset\mathbb{Z}_{2k}$ with $|U|=k$. Let $U^c$ denote the complement of $U$. Let $v\in \mathbb{Z}_{2k}^{\times}$. How much is it known about $U+vU^c$? For example: When $U+v\complement U ...
3
votes
0answers
114 views

Bounds on difference sets of relatively dense A \subseteq {1, …, n}

Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like ...
4
votes
3answers
578 views

Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

I have an optimization problem where I need to select $k$ integers over the interval $[0, N]$ s.t. I maximize the minimum difference between any pairwise sum of the $k$ integers (where we also include ...
19
votes
0answers
402 views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
1
vote
1answer
361 views

Generalizations of Cauchy-Davenport Theorem

The Cauchy-Davenport Theorem says that if $A_1, \ldots, A_k$ are subsets of ${\mathbb Z}_p$, $p$ prime, then $| \sum_i A_i | \geq \min (p, \sum_i |A_i| -k +1)$. I am looking for a generalization that ...
0
votes
1answer
84 views

sum of a binomial-weighted entity

Does anybody know a closed-form solution for the following expression (N>=1)? I don't even know where to begin with the i+n denominator. Sum of i=0 to n Combin(n,i) * (2i/(i+n)) / (2^n)
4
votes
0answers
384 views

Largest set of integers without 3-term arithmetic progressions mod $n$

I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b ...
6
votes
1answer
254 views

Recovering Sidon sets from difference sets, part 2.

This is inspired by a recent question. A set $A \subset \mathbb{Z}/n\mathbb{Z}$ with $|A|=m$ is a Sidon set if all the pairwise sums of distinct elements are unequal: $A+A=\{a+a' \mid a,a' \in A, a ...
2
votes
2answers
365 views

Recovering Sidon sets from difference sets

How can I recover a Sidon set $A\subseteq \mathbb{Z}/n\mathbb{Z}$ from the set $A-A\subseteq \mathbb{Z}/n\mathbb{Z}$? Is it even unique? (up to translation and reflection) ($A-A$ stands for the set ...
4
votes
1answer
229 views

Additive energy of random sets

Given two random sets $A,B$ in a finite field (say $x\in A$ independently and with probability $1/2$), what is known about the additive energy $E(A,B)=|\{(a,a',b,b')\in A\times A\times B\times B: ...
0
votes
0answers
147 views

upper bound on the size of sumset of lattice points

Let $\Lambda$ be a lattice (discrete additive subgroup) in $\mathbb R^n$ ($n\geq 2$). In my problem, $\Lambda$ lies in a $k$ dimensional ($1< k\leq n$) subspace of $\mathbb R^n$. Let $A\subset ...
1
vote
1answer
143 views

Is there a function that determines the rank of a multiset after inserting another element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements. The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ...
3
votes
1answer
333 views

Additive set with small sum set and large difference set

I have a question! Can someone explain how (the intuition, method?) one can try to construct an additive set of cardinality $N$ with a small sum set (around $N$) and a very large difference set ...
27
votes
2answers
2k views

Number of elements in the set $\{1,\cdots,n\}\times\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
5
votes
1answer
746 views

Graham-Rothschild via Hales-Jewett

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild ...
9
votes
0answers
538 views

Cliques in the Paley graph and a problem of Sarkozy

The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously ...
0
votes
0answers
545 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
4
votes
3answers
329 views

L^2-Flattening Lemma

I am reading a significant paper of Bourgain and Gamburd on "Uniform expansion bounds for Cayley graphs of $\mathrm{SL}_2(\Bbb{F}_p)$". They have proven a proposition which in their new papers they ...
3
votes
2answers
813 views

There exists B subset A, |B| = log n, A \cap 2*B = \emptyset

This is exercise 1.8.1 of Additive Combinatorics. Problem Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \Omega ( \log n )$, s.t. $A \cap 2*B = ...
3
votes
0answers
211 views

Convex subsets of sumsets

There's a famous old problem in additive number theory which asks whether, for any $\epsilon > 0$, if $B$ is a 2-basis for the set $A =$ {$1^2,2^2,...,n^2$}, i.e.: a set for which $B+B \supseteq ...
2
votes
0answers
112 views

Lower bound on P(Y > 3/2 E(Y)) where Y = # of triangles in graph

Context This is exercise 1.7.1 of Tao/Vu's Additive Combinatorics, generally considered a graduate level math textbook. My question is not "How do I solve this exercise?" My question is "What is ...
3
votes
0answers
124 views

Other interesting examples of pseudo-random measures

Here we use the notion of pseudo-randomness (or variant of) used in the proof of the Green-Tao theorem. In particular, we say a measure $\nu : \mathbb{Z}_N \rightarrow \mathbb{R}^+$ is pseudo-random ...
7
votes
2answers
319 views

Elementary Proof of Basis of Order k

Context According to the FAQ, questions of the form "the sorts of questions you come across when you're writing or reading articles or graduate level books" are acceptable. This falls into the ...
1
vote
1answer
234 views

Technique: Compactness => (Finite -> Reals)

Context I'm studying a classical results of Erdos and Lovasz, on colorings of the real line. The theorem to be proved is as follows: Let $m, k$ be two positive integers satisfying: ...
10
votes
0answers
482 views

What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is ...
0
votes
0answers
268 views

Kakeya problem and arithmetic progressions

Here's something I also posted on Stackexchange recently. It's very related to the Kakeya problem, yet I fail to see why this is true. It goes like this: Let $r > 2$ be an integer parameter. Let ...
8
votes
3answers
589 views

A simple looking problem in partitions that became increasingly complex

I began with problem which looked simple in the beginning but became increasingly complex as I dug deeper. Main questions: Find the number of solutions $s(n)$ of the equation $$ n = \frac{k_1}{1} + ...
23
votes
3answers
824 views

Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
4
votes
1answer
474 views

Ruzsa-type inequalities for additive energy

As the subject says, I have some questions about some Ruzsa-type inequalities for additive-energy. It would be wonderful if anyone could shed some light. First, the definition: let $E(A,B)$ be the ...
23
votes
3answers
1k views

long enough interval of integers to solve a simultaneous congruence

Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ ...
3
votes
1answer
245 views

Bounds on pseudosquares

Suppose $n\in\mathbb{Z}^+$ is a nonsquare in $\mathbb{Z}$ but is a square mod $2^2,3^2,4^2,5^2,\ldots,k^2.$ How small can $n$ be? On the ERH, there are no small pseudosquares: ...
9
votes
1answer
690 views

Is it known that $(F_p^{\times} \ltimes F_p, F_p)$ is not a relative expander family?

Shalom [edit: originally M. Burger] showed that the pair $(\mathrm{SL}_2(\mathbb{Z}) \ltimes \mathbb{Z}^2, \mathbb{Z}^2)$ has Relative Property (T) with respect to standard generating sets. (The ...
1
vote
0answers
109 views

Examples of using additive structure to analyze size of a set mod some ideal?

There are examples of proofs that analyze the structure of some set $S$ of integers by looking at the size of the set mod some positive integer $n$ (for example, the $3k-3$ theorem.) Are there ...