# June 10 Update

Chris and I mostly discussed about how to bound the W1 distance for our lower bound instance. The lower-bound instance we have currently is the following: Let $l$ be an odd number.

* $G_1:$ Create $o$ rings of size $2l$ can connect them with each other by a larger ring (which we call the _outer graph_). This means that from every node, we can land at two different rings. So instead of a regular expander we thought of before, we are connecting it by a "high-girth" graph. Therefore, we have $o$ blocks of length $2l$ rings connected by an outer graph.
* $G_2:$ Create $2o$ rings of size $l$. In each block, we have two disjoint rings connected by the same _outer graph_ as in $G1$.
* Note that in both the instances, the probability of leaving the ring is $(1/2)$ and degree of each node is $4$.

Then, we wanted to compute the Wasserstein distance between the two graphs. Experimentally, the Wasserstein distance seems to converge to some value. We will be done if the value it converges to is $1/\text{poly}(l)$.

To prove the Wasserstein distance formally, Chris proposed the idea of using the dual formulation of the W1 distance and use one of the Legendre polynomial as the "test" function. We did the following calculations:
Let $s$ be the spectrum of $G1$ and $q$ be the spectrum of $G_2$. Let $L_i$ denote the $i$-th Legendre polynomial.The first $(l-1)$ moments of $G_1$ and $G_2$ are same. Therefore, we get that
$$ q-s = c_l L_l + \dots + c_{2l-1} L_{2l-1} + \dots $$
Note that the difference between the $l$-th moment is $= 1/4^l = 1/2^{(2l)} \implies c_l \approx\frac{1}{2^l}$.
This is because $l$ is an odd integer and no odd length random (of length $l$) walk would end up at the starting node in $G_1$ and the only way it ends up on the starting in $G_2$ is by finising the $l$-length cycle.

Similarly, assuming that $o$ is large enough, we get that a lower bound on the different between the $(2l-1)$-th (odd) moment is
$$ \int_{-1}^{1} (q-s) x^{(2l-1)} \mathrm{d}x \geq {{l+l-1}\choose{l}} \cdot \frac{1}{4^{2l-1}} \approx \frac{1}{2^{2l}} .$$
Further note the following identities:
$$ \begin{align}
\int_{-1}^{1} x^{2l-1} L_{2l-1} \mathrm{d}x &\geq \frac{1}{l 2^{2l-1}}\\
\int_{-1}^{1} x^{2l-1} L_l \mathrm{d}x &\geq (0.85)^{2l}
\end{align}$$
Therefore, one way to give an upper bound on the Wasserstein distance is by considering the $L_{2l-1}$ as the test function in the dual formulation. We had hoped that this would imply that $c_{2l-1}$ is $1/\text{poly(l)}$, which is not necessarily the case.

If we can prove that any of the coefficients $c_l,\dots,c_{2l-1},\dots$ are $1/\text{poly(l)}$ large, then we can show an upper bound on the W1 distance. However, that is not clear from the above two identities.

So now I am again experimentally trying to verify is the W1 distance is $1/\text{poly}(l)$.