Infrastructure (number theory)

Last updated November 12, 2024

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 ${\mathcal {O}}(D^{1/4+\varepsilon })$ binary operations (for every $\varepsilon >0$ ), where $D$ is the discriminant of the quadratic field; previous methods required ${\mathcal {O}}(D^{1/2+\varepsilon })$ binary operations.^[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.^[9]

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.^[10] It was extended to certain cubic function fields of unit rank one by Renate Scheidler and A. Stein.^[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.^[14]

One-dimensional case

Abstract definition

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

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

Giant steps and reduction maps

Observing that $\mathbb {R} /R\mathbb {Z}$ is naturally an abelian group, one can consider the sum $d(x)+d(y)\in \mathbb {R} /R\mathbb {Z}$ for $x,y\in X$ . In general, this is not an element of $d(X)$ . But instead, one can take an element of $d(X)$ which lies nearby. To formalize this concept, assume that there is a map $red:\mathbb {R} /R\mathbb {Z} \to X$ ; then, one can define $gs(x,y):=red(d(x)+d(y))$ to obtain a binary operation $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 $red$ . Assuming that one wants to have the condition $red\circ d=\mathrm {id} _{X}$ , a range of possibilities remain. One possible choice^[15] is given as follows: for $v\in \mathbb {R} /R\mathbb {Z}$ , define $f_{v}:=\inf\{f\geq 0\mid v-f\in d(X)\}$ ; then one can define $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 $x\in d(X)$ such that $|d(x)-v|$ is minimal (here, $|d(x)-v|$ is stands for $\inf\{|f-v|\mid f\in d(x)\}$ , as $d(x)$ is of the form $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]

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 $\mathbb {R} /R\mathbb {Z}$

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

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

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

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

Related Research Articles

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

In mathematics, the unitary group of degree n, denoted U(n), is the group of n × n unitary matrices, with the group operation of matrix multiplication. The unitary group is a subgroup of the general linear group GL(n, C), and it has as a subgroup the special unitary group, consisting of those unitary matrices with determinant 1.

In mathematics, a self-adjoint operator on a complex vector space V with inner product $is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A * . By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.$

<span class="mw-page-title-main">Adjoint representation</span> Mathematical term

In mathematics, the adjoint representation of a Lie group G is a way of representing the elements of the group as linear transformations of the group's Lie algebra, considered as a vector space. For example, if G is $, the Lie group of real n -by- n invertible matrices, then the adjoint representation is the group homomorphism that sends an invertible n -by- n matrix to an endomorphism of the vector space of all linear transformations of defined by: .$

In mathematics, an algebraic torus, where a one dimensional torus is typically denoted by $,, or, is a type of commutative affine algebraic group commonly found in projective algebraic geometry and toric geometry. Higher dimensional algebraic tori can be modelled as a product of algebraic groups . These groups were named by analogy with the theory of tori in Lie group theory. For example, over the complex numbers the algebraic torus is isomorphic to the group scheme, which is the scheme theoretic analogue of the Lie group . In fact, any -action on a complex vector space can be pulled back to a -action from the inclusion as real manifolds.$

In mathematics and in theoretical physics, the Stone–von Neumann theorem refers to any one of a number of different formulations of the uniqueness of the canonical commutation relations between position and momentum operators. It is named after Marshall Stone and John von Neumann.

In mathematics, the metaplectic group Mp_2n is a double cover of the symplectic group Sp_2n. It can be defined over either real or p-adic numbers. The construction covers more generally the case of an arbitrary local or finite field, and even the ring of adeles.

The following are important identities involving derivatives and integrals in vector calculus.

An external ray is a curve that runs from infinity toward a Julia or Mandelbrot set. Although this curve is only rarely a half-line (ray) it is called a ray because it is an image of a ray.

In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781.

The M. Riesz extension theorem is a theorem in mathematics, proved by Marcel Riesz during his study of the problem of moments.

In mathematics, the Morse–Palais lemma is a result in the calculus of variations and theory of Hilbert spaces. Roughly speaking, it states that a smooth enough function near a critical point can be expressed as a quadratic form after a suitable change of coordinates.

In mathematics, the spin representations are particular projective representations of the orthogonal or special orthogonal groups in arbitrary dimension and signature. More precisely, they are two equivalent representations of the spin groups, which are double covers of the special orthogonal groups. They are usually studied over the real or complex numbers, but they can be defined over other fields.

In operator theory, a branch of mathematics, a positive-definite kernel is a generalization of a positive-definite function or a positive-definite matrix. It was first introduced by James Mercer in the early 20th century, in the context of solving integral operator equations. Since then, positive-definite functions and their various analogues and generalizations have arisen in diverse parts of mathematics. They occur naturally in Fourier analysis, probability theory, operator theory, complex function-theory, moment problems, integral equations, boundary-value problems for partial differential equations, machine learning, embedding problem, information theory, and other areas.

In mathematics, especially in the area of algebra known as representation theory, the representation ring of a group is a ring formed from all the finite-dimensional linear representations of the group. Elements of the representation ring are sometimes called virtual representations. For a given group, the ring will depend on the base field of the representations. The case of complex coefficients is the most developed, but the case of algebraically closed fields of characteristic p where the Sylow p-subgroups are cyclic is also theoretically approachable.

In mathematical analysis, and especially in real, harmonic analysis and functional analysis, an Orlicz space is a type of function space which generalizes the L^p spaces. Like the L^p spaces, they are Banach spaces. The spaces are named for Władysław Orlicz, who was the first to define them in 1932.

In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.

Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on $. Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical theorem of Stokes can be stated in one sentence:$

Coherent states have been introduced in a physical context, first as quasi-classical states in quantum mechanics, then as the backbone of quantum optics and they are described in that spirit in the article Coherent states. However, they have generated a huge variety of generalizations, which have led to a tremendous amount of literature in mathematical physics. In this article, we sketch the main directions of research on this line. For further details, we refer to several existing surveys.

In financial mathematics and stochastic optimization, the concept of risk measure is used to quantify the risk involved in a random outcome or risk position. Many risk measures have hitherto been proposed, each having certain characteristics. The entropic value at risk (EVaR) is a coherent risk measure introduced by Ahmadi-Javid, which is an upper bound for the value at risk (VaR) and the conditional value at risk (CVaR), obtained from the Chernoff inequality. The EVaR can also be represented by using the concept of relative entropy. Because of its connection with the VaR and the relative entropy, this risk measure is called "entropic value at risk". The EVaR was developed to tackle some computational inefficiencies of the CVaR. Getting inspiration from the dual representation of the EVaR, Ahmadi-Javid developed a wide class of coherent risk measures, called g-entropic risk measures. Both the CVaR and the EVaR are members of this class.

References

↑ D. Shanks: The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pp. 217-224. University of Colorado, Boulder, 1972. MR 389842
↑ H. W. Lenstra Jr.: On the calculation of regulators and class numbers of quadratic fields. Number theory days, 1980 (Exeter, 1980), 123–150, London Math. Soc. Lecture Note Ser., 56, Cambridge University Press, Cambridge, 1982. MR 697260
↑ R. J. Schoof: Quadratic fields and factorization. Computational methods in number theory, Part II, 235–286, Math. Centre Tracts, 155, Math. Centrum, Amsterdam, 1982. MR 702519
↑ H. C. Williams: Continued fractions and number-theoretic computations. Number theory (Winnipeg, Man., 1983). Rocky Mountain J. Math. 15 (1985), no. 2, 621–655. MR 823273
↑ H. C. Williams, G. W. Dueck, B. K. Schmid: A rapid method of evaluating the regulator and class number of a pure cubic field. Math. Comp. 41 (1983), no. 163, 235–286. MR 701638
↑ G. W. Dueck, H. C. Williams: Computation of the class number and class group of a complex cubic field. Math. Comp. 45 (1985), no. 171, 223–231. MR 790655
↑ J. Buchmann, H. C. Williams: On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Math. Comp. 50 (1988), no. 182, 569–579. MR 929554
↑ J. Buchmann: Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift, Düsseldorf, 1987. PDF
↑ R. Schoof: Computing Arakelov class groups. (English summary) Algorithmic number theory: lattices, number fields, curves and cryptography, 447–495, Math. Sci. Res. Inst. Publ., 44, Cambridge University Press, 2008. MR 2467554 PDF
↑ A. Stein, H. G. Zimmer: An algorithm for determining the regulator and the fundamental unit of hyperelliptic congruence function field. In "Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91," Association for Computing Machinery, (1991), 183–184.
↑ R. Scheidler, A. Stein: Unit computation in purely cubic function fields of unit rank 1. (English summary) Algorithmic number theory (Portland, OR, 1998), 592–606, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. MR 1726104
↑ R. Scheidler: Ideal arithmetic and infrastructure in purely cubic function fields. (English, French summary) J. Théor. Nombres Bordeaux 13 (2001), no. 2, 609–631. MR 1879675
↑ S. Paulus, H.-G. Rück: Real and imaginary quadratic representations of hyperelliptic function fields. (English summary) Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817
1 2 Fontein, F. (2011). "The Infrastructure of a Global Field of Arbitrary Unit Rank". Math. Comp. 80 (276): 2325–2357. arXiv: 0809.1685 . doi:10.1090/S0025-5718-2011-02490-7. S2CID 14352393.
1 2 3 F. Fontein: Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. (English summary) Adv. Math. Commun. 2 (2008), no. 3, 293–307. MR 2429459
↑ S. D. Galbraith, M. Harrison, D. J. Mireles Morales: Efficient hyperelliptic arithmetic using balanced representation for divisors. (English summary) Algorithmic number theory, 342–356, Lecture Notes in Comput. Sci., 5011, Springer, Berlin, 2008. MR 2467851
↑ D. Hühnlein, S. Paulus: On the implementation of cryptosystems based on real quadratic number fields (extended abstract). Selected areas in cryptography (Waterloo, ON, 2000), 288–302, Lecture Notes in Comput. Sci., 2012, Springer, 2001. MR 1895598
↑ M. J. Jacobson Jr., R. Scheidler, H. C. Williams: The efficiency and security of a real quadratic field based key exchange protocol. Public-key cryptography and computational number theory (Warsaw, 2000), 89–112, de Gruyter, Berlin, 2001 MR 1881630

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[shanks-infrastructure-1] D. Shanks: The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pp. 217-224. University of Colorado, Boulder, 1972. MR 389842

[lenstra-infrastructure-2] H. W. Lenstra Jr.: On the calculation of regulators and class numbers of quadratic fields. Number theory days, 1980 (Exeter, 1980), 123–150, London Math. Soc. Lecture Note Ser., 56, Cambridge University Press, Cambridge, 1982. MR 697260

[schoof-infrastructure1-3] R. J. Schoof: Quadratic fields and factorization. Computational methods in number theory, Part II, 235–286, Math. Centre Tracts, 155, Math. Centrum, Amsterdam, 1982. MR 702519

[williams-infrastructure1-4] H. C. Williams: Continued fractions and number-theoretic computations. Number theory (Winnipeg, Man., 1983). Rocky Mountain J. Math. 15 (1985), no. 2, 621–655. MR 823273

[williams-dueck-schmid-5] H. C. Williams, G. W. Dueck, B. K. Schmid: A rapid method of evaluating the regulator and class number of a pure cubic field. Math. Comp. 41 (1983), no. 163, 235–286. MR 701638

[williams-dueck-6] G. W. Dueck, H. C. Williams: Computation of the class number and class group of a complex cubic field. Math. Comp. 45 (1985), no. 171, 223–231. MR 790655

[buchmann-williams-infrastructure-7] J. Buchmann, H. C. Williams: On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Math. Comp. 50 (1988), no. 182, 569–579. MR 929554

[buchmann-habil-8] J. Buchmann: Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift, Düsseldorf, 1987. PDF

[9] R. Schoof: Computing Arakelov class groups. (English summary) Algorithmic number theory: lattices, number fields, curves and cryptography, 447–495, Math. Sci. Res. Inst. Publ., 44, Cambridge University Press, 2008. MR 2467554 PDF

[stein-zimmer-10] A. Stein, H. G. Zimmer: An algorithm for determining the regulator and the fundamental unit of hyperelliptic congruence function field. In "Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91," Association for Computing Machinery, (1991), 183–184.

[stein-scheidler-cubicinfra-11] R. Scheidler, A. Stein: Unit computation in purely cubic function fields of unit rank 1. (English summary) Algorithmic number theory (Portland, OR, 1998), 592–606, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. MR 1726104

[scheidler-infrapurecubic-12] R. Scheidler: Ideal arithmetic and infrastructure in purely cubic function fields. (English, French summary) J. Théor. Nombres Bordeaux 13 (2001), no. 2, 609–631. MR 1879675

[paulus-rueck-13] S. Paulus, H.-G. Rück: Real and imaginary quadratic representations of hyperelliptic function fields. (English summary) Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817

[fontein-infrastructure-14] 1 2 Fontein, F. (2011). "The Infrastructure of a Global Field of Arbitrary Unit Rank". Math. Comp. 80 (276): 2325–2357. arXiv: 0809.1685 . doi:10.1090/S0025-5718-2011-02490-7. S2CID 14352393.

[fontein-pohlighellman-15] 1 2 3 F. Fontein: Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. (English summary) Adv. Math. Commun. 2 (2008), no. 3, 293–307. MR 2429459

[galbraith-harrison-mirelesmorales-16] S. D. Galbraith, M. Harrison, D. J. Mireles Morales: Efficient hyperelliptic arithmetic using balanced representation for divisors. (English summary) Algorithmic number theory, 342–356, Lecture Notes in Comput. Sci., 5011, Springer, Berlin, 2008. MR 2467851

[huehnlein-paulus-17] D. Hühnlein, S. Paulus: On the implementation of cryptosystems based on real quadratic number fields (extended abstract). Selected areas in cryptography (Waterloo, ON, 2000), 288–302, Lecture Notes in Comput. Sci., 2012, Springer, 2001. MR 1895598

[jacobson-scheidler-williams-18] M. J. Jacobson Jr., R. Scheidler, H. C. Williams: The efficiency and security of a real quadratic field based key exchange protocol. Public-key cryptography and computational number theory (Warsaw, 2000), 89–112, de Gruyter, Berlin, 2001 MR 1881630

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]