Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Now I have the additional constraint that each column must contain at most p bits set to 1. For instance for p=2 (and n=8), a possible solution is:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Given n and p, does an algorithm exist to find an optimal encoding (shortest length) ? (and can it be proved that it computes an optimal solution?)


Two approaches have been proposed so far to estimate a lower bound on the number of bits $m$. The goal of this section is to provide an analysis and a comparaison of the two answers, in order to explain the choice for the best answer.

Yuval's approach is based on entropy and provides a very nice lower bound: $\frac{logn}{h(p/n)}$ where $h(x) = xlogx + (1-x)log(x)$.

Alex's approach is based on combinatorics. If we develop his reasonning a bit more, it is also possible to compute a very good lower bound:

Given $m$ the number of bits $\geq\lceil log_2(n)\rceil$, there exists a unique $k$ such that $$ 1+\binom{m}{1} + ... +\binom{m}{k} \lt n \leq 1+\binom{m}{1} + ... + \binom{m}{k}+\binom{m}{k+1}$$ One can convince himself that an optimal solution will use the codeword with all bits low, then the codewords with 1 bit high, 2 bits high, ..., k bits high. For the $n-1-\binom{m}{1}-...-\binom{m}{k}$ remaining symbols to encode, it is not clear at all which codewords it is optimal to use but, for sure the weights $w_i$ of each column will be bigger than they would be if we could use only codewords with $k+1$ bits high and have $|w_i - w_j| \leq 1$ for all $i, j$. Therefore one can lower bound $p=max(w_i)$ with $$p_m = 0 + 1 + \binom{m-1}{2} +... + \binom{m-1}{k-1} + \lceil \frac{(n-1-\binom{m}{1}-...-\binom{m}{k}) (k+1)}{m} \rceil$$

Now, given $n$ and $p$, try to estimate $m$. We know that $p_m \leq p$ so if $p \lt p_{m'}$, then $m' \lt m$. This gives the lower bound for $m$. First compute the $p_m$ then find the biggest $m'$ such that $p \lt p_{m'}$

This is what we obtain if we plot, for $n=1000$, the two lower bounds together, the lower bound based on entropy in green, the one based on the combinatorics reasonning above in blue, we get:enter image description here

Both look very similar. However if we plot the difference between the two lower bounds, it is clear that the lower bound based on combinatorics reasonning is better overall, especially for small values of $p$.

enter image description here

I believe that the problem comes from the fact that the inequality $H(X) \leq \sum H(X_i)$ is weaker when $p$ gets smaller, because the individual coordinates become correlated with small $p$. However this is still a very good lower bound when $p=\Omega(n)$.

Here is the script (python3) that was used to compute the lower bounds:

from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m 
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)


  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  • 1
    $\begingroup$ @D.W. the constraint is quite as your states. each column must contain at most p bits set to 1. ie. the bit 1's at each position of all selected keys do not exceed p. But I think the first step is still counting the capacity of each bit width. $\endgroup$ – Terence Hang Sep 2 '15 at 16:52
  • $\begingroup$ user3017842, I suspect your latest edit should be posted as a self-answer. I think it stands alone as an answer to your question. Do you agree? If so, the right place for it is in the answer box, rather than in the question -- that will make a lot more sense for future readers who come across this (and also allows the community to vote on your answer). I appreciate that you're sharing the analysis you did -- thank you. I encourage you to post that material as an answer, and then remove it from the question. What do you think? Does that seem like it makes sense to you? $\endgroup$ – D.W. Sep 5 '15 at 3:15
  • $\begingroup$ @D.W. The EDIT section only makes a comparaison between the two proposed answers in order to explain the choice for the best answer. Therefore I didn't want to put it as a self-answer. But I completely agree that it lacks of clarity for future users, therefore I've clarified the goal of the section and provided links to the corresponding answers. I believe it is a bit more clear now. $\endgroup$ – user3017842 Sep 6 '15 at 9:05

There is an additional lower bound we can build, that will address cases like what @user3017842 mentioned in their comment on Yuval's answer. (Cases where $p$ is particularly small.) Suppose we knew $m$ already: Then we have $pm$ bits high total across all codewords. Since we're interested the cases where $p$ is small, we view these high bits as our limiting resource, and want to build a code with it (and see how many codewords we can possibly get out). We can have 1 codeword with all 0s, then $m$ codewords with a single 1, then $m \choose 2$ with two 1s, etc. If we call the highest number of bits in a codeword $k$, then $$pm = 0\cdot 1 + 1\cdot m + 2\cdot {m \choose 2}+... \le \sum_i^k i{m \choose i}$$ While our number of codewords $n$ is similarly bounded by $$n \le \sum_i^k {m \choose i}$$ If we look at the case where $p \le m$, then $k \le 2$ is already implied by the first inequality. ($pm = m^2 = m + 2{m \choose 2}$). So then the code would consist of the $0$-word, $m$ single-$1$-words, and $(p-1)m/2$ two-$1$-words. Thus $$ n \le 1 + m + (p-1)m/2 $$ or inverting $$ m \ge \frac{2(n-1)}{p+1} .$$ This will yield the tight lower bound of $m\ge 5$ on the example you provide, but as mentioned before, will probably only be very useful while $p \approx m$ (or $p \approx \sqrt n$).

  • 1
    $\begingroup$ Please see the EDIT section of the main post to see why your answer wins ! $\endgroup$ – user3017842 Sep 4 '15 at 18:06

Here is a lower bound and an asymptotically matching construction, at least for some ranges of the parameters. Denote by $m$ the number of columns, and suppose for simplicity that $p \leq n/2$.

We start with a lower bound on $m$. Let $X$ be the encoding of symbol chosen uniformly at random. Let $X_1,\ldots,X_m$ be the individual coordinates, and let $w_i \leq p$ be the weight of the $i$th column. Then $$ \log n = H(X) \leq \sum_{i=1}^m H(X_i) = \sum_{i=1}^m h(w_i/n) \leq m h(p/n). $$ Therefore $$ m \geq \frac{\log n}{h(p/n)}. $$ Here $H$ is the entropy of a random variable $H(X) = -\sum_x \Pr[X=x] \log \Pr[X=x]$ and $h$ is the entropy function $h(x) = -x\log x-(1-x)\log(1-x)$. (You can use whatever base for the logarithm you want.)

The asymptotically matching construction, that should work for $p = \Omega(n)$, chooses $m$ a bit larger than this lower bound, and chooses a random encoding scheme, each bit being set to $1$ with some probability $q/n$ which is a bit smaller than $p/n$. Choosing the parameters correctly, we should get that this results in a legal encoding (all codewords are different and all column weights are at most $p$) with positive probability.

  • $\begingroup$ Nice lower bound. Why should the matching construction work for $p=\Omega(n)$? is there any easy way to believe it other than bounding the probability of getting an invalid encoding when $m$ is picked near the lower bound? $\endgroup$ – Ariel Sep 3 '15 at 15:46
  • $\begingroup$ Experience tells me that it has a high chance of working, but you can't know for sure without trying. $\endgroup$ – Yuval Filmus Sep 3 '15 at 16:27
  • $\begingroup$ I believe this lower bound is very good when the individual coordinates $X_1, X_2, ..., X_m$ are virtually independent (because inequality $H(X) \leq \sum H(X_i)$ will be close to be an equality). This is likely to be the case when $p$ is close enough to $n/2$. However when $p$ remains small, this is no more the case. Consider for example the extreme case when $p=1$. $\endgroup$ – user3017842 Sep 3 '15 at 17:42
  • 1
    $\begingroup$ When $p=1$ it is clear that the number of bits is $n-1$ (as suggested in Alex Meiburg's answer). However $n-1 - \frac{logn} {h(p/n))} \sim n/logn$. The lower bound becomes inaccurate when $p$ remains small while $n$ is getting large. Besides, for small $p$ such as $p=1$, the proposed construction will not work quite well because of the well-known birthday problem. But, still, this is a very nice approach, especially when $p=\Omega(n)$ ! $\endgroup$ – user3017842 Sep 3 '15 at 18:05
  • $\begingroup$ I've made a comparaison with another lower bound deduced from combinatorics reasonning suggested in another answer. It turns out that your lower bound is slightly weaker, especially when $p$ gets smaller. Please see the details of the comparaison in the EDIT section of the main post. Nonetheless, I was very impressed by your solution! Thanks ! $\endgroup$ – user3017842 Sep 4 '15 at 18:05

Here is a simple search methodology. We start from some lower-bound on the number of bits and then try to find a legal encoding. Specifically.

Let m be the current number of bits. Encode symbol i as bi1, bi2, ..., bim.

Constraints: bi xor bj isn't 0 - in other words each symbol's encoding is unique

For all j: sum_i bij <= p.

This is a pseudo-boolean satisfiability problem (well it can easily be encoded as a standard satifiability problem). So just keep increasing m until you find one that is satisfiable (or do a binary search using lower and upper bounds to find the minimal m).

Of course, this doesn't guarantee that in practice you'll be able to actually find the minimal m, the SAT check could timeout.


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.