A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\cU = (\vec{u}_1, \cdots, \vec{u}_K)$ and $\cV = (\vec{v}_1, \cdots, \vec{v}_K)$ where $\vec{u}_i, \vec{v}_j \in \Z_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \vec{u}_i, \vec{v}_i \rangle =0 \pmod{m}$, and for any $i \ne j$, $\langle \vec{u}_i, \vec{v}_j \rangle \ne 0 \pmod{m}$. An $\mathbf{MV}$ family is called $r$-restricted if inner products $\langle u_i, v_j\rangle$, for all $i,j$, take at most $r$ different values. The $r$-restricted $\mathbf{MV}$ families are extremely important since the only known construction of constant-query subexponential locally decodable codes (LDCs) are based on them. Such LDCs constructed via matching vector families are called matching vector codes. Let $\mathbf{MV}(m,n)$ (respectively $\mathbf{MV}(m, n, r)$) denote the largest $K$ such that there exists an $\mathbf{MV}$ family (respectively $r$-restricted $\mathbf{MV}$ family) of size $K$ in $\Z_m^n$. Such a $\mathbf{MV}$ family can be transformed in a black-box manner to a good $r$-query locally decodable code taking messages of length $K$ to codewords of length $N = m^n$.

For small prime $m$, an almost tight bound $\mathbf{MV}(m,n) \le O(m^{n/2})$ was first shown by Dvir, Gopalan, Yekhanin (FOCS'10, SICOMP'11), while for general $m$, the same paper established an upper bound of $O(m^{n-1+o_m(1)})$, with $o_m(1)$ denoting a function that goes to zero when $m$ grows. For any arbitrary constant $r \ge 3$ and composite $m$, the best upper bound till date on $\mathbf{MV}(m,n,r)$ is $O(m^{n/2})$, is due to Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14).In a breakthrough work, Alrabiah, Guruswami, Kothari and Manohar (STOC'23) implicitly improve this bound for $3$-restricted families to $\mathbf{MV}(m, n, 3) \leq O(m^{n/3})$.

In this work, we present an upper bound for $r=3$ where $\mathbf{MV}(m,n,3) \le m^{n/6 +O(\log n)}$, and as a result, any $3$-query matching vector code must have codeword length of $N \geq K^{6-o(1)}$.

fixed a few typos; updated introduction.

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle =0 \pmod{m}$, and for any $i \ne j$, $\langle \mathbf{u}_i, \mathbf{v}_j \rangle \ne 0 \pmod{m}$. An $\mathbf{MV}$ family is called $r$-restricted if inner products $\langle u_i, v_j\rangle$, for all $i,j$, take at most $r$ different values. The $r$-restricted $\mathbf{MV}$ families are extremely important since the only known construction of constant-query subexponential locally decodable codes (LDCs) are based on them. Such LDCs constructed via matching vector families are called matching vector codes. Let $\mathbf{MV}(m,n)$ (respectively $\mathbf{MV}(m, n, r)$) denote the largest $K$ such that there exists an $\mathbf{MV}$ family (respectively $r$-restricted $\mathbf{MV}$ family) of size $K$ in $\mathbb{Z}_m^n$. Such a $\mathbf{MV}$ family can be transformed in a black-box manner to a good $r$-query locally decodable code taking messages of length $K$ to codewords of length $N = m^n$.

For small prime $m$, an almost tight bound $\mathbf{MV}(m,n) \le O(m^{n/2})$ was first shown by Dvir, Gopalan, Yekhanin (FOCS'10, SICOMP'11), while for general $m$, the same paper established an upper bound of $O(m^{n-1+o_m(1)})$, with $o_m(1)$ denoting a function that goes to zero when $m$ grows. For any arbitrary constant $r \ge 3$ and composite $m$, the best upper bound till date on $\mathbf{MV}(m,n,r)$ is $O(m^{n/2})$, is due to Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14).In a breakthrough work, Alrabiah, Guruswami, Kothari and Manohar (STOC'23) implicitly improve this bound for $3$-restricted families to $\mathbf{MV}(m, n, 3) \leq O(m^{n/3})$.

In this work, we improve the upper bound for $r=3$. We show that $\mathbf{MV}(m,n,3) \le m^{n/6 +O(\log n)}$, and as a result, any $3$-query matching vector code must have codeword length of $N \geq K^{6-o(1)}$.