Infrastructure (number theory)

In mathematics, an infrastructure is a group-like structure appearing in global fields.
Historic development.
In 1972, D. Shanks first discovered the infrastructure of a real quadratic number field and applied his baby-step giant-step algorithm to compute the regulator of such a field in formula_1 binary operations (for every formula_2), where formula_3 is the discriminant of the quadratic field; previous methods required formula_4 binary operations. Ten years later, H. W. Lenstra published a mathematical framework describing the infrastructure of a real quadratic number field in terms of "circular groups". It was also described by R. Schoof and H. C. Williams, and later extended by H. C. Williams, G. W. Dueck and B. K. Schmid to certain cubic number fields of unit rank one and by J. Buchmann and H. C. Williams to all number fields of unit rank one. In his habilitation thesis, J. Buchmann presented a baby-step giant-step algorithm to compute the regulator of a number field of "arbitrary" unit rank. The first description of infrastructures in number fields of arbitrary unit rank was given by R. Schoof using Arakelov divisors in 2008.
The infrastructure was also described for other global fields, namely for algebraic function fields over finite fields. This was done first by A. Stein and H. G. Zimmer in the case of real hyperelliptic function fields. It was extended to certain cubic function fields of unit rank one by R. Scheidler and A. Stein. In 1999, S. Paulus and H.-G. Rück related the infrastructure of a real quadratic function field to the divisor class group. This connection can be generalized to arbitrary function fields and, combining with R. Schoof's results, to all global fields.
One-dimensional case.
Abstract definition.
A one-dimensional (abstract) infrastructure formula_5 consists of a real number formula_6, a finite set formula_7 together with an injective map formula_8. The map formula_9 is often called the "distance map".
By interpreting formula_10 as a circle of circumference formula_11 and by identifying formula_12 with formula_13, one can see a one-dimensional infrastructure as a circle with a finite set of points on it.
Baby steps.
A baby step is a unary operation formula_14 on a one-dimensional infrastructure formula_5. Visualizing the infrastructure as a circle, a baby step assigns each point of formula_13 the next one. Formally, one can define this by assigning to formula_17 the real number formula_18; then, one can define formula_19.
Giant steps and reduction maps.
Observing that formula_10 is naturally an abelian group, one can consider the sum formula_21 for formula_22. In general, this is not an element of formula_13. But instead, one can take an element of formula_13 which lies "nearby". To formalize this concept, assume that there is a map formula_25; then, one can define formula_26 to obtain a binary operation formula_27, called the giant step operation. Note that this operation is in general "not" associative.
The main difficulty is how to choose the map formula_28. Assuming that one wants to have the condition formula_29, a range of possibilities remain. One possible choice is given as follows: for formula_30, define formula_31; then one can define formula_32. This choice, seeming somewhat arbitrary, appears in a natural way when one tries to obtain infrastructures from global fields. Other choices are possible as well, for example choosing an element formula_33 such that formula_34 is minimal (here, formula_34 is stands for formula_36, as formula_37 is of the form formula_38); one possible construction in the case of real quadratic hyperelliptic function fields is given by S. D. Galbraith, M. Harrison and D. J. Mireles Morales.
Relation to real quadratic fields.
D. Shanks observed the infrastructure in real quadratic number fields when he was looking at cycles of reduced binary quadratic forms. Note that there is a close relation between reducing binary quadratic forms and continued fraction expansion; one step in the continued fraction expansion of a certain quadratic irrationality gives a unary operation on the set of reduced forms, which cycles through all reduced forms in one equivalence class. Arranging all these reduced forms in a cycle, Shanks noticed that one can quickly jump to reduced forms further away from the beginning of the circle by composing two such forms and reducing the result. He called this binary operation on the set of reduced forms a giant step, and the operation to go to the next reduced form in the cycle a baby step.
Relation to formula_10.
The set formula_10 has a natural group operation and the giant step operation is defined in terms of it. Hence, it makes sense to compare the arithmetic in the infrastructure to the arithmetic in formula_10. It turns out that the group operation of formula_10 can be described using giant steps and baby steps, by representing elements of formula_10 by elements of formula_12 together with a relatively small real number; this has been first described by D. Hühnlein and S. Paulus and by M. J. Jacobson, Jr., R. Scheidler and H. C. Williams in the case of infrastructures obtained from real quadratic number fields. They used floating point numbers to represent the real numbers, and called these representations CRIAD-representations resp. formula_45-representations. More generally, one can define a similar concept for all one-dimensional infrastructures; these are sometimes called formula_46-representations.
A set of formula_46-representations is a subset formula_48 of formula_49 such that the map formula_50 is a bijection and that formula_51 for every formula_17. If formula_25 is a reduction map, formula_54 is a set of formula_46-representations; conversely, if formula_48 is a set of formula_46-representations, one can obtain a reduction map by setting formula_58, where formula_59 is the projection on $X$. Hence, sets of formula_46-representations and reduction maps are in a one-to-one correspondence.
Using the bijection formula_61, one can pull over the group operation on formula_10 to formula_48, hence turning formula_48 into an abelian group formula_65 by formula_66, formula_67. In certain cases, this group operation can be explicitly described without using formula_68 and formula_9.
In case one uses the reduction map formula_70, one obtains formula_71. Given formula_72, one can consider formula_73 with formula_74 and formula_75; this is in general no element of formula_76, but one can reduce it as follows: one computes formula_77 and formula_78; in case the latter is not negative, one replaces formula_73 with formula_80 and continues. If the value was negative, one has that formula_81 and that formula_82, i.e. formula_83.