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

Todo

• Use Cython to improve timings on the sieve

REFERENCES:

• [MR2016]

• [Sma1995]

• [Sma1998]

• [Yu2007]

• [AKMRVW]

AUTHORS:

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

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

Return the constant \(K_0\) from [AKMRVW].

INPUT:

• SUK – a group of \(S\)-units

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

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

OUTPUT:

The constant \(K_0\), a real number.

EXAMPLES:

sage: 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

REFERENCES:

• [Sma1995] p. 824

• [AKMRVW] arXiv 1903.00977

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

Return the constant \(K_1\) from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of \(S\)-units

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

• A – 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

REFERENCES:

• [Sma1995] p. 825

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

Return the constant \(\Omega'\) appearing in [AKMRVW].

INPUT:

• dK – the degree of a number field \(K\)

• v – a finite place of \(K\)

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

• prec – the precision of the real field

OUTPUT:

The constant \(\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

REFERENCES:

• [AKMRVW] arXiv 1903.00977

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

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

REFERENCES:

• [Yu2007] p.189,193

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

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

INPUT:

• p – a rational prime number

• dK – the absolute degree of some number field \(K\)

• ep – the absolute ramification index of some prime frak_p of \(K\) lying above \(p\)

OUTPUT:

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

EXAMPLES:

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

REFERENCES:

• [Yu2007]

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

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\)-units

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

• prec – the precision of the real field

OUTPUT:

The constant \(c_8\) as a real number.

EXAMPLES:

sage: 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

REFERENCES:

• [Sma1995] p. 825

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

• [AKMRVW] arXiv 1903.00977

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

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

INPUT:

• K – a number field

• v – a finite place of K

OUTPUT:

True if (1.15) is satisfied, otherwise False.

EXAMPLES:

sage: 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

REFERENCES:

• [Yu2007] p. 188

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

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

INPUT:

• mu – an element of a field K

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

• v – a place of K

• prec – the precision of the real field

OUTPUT:

The value \(h_p(mu)\).

EXAMPLES:

sage: 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

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

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

REFERENCES:

• [Yu2007] p. 192

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

Return a pair \([\beta_k,|beta_k|_v]\), where \(\beta_k\) has the smallest nonzero valuation in absolute value of the list betas_and_ns.

INPUT:

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

OUTPUT:

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

EXAMPLES:

sage: 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]

REFERENCES:

• [Sma1995] pp. 824-825

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

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

INPUT:

• SUK – a group of \(S\)-units

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

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

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

OUTPUT:

The constant \(c_{11}\), a real number

EXAMPLES:

sage: 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

REFERENCES:

• [Sma1995] p. 825

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

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

INPUT:

• SUK – a group of \(S\)-units

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

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

OUTPUT:

The constant \(c_{13}\), as a real number

EXAMPLES:

sage: 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

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

REFERENCES:

• [Sma1995] p. 825

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

Return the constant \(c_3\) from [AKMRVW].

INPUT:

• SUK – a group of \(S\)-units

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

OUTPUT:

The constant \(c_3\), as a real number

EXAMPLES:

sage: 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

Note

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

REFERENCES:

• [AKMRVW] arXiv 1903.00977

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

Return the constant \(c_4\) from Smart’s TCDF paper, [Sma1995].

INPUT:

• SUK – a group of \(S\)-units

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

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

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

OUTPUT:

The constant \(c_4\), as a real number

EXAMPLES:

sage: 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

REFERENCES:

• [Sma1995] p. 824

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

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

INPUT:

• rfv_dictionary – a 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]}

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

Given a list of \(S\)-unit equation solutions, remove trivial redundancies.

INPUT:

• sfs_list – a list of solutions to the \(S\)-unit equation

OUTPUT:

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

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

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

INPUT:

• SUK – a group of \(S\)-units

• iota – an element of K

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

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

OUTPUT:

The log vector as a list of real numbers

EXAMPLES:

sage: 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]

REFERENCES:

• [Sma1995] p. 823

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

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

INPUT:

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

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

OUTPUT:

A pair of vectors [v, w] satisfying:

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

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

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

4. w[j] == wi[j] modulo qi - 1 for all i and all \(j > 0`\)

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

EXAMPLES:

sage: 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)]

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

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

INPUT:

• split_prime_list – a list of rational primes that split completely in \(K\)

• complement_exp_vec_dict – a dictionary of dictionaries. The keys are primes from split_prime_list.

OUTPUT:

A list of compatible systems of exponent vectors.

Note

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

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

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

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

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

EXAMPLES:

sage: 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)]]]

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

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

INPUT:

• a – an exponent vector for the modulus m0

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

• m1 – a positive integer (specifying the alternate modulus)

• g – the gcd of m0 and m1

OUTPUT:

A list of exponent vectors modulo m1 which are compatible with a.

Note

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

EXAMPLES:

sage: 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)]

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

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

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

INPUT:

• a0 – an exponent vector modulo m0

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

• g – the gcd of m0 and m1

• l – the length of a0 and of a1

OUTPUT:

True if there is an integer exponent vector a satisfying

\[\begin{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 False otherwise.

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

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

Constructs a dictionary associating complement vectors to residue field vectors.

INPUT:

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

• q – the characteristic of the residue field

OUTPUT:

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

EXAMPLES:

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

sage: 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)]}

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

Construct the complement exponent vector dictionaries.

INPUT:

• split_primes_list – a list of rational primes which split completely in the number field \(K\)

• SUK – the \(S\)-unit group for a number field \(K\)

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

OUTPUT:

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

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

Note

• The data of comp_exp_vec will later be lifted to \(\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

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

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

INPUT:

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

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

• d – the number of primes in \(K\) above the rational prime \(q\)

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

OUTPUT:

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

Note

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

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

EXAMPLES:

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

sage: 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)]}

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

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

INPUT:

• SUK – a group of \(S\)-units

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

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

OUTPUT:

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

EXAMPLES:

sage: 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

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

INPUT:

• prime – a prime ideal of a number field \(K\)

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

OUTPUT:

A polynomial with integer coefficients that is equivalent mod p^prec to a defining polynomial for the completion of \(K\) associated to the specified prime.

Note

\(K\) has to be an absolute extension

EXAMPLES:

sage: 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

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

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

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

INPUT:

• ev – an exponent vector modulo \(p-1\)

• p – the prime such that ev is an exponent vector modulo \(p-1\)

• q – a prime, distinct from \(p\), that is a key in the complement_ev_dict

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

OUTPUT:

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

Note

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

EXAMPLES:

sage: 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

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

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

INPUT:

• a – an element of a number field \(K\)

• prime – a prime ideal of \(K\)

• prec – a positive natural number

OUTPUT:

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

Note

\(K\) has to be an absolute number field

EXAMPLES:

sage: 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

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

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

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

The entries must be hashable.

EXAMPLES:

sage: 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

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

INPUT:

• a – an element of a number field \(K\)

• prime – a prime ideal of the number field \(K\)

• prec – a positive integer

OUTPUT:

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

Note

Here we take into account the other primes in \(K\) above \(p\) in order to get coefficients with small values

EXAMPLES:

sage: 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

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

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

INPUT:

• a – an element of a number field \(K\)

• prime – a prime ideal of the number field \(K\)

• prec – a positive integer

OUTPUT:

The prime-adic logarithm of \(a\) and accuracy p^prec, where \(p\) is the rational prime below prime

ALGORITHM:

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

EXAMPLES:

sage: 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

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

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

INPUT:

• A – a square \(n\) by \(n\) non-singular integer matrix whose rows generate a lattice \(\mathcal L\)

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

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

OUTPUT:

A lower bound for the square of

\[\begin{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

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

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

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

INPUT:

• SUK – a group of \(S\)-units

• v – a finite place of K

OUTPUT:

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

EXAMPLES:

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]

REFERENCES:

• [AKMRVW]

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

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

INPUT:

• SUK – a group of \(S\)-units

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

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

OUTPUT:

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

EXAMPLES:

sage: 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

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

INPUT:

• prime – a prime ideal of a number field \(K\)

• B0 – the initial bound

• M – a list of elements of \(K\), the \(\mu_i\)’s from Lemma IX.3 of [Sma1998]

• M_logp – the p-adic logarithm of elements in \(M\)

• m0 – an element of \(K\), this is \(\mu_0\) from Lemma IX.3 of [Sma1998]

• c3 – a positive real constant

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

OUTPUT:

A pair consisting of:

1. a new upper bound, an integer

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

Note

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

EXAMPLES:

This example indicates a case where we must increase precision:

sage: 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

And 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

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

Return a list \([\mu_0]\) of all possible \(\mu_0\) values defined in [AKMRVW].

INPUT:

• SUK – a group of \(S\)-units

• v – a finite place of K

OUTPUT:

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

EXAMPLES:

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]

Note

\(n_0\) is the valuation of the coefficient \(\alpha_d\) of the \(S\)-unit equation such that \(|\alpha_d \tau_d|_v = 1\) We have set \(n_0 = 0\) here since the coefficients are roots of unity \(\alpha_0\) is not defined in the paper, we set it to be 1

REFERENCES:

• [AKMRVW]

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

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

INPUT:

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

• B0 – the initial bound

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

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

• c13 – a positive real number

OUTPUT:

A tuple consisting of:

1. a new upper bound, an integer

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

Note

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

REFERENCES:

See [Sma1998], [AKMRVW].

EXAMPLES:

sage: 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)

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

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

INPUT:

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

• S – a list of finite primes of \(K\)

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

• bump – a 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 – a 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:

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

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

3. If the default generators for the \(S\)-units of \(K\) are \((\rho_0, \rho_1, \dots, \rho_t)\), then these satisfy \(x_i = \prod(\rho_i)^{(a_i)}\) and \(y_i = \prod(\rho_i)^{(b_i)}\).

EXAMPLES:

sage: 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

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

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

INPUT:

• SUK – the \(S\)-unit group of a number field \(K\)

• q – a rational prime number which splits completely in \(K\)

OUTPUT:

A list of tuples, [ideals_over_q, residue_fields, rho_images, product_rho_orders], where

1. ideals_over_q is a list of the \(d = [K:\QQ]\) ideals in \(K\) over \(q\)

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

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

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

Note

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

• The primes of \(S\) must not lie over \(q\).

EXAMPLES:

sage: 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)

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

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

INPUT:

• SUK – the group of \(S\)-units where we search for solutions

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

• cs_list – a list of compatible systems of exponent vectors modulo \(q-1\) for various primes \(q\)

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

OUTPUT:

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

1. an exponent vector over the integers, ev

2. an exponent vector over the integers, cv

3. the S-unit corresponding to ev, iota_exp

4. the S-unit corresponding to cv, iota_comp

Note

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

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

• iota_exp + iota_comp == 1

EXAMPLES:

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

sage: 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)]

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

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

INPUT:

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

• S – a list of finite primes of \(K\)

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

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

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

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

OUTPUT:

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

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

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

3. If the default generators for the \(S\)-units of \(K\) are \((\rho_0, \rho_1, \dots, \rho_t)`\), then these satisfy \(x_i = \prod(\rho_i)^{(a_i)}\) and \(y_i = \prod(\rho_i)^{(b_i)}\).

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

EXAMPLES:

sage: 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

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

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

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.

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

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

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

INPUT:

• SUK – the \(S\)-unit group of an absolute number field \(K\).

• bound – a positive integer

OUTPUT:

A 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]

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.