gcd ignores the coefficient ring's minimal polynomial, returning only the base-field part
Nobody has claimed this yet.
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
This issue was triaged from [`bugs/dan/1-gcd-over-separable-extensions`](https://github.com/Macaulay2/M2/blob/388c1ff0ce30d83751dea7bc7eac77fdc1305dd7/bugs/dan/1-gcd-over-separable-extensions), one of the 857 files removed from the pre-GitHub `bugs/` tree by [`d2c8d27826`](https://github.com/Macaulay2/M2/commit/d2c8d27826) and catalogued in [#36](https://github.com/Macaulay2/M2/issues/36). **The commentary below was written by Claude (Claude Opus 5, via Claude Code)**, not by @d-torrance, whose account posted it -- please weigh it accordingly.
### The original file, verbatim
```text
Implement gcd over separable extensions of fields. The idea would be that
every scalar, is, up to a unit, an idempotent.
```
### Where it stands today
Unmet — and rather than declining, `gcd` returns a common divisor that is **not greatest**.
### The counterexample
Over `QQ[a]/(a^2-1)`, which is `QQ × QQ`, with `e = (1+a)/2` and `f = (1-a)/2` verified idempotent and
orthogonal:
```m2
F = e*(x-1) + f*(x-2)
G = e*(x-1) + f*(x-3)
d = e*(x-1) + f -- degree 1, divides both F and G
gcd(F, G) -- 1
```
A first attempt of mine, `(x^2-1)*(x-a)` against `(x^2-1)*(x+a)`, gave the right answer and was a
**coincidence** — both components share a gcd there. The idempotent construction is what makes the
components disagree.
### Cause, and the capability already exists
`gcd` calls the two-argument `rawGCD` (`factor.m2:26-28`) with no minimal polynomial, so an extension in
the coefficient ring is invisible and only the base-field part comes back. Over
`K = QQ[a]/(a^6-a^3-1)` with `R = K[t]`, `F = t^6-t^3-1`, `G = (t-a)*(t+a)`:
- the front end says `1`,
- `rawGCD(raw F, raw G, raw (ideal K)_0)` returns `t-a`.
That is Mike's 2009 diagnosis verbatim, from `bugs/mike/0-gcd-doc.m2` line 3: *"rawGCDRingElement is not
being called from the front end"*.
### The guard that was supposed to prevent this only checks the top ring
Dan's proposal in **#321** — *"just give an error if the ring is a quotient ring"* — exists at
`factor.m2:24`, but tests only the top ring. So `gcd` errors in `QQ[a]/(a^2-1)` and **proceeds** in
`(QQ[a]/(a^2-1))[x]`; likewise for pzinn's `ZZ[y]/(y^2+3)` example. This is the third guard-depth defect
of this cohort, after #4576 and #4578.
### Deliberately left separate
`bugs/mike/0-gcd-doc.m2` is a 120-line multi-ask file covering `factor` over `toField` ("NOT
CORRECT!!"), bivariate gcd and missing documentation, so it needs reading *against* this issue rather
than closing as its duplicate. **#1958** is the units-in-a-field case Mike called expected.
`open` · disposition `issue` · source of truth: [`bug-triage/catalog.tsv`](https://github.com/d-torrance/M2/blob/bug-triage/bug-triage/catalog.tsv)
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with factor.m2 lines 24-28 and trace how gcd invokes the two-argument rawGCD. Compare that path with rawGCD on the minimal polynomial, using the QQ[a]/(a^6-a^3-1) example and the nested quotient guard described here. Done means gcd no longer returns only the base-field part for the supplied counterexamples and handles quotient coefficient rings consistently.
Written by the indexing model from the issue text.
Assessment
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100