**3**

votes

**1**answer

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

**10**

votes

**1**answer

716 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

122 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

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

**6**

votes

**3**answers

453 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

627 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

487 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

817 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

347 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

527 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

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

**23**

votes

**1**answer

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

874 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

635 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

541 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

889 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

378 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

632 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

254 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

696 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

400 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

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

**16**

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

396 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

967 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

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

**5**

votes

**1**answer

312 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

205 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

126 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

295 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

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

**10**

votes

**3**answers

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

677 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

318 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

509 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

331 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

706 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

393 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

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

**16**

votes

**3**answers

948 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

711 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

753 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

300 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

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