Complete safe-packet degree
On this page · Permalink · Source line 129
CLAIM C02
15.1 Pointwise coverage rather than one easy packet
On this page · Permalink · Source line 131
Let
This is the ideal of functions supported only on the accepting set of \(f\). For nonzero \(f\), the one-packet parameter is
It asks for one safe nonzero polynomial, which may detect only an easy portion of the accepting set. One-sided polynomial immunity is established terminology in this setting; see the background reference [54].
For a positive input \(v\), define instead
Set \(\beta(0)=0\). Thus \(\beta(f)\) is the degree needed before safe polynomials collectively detect every positive input. Finally, put
where \({\operatorname{Aff}}_n\) is the set of affine Boolean functions on the logical inputs.
Proposition 15.1: Basic size bounds
For nonzero \(f\) on \(n\) inputs,
If \(f\) has at least two positive inputs, then \(\beta(f)\le n-1\). In particular \(\beta^*(f)\le n\).
Proof
Any polynomial detecting a specified positive input is nonzero, giving the first inequality. For \(v\in{\{0,1\}}^n\), its point indicator is
If \(f(v)=1\), then \(\delta_v\in I_f\) and has degree \(n\), proving the upper bound.
If \(v\) and \(w\) are distinct positive inputs, \(\delta_v+\delta_w\) is safe and equals one at \(v\). The degree-\(n\) coefficients of its two summands are both one, so they cancel. Its degree is at most \(n-1\). Do this for each positive \(v\). The last assertion applies the general bound to every affine adjustment, with the stated zero convention.
Proposition 15.2: Affine input invariance
Invertible affine changes of logical input coordinates preserve \(\alpha_1\), \(\beta\), and \(\beta^*\), with the pointwise parameters transported by the corresponding bijection of inputs.
Proof
Composition with an affine map cannot increase multilinear degree. Composition with its affine inverse proves equality of degrees. Such composition bijects the accepting and rejecting inputs, hence maps safe polynomials bijectively to safe polynomials and preserves their pointwise detecting property. It also permutes the affine output masks used in the definition of \(\beta^*\).