Opened 2 years ago
Closed 2 years ago
#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, GitHub, GitLab) | 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 2 years ago by
- Branch set to public/27657
- Commit set to bb8a7634a43794ba53386d62ce86a904bad29dbe
- Status changed from new to needs_review
comment:2 Changed 2 years ago by
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 2 years ago by
- Reviewers set to Travis Scrimshaw
comment:4 Changed 2 years ago by
- Commit changed from bb8a7634a43794ba53386d62ce86a904bad29dbe to 409226089efce2d4e86148fbb06cdd1668e15717
comment:5 Changed 2 years ago by
- Status changed from needs_review to positive_review
comment:6 Changed 2 years ago by
- 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.
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:
Last 10 new commits:
Trac #27657: simplify reduced generators by remove extraneous ones
Trac #27657: check all powersets of ideal generators to find minimal set
Trac #27657: document algorithm used in FunctionFieldIdealGlobal's gens_two()
Trac #27657: doctest changes consisting solely of removing extraneous generators
Trac #27657: doctest updates that are simpler in the sense that they're principal
Trac #27657: doctest updates that are obvious simplifications of the old ones
Trac #27657: doctest update that is solely adding extra spaces
Trac #27657: doctest changes that swapped one generator for another
Trac #27657: doctest update that just changes order of generators
Trac #27657: two doctests whose outputs are more complicated with the new code