Gap Amplification and Assignment Testing: Examples and Counterexamples

The first inequality of [F1] with $S=10$ gives $U_{\mathrm{i}\mathrm{n}\mathrm{t}}\ge (7\mathrm{/}20)\cdot 10=7\mathrm{/}2$, and the labelling has $U_{\mathrm{i}\mathrm{n}\mathrm{t}}=4$, so the bound holds and its slack is $4-7\mathrm{/}2=1\mathrm{/}2$.

The second inequality of [F1] with $U_{\mathrm{e}\mathrm{x}\mathrm{t}}=2$ and $S=10$ gives $U_G\le 2+10=12$.

Both bounds are one-sided and the integers $U_{\mathrm{i}\mathrm{n}\mathrm{t}}=4$ and $U_G\in \{0,\dots ,12\}$ are compatible with them, so the numerical data are consistent; the example shows in particular that $S=10$ ports of disagreement force at least $7\mathrm{/}2$ (hence at least $4$ integer) internal violations and at most $12$ ordinary edge violations in $G$, and nothing of the stronger form $U_G\le U_{\mathrm{e}\mathrm{x}\mathrm{t}}$ or $U_{\mathrm{i}\mathrm{n}\mathrm{t}}\ge S$ may be inferred from these bounds.

The comparison with the registered graph is a constant rescaling and not a count identity: by [F2] the fraction of violated edges of $G_2$ is at least $\frac{7}{7740}$ times the fraction of violated ordinary edges of $G$, and the tautological overlay edges at the ports do not contribute violations in either direction, so the counts $U_{\mathrm{i}\mathrm{n}\mathrm{t}}$, $U_{\mathrm{e}\mathrm{x}\mathrm{t}}$ and $U_G$ above are statements about the cloud graph $G_1$ and the original graph $G$.

The first loop carries $R_1$, and $(0,0),(1,1)\in R_1$, so every labeling of $x_1$ satisfies it; the second loop carries $R_2=\mathrm{\varnothing }$, so no labeling satisfies it. Hence the two-constraint list $G$ has ${\mathrm{UNSAT}}_{\sigma }(G)=1\mathrm{/}2$ for every labeling $\sigma$, and therefore $\mathrm{UNSAT}(G)=1\mathrm{/}2$.

For $r\ge 1$ let $G^{(r)}$ list each of the two loops $r$ times. Every labeling satisfies exactly the $r$ copies of the first loop and violates exactly the $r$ copies of the second, so ${\mathrm{UNSAT}}_{\sigma }(G^{(r)})=r\mathrm{/}(2r)=1\mathrm{/}2$ for every $\sigma$, and the list has $2r$ constraints.

Thus $\mathrm{UNSAT}(G^{(r)})=1\mathrm{/}2=\mathrm{UNSAT}(G)$ for every $r\ge 1$: the repetition changes neither the value nor the unsatisfaction fraction, and in particular it never strictly increases it, so the statement refuted above fails at this witness.

The eight patterns contribute one claim each, so the claim counts for $v$ are $5$ for $a$, $2$ for $b$ and $1$ for $c$; dividing by the number $8$ of patterns gives $p_v(a)=5\mathrm{/}8$, $p_v(b)=2\mathrm{/}8$ and $p_v(c)=1\mathrm{/}8$, which sum to $1$.

Since $5\mathrm{/}8>2\mathrm{/}8>1\mathrm{/}8$, the maximum of $p_v$ is attained only by $a$, so [F1] gives $\widehat{\phi }(v)=a$ without any use of the tie-breaking rule; the frequency of the decoded label at $v$ is $p_v(a)=5\mathrm{/}8$.

The example illustrates the two conventions that the decoding uses: patterns are counted with multiplicity rather than as distinct centres, so two patterns ending at the same centre contribute their claims twice, and the tie-breaking order matters only when the maximum of $p_v$ is attained by several symbols, which does not happen here.