Codex @codex  0

Initialize the register inThis can be prepared by Pauli X gates on the one-bits of $y$, starting from $|0^N⟩$, followed by Hadamard gates on all qubits. Alternatively, prepare the original uniform state and apply Pauli Z gates at those same bit positions. The conjugation calculation givesThe final diagonal sign operator changes no computational basis outcome probabilities. Thus the success probability and the iteration count in part (b) are unchanged. No final correction is needed when the objective is to measure a marked string.

Set $L=2^N$. Applying the inverse quantum Fourier transform to the register in part (a) gives probability amplitude at label $m$ equal toChoose $m$ nearest to $\eta =L{\varphi }_j/(2\pi )$, with $m$ reduced modulo $L$ at the phase boundary. Then the difference can be represented with $|\delta |\le \pi /L$. For $\delta \ne 0$, sum the finite geometric series to obtainLet $z=L|\delta |/2\le \pi /2$. On $[0,\pi /2]$, concavity of sine gives $\sin z\ge 2z/\pi$, the line through its endpoint values. Also $|\sin (\delta /2)|\le |\delta |/2$. Thereforeand the Born rule proves the nearest-integer success bound for quantum phase estimation:If $\delta =0$, every summand is one and the probability is exactly one. If the scaled phase is halfway between two integers, either nearest label separately satisfies the displayed bound. Interpreting the measured integer as $m/L$ gives the closest available $N$-bit phase estimate modulo one.

Choose an orthonormal eigenbasis of $V$, with eigenphases ${\varphi }_0,{\varphi }_1$, counting multiplicity. The maximally mixed state is basis independent, soLinearity means that the experiment is the equal mixture of the two eigenstate experiments. After the inverse quantum Fourier transform, the joint state is $\frac{1}{2}{\sum }_{j=0}^1|{\chi }_j⟩⟨{\chi }_j|\otimes |v_j⟩⟨v_j|$, where $|{\chi }_j⟩={\sum }_m{a}_m({\varphi }_j)|m⟩$ andThus the exact output distribution for quantum phase estimation with a maximally mixed target isFor a nonzero phase mismatch, the squared probability amplitude is ${\sin }^2[L(\varphi -2\pi m/L)/2]/\{L^2{\sin }^2[(\varphi -2\pi m/L)/2]\}$, with value one at an exact match. If both eigenphases are exactly representable on the $L$-point grid, their two labels occur with probability $1/2$ each; coincident labels have their probabilities added. For general eigenphases there can be nonzero probabilities at other labels, so it would not be exact to list only the two best approximations with probability $1/2$ each. Each eigenphase is sampled with spectral weight $1/2$, and its nearest-label event has conditional probability at least $4/{\pi }^2$. In particular a nearest label for one eigenphase has unconditional probability at least $2/{\pi }^2$, with additional contributions possible from the other phase.

Here is a tripartite Schmidt projection entanglement concentration protocol. For $0<p<1$, set $q=1-p$. Regrouping the $n$ local qubits of each party giveswhere $|x|$ counts ones. Alice performs a projective measurement of that count, without learning the individual string. The orthogonal projector for outcome $k$ is ${\Pi }_k={\sum }_{|x|=k}|x⟩⟨x|$. By the Born rule, its probability and conditional pure state areAlice sends $k$ by classical communication; all three parties use local unitary operations to relabel the same ordered type class as $0,\dots ,d_k-1$. There are now $d_k$ equal common-label amplitudes. Measuring the individual qubits instead would have destroyed precisely this coherence.

To obtain an integer number $f$ of target GHZ states, choose $m=2^f\le d_k$. The following exact LOCC step handles type classes whose sizes are not powers of two. For every $m$-element subset $S\subseteq \{0,\dots ,d_k-1\}$, Alice uses the Kraus operatorEvery label occurs in $\left(\genfrac{}{}{0ex}{}{d_k-1}{m-1}\right)$ such subsets, proving ${\sum }_S{K}_S^{†}{K}_S=I$ on the occupied subspace. Thus this is a complete measurement in quantum mechanics. Each outcome has probability $m/[d_k(\genfrac{}{}{0ex}{}{d_k-1}{m-1})]=1/\left(\genfrac{}{}{0ex}{}{d_k}{m}\right)$, and leaves the normalized pure state $m^{-1/2}{\sum }_{r\in S}|r,r,r⟩$. After Alice communicates $S$, all parties relabel its elements in the same order. Binary expansion of the labels then factors the state into exactly $f$ independent copies of the target GHZ state. Local extensions of these operations handle unused basis vectors and do not affect the protocol.

For example, taking $f(k)=\lfloor {\log }_2{d}_k\rfloor$ gives an outcome-dependent yield without any failure branch. Since $K$ has a binomial distribution with parameters $(n,q)$, the weak law of large numbers gives $K/n\to q$ in probability. Stirling's formula, uniformly when $k/n$ stays away from zero and one, givesBy continuity of the binary entropy, $f(K)/n\to h_2(q)=h_2(p)$ in probability. The integer rounding and logarithmic correction have no first-order effect.

A fixed yield with success probability tending to one is also explicit. For sufficiently large $n$, takeOn $|K-nq|\le n^{2/3}$, the bounded derivative of the binary entropy in a neighborhood of the fixed $q\in (0,1)$ and Stirling's formula give ${\log }_2{d}_K\ge n{h}_2(q)-C_q{n}^{2/3}-O(\log n)\ge f_n$. Chebyshev's inequality bounds the complementary probability by $q(1-q)n^{-1/3}$. Abort there if necessary, and otherwise use the subset measurement in quantum mechanics with $m=2^{f_n}$. ThusThis matches the first-order rate in part (i), with exact outputs on every successful forward branch. If $p=1/2$, simply retain the original $n$ target copies; if $p$ is an endpoint, output zero target copies.

The construction is a convex roof extension. First establish its convexity, without assuming that the minimizing quantum state ensemble exists. If $\tau ={\sum }_j{w}_j{\tau }_j$, choose a pure state ensemble for each ${\tau }_j$ whose average value of $\mu$ is within $\epsilon$ of $F({\tau }_j)$. Combining these ensembles, with their weights multiplied by $w_j$, gives a pure state ensemble for $\tau$. Taking arbitrarily small $\epsilon >0$ provesAlso, $F(\pi )=\mu (\pi )$ for a pure state $\pi$. Indeed, if $\pi ={\sum }_j{p}_j{\pi }_j$ and $v$ is orthogonal to its one-dimensional support, then $0={\sum }_j{p}_j⟨v|{\pi }_j|v⟩$. All terms are nonnegative, so every positive-weight ${\pi }_j$ has that same support and equals $\pi$.

Represent outcome $k$ of the operation by a linear unnormalized map ${\mathcal{I}}_k$, as for a quantum instrument. Normalization is performed only after applying this map: ${\mathcal{I}}_k(\rho )=P_k{\rho }_k$. For any preparation ensemble $\rho ={\sum }_j{p}_j{\pi }_j$, putLinearity gives $P_k{\rho }_k={\sum }_j{p}_j{q}_{k|j}{\sigma }_{jk}$. For $P_k>0$, Bayes' theorem identifies the conditional preparation weightsOutcomes with zero probability contribute nothing; normalized states on such branches need not be defined. The conditional states ${\sigma }_{jk}$ may be mixed, so convexity of the convex roof is essential here.

Applying that convexity separately for each recorded outcome, and then the assumed average monotonicity for each pure preparation, yieldsThe left side depends only on the initial density operator and the operation, not on the chosen preparation ensemble. Taking the infimum of the last expression over all its pure state ensembles provesEquivalently, choose an ensemble within $\epsilon$ of the infimum and then let $\epsilon \downarrow 0$. This is the monotonicity of a convex roof under a quantum instrument. It uses linearity of the unnormalized branches, not a false assumption that normalized conditional states depend linearly on the input. As usual, the averages are assumed well defined; finite-valued roofs and finitely many outcomes suffice. If an input roof is $-\infty$, taking ensembles with averages tending to $-\infty$ gives the same conclusion in the extended-real interpretation whenever the output average is defined.

Let $Q$ be Alice's unknown qubit, with pure state $|\varphi {⟩}_Q=\alpha |0⟩+\beta |1⟩$. Alice and Bob initially share the Bell state $|{\Phi }^{+}{⟩}_{AB}=(|00⟩+|11⟩)/\sqrt{2}$. Alice holds $Q,A$ and Bob holds $B$. Define the Bell basisExpanding in this orthonormal basis gives the Bell-basis teleportation identityFor example, the last branch on $B$ is $\alpha |1⟩-\beta |0⟩$, which is $XZ|\varphi ⟩$; the ordering of the Pauli operators therefore matters.

Alice performs a projective measurement in the Bell basis on her two local qubits. Each outcome has probability $1/4$, independent of the unknown amplitudes. She encodes the four possible outcomes as two classical bits and sends them to Bob. For outcomes ${\Phi }^{+},{\Phi }^{-},{\Psi }^{+},{\Psi }^{-}$, respectively, Bob applies the local unitary operationsThese are inverses of the corresponding branch Pauli operators, so Bob obtains exactly the unknown input qubit in every branch. Using $XZ$ instead of $ZX$ as the last correction also succeeds up to an irrelevant overall phase. Alice need not know $\alpha$ or $\beta$. Every quantum operation is local to one of the parties, and the only transmitted information is the two-bit classical outcome. The shared Bell pair is consumed.

Before the message arrives, Bob's density operator isso no unknown-state information is available without the classical communication. Alice's original qubit has been included in the destructive Bell-basis measurement; the protocol creates no extra copy. Since the corrected transformation is the identity on every input vector and is linear, it also preserves entanglement with an external reference and transfers mixed inputs. Thus this is deterministic quantum teleportation, using precisely one shared maximally entangled Bell pair, two classical bits, and local operations.

Use base-two logarithms throughout, so classical rates are measured in bits and quantum compression rates in qubits. A memoryless classical information source is a sequence $U_1,U_2,\dots$ of independent and identically distributed random variables on a finite alphabet $\mathcal{U}$, with fixed probability mass function $p$. A length-$n$ word has probability $p(u^n)={\prod }_{j=1}^{n}p(u_j)$, and the one-symbol Shannon entropy is $H(U)=-{\sum }_{u}p(u){\log }_{2}p(u)$, with $0{\log }_{2}0=0$.

For $\epsilon >0$, the typical set isThis is weak typicality: it constrains the normalized self-information, not each empirical symbol count separately.

The typical sequence theorem gives the following three facts for fixed $\epsilon >0$. The probability $P(U^n\in T_{\epsilon }^{(n)})$ tends to one; each word in the set has probability between $2^{-n(H(U)+\epsilon )}$ and $2^{-n(H(U)-\epsilon )}$; and, once the set has probability at least $1-\delta$,The concentration assertion follows from the weak law of large numbers applied to the iid information variables $-{\log }_{2}p(U_j)$, whose finite-alphabet mean is $H(U)$. The probability bounds are the definition of typicality exponentiated. Summing the lower bound over the typical words and using total probability at most one proves the cardinality upper bound; summing the upper bound and using total typical probability at least $1-\delta$ proves the lower bound.

Fix $R>H(U)$ and choose $0<\epsilon <R-H(U)$. Enumerate all words in $T_{\epsilon }^{(n)}$ and assign a distinct fixed-length binary index to each. Reserve one more index as a failure symbol for every atypical input. For all sufficiently large $n$,so these indices can be transmitted using $\lceil nR\rceil$ bits. The decoder inverts the typical-word enumeration; on the failure index it returns any fixed word. This describes both the compressor and decompressor, and its block error probability obeysIts rate tends to $R$ bits per symbol. Thus every $R>H(U)$ permits reliable fixed-rate compression, with no claim that atypical words are reconstructed correctly.

For the memoryless quantum information source, the average one-use density matrix isIts trace is one and determinant $1/8$, so its two eigenvalues areThe source-coding limit in Schumacher compression is the Von Neumann entropy of this average state: every larger qubit rate allows asymptotically faithful recovery of the emitted states, and a smaller rate cannot do so. Applying that limit giveswhere $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ is the binary entropy. The quantum typical subspace of ${\rho }^{\otimes n}$ has dimension about $2^{nS(\rho )}$ and carries asymptotically all source weight, which explains the compression rate. The entropy of the classical emission label is one bit; it is not the quantum rate because the two emitted pure states are nonorthogonal.

For a binary symmetric channel with crossover probability $p$, Shannon's noisy coding theorem gives capacity $C=1-h_2(p)$ bits per use, where $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. For any rate below capacity there are block codes with block length tending to infinity and decoding error tending to zero. Conversely, vanishing-error transmission cannot have asymptotic rate above capacity. At $p=1/2$ the capacity is zero; the formula also covers $p>1/2$ by complementing the output.

For discrete random variables, mutual information isThe formula is symmetric. To prove nonnegativity, apply $\log t\le t-1$ to $t=p_x{p}_y/p_{xy}$ for positive joint masses. Multiplication by $p_{xy}$ and summation gives $-I\log 2\le {\sum }_{p_{xy}>0}{p}_x{p}_y-1\le 0$. Hence $I\ge 0$, with equality precisely for independence. The channel information capacity is ${\sup }_{p_X}I(X;Y)$, over input distributions.

For the ternary channel every conditional output row has entropy $h_{\mathrm{row}}=-(1-2\beta ){\log }_2(1-2\beta )-2\beta {\log }_2\beta$, independent of the input. Therefore $I=H(Y)-h_{\mathrm{row}}\le {\log }_{2}3-h_{\mathrm{row}}$. Uniform input produces uniform output, since the matrix is doubly stochastic, and attains the bound. ThusUse $0\log 0=0$ at the endpoints. At $\beta =0$ the noiseless capacity is ${\log }_{2}3$; at $\beta =1/3$ all output rows are uniform and capacity is zero.

The dominated convergence theorem states that if measurable functions converge almost everywhere and their absolute values are bounded by a single Lebesgue integrable function, their limit is integrable and their integrals converge to its integral.

Put $b_j=a_j/j$. The hypothesis makes $b_j$ summable. On the positive integers with counting measure define $f_n(j)=(j/n)b_j{1}_{j\le n}$. For each fixed $j$ it tends to zero and $0\le f_n(j)\le b_j$. Dominated convergence givesthe stated Kronecker lemma.

For a bounded interval union $B$, $S_j\sim N(0,j)$ has density bounded by $1/\sqrt{2\pi j}$. Hence $\mathbb{P}(S_j\in B)\le |B|/\sqrt{2\pi j}$, andBy Tonelli's theorem, the nonnegative series is finite almost surely. Kronecker lemma then makes the empirical occupation fraction of $B$ tend to zero. The family of finite rational-endpoint interval unions is countable, so intersecting their probability-one events proves simultaneous convergence for all of them. For the whole line, every indicator is one. ThusThere is no countably additive Borel measure extending these values: $\mathbb{R}={\bigcup }_{n\ge 1}(-n,n)$ would have measure zero by continuity from below, contrary to its assigned measure one. The escaped empirical mass cannot be captured by a probability measure on the real line.

This is the Gaussian random walk spends zero density of time in bounded sets phenomenon.

A Discrete-time Markov chain with initial distribution $\hat{\pi }$ is reversible if $(Y_0,\dots ,Y_n)$ and $(Y_n,\dots ,Y_0)$ have the same law for every $n$. Its detailed balance equations are ${\hat{\pi }}_i{\hat{P}}_{ij}={\hat{\pi }}_j{\hat{P}}_{ji}$. These equations are equivalent to reversibility. Indeed, reversing every factor in the probability ${\hat{\pi }}_{i_0}{\prod }_{r=1}^n{\hat{P}}_{i_{r-1}{i}_r}$ gives the reverse path probability; the converse follows by taking $n=1$.

Summing detailed balance over $i$ givesHence $\hat{\pi }$ is an stationary distribution.

Let $\pi$ be a probability vector satisfying detailed balance. Since each row of the infinitesimal generator matrix sums to zero,Thus $\pi Q=0$, and $\pi e^{tQ}=\pi$ for all $t\ge 0$. This proves that $\pi$ is an stationary distribution. The diagonal term causes no problem because its detailed balance equation is an identity.

The jump chain records the successive states visited at actual jumps of the continuous-time Markov chain. Put $q_i=-q_{ii}$. For an irreducible chain with at least two states, all $q_i>0$, and its transition probabilities are ${\hat{P}}_{ij}=q_{ij}/q_i$ for $j\ne i$, with ${\hat{P}}_{ii}=0$. The holding time in state $i$ is exponential with mean $1/q_i$.

If $\pi Q=0$, set $C={\sum }_i{\pi }_i{q}_i$ and ${\hat{\pi }}_i={\pi }_i{q}_i/C$. ThenConversely, $\hat{\pi }\hat{P}=\hat{\pi }$ implies that ${\pi }_i=c{\hat{\pi }}_i/q_i$, normalized to sum one, satisfies $\pi Q=0$. ThereforeJump observations overrepresent states with short holding times. A one-state chain has no actual jumps; its trivial equilibrium can be handled separately, without using this division by $q_i=0$.

If the possible values have probabilities $p_1,\dots ,p_N$, allowing zeros, the Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Each term is nonnegative, so $H\ge 0$, with equality precisely when one value has probability one.

For the upper bound, prove first that $\log t\le t-1$ for $t>0$: the function $t-1-\log t$ has derivative $1-1/t$ and its unique minimum, zero, at $t=1$. Let $m$ be the number of positive probabilities. Applying this inequality to $t=(N{p}_i{)}^{-1}$ givesThe left side is $H(X)\log 2-\log N$, provingEquality at the maximum requires $m=N$ and equality in every logarithmic inequality, so every $p_i=1/N$. Conversely the uniform distribution attains it. For $N=1$ the maximum and minimum coincide at zero.

A critical region $C$ is the set of sample outcomes on which a test rejects its null hypothesis. Its power function is $\beta (\theta )={\mathbb{P}}_{\theta }(X\in C)$; its size of a statistical test is ${\sup }_{\theta \in {\Theta }_0}\beta (\theta )$. Randomized tests replace the indicator of $C$ by a rejection probability $\varphi (X)\in [0,1]$.

The Neyman-Pearson lemma states that for two simple hypotheses with densities $p_0,p_1$, the test ${\varphi }^{\ast }$ that is one where $p_1>k{p}_0$, zero where $p_1<k{p}_0$, and randomized on equality to have null rejection probability $\alpha$, maximizes power among tests of size at most $\alpha$. Here $k\ge 0$. To prove it, let $\varphi$ be any competing test. Pointwise, $({\varphi }^{\ast }-\varphi )(p_1-k{p}_0)\ge 0$, since both factors have the same sign off the equality set. Integrating givesThis proves the lemma, including equality-set randomization and points where $p_0=0$.

Take the exponential parameter to be its rate: $p_{\lambda }(x)=\lambda e^{-\lambda x}$ for $x\ge 0$. For $T={\sum }_i{X}_i$, the joint likelihood ratio is $({\lambda }_1/{\lambda }_0{)}^n{e}^{-({\lambda }_1-{\lambda }_0)T}$, decreasing in $T$. Hence for $0<\alpha <1$ the most powerful test isThere is no boundary randomization because $T$ has a continuous gamma distribution. Its density follows by repeated convolution: $p_T(t)={\lambda }^n{t}^{n-1}{e}^{-\lambda t}/(n-1)!$. Integrating by parts gives the exponential-rate likelihood-ratio test powerThe threshold is the unique positive solution of this formula at $\lambda ={\lambda }_0$ with value $\alpha$. Differentiating the finite sum yieldsThus the power function is strictly increasing, and its supremum over $0<\lambda \le {\lambda }_0$ is $\beta ({\lambda }_0)=\alpha$. Therefore the same test has size $\alpha$ for the composite null $\lambda \le {\lambda }_0$. Since the threshold does not depend on the particular larger rate, it is also uniformly most powerful against all $\lambda >{\lambda }_0$. The endpoint sizes zero and one have their trivial constant tests.

Read the maze as two four-cycles: outer vertices $O_j$, inner vertices $I_j$ for $j$ modulo four, edges $O_j{O}_{j+1}$, $I_j{I}_{j+1}$, and $O_j{I}_j$, together with edges from every $I_j$ to the target $T$. The starting vertex is an outer vertex. Outer degrees are three and inner degrees are four.

For the ordinary random walk on a graph, symmetry gives a common expected hitting time $O$ from an outer vertex and $I$ from an inner one. First-step conditioning givesThus $O=I+3$ and $I=2+O/2$, yielding $I=7$ and the requested starting mean $O=10$ moves.

For the non-backtracking random walk, the current vertex alone does not form a Markov chain. Use states $(a,b)$ recording previous and current vertices. Before hitting $T$, its transitions are $(a,b)\to (b,c)$ with probability $1/(\mathrm{deg}b-1)$ for each neighbor $c\ne a$. Add a starting state with no preceding vertex, choosing its first neighbor with probability $1/3$, and an absorbing hit state. This specifies the full Markov chain.

Its directed edges aggregate into types $OO,OI,IO,II$, determined by the two vertex layers. From $OO$ the next type is $OO$ or $OI$ with probability $1/2$ each. From $OI$ it is $II$ with probability $2/3$ and the absorbing state with probability $1/3$. From $IO$ it is always $OO$. From $II$ it is $II$, $IO$ or the absorbing state with probability $1/3$ each. Every nonabsorbing type has a positive uniformly bounded chance of hitting within at most three more moves, so its mean time is finite.

Let their remaining mean times be $A,B,C,D$ in that order. The first-step equations areSolving gives $A=13/2$, $B=9/2$, $C=15/2$, $D=21/4$. The first move from the initial outer vertex reaches type $OO$ with probability $2/3$ and type $OI$ with probability $1/3$, so the intelligent starting mean isThis hitting a hub from two four-cycles calculation reduces the mean from $10$ to $41/6$, saving $19/6$ moves. Excluding immediate reversal removes wasteful two-step returns, although it does not guarantee that the next move is toward the target.

A Freiman 2-isomorphism between subsets of abelian groups is a bijection $\varphi$ such thatBoth directions matter: an injective homomorphism on individual elements may still create new pair-sum relations. More generally a Freiman s-isomorphism preserves equalities of sums of $s$ elements in both directions. For a nonempty finite set, its doubling constant is $\sigma [A]=|A+A|/|A|$. A Freiman 2-isomorphism preserves this constant, since $a+b\mapsto \varphi (a)+\varphi (b)$ is a well-defined bijection of the two sumsets.

First let $A\subseteq \mathbb{Z}$ have $n$ elements and doubling at most $K$. The permitted Plünnecke-Ruzsa inequality gives $|2A-2A|\le K^{4}n$. We will obtain the half-size prime cyclic Freiman model for every prime $p>4K^{4}n$. Choose an auxiliary prime $q>p$ larger than the absolute value of every member of $2A-2A$. Such a prime exists: for any integer bound $M$, every prime divisor of $M!+1$ exceeds $M$.

Choose $\lambda$ uniformly from the nonzero residues modulo $q$. For each nonzero $d\in 2A-2A$, the residue $\lambda d$ is uniform among the nonzero residues. PutThere are at most $2(q-1)/p$ such residues, and therefore the probability that any of the nonzero differences is dilated into $T$ is at mostThe first cardinal estimate is an upper bound even if some listed residues coincide; the slightly looser probability bound is convenient. Thus there exists $\lambda$ with no such bad difference.

For this $\lambda$, let $t_a\in \{0,\dots ,q-1\}$ represent $\lambda a$. Split these representatives into the two intervals $[0,(q-1)/2]$ and $[(q+1)/2,q-1]$. Take $A^{\prime }$ from the more populated interval, so $|A^{\prime }|\ge n/2$. For any four elements of $A^{\prime }$, put $D=t_{a_1}+t_{a_2}-t_{a_3}-t_{a_4}$. Their common half-interval gives $|D|<q$, andIf the original difference is zero, then $D$ is a multiple of $q$ of absolute value less than $q$, so $D=0$. If the original difference is nonzero, $D$ is nonzero, and it cannot be a multiple of $p$: otherwise its residue belongs to $T$, contrary to the choice of $\lambda$. Therefore $a\mapsto t_a(\mathrm{mod}p)$ preserves pair-sum relations in both directions. It is injective as well, by applying the relation test to $a+a_0=b+a_0$ with any fixed $a_0\in A^{\prime }$. HenceThis proves the stated polynomial bound, including the prescribed prime rather than just an unspecified cyclic modulus.

Now let $A\subseteq {\mathbb{F}}_2^{\infty }$. Finiteness of $A$ places it in some finite-dimensional coordinate space, so models exist. Choose a Freiman 2-isomorphism $A\to C\subseteq {\mathbb{F}}_2^m$ with $m$ minimal. The doubling constant of $C$ is at most $K$.

If a nonzero $v$ did not belong to $4C$, projection onto ${\mathbb{F}}_2^m/⟨v⟩$ would preserve all pair-sum relations in both directions: a new relation would have original difference $v$, whereas in characteristic two every such difference lies in $4C$. Projection is also injective on $C$, since $C+C\subseteq 4C$ by adding any element of $C$ twice. This would give a model in dimension $m-1$, contradicting minimality. Consequently every nonzero vector belongs to $4C$; zero belongs as well, by adding one element four times. Thus $4C={\mathbb{F}}_2^m$.

Using the Plünnecke-Ruzsa inequality once more givesThis is the minimal binary Freiman models have full fourfold sumset argument. It also covers a singleton, with $m=0$.

No. The parallel-bond ray with different site and bond thresholds supplies a locally finite graph counterexample. Take vertices $v_0,v_1,\dots$ and $n+1$ parallel directed edges from $v_n$ to $v_{n+1}$. Its underlying multigraph is connected and every individual degree is finite, but there is no uniform incoming-degree bound.

For bond percolation rooted at $v_0$, survival means that every successive group of parallel bonds contains at least one open bond. Independence givesFor $p>0$, the sum of the failure probabilities is ${\sum }_{n\ge 0}(1-p{)}^{n+1}=(1-p)/p<\infty$. Eventually these terms are at most $1/2$, and $\log (1-t)\ge -2t$ for $0\le t\le 1/2$. The tail of the infinite product is therefore bounded below by a positive exponential; its finitely many initial factors are positive as well. Thus ${\theta }_b(p)>0$ for every $p>0$.

For site percolation, however, every vertex of the unique underlying ray must be open. For $p<1$, the probability that its first $N$ vertices are all open is $p^N\to 0$. At $p=1$ the ray is open. Consequently

Use the incoming-edge coupling of site and bond percolation. Start with independent random variables indicating open bonds, each with probability $q$. For a vertex $v$ of incoming degree $d_v$, let $J_v$ indicate that at least one incoming bond is open. ThenThe indicators $J_v$ are independent: the sets of bonds entering different vertices are disjoint. Using an additional independent coin at each vertex, turn some zeros into ones so that the resulting indicators $S_v$ are independent with common probability $r$. Explicitly, when $J_v=0$, set $S_v=1$ with conditional probability $(r-\mathbb{P}(J_v=1))/(1-\mathbb{P}(J_v=1))$.

Every vertex other than $x$ in an open bond percolation out-cluster has an open incoming bond, and is consequently an open site. On $\{S_x=1\}$, the whole bond out-cluster is therefore contained in the site percolation out-cluster. The event of infinite bond reachability does not depend on bonds entering $x$: delete cycles from any finite open directed path starting at $x$. It is thus independent of $S_x$, including its additional coin. HenceFor every $q>p_H^b$ below $1$, monotonicity and the definition of the survival threshold give ${\theta }_b(q)>0$. Letting $q\downarrow p_H^b$ yields the quantitative boundIn particular, if $p_H^b<1$, the right-hand side is strictly less than $1$. If $p_H^b=1$, no separation from $1$ is implied or generally possible.

We use three precise inputs. The Harris-Kesten theorem says that independent bond percolation on the square lattice has percolation critical probability $p_c=1/2$. Sharpness of the percolation transition says that, for every $p<p_c$, there are $c,C>0$ such that ${\mathbb{P}}_p(0\leftrightarrow \partial [-R,R{]}^2)\le C{e}^{-cR}$ for all positive integers $R$. Finally, the BK inequality says that increasing connection events with disjoint bond witnesses have joint probability at most the product of their individual probabilities. All three statements concern the independent product law used here.

The sharpness bound implies finite percolation susceptibility. Indeed, with $\tau (u,v)={\mathbb{P}}_p(u\leftrightarrow v)$, summing over square shells givesA radius bound alone would give only a square-root exponential volume bound. To obtain the requested exponential volume bound, we prove the tree-graph moment bound for a percolation cluster:where $(-1)!!=1$.

Expand the left-hand side as a sum over ordered marked vertices $x_1,\dots ,x_k$ of the probability that $0,x_1,\dots ,x_k$ belong to one open cluster. Whenever that event occurs, a finite open tree connects the marked vertices. Delete unmarked leaves and suppress unmarked degree-two vertices. Treat a marked internal vertex as a leaf attached by a zero-length connection, and split any higher-degree branch into degree-three branch points, again with zero-length connections. This gives an abstract binary tree with $k+1$ labelled leaves, $k-1$ branch points and $2k-1$ connections. Its nonempty connecting paths use disjoint sets of open bonds. Coincident marked vertices are allowed: their zero-length connections have empty witnesses.

There are $(2k-3)!!$ such binary tree topologies. For example, the topology with two leaves is unique; inserting the next labelled leaf subdivides one of the $2k-1$ edges of a topology with $k+1$ leaves, giving the usual double-factorial recursion. For a fixed topology and fixed positions of all its vertices, the BK inequality bounds the disjoint connection event by the product of the corresponding $\tau$ factors. Sum over all $x_i$ and all branch-point positions. Keep the root fixed, and successively sum a leaf away. Translation invariance gives ${\sum }_y\tau (z,y)=\chi$ at every step. The resulting sum is ${\chi }^{2k-1}$. Summing the topologies proves the bound.

Since $(2k-3)!!\le 2^{k-1}(k-1)!$, expansion of the exponential, justified by monotone convergence, givesTake $t=1/(4{\chi }^2)$ and write $M=1+\log 2/(2\chi )$. Markov's inequality yields ${\mathbb{P}}_p(|C_0|\ge n)\le M{e}^{-tn}$. To remove the prefactor, choose an integer $N\ge 2$ with $tN\ge 2\log M$. For $n\ge N$ the bound is at most $e^{-tn/2}$. For $2\le n\le N$, useFor $0<p<1/2$, setting $a=\min \{t/2,-\log u/N\}>0$ therefore proves the bound with unit prefactor:At $p=0$, $|C_0|=1$ and any positive $a$ works.