**7**

votes

**3**answers

840 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

622 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

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

**1**answer

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

**18**

votes

**3**answers

885 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

375 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

627 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

251 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

692 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

391 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

587 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

1k 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

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

**19**

votes

**4**answers

2k 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

963 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

353 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

311 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

200 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

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

**1**

vote

**1**answer

125 views

### In what cases are the counting function and representation functions strongly related?

Let $A \subset \mathbb{N}$ be a subset of the natural numbers and $h > 0$ be a natural number. Let $a(n) = |A \cap [1,n]|$ be the counting function of $A$, and let $r_{A,h}(n)$ be the number of ...

**6**

votes

**2**answers

293 views

### Known additive bases with irregular counting function

For $A \subset \mathbb{N}$ and positive integer $h > 0$, define $r_{A,h}(n)$ to be the number of ways to write $n$ as the sum of $h$ (not necessarily distinct) elements of $A$. We say $A$ is an ...

**4**

votes

**1**answer

362 views

### How large can a non-sumset be?

The theory of sumsets $A+B$ where $A$ and $B$ are finite subsets of an additive group $Z$ is extensively studied in additive combinatorics: finding long arithmetic progressions inside them, finding ...

**8**

votes

**1**answer

553 views

### When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

As a natural (and expectable) extension of my earlier question:
How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, ...

**12**

votes

**2**answers

625 views

### Arithmetic progressions modulo $p$ under the squaring map

I feel that the following problem should be known, but I'm not sure where to look for it.
Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...

**7**

votes

**1**answer

284 views

### When does $P(a-b)=0$ for $a\ne b$ ensure $P(0)=0$?

Let $n$ be a positive integer. How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a quadratic polynomial in $n$ variables, vanishing at all non-zero points of the sumset ...

**5**

votes

**3**answers

508 views

### Any rigorous way to claim that sums with repeat summands are few?

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...

**7**

votes

**2**answers

1k views

### Recent results on the Gauss circle problem?

Possible Duplicate:
What is the status of the Gauss Circle Problem?
The Gauss circle problem is the following: Let $N(r)$ denote the number of solutions in integer pairs $(i,j)$ to the ...

**4**

votes

**0**answers

330 views

### A question about Erdos thin bases

Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order ...

**11**

votes

**2**answers

686 views

### Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...

**6**

votes

**1**answer

380 views

### Arbitrarily thin additive bases of the natural numbers

A subset $A$ of $\mathbb{N}$ is called a basis of order $k$ if the set $kA$ = {$a_1 + \cdots + a_k | a_1, \cdots, a_k \in A$} $= \mathbb{N} \setminus C$, where $C$ is a finite set of positive ...

**5**

votes

**1**answer

576 views

### A question on the singular series and singular integral in Hardy-Littlewood Circle Method

Given a set $A$ of positive integers, set $r_{A,h}(N)$ to be the number of $h$-tuples $(a_1, \cdots, a_h)$ such that $N = a_1 + \cdots + a_h$. Set $f(z) = \sum_{a \in A} z^a$. Then by Cauchy's Theorem ...

**14**

votes

**3**answers

912 views

### The sum of integers being a bijection

What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...

**6**

votes

**2**answers

694 views

### Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density

It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...

**11**

votes

**2**answers

747 views

### Did Erdős publish his proof of the multiplicative version of the Erdős-Turán conjecture?

I read in an article of Erdős ("Extremal problems in number theory") that he had a proof of the multiplicative version of the Erdős-Turán conjecture. The statement of this theorem is
Let $a_1 < ...

**4**

votes

**1**answer

298 views

### Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?

The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that:
Theorem. If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq ...

**2**

votes

**2**answers

1k views

### Almost periodic functions in Tao's ergodic proof of Szemerédi's theorem

Do we say that a function $f$ is uniformly almost periodic in the aforementioned proof if $f$ is bounded (in the sense that $||f||_{L^\infty}\leq 1$) and that there exists a natural number $d>0$ ...

**30**

votes

**4**answers

2k views

### Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...

**15**

votes

**3**answers

1k views

### What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...

**6**

votes

**1**answer

366 views

### Upper bound for size of subsets of a finite group that contains a sum-full set

Problem
I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:
Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we
define $k(G)$ be ...

**11**

votes

**7**answers

866 views

### describe subsets of the integers closed under the binary operation Ax+By

Could one describe the subsets of the integers closed under the binary operation Ax+By
where A and B are arbitrary fixed integers ? That is, describe the subsets S
of the integers such that if ...

**3**

votes

**1**answer

1k views

### Queries about the Skolem-Mahler-Lech theorem (integer zeros of exponential polynomials)

The Skolem-Mahler-Lech Theorem says that the integer zeros of an exponential polynomial are the union of complete arithmetic progressions and a finite number of exceptional zeros. ...

**7**

votes

**1**answer

627 views

### Homogeneous arithmetic progressions in difference sets

I have a nasty feeling that I ought to be able to answer this question, but I've got other things to think about right now and I'm interested in the answer just so that I can reply to a mathematical ...

**4**

votes

**1**answer

536 views

### Cauchy-Davenport strengthening?

Is the following statement, refining classical Cauchy-Davenport Theorem (that states that for sets $A$, $B$ of residues modulo prime $p$, $|A+B|\geq |A|+|B|-1$ provided that RHS does not exceed $p$) ...

**6**

votes

**1**answer

857 views

### Additive combinatorics and large Fourier coefficients

Elon Lindenstrauss explains in his talk at the MSRI in Fall 2008 (the relevant comment is at minute 41 of the video) that the set of large Fourier coefficients of a probability measure $\mu$ on the ...

**4**

votes

**2**answers

506 views

### Sum of sets modulo a square

I would be glad to see a reference to the following easy lemma in additive combinatorics: if $A_1$ and $A_2$ are two sets of remainders modulo $n^2$, each has cardinality $n > 1$ and all elements ...

**20**

votes

**1**answer

2k views

### Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...

**7**

votes

**1**answer

441 views

### A variation of Minkowski sum

I have to work with the following variation of Minkowski sum:
Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$.
Set
$$K^+=\{\\,x+y\in\mathbb ...

**2**

votes

**3**answers

218 views

### Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances ...

**14**

votes

**1**answer

628 views

### Goldbach-type theorems from dense models?

I'm not a number theorist, so apologies if this is trivial or obvious.
From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...

**5**

votes

**2**answers

405 views

### k-pseudorandom measures

In reading the paper of Green and Tao on arithmetic progressions within the primes, I became very interested in the notion of a k-pseudorandom measure discussed in that paper.
A measure here is a ...