E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham

E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham Inspired by Problem 21.4: “To Have a Cake” John Horton Conway and Alexander Soifer, Fine Hall, Princeton University, July 2007 The problem title comes from a famous proverb “To have a cake and eat it too,” which in my early American years I could not understand. Surely you have to “have a cake” in order “to eat it”! A better formulation of this folk wisdom would have been “To keep a cake and eat it too,” which is obviously impossible, hence a moral of the © Alexander Soifer 2017 A. Soifer, The Colorado Mathematical Olympiad: The Third Decade and Further Explorations, DOI 10.1007/978-3-319-52861-8_13 171 172 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham proverb. But that is not what I would like to share with you here. A version of what follows first appeared in the second, 2009 Springer edition of my book “How Does One Cut a Triangle?” [Soi6]. But it fits here so well that I am including its new updated and expanded 2016 version. During the years 2002–2004 and 2006–2007, I was a “Visiting Fellow” at Princeton University. In American translation from the British, a “fellow” stands for a researcher.1 A fine Mathematics Department was appropriately located in Fine Hall. My first office (2003–2004) was on the third floor near the office of the celebrated mathematician John Horton Conway, the John von Neumann Professor of Mathematics. We soon became friends. John would come in and litter my blackboard with virtuoso calculations of polyhedral invariants. In the photo, you can see an example of John’s work, with “Please leave” message to the custodians. I have never seen John with a calculator—he did not need one. John brilliantly simplified calculations to the point they became trivial—it was nothing short of a show watching John calculate. My Princeton office blackboard beautifully ‘decorated’ by John H. Conway During one of the breaks in our work, John took me to the Princeton Cemetery to pay homage to Kurt G€odel. On other breaks, we walked 1 At the same time, I was a “Long Term Visiting Scholar” at Rutgers University, Piscataway, but there I was involved in totally different problems, jointly with the genius Saharon Shelah. Read about it in my “The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators” [Soi3]. Inspired by Problem 21.4: “To Have a Cake” 173 to a Chinese restaurant, where John taught me to use chopsticks. My final chop-exam was to pick ice cubes with chopsticks. On one of the walks to pick up John’s youngest son Gareth from a kindergarten, John shared with me his ideas on the foundations of set theory. The contrast between two British ‘imports’ to Princeton-Math, Andrew Wiles and John Conway, could not be more dramatic. As an intellectual, Conway knew much about much, and was curious across many human endeavors. Wiles’ interests were rather narrow. Having conquered—jointly with Richard Taylor—the most famous problem in the history of mathematics, Fermat’s Last Theorem (FLT), Andrew believed that Fermat did not have a proof of his FLT, while romantic Conway—and I—trusted Fermat had a proof, of course, different from the one found by Taylor and Wiles. During 2006–2007 academic year, Princeton-Math Department Manager Scott Kenney suddenly got rid of the Fine Hall Commons Room’s library. These books were donated over a half a century by Princeton mathematicians. The library contained rare first editions of mathematical books. Andrew Wiles, the Chair of the Department, reacted as follows to the inquiry of the Vice-Chair Simon B. (Si) Kochen: “I was out of the country. But they were obsolete anyway.” This act upset the intellectuals of the department, such as Conway, Kochen, and Joseph Kohn. After all, a first edition is a treasure to those who value books, and “obsolete” to those who don’t. The now empty wall-long book case was thrown away and replaced by one more blackboard. Perhaps, a contrast with Andrew Wiles and other successful narrow specialists, prompted a chip on John Conway’s shoulder, as he once told me, “I haven’t done anything major in mathematics.” I replied in disagreement. John was perhaps the most ingenious mathematician I met, with an unparalleled breadth, insight, and irresistible taste for beauty—in mathematics, philosophy, literature, and life. During my second Princeton stay, 2006–2007, John suffered a stroke. However, even that did not stop him. I recall visiting John as he was recovering at his house, when he most energetically demanded from Robert MacPherson, an editor of Annals of Mathematics, to publish Thomas Hales’ computer-aided proof on the nearly 400-year old Johannes Kepler’s optimal ball packing conjecture. In a sense, John Conway won, for today I read on the journal’s Internet page that Computer-assisted proofs of exceptionally important mathematical theorems will be considered by the Annals. 174 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham We lived close to each other, and I witnessed John’s determination to get back in shape after a triple-bypass heart surgery, as he daily stubbornly walked around our neighborhood, leaning on a cane. One of my main projects at Princeton was writing a book “The Scholar and the State: In Search of Van der Waerden” [Soi10]. It was both enjoyable as it was profitable to share my newly uncovered archival documents with and to get feedback from my colleagues at Princeton-Math, especially from my friends John Conway and Harold W. Kuhn. Princeton-Math maintained an historic tradition of a daily 3 to 4 p.m. coffee hour in the Commons Room, on the third floor of the Fine Hall, attended by everyone, from undergraduate students to the “Beautiful Mind” (John F. Nash, Jr.). For one such coffee hour, I came thinking about a natural partition of an equilateral triangle into n2 congruent equilateral triangles. Of course, n2 unit equilateral triangles can cover an equilateral triangle of side n. I asked myself a question, where does the continuous clashes with the discrete? What if we were to enlarge the side length of the large triangle from n to n +ε, where ε is a ‘however small’ positive value, how many unit triangles will we need to cover it? This comprised my new open problem: Cover-Up Problem E21.1. Find the minimum number of unit equilateral triangles required to cover an equilateral triangle of side n +ε. During the next coffee hour, I posed the problem to a few Princeton colleagues. The problem immediately excited John Conway. From the Commons Room he went to the airport, to fly to a conference. On board of the airplane, John found a way to do the job with just n2 + 2 unit triangles. (Area considerations alone show the need for at least n2 + 1 of them.) Conway shared his cover-up with me upon his return—at a coffee hour, of course. Now it was my turn to travel to a conference. I usually have a quality time on an airplane: being among the strangers is akin to a solitude. What I found onboard was a totally different cover-up with the same number, n2 + 2 unit triangles. Upon my return, at a coffee hour, I shared my cover-up with John Conway. We decided to publish our results together. John suggested setting a new world record in the number of words in a paper, and submitting it to the American Mathematical Monthly. On April 28, 2004, at 11:50 a.m. (computers record the exact time!), I submitted our paper that included just two words, “n2 + 2 can” Inspired by Problem 21.4: “To Have a Cake” 175 and our two drawings. I am compelled to reproduce our submission here in its entirety (Figs. E21.1 and E21.2). Can n2 + 1 unit equilateral triangles cover an equilateral triangle of side > n, say n + ε? John H. Conway & Alexander Soifer Princeton University, Mathematics, Fine Hall, Princeton, NJ 08544, USA conway@math.princeton.edu & asoifer@princeton.edu n2 + 2 can: Fig. E21.1 Fig. E21.2 176 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham The American Mathematical Monthly was surprised, and did not know what to do about our new world record of a 2-word article. Two days later, on April 30, 2004, the Editorial Assistant Mrs. Margaret Combs acknowledged the receipt of the paper, and continued: The Monthly publishes exposition of mathematics at many levels, and it contains articles both long and short. Your article, however, is a bit too short to be a good [sic] Monthly article. . . A line or two of explanation would really help. The same day, at the coffee hour, I showed John The Monthly e-mail and asked, “What do you think?” His answer was concise, “Do not give up too easily.” Accordingly, I replied The Monthly the same day: I respectfully disagree that a short paper in general—and this paper in particular—merely due to its size must be “a bit too short to be a good Monthly article.” Is there a connection between quantity and quality? ... We have posed a fine (in our opinion) open problem and reported two distinct ‘behold-style’ proofs of our advance on this problem. What else is there to explain? The Monthly, apparently felt outgunned, for on May 4, 2004, the reply came from The Monthly’s top gun, Editor-in-Chief Bruce Palka: The Monthly publishes two types of papers: “articles,” which are substantive expository papers ranging in length from about six to twenty-five pages, and “notes,” which are shorter, frequently somewhat more technical pieces (typically in the one-to-five page range). I can send your paper to the notes editor if you wish, but I expect that he’ll not be interested in it either because of its length and lack of any substantial accompanying text. . . The standard way in which we use such short papers these days is as “boxed filler” on pages that would otherwise contain a lot of the blank space that publishers abhor. . . If you’d allow us to use your paper in that way, I’d be happy to publish it. John Conway and I accepted the “filler,” and in January 2005 issue our paper [CS1] was published. The Monthly, however, invented the title without any consultation with the authors, and added our title to the body of the article! Inspired by Problem 21.4: “To Have a Cake” 177 We also published a short article [CS2] in Geombinatorics, where we additionally observed that the ‘equilaterality’ is essential, for otherwise n2 + 1 triangles, similar to the large triangle T and with the ratio of sizes 1: (n + ε) can cover T (Fig. E21.3). Fig. E21.3 Mitya Karabash receiving the book from Alexander Soifer, Princeton, 2007 Then Mitya Karabash, whom I first met when he was a high schooler in New York and now a brilliant student at Columbia University, joined me for further explorations of this problem. First of all, we observed the following result, which is better than its simple proof: 178 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham Non-Equilateral Cover-Up E21.2 [KS1]. For every non-equilateral triangle T, n2 + 1 triangles similar to T and with the ratio of linear sizes 1: (n + ε), can cover T. Proof. An appropriate affine transformation maps an equilateral triangle and its covering shown in Fig. E21.2 onto T. This transformation produces a covering of T with n2 + 2 triangles similar to T. We can now cover the top triangle with only 2 tiling triangles instead of 3 as shown in Fig. E21.4, thus reducing the total number of covering triangles to n2 + 1. ■ Fig. E21.4 Mitya and I then generalized the problem from covering a triangle to covering more complex figures we named trigons. n-Trigon Tn is the union of n triangles from the standard triangulation of the plane such that a triangular rook can find a path between any two triangles of Tn , i.e., the union of n edge-connected triangles. If the triangulation is equilateral, then we say that the n-trigon is equilateral. You can see an example of an equilateral 9-trigon in Fig. E21.5. Fig. E21.5 Inspired by Problem 21.4: “To Have a Cake” 179 In our cover-up games, we assume that the ratio of the corresponding sides of the triangles forming the trigon and the titling triangles is (1 + ε)/1. We proved the following result: Karabash-Soifer’s Trigon Theorem E21.3 [KS1]. An n-trigon Tn can be covered with 1. n + 2 triangles if the trigon is equilateral; 2. n + 1 triangles if the trigon is non-equilateral. In spite of all the progress, however, one ‘little’ question remains open. I will formulate it here as a conjecture: in 2004 John Conway and I thought we knew the answer – we just had no idea how to prove it! Conway-Soifer Cover-Up Conjecture E21.4. Equilateral triangle of side n + ε cannot be covered by n2 + 1 unit equilateral triangles. If proven, this conjecture would chaaracterize the equilateral triangle as the only triangle requiring n2 + 2 unit covering triangles. This property could then be used as a definition of an equilateral triangle! Right after the Cover-Up Problem E21.1, I created the Cover-Up Squared Problem. Naturally, a square of side n can be covered by n2 unit squares. When, however, we let the side length increase merely to n + ε, we get a new open problem: Cover-Up Squared Problem E21.5 [Soi2]. Find the smallest number P(n) of unit squares that can cover a square of side length n + ε. I devised a covering approach illustrated in Fig. E21.6. 180 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham D E A n–k C B k+e Fig. E21.6 My results were followed by the joint ones by Mitya Karabash and I. The best Mitya and I were able to do in the Cover-Up Squared, was to match Paul Erdős and Ronald L. Graham’s dual 1975 result [EG1] on packing squares in a square: Karabash-Soifer’s Theorem E21.6 [KS2]. P(n) ¼ n2 + O(n7/11). Let me explain the “big O” notation. We write f(n) ¼ O(g(n)) if asymptotically the function f(n) grows not faster than a constant multiple of g(n). Immediately upon the publication of this result, on July 18, 2008, I received an e-mail from Ron Graham: Hi Sasha, I received the latest issue of Geombinatorics with your nice article on square covering. I am mentioning this e-mail because, like in movie series made for television, there was a continuation to Ron’s e-mail. A mere month later, he sent me a manuscript, jointly written with his wife and a distinguished mathematician in her own rights Fan Chug, entitled Packing equal squares into a large square. In it, they improved the 33-year old Graham-Erdős result [GE], and also Mitya’s and my Theorem E21.6: Inspired by Problem 21.4: “To Have a Cake” 181 Chung-Graham’s E21.7 [CG].  Theorem  pffiffi 2 3þ 2Þ=7 ð logn . P(n) ¼ n + O n Do you see why Chung-Graham result is slightly better than Karabash-Soifer? Here is why: 7=11 ¼ 0:636363 . . .  pffiffiffi 3 þ 2 =7 ¼ 0:630601 . . . Would you like to hear “tttha rrrest of the story,” as Paul Harvey used to say on the radio? On November 5, 2008, I was asked by the Editor-in-Chief Ole Warnaar to referee Chung-Graham manuscript submitted to the Journal of Combinatorial Theory, Series A! On December 12, 2008, I wrote my report: REVIEW OF CHUNG-GRAHAM MS Dear Professor Warnaar, I have read the manuscript with great interest and pleasure. The results represent a small but important improvement, attained by clever improvements in the approach of Erdős-Graham 1975. . . I enthusiastically recommend this article for publication in JCTA. The Chung-Graham paper appeared shortly after [CG]. The Cover-Up Squared Problem remains open, both in search for the asymptotically lowest possible answer and for exact values for small n. Mitya and I conjecture: Karabash-Soifer Cover-Up Square Conjecture E21.8 [KS2]. P(n) ¼ n2 + Ω(n1/2). We write f(n) ¼ Ω(g(n)) if asymptotically the function f(n) grows not slower than a constant multiple of g(n). If you haven’t started working on these exciting problems yet, you are wasting your time. :) Do share with me any and all advances you achieve! 182 E21. Cover-Up with John Conway, Mitya Karabash, and Ron Graham Ronald L. Graham and Alexander Soifer, March 2009, Boca Raton, FL