Skip to main content.

Interpreting One-dimensional Infrastructures as Groups: f-Representations.

.

Let (X, d) be a one-dimensional infrastructure of circumference R > 0. We have seen that we obtain two operations \bs : X \to X and \gs : X \times X \to X together with a reduction map red : \R/R\Z \to X, and we have \gs(x, x') = red(d(x) + d(x')) for x, x' \in X. This gives us a binary operation which is in general not associative. For several reasons, it would be interesting to embed the infrastructure into a group. An obvious choice for such a group would be \R/R\Z, as we can identify X as a subset of \R/R\Z by identifying it with d(X). Such an interpretation of the infrastructure as part of a “circular group” has first been considered by Hendrik Lenstra in his 1980 paper On the computation of regulators and class numbers of quadratic fields.

The idea is to consider pairs (x, f) \in X \times \R; the map d : X \times \R \to \R/R\Z, (x, f) \mapsto d(x) + f is obviously surjective, but far from being injective. Hence, it would be a good idea to restrict X \times \R to a subset which makes this map both injective and surjective. We want this subset to contain X \times \{ 0 \}; note that d|_{X \times \{ 0 \}} : X \times \{ 0 \} \to \R/R\Z is injective and essentially equals d : X \to \R/R\Z by the identification X \leftrightarrow X \times \{ 0 \}, x \mapsto (x, 0). We obtain the following definition:

Definition.

A set of f-representations of (X, d) is a set \fRep \subseteq X \times \R such that d|_{\fRep} : \fRep \to \R/R\Z is bijective and such that X \times \{ 0 \} \subseteq \fRep.

But how to obtain such a subset? In fact, we already have all ingredients ready, as the following proposition shows, by relating f-representations to reduction maps:

Theorem.

Let (X, d) be a one-dimensional infrastructure. Let A be the set of reduction maps and B be the set of f-representations for (X, d). The map

\Phi : A \to B, \quad red \mapsto \{ (x, f) \in X \times \R \mid red(d(x) + f) = x \}

is a bijection, with its inverse given by

\Psi : B \to A, \quad \fRep \mapsto \pi_1 \circ (d|_{\fRep})^{-1},

where \pi_1 : X \times \R \to X, (x, f) \mapsto x is the projection onto the first component.

Now fix one corresponding choice of red and \fRep, and let \psi : \fRep \to \R/R\Z, (x, f) \mapsto d(x, f) = d(x) + f be the associated bijection. Then

\gs(x, x') = red(d(x) + d(x')) = \pi_1(\psi^{-1}(\psi(x, 0) + \psi(x', 0)))

for all x, x' \in X with \pi_1 : (x, f) \mapsto x being the projection. Moreover, using the bijection \psi, \fRep becomes a group which we will write additively by (x, f) + (x', f') := \psi^{-1}(\psi(x, f) + \psi(x', f')), which extends the giant steps.

Finally, let red be the map we originally defined for infrastructures, i.e. red(r) = d^{-1}(r - \min\{ f \in \R \mid f \ge 0, \; r - f \in d(X) \}) for r \in \R/R\Z. In that case, one can compute the group operation on \fRep without having to evalute \psi^{-1} or d, with only computing baby and giant steps and relative distances, i.e. d(\bs(x)) - d(x) \ge 0 resp. d(x) + d(x') - d(\gs(x, x')) \ge 0 for x, x' \in X:

Theorem.

Let D_{\min} := \min\{ d(\bs(x)) - d(x) \mid x \in X \} and D_{\max} := \max\{ d(\bs(x)) - d(x) \mid x \in X \}, and let (x, f), (x', f') \in \fRep. Then (x, f) + (x', f') can be computed with one giant step computation and at most \ceil{\frac{3 D_{\max}}{D_{\min}}} baby step computations as follows:

  1. Compute x'' := \gs(x, x') and f'' := f + f' + ( d(x) + d(x') - d(\gs(x, x')) ).
  2. Compute x''' := \bs(x'') and f''' := f'' - ( d(x''') - d(x'') ).
  3. If f''' \ge 0, set (x'', f'') := (x''', f''') and go to step 2.
  4. Return the pair (x'', f'').

In the case of infrastructures obtained from global fields, we are also able to describe the group operation in \fRep without having to evaluate \psi^{-1} or d. In fact, evaluating \psi^{-1} or d is essentially the discrete logarithm problem, for which so far no general polynomial methods for solving it exist in the case of global fields.

Categories: Algebra Number Theory
Tags:

Comments.

No comments.