## 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?

## 507 – Homework 1

September 2, 2010

This set is due Monday, September 13.

## 507 – Advanced Number Theory (Syllabus)

May 14, 2010

Section 1.
Instructor:
Andrés E. Caicedo.
Contact Information: See here.
Time: MWF 12:40-1:30 pm.
Place: M/G 124.
Office Hours: MF 11:40 am-12:30 pm 10:40-11:30 am (or by appointment).

The (admittedly impossible) goal is to discuss the following topics:

1. Divisibility
2. Congruences
3. Primitive roots
5. Prime numbers
6. Waring’s problem
7. Geometry of numbers
8. Transcendental number theory
10. Integer partitions

Recommended background: Mathematics 306: Number theory, or equivalent. It is highly desirable that you have taken prior courses in analysis and abstract algebra.

Textbook: Elementary methods in number theory. By Melvin Nathanson. Springer-Verlag (2000), ISBN: 0-387-98911-9.

At the end, this was a matter of personal taste, as my list of topics leans more towards the “analytic” than the “algebraic” side of things. This list is somewhat nonstandard. Here are some additional suggested references, both for the course and for number theory in general. I will add suggestions through the course, depending on the topic being covered:

1. A classical introduction to number theory. By Kenneth Ireland and Michael Rosen. Springer-Verlag (1990), ISBN: 0-387-97329-X. Highly recommended, this could have been our textbook.
2. Algebraic number theory and Fermat’s last theorem. By Ian Stewart and David Tall. A K Peters (2002), ISBN: 978-1568811192. This would be a nice textbook for a first course in algebraic number theory, but it requires background in Galois theory.
3. Multiplicative number theory. By Harold Davenport, revised by Hugh Montgomery. Springer-Verlag (2000), ISBN: 0-387-95097-4. This is a very nice book, but it definitely requires background in complex analysis.
4. Making transcendence transparent: an intuitive approach to classical transcendental number theory. By Edward Burger and Robert Tubbs. Springer-Verlag (2004), ISBN: 978-0387214443.
5. Additive number theory: The classical bases. By Melvyn Nathanson. Springer-Verlag (1996), ISBN: 978-0387946566.
6. Additive number theory: Inverse problems and the geometry of sumsets. By Melvyn Nathanson. Springer-Verlag (1996), ISBN: 0-387-94655-1.
7. Integer partitions. By George Andrews and Kimmo Eriksson. Cambridge University Press (2004), ISBN: 0-521-60090-1. Andrews also authored a more advanced textbook on partition theory, that requires complex analysis.