- Split View
-
Views
-
Cite
Cite
Lin Zhu, Wen Ming Li, Liang Feng Zhang, On the Modulus in Matching Vector Codes, The Computer Journal, Volume 65, Issue 12, December 2022, Pages 2991–2997, https://doi.org/10.1093/comjnl/bxab121
- Share Icon Share
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^{\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 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^{\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 infinitely many new good numbers.
1 Introduction
Classical error-correcting codes allow one to encode any |$n$|-bit message |$x$| as an |$N$|-bit codeword |$C(x)$| such that |$x$| can still be recovered, even if a constant fraction of |$C(x)$| has been corrupted. The disadvantage of such codes is that one has to read all or most of the codeword to recover any information about |$x$|. As a better solution for decoding particular bits of the message, a |$(k,\delta ,\epsilon )$|-locally decodable code (LDC) [1] encodes any |$n$|-bit message |$x$| to an |$N$|-bit codeword, such that any message bit |$x_i$| can be recovered with probability |$\geq 1-\epsilon $|, by a randomized decoding procedure that makes at most |$k$| queries, even if |$\delta N$| bits of |$C(x)$| have been corrupted. Such codes have interesting applications [2, 3] in cryptography and complexity theory. For an efficient LDC, both the code length |$N$| and the query complexity |$k$| should be as small as possible, as functions of |$n$|.
Following [1, 4, 5], Gasarch [2] and Goldreich et al. [4] conjectured that for any constant |$k$|, the length |$N$| of a |$k$|-query LDC should be |$\exp (n^{\Omega (1)})$|. Yekhanin [6] disproved this conjecture with a three-query LDC of length |$\exp (\exp (O(\log n/\log \log n)))$|, assuming that there are infinitely many Mersenne primes. For any |$r\geq 2$|, Efremenko [7] provided a construction of |$2^r$|-query LDCs of length |$N_r=\exp (\exp (O((\log n)^{1-1/r} (\log \log n)^{1/r})))$| under no assumptions, and in particular a three-query LDC when |$r=2$|. Such codes have been reformulated and called matching vector codes (MVCs) in [8].
The MVCs in [7] are based on two ingredients: |$S$|-matching family and |$S$|-decoding polynomial. For |$r\geq 2$|, let |$\mathcal{M}_r$| be the set of integers of the form |$m=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_r^{\alpha _r}$|, where |$p_1,p_2,\ldots ,p_r>2$| are distinct primes and |$\alpha _1,\alpha _2,\ldots ,\alpha _r>0$|. The existence of both ingredients in MVCs depends on a modulus |$m \in{\cal M}_r$|. In particular, the query complexity |$k$| of the MVC is equal to the number of monomials in the |$S$|-decoding polynomial and is at most |$2^r$| for all |$m\in{\cal M}_r$|. A number |$m\in{\cal M}_r$| has been called good if an |$S$|-decoding polynomial with |$k<2^r$| monomials exists when |$m$| is used to construct MVC. For example, the three-query LDC of [7] was constructed with the good number |$m=7\times 73$|. Itoh and Suzuki [9] showed that one can reduce the query complexity of MVCs via a composition theorem. In particular, by using the good numbers 511 and 2047, they were able to obtain |$9\cdot 2^{r-4}$|-query LDC of length |$N_r$| for all |$r>5 $|. Chee et al. [10] showed that if there exist primes |$t,p_1,p_2$| such that |$m=2^t-1=p_1p_2$|, then |$m$| must be good. They determined 50 new good numbers of the above form and then significantly reduced the query complexity of MVCs.
Since [7, 9, 10], the work of finding good numbers has become interesting. However, the study of [7, 9, 10] was limited to good numbers of the form |$m=p_1p_2\in{\cal M}_2$|. When |$\max \{\alpha _1,\alpha _2\}>1$|, it is not known how to decide a number of the form |$m=p_1^{\alpha _1}p_2^{\alpha _2}\in{\cal M}_2$| is good except using the very expensive computer search. In this paper, we shall provide two methods for obtaining new good numbers in |${\cal M}_2$|:
If |$m_1=p_1^{\alpha _1}p_2^{\alpha _2}\in{\cal M}_2$| is good and |$m_2 =p_1^{\beta _1}p_2^{\beta _2}\in{\cal M}_2$| is a multiple of |$m_1$|, then |$m_2$| must be good as well.
If |$m_2=p_1^{\beta _1}p_2^{\beta _2}\in{\cal M}_2$| is good, and there is an |$S$|-decoding polynomial of the form |$P(X)=X^u+aX^v+b$| for |$m_2$| such that |$\gcd (u,v,m_2)=p_1^{\omega _1}p_2^{\omega _2}$|, then |$m_1=m_2/(p_1^{\omega _1}p_2^{\omega _2})$| must be good as well.
2 Preliminaries
We denote by |$\mathbb{Z}$| and |$\mathbb{Z}^+$| the set of integers and positive integers, respectively. For any |$n\in \mathbb{Z}^+$|, we denote |$[n]=\{1,2,\ldots ,n\}$|. For any |$m\in \mathbb{Z}^+$|, we denote by |$\mathbb{Z}_m$| the set of integers modulo |$m$| and denote by |$\mathbb{Z}_m^*$| the multiplicative group of integers modulo |$m$|. When |$m$| is odd, we have that |$2\in \mathbb{Z}_m^*$| and denote by |${\textrm{ord}}_m(2)$| the multiplicative order of |$2$| in |$\mathbb{Z}_m^*$|. For a prime power |$q$|, we denote by |$\mathbb{F}_q$| the finite field of |$q$| elements and denote by |$\mathbb{F}_q^*$| the multiplicative group of |$\mathbb{F}_q$|. For any |$z\in \mathbb{F}_q^*$|, we denote by |${\textrm{ord}}_q(z)$| the multiplicative order of |$z$|. For any two vectors |$x=(x_1,\ldots ,x_n),y=(y_1,\ldots ,y_n)$|, we denote by |$d_H(x,y)=\{i: i\in [n], x_i\neq y_i\}$| the Hamming distance between |$x$| and |$y$|. For any |$x,y\in \mathbb{Z}_m^h$|, we denote by |$\langle x,y \rangle _m=\sum _{i=1}^n x_iy_i \bmod m$| the dot product of |$x$| and |$y$|. If the components of a vector |$y$| are labeled by a set |$V$|, then for every |$v\in V$| we denote by |$y[v]$| the |$v$|th component of |$y$|.
(locally decodable code) Let |$k,n,N\in \mathbb{Z}^+$| and let |$0\leq \delta ,\epsilon \leq 1$|. A code |$C:\mathbb{F}_q^n\longrightarrow \mathbb{F}_q^N$| is said to be |$(k, \delta , \varepsilon )$|-locally decodable if there exist randomized decoding algorithms |$D_1,D_2,\ldots ,D_n$| such that:
For any |$x\in \mathbb{F}_q^n$|, any |$y\in \mathbb{F}_q^N$| such that |$d_H(C(x),y)\leq \delta N$| and any |$i\in [n]$|, |$\Pr [D_i(y)=x_i]\geq 1-\epsilon $|.
The algorithm |$D_i$| makes at most |$k$| queries to |$y$|.
The numbers |$k$| and |$N$| are called the query complexity and the length of |$C$|, respectively. They are usually considered as functions of |$n$|, the message length, and measure the efficiency of |$C$|. Ideally, we would like |$k$| and |$N$| to be as small as possible.
Efremenko [7] proposed a construction of LDCs, which is based on two fundamental building blocks: |$S$|-matching family and |$S$|-decoding polynomial.
(|$S$|-matching family) Let |$m,h,n\in \mathbb{Z}^+$| and let |$S\subseteq \mathbb{Z}_m\setminus \{0\}$|. A set |${\cal U}=\{u_i\}_{i=1}^{n}\subseteq \mathbb{Z}_m^h$| is said to be an |$S$|-matching family if
|$\langle u_i,u_i\rangle _m =0$| for every |$i\in [n]$|,
|$\langle u_i,u_j\rangle _m \in S$| for all |$i,j\in [n]$| such that |$i\neq j$|.
(|$S$|-decoding polynomial) Let |$m\in \mathbb{Z}^+$| be odd. Let |$t={\textrm{ord}}_m(2)$| and let |$\gamma \in \mathbb{F}_{2^t}^*$| be a primitive |$m$|th root of unity. A polynomial |$P(X)\in \mathbb{F}_{2^t}[X]$| is said to be an |$S$|-decoding polynomial if
|$P(\gamma ^s)=0$| for every |$s\in S$|,
|$P(\gamma ^0)=1$|.
Given an |$S$|-matching family |${\cal U}=\{u_i\}_{i=1}^n \subseteq \mathbb{Z}_m^h$| and an |$S$|-decoding polynomial |$P(X)=a_0+a_1X^{b_1}+\cdots + a_{k-1} X^{b_{k-1}}\in \mathbb{F}_{2^t}[X]$|, Efremenko’s LDC can be described in Figure 1.
([7, 11]) For any |$m\in{\cal M}_r (r\geq 2)$| and integer |$h>0$|, there is an |$S_m$|-matching family |${\cal U}=\{u_i\}_{i=1}^{n}\subseteq \mathbb{Z}_m^h$| of size |$n\geq \exp (c(\log h)^r/(\log \log h)^{r-1})$|, where |$c$| is a constant that only depends on |$m$|.
In particular, the |$n$| takes the form of |$\ell ^\ell $| for an integer |$\ell>0$| and |$h$| is determined by both |$m$|, |$\ell $|, and the weak representation of the function |${\textsf{OR}}_\ell $| [11]. Efremenko [7] also observed that the polynomial |$P(X)= \prod _{s\in S_m} (X-\gamma ^s)/(1-\gamma ^s)$| is an |$S_m$|-decoding polynomial with |$k\leq 2^r$| monomials.
([7]) For any |$m\in{\cal M}_r (r\geq 2)$|, there is an |$S_m$|-decoding polynomial with at most |$ 2^r$| monomials.
Lemmas 2.1 and 2.2 yield LDCs of subexponential length.
([7]) For every integer |$r\geq 2$|, there is a |$(k,\delta ,k\delta )$|-LDC of query complexity |$k\leq 2^r$| and length |$N_r$|.
For every integer |$r\geq 2$|, Theorem 2.1 gives an infinite family of LDCs, each based on a number |$m\in{\cal M}_r$|. Different |$m\in{\cal M}_r$| may give LDCs of different query complexity. For example, |$m=7\times 73$| gives a code of query complexity 3 [7], while |$m=3\times 5$| is only able to give a code of query complexity 4 [9]. A number of the form |$m=p_1p_2$| has been called good in [9, 10] if it is able to result in an LDC of query complexity |$<4$|. By using the good numbers 511 and 2047, Itoh and Suzuki [9] concluded that for any |$r>5$|, the query complexity |$2^r$| of the LDCs in Theorem 2.1 can be reduced to |$9\cdot 2^{r-4} $|. On the other hand, for |$r=2,3,4$| and |$5$|, the best decoding algorithms to date for the LDCs in Theorem 2.1 have query complexity 3, 8, 9 and 24, respectively. Chee et al. [10] showed that Mersenne numbers of the form |$p_1p_2$| are good. With infinitely many such good numbers, Chee et al. [10] can further reduce the query complexity to |$3^{r/2}$|.
3 Good Numbers of the Form |${p}_1^{\alpha _1} {p}_2^{\alpha _2}$|
Let |$m= p_1^{\alpha _1}p_2^{\alpha _2}\in \mathcal{M}_2$|. Let |$t={\textrm{ord}}_m(2)$| and let |$\gamma \in \mathbb{F}_{2^t}^*$| be a primitive |$m{\textrm{th}}$| root of unity. Lemma 2.2 shows that there is an |$S_m$|-decoding polynomial |$P(X)$| with |$k\leq 4$| monomials. In this section, we will establish several sufficient and necessary conditions for a number |$m$| to be good.
Let |$m= p_1^{\alpha _1}p_2^{\alpha _2}\in{\cal M}_2$|. Then any |$S_m$|-decoding polynomial has |$\geq 3$| monomials.
Let |$\mathbb{M}_2$| be the set of good numbers in |${\cal M}_2$|. The following lemmas characterize |$\mathbb{M}_2$|.
Let |$m=p_1^{\alpha _1} p_2^{\alpha _2}\in{\cal M}_2$|. Then |$m\in \mathbb{M}_2$| if and only if there is a polynomial |$Q(X)=X^u+aX^v+b \in \mathbb{F}_{2^t}[X]$| that satisfies the following properties
① |$ab\neq 0, $|
② |$|\{(u\bmod ~m), (v\bmod ~m),0\}|=3$|, and
③ |$Q(\gamma )=Q(\gamma ^{s_{01}}) = Q(\gamma ^{s_{10}})=0$|, |$Q(1) \neq 0$|.
④ |$c_1c_2c_3\neq 0$|,
⑤ |$|\{(d_1 \bmod ~m), (d_2~\bmod ~m),(d_3~\bmod ~m)\}|=3$|, and
⑥ |$P(\gamma ^{s_{01}})=P(\gamma ^{s_{10}})=P(\gamma )=0, P(1)=1$|.
Conversely, suppose that |$Q(X)=X^u+aX^v+b$| is a polynomial that satisfies the properties ①, ② and ③. Then |$P(X)=Q(X)/Q(1)$| will be an |$S_m$|-decoding polynomial with exactly three monomials. Therefore, |$m\in \mathbb{M}_2$|.
Let |$\rho (z_1,z_2)=\tau (z_1,z_2)-1= (1+z_2^{-1})(1+z_1^{-1})^{-1}.$| Then Lemma 3.4 gives the following theorem.
Let |$m=p_1^{\alpha _1} p_2^{\alpha _2}\in{\cal M}_2$|. Let |$t={\textrm{ord}}_m(2)$| and let |$\gamma \in \mathbb{F}_{2^t}^*$| be a primitive |$m{\textrm{th}}$| root of unity. Then |$m \in \mathbb{M}_2$| if and only if |$\rho $| is not injective on |$\cal D$|.
Theorem 3.1 gives a characterization of the good numbers in |${\cal M}_2$|. We say that |$(u,v)\in E^2$| form a collision for |$m$| if
|$\rho (\gamma ^{s_{10}u},\gamma ^{s_{01}u})=\rho (\gamma ^{s_{10}v},\gamma ^{s_{01}v})$|, and
|$u\not \equiv v(\bmod ~m)$|.
The proof of Lemma 3.4 shows that |$m\in \mathbb{M}_2$| if and only if there is a collision |$(u, v)\in E^2$| for |$m$|.
4 Implications between Good Numbers
In this section, we show the implications between good numbers in |${\cal M}_2$|, which allows us to construct new good numbers from old.
Let |$m_1=p_1^{\alpha _1} p_2^{\alpha _2}, m_2=p_1^{\beta _1} p_2^{\beta _2} \in{\cal M}_2$|. Let |$t_i={\textrm{ord}}_{m_i}(2)$| and let |$\gamma _i \in \mathbb{F}_{2^{t_i}}^*$| be a primitive |$m_i{\textrm{th}}$| root of unity for |$i=1,2$|. If |$m_1|m_2$|, then there is an integer |$\sigma \in \mathbb{Z}_{m_1}^*$| such that |$\gamma _1=\gamma _2^{\sigma m_2/m_1}$|.
As |$m_1|m_2$| and |$m_2|(2^{t_2}-1)$|, we must have that |$t_1|t_2$|. Then |$\mathbb{F}_{2^{t_1}}$| is a subfield of |$\mathbb{F}_{2^{t_2}}$|. Note that |$\gamma _1\in \mathbb{F}_{2^{t_1}}\subseteq \mathbb{F}_{2^{t_2}}$| and |$\gamma _2^{m_2/m_1} \in \mathbb{F}_{2^{t_2}}$| are elements of the same finite field and have the same multiplicative order (i.e. |$m_1$|). Both |$\langle \gamma _1\rangle $| and |$\langle \gamma _2^{m_2/m_1}\rangle $| are subgroups of |$\mathbb{F}_{2^{t_2}}^*$| of order |$m_1$|. As |$\mathbb{F}_{2^{t_2}}^*$| has a unique subgroup of order |$m_1$|, it must be the case that |$\langle \gamma _1\rangle =\langle \gamma _2^{m_2/m_1}\rangle $|. Hence, there is an integer |$\sigma \in \mathbb{Z}_{m_1}^*$| such that |$ \gamma _1=\gamma _2^{\sigma m_2/m_1}$|.
Let |$m_1=p_1^{\alpha _1} p_2^{\alpha _2}, m_2=p_1^{\beta _1} p_2^{\beta _2}\in{\cal M}_2$|. If |$m_1\in \mathbb{M}_2$| and |$m_1|m_2$|, then |$m_2\in \mathbb{M}_2$|.
For |$i\in \{1,2\}$|, let |$S_{m_i}=\{s^i_{01},s^i_{10}, 1 \}$|, let |$t_i={\textrm{ord}}_{m_i}(2)$|, and let |$\gamma _i \in \mathbb{F}_{2^{t_i}}^*$| be of order |$m_i$|. Let |$E_1=\{e:p_1^{\alpha _1}\nmid e, p_2^{\alpha _2}\nmid e, e\in \mathbb{Z}\}$| and |$ E_2=\{e:p_1^{\beta _1}\nmid e, p_2^{\beta _2}\nmid e, e\in \mathbb{Z}\}$|.
Let |$m_2=p_1^{\beta _1} p_2^{\beta _2}\in{\cal M}_2$|. Suppose that |$m_2\in \mathbb{M}_2$| and |$(u,v)=(p_1^{i_1}p_2^{i_2}\sigma _1, p_1^{j_1}p_2^{j_2}\sigma _2)$| is a collision for |$m_2$|, where |$\sigma _1,\sigma _2\in \mathbb{Z}_{m_2}^*$|. Let |$\omega _1=\min \{i_1,j_1\}$| and |$\omega _2=\min \{i_2, j_2\}$|. Then |$m_1:=m_2/(p_1^{\omega _1}p_2^{\omega _2})$| belongs to |$\mathbb{M}_2$|.
Let |$m_2 = 7^2\times 151$|. Then |$S_{m_2}=\{s_{01}=1813,s_{10}=5587,s_{11}=1\}$|. Let |$t_2={\textrm{ord}}_{m_2}(2)$| and let |$\gamma _2 \in \mathbb{F}_{2^{t_2}}^*$| be a primitive |$m_2{\textrm{th}}$| root of unity. Then |$(238, 455)$| is a collision for |$m_2$|. Clearly, |$\omega _1=1$| and |$\omega _2=0$|. Then |$m_1=m_2/7=1057$| must be a good number, which is |$<m_2$|.
5 Conclusion
In this paper, we characterized the good numbers in |${\cal M}_2$| and showed two implications between good numbers in |${\cal M}_2$|. In particular, the second implication requires an additional condition. It is an interesting problem to remove the condition.
DATA AVAILABILITY STATEMENT
No new data were generated or analysed in support of this research.
ACKNOWLEDGEMENTS
The authors would like to thank the anonymous reviewers for their helpful suggestions.
FUNDING
Natural Science Foundation of Shanghai (21ZR1443000); Singapore Ministry of Education (RG12/19).
References