column subspaces of a matrix, that we will require. Let $\mathbb{F}$ be a
field. For any matrix $M\in\mathbb{F}^{N\times K}$, and any $A\subseteq[N]$,
let $M_{A}=M_{[K]\times A}$, and
$\imaginary(M_{A})=\text{span}_{\mathbb{F}}(M_{[K],t}:t\in A)$.

######  Proposition 6.2 ([BGM23]).

Let $K\in[N]$, and $M\in\mathbb{F}^{N\times K}$ be an MDS matrix. Then for any
$A_{1},\ldots,A_{\ell}\subseteq[N]$ such that $|A_{t}|\leq K,\,t\in[\ell]$, we
have

$\dim\bigg{(}\bigcap_{t=1}^{\ell}\imaginary(M_{A_{t}})\bigg{)}=\max_{\begin{subarray}{c}P_{1}\sqcup\cdots\sqcup
P_{u}=[\ell]\\\
\text{partition}\end{subarray}}\bigg{(}\sum_{r=1}^{u}\bigg{|}\bigcap_{t\in
P_{r}}A_{t}\bigg{|}-(u-1)K\bigg{)}$

######  Proposition 6.3 ([Tia19, BGM22]).

Let $K\in[N]$, and $M\in\mathbb{F}^{N\times K}$ be a matrix. Then for any
$A_{1},\ldots,A_{\ell}\subseteq[N]$, we have

$\dim\bigg{(}\bigcap_{t=1}^{\ell}\imaginary(M_{A_{t}})\bigg{)}=\sum_{t=1}^{\ell}\dim(\imaginary(M_{A_{t}}))-\rank\begin{bmatrix}M_{A_{1}}&-M_{A_{2}}&&&\\\
M_{A_{1}}&&-M_{A_{3}}&&\\\ \vdots&&&\ddots&\\\
M_{A_{1}}&&&&-M_{A_{\ell}}\end{bmatrix}.$

Recall that a parity check matrix of $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$
is
$H_{E,k}(Y_{[n]})\coloneqq\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi\cdot
G_{E,sn-k}(Y_{[n]})$. Further, for any $I\subseteq[n]$, denote
$H_{E,k}(Y_{I})=(\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi)\big{|}_{s|I|\times
s|I|}\cdot G_{E,sn-k}(Y_{I})$. We note the following.

######  Observation 6.4.

By Proposition 4.2, it follows that $H_{E,k}(Y_{[n]})$ is an MDS matrix.

We are interested in the full-rankness of the RIM upon removal of some rows.
The number of columns of $\mathsf{RIM}_{I_{J}}^{B}(Y_{[n]\setminus B})$ is
clearly equal to $(|J|-1)k$. The number of rows is equal to

$\displaystyle\sum_{i\in[n]\setminus B}|J^{\prime}_{i}|s$
$\displaystyle=\sum_{i\in[n]\setminus B}(|J_{i}|-1)s$
$\displaystyle=\sum_{j\in J}\sum_{i\in I_{j}}s\cdot\mathbf{1}(j>j_{i})$ by
double counting $\displaystyle=s\cdot\bigg{(}\sum_{j\in J}|I_{j}|-\sum_{j\in
J}\sum_{i\in I_{j}}\mathbf{1}(j=j_{i})\bigg{)}$
$\displaystyle=s\cdot\bigg{(}\sum_{j\in J}|I_{j}|-\bigg{|}\bigcup_{j\in
J}I_{j}\bigg{|}\bigg{)}.$

We therefore define $\text{wt}(I_{J})=\sum_{j\in
J}|I_{j}|-\big{|}\bigcup_{j\in J}I_{j}\big{|}$, so that the number of rows is
equal to $s\cdot\text{wt}(I_{J})$. We can now argue about the full-rankness of
the RIM. Our proof works for polynomial ideal codes, and can be considered to
be a more compact version of the argument in [GZ23].

######  Lemma 6.5.

Consider the generic polynomial ideal code
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$. Let $\lambda>0$, and
$I_{1},\ldots,I_{T}\subseteq[n]$ such that

$\displaystyle\text{wt}(I_{[T]})$ $\displaystyle\geq(1+\lambda)(T-1)k/s,$
$\displaystyle\text{and}\qquad\text{wt}(I_{J})$
$\displaystyle\leq(1+\lambda)(|J|-1)k/s\qquad\text{for all
}J\subseteq[T],\,J\neq\emptyset.$

Then, for any $B\subseteq[n]$ such that $|B|(T-1)\leq\lambda k/s$, we have
$\ker(\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]\setminus B}))=0$.

###### Proof.

Let $I^{\prime}_{j}=I_{j}\setminus B,\,j\in[T]$. Without loss of generality,
we assume $\bigcup_{j=1}^{T}I^{\prime}_{j}=[n^{\prime}]$ for some
$n^{\prime}\leq n$. We have $\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]\setminus
B})=\mathsf{RIM}_{I^{\prime}_{[T]}}(Y_{[n^{\prime}]})$. Further, we have

$\displaystyle\text{wt}(I^{\prime}_{[T]})$
$\displaystyle\geq\text{wt}(I_{[T]})-|B|(T-1)\geq((1+\lambda)(T-1)k-\lambda
k)/s,$ $\displaystyle\text{and}\qquad\text{wt}(I^{\prime}_{J})$
$\displaystyle\leq\text{wt}(I_{J})\leq(1+\lambda)(|J|-1)k/s$
$\displaystyle\text{for all }J\subseteq[T],\,J\neq\emptyset.$

This implies that for all $j\in[T]$,

$\displaystyle|I^{\prime}_{j}|\geq\text{wt}(I^{\prime}_{[T]})-\text{wt}(I^{\prime}_{[T]\setminus\\{j\\}})\geq\frac{k}{s}\quad\implies\quad\big{|}[n^{\prime}]\setminus
I^{\prime}_{j}\big{|}\leq n^{\prime}-\frac{k}{s}.$ (9)

Now suppose $\ker(\mathsf{RIM}_{I^{\prime}_{[T]}}(Y_{[n^{\prime}]}))\neq 0$,
and let $z=\begin{bmatrix}z_{1}\\\ \vdots\\\
z_{T-1}\end{bmatrix}\in\ker(\mathsf{RIM}_{I^{\prime}_{[T]}}(Y_{[n^{\prime}]})),\,z\neq
0^{(T-1)k}$. Further, denote $z_{T}=0^{k}$. Define

$y=\begin{bmatrix}G_{E,k}(Y_{1})z_{j_{1}}\\\ \vdots\\\
G_{E,k}(Y_{n^{\prime}})z_{j_{n^{\prime}}}\end{bmatrix}\in\mathbb{F}_{q}(Y_{[n^{\prime}]})^{sn^{\prime}\times
1}.$

Since
$H_{E,k}(Y_{[n^{\prime}]})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}G_{E,k}(Y_{[n^{\prime}]})=0$,
we immediately have

$\displaystyle
H_{E,k}(Y_{[n^{\prime}]})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\big{(}y-G_{E,k}(Y_{[n^{\prime}]})z_{1}\big{)}=\cdots=H_{E,k}(Y_{[n^{\prime}]})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\big{(}y-G_{E,k}(Y_{[n^{\prime}]})z_{T}\big{)}=H_{E,k}(Y_{[n^{\prime}]})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}y.$
(10)

For every $j\in[T]$, let $A_{j}=[n^{\prime}]\setminus I_{j}^{\prime}$, and by
(9) we have $|A_{j}\big{\uparrow}_{s}|\leq sn^{\prime}-k$. By [AGL23,
Corollary A.4], there exist $\delta_{1},\ldots,\delta_{T}\geq 0$ such that
$\sum_{j=1}^{T}\delta_{t}=sn^{\prime}-k$, and the set system
$\\{Z_{1},\ldots,Z_{sn^{\prime}-k}\\}\subseteq 2^{[sn^{\prime}]}$ is an MDS
zero pattern and consists of $\delta_{j}$ copies of $A_{j}\big{\uparrow}_{s}$,
for $j\in[T]$. Then it is immediate that the set system
$\\{Z_{1}\big{\downarrow}_{s},\ldots,Z_{sn^{\prime}-k}\big{\downarrow}_{s}\\}\subseteq
2^{[n^{\prime}]}$ is an $s$-folded MDS zero pattern, and contains $\delta_{j}$
copies of $A_{j}$, for $j\in[T]$.

Since $H_{E,k}(Y_{[n^{\prime}]})$ is $s$-folded GZP, there exists an
invertible matrix
$M\in\mathbb{F}_{q}(Y_{[n^{\prime}]})^{(sn^{\prime}-k)\times(sn^{\prime}-k)}$
such that $H\coloneqq H_{E,k}(Y_{[n^{\prime}]})\cdot M$ contains
$\\{Z_{1}\big{\downarrow}_{s},\ldots,Z_{sn^{\prime}-k}\big{\downarrow}_{s}\\}$.
We immediately note the following.

  1. (H.a)

For any $v\in\mathbb{F}_{q}(Y_{[n^{\prime}]})^{sn^{\prime}\times 1}$ such that
$\text{supp}(v)\subseteq A_{j}$ for some $j\in[T]$, we have
$\text{supp}(v)\subseteq Z_{t}\big{\downarrow}_{s}$ for some
$t\in[sn^{\prime}-k]$, and so
$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}v=0$.

  2. (H.b)

By the definitions, $\text{supp}(y-G_{E,k}(Y_{[n^{\prime}]})z_{j})\subseteq
A_{j}$ for all $j\in[T]$.

  3. (H.c)

By (10),

$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\big{(}y-G_{E,k}(Y_{[n^{\prime}]})z_{1}\big{)}=\cdots=H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\big{(}y-G_{E,k}(Y_{[n^{\prime}]})z_{T}\big{)}=H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}y,$

since we also have
$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}G_{E,k}(Y_{[n^{\prime}]})=0$.

  4. (H.d)

There exists $j\in[T]$ such that $y-G_{E,k}(Y_{[n^{\prime}]})z_{j}\neq 0$. If
this doesn’t hold, then note that $z_{T}=0$, and so
$y-G_{E,k}(Y_{[n^{\prime}]})z_{T}=y=0$. Further, this implies
$G_{E,k}(Y_{[n^{\prime}]})z_{1}=\cdots=G_{E,k}(Y_{[n^{\prime}]})z_{T-1}=0$,
and so $z_{1}=\cdots=z_{T-1}=0$, a contradiction.

Since $H$ is an MDS matrix (by Observation 6.4), (H.c) and (H.d) imply
$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}y\neq
0$. However, (H.a), (H.b), and (H.c) imply
$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}y=0$,
and thus, we have a contradiction. Hence, we conclude that
$\ker(\mathsf{RIM}_{I^{\prime}_{[T]}}(Y_{[n^{\prime}]}))=0$. ∎

We will now proceed to show that randomly punctured polynomial ideal codes
achieve list-decoding capacity with polynomial alphabet size.

###  6.3 Full-rankness of RIM under random assignment

Let us begin with some definitions. Consider a matrix $M\in\mathbb{F}^{R\times
T}$, where $R\geq T$. We can index every $T\times T$ submatrix (and minor) of
$M$ by the vector of row indices of $M$ defining the submatrix. In other
words, there is an obvious one-to-one correspondence between the $T\times T$
submatrices (and minors) of $M$, and vectors $(r_{1},\ldots,r_{T})\in[R]^{T}$
satisfying $r_{1}<\cdots<r_{T}$. If $A_{(r_{1},\ldots,r_{T})}$ denotes the
$T\times T$ submatrix of $M$ defined by the row indices
$(r_{1},\ldots,r_{T})$, then the corresponding minor is
$\det(A_{(r_{1},\ldots,r_{T})})$. We will order the submatrices
$A_{(r_{1},\ldots,r_{T})}$ of $M$ by the _lexicographic order_ on the row
indices $(r_{1},\ldots,r_{T})$. Denote this order by $\preceq$.

We will now work over the fields $\mathbb{F}_{q}$ and
$\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$. Let
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$ be distinct. Consider a matrix
$M(Y_{[n]})\in\mathbb{F}_{q}(Y_{[n]})^{R\times T}$, where $R\geq T$, such that
$\rank(M(Y_{[n]}))=T$. So $M$ has at least one nonzero $T\times T$ minor. Let
$A(Y_{[n]})$ be the $\preceq$-least submatrix of $M(Y_{[n]})$ such that
$\det(A(Y_{[n]}))\neq 0$. We say $i\in[n]$ is a faulty index of $M(Y_{[n]})$
if

$\det(A(\alpha_{\leq i-1},Y_{i},Y_{\geq i}))\neq
0\quad\text{and}\quad\det(A(\alpha_{\leq i-1},\alpha_{i},Y_{\geq i}))=0.$

The following observation is immediate.

######  Observation 6.6.

For distinct $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$, if $i\in[n]$ is
a faulty index of $M(Y_{[n]})$, then

$\det(A(\alpha_{\leq t},Y_{\geq t+1}))\begin{cases}\neq 0&\text{if }t\leq
i-1,\\\ =0&\text{if }t\geq i.\end{cases}$

Let $k\in[sn]$, and consider the polynomial ideal code
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$. Further, consider
$\lambda>0$, and suppose $\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is
not $(\rho,L)$-average radius list decodable, where

$\rho\leq\frac{L}{L+1}\bigg{(}1-(1+\lambda)\frac{k}{sn}\bigg{)}.$

Let this be witnessed by

$\text{a received word }w=\begin{bmatrix}w_{1}\\\ \vdots\\\
w_{n}\end{bmatrix}=\begin{bmatrix}[w_{1,t}]_{t=0}^{s-1}\\\ \vdots\\\
[w_{n,t}]_{t=0}^{s-1}\end{bmatrix}\in\mathbb{F}^{sn\times 1},$

and codewords
$[f_{1}],\ldots,[f_{L+1}]\in\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$,
where $[f_{j}]=G_{E,k}(\alpha_{[n]})\cdot f_{j}$ for all $j\in[L+1]$. So we
have

$\displaystyle\sum_{j=1}^{L+1}\Delta^{(s)}_{n}([f_{j}],w)\leq(L+1)\rho n\leq
L\bigg{(}n-(1+\lambda)\frac{k}{s}\bigg{)}.$ (11)

For every $j\in[L+1],\,i\in[n]$, let

$I_{j}=\\{i\in[n]:[f_{j}]_{i}=w_{i}\\},\quad\text{and}\quad
J_{i}=\\{j\in[L+1]:[f_{j}]_{i}=w_{i}\\}.$

With these notations, we can now consider the reduced intersection matrix
$\mathsf{RIM}_{I_{[L+1]}}(Y_{[n]})$. By the construction, we immediately see
that

$\mathsf{RIM}_{I_{[L+1]}}(\alpha_{[n]})\cdot\begin{bmatrix}f_{1}-f_{L+1}\\\
\vdots\\\ f_{L}-f_{L+1}\end{bmatrix}=0,$

which means $\ker(\mathsf{RIM}_{I_{[L+1]}}(\alpha_{[n]}))\neq 0$. This also
implies $\ker(\mathsf{RIM}_{I_{J}}(\alpha_{[n]}))\neq 0$, for all
$J\subseteq[L+1],\,J\neq\emptyset$. Now note that we have

$\displaystyle\text{wt}(I_{[L+1]})$
$\displaystyle=\sum_{j=1}^{L+1}|I_{j}|-\bigg{|}\bigcup_{j=1}^{L+1}I_{j}\bigg{|}$
$\displaystyle=\sum_{j=1}^{L+1}(n-\Delta^{(s)}_{n}([f_{j}],w))-\bigg{|}\bigcup_{j=1}^{L+1}I_{j}\bigg{|}$
$\displaystyle\geq n(L+1)-L\bigg{(}n-(1+\lambda)\frac{k}{s}\bigg{)}-n$
$\displaystyle=(1+\lambda)L\cdot\frac{k}{s}.$

Therefore, choose a minimal set $S$, with respect to inclusion, such that
$|S|\geq 2$ and $\text{wt}(I_{S})\geq(1+\lambda)(|S|-1)k/s$. Without loss of
generality, we assume $S=[T]$ for some $T\in[2,L+1]$. (This can be ensured by
a suitable permutation of the set $\\{[f_{1}],\ldots,[f_{L+1}]\\}$.) We thus
have the following.

######  Observation 6.7.

For the choices of parameters made as above, we have

  1. (a)

$\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))\neq 0$.

  2. (b)

$\text{wt}(I_{[T]})\geq(1+\lambda)(|T|-1)k/s$.

  3. (c)

$\text{wt}(I_{J})\leq(1+\lambda)(|J|-1)k/s$, for all
$J\subseteq[T],\,J\neq\emptyset$.

However, by Lemma 6.5, we get

$\ker(\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]\setminus B}))=0,\quad\text{for all
}B\subseteq[n]\text{ such that }|B|(T-1)\leq\lambda\cdot\frac{k}{s}.$

We will now inspect the rank of the generic RIM under partial substitutions,
via Algorithm 1, which is identical to the one in [GZ23], but operates on our
RIM.

Input: Subsets $I_{1},\ldots,I_{T}\subseteq[n]$, distinct elements
$\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}_{q}$, and $r\in\mathbb{Z}^{+}$.

Output: Success, Failure, or a _certificate_ $(i_{1},\dots,i_{r})\in[n]^{r}$.

START

Let $B\leftarrow\emptyset$.

for  _$j=1$ to $r$_ do

if  _$\rank(\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]})) <(T-1)k$_ then

Output Failure. STOP.

else if  _a faulty index $i\in[n]$ of $\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]})$
exists_ then

$i_{j}\leftarrow i$ and $B\leftarrow B\cup\\{i\\}$.

else

Output Success. STOP.

end if

end for

Output $(i_{1},\dots,i_{r})$.

Algorithm 1 Certify-Full-
Rankness($I_{1},\ldots,I_{T},\alpha_{1},\ldots,\alpha_{n},r$)

The output of Algorithm 1 is captured in the following result.

######  Proposition 6.8.

Let $\lambda>0$, and $T\geq 2$. Let
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$ be distinct, and
$I_{1},\ldots,I_{T}\subseteq[n]$ such that

$\displaystyle\text{wt}(I_{[T]})$ $\displaystyle\geq(1+\lambda)(T-1)k/s,$
$\displaystyle\text{and}\qquad\text{wt}(I_{J})$
$\displaystyle\leq(1+\lambda)(|J|-1)k/s\qquad\text{for all
}J\subseteq[T],\,J\neq\emptyset.$

Further, let $r\leq\lfloor(\lambda k)/((T-1)s)\rfloor+1$. Then Certify-Full-
Rankness$(I_{1},\ldots,I_{t},\alpha_{1},\ldots,\alpha_{n},r)$ (Algorithm 1)
will give exactly one of the following two outputs.

  1. (a)

Success. In this case, $\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))=0$.

  2. (b)

A certificate $(i_{1},\ldots,i_{r})\in[n]^{r}$. In this case,
$i_{1},\cdots,i_{r}$ are distinct, where for every $j\in[r]$, the index
$i_{j}$ is the faulty index of $\mathsf{RIM}_{I_{[T]}}^{B_{j}}(Y_{[n]\setminus
B_{j}})$ with $B_{j}=\\{i_{1},\ldots,i_{j-1}\\}$ being the instance of $B$ in
the $j$-th iteration.

###### Proof.

Firstly, for any $j\in[r]$, in the $j$-th iteration, we have $|B|\leq j-1\leq
r-1\lfloor(\lambda k)/((T-1)s)\rfloor$. So by Observation 6.7, we have
$\ker(\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]\setminus B}))=0$. Thus Algorithm 1
cannot output Failure.

Now suppose, for some $j\in[r]$, in the $j$-th iteration, Algorithm 1 outputs
Success and stops. This means there is no faulty index for
$\mathsf{RIM}_{I_{[T]}}^{B}(Y_{[n]\setminus B})$, and therefore,
$\ker(\mathsf{RIM}_{I_{[T]}}^{B}(\alpha_{[n]\setminus B}))=0$. This implies
$\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))=0$.

The remaining possibility is that Algorithm 1 outputs a certificate
$(i_{1},\ldots,i_{r})\in[n]^{r}$, where for every $j\in[r]$, the index $i_{j}$
is the faulty index of $\mathsf{RIM}_{I_{[T]}}^{B_{j}}(Y_{[n]\setminus
B_{j}})$. (Here, we denote $B_{j}$ to be the instance of $B$ in the $j$-th
iteration.) Let us denote $B_{j}=\\{i_{1},\cdots,i_{j-1}\\},\,j\in[r]$. It is
immediate that for any $j\in[r]$, if $i\in[n]$ is a faulty index of
$\mathsf{RIM}_{I_{[T]}}^{B_{j}}(Y_{[n]\setminus B_{j}})$, then $i\not\in
B_{j}$. Thus $i_{1},\cdots,i_{r}$ are distinct. This completes the proof. ∎

We now proceed to inspect the rank of RIM under random partial substitutions.
The argument is nearly identical to that in [GZ23], but we present a proof for
completeness.

######  Proposition 6.9.

Let $q\geq n,\,k\leq q-n+1$, $\lambda>0$, and $T\geq 2$. Let
$I_{1},\ldots,I_{T}\subseteq[n]$ such that

$\displaystyle\text{wt}(I_{[T]})$ $\displaystyle\geq(1+\lambda)(T-1)k/s,$
$\displaystyle\text{and}\qquad\text{wt}(I_{J})$
$\displaystyle\leq(1+\lambda)(|J|-1)k/s\qquad\text{for all
}J\subseteq[T],\,J\neq\emptyset.$

Further, let $r\leq\lfloor(\lambda k)/((T-1)s)\rfloor+1$. Then for any
$(i_{1},\ldots,i_{r})\in[n]^{r}$ such that $i_{1},\ldots,i_{r}$ are distinct,
we have

$\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}\\\
\text{distinct}\end{subarray}}\Big{[}(i_{1},\ldots,i_{r})={\texttt{Certify-
Full-
Rankness}}(I_{1},\ldots,I_{T},\alpha_{1},\ldots,\alpha_{n},r)\Big{]}\leq\bigg{(}\frac{(T-1)(k-1)s\cdot
c(s)}{q-n+1}\bigg{)}^{r}.$

###### Proof.

Fix any $j\in[r]$. Let $B_{j}=\\{i_{1},\ldots,i_{j-1}\\}$. Since $|B_{j}|\leq
j-1\leq r-1\leq\lfloor(\lambda k)/((T-1)s)\rfloor$, by Observation 6.7, we
have $\ker(\mathsf{RIM}_{I_{[T]}}^{B_{j}}(Y_{[n]\setminus B_{j}}))=0$. So let
$A_{j}(Y_{[n]\setminus B_{j}})$ be the $\preceq$-least $(T-1)k\times(T-1)k$
nonsingular submatrix of $\mathsf{RIM}_{I_{[T]}}^{B_{j}}(Y_{[n]\setminus
B_{j}})$. Now define the event $E_{j}$ by

$E_{j}:\qquad\det(A_{j}(\alpha_{\leq i_{j}-1},Y_{i_{j}},Y_{\geq i_{j}}))\neq
0\quad\text{and}\quad\det(A_{j}(\alpha_{\leq i_{j}-1},\alpha_{i_{j}},Y_{\geq
i_{j}}))=0.$

Without loss of generality, assume $i_{1}<\cdots<i_{r}$ (otherwise, we relabel
the indices). Assuming that the probability distribution is uniform over all
tuples $(\alpha_{1},\ldots,\alpha_{n})\in\mathbb{F}_{q}^{n}$ with distinct
entries, we need to prove that

$\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge
E_{r}]\leq\bigg{(}\frac{(T-1)(k-1)s\cdot c(s)}{q-n+1}\bigg{)}^{r}.$

If the L.H.S. above is zero, then we are done. So we assume that the L.H.S. is
positive. This implies (denoting $E_{0}$ to be the certain event),

$\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge
E_{r}]=\prod_{j=1}^{r}\frac{\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge
E_{j}]}{\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge E_{j-1}]}.$

Fix any $j\in[r]$. Let

$S=\big{\\{}\beta=(\beta_{1},\ldots,\beta_{i_{j}-1})\in\mathbb{F}_{q}^{i_{j}-1}:\operatorname*{\mathbb{P}}[(\alpha_{\leq
i_{j}-1}=\beta)\wedge E_{1}\wedge\cdots\wedge E_{j-1}]>0\big{\\}}.$

Then we get

$\displaystyle\frac{\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge
E_{j}]}{\operatorname*{\mathbb{P}}[E_{1}\wedge\cdots\wedge E_{j-1}]}$
$\displaystyle=\frac{\sum_{\beta\in S}\operatorname*{\mathbb{P}}[(\alpha_{\leq
i_{j}-1}=\beta)\wedge E_{1}\wedge\cdots\wedge E_{j}]}{\sum_{\beta\in
S}\operatorname*{\mathbb{P}}[(\alpha_{\leq i_{j}-1}=\beta)\wedge
E_{1}\wedge\cdots\wedge E_{j-1}]}$ $\displaystyle=\frac{\sum_{\beta\in
S}\operatorname*{\mathbb{P}}[(\alpha_{\leq i_{j}-1}=\beta)\wedge
E_{j}]}{\sum_{\beta\in S}\operatorname*{\mathbb{P}}[\alpha_{\leq
i_{j}-1}=\beta]}$ $\displaystyle\leq\max_{\beta\in
S}\frac{\operatorname*{\mathbb{P}}[(\alpha_{\leq i_{j}-1}=\beta)\wedge
E_{j}]}{\operatorname*{\mathbb{P}}[\alpha_{\leq i_{j}-1}=\beta]}$
$\displaystyle=\max_{\beta\in
S}\operatorname*{\mathbb{P}}[E_{j}\,|\,\alpha_{\leq i_{j}-1}=\beta].$

Now consider any $\beta\in S$. It is enough to prove that
$\operatorname*{\mathbb{P}}[E_{j}\,|\,\alpha_{\leq
i_{j}-1}=\beta]\leq(T-1)(k-1)s\cdot c(s)/(q-n+1)$. Define $Q(Y_{\geq
i_{j}})=\det(A_{j}(\beta,Y_{\geq i_{j}}))\in\mathbb{F}_{q}[Y_{\geq i_{j}}]$.
If $Q(Y_{\geq i_{j}})=0$, then it follows immediately that
$\operatorname*{\mathbb{P}}[E_{j}\,|\,\alpha_{\leq i_{j}-1}=\beta]=0$. So now
suppose $Q(Y_{\geq i_{j}})\neq 0$. Conditioned on $\alpha_{\leq
i_{j}-1}=\beta$, the random variable $\alpha_{i_{j}}$ is uniformly distributed
on $\mathbb{F}_{q}\setminus\\{\beta_{1},\ldots,\beta_{i_{j}-1}\\}$. Consider
$Q(Y_{\geq i_{j}})\in\mathbb{F}_{q}(Y_{>i_{j}})[Y_{i_{j}}]$, and note that
$\deg_{Y_{i_{j}}}(Q)\leq\deg_{Y_{i_{j}}}(A_{j}(Y_{[n]}))\leq(T-1)(k-1)$. By
the count on the number of zeros of a nonzero univariate polynomial, we get

$\operatorname*{\mathbb{P}}[E_{j}\,|\,\alpha_{\leq
i_{j}-1}=\beta]=\operatorname*{\mathbb{P}}_{\alpha_{i_{j}}}[Q(\alpha_{i_{j}},Y_{>i_{j}})=0]\leq\frac{(T-1)(k-1)s\cdot
c(s)}{q-i_{j}+1}\leq\frac{(T-1)(k-1)s\cdot c(s)}{q-n+1}.\qed$

Our main conclusion now follows quickly.

######  Corollary 6.10.

Let $q\geq n,\,k\leq q-n+1$, $\lambda>0$, and $T\geq 2$. Let
$I_{1},\ldots,I_{T}\subseteq[n]$ such that

$\displaystyle\text{wt}(I_{[T]})$ $\displaystyle\geq(1+\lambda)(T-1)k/s,$
$\displaystyle\text{and}\qquad\text{wt}(I_{J})$
$\displaystyle\leq(1+\lambda)(|J|-1)k/s\qquad\text{for all
}J\subseteq[T],\,J\neq\emptyset.$

Further, let $r\leq\lfloor(\lambda k)/((T-1)s)\rfloor+1$. Then

$\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}\\\
\text{distinct}\end{subarray}}\big{[}\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))\neq
0\big{]}\leq\bigg{(}\frac{(T-1)n(k-1)s\cdot c(s)}{q-n+1}\bigg{)}^{r}.$

###### Proof.

By Proposition 6.8(a), if Algorithm 1 outputs Success, then
$\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))=0$. Therefore, by Proposition
6.8(b), we get

$\displaystyle\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}\\\
\text{distinct}\end{subarray}}\big{[}\ker(\mathsf{RIM}_{I_{[T]}}(\alpha_{[n]}))\neq
0\big{]}$
$\displaystyle=\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{r})\in[n]^{r}\\\
\text{certificate}\end{subarray}}\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}\\\
\text{distinct}\end{subarray}}\Big{[}(i_{1},\ldots,i_{r})={\texttt{Certify-
Full-Rankness}}(I_{1},\ldots,I_{T},\alpha_{1},\ldots,\alpha_{n},r)\Big{]}$
$\displaystyle\leq n^{r}\bigg{(}\frac{(T-1)(k-1)s\cdot
c(s)}{q-n+1}\bigg{)}^{r}=\bigg{(}\frac{(T-1)n(k-1)s\cdot
c(s)}{q-n+1}\bigg{)}^{r}.\qed$

###  6.4 List decoding up to capacity

We can now conclude with our main result about list decoding randomly
punctured polynomial ideal codes. Assume Condition 2.1.

######  Theorem 6.11.

Let $\epsilon\in(0,1),\,c>2$, and $n,s,k,L\geq 1$ with $k\leq sn$. Consider
the field $\mathbb{F}_{q}$ with $q\geq 2^{L(L+c)/\epsilon}Ls\cdot c(s)\cdot
n(k-1)+n$, and let $E(X,Y)\in\big{(}\mathbb{F}_{q}[Y]\big{)}[X]$ be
polylinear, completely $s$-bounded. Then, a randomly punctured polynomial
ideal code $\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ over
$\mathbb{F}_{q}$, having rate $k/sn$, is
$\big{(}\frac{L}{L+1}(1-R-\epsilon),L\big{)}$-average radius list decodable,
with probability at least $1-2^{-(c-2)n}$.

###### Proof.

Note that the number of possibilities of the tuple $(T,I_{1},\ldots,I_{T})$,
where $T\in[2,L+1]$ and $I_{1},\ldots,I_{T}\subseteq[n]$, is at most
$\sum_{T=2}^{L+1}2^{Tn}\leq 2^{(L+2)n}$. Choose $\lambda=\epsilon/R=\epsilon
sn/k$. Then, appealing to Corollary 6.10 (which means $r=\epsilon n/L$) and
Lemma 5.3, the probability that a randomly punctured polynomial ideal code
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is not
$\big{(}\frac{L}{L+1}(1-R-\epsilon),L\big{)}$-average radius list decodable is
at most

$2^{(L+2)n}\bigg{(}\frac{Ln(k-1)s\cdot c(s)}{q-n+1}\bigg{)}^{\frac{\epsilon
n}{L}}\leq 2^{-(c-2)n}.\qed$

This completes the proof.

As a corollary of Theorem 6.11, we obtain _efficient_ list decoding up to
capacity. We work this out in Section 6.5 below, where it is stated as
Corollary 6.14.

###  6.5 Algorithmic list decoding up to capacity

The work of [BHKS21] showed algorithmic list decoding up to capacity of a
large subclass of polynomial ideal codes (with sufficiently large folding).
This includes, as special cases, folded Reed-Solomon codes, additive folded
Reed-Solomon codes, and univariate multiplicity codes. In fact, [BHKS21]
provided a unifying algorithm to list decode these codes, with output list
size a polynomial in the field size. We improve the output list size to the
optimal for some of these codes. Let us first define this subclass of
polynomial ideal codes considered in [BHKS21].

Assuming our usual notations, consider the polynomial ideal code
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$, where $\deg_{X}(E)=s$. Recall that
any codeword $[f]\in\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is represented as

$[f]=\begin{bmatrix}\mathcal{L}(f)(y_{1})\\\ \vdots\\\
\mathcal{L}(f)(y_{n})\end{bmatrix}=\begin{bmatrix}\begin{bmatrix}L_{0}(f)(y_{1})&\cdots
L_{s-1}(f)(y_{1})\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\\\
\vdots\\\ \begin{bmatrix}L_{0}(f)(y_{n})&\cdots
L_{s-1}(f)(y_{n})\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\end{bmatrix},$

where $f(X)\equiv
L_{0}(f)(y_{i})+L_{1}(f)(y_{i})X+\cdots+L_{s-1}(f)(y_{i})X^{s-1}\,\left(\text{mod
}E(X,y_{i})\right)$ for all $i\in[n]$. For $r\geq 1$ such that $k+(sn/r)\leq
sn$ and two families of linear operators
$\mathcal{G}=\begin{bmatrix}G_{0}&\cdots&G_{r-1}\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
and
$\mathcal{T}=\begin{bmatrix}T_{0}&\cdots&T_{s-1}\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
on $\mathbb{F}[X]$, we say $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is
$(r,s;\mathcal{G},\mathcal{T})$-list composable if

  1. (a)

$\deg(G_{j}(f))\leq\deg(f)$ for all $f(X)\in\mathbb{F}[X],\,j\in[0,r-1]$.

  2. (b)

The matrix

$\mathsf{D}(\mathcal{G})\coloneqq\begin{bmatrix}d_{0,0}&\cdots&d_{0,k-1}\\\
\vdots&\ddots&\vdots\\\
d_{r-1,0}&\cdots&d_{r-1,k-1}\end{bmatrix}\in\mathbb{F}^{r\times k}$

has full rank $r$ where, for every $j\in[0,r-1]$, the linear operator $G_{j}$
restricted to the subspace $\\{f(X)\in\mathbb{F}[X]:\deg(f)<k\\}$ has the
matrix

$\begin{bmatrix}d_{j,0}&&*\\\ &\ddots&\\\ &&d_{j,k-1}\end{bmatrix}$

with respect to the standard basis $\\{1,X,\ldots,X^{k-1}\\}$.

  3. (c)

There exists a matrix $M_{\mathcal{T}}(Y)\in\mathbb{F}[Y]^{s\times s}$ such
that $\mathcal{T}(f)(y_{i})=f(M_{\mathcal{T}}(y_{i}))\cdot\mathcal{T}(1)$, for
all $f(X)\in\mathbb{F}[X],\,i\in[n]$.

  4. (d)

For every $i\in[n],\,j\in[0,r-1]$, there exists a linear map
$\mathsf{t}_{i,j}:\mathbb{F}^{s}\to\mathbb{F}^{s}$ such that

$\mathcal{T}(G_{j}(f))(y_{i})=\mathsf{t}_{i,j}(\mathcal{L}(f)(y_{i})),\quad\text{for
all }f(X)\in\mathbb{F}[X].$

Further, we say $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is $(r,s)$-list
composable if it is $(r,s;\mathcal{G},\mathcal{T})$-list composable, for some
families of linear operators $\mathcal{G}$ and $\mathcal{T}$. As observed in
[BHKS21], the affine folded Reed-Solomon code
$\mathrm{AFRS}^{(s)}_{\ell}(y_{1},\ldots,y_{n};k)$ over $\mathbb{F}_{q}$ is
$(r,s)$-list composable for all $r\leq s$, if the nonzero affine linear map
$\ell(y)=\alpha y+\beta$ (for $y\in\mathbb{F}_{q}$) satisfies either (i)
$\text{ord}(\ell)>k$, or (ii) $\text{char}(\mathbb{F}_{q})\geq k$ and
$\beta\neq 0$.

The algorithmic result of [BHKS21] is the following.

######  Theorem 6.12 ([BHKS21]).

Consider the field $\mathbb{F}_{q}$. Suppose a polynomial ideal code
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ satisfies

  1. (a)

$E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}$ satisfies $\deg(E_{j})\leq
s-j,\,j\in[0,s-1]$.

  2. (b)

$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is
$(r,s;\mathcal{G},\mathcal{T})$-list composable.

Then there exists a deterministic polynomial time algorithm that list decodes
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ up to radius
$1-\frac{k}{sn}-\frac{1}{r}$, with output list size $q^{u}$, where $k-u$ is
the minimum distance of the linear code generated by the rows of
$\mathsf{D}(\mathcal{G})$.

Composing Theorem 6.12 with a randomized _pruning algorithm_ of [KRZSW23]
improves the output list size to give the following.

######  Corollary 6.13 (Follows from [BHKS21, KRZSW23]).

Let $R\in(0,1),\epsilon\in(0,1-R)$ be fixed, and $n,s\geq 1$ with $s\sim
1/\epsilon^{2}$, and $n\to\infty$. Consider the field $\mathbb{F}_{q}$.
Suppose a polynomial ideal code $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};Rsn)$
satisfies

  1. (a)

$E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}$ satisfies $\deg(E_{j})\leq
s-j,\,j\in[0,s-1]$.

  2. (b)

$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};Rsn)$ is $(r,s)$-list composable, for
$r\sim 1/\epsilon$.

Then there exists a polynomial time algorithm that list decodes
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};Rsn)$ up to radius $1-R-\epsilon$, with
output list size $(1/\epsilon)^{O(1/\epsilon)}$.

Combining Theorem 6.11 with Corollary 6.13, we get the following algorithmic
result, with optimal output list size.

######  Corollary 6.14.

Let $R\in(0,1),\epsilon\in(0,1-R)$ be fixed, and $n,s\geq 1$ with $s\sim
1/\epsilon^{2}$, and $n\to\infty$. Consider the field $\mathbb{F}_{q}$, and
let $E(X,Y)\in\big{(}\mathbb{F}_{q}[Y]\big{)}[X]$ be polylinear completely
$s$-bounded. If $q\geq\Omega(2^{1/\epsilon^{2}}s\cdot c(s)\cdot n^{2})$, then
there exists a polynomial time algorithm that list decodes a randomly
punctured polynomial ideal code
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};Rsn)$ up to radius
$1-R-\epsilon$, with output list size $O(1/\epsilon)$, provided that the code
satisfies the following:

  1. (a)

$E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}$ satisfies $\deg(E_{j})\leq
s-j,\,j\in[0,s-1]$;

  2. (b)

$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};Rsn)$ is $(r,s)$-list
composable, for $r\sim 1/\epsilon$.

## References

  * [AGL23] Omar Alrabiah, Venkatesan Guruswami, and Ray Li.  Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields.  arXiv Preprint, 2023.  https://arxiv.org/abs/2304.09445
  * [BDG23] Joshua Brakensiek, Manik Dhar, and Sivakanth Gopi.  Generalized GM-MDS: Polynomial Codes are Higher Order MDS.  arXiv Preprint, 2023.  https://arxiv.org/abs/2310.12888.
  * [BDGZ23] Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, and Zihan Zhang.  AG codes achieve list decoding capacity over contant-sized fields.  arXiv Preprint, 2023.  https://doi.org/10.48550/arXiv.2310.12898.
  * [BFNW93] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.  BPP has subexponential time simulations unless EXPTIME has publishable proofs.  Computational Complexity, 3(4):307–318, 1993.  https://doi.org/10.1007/BF01275486.
  * [BGM22] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam.  Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes.  IEEE Transactions on Information Theory, 68(11):7125–7140, 2022\.  https://doi.org/10.1109/TIT.2022.3187366
  * [BGM23] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam.  Generic Reed-Solomon Codes Achieve List-Decoding Capacity.  STOC 2023, page 1488–1501, New York, NY, USA, 2023. Association for Computing Machinery.  https://doi.org/10.1145/3564246.3585128
  * [BHKS21] Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan.  Ideal-theoretic explanation of capacity-achieving decoding.  In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 56:1–56:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.56
  * [BW87] E. R. Berlekamp and L. Welch.  Error correction of algebraic block codes.  US Patent Number 4,633,470, 1987.
  * [CPS99] Jin-Yi Cai, Aduri Pavan, and D. Sivakumar.  On the hardness of permanent.  In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1563 of Lecture Notes in Computer Science, pages 90–99. Springer, 1999.  https://doi.org/10.1007/3-540-49116-3_8.
  * [DKSS13] Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan.  Extensions to the method of multiplicities, with applications to Kakeya sets and mergers.  SIAM Journal on Computing, 42(6):2305–2328, 2013.  https://doi.org/10.1137/100783704.
  * [DL78] Richard A. DeMillo and Richard J. Lipton.  A probabilistic remark on algebraic program testing.  Inf. Process. Lett., 7(4):193–195, 1978.  https://doi.org/10.1016/0020-0190(78)90067-4
  * [DSDY13] Son Hoang Dau, Wentu Song, Zheng Dong, and Chau Yuen.  Balanced Sparsest generator matrices for MDS codes.  In 2013 IEEE International Symposium on Information Theory, pages 1889–1893, 2013.  https://doi.org/10.1109/ISIT.2013.6620554
  * [DSY14] Son Hoang Dau, Wentu Song, and Chau Yuen.  On the existence of MDS codes over small fields with constrained generator matrices.  In 2014 IEEE International Symposium on Information Theory, pages 1787–1791, 2014.  https://doi.org/10.1109/ISIT.2014.6875141
  * [Fuh11] Paul A. Fuhrmann.  A Polynomial Approach to Linear Algebra.  Springer New York, NY, 1st edition, 2011.  https://doi.org/10.1007/978-1-4419-8734-1
  * [GL89] Oded Goldreich and Leonid A Levin.  A hard-core predicate for all one-way functions.  In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 25–32. ACM, 1989.  https://doi.org/10.1145/73007.73010.
  * [GR08] Venkatesan Guruswami and Atri Rudra.  Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.  IEEE Transactions on Information Theory, 54(1):135–150, 2008.  https://doi.org/10.1109/TIT.2007.911222
  * [GR22] Zeyu Guo and Noga Ron-Zewi.  Efficient list-decoding with constant alphabet and list sizes.  IEEE Trans. Inf. Theory, 68(3):1663–1682, 2022.  https://doi.org/10.1109/TIT.2021.3131992.
  * [GRS00] Oded Goldreich, Dana Ron, and Madhu Sudan.  Chinese remaindering with errors.  IEEE Transactions on Information Theory, 46(4):1330–1338, 2000\.  https://doi.org/10.1109/18.850672.
  * [GRX18] Venkatesan Guruswami, Nicolas Resch, and Chaoping Xing.  Lossless dimension expanders via linearized polynomials and subspace designs.  In Proceedings of the 33rd Computational Complexity Conference (CCC), volume 102 of LIPIcs, pages 4:1–4:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  https://doi.org/10.4230/LIPIcs.CCC.2018.4.
  * [GS99] Venkatesan Guruswami and Madhu Sudan.  Improved decoding of Reed-Solomon and algebraic-geometry codes.  IEEE Transactions on Information Theory, 45(6):1757–1767, 1999\.  https://doi.org/10.1109/18.782097.
  * [GS12] Natalio H. Guersenzvaig and Fernando Szechtman.  Is every matrix similar to a polynomial in a companion matrix?  Linear algebra and its applications, 437(7):1611–1627, 2012.  https://doi.org/10.1016/j.laa.2012.04.049
  * [GST22] Eitan Goldberg, Chong Shangguan, and Itzhak Tamo.  Singleton-type bounds for list-decoding and list-recovery, and related results.  In IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 - July 1, 2022, pages 2565–2570. IEEE, 2022\.  https://doi.org/10.1109/ISIT50566.2022.9834849.
  * [Gur04] Venkatesan Guruswami.  List decoding of error-correcting codes, volume 3282 of Lecture Notes in Computer Science.  Springer Berlin, Heidelberg, 2004.  https://doi.org/10.1007/b104335
  * [Gur09] Venkatesan Guruswami.  Artin automorphisms, cyclotomic function fields, and folded list-decodable codes.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 23–32. ACM Press, 2009.  http://doi.acm.org/10.1145/1536414.1536420.
  * [GUV09] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan.  Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.  Journal of the ACM, 56(4):20:1–20:34, 2009.  https://doi.org/10.1145/1538902.1538904.
  * [GW13] Venkatesan Guruswami and Carol Wang.  Linear-algebraic list decoding for variants of reed–solomon codes.  IEEE Transactions on Information Theory, 59(6):3257–3268, 2013\.  https://doi.org/10.1109/TIT.2013.2246813
  * [GX12] Venkatesan Guruswami and Chaoping Xing.  Folded codes from function field towers and improved optimal rate list decoding.  In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 339–350. ACM, 2012.  https://doi.org/10.1145/2213977.2214009.
  * [GX14] Venkatesan Guruswami and Chaoping Xing.  Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets.  In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1858–1866. SIAM, 2014.
  * [GX15] Venkatesan Guruswami and Chaoping Xing.  Optimal rate algebraic list decoding using narrow ray class fields.  Journal of Combinatorial Theory, Series A, 129:160–183, 2015.
  * [GX22] Venkatesan Guruswami and Chaoping Xing.  Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-Geometric Codes.  J. ACM, 69(2), January 2022.  https://doi.org/10.1145/3506668
  * [GZ23] Zeyu Guo and Zihan Zhang.  Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets.  arXiv Preprint, 2023.  https://arxiv.org/abs/2304.01403
  * [Jac13] Nathan Jacobson.  Lectures in Abstract Algebra: II. Linear Algebra, volume 31.  Springer New York, NY, 2013.  https://doi.org/10.1007/978-1-4684-7053-6
  * [Kap74] Irving Kaplansky.  Linear Algebra and Geometry: A Second Course.  Chelsea Publishing Company, 2nd edition, 1974.
  * [KM93] Eyal Kushilevitz and Yishay Mansour.  Learning decision trees using the Fourier spectrum.  SIAM Journal on Computing, 22(6):1331–1348, 1993.  https://doi.org/10.1137/0222080.
  * [Knu97] Donald E. Knuth.  The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms.  Addison-Wesley Longman Publishing Co., Inc., USA, 1997.  https://doi.org/10.5555/270146
  * [Kop15] Swastik Kopparty.  List-Decoding Multiplicity Codes.  Theory of Computing, 11(5):149–182, 2015.  10.4086/toc.2015.v011a005
  * [Kra03] V.Y. Krachkovsky.  Reed-Solomon codes for correcting phased error bursts.  IEEE Transactions on Information Theory, 49(11):2975–2984, 2003\.  https://doi.org/10.1109/TIT.2003.819333
  * [KRZSW23] Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters.  Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes.  SIAM Journal on Computing, 52(3):794–840, 2023.
  * [KSY14] Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin.  High-Rate Codes with Sublinear-Time Decoding.  J. ACM, 61(5), Sep 2014.  https://doi.org/10.1145/2629416
  * [Lov21] Shachar Lovett.  Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture.  SIAM Journal on Computing, 50(4):1248–1262, 2021.  https://doi.org/10.1137/20M1323345.
  * [MS77] Florence Jessie MacWilliams and Neil James Alexander Sloane.  The Theory of Error-Correcting Codes, volume 16.  Elsevier, 1977.
  * [Ö22] Ore Ö.  Über höhere Kongruenzen.  Norsk Mat. Forenings Skrifter Ser. I, (7):15, 1922.
  * [Pet60] W. Wesley Peterson.  Encoding and error-correction procedures for the Bose-Chaudhuri codes.  IRE Transactions on Information Theory, 6(4):459–470, 1960.  https://doi.org/10.1109/TIT.1960.1057586.
  * [Rot22] Ron M. Roth.  Higher-order MDS codes.  IEEE Trans. Inf. Theory, 68(12):7798–7816, 2022.  https://doi.org/10.1109/TIT.2022.3194521.
  * [RS60] Irving S. Reed and Gustave Solomon.  Polynomial codes over certain finite fields.  SIAM Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.  https://doi.org/10.1137/0108018.
  * [RT97] M. Yu. Rosenbloom and M. A. Tsfasman.  Codes for the $m$-metric.  Problemy Peredachi Informatsii, 33(1):55–63, 1997.  English translation in: _Problems of Information Transmission_ , 33(1):45–52, 1997. https://www.mathnet.ru/eng/ppi359
  * [Sch80] Jacob T. Schwartz.  Fast probabilistic algorithms for verification of polynomial identities.  Journal of the Association for Computing Machinery (JACM), 27(4):701–717, 1980.  https://doi.org/10.1145/322217.322225
  * [Sol99] Louis Solomon.  Similarity of the companion matrix and its transpose.  Linear Algebra and its Applications, 302:555–561, 1999.  https://doi.org/10.1016/S0024-3795(99)00210-4
  * [Spi60] A. Spitzbart.  A Generalization of Hermite’s Interpolation Formula.  The American Mathematical Monthly, 67(1):42–46, 1960.  https://doi.org/10.2307/2308924
  * [ST20] Chong Shangguan and Itzhak Tamo.  Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius.  STOC 2020, page 538–551, New York, NY, USA, 2020. Association for Computing Machinery.  https://doi.org/10.1145/3357713.3384295
  * [STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan.  Pseudorandom generators without the XOR lemma.  Journal of Computer and System Sciences, 62(2):236–266, 2001.  https://doi.org/10.1006/jcss.2000.1730.
  * [Sud97] Madhu Sudan.  Decoding of Reed Solomon Codes beyond the Error-Correction Bound.  Journal of Complexity, 13(1):180–193, 1997.  https://doi.org/10.1006/jcom.1997.0439
  * [Tam23] Itzhak Tamo.  Tighter List-Size Bounds for List-Decoding and Recovery of Folded Reed-Solomon and Multiplicity Codes.  arXiv Preprint, 2023.  https://arxiv.org/abs/2312.17097.
  * [Tia19] Yongge Tian.  Formulas for calculating the dimensions of the sums and the intersections of a family of linear subspaces with applications.  Beiträge zur Algebra und Geometrie/Contributions to Algebra and Geometry, 60:471–485, 2019.  https://doi.org/10.1007/s13366-018-00432-9
  * [Tre03] Luca Trevisan.  List-decoding using the XOR lemma.  In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science FOCS, pages 126–135, 2003.  https://doi.org/10.1109/SFCS.2003.1238187.
  * [TU12] Amnon Ta-Shma and Christopher Umans.  Better condensers and new extractors from Parvaresh-Vardy codes.  In Proceedings of the 27th Computational Complexity Conference (CCC), pages 309–315. IEEE Computer Society, 2012.  https://doi.org/10.1109/CCC.2012.25.
  * [TZ59] Olga Taussky and Hans Zassenhaus.  On the similarity transformation between a matrix and its transpose.  Pacific Journal of Mathematics, 9(3):893–896, 1959.  http://dx.doi.org/10.2140/pjm.1959.9.893
  * [TZ04] Amnon Ta-Shma and David Zuckerman.  Extractor codes.  IEEE Transactions on Information Theory, 50(12):3015–3025, 2004\.  https://doi.org/10.1109/TIT.2004.838377.
  * [Wel71] Dominic James Anthony Welsh.  Generalized versions of Hall’s theorem.  Journal of Combinatorial Theory, Series B, 10(2):95–101, 1971.  https://doi.org/10.1016/0095-8956(71)90069-4
  * [YH19] Hikmet Yildiz and Babak Hassibi.  Optimum Linear Codes With Support-Constrained Generator Matrices Over Small Fields.  IEEE Transactions on Information Theory, 65(12):7868–7875, 2019\.  https://doi.org/10.1109/TIT.2019.2932663
  * [Zip79] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In International symposium on symbolic and algebraic manipulation, pages 216–226. Springer, 1979.  https://doi.org/10.1007/3-540-09519-5_73

##  Appendix A Duals of polynomial ideal codes with irreducible moduli

In this section, we will obtain a slightly different analysis of duality, and
characterize the duals of polynomial ideal codes
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ in the case where the functional
moduli $E(X,y_{1}),\ldots,E(X,y_{n})$ are all irreducible over $\mathbb{F}$.

######  Theorem A.1 (Informal).

Let $E(X,Y)\in(\mathbb{F}[X])[Y]$ be a formal modulus, and
$y_{1},\ldots,y_{n}\in\mathbb{F}$ be distinct such that the functional moduli
$E(X,y_{1}),\ldots,E(X,y_{n})$ are all irreducible over $\mathbb{F}$. There
exists a block invertible matrix $\Theta\in\mathbb{F}^{sn\times sn}$ such that
the following holds: for any $k\in[sn]$, and block invertible matrix
$U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{sn\times sn}$, we have

$\displaystyle\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)^{\perp}$
$\displaystyle=\mathbf{GPI}_{E}((U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Theta;y_{1},\ldots,y_{n};sn-k).$
$\displaystyle\text{In
particular,}\qquad\qquad\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)^{\perp}$
$\displaystyle=\mathbf{GPI}_{E}(\Theta;y_{1},\ldots,y_{n};sn-k).$

We will state and prove a formal version of Theorem A.1 soon. Let us begin by
gathering some basic observations.

#### Companion matrix

We will need a folklore fact: over any commutative ring with unity, a
companion matrix is similar to its transpose. More broadly, the definition of
the polynomial ideal code itself can be seen to be reliant on the fact: the
linear operator on $\mathbb{F}^{s}$, defined by left multiplication by a fixed
matrix, induces an $\mathbb{F}[X]$-module structure on $\mathbb{F}^{s}$. For a
detailed discussion on these facts, and more, see Taussky and Zassenhaus
[TZ59], Solomon [Sol99], Kaplansky [Kap74, Chapter 2], Fuhrmann [Fuh11,
Chapters 5 and 6], and Jacobson [Jac13, Chapter 3].

######  Proposition A.2 (Folklore, see Fuhrmann [Fuh11, Chapter 5]).

Let $R$ be a commutative ring with unity. For any
$f(X)=X^{s}+\sum_{j=0}^{s-1}f_{j}X^{j}\in R[X]$, we have
$W_{f}^{-1}C_{f}W_{f}=C_{f}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$,
where

$C_{f}=\begin{bmatrix}0&&&-f_{0}\\\ 1&&&-f_{1}\\\ &\ddots&&\vdots\\\
&&1&-f_{s-1}\end{bmatrix},\quad\text{and}\quad
W_{f}=\begin{bmatrix}f_{1}&\cdots&f_{s-1}&1\\\
\vdots&\text{\reflectbox{$\ddots$}}&\text{\reflectbox{$\ddots$}}\\\
f_{s-1}&\text{\reflectbox{$\ddots$}}&\\\ 1&&\end{bmatrix}.$

(Note that $W_{f}$ is invertible in $R$, since
$\det(W_{f})=(-1)^{\binom{s}{2}}\neq 0$.)

We will also need the following result about the rank of a polynomial acting
on a companion matrix. It is explicitly stated in Guersenzvaig and Szechtman
[GS12], but as they remark, it is also implicit in the discussion in Jacobson
[Jac13, Chapter 3].

######  Proposition A.3 ([GS12],[Jac13, Chapter 3]).

For any nonzero polynomials $f(X),g(X)\in\mathbb{F}[X]$, we have

$\ker(g(C_{f}))=0\quad\iff\quad\gcd(f,g)=1.$

#### Explicit Chinese remainder theorem

Since $E(X,y_{1}),\ldots,E(X,y_{n})$ are pairwise coprime, the Chinese
Remainder Theorem asserts a ring isomorphism

$\frac{\mathbb{F}[X]}{\prod_{i=1}^{n}E(X,y_{i})}\simeq\bigoplus_{i=1}^{n}\frac{\mathbb{F}[X]}{E(X,y_{i})}.$

Here, the explicit isomorphism is as follows: the forward map is obtained by
Division Algorithm, and the inverse map is determined by Lagrange
interpolation. (See, for instance, MacWilliams and Sloane [MS77, Chapter 10,
Theorem 5], and Knuth [Knu97, Section 4.3.2, Exercise 4.6.2-3].)

The following observation is then immediate.

######  Observation A.4.

We have a Lagrange interpolation formula as follows: for any
$f(X)\in\mathbb{F}[X]$ with $\deg(f)<sn$, we have

$f(X)=\sum_{i=1}^{n}\sum_{j=0}^{s-1}\Lambda_{i,j}(X)L_{j}(f)(y_{i}),$

where, for every $i\in[n],\,j\in[0,s-1]$, the following hold.

  1. (i)

The congruence

$\Lambda_{i,j}(X)\equiv\begin{cases}0&\,\left(\text{mod }\prod_{i^{\prime}\neq
i}E(X,y_{i^{\prime}})\right),\\\\[5.0pt] X^{j}&\,\left(\text{mod
}E(X,y_{i})\right).\end{cases}$

  2. (ii)

$\Lambda_{i,j}(X)=\prod_{i^{\prime}\neq i}E(X,y_{i^{\prime}})\cdot
D_{i,j}(X)$, where

$D_{i,j}(X)=\bigg{(}\prod_{i^{\prime}\neq
i}E(X,y_{i^{\prime}})\bigg{)}^{-1}\cdot X^{j}\,\left(\text{mod
}E(X,y_{i})\right),$

since $\prod_{i^{\prime}\neq i}E(X,y_{i^{\prime}})$ is invertible in
$\mathbb{F}[X]\big{/}\big{\langle}E(X,y_{i})\big{\rangle}$.

  3. (iii)

As a consequence of (b),

$\deg(\Lambda_{i,j})=s(n-1)+\deg(D_{i,j}),$

and so $\deg(D_{i,j})<s$.

So define $B_{i}=\\{j\in[0,s-1]:\deg(D_{i,j})=s-1\\},\,i\in[n]$. We then get
the following.

######  Lemma A.5.

$B_{i}\neq\emptyset$, for all $i\in[n]$.

###### Proof.

Fix any $i\in[n]$. Let $D^{\prime}_{i}=\\{\deg(D_{i,j}):t\in[0,s-1]\\}$, and
let $M_{1}>\cdots>M_{\ell}$ be all the distinct values in $D^{\prime}_{i}$.
For each $w\in[\ell]$, let $j^{\prime}_{w}\in[0,s-1]$ be the smallest such
that $\deg(D_{i,j^{\prime}_{w}})=M_{w}$.

Suppose $B_{i}=\emptyset$, that is, $M_{1}=\max(D^{\prime}_{i})<s-1$. So this
means $\ell<s$, since there are only $\ell$ distinct values in
$D^{\prime}_{i}$. If $j^{\prime}_{1}<s_{-}1$, then we see that
$D_{i,j^{\prime}_{1}+1}(X)=X\cdot D_{i,j^{\prime}_{1}}(X)$, and therefore,
$\deg(D_{i,j^{\prime}_{1}+1})=M_{1}+1$, a contradiction. So
$j^{\prime}_{1}=s-1$. Now consider the set
$D^{\prime\prime}_{i}=D^{\prime}_{i}\setminus\\{M_{1}\\}=\\{\deg(D_{i,j}):j\in[0,s-2]\\}$.
The distinct values in $D^{\prime\prime}_{i}$ are precisely
$M_{2}>\cdots>M_{\ell}$. We can repeat the argument as before and conclude
that $j^{\prime}_{2}=s-2$. Inductively, we get $j^{\prime}_{w}=s-w$ for all
$w\in[\ell]$. Thus $j^{\prime}_{\ell}=s-\ell\geq 1$, which means
$\deg(D_{i,0})<M_{\ell}$. This is a contradiction, since
$M_{\ell}=\min(D^{\prime}_{i})$. Hence, $M_{1}=s-1$, that is,
$B_{i}\neq\emptyset$. ∎

We are now ready to describe the dual of a generalized polynomial ideal code
$\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)$, where the functional moduli
$E(X,y_{1}),\ldots,E(X,y_{n})$ are all irreducible over $\mathbb{F}$. Let
$C_{i}\coloneqq C_{E(X,y_{i})}=C_{E}(y_{i})\in\mathbb{F}^{s\times s}$, the
companion matrix of $E(X,y_{i})$, for all $i\in[n]$.

######  Theorem A.6 (Formal version of Theorem A.1).

Let $E(X,Y)\in(\mathbb{F}[X])[Y]$ be a formal modulus, and
$y_{1},\ldots,y_{n}\in\mathbb{F}$ be distinct such that the functional moduli
$E(X,y_{1}),\ldots,E(X,y_{n})$ are all irreducible over $\mathbb{F}$. Let

$\displaystyle W_{i}$ $\displaystyle=W_{E(X,y_{i})},$ $\displaystyle\text{for
}i\in[n],$ $\displaystyle\Theta_{i}(X)$
$\displaystyle=\sum_{j=0}^{s-1}\bigg{(}W_{i}\cdot\sum_{\ell\in
B_{i}}\text{coeff}(X^{s-1},D_{i,\ell})\,e_{s,\ell}\bigg{)}_{j}\,X^{j},$
$\displaystyle\text{for }i\in[n],$ $\displaystyle\Gamma_{i}$
$\displaystyle=W_{i}^{-1}\cdot\Theta_{i}(C_{i}),$ $\displaystyle\text{for
}i\in[n],$ $\displaystyle\text{and}\quad\qquad\Gamma$
$\displaystyle=\begin{bmatrix}\Gamma_{1}&&\\\ &\ddots&\\\
&&\Gamma_{n}\end{bmatrix}.$

Then for any $k\in[sn]$, and block invertible matrix
$U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{sn\times sn}$, we have

$\displaystyle\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)^{\perp}$
$\displaystyle=\mathbf{GPI}_{E}((U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi;y_{1},\ldots,y_{n};sn-k).$
$\displaystyle\text{In
particular,}\qquad\qquad\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)^{\perp}$
$\displaystyle=\mathbf{GPI}_{E}(\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi;y_{1},\ldots,y_{n};sn-k).$

###### Proof.

Consider any $f(X),g(X)\in\mathbb{F}[X]$ with $\deg(f)<k,\,\deg(g)<sn-k$. So
Observation A.4(b) gives

$f(X)g(X)=\sum_{i=1}^{n}\sum_{j=0}^{s-1}\Lambda_{ij}(X)L_{j}(fg)(y_{i}).$

Since $\deg(fg)<sn-1$, we have $\text{coeff}(X^{sn-1},fg)=0$. However, we get

$\displaystyle\text{coeff}(X^{sn-1},fg)$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=0}^{s-1}\text{coeff}(X^{s-1},D_{i,j})\,L_{j}(fg)(y_{i})$
by Observation A.4(b)(iii) $\displaystyle=\sum_{i=1}^{n}\bigg{(}\sum_{j\in
B_{i}}\text{coeff}(X^{s-1},D_{i,j})\,e_{s,j}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bigg{)}\cdot(fg)(C_{i})\cdot
e_{s,0}$ by Observation A.4(a) $\displaystyle=\sum_{i=1}^{n}\bigg{(}\sum_{j\in
B_{i}}\text{coeff}(X^{s-1},D_{i,j})\,e_{s,j}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bigg{)}\cdot
g(C_{i})\cdot f(C_{i})\cdot e_{s,0}$
$\displaystyle=\sum_{i=1}^{n}\bigg{(}\sum_{j\in
B_{i}}\text{coeff}(X^{s-1},D_{i,j})\,e_{s,j}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bigg{)}\cdot(g(C_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}))^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
f(C_{i})\cdot e_{s,0}$ $\displaystyle=\sum_{i=1}^{n}\bigg{(}\sum_{j\in
B_{i}}\text{coeff}(X^{s-1},D_{i,j})\,e_{s,j}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bigg{)}\cdot\big{(}W_{i}^{-1}\cdot
g(C_{i})\cdot
W_{i}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
f(C_{i})\cdot e_{s,0}$ by Proposition A.2
$\displaystyle=\sum_{i=1}^{n}\big{(}W_{i}^{-1}\cdot g(C_{i})\cdot(W_{i}\cdot
b_{i})\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
f(C_{i})\cdot e_{s,0}$ (12)

where we define $b_{i}=\sum_{j\in
B_{i}}\text{coeff}(X^{s-1},D_{i,j})\,e_{s,j}$, for all $i\in[n]$. Further,
note that $b_{i}\neq 0^{s}$ by Lemma A.5. So $W_{i}\cdot b_{i}\neq 0^{s}$. Now
we have

$\Theta_{i}(X)\coloneqq\sum_{j=0}^{s-1}\big{(}W_{i}\cdot
b_{i})_{j}\,X^{j},\quad i\in[n].$

So (12) gives

$\displaystyle\text{coeff}(X^{sn-1},fg)$
$\displaystyle=\sum_{i=1}^{n}\big{(}W_{i}^{-1}\cdot g(C_{i})\cdot(W_{i}\cdot
b_{i})\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
f(C_{i})\cdot e_{s,0}$ $\displaystyle=\sum_{i=1}^{n}\big{(}W_{i}^{-1}\cdot
g(C_{i})\cdot\Theta_{i}(C_{i})\cdot
e_{s,0}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
f(C_{i})\cdot e_{s,0}$
$\displaystyle=\sum_{i=1}^{n}\Big{(}\big{(}W_{i}^{-1}\cdot\Theta_{i}(C_{i})\big{)}\cdot\big{(}g(C_{i})\cdot
e_{s,0}\big{)}\Big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}f(C_{i})\cdot
e_{s,0}\big{)}.$

For each $i\in[n]$, we see that

  * •

$E(X,y_{i})$ is irreducible, and $\deg(E(X,y_{i}))=s$.

  * •

$\Theta_{i}(X)\neq 0$, and $\deg(\Theta_{i})<s$.

  * •

So $\gcd(\Theta_{i}(X),E(X,y_{i}))=1$, and
$N_{i}=W_{i}^{-1}\cdot\Theta_{i}(C_{i})$ is invertible, by Proposition A.3.

Thus, using Observation A.4(a), we have the implications

$\displaystyle\sum_{i=1}^{n}\big{(}N_{i}\cdot\big{(}g(C_{i})\cdot
e_{s,0}\big{)}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}f(C_{i})\cdot
e_{s,0}\big{)}$ $\displaystyle=0$ $\displaystyle\implies$
$\displaystyle\sum_{i=1}^{n}\big{(}N_{i}\cdot\big{(}\psi_{i}\cdot
g(C_{i})\cdot
e_{s,0}\big{)}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}\psi_{i}\cdot
f(C_{i})\cdot e_{s,0}\big{)}$ $\displaystyle=0$ $\displaystyle\implies$
$\displaystyle\sum_{i=1}^{n}\Big{(}\big{(}(U_{i}^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\psi_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}N_{i}\psi_{i}\big{)}\cdot\big{(}g(C_{i})\cdot
e_{s,0}\big{)}\Big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}U_{i}\cdot
f(C_{i})\cdot e_{s,0}\big{)}$ $\displaystyle=0$ $\displaystyle\implies$
$\displaystyle\Big{(}\big{(}(U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi\big{)}\cdot[g]\Big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}U\cdot[f]\big{)}$
$\displaystyle=0$

So

$\mathbf{GPI}_{E}((U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\psi^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Gamma\psi;y_{1},\ldots,y_{n};sn-k)\subseteq\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)^{\perp}.$

Further, both the above vector spaces have dimension $sn-k$, and this
completes the proof. ∎


††thanks: These authors contributed equally††thanks: These authors contributed
equally††thanks: These authors contributed equally

# Large Bilinear Magnetoresistance from Rashba Spin-Splitting on the Surface
of a Topological Insulator

Yang Wang  Department of Physics and Astronomy, University of Delaware,
Newark, Delaware, 19716, USA  Binbin Liu  School of Physics, Beihang
University, Beijing 100191, China  Yue-Xin Huang  Research Laboratory for
Quantum Materials, Singapore University of Technology and Design, Singapore
487372, Singapore  Sivakumar V. Mambakkam  Department of Materials Science and
Engineering, University of Delaware, Newark, Delaware, 19716, USA  Yong Wang
Department of Materials Science and Engineering, University of Delaware,
Newark, Delaware, 19716, USA  Shengyuan A. Yang  Research Laboratory for
Quantum Materials, Singapore University of Technology and Design, Singapore
487372, Singapore  Xian-Lei Sheng  School of Physics, Beihang University,
Beijing 100191, China  Stephanie A. Law  Department of Physics and Astronomy,
University of Delaware, Newark, Delaware, 19716, USA  Department of Materials
Science and Engineering, University of Delaware, Newark, Delaware, 19716, USA
John Q. Xiao<EMAIL_ADDRESS>Department of Physics and Astronomy, University of
Delaware, Newark, Delaware, 19716, USA

###### Abstract

In addition to the topologically protected linear dispersion, a band-bending-
confined two-dimensional electron gas with tunable Rashba spin-splitting (RSS)
was found to coexist with the topological surface states on the surface of
topological insulators (TIs). Here, we report the observation of large
bilinear magnetoresistance (BMR) in Bi2Se3 films decorated with transition
metal atoms. The magnitude of the BMR sensitively depends on the type and
amount of atoms deposited, with a maximum achieved value close to those of
strong Rashba semiconductors. Our first-principles calculations reproduce the
quantum well states and reveal sizable RSS in all Bi2Se3 heterostructures with
broken inversion symmetry. Our results show that charge-spin interconversion
through RSS states in TIs can be fine-tuned through surface atom deposition
and easily detected via BMR for potential spintronic applications.

Bilinear or unidirectional magnetoresistance in nonmagnetic systems without
inversion symmetry [1, 2, 3, 4, 5, 6, 7] describes the difference in
resistance when the electric current or magnetic field direction is switched.
It can be phenomenologically expressed as [1, 2, 8]

$\displaystyle R(I,B)=R_{0}[1+\beta
B^{2}+\gamma\bm{I}\cdot(\bm{P}\times\bm{B})]$ (1)

where $R_{0}$ is the resistance at zero magnetic field, $\bm{I}$ is the
electric current, $\bm{B}$ is the magnetic field, and $\bm{P}$ represents the
polar direction of the conductor. The second term describes the normal
magnetoresistance. The magnitude of the BMR is measured by the coefficient
$\gamma$. Such rectification effect typically exists in chiral conductors [9,
10] or systems where the spin-degeneracy is lifted by inversion symmetry
breaking in combination with spin-orbit coupling (SOC) [2, 3, 4, 5]. For the
latter case, topological insulator surfaces [11, 12] and Rashba spin-splitting
[13, 14] states with spin-momentum locked spin-textures are canonical
examples.

As illustrated in Figs. 1(a) and 1(b), taking the TI surface dispersion or the
inner half of a Rashba-type band as an example, when driven by an
$x$-direction electric field, a second-order spin current is generated through
spin-momentum locking [15]. It can be intuitively understood as equal amounts
of electrons with opposite spin polarizations moving in opposite directions,
so there is a nonlinear spin but no charge current. When a magnetic field is
applied, the upright Dirac cone is sheared due to the existence of nonlinear-
in-momentum terms arising from e.g., particle-hole asymmetry ($k^{2}$) or
hexagonal warping ($k^{3}$). This causes imbalance between the left- and
right-moving electrons, and the nonlinear spin current is partially converted
into a nonlinear charge current, giving rise to the BMR [3, 16, 17, 18]. As to
the full Rashba band [Fig. 1(c)], when the Fermi level is above the charge
neutral point (CNP) (region III), due to the cancellation of the two Fermi
contours with opposite spin helicities, the BMR is small. When the Fermi level
lies in region II, a large BMR arises from the addition of the two Fermi
contours [2, 18]. There is also a narrow region I induced by Zeeman splitting
which also exhibits large BMR. However, for the small magnetic fields ( 0.2 T)
used in this study, this region of width $\sim$0.1 meV can be neglected.

Figure 1: Illustration of the BMR and band-bending mechanisms. (a) Driven by
an $x$-direction electric field, there is a second-order spin current
generated in the states of an inner Rashba band or the surface TI dispersion
with particle-hole asymmetry, due to spin-momentum locking. (b) When a
magnetic field is applied in the $y$-direction, it distorts the Fermi contour
asymmetrically and causes an imbalance between the right- and left-moving
electrons with opposite spin polarizations, resulting in a net second-order
charge current. (c) The cross-section of a complete Rashba band under an in-
plane mangetic field. Regions II and III have large and small BMR responses,
respectively. Region I is narrow and can be neglected. (d) From the TI bulk to
surface, the band bends downward and a ladder of QW states are formed in the
surface 2DEG. When there is also substantial electric potential gradient,
these QW states are spin-split by Rashba SOC. $E_{\text{CBM}}$,
$E_{\text{D}}$, and $E_{\text{VBM}}$ denote the energy of conduction band
minimum, Dirac point, and valence band maximum, respectively.

Experimentally, a BMR with a magnitude of $\gamma\sim$0.01
$\mathrm{A}^{-1}\mathrm{B}^{-1}$ was reported in Bi2Se3 grown on Al2O3
substrates [3]. It was attributed to the hexagonal warping effect in the
topological surface states (TSS). Much larger BMR was achieved through the RSS
mechanism [Fig. 1(c)], with $\gamma$ reaching $\sim$1
$\mathrm{A}^{-1}\mathrm{T}^{-1}$ in the polar semiconductor BiTeBr [2] and
$\sim$10-100 $\mathrm{A}^{-1}\mathrm{T}^{-1}$ in the two-dimensional electron
gases (2DEGs) formed at oxide interfaces [5, 19] Actually, as sketched in Fig.
1(d), early angle-resolved photoelectron spectroscopy (ARPES) and
computational studies revealed that on the surface of Bi2Se3 a 2DEG is
confined in the top most several QLs due to band-bending (BB)[20, 21]. Further
introduction of an electrostatic potential gradient either by electric
gating[22] or surface atoms evaporation[23] will cause tunable and robust RSS
in these QW states. It is natural to ask, can these spin-split states on the
surface of TIs generate large BMR?

In this study, we observed large tunable BMR in thick Bi2Se3 films decorated
with transition metal (TM) atoms. The maximum nonreciprocal coefficient
$\gamma$ achieved is comparable to these of strong Rashba materials. Our
density-functional theory (DFT) calculations reproduce the ladder of QW states
with sizable RSS in all inversion asymmetric Bi2Se3 heterostructures. Through
analysis of the temperature dependence, we deduce the large BMR is mainly from
the states in region II of the Rashba band, accessed during the band-bending
process. As a complement to previous ARPES measurements, our work further
validates TIs from nonreciprocal transport aspects as a highly tunable Rashba
material to explore charge-spin interconversion phenomena through
nontopological bands.

The 60 quintuple-layer (QL) Bi2Se3 (BS) films used in this study were grown on
GaAs substrates by the molecular beam epitaxy (MBE) method and decorated with
0.5-1.5 nm thick Cu or Au atoms (See Supplemental Material [24] for growth and
characterization details). The Hall bar devices were patterned by the standard
photolithography method. Because of the small amount of metal deposited, in
transport measurements the current essentially only goes through the 60 QL BS
layer. As depicted in Fig. 2(a), both the substrate and deposited TM atoms can
break the inversion symmetry of Bi2Se3, introduce an electric potential
gradient, and cause substantial RSS. Additionally, the Cu and Au atoms migrate
into the van der Waals layered Bi2Se3 structure [25, 26] and $p$\- or $n$-dope
it. The doping effects can be seen in the linear transport regime. As
displayed in Fig. 2(b), compared with bare BS film grown on GaAs, Cu or Au
raises or lowers the resistance of BS, suggesting that they are working as
electron acceptors or donors, respectively. Interestingly, although the BS/Au
sample maintains metallic behavior, the resistance of BS/Cu devices first
increases and then decreases when temperature is lowered from 290 K to 5 K,
with a peak around 200 K. Such nonmonotonic behavior was also observed in Cu-
doped Bi2Te3 and was attributed to the change in carrier density [27, 28].
Moreover, the smaller resistance in BS/Cu(0.5) and the similar resistances in
BS/Cu(1 and 1.5) samples suggest that saturation of the doping effect occurs
between deposition of 0.5 to 1 nm Cu. From Hall measurements, the sheet
carrier density $n_{\text{s}}$ for the GaAs/BS, BS/Cu(0.5, 1, and 1.5), and
BS/Au(1) samples are 5.2, 3.9, 4.1, 5.1, and 5.6$\times 10^{13}$
$\mathrm{c}\mathrm{m}^{-2}$, respectively. These results suggest that Cu
doping can suppress the bulk conduction for the as-grown $n$-doped Bi2Se3
films.

Figure 2: (a) Crystalline structure of the GaAs/Bi2Se3/TM heterostructure. The
blue arrows represent electric field potential induced by the GaAs substrate
or deposited TM. (b) Longitudinal resistance versus temperature for various
Bi2Se3 heterostructures. The inset depicts a device image with scale bar 20
$\mu$m. (c) Longitudinal second-harmonic resistance as a function of
$y$-direction magnetic field in various devices. The top inset illustrates the
measurement setup. The bottom inset is a zoomed-in plot of the GaAs/$n$-BS,
GaAs/BS, and BS/Au(1) samples. (d) The slope $R_{xx}^{2\omega}/B$ exhibits a
linear dependence on current. (e) $R_{xx}^{2\omega}/B$ of the BS/Cu(1) sample
at different temperatures. (f) Summary of the temperature dependence of the
BMR in different devices. Inset is normalized BMR magnitude.

The effect from electrostatic potential on Bi2Se3 is revealed by nonreciprocal
transport responses, which sensitively depends on the symmetry and band
structure of the material [1]. As indicated by the name, the bilinear
magnetoresistance depends linearly on both external magnetic and electric
fields. As sketched in Fig. 2(c) top inset, we sent a low frequency a.c.
current in the $x$-direction, swept the magnetic field in the $y$-direction,
and measured the longitudinal second-harmonic resistance (SHR)
$R_{xx}^{2\omega}\equiv V_{x}^{2\omega}/I$ by the standard lock-in technique.
$R_{xx}^{2\omega}$ in all samples exhibits linear dependence on $B$, as
expected. GaAs-$n$ denotes another Bi2Se3 (60 QL) sample also grown on GaAs
substrate, but it has a much higher carrier density of $2.7\times 10^{14}$
$\mathrm{c}\mathrm{m}^{-2}$, so the current is shunt through the bulk. The SHR
of it is negligibly small, showing that the inversion-symmetric BS bulk does
not contribute to the BMR. BMR is detected in other samples where substantial
current is carried by the surface states. As shown in Fig. 2(c) bottom inset,
the BMR in GaAs/BS and BS/Au(1) have opposite signs, corresponding to the
bottom and top surface contributions, respectively. The BMR magnitude $\gamma$
in the GaAs/BS sample already reaches 0.08 $\mathrm{A}^{-1}\mathrm{T}^{-1}$,
which is about an order of magnitude larger than that in Al2O3/BS samples with
similar carrier densities [3]. This suggests spin-split QW states instead of
hexagonally warped TSS as the origin of the observed BMR. The reason why RSS-
induced BMR was not dominant in Al2O3/BS is possibly because the downward
band-bending effect is weak in the thin BS(20 QL) film grown on the high-$k$
dielectric Al2O3 substrate [29]. The BMR can be further enhanced by the
deposition of TM atoms. In the BS/Cu(1) sample, $\gamma$ reaches 2.0
$\mathrm{A}^{-1}\mathrm{T}^{-1}$, surpassing that of the strong Rashba
semiconductor BiTeBr ($\gamma\sim 1$) [2]. We noticed that compared with Ref.
[2, 3], the SHR in our samples is large and of low noise. This is rare in 3D
polar conductors, suggesting the robustness of the TSS on TI surfaces. Fig.
2(d) shows that the slope $R_{xx}^{2\omega}/B$ also scales linearly with
current, together with Fig. 2(c) demonstrating the bilinear nature of the
measured resistance.

We confirmed that that under an $x$-direction field, the longitudinal SHR
becomes much smaller, consistent with the selection rule in Eq. (1). We also
observed the transverse counterpart of BMR, the nonlinear planar Hall effect
[17] in our samples. (See Supplemental Note 4 for details.) As represented by
the BS/Cu(1) sample [Fig. 2(e)], the magnitude of the BMR decreases
monotonically from being maximum at 4.5 K to being negligible at 70 K. This
trend is observed in all the samples. Moreover, as shown in Fig. 2(f), despite
having different maximum values, the normalized BMR magnitude
$R_{xx}^{2\omega}(T)/R_{xx}^{2\omega}(4.5~{}$\mathrm{K}$)$ exhibits very
similar temperature dependence in different samples.

Figure 3: Calculated band structures of (a) Bi2Se3(6QL), (b)
Bi2Se3(6QL)/Cu(4ML), and (c) GaAs(1L)/Bi2Se3(6QL). Dirac and QW denote the
topological surface and nontopological quantum well states, respectively. The
inset in (b) is a zoom-in image of the QW1 states, with the momentum offset
$k_{0}$ and energy splitting $E_{R}$ marked in the figure.

To support our claim that the observed BMR is from RSS, we carried out
density-functional theory (DFT) calculations for Bi2Se3 heterostructures made
with 6 QL Bi2Se3 and 1-4 monolayer (ML) Cu, 2 ML Au or 1 layer (L) GaAs.
Because the 2DEG on Bi2Se3 is confined in the top few ($<10$) QLs due to band
bending [21], which gives its unique quantum well (QW) states other than the
continuous bulk bands, we believe the calculations on 6 QL Bi2Se3 can capture
the essential features of the real 2DEG states formed on the surface of our
Bi2Se3 samples. The calculated band structures are shown in Fig. 3. In the
standalone Bi2Se3 film with preserved inversion symmetry, besides the
topologically protected gapless surface Dirac dispersion, the bulk states are
quantized into a ladder of QW states [Fig. 3(a)]. All the states are spin-
degenerate in momentum space, and BMR is correspondingly forbidden. As shown
in Fig. 3(b) and 3(c), when Bi2Se3 is proximately coupled to either Cu or
GaAs, inversion symmetry breaking together with SOC lifts the spin degeneracy
and causes Rashba-type spin-splitting in all the QW states. The size of RSS is
described by the Rashba coefficient $\alpha_{R}=2E_{\text{R}}/k_{0}$ , where
$E_{\text{R}}$ and $k_{0}$ are the energy splitting and momentum offset,
respectively, as defined in the inset of Fig. 3(b). The BS/Cu slab has well-
separated topological surface and nontopological QW states with sizable RSS.
While in GaAs/BS, the GaAs bands hybridize with BS bands and unexpectedly
large RSS (with maximum 2.3 $\mathrm{e}\mathrm{V}\AA$) is observed at low QW
states possibly due to the band anti-crossing features [30]. However, in real
samples, the bottom and top BS surfaces have different interfacial qualities,
so it is reasonable to only compare the RSS at the top BS/Cu or Au interfaces.

Figure 4: Calculated band structures of (a) Bi2Se3(6QL), (b)
Bi2Se3(6QL)/Cu(4ML), and (c) GaAs(1L)/Bi2Se3(6QL). Dirac and QW denote the
topological surface and nontopological quantum well states, respectively. The
inset in (b) is a zoom-in image of the QW1 states, with the momentum offset
$k_{0}$ and energy splitting $E_{R}$ marked in the figure.

As summarized in Fig. 4(a), QW1 has the largest $\alpha_{\text{R}}$ in each
material, reaching 1 and 1.6 $\mathrm{e}\mathrm{V}\AA$ in the BS/Cu(4ML) and
BS/Au(4ML) slabs, respectively. Importantly, the higher QW states (QW2, 3, …)
also exhibit sizable RSS, at the order of 0.5 $\mathrm{e}\mathrm{V}\AA$. These
features are consistent with previous ARPES [23] and DFT [31] results, and are
crucial for the observation of the BMR on the surface of TIs, as discussed
below. Fig. 4(a) also displays the BMR magnitude $\gamma$ of the Bi2Se3
heterostructures made in this study together with those of Al2O3/Bi2Se3 [3]
and BiTeBr [2]. Besides exhibiting large values, we find that $\gamma$ does
not follow the same trend as that of $\alpha_{\text{R}}$ in QW1 or QW2. This
means that RSS is a necessary but not sufficient condition for the observation
of large BMR. There are other factors that control the magnitude of BMR.
Different from the perfect lattice structure used in the calculation, the MBE-
grown GaAs/BS has an imperfect interface with reduced SOC strength, and
correspondingly, the real RSS should be smaller than predicted. Besides,
defects formation also makes the bottom surface more resistive, so less amount
of current goes through it as compared to the top surface. This can explain
the small BMR observed in the GaAs/BS sample. Similarly, in the BS/Au sample,
majority of the current is shunted through the heavily $n$-doped bulk, so
despite having a larger RSS, its BMR magnitude is smaller than that of BS/Cu
samples.

These above considerations cannot explain the significant drop of $\gamma$
from 2 $\mathrm{A}^{-1}\mathrm{T}^{-1}$ in BS/Cu(1) to 0.4
$\mathrm{A}^{-1}\mathrm{T}^{-1}$ in BS/Cu(1.5), given that these two samples
have very similar resistivities [Fig. 2(b)] and $\alpha_{\text{R}}$ [Fig.
4(a)]. Here we propose a band-bending picture to explain this discrepancy. The
model Hamiltonian of a Rashba band under a $y$-direction magnetic field can be
written as

$\displaystyle
H=\hbar^{2}k^{2}/{2m^{*}}+\alpha_{\text{R}}(k_{x}\sigma_{y}-k_{y}\sigma_{x})+B_{y}\sigma_{y},$
(2)

where $\hbar$ is the reduced Planck constant, $m^{*}$ is the effective mass of
the electrons, $\bm{\sigma}$ represent Pauli spin matrices, and $B_{y}$ is the
magnetic field measured in energy unit. Using semiclassical Boltzmann
approach, we numerically calculated the chemical potential and temperature
dependence of the BMR (See Supplemental Note 5 for details). As plotted in
Fig. 4(b), consistent with the qualitative argument in the introduction [Fig.
1(c)], at $T=0$ the BMR is zero when chemical potential $\mu$ lies in region
III and only becomes finite when temperature increases or $\mu$ goes into
region II. Fig. 4(c) shows that in region II $\gamma$ decreases when
temperature is increased, which is consistent with our experimental results
[Fig. 2(f)]. This together with the opposite temperature dependence of the BMR
and its small magnitude in region III suggest that the observed BMR is
dominantly from region II. Based on the measured carrier density
$n_{\text{s}}$ ($3.9-5.6\times 10^{13}$ $\mathrm{c}\mathrm{m}^{-2}$), the bulk
Fermi level relative to the unbent surface Dirac point is $\sim$0.3 eV, which
is much higher than the level of the bulk conduction band minimum (CBM) for
Bi2Se3 ($\sim$0.2 eV) [20, 23]. Given the energy splitting $E_{\text{R}}\sim
10$ $\mathrm{m}\mathrm{e}\mathrm{V}$, region II of QW1 cannot be accessed
during the downward BB process. This leads us to draw the schematic picture as
shown in Fig. 4(d). Different from the topological surface states, the QW
states of the 2DEG on the TI surface spread over a depth of $\sim$10 QL [21].
Going from bulk to surface, during the BB process, the position of the Fermi
level relative to the QW1 minimum shifts up gradually, and the region II of
higher QW levels (e.g., QW2) is accessed. It is these states that make
dominant contributions to the observed large BMR which weakens as temperature
increases. As sketched at the bottom of Fig. 4(d), due to the exponential
carrier density profile of the 2DEG [20, 22], the number of electrons in
region II takes a maximum if the local Fermi level at the surface happens to
be in region II. This requires a delicate balance between the bulk Fermi level
and the BB strength. This can explain the significantly different $\gamma$ in
the BS/Cu(1) and BS/Cu(1.5) devices.

In conclusion, we observed large BMR in Bi2Se3 heterostructures surpassing
that of strong bulk Rashba semiconductors. On the one hand, we find Cu is a
preferential material to engineer Bi2Se3 into a Rashba material, because it
not only imposes electrostatic potential to generate sizable RSS, but also
suppresses the bulk conduction through diffusive doping. On the other hand,
analysis on the temperature dependence suggests that the observed BMR is
dominantly from the states below the band-crossing point of higher-level QW
states, accessed during the gradual band-bending process. This ensures the
easy electrical detection of the RSS through BMR and suggests that BMR should
have robust tunability through chemical potential or band-bending engineering.
Our work demonstrates BMR as an electrical transport signature to assist the
search for inversion asymmetric TI heterostructures with large RSS.

###### Acknowledgements.

We thank Yi Ji for the use of the home-built cryogenic transport measurement
system. This work was supported by the U.S. DOE, Office of Basic Energy
Sciences under Contract No. DE-SC0016380 and by NSF DMR Grant No. 1904076. B.
Liu and X.-L. Sheng acknowledge the support from National Natural Science
Foundation of China under Grant No. 12174018. Y.-X. H and S. A. Yang are
supported by Singapore NRF CRP22-2019-0061. The authors acknowledge the use of
the Materials Growth Facility (MGF) at the University of Delaware, which is
partially supported by the National Science Foundation Major Research
Instrumentation under Grant No. 1828141 and UD-CHARM, a National Science
Foundation MRSEC, under Award No. DMR-2011824.

## References

  * [1] Y. Tokura and N. Nagaosa, Nat. Commun. 9, 3740 (2018).
  * [2] T. Ideue, K. Hamamoto, S. Koshikawa, M. Ezawa, S. Shimizu, Y. Kaneko, Y. Tokura, N. Nagaosa, and Y. Iwasa, Nat. Phys. 13, 578 (2017).
  * [3] P. He, S. S. L. Zhang, D. Zhu, Y. Liu, Y. Wang, J. Yu, G. Vignale, and H. Yang, Nat. Phys. 14, 495 (2018).
  * [4] T. Guillet, C. Zucchetti, Q. Barbedienne, A. Marty, G. Isella, L. Cagnon, C. Vergnaud, H. Jaffrès, N. Reyren, J.-M. George, A. Fert, and M. Jamet, Phys. Rev. Lett. 124, 027201 (2020).
  * [5] P. He, S. McKeown Walker, S. S.-L. Zhang, F. Y. Bruno, M. S. Bahramy, J. M. Lee, R. Ramaswamy, K. Cai, O. Heinonen, G. Vignale, F. Baumberger, and H. Yang, Phys. Rev. Lett. 120, 266802 (2018).
  * [6] Y. Wang, H. F. Legg, T. Bömerich, J. Park, S. Biesenkamp, A. A. Taskin, M. Braden, A. Rosch, and Y. Ando, Phys. Rev. Lett. 128, 176602 (2022).
  * [7] H. F. Legg, M. Rößler, F. Münning, D. Fan, O. Breunig, A. Bliesener, G. Lippertz, A. Uday, A. A. Taskin, D. Loss, J. Klinovaja, and Y. Ando, Nat. Nanotechnol. 17, 696 (2022).
  * [8] G. L. J. A. Rikken and P. Wyder, Phys. Rev. Lett. 94, 016601 (2005).
  * [9] G. L. J. A. Rikken, J. Fölling, and P. Wyder, Phys. Rev. Lett. 87, 236602 (2001).
  * [10] F. Pop, P. Auban-Senzier, E. Canadell, G. L. J. A. Rikken, and N. Avarvari, Nat. Commun. 5, 3757 (2014).
  * [11] M. Z. Hasan and C. L. Kane, Rev. Mod. Phys. 82, 3045 (2010).
  * [12] X.-L. Qi and S.-C. Zhang, Rev. Mod. Phys. 83, 1057 (2011).
  * [13] E. I. Rashba, Sov. Phys. Solid State 2, 1109 (1960).
  * [14] Y. A. Bychkov and E. I. Rashba, JETP Lett. 39, 78 (1984).
  * [15] K. Hamamoto, M. Ezawa, K. W. Kim, T. Morimoto, and N. Nagaosa, Phys. Rev. B 95, 224430 (2017).
  * [16] S. S.-L. Zhang and G. Vignale, Proc. SPIE 10732, 1073215 (2018).
  * [17] P. He, S. S.-L. Zhang, D. Zhu, S. Shi, O. G. Heinonen, G. Vignale, and H. Yang, Phys. Rev. Lett. 123, 016801 (2019).
  * [18] Y. Li, Y. Li, P. Li, B. Fang, X. Yang, Y. Wen, D.-x. Zheng, C.-h. Zhang, X. He, A. Manchon, Z.-H. Cheng, and X.-x. Zhang, Nat. Commun. 12, 540 (2021).
  * [19] D. Choe, M.-J. Jin, S.-I. Kim, H.-J. Choi, J. Jo, I. Oh, J. Park, H. Jin, H. C. Koo, B.-C. Min, S. Hong, H.-W. Lee, S.-H. Baek, and J.-W. Yoo, Nat. Commun. 10, 4510 (2019).
  * [20] M. Bianchi, D. Guan, S. Bao, J. Mi, B. B. Iversen, P. D. C. King, and P. Hofmann, Nat. Commun. 1, 128 (2010).
  * [21] M. S. Bahramy, P. D. C. King, A. de la Torre, J. Chang, M. Shi, L. Patthey, G. Balakrishnan, Ph. Hofmann, R. Arita, N. Nagaosa, and F. Baumberger, Nat. Commun. 3, 1159 (2012).
  * [22] P. D. C. King, R. C. Hatch, M. Bianchi, R. Ovsyannikov, C. Lupulescu, G. Landolt, B. Slomski, J. H. Dil, D. Guan, J. L. Mi, E. D. L. Rienks, J. Fink, A. Lindblad, S. Svensson, S. Bao, G. Balakrishnan, B. B. Iversen, J. Osterwalder, W. Eberhardt, F. Baumberger, and P. Hofmann, Phys. Rev. Lett. 107, 096802 (2011).
  * [23] Z.-H. Zhu, G. Levy, B. Ludbrook, C. N. Veenstra, J. A. Rosen, R. Comin, D. Wong, P. Dosanjh, A. Ubaldini, P. Syers, N. P. Butch, J. Paglione, I. S. Elfimov, and A. Damascelli, Phys. Rev. Lett. 107, 186405 (2011).
  * [24] See Supplemental Material at [URL will be inserted by publisher] for details on experimental and computational methods, Bi2Se3 film characterization, the transverse nonlinear Hall measurement results, and model calculations, which includes Refs. [32, 33, 34, 35, 36, 37, 38, 39, 40]
  * [25] Y.-L. Wang, Y. Xu, Y.-P. Jiang, J.-W. Liu, C.-Z. Chang, M. Chen, Z. Li, C.-L. Song, L.-L. Wang, K. He, X. Chen, W.-H. Duan, Q.-K. Xue, and X. C. Ma, Phys. Rev. B 84, 075335 (2011).
  * [26] S.-J. Chang, P.-Y. Chuang, C.-W. Chong, Y.-J. Chen, J.-C. A. Huang, P.-W. Chen and Y.-C. Tseng, RSC Adv. 8, 7785 (2018).
  * [27] H.-J. Wu and W.-T. Yen, RSC Adv. 157, 33 (2018).
  * [28] S. Dan, S. Kumar, S. Dan, D. Pal, S. Patil, A. Verma, S. Saha, K. Shimada, and S. Chatterjee, Appl. Phys. Lett. 120, 022105 (2022).
  * [29] H. Steinberg, D. R. Gardner, Y. S. Lee, and P. Jarillo-Herrero, Nano Lett. 10, 5032 (2010).
  * [30] C. M. Acosta, E. Ogoshi, A. Fazzio, G. M. Dalpian, and A. Zunger, Matter 3, 145 (2020).
  * [31] H. Yang, X. Peng, X. Wei, W. Liu, W. Zhu, D. Xiao, G. M. Stocks, and J. Zhong, Phys. Rev. B 86, 155317 (2012).
  * [32] Z. Wang and S. Law, Cryst. Growth Des. 21, 6752 (2021).
  * [33] G. Kresse and J. Hafner, Phys. Rev. B 49, 14251 (1994).
  * [34] G. Kresse and J. Furthmüller, Phys. Rev. B 54, 11169 (1996).
  * [35] Blöchl, Phys. Rev. B 50, 17953 (1994).
  * [36] J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865 (1996).
  * [37] S. Grimme, J. Antony, S. Ehrlich, and H. Krieg, J. Chem. Phys. 132, 154104 (2010).
  * [38] S. Grimme, S. Ehrlich, and L. Goerigk, J. Comput. Chem. 32, 1456 (2011).
  * [39] A. Wolos, S. Szyszko, A. Drabinska, M. Kaminska, S. G. Strzelecka, A. Hruban, A. Materna, M. Piersa, J. Borysiuk, K. Sobczak, and M. Konczykowski, Phys. Rev. B 93, 155114 (2016).
  * [40] T. H. Wang and H. T. Jeng, arXiv:1608.00348 (2016).