Since U \in \Cliff(d), by Definition 6.55 of the Clifford group, there exist functions f \colon \mathbb{Z}^2 \to \mathbb{Z}^2 and g \colon \mathbb{Z}^2 \to \mathbb{R} such that U D_{\p} U^\dagger = e^{ig(\p)} D_{f(\p)} for all \p \in \mathbb{Z}^2. The proof proceeds in three stages:

1. f is additive modulo d,

2. the linear part of f has determinant 1 modulo d,

3. the phase e^{ig(\p)} must be an inner-product phase \omega^{\langle\bchi, F\p\rangle}.

To show that f is additive modulo d, we compute (U D_{\p} U^\dagger)(U D_{\q} U^\dagger) in two different ways. On one hand, we first use Definition 6.55 twice and then apply Lemma 5.48 to get (U D_{\p} U^\dagger)(U D_{\q} U^\dagger) = e^{ig(\p)} D_{f(\p)} \cdot e^{ig(\q)} D_{f(\q)} = e^{i(g(\p)+g(\q))} \tau^{\langle f(\p),f(\q)\rangle} D_{f(\p)+f(\q)}. On the other, we first use U^\dagger U = I and then apply Lemma 5.48 followed by Definition 6.55 to get U(D_{\p} D_{\q})U^\dagger = U(\tau^{\langle \p,\q\rangle} D_{\p+\q})U^\dagger = \tau^{\langle \p,\q\rangle} e^{ig(\p+\q)} D_{f(\p+\q)}. Equating both expressions gives e^{i(g(\p)+g(\q))} \tau^{\langle f(\p),f(\q)\rangle} D_{f(\p)+f(\q)} = \tau^{\langle \p,\q\rangle} e^{ig(\p+\q)} D_{f(\p+\q)}. Thanks to Lemma 5.53, we can compare the subscripts of D on both sides and get f(\p+\q) \equiv f(\p)+f(\q) \pmod{d}. In other words, f modulo d is an additive map \mathbb{Z}_d^2 \to \mathbb{Z}_d^2. This means it can be represented by a matrix: f(\p) = F'\p + d\,h(\p) for some integer matrix F' and function h \colon \mathbb{Z}^2 \to \mathbb{Z}^2. Thanks to Lemma 5.50 we can drop the second term and write D_{f(\p)} = D_{F'\p}. We conclude that U acts on displacement operators by conjugation as U D_{\p} U^\dagger = e^{ig'(\p)} D_{F'\p} for some phase function g'.

Repeating the above argument for e^{ig'(\p)} D_{F'\p} and comparing the phases gives e^{i(g'(\p+\q) - g'(\p) - g'(\q))} \tau^{\langle \p,\q\rangle - \langle F'\p,F'\q\rangle} = 1. Recall from Lemma 3.3 that the symplectic inner product \braket{\p,\q} is antisymmetric in \p,\q ∈ ℤ_d^2. Since g'(\p+\q) - g'(\p) - g'(\q) is symmetric, swapping \p and \q and then dividing the above with the resulting equation gives \tau^{2(\langle \p,\q\rangle - \langle F'\p,F'\q\rangle)} = 1 for all \p,\q ∈ ℤ_d^2. Using \omega = \tau^2 from Lemma 2.11, \omega^{\langle \p,\q\rangle - \langle F'\p,F'\q\rangle} = 1. Since \langle F'\p, F'\q\rangle = (\det F')\langle \p,\q\rangle by Lemma 3.9, this forces \det F' \equiv 1 \pmod{d}. Since d is prime, there exists F \in \SL(2,\mathbb{Z}_d) with F \equiv F' \pmod{d}, and D_{F\p} = D_{F'\p} for all \p.

From Lemma 5.52, we have D_{\p}^d = I. Conjugating by U gives e^{idg'(\p)} D_{F\p}^d = I, so e^{idg'(\p)} = 1. Therefore e^{ig'(\p)} = \omega^{\tilde{g}(\p)} for some function \tilde{g} \colon \mathbb{Z}^2 \to \mathbb{Z}_d, and we have U D_{\p} U^\dagger = \omega^{\tilde{g}(\p)} D_{F\p}.

Applying the above argument once more gives \omega^{\tilde{g}(\p+\q) - \tilde{g}(\p) - \tilde{g}(\q)} \tau^{\langle \p,\q\rangle - \langle F\p,F\q\rangle} = 1. Since F \in \SL(2,\mathbb{Z}_d), we have \langle F\p,F\q\rangle = (\det F)\langle \p,\q\rangle = \langle \p,\q\rangle by Lemma 3.9, so \tilde{g}(\p+\q) \equiv \tilde{g}(\p)+\tilde{g}(\q) \pmod{d}. Any additive function \mathbb{Z}^2 \to \mathbb{Z}_d has the form \tilde{g}(\p) = \langle\bchi', \p\rangle for some fixed \bchi' \in \mathbb{Z}_d^2. Setting \bchi = F\bchi' and using Lemma 3.10, we conclude that U D_{\p} U^\dagger = \omega^{\langle\bchi, F\p\rangle} D_{F\p} for all \p \in \mathbb{Z}^2.