mark $\circ$ only for the sake readability.

The following claim is immediate from the definition of ${\psi}$.

\[claim:mark to infl\] Fix a string $x \in {\{0,1\}^{n}}$. Let $M {\subseteq}[n]$ be the set of marked coordinates in ${{\sf mark}}(x)$. Then,

-   For every $i \in  M$ it holds that ${\psi}(x)_i = x_i$.

-   For every $j \in [n] \setminus M$, the $j^{\text{th}}$ coordinate of ${\psi}(x)$ does not depend on any of the bits $\{x_i\}_{i \in M}$.

We are now ready to prove Theorem \[thm:main\].

Proof of Theorem \[thm:main\] {#sec:finally the proof}
-----------------------------

We first show that ${{\sf maxStretch}}({\psi}) \le 4$. Fix an edge in ${\{0,1\}^{n}}$, that is, take $x \in {\{0,1\}^{n}}$ and $i \in [n]$ such that $x_i = 0$. Our goal is to show that ${{\sf distance}}({\psi}(x), {\psi}(x+e_i)) \leq 4$. Let $y,y' \in {\{0,1,{\sqcup}\}^{n}}$ be the encodings of the chains $C_y, C_{y'}$ that contain $x,x+e_i$ respectively. As mentioned in Section \[sec:the partition\], the output of the algorithm on input $x$ is independent of the order in which the algorithm marks the $10$ pairs. Therefore, given an input $x$, we may perform the marking stage in three steps:

1.  Perform the marking stage on the prefix of $x$ of length $i-1$.

