Key Takeaway: This paper presents a new method for determining the minimum size of a set W Vkn such that for each x in Vkn, there is an element in W that differs from x in at most one coordinate, and obtains (7, 3) 216.

Abstract

Abstract The set Vkn of all n-tuples (x1, x2,…, xn) with xi ϵ, Z k is considered. The problem treated in this paper is determining σ(n, k), the minimum size of a set W ⊆ Vkn such that for each x in Vkn, there is an element in W that differs from x in at most one coordinate. By using a new constructive method, it is shown that σ(n, p) ⩽ (p − t + 1)pn−r, where p is a prime and n = 1 + t(p r−1 − 1) (p − 1) for some integers t and r. The same method also gives σ(7, 3) ⩽ 216. Another construction gives the inequality σ(n, kt) ⩽ σ(n, k)tn−1 which implies that σ(q + 1, qt) = qq−1tq when q is a prime power. By proving another inequality σ(np + 1, p) ⩾ σ(n, p)pn(p−1), σ(10, 3) ⩽ 5 · 36 and σ(16, 5) ⩽ 13 · 512 are obtained.