88 Communication Complexity — Func Disjointness Lower Bound
88.1 Overview
This module formalises a linear lower bound on the public-coin randomised communication complexity of the \(n\)-bit Disjointness function, following the information-theoretic argument of Rao and Yehudayoff (Chapter 6 of Communication Complexity). The key objects are the hard input distribution on CommunicationComplexity.Functions.Disjointness.RandomizedLowerBound.HardSample, the coarse conditioning variable \(Z = (M, T, X_{\lt T}, Y_{\gt T})\), and two corrected mutual information terms whose sum is bounded above by \(O(\ell /n)\) and shown to be bounded below by a constant whenever the protocol error on the hard distribution is at most \(1/32\).
88.2 Declarations
Alice’s bit in a disjoint coordinate-pair.
Bob’s bit in a disjoint coordinate-pair.
There are three disjoint coordinate-pairs.
A disjoint coordinate-pair never has both bits equal to true.
Swap Alice’s and Bob’s sides in a disjoint coordinate.
Swapping sides twice recovers the original disjoint coordinate.
After swapping a disjoint coordinate, Alice sees Bob’s original bit.
The sample space for the hard distribution. The other coordinate at \(T\) is ignored; keeping it in the sample space makes the ambient type a simple product-like finite type.
Technical auxiliary result for equivProd.
Cardinality of the explicit hard-distribution sample space.
Uniform law on the special coordinate.
Each coordinate has mass \(1 / n\) under the uniform law on Fin n.
The uniform law on Fin n assigns mass by normalized cardinality.
The uniform law on Fin n has total mass \(1\).
Uniform law on one bit.
Each bit has mass \(1 / 2\) under the uniform law on one bit.
The uniform law on Bool assigns mass by normalized cardinality.
The uniform law on Bool has total mass \(1\).
The uniform law on generated disjoint coordinate vectors.
The uniform law on one disjoint coordinate.
Each generated disjoint coordinate vector has mass \(3^{-n}\) under the uniform law.
The uniform law on disjoint-coordinate vectors assigns mass by normalized cardinality.
The uniform law on disjoint-coordinate vectors has total mass \(1\).
Each disjoint coordinate has mass \(1 / 3\) under the one-coordinate uniform law.
Alice’s bit at coordinate \(i\) under a hard-distribution sample.
Bob’s bit at coordinate \(i\) under a hard-distribution sample.
Alice’s input set under a hard-distribution sample.
Bob’s input set under a hard-distribution sample.
Alice’s full input vector under a hard-distribution sample.
Bob’s full input vector under a hard-distribution sample.
Reverse the coordinate order of a boolean vector.
Reversing a boolean vector twice recovers it.
Reversing boolean vectors is injective.
Reverse the coordinate order of a subset of coordinates.
Reversing a coordinate set twice recovers it.
The input pair generated by a hard-distribution sample.
The event that the special coordinate is an actual intersection.
The event that the two special-coordinate bits have prescribed values.
The event that the special coordinate has a prescribed value.
The event that both special-coordinate bits are zero.
The event that the generated input pair is disjoint.
The special coordinate selected by the hard distribution.
Alice’s bit at the special coordinate.
Bob’s bit at the special coordinate.
Alice’s input bits before the special coordinate, padded by false elsewhere.
Alice’s input bits up to and including the special coordinate, padded by false elsewhere.
Bob’s input bits after the special coordinate, padded by false elsewhere.
Bob’s input bits from the special coordinate onward, padded by false elsewhere.
The common coarse variable \(T, X_{\lt T}, Y_{\gt T}\) used for special-coordinate fibers.
Alice’s corrected special-coordinate conditioning variable: \(T, X_{\lt T}, Y_{≥T}\).
Alice’s corrected conditioning data without the special coordinate: \(X_{\lt T}, Y_{≥T}\).
Alice’s corrected conditioning is the special coordinate together with the remaining conditioning data.
Bob’s corrected special-coordinate conditioning variable: \(T, X_{≤T}, Y_{\gt T}\).
Alice’s bit at a fixed coordinate.
Alice’s fixed-coordinate strict prefix \(X_{\lt i}\), represented without padding.
Alice’s fixed-coordinate \(X_{\lt i}\) prefix.
Bob’s fixed-coordinate \(Y_{\lt i}\) prefix.
Bob’s fixed-coordinate \(Y_{≥i}\) suffix.
The fixed-coordinate Alice conditioning variable \(X_{\lt i}, Y_{≥i}\).
The fixed-coordinate conditioning variable \((X_{\lt i}, Y)\) used in the chain-rule sum. The \(X_{\lt i}\) prefix is represented without padding so that recodings are injective.
Recode \((X_{\lt i}, Y)\) as \((Y_{\lt i}, X_{\lt i}, Y_{≥i})\), the conditioning variable produced by the chain-rule split.
The chain-rule conditioning \((Y_{\lt i}, X_{\lt i}, Y_{≥i})\) is an injective recoding of \((X_{\lt i}, Y)\).
On hard samples, recoding \((X_{\lt i}, Y)\) gives exactly \((Y_{\lt i}, X_{\lt i}, Y_{≥i})\).
The values of Alice’s corrected conditioning variable for which \(Y_{T} = false\).
The \(Y_{≥T}\) component of Alice’s corrected conditioning contains the bit \(Y_{T}\).
The event \(Y_{T}=false\) is determined by Alice’s corrected conditioning variable.
The conditioning-value recoding induced by reversing coordinates and swapping Alice/Bob.
Recoding a conditioning value twice recovers the original value.
The conditioning-value duality map is injective.
The deterministic protocol type for disjointness inputs of length \(n\).
The syntactic transcript type for a disjointness protocol.
The raw type of values of the \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) variable for a protocol.
Technical auxiliary result for ext.
A raw \(Z\) value is equivalent to the product of its named fields.
The raw \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) variable used for coarse special-coordinate fibers.
The type of achievable values of the \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) variable for a protocol.
The transcript component of an achievable \(Z\) value.
The special-coordinate component of an achievable \(Z\) value.
The \(X_{\lt T}\) component of an achievable \(Z\) value.
The \(Y_{\gt T}\) component of an achievable \(Z\) value.
The raw value underlying an achievable \(Z\) value.
The achievability proof carried by a ZType value.
Technical auxiliary result for ext.
The \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) variable used for coarse special-coordinate fibers.
The fiber of the \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) variable above a value \(z\).
The protocol output determined by a \(Z\) value, through its transcript leaf.
Technical auxiliary result for run_eq_zOutput_of_zVariable_eq.
Every achievable \(Z\) fiber has positive ambient hard-distribution mass.
The hard input distribution as a measure on input pairs.
The hard input distribution packaged as a finite probability space for distributional error.
The protocol dual swaps Alice/Bob and reverses both coordinate sets.
The transcript-level map induced by protocol duality.
The transcript-level map induced by protocol duality is injective.
Technical auxiliary result for xBit_of_ne_special.
Technical auxiliary result for yBit_of_ne_special.
Away from \(T\), generated coordinate-pairs are disjoint.
The disjoint coordinate with the given bits. On the invalid \((true, true)\) input this chooses an arbitrary disjoint coordinate; the projection lemmas below assume that invalid case away.
coordinateOfBits preserves Alice’s bit when the requested pair is disjoint.
coordinateOfBits preserves Bob’s bit when the requested pair is disjoint.
coordinateOfBits reconstructs an existing disjoint coordinate from its two projections.
Mix Alice’s input from \(ωX\) with Bob’s input from \(ωY\). This is only intended to be used when the two samples agree on \(T\), \(X_{\lt T}\), and \(Y_{\gt T}\); under those hypotheses the mixed coordinate requests are always disjoint.
The generated sets are disjoint exactly when the two special-coordinate bits are not both true.
The generated disjoint coordinate-pair vector. On samples outside \(D\), the special coordinate uses the arbitrary default built into coordinateOfBits.
On disjoint samples, the generated coordinate vector recovers Alice’s input bit at every coordinate.
On disjoint samples, the generated coordinate vector recovers Bob’s input bit at every coordinate.
The other value at the special coordinate is ignored by the generated input.
Coordinates for the conditioned-on-disjointness sample space: the special coordinate, the generated disjoint coordinate-pair vector, and the ignored other value at the special coordinate.
Technical auxiliary result for disjointEventEquiv.
Technical auxiliary result for disjointEventInterDisjointModelEquiv.
Technical auxiliary result for card_disjointEvent_inter_disjointModel_fiber.
Under the hard distribution, a singleton fiber of the disjoint model together with \(D\) has one ambient sample’s worth of mass.
Dualize the hard sample space by swapping Alice/Bob and reversing coordinate order.
Dualizing a hard sample twice recovers the original sample.
Alice’s bit in the dual hard sample is Bob’s original bit at the reversed coordinate.
Bob’s bit in the dual hard sample is Alice’s original bit at the reversed coordinate.
Dual hard samples swap Alice’s input with Bob’s input and reverse coordinates.
Dual hard samples swap Bob’s input with Alice’s input and reverse coordinates.
The generated input of a dual hard sample is the reversed, swapped original input.
Hard-sample duality preserves the disjoint-input event.
Alice’s special bit in the dual hard sample is Bob’s original special bit.
Bob’s special bit in the dual hard sample is Alice’s original special bit.
The \(X_{T}=Y_{T}=false\) slice is invariant under hard-sample duality.
Alice’s full input vector in the dual is Bob’s original full vector in reverse order.
Bob’s full input vector in the dual is Alice’s original full vector in reverse order.
Alice’s before-special vector in the dual is Bob’s after-special vector in reverse order.
Bob’s after-special vector in the dual is Alice’s before-special vector in reverse order.
Alice’s \(X_{≤T}\) vector in the dual is Bob’s \(Y_{≥T}\) vector in reverse order.
Bob’s \(Y_{≥T}\) vector in the dual is Alice’s \(X_{≤T}\) vector in reverse order.
Alice’s corrected conditioning in the dual is Bob’s corrected conditioning in recoded form.
Bob’s corrected conditioning in the dual is Alice’s corrected conditioning in recoded form.
If two samples agree on the data contained in \(Z\), then Alice’s bit from the first sample and Bob’s bit from the second sample are disjoint away from the special coordinate.
The mixed sample has Alice’s input bits from the first sample.
The mixed sample has Bob’s input bits from the second sample.
The mixed sample has Alice’s full input from the first sample.
The mixed sample has Bob’s full input from the second sample.
The mixed sample’s generated input is the mixed input pair.
Mixing preserves Alice’s before-\(T\) conditioning data from the first sample.
Mixing preserves Bob’s after-\(T\) conditioning data from the second sample.
The mixed sample has Alice’s special bit from the first sample.
The mixed sample has Bob’s special bit from the second sample.
Swapping twice recovers the first sample. This is the involution behind the rectangle-counting argument for conditional independence on \(Z\) fibers.
The hard sample distribution is the product distribution on the independent fields \(T\), \(X_{T}\), \(Y_{T}\), and other. This rectangle form is the most convenient way to compute probabilities of events depending separately on the four fields.
The hard distribution creates an intersection with probability \(1 / 4\).
Each prescribed pair of special-coordinate bits has probability \(1 / 4\).
Under the hard distribution, the special coordinate is uniform.
Under the hard distribution, \(T=i\) and the special bits intersect with probability \(1/(4n)\).
The event \((X_{T}, Y_{T}) = (0, 0)\) has probability \(1 / 4\).
The event \(Y_{T} = false\) has probability \(1 / 2\).
The disjoint event is the complement of the special-intersection event.
The hard distribution generates disjoint inputs with probability \(3 / 4\).
Under the hard distribution, \(T=i\) and disjointness have probability \(3/(4n)\).
The disjoint event has positive measure under the hard distribution.
The hard distribution conditioned on the generated input being disjoint.
Under the disjoint-conditioned hard distribution, the special coordinate remains uniform.
The special-coordinate singleton event is the corresponding named event.
Under the disjoint-conditioned distribution, preimages of special-coordinate singletons have the uniform mass.
Under the measure conditioned on disjointness, the disjointness event holds almost surely.
If Bob’s special bit is false, the generated inputs are disjoint.
A prescribed special-coordinate bit pair is disjoint exactly when it is not \((true,true)\).
The \((X_{T},Y_{T})=(0,0)\) slice is contained in the disjoint event.
Under the disjoint-conditioned hard distribution, \((X_{T},Y_{T})=(0,0)\) has mass \(1 / 3\).
Under the disjoint-conditioned hard distribution, each non-intersecting special bit-pair has mass \(1/3\).
Under the disjoint-conditioned hard distribution, \(Y_{T}=false\) has mass \(2 / 3\).
The disjoint-conditioned hard distribution, further conditioned on Bob’s special bit being false. This is the Alice-side conditioning used in the one-bit Pinsker step.
Conditioning the disjoint law on \(Y_{T} = false\) gives a probability measure.
Under \(D ∧ Y_{T}=false\), Alice’s special bit is uniform.
Under the disjoint-conditioned distribution, the disjoint model is uniform.
Technical auxiliary result for disjointModelFiberForSpecialCoordinateCoordinateVectorEquiv.
Technical auxiliary result for card_disjointModel_fiber_for_specialCoordinate_coordinateVector.
Under the disjoint-conditioned distribution, the pair of the special coordinate and the generated disjoint coordinate vector is uniform on \(Fin n × \{ 0,1\} ^{n}_{disj}\).
The uniform law on disjoint coordinate vectors is the product of the one-coordinate uniform laws.
Under the uniform disjoint-coordinate-vector law, the coordinates are independent.
Alice’s bit at a fixed coordinate of a generated disjoint coordinate vector.
Bob’s bit at a fixed coordinate of a generated disjoint coordinate vector.
Alice’s input set represented by a generated disjoint coordinate vector.
Bob’s input set represented by a generated disjoint coordinate vector.
The input pair represented by a generated disjoint coordinate vector.
The protocol transcript as a function of the generated disjoint coordinate vector.
Alice’s coordinate-vector bits before a fixed coordinate, padded by false elsewhere.
Bob’s coordinate-vector bits before a fixed coordinate, padded by false elsewhere.
Bob’s coordinate-vector bits from a fixed coordinate onward, padded by false elsewhere.
The coordinate-vector version of Alice’s fixed-coordinate conditioning.
The one-bit-per-coordinate version of Alice’s fixed conditioning: use \(X_{j}\) before \(i\) and \(Y_{j}\) from \(i\) onward.
Alice’s fixed conditioning as one bit from each coordinate.
The residual coordinate bit left after conditioning on coordinateAliceCondBit. Before \(i\) this is Bob’s bit; at \(i\) it is Alice’s bit; after \(i\) it is unused.
Recode the one-bit-per-coordinate Alice conditioning into the padded pair used in the information term.
The one-bit-per-coordinate conditioning recodes to the padded-pair conditioning.
The padded-pair recoding of Alice’s one-bit-per-coordinate conditioning is injective.
Technical auxiliary result for coordinateAliceCondBits_fiber_eq_iInter.
Technical auxiliary result for coordinateWithCondBit.
Technical auxiliary result for coordinateWithCondBit_spec.
Each single-coordinate conditioning bit has positive mass under the uniform disjoint-vector law.
The per-coordinate residual/conditioning pairs are independent under the product-uniform disjoint-coordinate law.
After fixing Alice’s one-bit-per-coordinate conditioning, the current Alice bit is independent of Bob’s earlier bits under the product-uniform disjoint-coordinate law.
Product-coordinate form of the fixed-coordinate independence input: \(I(X_{i} : Y_{\lt i} | X_{\lt i},Y_{≥i})=0\), first with the one-bit-per-coordinate conditioning.
Product-coordinate form of the fixed-coordinate independence input, using the padded-pair conditioning variable.
Under \(D\), Alice’s fixed bit is the corresponding coordinate-vector projection.
Under \(D\), Bob’s fixed prefix is the corresponding coordinate-vector projection.
Under \(D\), Alice’s fixed conditioning is the corresponding coordinate-vector projection.
Under \(D\), the special coordinate and generated disjoint coordinate vector have the product law: \(T\) is uniform and independent of the disjoint coordinate vector.
The second marginal of the product law for \((T, coordinates)\) is the uniform disjoint-coordinate-vector law.
The generated disjoint coordinate vector under \(D\) has the uniform disjoint-vector law.
Conditioning the product law for \((T, coordinates)\) on \(T=i\) leaves the second coordinate uniform.
The fixed-coordinate Alice cross-information triple has the same law under \(D\) as the corresponding coordinate-vector triple under the uniform disjoint-coordinate law.
Even after conditioning on \(T=i\), the generated disjoint coordinate vector has the uniform disjoint-vector law.
A measure-preserving self-map leaves every random variable identically distributed with its pullback along that map.
The preimage of a singleton under hard-sample duality is the dual singleton.
The uniform hard-sample measure gives the same mass to a sample and its dual.
Hard-sample duality preserves the uniform hard-sample measure.
The disjoint-conditioned hard-sample measure gives the same mass to a sample and its dual.
Hard-sample duality preserves the disjoint-conditioned hard-sample measure.
Conditioning on a subevent of disjointness is the same under the ambient hard distribution and under the hard distribution first conditioned on disjointness.
Conditioning on \((X_{T},Y_{T})=(0,0)\) costs at most a factor \(2\) relative to conditioning only on \(Y_{T}=false\) under the disjoint distribution. This is the reweighting step before Markov’s inequality.
The transcript random variable induced by a deterministic protocol on the hard sample space.
Under \(D\), the transcript is a function of the generated disjoint coordinate vector.
The transcript entropy is at most the protocol length in bits, for any ambient measure.
The dual protocol transcript on the dual hard sample is the original transcript recoded through protocol duality.
Dualize a raw \(Z = (M,T,X_{\lt T},Y_{\gt T})\) value by recoding the transcript and coarse conditioning data.
Technical auxiliary result for rawZVariable_dualProtocol_dualHardSample.
Dualize an achievable \(Z = (M,T,X_{\lt T},Y_{\gt T})\) value by recoding the transcript and coarse conditioning data.
Raw \(Z\) dualization is injective.
The \(Z\)-value recoding induced by protocol and hard-sample duality is injective.
The \(Z\) variable for the dual protocol and hard sample is the recoded original \(Z\).
Pulling a recoded dual \(Z\) fiber back along hard-sample duality gives the original \(Z\) fiber.
The ambient hard-sample measure gives corresponding original and dual \(Z\) fibers the same mass.
Real-valued version of volume_zVariable_dualProtocol_dualZValue.
Probabilities under the hard input distribution can be computed on the explicit hard sample space by taking preimages under input.
The sample-space event where a deterministic protocol errs on disjointness.
Distributional error under the hard input distribution is the probability of the named sample-space error event.
The special-coordinate bit-pair.
The law of \(X_{T}\) under \(D ∧ Y_{T}=false\) is the uniform bit law.
The uniform law on one bit has full support.
Uniform law on a bit-pair.
Each bit-pair has mass \(1 / 4\) under the uniform law on two bits.
The uniform law on two bits is the product of the one-bit uniform laws.
The hard-distribution measure conditioned on a \(Z=z\) fiber.
Conditional probabilities under a \(Z=z\) fiber are computed by intersecting with the fiber and dividing by its mass.
The mass of a \(Z\) fiber under the Alice-side conditioned measure, with the \(3/2\) scaling from \(Pr_{D}[Y_{T}=false]=2/3\) made explicit.
Conditioning first on \(Y_{T}=false\) under \(D\), then on a \(Z\) value, is the same as conditioning under \(D\) on the intersection of those events.
Conditioning a \(Z=z\) fiber further on a special Bob-bit value is the same as conditioning the ambient hard distribution on the intersection of those two fiber events.
Conditioning a \(Z=z\) fiber further on \(Y_{T}=false\) agrees with conditioning the \(D ∧ Y_{T}=false\) measure on the same \(Z\) fiber.
A positive \(Z=z\) fiber under \(D ∧ Y_{T}=false\) makes the \(Y_{T}=false\) branch of the ambient \(Z=z\) fiber positive.
The conditional law of the special bit-pair on a positive-mass \(Z=z\) fiber.
On a positive-mass \(Z=z\) fiber, the conditional specialPair singleton mass is the corresponding preimage probability under the fiber measure.
The conditional law of Alice’s special bit on a positive-mass \(Z=z\) fiber.
The conditional law of Bob’s special bit on a positive-mass \(Z=z\) fiber.
On a positive-mass \(Z=z\) fiber, Alice’s conditional special-bit singleton mass is the corresponding preimage probability under the fiber measure.
On a positive-mass \(Z=z\) fiber, Bob’s conditional special-bit singleton mass is the corresponding preimage probability under the fiber measure.
The TV distance between the conditional special-pair law on a \(Z=z\) fiber and the uniform bit-pair law.
The TV distance between Alice’s conditional special-bit law and a uniform bit.
The TV distance between Bob’s conditional special-bit law and a uniform bit.
Alice’s one-bit conditional TV distance is nonnegative.
Pulling a dual \(Z\) fiber intersected with a dual Alice-special-bit event back along hard-sample duality gives the corresponding original Bob-special-bit event.
The ambient hard-sample measure gives corresponding original and dual one-bit \(Z\)-fiber events the same mass.
Real-valued version of volume_zVariable_dualProtocol_dualZValue_inter_specialX.
The Alice one-bit law on the dual protocol’s recoded \(Z\) fiber is Bob’s one-bit law on the original \(Z\) fiber.
The Alice one-bit distance for the dual protocol at the recoded \(Z\) value is the original Bob one-bit distance.
The dual Alice bad event on the \(X_{T}=Y_{T}=false\) slice is the original Bob bad event.
Pinsker for Alice’s one-bit fiber distance against the uniform bit.
Alice’s one-bit fiber KL cost on a \(Z=z\) fiber.
Pointwise Pinsker for Alice.
Integrated Alice Pinsker bound over the \(D ∧ Y_{T}=false\) conditioned measure.
Jensen’s inequality converts a squared Alice-side average-distance estimate under \(D ∧ Y_{T}=false\) into the average-distance estimate used before Markov.
Markov’s inequality converts the Alice-side average-distance estimate under \(D ∧ Y_{T}=false\) into a bad-\(Z\) probability bound.
A \(Z\) value is good when the conditional special-pair law on its achievable fiber is within \(2γ\) of uniform.
The good-fiber event, pulled back to the hard sample space through \(Z\).
The generated input follows the transcript of any deterministic protocol.
If a sample has \(Z=z\), its generated input follows the transcript component of \(z\).
Equal \(Z\) value fixes the special coordinate.
Equal \(Z\) value fixes Alice’s bits before the special coordinate.
Equal \(Z\) value fixes Bob’s bits after the special coordinate.
The transcript component of \(Z\) is a rectangle: two samples in the same \(Z\) fiber also contain the two mixed input pairs in that transcript rectangle.
Two samples in the same \(Z\) fiber have the same special coordinate.
Two samples in the same \(Z\) fiber have the same \(X_{\lt T}\) conditioning data.
Two samples in the same \(Z\) fiber have the same \(Y_{\gt T}\) conditioning data.
The mixed sample of two samples in the same \(Z\) fiber remains in that \(Z\) fiber.
If two samples are in a \(Z=z\) fiber, and the first has Alice special bit bX while the second has Bob special bit bY, then their mix is in the same fiber with special pair \((bX, bY)\).
The swapped mix of two samples in a \(Z=z\) fiber remains in that fiber.
If one sample in a fiber has special pair \(b\) and the other is just in the fiber, mixing with the special-pair sample on Alice’s side lands in the fiber with Alice special bit b.1.
If one sample in a fiber has special pair \(b\) and the other is just in the fiber, mixing with the special-pair sample on Bob’s side lands in the fiber with Bob special bit b.2.
The switching map \((ωX, ωY) ↦ (mix ωX ωY, mix ωY ωX)\) gives the cardinal identity underlying conditional independence of specialX and specialY on a \(Z=z\) fiber.
Under the uniform hard-distribution measure, real measure is cardinality divided by the size of the sample space.
The rectangle switching identity, translated from cardinalities to the uniform hard-distribution measure.
To prove the conditional special-pair law factors, it suffices to prove singleton factorization for the four bit-pairs.
Singleton factorization can be proved directly on the underlying \(Z=z\) fiber measure.
A cross-multiplied version of singleton factorization, phrased using the original hard distribution instead of conditional fiber probabilities.
The protocol transcript is a rectangle on each coarse fiber, so conditioned on a positive \(Z=z\) fiber the special bits factor as the product of their two marginals.
A product special-pair law gives singleton factorization of the conditional bit laws on the same \(Z\) fiber.
On a product-law \(Z\) fiber, conditioning on one Bob special-bit value does not change Alice’s special-bit law.
Rectangle switching implies the fiber identity \(p(X_{T} | Z=z) = p(X_{T} | Z=z, Y_{T}=false)\).
After rectangle switching, Alice’s xFiberKL can be computed by first conditioning on \(Y_{T}=false\) inside the \(Z=z\) fiber.
Alice’s xFiberKL can be rewritten as KL for the special Alice bit under \(D ∧ Y_{T}=false\) conditioned on the same \(Z=z\) fiber.
Positive mass under \(D ∧ Y_{T}=false\) supplies the positivity hypotheses needed to rewrite Alice’s fiber KL using the \(D ∧ Y_{T}=false, Z=z\) conditional law.
Product-distribution step for \(Z\) fibers. Conditioned on a transcript rectangle and the coarse data, the special bits are independent, so the pair TV distance is controlled by the two one-bit TV distances.
If both one-bit marginal distances on a \(Z\) fiber are at most \(γ\), then the fiber is good.
The corrected Alice special-coordinate information term: \(I(X_{T} : M | T, X_{\lt T}, Y_{≥T}, D)\).
The corrected Bob special-coordinate information term: \(I(Y_{T} : M | T, X_{≤T}, Y_{\gt T}, D)\).
The total corrected special-coordinate information.
Bob’s corrected information term is nonnegative.
Alice’s information term is bounded by the total corrected information.
Alice’s corrected information term for the dual protocol is Bob’s corrected information term for the original protocol.
Bob’s corrected information term for the dual protocol is Alice’s corrected information term for the original protocol.
Full-vector information for the dual protocol is the swapped full-vector information for the original protocol.
The total corrected information is invariant under protocol duality.
The fixed-coordinate summand \(I(X_{i} : M | X_{\lt i}, Y_{≥i})\).
The fixed-coordinate term with the full \(Y\) vector in the conditioning.
The zero cross-information term \(I(X_{i} : Y_{\lt i} | X_{\lt i}, Y_{≥i})\).
Fixed-coordinate independence input for the hard distribution conditioned on \(D\): \(I(X_{i} : Y_{\lt i} | X_{\lt i}, Y_{≥i}, D) = 0\).
Fixed-coordinate chain-rule inequality: \(I(X_{i} : M | X_{\lt i},Y_{≥i}) ≤ I(X_{i} : M | X_{\lt i},Y)\).
Summing the fixed-coordinate inequalities.
Chain rule for the full Alice vector: \(∑_{i} I(X_{i} : M | X_{\lt i},Y,D) = I(X : M | Y,D)\).
Chain-rule step for the Alice summands: \(∑_{i} I(X_{i} : M | X_{\lt i}, Y_{≥i}, D) ≤ I(X : M | Y, D)\). Its only probabilistic input is fixedAliceCrossInfoTerm_eq_zero.
Expanding Alice’s random-coordinate information term by the special coordinate \(T\).
Uniformity/independence step for the special coordinate: after conditioning on \(T=i\), the random-coordinate Alice information term is the fixed-coordinate summand.
Averaging over the special coordinate: conditioned on \(D\), \(T\) is uniform and independent of \((X,Y,M)\), so the Alice term is the average of the fixed-coordinate summands.
Alice fixed-coordinate chain-rule bound after conditioning on disjointness and averaging over the uniform special coordinate: \(I(X_{T} : M | T, X_{\lt T}, Y_{≥T}, D) ≤ I(X : M | Y, D) / n\).
Bob fixed-coordinate chain-rule bound after conditioning on disjointness and averaging over the uniform special coordinate: \(I(Y_{T} : M | T, X_{≤T}, Y_{\gt T}, D) ≤ I(Y : M | X, D) / n\).
The Alice full-vector information is bounded by the transcript entropy.
The Bob full-vector information is bounded by the transcript entropy.
Alice’s averaged fixed-coordinate information plus the entropy bound \(H(M) ≤ ℓ\).
Bob’s averaged fixed-coordinate information plus the entropy bound \(H(M) ≤ ℓ\).
The corrected claim information is at most the averaged full-vector transcript information coming from the entropy bound \(H(M) ≤ ℓ\).
On the branch \(Y_{T}=false\), the corrected Alice suffix \(Y_{≥T}\) is the same information as the coarse suffix \(Y_{\gt T}\), since the missing coordinate is fixed to false.
On the branch \(Y_{T}=false\), Alice’s corrected conditioning is exactly the coarse conditioning from \(Z=(M,T,X_{\lt T},Y_{\gt T})\).
Under \(D ∧ Y_{T}=false\), Bob’s special bit is almost surely false.
Under \(D ∧ Y_{T}=false\), Alice’s fine conditioning variable is a.e. the coarse conditioning variable.
The Alice information term after additionally conditioning on \(Y_{T}=false\): \(I(X_{T} : M | T, X_{\lt T}, Y_{≥T}, Y_{T}=0, D)\).
The same Alice \(Y_{T}=false\) information term using the coarse conditioning \(T, X_{\lt T}, Y_{\gt T}\).
Since \(X_{T}\) is uniform under \(D ∧ Y_{T}=false\), the conditional KL average to the uniform bit law is the mutual information between \(X_{T}\) and the full \(Z=(M,T,X_{\lt T},Y_{\gt T})\) variable.
The fine \(Y_{≥T}\) and coarse \(Y_{\gt T}\) versions of the Alice \(Y_{T}=false\) information term agree, because \(Y_{T}\) is fixed on the conditioned measure.
The averaged Alice fiber KL cost under \(D ∧ Y_{T}=false\), as a finite sum over \(Z\) values.
The averaged Alice fiber KL cost under \(D ∧ Y_{T}=false\) as a finite sum of actual KL divergences for the conditional \(Z=z\) laws.
The averaged Alice fiber KL under \(D ∧ Y_{T}=false\), rewritten as the PFR real conditional KL used by the entropy API.
Flip only Alice’s special-coordinate bit. This preserves the coarse conditioning data \(T, X_{\lt T}, Y_{\gt T}\) and toggles \(X_{T}\).
Technical auxiliary result for flipSpecialX_flipSpecialX.
Technical auxiliary result for flipSpecialX_preimage_singleton.
Technical auxiliary result for volume_measureReal_singleton_flipSpecialX.
Technical auxiliary result for volume_measurePreserving_flipSpecialX.
Technical auxiliary result for specialX_flipSpecialX.
Technical auxiliary result for specialY_flipSpecialX.
Technical auxiliary result for xBeforeSpecial_flipSpecialX.
Technical auxiliary result for yAfterSpecial_flipSpecialX.
Technical auxiliary result for coarseConditioning_flipSpecialX.
In every \(Y_{T}=false, coarse=c\) fiber of the ambient hard distribution, each value of \(X_{T}\) has half the mass.
The preceding ambient counting identity remains true after conditioning on \(Y_{T}=false\).
Under \(D ∧ Y_{T}=false\), the coarse data \(T, X_{\lt T}, Y_{\gt T}\) is independent of \(X_{T}\). This is the sampling independence used before adding the transcript rectangle.
The full \(Z=(M,coarse)\) mutual information is the coarse information term, because the coarse part alone is independent of \(X_{T}\) under \(D ∧ Y_{T}=false\).
KL identification with the coarse \(Z\) conditioning: the average Alice one-bit fiber KL is the conditional mutual information \(I(X_{T} : M | T,X_{\lt T},Y_{\gt T},Y_{T}=0,D)\).
Identification of the average Alice one-bit fiber KL with the conditional mutual information under \(Y_{T}=false\). This packages the step \(p(x_{t} | z) = p(x_{t} | z, y_{t}=0) = p(x_{t} | z, y_{t}=0, D)\) coming from independence and the rectangle property of the transcript.
Alice-side reweighting: \((2/3) I(X_{T} : M | T, X_{\lt } T, Y_{≥T}, Y_{T}=0, D) ≤ I(X_{T} : M | T, X_{\lt } T, Y_{≥T}, D)\). The factor is \(Pr[Y_{T}=false | D] = 2/3\), and the event \(Y_{T}=false\) is determined by the conditioning variable because \(Y_{≥T}\) contains \(Y_{T}\).
Alice information step under \(D ∧ Y_{T}=false\): the average one-bit KL cost is bounded by Alice’s information term, with the \(2/3\) conditioning factor.
Alice information step under \(D ∧ Y_{T}=false\): the average one-bit KL cost is bounded by the small total information assumption.
Alice Pinsker/information step under \(D ∧ Y_{T}=false\): the squared one-bit marginal distance has average at most \(γ^{4}\). This is the KL-to-information comparison from the inequality \((2/3) I(X_{T} : M | T, X_{\lt T}, Y_{≥T}, Y_{T}=0, D) ≤ I(X_{T} : M | T, X_{\lt T}, Y_{≥T}, D)\).
Alice marginal estimate: under the \((X_{T},Y_{T})=(0,0)\) slice, the set of \(Z\) fibers whose Alice special-bit marginal is farther than \(γ\) from uniform has mass at most \(γ / 2\).
Bob marginal estimate, symmetric to the Alice marginal estimate.
If the corrected special-coordinate information is \(≤ 2γ^{4} / 3\), then the set of \(Z\) fibers where the conditional law of \((X_{T}, Y_{T})\) is within \(2γ\) of uniform has hard-distribution mass at least \((1 - 4γ) / 4\).
Intersecting with the defining \(Z=z\) fiber does not change probabilities under the corresponding fiber measure.
A good \(z\) gives the expected singleton-mass estimate for the conditional special-pair law.
A good \(z\) gives a lower bound on each singleton mass of the conditional special-pair law.
On a fixed \(Z=z\) fiber, inputs whose special pair equals the \(Z\)-determined protocol output on both sides are protocol errors.
On a good \(Z\) fiber, the conditional protocol-error probability is at least \(1 / 4 - 2 * γ\). If the protocol output on the fiber is true, then the \((true, true)\) special bit-pair witnesses errors; otherwise \((false, false)\) witnesses errors.
Averaging the good-fiber error lower bound over all good \(Z\) fibers gives an unconditional error lower bound.
The final good-fiber error calculation, phrased using distributional error.
A deterministic protocol with distributional error at most \(1 / 32\) must reveal a constant amount of the corrected special-coordinate information.
Deterministic fixed-error disjointness lower bound from the information estimate.
Public-coin fixed-error lower bound from the deterministic distributional lower bound via minimax.
Headline theorem: public-coin randomized communication complexity of disjointness is linear at fixed error \(1 / 32\), with a concrete conservative constant. The cutoff is the floor of the real number \(n / 2^{32}\), so the asymptotic constant is stated over the reals.