Tag Archives: Additive combinatorics

Extermal Combinatorics II: Some Geometry and Number Theory

Extremal problems in additive number theory

Our first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal problems for sets of real numbers, and for geometric configurations in planar Euclidean geometry. 

Problem I: Given a set A of n real numbers, how small can the set A+A={a+a’: a,a’ \in A} be?

If A={1,2,…,n} |A+A|=2n-1. Suppose the elements of A are a_1,a_2, \dots, a_n and a_1< a_2<a_3\dots a_n. Note that a_1+a_1<a_1+a_2<a_1+a_2< \dots  a_1+a_n<a_2+a_n<\dots a_n+a_n. So we identified 2n-1 distinct elements in A+A. This is the Cauchy-Davenport theorem.  

Problem II: Given a set A of n positive real numbers, how small can be the set A \cdot A={a\cdot a’: a,a’ \in A}?

You may protest (again, like in the first lecture,) that I regard problem II a different problem. You can move from problem II to problem I by taking the logarithm of all elements in A, or you can simply use the same proof with the sum replaced by a product. The proof relies only on very basic monotonicity properties of these operations.

OK, lets have another problem II.

Problem II: Given a set A of n real numbers, how small can the quantity max (|A+A|, |A \cdot A|) be? 

This problem was asked by Erdös, and in hindsight it is a very good problem. Erdös conjectured that the maximum behaves like n^2, and this is open.  We will see below a wonderful proof by Elekes that the maximum is (up to a multiplicative constant) at least n^{5/4}. The exponent 5/4 was improved twice(!!) by Jozsef Solymosi and there is a very nice post about his most recent ingenious proof for a lower bound max (|A+A|, |A \cdot A|) \ge (1/2) n^{4/3} (\log n)^{-1/3} in Izabella Laba’s blog. 

(Update 2/1/2008: “product-sum theorems” of this type grew into a large area with surprising applications in math and CS. They give a strong tool to extract randomness, and they are useful when we consider product of matrices where sums and products are naturally entangled. Here is a recent relevant post written by Herald Helfgott from Izabella Laba’s blog.)

Extremal problems in plane geometry

Problem III:  Given n points in the plane what is the maximum number of pairs among them at distance ‘1’

Problem IV:  Given s points and t lines in the plane what is the maximum number of incidences between them.

An incidence is a pair (p,\ell ) where p  is a point \ell  is a line and p \in \ell.

Problem V: Given a graph G with v vertices and e edges what is the minimum number of crossings in a planar drawing of G.

The second of my extremal combinatorics lectures was devoted to the surprising connections that were found between the above problems. There is also a very nice post about this material on Terry Tao’s blog. To show you something new I will describe a few problems in higher dimensions at the end.

Continue reading