# On the Modulus in Matching Vector Codes. (arXiv:2107.09830v1 [cs.IT])

Jul 22, 2021

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
\$kleq 2^r\$ and \$N=exp(exp(O((log n)^{1-1/r} (loglog 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.