Source-linked AI summary
Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
Sidhant Saraogi
TL;DR
The paper addresses upper bounds for 3-restricted matching vector families, which are important for constructions of constant-query locally decodable codes. It uses a polynomial-method argument to control collisions in sumsets, proving a subexponential size bound for m ≤ √n and deriving a consequence for matching vector codes.
Problem
The paper studies the size of 3-restricted MVFs, which support constructions of the best-known constant-query locally decodable codes and previously had weaker upper bounds.
Method
The proof controls collision classes in sumsets using a polynomial method applied to a low-rank matrix of inner-product residues and moonflower structure.
Results
For every 2 ≤ m ≤ √n, the size of a 3-restricted MVF is at most 2^{O(√(n log n log m))}.
Takeaways & Limitations
The bound yields a strong lower bound on certain 3-query matching vector codes.
Takeaways & Limitations
The proof section treats typical 3-restricted MVFs modulo m = p^a q^b, with p and q distinct primes and a, b ≥ 1.
Abstract
from arXiv · showhide
Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.
1 Introduction
Matching vector families are structured vector pairs with modular inner-product conditions and important applications, especially to constant-query locally decodable codes. The paper proves a substantially stronger subexponential upper bound for 3-restricted families and develops a polynomial-method argument controlling sumset collisions.
- Definitions: Matching vector families consist of two ordered vector lists whose cross-inner-products follow specified residue patterns modulo m.The largest family sizes are denoted MV(m, n) and MV(m, n, r) for unrestricted and r-restricted families, respectively.
- Applications: MV families have applications to locally decodable codes, private information retrieval, conditional disclosure of secrets, circuit complexity, catalytic computation, Ramsey graphs, and weak polynomial representations of OR.Restricted MV families also yield constant-query LDC constructions, including 3-query codes.
- Our Results: The result improves the previous best upper bound of 2^{O(n/log n)} for 3-restricted MVFs.The paper also derives a strong lower bound on certain 3-query matching vector codes.
- Our Results: 3-restricted MVFs satisfy an upper bound of 2^{O(√(n log n log m))} for every 2 ≤ m ≤ √n.For constant m, the theorem gives a subexponential bound in n.
- Techniques: The proof studies collision classes of equal-size subset sums and shows that no collision class can be too large.It combines maximal moonflowers with a polynomially transformed low-rank inner-product residue matrix whose induced J − I structure has large rank.
- Related Work: Aggarwal and Obremski independently obtained the same upper bound for 3-restricted MVFs.
AI Usage
The paper reports that its main ideas were developed while exploring the intuition of prior work in extended conversations with ChatGPT 5.5. The author refined the proof idea, while subsequent conversations provided no further insight into improving the stated bounds.
- AI Usage: The main ideas were obtained while exploring multiple directions related to prior work in extended conversations with ChatGPT 5.5.
- AI Usage: The main idea behind the proof of Theorem 11 was developed by ChatGPT 5.5 and refined into its current form by the author.
- AI Usage: Subsequent conversations did not provide further insight into improving the bound for 3-restricted or more general r-restricted MVFs.
2 Preliminaries
The preliminaries reduce general 3-restricted matching vector families to a typical prime-product modulus and introduce moonflowers and rank-preserving polynomial-method tools.
- Matching Vector Families: Typical 3-restricted MVFs have modulus m = p^a q^b with distinct primes and structured residues α, β.The reduction applies after excluding proper-divisor moduli and prime-power cases.
- Moonflowers: Moonflowers capture the lower-bound combinatorial structure needed in the proof, with each set containing an element unique to it.The paper uses moonflowers rather than external results about them.
- Linear Algebra: A coefficient-extraction map τ_q transfers matrices over Z_{q^b} to F_q while preserving the rank bound required by the polynomial argument.For a divisible by q^{b−1}, τ_q(a) records the coefficient of q^{b−1}.
- Linear Algebra: Entrywise application of a multilinear polynomial to d low-rank matrices yields rank at most (n + 1)^d.The construction expands the polynomial over subsets and bounds each Hadamard-product term.
3 Proofs
The proof controls equal-sum collisions by ruling out large moonflowers through a low-rank indicator matrix and a multilinear polynomial construction, then completes the bound by induction.
- Collision control: The key collision lemma shows that a collision class cannot contain a large moonflower.This is the central combinatorial restriction used in the induction on sumset size.
- Low-rank matrix: The indicator matrix Π records whether each inner product equals α and has rank at most n over F_q.It is obtained by scaling the residue matrix after reduction modulo q^b.
- Polynomial method: For a moonflower of equal-sum sets, the constructed matrix has diagonal pattern ℓ and off-diagonal patterns in T_ℓ, with ℓ excluded from T_ℓ.A pigeonhole restriction first makes ℓ uniform across at least L/d sets.
- Polynomial method: A multilinear polynomial maps those patterns to P = J − I, forcing large rank while entrywise construction from Π supplies an upper rank bound.The two rank estimates are combined to complete the auxiliary lemma.
- Setup: A typical 3-restricted MVF supplies the residue structure needed for the proof after reduction to a divisor-minimal modulus.Prime-power moduli are handled by the known prime-power bound.
- Induction: Collision classes are bounded using a maximal moonflower: every representation intersects its small union, reducing the remainder to an (s − 1)-sum.The resulting recurrence is combined with the moonflower bound and optimized over s.