Growth function $\tau_{\mathcal{H}}(m)$ lower bound I have been working on this problem for a long time and I would like some help. They ask me to find for each $ n $ a hypothesis class $ \mathcal {H} \subset \{\pm 1 \}^{\mathbb {N}} $ with $ n $ elements such that the growth function is $ \tau_{\mathcal{H}}(m) =\min\{ m+1,n \}$. And they ask me to prove that in general $\tau_{\mathcal{H}}(m) \geqslant \min\{ m+1,n \}$ if $|\mathcal{H}|=n$.
I have worked with the indicator functions of the sets $\{1\}, \{2\},\ldots, \{n\}$ and $\{1\}, \{1,2\},\ldots, \{1,2,\ldots,n\}$ but in no case have I obtained results. I would appreciate if you could help me.
A hypothesis class is just a designation for that subset of functions of $ \{\pm 1 \}^{\mathbb{N}}$ (in this case). And the growth function is $$\tau_{\mathcal{H}}(m)=\sup |\mathcal{H}_{C}|$$ where the supreme is taken over all subsets $ C \subset \mathbb{N}$ such that $|C|=m$. Here, $$\mathcal{H}_{C}=\{ h|_{C}: h\in \mathcal{H} \}$$
 A: $\newcommand{\mh}{\mathcal H}$So the idea behind this question, is to understand how one can create $\mathcal H$ in such a way that $\tau_{\mathcal H}(m)$ is minimized for a particular $m$. For this, we'll prove the inequality, and then see how the inequality can be tightened to be exact.

We first make some remarks.
The most important thing about the supremum is that because $\mh_C$ takes only integer values, the supremum in $l=\tau_{\mh}(m) = \sup_{|C| = m} |\mathcal H_C|$ is attained. That is, there exists a subset $C = \{x_1,...,x_m\}$ such that $|\{h|_{\{x_1,...,x_m\}} : h \in \mathcal H\}| = |\mathcal H_C|=l$.
Now, we claim that $\mathcal H$ has at least $l$ distinct elements. Suppose not, say $\mathcal H$ had $k<l$ elements. Then, the set $\{h|_{\{x_1,...,x_m\}} : h \in \mathcal H\}$ can have only $k$ elements because there are only $k$ functions available to restrict to $C$. This is a contradiction since we know this quantity is bigger than $k$. Therefore, $n=|\mh| \geq l$.

Now, we go through an algorithm. We will shortly see what this algorithm produces.
We begin with $\mathcal H$, so let $\mh = \{h_1,h_2,...,h_n\}$ where $n = |\mh|$.

*

*There is a point $x_1$ such that $h_1(x_1) \neq h_2(x_1)$, because otherwise $h_1=h_2$, a contradiction.


*Now,we know that $h_3(x_1)$ is equal to either $h_1(x_1)$ or $h_2(x_1)$. Suppose that it equals $h_i(x_1)$ for $i \in \{1,2\}$. Then, we know that there is a different point $x_2 \neq x_1$ such that $h_i(x_2) \neq h_3(x_2)$ (because otherwise, $h_i=h_3$ everywhere, which is not possible).


*Now, consider $h_4$. Then, we have two possibilities : either there is an $i\in \{1,2,3\}$ such that $h_4(x_1) = h_i(x_1)$ and $h_4(x_2) = h_i(x_2)$, OR there is no such $i$. In the latter case, just take any $x_3 \neq x_2,x_1$. In the former case, there is a $x_3 \neq x_2,x_1$ where $h_4(x_3) \neq h_i(x_3)$  (because otherwise, $h_4 =h_i$ everywhere).


*In the general case : suppose that $\{x_1,...,x_{l-1}\}$ are available. Then, consider $h_l$. One of the following must be true : either there is no $i \in \{1,2,...,l-1\}$ such that $h_{i}(x_j) = h_l(x_j)$ for all $j \in \{1,2,...,l-1\}$, or there is such an $i$. In the former case, take any $x_l \neq x_1,x_2,...,x_{l-1}$. In the latter case, there is an $x_l \neq x_1,x_2,...,x_{l-1}$ where $h_l(x_l) \neq h_i(x_l)$, and we update the set $\{x_1,...,x_l\}$.
This algorithm stops only when we run out of elements in $\mathcal H$ : otherwise,we can keep going!

Suppose that, after $l$ steps, we have the set $S_l = \{x_1,...,x_l\}$. We claim the following : let $\mh_l$ be the set of functions $\{h_1,...,h_{l+1}\}$. We claim that $|(H_l)_{S_l}| \geq l+1$.
First for $l=1$. Clearly $h_1|_{\{x_1\}} , h_2|_{\{x_1\}} \in \mathcal H_{\{x_1\}}$ and these are distinct. Therefore, $|\mh_{\{x_1\}} | \geq 2$ or in other words, $|\mh_{S_1}| \geq 2$.
Now for general $l$. We have two cases : either there is an $i$ such that $h_i(x_j) = h_l(x_j)$ for all $j= 1,2,...,l-1$, or there is no such $i$. By our induction hypothesis we know that the set $(H_l)_{S_l}$ has at least $l+1$ elements. Now, if there is no such $i$, then we know that $h_l|_{S_l}$ is different from $h_i|_{S_l}$ for all $i=1,2,...,l-1$, and hence $h_l|_{S_{l+1}}$ is different from $h_i|_{S_{l+1}}$ for all $i = 1,2,...,l-1$. If there is such an $i$, then the construction proves that $h_j|_{S{l+1}}$ is different from $h_l|_{S_{l+1}}$ for all $j=1,2,...,l-1$, because for the $i$ where the $h_i$ does equal $h_l$ on $S_l$, $x_l$ has been chosen to ensure they differ at it (and for the $i$ that don't match, we go back to the other logic anyway). Therefore, whatever happens, $(H_l)_{S_l}$ contains $l+2$ distinct elements, counting the newly inducted and distinct $h_{l}|_{S_{l+1}}$. The induction is complete.

But now, we're actually done, because :

*

*Suppose that $m+1 \leq n$. Then, we keep going in the algorithm and stop at step $m$, which we can do because we have at least $m+1$ functions. At this point, we know that $|(\mathcal H_m)_{S_m}| \geq m+1$, therefore $$ \tau_{\mh}(m) \geq |\mh_{S_m}| \geq |(\mathcal H_m)_{S_m}| \geq m+1$$ as desired.


*Suppose that $m+1>n$. Then, we stop the algorithm at $n-1$ steps, at which point we've got the statement $|(\mathcal H_{n-1})_{S_{n-1}}| \geq n$. Since $\mh = \mathcal H_{n-1}$, we have :
$$
\tau_{\mh}(m) \geq |(\mh)_{S_{n-1}}| = |(\mh_{n-1})_{S_{n-1}}| \geq n
$$
Hence, $\tau_{\mh}(m)\geq \min\{m+1,|\mh|\}$.

Now, how can we make an $h_i$ for which this algorithm is water-tight? I appreciate the reasoning you've made to come up with an example.
The point is, to make sure that at each step there is exactly one candidate that we can add to $S_l$, and no more. If we do this, then the algorithm actually becomes an equality at each stage, but it also turns out that we can get equality in the other inequalities we used, to get the hypothesis class we wish for.

Your example is actually correct, so our hypothesis class $\mh = \{h_i\}$ is defined as $h_i(k) = -1$ if $i \leq k$ and $h_i(k) = 1$ otherwise. (which is basically the indicators of $\{1\},\{1,2\},\{1,2,3\},...$)
We will prove that $\tau_{\mh}(m) = m+1$ for all $m$.
Indeed, let us consider a subset $C$ of size $m$. Let $C$ be $C = \{x_1,x_2,...,x_m\}$ with $x_1<x_2<...<x_m$. Then, the functions in $\mh_C$ is easily seen to be exactly the set $$
1_{[x_1,...,x_m]}, 1_{[x_2,...,x_m]}, ... , 1_{x_m}
$$
regardless of the values of $x_1,...,x_m$. Therefore, the set $|\mh_C|$ always has size $m+1$ for any $C$ of size $m$, and hence $\tau_{\mh}(m) = m+1$.
Now, if you want an exact example where $n<m+1$, then you can just take the first $n$ functions of the function class $\mh$ I described above (namely the set $\mh_n = \{h_1,...,h_n\}$), and see that here , if $n<m+1$, then $\tau_{\mh_n}(m) = n$. This follows because you can use the same idea as I used in the other case and explicitly describe what $h_i|_{C}$ are ,for $1 \leq i \leq n$ and any set $C= \{x_1,...,x_m\}$ with $x_1<x_2<...<x_m$.
