Solver for the $S$-unit equation $x+y=1$

Inspired by works of Tzanakis–de Weger, Baker–Wustholz and Smart, we use the LLL methods to implement an algorithm that returns all $S$-unit solutions to the equation $x+y=1$.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^2 + x + 1)
sage: S = K.primes_above(3)
sage: expected = [((4, 1), (4, 0), xi + 2, -xi - 1),
....:             ((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....:             ((1, 0), (5, 0), xi + 1, -xi),
....:             ((2, 0), (3, 1), xi, -xi + 1)]
sage: sols = solve_S_unit_equation(K, S, 200)
sage: eq_up_to_order(sols, expected)
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> S = K.primes_above(Integer(3))
>>> expected = [((Integer(4), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)),
...             ((Integer(3), -Integer(1)), (Integer(2), -Integer(1)), Integer(1)/Integer(3)*xi + Integer(2)/Integer(3), -Integer(1)/Integer(3)*xi + Integer(1)/Integer(3)),
...             ((Integer(1), Integer(0)), (Integer(5), Integer(0)), xi + Integer(1), -xi),
...             ((Integer(2), Integer(0)), (Integer(3), Integer(1)), xi, -xi + Integer(1))]
>>> sols = solve_S_unit_equation(K, S, Integer(200))
>>> eq_up_to_order(sols, expected)
True

Sage Live

from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^2 + x + 1)
S = K.primes_above(3)
expected = [((4, 1), (4, 0), xi + 2, -xi - 1),
            ((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
            ((1, 0), (5, 0), xi + 1, -xi),
            ((2, 0), (3, 1), xi, -xi + 1)]
sols = solve_S_unit_equation(K, S, 200)
eq_up_to_order(sols, expected)

Todo

• Use Cython to improve timings on the sieve

REFERENCES:

• [MR2016]

• [Sma1995]

• [Sma1998]

• [Yu2007]

• [AKMRVW]

AUTHORS:

• Alejandra Alvarado, Angelos Koutsianas, Beth Malmskog, Christopher Rasmussen, David Roe, Christelle Vincent, Mckenzie West (2018-04-25 to 2018-11-09): original version

sage.rings.number_field.S_unit_solver.K0_func(SUK, A, prec=106)

Return the constant $K_0$ from [AKMRVW].

INPUT:

• SUK – a group of $S$-units

• A – the set of the products of the coefficients of the $S$-unit equation with each root of unity of $K$

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $K_0$, a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import K0_func
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 11)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
sage: v = K.primes_above(3)[0]
sage: K0_func(SUK, K.roots_of_unity())
8.84763586062272e12

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import K0_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(11), names=('a',)); (a,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(6))))
>>> v = K.primes_above(Integer(3))[Integer(0)]
>>> K0_func(SUK, K.roots_of_unity())
8.84763586062272e12

Sage Live

from sage.rings.number_field.S_unit_solver import K0_func
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 11)
SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
v = K.primes_above(3)[0]
K0_func(SUK, K.roots_of_unity())

REFERENCES:

• [Sma1995] p. 824

• [AKMRVW] arXiv 1903.00977

sage.rings.number_field.S_unit_solver.K1_func(SUK, v, A, prec=106)

Return the constant $K_1$ from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of $S$-units

• v – an infinite place of $K$ (element of SUK.number_field().places(prec))

• A – list of all products of each potential $a$, $b$ in the $S$-unit equation $ax+by+1=0$ with each root of unity of $K$

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $K_1$, a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import K1_func
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: phi_real = K.places()[0]
sage: phi_complex = K.places()[1]
sage: A = K.roots_of_unity()

sage: K1_func(SUK, phi_real, A)
4.483038368145048508970350163578e16

sage: K1_func(SUK, phi_complex, A)
2.073346189067285101984136298965e17

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import K1_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> phi_real = K.places()[Integer(0)]
>>> phi_complex = K.places()[Integer(1)]
>>> A = K.roots_of_unity()

>>> K1_func(SUK, phi_real, A)
4.483038368145048508970350163578e16

>>> K1_func(SUK, phi_complex, A)
2.073346189067285101984136298965e17

Sage Live

from sage.rings.number_field.S_unit_solver import K1_func
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
phi_real = K.places()[0]
phi_complex = K.places()[1]
A = K.roots_of_unity()
K1_func(SUK, phi_real, A)
K1_func(SUK, phi_complex, A)

REFERENCES:

• [Sma1995] p. 825

sage.rings.number_field.S_unit_solver.Omega_prime(dK, v, mu_list, prec=106)

Return the constant ${\mathrm{\Omega }}^{\prime }$ appearing in [AKMRVW].

INPUT:

• dK – the degree of a number field $K$

• v – a finite place of $K$

• mu_list – list of nonzero elements of $K$. It is assumed that the sublist mu_list[1:] is multiplicatively independent

• prec – the precision of the real field

OUTPUT: the constant ${\mathrm{\Omega }}^{\prime }$

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import mus, Omega_prime
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
sage: v = K.primes_above(3)[0]
sage: mu_list = [-1] + mus(SUK, v)
sage: dK = K.degree()
sage: Omega_prime(dK, v, mu_list)
0.000487349679922696

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import mus, Omega_prime
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(6))))
>>> v = K.primes_above(Integer(3))[Integer(0)]
>>> mu_list = [-Integer(1)] + mus(SUK, v)
>>> dK = K.degree()
>>> Omega_prime(dK, v, mu_list)
0.000487349679922696

Sage Live

from sage.rings.number_field.S_unit_solver import mus, Omega_prime
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
v = K.primes_above(3)[0]
mu_list = [-1] + mus(SUK, v)
dK = K.degree()
Omega_prime(dK, v, mu_list)

REFERENCES:

• [AKMRVW] arXiv 1903.00977

sage.rings.number_field.S_unit_solver.Yu_C1_star(n, v, prec=106)

Return the constant $C_1^{\ast }$ appearing in [Yu2007] (1.23).

INPUT:

• n – the number of generators of a multiplicative subgroup of a field $K$

• v – a finite place of $K$ (a fractional ideal)

• prec – the precision of the real field

OUTPUT: the constant $C_1^{\ast }$ as a real number

EXAMPLES:

Sage

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 5)
sage: v11 = K.primes_above(11)[0]
sage: from sage.rings.number_field.S_unit_solver import Yu_C1_star
sage: Yu_C1_star(1,v11)
2.154667761574516556114215527020e6

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> v11 = K.primes_above(Integer(11))[Integer(0)]
>>> from sage.rings.number_field.S_unit_solver import Yu_C1_star
>>> Yu_C1_star(Integer(1),v11)
2.154667761574516556114215527020e6

Sage Live

x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 5)
v11 = K.primes_above(11)[0]
from sage.rings.number_field.S_unit_solver import Yu_C1_star
Yu_C1_star(1,v11)

REFERENCES:

• [Yu2007] p.189,193

sage.rings.number_field.S_unit_solver.Yu_a1_kappa1_c1(p, dK, ep)

Compute the constants a(1), kappa1, and c(1) of [Yu2007].

INPUT:

• p – a rational prime number

• dK – the absolute degree of some number field $K$

• ep – the absolute ramification index of some prime frak_p of $K$ lying above $p$

OUTPUT:

The constants a(1), kappa1, and c(1).

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import Yu_a1_kappa1_c1
sage: Yu_a1_kappa1_c1(5, 10, 3)
(16, 20, 319)

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import Yu_a1_kappa1_c1
>>> Yu_a1_kappa1_c1(Integer(5), Integer(10), Integer(3))
(16, 20, 319)

Sage Live

from sage.rings.number_field.S_unit_solver import Yu_a1_kappa1_c1
Yu_a1_kappa1_c1(5, 10, 3)

REFERENCES:

• [Yu2007]

sage.rings.number_field.S_unit_solver.Yu_bound(SUK, v, prec=106)

Return $c_8$ such that $c_8\ge exp(2)/\log (2)$ and $or{d}_p(\mathrm{\Theta }-1)<c_8\log B$, where $\mathrm{\Theta }=\prod _{j=1}^n{\alpha }_j^{b_j}$ and $B\ge \underset{j}{max}|b_j|$ and $B\ge 3$.

INPUT:

• SUK – a group of $S$-units

• v – a finite place of $K$ (a fractional ideal)

• prec – the precision of the real field

OUTPUT: the constant $c_8$ as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import Yu_bound
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 11)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
sage: v = K.primes_above(3)[0]
sage: Yu_bound(SUK, v)
9.03984381033128e9

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import Yu_bound
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(11), names=('a',)); (a,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(6))))
>>> v = K.primes_above(Integer(3))[Integer(0)]
>>> Yu_bound(SUK, v)
9.03984381033128e9

Sage Live

from sage.rings.number_field.S_unit_solver import Yu_bound
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 11)
SUK = UnitGroup(K, S=tuple(K.primes_above(6)))
v = K.primes_above(3)[0]
Yu_bound(SUK, v)

REFERENCES:

• [Sma1995] p. 825

• [Yu2007] p. 189–193 esp. Theorem 1

• [AKMRVW] arXiv 1903.00977

sage.rings.number_field.S_unit_solver.Yu_condition_115(K, v)

Return True or False, as the number field K and the finite place v satisfy condition (1.15) of [Yu2007].

INPUT:

• K – a number field

• v – a finite place of K

OUTPUT:

True if (1.15) is satisfied, otherwise False.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import Yu_condition_115
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 5)
sage: v2 = K.primes_above(2)[0]
sage: v11 = K.primes_above(11)[0]
sage: Yu_condition_115(K, v2)
False
sage: Yu_condition_115(K, v11)
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import Yu_condition_115
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> v2 = K.primes_above(Integer(2))[Integer(0)]
>>> v11 = K.primes_above(Integer(11))[Integer(0)]
>>> Yu_condition_115(K, v2)
False
>>> Yu_condition_115(K, v11)
True

Sage Live

from sage.rings.number_field.S_unit_solver import Yu_condition_115
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 5)
v2 = K.primes_above(2)[0]
v11 = K.primes_above(11)[0]
Yu_condition_115(K, v2)
Yu_condition_115(K, v11)

REFERENCES:

• [Yu2007] p. 188

sage.rings.number_field.S_unit_solver.Yu_modified_height(mu, n, v, prec=106)

Return the value of h(n)(mu) as appearing in [Yu2007] equation (1.21).

INPUT:

• mu – an element of a field K

• n – number of mu_j to be considered in Yu’s Theorem

• v – a place of K

• prec – the precision of the real field

OUTPUT:

The value $h_p(mu)$.

EXAMPLES:

Sage

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 5)
sage: v11 = K.primes_above(11)[0]
sage: from sage.rings.number_field.S_unit_solver import Yu_modified_height
sage: Yu_modified_height(a, 3, v11)
0.8047189562170501873003796666131

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> v11 = K.primes_above(Integer(11))[Integer(0)]
>>> from sage.rings.number_field.S_unit_solver import Yu_modified_height
>>> Yu_modified_height(a, Integer(3), v11)
0.8047189562170501873003796666131

Sage Live

x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 5)
v11 = K.primes_above(11)[0]
from sage.rings.number_field.S_unit_solver import Yu_modified_height
Yu_modified_height(a, 3, v11)

If mu is a root of unity, the output is not zero. ::

sage: Yu_modified_height(-1, 3, v11) 0.03425564675426243634374205111379

REFERENCES:

• [Yu2007] p. 192

sage.rings.number_field.S_unit_solver.beta_k(betas_and_ns)

Return a pair $[{\beta }_k,|bet{a}_k{|}_v]$, where ${\beta }_k$ has the smallest nonzero valuation in absolute value of the list betas_and_ns.

INPUT:

• betas_and_ns – list of pairs [beta,val_v(beta)] outputted from the function where beta is an element of SUK.fundamental_units()

OUTPUT:

The pair [beta_k,v(beta_k)], where beta_k is an element of K and val_v(beta_k) is a integer.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import beta_k
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: v_fin = tuple(K.primes_above(3))[0]

sage: betas = [[beta, beta.valuation(v_fin)] for beta in SUK.fundamental_units()]
sage: beta_k(betas)
[xi, 1]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import beta_k
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> v_fin = tuple(K.primes_above(Integer(3)))[Integer(0)]

>>> betas = [[beta, beta.valuation(v_fin)] for beta in SUK.fundamental_units()]
>>> beta_k(betas)
[xi, 1]

Sage Live

from sage.rings.number_field.S_unit_solver import beta_k
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
v_fin = tuple(K.primes_above(3))[0]
betas = [[beta, beta.valuation(v_fin)] for beta in SUK.fundamental_units()]
beta_k(betas)

REFERENCES:

• [Sma1995] pp. 824-825

sage.rings.number_field.S_unit_solver.c11_func(SUK, v, A, prec=106)

Return the constant $c_{11}$ from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of $S$-units

• v – a place of $K$, finite (a fractional ideal) or infinite (element of SUK.number_field().places(prec))

• A – the set of the product of the coefficients of the $S$-unit equation with each root of unity of $K$

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $c_{11}$, a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import c11_func
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: phi_real = K.places()[0]
sage: phi_complex = K.places()[1]
sage: A = K.roots_of_unity()

sage: c11_func(SUK, phi_real, A)  # abs tol 1e-29
3.255848343572896153455615423662

sage: c11_func(SUK, phi_complex, A)  # abs tol 1e-29
6.511696687145792306911230847323

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import c11_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> phi_real = K.places()[Integer(0)]
>>> phi_complex = K.places()[Integer(1)]
>>> A = K.roots_of_unity()

>>> c11_func(SUK, phi_real, A)  # abs tol 1e-29
3.255848343572896153455615423662

>>> c11_func(SUK, phi_complex, A)  # abs tol 1e-29
6.511696687145792306911230847323

Sage Live

from sage.rings.number_field.S_unit_solver import c11_func
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
phi_real = K.places()[0]
phi_complex = K.places()[1]
A = K.roots_of_unity()
c11_func(SUK, phi_real, A)  # abs tol 1e-29
c11_func(SUK, phi_complex, A)  # abs tol 1e-29

REFERENCES:

• [Sma1995] p. 825

sage.rings.number_field.S_unit_solver.c13_func(SUK, v, prec=106)

Return the constant $c_{13}$ from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of $S$-units

• v – an infinite place of K (element of SUK.number_field().places(prec))

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $c_{13}$, as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import c13_func
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: phi_real = K.places()[0]
sage: phi_complex = K.places()[1]

sage: c13_func(SUK, phi_real)  # abs tol 1e-29
0.4257859134798034746197327286726

sage: c13_func(SUK, phi_complex)  # abs tol 1e-29
0.2128929567399017373098663643363

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import c13_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> phi_real = K.places()[Integer(0)]
>>> phi_complex = K.places()[Integer(1)]

>>> c13_func(SUK, phi_real)  # abs tol 1e-29
0.4257859134798034746197327286726

>>> c13_func(SUK, phi_complex)  # abs tol 1e-29
0.2128929567399017373098663643363

Sage Live

from sage.rings.number_field.S_unit_solver import c13_func
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
phi_real = K.places()[0]
phi_complex = K.places()[1]
c13_func(SUK, phi_real)  # abs tol 1e-29
c13_func(SUK, phi_complex)  # abs tol 1e-29

It is an error to input a finite place.

Sage

sage: phi_finite = K.primes_above(3)[0]
sage: c13_func(SUK, phi_finite)
Traceback (most recent call last):
...
TypeError: Place must be infinite

Python

>>> from sage.all import *
>>> phi_finite = K.primes_above(Integer(3))[Integer(0)]
>>> c13_func(SUK, phi_finite)
Traceback (most recent call last):
...
TypeError: Place must be infinite

Sage Live

phi_finite = K.primes_above(3)[0]
c13_func(SUK, phi_finite)

REFERENCES:

• [Sma1995] p. 825

sage.rings.number_field.S_unit_solver.c3_func(SUK, prec=106)

Return the constant $c_3$ from [AKMRVW].

INPUT:

• SUK – a group of $S$-units

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $c_3$, as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import c3_func
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))

sage: c3_func(SUK)  # abs tol 1e-29
0.4257859134798034746197327286726

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import c3_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))

>>> c3_func(SUK)  # abs tol 1e-29
0.4257859134798034746197327286726

Sage Live

from sage.rings.number_field.S_unit_solver import c3_func
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
c3_func(SUK)  # abs tol 1e-29

Note

The numerator should be as close to 1 as possible, especially as the rank of the $S$-units grows large

REFERENCES:

• [AKMRVW] arXiv 1903.00977

sage.rings.number_field.S_unit_solver.c4_func(SUK, v, A, prec=106)

Return the constant $c_4$ from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of $S$-units

• v – a place of K, finite (a fractional ideal) or infinite (element of SUK.number_field().places(prec))

• A – the set of the product of the coefficients of the S-unit equation with each root of unity of K

• prec – the precision of the real field (default: 106)

OUTPUT: the constant $c_4$, as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import c4_func
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: phi_real = K.places()[0]
sage: phi_complex = K.places()[1]
sage: v_fin = tuple(K.primes_above(3))[0]
sage: A = K.roots_of_unity()

sage: c4_func(SUK, phi_real, A)
1.000000000000000000000000000000

sage: c4_func(SUK, phi_complex, A)
1.000000000000000000000000000000

sage: c4_func(SUK, v_fin, A)
1.000000000000000000000000000000

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import c4_func
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> phi_real = K.places()[Integer(0)]
>>> phi_complex = K.places()[Integer(1)]
>>> v_fin = tuple(K.primes_above(Integer(3)))[Integer(0)]
>>> A = K.roots_of_unity()

>>> c4_func(SUK, phi_real, A)
1.000000000000000000000000000000

>>> c4_func(SUK, phi_complex, A)
1.000000000000000000000000000000

>>> c4_func(SUK, v_fin, A)
1.000000000000000000000000000000

Sage Live

from sage.rings.number_field.S_unit_solver import c4_func
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
phi_real = K.places()[0]
phi_complex = K.places()[1]
v_fin = tuple(K.primes_above(3))[0]
A = K.roots_of_unity()
c4_func(SUK, phi_real, A)
c4_func(SUK, phi_complex, A)
c4_func(SUK, v_fin, A)

REFERENCES:

• [Sma1995] p. 824

sage.rings.number_field.S_unit_solver.clean_rfv_dict(rfv_dictionary)

Given a residue field vector dictionary, remove some impossible keys and entries.

INPUT:

• rfv_dictionary – dictionary whose keys are exponent vectors and whose values are residue field vectors

OUTPUT: none, but it removes some keys from the input dictionary

Note

• The keys of a residue field vector dictionary are exponent vectors modulo $q-1$ for some prime $q$.

• The values are residue field vectors. It is known that a residue field vector which comes from a solution to the $S$-unit equation cannot have 1 in any entry.

EXAMPLES:

In this example, we use a truncated list generated when solving the $S$-unit equation in the case that $K$ is defined by the polynomial $x^2+x+1$ and $S$ consists of the primes above 3:

Sage

sage: from sage.rings.number_field.S_unit_solver import clean_rfv_dict
sage: rfv_dict = {(1, 3): [3, 2], (3, 0): [6, 6], (5, 4): [3, 6], (2, 1): [4, 6],
....:             (5, 1): [3, 1], (2, 5): [1, 5], (0, 3): [1, 6]}
sage: len(rfv_dict)
7
sage: clean_rfv_dict(rfv_dict)
sage: len(rfv_dict)
4
sage: rfv_dict
{(1, 3): [3, 2], (2, 1): [4, 6], (3, 0): [6, 6], (5, 4): [3, 6]}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import clean_rfv_dict
>>> rfv_dict = {(Integer(1), Integer(3)): [Integer(3), Integer(2)], (Integer(3), Integer(0)): [Integer(6), Integer(6)], (Integer(5), Integer(4)): [Integer(3), Integer(6)], (Integer(2), Integer(1)): [Integer(4), Integer(6)],
...             (Integer(5), Integer(1)): [Integer(3), Integer(1)], (Integer(2), Integer(5)): [Integer(1), Integer(5)], (Integer(0), Integer(3)): [Integer(1), Integer(6)]}
>>> len(rfv_dict)
7
>>> clean_rfv_dict(rfv_dict)
>>> len(rfv_dict)
4
>>> rfv_dict
{(1, 3): [3, 2], (2, 1): [4, 6], (3, 0): [6, 6], (5, 4): [3, 6]}

Sage Live

from sage.rings.number_field.S_unit_solver import clean_rfv_dict
rfv_dict = {(1, 3): [3, 2], (3, 0): [6, 6], (5, 4): [3, 6], (2, 1): [4, 6],
            (5, 1): [3, 1], (2, 5): [1, 5], (0, 3): [1, 6]}
len(rfv_dict)
clean_rfv_dict(rfv_dict)
len(rfv_dict)
rfv_dict

sage.rings.number_field.S_unit_solver.clean_sfs(sfs_list)

Given a list of $S$-unit equation solutions, remove trivial redundancies.

INPUT:

• sfs_list – list of solutions to the $S$-unit equation

OUTPUT: list of solutions to the $S$-unit equation

Note

The function looks for cases where $x+y=1$ and $y+x=1$ appear as separate solutions, and removes one.

EXAMPLES:

The function is not dependent on the number field and removes redundancies in any list.

Sage

sage: from sage.rings.number_field.S_unit_solver import clean_sfs
sage: sols = [((1, 0, 0), (0, 0, 1), -1, 2), ((0, 0, 1), (1, 0, 0), 2, -1)]
sage: clean_sfs( sols )
[((1, 0, 0), (0, 0, 1), -1, 2)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import clean_sfs
>>> sols = [((Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(0), Integer(1)), -Integer(1), Integer(2)), ((Integer(0), Integer(0), Integer(1)), (Integer(1), Integer(0), Integer(0)), Integer(2), -Integer(1))]
>>> clean_sfs( sols )
[((1, 0, 0), (0, 0, 1), -1, 2)]

Sage Live

from sage.rings.number_field.S_unit_solver import clean_sfs
sols = [((1, 0, 0), (0, 0, 1), -1, 2), ((0, 0, 1), (1, 0, 0), 2, -1)]
clean_sfs( sols )

sage.rings.number_field.S_unit_solver.column_Log(SUK, iota, U, prec=106)

Return the log vector of iota; i.e., the logs of all the valuations.

INPUT:

• SUK – a group of $S$-units

• iota – an element of K

• U – list of places (finite or infinite) of K

• prec – the precision of the real field (default: 106)

OUTPUT: the log vector as a list of real numbers

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import column_Log
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: S = tuple(K.primes_above(3))
sage: SUK = UnitGroup(K, S=S)
sage: phi_complex = K.places()[1]
sage: v_fin = S[0]
sage: U = [phi_complex, v_fin]
sage: column_Log(SUK, xi^2, U)  # abs tol 1e-29
[1.464816384890812968648768625966, -2.197224577336219382790490473845]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import column_Log
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> S = tuple(K.primes_above(Integer(3)))
>>> SUK = UnitGroup(K, S=S)
>>> phi_complex = K.places()[Integer(1)]
>>> v_fin = S[Integer(0)]
>>> U = [phi_complex, v_fin]
>>> column_Log(SUK, xi**Integer(2), U)  # abs tol 1e-29
[1.464816384890812968648768625966, -2.197224577336219382790490473845]

Sage Live

from sage.rings.number_field.S_unit_solver import column_Log
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
S = tuple(K.primes_above(3))
SUK = UnitGroup(K, S=S)
phi_complex = K.places()[1]
v_fin = S[0]
U = [phi_complex, v_fin]
column_Log(SUK, xi^2, U)  # abs tol 1e-29

REFERENCES:

• [Sma1995] p. 823

sage.rings.number_field.S_unit_solver.compatible_system_lift(compatible_system, split_primes_list)

Given a compatible system of exponent vectors and complementary exponent vectors, return a lift to the integers.

INPUT:

• compatible_system – list of pairs [ [v0, w0], [v1, w1], .., [vk, wk] ] where [vi, wi] is a pair of complementary exponent vectors modulo qi - 1, and all pairs are compatible

• split_primes_list – list of primes [ q0, q1, .., qk ]

OUTPUT: a pair of vectors [v, w] satisfying:

1. v[0] == vi[0] for all i

2. w[0] == wi[0] for all i

3. v[j] == vi[j] modulo qi - 1 for all i and all j > 0

4. w[j] == wi[j] modulo qi - 1 for all i and all $j>0‘$

5. every entry of v and w is bounded by L/2 in absolute value, where L is the least common multiple of {qi - 1 : qi in split_primes_list }

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import compatible_system_lift
sage: split_primes_list = [3, 7]
sage: comp_sys = [[(0, 1, 0), (0, 1, 0)], [(0, 3, 4), (0, 1, 2)]]
sage: compatible_system_lift(comp_sys, split_primes_list)
[(0, 3, -2), (0, 1, 2)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import compatible_system_lift
>>> split_primes_list = [Integer(3), Integer(7)]
>>> comp_sys = [[(Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(1), Integer(0))], [(Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(1), Integer(2))]]
>>> compatible_system_lift(comp_sys, split_primes_list)
[(0, 3, -2), (0, 1, 2)]

Sage Live

from sage.rings.number_field.S_unit_solver import compatible_system_lift
split_primes_list = [3, 7]
comp_sys = [[(0, 1, 0), (0, 1, 0)], [(0, 3, 4), (0, 1, 2)]]
compatible_system_lift(comp_sys, split_primes_list)

sage.rings.number_field.S_unit_solver.compatible_systems(split_prime_list, complement_exp_vec_dict)

Given dictionaries of complement exponent vectors for various primes that split in $K$, compute all possible compatible systems.

INPUT:

• split_prime_list – list of rational primes that split completely in $K$

• complement_exp_vec_dict – dictionary of dictionaries; the keys are primes from split_prime_list

OUTPUT: list of compatible systems of exponent vectors

Note

• For any $q$ in split_prime_list, complement_exp_vec_dict[q] is a dictionary whose keys are exponent vectors modulo $q-1$ and whose values are lists of exponent vectors modulo $q-1$ which are complementary to the key.

• An item in system_list has the form [ [v0, w0], [v1, w1], ..., [vk, wk] ], where:

  - ``qj = split_prime_list[j]``
  - ``vj`` and ``wj`` are complementary exponent vectors modulo ``qj - 1``
  - the pairs are all simultaneously compatible.
  

• Let H = lcm( qj - 1 : qj in split_primes_list ). Then for any compatible system, there is at most one pair of integer exponent vectors [v, w] such that:

  - every entry of ``v`` and ``w`` is bounded in absolute value by ``H``
  - for any ``qj``, ``v`` and ``vj`` agree modulo ``(qj - 1)``
  - for any ``qj``, ``w`` and ``wj`` agree modulo ``(qj - 1)``
  

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import compatible_systems
sage: split_primes_list = [3, 7]
sage: checking_dict = {3: {(0, 1, 0): [(1, 0, 0)]}, 7: {(0, 1, 0): [(1, 0, 0)]}}
sage: compatible_systems(split_primes_list, checking_dict)
[[[(0, 1, 0), (1, 0, 0)], [(0, 1, 0), (1, 0, 0)]]]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import compatible_systems
>>> split_primes_list = [Integer(3), Integer(7)]
>>> checking_dict = {Integer(3): {(Integer(0), Integer(1), Integer(0)): [(Integer(1), Integer(0), Integer(0))]}, Integer(7): {(Integer(0), Integer(1), Integer(0)): [(Integer(1), Integer(0), Integer(0))]}}
>>> compatible_systems(split_primes_list, checking_dict)
[[[(0, 1, 0), (1, 0, 0)], [(0, 1, 0), (1, 0, 0)]]]

Sage Live

from sage.rings.number_field.S_unit_solver import compatible_systems
split_primes_list = [3, 7]
checking_dict = {3: {(0, 1, 0): [(1, 0, 0)]}, 7: {(0, 1, 0): [(1, 0, 0)]}}
compatible_systems(split_primes_list, checking_dict)

sage.rings.number_field.S_unit_solver.compatible_vectors(a, m0, m1, g)

Given an exponent vector a modulo m0, return an iterator over the exponent vectors for the modulus m1, such that a lift to the lcm modulus exists.

INPUT:

• a – an exponent vector for the modulus m0

• m0 – positive integer (specifying the modulus for a)

• m1 – positive integer (specifying the alternate modulus)

• g – the gcd of m0 and m1

OUTPUT: list of exponent vectors modulo m1 which are compatible with a

Note

Exponent vectors must agree exactly in the 0th position in order to be compatible.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import compatible_vectors
sage: a = (3, 1, 8, 1)
sage: list(compatible_vectors(a, 18, 12, gcd(18,12)))
[(3, 1, 2, 1),
 (3, 1, 2, 7),
 (3, 1, 8, 1),
 (3, 1, 8, 7),
 (3, 7, 2, 1),
 (3, 7, 2, 7),
 (3, 7, 8, 1),
 (3, 7, 8, 7)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import compatible_vectors
>>> a = (Integer(3), Integer(1), Integer(8), Integer(1))
>>> list(compatible_vectors(a, Integer(18), Integer(12), gcd(Integer(18),Integer(12))))
[(3, 1, 2, 1),
 (3, 1, 2, 7),
 (3, 1, 8, 1),
 (3, 1, 8, 7),
 (3, 7, 2, 1),
 (3, 7, 2, 7),
 (3, 7, 8, 1),
 (3, 7, 8, 7)]

Sage Live

from sage.rings.number_field.S_unit_solver import compatible_vectors
a = (3, 1, 8, 1)
list(compatible_vectors(a, 18, 12, gcd(18,12)))

The order of the moduli matters.

Sage

sage: len(list(compatible_vectors(a, 18, 12, gcd(18,12))))
8
sage: len(list(compatible_vectors(a, 12, 18, gcd(18,12))))
27

Python

>>> from sage.all import *
>>> len(list(compatible_vectors(a, Integer(18), Integer(12), gcd(Integer(18),Integer(12)))))
8
>>> len(list(compatible_vectors(a, Integer(12), Integer(18), gcd(Integer(18),Integer(12)))))
27

Sage Live

len(list(compatible_vectors(a, 18, 12, gcd(18,12))))
len(list(compatible_vectors(a, 12, 18, gcd(18,12))))

sage.rings.number_field.S_unit_solver.compatible_vectors_check(a0, a1, g, l)

Given exponent vectors with respect to two moduli, determine if they are compatible.

INPUT:

• a0 – an exponent vector modulo m0

• a1 – an exponent vector modulo m1 (must have the same length as a0)

• g – the gcd of m0 and m1

• l – the length of a0 and of a1

OUTPUT: True if there is an integer exponent vector a satisfying

$$\begin{array}{r}\begin{array}{rl}a[0]& ==a0[0]==a1[0]\\ a[1:]& ==a0[1:]\mathrm{mod}{m}_0\\ a[1:]& ==a1[1:]\mathrm{mod}{m}_1\end{array}\end{array}$$

and False otherwise.

Note

• Exponent vectors must agree exactly in the first coordinate.

• If exponent vectors are different lengths, an error is raised.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import compatible_vectors_check
sage: a0 = (3, 1, 8, 11)
sage: a1 = (3, 5, 6, 13)
sage: a2 = (5, 5, 6, 13)
sage: compatible_vectors_check(a0, a1, gcd(12, 22), 4r)
True
sage: compatible_vectors_check(a0, a2, gcd(12, 22), 4r)
False

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import compatible_vectors_check
>>> a0 = (Integer(3), Integer(1), Integer(8), Integer(11))
>>> a1 = (Integer(3), Integer(5), Integer(6), Integer(13))
>>> a2 = (Integer(5), Integer(5), Integer(6), Integer(13))
>>> compatible_vectors_check(a0, a1, gcd(Integer(12), Integer(22)), 4)
True
>>> compatible_vectors_check(a0, a2, gcd(Integer(12), Integer(22)), 4)
False

Sage Live

from sage.rings.number_field.S_unit_solver import compatible_vectors_check
a0 = (3, 1, 8, 11)
a1 = (3, 5, 6, 13)
a2 = (5, 5, 6, 13)
compatible_vectors_check(a0, a1, gcd(12, 22), 4r)
compatible_vectors_check(a0, a2, gcd(12, 22), 4r)

sage.rings.number_field.S_unit_solver.construct_comp_exp_vec(rfv_to_ev_dict, q)

Construct a dictionary associating complement vectors to residue field vectors.

INPUT:

• rfv_to_ev_dict – dictionary whose keys are residue field vectors and whose values are lists of exponent vectors with the associated residue field vector

• q – the characteristic of the residue field

OUTPUT: a dictionary whose typical key is an exponent vector a, and whose associated value is a list of complementary exponent vectors to a

EXAMPLES:

In this example, we use the list generated when solving the $S$-unit equation in the case that $K$ is defined by the polynomial $x^2+x+1$ and $S$ consists of the primes above 3

Sage

sage: from sage.rings.number_field.S_unit_solver import construct_comp_exp_vec
sage: rfv_to_ev_dict = {(6, 6): [(3, 0)], (5, 6): [(1, 2)], (5, 4): [(5, 3)],
....:                   (6, 2): [(5, 5)], (2, 5): [(0, 1)], (5, 5): [(3, 4)],
....:                   (4, 4): [(0, 2)], (6, 3): [(1, 4)], (3, 6): [(5, 4)],
....:                   (2, 2): [(0, 4)], (3, 5): [(1, 0)], (6, 4): [(1, 1)],
....:                   (3, 2): [(1, 3)], (2, 6): [(4, 5)], (4, 5): [(4, 3)],
....:                   (2, 3): [(2, 3)], (4, 2): [(4, 0)], (6, 5): [(5, 2)],
....:                   (3, 3): [(3, 2)], (5, 3): [(5, 0)], (4, 6): [(2, 1)],
....:                   (3, 4): [(3, 5)], (4, 3): [(0, 5)], (5, 2): [(3, 1)],
....:                   (2, 4): [(2, 0)]}
sage: construct_comp_exp_vec(rfv_to_ev_dict, 7)
{(0, 1): [(1, 4)],
 (0, 2): [(0, 2)],
 (0, 4): [(3, 0)],
 (0, 5): [(4, 3)],
 (1, 0): [(5, 0)],
 (1, 1): [(2, 0)],
 (1, 2): [(1, 3)],
 (1, 3): [(1, 2)],
 (1, 4): [(0, 1)],
 (2, 0): [(1, 1)],
 (2, 1): [(4, 0)],
 (2, 3): [(5, 2)],
 (3, 0): [(0, 4)],
 (3, 1): [(5, 4)],
 (3, 2): [(3, 4)],
 (3, 4): [(3, 2)],
 (3, 5): [(5, 3)],
 (4, 0): [(2, 1)],
 (4, 3): [(0, 5)],
 (4, 5): [(5, 5)],
 (5, 0): [(1, 0)],
 (5, 2): [(2, 3)],
 (5, 3): [(3, 5)],
 (5, 4): [(3, 1)],
 (5, 5): [(4, 5)]}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import construct_comp_exp_vec
>>> rfv_to_ev_dict = {(Integer(6), Integer(6)): [(Integer(3), Integer(0))], (Integer(5), Integer(6)): [(Integer(1), Integer(2))], (Integer(5), Integer(4)): [(Integer(5), Integer(3))],
...                   (Integer(6), Integer(2)): [(Integer(5), Integer(5))], (Integer(2), Integer(5)): [(Integer(0), Integer(1))], (Integer(5), Integer(5)): [(Integer(3), Integer(4))],
...                   (Integer(4), Integer(4)): [(Integer(0), Integer(2))], (Integer(6), Integer(3)): [(Integer(1), Integer(4))], (Integer(3), Integer(6)): [(Integer(5), Integer(4))],
...                   (Integer(2), Integer(2)): [(Integer(0), Integer(4))], (Integer(3), Integer(5)): [(Integer(1), Integer(0))], (Integer(6), Integer(4)): [(Integer(1), Integer(1))],
...                   (Integer(3), Integer(2)): [(Integer(1), Integer(3))], (Integer(2), Integer(6)): [(Integer(4), Integer(5))], (Integer(4), Integer(5)): [(Integer(4), Integer(3))],
...                   (Integer(2), Integer(3)): [(Integer(2), Integer(3))], (Integer(4), Integer(2)): [(Integer(4), Integer(0))], (Integer(6), Integer(5)): [(Integer(5), Integer(2))],
...                   (Integer(3), Integer(3)): [(Integer(3), Integer(2))], (Integer(5), Integer(3)): [(Integer(5), Integer(0))], (Integer(4), Integer(6)): [(Integer(2), Integer(1))],
...                   (Integer(3), Integer(4)): [(Integer(3), Integer(5))], (Integer(4), Integer(3)): [(Integer(0), Integer(5))], (Integer(5), Integer(2)): [(Integer(3), Integer(1))],
...                   (Integer(2), Integer(4)): [(Integer(2), Integer(0))]}
>>> construct_comp_exp_vec(rfv_to_ev_dict, Integer(7))
{(0, 1): [(1, 4)],
 (0, 2): [(0, 2)],
 (0, 4): [(3, 0)],
 (0, 5): [(4, 3)],
 (1, 0): [(5, 0)],
 (1, 1): [(2, 0)],
 (1, 2): [(1, 3)],
 (1, 3): [(1, 2)],
 (1, 4): [(0, 1)],
 (2, 0): [(1, 1)],
 (2, 1): [(4, 0)],
 (2, 3): [(5, 2)],
 (3, 0): [(0, 4)],
 (3, 1): [(5, 4)],
 (3, 2): [(3, 4)],
 (3, 4): [(3, 2)],
 (3, 5): [(5, 3)],
 (4, 0): [(2, 1)],
 (4, 3): [(0, 5)],
 (4, 5): [(5, 5)],
 (5, 0): [(1, 0)],
 (5, 2): [(2, 3)],
 (5, 3): [(3, 5)],
 (5, 4): [(3, 1)],
 (5, 5): [(4, 5)]}

Sage Live

from sage.rings.number_field.S_unit_solver import construct_comp_exp_vec
rfv_to_ev_dict = {(6, 6): [(3, 0)], (5, 6): [(1, 2)], (5, 4): [(5, 3)],
                  (6, 2): [(5, 5)], (2, 5): [(0, 1)], (5, 5): [(3, 4)],
                  (4, 4): [(0, 2)], (6, 3): [(1, 4)], (3, 6): [(5, 4)],
                  (2, 2): [(0, 4)], (3, 5): [(1, 0)], (6, 4): [(1, 1)],
                  (3, 2): [(1, 3)], (2, 6): [(4, 5)], (4, 5): [(4, 3)],
                  (2, 3): [(2, 3)], (4, 2): [(4, 0)], (6, 5): [(5, 2)],
                  (3, 3): [(3, 2)], (5, 3): [(5, 0)], (4, 6): [(2, 1)],
                  (3, 4): [(3, 5)], (4, 3): [(0, 5)], (5, 2): [(3, 1)],
                  (2, 4): [(2, 0)]}
construct_comp_exp_vec(rfv_to_ev_dict, 7)

sage.rings.number_field.S_unit_solver.construct_complement_dictionaries(split_primes_list, SUK, verbose=False)

Construct the complement exponent vector dictionaries.

INPUT:

• split_primes_list – list of rational primes which split completely in the number field $K$

• SUK – the $S$-unit group for a number field $K$

• verbose – boolean to provide additional feedback (default: False)

OUTPUT:

A dictionary of dictionaries. The keys coincide with the primes in split_primes_list. For each $q$, comp_exp_vec[q] is a dictionary whose keys are exponent vectors modulo $q-1$, and whose values are lists of exponent vectors modulo $q-1$.

If $w$ is an exponent vector in comp_exp_vec[q][v], then the residue field vectors modulo $q$ for $v$ and $w$ sum to [1,1,...,1]

Note

• The data of comp_exp_vec will later be lifted to $\mathbf{Z}$ to look for true $S$-Unit equation solutions.

• During construction, the various dictionaries are compared to each other several times to eliminate as many mod $q$ solutions as possible.

• The authors acknowledge a helpful discussion with Norman Danner which helped formulate this code.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import construct_complement_dictionaries
sage: x = polygen(ZZ, 'x')
sage: f = x^2 + 5
sage: H = 10
sage: K.<xi> = NumberField(f)
sage: SUK = K.S_unit_group(S=K.primes_above(H))
sage: split_primes_list = [3, 7]
sage: actual = construct_complement_dictionaries(split_primes_list, SUK)
sage: expected = {3: {(0, 1, 0): [(0, 1, 0), (1, 0, 0)],
....:                 (1, 0, 0): [(0, 1, 0), (1, 0, 0)]},
....:             7: {(0, 1, 0): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
....:                 (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:                 (0, 3, 2): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
....:                 (0, 3, 4): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:                 (0, 5, 0): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:                 (0, 5, 4): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
....:                 (1, 0, 0): [(0, 1, 0), (0, 3, 2), (0, 5, 4)],
....:                 (1, 0, 2): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
....:                 (1, 0, 4): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
....:                 (1, 2, 0): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
....:                 (1, 2, 2): [(0, 1, 0), (0, 3, 2), (0, 5, 4)],
....:                 (1, 2, 4): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
....:                 (1, 4, 0): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
....:                 (1, 4, 2): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
....:                 (1, 4, 4): [(0, 1, 0), (0, 3, 2), (0, 5, 4)]}}
sage: all(set(actual[p][vec]) == set(expected[p][vec])
....:     for p in [3, 7] for vec in expected[p])
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import construct_complement_dictionaries
>>> x = polygen(ZZ, 'x')
>>> f = x**Integer(2) + Integer(5)
>>> H = Integer(10)
>>> K = NumberField(f, names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = K.S_unit_group(S=K.primes_above(H))
>>> split_primes_list = [Integer(3), Integer(7)]
>>> actual = construct_complement_dictionaries(split_primes_list, SUK)
>>> expected = {Integer(3): {(Integer(0), Integer(1), Integer(0)): [(Integer(0), Integer(1), Integer(0)), (Integer(1), Integer(0), Integer(0))],
...                 (Integer(1), Integer(0), Integer(0)): [(Integer(0), Integer(1), Integer(0)), (Integer(1), Integer(0), Integer(0))]},
...             Integer(7): {(Integer(0), Integer(1), Integer(0)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(2), Integer(2)), (Integer(1), Integer(4), Integer(4))],
...                 (Integer(0), Integer(1), Integer(2)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...                 (Integer(0), Integer(3), Integer(2)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(2), Integer(2)), (Integer(1), Integer(4), Integer(4))],
...                 (Integer(0), Integer(3), Integer(4)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...                 (Integer(0), Integer(5), Integer(0)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...                 (Integer(0), Integer(5), Integer(4)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(2), Integer(2)), (Integer(1), Integer(4), Integer(4))],
...                 (Integer(1), Integer(0), Integer(0)): [(Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(5), Integer(4))],
...                 (Integer(1), Integer(0), Integer(2)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(2), Integer(0)), (Integer(1), Integer(4), Integer(2))],
...                 (Integer(1), Integer(0), Integer(4)): [(Integer(1), Integer(0), Integer(2)), (Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0))],
...                 (Integer(1), Integer(2), Integer(0)): [(Integer(1), Integer(0), Integer(2)), (Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0))],
...                 (Integer(1), Integer(2), Integer(2)): [(Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(5), Integer(4))],
...                 (Integer(1), Integer(2), Integer(4)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(2), Integer(0)), (Integer(1), Integer(4), Integer(2))],
...                 (Integer(1), Integer(4), Integer(0)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(2), Integer(0)), (Integer(1), Integer(4), Integer(2))],
...                 (Integer(1), Integer(4), Integer(2)): [(Integer(1), Integer(0), Integer(2)), (Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0))],
...                 (Integer(1), Integer(4), Integer(4)): [(Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(5), Integer(4))]}}
>>> all(set(actual[p][vec]) == set(expected[p][vec])
...     for p in [Integer(3), Integer(7)] for vec in expected[p])
True

Sage Live

from sage.rings.number_field.S_unit_solver import construct_complement_dictionaries
x = polygen(ZZ, 'x')
f = x^2 + 5
H = 10
K.<xi> = NumberField(f)
SUK = K.S_unit_group(S=K.primes_above(H))
split_primes_list = [3, 7]
actual = construct_complement_dictionaries(split_primes_list, SUK)
expected = {3: {(0, 1, 0): [(0, 1, 0), (1, 0, 0)],
                (1, 0, 0): [(0, 1, 0), (1, 0, 0)]},
            7: {(0, 1, 0): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
                (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
                (0, 3, 2): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
                (0, 3, 4): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
                (0, 5, 0): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
                (0, 5, 4): [(1, 0, 0), (1, 2, 2), (1, 4, 4)],
                (1, 0, 0): [(0, 1, 0), (0, 3, 2), (0, 5, 4)],
                (1, 0, 2): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
                (1, 0, 4): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
                (1, 2, 0): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
                (1, 2, 2): [(0, 1, 0), (0, 3, 2), (0, 5, 4)],
                (1, 2, 4): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
                (1, 4, 0): [(1, 0, 4), (1, 2, 0), (1, 4, 2)],
                (1, 4, 2): [(1, 0, 2), (1, 2, 4), (1, 4, 0)],
                (1, 4, 4): [(0, 1, 0), (0, 3, 2), (0, 5, 4)]}}
all(set(actual[p][vec]) == set(expected[p][vec])
    for p in [3, 7] for vec in expected[p])

sage.rings.number_field.S_unit_solver.construct_rfv_to_ev(rfv_dictionary, q, d, verbose=False)

Return a reverse lookup dictionary, to find the exponent vectors associated to a given residue field vector.

INPUT:

• rfv_dictionary – dictionary whose keys are exponent vectors and whose values are the associated residue field vectors

• q – a prime (assumed to split completely in the relevant number field)

• d – the number of primes in $K$ above the rational prime $q$

• verbose – boolean (default: False); flag to indicate more detailed output is desired

OUTPUT:

A dictionary P whose keys are residue field vectors and whose values are lists of all exponent vectors which correspond to the given residue field vector.

Note

• For example, if rfv_dictionary[e0] = r0, then P[r0] is a list which contains e0.

• During construction, some residue field vectors can be eliminated as coming from solutions to the $S$-unit equation. Such vectors are dropped from the keys of the dictionary P.

EXAMPLES:

In this example, we use a truncated list generated when solving the $S$-unit equation in the case that $K$ is defined by the polynomial $x^2+x+1$ and $S$ consists of the primes above 3:

Sage

sage: from sage.rings.number_field.S_unit_solver import construct_rfv_to_ev
sage: rfv_dict = {(1, 3): [3, 2], (3, 0): [6, 6], (5, 4): [3, 6], (2, 1): [4, 6],
....:             (4, 0): [4, 2], (1, 2): [5, 6]}
sage: construct_rfv_to_ev(rfv_dict,7,2,False)
{(3, 2): [(1, 3)], (4, 2): [(4, 0)], (4, 6): [(2, 1)], (5, 6): [(1, 2)]}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import construct_rfv_to_ev
>>> rfv_dict = {(Integer(1), Integer(3)): [Integer(3), Integer(2)], (Integer(3), Integer(0)): [Integer(6), Integer(6)], (Integer(5), Integer(4)): [Integer(3), Integer(6)], (Integer(2), Integer(1)): [Integer(4), Integer(6)],
...             (Integer(4), Integer(0)): [Integer(4), Integer(2)], (Integer(1), Integer(2)): [Integer(5), Integer(6)]}
>>> construct_rfv_to_ev(rfv_dict,Integer(7),Integer(2),False)
{(3, 2): [(1, 3)], (4, 2): [(4, 0)], (4, 6): [(2, 1)], (5, 6): [(1, 2)]}

Sage Live

from sage.rings.number_field.S_unit_solver import construct_rfv_to_ev
rfv_dict = {(1, 3): [3, 2], (3, 0): [6, 6], (5, 4): [3, 6], (2, 1): [4, 6],
            (4, 0): [4, 2], (1, 2): [5, 6]}
construct_rfv_to_ev(rfv_dict,7,2,False)

sage.rings.number_field.S_unit_solver.cx_LLL_bound(SUK, A, prec=106)

Return the maximum of all of the $K_1$’s as they are LLL-optimized for each infinite place $v$.

INPUT:

• SUK – a group of $S$-units

• A – list of all products of each potential $a$, $b$ in the $S$-unit equation $ax+by+1=0$ with each root of unity of $K$

• prec – precision of real field (default: 106)

OUTPUT: a bound for the exponents at the infinite place, as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import cx_LLL_bound
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: A = K.roots_of_unity()

sage: cx_LLL_bound(SUK, A) # long time
35

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import cx_LLL_bound
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> A = K.roots_of_unity()

>>> cx_LLL_bound(SUK, A) # long time
35

Sage Live

from sage.rings.number_field.S_unit_solver import cx_LLL_bound
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
A = K.roots_of_unity()
cx_LLL_bound(SUK, A) # long time

sage.rings.number_field.S_unit_solver.defining_polynomial_for_Kp(prime, prec=106)

INPUT:

• prime – a prime ideal of a number field $K$

• prec – a positive natural number (default: 106)

OUTPUT: a polynomial with integer coefficients that is equivalent mod p^prec to a defining polynomial for the completion of $K$ associated to the specified prime

Note

$K$ has to be an absolute extension

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import defining_polynomial_for_Kp
sage: K.<a> = QuadraticField(2)
sage: p2 = K.prime_above(7); p2
Fractional ideal (2*a - 1)
sage: defining_polynomial_for_Kp(p2, 10)
x + 266983762

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import defining_polynomial_for_Kp
>>> K = QuadraticField(Integer(2), names=('a',)); (a,) = K._first_ngens(1)
>>> p2 = K.prime_above(Integer(7)); p2
Fractional ideal (2*a - 1)
>>> defining_polynomial_for_Kp(p2, Integer(10))
x + 266983762

Sage Live

from sage.rings.number_field.S_unit_solver import defining_polynomial_for_Kp
K.<a> = QuadraticField(2)
p2 = K.prime_above(7); p2
defining_polynomial_for_Kp(p2, 10)

Sage

sage: K.<a> = QuadraticField(-6)
sage: p2 = K.prime_above(2); p2
Fractional ideal (2, a)
sage: defining_polynomial_for_Kp(p2, 100)
x^2 + 6
sage: p5 = K.prime_above(5); p5
Fractional ideal (5, a + 2)
sage: defining_polynomial_for_Kp(p5, 100)
x + 3408332191958133385114942613351834100964285496304040728906961917542037

Python

>>> from sage.all import *
>>> K = QuadraticField(-Integer(6), names=('a',)); (a,) = K._first_ngens(1)
>>> p2 = K.prime_above(Integer(2)); p2
Fractional ideal (2, a)
>>> defining_polynomial_for_Kp(p2, Integer(100))
x^2 + 6
>>> p5 = K.prime_above(Integer(5)); p5
Fractional ideal (5, a + 2)
>>> defining_polynomial_for_Kp(p5, Integer(100))
x + 3408332191958133385114942613351834100964285496304040728906961917542037

Sage Live

K.<a> = QuadraticField(-6)
p2 = K.prime_above(2); p2
defining_polynomial_for_Kp(p2, 100)
p5 = K.prime_above(5); p5
defining_polynomial_for_Kp(p5, 100)

sage.rings.number_field.S_unit_solver.drop_vector(ev, p, q, complement_ev_dict)

Determine if the exponent vector, ev, may be removed from the complement dictionary during construction. This will occur if ev is not compatible with an exponent vector mod $q-1$.

INPUT:

• ev – an exponent vector modulo $p-1$

• p – the prime such that ev is an exponent vector modulo $p-1$

• q – a prime, distinct from $p$, that is a key in the complement_ev_dict

• complement_ev_dict – dictionary of dictionaries, whose keys are primes complement_ev_dict[q] is a dictionary whose keys are exponent vectors modulo $q-1$ and whose values are lists of complementary exponent vectors modulo $q-1$

OUTPUT: True if ev may be dropped from the complement exponent vector dictionary, and False if not

Note

• If ev is not compatible with any of the vectors modulo $q-1$, then it can no longer correspond to a solution of the $S$-unit equation. It returns True to indicate that it should be removed.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import drop_vector
sage: drop_vector((1, 2, 5), 7, 11, {11: {(1, 1, 3): [(1, 1, 3), (2, 3, 4)]}})
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import drop_vector
>>> drop_vector((Integer(1), Integer(2), Integer(5)), Integer(7), Integer(11), {Integer(11): {(Integer(1), Integer(1), Integer(3)): [(Integer(1), Integer(1), Integer(3)), (Integer(2), Integer(3), Integer(4))]}})
True

Sage Live

from sage.rings.number_field.S_unit_solver import drop_vector
drop_vector((1, 2, 5), 7, 11, {11: {(1, 1, 3): [(1, 1, 3), (2, 3, 4)]}})

Sage

sage: P = {3: {(1, 0, 0): [(1, 0, 0), (0, 1, 0)],
....:          (0, 1, 0): [(1, 0, 0), (0, 1, 0)]},
....:      7: {(0, 3, 4): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:          (1, 2, 4): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
....:          (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:          (0, 5, 4): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
....:          (1, 4, 2): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
....:          (1, 0, 4): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
....:          (0, 3, 2): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
....:          (1, 0, 0): [(0, 5, 4), (0, 3, 2), (0, 1, 0)],
....:          (1, 2, 0): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
....:          (0, 1, 0): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
....:          (0, 5, 0): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
....:          (1, 2, 2): [(0, 5, 4), (0, 3, 2), (0, 1, 0)],
....:          (1, 4, 0): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
....:          (1, 0, 2): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
....:          (1, 4, 4): [(0, 5, 4), (0, 3, 2), (0, 1, 0)]}}
sage: drop_vector((0, 1, 0), 3, 7, P)
False

Python

>>> from sage.all import *
>>> P = {Integer(3): {(Integer(1), Integer(0), Integer(0)): [(Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(1), Integer(0))],
...          (Integer(0), Integer(1), Integer(0)): [(Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(1), Integer(0))]},
...      Integer(7): {(Integer(0), Integer(3), Integer(4)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...          (Integer(1), Integer(2), Integer(4)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(4), Integer(2)), (Integer(1), Integer(2), Integer(0))],
...          (Integer(0), Integer(1), Integer(2)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...          (Integer(0), Integer(5), Integer(4)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(4), Integer(4)), (Integer(1), Integer(2), Integer(2))],
...          (Integer(1), Integer(4), Integer(2)): [(Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0)), (Integer(1), Integer(0), Integer(2))],
...          (Integer(1), Integer(0), Integer(4)): [(Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0)), (Integer(1), Integer(0), Integer(2))],
...          (Integer(0), Integer(3), Integer(2)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(4), Integer(4)), (Integer(1), Integer(2), Integer(2))],
...          (Integer(1), Integer(0), Integer(0)): [(Integer(0), Integer(5), Integer(4)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(1), Integer(0))],
...          (Integer(1), Integer(2), Integer(0)): [(Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0)), (Integer(1), Integer(0), Integer(2))],
...          (Integer(0), Integer(1), Integer(0)): [(Integer(1), Integer(0), Integer(0)), (Integer(1), Integer(4), Integer(4)), (Integer(1), Integer(2), Integer(2))],
...          (Integer(0), Integer(5), Integer(0)): [(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(3), Integer(4)), (Integer(0), Integer(5), Integer(0))],
...          (Integer(1), Integer(2), Integer(2)): [(Integer(0), Integer(5), Integer(4)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(1), Integer(0))],
...          (Integer(1), Integer(4), Integer(0)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(4), Integer(2)), (Integer(1), Integer(2), Integer(0))],
...          (Integer(1), Integer(0), Integer(2)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(4), Integer(2)), (Integer(1), Integer(2), Integer(0))],
...          (Integer(1), Integer(4), Integer(4)): [(Integer(0), Integer(5), Integer(4)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(1), Integer(0))]}}
>>> drop_vector((Integer(0), Integer(1), Integer(0)), Integer(3), Integer(7), P)
False

Sage Live

P = {3: {(1, 0, 0): [(1, 0, 0), (0, 1, 0)],
         (0, 1, 0): [(1, 0, 0), (0, 1, 0)]},
     7: {(0, 3, 4): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
         (1, 2, 4): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
         (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
         (0, 5, 4): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
         (1, 4, 2): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
         (1, 0, 4): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
         (0, 3, 2): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
         (1, 0, 0): [(0, 5, 4), (0, 3, 2), (0, 1, 0)],
         (1, 2, 0): [(1, 2, 4), (1, 4, 0), (1, 0, 2)],
         (0, 1, 0): [(1, 0, 0), (1, 4, 4), (1, 2, 2)],
         (0, 5, 0): [(0, 1, 2), (0, 3, 4), (0, 5, 0)],
         (1, 2, 2): [(0, 5, 4), (0, 3, 2), (0, 1, 0)],
         (1, 4, 0): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
         (1, 0, 2): [(1, 0, 4), (1, 4, 2), (1, 2, 0)],
         (1, 4, 4): [(0, 5, 4), (0, 3, 2), (0, 1, 0)]}}
drop_vector((0, 1, 0), 3, 7, P)

sage.rings.number_field.S_unit_solver.embedding_to_Kp(a, prime, prec)

INPUT:

• a – an element of a number field $K$

• prime – a prime ideal of $K$

• prec – a positive natural number

OUTPUT:

An element of $K$ that is equivalent to $a$ modulo p^(prec) and the generator of $K$ appears with exponent less than $e\cdot f$, where $p$ is the rational prime below prime and $e$, $f$ are the ramification index and residue degree, respectively.

Note

$K$ has to be an absolute number field

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import embedding_to_Kp
sage: K.<a> = QuadraticField(17)
sage: p = K.prime_above(13); p
Fractional ideal (a - 2)
sage: embedding_to_Kp(a-3, p, 15)
-20542890112375827

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import embedding_to_Kp
>>> K = QuadraticField(Integer(17), names=('a',)); (a,) = K._first_ngens(1)
>>> p = K.prime_above(Integer(13)); p
Fractional ideal (a - 2)
>>> embedding_to_Kp(a-Integer(3), p, Integer(15))
-20542890112375827

Sage Live

from sage.rings.number_field.S_unit_solver import embedding_to_Kp
K.<a> = QuadraticField(17)
p = K.prime_above(13); p
embedding_to_Kp(a-3, p, 15)

Sage

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^4 - 2)
sage: p = K.prime_above(7); p
Fractional ideal (-a^2 + a - 1)
sage: embedding_to_Kp(a^3 - 3, p, 15)
-1261985118949117459462968282807202378

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(4) - Integer(2), names=('a',)); (a,) = K._first_ngens(1)
>>> p = K.prime_above(Integer(7)); p
Fractional ideal (-a^2 + a - 1)
>>> embedding_to_Kp(a**Integer(3) - Integer(3), p, Integer(15))
-1261985118949117459462968282807202378

Sage Live

x = polygen(ZZ, 'x')
K.<a> = NumberField(x^4 - 2)
p = K.prime_above(7); p
embedding_to_Kp(a^3 - 3, p, 15)

sage.rings.number_field.S_unit_solver.eq_up_to_order(A, B)

If A and B are lists of four-tuples [a0,a1,a2,a3] and [b0,b1,b2,b3], check that there is some reordering so that either ai=bi for all i or a0==b1, a1==b0, a2==b3, a3==b2.

The entries must be hashable.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import eq_up_to_order
sage: L = [(1,2,3,4), (5,6,7,8)]
sage: L1 = [L[1], L[0]]
sage: L2 = [(2,1,4,3), (6,5,8,7)]
sage: eq_up_to_order(L, L1)
True
sage: eq_up_to_order(L, L2)
True
sage: eq_up_to_order(L, [(1,2,4,3), (5,6,8,7)])
False

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import eq_up_to_order
>>> L = [(Integer(1),Integer(2),Integer(3),Integer(4)), (Integer(5),Integer(6),Integer(7),Integer(8))]
>>> L1 = [L[Integer(1)], L[Integer(0)]]
>>> L2 = [(Integer(2),Integer(1),Integer(4),Integer(3)), (Integer(6),Integer(5),Integer(8),Integer(7))]
>>> eq_up_to_order(L, L1)
True
>>> eq_up_to_order(L, L2)
True
>>> eq_up_to_order(L, [(Integer(1),Integer(2),Integer(4),Integer(3)), (Integer(5),Integer(6),Integer(8),Integer(7))])
False

Sage Live

from sage.rings.number_field.S_unit_solver import eq_up_to_order
L = [(1,2,3,4), (5,6,7,8)]
L1 = [L[1], L[0]]
L2 = [(2,1,4,3), (6,5,8,7)]
eq_up_to_order(L, L1)
eq_up_to_order(L, L2)
eq_up_to_order(L, [(1,2,4,3), (5,6,8,7)])

sage.rings.number_field.S_unit_solver.log_p(a, prime, prec)

INPUT:

• a – an element of a number field $K$

• prime – a prime ideal of the number field $K$

• prec – positive integer

OUTPUT:

An element of $K$ which is congruent to the prime-adic logarithm of $a$ with respect to prime modulo p^prec, where $p$ is the rational prime below prime.

Note

Here we take into account the other primes in $K$ above $p$ in order to get coefficients with small values.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import log_p
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 14)
sage: p1 = K.primes_above(3)[0]
sage: p1
Fractional ideal (3, a + 1)
sage: log_p(a+2, p1, 20)
8255385638/3*a + 15567609440/3

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import log_p
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(14), names=('a',)); (a,) = K._first_ngens(1)
>>> p1 = K.primes_above(Integer(3))[Integer(0)]
>>> p1
Fractional ideal (3, a + 1)
>>> log_p(a+Integer(2), p1, Integer(20))
8255385638/3*a + 15567609440/3

Sage Live

from sage.rings.number_field.S_unit_solver import log_p
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 14)
p1 = K.primes_above(3)[0]
p1
log_p(a+2, p1, 20)

Sage

sage: K.<a> = NumberField(x^4 + 14)
sage: p1 = K.primes_above(5)[0]
sage: p1
Fractional ideal (5, a + 1)
sage: log_p(1/(a^2-4), p1, 30)
-42392683853751591352946/25*a^3 - 113099841599709611260219/25*a^2 -
8496494127064033599196/5*a - 18774052619501226990432/25

Python

>>> from sage.all import *
>>> K = NumberField(x**Integer(4) + Integer(14), names=('a',)); (a,) = K._first_ngens(1)
>>> p1 = K.primes_above(Integer(5))[Integer(0)]
>>> p1
Fractional ideal (5, a + 1)
>>> log_p(Integer(1)/(a**Integer(2)-Integer(4)), p1, Integer(30))
-42392683853751591352946/25*a^3 - 113099841599709611260219/25*a^2 -
8496494127064033599196/5*a - 18774052619501226990432/25

Sage Live

K.<a> = NumberField(x^4 + 14)
p1 = K.primes_above(5)[0]
p1
log_p(1/(a^2-4), p1, 30)

sage.rings.number_field.S_unit_solver.log_p_series_part(a, prime, prec)

INPUT:

• a – an element of a number field $K$

• prime – a prime ideal of the number field $K$

• prec – positive integer

OUTPUT:

The prime-adic logarithm of $a$ and accuracy p^prec, where $p$ is the rational prime below prime.

ALGORITHM:

The algorithm is based on the algorithm on page 30 of [Sma1998].

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import log_p_series_part
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 - 5)
sage: p1 = K.primes_above(3)[0]
sage: p1
Fractional ideal (3)
sage: log_p_series_part(a^2 - a + 1, p1, 30)
120042736778562*a + 263389019530092

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import log_p_series_part
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) - Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> p1 = K.primes_above(Integer(3))[Integer(0)]
>>> p1
Fractional ideal (3)
>>> log_p_series_part(a**Integer(2) - a + Integer(1), p1, Integer(30))
120042736778562*a + 263389019530092

Sage Live

from sage.rings.number_field.S_unit_solver import log_p_series_part
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 - 5)
p1 = K.primes_above(3)[0]
p1
log_p_series_part(a^2 - a + 1, p1, 30)

Sage

sage: K.<a> = NumberField(x^4 + 14)
sage: p1 = K.primes_above(5)[0]
sage: p1
Fractional ideal (5, a + 1)
sage: log_p_series_part(1/(a^2-4), p1, 30)
5628940883264585369224688048459896543498793204839654215019548600621221950915106576555819252366183605504671859902129729380543157757424169844382836287443485157589362653561119898762509175000557196963413830027960725069496503331353532893643983455103456070939403472988282153160667807627271637196608813155377280943180966078/1846595723557147156151786152499366687569722744011302407020455809280594038056223852568951718462474153951672335866715654153523843955513167531739386582686114545823305161128297234887329119860255600972561534713008376312342295724191173957260256352612807316114669486939448006523889489471912384033203125*a^2 + 2351432413692022254066438266577100183514828004415905040437326602004946930635942233146528817325416948515797296867947688356616798913401046136899081536181084767344346480810627200495531180794326634382675252631839139904967037478184840941275812058242995052383261849064340050686841429735092777331963400618255005895650200107/1846595723557147156151786152499366687569722744011302407020455809280594038056223852568951718462474153951672335866715654153523843955513167531739386582686114545823305161128297234887329119860255600972561534713008376312342295724191173957260256352612807316114669486939448006523889489471912384033203125

Python

>>> from sage.all import *
>>> K = NumberField(x**Integer(4) + Integer(14), names=('a',)); (a,) = K._first_ngens(1)
>>> p1 = K.primes_above(Integer(5))[Integer(0)]
>>> p1
Fractional ideal (5, a + 1)
>>> log_p_series_part(Integer(1)/(a**Integer(2)-Integer(4)), p1, Integer(30))
5628940883264585369224688048459896543498793204839654215019548600621221950915106576555819252366183605504671859902129729380543157757424169844382836287443485157589362653561119898762509175000557196963413830027960725069496503331353532893643983455103456070939403472988282153160667807627271637196608813155377280943180966078/1846595723557147156151786152499366687569722744011302407020455809280594038056223852568951718462474153951672335866715654153523843955513167531739386582686114545823305161128297234887329119860255600972561534713008376312342295724191173957260256352612807316114669486939448006523889489471912384033203125*a^2 + 2351432413692022254066438266577100183514828004415905040437326602004946930635942233146528817325416948515797296867947688356616798913401046136899081536181084767344346480810627200495531180794326634382675252631839139904967037478184840941275812058242995052383261849064340050686841429735092777331963400618255005895650200107/1846595723557147156151786152499366687569722744011302407020455809280594038056223852568951718462474153951672335866715654153523843955513167531739386582686114545823305161128297234887329119860255600972561534713008376312342295724191173957260256352612807316114669486939448006523889489471912384033203125

Sage Live

K.<a> = NumberField(x^4 + 14)
p1 = K.primes_above(5)[0]
p1
log_p_series_part(1/(a^2-4), p1, 30)

sage.rings.number_field.S_unit_solver.minimal_vector(A, y, prec=106)

INPUT:

• A – a square $n$ by $n$ non-singular integer matrix whose rows generate a lattice $\mathcal{L}$

• y – a row (1 by $n$) vector with integer coordinates

• prec – precision of real field (default: 106)

OUTPUT: a lower bound for the square of

$$\begin{array}{r}\ell (\mathcal{L},\overrightarrow{y})=\{\begin{array}{ll}{\displaystyle \underset{\overrightarrow{x}\in \mathcal{L}}{min}\Vert \overrightarrow{x}-\overrightarrow{y}\Vert }& ,\overrightarrow{y}\notin \mathcal{L}.\\ {\displaystyle \underset{0\ne \overrightarrow{x}\in \mathcal{L}}{min}\Vert \overrightarrow{x}\Vert }& ,\overrightarrow{y}\in \mathcal{L}.\end{array}‘\end{array}$$

ALGORITHM:

The algorithm is based on V.9 and V.10 of [Sma1998]

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import minimal_vector
sage: B = matrix(ZZ, 2, [1,1,1,0])
sage: y = vector(ZZ, [2,1])
sage: minimal_vector(B, y)
1/2

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import minimal_vector
>>> B = matrix(ZZ, Integer(2), [Integer(1),Integer(1),Integer(1),Integer(0)])
>>> y = vector(ZZ, [Integer(2),Integer(1)])
>>> minimal_vector(B, y)
1/2

Sage Live

from sage.rings.number_field.S_unit_solver import minimal_vector
B = matrix(ZZ, 2, [1,1,1,0])
y = vector(ZZ, [2,1])
minimal_vector(B, y)

Sage

sage: B = random_matrix(ZZ, 3)
sage: while not B.determinant():
....:     B = random_matrix(ZZ, 3)
sage: B # random
[-2 -1 -1]
[ 1  1 -2]
[ 6  1 -1]
sage: y = vector([1, 2, 100])
sage: minimal_vector(B, y)  # random
15/28

Python

>>> from sage.all import *
>>> B = random_matrix(ZZ, Integer(3))
>>> while not B.determinant():
...     B = random_matrix(ZZ, Integer(3))
>>> B # random
[-2 -1 -1]
[ 1  1 -2]
[ 6  1 -1]
>>> y = vector([Integer(1), Integer(2), Integer(100)])
>>> minimal_vector(B, y)  # random
15/28

Sage Live

B = random_matrix(ZZ, 3)
while not B.determinant():
    B = random_matrix(ZZ, 3)
B # random
y = vector([1, 2, 100])
minimal_vector(B, y)  # random

sage.rings.number_field.S_unit_solver.mus(SUK, v)

Return a list $[\mu ]$, for $\mu$ defined in [AKMRVW].

INPUT:

• SUK – a group of $S$-units

• v – a finite place of K

OUTPUT: list [mus] where each mu is an element of K

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import mus
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: v_fin = tuple(K.primes_above(3))[0]

sage: mus(SUK, v_fin)
[xi^2 - 2]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import mus
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> v_fin = tuple(K.primes_above(Integer(3)))[Integer(0)]

>>> mus(SUK, v_fin)
[xi^2 - 2]

Sage Live

from sage.rings.number_field.S_unit_solver import mus
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
v_fin = tuple(K.primes_above(3))[0]
mus(SUK, v_fin)

REFERENCES:

• [AKMRVW]

sage.rings.number_field.S_unit_solver.p_adic_LLL_bound(SUK, A, prec=106)

Return the maximum of all of the $K_0$’s as they are LLL-optimized for each finite place $v$.

INPUT:

• SUK – a group of $S$-units

• A – list of all products of each potential $a$, $b$ in the $S$-unit equation $ax+by+1=0$ with each root of unity of $K$

• prec – precision for $p$-adic LLL calculations (default: 106)

OUTPUT:

A bound for the max of exponents in the case that extremal place is finite (see [Sma1995]) as a real number

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: A = SUK.roots_of_unity()
sage: prec = 100
sage: p_adic_LLL_bound(SUK, A, prec)
89

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> A = SUK.roots_of_unity()
>>> prec = Integer(100)
>>> p_adic_LLL_bound(SUK, A, prec)
89

Sage Live

from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
A = SUK.roots_of_unity()
prec = 100
p_adic_LLL_bound(SUK, A, prec)

sage.rings.number_field.S_unit_solver.p_adic_LLL_bound_one_prime(prime, B0, M, M_logp, m0, c3, prec=106)

INPUT:

• prime – a prime ideal of a number field $K$

• B0 – the initial bound

• M – list of elements of $K$, the ${\mu }_i$’s from Lemma IX.3 of [Sma1998]

• M_logp – the $p$-adic logarithm of elements in $M$

• m0 – an element of $K$, this is ${\mu }_0$ from Lemma IX.3 of [Sma1998]

• c3 – a positive real constant

• prec – the precision of the calculations (default: 106), i.e., values are known to O(p^prec)

OUTPUT: a pair consisting of:

1. a new upper bound, an integer

2. a boolean value, True if we have to increase precision, otherwise False

Note

The constant $c_5$ is the constant $c_5$ at the page 89 of [Sma1998] which is equal to the constant $c_{10}$ at the page 139 of [Sma1995]. In this function, the $c_i$ constants are in line with [Sma1998], but generally differ from the constants in [Sma1995] and other parts of this code.

EXAMPLES:

This example indicates a case where we must increase precision:

Sage

sage: from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound_one_prime
sage: prec = 50
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 3)
sage: S = tuple(K.primes_above(3))
sage: SUK = UnitGroup(K, S=S)
sage: v = S[0]
sage: A = SUK.roots_of_unity()
sage: K0_old = 9.4755766731093e17
sage: Mus = [a^2 - 2]
sage: Log_p_Mus = [185056824593551109742400*a^2
....:               + 1389583284398773572269676*a + 717897987691852588770249]
sage: mu0 = K(-1)
sage: c3_value = 0.42578591347980
sage: m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
....:                                                       mu0, c3_value, prec)
sage: m0_Kv_new
0
sage: increase_prec
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound_one_prime
>>> prec = Integer(50)
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> S = tuple(K.primes_above(Integer(3)))
>>> SUK = UnitGroup(K, S=S)
>>> v = S[Integer(0)]
>>> A = SUK.roots_of_unity()
>>> K0_old = RealNumber('9.4755766731093e17')
>>> Mus = [a**Integer(2) - Integer(2)]
>>> Log_p_Mus = [Integer(185056824593551109742400)*a**Integer(2)
...               + Integer(1389583284398773572269676)*a + Integer(717897987691852588770249)]
>>> mu0 = K(-Integer(1))
>>> c3_value = RealNumber('0.42578591347980')
>>> m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
...                                                       mu0, c3_value, prec)
>>> m0_Kv_new
0
>>> increase_prec
True

Sage Live

from sage.rings.number_field.S_unit_solver import p_adic_LLL_bound_one_prime
prec = 50
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^3 - 3)
S = tuple(K.primes_above(3))
SUK = UnitGroup(K, S=S)
v = S[0]
A = SUK.roots_of_unity()
K0_old = 9.4755766731093e17
Mus = [a^2 - 2]
Log_p_Mus = [185056824593551109742400*a^2
              + 1389583284398773572269676*a + 717897987691852588770249]
mu0 = K(-1)
c3_value = 0.42578591347980
m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
                                                      mu0, c3_value, prec)
m0_Kv_new
increase_prec

And now we increase the precision to make it all work:

Sage

sage: prec = 106
sage: K0_old = 9.475576673109275443280257946930e17
sage: Log_p_Mus = [1029563604390986737334686387890424583658678662701816*a^2
....:               + 661450700156368458475507052066889190195530948403866*a]
sage: c3_value = 0.4257859134798034746197327286726
sage: m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
....:                                                       mu0, c3_value, prec)
sage: m0_Kv_new
476
sage: increase_prec
False

Python

>>> from sage.all import *
>>> prec = Integer(106)
>>> K0_old = RealNumber('9.475576673109275443280257946930e17')
>>> Log_p_Mus = [Integer(1029563604390986737334686387890424583658678662701816)*a**Integer(2)
...               + Integer(661450700156368458475507052066889190195530948403866)*a]
>>> c3_value = RealNumber('0.4257859134798034746197327286726')
>>> m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
...                                                       mu0, c3_value, prec)
>>> m0_Kv_new
476
>>> increase_prec
False

Sage Live

prec = 106
K0_old = 9.475576673109275443280257946930e17
Log_p_Mus = [1029563604390986737334686387890424583658678662701816*a^2
              + 661450700156368458475507052066889190195530948403866*a]
c3_value = 0.4257859134798034746197327286726
m0_Kv_new, increase_prec = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus,
                                                      mu0, c3_value, prec)
m0_Kv_new
increase_prec

sage.rings.number_field.S_unit_solver.possible_mu0s(SUK, v)

Return a list $[{\mu }_0]$ of all possible ${\mu }_0$ values defined in [AKMRVW].

INPUT:

• SUK – a group of $S$-units

• v – a finite place of K

OUTPUT: list [mu0s] where each mu0 is an element of K

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import possible_mu0s
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3)
sage: S = tuple(K.primes_above(3))
sage: SUK = UnitGroup(K, S=S)
sage: v_fin = S[0]

sage: possible_mu0s(SUK, v_fin)
[-1, 1]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import possible_mu0s
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3), names=('xi',)); (xi,) = K._first_ngens(1)
>>> S = tuple(K.primes_above(Integer(3)))
>>> SUK = UnitGroup(K, S=S)
>>> v_fin = S[Integer(0)]

>>> possible_mu0s(SUK, v_fin)
[-1, 1]

Sage Live

from sage.rings.number_field.S_unit_solver import possible_mu0s
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3)
S = tuple(K.primes_above(3))
SUK = UnitGroup(K, S=S)
v_fin = S[0]
possible_mu0s(SUK, v_fin)

Note

$n_0$ is the valuation of the coefficient ${\alpha }_d$ of the $S$-unit equation such that $|{\alpha }_d{\tau }_d{|}_v=1$ We have set $n_0=0$ here since the coefficients are roots of unity ${\alpha }_0$ is not defined in the paper, we set it to be 1

REFERENCES:

• [AKMRVW]

• [Sma1995] pp. 824-825, but we modify the definition of sigma (sigma_tilde) to make it easier to code

sage.rings.number_field.S_unit_solver.reduction_step_complex_case(place, B0, list_of_gens, torsion_gen, c13)

INPUT:

• place – (ring morphism) an infinite place of a number field $K$

• B0 – the initial bound

• list_of_gens – set of generators of the free part of the group

• torsion_gen – an element of the torsion part of the group

• c13 – a positive real number

OUTPUT: a tuple consisting of:

1. a new upper bound, an integer

2. a boolean value, True if we have to increase precision, otherwise False

Note

The constant c13 in Section 5, [AKMRVW] This function does handle both real and non-real infinite places.

REFERENCES:

See [Sma1998], [AKMRVW].

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import reduction_step_complex_case
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField([x^3 - 2])
sage: SK = sum([K.primes_above(p) for p in [2,3,5]],[])
sage: G = [g for g in K.S_unit_group(S=SK).gens_values()
....:        if g.multiplicative_order() == Infinity]
sage: p1 = K.places(prec=100)[1]
sage: reduction_step_complex_case(p1, 10^5, G, -1, 2)
(18, False)

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import reduction_step_complex_case
>>> x = polygen(ZZ, 'x')
>>> K = NumberField([x**Integer(3) - Integer(2)], names=('a',)); (a,) = K._first_ngens(1)
>>> SK = sum([K.primes_above(p) for p in [Integer(2),Integer(3),Integer(5)]],[])
>>> G = [g for g in K.S_unit_group(S=SK).gens_values()
...        if g.multiplicative_order() == Infinity]
>>> p1 = K.places(prec=Integer(100))[Integer(1)]
>>> reduction_step_complex_case(p1, Integer(10)**Integer(5), G, -Integer(1), Integer(2))
(18, False)

Sage Live

from sage.rings.number_field.S_unit_solver import reduction_step_complex_case
x = polygen(ZZ, 'x')
K.<a> = NumberField([x^3 - 2])
SK = sum([K.primes_above(p) for p in [2,3,5]],[])
G = [g for g in K.S_unit_group(S=SK).gens_values()
       if g.multiplicative_order() == Infinity]
p1 = K.places(prec=100)[1]
reduction_step_complex_case(p1, 10^5, G, -1, 2)

sage.rings.number_field.S_unit_solver.sieve_below_bound(K, S, bound=10, bump=10, split_primes_list=[], verbose=False)

Return all solutions to the $S$-unit equation $x+y=1$ over $K$ with exponents below the given bound.

INPUT:

• K – a number field (an absolute extension of the rationals)

• S – list of finite primes of $K$

• bound – positive integer upper bound for exponents, solutions with exponents having absolute value below this bound will be found (default: 10)

• bump – positive integer by which the minimum LCM will be increased if not enough split primes are found in sieving step (default: 10)

• split_primes_list – list of rational primes that split completely in the extension $K/\mathbf{Q}$, used for sieving. For complete list of solutions should have lcm of $\{(p_i-1)\}forprimes‘p_i$ greater than bound (default: []).

• verbose – an optional parameter allowing the user to print information during the sieving process (default: False)

OUTPUT:

A list of tuples $[(A_1,B_1,x_1,y_1),(A_2,B_2,x_2,y_2),\dots (A_n,B_n,x_n,y_n)]$ such that:

1. The first two entries are tuples $A_i=(a_0,a_1,\dots ,a_t)$ and $B_i=(b_0,b_1,\dots ,b_t)$ of exponents.

2. The last two entries are $S$-units $x_i$ and $y_i$ in $K$ with $x_i+y_i=1$.

3. If the default generators for the $S$-units of $K$ are $({\rho }_0,{\rho }_1,\dots ,{\rho }_t)$, then these satisfy $x_i=\prod ({\rho }_i{)}^{(a_i)}$ and $y_i=\prod ({\rho }_i{)}^{(b_i)}$.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import sieve_below_bound, eq_up_to_order
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^2 + x + 1)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
sage: S = SUK.primes()
sage: sols = sieve_below_bound(K, S, 10)
sage: expected = [((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....:             ((4, 1), (4, 0), xi + 2, -xi - 1),
....:             ((2, 0), (3, 1), xi, -xi + 1),
....:             ((1, 0), (5, 0), xi + 1, -xi)]
sage: eq_up_to_order(sols, expected)
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import sieve_below_bound, eq_up_to_order
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(3))))
>>> S = SUK.primes()
>>> sols = sieve_below_bound(K, S, Integer(10))
>>> expected = [((Integer(3), -Integer(1)), (Integer(2), -Integer(1)), Integer(1)/Integer(3)*xi + Integer(2)/Integer(3), -Integer(1)/Integer(3)*xi + Integer(1)/Integer(3)),
...             ((Integer(4), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)),
...             ((Integer(2), Integer(0)), (Integer(3), Integer(1)), xi, -xi + Integer(1)),
...             ((Integer(1), Integer(0)), (Integer(5), Integer(0)), xi + Integer(1), -xi)]
>>> eq_up_to_order(sols, expected)
True

Sage Live

from sage.rings.number_field.S_unit_solver import sieve_below_bound, eq_up_to_order
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^2 + x + 1)
SUK = UnitGroup(K, S=tuple(K.primes_above(3)))
S = SUK.primes()
sols = sieve_below_bound(K, S, 10)
expected = [((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
            ((4, 1), (4, 0), xi + 2, -xi - 1),
            ((2, 0), (3, 1), xi, -xi + 1),
            ((1, 0), (5, 0), xi + 1, -xi)]
eq_up_to_order(sols, expected)

sage.rings.number_field.S_unit_solver.sieve_ordering(SUK, q)

Return ordered data for running sieve on the primes in SUK over the rational prime $q$.

INPUT:

• SUK – the $S$-unit group of a number field $K$

• q – a rational prime number which splits completely in $K$

OUTPUT: list of tuples; [ideals_over_q, residue_fields, rho_images, product_rho_orders], where:

1. ideals_over_q is a list of the $d=[K:\mathbf{Q}]$ ideals in $K$ over $q$

2. residue_fields[i] is the residue field of ideals_over_q[i]

3. rho_images[i] is a list of the reductions of the generators in of the $S$-unit group, modulo ideals_over_q[i]

4. product_rho_orders[i] is the product of the multiplicative orders of the elements in rho_images[i]

Note

• The list ideals_over_q is sorted so that the product of orders is smallest for ideals_over_q[0], as this will make the later sieving steps more efficient.

• The primes of $S$ must not lie over $q$.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import sieve_ordering
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3*x + 1)
sage: SUK = K.S_unit_group(S=3)
sage: sieve_data = list(sieve_ordering(SUK, 19))
sage: sieve_data[0]
(Fractional ideal (-2*xi^2 + 3),
 Fractional ideal (-xi + 3),
 Fractional ideal (2*xi + 1))

sage: sieve_data[1]
(Residue field of Fractional ideal (-2*xi^2 + 3),
 Residue field of Fractional ideal (-xi + 3),
 Residue field of Fractional ideal (2*xi + 1))

sage: sieve_data[2]
([18, 9, 16, 8], [18, 7, 10, 4], [18, 3, 12, 10])

sage: sieve_data[3]
(972, 972, 3888)

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import sieve_ordering
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3)*x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = K.S_unit_group(S=Integer(3))
>>> sieve_data = list(sieve_ordering(SUK, Integer(19)))
>>> sieve_data[Integer(0)]
(Fractional ideal (-2*xi^2 + 3),
 Fractional ideal (-xi + 3),
 Fractional ideal (2*xi + 1))

>>> sieve_data[Integer(1)]
(Residue field of Fractional ideal (-2*xi^2 + 3),
 Residue field of Fractional ideal (-xi + 3),
 Residue field of Fractional ideal (2*xi + 1))

>>> sieve_data[Integer(2)]
([18, 9, 16, 8], [18, 7, 10, 4], [18, 3, 12, 10])

>>> sieve_data[Integer(3)]
(972, 972, 3888)

Sage Live

from sage.rings.number_field.S_unit_solver import sieve_ordering
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3*x + 1)
SUK = K.S_unit_group(S=3)
sieve_data = list(sieve_ordering(SUK, 19))
sieve_data[0]
sieve_data[1]
sieve_data[2]
sieve_data[3]

sage.rings.number_field.S_unit_solver.solutions_from_systems(SUK, bound, cs_list, split_primes_list)

Lift compatible systems to the integers and return the $S$-unit equation solutions that the lifts yield.

INPUT:

• SUK – the group of $S$-units where we search for solutions

• bound – a bound for the entries of all entries of all lifts

• cs_list – list of compatible systems of exponent vectors modulo $q-1$ for various primes $q$

• split_primes_list – list of primes giving the moduli of the exponent vectors in cs_list

OUTPUT:

A list of solutions to the S-unit equation. Each solution is a list:

1. an exponent vector over the integers, ev

2. an exponent vector over the integers, cv

3. the S-unit corresponding to ev, iota_exp

4. the S-unit corresponding to cv, iota_comp

Note

• Every entry of ev is less than or equal to bound in absolute value

• every entry of cv is less than or equal to bound in absolute value

• iota_exp + iota_comp == 1

EXAMPLES:

Given a single compatible system, a solution can be found.

Sage

sage: from sage.rings.number_field.S_unit_solver import solutions_from_systems
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^2 - 15)
sage: SUK = K.S_unit_group(S=K.primes_above(2))
sage: split_primes_list = [7, 17]
sage: a_compatible_system = [[[(0, 0, 5), (0, 0, 5)], [(0, 0, 15), (0, 0, 15)]]]
sage: solutions_from_systems(SUK, 20, a_compatible_system, split_primes_list)
[((0, 0, -1), (0, 0, -1), 1/2, 1/2)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import solutions_from_systems
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) - Integer(15), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = K.S_unit_group(S=K.primes_above(Integer(2)))
>>> split_primes_list = [Integer(7), Integer(17)]
>>> a_compatible_system = [[[(Integer(0), Integer(0), Integer(5)), (Integer(0), Integer(0), Integer(5))], [(Integer(0), Integer(0), Integer(15)), (Integer(0), Integer(0), Integer(15))]]]
>>> solutions_from_systems(SUK, Integer(20), a_compatible_system, split_primes_list)
[((0, 0, -1), (0, 0, -1), 1/2, 1/2)]

Sage Live

from sage.rings.number_field.S_unit_solver import solutions_from_systems
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^2 - 15)
SUK = K.S_unit_group(S=K.primes_above(2))
split_primes_list = [7, 17]
a_compatible_system = [[[(0, 0, 5), (0, 0, 5)], [(0, 0, 15), (0, 0, 15)]]]
solutions_from_systems(SUK, 20, a_compatible_system, split_primes_list)

sage.rings.number_field.S_unit_solver.solve_S_unit_equation(K, S, prec=106, include_exponents=True, include_bound=False, proof=None, verbose=False)

Return all solutions to the $S$-unit equation $x+y=1$ over $K$.

INPUT:

• K – a number field (an absolute extension of the rationals)

• S – list of finite primes of $K$

• prec – precision used for computations in real, complex, and $p$-adic fields (default: 106)

• include_exponents – whether to include the exponent vectors in the returned value (default: True)

• include_bound – whether to return the final computed bound (default: False)

• verbose – whether to print information during the sieving step (default: False)

OUTPUT:

A list of tuples $[(A_1,B_1,x_1,y_1),(A_2,B_2,x_2,y_2),\dots (A_n,B_n,x_n,y_n)]$ such that:

1. The first two entries are tuples $A_i=(a_0,a_1,\dots ,a_t)$ and $B_i=(b_0,b_1,\dots ,b_t)$ of exponents. These will be omitted if include_exponents is False.

2. The last two entries are $S$-units $x_i$ and $y_i$ in $K$ with $x_i+y_i=1$.

3. If the default generators for the $S$-units of $K$ are $({\rho }_0,{\rho }_1,\dots ,{\rho }_t)‘$, then these satisfy $x_i=\prod ({\rho }_i{)}^{(a_i)}$ and $y_i=\prod ({\rho }_i{)}^{(b_i)}$.

If include_bound, will return a pair (sols, bound) where sols is as above and bound is the bound used for the entries in the exponent vectors.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^2 + x + 1)
sage: S = K.primes_above(3)
sage: sols = solve_S_unit_equation(K, S, 200)
sage: expected = [((4, 1), (4, 0), xi + 2, -xi - 1),
....:             ((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....:             ((1, 0), (5, 0), xi + 1, -xi),
....:             ((2, 0), (3, 1), xi, -xi + 1)]
sage: eq_up_to_order(sols, expected)
True

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> S = K.primes_above(Integer(3))
>>> sols = solve_S_unit_equation(K, S, Integer(200))
>>> expected = [((Integer(4), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)),
...             ((Integer(3), -Integer(1)), (Integer(2), -Integer(1)), Integer(1)/Integer(3)*xi + Integer(2)/Integer(3), -Integer(1)/Integer(3)*xi + Integer(1)/Integer(3)),
...             ((Integer(1), Integer(0)), (Integer(5), Integer(0)), xi + Integer(1), -xi),
...             ((Integer(2), Integer(0)), (Integer(3), Integer(1)), xi, -xi + Integer(1))]
>>> eq_up_to_order(sols, expected)
True

Sage Live

from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^2 + x + 1)
S = K.primes_above(3)
sols = solve_S_unit_equation(K, S, 200)
expected = [((4, 1), (4, 0), xi + 2, -xi - 1),
            ((3, -1), (2, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
            ((1, 0), (5, 0), xi + 1, -xi),
            ((2, 0), (3, 1), xi, -xi + 1)]
eq_up_to_order(sols, expected)

In order to see the bound as well, use the optional parameter include_bound:

Sage

sage: solutions, bound = solve_S_unit_equation(K, S, 100, include_bound=True)
sage: bound
6

Python

>>> from sage.all import *
>>> solutions, bound = solve_S_unit_equation(K, S, Integer(100), include_bound=True)
>>> bound
6

Sage Live

solutions, bound = solve_S_unit_equation(K, S, 100, include_bound=True)
bound

You can omit the exponent vectors:

Sage

sage: sols = solve_S_unit_equation(K, S, 200, include_exponents=False)
sage: expected = [(xi + 2, -xi - 1), (1/3*xi + 2/3, -1/3*xi + 1/3),
....:             (-xi, xi + 1), (-xi + 1, xi)]
sage: set(frozenset(a) for a in sols) == set(frozenset(b) for b in expected)
True

Python

>>> from sage.all import *
>>> sols = solve_S_unit_equation(K, S, Integer(200), include_exponents=False)
>>> expected = [(xi + Integer(2), -xi - Integer(1)), (Integer(1)/Integer(3)*xi + Integer(2)/Integer(3), -Integer(1)/Integer(3)*xi + Integer(1)/Integer(3)),
...             (-xi, xi + Integer(1)), (-xi + Integer(1), xi)]
>>> set(frozenset(a) for a in sols) == set(frozenset(b) for b in expected)
True

Sage Live

sols = solve_S_unit_equation(K, S, 200, include_exponents=False)
expected = [(xi + 2, -xi - 1), (1/3*xi + 2/3, -1/3*xi + 1/3),
            (-xi, xi + 1), (-xi + 1, xi)]
set(frozenset(a) for a in sols) == set(frozenset(b) for b in expected)

It is an error to use values in S that are not primes in K:

Sage

sage: solve_S_unit_equation(K, [3], 200)
Traceback (most recent call last):
...
ValueError: S must consist only of prime ideals,
or a single element from which a prime ideal can be constructed.

Python

>>> from sage.all import *
>>> solve_S_unit_equation(K, [Integer(3)], Integer(200))
Traceback (most recent call last):
...
ValueError: S must consist only of prime ideals,
or a single element from which a prime ideal can be constructed.

Sage Live

solve_S_unit_equation(K, [3], 200)

We check the case that the rank is 0:

Sage

sage: K.<xi> = NumberField(x^2 + x + 1)
sage: solve_S_unit_equation(K, [])
[((1,), (5,), xi + 1, -xi)]

Python

>>> from sage.all import *
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> solve_S_unit_equation(K, [])
[((1,), (5,), xi + 1, -xi)]

Sage Live

K.<xi> = NumberField(x^2 + x + 1)
solve_S_unit_equation(K, [])

sage.rings.number_field.S_unit_solver.split_primes_large_lcm(SUK, bound)

Return a list $L$ of rational primes $q$ which split completely in $K$ and which have desirable properties (see NOTE).

INPUT:

• SUK – the $S$-unit group of an absolute number field $K$

• bound – positive integer

OUTPUT: list $L$ of rational primes $q$, with the following properties:

• each prime $q$ in $L$ splits completely in $K$

• if $Q$ is a prime in $S$ and $q$ is the rational prime below $Q$, then $q$ is not in $L$

• the value $\mathrm{lcm}(\{q-1:q\in L\})$ is greater than or equal to 2*bound + 1.

Note

• A series of compatible exponent vectors for the primes in $L$ will lift to at most one integer exponent vector whose entries $a_i$ satisfy $|a_i|$ is less than or equal to bound.

• The ordering of this set is not very intelligent for the purposes of the later sieving processes.

EXAMPLES:

Sage

sage: from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
sage: x = polygen(ZZ, 'x')
sage: K.<xi> = NumberField(x^3 - 3*x + 1)
sage: S = K.primes_above(3)
sage: SUK = UnitGroup(K, S=tuple(S))
sage: split_primes_large_lcm(SUK, 200)
[17, 19, 37, 53]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(3) - Integer(3)*x + Integer(1), names=('xi',)); (xi,) = K._first_ngens(1)
>>> S = K.primes_above(Integer(3))
>>> SUK = UnitGroup(K, S=tuple(S))
>>> split_primes_large_lcm(SUK, Integer(200))
[17, 19, 37, 53]

Sage Live

from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
x = polygen(ZZ, 'x')
K.<xi> = NumberField(x^3 - 3*x + 1)
S = K.primes_above(3)
SUK = UnitGroup(K, S=tuple(S))
split_primes_large_lcm(SUK, 200)

With a tiny bound, Sage may ask you to increase the bound.

Sage

sage: from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
sage: K.<xi> = NumberField(x^2 + 163)
sage: SUK = UnitGroup(K, S=tuple(K.primes_above(23)))
sage: split_primes_large_lcm(SUK, 8)
Traceback (most recent call last):
...
ValueError: Not enough split primes found. Increase bound.

Python

>>> from sage.all import *
>>> from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
>>> K = NumberField(x**Integer(2) + Integer(163), names=('xi',)); (xi,) = K._first_ngens(1)
>>> SUK = UnitGroup(K, S=tuple(K.primes_above(Integer(23))))
>>> split_primes_large_lcm(SUK, Integer(8))
Traceback (most recent call last):
...
ValueError: Not enough split primes found. Increase bound.

Sage Live

from sage.rings.number_field.S_unit_solver import split_primes_large_lcm
K.<xi> = NumberField(x^2 + 163)
SUK = UnitGroup(K, S=tuple(K.primes_above(23)))
split_primes_large_lcm(SUK, 8)

Make live