polyeantic [polymake wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== polyeantic ======

This extension serves as a wrapper for [[https://github.com/flatsurf/e-antic|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.

===== Download =====

TODO: distribution

===== Installation =====

This requires an installation of polymake, version TODO, E-ANTIC, version 1.0.1, and its dependencies.

Start up polymake and run:
<code>
polytope > import_extension("/path/to/extension","--with-antic=/path/to/antic","--with-arb=/path/to/arb","--with-eantic=/path/to/eantic");
</code>

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.
<code>
$ cd /path/to/extension/
$ bash install_deps.sh
</code>
Then you start polymake's interactive session and do:
<code>
polytope > $path = "/path/to/extension";
polytope > $depspath = "$path/build/deps/install";
polytope > import_extension($path,"--with-antic=$depspath","--with-arb=$depspath","--with-eantic=$depspath");
</code>

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 [[user_guide/extend/extensions|guide to polymake's extension system]].

===== Introduction =====

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.

====== An introduction to polyeantic ======

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.

===== NumberField =====

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%%''.

<code perl>
> $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])
</code>
Equivalently, the polynomial can be given by a combination of two ''%%String%%''s, one of which is the pretty string representation and the other one specifies the variable name:

<code perl>
> $nf = new NumberField("a^2 - a - 1", "a", 1.61803, .00001);
> print $nf;
NumberField(a^2 - 1*a - 1, [1.618033988749894848205 +/- 6.52e-22])
</code>
Printing the ''%%NumberField%%'' reveals two pieces of information:

  - a pretty string display of the defining polynomial
  - and an approximated value of the generator. The precision of a ''%%NumberField%%'' is set during construction by passing an additional ''%%Int%%'' (default value: ''%%64%%'') but can also be refined retroactively:

<code perl>
> refine_embedding($nf, 2048);
> print $nf;
NumberField(a^2 - 1*a - 1, [1.618033988749894848204586834365638117720309179805762862135448623 +/- 2.95e-64])
</code>
===== NumberFieldElement =====

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]$:

<code perl>
> $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
</code>
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 ''%%NumberFieldElement%%''s can be handled intuitively using operators for arithmetic and comparison:

<code perl>
> print(1/$a + 1/$a**2 == 1);
true
</code>
==== NumberFieldElement as a Scalar type ====

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$.

<code perl>
> $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;
</code>
=== NumberFieldElement and QuadraticExtension ===

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).

<code perl>
> $j = johnson_solid(2);
> $p = new Polytope<NumberFieldElement>(VERTICES=>$j->VERTICES);
> print $p->FACETS==convert_to<NumberFieldElement>($j->FACETS);
true
</code>
Of course, these ''%%Polytope%%''s 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 ''%%NumberFieldElement%%''s in our ''%%Polytope%%''s properties.

<code perl>
> 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).
</code>
We can easily check that the maximality holds true by multiplying each vertex with the objective function:

<code perl>
> 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)
</code>