Upper Bounds on Matching Families in $\mathbb{Z}_{pq}^n$

Yeow Meng Chee, San Ling, Huaxiong Wang, Liang Feng ZhangarXiv 2013 · arXiv

Abstract

This paper establishes a new, tighter upper bound on the size of "matching families" in the ring $\mathbb{Z}_{pq}^n$. Since matching families are the fundamental building blocks for the most efficient known Locally Decodable Codes (LDCs), this result provides a clearer theoretical limit on how short a constant-query LDC can actually be. By employing a spectral method based on projective graphs and a novel "Tensor Lemma," the authors improve the upper bound from $O(m^{0.75n})$ to $O(m^{0.625n + 0.125})$ for $m=pq$.

Introduction

Locally Decodable Codes (LDCs) are a special class of error-correcting codes that allow a user to recover a single bit of the original message by reading only a tiny, constant number of bits from a (potentially corrupted) codeword. This is a massive improvement over standard codes, which usually require reading the entire codeword to fix even a single error.

The "holy grail" in LDC research is finding the best trade-off between the length of the codeword ($N$) and the length of the message ($k$). Currently, the best constructions for LDCs with a constant number of queries rely on a combinatorial structure called matching families. The size of these matching families directly determines the efficiency of the resulting LDC. While researchers have found ways to build large matching families (providing lower bounds), we need upper bounds to understand the absolute limits of these techniques. This paper specifically tackles the case where the ring modulus $m$ is the product of two distinct primes ($m = pq$), a setting central to many modern LDC constructions.

Methods

The authors employ a sophisticated spectral method rooted in graph theory. Their approach follows these key steps:

Projective Graphs

They represent the matching family problem as a graph problem. They define "projective graphs" over the ring $\mathbb{Z}_m$, where vertices are points and hyperplanes, and edges represent "incidence" (a point lying on a hyperplane). The complexity of these structures grows significantly as the modulus $m$ moves from a prime to a composite number.

Example elements of projective spaces $\mathbb{P}_{3,m}$ for $m=2, 3, 6$, illustrating the underlying sets for projective graphs over prime and composite moduli.

The Tensor Lemma

The core technical innovation is a "Tensor Lemma." The authors prove that the adjacency matrix of a projective graph over $\mathbb{Z}_{pq}$ is actually the tensor product of the adjacency matrices of projective graphs over the simpler prime fields $\mathbb{Z}_p$ and $\mathbb{Z}_q$.

Eigenvalue Analysis and Expansion

By decomposing the complex composite structure into prime components, they can calculate the eigenvalues of the graph's adjacency matrix. They prove that these projective graphs have an "expanding property." They then use the "unique neighbor property"—a characteristic of matching families—to show that if a set of points in the graph is too large, it would violate the graph's expansion limits.

Key Results

The paper proves that for a constant dimension $n$, as the primes $p$ and $q$ grow large (and $p/q \to 1$), the size of any matching family $k(m, n)$ is bounded by:

$O(m^{0.625n + 0.125})$

This is a substantial improvement over the previous best-known upper bound of $O(m^{0.75n})$. For context, researchers have conjectured that the true limit might be around $O(m^{0.5n})$, and this paper moves the theoretical ceiling significantly closer to that target.

Discussion and Future Work

  • Algebraic Decomposition: The most significant insight is the realization that the structure of matching families over a composite modulus $pq$ can be elegantly decomposed using tensor products. This allows the authors to leverage well-understood properties of prime fields to solve a much harder problem over composite rings.
  • The Expansion Link: The paper reinforces a deep connection between coding theory and the "expansion" of graphs. In essence, if a graph is "well-connected" (expands well), it limits how many "unique neighbors" a subset of vertices can have, which in turn limits the size of the matching family.
  • Limitations: The current method is specifically optimized for $m = pq$. The authors note that as the number of distinct prime factors in $m$ increases, their spectral method becomes "weaker" because the gap between the largest eigenvalues of the graph shrinks. A natural next step is extending this refined spectral approach to general integers $m$ that are not just products of two primes.

Summary updated

Abstract

\textit{Matching families} are one of the major ingredients in the construction of {\em locally decodable codes} (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in $\mathbb{Z}_m^n$, where $\mathbb{Z}_m$ is the ring of integers modulo $m$, is an interesting problem. In this paper, we show an upper bound of $O((pq)^{0.625n+0.125})$ for the size of any matching family in $\mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is valid when $n$ is a constant, $p\rightarrow \infty$ and $p/q\rightarrow 1$. Our result improves an upper bound of Dvir {\it et al.}
BibTeX
@misc{chee2013upper,
  author = {Yeow Meng Chee and San Ling and Huaxiong Wang and Liang Feng Zhang},
  title = {{Upper Bounds on Matching Families in $\textbackslash\{\}mathbb\{Z\}\_\{pq\}^n$}},
  year = {2013},
  eprint = {1301.0980},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1301.0980},
}
Figure