The Length of Functional Batch and PIR Codes

1. Problem Statement and Context

The paper addresses the fundamental problem of determining the minimum length ($n$) required for Functional Batch and Functional PIR (Private Information Retrieval) codes of a fixed dimension ($k$) and a fixed list size ($t$) over an arbitrary finite field $\mathbb{F}_q$.

• Background: PIR codes allow a user to retrieve a specific data symbol via multiple disjoint recovery sets, ensuring privacy. Batch codes generalize this to retrieve multiple distinct symbols simultaneously. Functional codes extend these concepts further, allowing the retrieval of functions of the stored data (linear combinations) rather than just the raw symbols.
• The Gap: Previous research on these codes has almost exclusively focused on the binary field ($q=2$). The behavior of these codes over non-binary fields ($q > 2$) remains largely unexplored.
• Key Conjecture: A central open problem is the Functional Batch Conjecture (Zhang, Etzion, and Yaakobi), which posits that the binary $[k, 2^k-1]$ simplex code is a $2^{k-1}$-functional batch code. This is equivalent to a combinatorial matching problem in finite abelian groups.
• Objective: The authors aim to generalize results from binary to arbitrary finite fields, compute exact values for specific parameters, establish tight bounds, and analyze the asymptotic behavior of the minimum length functions $FP(k, t, q)$ and $FB(k, t, q)$.

2. Methodology and Notation

The authors define two primary functions:

• $FP(k, t, q)$: The minimum length of a $k$-dimensional $t$-functional PIR code over $\mathbb{F}_q$.
• $FB(k, t, q)$: The minimum length of a $k$-dimensional $t$-functional batch code over $\mathbb{F}_q$.

Methodological Approach:

1. Combinatorial Construction: The authors construct generator matrices by treating columns as points in the projective space $PG(k-1, q)$. They analyze how these points can be partitioned to serve specific lists of vectors (recovery sets).
2. Parity and Counting Arguments: They utilize pigeonhole principles and parity analysis (distinguishing between even and odd $q$) to derive lower bounds on the number of columns required.
3. Subadditivity: They leverage the property that these functions are subadditive in $k$ and $t$ to extend results from small parameters to larger ones.
4. Group Theory: For specific bounds, they employ results from finite abelian groups (specifically the "seating couple problem" and Hall's marriage theorem variants) to prove the existence of specific recovery partitions.
5. Asymptotic Analysis: They apply Fekete's Lemma to study the limits of the ratio $n/t$ as $t \to \infty$ and analyze the growth rate when both $k$ and $t$ diverge.

3. Key Contributions and Results

A. Exact Values for Specific Parameters

• Dimension $k=2$: The authors derive a closed-form formula for $FB(2, t, q)$ for any prime power $q$:
  $$FB(2, t, q) = \left\lceil \frac{2(q+1)t}{q+2} \right\rceil = t + \left\lceil \frac{qt}{q+2} \right\rceil$$
  This generalizes the known binary result ($q=2 \implies t + \lceil t/2 \rceil$).
• Multiples of Critical Thresholds: They generalize known binary results to arbitrary fields. Specifically, for $FP(k, t, q)$, they show that if $t$ is a multiple of $\frac{q^k+q-2}{2}$, the length is exactly $s(q^k-1)$.
  $$FP\left(k, s \cdot \frac{q^k+q-2}{2}, q\right) = s(q^k - 1)$$
  This identifies the "natural" generalization of the binary simplex code property to non-binary fields.

B. Bounds and Field Size Dependence

• Lower Bounds:
  • They establish a logarithmic lower bound: $FB(k, t, q) \geq \frac{tk}{\log_{q-1}(t(q-1)+1)}$.
  • They prove that for sufficiently large $q$ (specifically $q \geq \binom{kt}{k-1}$), the length stabilizes at the trivial upper bound: $FB(k, t, q) = kt$.
• Upper Bounds:
  • They provide a construction showing $FB(k, 2, 2) \leq \lceil 3k/2 \rceil$.
  • They prove that for the specific case of $t = q^k + q - 2$, the length is bounded by $2(q^k - 1) + (q-2)k$. This suggests the Functional Batch Conjecture holds "up to a linear error term" in $k$ for non-binary fields.
• Asymmetry: The paper demonstrates that $FB(k, t, q) \neq FB(t, k, q)$ in general. Specifically, for large $k$, $FB(k, t, q)$ can be significantly smaller than $FB(t, k, q)$, disproving any naive symmetry conjecture.

C. Asymptotic Behavior

The authors analyze the behavior of the codes as parameters grow:

1. Fixed $k$, $t \to \infty$:
   The limit of the ratio of length to list size exists and is given by:
   $$\lim_{t \to \infty} \frac{FB(k, t, q)}{t} = \lim_{t \to \infty} \frac{FP(k, t, q)}{t} = \frac{2(q^k - 1)}{q^k + q - 2}$$
   This result confirms that the asymptotic efficiency of functional batch codes matches that of functional PIR codes, regardless of the field size.
2. Simultaneous Growth ($k, t \to \infty$):
   When both dimension and list size diverge, the length grows sub-quadratically. Specifically:
   $$\lim_{n \to \infty} \frac{FB(k_n, t_n, q)}{k_n t_n} = 0$$
   Furthermore, they establish that the normalized length grows logarithmically:
   $$1 \leq \liminf_{n \to \infty} \frac{FP(k_n, t_n, q) \log_q(t_n)}{k_n t_n} \leq \limsup_{n \to \infty} \frac{FB(k_n, t_n, q) \log_q(t_n)}{k_n t_n} < 4$$

4. Significance and Implications

• Generalization of Theory: This work is the first to systematically treat functional batch and PIR codes over arbitrary finite fields, moving beyond the binary restriction that dominated the literature.
• Insight into the Functional Batch Conjecture: By computing exact values and bounds for non-binary fields, the paper suggests that the "correct" list size for the Functional Batch Conjecture over $\mathbb{F}_q$ is likely $\frac{q^k+q-2}{2}$ (rather than $2^{k-1}$ in the binary case).
• Practical Storage Efficiency: The results provide concrete formulas for the minimum storage overhead ($n$) required to support private and batched retrieval in distributed storage systems, particularly for non-binary alphabets which are common in modern storage technologies (e.g., flash memory, DNA storage).
• Combinatorial Connections: The paper bridges coding theory with combinatorial problems in finite abelian groups, specifically relating code length to partitioning and matching problems, offering new tools for researchers in both fields.

In summary, the paper provides a comprehensive theoretical framework for functional batch and PIR codes, offering exact solutions for small dimensions, tight bounds for general parameters, and a complete characterization of their asymptotic behavior over arbitrary finite fields.