# Structure and Randomness: Pages from Year One of a Mathematical Blog

31 May

The Fields prize winner, Terence Tao, published a book, Structure and Randomness: Pages from Year One of a Mathematical Blog, which is a collection of articles written in 2007 on his blog. There are many interesting articles, but the prerequisite exceed my knowledge too much.

I selected and skimmed some chapters here, but it is still too hard to understand for me. I just note them here, and maybe one day I am able to  understand it.

• The Hahn-Banach theorem, Menger’s theorem, and Helly’s theorem
The Hahn-Banach theorem is a theorem in mathematical analysis. The definition on wikipedia is too abstract for me to image what the usage of this ‘tool’ is, however, this article in fact discuss the famous lemma — Farkas’ lemma which is sometimes known as Hahn-Banach theorem. (T. Tao said that)

Farkas’ lemma. Let $P_1,\ldots,P_m: {\Bbb R}^d \to {\Bbb R}$ be affine-linear functionals. Then exactly one of the following statements holds:

1. 1. The system of inequalities $P_1(x), \ldots, P_m(x) \geq 0$ has a solution $x \in {\Bbb R}^d$.
2. 2. There exist non-negative reals $q_1,\ldots,q_m \geq 0$ such that $q_1 P_1 + \ldots + q_m P_m = -1$.

However it is also not familiar to me. At least, this is not the version of Farkas’s lemma in my mind. In fact, it is an alternative version of Farkas’s lemma. I know it has an important role in optimization theory, e.g., LP and SDP.

Farkas’ lemma can thus be interpreted geometrically as follows: Given a cone and a vector, either the vector is in the cone or there is a hyperplane separating the vector from the cone, but not both.

But I didn’t know it also connects to combinatorics, e.g., Minimax theorem, Menger’s theorem.

• Simons Lecture I: Structure and randomness in Fourier analysis and number theory

For instance, from the Siegel-Walfisz theorem we know that the last digit of large prime numbers is uniformly distributed in the set {1,3,7,9}; thus, if N is a large integer, the number of primes less than N ending in (say) 3, divided by the total number of primes less than N, is known to converge to 1/4 in the limit as N goes to infinity.

Fourier analysis is an essential feature of many of these problems from the perspective of the dichotomy between structure and randomness, and in particular viewing structure as an obstruction to computing statistics which needs to be understood before the statistic can be accurately computed.

• Simons Lecture II: Structure and randomness in ergodic theory and graph theory

It is in fact easy to see that Schur’s theorem is deducible from Ramsey’s theorem. Indeed, given a colouring of the positive integers, one can create an infinite coloured complete graph (the Cayley graph associated to that colouring) whose vertex set is the integers ${\Bbb Z}$, and such that an edge {a,b} with a < b is coloured using the colour assigned to b-a. Applying Ramsey’s theorem, together with the elementary identity (c-a) = (b-a) + (c-b), we then quickly deduce Schur’s theorem.

• Simons Lecture III: Structure and randomness in PDE
• Milliman Lecture I: Additive combinatorics and the primes
• Milliman Lecture II: Additive combinatorics and random matrices
• Milliman Lecture III: Sum-product estimates, expanders, and exponential sums
• Open question: triangle and diamond densities in large dense graphs