#27657 closed enhancement (fixed)

Simplify ideal generators in function field code

Reported by: gh-BrentBaccala Owned by:
Priority: minor Milestone: sage-8.8
Component: algebra Keywords: function fields
Cc: Merged in:
Authors: Brent Baccala Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 4092260 (Commits) Commit: 409226089efce2d4e86148fbb06cdd1668e15717
Dependencies: Stopgaps:

Description

Ideals of orders are often presented using more generators than needed. For example, this snippet is taken directly from a test case in sage/src/function_fields/ideal.py:

sage: K.<x> = FunctionField(QQ); R.<y> = K[]                                                                          
sage: L.<y> = K.extension(y^2 - x^3 - 1)                                                                              
sage: O = L.equation_order()                                                                                          
sage: O.ideal(x^2 + 1)                                                                                                
Ideal (x^2 + 1, (x^2 + 1)*y) of Order in Function field in y defined by y^2 - x^3 - 1                                 

The presentation is obviously non-optimal, since the ideal was created with a single generator, but printed with two!

Change History (6)

comment:1 Changed 18 months ago by gh-BrentBaccala

  • Authors set to Brent Baccala
  • Branch set to public/27657
  • Commit set to bb8a7634a43794ba53386d62ce86a904bad29dbe
  • Status changed from new to needs_review

This ticket is a lot harder than I had realized. Implementing an algorithm to test these ideals for principality is not trivial. The proposed code is an improvement, but doesn't always find a single generator for a principal ideal. At least it finds them in some cases, like the one in the ticket description:

sage: K.<x> = FunctionField(QQ); R.<y> = K[]
sage: L.<y> = K.extension(y^2 - x^3 - 1)
sage: O = L.equation_order()
sage: O.ideal(x^2 + 1)
Ideal (x^2 + 1) of Order in Function field in y defined by y^2 - x^3 - 1

Last 10 new commits:

d509372Trac #27657: simplify reduced generators by remove extraneous ones
2b875aaTrac #27657: check all powersets of ideal generators to find minimal set
278a947Trac #27657: document algorithm used in FunctionFieldIdealGlobal's gens_two()
3557949Trac #27657: doctest changes consisting solely of removing extraneous generators
5a567a6Trac #27657: doctest updates that are simpler in the sense that they're principal
dc3aff7Trac #27657: doctest updates that are obvious simplifications of the old ones
f1934bdTrac #27657: doctest update that is solely adding extra spaces
76c5824Trac #27657: doctest changes that swapped one generator for another
a931c80Trac #27657: doctest update that just changes order of generators
bb8a763Trac #27657: two doctests whose outputs are more complicated with the new code

comment:2 Changed 18 months ago by tscrim

A few little tweaks:

-        ALGORITHM::
+        ALGORITHM:
 
-            At most two generators are required to generate ideals
-            in Dedekind domains.
+        At most two generators are required to generate ideals in
+        Dedekind domains.
 
-            Lemma 4.7.9, algorithm 4.7.10, and exercise 4.29 of [Coh1993]_
-            tell us that for an integral ideal $I$ in a number field,
-            if we pick $a$ such that $\gcd(N(I), N(a)/N(I)) = 1$, then
-            $a$ and $N(I)$ generate the ideal.  $N()$ is the norm, and
-            this result (presumably) generalizes to function fields.
+        Lemma 4.7.9, Algorithm 4.7.10, and Exercise 4.29 of [Coh1993]_
+        tell us that for an integral ideal `I` in a number field, if
+        we pick `a` such that `\gcd(N(I), N(a)/N(I)) = 1`, then `a`
+        and `N(I)` generate the ideal.  `N()` is the norm, and this
+        result (presumably) generalizes to function fields.
 
-            After computing $N(I)$, we search exhaustively to find $a$.
+        After computing `N(I)`, we search exhaustively to find `a`.

As ALGORITHM is not a standard Sphinx directive (cf. .. TODO::), so it should not be indented. Also, we prefer backticks over dollar signs.

Once this is done, you can set a positive review on my behalf.

comment:3 Changed 18 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

comment:4 Changed 18 months ago by git

  • Commit changed from bb8a7634a43794ba53386d62ce86a904bad29dbe to 409226089efce2d4e86148fbb06cdd1668e15717

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

0ddeeedMerge tag '8.8.beta5' into public/27657
4092260Trac #27657: use standard formatting in ALGORITHM block

comment:5 Changed 18 months ago by gh-BrentBaccala

  • Status changed from needs_review to positive_review

comment:6 Changed 17 months ago by vbraun

  • Branch changed from public/27657 to 409226089efce2d4e86148fbb06cdd1668e15717
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.