I'm reading this paper on the element distinctness problem, and I'm having some trouble parsing Claim 2. I've recently been going through The Symmetric Group by Sagan (Chapters 1 and 2 so far).
Here's the premise. For an alphabet $\Sigma$ of size $n$, consider the list of distinct elements $z=(z_1,\dots, z_n)$. The index permutations $\pi\in S_n$ just change the order of lists: $$z_\pi:=\pi z=(z_{\pi^{-1}(1)},\dots, z_{\pi^{-1}(n)}).$$ The alphabet permutations $\tau\in S_\Sigma$ relabel elements in the list: $$z^\tau:=\tau z=(\tau(z_1),\dots, \tau(z_n)).$$
Now we consider the matrices $V^\tau_\pi$ which perform the map $V^\tau_\pi=z^\tau_\pi$. Here's where my questions start, as the the author states "$V$ is isomorphic to the regular representation of $S_n$ and $S_\Sigma$.'' So, I know that the regular representation of $S_n$ is just consists of the algebra $\mathbb C[S_n]$, meaning I need an $S_n$-isomorphism between $S_n$ and $V$, yet I'm unclear on what $V$ is. I'd think it'd be $V=\text{span}\{V^\tau_\pi\mid \pi\in S_n, \tau\in S_\Sigma\}$, but the basis $\{V^\tau_\pi\}$ obviously has more than $n!$ elements, so that led me to believe they're referring to $\{V_\pi^\varepsilon\}$ and $\{V^\tau_\varepsilon\}$, is this correct?
On the other hand, Claim 2 says that $$V\cong \bigoplus_{\lambda\vdash n}\lambda\times \lambda,$$ which led me to the following question: When they say $V\cong \bigoplus_{\lambda\vdash n}\lambda\times \lambda$, is it convention for $\lambda$ to refer to the Specht module $S^\lambda$? Or is that even what they mean? I think it should be more clear why the claim is true when I know the answers to these two questions.
Thanks!