Why the auxiliary dimension bounds each integer measurement
Each auxiliary measurement row has D entries in {-1,0,1}, so its absolute coefficient sum is at most D. Fill one auxiliary copy with original bits: when an original variable appears several times, add its coefficients. The triangle inequality shows that this cannot increase the absolute sum. Discarding unused coordinates and splitting the row among disjoint original groups cannot increase it either. Every resulting row is integral and has absolute sum at most D. On Boolean inputs its value is therefore an integer between -D and D, with at most 2D+1 possibilities. Different copies produce separate rows, not one row that adds every copy together. This establishes the counting routine's range bound B=D.
0
1
Tags
Math