Mathematics additive combinatorics

Mathematics additive combinatorics
Project description
Must be typed by Latex for those mathematical symbols. And follow the instructions I upload.<br />
There are totally 24 topics to choose and just one needed. so you can choose anyone you think is easy to finsh with high quality.

ADDITIVECOMBINATORICS:FINALPROJECT
LEO GOLDMAKHER
In lieu of a final exam, you will write an expository paper on an interesting theorem or question
related to additive combinatorics. The paper should be aimed at your peers, and should be easy
to read for your classmates. Your goal is give as much insight into the theorem and the proof as
you can in 5–10 pages. The paper should explain what the theorem says, give some motivation,
and outline the proof. Some examples of expository mathematical writing can be found on my
webpage:
www.math.toronto.edu/lgoldmak/
Here are some common ways to write about a theorem. For motivation, you might talk about the
history of problem, you might give an application of the theorem, or you might compare it to other
theorems. If the statement of the theorem is hard to absorb, you could explain what it says in a
particular example. (It is always a great exercise to generate your own examples; in the end, you
may decide that the ‘well-known’ examples are better than the ones you came up with, but it’s also
possible that your examples will be more interesting, and in any event your work will allow you to
better appreciate the theorem and existing examples.) You could also give counterexamples which
show why all the hypotheses of the theorem are necessary or why the conclusion is not stronger. If
there are open problems related to the theorem, you could mention those. Then you should write
something about the proof – I don’t necessarily need all the details, but I do require that you at
least write a clear outline of the argument. Some common ways to try to understand a proof are to
prove a special case of the theorem in which the ideas are all present but some technical aspects are
suppressed (e.g. our proof of Ruzsa’s theorem for groups of finite exponent). Alternatively, you
could prove something in a similar spirit but more elementary. Conversely, you could try to explain
why the proof is difficult – why isn’t there an easier proof? It’s up to you to figure out which of
these options gives the most insight into your theorem / problem. You may pick your own topic;
I’ve included a list of possible topics on the next page, in case you need some inspiration. In terms
of researching your topic, two websites which are particularly helpful are
www.arxiv.org
and
www.ams.org/mathscinet/
(the latter is only usable from a U of T network).
The paper must be
typed up
and submitted by email to me at
lgoldmak@math.toronto.edu
The deadline for submission is April 19th. A particularly convenient way to type mathematical text
is to use L
A
T
E
X. If you wish to try it, I would be happy to help you set it up. To get started, you
need to download miktex (it’s a free download, although it is a very large file and takes some time
to download). Then I can send you some sample L
A
T
E
Xfiles for you to play around with. There are
a lot of excellent resources available online to help you, as well.
On the next pages are a list of possible topics, but you should feel free to find your own; any topic
which inspires you is fine, so long as it’s at least tangentially related to additive combinatorics.
Date
: March 19, 2014.
I am indebted to Larry Guth, who gave a similar assignment in his graduate analysis course at U of T.
S
OME
P
OSSIBLE
T
OPICS
:
(1)
Higher order Fourier analysis (see Balazs Szegedy’s paper on arxiv)
(2)
van der Waerden’s theorem, the Hales-Jewett theorem, and monochromatic subsets. An
open problem in this area is: color the integers using a finite number of colors. Must there
exist integers
x
and
y
such that
x
+
y
and
xy
are the same color? The answer is yes:
x
=
y
= 2
. But if you exclude this trivial example, it’s an open question. You may find
Soundararajan’s course notes on additive combinatorics (freely available on his Stanford
homepage) helpful as a starting point.
(3)
Szemer
´
edi-Trotter and other incidence theorems from geometry, and their applications to
sum-product. (Zeev Dvir has a long write-up on the subject, which you could use as a
starting point.)
(4)
Applications of sum-product theorems to computer science. (You may wish to look at the
expositions on the subject by Shachar Lovett, Emanuele Viola, and the Princeton mini-
course on Additive Combinatorics.)
(5)
More sums than differences – when does a set
A
satisfy
j
A
+
A
j
>
j
A
A
j
? See recent
papers (on the arxiv) by Steven J. Miller et al.
(6)
The multiplication table problem and generalizations; see the PhD thesis of Dimitris Kouk-
oulopoulos (available on his homepage), as well as work of Kevin Ford.
(7)
S
´
ark
?
ozy’s conjecture on non-decomposability of quadratic residues as a sumset; see the
recent paper on the arxiv by Blackburn, Konyagin, and Shparlinski for a starting point.
(But there has been a lot of other work on the subject you should look at.)
(8)
Sidon sets (e.g. see the paper
Combinatorial problems in finite fields and Sidon sets
by
Javier Cilleruelo).
(9)
The generalization (by Ben Green and Imre Ruzsa) of Freiman’s theorem to arbitrary
abelian groups
(10)
Theorem:
Every large subset of
Z
=p
Z
can be written in the form
A
+
A
. This is originally
a result of Ben Green; see
Large sets in finite fields are sumsets
by Noga Alon for more
current results.
(11)
Khovanskii’s theorem: given any finite
A
Z
, there exists a polynomial
f
A
(
x
)
such that
j
nA
j
=
f
A
(
n
)
for all sufficiently large
n
. See the paper by Jelinek and Klazar on the arxiv,
or Ruzsa’s notes
Sumsets and Structure
.
(12)
The Green-Tao theorem: there exist arbitrarily long arithmetic progressions of primes. See
the recent exposition by David Conlon, Jacob Fox, and Yufei Zhao on the arxiv.
(13)
The Breuillard-Green-Tao theorem: a generalization of Freiman’s theorem to arbitrary
(non-abelian) groups. (See their paper.)
(14)
Harald Helfgott’s work on SL
2
; see section 4 of Ben Green’s survey paper
Approximate
groups and their applications
on the arxiv.
(15)
Bourgain’s proof of the existence of long arithmetic progressions in
A
+
B
. (You might
find Olof Sisask’s expository paper of the same name to be a good starting point.)
(16)
S
´
ark
?
ozy’s theorem on perfect squares. (See Neil Lyall’s paper
A new proof of Sarkozy’s
theorem
for references on the problem.)
(17)
Roth’s theorem on three term progressions and Gowers’ generalization to four term pro-
gressions. (You may wish to see Soundararajan’s course notes on additive combinatorics,
available on his homepage at Stanford.)
(18)
The ergodic proof of Szemer
´
edi’s theorem; see the paper in
Bulletin of the AMS
by H.
Furstenberg, Y. Katznelson, and D. Ornstein. (This is one of the most beautiful papers
known to me in any field of mathematics.)
(19)
Applications of the Balog-Szemer
´
edi-Gowers theorem.
(20)
Sum-product theorems: Solymosi’s work over
R
(we presented his strongest result in class,
but his earlier work is takes a different approach which is also interesting); the extension
to
C
by S. V. Konyagin and M. Rudnev (see their paper on the arxiv); and work on sum-
product over finite fields, for example
Estimates for the number of sums and products
and for exponential sums in fields of prime order
by J. Bourgain, A. Glibichuk, and S. V.
Konyagin, and
A sum-product estimate in finite fields, and applications
by J. Bourgain, N.
Katz, and T. Tao.
(21)
The Kakeya conjecture over finite fields was seen to be extremely difficult, until Zeev Dvir
(a graduate student in computer science) discovered a beautifully simple argument; see his
paper
On the size of Kakeya sets in finite fields
, available on the arxiv. Also see the follow-
up paper by S. Saraf and M. Sudan,
Improved lower bound on the size of Kakeya sets over
finite fields
.
(22)
Dvir’s work helped to popularize the ‘polynomial method,’ a powerful technique which is
useful both throughout math and computer science. Discuss the polynomial method. You
may find the MIT course given by Larry Guth (course notes freely available online) helpful.
One of the spectacular applications of the method is the near-resolution of the notorious
Erd
?
os distinct distances problem; see the paper by L. Guth and N. Katz.
(23)
Sanders’ work on the polynomial Freiman-Ruzsa conjecture. In addition to Sanders’ orig-
inal paper, you may find S. Lovett’s expository paper on the subject helpful.
(24)
Applications of the polynomial Freiman-Ruzsa conjecture to computer science. You may
wish to start by exploring
An additive combinatorics approach relating rank to commu-
nication complexity
by E. Ben-Sasson, S. Lovett, and N. Ron-Zewi, and
From affine to
two-source extractors via approximate duality
by N. Ron-Zewi and E. Ben-Sasson.
WWW
.
MATH
.
TORONTO
.
EDU
/
LGOLDMAK
/APM461/
E-mail address
:
lgoldmak@math.toronto.edu
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂