Posts Tagged ‘arxiv’



Quiver-superpotentials

Monday, January 14th, 2008

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 \xymatrix{\vtx{v_i} \ar[r]^a & \vtx{v_j}} 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

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

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

\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 &}

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…

thanks for linking

Friday, January 11th, 2008

I’ve re-installed the Google analytics plugin on december 22nd, so it is harvesting data for three weeks only. Still, it is an interesting tool to gain insight in the social networking aspect of math-blogging, something I’m still very bad at…

Below the list of all blogs referring at least 10 times over this last three weeks. In brackets are the number of referrals and included are the average time Avg. they spend on this site, as well as the bounce back rate BB. It gives me the opportunity to link back to some of their posts, as a small token of gratitude. I may repeat this in the future, so please keep on linking…

Not Even Wrong (69) : Avg (1.05 min) BB (52.94%)

The most recent post of Peter is an update on the plagiarism scandal on the arXiv.

The n-category cafe (63) : Avg (2.13 min) BB (50%)

The one series I followed at the cafe lately was the Geometric Representation Theory course run by John Baez and James Dolan. They provide downloadable movies as well as notes.

Richard Borcherd’s blog (47) : Avg (1.53 min) BB (53.19%)

It is great to see that Borcherds has taken up blogging again, with a post on the uselessness of set theory.

The Arcadian functor (32) : Avg (3.45 min) BB (34.38 %)

It is clear from the low bounce-back rate and the high average time spend on this site, that Kea’s readers and mine have common interests. Often I feel that Kea and I are talking about the same topics, but that our language is so different, that it is difficult for me to spot the precise connection. I definitely should start (for myself) a translation-project of her M-theory posts.

RupertGee’s iBlog (23) : Avg (6.48 min) BB (34.7 %)

Surprisingly, and contrasting to my previous rant iTouch-people (or at least those coming here from Rupert Gee’s blog) sure take time to read the posts and look for more.

Ars Mathematica (22) : Avg (0:01 min) BB (77,2 %)

Well, the average time and bounce back rate say it all : people coming here from Ars Mathematica are not interested in longer posts…

iTouch Fans Forum (14) : Avg (2:07 min) BB (42.86 %)

Again, better statistics than I would have expected.

Vivatsgasse 7 (13) : Avg (1:51 min) BB (38.46 %)

I hope these guys haven’t completely given up on blogging as it is one of my favourites.

Sixth form mathematics (12) : Avg (1:40 min) BB (25 %)

My few old posts on LaTeXrender still draw referrals…

Strategic Boards (12) : Avg (0:01 min) BB (91.67 %)

People in strategic board games are not really in my game-posts it seems…

The Everything Seminar (11) : Avg (2:04 min) BB (72.73 %)

Greg Muller has been posting a couple of nice posts on chord diagrams, starting here.

Noncommutative Geometry (11) : Avg (3:36 min) BB (27.27 %)

Well, we are interested in the same thing viewed from different angles, so good average times and a low bounce back rate. Maybe, I should make another attempt to have cross-interaction between the two blogs.

Doodles worth millions (or not)

Thursday, January 10th, 2008

Via PD1, who told me the story on her 23rd birthday, yesterday.

The story starts with Alex Matter, whose father, Herbert, and mother, Mercedes, were artists and friends of Jackson Pollock, famous for his drip-paintings. He discovered a group of small drip paintings in a storage locker in Wainscott, N.Y. which he believed to be authentic Pollocks, and if he is proved right, they would be worth millions of dollars.

Usually such discoveries lead to heated debates among art-critics and Pollock-experts whether one finds proof to authenticate the paintings. Not this time. In steps a mathematician who claims that he can authenticate a Pollock drip-painting by calculating its fractal dimension (??!!)… and claims that these drippings cannot be Pollocks because their dimension is too small… LOL!

This madmatician is Richard Taylor from the University of Oregon in Corvallis.

Taylor took a digital image of a Pollock painting into his lab, broke the image into its separate colors, and computed the fractal dimension of the lines in each color. Each time, he got a number between 1 and 2, confirming his notion that Pollock’s paintings are fractal. “Rather than mimicking nature,” Taylor says, Pollock “adopted its language of fractals to build his own patterns.” In 1999, Taylor reported that the fractal dimension of Pollock’s paintings increased during his life. His early drip paintings have a loose web of lines, mostly at the same scale. Because these paintings show no fractal qualities, their dimension is near 1. But Pollock’s later paintings have a dense network of overlapping lines, ranging from large, bold strokes to delicate threads, Taylor calculated a fractal dimension of 1.72 for these works.

His paper on this “Authenticating Pollock Paintings Using Fractal Geometry” can be found here. Luckily, the story doesn’t end here. In steps a graduate student in astrophysics at Case Western, Katherine Jones-Smith who had to give a seminar talk to her fellow students.

“I was sort of bored with particle astrophysics,” Jones-Smith says, so she looked around for something different. She came across an account of Taylor’s work, and “it sounded really cool,” she recalls. “The obvious check to me was to make sure that not any old scribble would appear to be fractal,” she says. “So, I made some scribbles.” Much to her surprise, when she computed the fractal dimension of her scribbles, they turned out to be greater than 1.

Recently, she arXived her findings in the paper Drip Paintings and Fractal Analysis from which the above doodles are taken, called appropriately “Gross pebbles” and “Mixed stars”.

When Katherine Jones-Smith made some doodles on a page “”pretty ugly” ones, she says”she found that they shared the qualities of a Pollock, according to an analysis that follows Taylor’s approach. “Either Taylor is wrong, or Kate’s drawings are worth $40 million,” says Jones-Smith’s collaborator Harsh Mathur. “We’d be happy either way.

More on this hilarious story can be found in this science news article, this New-York times story or the Pollocks-bollocks blog entry over at biophemera.

working archive plugin, please!

Tuesday, January 8th, 2008

Over the last two weeks Ive ported all old neverendingbooks-post from the last 4 years to a nearly readable format. Some tiny problems remain : a few TeX-heavy old posts are still in $…$ format rather than LaTeXrender-compatible (but Ill fix this soon), a few links may turn out to be dead (still have to check out those), TheLibrary-project links do not exist at the moment (have to decide whether to revive the project or to start a similar idea afresh), some other techie-things such as FoaF-stuff will be updated/expanded soon, et. etc. (and still have to port some 20 odd posts).

Anyway, the good news being that we went from about 40 posts since last july to over 310 posts, all open to the internal Search engine. Having all this stuff online is only useful if one can browse through it easily, so I wanted to install a proper up-to-date archive-plugin…

The current theme Redoable has build-in support for the Extended Live Archives v0.10beta-r18 plugin which would be ideal if I could get it installed… Im not the total newbie in installing WordPress-plugins and Ive read all the documentation and the support-forum and chmodded whathever I felt like chmodding, but still no success… If you know how to kick it into caching the necessary files, please drop a comment!

The next alternative Ive tried was the AWSOM Archive Version 1.2.3 plugin which gave me a pull-down menu just under the title-bar but not much seems to happen when using bloody Safari (Flock was OK though). Maybe Ill give it another go…

UPDATE (jan. 9th) : The AWSOM Archive seems to be working fine with the Redoable theme when custom installed in the footer. So, there is now a pulldown-menu at the bottom of the page.

**UPDATE (jan. 12th) : Ive installed the new version 1.3 of AWSOM Archive and it works from the default position **

At a loss I opted in the end for the simplest (though not the most aesthetic) plugin : Justin Blanton’s Smart Archives. This provides a year-month scheme at the top followed by a reverse ordered list of all months and titles of posts and is available as the arXiv neverendingbooks link available also from the sidebar (up, second link). I hope it will help you not to get too lost on this site…

Suggestions for a working-from-the-box WordPress Archive plugin, anyone???

tori & crypto : Diffie-Hellman or GCHQ?

Thursday, January 3rd, 2008

rationality & cryptography

  1. tori & crypto : Diffie-Hellman or GCHQ?
  2. key-compression
  3. ECSTR aka XTR
  4. A cat called CEILIDH
  5. Weil descent
  6. the crypto lattice

Boris Kunyavskii arXived the paper Algebraic tori - thirty years after dedicated to the 80th anniversary of V. E. Voskresenskii. The goal is to give an overview of results of V. E. Voskresenskii on arithmetic and birational properties of algebraic tori which culminated in his monograph “Algebraic Tori” published in Russian 30 years ago. As Ive worked on this stuff a long time ago I glanced through the paper and it contains a nice summary of the work of V.E. Voskresenskii, and later of Jean-Louis Colliot-Thelene, Jean-Jacques Sansuc and David Saltman. To my surprise I also made a guest-appearance and even seem to have a conjecture (??!!). Fortunately the ‘conjecture’ turned out to be correct as was proved by Nicole Lemire and Martin Lorenz. But a much bigger surprise (at least to me) is contained in the final section of the paper where applications of (stable) rationality of certain tori are given to primality testing and public key cryptography!

In [GPS] the authors propose to use a similar idea of compression for using tori in an even more recent cryptographic protocol (so-called pairing-based cryptography). It is interesting to note that the efficiency (compression factor) of the above mentioned cryptosystems heavily depends on rationality of tori under consideration (more precisely, on an explicit rational parameterization of the underlying variety). As the tori used by Rubin and Silverberg are known to be stably rational, the seemingly abstract question on rationality of a given stably rational torus is moving to the area of applied mathematics. The first challenging problem here is to obtain an explicit rational parameterization of the 8-dimensional torus T_{30} , deïfined over a finite field k and splitting over its cyclic extension L of degree 30.
This is a particular case of a problem posed by Voskresenskii [Vo77, Problem 5.12] 30 years ago. Let us hope that we will not have to wait another 30 years for answering this question on a degree 30 extension.

That’s all it takes to get me seriously side-tracked… so the last couple of hours I’ve been reading up on this connection between tori and cryptography. I will spend a couple of posts on these beautiful results. The latest seems to be that, while rationality of T_{30} is still unknown, one can use an explicit stable-rationality description of it to get a better bound than the XTR-system (the system corresponding to the torus T_{6}) which in turn is better than the LUC-system (corresponding to T_2), which is turn is twice as efficient as the Diffie-Hellman key exchange system… So let us start gently with the latter one…

Whitfield Diffie (r.) and Martin Hellman (m.) published in 1976 their public key-exchange system. Take a large prime power q=p^N, make it public and consider the finite field \mathbb{F}_q which is known to have a cyclic group of units \mathbb{F}^*_q of order q-1. Now, take g to be an element in it of large order (preferable a generator but that isnt necessary) and also make this element public.

Now choose a random integer a (your hidden secret) and compute the element g^a \in \mathbb{F}_q and publicize this element. Suppose someone else published his/her element g^b constructed from his/her secret integer b then both you and this other person can compute from the published data and their secret numbers the element (the shared key)

g^{ab}=(g^b)^a = (g^a)^b

(because you know a and the published g^b and your correspondent knows b and the published g^a) but nobody else can compute it from the public-available data only because discrete logarithms cannot be feasibly computed in the group \mathbb{F}_q^*. Hellman suggests to call this system the Diffie-Hellman-Merkl key-exchange (via this link)

The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem — Diffie and Hellman on public key cryptography and Merkle on public key distribution — when they became aware of each other’s work and realized there was synergy in their approaches. In Hellman’s words: “We each had a key part of the puzzle and while it’s true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery.”

And that was the full story until 1997. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970’s in the field of “non-secret encryption”. The people involved are James Ellis, Clifford Cocks and Malcolm Williamson (r.).

Here is a note by Ellis on his recollection of the history of ‘Non-secret encryption” :

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from continued secrecy.
In keeping with this tradition it is now appropriate to tell the story of the invention and development within CESG of non-secret encryption (NSE) which was our original name for what is now called PKC. The task of writing this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned…

The once secret notes of Williamson are also available. NON-SECRET ENCRYPTION USING A FINITE FIELD by M J Williamson, 21 January 1974 and THOUGHTS ON CHEAPER NON-SECRET ENCRYPTION M J Williamson, 10 August 1976.

AWSOM Powered