Skip to content →

Tag: groups

Quiver-superpotentials

Published January 14, 2008 by lieven

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…

Leave a Comment

ECSTR aka XTR

Published January 5, 2008 by lieven

The one thing that makes it hard for an outsider to get through a crypto-paper is their shared passion for using nonsensical abbreviations. ECSTR stands for “Efficient Compact Subgroup Trace Representation” and we are fortunate that Arjen Lenstra and Eric Verheul shortened it in their paper The XTR public key system to just XTR. As both of them speak Dutch, they will know why Ive chosen a magpie-picture on the left… Btw. there is a nice MSRI-talk by Lenstra, starting off with a couple of jokes on what ECSTR is NOT meant to abbreviate (one of them being ‘Elliptic Curve Systems Too Risky’… (( I may even start to share their passion… )) ).

The XTR-system uses safety of $\mathbb{F}_{p^6} $ in the Diffie-Hellman key exchange while transmitting only $2=\phi(6) $ pits. The first question one asks is : why the jump from $N=2 $ from last time to $N=6 $? Well, remember that (conjecturally) we want to use safety of $\mathbb{F}_q $ for $q=p^N $ while using only $\phi(N) $ pits. That is, we want to have $N log(p) $ large (for safety) while at the same time $\phi(N) log(p) $ small (for efficiency). Thus, the most useful N’s to consider are those in the sequence

$N=1,~2,~6=2.3,~30=2.3.5,~210=2,3,5,7,~\ldots $

that is, the products of the first so many prime numbers. The number of elements of the cyclic group $\mathbb{F}_q^* $ is equal to

$p^6-1 = (p-1)(p+1)(p^2+p+1)(p^2-p+1) $

and that the subgroup of order $p-1 $ can be embedded in $\mathbb{F}_p^* $, that of order $p+1 $ can be embedded in $\mathbb{F}_{p^2}^* $, that of order $p^2+p+1 $ can be embedded in $\mathbb{F}_{p^3}^* $, BUT that the subgroup of order $\Phi_6(p)=p^2-p+1 $ CANNOT be embedded in any $\mathbb{F}_{p^i}^* $ for $i = 1,2,3 $, or in other words, the $p^2-p+1 $ subgroup is as hard as $\mathbb{F}_{p^6}^* $. So, let us take a generator $g $ of the subgroup $T_6 $ of order $p^2-p+1 $ and do the Diffie-Hellman trick with it in a modified manner.

Galois groups of finite fields are cyclic and generated by the Frobenius $x \mapsto x^p $. In particular, the Galois group $Gal(\mathbb{F}_{p^6}/\mathbb{F}_{p^2}) = C_3 $ is cyclic of order three and consists of the auromorphisms ${ 1=id, \sigma = (x \mapsto x^{p^2}), \sigma^2 = (x \mapsto x^{p^4}) } $, so the corresponding trace map is given by

$Tr~:~\mathbb{F}_{p^6} \rightarrow \mathbb{F}_{p^2} \qquad Tr(x) = x + x^{p^2} + x^{p^4} $

So, how do we perform our key-exchange using my secret number $a $ and yours $b $? Well, I’ll send you $Tr(g^a) $ and as this is an element of the quadratic extension $\mathbb{F}_{p^2} $ I’ll need just 2 pits instead of 6 and you will send me likewise $Tr(g^b) $. I claim that the common key we (and only we) can compute is $Tr(g^{ab}) $. How does this work?

Given any element $x \in T_6 \subset \mathbb{F}_{p^6}^* $ we can compute the 3-element set $C_x = { x,\sigma(x),\sigma(x^2) } $ and hence the characteristic polynomial
$~(t-x)(t-\sigma(x))(t-\sigma^2(x)) $

$ = t^3 – (x+\sigma(x)+\sigma^2(x))t^2 + (x \sigma(x)+ x\sigma^2(x)+\sigma(x)\sigma^2(x))t – x \sigma(x)\sigma^2(x) $

The first coefficient $x+\sigma(x)+\sigma^2(x) $ is the trace $Tr(x) $ and the second and third coefficients are respectively $Tr(x \sigma(x)) $ and the norm $N(x) $. Now, if $x \in T_6 $ one can show that

$Tr(x \sigma(x)) = Tr(x)^p $ and $N(x)=1 $

That is, from knowing only $Tr(x) $ we can compute the characteristic polynomial and hence recover the 3-element set ${ h,\sigma(h),\sigma^2(h) } $!

If I give you $Tr(g^a) $ you can compute from it the 3-set ${ g^a,\sigma(g^a),\sigma^2(g^a) } $ and raise them all the the b-th power (b being your secret number) to obtain

${ g^{ab},\sigma(g^a)^b,\sigma^2(g^a)^b } = { g^{ab},\sigma(g^{ab}),\sigma^2(g^{ab}) } $

but then you also know our shared key $Tr(g^{ab}) = g^{ab}+\sigma(g^{ab})+\sigma^2(g^{ab}) $… Done!

Leave a Comment

quivers versus quilts

Published January 2, 2008 by lieven

We have associated to a subgroup of the modular group $PSL_2(\mathbb{Z}) $ a quiver (that is, an oriented graph). For example, one verifies that the fundamental domain of the subgroup $\Gamma_0(2) $ (an index 3 subgroup) is depicted on the right by the region between the thick lines with the identification of edges as indicated. The associated quiver is then

\[
\xymatrix{i \ar[rr]^a \ar[dd]^b & & 1 \ar@/^/[ld]^h \ar@/_/[ld]_i \\
& \rho \ar@/^/[lu]^d \ar@/_/[lu]_e \ar[rd]^f & \\
0 \ar[ru]^g & & i+1 \ar[uu]^c}
\]

The corresponding “dessin d’enfant” are the green edges in the picture. But, the red dot on the left boundary is identied with the red dot on the lower circular boundary, so the dessin of the modular subgroup $\Gamma_0(2) $ is

\[
\xymatrix{| \ar@{-}[r] & \bullet \ar@{-}@/^8ex/[r] \ar@{-}@/_8ex/[r] & -}
\]

Here, the three red dots (all of them even points in the Dedekind tessellation) give (after the identification) the two points indicated by a $\mid $ whereas the blue dot (an odd point in the tessellation) is depicted by a $\bullet $. There is another ‘quiver-like’ picture associated to this dessin, a quilt of the modular subgroup $\Gamma_0(2) $ as studied by John Conway and Tim Hsu.

On the left, a quilt-diagram copied from Hsu’s book Quilts : central extensions, braid actions, and finite groups, exercise 3.3.9. This ‘quiver’ has also 5 vertices and 7 arrows as our quiver above, so is there a connection?

A quilt is a gadget to study transitive permutation representations of the braid group $B_3 $ (rather than its quotient, the modular group $PSL_2(\mathbb{Z}) = B_3/\langle Z \rangle $ where $\langle Z \rangle $ is the cyclic center of $B_3 $. The $Z $-stabilizer subgroup of all elements in a transitive permutation representation of $B_3 $ is the same and hence of the form $\langle Z^M \rangle $ where M is called the modulus of the representation. The arrow-data of a quilt, that is the direction of certain edges and their labeling with numbers from $\mathbb{Z}/M \mathbb{Z} $ (which have to satisfy some requirements, the flow rules, but more about that another time) encode the Z-action on the permutation representation. The dimension of the representation is $M \times k $ where $k $ is the number of half-edges in the dessin. In the above example, the modulus is 5 and the dessin has 3 (half)edges, so it depicts a 15-dimensional permutation representation of $B_3 $.

If we forget the Z-action (that is, the arrow information), we get a permutation representation of the modular group (that is a dessin). So, if we delete the labels and directions on the edges we get what Hsu calls a modular quilt, that is, a picture consisting of thick edges (the dessin) together with dotted edges which are called the seams of the modular quilt. The modular quilt is merely another way to depict a fundamental domain of the corresponding subgroup of the modular group. For the above example, we have the indicated correspondences between the fundamental domain of $\Gamma_0(2) $ in the upper half-plane (on the left) and as a modular quilt (on the right)

That is, we can also get our quiver (or its opposite quiver) from the modular quilt by fixing the orientation of one 2-cell. For example, if we fix the orientation of the 2-cell $\vec{fch} $ we get our quiver back from the modular quilt


\[
\xymatrix{i \ar[rr]^a \ar[dd]^b & & 1 \ar@/^/[ld]^h \ar@/_/[ld]_i \\
& \rho \ar@/^/[lu]^d \ar@/_/[lu]_e \ar[rd]^f & \\
0 \ar[ru]^g & & i+1 \ar[uu]^c}
\]

This shows that the quiver (or its opposite) associated to a (conjugacy class of a) subgroup of $PSL_2(\mathbb{Z}) $ does not depend on the choice of embedding of the dessin (or associated cuboid tree diagram) in the upper half-plane. For, one can get the modular quilt from the dessin by adding one extra vertex for every connected component of the complement of the dessin (in the example, the two vertices corresponding to 0 and 1) and drawing a triangulation from them (the dotted lines or ‘seams’).

One Comment