An affine shift reveals a harder accepting point
On this page · Permalink · Source line 292
For \(k\ge2\), let \(B=z_1\cdots z_k\) and \(F_k=ab\ \mathrm{OR}\ B\) on \(n=k+2\) inputs. Add the affine mask \(a\) to obtain \(G_k=F_k+a\). On the face \(b=1\),
This is a singleton indicator on the \(k+1\) variables \((a,z)\). At \(v=(a=0,b=1,z=1^k)\), every safe detecting polynomial must restrict to that singleton indicator, so its degree is at least \(k+1\).
The general two-positive indicator construction gives the matching upper bound \(\beta(G_k)\le n-1=k+1\). The maintained family proves
The gap between one-packet and complete degree therefore grows with \(k\).
| \(k\) | \(n\) | \(\beta^*\) | complete bound \(2k-1\) | combined degree/one-packet bound |
|---|---|---|---|---|
| 2 | 4 | 3 | 3 | 3 |
| 3 | 5 | 4 | 5 | 4 |
| 4 | 6 | 5 | 7 | 5 |
| 6 | 8 | 7 | 11 | 7 |
For \(k=3\), all 64 affine masks were freshly checked and the optimized parameters are exactly \((3,4)\). The all-size family proof is not inferred from those 64 cases. Its restored construction has \(T\le2n-3\), so this remains a linear-size easy family. The exact optimum between the lower and upper constructions is not asserted when they differ.