Non-Monotonicity of Optimal Identifying Code Size in Hypercubes (with Rigorous Certificates for r=2 and Explicit Counterexamples for r > n/2)
Identifying codes, introduced by Karpovsky–Chakrabarty–Levitin, are useful for fault localization in networks. In the binary Hamming space (hypercube) Q_n, let M_r(n) denote the minimum size of an r-identifying code. A natural open question asks: for fixed radius r, is M_r(n) monotonically non-decreasing in the dimension n? While monotonicity is known to hold for r=1 (Moncel), the case r>1 remained open. We provide two fully explicit counterexamples: (1) The classical r=2 counterexample M_2(3)=7 > 6=M_2(4), where we construct a 6-element code and prove no 5-element code exists, forming a rigorous certificate; (2) A stronger result showing that even under the constraint r > n/2, monotonicity can fail: M_3(4)=15 while M_3(5) ≤ 10, hence M_3(5) < M_3(4). These phenomena demonstrate that optimal identifying code sizes can exhibit sudden drops at boundary regimes (e.g., n = r+1).