For $n\ge 1$ we write $[n]$ to denote the set $\{0,1,\ldots,n-1\}$. Let $2^{[n]}$ be the set of all functions from $[n]$ to $\{0,1\}$. Let $\mathcal{F}$ and $\mathcal{G}$ be two nonempty subsets of $2^{[n]}$. Fix $1\le k\le n$. Take $0\le j \le n-k$. We say that $f,g\in 2^{[n]}$ **disagree over $[j,j+k)$** if the restrictions of $f$ and $g$ to $\{j,j+1,\ldots,j+k-1\}$ are different, that is, $f|\_{\{j,j+1,\ldots,j+k-1\}}\neq g|\_{\{j,j+1,\ldots,j+k-1\}} $. We say that $f\in 2^{[n]}$ **disagree** with a nonempty $\mathcal{G}\subset 2^{[n]}$ over $[j,j+k)$ if for every $g\in\mathcal{G}$ we have that $f$ and $g$ disagree over $[j,j+k)$. That is, for some fixed $j$ the function $f$ disagress over $[j,j+k)$ with all functions in $\mathcal{G}$.


We say that $\mathcal{F}$ and $\mathcal{G}$ are **$k$-separated** if there exists $0\le j \le n-k$ such that 
either there exists $f\in\mathcal{F}$ which disagrees with $\mathcal{G}\subset 2^{[n]}$ over $[j,j+k)$ or there exists $g\in\mathcal{G}$ which disagrees with $\mathcal{F}\subset 2^{[n]}$ over $[j,j+k)$.


Let $\mathscr{T}\_{n,k}$ be the **largest possible** family of pairwise $k$-separated nonempty subsets of $2^{[n]}$, that is, $\mathscr{T}\_{n,k}$ is a family of maximal cardinality among all families $\mathscr{F}$ such that if $\mathcal{F},\mathcal{G}\in \mathscr{F}$ and $\mathcal{F}\neq \mathcal{G}$ then $\mathcal{F}$ and $\mathcal{G}$ are $k$-separated.


Keeping $k$ fixed I am looking for an asymptotic behaviour of the cardinality, $|\mathscr{T}\_{n,k}|$ of $\mathscr{T}\_{n,k}$ as $n\to\infty$. In particular, I hope that
$$
\frac{|\mathscr{T}\_{n,k}|}{2^{2^n}}\to 1\text{ as }n\to\infty.
$$



Size of a family of sets of $k$-separated functions over $\{0,1,\ldots,n-1\}$
**1: Hopes.** Let me begin by taking away your hope - that is, disproving the conjectured asymptotic, $|{\mathscr{T}\_{n,k}}|/2^{2^n} \to 1$.


I will say that a family $\mathcal{F}$ is $k$-rich if for each $j \in [n]$ and $w \in \{0,1\}^k$, there is $f \in \mathcal{F}$ with $f|\_{[j,j+k)} = w$. Accordingly, I will say that a pair $(j,w) \in [n] \times \{0,1\}^k$ "bad" for $\mathcal{F}$ if $f|\_{[j,j+k)} \neq w$ for all $f \in \mathcal{F}$, so that $\mathcal{F}$ is $k$-rich if it has no "bad" pair $(j,w)$.


**Claim.** No two $k$-rich families are $k$-separated.


*Proof.* For any sequence $g \in \{0,1\}^n$, any $j \in [n]$ and any $k$-rich family $\mathcal{F}$, there exists $f \in \mathcal{F}$ such that $g|\_{[j,j+k)} = f\_{[j,k+j)}$. Hence, $g$ does not disagree with $\mathcal{F}$ over $[j,j+k)$. The rest follows by unwinding definitions.


**Claim.** The number of families that are not $k$-rich is $o(2^{2^n})$.


*Proof.* Recall taht for each family $\mathcal{F}$ that is not $k$-rich, there exist a "bad" pair $j \in [n]$, $w \in \{0,1\}^k$. Given $j \in [n]$, $w \in \{0,1\}^k$, the number of $f \in \{0,1\}^{[n]}$ with $f|\_{[j,j+k)} \neq w$ is $(1-2^{-k})2^n$. Hence, the number of families $\mathcal{F}$ for which the pair $(j,w)$ is bad is $2^{(1-2^{-k})2^n}$. By the union bound, the number of families that are not $k$-richis at most $2^{2^n} \times {2^k n}/{2^{2^{n-k}}}$. If $k$ is kept constant and $n \to \infty$, then ${2^k n}/{2^{2^{n-k}}} \to 0$.


**2: Asymptotics.** We will show that $\lim\_{n \to \infty} \log |\mathscr{T}\_{n,k}|/n = 2^{k(1+o(1))}$, where the $o(1)$ term tends to $0$ as $k \to \infty$.


For a given family $\mathcal{F}$, let $B(\mathcal{F})$ denote the set of ``bad'' pairs $j,w$:
$$B(\mathcal{F}) = \{ (j,w) \ : \ f\_{[j,j+k)} \neq w \quad \forall f \in \mathcal{F}\} \subset [n] \times \{0,1\}^k.$$


**Claim:** Two families $\mathcal{F}, \mathcal{G}$ are $k$-separated if and only if $B(\mathcal{F}) \neq B(\mathcal{G})$.


*Proof:* Suppose that $f \in \mathcal{F}$ and $j$ is such that $f$ disagrees with $\mathcal{G}$ on $[j,j+k)$. Then $(j,f|\_{[j,j+k)}) \in B(\mathcal{G}) \setminus B(\mathcal{F})$. Conversely, if $(j,w) \in B(\mathcal{G}) \setminus B(\mathcal{F})$ then there exists $f \in \mathcal{F}$ such that $w=f|\_{[j,j+k)}$, and since $(j,w) \in B(\mathcal{G})$, $f$ disagrees with $\mathcal{G}$ on $[j,j+k)$. 


Since each two sets in $\mathscr{T}\_{n,k}$ are $k$-separated, each of them corresponds to a different subset of $[n] \times \{0,1\}^k$, and so $$|\mathscr{T}\_{n,k}| \leq 2^{n2^k}.$$


In the opposite direction, let $\mathscr{B}$ denote the family of all sets $B \subset [n] \times \{0,1\}^k$ such that $k \mid j$ and $\sum\_{i} w\_i \equiv 1 \bmod{2}$ for all $(j,w) \in B$. 


**Claim:** For each $B \in \mathscr{B}$ there exists a family $\mathcal{F}\_B$ such that $B(\mathcal{F}\_B) = B$.


*Proof:* Let $\mathcal{F}$ consis of all sequences $f \in \{0,1\}^n$ such that $f|\_{[j,j+k)} \neq w$ for each $(j,w) \in B$. Clearly, $B \subset B(\mathcal{F})$ so it remains to show that $B(\mathcal{F})$ contains no other pair. Let $(i,u) \in [n] \times \{0,1\}^k \setminus B$ be any such tentative pair. We need to construct $f \in \mathcal{F}$ with $f\_{[i,i+k)} = u$. On each interval $[j,j+k)$ with $k \mid j$ and $[i,i+k) \cap [j,j+k) = \emptyset$, put $f|\_{[j,j+k)} = 0^k$. If $i < j < i+k$, $k \mid j$, then set $f|\_{[i,j)} = u\_{[0,j-i)}$, $f\_j = \sum\_{t=<j-i} u\_t \bmod{1}$ and $f|\_{(j,j+k)} = 0^{j-i-1}$. If $j<i<j+k$, $k \mid j$, define $f|\_{[j,j+k)}$ in the analogous manner. This construction guarantees that $\sum\_{t=0}^{k-1} f\_{j+t} \equiv 0 \bmod{2}$ for each $j$ with $k \mid j$, so $f|\_{[j,j+k)} \neq w$ for each $(j,w) \in B$.


Since the set $\mathscr{T} = \{ \mathcal{F}\_B \ : \ B \in \mathscr{B}\}$ is $k$-separated, we have the bound:
$$
|\mathscr{T}\_{n,k}| \geq |\mathscr{B}| \simeq 2^{n 2^{k-1}/k}.
$$ 


At the end of the day, we have the nearly matching lower and upper bounds:
$$ 2^{k} \geq \lim\_{n \to \infty} \log |\mathscr{T}\_{n,k}|/n \geq 2^{k-1}/k = 2^{k - o(k)}.$$


