5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.