Manuscript En02-A@1 · En02-A-v1.tex · theorem · bb1319d5

Theorem: H: exact certificate cost

Exact fine-graining certificate cost and cheaper symmetry › Primitive multiplicities and the certificate family · lines 1014–1048 · proof included or linked

En02-A@1#thm:H, En02-A@1#eq:fgcost

Back to manuscript

For primitive multiplicities,

C_{FG} (s, m) = s + ⌈ lo g_{2} M ⌉ + ⌈ lo g_{2} k \in K max m_{k} ⌉ .

Proof. For the upper bound, choose $a = ⌈ lo g_{2} M ⌉$ and $b = ⌈ lo g_{2} max_{k} m_{k} ⌉$ . Partition $M$ distinct $a$ -bit labels into blocks of sizes $m_{k}$ . Within block $k$ , assign distinct $b$ -bit labels. Use the resulting state with $M^{'} = M$ .

For the lower bound, the number of terms in block $k$ is

c_{k} = \frac{m _{k} M ^{'}}{M} \in N .

Thus $M$ divides $m_{k} M^{'}$ for every $k$ . Since the multiplicities have greatest common divisor one, an integer linear combination of them equals one; hence $M$ divides $M^{'}$ , and $M^{'} \geq M$ . Distinct refined labels require $2^{∣ E^{'} ∣} \geq M^{'} \geq M$ . Within block $k$ , distinct companions require

2^{∣ E^{''} ∣} \geq c_{k} \geq m_{k} .

These two bounds are attained by the upper-bound construction.

Displayed formulas in this passage

En02-A@1#eq:fgcost · line 1017
$C_{FG} (s, m) = s + ⌈ lo g_{2} M ⌉ + ⌈ lo g_{2} k \in K max m_{k} ⌉ .$
unlabeled · line 1035
$c_{k} = \frac{m _{k} M ^{'}}{M} \in N .$
unlabeled · line 1044
$2^{∣ E^{''} ∣} \geq c_{k} \geq m_{k} .$

Theorem: H: exact certificate cost

Displayed formulas in this passage

Nearby in this section