# Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization
## 3 The Parallelization Theorems  
Suppose a complex \(K\) is assigned a gradient vector field \(V\) using an algorithm \(\alpha\). Suppose further that \(U\) and \(W\) are two subcomplexes of \(K\) that form a covering of \(K\). In particular, there are vector fields \(V_{\alpha}(K)\), \(V_{\alpha}(U[i])\), and \(V_{\alpha}(W[i])\) for various values of \(i\). Theorem 3.1: _If \(\alpha\) is a uniformly \(k\)-local algorithm for some \(k\geq 1\), then_  
\[V_{\alpha}(K)\,=\,(V_{\alpha}(U[k])\cup V_{\alpha}(W[k]))\setminus(V_{\alpha} (U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(U[2k+1]\cap W[2k+1]).\]  
_In slightly different terms,_  
\[V_{\alpha}(K)\,\,\,=\,\,\,(V_{\alpha}(U[k])\cup V_{\alpha}(W[k]))\setminus(V_{ \alpha}(U[k])\setminus V_{\alpha}(U[2k+1]))\setminus(V_{\alpha}(W[k])\setminus V _{\alpha}(W[2k+1])).\]  
The informal idea is this. It is elementary to check that \(V_{\alpha}(K)\) is contained in \(V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\) using that the algorithm \(\alpha\) is uniformly \(k\)-local. Let us refer to the difference as \"mistakes\" in building \(V_{\alpha}(K)\) from the union. We see that for the same reason, \(V_{\alpha}(U[k])\setminus V_{\alpha}(U[2k+1])\) can be viewed as all the mistakes made near the border of \(U[k]\). This set is interpreted as pairs of cells in \(V_{\alpha}(U[k])\) that are not in \(V_{\alpha}(K)\). Similarly, \(V_{\alpha}(W[k])\setminus V_{\alpha}(W[2k+1])\) is the set of mistakes made near the border of \(W[k]\). Since the cells near the borders of the subcomplexes are far enough away in the adjacency relation chains, they do not contain common adjacent cells. The local nature of the algorithm, again, guarantees that no other mistakes are made away from the borders of \(U[k]\) and \(W[k]\). We now give a formal proof. Proof: If the pair \((\sigma\leq\tau)\) is contained in \(V_{\alpha}(K)\), it is placed in this list according to the algorithm \(\alpha\). According to the assumption, this placement is the outcome of inspection of data relevant to \(\alpha\) in \(\sigma[k]\). If \(\sigma\) and \(\tau\) are cells of \(U\), then \(\sigma[k]\) is contained in \(U[k]\). Since \(\alpha\) applied to \(U[k]\) would use the exact same data as \(\sigma[k]=\sigma_{U[k]}[k]\), this proves that \((\sigma\leq\tau)\) is in \(V_{\alpha}(U[k])\). Repeating the argument for \(W\) in place of \(U\), this gives the inclusion \(V_{\alpha}(K)\subset V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\). We now examine \((\sigma\leq\tau)\) in the difference  
\[M=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(K).\]  
Observe that whenever the cell \(\sigma\) is outside of \(W[k]\), it is contained in \(U\). This makes \(\sigma_{K}[k]=\sigma_{U[k]}[k]\), so the outcome of the decision \(\alpha\) makes on the inclusion of \((\sigma\leq\tau)\) in, respectively, \(V_{\alpha}(K)\) and \(V_{\alpha}(U[k])\) is the same. This shows that such \((\sigma\leq\tau)\) is disqualified from \(M\), as it is excluded as part of \(V_{\alpha}(K)\). Our conclusion is that whenever \((\sigma\leq\tau)\) is in \(M\), \(\sigma\) must be in \(W[k]\). A symmetric argument proves that it also must also be in \(U[k]\). The last paragraph proves that our pair of cells \(\sigma\), \(\tau\) is contained in \(U[k+1]\cap W[k+1]\). Therefore, \(\alpha\) uses the same data for placing \((\sigma\leq\tau)\) in either \(V_{\alpha}(U[2k+1]\cap W[2k+1])\) or \(V_{\alpha}(K)\). This allows us to rewrite  
\[M=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(U[2k+1]\cap W[2k+1 ]).\]  
This gives the first formula. Let \(M_{U}=V_{\alpha}(U[k])\setminus V_{\alpha}(K)\) and \(M_{W}=V_{\alpha}(W[k])\setminus V_{\alpha}(K)\), so that \(M=M_{U}\cup M_{W}\). The same argument as above shows that  
\[M_{U}=V_{\alpha}(U[k])\setminus V_{\alpha}(U[2k+1]),\]  
and similarly  
\[M_{W}=V_{\alpha}(W[k])\setminus V_{\alpha}(W[2k+1]).\]  
Now  
\[V_{\alpha}(K)=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus(M_{U}\cup M_{W})\]gives the second formula.