**1**

vote

**1**answer

161 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

**1**answer

453 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

**0**answers

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

**2**answers

248 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

**1**answer

733 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

**1**answer

145 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

**0**answers

31 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

**1**answer

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

**0**answers

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

**3**answers

568 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

**0**answers

393 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

**1**answer

353 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

**1**answer

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

**0**answers

378 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

**1**answer

253 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

**2**answers

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

**1**answer

227 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

**0**answers

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

**1**answer

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

**1**answer

326 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

**2**answers

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

**1**answer

744 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

**0**answers

531 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

**0**answers

533 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

**3**answers

324 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

**2**answers

812 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

**0**answers

209 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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

476 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

**0**answers

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

**3**answers

588 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} + ...

**22**

votes

**3**answers

780 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

**1**answer

468 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

**3**answers

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

**1**answer

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

**1**answer

687 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

**0**answers

108 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

**2**answers

636 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

**2**answers

289 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

**2**answers

585 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

**1**answer

437 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

**3**answers

767 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

**0**answers

320 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

**1**answer

471 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

**2**answers

489 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

**1**answer

970 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

**3**answers

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