Tagged Questions

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

119 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 ...
129 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 ...
337 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 "...
259 views

967 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 ...
569 views

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 ...
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$ ...
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: $L_p>e^{\sqrt{p/2}}$....
718 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 ...
123 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 ...
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 ...
457 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 ...
631 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 ...
489 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 ...
824 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. ...
350 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 ...
531 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 ...
526 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 ...
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 ...
879 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 ...
644 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 Erdos-...
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) ...
545 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 ...
891 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.: ...
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 ...
633 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 ...
256 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 ...
699 views

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