Upper bounds for binary identifying codes

A nonempty set of words in a binary Hamming space Fn is called an r-identifying code if for every word the set of codewords within distance r from it is unique and nonempty. The smallest possible cardinality of an r-identifying code is denoted by Mr(n). In this paper, we consider questions closely related to the open problem whether Mt+r(n+m)⩽Mt(m)Mr(n) is true. For example, we show results like M1+r(n+m)⩽4M1(m)Mr(n), which improve previously known bounds. We also consider codes which identify sets of words of size at most ℓ. The smallest cardinality of such a code is denoted by . We prove that is true for all ℓ⩾r+3 when r⩾1 and t=1. We also obtain a result M1(n+1)⩽(2+εn)M1(n) where εn→0 when n→∞. This bound is related to the conjecture M1(n+1)⩽2M1(n). Moreover, we give constructions for the best known 1-identifying codes of certain lengths.