On the Modulus in Matching Vector Codes. (22nd September 2021) - Zhu, Lin; Li, Wen Ming; Zhang, Liang Feng
Abstract: A k -query locally decodable code (LDC) C allows one to encode any n -symbol message x as a codeword C(x) of N symbols such that each symbol of x can be recovered by looking at k symbols of C(x), even if a constant fraction of C(x) has been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus m=p_1^α _1p_2^α _2… p_r^α _r may result in an MVC with k≤ 2^r and N=((O((n)^1-1/r (n)^1/r))) . The m is good if it is possible to have k<2^r . The good numbers yield more efficient MVCs. Prior to this work, there are only finitely many good numbers. All of them were obtained via computer search and have the form m=p_1p_2 . In this paper, we study good numbers of the form m=p_1^α _1p_2^α _2 . We show that if m=p_1^α _1p_2^α _2 is good, then any multiple of m of the form p_1^β _1p_2^β _2 must be good as well. Given a good number m=p_1^α _1p_2^α _2, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields infinitely many new good numbers.