Solving S-unit equations over number fields

[malmskog]

This is a generalization of #19887.

We would like to incorporate functions to find all solutions to some classes of linear equations in the S-units of a number field. This builds on code by Christopher Rasmussen, Beth Malmskog, and Angelos Koutsianas, with contributions by Christelle Vincent, Alejandra Alvarado, and Mckenzie West. Based on work by Baker, Smart, de Weger, Yu, and others.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6e9ec60

remove test file, add new file

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3d12a9a

constants for Baker bound, passing doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​71e1969

added line to all.py in number_field to include S_unit_solver

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0486ff4

Added the sieve, it's in its own file, sieve.py

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​190f05b

Have docstrings working in S_unit_solver.py and sieve.py

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9abdc79

All doctests passed and S-unit solver being uploaded

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f4637ff

Seive updated, doc tests passed

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fa96845

Singleton list no longer a list

[roed]

I haven't read through S_unit_solver.py, but I wouldn't import everything into the global namespace in number_field/all.py.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​530abc2

Adjusted number_field/all.py to only incude solve_S_unit_equation

[chapoton]

you need to build and check the doc. For instance, the correct syntax is

EXAMPLES::

    sage: 2+2
    4

with a double colon after EXAMPLES and an empty line just after.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0d4e74e	Added references, added spacing to docstrings, added imports to docstrings for most functions
​d6db07c	solver updated

[chapoton]

1) This is not a correct syntax (around True):

+    - ````True`` or ``False``

2) ..NOTE, INPUT:, OUTPUT: and REFERENCES: should also be followed by a blank line, so this is wrong, for example:

+    ..NOTE::
+        The numerator should be as close to 1 as possible, especially as the rank of the `S`-units grows large

Also the next lines should then be indented if and only if the block command ends with ::

3) + Example:: should rather be EXAMPLES::

4) COMMENT: is not a standard block command, use nothing or ALGORITHM:

5) every single function must have a non-empty EXAMPLES:: block with useful doctests

6) comparison to None should not use prec == None but rather prec is None

7) once again, you should build the doc, and look at it, until it is completely fine !

8) This is lacking ::

+    Use CRT to check the output
+
+        sage: CRT(2, 2, 18, 27)

as well as here:

+    The order of the moduli matters.
+
+        sage: len(compatible_vectors(a, 18, 12))

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3c80f8e

Updated all docstrings to match formatting requirements, now we just need a few more examples and fine tuning

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​95a641d

Examples for every function

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e2c242b

Merge branch 't/22148/solving_s_unit_equations_over_number_fields' into sage76

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5d19c5f

updating to 8.0

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0ba9387

Merge branch 'develop' into t/22148/solving_s_unit_equations_over_number_fields

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d1e5660

adding untracked files

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​2683f65

Adding all relevant files and changes to 8.0.rc2 on a new ticket. This is being done in place of merging and rebasing, which failed due to trailing whitespace erros.

[mwest]

We will be restructuring the code, taking out the functions that may be useful elsewhere.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​0856ba1	Merging in required is_real_place function
​357586a	Merging in required abs_val function.
​28fd812	Adding all functions, doc tests passed
​7ca00f8	Adding dependency of ticket 23515
​81984d9	Functions added, all doc tests passed
​4a13ad2	Added function to find all completely split primes less than B
​fb4b993	find split primes function
​efb52b6	Sieve and final function added
​0b66b8f	references added
​135c8cb	updated develop branch

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2683f65	Adding all relevant files and changes to 8.0.rc2 on a new ticket. This is being done in place of merging and rebasing, which failed due to trailing whitespace erros.
​ba4d61c	Merging files to appease git
​7c73095	Merge branch 'develop' into ticket_22148
​f69ccba	Merged to 8.1.beta4

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cc865ae

Breaking out sieve into new function

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​38eed97

Reviewer changes

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​be25622	Updating to latest version of Sage
​2082399	Fixed documentation in compatible_system_lift

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f0d9b03

Found actual documentation error, all builds now

[chapoton]

patchbot has found many issues.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​62179a5

Updating Sage version

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​faeecea

removed solver from all.py

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4078571

Moving imports to top of doc

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a9c2f99	updated to latest version of initial bounds ticket
​5419ad1	Updated to latest version of bound reduction
​ced9505	updated inputs

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f7f9ec0	changed xrange to range, removed unnecessary imports, removing unused variables
​12bf810	More unused variables (trash, garbage, and _) and ValueErrors added to main function
​8792981	Added a few more doc tests and an additional parameter 'returnBound' to solve_S_unit_equation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​486b0be

A few small consistency changes on Matrix construction

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cf77348

Merge branch 'develop' into t/22148/solving_s_unit_equations_over_number_fields

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c10f78a	Updating Python formatting to be more readible
​4ac6b85	Updating Python formatting to be more readible
​d44b257	Changes through LLL bounds made
​6221ade	Updated formatting on remaining functions

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​20c9365

Changes in documentation?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0ba3330	changes to (default: blah) location in documentation to end of line
​2449837	Slight location change of documentation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​642260a

New sage

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5ea5b82

Merge branch 'develop' into t/22148/solving_s_unit_equations_over_number_fields

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​91bc5c2	removed some unused variables
​553ea51	Adjusting documentation and code to fit with Python conventions
​9cde3c2	removed unnecessary assignment
​ad4d6db	Some small changes for consistency
​8472bc4	Adjusting documentation and code to fit with Python conventions
​a7ee30d	Add missing sagelib dependencies
​309a701	Updating to latest version of sage adding in necessary ticket 26007
​2328f19	Merge branch 't/23515/initial_bounds_for_solutions_to_s_unit_equation' into t/23516/use_lll_to_reduce_bounds_for_s_unit_solutions
​609ca2a	Change Matrix to matrix
​7e502e9	Resolved merge errors

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​5b43621

Merge branch 'u/mwest/solving_s_unit_equations_over_number_fields' of git://trac.sagemath.org/sage into t/22148/solving_s_units

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​96ec966

Small improvements to code

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b99495e

Add long time to an LLL bound

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a07f05d	Speed improvements, add function to number fields, fix a bug in padic_LLL, add options for returning different info
​f235882	Fix ordering of output, bug in include_exponents

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5ebdf40

Fix pyflakes complaints and add code for rank 0

[roed]

I've added a fix for the cask that the S-unit group has rank 0 (ie quadratic imaginary with empty S). I've run all long tests, so if you're happy with the changes you can go ahead and mark this as positive review.

[mwest]

Thank you for taking the time to review and help Beth implement the solver as a method.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​7ce917f

py3 fixes

[roed]

I made some fixes for Python3. Running tests, and if they all pass I'll set this back to positive review.

[roed]

All tests pass, so back to positive review.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​0b82979

prec->local prec in p-adic LLL bound

[roed]

I made a change requested by one of the authors, which I agree with. I ran all long tests, which passed. Back to positive review.

[slelievre]

Two questions:

• isn't there an indentation problem in def S_unit_solutions? (if so please open follow-up ticket)
• does this solve #19887?

[mwest]

Replying to slelievre:

Two questions:

• isn't there an indentation problem in def S_unit_solutions? (if so please open follow-up ticket)
• does this solve #19887?

1. yes there is an error, fixed in #26864
2. I believe so, but I am not totally certain.