claimroutine

Branch on high-incidence variables

Claim·§5.5 Constructing the forms and completing the proof·inside thmCounting zeros of sparse polynomials faster

Statement (paper)

Let M=∑f∈F∣If∣M=\sum_{f\in\mathcal F}|I_f|, λ=⌈log⁡2n⌉\lambda=\lceil\log_2 n\rceil and b0=⌈M/n⌉⌈λ⌉b_0=\lceil M/n\rceil\lceil\sqrt\lambda\rceil, and let S⊆[n]S\subseteq[n] be the set of variables belonging to more than b0b_0 scopes. Then ∣S∣⩽n/λ|S|\le n/\sqrt\lambda, so there are at most 2n/λ2^{n/\sqrt\lambda} branches x∣S=bx|_S=b with b∈{0,1}Sb\in\{0,1\}^S; each branch has the same number n′⩾n−n/λ⩾n/2n'\ge n-n/\sqrt\lambda\ge n/2 of free variables, after substituting the fixed bits neither the degree nor the number of monomials of any PiP_i increases, and N(P)N(\mathcal P) is the sum of the common-zero counts of the branches.

In plain English

Let SS be the set of variables appearing in more than b0=⌈M/n⌉⌈λ⌉b_0=\lceil M/n\rceil\lceil\sqrt\lambda\rceil scopes, where M=∑f∈F∣If∣M=\sum_{f\in\mathcal F}|I_f| and λ=⌈log⁡2n⌉\lambda=\lceil\log_2 n\rceil. Then ∣S∣⩽n/λ|S|\le n/\sqrt\lambda, so fixing x∣S=bx|_S=b gives at most 2n/λ2^{n/\sqrt\lambda} branches, each with n′⩾n/2n'\ge n/2 free variables and no increase in degree or monomial count, and the total count N(P)N(\mathcal P) is the sum of the branch counts.

Why it's here

This step removes the variables that occur in too many scopes, at the price of at most 2n/λ2^{n/\sqrt\lambda} branches, which fits within the target running time. Each branch then has bounded variable incidence, which the per-branch design needs. Because the branch counts add up to N(P)N(\mathcal P) and the branches can be processed one after another, the result also supports the polynomial-space bound.
Classified routine:
A Markov-type averaging bound (at most M/b_0 \le n/\sqrt\lambda variables can have incidence above b_0) combined with standard branching on those variables, as in sparsification and other exponential-time algorithms; substituting constants cannot raise degree or monomial count, and the zero counts of the branches add up to the total.

Uses

Nothing else in the paper

Used by

claimPer-branch parameters satisfy layout hypothesesclaimPolynomial space by sequential branches

Sources

PaperOpen
Section
§5.5 Constructing the forms and completing the proof
Page
—
Label
—
Line
main_full_version.tex:3097
Leannot aligned

Phase 2 aligns this node to a Lean declaration.