**1**

vote

**1**answer

135 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

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

**25**

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

732 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

525 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

468 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

314 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

804 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

205 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

108 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

117 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

224 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

452 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

258 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

585 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

**3**answers

755 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

440 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

244 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

659 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

102 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

625 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

278 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

574 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

420 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

757 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

311 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

463 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

483 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

941 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

770 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

**1**answer

546 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

**3**answers

978 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

**1**answer

439 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

**3**answers

785 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

**1**answer

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

**2**

votes

**3**answers

618 views

### Arithmetic progressions of length 3 in subset of Z_n of size n^d

Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0< d <1$).
Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$.
[The ...

**2**

votes

**0**answers

247 views

### Prime divisors of the difference set

Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few ...

**4**

votes

**1**answer

647 views

### Size of Sum Sets

Let $\{a_{k}\}$ be an increasing sequence of positive real numbers. Let us define $A_{n}:=\{a_1,\ldots,a_{n}\}$ and consider the set
$$
S_{n}^{(2)}=\Big \{(x_1,x_2,x_3,x_4)\in ...

**5**

votes

**1**answer

376 views

### Fourier analysis, orthogonality, and Plancherel for finite abelian groups

I am reading an outstanding paper by Bateman and Katz, improving the best known bounds on the cap set problem (Roth's theorem over $\mathbb{F}_3^N$).
The paper contains some technical lemmas for ...

**5**

votes

**0**answers

540 views

### Expectation of Gowers norm

This was a problem that came up during a course on Analytic Combinatorics that I had taken this semester. Here's the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \mathbb{F}_2^n ...

**15**

votes

**2**answers

913 views

### Roth's theorem and Behrend's lower bound

Roth's theorem on 3-term arithmetic progressions (3AP) is concerned with the value of $r_3(N)$, which is defined as the cardinality of the largest subset of the integers between 1 and N with no ...

**5**

votes

**3**answers

375 views

### Structure of nonaveraging sets of integers

A set of integers is said to be nonaveraging if it contains no three-term arithmetic progression. I call a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ optimal when it has maximal ...

**17**

votes

**4**answers

1k views

### Arithmetic progressions inside polynomial sets

There are at most 3 perfect squares in arithmetic progression (Fermat, Euler). It was shown in [1] that if $n>2$ there are no three term arithmetic progression consisting of nth powers.
Take a ...

**2**

votes

**0**answers

934 views

### Fun question in additive combinatorics

It is easy to see that for a finite set of integers $A$ of cardinality $n$, the cardinality of the sumset $A+A$ satisfies
$$
2n-1\leq |A+A|\leq \frac{n(n+1)}{2}.
$$
The lower bound is essentially ...

**6**

votes

**1**answer

338 views

### Bounds on the size of sets not containing a given finite pattern

Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, ...

**4**

votes

**1**answer

286 views

### Thin subbases for the primes?

Hi all,
My question concerns a general problem concern the Erdos-Turan conjecture on additive bases; that of finding thin subbases in a given basis. For a given $A \subset \mathbb{N}$, define ...

**4**

votes

**1**answer

191 views

### Methods to determine whether a given set is the sum of other sets

In Tao and Vu's Additive Combinatorics, it is mentioned that "if we replace the additive set $A$ by a larger set, such as $A+B$, $A+A+A$, or $2A - 2A$, then one can locate significantly larger ...

**3**

votes

**2**answers

880 views

### Choice of normalization of the finite Fourier transform

Let $f : \mathbb{Z}/N\mathbb{Z} \rightarrow \mathbb{C}$ be a function. Is its Fourier transform typically defined by
$$\widehat{f}(\xi) = \sum_{x \in \mathbb{Z}/N \mathbb{Z}} f(x) e^{- 2 \pi i x \xi ...