This extension serves as a wrapper for E-ANTIC, a software library for performing operations in real embedded number fields with arbitrary precision.
A new Scalar type, NumberFieldElement, is introduced which can take advantage of polymake's existing features. This allows for many possibilities to combine algebraic and geometric properties.
TODO: distribution
This requires an installation of polymake, version TODO, E-ANTIC, version 1.0.1, and its dependencies.
Start up polymake and run:
polytope > import_extension("/path/to/extension","--with-antic=/path/to/antic","--with-arb=/path/to/arb","--with-eantic=/path/to/eantic");
The optional –with-package arguments can be omitted if the respective package is installed at a standard location.
For Linux, polyeantic has a script file called install_deps.sh in its main directory which installs any requirements (besides polymake) to a sub-directory.
$ cd /path/to/extension/ $ bash install_deps.sh
Then you start polymake's interactive session and do:
polytope > $path = "/path/to/extension"; polytope > $depspath = "$path/build/deps/install"; polytope > import_extension($path,"--with-antic=$depspath","--with-arb=$depspath","--with-eantic=$depspath");
Do not forget to use an absolute path! Afterwards you are good to run the code. This import needs to be performed only once. The reference to the extension is permanently stored in $HOME/.polymake/settings. For more details there is a guide to polymake's extension system.
Most of this extension's capabilities reside within the application common; only the client regular_n_gon is part of the application polytope.
For an interactive version of this introduction we refer to the jupyter notebook file demo/introduction.ipynb which is covering the basic usage of this extension.
This jupyter notebook is meant to provide the user with the tools to use the Scalar type NumberFieldElement, which is powered by E-ANTIC. It consists of small examples which progressively demonstrate usage and capabilities of this extension.
A number field is the extension $\mathbb{Q}\left[a\right]$ of the rational numbers $\mathbb{Q}$ generated by an algebraic number $a$. That especially means that there exists a polynomial with rational coefficients such that $a$ is root of said polynomial. While a number field is purely algebraic (which also is reflected in the way E-ANTIC does its computations) the real embedding allows us to assign fitting values to the additional elements of $\mathbb{Q}\left[a\right]$. We can conclude that we can precisely define a number field by naming a defining polynomial together with a small enough interval (for uniqueness of the root while embedding), setting the foundation for constructing a NumberField. Note that a certain knowledge about the polynomial and/or the algebraic number is therefore required to receive the desired real-embedded number field.
The following lines create the number field $\mathbb{Q}\left[\phi\right]$ generated by the golden ratio $\phi$, positive root of $a^2 - a - 1$. We make use of the constructor NumberField(UniPolynomial p, double m, double r) where p is the defining polynomial and the interval is described by a combination of the midpoint m and the radius r.
> $p = new UniPolynomial<Rational,Int>("x^2 - x - 1"); > $nf = new NumberField($p, 1.61803, .00001); > print $nf; NumberField(a^2 - 1*a - 1, [1.618033988749894848205 +/- 6.52e-22])
Equivalently, the polynomial can be given by a combination of two Strings, one of which is the pretty string representation and the other one specifies the variable name:
> $nf = new NumberField("a^2 - a - 1", "a", 1.61803, .00001); > print $nf; NumberField(a^2 - 1*a - 1, [1.618033988749894848205 +/- 6.52e-22])
Printing the NumberField reveals two pieces of information:
NumberField is set during construction by passing an additional Int (default value: 64) but can also be refined retroactively:
> refine_embedding($nf, 2048); > print $nf; NumberField(a^2 - 1*a - 1, [1.618033988749894848204586834365638117720309179805762862135448623 +/- 2.95e-64])
A NumberFieldElement is exactly what the name suggests: It represents an element living in a number field. Every NumberFieldElement requires a parent NumberField which is usually given to the constructor. There are two cases to be considered: the number field element $x$ is trivial (i.e. $x\in\mathbb{Q}$) or it is non-trivial (i.e. $x\in\mathbb{Q}\left[a\right]\setminus\mathbb{Q}$). The first case can be completely covered by polymake's Rational (and other types which Rational can be constructed from), whereas the latter can be viewed as a polynomial in $\mathbb{Q}$ over the generator $a$. This polynomial must either be a UniPolynomial<Rational,Int> or a pretty String. We construct some elements of $\mathbb{Q}\left[\phi\right]$:
> $a = new NumberFieldElement($nf, "a"); > > $p2 = new UniPolynomial<Rational,Int>("1 - x"); > $nfe_pol = new NumberFieldElement($nf, $p2); > > $nfe_one = new NumberFieldElement($nf, 1); > > $r = new Rational("inf"); > $nfe_inf = new NumberFieldElement($nf, $r); > > print join("\n", $a, $nfe_pol, $nfe_one, $nfe_inf); (a ~ 1.6180340) (-a+1 ~ -0.61803399) 1 inf
The output also shows a difference between the trivial and the non-trivial case. Trivial elements are printed directly, whereas the non-trivial elements display is split into the precise algebraic representation and its approximation, separated by a ~. These NumberFieldElements can be handled intuitively using operators for arithmetic and comparison:
> print(1/$a + 1/$a**2 == 1); true
The statement we just printed indeed is true, as it is equivalent to $a being the root of the generating polynomial $a^2 - a - 1$. The golden ratio is known for its appealing geometrical attributes, many of which appear in nature, arts and science. We will now utilize the fact that NumberFieldElement has been implemented as a Scalar type to create a visualization of said attributes. The following code will create a spiral of squares of regularly decreasing side length (i.e. by factor $\phi^{-1}$), for which we will use polymake's PolyhedralComplex type. Starting with side length $1$, this will result in a progressing covering of the rectangle with side lengths $\phi$ and $1$.
> $n = 20; # number of additional squares; the first 6 squares establish regularity in construction > > $vert = new Matrix<NumberFieldElement>(16 + 2*$n, 3); # collect values for input property `POINTS` > $poly = new Array<Array<Int>>(6 + $n); # collect values for input property > > # side length = 1 > $vert->[0] = [1, 0, 0]; > $vert->[1] = [1, 0, 1]; > $vert->[2] = [1, 1, 1]; > $vert->[3] = [1, 1, 0]; > $poly->[0] = [0, 1, 2, 3]; > > # side length = 1/a > $d = new Vector<NumberFieldElement>([0, 0, -1/$a]); # to calculate new vertices of current square from existing points > $vert->[4] = [1, $a, 1]; > $vert->[5] = $vert->[4] + $d; > $vert->[6] = $vert->[2] + $d; > $poly->[1] = [2, 4, 5, 6]; > > # side length = 1/a^2 > $d = new Vector<NumberFieldElement>([0, $d->[2]/$a, -$d->[1]/$a]); # rotate and scale from previous d > $vert->[7] = [1, $a, 0]; > $vert->[8] = $vert->[7] + $d; > $vert->[9] = $vert->[5] + $d; > $poly->[2] = [5, 7, 8, 9]; > > # side length = 1/a^3 > $d = new Vector<NumberFieldElement>([0, $d->[2]/$a, -$d->[1]/$a]); > $vert->[10] = $vert->[3] + $d; > $vert->[11] = $vert->[8] + $d; > $poly->[3] = [8, 3, 10, 11]; > > # side length = 1/a^4 > $d = new Vector<NumberFieldElement>([0, $d->[2]/$a, -$d->[1]/$a]); > $vert->[12] = $vert->[6] + $d; > $vert->[13] = $vert->[10] + $d; > $poly->[4] = [10, 6, 12, 13]; > > # side length = 1/a^5 > $d = new Vector<NumberFieldElement>([0, $d->[2]/$a, -$d->[1]/$a]); > $vert->[14] = $vert->[9] + $d; > $vert->[15] = $vert->[12] + $d; > $poly->[5] = [12, 9, 14, 15]; > > # the previous polytopes set up enough information that we can progress in a regular pattern from now on > for (my $i = 0; $i < $n; $i++) { > # side length = 1/a^(6+i) > $d = new Vector<NumberFieldElement>([0, $d->[2]/$a, -$d->[1]/$a]); > $vert->[16 + 2*$i] = $vert->[11 + 2*$i] + $d; > $vert->[17 + 2*$i] = $vert->[14 + 2*$i] + $d; > $poly->[6 + $i] = [14 + 2*$i, 11 + 2*$i, 16 + 2*$i, 17 + 2*$i]; > } > > $c = new fan::PolyhedralComplex<NumberFieldElement>(POINTS=>$vert, INPUT_POLYTOPES=>$poly); > $c->VISUAL;
Because $\sqrt{x}$ is root of a polynomial with rational coefficients for $x\in\mathbb{Q}$, any QuadraticExtension<Rational> type variable can losslessly be converted to a NumberFieldElement. The following lines take the VERTICES from a the pentagonal pyramid, a Johnson solid which is implemented using the QuadraticExtension type, to construct a Polytope<NumberFieldElement> and perform a convex hull computation on this new object. We compare the FACETS of our new polytope with the FACETS of our inital johnson solid to test for correctness (note: this quick comparison is possible because for both objects the same algorithm was used; otherwise the FACETS would be permuted).
> $j = johnson_solid(2); > $p = new Polytope<NumberFieldElement>(VERTICES=>$j->VERTICES); > print $p->FACETS==convert_to<NumberFieldElement>($j->FACETS); true
Of course, these Polytopes can be equipped with a linear program. Let us take a look at the constraints this polytope describes and then define our objective function. For this cause we want to construct a new NumberFieldElement living in the same NumberField. We can access this by calling the user method parent on one of the NumberFieldElements in our Polytopes properties.
> print_constraints($p->FACETS); > $a = new NumberFieldElement($p->FACETS->[0][0]->parent, "a"); > $obj = new Vector<NumberFieldElement>([0,1, $a/2, 5]); > $p->LP(LINEAR_OBJECTIVE=>$obj); > $res = $p->LP->MAXIMAL_VALUE; > print "The maximal value is $res."; 0: x1 - x2 - x3 >= (-1/12*a-5/12 ~ -0.60300566) 1: (1/2*a+1/2 ~ 1.6180340) x2 + x3 >= (-1/6 ~ -0.16666667) 2: (-1/2*a+3/2 ~ 0.38196601) x1 - x2 >= (-1/6*a ~ -0.37267800) 3: -(-1/2*a+3/2 ~ 0.38196601) x1 - x2 >= (-1/6*a ~ -0.37267800) 4: -x1 - x2 - x3 >= (-1/12*a-5/12 ~ -0.60300566) 5: -(-1/2*a+3/2 ~ 0.38196601) x2 - x3 >= (-1/6*a ~ -0.37267800) The maximal value is (17/24*a+9/8 ~ 2.7088815).
We can easily check that the maximality holds true by multiplying each vertex with the objective function:
> for (my $i = 0; $i < $p->VERTICES->rows(); $i++) { > my $val = $p->VERTICES->row($i) * $obj; > print $val <= $res, ": ", $val, "\n"; > } true: (-5/12*a+5/2 ~ 1.5683050) true: (-5/12*a-5/2 ~ -3.4316950) true: (-1/24*a-3/8 ~ -0.46816950) true: (-13/24*a-7/8 ~ -2.0862035) true: (17/24*a+9/8 ~ 2.7088815) true: (17/24*a+1/8 ~ 1.7088815)