# Sequence design to optimize a combinatorial objective

Given a set $$\cal N$$ of $$N$$ objects, we seek to attribute a code, i.e., a binary sequence, to each of them to achieve the following objective of being capable to select any subset $${\cal S}\subseteq {\cal N}$$ of objects with minimal communication cost. To select a set of objects, we need to broadcast a message containing a set of positions in the binary sequence and their values. All the objects matching the broadcast message are selected. For example, consider a system of $$3$$ objects with codes $$001,000,111$$, respectively. If we want to slect the first two objects, we can broadcast $$\{position=1,value=0\}$$ so that only the first two objects match. My problem is to design a coding scheme of length $$o(N)$$ (ideally $$O(\log N)$$) such that for any subset of target objects, we only need to broadcast an $$O(1)$$-length message to select them.

• There are $2^N$ subsets $S$ of a set of $N$ objects. To select an arbitrary one of these with a constant length message and codes of length $\log N$ seems optimistic to me. Jul 17 at 5:12
• What about allowing ${\cal O}(\log N)$ message length Jul 17 at 5:43

Suppose that there was a code $$\mathcal{E}: \mathcal{N} \rightarrow \{0,1\}^{\omega(1)}$$ that achieved this condition; in particular, we have two types of messages $$p \in \mathcal{P} \subset \{0,1,...d-1\}^c$$ (i.e., positions) and $$v \in \mathcal{V} \subset \{0,1\}^c$$ (i.e., values) such that $$\mathcal{S}(p,v) = \{ x \in \mathcal{N} \ | \ \mathcal{E}(x)_{p_0}=v_0,\dots,\mathcal{E}(x)_{p_{c-1}}=v_{c-1}\}$$ defines the set you want to select for some constant $$c$$. Because the length of $$p$$ must be $$\mathcal{O}(1)$$, we must have $$d = O(1)$$ as well (after some relabeling for the positions that are not used).

In order to achieve this, we must have that the function $$\mathcal{S} : \mathcal{P} \times \mathcal{V} \rightarrow 2^{\mathcal{N}}$$ is bijective and in particular, we must have $$2^{c(1+\log d)} \geq |\mathcal{P} \times \mathcal{V}| \geq |2^{\mathcal{N}} | \geq 2^{\log n}$$ or $$c(1+\log d) = \omega (1),$$ which is a contradiction because we assumed that $$c,d$$ were constants.

If you allow a variable size alphabet for the position messages $$p$$ (or $$d = \omega(1)$$), then the question becomes algorithmically meaningless. Likewise, you may try to doing something clever like instead defining $$\mathcal{P} \subset 2^{\{0,1,...,d-1\}}$$, but a similar proof will again work.

Edit @ Jul 22 2022

Since the original question had an easy answer let us consider the following more difficult generalization of the question.

Suppose we allow the messages $$p,$$ $$v$$, and the encoding $$\mathcal{E}$$ to be longer. Then what is the lower bound on the $$(p,v)$$ messages?

Here is simpler pure information-theoretic proof. Sometimes it is easier to prove something by allowing a more powerful computational model and showing that even with this extra power you can't do better.

Here I will show you that no matter what set of questions you may ask (i.e., the $$p$$ messages can be replaced with arbitrary boolean functions), I will still always need at least $$\Omega(n )$$ many bits.

Theorem Any set of binary sequences that encode the subsets $$\mathcal{S} \subset \mathcal{N}$$ as position/value messages must have a minimum of $$\Omega( n)$$ many bits. Furthermore, this remains true if you replace the $$p$$ messages with arbitrary boolean functions.

(Proof) Suppose that $$d,c$$ is the number of positions/values that are used in a scheme. Consider the following decision tree. The root is labeled $$r_{0,0} := \mathcal{S}$$ and the children of the root are labeled $$r_{1,(p_0,v_0)} := \{ x \in \mathcal{N}\ \mid \ \mathcal{E}(x)_{p_0}=v_0 \}$$ and more generally the children of $$r_{i,(p_i,v_i)}$$ at layer $$i+1$$ are labeled $$r_{i+1,(p_{i+1},v_{i+1})}:= \{ x \in r_{i,(p_i,v_i)} \ | \ \mathcal{E}(x)_{p_{i+1}}=v_{i+1}\}$$. This forms a decision tree in an alphabet with at most $$2d \geq |\{(p_i,v_i) \in [d] \times  \mid (p_i,v_i) \in (p,v) \in \mathcal{P} \times \mathcal{V}\}|$$ many branches at any node. A classical information-theoretic argument (see Cover and Thomas) gives us that any such decision tree that can partition the power set must have at least $$\Omega(2^n)=\Omega(|2^\mathcal{N}|)$$ many nodes and thus at least $$c = \log_{2d}(2^n)$$ depth. However, the position messages $$p$$ require at least $$\Omega(\log(d))$$ amount of bits to encode. Thus the maximum message length, $$l = \max\{|(p,v)|\ \mid \ (p,v) \in \mathcal{P} \times \mathcal{V} \}$$, satisfies $$l = \Omega(c\log(d)) = \Omega(\log_{2d}(2^n)\log(d)) = \Omega(n).$$ QED

• thank you pedro for your proof, which I appreciate. If I seek say a coding scheme of length polylog(N) and O(log n) length message or even $O(n^a)$ length with $a<1$, can we design such codes? Jul 21 at 10:14
• Hey Ichen, thanks for the positive feedback! It is funny that you ask because I was going to add a comment about this but I didn't want to make the answer too long. If you notice in the proof I said that $\mathcal{E}: \mathcal{N} \rightarrow \{0,1\}^{\omega(1)}$ so that the proof actually does not depend on the length of the coding scheme! This surprised me while I was working on it. In particular, the contradiction inequality is $2^{c(1+\log d)} \geq |\mathcal{P} \times \mathcal{V}| \geq |2^{\mathcal{N}} | \geq 2^{\log n}$ which does not depend on the length of the coding scheme! Cool huh? Jul 21 at 14:35
• @Ichen I believe I answered your more general question. You will always need $\omega(n)$ many bits for any scheme. Please take a look at the edited answer. Best wishes! Jul 22 at 23:58
• @Ichen I actually realized that the proof proves something far stronger; you can replace the $p$ messages with any boolean functions $p'$ and the proof still works. It is an information-theoretic lower bound that follows directly from combinatorics/counting nodes on a decision tree. Best of luck! Jul 23 at 15:44