Department of Mathematics,

Temple University, Philadelphia, PA 19122, USA.

Email: zeilberg@math.rutgers.edu

*Dedicated to A. Nilli, on her R(4,4)-th birthday*

**Abstract**: Using some general vague principles
of rough classification
of W. T. Gowers, we prove the asymptotic bound of the title
for the celebrated diagonal Ramsey Numbers.

Combinatorics is not unlike a competitive sport, and sometimes
a breaking of a record has mostly psychological rather than
conceptual significance. Hence when,
on May 6, 1954, Sir Dr. Roger
Bannister ran *one* mile in less than *four* minutes,
the whole world was excited, even though both *mile* and
*minute* are arbitrary human-made units.

Four is also a very significant number in both the mathematical and
physical universes. Until recently we believed that we live in 4 dimensions,
and even if string theory turns out to be the *theory of everything*,
the remaining 6 dimensions are negligible. Hara and Slade proved that
above *four* dimensions, self-avoiding walks behave basically like
random walks. In *four* dimensions they
seem to almost do so, but for dimensions less than *four* they
are probably very different.
Smale proved that the Poincare conjecture is *true*
for dimension greater than *four*, while Freedman and
Donaldson proved the existence of kinky spaces in dimension *four*.
It is trivial that *three* colors do not suffice, while
*five* colors suffice to color a planar map, yet it is
relatively hard to prove that *four* colors suffice.

Here we announce the breaking of the notorious *4 barrier* for
the asymptotic upper bound for the n-th root of R(n,n). The details are all
contained in the source code and output of 300 hours of CPU of
the Maple package FRANK
written by the second author, and
executed by the first author. Here we will only describe,
in very vague terms the rough ideas behind the proof.

Most of the credit is due to W. T. Gowers, the second-youngest
member of the top-16 most influential living mathematicians,
according to Cliff Pickover's list (`Wonders of Numbers', Oxford
Univ. Press, 2001, p. 88). This must be Gowers's favorite problem,
since he listed it *first* in his list of 19 open problems
for the 21st century ([1], p. 17).

The very general, rather rough, extremely vague, but nevertheless seminal, principle behind our proof is described succinctly on p. 74 of [2]. Partition the family of graphs into a union of disjoint families, each of them with additional structure, and prove the upper bound separately for each of them, using different methods, if necessary.

But this is easier said than done. What if the number of cases
exceeds, say, 10000, and each case requires solving a recursive
inequality involving a system of 100 equations for
100 unknown discrete functions, each of which depend on
up to 50 variables? Luckily, the first author, assisted by its
sibling, Shalom B. Ekhad (with some help from Shalom's kind
editor and agent, Jeff Lagarias), and all the computer servants
of the enigmatic, elite, and *secret* society called the
Bitchen Mathematicians.
(consisting of the world's 12
greatest mathematicians), made the proof possible.

Recall that the classical proof that R(n,n) is less than (2n-2)!/(n-1)!)**2 consists in introducing a more general quantity, R(n,m) and, claiming, by an extremely naive and simple-minded pigeon-principle argument, that R(m,n) is less than R(m-1,n)+R(m,n-1), which implies by induction that R(m,n) is less than (m+n-2)!/((m-1)!(n-1)!).

This simple argument takes no advantage of any extra structure that a graph might have, that would force an n-clique or m-independent set. We introduce ten attributes: the number of edges, and certain parameters derived from the spectrum of the graph, using Alon and Milman's celebrated result about the second-largest eigenvalue. Then each family is treated separately, getting a system of recursive inequalities, that is solved using the famous WZ method, and then analyzed asymptotically by the Birkhoff-Trijinski method.

Much more important than the result itself, is the
*method of proof*, that, unlike previous `computer-proofs',
like the Four Color Theorem or Kepler's Conjecture that were merely
*computer-assisted*, the present proof is purely
*computer-generated*. The only human parts were
the very vague idea of Gowers mentioned above, and of course
some routine programming by the second author.

2. W. T. Gowers. The two cultures of mathematics, in: `Mathematics: Frontiers and Perspectives', edited by V. Arnold et. al, AMS, 2000. Available from W. T. Gowers's on-line papers.