kernel(RingMap) cannot use a Hilbert function hint unless the map preserves degrees

@d-torrance

Written by Claude (Claude Opus 5, via Claude Code), not by @d-torrance, whose account posted it -- please weigh it accordingly.

This is bugs/dan/1-kernel-ringmap, one of the 857 files removed from the pre-GitHub bugs/ tree by d2c8d27826 and catalogued in #36.

The original file, verbatim

fix kernel(RingMap):

From: Michael Stillman <mike@math.cornell.edu>
To: dan@math.uiuc.edu
In-Reply-To: <200804101301.m3AD1Iot006150@u123.math.uiuc.edu>
Subject: Re: another interesting example
Date: Thu, 10 Apr 2008 09:48:24 -0400

...

The other strategy that might be good is this:  To compute the kernel  
of a ringmap R/J <--- S, given by f1,...,fr, in the case when J,  
f1, ..., fr are not homogeneous, do the following:
  a. homogenize a GB of J, and f1, ..., fr, and create the ideal(Jh,  
f1h-y1, ..., frh-yr).  Compute the HF of Jh, and then set the HF hint  
of this new ideal to: (poincare Jh) * product(1..r, i -> (1- 
t^(deg(fih)))).  After doing the computation, dehomogenize, and do  
'forceGB' on the answer.

...

What the file is about

kernel f for a ring map is computed by forming the graph ideal of f and taking a Gröbner basis of
it, which is the expensive step. Knowing the ideal's Hilbert function in advance lets that computation
be given a hint and go much faster — but the hint is only usable when the ideal is homogeneous. This
file is Mike Stillman's 2008 recipe for the case where it is not: homogenize a Gröbner basis of J
and the f_i, build the hint from the homogenized pieces, then dehomogenize and forceGB the result.

Mike's 2008 recipe has three ingredients, and they have landed unevenly.

The Hilbert-function hint: implemented, for degree-preserving maps

ringmap.m2:320-332 sets poincare cokernel graph to poincare module target f times
product(degrees source graph, d -> 1 - T_d), and asserts at :332 that gb used it. Verified live
with R = QQ[a,b,c,d, Degrees => {4,4,4,4}] mapping to QQ[s,t] by {s^4, s^3*t, s*t^3, t^4}:
isHomogeneous graph is true, canUseHilbertHint is true, and gb records the
rawGBSetHilbertFunction log key.

The inhomogeneous case — the one the email was written for — is unmet

canUseHilbertHint requires isHomogeneous m (gb.m2:271). With standard degrees the graph ideal is
inhomogeneous, because a - s^4 mixes degrees in QQ[p_0..p_5], so the block is skipped and there is no
homogenize/dehomogenize path. That is precisely Mike's recipe: homogenize a GB of J and the f_i,
form (Jh, f1h - y1, …), set the hint to (poincare Jh) * product(1 - t^deg(fih)), then dehomogenize.

The recipe's last step is tracked elsewhere

forceGB appears 0 times in ringmap.m2, and #686 asks for exactly it, quoting the same
reasoning.

Live code

PR #4485 (open) is adding another strategy to the same hook table, for skew-commutative targets via a
new centerRing — so ringmap.m2's strategy block is being edited right now.

_{open · disposition issue · source of truth: bug-triage/catalog.tsv}

Triage twelve more rows, filing Macaulay2#4589 and Macaulay2#4590

README: three lessons from the batch that produced Macaulay2#4589 and M…

@d-torrance

Written by Claude (Claude Opus 5, via Claude Code), not by @d-torrance, whose account posted it -- please weigh it accordingly.

Provenance for the guard this issue names, which turns out to be a scoped decision rather than an
oversight.

canUseHilbertHint was introduced by #3942 (merged 2026-06-04), the PR that fixed the crash in
#1935 and #3937 — before it, a wrong Hilbert hint aborted the process rather than raising an error.
That PR's description records the scope it chose:

A function canUseHilbertHint has been added, documented, which allows one (and the GB code) to
decide if in a given situation, the Hilbert hint is usable.

The abort when discovering a bad Hilbert function is removed. Instead, an exception is issued.

Note: multi-graded rings will not use any Hilbert hint. If desired, we can likely add this, but
it will take some effort and time.

So the predicate has two deliberate restrictions, and its author already priced extending one of
them. This issue is about the other: canUseHilbertHint Matrix additionally requires
isHomogeneous m, which is what excludes the inhomogeneous case Mike's 2008 recipe was written for.
Worth knowing before anyone treats it as a missing check to be relaxed casually — the safety it
provides is what stopped the crash in #1935.

_{From bugs/dan/1-kernel-ringmap in the pre-GitHub bugs/ tree, being triaged in #36. Source of truth: bug-triage/catalog.tsv.}

Comment PR provenance onto four already-filed issues

Triage ReesAlgebra2 through det-bug-from-ggsmith; one issue, one dupl…

@d-torrance

Written by Claude (Claude Opus 5, via Claude Code), not by @d-torrance, whose account posted it -- please weigh it accordingly.

A second file from the same directory gives the inhomogeneous case a price, which this issue currently
argues for from the source alone.

bugs/mike/bench-implicit.m2, also removed with bugs/ in d2c8d27 (#36), is an implicitization
benchmark whose map is exactly the shape described above — degree-1 source variables, quadric images, so
nothing in sight is homogeneous:

n = 5
R = ZZ/32003[vars(0..n-1)]
S = ZZ/32003[vars(26..26+n)]
phi = map(R,S,random(R^1,R^{(numgens S):-2}))
gbTrace=3
ker phi;

The only change worth making to it is to regrade S so that the map becomes graded. That leaves ker phi
the same set of polynomials — the grading of S has no bearing on which polynomials go to zero — and alters
only whether the algorithm can see it as homogeneous:

	`isHomogeneous phi`	graph ideal homogeneous	`canUseHilbertHint`	`ker phi`
`S = ZZ/32003[vars(26..31)]`	false	false	false	no result in 600 s
`S = ZZ/32003[vars(26..31), Degrees => {6:2}]`	true	true	true	196 s

canUseHilbertHint is the predicate at gb.m2:271 named above, and the fast row is the one where it
returns true. The 196-second answer is a single generator, degree 32 in the regraded ring, so the degree-16
implicit equation of the image hypersurface. Reproduced on 1.26.06-40-gd8e86d689d with setRandomSeed 42.

What this does and does not bound

It does not measure what implementing the homogenize/dehomogenize path would buy. Regrading buys
homogeneity in general, and a graded Gröbner basis gains degree-by-degree progress and early termination
quite apart from any Hilbert hint. So 196 s against 600 s is a ceiling on the prize, not an estimate of it.

The 600 s is a lower bound, since that run was killed rather than finishing.

Read narrowly, then: on a five-line example in six variables, the gap between having the hint machinery
available and not having it is at least a factor of three and possibly unbounded, on a computation that is
otherwise small. That seemed worth recording next to the code reading, since an issue with no numbers on it
is easy to file under "would be nice".

One incidental warning for anyone re-running the file: vars(26..31) is A..F, so a matrix held in a
variable named F is silently clobbered the moment S is created. The original avoids this only by
inlining the matrix into the map call, and it cost me two confusing runs.

_{From bugs/mike/bench-implicit.m2 in the pre-GitHub bugs/ tree, being triaged in #36. Source of truth: bug-triage/catalog.tsv.}

Comment the ker phi timing pair onto Macaulay2#4590, and fix how the …

Batch 87: 10 issues triaged, and a refusal that never attempts the th…

Drop the twelve leftover `feature request` labels

Navigation Menu

Repository navigation

kernel(RingMap) cannot use a Hilbert function hint unless the map preserves degrees #4590

The original file, verbatim

What the file is about

The Hilbert-function hint: implemented, for degree-preserving maps

The inhomogeneous case — the one the email was written for — is unmet

The recipe's last step is tracked elsewhere

Live code

What this does and does not bound

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

kernel(RingMap) cannot use a Hilbert function hint unless the map preserves degrees #4590

Description

The original file, verbatim

What the file is about

The Hilbert-function hint: implemented, for degree-preserving maps

The inhomogeneous case — the one the email was written for — is unmet

The recipe's last step is tracked elsewhere

Live code

Activity

d-torrance commented on Aug 7, 2026

d-torrance commented on Aug 13, 2026

What this does and does not bound

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions