The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond

ampn

A quick schematic road-map to these new geometric objects. The  positroidron can be seen as a cellular structure on the nonnegative Grassmanian – the part of the real Grassmanian G(m,n) which corresponds to m by n matrices with all m by m minors non-negative. The cells in the cellular structure of the positroidron correspond to those matrices with the same (+,0) pattern for m by m minors. When m=1 we get a (spherical) simplex. When we project the positroidron using an n by k totally positive matrix we get for m=1 the cyclic polytope, and for general m the  amplituhedron. When we project using general matrices we obtain general polytopes for m=1, and an interesting extension of polytopes proposed by Thomas Lam for general m.   

Alex Postnikov’s recent lectures series in our Midrasha was an opportunity to understand slightly better some remarkable combinatorial objects that drew much attention recently. Continue reading

Test your intuition 24: Which of the following three groups is trivial

1office08

Martin Bridson

We have three finitely presented groups

A is generated by two generators a and b and one relation  a^{-1} \cdot b\cdot a = b^2

B is generated by three generators a, b, c and three relations a^{-1} \cdot b\cdot a = b^2,  b^{-1}\cdot c\cdot b = c^2,  c^{-1}\cdot a\cdot c = a^2.

C is generated by four generators a, b, c, d and four relations a^{-1} \cdot b\cdot a = b^2,  b^{-1}\cdot c\cdot b = c^2,  c^{-1}\cdot d\cdot c = d^2, and d^{-1}\cdot a \cdot d = a^2.

Test your intuition: which of the groups A, B or C is trivial

Please do not answer this poll if you already knew the answer

This poll is to learn how many people already knew the answer before. Please please answer.

As always comments are welcome!

Update: I did not know the answer (and I feel now better about it).

New Ramanujan Graphs!

margulis1

margulis2

Margulis’ paper

Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question about girth at the end of the post.) In a subsequent paper Margulis used the girth property in order to construct efficient error-correcting codes. (Later Sipser and Spielman realized how to use the expansion property for this purpose.)

The purpose of this post is to briefly tell you about new Ramanujan graphs exhibited by Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Here is the paper. This construction is remarkable for several reasons: First, it is the first elementary proof for the existence of Ramanujan graphs which also shows, for the first time, that there are k-regular Ramanujan graphs (with many vertices)  when k is not q+1, and q is a prime power. Second, the construction uses a novel “greedy”-method (with further promised fruits) based on identifying classes of polynomials with interlacing real roots, that does not lead (so far) to an algorithm (neither deterministic nor randomized). Third, the construction relies on Nati Linial’s idea of random graph liftings and verify (a special case of) a beautiful conjecture of Yonatan Bilu and Linial.  Continue reading

Andrei

andrei

Andrei Zelevinsky passed away a week ago on April 10, 2013, shortly after turning sixty. Andrei was a great mathematician and a great person. I first met him in a combinatorics conference in Stockholm 1989. This was the first major conference in combinatorics (and perhaps in all of mathematics) with massive participation of mathematicians from the Soviet Union, and it was a meeting point for east and west and for different areas of combinatorics. The conference was organized by Anders Björner who told me that Andrei played an essential role helping to get the Russians to come. One anecdote I remember from the conference was that Isreal Gelfand asked Anders to compare the quality of his English with that of Andrei. “Isreal”, told him Anders politely, “your English is very good, but I must say that Andrei’s English is a touch better.” Gelfand was left speechless for a minute and then asked again: “But then, how is my English compared with Vera’s?” In 1993, Andrei participated in a combinatorics conference that I organized in Jerusalem (see pictures below), and we met on various occasions since then. Andrei wrote a popular blog (mainly) in Russian Avzel’s journal. Beeing referred there once as an “esteemed colleague” (высокочтимым коллегой) and another time as  “Gilushka” demonstrates the width of our relationship.

Let me mention three things from Andrei’s mathematical work.

Andrei is famous for the Bernstein-Zelevinsky theory. Bernstein and Zelevinsky classified the irreducible complex representations of a general linear group over a local field in terms of cuspidal representations. The case of GL(2) was carried out in the famous book by Jacquet-Langlands, and the theory for GL(n) and all reductive groups was a major advance in representation theory.

The second thing I would like to mention is Andrei’s work with Gelfand and Kapranov on genaralized hypergeometric functions. To get some impression on the GKZ theory you may look at the BAMS’ book review of their book written by Fabrizio Catanese. This work is closely related to the study of toric varieties, and it introduced the secondary polytopes. The secondary polytopes is a polytope whose vertices correspond to (certain) triangulations of a polytope P. When P is a polygon then the secondary polytope is the associahedron (also known as the Stasheff polytope).

The third topic is  the amazing cluster algebras.  Andrei Zelevinsky and Sergey Fomin invented cluster algebras which turned out to be an extremely rich mathematical object with deep and important connections to many areas, a few are listed in Andrei’s short introduction (mentioned below): quiver representations, preprojective algebras, Calabi-Yau algebras and categories,  Teichmüller theory, discrete integrable systems, Poisson geometry, and we can add also,  Somos sequences, alternating sign matrices, and, yet again, to associahedra and related classes of polytopes. A good place to start learning about cluster algebras is Andrei’s article from the Notices of the AMS: “What is a cluster algebra.” The cluster algebra portal can also be useful to keep track. And here is a very nice paper with a wide perspective called “integrable combinatorics”  by Phillippe Di Francesco. I should attempt a separate post for cluster algebras.

Andrei was a wonderful person and mathematician and I will miss him.

jerusalem93 Andrei Jerusalem 33

Primality and Factoring in Number Fields

Both PRIMALITY – deciding if an integer n is a prime and FACTORING – representing an integer as a product of primes, are algorithmic questions of great interest. I am curious to know what is known about these questions over general number fields. A major difference there is that there is know unique factorization to primes. Let me repeat here a question that I asked over TCS-stackexchange.

What is known about the computational complexity of factoring integers in general number fields? More specifically:

0. Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?

1. Is it known that primality over number fields is in P or BPP?

2. What are the best known algorithms for factoring over number fields? (Do the \exp \sqrt n and the (apparently) \exp n^{1/3} algorithms extend from \mathbb{Z}?) Here, factoring refers to finding some representation of a number (represented by n bits) as a product of primes.

3. What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?

4. Over \mathbb{Z} it is known that deciding if a given number has a factor in an interval [a,b] is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?

5. Is factoring in number fields in BQP?

Motivation and updates: The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by an earlier TCSexchange question. Lior Silverman presented in the comment section  below  a thorough answer.

Test Your Intuition (16): Euclid’s Number Theory Theorems

Euclid’s

Euclid’s book IX on number theory contains 36 propositions.

The 36th proposition is:

Proposition 36.If as many numbers as we please beginning from a unit are set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last makes some number, then the product is perfect.

It asserts that if 2^n-1 is a prime number then 2^{n-1}\cdot (2^n-1) is a perfect number. (A number m is perfect of it is equal to the sum of its proper divisors.)

This is certainly a remarkable achievement of ancient Greek mathematics. Other Propositions of the same book would be less impressive for us:

Proposition 23.If as many odd numbers as we please are added together, and their multitude is odd, then the sum is also odd.

Proposition 24.If an even number is subtracted from an even number, then the remainder is even.

Proposition 25.If an odd number is subtracted from an even number, then the remainder is odd.

Proposition 26.If an odd number is subtracted from an odd number, then the remainder is even.

Proposition 27.If an even number is subtracted from an odd number, then the remainder is odd.

Proposition 28.If an odd number is multiplied by an even number, then the product is even.

Proposition 29.If an odd number is multiplied by an odd number, then the product is odd.

Test your intuition: What is the reason that deep mathematical results are stated by Euclid along with trivial results.

The AC0 Prime Number Conjecture

Möbius randomness and computational complexity

Last spring Peter Sarnak gave a thought-provoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.)

Here is a variation of the type of questions Peter has raised.

The AC_0 Prime Number Conjecture: The correlation between the Möbius function and any function f from the natural numbers to {-1,1}, so that f can be described by a bounded depth polynomial size circuit, tends to zero!

Updates: (March) The conjecture made it to major league blogs as a very interesting blog post describing the conjecture appeared on Dick Lipton’s blog, and let to some interesting discussion. I posted two related Mathoverflow problems . The first
is about the discrete Fourier coefficients of the Mobius function
and the second
is about Walsh-Fourier coefficients of the Mobius function.
 Ben Green have posted an answer to my Mathoverflow question indicating an affarmative solution for the AC^0 Prime Number Conjecture. The proof is based on combining the Linial-Mansour-Nisan theorem with Results and techniques by Glyn Harman and Imre Kátai, (From the paper Primes with preassigned digits. II. Acta Arith. 133 (2008), 171–184.)

Ben have written some rough notes on this a short paper giving the solution here.  (An  earlier note by Ben assumed GRH and the full paper contain the extra work is needed to prove it unconditionally.) This is a very nice result. Ben is also optimistic that showing that all Walsh-Fourier functions are orthogonal to Mobius (which is a more general result) is within reach by combining the above result with results by Mauduit-Rivat. 

Of course, the next logical step is the ACC[2]-Prime number conjecture.  This includes as a very special case the question if all Walsh-Fourier functions are orthogonal asymptotically to the Mobius function. The “Walsh-Fourier” functions are high degree monomials over the real but they can be considered as linear functions over Z/2Z. For that, replace the values {-1,+1} by {0,1} both in the domain and range of our Boolean functions? What about low degree polynomials instead of linear polynomials? If we can extend the results to polynomials over Z/2Z of degree at most polylog (n) this will imply by a result of Razborov Mobius randomness for AC0[2] circuits. (This is interesting also under GRH).

(AprilJean Bourgain proved (private communication)  that for every Walsh function $W_S$ we have \sum_{m=1}^{X}\mu(m) W_S(m) \le X \cdot e^{-(\log X)^{1/10}}. In other words, \hat \mu(S) \le e^{-(\log X)^{1/10}}.

Jean also showed that under GRH \sum_{m=1}^X\mu(m)W_S(m) \le X^{1-(c/(\log\log X)^2)}. In other words, \hat \mu(S) \le X^{-(c/\log \log X)^2}. This result suffices to show under  GRH the “monotone prime number conjecture.”

While the questions about polylog degree polynomials over Z/2Z and about AC0(2) circuits  are still open, Jean Bourgain was able to prove Mobius randomness for AC0(2) circuits of certain sublinear size.

Jean also noted that to show that the Mobius function itself is non-approximable by a AC0[2) circuit (namely you cannot reach correlation say of 0.99) can easily be derived from Razborov Smolensky theorem, since an easy computation shows that \mu(3x)^2 has correlation >0.8 with the 0(mod 3) function. So we have a simple argument showing that (for n large) an ACC(2) function (or even a polylog degree polynomial)) cannot have correlation larger than 0.99 with the Mobius function, but showing that it cannot have correlation larger than 0.01 with the Mobius function seems at present very difficult. (More update: as it turned out, this last observation can be found already in Allender-Saks-Shparlinski’s paper.) 
 

End of updates.

Let me state the conjecture more precisely. Continue reading

Octonions to the Rescue

Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth.

Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect.

Update: There is more to be told about the background of the new exciting paper. In particular, I would like to tell you more about regular graphs with high girth. (I started below.) The Ramanujan graphs story is, of course, also fascinating so at the very least I should give good links.

Michael Atiyah‘s lecture at IAS physics last Friday was entertaining, educational and quite provocative.

The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octonions. Atiyah expects that the Octonions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk,  Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octonionic ideas of this wise energetic scientific tycoon.

The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.
http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.

So I waited a couple of hours before looking at the link. Indeed,  1011.2642v1.pdf is a great paper. It uses Octonions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth. Peter Sarnak’s initial reaction to the new paper was: “wow”.

Here is a link to a paper entitled “Octonions” by John Baez, that appeared in Bull. AMS.

Some background:

Let G be a k-regular graph with girth g where g is an odd integer. Continue reading

The Amitsur-Levitzki Theorem for a Non Mathematician.

Yaacov Levitzki

The purpose of this post is to describe the Amitsur-Levitzki theorem: It is meant for people who are not necessarily mathematicians. Yet they need to know two things. The first is what matrices are. Very briefly, matrices are rectangular arrays of numbers. The second is that two n by n square matrices A and B can be multiplied. We denote their product by A x B and the product is again an n by n matrix. Unlike numbers, the product of matrices need not be commutative.  In other words A x B can be different from B x A.  The Wikipedia article about matrices is a good source.

We can multiply more than two matrices. We can write A x B x C for the product of A, B and C. The order of the matrices is important, but the order in which we perform the multiplication is not. This is because multiplication of matrices is associative,  that is

 (A x B ) x C  = A x (B x C).

Here is the Amitsur Levitzki Theorem for 2 x2 matrices:

For every four 2 x 2 matrices A, B, C, and D

A x B x C x D – B x A x C x D – A x B x D x C + B x A x D x C – A x C x B x D + C x A x B x D  +  A x C x D x B – C x A x D x B + A x D x B x C  – D x A x B x C – A x D x C x B  + D x A x C x B +  C  x D x A x B –   C x D x B x A –  D x C x A x B + D x C x B x A  – B x D x A x C  + B x D x C x A   + D x B x A x C  – D x B x C x A  + B x C x A x D  –  B x C x D x A  –  C x B x A x D + C x B x D x A = 0 .

In other words, we take the sum of the products of the matrices for all 24 possible orderings (permutations) with certain plus or minus signs, and lo and behold, we always get 0.

I will say more about it. But first a few remarks. The Amitsur-Levitzki theorem deals with products of 2k matrices of size k \times k. It is very beautiful and important and when it comes to mathematics, it doesn’t get much better than that. It can be a nice theorem to explain to non mathematicians, but in this case I have especially one non-mathematician in mind. Alex Levitzki – Yaacov Levitzkii’s son.  I promised Alex who is a famous HU biologist and chemist to tell him about his father’s theorem so why not share it with others. Yaacov Levitzki was one of the founding members of my department in Jerusalem. As a young man he came to Göttingen with the idea to study chemistry but attending a lecture by Emmy Noether converted him to mathematics.

The Amitsur Levitzki Theorem: For every 2n matrices of size n by n denoted by A_1,A_2,\dots A_{2n}, we have: 

\sum sgn (\sigma) \prod_{i=1}^{2n} A_{\sigma(i)} =0,

where the sum is taken over all (2n)! orderings (permutations) \sigma of \{1,2,\dots, 2n\} and sgn(\sigma) denotes the sign of the ordering  \sigma. Continue reading