Category: featured

the Bost-Connes coset space

Published January 17, 2008 by lievenlb

By now, everyone remotely interested in Connes’ approach to the Riemann hypothesis, knows the _one line mantra_

one can use noncommutative geometry to extend Weil’s proof of the Riemann-hypothesis in the function field case to that of number fields

But, can one go beyond this sound-bite in a series of blog posts? A few days ago, I was rather optimistic, but now, after reading-up on the Connes-Consani-Marcolli project, I feel overwhelmed by the sheer volume of their work (and by my own ignorance of key tools in the approach). The most recent account takes up half of the 700+ pages of the book Noncommutative Geometry, Quantum Fields and Motives by Alain Connes and Matilde Marcolli…

So let us set a more modest goal and try to understand one of the first papers Alain Connes wrote about the RH : Noncommutative geometry and the Riemann zeta function. It is only 24 pages long and relatively readable. But even then, the reader needs to know about class field theory, the classification of AF-algebras, Hecke algebras, etc. etc. Most of these theories take a book to explain. For example, the first result he mentions is the main result of local class field theory which appears only towards the end of the 200+ pages of Jean-Pierre Serre’s Local Fields, itself a somewhat harder read than the average blogpost…

Anyway, we will see how far we can get. Here’s the plan : I’ll take the heart-bit of their approach : the Bost-Connes system, and will try to understand it from an algebraist’s viewpoint. Today we will introduce the groups involved and describe their cosets.

For any commutative ring $R $ let us consider the group of triangular $2 \times 2 $ matrices of the form

$P_R = { \begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix}~|~b \in R, a \in R^* } $

(that is, $a $ in an invertible element in the ring $R $). This is really an affine group scheme defined over the integers, that is, the coordinate ring

$\mathbb{Z}[P] = \mathbb{Z}[x,x^{-1},y] $ becomes a Hopf algebra with comultiplication encoding the group-multiplication. Because

$\begin{bmatrix} 1 & b_1 \\ 0 & a_1 \end{bmatrix} \begin{bmatrix} 1 & b_2 \\ 0 & a_2 \end{bmatrix} = \begin{bmatrix} 1 & 1 \times b_2 + b_1 \times a_2 \\ 0 & a_1 \times a_2 \end{bmatrix} $

we have $\Delta(x) = x \otimes x $ and $\Delta(y) = 1 \otimes y + y \otimes x $, or $x $ is a group-like element whereas $y $ is a skew-primitive. If $R \subset \mathbb{R} $ is a subring of the real numbers, we denote by $P_R^+ $ the subgroup of $P_R $ consisting of all matrices with $a > 0 $. For example,

$\Gamma_0 = P_{\mathbb{Z}}^+ = { \begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix}~|~n \in \mathbb{Z} } $

which is a subgroup of $\Gamma = P_{\mathbb{Q}}^+ $ and our first job is to describe the cosets.

The left cosets $\Gamma / \Gamma_0 $ are the subsets $\gamma \Gamma_0 $ with $\gamma \in \Gamma $. But,

$\begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix} \begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & b+n \\ 0 & a \end{bmatrix} $

so if we represent the matrix $\gamma = \begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix} $ by the point $~(a,b) $ in the right halfplane, then for a given positive rational number $a $ the different cosets are represented by all $b \in [0,1) \cap \mathbb{Q} = \mathbb{Q}/\mathbb{Z} $. Hence, the left cosets are all the rational points in the region between the red and green horizontal lines. For fixed $a $ the cosets correspond to the rational points in the green interval (such as over $\frac{2}{3} $ in the picture on the left.

Similarly, the right cosets $\Gamma_0 \backslash \Gamma $ are the subsets $\Gamma_0 \gamma $ and as

$\begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix} = \begin{bmatrix} 1 & b+na \\ 0 & a \end{bmatrix} $

we see similarly that the different cosets are precisely the rational points in the region between the lower red horizontal and the blue diagonal line. So, for fixed $a $ they correspond to rational points in the blue interval (such as over $\frac{3}{2} $) $[0,a) \cap \mathbb{Q} $. But now, let us look at the double coset space $\Gamma_0 \backslash \Gamma / \Gamma_0 $. That is, we want to study the orbits of the action of $\Gamma_0 $, acting on the right, on the left-cosets $\Gamma / \Gamma_0 $, or equivalently, of the action of $\Gamma_0 $ acting on the left on the right-cosets $\Gamma_0 \backslash \Gamma $. The crucial observation to make is that these actions have finite orbits, or equivalently, that $\Gamma_0 $ is an almost normal subgroup of $\Gamma $ meaning that $\Gamma_0 \cap \gamma \Gamma_0 \gamma^{-1} $ has finite index in $\Gamma_0 $ for all $\gamma \in \Gamma $. This follows from

$\begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix} \begin{bmatrix} 1 & m \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & b+m+an \\ 0 & a \end{bmatrix} $

and if $n $ varies then $an $ takes only finitely many values modulo $\mathbb{Z} $ and their number depends only on the denominator of $a $. In the picture above, the blue dots lying on the line over $\frac{2}{3} $ represent the double coset

$\Gamma_0 \begin{bmatrix} 1 & \frac{2}{3} \\ 0 & \frac{2}{3} \end{bmatrix} $ and we see that these dots split the left-cosets with fixed value $a=\frac{2}{3} $ (that is, the green line-segment) into three chunks (3 being the denominator of a) and split the right-cosets (the line-segment under the blue diagonal) into two subsegments (2 being the numerator of a). Similarly, the blue dots on the line over $\frac{3}{2} $ divide the left-cosets in two parts and the right cosets into three parts.

This shows that the $\Gamma_0 $-orbits of the right action on the left cosets $\Gamma/\Gamma_0 $ for each matrix $\gamma \in \Gamma $ with $a=\frac{2}{3} $ consist of exactly three points, and we denote this by writing $L(\gamma) = 3 $. Similarly, all $\Gamma_0 $-orbits of the left action on the right cosets $\Gamma_0 \backslash \Gamma $ with this value of a consist of two points, and we write this as $R(\gamma) = 2 $.

For example, on the above picture, the black dots on the line over $\frac{2}{3} $ give the matrices in the double coset of the matrix

$\gamma = \begin{bmatrix} 1 & \frac{1}{7} \\ 0 & \frac{2}{3} \end{bmatrix} $

and the gray dots on the line over $\frac{3}{2} $ determine the elements of the double coset of

$\gamma^{-1} = \begin{bmatrix} 1 & -\frac{3}{14} \\ 0 & \frac{3}{2} \end{bmatrix} $

and one notices (in general) that $L(\gamma) = R(\gamma^{-1}) $. But then, the double cosets with $a=\frac{2}{3} $ are represented by the rational b’s in the interval $[0,\frac{1}{3}) $ and those with $a=\frac{3}{2} $ by the rational b’s in the interval $\frac{1}{2} $. In general, the double cosets of matrices with fixed $a = \frac{r}{s} $ with $~(r,s)=1 $ are the rational points in the line-segment over $a $ with $b \in [0,\frac{1}{s}) $.

That is, the Bost-Connes double coset space $\Gamma_0 \backslash \Gamma / \Gamma_0 $ are the rational points in a horrible fractal comb. Below we have drawn only the part of the dyadic values, that is when $a = \frac{r}{2^t} $ in the unit inverval

and of course we have to super-impose on it similar pictures for rationals with other powers as their denominators. Fortunately, NCG excels in describing such fractal beasts…

UPDATE : here is a slightly beter picture of the coset space, drawing the part over all rational numbers contained in the 15-th Farey sequence. The blue segments of length one are at 1,2,3,…

Quiver-superpotentials

Published January 14, 2008 by lievenlb

It’s been a while, so let’s include a recap : a (transitive) permutation representation of the modular group $\Gamma = PSL_2(\mathbb{Z}) $ is determined by the conjugacy class of a cofinite subgroup $\Lambda \subset \Gamma $, or equivalently, to a dessin d’enfant. We have introduced a quiver (aka an oriented graph) which comes from a triangulation of the compactification of $\mathbb{H} / \Lambda $ where $\mathbb{H} $ is the hyperbolic upper half-plane. This quiver is independent of the chosen embedding of the dessin in the Dedeking tessellation. (For more on these terms and constructions, please consult the series Modular subgroups and Dessins d’enfants).

Why are quivers useful? To start, any quiver $Q $ defines a noncommutative algebra, the path algebra $\mathbb{C} Q $, which has as a $\mathbb{C} $-basis all oriented paths in the quiver and multiplication is induced by concatenation of paths (when possible, or zero otherwise). Usually, it is quite hard to make actual computations in noncommutative algebras, but in the case of path algebras you can just see what happens.

Moreover, we can also see the finite dimensional representations of this algebra $\mathbb{C} Q $. Up to isomorphism they are all of the following form : at each vertex $v_i $ of the quiver one places a finite dimensional vectorspace $\mathbb{C}^{d_i} $ and any arrow in the quiver
[tex]\xymatrix{\vtx{v_i} \ar[r]^a & \vtx{v_j}}[/tex] determines a linear map between these vertex spaces, that is, to $a $ corresponds a matrix in $M_{d_j \times d_i}(\mathbb{C}) $. These matrices determine how the paths of length one act on the representation, longer paths act via multiplcation of matrices along the oriented path.

A necklace in the quiver is a closed oriented path in the quiver up to cyclic permutation of the arrows making up the cycle. That is, we are free to choose the start (and end) point of the cycle. For example, in the one-cycle quiver

[tex]\xymatrix{\vtx{} \ar[rr]^a & & \vtx{} \ar[ld]^b \\ & \vtx{} \ar[lu]^c &}[/tex]

the basic necklace can be represented as $abc $ or $bca $ or $cab $. How does a necklace act on a representation? Well, the matrix-multiplication of the matrices corresponding to the arrows gives a square matrix in each of the vertices in the cycle. Though the dimensions of this matrix may vary from vertex to vertex, what does not change (and hence is a property of the necklace rather than of the particular choice of cycle) is the trace of this matrix. That is, necklaces give complex-valued functions on representations of $\mathbb{C} Q $ and by a result of Artin and Procesi there are enough of them to distinguish isoclasses of (semi)simple representations! That is, linear combinations a necklaces (aka super-potentials) can be viewed, after taking traces, as complex-valued functions on all representations (similar to character-functions).

In physics, one views these functions as potentials and it then interested in the points (representations) where this function is extremal (minimal) : the vacua. Clearly, this does not make much sense in the complex-case but is relevant when we look at the real-case (where we look at skew-Hermitian matrices rather than all matrices). A motivating example (the Yang-Mills potential) is given in Example 2.3.2 of Victor Ginzburg’s paper Calabi-Yau algebras.

Let $\Phi $ be a super-potential (again, a linear combination of necklaces) then our commutative intuition tells us that extrema correspond to zeroes of all partial differentials $\frac{\partial \Phi}{\partial a} $ where $a $ runs over all coordinates (in our case, the arrows of the quiver). One can make sense of differentials of necklaces (and super-potentials) as follows : the partial differential with respect to an arrow $a $ occurring in a term of $\Phi $ is defined to be the path in the quiver one obtains by removing all 1-occurrences of $a $ in the necklaces (defining $\Phi $) and rearranging terms to get a maximal broken necklace (using the cyclic property of necklaces). An example, for the cyclic quiver above let us take as super-potential $abcabc $ (2 cyclic turns), then for example

$\frac{\partial \Phi}{\partial b} = cabca+cabca = 2 cabca $

(the first term corresponds to the first occurrence of $b $, the second to the second). Okay, but then the vacua-representations will be the representations of the quotient-algebra (which I like to call the vacualgebra)

$\mathcal{U}(Q,\Phi) = \frac{\mathbb{C} Q}{(\partial \Phi/\partial a, \forall a)} $

which in ‘physical relevant settings’ (whatever that means…) turn out to be Calabi-Yau algebras.

But, let us return to the case of subgroups of the modular group and their quivers. Do we have a natural super-potential in this case? Well yes, the quiver encoded a triangulation of the compactification of $\mathbb{H}/\Lambda $ and if we choose an orientation it turns out that all ‘black’ triangles (with respect to the Dedekind tessellation) have their arrow-sides defining a necklace, whereas for the ‘white’ triangles the reverse orientation makes the arrow-sides into a necklace. Hence, it makes sense to look at the cubic superpotential $\Phi $ being the sum over all triangle-sides-necklaces with a +1-coefficient for the black triangles and a -1-coefficient for the white ones. Let’s consider an index three example from a previous post

[tex]\xymatrix{& & \rho \ar[lld]_d \ar[ld]^f \ar[rd]^e & \\
i \ar[rrd]_a & i+1 \ar[rd]^b & & \omega \ar[ld]^c \\
& & 0 \ar[uu]^h \ar@/^/[uu]^g \ar@/_/[uu]_i &}[/tex]

In this case the super-potential coming from the triangulation is

$\Phi = -aid+agd-cge+che-bhf+bif $

and therefore we have a noncommutative algebra $\mathcal{U}(Q,\Phi) $ associated to this index 3 subgroup. Contrary to what I believed at the start of this series, the algebras one obtains in this way from dessins d’enfants are far from being Calabi-Yau (in whatever definition). For example, using a GAP-program written by Raf Bocklandt Ive checked that the growth rate of the above algebra is similar to that of $\mathbb{C}[x] $, so in this case $\mathcal{U}(Q,\Phi) $ can be viewed as a noncommutative curve (with singularities).

However, this is not the case for all such algebras. For example, the vacualgebra associated to the second index three subgroup (whose fundamental domain and quiver were depicted at the end of this post) has growth rate similar to that of $\mathbb{C} \langle x,y \rangle $…

I have an outlandish conjecture about the growth-behavior of all algebras $\mathcal{U}(Q,\Phi) $ coming from dessins d’enfants : the algebra sees what the monodromy representation of the dessin sees of the modular group (or of the third braid group).
I can make this more precise, but perhaps it is wiser to calculate one or two further examples…

One Comment

the crypto lattice

Published January 12, 2008 by lievenlb

Last time we have seen that tori are dual (via their group of characters) to lattices with a Galois action. In particular, the Weil descent torus $R_n=R^1_{\mathbb{F}_{p^n}/\mathbb{F}_p} \mathbb{G}_m $ corresponds to the permutation lattices $R_n^* = \mathbb{Z}[x]/(x^n-1) $. The action of the generator $\sigma $ (the Frobenius) of the Galois group $Gal(\mathbb{F}_{p^n}/\mathbb{F}_p) $ acts on the lattice by multiplication with $x $.

An old result of Masuda (1955), using an even older lemma by Speiser (1919), asserts than whenever the character-lattice $T^* $ of a torus $T $ is a permutation-lattice, the torus is rational, that is, the function-field
of the torus $\mathbb{F}_p(T) $ is purely trancendental

$\mathbb{F}_p(y_1,\ldots,y_d) = \mathbb{F}_p(T) = (\mathbb{F}_{q^n}(T^*))^{Gal} $

(recall from last time that the field on the right-hand side is the field of fractions of the $Gal $-invariants of the group-algebra of the free Abelian group $T^* = \mathbb{Z} \oplus \ldots \oplus \mathbb{Z} $ where the rank is equal to the dimension $d $ of the torus).

The basic observation made by Rubin and Silverberg was that the known results on crypto-compression could be reformulated in the language of algebraic tori as : the tori $T_2 $ (LUC-system) and $T_6 $ (CEILIDH-system) are rational! So, what about the next cryptographic challenges? Are the tori $T_{30} $, $T_{210} $ etc. also rational varieties?

Recall that as a group, the $\mathbb{F}_p $-points of the torus $T_n $, is the subgroup of $\mathbb{F}_{p^n}^* $ corresponding to the most crypto-challenging cyclic subgroup of order $\Phi_n(p) $ where $\Phi_n(x) $ is the n-th cyclotomic polynomial. The character-lattice of this crypto-torus $T_n $ we call the crypto-lattice and it is

$T_n^* = \mathbb{Z}[x]/(\Phi_n(x)) $

(again the action of the Frobenius is given by multiplication with $x $) and hence has rank $\phi(n) $, explaining that the torus $T_n $ has dimension $\phi(n) $ and hence that we can at best expect a compression from $n $-pits to $\phi(n) $-pits. Note that the lattice $T_n^* $ is no longer a permutation lattice, so we cannot use the Masuda-Speiser result to prove rationality of $T_n $.

What have mathematicians proved on $T_n $ before it became a hot topic? Well, there is an old conjecture by V. E. Voskresenskii asserting that all $T_n $ should be rational! Unfortunately, he could prove this only when $n $ is a prime power. Further, he proved that for all $n $, the lattice $T_n $ is at least stably-rational meaning that it is rational upto adding free parameters, that is

$\mathbb{F}_p(T_n)(z_1,\ldots,z_l) = \mathbb{F}_p(y_1,\ldots,y_{d+l}) $

which, sadly, is only of cryptographic-use if $l $ is small (see below). A true rationality result on $T_n $ was proved by A.A. Klyashko : $T_n $ is rational whenever $n=p^a.q^b $ a product of two prime powers.But then, $30=2 \times 3 \times 5 $ the first unknown case…

At Crypto 2004, Marten van Dijk and David Woodruff were able to use an explicit form of Voskresenskii stable rationality result to get an asymptotic optimal crypto-compression rate of $n/\phi(n) $, but their method was of little practical use in the $T_{30} $, for what their method gave was a rational map

$T_{30} \times \mathbb{A}^{32}_{\mathbb{F}_p} \rightarrow \mathbb{A}^{40}_{\mathbb{F}_p} $

and the number of added parameters (32) is way too big to be of use.

But then, one can use century-old results on cyclotomic polynomials to get a much better bound, as was shown in the paper Practical cryptography in high dimensional tori by the collective group of all people working (openly) on tori-cryptography. The idea is that whenever q is a prime and a is an integer not divisible by q, then on the level of cyclotomic polynomials we have the identity

$\Phi_{aq}(x) \Phi_a(x) = \Phi_a(x^q) $

On the level of tori this equality implies (via the character-lattices) an ismorphism (with same assumptions)

$T_{aq}(\mathbb{F}_p) \times T_a(\mathbb{F}_p) \simeq (R^1_{\mathbb{F}_{p^q}/\mathbb{F}_p} T_a)(\mathbb{F}_p) = T_a(\mathbb{F}_{p^q}) $

whenever aq is not divisible by p. Apply this to the special case when $q=5,a=6 $ then we get

$T_{30}(\mathbb{F}_p) \times T_6(\mathbb{F}_p) \simeq R^1_{\mathbb{F}_{p^5}/\mathbb{F}_p} T_6(\mathbb{F}_p) $

and because we know that $T_6 $ is a 2-dimensional rational torus we get, using Weil descent, a rational map

$T_{30} \times \mathbb{A}^2_{\mathbb{F}_p} \rightarrow \mathbb{A}^{10}_{\mathbb{F}_p} $

which can be used to get better crypto-compression than the CEILIDH-system!

This concludes what I know of the OPEN state of affairs in tori-cryptography. I’m sure ‘people in hiding’ know a lot more at the moment and, if not, I have a couple of ideas I’d love to check out. So, when I seem to have disappeared, you know what happened…