A hypergraph on the vertex set \(\mathrm{Fin}\, n\) is a finite collection of subsets of \(\mathrm{Fin}\, n\), modelled as \(\mathtt{Finset}\, (\mathtt{Finset}\, (\mathrm{Fin}\, n))\). Its elements are called edges (or constraints).

A hypergraph \(H\) on \(\mathrm{Fin}\, n\) is \(q\)-uniform when every edge \(C \in H\) has exactly \(q\) vertices, i.e. \(\left\lvert C\right\rvert = q\).

A hypergraph \(H\) is a matching when its edges are pairwise disjoint: for all \(C, C' \in H\) with \(C \neq C'\), the sets \(C\) and \(C'\) are disjoint.

The degree of a vertex set \(Q \subseteq \mathrm{Fin}\, n\) in a hypergraph \(H\) is the number of edges of \(H\) containing \(Q\):

A hypergraph \(H\) satisfies the pair-degree bound \(d\) when every pair of distinct vertices \(u \neq v\) lies in at most \(d\) edges, i.e. \(\deg _H(\{ u,v\} ) \le d\).

The predicate on an integer \(x\) stating that \(x\) is a sign value, i.e. \(x = 1\) or \(x = -1\). Assignments used below take values in this set.

The structural data of a \((3,\delta ,\varepsilon )\)-normally decodable code with message length \(k\) and block length \(n\): for each message index \(i : \mathrm{Fin}\, k\) a hypergraph \(H_i\) on \(\mathrm{Fin}\, n\) which is \(3\)-uniform and a matching, together with real parameters \(\delta \gt 0\) and \(\varepsilon \gt 0\) and the density requirement \(\delta n \le \left\lvert H_i\right\rvert \) for every \(i\).

For a normal form code \(L\), the hypergraph obtained as the union of all its matchings, \(\bigcup _{i : \mathrm{Fin}\, k} H_i\), viewed as a hypergraph on \(\mathrm{Fin}\, n\).

For a normal form code \(L\), the total number of constraints

For an assignment \(x : \mathrm{Fin}\, n \to \mathbb {Z}\) and a set \(C \subseteq \mathrm{Fin}\, n\), the product

For a normal form code \(L\), a message \(b : \mathrm{Fin}\, k \to \mathbb {Z}\) and an assignment \(x : \mathrm{Fin}\, n \to \mathbb {Z}\), the real-valued XOR instance

where \(m\) is the total number of constraints of \(L\).

The value \(\mathrm{val}(\psi _b)\) of the XOR instance associated with a message \(b\), defined as the supremum of \(\psi _b(x)\) over all assignments \(x : \mathrm{Fin}\, n \to \mathbb {Z}\) taking values in \(\{ -1,1\} \).

The doubled vertex set \(\mathrm{Fin}\, n \times \mathrm{Fin}\, 2\), carrying two labelled copies of each vertex of \(\mathrm{Fin}\, n\).

The map sending a vertex \(u : \mathrm{Fin}\, n\) to its first copy \(u^{(1)} = (u,0)\) in the double-copy ground set.

The map sending a vertex \(u : \mathrm{Fin}\, n\) to its second copy \(u^{(2)} = (u,1)\) in the double-copy ground set.

The image \(C^{(1)}\) of a set \(C \subseteq \mathrm{Fin}\, n\) under the injection \(u \mapsto u^{(1)}\), a subset of the double-copy ground set.

The image \(C^{(2)}\) of a set \(C \subseteq \mathrm{Fin}\, n\) under the injection \(u \mapsto u^{(2)}\), a subset of the double-copy ground set.