# Size of a family of sets of $k$-separated functions over $\{0,1,\ldots,n-1\}$

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.$$

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= and $$f|_{(j,j+k)} = 0^{j-i-1}$$. If $$j, $$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)}.$$