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

3
votes
1answer
144 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
30 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
113 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
559 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
382 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
351 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
83 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
375 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
252 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
364 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
224 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
142 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
320 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
742 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
529 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
516 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
320 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
811 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
206 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
111 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
120 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
318 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
229 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
473 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
261 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
587 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} + ...
21
votes
3answers
775 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
463 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
686 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
106 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 ...
12
votes
2answers
629 views

Zero-sum partition of an abelian group

This is a question I have been asking myself some 5 years ago. I later got bored by lack of progress, but maybe some additive combinatorialists here know further. I'm not claiming it is conceptual or ...
4
votes
2answers
286 views

Conditions for an analogue of Cauchy-Davenport for simple groups

What conditions would be sufficient for a generalization of Cauchy-Davenport for simple groups? I can see two possible difficulties with a generalization for general groups: The sets could both be ...
4
votes
2answers
583 views

How local the property of “being a partition” is?

Note: The problem is solved! See EDIT below. The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the ...
4
votes
1answer
430 views

Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now. The most ...
10
votes
3answers
763 views

Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there? I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem. ...
6
votes
0answers
317 views

Small maximal sets with no 3-AP?

Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the smallest maximal ...
15
votes
1answer
469 views

The hypercube: $|A {\stackrel2+} E| \ge |A|$?

I have a good motivation to ask the question below, but since the post is already a little long, and the problem looks rather natural and appealing (well, to me, at least), I'd rather go straight to ...
4
votes
2answers
487 views

A weighted sum of non-negative integers

Suppse $n > m$ are positive integers. Then it is an elementary exercise to show that the number of $m$-tuples of non-negative integers $(x_1, \cdots, x_m)$ such that $x_1 + \cdots + x_m = n$ (order ...
22
votes
1answer
967 views

Arithmetic Progressions of Squares

Fermat may or may not have known that there are 3-term arithmetic progressions of squares (like $1^2, 5^2, 7^2$, and that there are no 4-term APs. Murky history aside, Keith Conrad has two pleasant ...
7
votes
3answers
794 views

Binomial coefficient in Andrews' partition book

First of all, i think MathOverflow is a very great community to discuss math, either basic or advanced, and i'm glad to participate here. It's my first post, so i'm sorry if i did anything wrong, and ...
6
votes
1answer
567 views

Relationship between Erdos and Falconer distance problems

Given a set $E \subset \mathbb{R}^d$, define the distance set of $E$ $$ \Delta(E) = \lbrace|x-y| : x,y \in E \rbrace, $$ where $|\cdot |$ is the usual Euclidean distance. $\bullet$ The ...
19
votes
3answers
1k views

Can nonabelian groups be detected “locally”?

Suppose $m,n\geq 2$ are two integers. Is it true that for every sufficiently large nonabelian group $G$, one can find a set $A\subset G$, with $|A|=n$, so that $|A^m| >\binom{n+m-1}{m}$? (Edit) ...
6
votes
1answer
474 views

Minimum cardinality of a difference set in $R^n$

Cross-posted from http://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn. Given a finite set $S$ of $m$ points in $\mathbb R^n$ that do not all lie in the ...
17
votes
3answers
813 views

An “Average” Erdős–Turán conjecture

Right, so the Erdős–Turán conjecture for additive bases (of order 2) says, with the usual notations, that $\sup r_B (n) = \infty$. Let’s look instead at the average number of representations, i.e.: ...
3
votes
1answer
366 views

Optimize / simple Set Covering Problem

Let $k,m\in\mathbb{N}$ be given. Let $M:=\{0,... , m-1\}$. How to find a subset $T\subset M$, $|T|=k$ such that $|T+T|$ is maximal, where $T+T=\{ (a+b)\mathbin\%m \mid a\in T,b\in T \}$ (“%” means ...