In mathematics, an infrastructure is a group-like structure appearing in global fields.
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
is the discriminant of the quadratic field; previous methods required
[1] Ten years later, H. W. Lenstra published[2] a mathematical framework describing the infrastructure of a real quadratic number field in terms of "circular groups".
It was also described by R. Schoof[3] and H. C. Williams,[4] and later extended by H. C. Williams, G. W. Dueck and B. K. Schmid to certain cubic number fields of unit rank one[5][6] and by J. Buchmann and H. C. Williams to all number fields of unit rank one.
[7] 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.
[8] The first description of infrastructures in number fields of arbitrary unit rank was given by R. Schoof using Arakelov divisors in 2008.
This was done first by A. Stein and H. G. Zimmer in the case of real hyperelliptic function fields.
[10] It was extended to certain cubic function fields of unit rank one by Renate Scheidler and A.
[11][12] In 1999, S. Paulus and H.-G. Rück related the infrastructure of a real quadratic function field to the divisor class group.
[13] This connection can be generalized to arbitrary function fields and, combining with R. Schoof's results, to all global fields.
, one can see a one-dimensional infrastructure as a circle with a finite set of points on it.
A baby step is a unary operation
Visualizing the infrastructure as a circle, a baby step assigns each point of
is naturally an abelian group, one can consider the sum
To formalize this concept, assume that there is a map
, called the giant step operation.
This choice, seeming somewhat arbitrary, appears in a natural way when one tries to obtain infrastructures from global fields.
[14] Other choices are possible as well, for example choosing an element
); 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.
[16] 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.
together with a relatively small real number; this has been first described by D. Hühnlein and S. Paulus[17] and by M. J. Jacobson, Jr., R. Scheidler and H. C. Williams[18] 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.
More generally, one can define a similar concept for all one-dimensional infrastructures; these are sometimes called
-representations, one can obtain a reduction map by setting
-representations and reduction maps are in a one-to-one correspondence.
In certain cases, this group operation can be explicitly described without using