Skip to main content
added 308 characters in body
Source Link

If a vector has $d$ zeroone-entries, and $d\leq n/2$, then delete as many ones as you can,    (and further zeros if necessary).
Conversely Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ zeroesones. The number of such vectors with exactly $n/6$ zerosones in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

IfEdit: In view of Yuri's comment, I am not mistakencorrect this: (Thank you, thenYuri!)

As $H(1/4)$ is about $0.811$
 , givingthis is about $2^{n/6 \times 0.811...+o(1)}=2^{0.1352\ldots n}$, which$2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.

This upper bound is considerably smallercertainly weaker than   the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.

Some backgroundexplanation why this worksthe method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities drastically. In other words the tail of this distibution is small.

If a vector has $d$ zero-entries, and $d\leq n/2$, then delete as many ones as you can,  (and further zeros if necessary).
Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ zeroes. The number of such vectors with exactly $n/6$ zeros in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

If I am not mistaken, then $H(1/4)$ is about $0.811$
  giving about $2^{n/6 \times 0.811...+o(1)}=2^{0.1352\ldots n}$, which is considerably smaller than  $2^{n/3}$.

Some background why this works: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities drastically. In other words the tail of this distibution is small.

If a vector has $d$ one-entries, and $d\leq n/2$, then delete as many ones as you can,  (and further zeros if necessary). Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ ones. The number of such vectors with exactly $n/6$ ones in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

Edit: In view of Yuri's comment, I correct this: (Thank you, Yuri!)

As $H(1/4)$ is about $0.811$, this is about $2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.

This upper bound is certainly weaker than the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.

Some explanation why the method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities. In other words the tail of this distibution is small.

Source Link

If a vector has $d$ zero-entries, and $d\leq n/2$, then delete as many ones as you can, (and further zeros if necessary).
Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ zeroes. The number of such vectors with exactly $n/6$ zeros in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

If I am not mistaken, then $H(1/4)$ is about $0.811$
giving about $2^{n/6 \times 0.811...+o(1)}=2^{0.1352\ldots n}$, which is considerably smaller than $2^{n/3}$.

Some background why this works: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities drastically. In other words the tail of this distibution is small.