`IntegerRelations`

Integer relations

This class provides methods to compute a basis of the exponent lattice

\[\{(e_1,\dots,e_n) \in \mathbb{Z}^n \colon x_1^{e_1} \dots x_n^{e_n}=1\}\]

of a tuple of algebraic numbers \(x=(x_1,\dots,x_n)\). If the algebraic numbers \(x\) are rational integers, a method based on factorizing these rational numbers is used. For general algebraic numbers two methods, both based on LLL and a bound on the basis, are implemented.

EXAMPLES:

sage: from rec_sequences.IntegerRelations import *

sage: IntegerRelations.integer_relations([2,-1])
[0 2]

sage: IntegerRelations.integer_relations([3])
[]

sage: numbers = [2^(1/2), (-2)^(1/3), I, -I]
sage: relations = IntegerRelations.integer_relations(numbers)
sage: relations.nrows()
3
sage: all([prod(xi**ei for xi, ei in zip(numbers, relation))==1 
....:                    for relation in relations])  
True

class rec_sequences.IntegerRelations.IntegerRelations

Bases: object

static additive_relations_ge(x, M)

Computes all possible additive integer relations up to a given size.

INPUT:

x – a list of vectors or lists of numbers
M – a number; an upper bound for that is guaranteed to contain a basis for the lattice

OUTPUT:

Let \(x=(v_1,\dots,v_s)\),

\[L=\{\sum_{i=1}^s \alpha_i v_i | \alpha_i \in \mathbb{Z}\}\]

and

\[\Lambda_0=\{(e_1,\dots,e_s) \in \mathbb{Z}^s | \sum_{i=1}^s e_i v_i=0\}.\]

If the lattice \(\Lambda_0\) has a basis with elements bounded by M, a basis for the lattice is found and returned (as the rows of an integer matrix).

static integer_relations(x, algorithm='kauers', integral=False)

Computes all possible integer relations of the given algebraic numbers. If the input is rational, then a method based on factorizing the input is used. Otherwise one of two algorithms can be used:

Kauers: An iterative algorithm based on LLL.
Ge: Ge’s original algorithm together with a result by Masser as explained in detail in [F14].

INPUT:

x – a list of algebraic numbers
algorithm (default: "kauers") – the algorithm used to compute the algebraic relations. Possible options are "kauers" and "ge".
integral (default: False) – if True it will be assumed that all elements of x are algebraic integers

OUTPUT:

Let \(x=(x_1,\dots,x_n)\). Returns a basis for the lattice of relations

\[\{(e_1,\dots,e_n) \in \mathbb{Z}^n \colon x_1^{e_1} \dots x_n^{e_n}=1\}\]

The basis is returned as the rows of a matrix over Z.

EXAMPLES:

sage: from rec_sequences.IntegerRelations import *

sage: IntegerRelations.integer_relations([-1])
[2]
sage: IntegerRelations.integer_relations([I,0,-I])
[ 1  0  1]
[-2  0  2]
sage: IntegerRelations.integer_relations([1,-1,2])
[1 0 0]
[0 2 0]

static integer_relations_ge(x)

Computes all possible integer relations of the given algebraic integers. This is based on Ge’s algorithm as outlined in the PhD thesis of Paolo Faccin [F14].

Warning

This method might return wrong relations, so the output should be checked carefully. For instance, the input [I, -I, 3, 4] yields, among others, the relation [0, 0, 31867, -25254] which is clearly wrong.

INPUT:

x – a list of non-zero algebraic integers, not all integral

OUTPUT:

Let \(x=(x_1,\dots,x_n)\). Returns a basis for the lattice of relations

\[\{(e_1,\dots,e_n) \in \mathbb{Z}^n \colon x_1^{e_1} \dots x_n^{e_n}=1\}\]

The basis is returned as the rows of a matrix over Z.

EXAMPLES:

sage: from rec_sequences.IntegerRelations import *

sage: ge_algorithm = IntegerRelations.integer_relations_ge
sage: ge_algorithm([QQbar(I),QQbar(-I),QQbar(1)])
[ 0  0  1]
[ 1  1  0]
[-2  2  0]

static integer_relations_integers(x)

Computes all possible integer relations of the given integer numbers.

INPUT:

x – a list of integers

OUTPUT:

Let \(x=(x_1,\dots,x_n)\). Returns a basis for the lattice of relations

\[\{(e_1,\dots,e_n) \in \mathbb{Z}^n \colon x_1^{e_1}\dots x_n^{e_n}=1\}\]

The basis is returned as the rows of a matrix over Z.

EXAMPLES:

sage: from rec_sequences.IntegerRelations import *

sage: IntegerRelations.integer_relations_integers([-1])
[2]
sage: IntegerRelations.integer_relations_integers([-3,3,2,1])
[ 2 -2  0  0]
[ 0  0  0  1]
sage: IntegerRelations.integer_relations_integers([1,-1,2])
[1 0 0]
[0 2 0]

static integer_relations_kauers(a, precision=100)

Computes all possible integer relations of the given algebraic integers. This is based on Ge’s algorithm as outlined in the PhD thesis of Manuel Kauers.

INPUT:

a – a list of non-zero algebraic integers, not all integral
precision (default: 100) – to check if certain vectors really give rise to integer relations, numerical checks with this precision are made before doing the symbolic check.

OUTPUT:

Let \(a=(a_1,\dots,a_n)\). Returns a basis for the lattice of relations

\[\{(e_1,\dots,e_n) \in \mathbb{Z}^n \colon a_1^{e_1}\dots a_n^{e_n}=1\}\]

The basis is returned as the rows of a matrix over Z.

EXAMPLES:

sage: from rec_sequences.IntegerRelations import *

log = <Logger IR (WARNING)>