DensePolynomial::mul_by_vanishing_poly ignores coset offset

[Kuhai9801]

Summary

DensePolynomial::mul_by_vanishing_poly(domain) appears to always compute multiplication by the subgroup vanishing polynomial:

x^n - 1

That is correct for ordinary subgroup domains. However, EvaluationDomain also supports coset domains via get_coset, and for a coset domain the vanishing polynomial is:

x^n - offset^n

where offset^n is available as domain.coset_offset_pow_size().

As a result, passing a coset domain to mul_by_vanishing_poly returns p(x) * (x^n - 1) instead of p(x) * (x^n - offset^n).

Difference from #902

Related to #902, but separate: #902 discusses divide_by_vanishing_poly, while this report is about mul_by_vanishing_poly and the repro below does not exercise division.

References

• DensePolynomial::mul_by_vanishing_poly: this is the affected helper. It builds x^n * p(x) and then subtracts p(x) coefficient-wise, which implements p(x) * (x^n - 1).
• EvaluationDomain::get_coset: this is the trait method used to construct the coset domain passed into the helper.
• EvaluationDomain::coset_offset_pow_size: this is the trait method exposing the offset^n value that distinguishes a coset vanishing polynomial from x^n - 1.
• EvaluationDomain::vanishing_polynomial: the trait's own vanishing-polynomial helper uses -coset_offset_pow_size() as the degree-0 coefficient, i.e. it returns x^size - offset^size.
• GeneralEvaluationDomain::get_coset: this forwards coset construction to the concrete domain, so the repro uses the public general-domain API while still exercising a real coset domain.

Affected Code

The current helper builds x^n * p(x) and then subtracts p(x) coefficient-wise:

pub fn mul_by_vanishing_poly<D: EvaluationDomain<F>>(&self, domain: D) -> Self {
    let mut shifted = vec![F::zero(); domain.size()];
    shifted.extend_from_slice(&self.coeffs);
    cfg_iter_mut!(shifted)
        .zip(&self.coeffs)
        .for_each(|(s, c)| *s -= c);
    Self::from_coefficients_vec(shifted)
}

For p(x) = a + bx and domain.size() = n, this builds:

[-a, -b, 0, ..., 0, a, b]

which is p(x) * (x^n - 1).

For a coset domain, the low coefficients should instead be scaled by offset^n:

[-offset^n * a, -offset^n * b, 0, ..., 0, a, b]

Minimal Reproduction

This patch adds a standalone integration test. It compares the helper output against both coefficient formulas directly, without relying on another polynomial multiplication implementation to define the expected value.

diff --git a/poly/tests/coset_vanishing_mul.rs b/poly/tests/coset_vanishing_mul.rs
new file mode 100644
index 000000000..000000000
--- /dev/null
+++ b/poly/tests/coset_vanishing_mul.rs
@@ -0,0 +1,50 @@
+use ark_ff::{One, Zero};
+use ark_poly::{
+    univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, GeneralEvaluationDomain,
+};
+
+#[test]
+fn mul_by_vanishing_poly_matches_coset_vanishing_polynomial() {
+    use ark_test_curves::bls12_381::Fr;
+
+    let domain = GeneralEvaluationDomain::<Fr>::new(8).unwrap();
+    let coset = domain.get_coset(Fr::from(5u64)).unwrap();
+    let offset_pow_size = coset.coset_offset_pow_size();
+    assert_ne!(offset_pow_size, Fr::one());
+
+    let a = Fr::from(3u64);
+    let b = Fr::from(7u64);
+    let p = DensePolynomial::from_coefficients_vec(vec![a, b]);
+
+    let actual = p.mul_by_vanishing_poly(coset);
+
+    // p(x) * (x^8 - 1)
+    let subgroup_formula = DensePolynomial::from_coefficients_vec(vec![
+        -a,
+        -b,
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        a,
+        b,
+    ]);
+
+    // p(x) * (x^8 - offset^8)
+    let coset_formula = DensePolynomial::from_coefficients_vec(vec![
+        -(offset_pow_size * a),
+        -(offset_pow_size * b),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        Fr::zero(),
+        a,
+        b,
+    ]);
+
+    assert_ne!(subgroup_formula, coset_formula);
+    assert_eq!(actual, coset_formula);
+}

Run:

cargo test -p ark-poly --features std --test coset_vanishing_mul -- --nocapture

Observed Behavior

The expected-behavior test currently fails because actual is the subgroup formula rather than the coset formula:

thread 'mul_by_vanishing_poly_matches_coset_vanishing_polynomial' panicked at poly/tests/coset_vanishing_mul.rs:48:5:
assertion `left == right` failed

The failure shows that the helper output matches p(x) * (x^8 - 1) even though the supplied domain is a coset and coset.coset_offset_pow_size() != 1.

Expected Behavior

I would expect mul_by_vanishing_poly(domain) to multiply by domain.vanishing_polynomial() for the provided domain.

Equivalently, for coset domains it should compute:

x^n * p(x) - domain.coset_offset_pow_size() * p(x)

If mul_by_vanishing_poly is intended to support only subgroup domains, then the method documentation may need to state that precondition, because the current signature accepts any D: EvaluationDomain<F>.

Possible Fix Direction

One possible implementation direction is to use domain.coset_offset_pow_size() when subtracting the low coefficients:

let offset_pow_size = domain.coset_offset_pow_size();
cfg_iter_mut!(shifted)
    .zip(&self.coeffs)
    .for_each(|(s, c)| *s -= offset_pow_size * *c);

For subgroup domains this preserves current behavior because coset_offset_pow_size() == F::one().

A regression test should cover a coset domain where coset_offset_pow_size() != F::one(). A useful assertion would be that the helper matches either domain.vanishing_polynomial() or the direct coefficient formula above.

[Kuhai9801]

Hi, I can also work on this if the fix direction sounds right.

I’d update mul_by_vanishing_poly to use domain.coset_offset_pow_size() when subtracting the low coefficients, preserving subgroup behavior while making coset domains multiply by x^n - offset^n.

I’d also add a focused regression test for a coset domain where coset_offset_pow_size() != 1.