Infrastructure (number theory)

A one-dimensional (abstract) infrastructure ${\displaystyle (X,d)}$ consists of a real number ${\displaystyle R>0}$, a finite set ${\displaystyle X\neq \emptyset }$ together with an injective map ${\displaystyle d:X\to \mathbb {R} /R\mathbb {Z} }$.[15] The map ${\displaystyle d}$ is often called the distance map.

By interpreting ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ as a circle of circumference ${\displaystyle R}$ and by identifying ${\displaystyle X}$ with ${\displaystyle d(X)}$, 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 ${\displaystyle bs:X\to X}$ on a one-dimensional infrastructure ${\displaystyle (X,d)}$. Visualizing the infrastructure as a circle, a baby step assigns each point of ${\displaystyle d(X)}$ the next one. Formally, one can define this by assigning to ${\displaystyle x\in X}$ the real number ${\displaystyle f_{x}:=\inf\{f'>0\mid d(x)+f'\in d(X)\}}$; then, one can define ${\displaystyle bs(x):=d^{-1}(d(x)+f_{x})}$.

Observing that ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ is naturally an abelian group, one can consider the sum ${\displaystyle d(x)+d(y)\in \mathbb {R} /R\mathbb {Z} }$ for ${\displaystyle x,y\in X}$. In general, this is not an element of ${\displaystyle d(X)}$. But instead, one can take an element of ${\displaystyle d(X)}$ which lies nearby. To formalize this concept, assume that there is a map ${\displaystyle red:\mathbb {R} /R\mathbb {Z} \to X}$; then, one can define ${\displaystyle gs(x,y):=red(d(x)+d(y))}$ to obtain a binary operation ${\displaystyle gs:X\times X\to X}$, called the giant step operation. Note that this operation is in general not associative.

The main difficulty is how to choose the map ${\displaystyle red}$. Assuming that one wants to have the condition ${\displaystyle red\circ d=\mathrm {id} _{X}}$, a range of possibilities remain. One possible choice[15] is given as follows: for ${\displaystyle v\in \mathbb {R} /R\mathbb {Z} }$, define ${\displaystyle f_{v}:=\inf\{f\geq 0\mid v-f\in d(X)\}}$; then one can define ${\displaystyle red(v):=d^{-1}(v-f_{v})}$. 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 ${\displaystyle x\in d(X)}$ such that ${\displaystyle |d(x)-v|}$ is minimal (here, ${\displaystyle |d(x)-v|}$ is stands for ${\displaystyle \inf\{|f-v|\mid f\in d(x)\}}$, as ${\displaystyle d(x)}$ is of the form ${\displaystyle v+R\mathbb {Z} }$); 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.

The set ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ 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 ${\displaystyle \mathbb {R} /R\mathbb {Z} }$. It turns out that the group operation of ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ can be described using giant steps and baby steps, by representing elements of ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ by elements of ${\displaystyle X}$ 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. ${\displaystyle (f,p)}$-representations. More generally, one can define a similar concept for all one-dimensional infrastructures; these are sometimes called ${\displaystyle f}$-representations.[15]

A set of ${\displaystyle f}$-representations is a subset ${\displaystyle fRep}$ of ${\displaystyle X\times \mathbb {R} /R\mathbb {Z} }$ such that the map ${\displaystyle \Psi _{fRep}:fRep\to \mathbb {R} /R\mathbb {Z} ,\;(x,f)\mapsto d(x)+f}$ is a bijection and that ${\displaystyle (x,0)\in fRep}$ for every ${\displaystyle x\in X}$. If ${\displaystyle red:\mathbb {R} /R\mathbb {Z} \to X}$ is a reduction map, ${\displaystyle fRep_{red}:=\{(x,f)\in X\times \mathbb {R} /R\mathbb {Z} \mid red(d(x)+f)=x\}}$ is a set of ${\displaystyle f}$-representations; conversely, if ${\displaystyle fRep}$ is a set of ${\displaystyle f}$-representations, one can obtain a reduction map by setting ${\displaystyle red(f)=\pi _{1}(\Psi _{fRep}^{-1}(f))}$, where ${\displaystyle \pi _{1}:X\times \mathbb {R} /R\mathbb {Z} \to X,\;(x,f)\mapsto x}$ is the projection on $X$. Hence, sets of ${\displaystyle f}$-representations and reduction maps are in a one-to-one correspondence.

Using the bijection ${\displaystyle \Psi _{fRep}:fRep\to \mathbb {R} /R\mathbb {Z} }$, one can pull over the group operation on ${\displaystyle \mathbb {R} /R\mathbb {Z} }$ to ${\displaystyle fRep}$, hence turning ${\displaystyle fRep}$ into an abelian group ${\displaystyle (fRep,+)}$ by ${\displaystyle x+y:=\Psi _{fRep}^{-1}(\Psi _{fRep}(x)+\Psi _{fRep}(y))}$, ${\displaystyle x,y\in fRep}$. In certain cases, this group operation can be explicitly described without using ${\displaystyle \Psi _{fRep}}$ and ${\displaystyle d}$.

In case one uses the reduction map ${\displaystyle red:\mathbb {R} /R\mathbb {Z} \to X,\;v\mapsto d^{-1}(v-\inf\{f\geq 0\mid v-f\in d(X)\})}$, one obtains ${\displaystyle fRep_{red}=\{(x,f)\mid f\geq 0,\;\forall f'\in [0,f):d(x)+f'\not \in d(X)\}}$. Given ${\displaystyle (x,f),(x',f')\in fRep_{red}}$, one can consider ${\displaystyle (x'',f'')}$ with ${\displaystyle x''=gs(x,x')}$ and ${\displaystyle f''=f+f'+(d(x)+d(x')-d(gs(x,x')))\geq 0}$; this is in general no element of ${\displaystyle fRep_{red}}$, but one can reduce it as follows: one computes ${\displaystyle bs^{-1}(x'')}$ and ${\displaystyle f''-(d(x'')-d(bs^{-1}(x'')))}$; in case the latter is not negative, one replaces ${\displaystyle (x'',f'')}$ with ${\displaystyle (bs^{-1}(x''),f''-(d(x'')-d(bs^{-1}(x''))))}$ and continues. If the value was negative, one has that ${\displaystyle (x'',f'')\in fRep_{red}}$ and that ${\displaystyle \Psi _{fRep_{red}}(x,f)+\Psi _{fRep_{red}}(x',f')=\Psi _{fRep_{red}}(x'',f'')}$, i.e. ${\displaystyle (x,f)+(x',f')=(x'',f'')}$.