Adversary Lower Bounds for the Collision \\ and the Set Equality Problems
Aleksandrs Belovs\thanks{MIT
We prove tight $\Omega(n^{1/3})$ lower bounds on the quantum query complexity of the \cpp and the \sep problems, provided that the size of the alphabet is large enough. We do this using the negative-weighted adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a very recent development by Zhandry.
_MainMacros.tex


\draft{\usepackage{easy-todo}}
%\release{\newcommand{\todo}[1]{}}
\newcommand{\bigtodo}[1]{\todo{#1}}

% ????
%\usepackage{todonotes}
%\newcommand{\bigtodo}[1]{\todo[inline]{#1}}
%\usepackage[notref,notcite]{showkeys}


\draft{\usepackage[notref,notcite]{showkeys}}

\usepackage{graphicx}

\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{latexsym}

\bigone{\newtheorem{thm}{Theorem}[chapter]}
\smallone{\newtheorem{thm}{Theorem}}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prp}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{clm}[thm]{Claim}
\newtheorem{fact}[thm]{Fact}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{obs}[thm]{Observation}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exm}[thm]{Example}
\newtheorem{assump}[thm]{Assumption}

\newcommand{\refthm}[1]{Theorem~\ref{thm:#1}}
\newcommand{\reflem}[1]{Lemma~\ref{lem:#1}}
\newcommand{\refprp}[1]{Proposition~\ref{prp:#1}}
\newcommand{\refcor}[1]{Corollary~\ref{cor:#1}}
\newcommand{\refclm}[1]{Claim~\ref{clm:#1}}
\newcommand{\reffact}[1]{Fact~\ref{fact:#1}}
\newcommand{\refconj}[1]{Conjecture~\ref{conj:#1}}
\newcommand{\refrem}[1]{Remark~\ref{rem:#1}}
\newcommand{\refobs}[1]{Observation~\ref{obs:#1}}
\newcommand{\refdefn}[1]{Definition~\ref{defn:#1}}
\newcommand{\refexm}[1]{Example~\ref{exm:#1}}
\newcommand{\refassump}[1]{Assumption~\ref{assump:#1}}

\newcommand{\refchp}[1]{Chapter~\ref{chp:#1}}
\newcommand{\refsec}[1]{Section~\ref{sec:#1}}
\newcommand{\refapp}[1]{Appendix~\ref{app:#1}}
\newcommand{\reffig}[1]{Figure~\ref{fig:#1}}
\newcommand{\refeqn}[1]{(\ref{eqn:#1})}
\newcommand{\reftbl}[1]{Table~\ref{tbl:#1}}
\newcommand{\refalg}[1]{Algorithm~\ref{alg:#1}}
\newcommand{\refsub}[1]{Subroutine~\ref{sub:#1}}
\newcommand{\refline}[1]{Line~\ref{line:#1}}
\newcommand{\reffoot}[1]{Footnote~\ref{foot:#1}}

\def \rf(#1:#2){\csname ref#1\endcsname{#2}}


\newcommand{\pfstart}{\begin{proof}} 
\newcommand{\pfsketch}{\begin{proof}[Proof sketch]}
\newcommand{\pfend}{\end{proof}} 
\newcommand{\itemstart}{\begin{itemize}\itemsep0pt}
\newcommand{\itemend}{\end{itemize}}
\newcommand{\descrstart}{\begin{description}\itemsep0pt}
\newcommand{\descrend}{\end{description}}
\newcommand{\enumstart}{\begin{enumerate}\itemsep0pt}
\newcommand{\enumend}{\end{enumerate}}


\newcommand{\C}{{\mathbb{C}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\Z}{{\mathbb{Z}}}
\renewcommand{\S}{{\mathbb{S}}}


% \ii = sqrt{-1}
\newcommand{\ii}{\mathsf{i}}
% e = 2.7....
\newcommand{\ee}{\mathsf{e}}
\newcommand{\eps}{\varepsilon}

\usepackage{xspace} 
\newcommand{\etal}{{\em et al.}\xspace}

\newcommand{\ignore}[1]{}


\def \s[#1]{\left(#1\right)}
\def \sA[#1]{\bigl(#1\bigr)}
\def \sB[#1]{\Bigl(#1\Bigr)}
\def \sC[#1]{\biggl(#1\biggr)}
\def \sD[#1]{\Biggl(#1\Biggr)}

\def \sk[#1]{\left[#1\right]}
\def \skA[#1]{\bigl[#1\bigr]}
\def \skB[#1]{\Bigl[#1\Bigr]}
\def \skC[#1]{\biggl[#1\biggr]}
\def \skD[#1]{\Biggl[#1\Biggr]}

\def \abs|#1|{\left| #1\right|}
\def \absA|#1|{\bigl|#1\bigr|}
\def \absB|#1|{\Bigl|#1\Bigr|}
\def \absC|#1|{\biggl|#1\biggr|}
\def \absD|#1|{\Biggl|#1\Biggr|}

\def \norm|#1|{\left\| #1\right\|}
\def \normA|#1|{\bigl\| #1\bigr\|}
\def \normB|#1|{\Bigl\| #1\Bigr\|}
\def \normC|#1|{\biggl\| #1\biggr\|}
\def \normD|#1|{\Biggl\| #1\Biggr\|}
\def \normS|#1|{\| #1\|}

\def \normFrob|#1|{\norm|#1|_{\mathrm{F}}}
\def \normtr|#1|{\norm|#1|_{\mathrm{tr}}}

\def \sfig#1{\left\{#1\right\}}
\def \sfigA#1{\bigl\{#1\bigr\}}
\def \sfigB#1{\Bigl\{#1\Bigr\}}
\def \sfigC#1{\biggl\{#1\biggr\}}
\def \sfigD#1{\Biggl\{#1\Biggr\}}

\def \floor[#1]{\lfloor #1 \rfloor}
\def \ceil[#1]{\lceil #1 \rceil}

\def \elem[#1]{[\![#1]\!]}

%\def \ket#1|#2>{|#2\mathbf\rangle_{\text{\rm #1}}}
\def \ket#1|#2>%
{\ifx&#1&%#1 is empty
|#2\rangle
\else
|#2\rangle_{\mathsf #1}
\fi}

\def \ketA#1|#2>%
{\ifx&#1&%#1 is empty
\bigl|#2\bigr\rangle
\else
\bigl|#2\bigr\rangle_{\mathsf #1}
\fi}


\def \ip<#1,#2>{\langle #1, #2\rangle}
\def \ipA<#1,#2>{\bigl\langle #1, #2\bigr\rangle}
\def \ipB<#1,#2>{\Bigl\langle #1, #2\Bigr\rangle}
\def \ipC<#1,#2>{\biggl\langle #1, #2\biggr\rangle}
\def \ipD<#1,#2>{\Biggl\langle #1, #2\Biggr\rangle}


\newcommand{\polylog}{\mathop{\mathrm{polylog}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}


%
\usepackage{silence}
\WarningFilter{latex}{Marginpar on page}
\WarningFilter{pdftex}{}

% My commands
%\def\mycommand#1#2{%
%\draft{\marginpar{\fbox{\sf{#1:} $#2$}}}%
%\expandafter\def\csname#1\endcsname{#2}%
%}

\def\mycommand#1#2{%
\draft{\marginpar{\fbox{\sf{#1:} $#2$}}}%
\expandafter\newcommand \csname#1\endcsname {#2}%
}
\def\remycommand#1#2{%
\draft{\marginpar{\fbox{\sf{#1:} $#2$}}}%
\expandafter\renewcommand \csname#1\endcsname {#2}%
}


\newcommand{\myincludegraphics}[2]{\release{\includegraphics[width=#1]{#2}}}

%Stuff for the bibliography
\draft{\newcommand{\myhref}[2]{#2}}
\release{\newcommand{\myhref}[2]{\href{#1}{#2}}}

QIP2014.tex
\documentclass[10pt]{article}

\newcommand\draft[1]{}
\newcommand\release[1]{#1}
\newcommand\bigone[1]{}
\newcommand\smallone[1]{#1}


\hyphenation{dem-on-strat-ed al-go-rithm}
\def\hyph{-\penalty0\hskip0pt\relax}

\newcommand{\cD}{{\cal D}}
\newcommand{\cV}{{\cal V}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cY}{{\cal Y}}
\newcommand{\cX}{{\cal X}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cQ}{{\cal Q}}
\newcommand{\cW}{{\cal W}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cS}{{\cal S}}

\renewcommand{\S}{\mathbb{S}}
\newcommand{\Adv}{\mathop{\mathrm{ADV}^{\pm}}}

%\usepackage{stfloats} % this is for positioning equations on the bottom of a page
%\usepackage{hyperref} % for \url etc
\usepackage{fullpage} % for making text fields wider

\input{_MainMacros.tex}


\newcommand{\I}{{\mathbb{I}}}
\newcommand{\J}{{\mathbb{J}}}

\newcommand{\spn}{\mathop{\mathrm{span}}}
\newcommand{\wrr}{\mathop{\mathrm{wr}}}
\newcommand{\Ind}{\mathop{\mathrm{Ind}}}
\newcommand{\ind}{\mathop{\mathrm{ind}}}
\newcommand{\Res}{\mathop{\mathrm{Res}}}
\newcommand{\Tr}{\mathop{\mathrm{Tr}}}
\newcommand{\cp}{{\hspace{-0.5pt}\textsc{cp}\hspace{-0.5pt}}}
\newcommand{\se}{{\hspace{-0.5pt}\textsc{se}\hspace{-0.5pt}}}
\newcommand{\qp}{{\hspace{-0.5pt}\textsc{q}\hspace{-0.5pt}}}
\newcommand{\row}{\mathop{\mathrm{Row}}}
\newcommand{\col}{\mathop{\mathrm{Col}}}
\newcommand{\Rep}{\mathop{\mathrm{Rep}}}
\newcommand{\sgn}{\mathop{\mathrm{sgn}}}

% Operators constituting the adversary matrix
\newcommand{\oW}{W}
\newcommand{\oX}{X}
\newcommand{\oY}{Y}
\newcommand{\oZ}{Z}

\newcommand{\OO}{\mathrm{O}}

\newcommand{\specht}[1]{S^{#1}}
\newcommand{\weyl}[2]{W^{#1}_{#2}}


\begin{document}


\title{Adversary Lower Bounds for the Collision \\ and the Set Equality Problems}
\author{
Aleksandrs Belovs\thanks{MIT, \protect\url{abelov@csail.mit.edu}}
\and
Ansis Rosmanis\thanks{David R. Cheriton School of Computer Science and
Institute for Quantum Computing, University of Waterloo, \protect\url{ansis.rosmanis@gmail.com}}
}
\date{}




\maketitle

\newcommand{\cpp}{{\sc Collision}\xspace}
\newcommand{\sep}{{\sc Set Equality}\xspace}

\begin{abstract}
We prove tight $\Omega(n^{1/3})$ lower bounds on the quantum query complexity of the \cpp and the \sep problems, provided that the size of the alphabet is large enough.
We do this using the negative-weighted adversary method.
Thus, we reprove the result by Aaronson and Shi, as well as a very recent development by Zhandry.
\end{abstract}
\section{Introduction}



In theory, quantum query complexity is surprisingly well-understood.  For each function, the (negative-weighted) adversary method~\cite{hoyer:advNegative} gives a tight estimate of its quantum query complexity~\cite{reichardt:advTight}.  
The adversary bound is a semi-definite optimisation problem. 
It performs nicely under composition~\cite{reichardt:advTight}, and it was used to prove strong direct product theorem~\cite{lee:strongDirect}.  There is no similar theory known for randomised query complexity.

In practice, however, it is quite hard to construct a solution to the adversary bound that would be close to the optimal.
In many applications, the positive-weighted version of the bound is used.  It is the original version of the bound developed by Ambainis~\cite{ambainis:adv}.  
This version uses a transparent combinatorial reasoning, and it is easy to use.
Unfortunately, the positive-weighted adversary is subject to some severe constraints like the certificate complexity barrier~\cite{spalek:advEquivalent, zhang:advPower} and the property testing barrier~\cite{hoyer:advNegative}.
The latter states that, if any positive input differs from each negative input in at least $\eps$ fraction of the input variables, no positive-weighted adversary can prove a lower bound better than $\Omega(1/\eps)$.

The proper negative-weighted adversary method usually requires a spectral analysis of the adversary matrix.  It does not have many applications so far.
It was used to prove tight lower bounds for formulae evaluation~\cite{reichardt:formulae}.  
Also, a recent line of development~\cite{spalek:kSumLower, belovs:onThePower} resulted in a relatively general construction of adversary bounds superseding the certificate complexity barrier:
For any family $\cS$ of $\OO(1)$-sized subsets of $[n]$, a relatively simple optimisation problem gives a tight lower bound on the problem of detecting whether the input string $x\in[q]^n$ contains a subset of elements that belongs to $\cS$ and whose sum is divisible by $q$.  In particular, this gave tight lower bounds for the $k$-sum and the triangle-sum problems.  The proof is based on the duality to the special case of quantum query algorithms: learning graph~\cite{belovs:learning}.

For some other functions, lower bounds on quantum query complexity were obtained using the polynomial method~\cite{beals:pol}.  
This method is known to be suboptimal~\cite{ambainis:polVsQCC}, but it is not subject to the limitations of the positive-weighted adversary.
This method works nice for functions with many symmetries.
For instance, consider the \cpp and the \sep problems.
The \cpp problem is to decide whether a function $x\colon [2n]\rightarrow[q]$ is one-to-one or two-to-one, given a promise that either case holds. 
The \sep problem is a special case of \cpp given an extra promise that the function $x$ is one-to-one on both subdomains $[1..n]$ and $[n+1..2n]$.

The \cpp problem was defined in~\cite{brassard:collision} together with a $\OO(n^{1/3})$-query algorithm for the problem (that also applies to \sep).
By the property testing barrier, no positive-weighted adversary can give a non-trivial lower bound.  All known lower bounds for these problems were obtained using the polynomial method.
Aaronson and Shi~\cite{shi:collisionLower} proved $\Omega(n^{1/3})$ lower bound for the \cpp problem using the polynomial method.  The proof was subsequently simplified by Kutin~\cite{kutin:collisionLower}.  The \sep problem was defined by Shi and conjectured to be as hard as \cpp~\cite{shi:collisionLowerOriginal}.
Midrij\=anis showed an $\Omega((n/\log n)^{1/5})$ lower bound using a combination of the non-negative adversary and the polynomial methods~\cite{midrijanis:setEquality}.
Very recently, Zhandry~\cite{zhandry:setEquality} proved a tight $\Omega(n^{1/3})$ lower bound for the \sep problem using rather complicated machinery from~\cite{zhandry:howToConstruct} based on the polynomial method.

%From the history of applications of the adversary and the polynomial bounds, one can conclude the following.
%The polynomial method works well for sufficiently symmetric functions with global differences between the positive and the negative inputs.  The adversary method works well for functions with local differences between the negative inputs.

In this paper, we extend the range of applications of the adversary bound, and construct tight lower bounds for the \cpp and the \sep problems, given that the size of the alphabet, $q$, is at least $\Omega(n^2)$.
Thus, we resolve Shi's conjecture affirmatively, which is done independently from Zhandry's work.
The lower bound for the \sep problem was used by Aaronson and Ambainis in their proof of the polynomial relation between the randomised and the quantum query complexities of partial, permutation-invariant functions~\cite{aaronson:structure}.  By improving the lower bound, we automatically improve the exponent in their result, as explained in their paper.

Understanding the adversary method is important for proving lower bounds for other functions.  Firstly, this method is known to be always tight.  Secondly, known constructions of the lower bounds through the adversary method have a strong duality to the known upper bounds.  This simplifies the construction of the lower bound.  The construction in this paper is also based on the duality to the upper bound, as explained in the beginning of \rf(sec:const).
Interestingly, the proofs for the \cpp and the \sep problems in this paper are almost identical, showing that the adversary method can be easier adopted for a specific function, as soon as a lower bound for a similar function is obtained.  This is in contrast to the polynomial method, as more than ten years separated Shi's and Zhandry's results.  
Also, we note that it is the first to our knowledge application of the adversary method that supersedes the property testing barrier.
We hope that some of these results will be useful in proving further lower bounds by the adversary method.

The paper is organised as follows.  In \rf(sec:prelim), we define the adversary method and the basics of the representation theory.  In \rf(sec:analysis), we give a general treatment of the \cpp and \sep problems, without actually defining the lower bound.  In \rf(sec:const), we construct the lower bound.  Two proofs of two technical results in this section are given in the appendix.



%============================================================
\section{Preliminaries} \label{sec:prelim}
%============================================================

For positive integers $m$ and $\ell \geq m$, let $[m]$ denote the set $\{1,2,...,m\}$ and $[m..\ell]$ denote the set $\{m,m+1,\ldots,\ell\}$.  For a matrix $A$, we denote its $(i,j)$-th entry by $A\elem[i,j]$, and similarly for vectors.
For any normal operator $A$ on a space $\cK$, we say that $A$ has {\em support} on $\cK'\subset\cK$ if $\cK'$ contains all the eigenvectors of $A$ having non-zero eigenvalues. 
 We do not ask $\cK'$ to be spanned by these eigenvalues (i.e., $\cK'$ can be larger than this span).

%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\subsection{Adversary Method} \label{sec:adv}
%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

We identify decision problems with Boolean-valued functions $f\colon \cD\to \{0,1\}$ with domain $\cD\subseteq[q]^{m}$. %(In our case of interest, $m=2n$.)
We are interested in quantum query complexity of decision problems.  For the definitions and basic properties refer to~\cite{buhrman:querySurvey}.  
In the paper, we only require the knowledge of the (general) adversary bound that we are about to define.

\begin{defn}\label{defn:advMatrix}
 An {\em adversary matrix}\footnote{
 Compared to an adversary matrix for an arbitrary problem~\cite{hoyer:advNegative}, we will  consider only a quarter of the matrix, as this quarter completely specifies the whole matrix (see~\cite{spalek:kSumLower} for details).
 }
 for a decision problem $f$ is a non-zero real
 $|f^{-1}(1)|\times|f^{-1}(0)|$-matrix $\Gamma$ whose rows are labeled by the positive inputs
 $f^{-1}(1)$ and columns by the negative inputs $f^{-1}(0)$.
 For any $i\in[m]$, the $|f^{-1}(1)|\times|f^{-1}(0)|$-matrix $\Delta_i$ is defined by
\[
 \Delta_i[\![x,y]\!] = \begin{cases}0,&x_i=y_i;\\1,&x_i\neq y_i.\end{cases}
\]
\end{defn}

\begin{thm}[Adversary bound~\cite{hoyer:advNegative,lee:stateConversion,spalek:kSumLower}]
\label{thm:adversary}
In the notation of \refdefn{advMatrix}, the quantum query complexity of the decision problem $f$ is $\Adv(f)$, where $\Adv(f)$ is the optimal value
of the semi-definite program
\begin{subequations}
\label{eq:adv}
\begin{alignat}{3}
 &{\mbox{\rm maximize }} &\quad& \norm|\Gamma| \\ 
 &{\mbox{\rm subject to }} && \norm|\Delta_i\circ\Gamma|\leq 1\qquad \mbox{ for all }i\in[m],
\end{alignat}
\end{subequations}
where the maximization is over all adversary matrices $\Gamma$ for $f$, $\norm|\cdot|$ is the spectral
 norm (i.e., the largest singular value), and $\circ$ is the Hadamard (entrywise) matrix product.
\end{thm}
Note that we can choose any adversary matrix $\Gamma$ and scale it so that the condition
 $\norm|\Delta_i\circ\Gamma|\leq 1$ holds. In practice, we use the condition
 $\norm|\Delta_i\circ\Gamma|= \mathrm{O}(1)$ instead of $\norm|\Delta_i\circ\Gamma|\leq 1$. 

Precise calculation of $\norm|\Delta_i\circ\Gamma|$ may be tedious, but we can upper bound
 $\norm|\Delta_i\circ\Gamma|$ using the following trick first introduced in~\cite{belovs:adv-el-dist} and later used in~\cite{spalek:kSumLower,belovs:onThePower,spalek:adv-array}.
 For any matrix $A$ of the same dimensions as $\Delta_i$, we call a matrix $B$ satisfying
 \[
  \Delta_i\circ B=\Delta_i\circ A \quad(\,= \Delta_i\circ\Delta_i\circ A\,)
 \]
 an {\em approximation of} $\Delta_i\circ A$ and denote it $\Delta_i\diamond A$.
Or, we write $A\stackrel{\Delta_i}{\longmapsto} B$.
Now, from the fact that
\[
\gamma_2(\Delta_i) = \max_B\big\{\norm|\Delta_i\circ B|:\norm|B|\leq 1\big\}\leq 2
\]
(see~\cite{lee:stateConversion} for this and other facts about the $\gamma_2$ norm),
it follows that
\[
  \norm|\Delta_i\circ A| = \norm|\Delta_i\circ(\Delta_i\diamond A)|
  \leq 2\norm|\Delta_i\diamond A|.
\]
Note that we can always choose $\Delta_i\diamond A = A$
 and
\[
 \Delta_i\diamond(\alpha'A'+\alpha''A'')
  =\alpha'(\Delta_i\diamond A') + \alpha''(\Delta_i\diamond A'').
\]

In order to show that $\norm|\Delta_i\circ\Gamma| = \mathrm{O}(1)$, it suffices to show that
 $\norm|\Delta_i\diamond\Gamma| = \mathrm{O}(1)$ for any $\Delta_i\diamond\Gamma$.
 That is, it suffices to show that we
 can change entries of $\Gamma$ with $x_i=y_i$ in a way that the 
 spectral norm of the resulting matrix is constantly bounded.

%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\subsection{Representation Theory}
\label{sec:representation}
%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

In this section, we introduce the basic notions of the representation theory of finite groups with the emphasis on the symmetric group.  For more background on this topic, the reader may refer to~\cite{curtis:representationTheory, serre:representation} for the general theory, and to~\cite{james:symmetricGroup, sagan:symmetricGroup} for the special case of the symmetric group.

Assume $G$ is a finite group.  
The group algebra $\R G$ is the real vector space with the elements of $G$ forming an orthonormal basis%
\footnote{
Usually, one works with complex modules.  However, the adversary matrix $\Gamma$ is real, and there is no difference in the representation theory of the symmetric group over the fields $\C$ and $\R$, so we have switched to modules over $\R$.
}.
The multiplication law in $G$ is extended to $\R G$ by linearity.  
A representation of $G$ is a (left) module over $\R G$.  A representation is called irreducible (or just irrep) if it does not contain a non-trivial $\R G$-submodule.
An essential basic result in the representation theory is the following
\begin{lem}[Schur's Lemma]
Assume $\theta\colon V\to W$ is an $\R G$-morphism between two irreducible $\R G$-modules $V$ and $W$. 
Then, $\theta=0$ if $V$ and $W$ are non-isomorphic, otherwise, $\theta$ is uniquely determined up to a scalar multiplier.
\end{lem}
Copies of non-isomorphic irreps in a fixed $\R G$-module $V$ are orthogonal.  
For any $\R G$-module $V$, one can define its canonical decomposition into subspaces, each spanned by all copies of a fixed irrep in $V$.

Let $\S_L$ denote the symmetric group of a finite set $L$, that is, the group with the permutations of $L$ as elements, and composition as the operation.  If $m$ is a positive integer, $\S_m$ denotes the isomorphism class of the symmetric groups $\S_L$ with $|L|=m$.
The representation theory of $\S_m$ is closely related to Young diagrams.

A decomposition $\lambda$ of an integer $m$ is a non-increasing list $(\lambda_1,\dots,\lambda_k)$ of positive integers satisfying $\lambda_1+\dots+\lambda_k = m$.  We denote this relation by $\lambda\vdash m$, or write $m = |\lambda|$.
A decomposition $\lambda = (\lambda_1,\dots,\lambda_k)$ is often represented in the form of a Young diagram that consists, from top to bottom, of rows of $\lambda_1,\lambda_2,\dots,\lambda_k$ boxes aligned by the left side. 
For a decomposition $\lambda=(\lambda_1,\dots,\lambda_k)$ of $m$ and an integer $\ell\ge \lambda_1$, by $(\ell, \lambda)$ we denote the decomposition $(\ell,\lambda_1,\dots,\lambda_k)$ of $m+\ell$.

For each decomposition $\lambda\vdash m$, one can assign an irreducible $\R\S_m$-module $\specht{\lambda}$, called the Specht module.  All these modules are pairwise non-isomorphic, and give a complete list of all the irreps of $\S_m$.



\section{Analysis of the Problem}
\label{sec:analysis}
Consider the three following types of input strings $x=(x_1,\dots,x_{2n})$ in $[q]^{2n}$:
\itemstart
\item[(a)] For each $a\in[q]$, there are exactly two or none $i\in[2n]$ such that $x_i = a$.
\item[(b)] For each $a\in[q]$, either there is no $x_i$ equal to $a$, or there is unique $i\in[n]$ and unique $j\in[n+1..2n]$ satisfying $x_i=x_j=a$.
\item[(c)] For each $a\in[q]$, there is at most one $i\in[2n]$ such that $x_i=a$.
\itemend
In the \cpp problem, given $x\in[q]^{2n}$ satisfying (a) or (c), the task is to distinguish these two cases.  We say that (a) forms the set of positive inputs, and (c) is the set of negative inputs.  In the \sep problem, the task is to distinguish (b) and (c) in a similar manner.
Since any string in (b) also satisfies the requirements in (a), \sep is a simpler problem than \cpp.
In the following, we will use subscripts $\cp$ and $\se$ to denote relation to \cpp and \sep, respectively.  To avoid unnecessary repetitions, we use notation $\qp$ that may refer to both $\cp$ and $\se$.

Positive inputs in (a) and (b) naturally give rise to corresponding matchings.  A {\em matching} $\mu$ on $[2n]$ is a decomposition 
\[
[2n] = \{\mu_{1,1},\mu_{1,2}\} \cup \{\mu_{2,1},\mu_{2,2}\}\cup \cdots\cup \{\mu_{n,1}, \mu_{n,2}\}
\]
of the set $[2n]$ into $n$ pairwise disjoint pairs of elements.  For concreteness, we will usually assume that $\mu_{i,1} < \mu_{i,2}$ for all $i\in[n]$, and $\mu_{1,1}<\mu_{2,1}<\cdots<\mu_{n,1}$.  
In particular, $\mu_{1,1}=1$.
Clearly, this assumption is without loss of generality.  
Let $M_\cp$ denote the set of all matchings on $[2n]$, and let $M_\se$ denote the set of matchings $\mu$ on $[2n]$ such that $1\le \mu_{i,1}\le n$ and $n+1\le \mu_{i,2}\le 2n$ for all $i$.


%There are $(2n-1)!!\frac{q!}{(q-n)!}$ positive inputs for \cpp, where 
%\[ (2n-1)!!=(2n-1)(2n-3)\cdots3\cdot1, \]
%$n!\frac{q!}{(q-n)!}$ positive inputs for \sep.  The set of negative inputs for both problems has cardinality $\frac{q!}{(q-2n)!}$.

\newcommand{\tGamma}{\tilde\Gamma}
\paragraph{Embedding.}
Our aim is to construct adversary matrices $\Gamma_\cp$ and $\Gamma_\se$ for the \cpp and the \sep problems, respectively. 
As described in \refdefn{advMatrix}, the rows of the adversary matrices are labeled by the positive inputs and columns---by the negative inputs.
We will use the trick initially used in~\cite{belovs:adv-el-dist}, and embed the adversary matrix $\Gamma_\qp$ into a larger $|M_\qp| q^n\times q^{2n}$ matrix $\tilde\Gamma_\qp$.
Columns of $\tGamma_\qp$ are labeled by all possible inputs in $[q]^{2n}$.  The rows of $\tGamma_\qp$ are split into blocks corresponding to the matchings in $M_\qp$.  Inside a block corresponding to $\mu$, there are all possible labels $x\in[q]^{2n}$ such that $x\elem[\mu_{i,1}]=x\elem[\mu_{i,2}]$ for all $i$.
We will denote rows by specifying both the label and the block, i.e., like $(x, \mu)$.

Besides legal labels, $\tGamma_\qp$ contains also {\em illegal} rows and columns.  A column is illegal if its label contains two equal elements.  A row corresponding to a matching $\mu$ is illegal if $x\elem[\mu_{i,1}] = x\elem[\mu_{j,1}]$ for some $i\ne j$.  
We obtain $\Gamma_\qp$ from $\tilde\Gamma_\qp$ by removing all the illegal rows and columns.
 
This embedding is used because it is easier to work with $\tilde\Gamma_\qp$ rather than with $\Gamma_\qp$. We clearly have
\begin{equation}
\label{eqn:DeltaiNorms}
 \norm|\Delta_i\circ\Gamma_\qp| \leq \big\|\Delta_i\circ\tilde\Gamma_\qp\big\|
\end{equation}
because $\Delta_i\circ\Gamma_\qp$ is a submatrix of $\Delta_i\circ\tilde\Gamma_\qp$.
If we could show that $\norm|\Gamma_\qp|$ is not much smaller than $\|\tilde\Gamma_\qp\|$, that would allow us to use $\tilde\Gamma_\qp$ instead of $\Gamma_\qp$ in \refthm{adversary}. 
That is not true for every choice of $\tilde\Gamma_\qp$, however.
For instance, if $\tilde\Gamma_\qp$ contains non-zero entries only in illegal rows or columns, then
$\Gamma_\qp=0$.
But for our special choice of $\tilde\Gamma_\qp$ this is the case, as shown in \refsec{subIllegal}.
The condition $q = \Omega(n^2)$ is essential for the proof.




%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\paragraph{Space $\cH$ and its subdivision.}
Let $\cH = \R^{q}$, and let $\cM_\qp = \R^{M_\qp}$ be the real vector space with the elements of $M_\qp$ forming an orthonormal basis.
Then, $\tilde\Gamma_\qp$ can be considered as an operator from $\cH^{\otimes 2n}$ to $\cM_\qp\otimes\cH^{\otimes n}$ if we identify a basis element $(\mu, z)\in M_\qp\times [q]^n$ with the row label $x$ in the $\mu$-block of $\tGamma_\qp$ defined by $x\elem[\mu_{i,a}] = z_i$.

Now we are going to define two basis of $\cH$.  The standard basis of $\cH$ is the one used in \rf(defn:advMatrix), i.e., the basis elements are the symbols of the input alphabet.  The {\em $e$-basis} is an orthonormal basis $e_0,e_1,\dots,e_{q-1}$ satisfying $e_0\elem[j]=1/\sqrt{q}$ for all $j\in[q]$.
The precise choice of the remaining basis elements is irrelevant.  Further in the text, we almost exclusively work in the $e$-basis.
Let
\[
  \cH_0=\spn\{e_0\}\qquad\text{and}\qquad\cH_1 = e_0^\perp = \spn\{e_1,\ldots,e_{q-1}\}.
\]
Let us agree on a notational convention that $\Pi$ with arbitrary sub- and superscripts denotes the orthogonal projector onto the space denoted by $\cH$ with the same sub- and superscripts.
Thus, for instance, $\Pi_0=e_0e_0^*=\J_\cH/q$ and $\Pi_1=\I_\cH-\J_\cH/q$, where $\I_\cH$ is the identity, $\J_{\cH}$ is the all-ones matrix.  An important relation is
\[
\Pi_1 \stackrel{\Delta}{\longmapsto} - \Pi_0,
\]
where $\Delta$ acts on the only variable.

Similarly, for the space $\cH^{\otimes m}$, the $e$-basis consists of tensor products of the vectors in $\{e_i\}$ of length $m$.  The vector $e_0$ in the tensor product is called the zero component.  The {\em weight} of the basis vector is the number of non-zero components in the product.  The space $\cH^{\otimes m}$ can be decomposed as $\cH^{\otimes m} = \bigoplus_{k=0}^m \cH^{(m)}_k$, where
\[
  \cH^{(m)}_k=\bigoplus\nolimits_{c\in\{0,1\}^{m}\!, \,|c|=k}\cH_{c_1}\otimes\ldots\otimes\cH_{c_{m}}
\]
is the space spanned by all the basis elements of weight $k$.

\paragraph{Symmetry.}
Let $\S_\cp=\S_{[2n]}$ be the symmetric group on $2n$ elements, and let $\S_\se$ be its subgroup $\S_{[1..n]}\times \S_{[n+1..2n]}$.
The \cpp and the \sep problems are invariant under the permutations of the input variables in $\S_\cp$ and $\S_\se$, respectively.  Hence, we may assume that $\Gamma_\qp$ is also invariant under these permutations~\cite{hoyer:advNegative}.  
We extend this symmetry to $\tGamma_\qp$ by requiring that, for each $\pi\in\S_\qp$, and labels $(x,\mu)$ and $y$, we have
\begin{equation}
\label{eqn:symmetry}
\tGamma_\qp\elem[(x,\mu), y] = \tGamma_\qp\elem[(\pi x, \pi\mu), \pi y],
\end{equation}
where $(\pi x)_i = x_{\pi^{-1}(i)}$ and $\pi\mu = \{\{\pi(\mu_{1,1}), \pi(\mu_{1,2})\},\dots, \{\pi(\mu_{n,1}), \pi(\mu_{n,2})\}\}$.  Note that $\cH^{(m)}_k$ is invariant under all the permutations in $\S_{[m]}$.

Because of this symmetry, we may use the representation theory in the construction of $\tGamma_\qp$.
The \cpp and the \sep problems also have symmetries associated with the {\em values} of the variables.  We make use of this symmetry in \rf(app:newMain), but is is unnecessary for the main part of the paper.


%============================================================
\section{Construction of the Adversary Matrix} \label{sec:const}
%============================================================
The form of our solution is taken from~\cite[Proposition 12]{belovs:onThePower}.
The adversary matrix $\tilde\Gamma_\qp$ is constructed as a linear combination
\begin{equation}
\label{eqn:decomposition}
   \tilde\Gamma_\qp = \sum\nolimits_{k}\alpha_k\bar \oW_{\qp,k},
\end{equation}
where, for each $k$, $\bar W_{\qp,k}$ is an operator from $\cH^{(2n)}_k$ to $\cM_\qp\otimes \cH^{(n)}_k$.  
The coefficients $\alpha_k$ are given by $\alpha_k = \max\{0, n^{1/3}-k\}$.
We again assume that $\bar \oW_{\qp,k}$ is invariant under the action of $\S_\qp$ (in the sense of \rf(eqn:symmetry)).  The purpose of this section is to find a suitable material for this form.

The first intention is to use the techniques of~\cite{belovs:onThePower} to define the matrices in~\rf(eqn:decomposition).  Unfortunately, this construction fails, as we show in \rf(sec:subconst1).
Luckily, it is possible to modify the definition of the matrices so that~\rf(eqn:decomposition) gives an optimal adversary matrix.  We describe this in \rf(sec:success).  Finally, in \rf(sec:subIllegal), we show how to transform $\tGamma_\qp$ into a valid adversary matrix $\Gamma_\qp$.


%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\subsection{First Attempt} \label{sec:subconst1}
%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
In this section, we define matrices $W_{\qp,k}$ that may seem as the most natural choice for the decomposition~\rf(eqn:decomposition).  Unfortunately, as we show in this section, they do not work well enough, so we will have to modify the construction in \rf(sec:success).

Recall that the matrix $\tilde\Gamma_\qp$ can be decomposed into blocks corresponding to different matchings $\mu\in M_\qp$.  
We first define one block of the matrix.
Let
\[  
\Psi_0=\Pi_0\otimes e_0^*=e_0^*\otimes \Pi_0
\qquad\text{and}\qquad
\Psi_1=\Pi_1\otimes e_0^*+e_0^*\otimes \Pi_1
\]
 be two operators from $\cH\otimes\cH$ to $\cH$.  For every $k\in[n]$ and every $\mu\in M_\qp$, define the operator $W^\mu_k\colon \cH^{\otimes 2n}\to \cH^{\otimes n}$ by 
\begin{equation}\label{eqn:Fsigma}
 W^\mu_k = \sum\nolimits_{c\in\{0,1\}^n\!, \,|c|=k}\Psi_{c_1}\otimes\ldots\otimes\Psi_{c_n},
\end{equation}
where, for $i\in[n]$, $\Psi_{c_i}$ maps the $\mu_{i,1}$-th and the $\mu_{i,2}$-th multiplier in $\cH^{\otimes 2n}$ to the $i$-th multiplier in $\cH^{\otimes n}$.
The block of the matrix $W_{\qp, k}$ corresponding to $\mu\in M_\qp$ is defined by $\frac{1}{\sqrt{|M_\qp|}} W_k^\mu$.

One can see that $\oW_{\qp,k}$ thus constructed satisfy the symmetry~\rf(eqn:symmetry).
Because of this, $\|\Delta_i\circ\tilde\Gamma_\qp\|$ is the same for all $i\in[2n]$.  Therefore, it suffices to estimate $\|\Delta_1\circ\tilde\Gamma_\qp\|$.
For that, we define the following decomposition:
\begin{equation}
\label{eqn:Wdecomposition}
\oW_{\qp,k}=\oX_{\qp,k}+\oY_{\qp,k}+\oZ_{\qp,k},
\end{equation}
where $\oX_{\qp,k}$, $\oY_{\qp,k}$, and $\oZ_{\qp,k}$ are defined similarly to $W_{\qp, k}$ via
\begin{equation}
\label{eqn:GHI}
\begin{split}
& X^{\mu}_{k} = \Psi_0\otimes \sum\nolimits_{c\in\{0,1\}^{n-1},\,|c|=k}\Psi_{c_2}\otimes\ldots\otimes \Psi_{c_{n}}, \\
& Y^{\mu}_{k} = (e_0^*\otimes \Pi_1)\otimes \sum\nolimits_{c\in\{0,1\}^{n-1},\,|c|=k-1}\Psi_{c_2}\otimes\ldots\otimes \Psi_{c_{n}}, \\
& Z^{\mu}_{k} = (\Pi_1\otimes e_0^*)\otimes \sum\nolimits_{c\in\{0,1\}^{n-1},\,|c|=k-1}\Psi_{c_2}\otimes\ldots\otimes \Psi_{c_{n}}.
\end{split}
\end{equation}
Recall that we always have $\mu(1,1)=1$.
Again, one can see that $\oX_{\qp,k}$, $\oY_{\qp,k}$, and $\oZ_{\qp,k}$
are symmetric under the action of $\S'_\qp$, where $\S'_\cp=\S_{[2..2n]}$ and $\S'_\se=\S_{[2..n]}\times \S_{[n+1..2n]}$. 

Inspired by~\cite{belovs:onThePower}, we could define $\Delta_1\diamond \oX_{\qp,k}= \oX_{\qp,k}$,\; $\Delta_1\diamond \oY_{\qp,k}= \oY_{\qp,k}$,\; and $\Delta_1\diamond \oZ_{\qp,k}= -\oX_{\qp,k-1}$,
so that
\begin{equation}
\label{eqn:firstCancellation}
\tilde\Gamma_\qp \stackrel{\Delta_1}{\longmapsto} \sum\nolimits_k (\alpha_{k-1}-\alpha_k) \oX_{\qp,k-1} + \sum\nolimits_k \alpha_k \oY_{\qp,k} , 
\end{equation}
if $\tGamma_\qp$ is defined by~\rf(eqn:decomposition) with $\bar W_{\qp,k} = W_{\qp, k}$.
However, it is not hard to show that
\begin{equation}
\label{eqn:exponentialNorm}
 \|W_{\qp, k}\| = \Theta(2^{k/2}),\qquad
\|X_{\qp, k}\| = \Theta(2^{k/2}),\quad\text{and}\quad\|Y_{\qp,k}\| = \Theta(2^{k/2}\sqrt{k/n})
\end{equation}
if $k=o(\sqrt{n})$.  Thus, this construction only gives a trivial lower bound.  It is also possible to show that this problem cannot be fixed by a mere modification of the coefficients $\alpha_k$.

This failure can be explained by the results in~\cite{belovs:onThePower}.
This construction only used that the learning graph complexity of the collision problem is $\Omega(n^{1/3})$.  On the other hand, in the same~\cite[Proposition 12]{belovs:onThePower} it is shown that the learning graph complexity of the hidden shift problem is also $\Omega(n^{1/3})$.  Thus, if this construction worked, we would also be able to prove $\Omega(n^{1/3})$ lower bound for the hidden shift, that is in contradiction with the fact that the query complexity of this problem is logarithmic.

Thus, in order to obtain an optimal solution, we have to again use the structure of the problem, in particular, that the size of the set $M_\qp$ is large, as one can construct an $\OO(\log|M_\qp|)$-query algorithm.  We do this by noticing that $M_\qp$ is symmetric with respect to the permutations of variables, thus, we restrict $W_{\qp, k}$ to some irreps of the symmetric group $\S_\qp$.



%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\subsection{Successful Construction}
\label{sec:success}
%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Our aim is to get rid of the $2^{k/2}$ factor in~\rf(eqn:exponentialNorm) while preserving an analogue of~\rf(eqn:firstCancellation).
The operator $W_{\qp, k}$ is symmetric with respect to $\S_\qp$, hence, it can be subdivided into parts corresponding to different representations of $\S_\qp$.  
We define the operator $\bar W_{\qp,k}$ by taking the part corresponding to representations with many boxes below the first row.
One can show that $W_{\cp, k}$ uses representations whose Young diagram has from $2n$ to $2n-k$ boxes in the first row.  Similarly, $W_{\se, k}$ uses representations such that the sum of the number of boxes in the first rows of the two Young diagrams defining the representation is between $2n$ and $2n-k$.

\newcommand{\bbcH}{\bar{\bar\cH}}
\newcommand{\bbPi}{\bar{\bar\Pi}}
Define $\bar\cH^{(m)}_k$ as the subspace of $\cH^{(m)}_k$ spanned by the irreps of $\S_m$ having exactly $k$ boxes below the first row, i.e., of the form $(m-k,\lambda)$.  
We will also use the subspace $\bbcH^{(m)}_k$ of $\cH^{(m)}_k$ that is spanned by the irreps having exactly $k-1$ boxes below the first row.

We restrict the operator $W_{\qp, k}$ by
\begin{equation}\label{eqn:Wbar}
\bar \oW_{\qp,k}=\oW_{\qp,k}\bar\Pi_{\qp,k},
\end{equation}
where $\bar \Pi_{\qp,k}$ is the orthogonal projector on one of the following subspaces:
\begin{equation}\label{eq:barPiQP}
\bar\cH_{\cp,k}=\bar\cH_{k}^{(2n)} \qquad \text{or} \qquad \bar\cH_{\se,k}=\sum\nolimits_{\ell =0}^k\bar\cH_{k-\ell}^{(n)}\otimes \bar\cH_{\ell}^{(n)}.
\end{equation}
Here, for $\bar\cH_{\se, k}$, the first and the second multiplier reside in the first $n$ and the second $n$ copies of $\cH$ in $\cH^{\otimes 2n}$, respectively.

In order to define the action of $\Delta_1$, we need the following decomposition result.  Its proof is rather technical, and is given in \rf(app:newMain).
\begin{lem}
\label{lem:newMain}
If $k = o(m)$, then
\[%begin{equation}
%\label{eqn:PimkDecomposition}
 \bar\Pi_k^{(m)} = \Pi_0\otimes \bar\Pi_k^{(m-1)} + \Pi_1\otimes \bar\Pi_{k-1}^{(m-1)} + \Phi_k^{(m)},
\]%end{equation}
where $\big\|\Phi_k^{(m)}\big\| =  \mathrm{O}(1/\sqrt{m})$ and $\Phi_k^{(m)}$ has support only on $\bbcH^{(m)}_k$.
\end{lem}

With $\Phi^{(m)}_k$ as in \rf(lem:newMain), let us denote
\begin{equation}\label{eqn:barHprime}
\begin{aligned}
  \bar\Pi_{\cp,k}' &=\bar\Pi_{k}^{(2n-1)},&\Phi_{\cp,k}&=\Phi_{k}^{(2n)},&\bbPi_{\cp,k} &= \bbPi^{(2n)}_k,\\
  \bar\Pi_{\se,k}'&=\sum\nolimits_{\ell=0}^k(\bar\Pi_{k-\ell}^{(n-1)}\otimes \bar\Pi_{\ell}^{(n)}),&
  \Phi_{\se,k}&=\sum\nolimits_{\ell=0}^{k-1}(\Phi^{(n)}_{k-\ell}\otimes \bar\Pi_{\ell}^{(n)}),&
  \bbPi_{\se,k} &= \sum\nolimits_{\ell=0}^{k-1}(\bbPi^{(n)}_{k-\ell}\otimes \bar\Pi_{\ell}^{(n)}).\\
\end{aligned}
\end{equation}

Note that $\bar\Pi_{\qp,k}$ and $\Phi_{\qp,k}$ act on $\cH^{\otimes2n}$ while $\bar\Pi'_{\qp,k}$ acts on $\cH^{\otimes(2n-1)}$.
Also, $\Phi_{\qp,k} = \bbPi_{\qp,k}\Phi_{\qp,k}$.
From \rf(lem:newMain), we have
\begin{equation}
\label{eqn:PiQkDecomposition}
 \bar\Pi_{\qp,k} = \Pi_0\otimes \bar\Pi'_{\qp,k} + \Pi_1\otimes \bar\Pi'_{\qp,k-1} + \Phi_{\qp,k}.
\end{equation}

With $X_{\qp,k}$, $Y_{\qp, k}$ and $Z_{\qp, k}$ as in \rf(sec:subconst1), let
\[
 \bar \oX_{\qp,k}=\oX_{\qp,k}(\Pi_0\otimes\bar\Pi'_{\qp,k}),\qquad 
 \bar \oY_{\qp,k}=\oY_{\qp,k}(\Pi_0\otimes\bar\Pi'_{\qp,k}),\quad\text{and}\quad 
 \bar \oZ_{\qp,k}=\oZ_{\qp,k}(\Pi_1\otimes\bar\Pi'_{\qp,k-1}),
\]
so that from~\rf(eqn:Wdecomposition),~\rf(eqn:GHI) and~\rf(eqn:PiQkDecomposition), we get
\[
 \bar \oW_{\qp,k}= \oW_{\qp,k} \bar\Pi_{\qp,k} = \bar\oX_{\qp,k}+\bar\oY_{\qp,k}+\bar\oZ_{\qp,k} + \oW_{\qp,k}\Phi_{\qp,k}. 
\]

We define the action of $\Delta_1$ on these operators by
\[
\bar \oX_{\qp,k} \stackrel{\Delta_1}{\longmapsto} \bar \oX_{\qp,k},\qquad
\bar \oY_{\qp,k} \stackrel{\Delta_1}{\longmapsto} \bar \oY_{\qp,k},\qquad
\oW_{\qp,k}\Phi_{\qp,k} \stackrel{\Delta_1}{\longmapsto} \oW_{\qp,k}\Phi_{\qp,k},
\quad\mbox{and}\quad
\bar \oZ_{\qp,k} \stackrel{\Delta_1}{\longmapsto} - \bar \oX_{\qp,k-1}.
\]
It is not hard to check that this definition satisfies the requirements in \rf(sec:adv).  Thus, for $\tilde\Gamma_\qp$ as defined in \rf(eqn:decomposition), we have
\[
\tilde\Gamma_\qp \stackrel{\Delta_1}{\longmapsto} \sum\nolimits_k (\alpha_{k-1}-\alpha_k) \bar \oX_{\qp,k-1} + \sum\nolimits_k \alpha_k \bar \oY_{\qp,k} +  \sum\nolimits_k \alpha_k \oW_{\qp,k}\Phi_{\qp,k}. 
\]
So far we have merely constructed an analogue of~\rf(eqn:firstCancellation).  The main difference between this construction and the one in \rf(sec:subconst1) is given by the following result.

\begin{lem}
\label{lem:normEstimations}
In the above notations, we have:
\[
(a)\quad \|\bar X_{\qp,k} \|\le 1,\qquad
(b)\quad \|\bar Y_{\qp,k} \| = \OO(\sqrt{k/n}),\qquad
(c)\quad \|W_{\qp,k}\Phi_{\qp,k} \| = \OO(1/\sqrt{n}).
\]
\end{lem}
Note the difference with~\rf(eqn:exponentialNorm).  We prove \rf(lem:normEstimations) in \rf(app:normEstimations).  

With this result, it is not hard to 
 show that $\alpha_k=\max\{n^{1/3}-k,0\}$ is a good choice for
 the values of $\alpha_k$ in the decomposition~\rf(eqn:decomposition). 
Indeed, for different $k$, all the operators $\bar \oX_{\qp,k}$ are orthogonal, and the same is true for $\bar \oY_{\qp,k}$ and $\oW_{\qp,k}\Phi_{\qp,k}$.
Hence, the following conditions ensure that $\|\Delta_1\diamond \tilde\Gamma_\qp\| = \OO(1)$:
\[
|\alpha_{k-1}-\alpha_k|\leq 1,\qquad
|\alpha_k|\leq \sqrt{n/k},
\quad \text{and} \quad 
|\alpha_k|\le \sqrt{n}
\]
for all $k$.  
Our choice $\alpha_k=\max\{n^{1/3}-k,0\}$ satisfy these conditions, giving us
\[
\big\|\tilde\Gamma_{\qp}\big\|  \geq
\big\|\alpha_0\bar\oW_{\qp,0}\big\|  =
\big\|\alpha_0\oW_{\qp,0}\big\|  =
\alpha_0=n^{1/3}.
\]


% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 
\subsection{Removal of Illegal Rows and Columns} \label{sec:subIllegal}
% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 
So far we have only constructed the matrix $\tilde\Gamma_\qp$ in which the actual adversary
 matrix $\Gamma_\qp$ is embedded.
We obtain $\Gamma_\qp$ by deleting all the illegal rows and columns of $\tilde\Gamma_\qp$.
We already have \rf(eqn:DeltaiNorms), and it is left to show that $\|\Gamma_\qp\|$ is not much smaller than $\|\tilde\Gamma_\qp\|$, in particular, not much smaller than $\alpha_0$.

We have $\Gamma_\qp=\sum_k\alpha_k\check \oW_{\qp,k}$, where
 $\check \oW_{\qp,k}$ is obtained form $\bar \oW_{\qp,k}$ by deleting all the illegal rows and
 columns. 
 Let us assume that $q\in\Omega(n^2)$, so that a constant ratio of rows and
 columns of $\tilde\Gamma_\qp$ remains in $\Gamma_\qp$.
 In particular, since $\bar \oW_{\qp,0}=\oW_{\qp,0}$ is the matrix of all entries equal and $\|\bar \oW_{\qp,0}\|=1$, we have $\|\check \oW_{\qp,0}\|=\Omega(1)$
 and its principal right-singular vector is the all-ones vector $\mathbf 1_{q!/(q-2n)!}$ of length $q!/(q-2n)!$.  All that is left to show is that
 $\check \oW_{\qp,k} \mathbf 1_{q!/(q-2n)!}=0$ whenever $k\neq 0$.

\newcommand{\legal}{\mathrm{legal}}
\newcommand{\illegal}{\mathrm{illegal}}
Let us split $\cH^{\otimes 2n}=\cH_{\legal}\oplus\cH_{\illegal}$, where $\cH_{\legal}$ and $\cH_{\illegal}$ are the spaces spanned by standard basis vectors corresponding to legal and illegal negative inputs, respectively.
 Let us further decompose
\[
\cH_{\legal}=\bigoplus\nolimits_{L\subset[q],|L|=2n}\cH_{\legal,L},
\]
 where $\cH_{\legal,L}$ is the space spanned by standard basis vectors corresponding to negative inputs $x\in[q]^{2n}$ 
such that entries of $x$ form the set $L$ of size $2n$. It is easy to see that, for all $L$, 
 $\cH_{\legal,L}$ is invariant under the action of $\S_{[2n]}$.  
Since $\bar\cH_{\se,k}\subseteq \bar\cH_{\cp,k}=\bar\cH_{k}^{(2n)}$,
if suffices to show
$
\bar\Pi_k^{(2n)}\Pi_{\legal,L}\mathbf 1_{q^{2n}}=0$,
 where $\mathbf 1_{q^{2n}}$ is the all-ones vector of length $q^{2n}$.

Note that the action of $\S_{[2n]}$ on $\cH_{\legal,L}$ is isomorphic to the regular representation of $\S_{[2n]}$, and we can decompose
\[
\cH_{\legal,L}=\bigoplus\nolimits_{\sigma\vdash 2n}\cH_{\legal,L,\sigma},
\]
 where
$\cH_{\legal,L,\sigma}$ is the subspace corresponding to $\dim\sigma$ copies of  the irrep $\sigma$ in the regular representation. 
Since we consider the regular representation, we have
$\Pi_{\legal,L,\sigma}\mathbf 1_{q^{2n}}=0$
 whenever $\sigma\neq(2n)$. So it is enough to consider 
$\Pi_{\legal,L,(2n)}$, but from the definition of $\bar\Pi_k^{(2n)}$ we have $\bar\Pi_k^{(2n)}\Pi_{\legal,L,(2n)}=0$ whenever $k\neq 0$.
Hence $\check \oW_{\qp,k} \mathbf 1_{q!/(q-2n)!}=0$ whenever $k\neq 0$, and $\|\Gamma_\qp\|=\Omega(\alpha_0)$. This gives us the main theorem of the paper.
\begin{thm}\label{thm:main}
For both $\qp\in\{\cp,\se\}$, let
\[
\tilde\Gamma_\qp=\sum\nolimits_{k=0}^{n^{1/3}}(n^{1/3}-k)\bar\oW_{\qp,k},
\]
where $\bar\oW_{\qp,k}$ is defined in \refeqn{Wbar}, and let $\Gamma_\qp$ be obtained from
$\tilde\Gamma_\qp$ by removing all the illegal rows and columns. 
Given that $q\in\Omega(n^2)$, $\Gamma_\cp$ and 
$\Gamma_\se$ are adversary matrices for \cpp and \sep, respectively,
giving an $\Omega(n^{1/3})$ lower bound on the quantum query complexity of both problems.
\end{thm}


%============================================================
\section{Discussion} \label{sec:concl}
%============================================================
In the paper, we prove tight lower bounds on the \cpp and \sep problems using the adversary method.
This is done by restricting the construction from~\cite{belovs:onThePower} on some specified irreducible representations of the symmetric group.

One oddity of this result is that it heavily uses the symmetry of the problem that is more typical for the polynomial method.  It is an interesting question whether the representation theory of the symmetric group can be avoided in the proof.  In particular, consider the problem of distinguishing a 1-to-1 input from a 2-to-1 input whose matching, as defined in \rf(sec:analysis), belongs to some specified set of matchings $M$.  Is it possible to characterise the quantum query complexity of this problem by a simple optimisation problem involving $M$?

Another open problem is whether the results in this paper can be combined with the results in~\cite{belovs:onThePower} in order to prove tight lower bounds for the {\sc $k$-distinctness} problem.  In particular, is the algorithm in~\cite{belovs:learningKDist} optimal?



\section*{Acknowledgment}
A.R. would like to thank Andris Ambainis, Chris Godsil, Robin Kothari, and Robert {\v S}palek for fruitful discussions. 
This research was performed while A.B. was at the University of Latvia supported by
the ERC Advanced Grant MQC and FP7 FET Proactive project QALGO. 
 A.R. acknowledges the support of Mike and Ophelia Lazaridis Fellowship, David R. Cheriton Graduate Scholarship, and the US ARO.







\bibliographystyle{../../habbrvN}
\bibliography{../../bib}









\appendix \section*{Appendix}
%====================================================================================
\section{Proof of \rf(lem:normEstimations)} \label{app:normEstimations}
%====================================================================================
Fix the value of $k$.  Assume $m\ge 2k$ is some integer, and consider the symmetric group $\S_m$.
Let $\kappa \in \R\S_m$ be defined by
\begin{equation}
\label{eqn:kappa}
\kappa = \frac{1}{2^{k}}\; (\eps - (a_1,b_1))(\eps - (a_2,b_2))\cdots (\eps - (a_k, b_k)).
\end{equation}
Here, $a_1,b_1,\dots,a_k,b_k$ are some distinct fixed elements of $[m]$, $\eps$ is the identity element of $\S_m$, and $(a_i,b_i)$ denotes the transposition of $a_i$ and $b_i$.

\begin{lem}
\label{lem:kappa}
For any $\lambda\vdash k$, the irreducible $\R\S_m$-module $\specht{(m-k,\lambda)}$ contains a non-zero vector $v$ satisfying $\kappa v = v$, where $\kappa$ is given by~\rf(eqn:kappa).
\end{lem}

\newcommand{\et}{\mathbf e_t}
\pfstart
In the proof, we use the notions and results from~\cite[Section 2.3]{sagan:symmetricGroup}.
Let $\ell=\lambda_1$, and let $t$ be a tableau of the shape $(m-k,\lambda)$ with $a_1,\dots,a_k$ being the first $k$ elements of the first row, and $b_1,\dots,b_k$ being the elements of the remaining rows, so that $b_1,\dots,b_{\ell}$ form the second row.  Let $\{C_1,\dots,C_\ell\}$ be the set of the columns of $t$ of lengths greater than 1.

Recall from~\cite[Section 2.3]{sagan:symmetricGroup} the non-zero vector $\et \in \specht{(m-k,\lambda)}$ that satisfies $\kappa_t\et = \et$, where $\kappa_t = C_1^{-}\cdots C_\ell^{-}$ and 
\[
C^{-} = \frac{1}{|C|!} \sum_{\pi\in \S_{C}} \sgn \pi\; \pi.
\]
Take $v = (\eps - (a_{\ell+1},b_{\ell+1}))\cdots (\eps - (a_k,b_k)) \et$.  Then, clearly, $\frac12 (\eps - (a_i,b_i)) v = v$ for $i>\ell$.  
Also, for $i\le\ell$, $\frac12 (\eps - (a_i, b_i)) v = v$, because $(\eps - (a_i, b_i)) \pi  = \pi (\eps - (a_i, b_i))$ for any $\pi\in\S_m$ that leaves $a_i$ and $b_i$ fixed and $\frac12 (\eps - (a_i, b_i)) C_i^{-}=C_i^{-}$.  Finally, it is easy to check that $v\ne 0$.  Indeed, no tabloid present in $\et$ can be cancelled by other terms of $v$, because they have different content of the first row.
\pfend

\begin{lem}
\label{lem:Wkv}
For any vector $v\in\cH^{(2n)}_k$ satisfying $\kappa v = v$ and any matching $\mu$, we have $\|W_k^\mu v\|\le \|v\|$, $\|X_k^\mu v\|\le \|v\|$, and $\|Y_k^\mu v\|\le \|v\|$, 
where $W_k^\mu$, $X_k^\mu$ and $Y_k^\mu$ are defined in~\rf(eqn:Fsigma) and~\rf(eqn:GHI).
\end{lem}

\pfstart
We prove the result for $W_k^\mu$, the proofs for $X_k^\mu$ and $Y_k^\mu$ being similar.
All vectors in the proof are considered in the $e$-basis.
We say that a basis vector is {\em used} in $v$, if it has a non-zero coefficient.  Let $A_i = \{a_i,b_i\}$ be the pairs from the definition of $\kappa$.  Note that
\begin{equation}
\label{eqn:vUses}
\text{each basis vector used in $v$ has exactly one non-zero component positioned in each $A_i$.}
\end{equation}

Split the basis vectors into equivalence classes by assigning two vectors to the same equivalence class iff they can be obtained from one another by a permutation used in $\kappa$, i.e., by permuting elements inside $A_i$.
In $v$, the coefficients of the basis vectors in one equivalence class are all equal up to a sign.

If $\mu$ contains a pair $A_i$ for some $i$, then $W_k^\mu v = 0$, so assume it is not the case.  We construct the following graph $G$ that depends on $\kappa$ and $\mu$.  Its vertex set is formed by the pairs $A_1,\dots, A_k$ and the singletons $\{j\}$ for $j\in [2n]\setminus \bigcup_i A_i$.  For each pair in $\mu$, connect the sets containing the elements of the pair by an edge.  The graph $G$ does not contain loops, but it may have parallel edges.  The graph $G$ has maximal degree 2, so it is a collection of paths and cycles.  Let $c$  denote the number of cycles in $G$.

The operator $W_k^\mu$ maps basis vectors of $\cH^{\otimes 2n}$ into basis vectors of $\cH^{\otimes n}$ (that correspond to the labelling of the edges of $G$) or the zero vector.  Let $v'$ be the vector $v$ with all terms that are mapped to 0 by $W_k^\mu$ removed.  We claim that $\|v'\|\le \|v\|/\sqrt{2^c}$.  Indeed, in any equivalence class, for each cycle, at least half of the vectors are mapped to 0 (for an edge matches two non-zero components in them).


Next, we claim that each basis vector in the range of $W_k^\mu$ has exactly $0$ or $2^c$ preimages among the basis vectors of the domain that satisfy (\ref{eqn:vUses}). 
Indeed, consider a labelling of the edges of $G$, and our task is to count the number of basis vectors in $\cH^{\otimes 2n}$ such that each $A_i$ contains exactly one non-zero component, and each edge matches $e_0$ and its label (which is either $e_0$ as well or a non-zero component).
Assume there is at least one way to satisfy these requirements.
Then, for each path in $G$, all edges but one are labeled by a non-zero component and there is a unique way to satisfy it.  For each cycle, there are two possibilities.
 

Since distinct basis vectors in the range of $W_k^\mu$ have no common preimage,
 we have $\|W_k^\mu v\| = \|W_k^\mu v'\| \le \sqrt{2^c} \|v'\| \le \|v\|$.
\pfend


Now we are ready to prove \rf(lem:normEstimations).
Let us start with point (a) stating that $\|\bar X_{\qp,k}\|\le 1$, where $\bar X_{\qp,k} = X_{\qp, k} (\Pi_0\otimes \bar\Pi_{\qp,k}')$.
This matrix is symmetric with respect to $\S'_\qp$.  Hence, Schur's lemma implies that there exists an irreducible $\R\S'_\qp$-module all consisting of right singular vectors of $\bar X_{\qp,k}$ of singular value $\|\bar X_{\qp,k}\|$.

By the definition of $\bar\Pi_{\qp,k}'$, the module is isomorphic to either $\specht{(2n-1-k,\lambda)}$ with $\lambda \vdash k$ for \cpp, or $\specht{(n-1-\ell,\lambda)}\otimes \specht{(n-k+\ell,\lambda')}$ with $\lambda\vdash \ell$ and $\lambda'\vdash k-\ell$ for \sep.  By \rf(lem:kappa), in both cases, there exists a non-zero vector $v$ in the module satisfying $\kappa v = v$ for some choice of $a_1,\dots,b_k$ (in the case of \sep, one has to take the tensor product of two vectors obtained by two applications of \rf(lem:kappa)).  By \rf(lem:Wkv), $\|X_k^\mu v\|\le \|v\|$, hence, $\|X_{\qp, k} v\|\le \|v\|$, and $\|\bar X_{\qp, k}\|\le 1$.

Consider case (b) now.  Similarly as for (a), we get a right singular vector $v$ of singular value $\|\bar Y_{\qp, k}\|$ such that $\kappa v = v$.  Note that, if $\mu$ matches 1 with an element outside $\{a_1,b_1,\dots,a_k,b_k\}$, then, because of~\rf(eqn:vUses), $Y_{\qp,k}^\mu v = 0$.  
Otherwise, 
we still get $\|Y^\mu_{\qp, k} v\|\le 1$ by \rf(lem:Wkv). The latter case only holds for an $\OO(k/n)$ fraction of all matchings, hence $\|\bar Y_{\qp ,k}\|= \OO(\sqrt{k/n})$.

Now, let us prove (c).
From \rf(lem:newMain), we know that $\normA|\Phi_k^{(m)}|=\OO(1/\sqrt{m})$ and $W_{\qp,k}\Phi_{\qp,k} = W_{\qp,k}\bbPi_{k}\Phi_{\qp,k}$.  So, it suffices to prove that $\|W_{\qp,k}\bbPi_{k} \| = \OO(1)$.
This time consider
\(
\kappa' = 2^{1-k}\; (\eps - (a_1,b_1))(\eps - (a_2,b_2))\cdots (\eps - (a_{k-1}, b_{k-1})).
\)
By an argument similar to (a), we get that $W_{\qp,k}$ has a right singular vector $v\in \bbcH_{\qp,k}$ of  singular value $\|W_{\qp,k}\bbPi_{k} \|$ that satisfies $\kappa'v=v$.  Now we proceed by modifying the proof of \rf(lem:Wkv).  
Again, we define $A_i=\{a_i,b_i\}$ for $i\in[k-1]$, and the equivalence classes as before.
Each of $A_i$ has to contain one non-zero component.  One of them may contain two non-zero components, or there can be one non-zero component in a singleton.

It suffices to prove that $\|W_k^\mu v\|\le \sqrt{3}\|v\|$ for any matching $\mu$.
Again, if $\mu$ has one of $A_i$ as a pair, then $W_k^\mu v=0$, so we may assume it is not the case, and define $G$ as before.
Consider a labelling of the edges of $G$ (that is, a basis vector of $\cH^{\otimes k}$), and let us count the number of preimages of this labelling.  Each cycle must have all its edges labelled by non-zero components, and there are two ways to satisfy it.  All paths, except one, have exactly one edge labelled by the zero component $e_0$.  They can be satisfied in a unique way.  One path has all its edges labelled by non-zero components.  We call it special.  Let $T$ be the length of the special path.  Then, it can be satisfied in $T+1$ ways, hence, the edge labelling has $(T+1)2^c$ preimages.

For basis vectors in $\cH^{\otimes 2n}$, we call a path special if the total number of non-zero components at the endpoints of its edges is equal to its length. 
All vectors of an equivalence class have the same special path.  Let us label all paths in $G$ with numbers from 1 to $\ell$, and let $T_i$ be the length of the $i$th path.  Let us decompose $v = v_1+\dots +v_\ell$ where $v_i$ only uses basis vectors with the $i$th special path.  Similarly to the proof of \rf(lem:Wkv), let $v_i'$ be the vector $v_i$ with terms mapped to 0 by $W_k^\mu$ removed.  
It is not hard to check that $\|v'_i\|\le \|v_i\|/\sqrt{2^{c+\max\{T_i-2,0\}}}$.  Hence, $\|W_k^\mu v_i\|\le \sqrt{(T_i+1)/2^{\max\{T_i-2,0\}}}\|v_i\| \le \sqrt{3}\|v_i\|$.  As $\{W_k^\mu v_i\}$ are orthogonal, we get that $\|W_k^\mu v\|\le \sqrt{3}\|v\|$.





%====================================================================================
\section{Proof of \rf(lem:newMain)} \label{app:newMain}
%====================================================================================
In this appendix, we give a proof of \rf(lem:newMain).  
For that, we need more background on the representation theory beneath our construction of the adversary matrix $\tilde\Gamma_\qp$.

\subsection{More on Representation Theory}

\paragraph{Young diagrams.}
For a Young diagram $\lambda$, let $\lambda^\top$ denote the transposed diagram of $\lambda$, i.e., the number of boxes in the $i$-th row of $\lambda^\top$ equals to the number of boxes in the $i$-th column of $\lambda$.
%
We write $\theta\preceq \lambda$ if a Young diagram $\theta$ is contained in $\lambda$, namely,
 if $\theta_i \le \lambda_i$ for all $i$.  We write $\theta\prec_1 \lambda$ if $\theta\preceq \lambda$ and $|\theta|=|\lambda|-1$.
%
The {\em distance} %~\cite[Sec.~3.3]{james:symmetric}
 between two boxes $b=(i,j)$ and $b'=(i',j')$ is defined as
\(
  d(b,b') = |i'-i|+|j-j'|
\).


\paragraph{Representations.}


Let us briefly describe the restriction and induction of representations.  Firstly, the {\em branching rule} says that the restriction of $S^\lambda$ from $\S_m$ to $\S_{m-1}$ is
\[
S^\lambda \downarrow_{\S_{m-1}}^{\S_m} \cong \bigoplus_{\lambda^-\prec_1\lambda} S^{\lambda^-}.
\]
We also need a more general Littlewood-Richardson rule.
Here we present only a very special case of the rule.
Let $\hat\lambda$ be the Young diagram that is obtained from $\lambda$ by removing a box in every column of $\lambda$, i.e., $\hat\lambda^\top_i = \max\{\lambda^\top_i-1,0\}$,
and let $\tilde\Lambda(\lambda)$ be the set of all Young diagrams $\tilde\lambda$ such that $\hat\lambda\preceq\tilde\lambda\preceq\lambda$,
 that is, $\tilde\lambda$ that are obtained from $\lambda$ by removing at most one box per column.
The Littlewood-Richardson rule states that, if $\lambda\vdash k$, then
\[
S^\lambda \times S^{(m-k)} \uparrow_{\S_k\times \S_{m-k}}^{\S_m} \cong
 \bigoplus
 S^{(m-|\tilde\lambda|,\tilde\lambda)},
\]
where the direct sum is over all $\tilde\lambda\in\tilde\Lambda(\lambda)$ satisfying $m-|\tilde\lambda|\geq \tilde\lambda_1$.

Let $\cK$ be a vector space of dimension $r$.
Consider the general linear group $GL(\cK)$, the group of invertible operators acting on $\cK$.
There is one-to-one correspondence between integral irreps of $GL(\cK)$ and Young diagrams having at most $r$ rows.
For such a Young diagram $\lambda$, let $\weyl{\lambda}r$ denote the corresponding irrep of $GL(\cK)$.  It is known as the Weyl module.

Let $m$ be a positive integer, and consider the space $\cK^{\otimes m}$.
Then $U\in GL(\cK)$ acts on this space by simultaneous matrix multiplication, that is,
\begin{equation}
\label{eqn:GLaction}
U:v_1\otimes\ldots\otimes v_{m}\mapsto Uv_1\otimes\ldots\otimes Uv_{m} = U^{\otimes m}(v_1\otimes\ldots\otimes v_{m}).
\end{equation}
The symmetric group $\S_{m}$ acts on $\cK^{\otimes m}$ by permuting the tensor factors, that is, for $\pi\in \S_{m}$, we have
\begin{equation}
\label{eqn:piaction}
\pi:v_1\otimes\ldots\otimes v_{m}\mapsto v_{\pi^{-1}(1)}\otimes\ldots\otimes v_{\pi^{-1}(m)}.
\end{equation}
These actions of $GL(\cK)$ and $\S_{m}$ commute, thus, they define a representation of their direct product, $GL(\cK)\times\S_m$.

\begin{thm}[Schur-Weyl duality]
\label{thm:SchurWeyl}
Given that $r=\dim\cK\ge m$, the above representation of $GL(\cK)\times \S_{m}$ on $\cK^{\otimes m}$ can be decomposed as a direct sum of irreps $\weyl{\lambda}r\times\specht\lambda$ taken over all $\lambda\vdash m$.
\end{thm}


%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\subsection{Decomposition of \texorpdfstring{$\cH^{\otimes k}$}{Hk} into Irreps} \label{sec:subRMirreps}
%  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\newcommand{\G}{GL(\cH_1)}
In this section, we consider the space $\cH^{\otimes k}$ we defined in \rf(sec:analysis) in more detail.
Recall that, in that section, we considered the permutations of the indices of the input variables.  In this section, we additionally consider the permutations of their values.
Namely, we consider the action of $\G\times\S_m$ on $\cH^{\otimes m}$.
The action of $\S_m$ is given by~(\ref{eqn:piaction}).  The action of $GL(\cH_1)$ is given by~\rf(eqn:GLaction), where $U\in GL(\cH_1)$ is embedded into $GL(\cH)$ using the assumption $Ue_0=e_0$.  Again, these operations commute, so they provide a legitimate representation of $GL(\cH_1)\times \S_m$.  Let us denote the action of $U\in\G$ and $\pi\in \S_m$ on $\cH^{\otimes m}$ by $R_m(U,\pi)$.

It is not hard to see that the subspace $\cH^{(m)}_k$ is invariant under the action of this group.  Thus, it remains to show how $\cH_k^{(m)}$ decomposes into irreps. 
First, consider the subspace $\cH_1^{\otimes k}\otimes\cH_0^{\otimes (m-k)}\subseteq\cH_k^{(m)}$, which is invariant under the action of $\G\times (\S_{[1..k]}\times \S_{[k+1..m]})$ and therefore defines a representation of this group. 
Note that $\G$ and $\S_{[k+1..m]}$ act trivially on the last $m-k$ multipliers in the tensor product. 
The largest value of $m$ we care about will be $2n$, thus, we have $\dim\cH_1=q-1\geq m$.
Hence, the Schur-Weyl duality says that this representation decomposes as a direct sum of the irreps $\weyl\lambda{q-1}\times\specht\lambda\times \specht{(m-k)}$, where the sum is over all $\lambda\vdash k$.
 Now we induce this representation of $\G\times (\S_{[1..k]}\times \S_{[k+1..m]})$ on $\cH_1^{\otimes k}\otimes\cH_0^{\otimes (m-k)}$ to a representation of $\G\times \S_{m}$ on $\cH_k^{(m)}$, and the Littlewood-Richardson rule gives us the following:
\begin{lem}
\label{lem:irreps}
The subspace $\cH_k^{(m)}$ can be decomposed as the direct sum of subspaces $\cH^{\lambda}_{(m-|\tilde\lambda|,\tilde\lambda)}$ corresponding to irreps $\weyl\lambda{q-1}\times\specht{(m-|\tilde\lambda|,\tilde\lambda)}$ of $\G\times \S_{m}$, where the sum is taken over all $\lambda\vdash k$ and  $\tilde\lambda\in\tilde\Lambda(\lambda)$ such that
 $m-|\tilde\lambda| > \tilde\lambda_1$.
\end{lem}
In particular, this representation is multiplicity-free,
that is, each irrep appears in it at most once.




\subsection{The Proof}
In this section, we finally prove \rf(lem:newMain).
Let $\S_{m-1}$ stand for $\S_{[2..m]}$.
For $\sigma\vdash m$, define $\cH^{(m)}_{k,\sigma}$ to be the subspace of $\cH^{(m)}_k$ spanned by the irreps of $\S_m$ isomorphic to $\cS^\sigma$. 
From the previous section, we know that $\cH^{(m)}_{k,(m-k,\lambda)}=\cH^{\lambda}_{(m-k,\lambda)}$,
 that is, it is the subspace corresponding to the unique copy of the
irrep $\weyl\lambda{q-1}\times\specht{(m-k,\lambda)}$ of $\G\times \S_m$ appearing in $\cH^{(m)}_k$.
We want to see how the subspace $\cH^{(m)}_k$ divides into the irreps of $\G\times \S_{m-1}$. 
Unlike in the case of $\G\times \S_{m}$, the representation is not multiplicity-free any longer. 
Therefore, when there are multiple copies of the same irrep in the representation, we would like to have a way to address a single copy.
Let us consider two ways of doing that.


% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\paragraph{Way 1: restricting an irrep of $\G\times \S_{m}$.}

We can take an irrep $\weyl\lambda{q-1}\times\specht\sigma$ of $\G\times \S_m$, corresponding to the subspace $\cH^{\lambda}_{\sigma}$, and restrict it to $\G\times \S_{m-1}$.
The restricted representation will be a direct sum over all irreps $\weyl\lambda{q-1}\times\specht{\sigma^-}$ such that $\sigma^-\prec_1\sigma$, and we denote the space corresponding to such an irrep by $\cH^{\lambda}_{\sigma^-;\sigma}$. 
%
 Thus, we may obtain multiple copies of the same irrep, but all of them are uniquely labeled. 


The specific irreps we are interested in appear in $\cH^{(m)}_k$ only once or twice. 
Irreps of the form $\weyl\lambda{q-1}\times\specht{(m-k-1,\lambda)}$ appear only once as they are only present in the restriction of $\weyl\lambda{q-1}\times\specht{(m-k,\lambda)}$.
For $\lambda^-\prec_1\lambda$, irreps of the form $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$ appear twice as they are present in the restrictions of $\weyl\lambda{q-1}\times\specht{(m-k+1,\lambda^-)}$ and $\weyl\lambda{q-1}\times\specht{(m-k,\lambda)}$. 
For shortness, let us use denotations
\begin{align*}
&\hat\cH^{\lambda}_{(m-k-1,\lambda)}     = \cH^{\lambda}_{(m-k-1,\lambda);(m-k,\lambda)}, \\
&\check\cH^{\lambda}_{(m-k,\lambda^-)} = \cH^{\lambda}_{(m-k,\lambda^-);(m-k+1,\lambda^-)}, \\ 
&\hat\cH^{\lambda}_{(m-k,\lambda^-)}    = \cH^{\lambda}_{(m-k,\lambda^-);(m-k,\lambda)}.
\end{align*}
We have
\begin{equation}
\label{eq:decomp}
 \cH^{\lambda}_{(m-k,\lambda)} = \hat\cH^{\lambda}_{(m-k-1,\lambda)} \oplus \bigoplus\nolimits_{\lambda^-\prec_1\lambda} \hat\cH^{\lambda}_{(m-k,\lambda^-)}.
\end{equation}

% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\paragraph{Way 2: considering $\cH_0\otimes \cH_{k}^{(m-1)}$ and $\cH_1\otimes \cH_{k-1}^{(m-1)}$ separately.}

Notice that, for $k\neq 0$, we have
\[
\cH_k^{(m)}=\cH_0\otimes \cH_{k}^{(m-1)}\oplus \cH_1\otimes \cH_{k-1}^{(m-1)},
\]
and both $\cH_0\otimes \cH_{k}^{(m-1)}$ and $\cH_1\otimes \cH_{k-1}^{(m-1)}$ are invariant under $\G\times \S_{m-1}$, thus defining two representations of the group. 
Let us first consider $\cH_0\otimes \cH_{k}^{(m-1)}$. 
The action of $\G\times \S_{m-1}$ on $\cH_0\otimes \cH_{k}^{(m-1)}$ is isomorphic to its action on $\cH_k^{(m-1)}$. 
In turn, \rf(lem:irreps) describes how $\cH_k^{(m-1)}$ decomposes into irreps of $\G\times \S_{m-1}$.
Hence, $\cH_0\otimes\cH_k^{(m-1)}$ decomposes as the direct sum of spaces $\cH_0\otimes\tilde\cH^{\lambda}_{(m-|\tilde\lambda|-1,\tilde\lambda)}$ corresponding to irreps $\weyl\lambda{q-1}\times\specht{(m-|\tilde\lambda|-1,\tilde\lambda)}$ of $\G\times \S_{m-1}$, where the sum is taken over all $\lambda\vdash k$ and  
 $\tilde\lambda\in\tilde\Lambda(\lambda)$.

This means that the representation of $\G\times \S_{m-1}$ defined by its action on $\cH_0\otimes\cH^{(m-1)}_k$ is multiplicity-free. 
We denote the subspace of $\cH_0\otimes\cH^{(m-1)}_k$ corresponding to the irrep $\weyl\lambda{q-1}\times\specht{\sigma'}$ by $\cH^{\lambda}_{0,\sigma'}$. 
Since $\weyl\lambda{q-1}\times\specht{(m-k-1,\lambda)}$ is contained in both $\cH^{(m)}_k$ and $\cH_0\otimes\cH^{(m-1)}_k$ exactly once, we have
\[
\hat\cH^{\lambda}_{(m-k-1,\lambda)} = \cH^{\lambda}_{0,(m-k-1,\lambda)} = \cH_0\otimes \tilde\cH^{\lambda}_{(m-k-1,\lambda)}.
\]
For the irrep $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$, where $\lambda^-\prec_1\lambda$, the situation is slightly more complicated as $\cH^{(m)}_k$ contains two copies of it: one in $\cH_0\otimes\cH^{(m-1)}_k$ and one in $\cH_1\otimes\cH^{(m-1)}_{k-1}$.
Let us denote the copy corresponding to the latter by $\cH^{\lambda}_{1,(m-k,\lambda^-)}$. We have
\begin{equation}
\label{eq:twocopies}
\hat\Pi^{\lambda}_{(m-k,\lambda^-)} + \check\Pi^{\lambda}_{(m-k,\lambda^-)} = \Pi^{\lambda}_{0,(m-k,\lambda^-)} + \Pi^{\lambda}_{1,(m-k,\lambda^-)}.
\end{equation}

% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
\paragraph{Overlaps of the copies of the same irrep.}

We would like to calculate what is the overlap between the subspaces $\hat\cH^{\lambda}_{(m-k,\lambda^-)}$ and $\cH^{\lambda}_{0,(m-k,\lambda^-)}$. 
The following lemma puts an upper bound on it:
\begin{lem}
\label{lem:overlap}
Let $d^\lambda_{\lambda^-}(m)$ be the distance in the $(m+1)$-box Young diagram $(m-k+1,\lambda)$ between the two boxes we have to remove in order to obtain $(m-k,\lambda^-)$. 
Then
\begin{equation}
\label{eq:overlap}
\Tr\big[\hat\Pi^{\lambda}_{(m-k,\lambda^-)}\Pi^{\lambda}_{0,(m-k,\lambda^-)}\big]\le\frac{1}{d^{\lambda}_{\lambda^-}(m)}\dim\big(\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}\big).
\end{equation}
\end{lem}
The proof of Lemma \ref{lem:overlap} is rather technical, and we leave it to \rf(sec:overlapProof). 

One can see that $d^\lambda_{\lambda^-}(m)\ge m-2k+2$, with equality achieved by $\lambda=(k)$ and $\lambda^-=(k-1)$. 
Since we consider $k\in o(m)$, we have 
\[
\frac{1}{d^\lambda_{\lambda^-}(m)}=\frac{1}{m}+o\Big(\frac{1}{m}\Big).
\]
Let $\Xi^{\lambda}_{1\leftarrow0,(m-k,\lambda^-)}$ be the {\em transporter} from  
the copy of the irrep $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$ corresponding to the subspace
 $\cH^{\lambda}_{0,(m-k,\lambda^-)}$ to the copy corresponding to the subspace 
 $\cH^{\lambda}_{1,(m-k,\lambda^-)}$,
that is, up to a global phase, the unique operator of the (spectral) norm one of rank
$\dim(\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)})$
 such that
\[
 \Xi^{\lambda}_{1\leftarrow0,(m-k,\lambda^-)}
 (R_m(U,\pi)\Pi^{\lambda}_{0,(m-k,\lambda^-)})
 =
 (R_m(U,\pi)\Pi^{\lambda}_{1,(m-k,\lambda^-)})
 \Xi^{\lambda}_{1\leftarrow0,(m-k,\lambda^-)}
\]
for all $U\in \G$ and $\pi\in \S_{m-1}$.
Define
\[
 \Xi^{\lambda}_{0\leftarrow1,(m-k,\lambda^-)}=(\Xi^{\lambda}_{1\leftarrow0,(m-k,\lambda^-)})^*.
\] 
From (\ref{eq:twocopies}) and (\ref{eq:overlap}) we get
\begin{equation}
\label{eq:hat_decompose}
\hat\Pi^{\lambda}_{(m-k,\lambda^-)} = \Big(\!1-\mathrm{O}\Big(\frac{1}{m}\Big)\!\Big)\Pi^{\lambda}_{1,(m-k,\lambda^-)}  +  \mathrm{O}\Big(\frac{1}{m}\Big)\Pi^{\lambda}_{0,(m-k,\lambda^-)} 
 +   \mathrm{O}\Big(\frac{1}{\sqrt{m}}\Big)   \Xi^{\lambda}_{(m-k,\lambda^-)},
\end{equation}
where 
\[
  \Xi^{\lambda}_{(m-k,\lambda^-)}=\Xi^{\lambda}_{1\leftarrow0,(m-k,\lambda^-)}+\Xi^{\lambda}_{0\leftarrow1,(m-k,\lambda^-)},
\]
which has the norm one.


% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

\paragraph{Connection between $\cH_1\otimes\cH^{(m-1)}_{k-1}$ and $\cH_0\otimes\cH^{(m-1)}_{k-1}$.}

The representation of $\G\times \S_{m-1}$ on $\cH_1\otimes\cH^{(m-1)}_{k-1}$ is not necessarily multiplicity-free.
Nor, for every irrep contained in it, the corresponding subspace can be written in form $\cH_1\otimes\cK$ for some space $\cK$. 
However, we have the following useful result.
\begin{lem}
\label{lem:X0X1}
 For any $\lambda'\vdash k-1$ we have
\[
\bigoplus\nolimits_{\lambda^+\succ_1\lambda'} \cH^{\lambda^+}_{1,(m-k,\lambda')} = \cH_1\otimes \tilde\cH^{\lambda'}_{(m-k,\lambda')}.
\]
\end{lem} 
\begin{proof}
Both spaces $\cH_1\otimes\cH^{(m-1)}_{k-1}$ and $\cH_0\otimes\cH^{(m-1)}_{k-1}$ are invariant under $\S_{m-1}$, and thus contain its representation. 
These representations decompose as $\bigoplus_\sigma\cH_1\otimes\cK'_\sigma$ and $\bigoplus_\sigma\cH_0\otimes\cK''_\sigma$, respectively, where $\sigma\vdash m-1$ and $\cH_1\otimes\cK'_\sigma$ and $\cH_0\otimes\cK''_\sigma$ are subspaces corresponding to (potentially multiple copies of) irrep $S^\sigma$.
 Since we ignore the action of $\G$ here, the first space in the tensor products plays no role, and we have $\cK'_\sigma=\cK''_\sigma=\cH^{(m-1)}_{k-1,\sigma}$.  
Finally, on the one hand side, we have
\[
\cH_1\otimes\cK'_{(m-k,\lambda')} = \bigoplus\nolimits_{\lambda^+\succ_1\lambda'} \cH^{\lambda^+}_{1,(m-k,\lambda')}
\]
and, on the other,
\[
\cH_0\otimes\cK''_{(m-k,\lambda')} = \cH^{\lambda'}_{0,(m-k,\lambda')} = \cH_0\otimes \tilde\cH^{\lambda'}_{(m-k,\lambda')}.
\]
\end{proof}

% = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

\paragraph{Putting everything together.}

We have
\begin{align}
 \bar\Pi_k^{(m)}=\!\!\notag\sum_{\lambda\vdash k}\!\Pi^{\lambda}_{(m-k,\lambda)} 
=  & \sum_{\lambda,\vdash k}\hat\Pi^{\lambda}_{(m-k-1,\lambda)} + \sum_{\lambda\vdash k}\sum_{\lambda^-\prec_1\lambda} \hat\Pi^{\lambda}_{(m-k,\lambda^-)} \\
\notag=  & \sum_{\lambda\vdash k}\hat\Pi^{\lambda}_{(m-k-1,\lambda)} + \sum_{\lambda^- \vdash k-1}\sum_{\;\lambda\succ_1\lambda^-}
          \Big(\big(1-\mathrm{O}\big(\frac{1}{m}\big)\big)\Pi^{\lambda}_{1,(m-k,\lambda^-)} +  \\
\notag     & \hspace{130pt} + \mathrm{O}\big(\frac{1}{m}\big)\Pi^{\lambda}_{0,(m-k,\lambda^-)} + \mathrm{O}\big(\frac{1}{\sqrt{m}}\big)\Xi^{\lambda}_{(m-k,\lambda^-)} \Big)\\
\notag =  & \;\Pi_0\otimes \!\!\!\sum_{\lambda\vdash k}\!\!\tilde\Pi^{\lambda}_{(m-k-1,\lambda)}
    + \Pi_1\otimes \!\!\!\!\!\sum_{\lambda'\vdash k-1}\!\!\!\!\tilde\Pi^{\lambda'}_{(m-1-|\lambda'|,\lambda')} + \Phi_k^{(m)} \\
\notag =  & \;\Pi_0\otimes \bar\Pi_k^{(m-1)}  + \Pi_1\otimes \bar\Pi_{k-1}^{(m-1)} + \Phi_k^{(m)},
\end{align}
where the first equality comes from (\ref{eq:decomp}), the second equality comes from (\ref{eq:hat_decompose}), the third equality comes from Lemma \ref{lem:X0X1}, and 
\begin{equation} \label{eq:Phik}
 \Phi_k^{(m)}= \sum_{\lambda\vdash k}\sum_{\;\lambda^-\prec_1\lambda}
          \Big(-\mathrm{O}\big(\frac{1}{m}\big)\Pi^{\lambda}_{1,(m-k,\lambda^-)} + \mathrm{O}\big(\frac{1}{m}\big)\Pi^{\lambda}_{0,(m-k,\lambda^-)} + \mathrm{O}\big(\frac{1}{\sqrt{m}}\big)\Xi^{\lambda}_{(m-k,\lambda^-)} \Big).
\end{equation}
The norm of $\Phi_k^{(m)}$ is in $\mathrm{O}(1/\sqrt{m})$, because the operators in the brackets of (\ref{eq:Phik}) are orthogonal for different pairs of $\lambda$ and $\lambda^-$. 
Also, one can see that $\Phi_k^{(m)}$ has support on
$\bar{\bar\cH}_{k}^{(m)}$.



%====================================================================================
\subsection{Proof of Lemma \ref{lem:overlap}} \label{sec:overlapProof}
%====================================================================================

We use inductive argument on $m$. 
Consider the groups
\[
 GL(\cH_1),\qquad \S_{m-1}=\S_{[m-1]}, \qquad \S_{m}=\S_{[m]}, \quad\text{and}\quad \S_{m+1}=\S_{[m+1]}
\]
and their action on $\cH^{\otimes (m+1)}$.
The representation of $\G\times \S_{m-1}$ on $\cH^{\otimes (m+1)}$ contains three copies of the irrep $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$.
Using notations similar to the previous section, they are
\begin{align*}
&\cH_a=\cH^{\lambda}_{(m-k,\lambda^-);(m-k+1,\lambda^-);(m-k+2,\lambda^-)}, \\
&\cH_b=\cH^{\lambda}_{(m-k,\lambda^-);(m-k+1,\lambda^-);(m-k+1,\lambda)}, \\
&\cH_c=\cH^{\lambda}_{(m-k,\lambda^-);(m-k,\lambda);(m-k+1,\lambda)},
\end{align*}
where we first restrict an irrep of $\G\times \S_{m+1}$ to $\G\times \S_{m}$, and then restrict the irreps of this restriction further to $\G\times \S_{m-1}$.
Let us consider few other ways how to address copies of $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$. 
The representation of $\G\times \S_{m}$ on $\cH^{\otimes m}\otimes \cH_0$ contains both irreps $\weyl\lambda{q-1}\times\specht{(m-k+1,\lambda^-)}$ and $\weyl\lambda{q-1}\times\specht{(m-k,\lambda)}$ exactly once, and their restrictions to $\G\times \S_{m-1}$ each contains a unique copy of $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$.
Let us denote these copies
\begin{align*}
&\cH'_d=\cH^{\lambda}_{(m-k,\lambda^-);(m-k+1,\lambda^-);\,m+1}, \\
&\cH'_c=\cH^{\lambda}_{(m-k,\lambda^-);(m-k,\lambda);\,m+1},
\end{align*}
respectively. 
Since $\cH^{\otimes (m+1)}$ also contains only one copy of $\weyl\lambda{q-1}\times\specht{(m-k,\lambda)}$, we have $\cH_c=\cH'_c$. 
Finally, $\cH^{\otimes (m-1)}\otimes \cH_0^{\otimes 2}$ contains a unique copy of $\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}$, which we denote by
\[
 \cH''_e=\cH^{\lambda}_{(m-k,\lambda^-);\,m;\,m+1}.
\]

Now let us consider overlaps of these irreps. Let
\[
\gamma^\lambda_{\lambda^-}(m)
= \frac{\Tr\big[\Pi^{\lambda}_{(m-k,\lambda^-);(m-k,\lambda);\,m+1} \Pi^{\lambda}_{(m-k,\lambda^-);\,m;\,m+1}\big]}{\dim\big(\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}\big)}
= \frac{\Tr\big[\Pi_c' \Pi_e''\big]}{\dim\big(\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}\big)}\in[0,1]
\]
and, consistently, let
\[
\gamma^\lambda_{\lambda^-}(m+1)
= \frac{\Tr\big[\Pi^{\lambda}_{(m-k+1,\lambda^-);(m-k+1,\lambda)} \Pi^{\lambda}_{(m-k+1,\lambda^-);\,m+1}\big]}{\dim\big(\weyl\lambda{q-1}\times\specht{(m-k+1,\lambda^-)}\big)}
= \frac{\Tr\big[\Pi_b \Pi'_d \big]}{\dim\big(\weyl\lambda{q-1}\times\specht{(m-k,\lambda^-)}\big)}\in[0,1],
\]
where the last equality comes from the fact that, if two copies of the same irrep have a certain overlap, then the unique irreps in their restrictions also have the same overlap.
Let $\gamma_m=\gamma^\lambda_{\lambda^-}(m)$ and $\gamma_{m+1}=\gamma^\lambda_{\lambda^-}(m+1)$ for short.
Thus, due to the orthogonality of $\Pi_d'$ and $\Pi_c$, we have
\[
\Pi'_d =
\left(\begin{array}{cc}
 (1-\gamma_{m+1})\Pi_a & \sqrt{\gamma_{m+1}(1-\gamma_{m+1})}\Xi_{a\leftarrow b}\\
 \sqrt{\gamma_{m+1}(1-\gamma_{m+1})} \Xi_{b\leftarrow a} & \gamma_{m+1}\Pi_b
\end{array}\right),
\]
which implies
%\[ % non-squashed version 
%\Pi''_e =
%\left(\begin{array}{ccc}
% (1-\gamma_m)(1-\gamma_{m+1})\Pi_a & (1-\gamma_m)\sqrt{\gamma_{m+1}(1-\gamma_{m+1})}\Xi_{a\leftarrow b} & \sqrt{\gamma_m(1-\gamma_m)(1-\gamma_{m+1})}\Xi_{a\leftarrow c}\\
% (1-\gamma_m)\sqrt{\gamma_{m+1}(1-\gamma_{m+1})} \Xi_{b\leftarrow a} & (1-\gamma_m)\gamma_{m+1}\Pi_b & \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\Xi_{b\leftarrow c}\\
% \sqrt{\gamma_m(1-\gamma_m)(1-\gamma_{m+1})}\Xi_{c\leftarrow a} & \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\Xi_{c\leftarrow b} & \gamma_m\Pi_c
%\end{array}\right),
%\]
\[ % squashed version 
\Pi''_e \hspace{-2pt}= \hspace{-2pt}
\left(\begin{array}{ccc}
 \hspace{-8pt}(1-\gamma_m)(1-\gamma_{m+1})\Pi_a \hspace{-10pt} & \hspace{-5pt}(1-\gamma_m)\sqrt{\gamma_{m+1}(1-\gamma_{m+1})}\Xi_{a\leftarrow b} & \hspace{-5pt} \sqrt{\gamma_m(1-\gamma_m)(1-\gamma_{m+1})}\Xi_{a\leftarrow c} \hspace{-6pt}\\
 \hspace{-8pt}(1-\gamma_m)\sqrt{\gamma_{m+1}(1-\gamma_{m+1})} \Xi_{b\leftarrow a} \hspace{-10pt} & \hspace{-5pt}(1-\gamma_m)\gamma_{m+1}\Pi_b & \hspace{-5pt} \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\Xi_{b\leftarrow c} \hspace{-6pt}\\
 \hspace{-8pt}\sqrt{\gamma_m(1-\gamma_m)(1-\gamma_{m+1})}\Xi_{c\leftarrow a} \hspace{-10pt} & \hspace{-5pt}\sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\Xi_{c\leftarrow b} & \hspace{-5pt} \gamma_m\Pi_c \hspace{-6pt}
\end{array}\hspace{-2pt}\right)\hspace{-2pt},
\]
where $\Xi_{a\leftarrow b},\Xi_{a\leftarrow c},\ldots,\Xi_{c\leftarrow b}$ are transporters between different copies of the irrep.


Let $d_m$ be equal to $d^\lambda_{\lambda^-}(m)$ in Lemma \ref{lem:overlap}, that is, let $d_m$ be the distance in $(m-k+1,\lambda)$ between the two boxes we have to remove in order to obtain $(m-k,\lambda^-)$.
 Consistently, let $d_{m+1}=d_m+1$ be
the distance in $(m-k+2,\lambda)$ between the two boxes we have to remove in order to obtain $(m-k+1,\lambda^-)$.
 We have to prove that $\gamma_m\leq 1/d_m$. If $\gamma_m=0$, we are done, so assume $\gamma_m>0$. 

\begin{clm} \label{cl:gamma}We have $\gamma_m\neq 1$ and 
\[\gamma_{m+1}=\frac{d_m-1}{(d_m+1)(1/\gamma_m-1)}.\]
\end{clm}
\begin{proof}
Let $V_{(m,m+1)}$ be the operator permuting the last two instances of the space $\cH$ in $\cH^{\otimes (m+1)}$. 
Any space corresponding to an irrep of $\G\times \S_{m+1}$ is invariant under $V_{(m,m+1)}$, and   $\cH^{\lambda}_{(m-k+1,\lambda)}$ is such a space.
This, in turn, means that the space $\cH_b\oplus\cH_c$ is invariant under $V_{(m,m+1)}$ as well, and the action of $V_{(m,m+1)}$ on this space is given by the orthogonal form~\cite[Section 3.4]{james:symmetricGroup} of irrep $S^{(m-k+1,\lambda)}$, namely,
\[
V_{(m,m+1)}|_{\cH_b\oplus\cH_c}= \left(\begin{array}{cc}
 -\frac{1}{d_m}\Pi_b & \sqrt{1-\frac{1}{d_m^2}}\Xi_{b\leftarrow c}\\
 \sqrt{1-\frac{1}{d_m^2}} \Xi_{c\leftarrow b} & \frac{1}{d_m}\Pi_c
\end{array}\right).
\]
%
Since $V_{(m,m+1)}(\I_\cH^{\otimes (m-1)}\otimes\Pi_0^{\otimes 2})= \I_\cH^{\otimes (m-1)}\otimes\Pi_0^{\otimes 2}$, we also have $V_{(m,m+1)}\Pi_e''=\Pi_e''$.
Thus, we have
\begin{multline*}
\left(\begin{array}{cc}
 -\frac{1}{d_m} & \sqrt{1-\frac{1}{d_m^2}}\\
 \sqrt{1-\frac{1}{d_m^2}}  & \frac{1}{d_m}
\end{array}\right)
\left(\begin{array}{cc}
 (1-\gamma_m)\gamma_{m+1} & \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\\
 \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}} & \gamma_m
\end{array}\right)
=\\=
\left(\begin{array}{cc}
 (1-\gamma_m)\gamma_{m+1} & \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}}\\
 \sqrt{\gamma_m(1-\gamma_m)\gamma_{m+1}} & \gamma_m
\end{array}\right),
\end{multline*}
which clearly cannot hold for $\gamma_m=1$. Simple further calculation proves the claim.
\end{proof}

Suppose the contrary: $\gamma_m>1/d_m$. Then there exists $c>0$ such that $\gamma_m=1/(d_m-\binom{d_m}{2}c)$.
Claim \ref{cl:gamma} gives us
\[
\gamma_{m+1}
 = \frac{d_m-1}{(d_m+1)(d_m-\binom{d_m}{2}c-1)}
 = \frac{1}{d_m+1 - \frac{d_m+1}{d_m-1}\binom{d_m}{2}c}
 = \frac{1}{d_{m+1} - \binom{d_{m+1}}{2}c}.
\]
By repeating the same argument, we get that $\gamma_{m'}=1/(d_{m'}-\binom{d_{m'}}{2}c)$ for all $m'\ge m$.
 However, since $d_{m'}$ grows linearly with $m'$, but $\binom{d_{m'}}{2}$ quadratically, there exists $m'$ such that $\gamma_{m'}\notin[0,1]$, which is a contradiction.



\end{document}
QIP2014.bbl
\begin{thebibliography}{10}

\bibitem{aaronson:structure}
S.~Aaronson and A.~Ambainis.
\newblock The need for structure in quantum speedups.
\newblock In {\em Proc. of 2nd ACM ITCS}, pages 338--352, 2011.
\newblock  \myhref{http://arxiv.org/abs/0911.0996}{{\ttfamily
  arXiv:0911.0996}}.

\bibitem{shi:collisionLower}
S.~Aaronson and Y.~Shi.
\newblock Quantum lower bounds for the collision and the element distinctness
  problems.
\newblock {\em Journal of the ACM}, 51(4):595--605, 2004.

\bibitem{ambainis:adv}
A.~Ambainis.
\newblock Quantum lower bounds by quantum arguments.
\newblock {\em Journal of Computer and System Sciences}, 64(4):750--767, 2002.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0002066}{{\ttfamily
  arXiv:quant-ph/0002066}}.

\bibitem{ambainis:polVsQCC}
A.~Ambainis.
\newblock Polynomial degree vs. quantum query complexity.
\newblock In {\em Proc. of 44th IEEE FOCS}, pages 230--239, 2003.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0305028}{{\ttfamily
  arXiv:quant-ph/0305028}}.

\bibitem{beals:pol}
R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf.
\newblock Quantum lower bounds by polynomials.
\newblock {\em Journal of the ACM}, 48(4):778--797, 2001.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/9802049}{{\ttfamily
  arXiv:quant-ph/9802049}}.

\bibitem{belovs:adv-el-dist}
A.~Belovs.
\newblock Adversary lower bound for element distinctness.
\newblock  \myhref{http://arxiv.org/abs/1204.5074}{{\ttfamily
  arXiv:1204.5074}}, 2012.

\bibitem{belovs:learningKDist}
A.~Belovs.
\newblock Learning-graph-based quantum algorithm for $k$-distinctness.
\newblock In {\em Proc. of 53rd IEEE FOCS}, pages 207--216, 2012.
\newblock  \myhref{http://arxiv.org/abs/1205.1534}{{\ttfamily
  arXiv:1205.1534}}.

\bibitem{belovs:learning}
A.~Belovs.
\newblock Span programs for functions with constant-sized 1-certificates.
\newblock In {\em Proc. of 44th ACM STOC}, pages 77--84, 2012.
\newblock  \myhref{http://arxiv.org/abs/1105.4024}{{\ttfamily
  arXiv:1105.4024}}.

\bibitem{belovs:onThePower}
A.~Belovs and A.~Rosmanis.
\newblock On the power of non-adaptive learning graphs.
\newblock In {\em Proc. of 28th IEEE Complexity}, pages 44--55, 2013.
\newblock  \myhref{http://arxiv.org/abs/1210.3279}{{\ttfamily
  arXiv:1210.3279}}.

\bibitem{spalek:kSumLower}
A.~Belovs and R.~{\v Spalek}.
\newblock Adversary lower bound for the {$k$-sum} problem.
\newblock In {\em Proc. of 4th ACM ITCS}, pages 323--328, 2013.
\newblock  \myhref{http://arxiv.org/abs/1206.6528}{{\ttfamily
  arXiv:1206.6528}}.

\bibitem{brassard:collision}
G.~Brassard, P.~H{\o}yer, and A.~Tapp.
\newblock Quantum cryptanalysis of hash and claw-free functions.
\newblock In {\em Proc. of 3rd LATIN}, volume 1380 of {\em LNCS}, pages
  163--169. Springer, 1998.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/9705002}{{\ttfamily
  arXiv:quant-ph/9705002}}.

\bibitem{buhrman:querySurvey}
H.~Buhrman and R.~de~Wolf.
\newblock Complexity measures and decision tree complexity: a survey.
\newblock {\em Theoretical Computer Science}, 288:21--43, 2002.

\bibitem{curtis:representationTheory}
C.~W. Curtis and I.~Reiner.
\newblock {\em Representation theory of finite groups and associative
  algebras}.
\newblock AMS, 1962.

\bibitem{hoyer:advNegative}
P.~H{\o}yer, T.~Lee, and R.~{\v Spalek}.
\newblock Negative weights make adversaries stronger.
\newblock In {\em Proc. of 39th ACM STOC}, pages 526--535, 2007.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0611054}{{\ttfamily
  arXiv:quant-ph/0611054}}.

\bibitem{james:symmetricGroup}
G.~James and A.~Kerber.
\newblock {\em The Representation Theory of the Symmetric Group}, volume~16 of
  {\em Encyclopedia of Mathematics and its Applications}.
\newblock Addison-Wesley, 1981.

\bibitem{kutin:collisionLower}
S.~Kutin.
\newblock Quantum lower bound for the collision problem with small range.
\newblock {\em Theory of Computing}, 1(1):29--36, 2005.

\bibitem{lee:stateConversion}
T.~Lee, R.~Mittal, B.~W. Reichardt, R.~{\v Spalek}, and M.~Szegedy.
\newblock Quantum query complexity of the state conversion problem.
\newblock In {\em Proc. of 52nd IEEE FOCS}, pages 344--353, 2011.
\newblock  \myhref{http://arxiv.org/abs/1011.3020}{{\ttfamily
  arXiv:1011.3020}}.

\bibitem{lee:strongDirect}
T.~Lee and J.~Roland.
\newblock A strong direct product theorem for quantum query complexity.
\newblock In {\em Proc. of 27th IEEE Complexity}, pages 236--246, 2012.
\newblock  \myhref{http://arxiv.org/abs/1104.4468}{{\ttfamily
  arXiv:1104.4468}}.

\bibitem{midrijanis:setEquality}
G.~Midrij{\=a}nis.
\newblock A polynomial quantum query lower bound for the set equality problem.
\newblock In {\em Proc. of 31st ICALP}, volume 3142 of {\em LNCS}, pages
  996--1005. Springer, 2004.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0401073}{{\ttfamily
  arXiv:quant-ph/0401073}}.

\bibitem{reichardt:advTight}
B.~W. Reichardt.
\newblock Reflections for quantum query algorithms.
\newblock In {\em Proc. of 22nd ACM-SIAM SODA}, pages 560--569, 2011.
\newblock  \myhref{http://arxiv.org/abs/1005.1601}{{\ttfamily
  arXiv:1005.1601}}.

\bibitem{reichardt:formulae}
B.~W. Reichardt and R.~{\v Spalek}.
\newblock Span-program-based quantum algorithm for evaluating formulas.
\newblock {\em Theory of Computing}, 8:291--319, 2012.
\newblock  \myhref{http://arxiv.org/abs/0710.2630}{{\ttfamily
  arXiv:0710.2630}}.

\bibitem{sagan:symmetricGroup}
B.~E. Sagan.
\newblock {\em The symmetric group: representations, combinatorial algorithms,
  and symmetric functions}, volume 203 of {\em Graduate Texts in Mathematics}.
\newblock Springer, 2001.

\bibitem{serre:representation}
J.-P. Serre.
\newblock {\em Linear Representations of Finite Groups}, volume~42 of {\em
  Graduate Texts in Mathematics}.
\newblock Springer, 1977.

\bibitem{shi:collisionLowerOriginal}
Y.~Shi.
\newblock Quantum lower bounds for the collision and the element distinctness
  problems.
\newblock In {\em Proc. of 43th IEEE FOCS}, pages 513�--519, 2002.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0112086}{{\ttfamily
  arXiv:quant-ph/0112086}}.

\bibitem{spalek:adv-array}
R.~{\v Spalek}.
\newblock Adversary lower bound for the orthogonal array problem.
\newblock  \myhref{http://arxiv.org/abs/1304.0845}{{\ttfamily
  arXiv:1304.0845}}, 2013.

\bibitem{spalek:advEquivalent}
R.~{\v Spalek} and M.~Szegedy.
\newblock All quantum adversary methods are equivalent.
\newblock {\em Theory of Computing}, 2:1--18, 2006.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0409116}{{\ttfamily
  arXiv:quant-ph/0409116}}.

\bibitem{zhandry:howToConstruct}
M.~Zhandry.
\newblock How to construct quantum random functions.
\newblock In {\em Proc. of 53rd IEEE FOCS}, pages 679--687, 2012.
\newblock  \myhref{http://eprint.iacr.org/2012/182}{{\ttfamily
  ePrint:2012/182}}.

\bibitem{zhandry:setEquality}
M.~Zhandry.
\newblock A note on the quantum collision and set equality problems.
\newblock  \myhref{http://arxiv.org/abs/1312.1027}{{\ttfamily
  arXiv:1312.1027}}, 2013.

\bibitem{zhang:advPower}
S.~Zhang.
\newblock On the power of {Ambainis} lower bounds.
\newblock {\em Theoretical Computer Science}, 339(2):241--256, 2005.
\newblock  \myhref{http://arxiv.org/abs/quant-ph/0311060}{{\ttfamily
  arXiv:quant-ph/0311060}}.

\end{thebibliography}
