## 507- Plünnecke inequalities and sumset estimates

February 10, 2011

George Petridis, a student of Gowers, has found very nice new arguments for the Plünnecke-Ruzsa sumset inequality (If $A$ is a finite subset of an Abelian group $G$, and ${}|A+A|\le C|A|$, then ${}|kA-lA|\le C^{k+l}|A|$ for any $k,l\in{\mathbb N}$) and for the Plünnecke graph inequalities.

In lecture we went through the nice standard argument. But the new proofs are significantly simpler. For example, the graph inequalities are no longer needed for the sumset ones, and Menger’s theorem is no longer needed fro the graph inequalities. Gowers has posted the nice proof in his blog, with links to Petridis’s papers on the ArXiv.

## 507- Problem list (IV)

January 21, 2011

For Part III, see here.

(Many thanks to Robert Balmer, Nick Davidson, and Amy Griffin for help with this list. If you have corrections/updates, please email me. Sorry for the delay with posting this.)

• Is there a dense subset of ${\mathbb R}^2$ with all pairwise distances rational?
• Is every polygonal region illuminable?
• Does the odd greedy expansion for Egyptian fractions terminate?
• Erdős conjecture on arithmetic progressions.
• Is ${\mathbb Z}$ existentially definable in ${\mathbb Q}$? (And similar extensions of Hilbert’s tenth problem. See also this question on MathOverflow.)
• Is any/none algebraic irrational real-time computable?
• Do perfect boxes exist?
• The lonely runner conjecture. (See also these posts by R. Lipton: 1, 2.)
• Hadwiger conjecture on convex bodies.
• What is the maximum number of points that can be placed in an $n\times n$ grid so that no three of them are collinear?
• Can we characterize Euclidean Ramsey sets?
• The Riemann hypothesis.

## 507- Problem list (III)

January 20, 2011

For Part II, see here.

(Many thanks to Robert Balmer, Nick Davidson, and Amy Griffin for help with this list.)

• The Erdös-Turán conjecture on additive bases of order 2.
• If $R(n)$ is the $n$-th Ramsey number, does $\lim_{n\to\infty}R(n)^{1/n}$ exist?
• Hindman’s problem: Is it the case that for every ﬁnite coloring of the positive integers, there are $x$ and $y$ such that $x$, $y$, $x + y$, and $xy$ are all of the same color?
• Does the polynomial Hirsch conjecture hold?
• Does $P=NP$? (See also this post (in Spanish) by Javier Moreno.)
• Mahler’s conjecture on convex bodies.
• Nathanson’s conjecture: Is it true that ${}|A+A|\le|A-A|$ for “almost all” finite sets of integers $A$?
• The (bounded) Burnside’s problem: For which $m,n$ is the free group $B(m,n)$ finite?
• Is the frequency of 1s in the Kolakoski sequence asymptotically equal to $1/2$? (And related problems.)
• A question on Narayana numbers: Find a combinatorial interpretation of identity 6.C7(d) in Stanley’s “Catalan addendum” to Enumerative combinatorics.

## 507 – Homework 3

October 24, 2010

This set is due Monday, November 8.

## 507 – Problem list (II)

October 16, 2010

For the beginning of the list, see here.

• Collatz conjecture, or the $3n+1$ problem.
• The sum-product problem.
• Is there a polynomial $p\in{\mathbb Q}[x,y]$ such that $p[{\mathbb Z}^2]={\mathbb N}$?
• The Bombieri-Lang conjecture and the closely related question by Friedman/Ziegler of whether there is a polynomial $p\in{\mathbb Q}[x,y]$ that maps ${\mathbb Q}^2$ injectively into ${\mathbb Q}$.
• The inscribed square problem.
• Are the values of the $\zeta$ function at the odd positive integers irrational?
• Schanuel’s conjecture.
• David Gale’s subset take-away problem.
• The Jacobian conjecture.

## 507 – Homework 2

September 29, 2010

This set is due Monday, October 18.

## 507 – Problem list (I)

September 21, 2010

This is the list of “problems of the day” mentioned through the course.

(Thanks Nick Davidson and Summer Hansen.)

• Frankl’s union-closed sets problem: If a finite collection of finite non-empty sets is closed under unions, must there be an element that belongs to at least half of the members of the collection?
• The inverse Galois problem: Is every finite group a Galois group over ${\mathbb Q}$?
• 1. Are there infinitely many Mersenne primes? 2. Are there infinitely many Fermat primes?
• For every positive $n$, is there a prime between $n^2$ and $(n+1)^2$?
• Does the dual Schroeder-Bernstein theorem imply the axiom of choice?
• The SchinzelSierpiński conjecture: Is every positive rational of the form $(p+1)/(q+1)$ for some primes $p$ and $q$? (The links require a BSU account to access MathSciNet.)
• Are there infinitely many twin primes?
• Are there any odd perfect numbers?
• Is the Euler-Mascheroni constant $\gamma$ irrational?
• Is $2$ a primitive root modulo $p$ for infinitely many primes $p$? More generally, does Artin’s conjecture hold?