polyeantic

A Polymake wrapper for E-ANTIC

Overview

• Introduction

• Getting Started

• Basic Usage

• Example Applications

Introduction

Real Embedded Number Fields

• The Number Field $\mathbb{Q}\left[a\right]$ is generated from an algebraic number $a$ with coefficients in $\mathbb{Q}$

• $a$ is a root of a finite non-zero (univariate) polynomial in $\mathbb{Q}$

• The real embedding allows to assign fitting values to the elements added by the extension

• $a$ is unique root of the given polynomial within a small enough neighbourhood

• Example: $a = \sqrt{2}$ is the unique root of $a^2 - 2$ on $\left[1,2\right]$ and generates a number field

E-ANTIC

• C/C++ libraray based on ANTIC

• Polynomial implementation uses flint

• Arbitrary precision calculations using arb

• Available on github: https://github.com/videlec/e-antic

Getting Started

Requirements

• Polymake
• E-ANTIC
• Their dependencies (note that both should be built with the same version of any common dependency)

Installing

• Download the files (git)
• Run Polymake
• import_extension("path/to/polyeantic/");
• Restart Polymake to compile polyeantic
• If needed, re-compiling can be initiated with reconfigure_extension("path/to/polyeantic/");
• For removal, run obliterate_extension("path/to/polyeantic/");

Basic Usage

NumberField

• Parent object resembling a specific number field $\mathbb{Q}\left[a\right]$
• Construction takes a polynomial (algebraic number) and an interval (uniqueness of root)
• Polynomial can be given in two forms:
  • UniPolynomial<Rational,Int>
  • Combination of two Strings containing the pretty string representation of the defining polynomial and the name of the polynomial's variable
• Interval is given by a combination of two Floats naming interval mid-point and radius
• (optional) Precision can be given as an Int
• The trivial case is $\mathbb{Q}$

Examples

• The following lines create the number field generated by the golden ratio, positive root of $a^2 - a - 1$:

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

• The same number field (but with higher precision) using the String constructor:

$nf = new NumberField("a^2 - a - 1", "a", 1.61803, .00001, 256);
print $nf;

NumberField(a^2 - 1*a - 1, [1.618033988749894848204586834365638117720309179805762862135448623 +/- 2.95e-64])

NumberFieldElement

• Actual scalar type extending Rational
• Needs a parent NumberField ($\mathbb{Q}$ in trivial case)
• Can be constructed with various input:
  • Rational, Integer, Int and Float for trivial elements
  • UniPolynomial or a pretty String of a polynomial over the generator $a$
• The degree of this polynomial is bounded by the degree of the defining polynomial
• The name of the variable does not have to be specified, but some choices (e.g. "x") are forbidden
• Arithmetics and comparison are available via the standard operators
• Supports positive and negative infinity

Examples

• These are some constructors for NumberFieldElements living in the NumberField $nf defined in the previous section:

$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

• Using some operations we show some known facts about the golden ratio:

print 1+(1/$a**2)+(1/$a**3);print "\n";
print ((1-$nfe_pol)*$a);print "\n";
print join("<->", -1/$a==$nfe_pol, 2<=$nfe_pol, $a > $nfe_pol, $a + $nfe_inf);

(a ~ 1.6180340)
(a+1 ~ 2.6180340)
1<-><->1<->inf

Example Applications

n-cube with diagonal of length 1

• Consider a euclidean n-cube with side length $x$ and assume its diagonal to have length $1$; we construct this as a Polytope object
• Using euclidean length calculation we have the formula $1^2 = \sum_{i=1}^{n}x^2$, or simplified: $n \cdot x^2 - 1 = 0$

$n = 2; $x = monomials<Rational,Int>(1);
$p = $n*$x*$x-1;
$nf = new NumberField($p, .5, .5);
$a = new NumberFieldElement($nf, "a");
$c = cube<NumberFieldElement>($n, $a/2);
print rows_numbered($c->VERTICES);
print_constraints($c->FACETS); print $c->VOLUME;

0:1 (-1/2*a ~ -0.35355339) (-1/2*a ~ -0.35355339)
1:1 (1/2*a ~ 0.35355339) (-1/2*a ~ -0.35355339)
2:1 (-1/2*a ~ -0.35355339) (1/2*a ~ 0.35355339)
3:1 (1/2*a ~ 0.35355339) (1/2*a ~ 0.35355339)
0: x1 >= (-1/2*a ~ -0.35355339)
1: -x1 >= (-1/2*a ~ -0.35355339)
2: x2 >= (-1/2*a ~ -0.35355339)
3: -x2 >= (-1/2*a ~ -0.35355339)

(1/2 ~ 0.50000000)

Linear Program

• $a$ is the generator of the numberfield with defining polynomial $x^{10} - 3$
  • maximize $x_1 + a \cdot x_2 + a^2 \cdot x_3$
  • subject to $$ \begin{align*} \left(\frac{1}{3}a^3\right) \cdot x_1 &\geq -1\\ \left(-3a^2\right) \cdot x_2 &\geq -1\\ a \cdot x_3 &\geq -1\\ \left(- 3a^3\right) \cdot x_1 + a \cdot x_2 + -3a^2 \cdot x_3 &\geq 0 \end{align*} $$

$p = new UniPolynomial<Rational,Int>("x^10 - 3");
$nf = new NumberField($p, 1.11, .01, 1024);
$a = new NumberFieldElement($nf, "a"); $nfe = new NumberFieldElement($nf, "- 3*a^2");
$cons = new Matrix<NumberFieldElement>([[1, 1/3 * $a**3, 0, 0], [1, 0, $nfe, 0], [1, 0, 0, $a], [0, $a * $nfe, $a, $nfe]]);
print_constraints($cons);

0: (1/3*a^3 ~ 0.46346306) x1 >= -1
1: -(3*a^2 ~ 3.7371928) x2 >= -1
2: (a ~ 1.1161232) x3 >= -1
3: -(3*a^3 ~ 4.1711675) x1 + (a ~ 1.1161232) x2 - (3*a^2 ~ 3.7371928) x3 >= 0

• Construct a Polytope from the inequalities
• Equip its linear program with the objective function
• Ask for maximal value and manually confirm its maximality

$ptope = new Polytope<NumberFieldElement>(INEQUALITIES=>$cons);
$obj = new Vector<NumberFieldElement>([0,1, $a, $a**2]);
$ptope->LP(LINEAR_OBJECTIVE=>$obj);
$res = $ptope->LP->MAXIMAL_VALUE;
print $res; print "\n\n";
for (my $i = 0; $i < $ptope->VERTICES->rows(); $i++) {
    print $ptope->VERTICES->row($i) * $obj <= $res; print ": "; print $ptope->VERTICES->row($i) * $obj; print "\n";
}

(4/27*a^9 - 1*a^7 + 3 ~ 1.2405345)

true: (-a^7 - 4*a - 9 ~ -15.622162)
true: (1/9*a^9 + 1/3*a^8 + 1/27*a^6 - 1*a ~ 0.056870543)
true: (4/27*a^9 - 1*a^7 + 3 ~ 1.2405345)
true: (1/9*a^9 - 1*a^7 - 1*a ~ -2.9751396)

Click here for additional output

polymake: used package tosimplex
  Dual simplex algorithm implemented by Thomas Opfer

Convex Hull

• Given these six points in $2$-space: $\left(0,0\right), \left(a,0\right), \left(\frac{a}{2},\frac{5}{3}a\right), \left(\frac{a}{3},2a\right), \left(0,2a\right), \left(\frac{a}{2},\frac{a}{2}\right)$, where $a$ is generator of an arbitrary number field (here from previous example)
• Compute the convex hull of the points, i.e. the H-description

$p = new Polytope<NumberFieldElement>(POINTS=>[[1,0,0],[1,$a,0],[1,$a/2,5/3*$a],[1,$a/3,2*$a],[1,0,2*$a],[1,$a/2,$a/2]]);
print_constraints($p->FACETS);

0: x1 >= 0
1: -(10/3 ~ 3.3333333) x1 - x2 >= (-10/3*a ~ -3.7204106)
2: x2 >= 0
3: -2 x1 - x2 >= (-8/3*a ~ -2.9763285)
4: -x2 >= (-2*a ~ -2.2322463)