Concept icon
Concept

Why retained incidence monomials have only linearly many selected coordinates

Let a<=cn be the remaining tests, each of degree at most k, and ell=n+1. In test i the V^j coefficient has incidence degree at most k(1+2j); replacing positive powers by first powers cannot increase degree. Test incidence names are disjoint, so their product is multilinear in all incidence coordinates. Shared truncation keeps only sum_i j_i<=ell-1. Therefore every surviving incidence monomial uses at most K=k(a+2(ell-1))=O_(k,c)(n) distinct coordinates. It may use two different copies of the same original variable; those are distinct incidences until the final Boolean substitution.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math