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.
 A: 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 [2]  \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
