Maximal lattice-free convex bodies introduced by Herb Scarf and the related complex of maximal lattice free simplices (also known as the Scarf complex) are remarkable geometric constructions with deep connections to combinatorics, convex geometry, integer programming, game theory, fixed point computations, algebraic geometry, and economics. It is certainly an object I would like to think more and tell you more about. Here is a sculpture made by artist Ann Lehman based on such a body generated by a certain 4 by 3 matrix.
Ann Lehman: A sculpture based on a maximal lattice free convex body (photograph taken by the sculptress).
The body described in this sculpture is topologically a (two dimensional) disk, triangulated in a specific way. The boundary is a polygon embedded in 3-space consist of 21 “blue” edges. The “black” edges are internal edges of the triangulation. The triangles of the triangulation are not part of the sculpture but it is easy to figure out what they are and the shape has a remarkable zigzag nature. All vertices are integral. The only interior integral point is in “red”. (The “green” point is the origin, it is not in the body.)
Herb Scarf, me , and the sculpture (picture taken by Kareen Rozen)
The Debate continues
The debate between Aram Harrow and me on Godel Lost letter and P=NP (GLL) regarding quantum fault tolerance continues. The first post entitled Perpetual motions of the 21th century featured mainly my work, with a short response by Aram. Aram posted two of his three rebuttal posts which included also short rejoiners by me. Aram’s first post entitled Flying machines of the 21th century dealt with the question “How can it be that quantum error correction is impossible while classical error correction is possible.” Aram’s second post entitled Nature does not conspire deals with the issue of malicious correlated errors. A third post by Aram is coming and the discussion is quite interesting. Stay tuned. In between our posts GLL had several other related posts like Is this a quantum computer? on how to tell that you really have a genuine quantum computer , and Quantum ground day that summarized the comments to the first post.
Virgin Island Boolean Functions
In the beginning of February I spend a week in a great symposium on Analysis of Boolean Functions, one among several conferences supported by the Simons foundation, that took place at St. John of the Virgin Islands.
Irit Dinur and me
Ryan O’Donnell who along with Elchanan Mossel and Krzysztof Oleszkiewicz (the team of “majority is stablest” theorem) organized the meeting, live blogged about it on his blog. There are also planned scribes of the lectures and videos. I posed the following problem (which arose naturally from works presented in the meeting): What can be said about circuits with n inputs representing n Gaussian random variables, and gates of the form: linear functions, max and min.
A surprising application of a theorem on convex polytopes.
(Told to me by Moritz Schmitt and Gunter Ziegler)
A theorem I proved with Peter Kleinschmidt and Gunter Meisinger asserts that every rational polytope of dimension d>8 contains a 3-face with at most 78 vertices or 78 facets. (A later theorem of Karu shows that our proof applies to all polytopes.) You would not expect to find a real life application for such a theorem. But a surprising application has just been given.
Before talking about the application let me say a few more words about the theorem. The point is that there is a finite list of 3-polytopes so that every polytope of a large enough dimension (as it turns out, eight or more) has a 3-face in the list. It is conjectured that a similar theorem holds for k-faces, and it is also conjectured that if the dimension is sufficiently high you can reduce the list to two polytopes: the simplex and the cube. These conjectures are still open. (See this post for related open problems about polytopes.) For k=2, it follows from Euler’s theorem that every three-dimensional polytope contains a face which is a triangle, quadrangle, or pentagon, and in dimension five and up, every polytope has a 2-face which is a triangle or a rectangle.
Rodica Simion immigrated to the United States from Romania. She was a Professor of Mathematices at George Washington University untill her untimely death on January 7, 2000. Her poem “Immigrant complex” appeared in : “Against Infinity”, An Anthology of Contemporary Mathematical Poetry, edited by Ernest Robson and Jet Wimp, 1979, p. 66. Published by Primary Press, Parker Ford, PA, and Jet Wimp, Drexel University.
I have a
not simplicial (it is-in fact-
not a cell-complex
(my cells are
not a CW
(I have no com-
plexion no weight
it is a
my thinking is of
class C-one even
it does not matter:
approximates it by
my talk (being merely
C-n (n > > 0)
And in my office, there is a beautiful autoportrait by my sister Tamar Kalai. (Click for a deatiled picture.)
Academic administation is a topic of great interest that desrves a special post. The highest post I served was as the department chair, and one thing I did was to acquire for the department a quilt by the artist Anna Maria Brenti. Of course, you are welcome to come and see it (and there are a few other things to see in the city of Jerusalem.) Meanwhile here are pictures: (Click for larger pictures.)
The artist Annamaria Brenti has a degree in Mathematics from the University of Florence; her interests gradually shifted to quilting while living in the U.S. Her quilts won international awards in major quilt shows in Europe and the United States. She has been an invited artist at several quilting events around the world, including the IX International Quilt Week in Yokohama (Japan) in 2001, the IX European Patchwork Meeting in Alsace (France) in 2003, the Pacific International Quilt Festival in Santa Clara (California, U.S.A.) in 2003, and the World of Quilting in Stoneleigh (U.K.) in 2003. She currently lives in Frascati (Rome, Italy).
You can read more about the various mathematical objects on the quilt in the website of the Institute of Mathematics at the Hebrew University of Jerusalem.