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: 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 = [((0, 1), (4, 0), xi + 2, -xi - 1),
....: ((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....: ((1, 0), (5, 0), xi + 1, -xi),
....: ((2, 0), (5, 1), xi, -xi + 1)]
sage: sols = solve_S_unit_equation(K, S, 200)
sage: eq_up_to_order(sols, expected)
True
>>> 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(0), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)),
... ((Integer(1), -Integer(1)), (Integer(0), -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(5), Integer(1)), xi, -xi + Integer(1))]
>>> sols = solve_S_unit_equation(K, S, Integer(200))
>>> eq_up_to_order(sols, expected)
True
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 = [((0, 1), (4, 0), xi + 2, -xi - 1),
((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
((1, 0), (5, 0), xi + 1, -xi),
((2, 0), (5, 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:
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)[source]¶
Return the constant \(K_0\) from [AKMRVW].
INPUT:
SUK– a group of \(S\)-unitsA– 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: 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
>>> 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
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
- sage.rings.number_field.S_unit_solver.K1_func(SUK, v, A, prec=106)[source]¶
Return the constant \(K_1\) from Smart’s TCDF paper, [Sma1995].
INPUT:
SUK– a group of \(S\)-unitsv– an infinite place of \(K\) (element ofSUK.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: 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
>>> 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
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)[source]¶
Return the constant \(\Omega'\) 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 sublistmu_list[1:]is multiplicatively independentprec– the precision of the real field
OUTPUT: the constant \(\Omega'\)
EXAMPLES:
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
>>> 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
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:
- sage.rings.number_field.S_unit_solver.Yu_C1_star(n, v, prec=106)[source]¶
Return the constant \(C_1^*\) 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^*\) as a real number
EXAMPLES:
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
>>> 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
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)[source]¶
Compute the constants a(1), kappa1, and c(1) of [Yu2007].
INPUT:
p– a rational prime numberdK– the absolute degree of some number field \(K\)ep– the absolute ramification index of some primefrak_pof \(K\) lying above \(p\)
OUTPUT:
The constants a(1), kappa1, and c(1).
EXAMPLES:
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)
>>> 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)
from sage.rings.number_field.S_unit_solver import Yu_a1_kappa1_c1 Yu_a1_kappa1_c1(5, 10, 3)
REFERENCES:
- sage.rings.number_field.S_unit_solver.Yu_bound(SUK, v, prec=106)[source]¶
Return \(c_8\) such that \(c_8 \geq exp(2)/\log(2)\) and \(ord_p (\Theta - 1) < c_8 \log B\), where \(\Theta = \prod_{j=1}^n \alpha_j^{b_j}\) and \(B \geq \max_j |b_j|\) and \(B \geq 3\).
INPUT:
SUK– a group of \(S\)-unitsv– 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: 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
>>> 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
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:
- sage.rings.number_field.S_unit_solver.Yu_condition_115(K, v)[source]¶
Return
TrueorFalse, as the number fieldKand the finite placevsatisfy condition (1.15) of [Yu2007].INPUT:
K– a number fieldv– a finite place ofK
OUTPUT:
Trueif (1.15) is satisfied, otherwiseFalse.EXAMPLES:
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
>>> 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
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)[source]¶
Return the value of h(n)(mu) as appearing in [Yu2007] equation (1.21).
INPUT:
mu– an element of a field Kn– number of mu_j to be considered in Yu’s Theoremv– a place of Kprec– the precision of the real field
OUTPUT:
The value \(h_p(mu)\).
EXAMPLES:
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
>>> 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
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)[source]¶
Return a pair \([\beta_k,|beta_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 wherebetais an element ofSUK.fundamental_units()
OUTPUT:
The pair
[beta_k,v(beta_k)], wherebeta_kis an element ofKandval_v(beta_k)is a integer.EXAMPLES:
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]
>>> 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]
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)[source]¶
Return the constant \(c_{11}\) from Smart’s TCDF paper, [Sma1995].
INPUT:
SUK– a group of \(S\)-unitsv– a place of \(K\), finite (a fractional ideal) or infinite (element ofSUK.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: 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
>>> 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
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)[source]¶
Return the constant \(c_{13}\) from Smart’s TCDF paper, [Sma1995].
INPUT:
SUK– a group of \(S\)-unitsv– an infinite place ofK(element ofSUK.number_field().places(prec))prec– the precision of the real field (default: 106)
OUTPUT: the constant \(c_{13}\), as a real number
EXAMPLES:
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
>>> 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
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: phi_finite = K.primes_above(3)[0] sage: c13_func(SUK, phi_finite) Traceback (most recent call last): ... TypeError: Place must be infinite
>>> 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
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)[source]¶
Return the constant \(c_3\) from [AKMRVW].
INPUT:
SUK– a group of \(S\)-unitsprec– the precision of the real field (default: 106)
OUTPUT: the constant \(c_3\), as a real number
EXAMPLES:
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
>>> 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
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:
- sage.rings.number_field.S_unit_solver.c4_func(SUK, v, A, prec=106)[source]¶
Return the constant \(c_4\) from Smart’s TCDF paper, [Sma1995].
INPUT:
SUK– a group of \(S\)-unitsv– a place ofK, finite (a fractional ideal) or infinite (element ofSUK.number_field().places(prec))A– the set of the product of the coefficients of theS-unit equation with each root of unity ofKprec– the precision of the real field (default: 106)
OUTPUT: the constant \(c_4\), as a real number
EXAMPLES:
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
>>> 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
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)[source]¶
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: 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]}
>>> 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]}
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)[source]¶
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: 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)]
>>> 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)]
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)[source]¶
Return the log vector of
iota; i.e., the logs of all the valuations.INPUT:
SUK– a group of \(S\)-unitsiota– an element ofKU– list of places (finite or infinite) ofKprec– the precision of the real field (default: 106)
OUTPUT: the log vector as a list of real numbers
EXAMPLES:
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]
>>> 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]
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)[source]¶
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 moduloqi - 1, and all pairs are compatiblesplit_primes_list– list of primes[ q0, q1, .., qk ]
OUTPUT: a pair of vectors
[v, w]satisfying:v[0] == vi[0]for alliw[0] == wi[0]for alliv[j] == vi[j]moduloqi - 1for alliand allj > 0w[j] == wi[j]moduloqi - 1for alliand all \(j > 0`\)every entry of
vandwis bounded byL/2in absolute value, whereLis the least common multiple of{qi - 1 : qi in split_primes_list }
EXAMPLES:
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)]
>>> 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)]
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)[source]¶
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 fromsplit_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_listhas 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: 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)]]]
>>> 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)]]]
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)[source]¶
Given an exponent vector
amodulom0, return an iterator over the exponent vectors for the modulusm1, such that a lift to the lcm modulus exists.INPUT:
a– an exponent vector for the modulusm0m0– positive integer (specifying the modulus fora)m1– positive integer (specifying the alternate modulus)g– the gcd ofm0andm1
OUTPUT: list of exponent vectors modulo
m1which are compatible withaNote
Exponent vectors must agree exactly in the 0th position in order to be compatible.
EXAMPLES:
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)]
>>> 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)]
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: len(list(compatible_vectors(a, 18, 12, gcd(18,12)))) 8 sage: len(list(compatible_vectors(a, 12, 18, gcd(18,12)))) 27
>>> 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
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)[source]¶
Given exponent vectors with respect to two moduli, determine if they are compatible.
INPUT:
a0– an exponent vector modulom0a1– an exponent vector modulom1(must have the same length asa0)g– the gcd ofm0andm1l– the length ofa0and ofa1
OUTPUT:
Trueif there is an integer exponent vector a satisfying\[\begin{split}\begin{aligned} a[0] &== a0[0] == a1[0]\\ a[1:] &== a0[1:] \mod m_0\\ a[1:] &== a1[1:] \mod m_1 \end{aligned}\end{split}\]and
Falseotherwise.Note
Exponent vectors must agree exactly in the first coordinate.
If exponent vectors are different lengths, an error is raised.
EXAMPLES:
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
>>> 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
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)[source]¶
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 vectorq– 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 toaEXAMPLES:
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: 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)]}
>>> 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)]}
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)[source]¶
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_vecwill later be lifted to \(\ZZ\) 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: 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): [(1, 0, 0), (0, 1, 0)], ....: (1, 0, 0): [(1, 0, 0), (0, 1, 0)]}, ....: 7: {(0, 1, 0): [(1, 0, 0), (1, 4, 4), (1, 2, 2)], ....: (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)], ....: (0, 3, 2): [(1, 0, 0), (1, 4, 4), (1, 2, 2)], ....: (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, 4, 4), (1, 2, 2)], ....: (1, 0, 0): [(0, 5, 4), (0, 3, 2), (0, 1, 0)], ....: (1, 0, 2): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], ....: (1, 0, 4): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], ....: (1, 2, 0): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], ....: (1, 2, 2): [(0, 5, 4), (0, 3, 2), (0, 1, 0)], ....: (1, 2, 4): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], ....: (1, 4, 0): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], ....: (1, 4, 2): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], ....: (1, 4, 4): [(0, 5, 4), (0, 3, 2), (0, 1, 0)]}} sage: all(set(actual[p][vec]) == set(expected[p][vec]) ....: for p in [3, 7] for vec in expected[p]) True
>>> 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(1), Integer(0), 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(7): {(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(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(4), Integer(4)), (Integer(1), Integer(2), Integer(2))], ... (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(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(0), Integer(2)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(4), Integer(2)), (Integer(1), Integer(2), Integer(0))], ... (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(1), Integer(2), Integer(0)): [(Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0)), (Integer(1), Integer(0), Integer(2))], ... (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(2), Integer(4)): [(Integer(1), Integer(0), Integer(4)), (Integer(1), Integer(4), Integer(2)), (Integer(1), Integer(2), 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(4), Integer(2)): [(Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(0)), (Integer(1), Integer(0), Integer(2))], ... (Integer(1), Integer(4), Integer(4)): [(Integer(0), Integer(5), Integer(4)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(1), Integer(0))]}} >>> all(set(actual[p][vec]) == set(expected[p][vec]) ... for p in [Integer(3), Integer(7)] for vec in expected[p]) True
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): [(1, 0, 0), (0, 1, 0)], (1, 0, 0): [(1, 0, 0), (0, 1, 0)]}, 7: {(0, 1, 0): [(1, 0, 0), (1, 4, 4), (1, 2, 2)], (0, 1, 2): [(0, 1, 2), (0, 3, 4), (0, 5, 0)], (0, 3, 2): [(1, 0, 0), (1, 4, 4), (1, 2, 2)], (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, 4, 4), (1, 2, 2)], (1, 0, 0): [(0, 5, 4), (0, 3, 2), (0, 1, 0)], (1, 0, 2): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], (1, 0, 4): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], (1, 2, 0): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], (1, 2, 2): [(0, 5, 4), (0, 3, 2), (0, 1, 0)], (1, 2, 4): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], (1, 4, 0): [(1, 0, 4), (1, 4, 2), (1, 2, 0)], (1, 4, 2): [(1, 2, 4), (1, 4, 0), (1, 0, 2)], (1, 4, 4): [(0, 5, 4), (0, 3, 2), (0, 1, 0)]}} 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)[source]¶
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 vectorsq– 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
Pwhose 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, thenP[r0]is a list which containse0.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: 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)]}
>>> 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)]}
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)[source]¶
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\)-unitsA– 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: 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
>>> 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
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)[source]¶
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^precto a defining polynomial for the completion of \(K\) associated to the specified primeNote
\(K\) has to be an absolute extension
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
Determine if the exponent vector,
ev, may be removed from the complement dictionary during construction. This will occur ifevis not compatible with an exponent vector mod \(q-1\).INPUT:
ev– an exponent vector modulo \(p-1\)p– the prime such thatevis an exponent vector modulo \(p-1\)q– a prime, distinct from \(p\), that is a key in thecomplement_ev_dictcomplement_ev_dict– dictionary of dictionaries, whose keys are primescomplement_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:
Trueifevmay be dropped from the complement exponent vector dictionary, andFalseif notNote
If
evis 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 returnsTrueto indicate that it should be removed.
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
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 belowprimeand \(e\), \(f\) are the ramification index and residue degree, respectively.Note
\(K\) has to be an absolute number field
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
If
AandBare lists of four-tuples[a0,a1,a2,a3]and[b0,b1,b2,b3], check that there is some reordering so that eitherai=bifor alliora0==b1,a1==b0,a2==b3,a3==b2.The entries must be hashable.
EXAMPLES:
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
>>> 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
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)[source]¶
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 toprimemodulop^prec, where \(p\) is the rational prime belowprime.Note
Here we take into account the other primes in \(K\) above \(p\) in order to get coefficients with small values.
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
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 accuracyp^prec, where \(p\) is the rational prime belowprime.ALGORITHM:
The algorithm is based on the algorithm on page 30 of [Sma1998].
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
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 coordinatesprec– precision of real field (default: 106)
OUTPUT: a lower bound for the square of
\[\begin{split}\ell (\mathcal L,\vec y) = \begin{cases} \displaystyle\min_{\vec x\in\mathcal L}\Vert\vec x-\vec y\Vert &, \vec y\not\in\mathcal L. \\ \displaystyle\min_{0\neq\vec x\in\mathcal L}\Vert\vec x\Vert &,\vec y\in\mathcal L. \end{cases}`\end{split}\]ALGORITHM:
The algorithm is based on V.9 and V.10 of [Sma1998]
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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)[source]¶
Return a list \([\mu]\), for \(\mu\) defined in [AKMRVW].
INPUT:
SUK– a group of \(S\)-unitsv– a finite place ofK
OUTPUT: list
[mus]where eachmuis an element ofKEXAMPLES:
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]
>>> 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]
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:
- sage.rings.number_field.S_unit_solver.p_adic_LLL_bound(SUK, A, prec=106)[source]¶
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\)-unitsA– 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: 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
>>> 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
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)[source]¶
INPUT:
prime– a prime ideal of a number field \(K\)B0– the initial boundM– 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 constantprec– the precision of the calculations (default: 106), i.e., values are known toO(p^prec)
OUTPUT: a pair consisting of:
a new upper bound, an integer
a boolean value,
Trueif we have to increase precision, otherwiseFalse
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: 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
>>> 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
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_precAnd now we increase the precision to make it all work:
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
>>> 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
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)[source]¶
Return a list \([\mu_0]\) of all possible \(\mu_0\) values defined in [AKMRVW].
INPUT:
SUK– a group of \(S\)-unitsv– a finite place ofK
OUTPUT: list
[mu0s]where eachmu0is an element ofKEXAMPLES:
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]
>>> 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]
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:
- sage.rings.number_field.S_unit_solver.reduction_step_complex_case(place, B0, list_of_gens, torsion_gen, c13)[source]¶
INPUT:
place– (ring morphism) an infinite place of a number field \(K\)B0– the initial boundlist_of_gens– set of generators of the free part of the grouptorsion_gen– an element of the torsion part of the groupc13– a positive real number
OUTPUT: a tuple consisting of:
a new upper bound, an integer
a boolean value,
Trueif we have to increase precision, otherwiseFalse
Note
The constant
c13in Section 5, [AKMRVW] This function does handle both real and non-real infinite places.REFERENCES:
EXAMPLES:
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)
>>> 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)
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)[source]¶
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/\QQ\), used for sieving. For complete list of solutions should have lcm of \(\{(p_i-1)\} for primes `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:
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.
The last two entries are \(S\)-units \(x_i\) and \(y_i\) in \(K\) with \(x_i + y_i = 1\).
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: 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 = [((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3), ....: ((0, 1), (4, 0), xi + 2, -xi - 1), ....: ((2, 0), (5, 1), xi, -xi + 1), ....: ((1, 0), (5, 0), xi + 1, -xi)] sage: eq_up_to_order(sols, expected) True
>>> 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(1), -Integer(1)), (Integer(0), -Integer(1)), Integer(1)/Integer(3)*xi + Integer(2)/Integer(3), -Integer(1)/Integer(3)*xi + Integer(1)/Integer(3)), ... ((Integer(0), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)), ... ((Integer(2), Integer(0)), (Integer(5), 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
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 = [((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3), ((0, 1), (4, 0), xi + 2, -xi - 1), ((2, 0), (5, 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)[source]¶
Return ordered data for running sieve on the primes in
SUKover 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:ideals_over_qis a list of the \(d = [K:\QQ]\) ideals in \(K\) over \(q\)residue_fields[i]is the residue field ofideals_over_q[i]rho_images[i]is a list of the reductions of the generators in of the \(S\)-unit group, moduloideals_over_q[i]product_rho_orders[i]is the product of the multiplicative orders of the elements inrho_images[i]
Note
The list
ideals_over_qis sorted so that the product of orders is smallest forideals_over_q[0], as this will make the later sieving steps more efficient.The primes of \(S\) must not lie over \(q\).
EXAMPLES:
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, 12, 16, 8], [18, 16, 10, 4], [18, 10, 12, 10]) sage: sieve_data[3] (648, 2916, 3888)
>>> 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, 12, 16, 8], [18, 16, 10, 4], [18, 10, 12, 10]) >>> sieve_data[Integer(3)] (648, 2916, 3888)
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)[source]¶
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 solutionsbound– a bound for the entries of all entries of all liftscs_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 incs_list
OUTPUT:
A list of solutions to the S-unit equation. Each solution is a list:
an exponent vector over the integers,
evan exponent vector over the integers,
cvthe S-unit corresponding to
ev,iota_expthe S-unit corresponding to
cv,iota_comp
Note
Every entry of
evis less than or equal to bound in absolute valueevery entry of
cvis less than or equal to bound in absolute valueiota_exp + iota_comp == 1
EXAMPLES:
Given a single compatible system, a solution can be found.
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)]
>>> 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)]
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)[source]¶
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:
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_exponentsisFalse.The last two entries are \(S\)-units \(x_i\) and \(y_i\) in \(K\) with \(x_i + y_i = 1\).
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)wheresolsis as above andboundis the bound used for the entries in the exponent vectors.EXAMPLES:
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 = [((0, 1), (4, 0), xi + 2, -xi - 1), ....: ((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3), ....: ((1, 0), (5, 0), xi + 1, -xi), ....: ((2, 0), (5, 1), xi, -xi + 1)] sage: eq_up_to_order(sols, expected) True
>>> 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(0), Integer(1)), (Integer(4), Integer(0)), xi + Integer(2), -xi - Integer(1)), ... ((Integer(1), -Integer(1)), (Integer(0), -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(5), Integer(1)), xi, -xi + Integer(1))] >>> eq_up_to_order(sols, expected) True
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 = [((0, 1), (4, 0), xi + 2, -xi - 1), ((1, -1), (0, -1), 1/3*xi + 2/3, -1/3*xi + 1/3), ((1, 0), (5, 0), xi + 1, -xi), ((2, 0), (5, 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: solutions, bound = solve_S_unit_equation(K, S, 100, include_bound=True) sage: bound 7
>>> from sage.all import * >>> solutions, bound = solve_S_unit_equation(K, S, Integer(100), include_bound=True) >>> bound 7
solutions, bound = solve_S_unit_equation(K, S, 100, include_bound=True) bound
You can omit the exponent vectors:
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
>>> 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
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: 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.
>>> 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.
solve_S_unit_equation(K, [3], 200)
We check the case that the rank is 0:
sage: K.<xi> = NumberField(x^2 + x + 1) sage: solve_S_unit_equation(K, []) [((1,), (5,), xi + 1, -xi)]
>>> 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)]
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)[source]¶
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 \(\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: 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]
>>> 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]
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: 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.
>>> 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.
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)