Opened 3 years ago

Closed 3 years ago

## #27657 closed enhancement (fixed)

# Simplify ideal generators in function field code

Reported by: | Brent Baccala | 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 3 years ago by

Authors: | → Brent Baccala |
---|---|

Branch: | → public/27657 |

Commit: | → bb8a7634a43794ba53386d62ce86a904bad29dbe |

Status: | new → needs_review |

### comment:2 Changed 3 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 3 years ago by

Reviewers: | → Travis Scrimshaw |
---|

### comment:4 Changed 3 years ago by

Commit: | bb8a7634a43794ba53386d62ce86a904bad29dbe → 409226089efce2d4e86148fbb06cdd1668e15717 |
---|

### comment:5 Changed 3 years ago by

Status: | needs_review → positive_review |
---|

### comment:6 Changed 3 years ago by

Branch: | public/27657 → 409226089efce2d4e86148fbb06cdd1668e15717 |
---|---|

Resolution: | → fixed |

Status: | positive_review → 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`