Differences

This shows you the differences between two versions of the page.

--- extensions:eantic [2021/07/10 16:42] – jordan
+++ extensions:eantic [2021/08/07 23:09] (current) – jordan
@@ Line 34: / Line 34: @@
 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]].
-===== Examples =====
+===== 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 further explanations we refer to the jupyter notebook file ''demo/introduction.ipynb'' which is covering the basic usage of this extension. This example is taken from there.
+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.
-We create the number field $\mathbb{Q}\left[\phi\right]$ generated by the **golden ratio** $\phi$, positive root of $a^2 - a - 1$. Therefore 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''.
+====== An introduction to polyeantic ======
-<code>
+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);
@@ Line 48: / Line 56: @@
 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:
-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:
-<code>
+  - a pretty string display of the defining polynomial
-$nf = new NumberField("a^2 - a - 1", "a", 1.61803, .00001);
+  - 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 =====
-An element of a number field can be constructed by stating its parent number field together with its value. This value can either trivially be given as another Scalar type, e.g. `Int`, or as a polynomial over the generator of the number field. This polynomial can either be given as an ''UniPolynomial<Rational,Int>'' or a pretty ''String''.
+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>
+<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)
@@ Line 74: / Line 94: @@
 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:
-The output of printing values dependent on the generator of the number field (which is displayed as ''a'') is split by a ''~'' into two representations, the exact algebraic polynomial over ''a'' and an approximate float.
+<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.";
+: x1 - x2 - x3 >= (-1/12*a-5/12 ~ -0.60300566)
+: (1/2*a+1/2 ~ 1.6180340) x2 + x3 >= (-1/6 ~ -0.16666667)
+: (-1/2*a+3/2 ~ 0.38196601) x1 - x2 >= (-1/6*a ~ -0.37267800)
+: -(-1/2*a+3/2 ~ 0.38196601) x1 - x2 >= (-1/6*a ~ -0.37267800)
+: -x1 - x2 - x3 >= (-1/12*a-5/12 ~ -0.60300566)
+: -(-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>
-Further, these ''NumberFieldElement''s can be handled intuitively using operators for arithmetic and comparison.