Thursday, April 29, 2010
technological toys
Inspired by Nigel (who is often on the bleeding edge of technology) I ordered a Fujitsu ScanSnap - see below - which arrived a day ago. It's about the size of a loaf of bread, has one control button ("Scan"), and scans 20 double-sided pages per minute to PDF. I hope to use it to organize the piles of preprints, handwritten notes and manuscripts that I have accumulated in nearly thirty years as a mathematician.
That then begs the question - what software should I use to keep track of the resulting huge pile of PDFs? Right how I am working with Zotero which will organize pdfs, archive them on a WebDAV server, and also integrate with Penn State's library and other sources of bibliographic info. And it will seamlessly import the bibtex bibliography that I have maintained since I started using TeX. But there may well be other useful software packages out there that will do the same or better - any suggestions?
That then begs the question - what software should I use to keep track of the resulting huge pile of PDFs? Right how I am working with Zotero which will organize pdfs, archive them on a WebDAV server, and also integrate with Penn State's library and other sources of bibliographic info. And it will seamlessly import the bibtex bibliography that I have maintained since I started using TeX. But there may well be other useful software packages out there that will do the same or better - any suggestions?
Monday, April 26, 2010
Various characterizations of exactness
This post is a place to list a number of papers that have recently appeared on the arXiv which reformulate the notion of exactness for groups (or property A for spaces or amenable actions) in different ways:
I'll post more later about the relations between these.
- A cohomological characterisation of Yu's Property A for metric spaces by Brodzki, Niblo and Wright.
- Invariant expectations and vanishing of bounded cohomology for exact groups by Douglas and Nowak.
- Amenable actions, invariant means and bounded cohomology by Brodzki, Niblo, Nowak and Wright.
- A note on topological amenability by Monod.
I'll post more later about the relations between these.
Invariant translation approximation
At the very end of my book Lectures on Coarse Geometry 
I asked the following question: suppose you take a discrete group $\Gamma$, consider it as a metric space and form the uniform translation algebra $UC^*(|\Gamma|)$. This algebra has a natural $\Gamma$-action and the $\Gamma$-fixed subalgebra, $UC^*(|\Gamma|)^\Gamma$, clearly contains the reduced $C^*$-algebra of the group $\Gamma$. Are these objects equal? In the book I showed that they are equal for amenable groups and outlined an argument, invented by Nigel Higson, which shows that they are also equal for free groups - this uses Haagerup's results about rapid decay.
It is clear that some kind of approximation property is involved here and in the book I called it the "invariant translation approximation property". (In our earlier discussions Nigel, Jerry and I were so irritated by this question that we called it the "completely stupid approximation property" but fortunately we were not completely stupid enough to use this term in print. Ooops...) Which groups possess this property?
While talking with Nowak in Texas I learned about a paper by Joachim Zacharias, On the invariant translation approximation property for discrete groups , which makes significant progress on this question. Zacharias' paper works as follows. First consider a strengthening of the ITAP by allowing coefficients: one looks at $UC^*(|\Gamma|;S)$ where $S$ is an auxiliary $C^*$-algebra (or operator space) and asks whether the $\Gamma$-invariant part of that is equal to $C^*_r(\Gamma)\otimes S$ (minimal tensor product). (N.B. There is no $\Gamma$-action on $S$ - no 'twisting'.) Zacharias proves that for exact groups this strengthened ITAP is equivalent to the Haagerup-Kraus approximation property ( Approximation properties for group $C^*$-algebras and group von Neumann algebras , Transactions of the American Mathematical Society, Vol. 344, No. 2 (Aug., 1994), pp. 667-699, which says that there is a net in the Fourier algebra $A(\Gamma)$ converging to 1 in a certain weak topology on the completely bounded multipliers on $C^*_r(\Gamma)$. Unfortunately no example of an exact discrete group without this property is known, but it has been conjectured that $SL(3,Z)$ is such a group.
On the way the author proves another characterization of exact groups, namely that $\Gamma$ is exact iff the map $S \mapsto UC^*(|\Gamma|;S)$ is an exact functor.
I asked the following question: suppose you take a discrete group $\Gamma$, consider it as a metric space and form the uniform translation algebra $UC^*(|\Gamma|)$. This algebra has a natural $\Gamma$-action and the $\Gamma$-fixed subalgebra, $UC^*(|\Gamma|)^\Gamma$, clearly contains the reduced $C^*$-algebra of the group $\Gamma$. Are these objects equal? In the book I showed that they are equal for amenable groups and outlined an argument, invented by Nigel Higson, which shows that they are also equal for free groups - this uses Haagerup's results about rapid decay.It is clear that some kind of approximation property is involved here and in the book I called it the "invariant translation approximation property". (In our earlier discussions Nigel, Jerry and I were so irritated by this question that we called it the "completely stupid approximation property" but fortunately we were not completely stupid enough to use this term in print. Ooops...) Which groups possess this property?
While talking with Nowak in Texas I learned about a paper by Joachim Zacharias, On the invariant translation approximation property for discrete groups , which makes significant progress on this question. Zacharias' paper works as follows. First consider a strengthening of the ITAP by allowing coefficients: one looks at $UC^*(|\Gamma|;S)$ where $S$ is an auxiliary $C^*$-algebra (or operator space) and asks whether the $\Gamma$-invariant part of that is equal to $C^*_r(\Gamma)\otimes S$ (minimal tensor product). (N.B. There is no $\Gamma$-action on $S$ - no 'twisting'.) Zacharias proves that for exact groups this strengthened ITAP is equivalent to the Haagerup-Kraus approximation property ( Approximation properties for group $C^*$-algebras and group von Neumann algebras , Transactions of the American Mathematical Society, Vol. 344, No. 2 (Aug., 1994), pp. 667-699, which says that there is a net in the Fourier algebra $A(\Gamma)$ converging to 1 in a certain weak topology on the completely bounded multipliers on $C^*_r(\Gamma)$. Unfortunately no example of an exact discrete group without this property is known, but it has been conjectured that $SL(3,Z)$ is such a group.
On the way the author proves another characterization of exact groups, namely that $\Gamma$ is exact iff the map $S \mapsto UC^*(|\Gamma|;S)$ is an exact functor.
Friday, April 23, 2010
Geometry and complexity theory
I'm at TAMU today, at the invitation of Piotr Nowak and Ron Douglas. Along with a number of others, they have made significant progress with understanding exactness of groups/property A in terms of appropriate notions of "invariant means" and "vanishing of bounded cohomology". I will probably write about this later.
However, while here I also had a chance to talk with Joseph Landsberg about his preprint P versus NP and geometry. Who could resist such a title? Here is my summary of what he told me. Suppose that you have to compute some huge polynomial in many variables. Then (obviously) in general it will take you a long time. As an example, consider the determinant of an $n\times n$ matrix, which is a polynomial of degree $n$ in $n^2$ variables. A brute force, term-by term evaluation takes a very long time. But in this case there is a trick - Gaussian elimination - which allows one to compute the polynomial much more quickly (with roughly $O(n^4)$ arithmetic operations I think). This is a hidden symmetry leading to speedy computation. Other polynomials, e.g. most famously the permanent (which is the same as the determinant but with all signs $+$), cannot (so far as is known) be computed in this easy way.
This leads to the notion of determinantal complexity (Valiant). You can envisage computing some polynomial such as the permanent of an $n\times n$ matrix by computing instead the determinant of some larger matrix built out of the original one in some way. (If the "larger matrix" is allowed to be sufficiently much larger one can always do this.) Define the determinantal complexity of the (sequence of) given polynomials to be the function that tells you how much you must increase the size of an $n\times n$ matrix to build a larger matrix that computes your polynomial via a determinat. Valiant conjectured that for the permanent, the determinantal compelxity grows faster than any polynomial. If I understand correctly, the falsity of this conjecture (i.e. a polynomial bound for $dc$ of the permanent) would imply $P=NP$.
To address this, the program of "geometric complexity theory" transfers the problem to one in algebraic or differential geometry. One looks at the variety defined by the determinant (in projective space) and allows the general (or special) linear group of the $n^2$ coordinates to act. The permanent (in some smaller degree $d$) defines a point in this space and the question becomes whether this point (or the Zariski closure of its orbit) lies in the Zariski closure of the orbit of the determinant. This question is then addressed either by representation theory (the ring of regular functions on a $G$-orbit can be completely described in terms of representation theory) or by local differential geometry.
However, while here I also had a chance to talk with Joseph Landsberg about his preprint P versus NP and geometry. Who could resist such a title? Here is my summary of what he told me. Suppose that you have to compute some huge polynomial in many variables. Then (obviously) in general it will take you a long time. As an example, consider the determinant of an $n\times n$ matrix, which is a polynomial of degree $n$ in $n^2$ variables. A brute force, term-by term evaluation takes a very long time. But in this case there is a trick - Gaussian elimination - which allows one to compute the polynomial much more quickly (with roughly $O(n^4)$ arithmetic operations I think). This is a hidden symmetry leading to speedy computation. Other polynomials, e.g. most famously the permanent (which is the same as the determinant but with all signs $+$), cannot (so far as is known) be computed in this easy way.
This leads to the notion of determinantal complexity (Valiant). You can envisage computing some polynomial such as the permanent of an $n\times n$ matrix by computing instead the determinant of some larger matrix built out of the original one in some way. (If the "larger matrix" is allowed to be sufficiently much larger one can always do this.) Define the determinantal complexity of the (sequence of) given polynomials to be the function that tells you how much you must increase the size of an $n\times n$ matrix to build a larger matrix that computes your polynomial via a determinat. Valiant conjectured that for the permanent, the determinantal compelxity grows faster than any polynomial. If I understand correctly, the falsity of this conjecture (i.e. a polynomial bound for $dc$ of the permanent) would imply $P=NP$.
To address this, the program of "geometric complexity theory" transfers the problem to one in algebraic or differential geometry. One looks at the variety defined by the determinant (in projective space) and allows the general (or special) linear group of the $n^2$ coordinates to act. The permanent (in some smaller degree $d$) defines a point in this space and the question becomes whether this point (or the Zariski closure of its orbit) lies in the Zariski closure of the orbit of the determinant. This question is then addressed either by representation theory (the ring of regular functions on a $G$-orbit can be completely described in terms of representation theory) or by local differential geometry.
Tuesday, April 20, 2010
I can write TeX!
Seems as though I figured out how to include some TeX: $x^2+y^2+z^2=r^2$, $\int_{-\infty}^\infty e^{-x^2}\,dx = \sqrt{\pi}$. I got this from http://sumidiot.blogspot.com/2008/01/latex-in-blogger.html if you want to try it. You need to allow a javascript file to run from Nottingham University (UK).
The Atiyah conjecture is false (sort of)
Diarmuid Crowley visited for a couple of days last week to talk about the Manifold Atlas Project which is a plan to produce a sort of online encyclopedia/journal of information about all sorts of manifolds. Of course we talked about other things also, and I learned from Diarmuid about a paper by Tim Austin of UCLA which gives a counterexample to a version of the "Atiyah Conjecture".
Atiyah would want me to point out that the conjecture is misnamed. In the paper in Asterisque where he introduces the L2 Betti numbers, Atiyah asked as a problem: "Give examples where these invariants are not integers or perhaps even irrational". The name "Atiyah conjecture" got attached to the claim that there are no such examples! And the question about the integrality of the invariants (for torsion free groups) is still open. But for groups with torsion, Zuk gave a counterexample some years ago to the claim that the denominators of the L2 Betti numbers must be generated by the torsion orders in the group; and now Austin shows that there are groups with irrational (even transcendental) L2 Betti numbers.
The argument is a non-constructive one: Austin builds an uncountable family of groups, and in the group ring of each group a particular element, such that the von Neumann dimensions of the kernels of these elements are all different. (The groups are certain "lamplighter-type" groups built on the free group.) Thus there are uncountably many different real numbers which are L2 Betti numbers, and some of them must not be rational (or algebraic). But the process doesn't identify a particular group for which this is true.
If I could figure out how to get TeX into this thing I might post more...
(Added later: See Thomas' comments below for a follow-up paper by Lukasz Grabowski, which begins "The main point of this article is to show some connections between Turing machines and von Neumann algebras".
Atiyah would want me to point out that the conjecture is misnamed. In the paper in Asterisque where he introduces the L2 Betti numbers, Atiyah asked as a problem: "Give examples where these invariants are not integers or perhaps even irrational". The name "Atiyah conjecture" got attached to the claim that there are no such examples! And the question about the integrality of the invariants (for torsion free groups) is still open. But for groups with torsion, Zuk gave a counterexample some years ago to the claim that the denominators of the L2 Betti numbers must be generated by the torsion orders in the group; and now Austin shows that there are groups with irrational (even transcendental) L2 Betti numbers.
The argument is a non-constructive one: Austin builds an uncountable family of groups, and in the group ring of each group a particular element, such that the von Neumann dimensions of the kernels of these elements are all different. (The groups are certain "lamplighter-type" groups built on the free group.) Thus there are uncountably many different real numbers which are L2 Betti numbers, and some of them must not be rational (or algebraic). But the process doesn't identify a particular group for which this is true.
If I could figure out how to get TeX into this thing I might post more...
(Added later: See Thomas' comments below for a follow-up paper by Lukasz Grabowski, which begins "The main point of this article is to show some connections between Turing machines and von Neumann algebras".
Lin Shan's index theory
OK, I am going to try to revive this blog in the hope that it will encourage me to read and keep up with the mathematical literature. We shall see...
Anyhow, I just wrote a review for Mathematical Reviews of the paper "Equivariant higher index theory and nonpositively curved manifolds" by Lin Shan (JFA 255(2008), 1480-1496. This paper defines and studies an analytic assembly map that includes both the coarse assembly map and the Baum-Connes assembly map as special cases, and it proves a Novikov conjecture type statement.
Anyhow, I just wrote a review for Mathematical Reviews of the paper "Equivariant higher index theory and nonpositively curved manifolds" by Lin Shan (JFA 255(2008), 1480-1496. This paper defines and studies an analytic assembly map that includes both the coarse assembly map and the Baum-Connes assembly map as special cases, and it proves a Novikov conjecture type statement.
Subscribe to:
Posts (Atom)