Consider the type of possible roles a single coordinate can play in the disjointness communication problem: it belongs to neither of the two sets, to the left set only, or to the right set only. This is a finite type, and it has exactly three elements.

Consider a coordinate in the disjointness distribution, whose state is one of three cases — belonging to neither player, to Alice only, or to Bob only — and let \(\mathrm{xBit}(c)\) and \(\mathrm{yBit}(c)\) denote Alice’s and Bob’s bits in that coordinate. Then for every such coordinate \(c\) it is never the case that both \(\mathrm{xBit}(c)\) and \(\mathrm{yBit}(c)\) equal true.

A disjoint coordinate records, for a single index, which of the two players’ inputs contains that index: neither, Alice only, or Bob only. Writing \(\mathrm{swap}\) for the operation that exchanges the two players’ sides — fixing "neither" and interchanging "Alice only" and "Bob only" — one has \(\mathrm{swap}(\mathrm{swap}(c)) = c\) for every disjoint coordinate \(c\); that is, \(\mathrm{swap}\) is an involution.

For every disjoint coordinate \(c\), Alice’s bit of the swapped coordinate \(\mathrm{swap}(c)\) equals Bob’s bit of the original coordinate \(c\).

A hard sample over \(n \ge 1\) coordinates consists of a distinguished coordinate \(T \in \{ 0,1,\dots ,n-1\} \), two bits \(x_T, y_T \in \{ 0,1\} \), and an assignment giving each of the \(n\) coordinates one of the three tags *neither*, *left only*, or *right only*. The number of such samples is exactly \(n \cdot 4 \cdot 3^{n}\).

Let \(n\) be a positive integer, and let the uniform probability law on the \(n\)-element set \(\{ 0,1,\dots ,n-1\} \) (the finite type \(\mathrm{Fin}\, n\)) assign equal mass to each point. Then for every element \(i\), the mass of the singleton \(\{ i\} \) equals \(\dfrac {1}{n}\).

Let \(n \ge 1\) and equip the \(n\)-element set \(\{ 0, 1, \dots , n-1\} \) with the uniform probability law, under which each point carries mass \(1/n\). Then for every subset \(S\) of this set, its probability is \(\left\lvert S\right\rvert /n\), the number of elements of \(S\) divided by \(n\).

Let \(n\) be a positive integer, and let \(\mu \) be the uniform probability law on the \(n\)-element set \(\{ 0, 1, \dots , n-1\} \), which assigns to each point equal weight. Then the total mass of \(\mu \) is one; that is, \(\mu (\{ 0,1,\dots ,n-1\} ) = 1\).

Under the uniform probability law on the two Boolean values, each individual outcome \(b\) carries mass exactly \(\tfrac {1}{2}\); that is, the singleton event \(\{ b\} \) has probability \(\tfrac {1}{2}\) for either choice of \(b\).

Let \(\mu \) denote the uniform probability law on the two-element type \(\mathrm{Bool}\). Then for every subset \(S \subseteq \mathrm{Bool}\), the real-valued measure of \(S\) equals \(|S|/2\), where \(|S|\) is the number of Boolean values lying in \(S\).

The uniform law on a single bit, viewed as a measure on the two-element set of Boolean values, assigns real-valued mass \(1\) to the whole space; that is, the measure of the universal set equals \(1\).

Let \(n \ge 1\), and consider vectors of length \(n\) whose entries are drawn from the three-element set \(\{ \text{neither}, \text{leftOnly}, \text{rightOnly}\} \) of disjoint-coordinate labels. Under the uniform law on these \(3^n\) vectors, every individual vector \(c\) carries probability mass

Let \(n \ge 1\), and consider the finite set of vectors \(x \colon \{ 1,\dots ,n\} \to \{ \text{neither}, \text{left only}, \text{right only}\} \) assigning to each coordinate one of three labels, of which there are \(3^n\) in total. Under the uniform probability law on this set, every subset \(S\) of such vectors has measure

where \(\left\lvert S\right\rvert \) denotes the number of vectors lying in \(S\).

Fix a positive integer \(n\), and consider the finite set of vectors \((x_1,\dots ,x_n)\) of length \(n\) in which each coordinate \(x_i\) takes one of the three values *neither*, *left-only*, or *right-only*. Under the uniform probability law on this set, the total mass — the measure assigned to the set of all such vectors — equals \(1\).

Let a *disjoint coordinate* be one of the three symbols \(\{ \text{neither}, \text{leftOnly},\ \text{rightOnly}\} \), and let \(\mu \) be the uniform law on this three-element set. Then for every disjoint coordinate \(c\), the measure of the singleton \(\{ c\} \) satisfies \(\mu (\{ c\} ) = \tfrac {1}{3}\).

For any boolean vector \(v = (v_0, v_1, \ldots , v_{n-1})\) of length \(n \ge 1\), reversing its coordinate order twice returns the original vector: if \(v'\) denotes the vector obtained by reversing the coordinate order of \(v\), then reversing the coordinate order of \(v'\) recovers \(v\) exactly.

For a positive integer \(n\), let \(\rho \colon \{ 0,1\} ^n \to \{ 0,1\} ^n\) be the map that reverses the coordinate order of a Boolean vector, sending \(v = (v_0, v_1, \dots , v_{n-1})\) to \((v_{n-1}, \dots , v_1, v_0)\). Then \(\rho \) is injective: whenever two Boolean vectors have the same reversal, they are equal.

Fix a positive integer \(n\), and for a subset \(S \subseteq \{ 0, 1, \dots , n-1\} \) let \(\overline{S} = \{ \, i : (n-1) - i \in S \, \} \) be the subset obtained by reversing the coordinate order. Then applying this reversal twice returns the original set: \(\overline{\overline{S}} = S\) for every \(S \subseteq \{ 0, 1, \dots , n-1\} \).

Fix \(n \ge 1\), and for a sample \(\omega \) from the hard distribution write \(T\) for its special coordinate, \(X_{\lt T}\) for Alice’s input bits at the coordinates before \(T\) (padded with \(\mathrm{false}\) from \(T\) onward), and \(Y_{\ge T}\) for Bob’s input bits at the coordinates from \(T\) onward (padded with \(\mathrm{false}\) before \(T\)). Then Alice’s corrected special-coordinate conditioning variable, namely the triple \((T,\, X_{\lt T},\, Y_{\ge T})\), coincides with the pair consisting of \(T\) together with Alice’s corrected dynamic conditioning data \((X_{\lt T},\, Y_{\ge T})\); that is, the two agree as functions of \(\omega \).

Fix \(n \ge 1\) and an index \(i \in \{ 0, 1, \dots , n-1\} \), and consider Boolean strings valued in \(\mathbb {F}_2 = \{ 0,1\} \). Define a map that sends a pair \((x, y)\), where \(x \colon \{ 0,\dots ,i-1\} \to \mathbb {F}_2\) records the first \(i\) coordinates of Alice’s input and \(y \colon \{ 0,\dots ,n-1\} \to \mathbb {F}_2\) is Bob’s full input, to the triple \((u, v, w)\) of Boolean functions on all of \(\{ 0,\dots ,n-1\} \) given by \(u(j) = y(j)\) if \(j \lt i\) and \(u(j) = 0\) otherwise, \(v(j) = x(j)\) if \(j \lt i\) and \(v(j) = 0\) otherwise, and \(w(j) = y(j)\) if \(j \ge i\) and \(w(j) = 0\) otherwise; that is, \((x,y) \mapsto (y_{\lt i}, x_{\lt i}, y_{\ge i})\) with all out-of-range coordinates zero-padded. Then this map is injective.

Fix a positive integer \(n\) and a coordinate \(i \in \{ 0,1,\dots ,n-1\} \). Let \(R\) be the map that sends a pair \((a,b)\) — where \(a\) is a Boolean vector indexed by \(\{ 0,\dots ,i-1\} \) and \(b\) is a Boolean vector of length \(n\) — to

whose three components are all Boolean vectors of length \(n\); here \([\, \cdot \, ]\) is the Iverson bracket, so each component takes the value \(0\) at every index falling outside the range named in its own bracket. For every sample \(\omega \) of the hard distribution, let \(b\) be Bob’s full induced input vector of length \(n\) and let \(a\) be Alice’s induced input restricted to the coordinates \(\{ 0,\dots ,i-1\} \) (a Boolean vector on those indices, carrying no padding). Then

where \(x_{\lt i}\), \(y_{\lt i}\), and \(y_{\ge i}\) are the length-\(n\) Boolean vectors that equal Alice’s induced input at each index below \(i\), Bob’s induced input at each index below \(i\), and Bob’s induced input at each index at least \(i\), respectively, and are \(0\) at every other index.

Fix a sample \(\omega \) of the hard distribution, and write \(T\) for its special coordinate. Let \(y_{\ge T}\) be Bob’s truncated input vector, whose value at a coordinate \(i\) is Bob’s bit at \(i\) when \(T \le i\) and is \(\mathrm{false}\) otherwise. Then evaluating this vector at the special coordinate itself gives Bob’s bit at the special coordinate: \(y_{\ge T}(T)\) equals \(y_T\).

Fix a positive integer \(n\) and work over the hard-distribution sample space, whose samples \(\omega \) record a special coordinate \(T \in \{ 0,\dots ,n-1\} \) together with enough data to determine Alice’s and Bob’s bits at every coordinate. Let \(Y_T(\omega )\) denote Bob’s bit at the special coordinate, and let the conditioning variable be the triple \(\bigl(T,\, X_{\lt T},\, Y_{\ge T}\bigr)\) consisting of the special coordinate, Alice’s bits strictly before it (padded with \(\mathrm{false}\) elsewhere), and Bob’s bits from it onward (padded with \(\mathrm{false}\) elsewhere). Then the set of samples with \(Y_T = \mathrm{false}\) coincides exactly with the set of samples whose conditioning variable \((t,x,y)\) satisfies \(y(t) = \mathrm{false}\).

Fix a positive integer \(n\), and let a triple \(c = (i, x, y)\) consist of a coordinate \(i \in \{ 0, 1, \dots , n-1\} \) together with two Boolean vectors \(x, y \colon \{ 0, 1, \dots , n-1\} \to \{ \text{true}, \text{false}\} \). Applying the dual conditioning-value recoding — which sends \(c\) to \((n-1-i,\, y \circ \mathrm{rev},\, x \circ \mathrm{rev})\), where \(\mathrm{rev}\) reverses the coordinate order — twice in succession returns the original triple \(c\); that is, the recoding is an involution.

Fix an integer \(n \ge 1\), and for a boolean vector \(x \colon \{ 0,1,\dots ,n-1\} \to \{ \text{true},\text{false}\} \) write \(\bar x\) for its coordinate reversal, \(\bar x(i) = x(n-1-i)\). Consider the map on triples \((i, x, y)\), where \(i \in \{ 0,1,\dots ,n-1\} \) and \(x, y\) are boolean vectors of length \(n\), defined by

which reverses the index, swaps the two vectors, and reverses the coordinate order of each. This map is injective.

Fix a positive integer \(n\) and a deterministic disjointness protocol \(p\) on inputs of length \(n\), and let \(z\) and \(z'\) be two raw \(Z\)-values for \(p\) — each consisting of a syntactic transcript of \(p\), a special coordinate in \(\{ 0,1,\dots ,n-1\} \), and two Boolean vectors indexed by \(\{ 0,1,\dots ,n-1\} \) recording the bits before and after that coordinate. If \(z\) and \(z'\) have the same transcript, the same special coordinate, the same "before" vector, and the same "after" vector, then \(z = z'\).

Fix a positive integer \(n\) and a deterministic protocol \(p\) for disjointness inputs of length \(n\), and recall that the raw \(Z\)-variable sends each hard-distribution sample \(\omega \) to the tuple \(Z(\omega ) = (M, T, X_{\lt T}, Y_{\gt T})\) consisting of the transcript of \(p\) on \(\omega \)’s input, the special coordinate, and the input bits before and after that coordinate. An achievable \(Z\)-value is a raw value together with a witness that it arises this way. Then for every achievable \(Z\)-value \(z\), there exists a hard-distribution sample \(\omega \) such that \(Z(\omega )\) equals the underlying raw value of \(z\).

Fix a deterministic communication protocol \(p\) for disjointness inputs of length \(n\), and consider achievable values of the variable \(Z = (M, T, X_{\lt T}, Y_{\gt T})\), each carrying a transcript \(M\), a special coordinate \(T \in \{ 0, \dots , n-1\} \), a Boolean string \(X_{\lt T}\) recording Alice’s bits before the special coordinate, and a Boolean string \(Y_{\gt T}\) recording Bob’s bits after it. Then two such achievable values \(z\) and \(z'\) coincide whenever they have the same transcript, the same special coordinate, the same \(X_{\lt T}\), and the same \(Y_{\gt T}\).

Fix \(n \ge 1\) and a deterministic protocol \(p\) for disjointness inputs of length \(n\). Let \(\omega \) be a sample of the hard distribution, and let \(z\) be an achievable value of the \(Z\)-variable \(Z = (M, T, X_{\lt T}, Y_{\gt T})\) for \(p\). If \(z\) is exactly the value of the \(Z\)-variable at \(\omega \), then running \(p\) on Alice’s input set \(X(\omega )\) and Bob’s input set \(Y(\omega )\) produces the same Boolean output as the output determined by \(z\) through its transcript leaf:

Fix a positive integer \(n\) and a deterministic communication protocol \(p\) for disjointness inputs of length \(n\). On the finite sample space of hard-distribution samples \(\omega \), let \(Z(\omega ) = (M, T, X_{\lt T}, Y_{\gt T})\) be the statistic recording the transcript \(M\) produced by running \(p\) on the input pair generated by \(\omega \), the special coordinate \(T\), Alice’s input bits strictly before \(T\), and Bob’s input bits strictly after \(T\). Then for every achievable value \(z\) of \(Z\)—that is, every \(z\) realized by at least one sample—the fiber \(Z^{-1}(\{ z\} )\), consisting of all samples \(\omega \) with \(Z(\omega ) = z\), has nonzero volume under the ambient measure on the sample space.

Let \(n\) be a positive integer, and let \(p\) be a deterministic two-party communication protocol in which both Alice’s and Bob’s inputs are subsets of \(\{ 0,1,\dots ,n-1\} \) and the output is a single Boolean. Protocol duality produces from \(p\) a protocol over the same input and output types by exchanging the roles of Alice and Bob and reversing the coordinate order \(i \mapsto n-1-i\) in both players’ inputs, and it induces a map on syntactic transcripts that sends each execution transcript of \(p\) to the transcript of the dual protocol carrying the very same sequence of Boolean messages. This induced transcript map is injective.

Let \(\omega \) be a sample of the hard distribution, with special coordinate \(T\), per-coordinate assignment \(\text{other}\), and let \(\text{xBit}(\omega , i)\) denote Alice’s bit at coordinate \(i\). Then for every coordinate \(i \neq T\), Alice’s bit at \(i\) equals Alice’s bit in the disjoint coordinate-pair \(\text{other}(i)\) that \(\omega \) assigns to \(i\).

Fix a positive integer \(n\) and a sample \(\omega \) of the hard distribution, consisting of a distinguished coordinate \(T \in \{ 0, 1, \dots , n-1\} \), two bits \(x_T\) and \(y_T\), and an assignment \(i \mapsto \omega _{\text{other}}(i)\) of a disjoint coordinate-type (one of *neither*, *left only*, *right only*) to each coordinate. For every coordinate \(i \ne T\), Bob’s bit at \(i\) under this sample equals the bit \(y(\omega _{\text{other}}(i))\) read off from the coordinate-type assigned to \(i\); that is, away from the distinguished coordinate the distinguished bit \(y_T\) plays no role.

Let \(\omega \) be a sample of the hard distribution on \(n\) coordinates, with special coordinate \(T\), and let \(i\) be any coordinate with \(i \neq T\). Then Alice’s bit and Bob’s bit at coordinate \(i\) are never both equal to \(\mathrm{true}\); that is, it is not the case that both the Alice-bit at \(i\) and the Bob-bit at \(i\) hold.

Let \(x, y \in \{ \mathrm{true}, \mathrm{false}\} \) be a pair of bits that are not both \(\mathrm{true}\). Then the disjoint coordinate built from \((x, y)\) has Alice’s bit equal to \(x\); that is, extracting Alice’s bit from this coordinate returns \(x\) exactly.

Let \(x, y \in \{ \mathrm{true}, \mathrm{false}\} \) be Alice’s and Bob’s bits in a single coordinate, and suppose they are not both \(\mathrm{true}\). Then Bob’s bit extracted from the disjoint coordinate assembled from \(x\) and \(y\) equals \(y\).

Let a *disjointness coordinate* be one of three values, recording, for a single index, whether that index belongs to neither of two subsets, to the first subset only (Alice’s), or to the second subset only (Bob’s). To each coordinate \(c\) attach two Boolean bits: Alice’s bit \(x(c)\), which is set precisely when \(c\) marks the index as belonging to Alice’s subset only, and Bob’s bit \(y(c)\), which is set precisely when \(c\) marks it as belonging to Bob’s subset only. Conversely, from a pair of bits \((x, y)\) form a coordinate \(\kappa (x, y)\) by taking "Alice only" if \(x\) is set, otherwise "Bob only" if \(y\) is set, and otherwise "neither." Then \(\kappa \bigl(x(c), y(c)\bigr) = c\) for every coordinate \(c\); that is, splitting a coordinate into its two bits and reassembling recovers the original coordinate.

Let \(\omega \) be a hard-distribution sample, with distinguished coordinate \(T\) carrying Alice’s bit \(x_T\) and Bob’s bit \(y_T\), and let \(X(\omega )\) and \(Y(\omega )\) be Alice’s and Bob’s input sets under \(\omega \). Then \(X(\omega )\) and \(Y(\omega )\) are disjoint if and only if it is not the case that \(x_T\) and \(y_T\) are both \(\mathrm{true}\).

Let \(\omega \) be a hard-distribution sample whose induced input pair, Alice’s set \(X(\omega )\) and Bob’s set \(Y(\omega )\), are disjoint. Then for every coordinate \(i\), Alice’s bit read off from the disjoint coordinate-pair generated at \(i\) agrees with Alice’s bit at \(i\) under \(\omega \).

Let \(\omega \) be a sample of the hard distribution lying in the disjoint event — that is, one whose induced input sets \(X(\omega )\) and \(Y(\omega )\) are disjoint. Then for every coordinate \(i\), the Bob-bit of the disjoint coordinate assigned to \(i\) by the generated coordinate-pair vector agrees with Bob’s bit \(\mathrm{yBit}(\omega , i)\) at that coordinate.

Fix \(n \ge 1\), and consider the finite sample space whose points \(\omega \) each consist of a distinguished coordinate \(T \in \{ 1,\dots ,n\} \), a pair of bits \(x_T, y_T\) at that coordinate, and a labelling of every coordinate by one of the three disjoint-coordinate types (neither, left-only, right-only). From such an \(\omega \) one reads off the generated coordinate-pair vector together with the pair of input sets \(X(\omega ), Y(\omega )\), and one records the model data \(\mathrm{model}(\omega ) = (T, \text{coordinate-pair vector},\ \text{the ignored label at } T)\). Then for every triple \(z\) in the target of the model map, there is exactly one sample \(\omega \) whose generated inputs are disjoint, that is \(X(\omega )\) and \(Y(\omega )\) are disjoint, and for which \(\mathrm{model}(\omega ) = z\).

Fix an integer \(n \ge 1\), and equip the finite space of hard samples with its uniform probability measure: a hard sample records a special coordinate \(T \in \{ 1,\dots ,n\} \), two bits \(x_T, y_T\), and a disjoint-coordinate value at each of the \(n\) coordinates, so there are \(n\cdot 4\cdot 3^{\, n}\) of them, each carrying mass \(1/(n\cdot 4\cdot 3^{\, n})\). Then for every point \(z\) of the space \(\{ 1,\dots ,n\} \times \big(\{ 1,\dots ,n\} \to \text{DisjointCoordinate}\big)\times \text{DisjointCoordinate}\), the set of hard samples that lie in the disjointness event and whose disjoint model equals \(z\) has measure exactly

the mass of a single sample.

Fix \(n \ge 1\), and let \(\omega \) be any hard sample: a distinguished coordinate \(T \in \{ 0,\dots ,n-1\} \), two bits recording Alice’s and Bob’s values there, and an assignment of a disjoint coordinate (neither, left-only, or right-only) to every coordinate. Applying the dualization map to \(\omega \) twice returns \(\omega \) itself; that is, the dualization — which reverses the coordinate order, interchanges Alice’s and Bob’s bits at the distinguished coordinate, and swaps the two sides of every coordinate assignment — is an involution.

Fix a positive integer \(n\), and let \(\omega \) be a sample of the hard distribution on \(n\) coordinates. For every coordinate \(i \in \{ 0, 1, \dots , n-1\} \), Alice’s bit at coordinate \(i\) in the dualized sample \(\omega ^{\ast }\) coincides with Bob’s bit at the reversed coordinate \(\mathrm{rev}(i) = n-1-i\) in the original sample \(\omega \); that is,

Let \(\omega \) be a sample of the hard distribution over \(n\) coordinates, and write \(\mathrm{rev}(i) = n-1-i\) for the reversal of a coordinate \(i \in \{ 0,1,\dots ,n-1\} \). Form the dual sample by swapping Alice’s and Bob’s roles and reversing the coordinate order. Then Bob’s bit at coordinate \(i\) of the dual sample equals Alice’s bit at the reversed coordinate \(\mathrm{rev}(i)\) of the original sample.

Fix a positive integer \(n\) of coordinates, and let \(\omega \) be any sample of the hard distribution. Then Alice’s input set of the dualized sample coincides with the coordinate-reversal of Bob’s input set of the original sample; that is, \(X(\mathrm{dual}(\omega )) = \mathrm{reverse}(Y(\omega ))\), where reversal sends each coordinate \(i\) to \(n-1-i\).

Fix \(n \ge 1\), and let \(\omega \) be a sample of the hard distribution on \(n\) coordinates, with Alice’s input set \(X(\omega ) \subseteq \{ 0,\dots ,n-1\} \) and Bob’s input set \(Y(\omega )\). Passing to the dual sample \(\omega '\) — obtained by swapping Alice’s and Bob’s roles and reversing the coordinate order — Bob’s input set of \(\omega '\) is exactly the coordinate reversal of Alice’s input set of \(\omega \):

where \(\operatorname {rev}(i) = n-1-i\). Equivalently, a coordinate \(i\) belongs to Bob’s set for the dualized sample precisely when the reversed coordinate \(\operatorname {rev}(i)\) belongs to Alice’s set for the original sample.

Fix \(n \ge 1\), and let \(\omega \) be a sample of the hard distribution, from which one reads off Alice’s input set \(X(\omega )\) and Bob’s input set \(Y(\omega )\), packaged as the input pair \((X(\omega ), Y(\omega ))\). Form the dual sample by swapping the roles of Alice and Bob and reversing the coordinate order \(i \mapsto \bar\imath \). Then the input pair generated by the dual sample is obtained from \((X(\omega ), Y(\omega ))\) by exchanging the two sets and reversing the coordinate order of each: Alice receives the coordinate-reversal of \(Y(\omega )\) and Bob receives the coordinate-reversal of \(X(\omega )\), i.e.

Let \(\omega \) be a sample of the hard distribution, and let \(\omega ^\ast \) be its dual, obtained by exchanging Alice’s and Bob’s roles while reversing the order of the coordinates. Then Alice’s and Bob’s input sets \(X(\omega ^\ast )\) and \(Y(\omega ^\ast )\) are disjoint if and only if \(X(\omega )\) and \(Y(\omega )\) are disjoint; that is, \(\omega ^\ast \) lies in the disjointness event exactly when \(\omega \) does.

Fix a positive integer \(n\), and let \(\omega \) be a point of the hard sample space on \(n\) coordinates. Passing to the dualized sample — which swaps the roles of Alice and Bob and reverses the coordinate order — turns Alice’s bit at the special coordinate into Bob’s bit at the special coordinate of \(\omega \): Alice’s special bit of the dual of \(\omega \) equals Bob’s special bit of \(\omega \).

Let \(\omega \) be a sample of the hard distribution, and let \(\omega '\) be its dual, obtained by exchanging the roles of Alice and Bob and reversing the order of the coordinates. Then Bob’s bit at the special coordinate of \(\omega '\) equals Alice’s bit at the special coordinate of \(\omega \).

Fix \(n \ge 1\), and let a hard sample \(\omega \) record a special coordinate \(T \in \{ 0,\dots ,n-1\} \), Alice’s and Bob’s bits \(x_T, y_T \in \{ \mathrm{false},\mathrm{true}\} \) at that coordinate, and a labelling of every coordinate by one of the three disjointness states. Let its dual be the hard sample obtained by reversing the coordinate order (sending each index \(i\) to \(n-1-i\)), swapping the sides of every coordinate label, and interchanging Alice’s and Bob’s special bits, so that the dual’s Alice-bit is \(y_T\) and its Bob-bit is \(x_T\). Then the dual of \(\omega \) has both of its special bits equal to \(\mathrm{false}\) if and only if \(\omega \) itself has both special bits equal to \(\mathrm{false}\).

Fix a positive dimension \(n\) and let \(\omega \) be a hard-distribution sample. Then Alice’s full input vector of the dual sample \(\omega ^{\vee }\) (obtained by swapping the roles of Alice and Bob and reversing the coordinate order) coincides, coordinate by coordinate, with the reversal of Bob’s full input vector of \(\omega \); that is, for every coordinate the value Alice receives in the dual is the value Bob receives in the original at the mirror-image coordinate \(n-1-i\).

Fix a positive integer \(n\) and let \(\omega \) be a hard sample on the \(n\) coordinates. Then Bob’s full input vector of the dualized sample equals the coordinate reversal of Alice’s full input vector of \(\omega \): for every coordinate the value Bob receives after dualizing agrees with the value Alice receives at the mirror-image coordinate of the original sample.

Fix a positive integer \(n\), and let \(\omega \) be a sample of the hard distribution on \(n\) coordinates — a choice of special coordinate \(T\), Alice’s and Bob’s bits there, and a disjointness type at every remaining coordinate. Write \(\omega ^\ast \) for the dual sample obtained by exchanging Alice’s and Bob’s roles and reversing the coordinate order. Then Alice’s before-special vector of \(\omega ^\ast \) equals the coordinate-reversal of Bob’s after-special vector of \(\omega \); concretely, at each coordinate \(i\) Alice’s before-special bit of \(\omega ^\ast \) at \(i\) coincides with Bob’s after-special bit of \(\omega \) at the mirror-image coordinate \(n-1-i\).

Fix a coordinate count \(n \ge 1\) and let \(\omega \) be a sample of the hard distribution, with special coordinate \(T\). Form the dual sample \(\omega ^{*}\) by swapping the roles of Alice and Bob and reversing the coordinate order \(i \mapsto \bar\imath \). Then Bob’s after-special vector of \(\omega ^{*}\) — the vector whose entry at each coordinate \(i\) is Bob’s bit of \(\omega ^{*}\) at \(i\) when \(i\) lies strictly after the special coordinate of \(\omega ^{*}\), and is \(\mathrm{false}\) otherwise — equals the coordinate reversal of Alice’s before-special vector of \(\omega \), whose entry at each coordinate \(i\) is Alice’s bit of \(\omega \) at \(i\) when \(i\) lies strictly before \(T\), and is \(\mathrm{false}\) otherwise. Equivalently, for every coordinate \(i\) the \(i\)-th entry of Bob’s after-special vector of \(\omega ^{*}\) agrees with the \(\bar\imath \)-th entry of Alice’s before-special vector of \(\omega \).

Fix a positive integer \(n\), and let \(\omega \) be a sample of the hard distribution on \(n\) coordinates. Form the dual sample by swapping Alice’s and Bob’s roles and reversing the coordinate order. Then Alice’s truncated input vector in the dual sample — her bits up to and including the special coordinate, padded by \(\mathrm{false}\) elsewhere — agrees coordinate-for-coordinate with the coordinate-reversal of Bob’s truncated input vector in \(\omega \), namely his bits from the special coordinate onward, padded by \(\mathrm{false}\) elsewhere.

Let \(n\) be a positive integer and let \(\omega \) be a sample of the hard distribution, with special coordinate \(T\), and write \(\mathrm{dual}(\omega )\) for its dual sample, obtained by exchanging Alice’s and Bob’s bits and reversing the coordinate order. Then Bob’s suffix vector \(y_{\ge T}\) of \(\mathrm{dual}(\omega )\) equals the coordinate-reversal of Alice’s prefix vector \(x_{\le T}\) of \(\omega \): for every coordinate \(i\) with \(0 \le i \le n-1\),

Let \(\omega \) be a sample of the hard distribution over \(n \ge 1\) coordinates, with special coordinate \(T\) and associated Alice/Bob bit vectors, and form its dual sample by reversing the coordinate order and interchanging the roles of Alice and Bob. Then Alice’s corrected conditioning variable of the dual sample, namely the triple \((T, X_{\lt T}, Y_{\ge T})\), equals the recoding of Bob’s corrected conditioning variable \((T, X_{\le T}, Y_{\gt T})\) of \(\omega \) that reverses the special coordinate and interchanges the two boolean vectors while reversing the coordinate order of each.

Fix a positive integer \(n\) and a hard-distribution sample \(\omega \) with special coordinate \(T \in \{ 0,\dots ,n-1\} \). Write \(\mathrm{rev}\) for the order-reversing map \(i \mapsto n-1-i\) on coordinates, and for a Boolean vector \(u\) write \(\bar u = u \circ \mathrm{rev}\) for its coordinate reversal. Recall that Alice’s conditioning variable of \(\omega \) is the triple \(\bigl(T,\ X_{\lt T},\ Y_{\ge T}\bigr)\) — the special coordinate together with Alice’s bits strictly before \(T\) (padded with \(\mathrm{false}\) elsewhere) and Bob’s bits from \(T\) onward — while Bob’s conditioning variable is \(\bigl(T,\ X_{\le T},\ Y_{\gt T}\bigr)\). Let \(\omega ^\ast \) denote the dual sample, obtained from \(\omega \) by reversing the coordinate order and interchanging Alice’s and Bob’s roles. Then Bob’s conditioning variable of \(\omega ^\ast \) equals the dual recoding of Alice’s conditioning variable of \(\omega \); that is, if \(\bigl(T,\ X_{\lt T},\ Y_{\ge T}\bigr)\) is Alice’s conditioning variable of \(\omega \), then Bob’s conditioning variable of \(\omega ^\ast \) is exactly \(\bigl(\mathrm{rev}(T),\ \overline{Y_{\ge T}},\ \overline{X_{\lt T}}\bigr)\).

Let \(\omega _X\) and \(\omega _Y\) be two samples of the hard distribution that share the same special coordinate \(T\), whose Alice-before-special vectors agree and whose Bob-after-special vectors agree. Then for every coordinate \(i \neq T\), it is never the case that Alice’s bit at \(i\) under \(\omega _X\) and Bob’s bit at \(i\) under \(\omega _Y\) are both true.

Let \(\omega _X\) and \(\omega _Y\) be two hard-distribution samples that share the same special coordinate \(T\), whose Alice-inputs on the coordinates before \(T\) agree, and whose Bob-inputs on the coordinates after \(T\) agree. Then at every coordinate \(i\), Alice’s bit under the mixed sample \(\mathrm{mix}(\omega _X,\omega _Y)\) equals Alice’s bit under \(\omega _X\) at that coordinate.

Let \(\omega _X\) and \(\omega _Y\) be two samples of the hard distribution that share the same special coordinate \(T\) (so their \(T\)-fields agree), that agree on the profile of Alice’s bits at the coordinates strictly below \(T\) (each padded by \(\mathrm{false}\) at the remaining coordinates), and that agree on the profile of Bob’s bits at the coordinates strictly above \(T\) (again each padded by \(\mathrm{false}\) elsewhere). Form the mixed sample that takes its special coordinate, Alice’s bit there, and Alice’s input from \(\omega _X\) while taking Bob’s bit at \(T\) and Bob’s input from \(\omega _Y\). Then for every coordinate \(i\), Bob’s bit at \(i\) in this mixed sample equals Bob’s bit at \(i\) in \(\omega _Y\).

Let \(\omega _X\) and \(\omega _Y\) be two samples of the hard distribution that agree on the special coordinate \(T\), on Alice’s padded input bits before \(T\), and on Bob’s padded input bits after \(T\). Then the mixed sample, which takes Alice’s data from \(\omega _X\) and Bob’s data from \(\omega _Y\), induces exactly Alice’s input set of \(\omega _X\); that is, \(X(\mathrm{mix}(\omega _X,\omega _Y)) = X(\omega _X)\).

Fix a positive integer \(n\) and consider two samples \(\omega _X\) and \(\omega _Y\) drawn from the hard-distribution sample space on the coordinates \(\{ 0,1,\dots ,n-1\} \). Suppose the two samples share the same special coordinate \(T\), that they agree on Alice’s input bits before the special coordinate, and that they agree on Bob’s input bits after the special coordinate. Then Bob’s input set of the mixed sample \(\operatorname {mix}(\omega _X,\omega _Y)\) — the sample that takes Alice’s data from \(\omega _X\) and Bob’s data from \(\omega _Y\) — coincides with Bob’s input set of \(\omega _Y\).

Let \(\omega _X\) and \(\omega _Y\) be two hard-distribution samples that agree on their special coordinate \(T\), whose associated Alice-bit vectors before the special coordinate coincide, and whose associated Bob-bit vectors after the special coordinate coincide. Then the input pair generated by mixing Alice’s data from \(\omega _X\) with Bob’s data from \(\omega _Y\) is exactly \((X(\omega _X),\, Y(\omega _Y))\): the Alice set of the mixed sample equals Alice’s input set under \(\omega _X\), and the Bob set of the mixed sample equals Bob’s input set under \(\omega _Y\).

Let \(\omega _X\) and \(\omega _Y\) be two samples of the hard distribution that share the same special coordinate \(T\), that agree on Alice’s before-special vector (the bits Alice holds at the coordinates strictly below \(T\), padded with \(\mathrm{false}\) elsewhere), and that agree on Bob’s after-special vector (the bits Bob holds at the coordinates strictly above \(T\), padded with \(\mathrm{false}\) elsewhere). Then the mixed sample \(\mathrm{mix}(\omega _X,\omega _Y)\), which takes Alice’s data from \(\omega _X\) and Bob’s data from \(\omega _Y\), has the same before-special vector as \(\omega _X\).

Let \(\omega _X\) and \(\omega _Y\) be two samples from the hard distribution on \(n\) coordinates, and suppose they share the same special coordinate, \(T(\omega _X) = T(\omega _Y)\), that Alice’s before-special profiles agree, \(x_{\lt T}(\omega _X) = x_{\lt T}(\omega _Y)\), and that Bob’s after-special profiles agree, \(y_{\gt T}(\omega _X) = y_{\gt T}(\omega _Y)\). Then Bob’s after-special profile of the mixed sample \(\mathrm{mix}(\omega _X,\omega _Y)\) coincides with that of \(\omega _Y\):

Fix a positive integer \(n\), and let \(\omega _X\) and \(\omega _Y\) be two samples from the hard distribution, each carrying a special coordinate together with Alice’s and Bob’s bits there and a disjoint coordinate on every other index. Form the mixed sample that takes Alice’s data from \(\omega _X\) and Bob’s data from \(\omega _Y\). Then Alice’s bit at the special coordinate of the mixed sample equals Alice’s bit at the special coordinate of \(\omega _X\).

Let \(\omega _X\) and \(\omega _Y\) be two samples of the hard distribution, and form the mixed sample that takes Alice’s input from \(\omega _X\) and Bob’s input from \(\omega _Y\). Then Bob’s bit at the special coordinate of the mixed sample equals Bob’s bit at the special coordinate of \(\omega _Y\).

For two samples \(\omega ,\omega '\) of the hard distribution, let \(\omega \ast \omega '\) denote their *mixture*: the sample built by taking Alice’s input from \(\omega \) and Bob’s input from \(\omega '\). Let \(\omega _X\) and \(\omega _Y\) be two samples that share the same special coordinate \(T\), whose Alice-bits before the special coordinate agree, and whose Bob-bits after the special coordinate agree. Then

Fix a positive integer \(n\), and let \(\mathrm{HardSample}(n)\) be the finite sample space whose points \(\omega \) record a special coordinate \(\omega .T \in \{ 0,\dots ,n-1\} \), two bits \(\omega .x_T,\omega .y_T \in \{ 0,1\} \), and a coordinate vector \(\omega .\mathrm{other}\colon \{ 0,\dots ,n-1\} \to \mathrm{DisjointCoordinate}\). For any set \(\mathcal T\) of special coordinates, any sets \(\mathcal X,\mathcal Y\) of bits, and any set \(\mathcal O\) of coordinate vectors, the ambient measure of the rectangle event

taken as a real number, equals the product

where \(\mu _{\mathrm{Fin}}\) is the uniform law on the special coordinate, \(\mu _{\mathrm{bit}}\) is the uniform law on one bit, and \(\mu _{\mathrm{vec}}\) is the uniform law on coordinate vectors, each evaluated on the corresponding set as a real number.

Fix an integer \(n \ge 1\), and let the sample space consist of all tuples \((T, x_T, y_T, c)\), where \(T \in \{ 1,\dots ,n\} \) is a distinguished coordinate, \(x_T, y_T \in \{ \mathrm{true}, \mathrm{false}\} \) are two Boolean values, and \(c\) assigns to each coordinate one of the three labels *neither*, *leftOnly*, or *rightOnly*; equip this finite space with the uniform probability measure. Then the event that the distinguished coordinate is a genuine intersection, namely \(\{ x_T = \mathrm{true} \text{ and } y_T = \mathrm{true}\} \), has probability \(\tfrac 14\).

Consider the finite sample space whose elements record a distinguished coordinate \(T\), two special bits \(x_T, y_T \in \{ 0,1\} \), and a labelling of every other coordinate by one of three values, equipped with the uniform probability measure. For any prescribed pair of bits \(b_x, b_y \in \{ 0,1\} \), the event that \(x_T = b_x\) and \(y_T = b_y\) has probability \(\tfrac {1}{4}\).

Fix a positive integer \(n\) and an index \(i \in \{ 0, 1, \dots , n-1\} \). Equip the finite sample space of hard samples with its uniform probability measure. Then the probability of the event that the special coordinate \(T\) equals \(i\) is

Equip the finite space of hard samples with the uniform probability measure, where each sample consists of a special coordinate \(T \in \{ 1,\dots ,n\} \), two Boolean bits \(x_T\) and \(y_T\), and a value in \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} \) for every one of the \(n\) coordinates. Then for each fixed coordinate \(i \in \{ 1,\dots ,n\} \), the probability that the special coordinate equals \(i\) and that both special bits are true, that is \(T = i\) and \(x_T = y_T = \text{true}\), is exactly \(\dfrac {1}{4n}\).

Consider the hard distribution’s sample space, whose points carry two special-coordinate bits \(x_T, y_T \in \{ 0,1\} \) (among other data), equipped with the uniform probability measure. The event that both special bits vanish, \(x_T = 0\) and \(y_T = 0\), has probability \(\tfrac {1}{4}\).

Consider the finite sample space of hard samples for a fixed number of coordinates \(n \ge 1\), equipped with the uniform probability distribution, where each sample records in particular Bob’s bit \(y_T \in \{ \mathrm{true}, \mathrm{false}\} \) at the special coordinate. Then the event that this bit takes the value \(\mathrm{false}\) has probability \(\tfrac {1}{2}\).

Fix an integer \(n \ge 1\), and consider the finite space of hard-distribution samples on \(n\) coordinates, each sample consisting of a special coordinate \(T \in \{ 1,\dots ,n\} \), two bits \(x_T\) and \(y_T\), and a disjoint-coordinate label (one of *neither*, *left only*, *right only*) attached to every coordinate. From such a sample one forms Alice’s set \(X\) and Bob’s set \(Y\). Then, as subsets of this sample space, the event that \(X\) and \(Y\) are disjoint equals the complement of the special-intersection event; equivalently, \(X\) and \(Y\) fail to be disjoint precisely on those samples for which \(x_T\) and \(y_T\) are both true.

Fix a positive integer \(n\), and draw a hard sample \(\omega \) uniformly at random from the finite sample space of the hard distribution on \(n\) coordinates. Then the disjointness event — the event that Alice’s input set \(X(\omega )\) and Bob’s input set \(Y(\omega )\) are disjoint — has probability exactly \(3/4\).

Fix \(n \ge 1\) and equip the sample space of the hard distribution with the uniform probability measure, so that a sample consists of a special coordinate \(T \in \{ 1,\dots ,n\} \), Alice’s and Bob’s bits \(x_T, y_T\) at that coordinate, and an independent uniformly chosen label in \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} \) at each of the \(n\) coordinates. For any fixed coordinate \(i \in \{ 1,\dots ,n\} \), the probability that the special coordinate satisfies \(T = i\) and that the generated sets \(X\) and \(Y\) are disjoint equals

Fix a positive integer \(n\), and consider the finite sample space of hard-distribution samples, each of which determines Alice’s input set \(X \subseteq \{ 1,\dots ,n\} \) and Bob’s input set \(Y \subseteq \{ 1,\dots ,n\} \). Under the ambient measure on this sample space, the disjoint event — the set of samples for which \(X\) and \(Y\) are disjoint — has nonzero measure.

Fix \(n \ge 1\), and consider the hard distribution on \(\mathrm{HardSample}(n)\) conditioned on the disjointness event (that Alice’s set \(X\) and Bob’s set \(Y\) are disjoint). Then for every coordinate \(i \in \{ 0,1,\dots ,n-1\} \), the conditional probability that the special coordinate \(T\) equals \(i\) is exactly

In other words, conditioning on disjointness leaves the special coordinate \(T\) uniformly distributed over the \(n\) coordinates.

Fix a positive integer \(n\) and a coordinate \(i \in \{ 0,1,\dots ,n-1\} \). The set of hard samples whose special coordinate equals \(i\) — that is, the preimage under the special-coordinate map of the singleton \(\{ i\} \) — coincides exactly with the event that the special coordinate takes the value \(i\).

Fix a positive integer \(n\), and consider the hard distribution on the sample space conditioned on the event that the generated input pair \((X,Y)\) is disjoint. Writing \(T \in \{ 0,1,\dots ,n-1\} \) for the special coordinate of a sample, then for every index \(i \in \{ 0,1,\dots ,n-1\} \) the conditional probability that \(T = i\) equals \(\tfrac {1}{n}\); that is, the special coordinate remains uniformly distributed after conditioning on disjointness.

Consider the hard distribution on samples \(\omega \), each of which determines Alice’s input set \(X(\omega )\) and Bob’s input set \(Y(\omega )\), and let \(D\) be the disjointness event \(\{ \omega : X(\omega ) \cap Y(\omega ) = \varnothing \} \). Under the distribution obtained by conditioning the hard distribution on \(D\), almost every sample belongs to \(D\); that is, with respect to the conditioned measure, the sets \(X(\omega )\) and \(Y(\omega )\) are disjoint almost surely.

Fix \(n \ge 1\), and consider a sample from the hard distribution: a special coordinate \(T \in \{ 1,\dots ,n\} \), bits \(x_T, y_T \in \{ 0,1\} \) at that coordinate, and for every coordinate a label drawn from \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} \) that fixes the two players’ bits away from \(T\). This sample determines Alice’s set \(X = \{ \, i : \text{Alice's bit at } i = 1\, \} \) and Bob’s set \(Y = \{ \, i : \text{Bob's bit at } i = 1\, \} \). If Bob’s bit at the special coordinate satisfies \(y_T = 0\), then \(X\) and \(Y\) are disjoint.

Let \(n \ge 1\), and let \(b_x, b_y \in \{ \mathrm{false}, \mathrm{true}\} \) be prescribed bits that are not both \(\mathrm{true}\). Then every hard-distribution sample whose special coordinate carries Alice’s bit \(b_x\) and Bob’s bit \(b_y\) generates a disjoint input pair: the special-bits event for \((b_x, b_y)\) is contained in the event that Alice’s set \(X\) and Bob’s set \(Y\) are disjoint.

Fix \(n \ge 1\) and consider a hard-distribution sample \(\omega \): a distinguished coordinate \(T \in \{ 1,\dots ,n\} \), two special bits \(x_T, y_T \in \{ 0,1\} \), and, at every coordinate, a disjoint coordinate-type (neither, left-only, or right-only) that determines Alice’s and Bob’s bits there. If both special bits vanish, \(x_T = 0\) and \(y_T = 0\), then Alice’s input set \(X(\omega )\) and Bob’s input set \(Y(\omega )\) are disjoint. Equivalently, the event that both special-coordinate bits are zero is contained in the event that the generated input pair is disjoint.

Fix \(n \ge 1\), and consider a sample drawn uniformly from the finite space consisting of a distinguished coordinate \(T \in \{ 0,\dots ,n-1\} \), two special bits \(x_T, y_T \in \{ 0,1\} \), and, for every coordinate, an independent label from \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} \); these data determine Alice’s set \(X = \{ i : x_i = 1\} \) and Bob’s set \(Y = \{ i : y_i = 1\} \), where at the coordinate \(T\) the two bits are \(x_T\) and \(y_T\) and at every other coordinate they are read off the label (with \(\text{neither}\mapsto (0,0)\), \(\text{leftOnly}\mapsto (1,0)\), \(\text{rightOnly}\mapsto (0,1)\)). Conditioning this uniform measure on the event that \(X\) and \(Y\) are disjoint, the conditional probability of the event \(x_T = 0\) and \(y_T = 0\) is exactly \(\tfrac {1}{3}\).

Consider the hard distribution on samples \(\omega \), conditioned on the event that Alice’s set and Bob’s set are disjoint. Let \(b_x, b_y \in \{ 0,1\} \) be a pair of prescribed values that are not both \(1\). Then the probability, under this conditioned distribution, that the special coordinate \(T\) carries Alice’s bit equal to \(b_x\) and Bob’s bit equal to \(b_y\) is exactly \(\tfrac {1}{3}\).

Fix a positive integer \(n\), and draw a point of the hard-distribution sample space uniformly at random, then condition on the event that Alice’s and Bob’s generated input sets are disjoint. Under this conditional distribution, the probability that Bob’s bit at the special coordinate \(T\) equals \(\mathrm{false}\) is exactly \(2/3\).

Fix a positive integer \(n\), and work on the finite sample space of hard samples on \(n\) coordinates, equipped with its ambient counting measure. Let \(\mu \) be the measure obtained by conditioning this counting measure first on the disjointness event—that Alice’s input set and Bob’s input set are disjoint—and then on the event that Bob’s bit at the special coordinate equals \(\mathrm{false}\). Then \(\mu \) is a probability measure; equivalently, \(\mu \) assigns total mass \(1\) to the whole sample space.

Fix a positive integer \(n\) and a Boolean value \(b\), and work on the finite sample space of hard-distribution samples over \(n\) coordinates. Form the probability distribution obtained by taking the uniform hard distribution, conditioning on the disjointness event that Alice’s set \(X\) and Bob’s set \(Y\) are disjoint, and conditioning again on Bob’s special bit \(y_T\) taking the value \(\mathrm{false}\). Under this distribution, the probability that Alice’s special bit \(x_T\) equals \(b\) is exactly \(\tfrac {1}{2}\).

Let \(n \ge 1\), and write \(\mathcal{C} = \{ \text{neither}, \text{left-only}, \text{right-only}\} \) for the three-element type of disjoint coordinates. Consider the hard distribution on samples conditioned on the event that the generated input pair of sets is disjoint. For every point \(z\) of the product space \(\{ 1,\dots ,n\} \times \bigl(\{ 1,\dots ,n\} \to \mathcal{C}\bigr) \times \mathcal{C}\), the conditional probability that a sample’s disjoint model — namely the triple consisting of its special coordinate, its generated disjoint coordinate-pair vector, and the ignored value at the special coordinate — equals \(z\) is exactly

Since this value is independent of \(z\) and equals the reciprocal of the cardinality of the product space, the disjoint model pushes the conditioned distribution forward to the uniform distribution on that space.

Fix a positive integer \(n\), an index \(i \in \{ 0, 1, \dots , n-1\} \), and a function \(\mathrm{coords}\) assigning to each index in \(\{ 0, 1, \dots , n-1\} \) one of the three disjointness labels *neither*, *leftOnly*, or *rightOnly*. Then there are exactly three triples \((a, f, c)\), where \(a\) is an index, \(f\) is such a labelling function, and \(c\) is a single disjointness label, subject to the constraints \(a = i\) and \(f = \mathrm{coords}\).

Fix a positive integer \(n\), and let \(\mathcal{D}\) be the three-element set of disjoint coordinate types, each coordinate belonging to neither player’s set, to Alice’s set only, or to Bob’s set only. Under the hard distribution conditioned on the generated input pair being disjoint, the joint law of the special coordinate together with the generated disjoint coordinate-pair vector is uniform: for every index \(i \in \{ 1, \dots , n\} \) and every assignment \(c \colon \{ 1, \dots , n\} \to \mathcal{D}\), the probability that the special coordinate equals \(i\) and the generated coordinate-pair vector equals \(c\) is exactly

Fix a positive integer \(n\), and consider length-\(n\) vectors whose entries are disjoint coordinates, each drawn from the three-element type \(\{ \text{neither}, \text{leftOnly}, \text{rightOnly}\} \). Then the uniform probability law on the set of all such vectors coincides with the product measure of \(n\) independent copies of the uniform law on a single disjoint coordinate.

Let \(n\) be a positive integer, and equip the finite set of functions \(x\colon \{ 0,1,\dots ,n-1\} \to \{ \text{neither},\text{leftOnly},\text{rightOnly}\} \) with the uniform probability law (each of the \(3^n\) such functions is equally likely). Then the coordinate maps \(x \mapsto x(i)\), for \(i = 0,1,\dots ,n-1\), are mutually independent random variables.

Fix a positive integer \(n\) and a coordinate index \(i \in \{ 0, 1, \dots , n-1\} \), and consider any assignment \(c = (c_0, \dots , c_{n-1})\) of a disjointness value to each coordinate, where each \(c_k\) carries Alice’s bit \(x_k\) and Bob’s bit \(y_k\). Then Alice’s fixed-coordinate conditioning at \(i\) — the pair whose first component holds \(x_j\) for \(j \lt i\) and \(\mathrm{false}\) elsewhere, and whose second component holds \(y_j\) for \(j \ge i\) and \(\mathrm{false}\) elsewhere — coincides with the result of first forming the single bit vector \(w\) with \(w_k = x_k\) for \(k \lt i\) and \(w_k = y_k\) for \(k \ge i\), and then recoding \(w\) into the padded pair \(\bigl(\, j \mapsto w_j \text{ if } j \lt i \text{ else } \mathrm{false},\ \ j \mapsto w_j \text{ if } i \le j \text{ else } \mathrm{false}\, \bigr)\). The two constructions agree as functions of the coordinate assignment.

Fix \(n \ge 1\) and an index \(i \in \{ 0,\dots ,n-1\} \), and consider the map that sends a bit-vector \(b \colon \{ 0,\dots ,n-1\} \to \{ 0,1\} \) to the pair of bit-vectors \((u, v)\) obtained by splitting \(b\) at coordinate \(i\): namely \(u(j) = b(j)\) for \(j \lt i\) and \(u(j) = 0\) otherwise, while \(v(j) = b(j)\) for \(j \ge i\) and \(v(j) = 0\) otherwise. This map is injective.

Fix \(n \ge 1\), an index \(i \in \{ 0, 1, \dots , n-1\} \), and a target bit-string \(b \colon \{ 0,1,\dots ,n-1\} \to \{ \mathrm{false},\mathrm{true}\} \). For a configuration \(c\) that assigns to each coordinate one of the three disjointness states, write \(A_i(c) \in \{ \mathrm{false},\mathrm{true}\} ^n\) for Alice’s fixed conditioning string and \(A_{i,k}(c)\) for its value at coordinate \(k\). Then the set of configurations whose conditioning string equals \(b\) exactly is the intersection over all coordinates of the sets on which each individual conditioning bit is correct:

Each coordinate of a disjointness instance takes one of three values — belonging to neither player, to the left player (Alice) only, or to the right player (Bob) only — and one records Alice’s bit, equal to \(1\) exactly on the left-only value, and Bob’s bit, equal to \(1\) exactly on the right-only value. Fix a positive integer \(n\), indices \(i, k \in \{ 0, 1, \dots , n-1\} \), and a bit \(b \in \{ 0,1\} \), and form the coordinate value that is left-only if \(k \lt i\) and \(b = 1\), right-only if \(k \ge i\) and \(b = 1\), and neither in every case where \(b = 0\). Then reading Alice’s bit of this value when \(k \lt i\), and Bob’s bit of it when \(k \ge i\), returns \(b\).

Fix a positive integer \(n\), and draw a random vector of \(n\) disjoint-coordinate symbols by sampling each of its \(n\) coordinates independently and uniformly from the three values *neither*, *left-only*, and *right-only*. For a coordinate index \(k\) write \(X_k\) for Alice’s bit at that coordinate (equal to \(1\) exactly when the \(k\)-th symbol is *left-only*) and \(Y_k\) for Bob’s bit (equal to \(1\) exactly when it is *right-only*). Then for every pair of indices \(i,k \in \{ 0,1,\dots ,n-1\} \) and every bit \(b \in \{ 0,1\} \), the event that Alice’s conditioning bit at coordinate \(k\) under cut-off \(i\) — namely \(X_k\) when \(k\lt i\) and \(Y_k\) otherwise — takes the value \(b\) has strictly positive probability under this uniform law.

Fix a positive integer \(n\) and an index \(i \in \{ 0,\dots ,n-1\} \), and let the coordinate vector \(c = (c_0,\dots ,c_{n-1})\) be drawn from the uniform law on \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} ^{n}\). For each coordinate \(k\) form the pair \(\bigl(R_i(k,c),\, A_i(k,c)\bigr)\), where \(A_i(k,c)\) is Alice’s conditioning bit — the \(X\)-bit of \(c_k\) when \(k\lt i\) and the \(Y\)-bit of \(c_k\) when \(k\ge i\) — and \(R_i(k,c)\) is the corresponding residual bit — the \(Y\)-bit of \(c_k\) when \(k\lt i\), the \(X\)-bit of \(c_k\) when \(k=i\), and \(\mathrm{false}\) when \(k\gt i\). Then the family of these \(\{ 0,1\} \times \{ 0,1\} \)-valued pairs, indexed by \(k \in \{ 0,\dots ,n-1\} \), is mutually independent.

Fix a positive integer \(n\), a coordinate \(i \in \{ 0,1,\dots ,n-1\} \), and a bit vector \(b \colon \{ 0,\dots ,n-1\} \to \{ 0,1\} \). Draw a coordinate vector uniformly from the \(n\)-fold product of the three-element set whose members mark a coordinate as belonging to neither party, to Alice only, or to Bob only; write \(X_k = 1\) exactly when coordinate \(k\) belongs to Alice only and \(Y_k = 1\) exactly when it belongs to Bob only. Condition on the event that Alice’s conditioning bit vector — whose \(k\)-th entry is \(X_k\) when \(k \lt i\) and \(Y_k\) when \(k \ge i\) — equals \(b\). Under this conditional law, Alice’s bit \(X_i\) at coordinate \(i\) and the vector of Bob’s earlier bits, equal to \(Y_j\) for each \(j \lt i\) and to \(0\) at every \(j \ge i\), are independent random variables.

Fix \(n \ge 1\) and draw a random vector \(C = (C_1, \dots , C_n)\) whose \(n\) coordinates are independent, each uniform over the three states of a disjoint coordinate-pair: one in which both parties’ bits are \(0\), one carrying only Alice’s bit, and one carrying only Bob’s bit. For each coordinate \(k\) let \(X_k\) be Alice’s bit, equal to \(1\) exactly in the second state, and let \(Y_k\) be Bob’s bit, equal to \(1\) exactly in the third; in particular \(X_k\) and \(Y_k\) are never simultaneously \(1\). Fix a coordinate \(i\) and form Alice’s conditioning vector \(A = (A_1, \dots , A_n)\) by setting \(A_k = X_k\) for \(k \lt i\) and \(A_k = Y_k\) for \(k \ge i\). Then the conditional mutual information between \(X_i\) and the tuple \((Y_k)_{k \lt i}\) of Bob’s bits at the coordinates strictly before \(i\), given \(A\), vanishes:

Fix a positive integer \(n\) and draw \(C = (C_1,\dots ,C_n)\) uniformly at random from \(\{ \text{neither},\text{leftOnly},\text{rightOnly}\} ^n\), so that the \(n\) coordinates are independent and each is uniform on the three possibilities. For each index \(j\) set Alice’s bit \(X_j = \mathbf{1}[C_j = \text{leftOnly}]\) and Bob’s bit \(Y_j = \mathbf{1}[C_j = \text{rightOnly}]\). Then for every coordinate \(i\), the conditional mutual information, taken under this uniform law, between Alice’s bit at \(i\) and Bob’s bits strictly before \(i\), given the pair consisting of Alice’s bits strictly before \(i\) and Bob’s bits from \(i\) onward, vanishes:

Fix a positive integer \(n\) and a coordinate \(i \in \{ 1,\dots ,n\} \). Under the hard distribution conditioned on the event that the generated input pair is disjoint, Alice’s bit at coordinate \(i\) agrees almost everywhere with the \(x\)-bit of the \(i\)-th entry of the disjoint coordinate-vector generated from the sample; that is, the two functions \(\omega \mapsto \)

Fix a coordinate index \(i\). Consider the hard distribution on samples \(\omega \) conditioned on the event that the generated input pair is disjoint. Then, almost surely with respect to this conditioned distribution, the two prefix functions on coordinates agree: the map sending each \(j\) to Bob’s bit \(\mathrm{yBit}(\omega , j)\) when \(j \lt i\) and to \(\mathrm{false}\) otherwise coincides with the map sending each \(j\) to Bob’s bit at coordinate \(j\) of the generated disjoint coordinate vector of \(\omega \) when \(j \lt i\) and to \(\mathrm{false}\) otherwise.

Fix a positive integer \(n\) and a coordinate \(i \in \{ 0, 1, \dots , n-1\} \), and equip the sample space of the hard distribution with the measure obtained by conditioning on the event that the generated pair of input sets is disjoint. There are two ways to record Alice’s conditioning information at coordinate \(i\) from a sample \(\omega \): directly, as the pair \(\big(X_{\lt i}(\omega ),\, Y_{\ge i}(\omega )\big)\) formed from the sample’s own Alice-prefix and Bob-suffix bits; and indirectly, by first forming the generated disjoint coordinate-pair vector of \(\omega \) and then extracting the coordinate-vector conditioning \(\big(\)

Fix an integer \(n \ge 1\), and consider the hard distribution on samples conditioned on the event that the generated input pair \((X,Y)\) is disjoint. Under this conditional law, the pair consisting of the special coordinate \(T \in \{ 1,\dots ,n\} \) and the generated disjoint coordinate vector \(c \colon \{ 1,\dots ,n\} \to \{ \text{neither}, \text{leftOnly}, \text{rightOnly}\} \) has the same distribution as a pair of independent random variables in which \(T\) is uniform on \(\{ 1,\dots ,n\} \) and \(c\) is uniform on all \(3^{n}\) coordinate vectors. In particular \(T\) and \(c\) are independent, and each is uniformly distributed on its range.

Fix a positive integer \(n\), and consider pairs \((t, c)\) in which \(t\) is an element of \(\{ 0, 1, \dots , n-1\} \) and \(c\) is a disjoint-coordinate vector, that is, a function assigning to each of the \(n\) coordinates one of the three values "neither", "left only", or "right only". Draw \((t, c)\) from the product of the uniform law on the special coordinate and the uniform law on disjoint-coordinate vectors. Then the second component \(c\) of this pair is identically distributed to a disjoint-coordinate vector drawn directly from the uniform law on disjoint-coordinate vectors; equivalently, the second marginal of the product law coincides with that uniform law.

Fix a positive integer \(n\), and consider the hard distribution on samples conditioned on the disjointness event — the event that the generated input pair \((X,Y)\) is disjoint. Under this conditioned distribution, the generated disjoint coordinate vector, viewed as a function \(\{ 1,\dots ,n\} \to \{ \text{neither}, \text{leftOnly}, \text{rightOnly}\} \), is identically distributed to a coordinate vector drawn from the uniform law on all such functions; that is, its law is exactly the uniform distribution over the \(3^n\) possible disjoint coordinate vectors.

Fix a positive integer \(n\) and an index \(i \in \mathrm{Fin}\, n\), and let \(\mathrm{DisjointCoordinate} = \{ \text{neither}, \text{leftOnly}, \text{rightOnly}\} \) be the three-element type. On the product space \(\mathrm{Fin}\, n \times (\mathrm{Fin}\, n \to \mathrm{DisjointCoordinate})\) form the product of the uniform law on the special coordinate and the uniform law on disjoint-coordinate vectors, and condition it on the event that the first coordinate equals \(i\). Then under this conditional law the second coordinate is identically distributed to a uniformly random disjoint-coordinate vector.

Fix a positive integer \(n\) and a coordinate \(i \in \{ 0, 1, \dots , n-1\} \). Consider two ways of producing a triple. First, draw a hard-distribution sample conditioned on the event that Alice’s input set \(X\) and Bob’s input set \(Y\) are disjoint, and record the triple \(\bigl(x_i,\; Y_{\lt i},\; (X_{\lt i}, Y_{\ge i})\bigr)\), where \(x_i\) is Alice’s bit at coordinate \(i\), \(Y_{\lt i}\) is Bob’s bit vector on the coordinates \(j \lt i\) (set to \(\mathrm{false}\) elsewhere), \(X_{\lt i}\) is Alice’s bit vector on the coordinates \(j \lt i\), and \(Y_{\ge i}\) is Bob’s bit vector on the coordinates \(j \ge i\) (each padded with \(\mathrm{false}\) outside its range). Second, draw a vector of disjoint coordinates uniformly at random and form the same triple from Alice’s and Bob’s bits read off that vector. Then these two random triples are identically distributed.