text:
\section{Dual Map for $\phi$-Separable Dichotomy: Proof of \thmref{dual map}}\label{appendix: Dual map}
In this appendix, we provide the proof of our main result for the construction of dual map \tt{i.e.} \thmref{dual map}. Using the properties of the dual map and bounds on the average teaching complexity for convex polytopes \tt{i.e.} \thmref{theorem: Main Theorem}, we provide the proof of \corref{cor: teach phi surfaces} which establishes similar bound on the average teaching complexity of $\phi$-separable dichotomies. We first state and prove the necessary lemmas and results in order to prove \thmref{dual map}. Before that, we mention a fundamental result from linear algebra \citep[also mentioned in][Theorem 2.8]{roman2007advanced} which would be used in a number of lemmas across appendices.

\begin{theorem}[Rank-Nullity Theorem]\label{theorem:rank nullity}
Let $V$ and $W$ be vector spaces over a field $F$, and let $T$: $V \rightarrow W$ be a linear transformation. Assuming the dimension of $V$ is finite, then
\begin{equation}
    \dim(V) = \dim(\textnormal{Ker}(T)) + \dim(\textnormal{Im}(T))
\end{equation}
where $\dim(\textnormal{Ker}(T))$ is nullity of $T$ and $\dim(\textnormal{Im}(T))$ is the rank of $T$.
\end{theorem}
\subsection{Relevant Lemmas for Proof of \thmref{dual map}}
First, we would prove a straight-forward result for homogeneous linear separability which forms the basis for the equivalence relation we obtained in \secref{sec.applied}.
\begin{lemma}\label{lemma:symmetry}
If $w$ is the normal vector for the homogeneous linear separator of $\curlybracket{\xndp,\xndn}$ then, $-w$ is the normal vector for the homogeneous linear separator of $\curlybracket{\xndn,\xnd}$.
\end{lemma}
\begin{proof} If $w$ is the normal vector for a homogeneous linear separator of $\curlybracket{\xndp,\xndn}$, then,
\begin{align*}
    w\cdot x > 0 \Leftrightarrow  (-w)\cdot x < 0\:  \: \text{if}\: x  \in \xndp\\
     w\cdot x < 0 \Leftrightarrow  (-w)\cdot x > 0\:  \: \text{if}\: x  \in \xndp
\end{align*}
Thus, $-w$ is the the normal vector for a homogeneous linear separator of $\curlybracket{\xndn,\xndp}$
\end{proof}
\noindent
To study the arrangement of dual hyperplanes, we define the matrices $\boldlam_{[(n-1)\times d]}$ and $\bracket{\boldlam_h}_{[(n-1)\times (d-1)]}$ such that $\forall$ $i \in \bracket{n-1}$ $\boldlam\bracket{i,:} = x^{(i)}$ and $\boldlam_h\bracket{i,:} = x_{[d-1]}^{(i)}$ where $x_{[d-1]}$ is first $d-1$ components of $x$. Using the $d'$-relaxed general position arrangement of $\xnd$ and nullity of $x^{(n)}$ as a dimension, in \lemref{rank dual} we show that $\rank{\boldlam_h}$ = $d'-1$ and any ($d'-1$) rows of $\boldlam_h$ are linearly independent .
\begin{lemma}\label{rank dual}
For the matrices constructed above, $\rank{\boldlam_h}$ = $d'-1$, and any ($d'-1$) rows of $\boldlam_h$ are linearly independent.
\end{lemma}
\begin{proof}
First part of the lemma is straight-forward since, by definition any $d'$ vectors in $\xnd$ are linearly independent which means $d'$ columns of $\boldlam$ are linearly independent, implying $(d'-1)$ columns of $\boldlam_h$ are linearly independent.\vspace{6pt}\\
\noindent
For the second part, for an indexed set $\mathbb{I}_{[d'-1]}$ $\triangleq$ $\curlybracket{i_1,i_2,\cdots,i_{d'-1}}$ consider the $(d'-1)$ rows
$\curlybracket{x_{[d-1]}^{(i_1)},x_{[d-1]}^{(i_2)},\cdots,x_{[d-1]}^{(i_{d'-1})}}$ of $\boldlam_h$ which are linearly dependent. Thus, $\exists$ scalars $\alpha_j$'s (not all zeros) such that:
\begin{align}
    \sum_{j=1}^{d'-1} \alpha_j\cdot x_{[d-1]}^{(i_j)} = 0 &\implies \sum_{j=1}^{d'-1} \alpha_j\cdot \bigparen{x_{[d-1]}^{(i_j)}, x^{(i_j)}_d} - \left(\sum_{j=1}^{d'-1}\alpha_j\cdot x^{(i_j)}_d\right)\cdot x^{(n)} = 0 \label{eqn:eqnd01}\\
    & \implies \sum_{j=1}^{d'-1}\alpha_j\cdot x^{(i_j)} - \left(\sum_{j=1}^{d'-1}\alpha_j\cdot x^{(i_j)}_d\right)\cdot x^{(n)} = 0 \label{eqn:eqnd02}
\end{align}
In \eqnref{eqn:eqnd01} we use that $x^{(n)} = \mathbi{e}_d$.
\eqnref{eqn:eqnd02} implies that we have $d'$ vectors of $\xnd$ linearly dependent. Contradiction! Thus, for any indexed set $\mathbb{I}_{[d'-1]}$, the corresponding submatrix of dimension $[d'-1 \times d'-1]$ of $\boldlam_h$, is full rank. Hence, the second part of the lemma is proven.
\end{proof}
Now, we would give the proof of the key lemma of duality which shows that the mapped hyperplanes follow the criterion of ($d'-1$)-relaxed general position. For the sake of clarity and flow, we would restart with the construction of sets. Let us define $\mathbb{I}_{[k]}$ $\triangleq$ $\{i_1,i_2,...,i_k\}$ as $k$ indices for rows. Denote by $\boldlam_{\mathbb{I}_{[k]}}$ = $\boldlam_{[\mathbb{I}_{[k]}\times d]}$ (rows of $\mathbf{\boldlam}$ corresponding to $\mathbb{I}_{[k]}$) and by $(\boldlam_h)_{\mathbb{I}_{[k]}}$ = $(\boldlam_h)_{[\mathbb{I}_{[k]}\times d-1]}$ (rows of $\boldlam_h$ corresponding to $\mathbb{I}_{[k]}$). As in \secref{sec.applied}, we redefine $\xnd$ $\triangleq$ $\curlybracket{x^{(1)}, x^{(2)}, \dots, x^{(n)}}$.

\begin{lemma}[Key lemma of duality]\label{key lemma of duality}
If $\mathcal{S}^k_{\cap}$ = $\condcurlybracket{x \in \mathbb{R}^{d-1}}{\boldlam_{\mathbb{I}_{[k]}}\binom{x}{1} = \mathbf{0}^k}$ for $1 \le k \le (d'-1)$, then $\dim(\mathcal{S}^k_{\cap}) = (d-1)-k$. Moreover, no $d'$ rows of $\boldlam$ intersects in dual space \tt{i.e.} $\condcurlybracket{x \in \mathbb{R}^{d-1}}{\boldlam_{\mathbb{I}_{[d']}}\binom{x}{1} = \mathbf{0}^{d'}} = \emptyset$.
\end{lemma}
\begin{proof}[Proof of \lemref{key lemma of duality} of Duality]
Define by $\mathbi{b} \triangleq \parenb{x^{(i_1)}_d, x^{(i_2)}_d,\cdots,x^{(i_k)}_d}$. Notice that,
\begin{align}
\mbox{\large\(
    \boldlam_{\mathbb{I}_{[k]}}\binom{x}{1} = 0 \Longleftrightarrow  (\boldlam_h)_{\mathbb{I}_{[k]}}x = -\mathbi{b}^{\top} \label{eqn:eqnd03}
\)}
\end{align}
If $k = d'-1$ then $(\boldlam_h)_{\mathbb{I}_{[d'-1]}}$ is $d'-1$ rank invertible matrix implying \eqnref{eqn:eqnd03} has a \textit{unique} solution.
\newline
Note that using \lemref{rank dual}, $(\boldlam_h)_{\mathbb{I}_{[k]}}$ has rank $k$ for $k < d'$. This implies that there is some $x_0 \in \mathbb{R}^{d-1}$ such that $(\boldlam_h)_{\mathbb{I}_{[k]}}x_0 = -\mathbi{b}^{\top}$. Thus, we rewrite \eqnref{eqn:eqnd03} as
\begin{align*}
\mbox{\large\(
    \boldlam_{\mathbb{I}_{[k]}}\binom{x}{1} = 0 \Longleftrightarrow (\boldlam_h)_{\mathbb{I}_{[k]}}x = (\boldlam_h)_{\mathbb{I}_{[k]}}x_0 \Longleftrightarrow (\boldlam_h)_{\mathbb{I}_{[k]}}(x-x_0) = 0
    \)}
\end{align*}
But using \thmref{theorem:rank nullity}, \textbf{Ker}$\parenb{(\boldlam_h)_{\mathbb{I}_{[k]}}}$ = $(d-1)-k$. This implies that $\dim\bigparen{\condcurlybracket{x \in \mathbb{R}^{d-1}}{(\boldlam_h)_{\mathbb{I}_{[k]}}(x-x_0) = 0}}$ = $(d-1)-k$. Thus, $\dim(\mathcal{S}^k_{\cap}) = (d-1)-k$. \\
\newline
Notice that if $\boldlam_{\mathbb{I}_{[d']}}\binom{x}{1} = \mathbf{0}^{d'}$ has a solution then we can define $\binom{x}{1}$ as a homogeneous linear separator and the points of $\xnd$ corresponding to $\boldlam_{\mathbb{I}_{[d']}}$ lie on a $(d-1)$-dimensional halfspace (subspace) defined by $\binom{x}{1}$. Note, $\dt{}^{(n)}$ doesn't lie on that subspace. On the other hand, because of $d'$-relaxed general position arrangement of $\xnd$, rows of $\boldlam_{\mathbb{I}_{[d']}}$ are linearly independent and lie on the subspace. It implies $\textbf{rows}(\boldlam_{\mathbb{I}_{[d']}})\cup \{\dt{}^{(n)}\}$ are linearly independent. Contradiction. Thus, $\condcurlybracket{x \in \mathbb{R}^{d-1}}{\boldlam_{\mathbb{I}_{[d']}}\binom{x}{1} = \mathbf{0}^{d'}} = \emptyset$.

Hence, the lemma follows.
\end{proof}
With \lemref{key lemma of duality} and \eqnref{eqn:construction}, we can formally prove our main theorem of the section on the dual map which says the dual set of hyperplanes are in $(d'-1)$-\tt{relaxed general position} and each equivalence class of dichotomies $\mathfrak{E}\parenb{\xnd}$ maps \tt{uniquely} to all the concepts (hypotheses) in $\boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\Hndo)}$.

\subsection{Proof of \thmref{dual map} and \corref{cor: teach phi surfaces}}
In this subsection, we provide the proof of the results of interest. Following the notations in \secref{sec.applied}, we use slightly different notations in the proofs for the sake of clarity.
For a dichotomy class $\bracket{\mathbi{v}} \in \mathfrak{E}\parenb{\xnd}$, we denote the dual point to a separator $w_{\bracket{\mathbi{v}}}$ of the representative dichotomy by $z_{w_{\bracket{\mathbi{v}}}}$ and region corresponding to $z_{w_{\bracket{\mathbi{v}}}}$ as\footnote{In section \secref{sec.applied}, we denote the dual point of the separator  $w_{\bracket{\mathbi{v}}}$ to $\bracket{\mathbi{v}}$ as $\h{}_{\bracket{\mathbi{v}}}$ and region containing $\h{}_{\bracket{\mathbi{v}}}$ as $r_{\h{}_{\bracket{\mathbi{v}}}}$.} $ r_{\h{}_{w_{\bracket{\mathbi{v}}}}} \in \boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\boldsymbol{\bar{\mathcal{H}}})}$ such that $z_{w_{\bracket{\mathbi{v}}}}
\in r_{\h{}_{w_{\bracket{\mathbi{v}}}}}$ \tt{i.e.} $r_{\h{}_{w_{\bracket{\mathbi{v}}}}} = \varphi_{\mathrm{dual}}(\bracket{\mathbi{v}})$.\\

\begin{proof}[Proof of \thmref{dual map}]
By the definition of \ref{tag: d.m}, we get $\Hndo = \Upsilon_{\mathrm{dual}}\parenb{\xnd}$. We constructed the matrices $\boldlam_{[n-1\times d]}$ and $\bracket{\boldlam_h}_{[n-1\times d-1]}$ to study the arrangement of dual hyperplanes. In the Key \lemref{key lemma of duality} of Duality, we proved that $\forall$ $1 \le k \le d'-1$, any size $k$ subset of $\Hndo$ intersects in a flat of dimension $(d-1-k)$ and no $d'$ dual hyperplanes intersect at a point. Thus, we show that $\Hndo$ is in $(d'-1)$-relaxed general position arrangement which proves the first part of the theorem.

First, we notice that $\varphi_{\mathrm{dual}}$ is well-defined since \eqnref{eqn:construction} is a sign preserving construction.
To prove the bijection of $\varphi_{\mathrm{dual}}$, we first show that it is an \tt{injection}. We assume that $\#\mathfrak{E}\parenb{\xnd} > 1$ since the other case can be handled trivially.
Denote by $\bracket{\mathbi{u}}, \bracket{\mathbi{v}}$ two different equivalence classes of $\mathfrak{E}\parenb{\xnd}$. Let $w_{\bracket{\mathbi{u}}}$ and $w_{\bracket{\mathbi{v}}}$ be two corresponding linear separators respectively. Since $\bracket{\mathbi{u}} \neq \bracket{\mathbi{v}}$, $\exists$ at \tt{least} one point $x' \neq x^{(n)} \in \xnd$ which is classified/labeled \tt{differently}. Consider the dual hyperplane $h_{x'} = \Upsilon_{\mathrm{dual}}(x')$, and the dual points $z_{w_{\bracket{\mathbi{u}}}}$ and $z_{w_{\bracket{\mathbi{v}}}}$ of $w_{\bracket{\mathbi{u}}}$ and $w_{\bracket{\mathbi{v}}}$ respectively using the construction shown in \eqnref{eqn:construction}. Since $w_{\bracket{\mathbi{u}}}$ and $w_{\bracket{\mathbi{v}}}$ classify $x'$ differently, $z_{w_{\bracket{\mathbi{u}}}}$ and $z_{w_{\bracket{\mathbi{v}}}}$ belongs to two different regions of $h_{x'}$, implying $r_{z_{w_{\bracket{\mathbi{u}}}}} \not\equiv r_{z_{w_{\bracket{\mathbi{v}}}}}$ where $r_{z_{w_{\bracket{\mathbi{u}}}}} = \varphi_{\mathrm{dual}}(\bracket{\mathbi{u}})$ and $r_{z_{w_{\bracket{\mathbi{v}}}}} = \varphi_{\mathrm{dual}}(\bracket{\mathbi{v}})$. Thus, $\varphi_{\mathrm{dual}}$ is an injection.
Consider a region $r \in \boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\boldsymbol{\bar{\mathcal{H}}})}$. Pick a point $z_0 \in r$. Now, define $w_z \triangleq (z_0^{\top},1)$. Since $z_0 \in r$, $w_z$ is a homogeneous linear separator of a dichotomy in the primal space corresponding to $r$ where dichotomy is defined by signs using \eqnref{eqn:construction}. Note that it is a valid dichotomy since $0\cdot z_0 + 1 > 0$ implying $(z_0^{\top},1)$ labels $x^{(n)}$ positively. We represent the dichotomy using the class $\bracket{\mathbi{u}}$. Since, $z_0$ is arbitrary, thus $\varphi_{\mathrm{dual}}^{-1}(r)= \bracket{\mathbi{u}}$ implying surjection of $\varphi_{\mathrm{dual}}$. Hence, we show $\varphi_{\mathrm{dual}}$ is a bijection.

\end{proof}

\noindent
The properties of the dual map is key in showing the bound on the teaching complexity of $\phi$-separable dichotomies. We note that the dual map retains the arrangement of the general position of points (\defref{general position vectors}) to relaxed general position of hyperplanes in the dual space (\defref{defn relaxed general position}). Thus, our bound on the average teaching complexity of convex polytopes in \thmref{theorem: Main Theorem} applies in the case of average teaching complexity of $\phi$-separable dichotomies which we show in \corref{cor: teach phi surfaces}. We present the proof of the corollary here.
\newline
\begin{proof}[Proof of \corref{cor: teach phi surfaces}] For the set $\xnd$, we consider the set of $\phi$-induced points $\phi(\xnd)$ =  $\{\phi(x^{(1)}),\phi(x^{(2)}),\dots,\phi(x^{(n)})\}$ in the $\phi$ induced primal space $\mathbb{R}^{d_{\phi}}$. For the $\phi$-separable dichotomies of $\xnd$, we denote the quotient set of equivalence classes of dichotomies as $\boldsymbol{\mathfrak{E}}_{\xnd}^{\phi}$. Since $\xnd$ are in $d'_\phi$-relaxed $\phi$-general position  for a fixed $d'_\phi \in [d_\phi]$
, we can apply the dual map $\bracket{\Upsilon_{\mathrm{dual}} ,\varphi_{\mathrm{dual}}}$ on the pair $[\phi(\xnd), \boldsymbol{\mathfrak{E}}_{\xnd}^{\phi}]$. We denote the set of
$d'_\phi-1$-relaxed general position
dual hyperplanes by $\boldsymbol{\mathcal{H}}_{n-1,d'_{\phi}-1} \triangleq \Upsilon_{\mathrm{dual}}(\phi(\xnd))$, and the set of dual regions as $\boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\boldsymbol{\mathcal{H}}_{n-1,d'_{\phi}-1})} \triangleq \varphi_{\mathrm{dual}}(\boldsymbol{\mathfrak{E}}_{\xnd}^{\phi})$. Using the definition of the teaching set for $\phi$-separable dichotomies and bijection of $\varphi_{\mathrm{dual}}(\cdot)$ (using \thmref{dual map}), we can write:
\begin{equation}
\expctover{\rgn_{[\mathbi{u}]} \sim \mathcal{U}}{M_n} =
\expctover{r\sim\cU}{|\mathcal{TS}(\boldsymbol{\mathcal{H}}_{n-1,d'_{\phi}-1},r)|} \label{eqn:phibound}
\end{equation}
where $\rgn_{[\mathbi{u}]}$ is a random class in $\boldsymbol{\mathfrak{E}}_{\xnd}^{\phi}$ and $r$ is a uniformly random region in $\boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\boldsymbol{\mathcal{H}}_{n-1,d'_{\phi}-1})}$. But, using \thmref{theorem: Main Theorem}, we know that $\mathrm{rhs}$ in \eqnref{eqn:phibound} is bounded by $\cO(d_{\phi}')$. Thus, we show that the average teaching complexity of $\phi$-separable dichotomies is $\cO(d_{\phi}')$. This proves the corollary.
\end{proof}
\clearpage