One fixed-alphabet Dinur transformation

Let ${\mathrm{\Sigma }}_{\star }$ denote the fixed alphabet of $66$ symbols produced by the alphabet reduction of Fixed-alphabet reduction with constant gap retention, that is, ${\mathrm{\Sigma }}_{\star }=\{B(0),B(1)\}\bigsqcup \{0,1{\}}^6,$ and let $W_{\star }=\mid {\mathrm{\Sigma }}_{\star }\mid =66\ge 2$.

Fix the constants of the gap-amplification step of A complete uniform graph gap-amplification step at the input alphabet ${\mathrm{\Sigma }}_{\star }$: its threshold $t_0$ (which depends only on $W_{\star }$ and on the absolute constants of that theorem), its output alphabet ${\mathrm{\Sigma }}_t$, its output degree bound $d_t$, its blowup $C_t$, its gap map $g_t(\epsilon )=\beta \sqrt{t}\min (\epsilon ,c\mathrm{/}t)$ and its completeness and edgeless-input clauses. For every integer $t\ge t_0$, denoted in the sequel by $t$ being in the transformation domain, define, for every finite binary constraint graph $G$ over ${\mathrm{\Sigma }}_{\star }$ whose relation tables are explicit and whose degree is arbitrary, $T_t(G):=A_{{\mathrm{\Sigma }}_t}(R_t(G)),$ where:

• $R_t(G)$ is the output of the published complete uniform gap-preserving step of A complete uniform graph gap-amplification step applied to $G$: first the degree reduction, then the local-view powering. It is a binary constraint graph over the finite alphabet ${\mathrm{\Sigma }}_t$ with at most $C_t\mid E(G)\mid$ ordinary edges, and it is edgeless whenever $G$ is edgeless;
• ${\mathrm{\Sigma }}_t$ has $\mid {\mathrm{\Sigma }}_t\mid =\mid {\mathrm{\Sigma }}_{\star }{\mid }^{(2D{)}^R}$ symbols for the absolute constant $D=387$ and the view radius $R=t+\lceil \sqrt{t}\rceil$, so $\mid {\mathrm{\Sigma }}_t\mid \ge 2$ for every $t$ in the domain;
• $A_{{\mathrm{\Sigma }}_t}$ is the alphabet reduction of Fixed-alphabet reduction with constant gap retention instantiated at the input alphabet ${\mathrm{\Sigma }}_t$, a deterministic map sending finite ${\mathrm{\Sigma }}_t$-graphs to finite binary constraint graphs over ${\mathrm{\Sigma }}_{\star }$ again.

Thus $T_t$ is a map from finite binary constraint graphs over ${\mathrm{\Sigma }}_{\star }$ to finite binary constraint graphs over ${\mathrm{\Sigma }}_{\star }$, defined exactly for integers $t\ge t_0$. It retains the input edge multiplicities and relation orientations throughout: both stages enumerate their relation tables explicitly and copy edge records, one per occurrence, without merging parallel edges or reversing endpoint order. It is deterministic and polynomial time in the bit length of the explicit encoding of its input, and it satisfies $\mid E(T_t(G))\mid \le 6M_{{\mathrm{\Sigma }}_t}{C}_t\mid E(G)\mid$ for the constant $M_{{\mathrm{\Sigma }}_t}$ of Alphabet reduction controls explicit size and degree attached to the input alphabet ${\mathrm{\Sigma }}_t$, while every output degree is bounded by the constant $6M_{{\mathrm{\Sigma }}_t}{d}_t$, which depends only on ${\mathrm{\Sigma }}_{\star }$ and $t$. By the two cited edgeless clauses, $T_t$ maps an edgeless graph to the edgeless graph over ${\mathrm{\Sigma }}_{\star }$. The definition asserts nothing about unsatisfaction; the amplification and completeness properties of $T_t$ are separate results.

The alphabet is fixed before the powering parameter is chosen: ${\mathrm{\Sigma }}_{\star }$ is used as the input alphabet of $R_t$, the intermediate alphabet ${\mathrm{\Sigma }}_t$ is a function of $t$ alone, and the alphabet reduction returns to the same absolute alphabet ${\mathrm{\Sigma }}_{\star }$. This is what lets the same map $T_t$ be iterated without changing the alphabet between rounds; the later iteration fixes one integer $t$ in the domain once and for all.

The construction is choice-free. The degree reduction, the powering, the edge-circuit construction and the alphabet reduction are all deterministic finite constructions, and no selection from a varying family of nonempty sets occurs.