NaiveDedupGeobucket retains opposite leading terms in its returned polynomial
Nobody has claimed this yet.
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
The noncommutative deduplicating polynomial heap returns both copies of a leading word whose coefficients should cancel. The equivalent test passes with HeapType::Trivial and HeapType::NaiveGeobucket.
Reproduction
Add this case to M2/Macaulay2/e/unit-tests/NCGroebnerTest.cpp, which already includes the required engine and test headers:
TEST(NCReduction, deduplicatingHeapCancellation)
{
FreeAlgebra* A = FreeAlgebra::create(
globalQQ, {"x", "y", "z"}, degreeRing(1), {1, 1, 1}, {}, {1});
ASSERT_NE(A, nullptr);
FreeAlgebraElement x(A), y(A), z(A);
A->var(*x, 0);
A->var(*y, 1);
A->var(*z, 2);
auto heap = makePolynomialHeap(HeapType::NaiveDedupGeobucket, *A);
auto f = y*z*x*z - y*z*y*y - y*z*z*x - z*x*y*z + z*x*z*y
- z*y*y*y - z*z*x*y - z*z*y*x - z*z*z*z;
auto g = -y*z*x*z - y*z*y*y - y*z*z*x;
const auto expected = -y*z*y*y - y*z*y*y - y*z*z*x - y*z*z*x
- z*x*y*z + z*x*z*y - z*y*y*y
- z*z*x*y - z*z*y*x - z*z*z*z;
heap->addPolynomial(*f);
heap->addPolynomial(*g);
EXPECT_EQ(expected, FreeAlgebraElement(A, *heap->value()));
}
Run M2-unit-tests --gtest_also_run_disabled_tests --gtest_filter='NCReduction.*deduplicatingHeapCancellation'. The wildcard also selects the regression after it receives the DISABLED_ prefix.
Expected canonical polynomial:
-2yzy^2-2yz^2x-zxyz+zxzy-zy^3-z^2xy-z^2yx-z^4
Actual:
yzxz-yzxz-2yzy^2-2yz^2x-zxyz+zxzy-zy^3-z^2xy-z^2yx-z^4
Although the two expressions are mathematically equal after cancellation, the returned representation retains the opposite yzxz terms and fails the engine's polynomial equality check. The returned polynomial should have the same canonical form as the other heap implementations.
Verification
Reproduced with CMake Debug and Autotools on Apple Silicon/macOS, using the engine at abbcf9b3b35df37fb6aa33fd5c05e9928ab9281a on the retroactive branch, with the test-only working-tree changes being prepared for MichaelABurr/M2#82. No production fix is included. The same failure occurs in the shuffled run with seed 915 and the coverage build.
Searched open and closed issues for NaiveDedupGeobucket and geobucket; the matches concerned other components or changes, not this cancellation failure.
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
Add the reproduction to M2/Macaulay2/e/unit-tests/NCGroebnerTest.cpp and run the provided M2-unit-tests filter to confirm the failure. Locate the NaiveDedupGeobucket implementation through HeapType::NaiveDedupGeobucket, compare its behavior with the passing heap implementations, and verify that the returned polynomial matches the stated canonical form.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend, testing-qa
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 66/100