Skip to main content.

n-dimensional Infrastructures.

.

For one-dimensional infrastructures, we have a circle \R/R\Z together with a finite, non-empty set X and an injective map d : X \to \R/R\Z. Now \R/R\Z = \R^n / \Lambda, where n = 1 and \Lambda is the one-dimensional lattice \Lambda = R \Z. Hence, one could say that an n-dimensional infrastructure is a torus \R^n/\Lambda together with X and d : X \to \R^n/\Lambda as above. From the discussion in the remarks of this post we see that we need some kind of reduction map to define giant steps (and also f-representations) in the one-dimensional case, even though there a pretty canonical reduction map is given. In the case of \R^n/\Lambda, we do not have something similar to a given positive direction. Moreover, definiting the “nearest” element of a finite subset of \R^n/\Lambda to some t \in \R^n/\Lambda is even more complicated and offers more choices which appear more or less obvious. Only the selection of different norms on \R^n lead to several possible definitions of such a map. Hence, we should require such a map in the definition:

Definition.

Let \Lambda \subseteq \R^n be a lattice. Then, an n-dimensional infrastructure is a non-empty finite set X together with an injective map d : X \to \R^n / \Lambda and another map red : \R^n/\Lambda \to X satisfying red \circ d = \id_X.

Again, as in the one-dimensional case, one can define giant steps:

\gs(x, x') := red(d(x) + d(x')), \quad x, x' \in X.

Moreover, one gets the same relation between reduction maps and f-representations, whence we define

\fRep := \fRep(X, d, red) := \{ (x, f) \in X \times \R^n \mid red(d(x) + f) = x \}.

Then the map

\Psi : \fRep(X, d, red) \to \R^n/\Lambda, \quad (x, f) \mapsto d(x) + f

is a bijection, and we can use this bijection to equip \fRep(X, d, red) with a group law by

(x, f) + (x', f') = \Psi^{-1}(\Psi(x, f) + \Psi(x', f')), \quad (x, f), (x', f') \in \fRep.

Discrete Infrastructure.

We say that an n-dimensional infrastructure (X, d, red) with lattice \Lambda is discrete if \Lambda \subseteq \Z^n, d(X) \subseteq \Z^n/\Lambda and if red does not depends on fractions. To make the last part more precise, define

floor : \R^n \to \Z^n, \quad (x_1, \dots, x_n) \mapsto (\floor{x_1}, \dots, \floor{x_n});

if \Lambda \subseteq \Z^n, floor induces a map \R^n/\Lambda \to \Z^n/\Lambda. Now, that red does not depends on fractions simply means that red factors through floor, i.e. that we can write red = red' \circ floor with red' : \Z^n/\Lambda \to X.

Moreover, if in the following we specify discrete infrastructures, we often just define red for values in \Z^n/\Lambda. In that case, for elements v \in \R^n/\Lambda \setminus \Z^n/\Lambda, define red(v) := red(floor(v)).

In case (X, d, red) is discrete, consider the subset

\fRep_{disc} := \fRep_{disc}(X, d, red) := \{ (x, f) \in \fRep \mid f \in \Z^n \}.

Then

\Psi|_{\fRep_{disc}} : \fRep_{disc} \to \Z^n/\Lambda

is an isomorphism.

Finite Abelian Groups as Infrastructures.

Let G be a finite abelian group, generated by g_1, \dots, g_n. Consider the relation lattice \Lambda \subseteq \Z^n for g_1, \dots, g_n, defined by

(v_1, \dots, v_n) \in \Lambda \Leftrightarrow \prod_{i=1}^n g_i^{v_i} = 1.

Then \Lambda is the kernel of \Z^n \to G, (v_1, \dots, v_n) \mapsto \prod_{i=1}^n g_i^{v_i}, and

\varphi : \Z^n/\Lambda \to G, \quad (v_1, \dots, v_n) + \Lambda \mapsto \prod_{i=1}^n g_i^{v_i}

is a group isomorphism. Define X := G, d := \varphi^{-1} and red := \varphi (or, more precisely, red := \varphi \circ floor); then (X, d, red) is an n-dimensional infrastructure. Moreover, for g, g' \in G, we have \gs(g, g') = g g', whence \gs equals the group operation of G. Hence, every finite abelian group can be seen in a natural way as an infrastructure.

Moreover, this shows that d can be thought of as an analogue to the discrete logarithm map, and red is an analogue of the power map n \mapsto g^n. In particular, we obtained the goal described in the first post of this series: we found a generalization of the discrete logarithm problem to a non-associative algebraic structure. In the next post, I will how such infrastructures can be obtained from global fields; this gives a rich source of examples for n-dimensional infrastructures.

What about baby steps?

Note that in the above discussion, I simply ignored baby steps. In the one-dimensional case, \R has a canonical direction (namely the positive one) and so has \R/R\Z, whence saying “go to the next element” makes sense. Opposed to that, in \R^n, there are infinitely many directions, no one better than another. Even if we fix a direction, “go to the next element in that direction” seems to not really make sense. So far, I have not seen any definition of baby steps in this case which works for all n-dimensional infrastructures.

Note that in the case of infrastructures obtained from global fields, one has some kind of canonical baby steps (even though there are still some choices left). In fact, there are n + 1 of them. To define them, though, one needs more information than just X, d and red: one needs information about a (n + 1)-st dimension, both for constructing the reduction map and for defining baby steps.

Categories: Algebra Number Theory
Tags:

Comments.

No comments.