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.

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".

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.

Infinite Expanders

In a note published at

http://www.wisdom.weizmann.ac.il/~itai/infexp.ps

it is asked (by Binjamini I think), "Is there an infinite expander?".

By definition an infinite expander is an infinite connected bounded geometry graph with the following property: there exists a positive constant, call it c, such that for any set S of vertices (whether finite or not) and any ball B, less than half of whose points are in S, the ratio

(size of boundary S intersect B)/(size of S intersect B)

is greater than c.


The conjecture is that no such "infinite expander" exists.

QUESTIONS:

(a) What would it take for the graph of a group to be an infinite expander?
(b) Relate to the coarse property T problem.

[math/0606120] Maximal rank maps between Riemannian manifolds with bounded geometry

[math/0606120] Maximal rank maps between Riemannian manifolds with bounded geometry

This paper by Abreu-Suzuki gives a condition under which a coarse submersion between Riemannian manifolds is coarsely a product.

Interesting not only in itself but for its references - which are to another author (Kumeu) who came up with the basic coarse ideas, in the context of bg Riemannian manifolds, in the middle 1980s. I had not been aware of this before.

GT Monographs: Volume 9

GT Monographs: Volume 9

This is the proceedings of an Oberwolfach conference on "exotic" homology manifolds. (Roughly speaking, these are manifolds for which the "zero'th Pontrjagin class" is not equal to 1.)

[math/0603675] The lower central series and pseudo-Anosov dilatations

[math/0603675] The lower central series and pseudo-Anosov dilatations

The lower central series and pseudo-Anosov dilatations

Authors:
Benson Farb,
Christopher J. Leininger,
Dan Margalit

Comments: 26 pages, 6 figures

Subj-class: Geometric Topology; Dynamical Systems


MSC-class: 37E30 (Primary) 57M60, 37B40 (Secondary)

The theme of this paper is that algebraic complexity implies dynamical
complexity for pseudo-Anosov homeomorphisms of a closed surface S_g of genus g.
Penner proved that the logarithm of the minimal dilatation for a pseudo-Anosov
homeomorphism of S_g tends to zero at the rate 1/g. We consider here the
smallest dilatation of any pseudo-Anosov homeomorphism of S_g acting trivially
on Gamma/Gamma_k, the quotient of Gamma = pi_1(S_g) by the k-th term of its
lower central series, k > 0. In contrast to Penner's asymptotics, we prove that
this minimal dilatation is bounded above and below, independently of g, with
bounds tending to infinity with k. For example, in the case of the Torelli
group I(S_g), we prove that L(I(S_g)), the logarithm of the minimal dilatation
in I(S_g), satisfies .197 < L(I(S_g))< 4.127. In contrast, we find
pseudo-Anosov mapping classes acting trivially on Gamma/Gamma_k whose
asymptotic translation lengths on the complex of curves tend to 0 as g tends
toward infinity.

Full-text: PostScript, PDF, or Other formats

[math/0603669] All generating sets of all property T von Neumann algebras have free entropy dimension $\leq 1$

[math/0603669] All generating sets of all property T von Neumann algebras have free entropy dimension $\leq 1$

All generating sets of all property T von Neumann algebras have free
entropy dimension $\leq 1$

Authors:
Kenley Jung,
Dimitri Shlyakhtenko

Comments: 6 pages

Subj-class: Operator Algebras


MSC-class: 46L54; 52C17

Suppose $N$ is a diffuse, property T von Neumann algebra and X is an
arbitrary finite generating set of selfadjoint elements for N. By using
rigidity/deformation arguments applied to representations of N in full matrix
algebras, we deduce that the microstate spaces of X are asymptotically discrete
up to unitary conjugacy. We use this description to show that the free entropy
dimension of X, $\delta_0(X)$, is less than or equal to 1. It follows that when
N embeds into the ultraproduct of the hyperfinite $\mathrm{II}_1$-factor, then
$\delta_0(X)=1$ and otherwise, $\delta_0(X)=-\infinity$. This generalizes the
earlier results of Voiculescu, and Ge, Shen pertaining to $SL_n(\mathbb Z)$ as
well as the results of Connes, Shlyakhtenko pertaining to group generators of
arbitrary property T algebras.

Full-text: PostScript, PDF, or Other formats

Which authors of this paper are endorsers?

[math/0603621] Property A, partial translation structures and uniform embeddings in groups

[math/0603621] Property A, partial translation structures and uniform embeddings in groups

Brodzki, Niblo, Wright. - I blogged this before, but now there is an explicit invariant.

[math/0603018] On the space of metrics with invertible Dirac operator

[math/0603018] On the space of metrics with invertible Dirac operator

This paper by Mattias Dahl shows that several geometric constructions, eg codim-3 surgery, which one knows how to do in the category of positive scalar curvature manifolds, can in fact be done in the category of spin manifolds with invertible Dirac operator.

[math/0601700] Representations of residually finite groups by isometries of the Urysohn space

[math/0601700] Representations of residually finite groups by isometries of the Urysohn space: "Representations of residually finite groups by isometries of the Urysohn space
Authors: Vladimir G. Pestov, Vladimir V. Uspenskij
Comments: 12 pages, LaTeX 2e
Subj-class: Representation Theory
MSC-class: 43A65; 20C99; 22A05; 22F05; 22F50; 54E50

As a consequence of Kirchberg's work, Connes Embedding Conjecture is equivalent to the property that every homomorphism of the group $F_\infty\times F_\infty$ into the unitary group $U(\ell^2)$ with the strong topology is pointwise approximated by homomorphisms with a precompact range. In this form, the property (which we call Kirchberg's property) makes sense for an arbitrary topological group. We establish the validity of the Kirchberg property for the isometry group $Iso(U)$ of the universal Urysohn metric space $U$ as a consequence of a stronger result: every representation of a residually finite group by isometries of $U$ can be pointwise approximated by representations with a finite range. This brings up the natural question of which other concrete infinite-dimensional groups satisfy the Kirchberg property."

[math/0512592] Thick metric spaces, relative hyperbolicity, and quasi-isometric rigidity

[math/0512592] Thick metric spaces, relative hyperbolicity, and quasi-isometric rigidity

Here's an interesting paper from the arXiv by Behrstock, Drutu and Mosher

[math/0302310] Hyperbolic group $C^*$-algebras and free-product $C^*$-algebras as compact quantum metric spaces

[math/0302310] Hyperbolic group $C^*$-algebras and free-product $C^*$-algebras as compact quantum metric spaces

An interesting paper on the metric geometry of the "dual absolute value of Dirac"

[math/0512040] A pairing between super Lie-Rinehart and periodic cyclic homology

[math/0512040] A pairing between super Lie-Rinehart and periodic cyclic homology

From the arXiv

Authors: Tomasz Maszczyk,
Comments: 11 pages,
Subj-class: K-Theory and Homology; Mathematical Physics,
MSC-class: Primary 16E40, 17B35, 19K56, Secondary 46L87

We consider a pairing producing various cyclic Hochschild cocycles, which led Alain Connes to cyclic cohomology. We are interested in geometrical meaning and homological properties of this pairing. We define a non-trivial pairing between the homology of a Lie-Rinehart (super-)algebra with coefficients in some partial traces and relative periodic cyclic homology. This pairing generalizes the index formula for summable Fredholm modules, the Connes-Kubo formula for the Hall conductivity and the formula computing the K0-group of a smooth noncommutative torus. It also produces new homological invariants of proper maps contracting each orbit contained in a closed invariant subset in a manifold acted on smoothly by a connected Lie group. Finally we compare it with the characteristic map for the Hopf-cyclic cohomology.

Piotr Nowak's Homepage

Piotr Nowak

I was going to reference just a couple of Piotr's articles but then I thought that I might as well point to his entire home page. Everything is good here! In particular he shows that coarse embeddability into a Hilbert space (or into ell-one) is not the same as property A. The example is devastatingly simple: take the disjoint union of n-fold products of copies of some finite group (e.g. the group of order 2). Notice that the spaces here are quasi-isometric to cubes in R^n with the ell-one metric. If one took the ell-two (Euclidean) metric instead, wouldn't one get Yu's old counterexample to coarse Baum-Connes? Something interesting seems to be going on here.

[Of course these aren't bg spaces. Is there a bg space with the same property?]

[math/0511098] K-Theory of pseudodifferential operators with semi-periodic symbols

[math/0511098] K-Theory of pseudodifferential operators with semi-periodic symbols

Authors: Severino T. Melo, Cintia C. Silva
Subj-class: Operator Algebras; K-Theory and Homology
MSC-class: 46L80; 47G30

Let A denote the C*algebra of bounded operators on L2(R) generated by: (i) all multiplications a(M) by functions a\in C[-\infty,+\infty], (ii) all multiplications by 2\pi-periodic continuous functions and (iii) all Fourier multipliers F^{-1}b(M)F, where F denotes the Fourier transform and b is in C[-\infty,+\infty]. The Fredholm property for operators in A is governed by two symbols, the principal symbol \sigma and an operator-valued symbol \gamma. We give two proofs of the fact that K0(A) and K1(A) are isomorphic, respectively, to Z and Z\oplus Z: by computing the connecting mappings in the standard K-theory six-term exact sequences associated to \sigma and to \gamma. For the second computation, we prove that the image of \gamma is isomorphic to the direct sum of two copies of the crossed product of C[-\infty,+\infty] by an automorphism, and then use the Pimsner-Voiculescu exact sequence to compute its K-theory.

Another Coarse Geometry correction

See this link for another correction to LCG, this time in the statement and proof of Rosenblatt's theorem in chapter 3. Thanks to Steve Ferrt and his students for spotting this one.

Best wishes

John

[math/0509526] An analogue of the Novikov Conjecture in complex algebraic geometry

[math/0509526] An analogue of the Novikov Conjecture in complex algebraic geometry

We're familiar with the idea that statements about positive scalar curvature metrics (Gromov-Lawson-Rosenberg conjecture) and statements about higher signatures (Novikov conjecture) have certain parallels - ultimately they involve the higher index theorem applied to different elliptic operators, Dirac in the first case and signature in the second.

In this new paper Jonathan Rosenberg proposes a further family of statements involving higher index theory for the Dolbeault operator. These are statements in complex algebraic geometry about "higher Todd genera" for varieties.

This could be a whole new playground for higher index theorists.