# Solve S-unit equation x + y = 1¶

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

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

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import solve_S_unit_equation, eq_up_to_order
sage: K.<xi> = NumberField(x^2+x+1)
sage: S = K.primes_above(3)
sage: expected = [((2, 1), (4, 0), xi + 2, -xi - 1),
....:             ((5, -1), (4, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....:             ((5, 0), (1, 0), -xi, xi + 1),
....:             ((1, 1), (2, 0), -xi + 1, xi)]
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
sage.rings.number_field.S_unit_solver.K0_func(SUK, A, prec=106)

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

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 K0, a real number

EXAMPLES:

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

sage: K0_func(SUK, A) # abs tol 1e-29
9.475576673109275443280257946929e17


REFERENCES:

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 K1, a real number

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import K1_func
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.396386097852707394927181864635e16

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


REFERENCES:

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

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 c11, a real number

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import c11_func
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:

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 c13, as a real number

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import c13_func
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:

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

Return the constant $$c_3$$ from Smart’s 1995 TCDF paper, [Sma1995]

INPUT:

• SUK – a group of $$S$$-units
• prec – the precision of the real field (default: 106)

OUTPUT:

The constant c3, as a real number

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import c3_func
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:

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 c4, as a real number

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import c4_func
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:

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

Return the constants $$c_8$$ and $$c_9$$ from Smart’s TCDF paper, [Sma1995]

INPUT:

• SUK – a group of $$S$$-units
• v – a finite place of K (a fractional ideal)
• 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

OUTPUT:

The constants c8 and c9, as real numbers

EXAMPLES:

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

sage: c8_c9_func(SUK, v_fin,A) # abs tol 1e-29
(4.524941291354698258804956696127e15, 1.621521281297160786545580368612e16)


REFERENCES:

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

Given a residue field vector dictionary, removes 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 the entries of 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 appearas 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: 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:

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, returns 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, determines 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)

A function to 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 $$\mathbb{Z}$$ to look for true $$S$$-Unit equation solutions.
• During construction, the various dictionaries are compared to each other several times to eliminate as many mod $$q$$ solutions as possible.
• The authors acknowledge a helpful discussion with Norman Danner which helped formulate this code.

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import construct_complement_dictionaries
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: 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
22

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

Determines 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: p = K.prime_above(13); p
Fractional ideal (-a + 2)
sage: embedding_to_Kp(a-3, p, 15)
-20542890112375827

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], checks 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: 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: 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: 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 on pp. 824-825 of TCDF, [Sma1995]

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

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

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 indictes 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: 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_precision = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus, mu0, c3_value, prec)
sage: m0_Kv_new
0
sage: increase_precision
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_precision = p_adic_LLL_bound_one_prime(v, K0_old, Mus, Log_p_Mus, mu0, c3_value, prec)
sage: m0_Kv_new
476
sage: increase_precision
False

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

Return a list $$[\mu_0]$$ of all possible $$\mu_0$$ values defined on pp. 824-825 of TCDF, [Sma1995]

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

• [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, G, g0, c7)

INPUT:

• place – (ring morphism) a complex place of a number field $$K$$
• B0 – the initial bound
• G – a set of generators of the free part of the group
• g0 – an element of the torsion part of the group
• c7 – 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 c7 in the reference page 138

REFERENCES:

See [Sma1998].

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import reduction_step_complex_case
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)
(17, False)

sage.rings.number_field.S_unit_solver.reduction_step_real_case(place, B0, G, c7)

INPUT:

• place – (ring morphism) a real place of a number field $$K$$
• B0 – the initial bound
• G – a set of generators of the free part of the group
• c7 – 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 c7 in the reference page 137

REFERENCES:

EXAMPLES:

sage: from sage.rings.number_field.S_unit_solver import reduction_step_real_case
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.real_places(prec=300)[0]
sage: reduction_step_real_case(p1, 10**10, G, 2)
(58, 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/Q, 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), ... ( A_n, B_n, x_n, y_n)] such that:

1. The first two entries are tuples A_i = (a_0, a_1, ... , a_t) and B_i = (b_0, b_1, ... , 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, ... , 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: 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 = [
....: ((5, -1), (4, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....: ((2, 1), (4, 0), xi + 2, -xi - 1),
....: ((2, 0), (1, 1), xi, -xi + 1),
....: ((5, 0), (1, 0), -xi, xi + 1)]
sage: eq_up_to_order(sols, expected)
True

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

Returns 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:\mathbb{Q}]$$ ideals in $$K$$ over $$q$$
2. residue_fields[i] is the residue field of ideals_over_q[i]
3. rho_images[i] is a list of the reductions of the generators in of the $$S$$-unit group, modulo ideals_over_q[i]
4. product_rho_orders[i] is the product of the multiplicative orders of the elements in rho_images[i]

Note

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

EXAMPLES:

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

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

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

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

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

Lifts compatible systems to the integers and returns the S-unit equation solutions 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: 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), ... ( A_n, B_n, x_n, y_n)] such that:

1. The first two entries are tuples A_i = (a_0, a_1, ... , a_t) and B_i = (b_0, b_1, ... , b_t) of exponents. These will be ommitted 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, ... , 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: K.<xi> = NumberField(x^2+x+1)
sage: S = K.primes_above(3)
sage: sols = solve_S_unit_equation(K, S, 200)
sage: expected = [
....: ((2, 1), (4, 0), xi + 2, -xi - 1),
....: ((5, -1), (4, -1), 1/3*xi + 2/3, -1/3*xi + 1/3),
....: ((5, 0), (1, 0), -xi, xi + 1),
....: ((1, 1), (2, 0), -xi + 1, xi)]
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
2


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: 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.
`