Concept icon
Concept

The linear degree budget for the whole lifted system

Suppose m equation lifts each have degree at most k. A retained term has degree at most sum_i k(1+2j_i), because e_j has degree at most one and h has degree two. Since sum_i j_i<ell, every retained V-coefficient has degree at most d=k(m+2(ell-1)). This remains true when different factors receive separate inputs; occurrences of one variable WITHIN a factor use the same replacement. With m=O(n) and ell=n+1, d=O(k n). In contrast, multiplying untruncated indicators gives a bound k m(2ell-1), quadratic in n for fixed k. Truncation preserves a low total degree without expanding every monomial.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math