Macaulay2 / Macaulay2/M2

gcd ignores the coefficient ring's minimal polynomial, returning only the base-field part

Open
#4,583 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bugs directory Core
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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.