Upper bound on size of minimal binary coverage code

Computer Science Asked by dohmatob on December 7, 2020

Let $$1 le r le n$$ b e integer(with $$n$$ large) and let $$mathscr X_n$$ be the set set of all $$2^n$$ binary strings of length $$n$$. A binary $$r$$-coverage code is a subset $$S$$ of $$mathscr X_n$$ such that every $$x in mathscr X_n$$ is within Hamming distance $$le r$$ of some $$y in S$$. A minimal $$r$$-coverage code is one for which the cardinality $$|S|$$ is minimal. Let this minimal cardinality be $$N_n(r)$$. Note that we have the trivial bound $$N_n(r) le 2^n$$.

Question. What are good upper-bounds for $$N_n(r)$$ in terms of $$N$$ and $$r$$ ?

So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider $$q$$-ary binary codes of length $$n$$, such that $$n to infty$$ with $$r/n to p in [0,(q-1)/q]$$, then the minimal code size has the following asymptotic limit $$(1/n)log_q N_{n,q}(r) to 1-H_q(p),$$ where $$H_q(p)$$ is the $$q$$-ary entropy of $$p$$. This answers my specific problem which corresponds to $$q=2$$.

Answered by dohmatob on December 7, 2020

Related Questions

How to generate graphs with a Hamiltonian path?

3  Asked on February 21, 2021 by always-newbie

Wifi throughput calculation

1  Asked on February 20, 2021 by copsa

Searching for points near given point in a multidimensional space

1  Asked on February 20, 2021 by saku

Group adjacent sections to create groups with biggest value, value is changing in groups

1  Asked on February 20, 2021 by rossko_dca

Thirty-one game. Prediction of the winner

1  Asked on February 17, 2021 by donvitomarco

Explanation of conventional solutions to the Firing Squad Synchronization problem

0  Asked on February 16, 2021 by von-spotz

If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

1  Asked on February 13, 2021 by aviv-barel

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

5  Asked on February 10, 2021 by gizmo

Complexity of a cutting operation on a list of binary trees

0  Asked on February 10, 2021 by arthur-b

speed of preorder traversal

1  Asked on February 8, 2021 by keith-paton

Mergesort and some claims on comparison

1  Asked on February 7, 2021 by user3661613

Proving the language of non-primes is in NP

1  Asked on February 6, 2021 by builderthebob00

Does writing more data to disk consume more energy than writing less?

0  Asked on February 5, 2021 by pookie

In Strassen’s algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

1  Asked on February 4, 2021 by retsek680

How to find the language of a CFG from Production rules

1  Asked on February 3, 2021 by stark2022

Machine Learning algorithm for predicting a user’s rating on an item?

0  Asked on February 1, 2021 by david-grnberger

Finding the Hamiltonian cycle that uses the least amount of straight lines

0  Asked on January 30, 2021 by tzlil

Can I have 2 free adjacent nodes in the fit algorithm for data management

0  Asked on January 29, 2021 by angelic-demonic

Longest path on a full tree

1  Asked on January 27, 2021 by bm1125