Skip to content →

Tag: Galois

the Bost-Connes Hecke algebra

As before, $\Gamma $ is the subgroup of the rational linear group $GL_2(\mathbb{Q}) $ consisting of the matrices

$\begin{bmatrix} 1 & b \\ 0 & a \end{bmatrix} $ with $a \in \mathbb{Q}_+ $ and $\Gamma_0 $ the subgroup of all matrices $\begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix} $ with $n \in \mathbb{N} $. Last time, we have seen that the double coset space $\Gamma_0 \backslash \Gamma / \Gamma_0 $ can be identified with the set of all rational points in the fractal comb consisting of all couples $~(a,b) $ with $a=\frac{m}{n} \in \mathbb{Q}_+ $ and $b \in [0,\frac{1}{n}) \cap \mathbb{Q} $

The blue spikes are at the positive natural numbers $a={ 1,2,3,\ldots } $. Over $a=1 $ they correspond to the matrices $\begin{bmatrix} 1 & \gamma \\ 0 & 1 \end{bmatrix} $ with $\gamma \in [0,1) \cap \mathbb{Q} $ and as matrix-multiplication of such matrices corresponds to addition of the $\gamma $ we see that these cosets can be identified with the additive group $\mathbb{Q}/\mathbb{Z} $ (which will reappear at a later stage as the multiplicative group of all roots of unity).

The Bost-Connes Hecke algebra $\mathcal{H} = \mathcal{H}(\Gamma,\Gamma_0) $ is the convolution algebra of all comlex valued functions with finite support on the double coset space $\Gamma_0 \backslash \Gamma / \Gamma_0 $. That is, as a vector space the algebra has as basis the functions $e_X $ with $X \in \Gamma_0 \backslash \Gamma / \Gamma_0 $ (that is, $X $ is a point of the fractal comb) and such that $e_X(X)=1 $ and $e_X(Y)=0 $ for all other double cosets $Y \not= X $. The algebra product on $\mathcal{H} $ is the convolution-product meaning that if $f,f’ $ are complex functions with finite support on the Bost-Connes space, then they can also be interpreted as $\Gamma_0 $-bi-invariant functions on the group $\Gamma $ (for this just means that the function is constant on double cosets) and then $f \ast f’ $ is the function defined for all $\gamma \in \Gamma $ by

$f \ast f'(\gamma) = \sum_{\mu \in \Gamma/ \Gamma_0} f(\mu) f'(\mu^{-1} \gamma) $

Last time we have seen that the coset-space $\Gamma / \Gamma_0 $ can be represented by all rational points $~(a,b) $ with $b<1 $. At first sight, the sum above seems to be infinite, but, f and f’ are non-zero only at finitely many double cosets and we have see last time that $\Gamma_0 $ acts on one-sided cosets with finite orbits. Therefore, $f \ast f $ is a well-defined $\Gamma_0 $-bi-invariant function with finite support on the fractal comb $\Gamma_0 \backslash \Gamma / \Gamma_0 $. Further, observe that the unit element of $\mathcal{H} $ is the function corresponding to the identity matrix in $\Gamma $.

Looking at fractal-comb picture it is obvious that the Bost-Connes Hecke algebra $\mathcal{H} $ is a huge object. Today, we will prove the surprising result that it can be generated by the functions corresponding to the tiny portion of the comb, shown below.

That is, we will show that $\mathcal{H} $ is generated by the functions $e(\gamma) $ corresponding to the double-coset $X_{\gamma} = \begin{bmatrix} 1 & \gamma \\ 0 & 1 \end{bmatrix} $ (the rational points of the blue line-segment over 1, or equivalently, the elements of the group $\mathbb{Q}/\mathbb{Z} $), together with the functions $\phi_n $ corresponding to the double-coset $X_n = \begin{bmatrix} 1 & 0 \\ 0 & n \end{bmatrix} $ for all $ n \in \mathbb{N}_+ $ (the blue dots to the right in the picture) and the functions $\phi_n^* $ corresponding to the double cosets $X_{1/n} = \begin{bmatrix} 1 & 0 \\ 0 & \frac{1}{n} \end{bmatrix} $ (the red dots to the left).

Take a point in the fractal comb $X = \begin{bmatrix} 1 & \gamma \\ 0 & \frac{m}{n} \end{bmatrix} $ with $~(m,n)=1 $ and $\gamma \in [0,\frac{1}{n}) \cap \mathbb{Q} \subset [0,1) \cap \mathbb{Q} $. Note that as $\gamma < \frac{1}{n} $ we have that $n \gamma < 1 $ and hence $e(n \gamma) $ is one of the (supposedly) generating functions described above.

Because $X = \begin{bmatrix} 1 & \gamma \\ 0 & \frac{m}{n} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & m \end{bmatrix} \begin{bmatrix} 1 & n \gamma \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & \frac{1}{n} \end{bmatrix} = X_m X_{n \gamma} X_{1/n} $ we are aiming for a relation in the Hecke algebra $\phi_m \ast e(n \gamma) \ast \phi^*_n = e_X $. This is ‘almost’ true, except from a coefficient.

Let us prove first the equality of functions $e_X \ast \phi_n = n \phi_m \ast e(n \gamma) $. To do this we have to show that they have the same value for all points $Y \in \Gamma_0 \backslash \Gamma / \Gamma_0 $ in the fractal comb. Let us first study the function on the right hand side.

$\phi_m \ast e(n \gamma) = \sum_{g \in \Gamma/\Gamma_0} \phi_m(g) e(n \gamma)(g^{-1}Y) $. Because $X_m \Gamma_0 $ is already a double coset (over $m $ we have a comb-spike of length one, so all rational points on it determine at the same time a one-sided and a double coset. Therefore, $\phi_m(g) $ is zero unless $g = X_m $ and then the value is one.

Next, let us consider the function on the left-hand side. $e_X \ast \phi_n(Y) = \sum_{g \in \Gamma / \Gamma_0} e_X(g) \phi_m( g^{-1} Y) $. We have to be a bit careful here as the double cosets over $a=\frac{m}{n} $ are different from the left cosets. Recall from last time that the left-cosets over a are given by all rational points of the form $~(a,b) $ with $ b < 1 $ whereas the double-cosets over a are represented by the rational points of the form $~(a,b) $ with $b < \frac{1}{n} $ and hence the $\Gamma_0 $-orbits over a all consist of precisely n elements g.
That is, $e_X(g) $ is zero for all $ g \in \Gamma/\Gamma_0 $ except when g is one of the following matrices

$ g \in { \begin{bmatrix} 1 & \gamma \\ 0 & \frac{m}{n} \end{bmatrix}, \begin{bmatrix} 1 & \gamma+\frac{1}{n} \\ 0 & \frac{m}{n} \end{bmatrix}, \begin{bmatrix} 1 & \gamma + \frac{2}{n} \\ 0 & \frac{m}{n} \end{bmatrix}, \ldots, \begin{bmatrix} 1 & \gamma + \frac{n-1}{n} \\ 0 & \frac{m}{n} \end{bmatrix} } $

Further, $\phi_n(g^{-1}Y) $ is zero unless $g^{-1}Y \in \Gamma_0 \begin{bmatrix} 1 & 0 \\ 0 & n \end{bmatrix} \Gamma_0 $, or equivalently, that $Y \in \Gamma_0 g \Gamma_0 \begin{bmatrix} 1 & 0 \\ 0 & n \end{bmatrix} \Gamma_0 = \Gamma_0 g \begin{bmatrix} 1 & 0 \\ 0 & n \end{bmatrix} \Gamma_0 $ and for each of the choices for g we have that

$ \begin{bmatrix} 1 & \gamma + \frac{k}{n} \\ 0 & \frac{m}{n} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & n \end{bmatrix} = \begin{bmatrix} 1 & n \gamma + k \\ 0 & m \end{bmatrix} \sim \begin{bmatrix} 1 & n\gamma \\ 0 & m \end{bmatrix} $

Therefore, the function $e_X \ast \phi_n $ is zero at every point of the fractal comb unless at $\begin{bmatrix} 1 & n \gamma \\ 0 & m \end{bmatrix} $ where it is equal to $n $. This proves the claimed identity of functions and as one verifies easily that $\phi_n^* \ast \phi_n = 1 $, it follows that all base vectors $e_X $ of $\mathcal{H} $ can be expressed in the claimed generators

$ e_X = n \phi_m \ast e(n \gamma) \ast \phi_n^* $

Bost and Connes use slightly different generators, namely with $\mu_n = \frac{1}{\sqrt{n}} \phi_n $ and $\mu_n^* = \sqrt{n} \phi_n^* $ in order to have all relations among the generators being defined over $\mathbb{Q} $ (as we will see another time). This will be important later on to have an action of the cyclotomic Galois group $Gal(\mathbb{Q}^{cycl}/\mathbb{Q}) $ on certain representations of $\mathcal{H} $.

5 Comments

the crypto lattice

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…

Leave a Comment

Weil descent

A classic Andre Weil-tale is his narrow escape from being shot as a Russian spy

The war was a disaster for Weil who was a conscientious objector and so wished to avoid military service. He fled to Finland, to visit Rolf Nevanlinna, as soon as war was declared. This was an attempt to avoid being forced into the army, but it was not a simple matter to escape from the war in Europe at this time. Weil was arrested in Finland and when letters in Russian were found in his room (they were actually from Pontryagin describing mathematical research) things looked pretty black. One day Nevanlinna was told that they were about to execute Weil as a spy, and he was able to persuade the authorities to deport Weil instead.

However, Weil’s wikipedia entry calls this a story too good to be true, and continues

In 1992, the Finnish mathematician Osmo Pekonen went to the archives to check the facts. Based on the documents, he established that Weil was not really going to be shot, even if he was under arrest, and that Nevanlinna probably didn’t do – and didn’t need to do – anything to save him. Pekonen published a paper on this with an afterword by Andre Weil himself. Nevanlinna’s motivation for concocting such a story of himself as the rescuer of a famous Jewish mathematician probably was the fact that he had been a Nazi sympathizer during the war. The story also appears in Nevanlinna’s autobiography, published in Finnish, but the dates don’t match with real events at all. It is true, however, that Nevanlinna housed Weil in the summer of 1939 at his summer residence Korkee at Lohja in Finland – and offered Hitler’s Mein Kampf as bedside reading.

This old spy-story gets a recent twist now that it turns out that Weil’s descent theory of tori has applications to cryptography. So far, I haven’t really defined what tori are, so let us start with some basics.

The simplest (and archetypical) example of an algebraic torus is the multiplicative group(scheme) $\mathbb{G}_m $ over a finite field $\mathbb{F}_q $ which is the affine variety

$\mathbb{V}(xy-1) \subset \mathbb{A}^2_{\mathbb{F}_q} $. that is, the $\mathbb{F}_q $ points of $\mathbb{G}_m $ are precisely the couples ${ (x,\frac{1}{x})~:~x \in \mathbb{F}_q^* } $ and so are in one-to-one correspondence with the non-zero elements of $\mathbb{F}_q $. The coordinate ring of this variety is the ring of Laurant polynomials $\mathbb{F}_q[x,x^{-1}] $ and the fact that multiplication induces a group-structure on the points of the variety can be rephrased by saying that this coordinate ring is a Hopf algebra which is just the Hopf structure on the group-algebra $\mathbb{F}_q[\mathbb{Z}] = \mathbb{F}_q[x,x^{-1}] $. This is the first indication of a connection between tori defined over $\mathbb{F}_q $ and lattices (that is free $\mathbb{Z} $-modules with an action of the Galois group $Gal(\overline{F}_q/F_q) $. In this correspondence, the multiplicative group scheme $\mathbb{G}_m $ corresponds to $\mathbb{Z} $ with the trivial action.

Now take a field extension $\mathbb{F}_q \subset \mathbb{F}_{q^n} $, is there an affine variety, defined over $\mathbb{F}_q $ whose $\mathbb{F}_q $-points are precisely the invertible elements $\mathbb{F}_{q^n}^* $? Sure! Just take the multiplicative group over $\mathbb{F}_{q^n} $ and write the elements x and y as $x = x_1 + x_2 a_2 + \ldots + x_n a_n $ (and a similar expression for y with ${ 1,a_2,\ldots,a_n }$ being a basis of $\mathbb{F}_{q^n}/\mathbb{F}_q $ and write the defning equation $xy-1 $ out, also with respect to this basis and this will then give you the equations of the desired variety, which is usually denoted by $R^1_{\mathbb{F}_{q^n}/\mathbb{F}_q} \mathbb{G}_m $ and called the Weil restriction of scalars torus.

A concrete example? Take $\mathbb{F}_9 = \mathbb{F}_3(\sqrt{-1}) $ and write $x=x_1+x_2 \sqrt{-1} $ and $y=y_1+y_2 \sqrt{-1} $, then the defining equation $xy-1 $ becomes

$~(x_1y_1-x_2y_2) + (x_1y_2-x_2y_1) \sqrt{-1} = 1 $

whence $R^1_{\mathbb{F}_9/\mathbb{F}_3} = \mathbb{V}(x_1y_1-x_2y_2-1,x_1y_2-x_2y_1) \subset \mathbb{A}^4_{\mathbb{F}_3} $, the intersection of two quadratic hypersurfaces in 4-dimensional space.

Why do we call $R^1 \mathbb{G}_m $ a _torus_? Well, as with any variety defined over $\mathbb{F}_q $ we can also look at its points over a field-extension, for example over the algebraic closure $\overline{\mathbb{F}}_q $ and then it is easy to see that

$R^1_{\mathbb{F}_{q^n}/\mathbb{F}_q} \mathbb{G}_m (\overline{\mathbb{F}}_q) = \overline{\mathbb{F}}_q^* \times \ldots \times \overline{\mathbb{F}}_q^* $ (n copies)

and such algebraic groups are called tori. (To understand terminology, the compact group corresponding to $\mathbb{C}^* \times \mathbb{C}^* $ is $U_1 \times U_1 = S^1 \times S^1 $, so a torus).

In fact, it is already the case that the $\mathbb{F}_{q^n} $ points of the restriction of scalar torus are $\mathbb{F}_{q^n}^* \times \ldots \times \mathbb{F}_{q^n}^* $ and therefore we call this field a splitting field of the torus.

This is the general definition of an algebraic torus : a torus T over $\mathbb{F}_q $ is an affine group scheme over $\mathbb{F}_q $ such that, if we extend scalars to the algebraic closure (and then it already holds for a finite extension) we get an isomorphism of affine group schemes

$T \times_{\mathbb{F}_q} \overline{\mathbb{F}}_q = \overline{\mathbb{F}}_q^* \times \ldots \times \overline{\mathbb{F}}_q^* = (\overline{\mathbb{F}}_q^*)^{n} $

in which case we call T a torus of dimension n. Clearly, the Galois group $Gal(\overline{\mathbb{F}}_q^*/\mathbb{F}_q) $ acts on the left hand side in such a way that we recover $T $ as the orbit space for this action.

Hence, anther way to phrase this is to say that an algebraic torus is the Weil descent of an action of the Galois group on the algebraic group $\overline{\mathbb{F}}_q^* \times \ldots \times \overline{\mathbb{F}}_q^* $.

Of course we can also rephrase this is more algebraic terms by looking at the coordinate rings. The coordinate ring of the algebraic group $~(\overline{\mathbb{F}}_q^*)^n $ is the group-algebra of the rank n lattice $\mathbb{Z}^n = \mathbb{Z} \oplus \ldots \oplus \mathbb{Z} $ (the free Abelian group of rank n), that is,
$\overline{\mathbb{F}}_q [ \mathbb{Z}^n ] $. Now the Galois group acts both on the field $\overline{\mathbb{F}}_q $ as on the lattice $\mathbb{Z}^n $ coming from the action of the Galois group on the extended torus $T \times_{\mathbb{F}_q} \overline{\mathbb{F}}_q $. In fact, it is best to denote this specific action on $\mathbb{Z}^n $ by $T^* $ and call $T^* $ the character group of $T $. Now, we recover the coordinate ring of the $\mathbb{F}_q $-torus $T $ as the ring of invariants

$\mathbb{F}_q[T] = \overline{\mathbb{F}}_q [T^*]^{Gal(\overline{\mathbb{F}}_q/\mathbb{F}_q)} $

Hence, the restriction of scalars torus $R^1_{\mathbb{F}_{q^n}/\mathbb{F}_q} \mathbb{G}_m $ is an n-dimensional torus over $\mathbb{F}_q $ and its corresponding character group is the free Abelian group of rank n which can be written as $\mathbb{Z}[x]/(x^n-1) = \mathbb{Z}1 \oplus \mathbb{Z}x \oplus \ldots \oplus \mathbb{Z}x^{n-1} $ and where the action of the cyclic Galois group $Gal(\mathbb{F}_{q^n}/\mathbb{F}_q) = C_n = \langle \sigma \rangle $ s such that the generator $\sigma $ as as multiplication by $x $. That is, in this case the character group is a permutation lattice meaning that the $\mathbb{Z} $-module has a basis which is permuted under the action of the Galois group. Next time we will encounter more difficult tori sich as the crypto-torus $T_n $.

One Comment