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)$ have been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{ \alpha_1}p_2^{ \alpha_2}\cdots p_r^{ \alpha_r}$ may result in an MVC with $k\leq 2^r$ and $N=\exp(\exp(O((\log n)^{ 1-1/r} (\log\log n)^{ 1/r})))$. The $m$ is { \em good} if it is possible to have $k<2^r$. The good numbers yield more efficient MVCs. Prior to this work, there are only { \em 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^{ \alpha_1}p_2^{ \alpha_2}$. We show that if $m=p_1^{ \alpha_1}p_2^{ \alpha_2}$ is good, then any multiple of $m$ of the form $p_1^{ \beta_1}p_2^{ \beta_2}$ must be good as well. Given a good number $m=p_1^{ \alpha_1}p_2^{ \alpha_2}$, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields { \em infinitely many} new good numbers.
Categories: cs.IT cs.CR math.IT