# Stabilizer codes: why is $N(S)/S$ homomorphic to the Pauli group on $k$ qubits

Given an abelian subgroup $$S$$ of the Pauli group on $$n$$ qubits with $$r$$ independent generators we obtain an $$2^{n-r}$$-dimensional subspace stabilized by $$S$$. By picking a basis for this space, it is easy to build a representation of the Pauli group on $$k$$ qubits generated by some set of matrices $$\overline{X_i}, \overline{Z_i}$$. However, I fail to see how to do so in a way that ensures that $$\overline{X_i}, \overline{Z_i}$$ are Pauli matrices in the original basis. The common way to build these logicals is to consider the quotient $$\mathcal{N}(S)/S$$, and note that it corresponds to the Pauli group on $$k$$ qubits, but I cannot quite prove it.

To answer your first question, as to why $$N(S)/S \cong P_{n-r}$$: this is hinted at in Gottesman's lecture notes (Section 3.4, https://arxiv.org/abs/0904.2557), and more detail is given on Physics SE at https://physics.stackexchange.com/questions/261030/size-of-the-quotient-of-normalizer-by-the-stabilizer-in-the-pauli-group (where the answerer says they are following Gottesman's lecture notes). There's also a fuller proof in his unpublished textbook, which I'll sketch here. I'll follow his notation and use $$c(p, q) = 0$$ to mean two Paulis $$p$$ and $$q$$ commute, or $$c(p, q) = 1$$ if they anti-commute. Also recall that a Pauli $$p = i^k (X_1^{a_1} Z_1^{b_1} \otimes \ldots \otimes X_n^{a_n} Z_n^{b_n}) \in P_n$$ can be represented (up to a sign) by a $$2n$$-bit vector $$(a_1, \ldots, a_n, b_1, \ldots, b_n)$$.
The key lemma is the following: given independent Paulis $$\{p_1, \ldots, p_m\}$$ and $$m$$ bits $$\{c_1, \ldots, c_m\}$$, there exist $$2^{2n-m}$$ Paulis $$q$$ such that $$\forall j$$ we have $$c(p_j, q) = c_j$$. A proof sketch is that, when converting to vector representations, each condition $$c(p_j, q) = c_j$$ is a linear constraint. Since the Paulis were independent, this gives a non-singular system of $$m$$ linear equations in a $$2n$$-dim binary vector space. This has $$2^{2n-m}$$ solutions.
Then to prove that $$N(S)/S \cong P_{n-r}$$, we can repeatedly pick cosets $$\overline{x_j}$$ and $$\overline{z_j}$$ in $$N(S)/S$$ whose representatives satisfy the commutativity relations $$c(x_j, x_k) = 0, c(z_j, z_k) = 0$$ and $$c(x_j, z_j) = \delta_{jk}$$. This will give us an inclusion of $$P_{n-r}$$ in $$N(S)/S$$. But also we can show $$|N(S)/S| = |P_{n-r}|$$ (see e.g. the Physics SE answer), so inclusion must mean isomorphism.
So suppose we've chosen some independent set of $$\overline{x_j}$$ and $$\overline{z_j}$$ cosets and we want to pick one more. We can pick a representative for it; this must be in $$N(S)$$, so must commute with all $$r$$ stabilizer generators. It must also commute/anti-commute as desired with the already-chosen coset representatives $$x_j$$ and $$z_j$$. By the lemma above, we can find a Pauli that satisfies these linear constraints.
A question about the rest of your post: almost certainly my fault, but I'm not quite following what you mean about building a representation of $$P_k$$ generated by $$\overline{X_j}$$ and $$\overline{Z_j}$$ such that these are Pauli matrices in the original basis. If you're still curious about this, maybe I can ask more questions and try and help. What's $$k$$ here, for example?