Fourier Sparsity of Delta Functions and Matching Vector PIRs

Ghasemi, Fatemeh; Kopparty, Swastik

doi:10.4230/LIPIcs.ITCS.2026.68

Fourier Sparsity of Delta Functions
and Matching Vector PIRs

Fatemeh Ghasemi

Department of Mathematics, University of Toronto, Canada Swastik Kopparty

Department of Mathematics and Department of Computer Science, University of Toronto, Canada

Abstract

In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes.

For integers $m, r$ , define a delta function on $\{0,1\}^{r}\subseteq\mathbb{Z}_{m}^{r}$ to be a function $f:\mathbb{Z}_{m}^{r}\to\mathbb{C}$ if $f(0)=1$ and $f(x)=0$ for all nonzero Boolean $x$ . The basic question that we study is how small can the Fourier sparsity of a delta function be; namely, how sparse can such an $f$ be in the Fourier basis?

In addition to being intrinsically interesting and natural, such questions arise naturally while studying “ $S$ -decoding polynomials” for the known matching vector families. Finding $S$ -decoding polynomials of reduced sparsity – which corresponds to finding delta functions with low Fourier sparsity – would improve the current best PIR schemes.

We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improvements to the Matching Vector PIR schemes simply by finding better $S$ -decoding polynomials. In particular, there are no $S$ -decoding polynomials which can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication for constantly many servers.

Many interesting questions remain open.

Keywords and phrases:

Fourier Sparsity, Matching Vectors, Private Information Retrieval

Funding:

Swastik Kopparty: Research supported by an NSERC Discovery Grant.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity ; Mathematics of computing

\rightarrow

Coding theory ; Mathematics of computing

\rightarrow

Mathematical analysis

DOI:

10.4230/LIPIcs.ITCS.2026.68

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In this paper we study some basic and natural questions about Fourier analysis of Boolean functions. Specifically, we study the Fourier transform of functions $f$ defined on the whole group $\mathbb{Z}_{m}^{r}$ given constraints on the values that $f$ takes on the Boolean hypercube $\{0,1\}^{r}$ . These questions were originally motivated by a connection to Matching Vector based Private Information Retrieval (PIR) schemes, but we feel that they are intrinsically interesting in their own right.

The relationship of the subset $\{0,1\}^{r}$ with the superset $\mathbb{Z}_{m}^{r}$ is of central importance in many aspects of complexity theory. Many fundamental results about $\{0,1\}^{r}$ begin by viewing it as a subset of $\mathbb{Z}_{m}^{r}$ (or $\mathbb{F}_{p}^{r}$ ), and using the more powerful algebra of the larger domain. This includes the Razborov-Smolensky lower bounds for $AC_{0}$ , arithmetization as a tool for interactive and probabilistically checkable proofs, and many more.

Let $m, r$ be integers. Our main concern is the Fourier behaviour of the Boolean hypercube $\{0,1\}^{r}$ contained within the abelian group $G=\mathbb{Z}_{m}^{r}$ . Specifically, we will be interested in estimating the minimum possible Fourier sparsity of a delta function $f:G\to\mathbb{C}$ .

$\blacksquare$

Fourier Sparsity: For $i\in[m^{r}]$ , let $\psi_{i}:G\to\mathbb{C}$ be the Fourier characters of $G$ . Every function $f$ from $G$ to $\mathbb{C}$ can be expressed uniquely as a linear combination of the $\psi_{i}$ . The number of $\psi_{i}$ that get a nonzero coefficient is called the Fourier sparsity of $f$ .
$\blacksquare$

Delta function: A function $f:G\to\mathbb{C}$ is called a delta function if $f(0)=1$ , and for all $x\in\{0,1\}^{r}\setminus\{0\}$ , we have $f(x)=0$ (informally, it behaves like “the delta function” on $\{0,1\}^{r}$ ).

On first reading, it may be useful to think about the asymptotic where $m$ is a fixed constant, even $3$ , and $r\to\infty$ .

The set of all delta functions is a $(m^{r}-2^{r})$ -dimensional affine subspace of the $m^{r}$ -dimensional space of all functions, and thus by general linear-algebra principles, there is always a subset of $2^{r}$ Fourier characters whose span contains some delta function. Can this $2^{r}$ be reduced?

1.1 Overview of Results

When $m=2$ , there is only one delta function; and its Fourier sparsity is $2^{r}$ .

Already for $m=3$ , the situation turns out to be quite interesting, with both nontrivial upper and lower bounds. We show that there are delta functions with Fourier sparsity $\leq O((\sqrt{3})^{r})$ , while any delta function must have Fourier sparsity at least $\Omega((1.5)^{r})$ .

The situation drastically changes with growing $m$ . We show that once $m\geq r$ , there are delta functions with Fourier sparsity $\leq r+1$ , and this is tight!

For general $m$ (with $r\to\infty$ ), we show an upper bound of $O(m^{r/(m-1)})=\exp\left(\frac{\log m}{m-1}\cdot r\right)$ and a lower bound of $\Omega\left(\left(\frac{m}{m-1}\right)^{r}\right)=\exp\left(\frac{1}{m-1}\cdot r\right)$ .

More general groups

For applications to PIRs (discussed below), we actually need to study a slightly generalized problem.

$\blacksquare$

The abelian group $G$ is now taken to be of the more general form $\prod_{i=1}^{r}\mathbb{Z}_{m_{i}}$ , where $m_{1},\ldots,m_{r}$ are positive integers,
$\blacksquare$

Instead of $\mathbb{C}$ -valued Fourier characters, for a field $\mathbb{F}$ containing $m_{i}$ distinct $m_{i}$ ’th roots of unity, we work with $\mathbb{F}$ -valued Fourier characters.

Even in this generalized setting, we can talk about the Boolean hypercube $\{0,1\}^{r}\subseteq G$ (which is simply the product of each $\{0,1\}\subseteq\mathbb{Z}_{m_{i}}$ ), delta functions, and the Fourier expansion of functions $f:G\to\mathbb{F}$ .

Appropriate generalizations of our lower bounds from the case where all the $m_{i}$ are equal to $m$ continue to hold in this generalized setting. However our upper bounds break down, and for the setting relevant to PIRs, this leaves open a much bigger gap, which would be very interesting to close.

Delta functions on $\{-1,0,1\}^{r}$

One could also talk about delta functions on sets more general that $\{0,1\}^{r}$ . For a subset $B\subseteq G$ with $0\in B$ , a $B$ -delta function is a function $f$ with $f(0)=1$ and $f(b)=0$ for all $b\in B\setminus\{0\}$ .

A natural and well known example is the case $B=G$ . The unique $G$ -delta function is the average of all its Fourier characters: this means that its Fourier sparsity is $|G|$ .

A another natural set to consider is $B=\{-1,0,1\}^{r}$ (when $G=\prod_{i=1}^{r}\mathbb{Z}_{m_{i}}$ ). One would expect that the Fourier sparsity of $B$ -delta functions to behave very similar to the case of $\{0,1\}^{r}$ . Surprisingly, there is a big difference!

Again from general principles, since $|B|=3^{r}$ , there is always a $B$ -delta function of sparsity at most $3^{r}$ . Are there $B$ -delta functions with smaller sparsity?

We show that for all $G$ , the Fourier sparsity of a $B$ -delta function is at least $2^{r}$ . This is in sharp contrast to the $\{0,1\}^{r}$ case, where the sparsity decays sharply with $m$ in the group $G=\mathbb{Z}_{m}^{r}$ , and there are are delta functions of sparsity as small as $r+1$ once $m>r$ .

Techniques

Our proofs are all elementary and simple. The lower bounds for $\{0,1\}^{r}$ are based on studying the product of a purported Fourier sparse delta function with a suitably constructed auxiliary function with desirable Fourier and primal support. The upper bounds for $\{0,1\}^{r}$ are by explicitly giving the functions. The lower bounds for $\{-1,0,1\}^{r}$ are proved using the linear algebra method of combinatorics.

We feel that closing the gaps between our upper and lower bounds will need some new insights about the Fourier analysis of Boolean functions, which may potentially be useful in the many other situations in theoretical computer science where $\{0,1\}^{r}$ is viewed as a subset of the larger domain $\mathbb{F}_{p}^{r}$ .

Another related theme we would like to mention is the uncertainty principle in finite abelian groups, which gives lower bounds on the Fourier sparsity of functions $f:G\to\mathbb{C}$ with small support. See [6, 13, 16] for various statements of this principle.

1.2 Matching Vector PIRs

The original motivation for studying Fourier-sparse delta functions is from questions about Private Information Retrieval (PIR). A PIR scheme¹¹1PIR schemes are very closely related to Locally Decodable Codes (LDCs). Many breakthroughs happened for both these notions together, but we only talk about PIRs in this paper. In particular, there are implications of our results for the LDCs known as Matching Vector codes. is an interactive protocol between a user and $t$ non-communicating servers, which allows the user to access any desired bit $a_{i}$ of a database $(a_{1},\ldots,a_{n})\in\{0,1\}^{n}$ without revealing any information about $i$ . PIRs have been extensively studied ever since their introduction by Chor, Goldreich, Kushilevitz and Sudan [5] in 1995. The main question is to achieve this with as little communication as possible. Very little is known on the lower bounds front; it is consistent with our knowledge that PIR can be achieved with $2$ -servers and $\mathsf{poly}\log(n)$ communication complexity!

When the number of servers $t$ is constant, it was originally believed that the amount of communication needed to be at least polynomial in $n$ , of the form $\Omega(n^{\varepsilon_{t}})$ . However, many years later, surprising results of Yekhanin [17] and Efremenko [9] strongly refuted this belief. These protocols are the Matching Vector PIRs, and achieve a communication complexity of $O(\exp((\log n)^{\varepsilon_{t}}))$ – and these are the only known way to achieve communication complexity subpolynomial in $n$ with a constant number of servers.

There are two key ingredients of Matching Vector PIRs:

$\blacksquare$
An $S$ -matching vector family: for a subset $S\subseteq\mathbb{Z}_{m}$ with $0\in S$ , an $S$ -matching vector family is a collection of $2n$ vectors $u_{i},v_{i}\in\mathbb{Z}_{m}^{k}$ , for $i\in[n]$ , such that:
- –
  
  $\langle u_{i},v_{j}\rangle=0$ if $i=j$ ,
- –
  
  $\langle u_{i},v_{j}\rangle\in S\setminus\{0\}$ if $i\neq j$ .
We would like $n$ as large as possible.
$\blacksquare$
An $S$ -decoding polynomial: for a subset $S\subseteq\mathbb{Z}_{m}$ and a field $\mathbb{F}$ containing an $m$ -th root of unity $\gamma_{m}$ , an $S$ -decoding polynomial is a polynomial $P(Z)\in\mathbb{F}[Z]$ such that:
- –
  
  $P(\gamma^{0})=1$ ,
- –
  
  $P(\gamma^{s})=0$ for each $s\in S\setminus\{0\}$ .
We would like $P(Z)$ to be as sparse as possible.

The best known PIR protocols [9, 7, 8, 10] use the $S$ -matching vector families coming from the work of Barrington-Biegel-Rudich [2] and Grolmusz [11]. Here $m$ is taken to be the product of primes $m_{1},\ldots,m_{r}$ , and $S$ is taken to be a product set $\prod_{i=1}^{r}\{0,1\}\subseteq\prod_{i=1}^{r}\mathbb{Z}_{m_{i}}\simeq\mathbb{% Z}_{m}$ . Such $S$ is called a canonical $S$ for $\mathbb{Z}_{m}$ .

Even with trivial $S$ -decoding polynomials, the above $S$ -matching vector family alone is enough to achieve the dramatic improvement of communication complexity from polynomial to subpolynomial. It achieves communication $\exp((\log n)^{\varepsilon_{t}})$ . A clever choice of $S$ -decoding polynomial further improves the communication complexity. The theory of sparse $S$ -decoding polynomials was developed and advanced by Yekhanin [17], Raghavendra [14], Efremenko [9], Itoh-Suzuki [12] and Chee-Feng-Ling-Wang-Zhang [4], to achieve significant improvements for small $t$ . Under plausible number theoretic conjectures, [4] reduces $\varepsilon_{t}$ by an absolute constant factor for all $t$ .²²2The improvement is more stark for fixed $t$ : the communication complexity using a clever $S$ -decoding polynomial is a further subpolynomial in the communication complexity achieved using trivial $S$ -decoding polynomials.

To improve Matching Vector PIR parameters further, there are two immediate avenues. The first is to get even larger $S$ -matching vector families – this is an extremely interesting and basic question about linear algebra mod $m$ , and has attracted quite a bit of interest [3, 1]. To summarize the current status: it is wide open whether these exist.

The other approach to improved PIRs, is to get sparser $S$ -decoding polynomials for the known $S$ -matching vector families. This approach, a priori, could also be capable of achieving polylogarithmic communication for a constant number of servers: this would be possible if there exist $S$ -decoding polynomials of constant sparsity modulo any $m$ . This is the approach that this paper addresses.

Our results imply that for the $S$ relevant for the known big matching vector family over $\mathbb{Z}_{m}$ , any $S$ -decoding polynomial has sparsity at least $r+1$ . This means that for a Matching Vector PIR using the known matching vector families and the best possible $S$ -decoding polynomial, the communication complexity for $t$ server PIR is at least $\exp((\log n)^{1/t})$ . In particular it cannot achieve polylogarithmic communication for a constant number of servers.

1.3 Questions

There are two very nice and basic open questions that we would like to highlight.

1.

Let $m_{1},\ldots,m_{r}$ be distinct primes, and let $\mathbb{F}$ be a field containing all the $m_{i}$ ’th roots of $1$ . We work with the $\mathbb{F}$ -valued Fourier characters. How small, as a function of $r$ , can the Fourier sparsity of delta functions on $\{0,1\}^{r}\subseteq\prod_{i=1}^{t}\mathbb{Z}_{m_{i}}$ ?

We showed that it cannot be smaller than $r+1$ , while the best upper bounds are exponential in $r$ (these come from known sparse $S$ -decoding polynomials [4]).

Can it be $r+1$ ? This would improve PIR communication to $\exp((\log n)^{1/t})$ .

Surprisingly, if we drop the assumption that the $m_{i}$ are distinct, then $r+1$ is achievable (see Lemma 16).
2.

We have the same setup as above (with the $m_{i}$ being distinct primes), but now we fix $\mathbb{F}$ to be the complex numbers $\mathbb{C}$ . We conjecture that every delta function on $\{0,1\}^{r}\subseteq\prod_{i=1}^{r}\mathbb{Z}_{m_{i}}$ has Fourier sparsity at least $2^{r}$ : there is no improvement on the trivial bound!

We prove the $r=2$ case in Appendix C. The proof uses ideas related to the classical Schwarz lemma from complex analysis, and boils down to studying certain Möbius transformations and their behavior on the unit disk. For larger $r$ it seems to be a challenging yet basic question.

Again, for identical $m_{i}$ , Fourier sparsity $r+1$ is achievable, so the distinctness of the primes $m_{i}$ has to be used.

Finally, the question of determining the Fourier sparsity of delta functions on $\mathbb{Z}_{m}^{r}$ for fixed $m$ is a very cleanly stated question which we do not fully understand. We know that it is exponential is $r$ , but the base of the exponent is somewhere between $m^{\frac{1}{m-1}}$ and $\frac{m}{m-1}$ .

2 Main Result

In order to state our main results, we need the following definitions.

Definition 1.

Let $G$ be a group and $\mathbb{F}$ be a field, $0\in B,B\subseteq G$ . We say:

f:G\rightarrow\mathbb{F}

is a delta function on $B$ (or $f$ is delta on $B$ , or $f$ is a $B$ -delta function) if:

$\blacksquare$

$f(0)=1$
$\blacksquare$

For all $b\in B\setminus\{0\}$ , we have $f(b)=0.$

For $\mathbb{F}$ -valued functions $f$ on the abelian group $G$ , we will be working with the $\mathbb{F}$ -valued Fourier transform $\widehat{f}$ (generalizing the usual $\mathbb{C}$ -valued Fourier transform), discussed in Section 3.

In the special case where the domain is $\mathbb{Z}_{m}^{r}$ and the function is delta on $\{0,1\}^{r}$ , the following theorem provides explicit bounds on the Fourier sparsity. Parts (i) and (ii) are special cases of the general lower bounds proved later in Section 3.2, namely Theorems 11 and 14, while parts (iii) and (iv) correspond to the upper bounds established in Lemma 16 and Claim 18. The proofs of all four parts appear in Section 3.2.

Theorem 2.

Let $f:\mathbb{Z}_{m}^{r}\rightarrow\mathbb{F}$ be delta on $\{0,1\}^{r}\subset\mathbb{Z}_{m}^{r}$ . We have:

(i)

$|Supp(\widehat{f})|\geq r+1$
(ii)

$|Supp(\widehat{f})|\geq(\frac{m}{m-1})^{r}$

In the other direction:

(iii)

For $m>r$ , there exists $f:\mathbb{Z}_{m}^{r}\to\mathbb{F}$ which is delta on $\{0,1\}^{r}$ with $|Supp(\widehat{f})|=r+1$ .
(iv)

For $m, r$ with $(m-1)\mid r$ , there exists $f:\mathbb{Z}_{m}^{r}\rightarrow\mathbb{F}$ which is delta on $\{0,1\}^{r}$ with $|Supp(\widehat{f})|\leq m^{\frac{r}{m-1}}$ .

One application of our results is to $S$ -decoding polynomials, a tool in the construction of Matching Vector PIRs. We describe this now.

Definition 3 ( $S$ -decoding polynomial for the canonical set $S$ ).

Let $m=p_{1}\cdots p_{r}$ and define the canonical set

	$\displaystyle S$	$\displaystyle=\{x\in\mathbb{Z}_{m}:x^{2}=x\}$
		$\displaystyle=\{x\in\mathbb{Z}_{m}\mid(x\mod p_{i})\in\{0,1\}\mbox{ for each }% i\}.$

Let $\mathbb{F}$ be a field containing a primitive $m$ -th root of unity $\gamma_{m}$ . A polynomial $P(Z)\in\mathbb{F}[Z]$ is called a $S$ -decoding polynomial if

$\blacksquare$

$P(\gamma_{m}^{s})=0$ for all $s\in S\setminus\{0\}$ ,
$\blacksquare$

$P(\gamma_{m}^{0})=P(1)=1$ .

If $P$ has exactly $t$ monomials, we say it is $t$ -sparse.

We restrict here to the canonical set $S$ ; a more general definition for arbitrary subsets $S\subseteq\mathbb{Z}_{m}$ will be given in Section 4.1.

$S$ -decoding polynomials play a central role in the construction of Matching Vector PIR schemes: sparser polynomials yield the same communication complexity with fewer servers. For the canonical set $S\subseteq\mathbb{Z}_{m}$ , our results show that such polynomials cannot be very sparse.

The following theorem gives the precise lower bound; its proof appears in Section 4.1 as Corollary 24.

Theorem 4.

Let $m=p_{1}\cdots p_{r}$ , and let $S$ be the canonical set for $m$ . If $P(Z)\in\mathbb{F}[Z]$ is an $S$ -decoding polynomial, then the number of its monomials is at least $r+1$ .

The consequences for Matching Vector PIRs are discussed in Section 4.

Our final main result concerns delta functions on a set different from the Boolean hypercube, namely $\{-1,0,1\}^{r}$ . For such functions we obtain a much stronger lower bound on Fourier sparsity, that does not decay with $m$ . The proof will be given in Section 3.3 as a corollary of Claim 19.

Theorem 5.

If $f:\mathbb{Z}_{m}^{r}\rightarrow\mathbb{F}$ is delta on $\{-1,0,1\}^{r}$ , then we have:

|Supp(\widehat{f})|\geq 2^{r}

3 Bounds for Delta Functions

In this section, we first derive bounds for delta functions on the Boolean hypercube $\{0,1\}^{r}$ , and then we establish a lower bound for delta functions over $\{-1,0,1\}^{r}$ .

3.1 Basic Facts from Fourier Analysis

We collect the Fourier-analytic facts used in this paper. Throughout, $G$ is a finite abelian group of size $m$ , written additively.

For a function $h$ on a finite set $X$ , we define its support as

Supp(h)\;:=\;\{\,x\in X:h(x)\neq 0\,\}.

For subsets $A, B$ of an additive group, we write

A+B\;:=\;\{\,a+b:a\in A,\ b\in B\,\}

for their sumset.

We now define the Fourier transform and state the basic Fourier inversion formula.

Definition 6 (Fourier transform over a finite abelian group, $\mathbb{F}$ -valued).

Let $G$ be a finite abelian group, and let $e$ denote the exponent of $G$ (i.e., the least common multiple of the orders of elements of $G$ ). Let $\mathbb{F}$ be a field with $\operatorname{char}(\mathbb{F})\nmid|G|$ such that $\mathbb{F}$ contains all $e$ -th roots of unity (equivalently, a primitive $e$ -th root of unity, and hence all its powers).

A character of $G$ is a group homomorphisms from $G$ to $\mathbb{F}^{\times}$ , where $\mathbb{F}^{\times}$ is the multiplicative group of $\mathbb{F}$ . Let $\widehat{G}$ be the group of all characters of $G$ .

For a function $f\colon G\to\mathbb{F}$ , its Fourier transform is the function $\widehat{f}\colon\widehat{G}\to\mathbb{F}$ defined by

\widehat{f}(\psi)\;=\;\frac{1}{|G|}\sum_{x\in G}f(x)\,\psi(x)^{-1},\qquad\psi% \in\widehat{G}.

Whenever we talk about the Fourier transform of $\mathbb{F}$ -valued functions on $G$ , we assume that $\operatorname{char}(|\mathbb{F}|)\not\mid|G|$ , and that $\mathbb{F}$ has the required roots of unity in it. The first assumption is non-negotiable. The second assumption is without loss of generality, by replacing $\mathbb{F}$ with a finite extension containing the required roots of unity (this is possible because of the first assumption).

Next we state the basic fact about the Fourier transform of the product of functions.

Lemma 7 (Character basis and explicit parametrization).

Let $\mathbb{F}$ be a field and $G\cong\oplus_{i=1}^{r}\mathbb{Z}_{m_{i}}$ be a finite abelian group such that $char(\mathbb{F})\nmid|G|$ and $\mathbb{F}$ contains primitive $m_{i}$ -th roots of unity $\omega_{m_{i}}$ for $1\leq i\leq r$ .

For any $a=(a_{1},...,a_{r})\in\oplus_{i=1}^{r}\mathbb{Z}_{m_{i}}$ , we have a character $\psi_{a}$ given by:

\psi_{a}(x_{1},...,x_{r})=\Pi_{i=1}^{r}\omega_{m_{i}}^{a_{i}x_{i}}.

every character $\psi:G\rightarrow\mathbb{F}$ is of the form $\psi_{a}$ for some $a$ .

Thus the character group $\widehat{G}$ is isomorphic to $\oplus_{i=1}^{r}\mathbb{Z}_{m_{i}}$ , and we identify them.

With this notation, every function $f:G\rightarrow\mathbb{F}$ can be written as

f=\sum_{a\in\widehat{G}}\widehat{f}(a).\psi_{a}

Lemma 8.

Let $G$ be a finite abelian group and $\mathbb{F}$ be a field. Suppose $f,g:G\to\mathbb{F}$ are functions and define $h=f\cdot g$ as their pointwise product. Then the Fourier transform of $h$ is given by the convolution of the Fourier transforms of $f$ and $g$ :

\widehat{h}(a)=\bigl(\ \widehat{f}*\widehat{g}\,\bigr)(a)=\sum_{b\in\widehat{G% }}\widehat{f}(b)\widehat{g}(a-b)

This implies:

Supp(\widehat{h})\subseteq Supp(\widehat{f})+Supp(\widehat{g})

Corollary 9.

Let $f,g:G\to\mathbb{F}$ be functions on a finite abelian group $G$ , and set $h=f\cdot g$ . Then

|Supp(\widehat{h})|\;\leq\;|Supp(\widehat{f})|\,|Supp(\widehat{g})|.

Finally, we recall the Fourier expansion of the (unique) $G$ -delta function, which we call the total delta function to avoid ambiguity.

Lemma 10 (Fourier expansion of the total delta function).

Let $G$ be a finite abelian group and let $\mathbb{F}$ be a field with $\operatorname{char}(\mathbb{F})\nmid|G|$ . Let $\delta$ denote the total delta function on $G$ , i.e.

\delta(x)\;=\;\begin{cases}1&\text{if }x=0,\\ 0&\text{otherwise}.\end{cases}

Then its Fourier transform is given by

\widehat{\delta}(a)\;=\;\frac{1}{|G|}\qquad\text{for all }a\in\widehat{G}.

In particular, $\widehat{\delta}$ is nonzero on every character, and so $\delta$ has Fourier sparsity exactly $|G|$ .

3.2 Bounds for Delta Functions on the Boolean Hypercube

In what follows, we first prove two lower bounds for functions

f:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\to\;\mathbb{F}

that are delta on $\{0,1\}^{r}$ . We then turn to the more specific setting

f:\mathbb{Z}_{m}^{r}\;\to\;\mathbb{F},

and establish an upper bound. In particular, when $m>r$ , this upper bound matches the lower bound $r+1$ , showing that the bound is tight.

First lower bound

Let

f:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\to\;\mathbb{F}

be a delta function on $\{0,1\}^{r}$ . We present two proofs showing that its Fourier sparsity is at least $r+1$ .

The following theorem formalizes this bound.

Theorem 11.

Let

f:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\to\;\mathbb{F}

be a delta function on $\{0,1\}^{r}\subseteq\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}$ , where $m_{1},\dots,m_{r}$ are (not necessarily distinct) positive integers. Assume further that $\mathbb{F}$ contains $m_{i}$ -th roots of unity $\omega_{m_{i}}$ for $1\leq i\leq r$ . Then

|Supp(\widehat{f})|\;\geq\;r+1.

First proof (of the first lower bound)

Our first proof proceeds by constructing an auxiliary function $g$ supported on $\{0,1\}^{r}$ . Multiplying $f$ by $g$ will produce a global delta function, and from this we can deduce a structural relation between the Fourier supports of $f$ and $g$ . The following lemma makes this precise.

Lemma 12.

Let

f:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\to\;\mathbb{F}

be a delta function on $\{0,1\}^{r}$ , where $m_{1},\dots,m_{r}$ are (not necessarily distinct) positive integers. Suppose $g:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\to\mathbb{F}$ is a function such that

$\blacksquare$

$g(x)=0$ for all $x\notin\{0,1\}^{r}$ ,
$\blacksquare$

$g(0)\neq 0$ .

Then

Supp(\widehat{f})+Supp(\widehat{g})\;=\;\mathbb{Z}_{m_{1}}\times\cdots\times% \mathbb{Z}_{m_{r}}.

Proof.

Let $h=fg$ . By Lemma 8,

Supp(\widehat{h})\;\subseteq\;Supp(\widehat{f})+Supp(\widehat{g}).

Since $g$ is supported on $\{0,1\}^{r}$ and $f$ vanishes on $\{0,1\}^{r}\setminus\{0\}$ with $f(0)\neq 0$ , we see that $h$ is supported only at $0$ . Thus $h$ is a nonzero scalar multiple of the total delta function on the whole group, and so by Lemma 10,

Supp(\widehat{h})=\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}.

This gives

Supp(\widehat{f})+Supp(\widehat{g})\;=\;\mathbb{Z}_{m_{1}}\times\cdots\times% \mathbb{Z}_{m_{r}}.\

$\hfill\blacktriangleleft$

To apply Lemma 12, we need an explicit function $g$ satisfying the required conditions and whose Fourier support we can describe precisely. The following example provides such a construction.

Example 13.

Let $\mathbb{F}$ be a field containing primitive $m_{i}$ -th roots of unity $\omega_{m_{i}}$ for $1\leq i\leq r$ . Define

g\colon\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\longrightarrow% \;\mathbb{F}

by

g(x_{1},\dots,x_{r})=\prod_{i=1}^{r}\;\Bigl(\omega_{m_{i}}^{x_{i}}\;\prod_{j=2% }^{m_{i}-1}\bigl(\,\omega_{m_{i}}^{x_{i}}-\omega_{m_{i}}^{j}\bigr)\Bigr).

For each coordinate $i$ , define

h_{i}(x_{i})\;=\;\omega_{m_{i}}^{x_{i}}\;\prod_{j=2}^{m_{i}-1}\bigl(\omega_{m_% {i}}^{x_{i}}-\omega_{m_{i}}^{j}\bigr)

Hence $h_{i}$ lies in the span of the characters $\{\;\omega_{m_{i}}^{b_{i}x_{i}}:1\leq b_{i}\leq m_{i}-1\;\}$ . Consequently, $g$ lies in the span

g\;\in\;Span\Bigl\{\,\prod_{i=1}^{r}\omega_{m_{i}}^{b_{i}x_{i}}\;\;:\;\;1\leq b% _{i}\leq m_{i}-1\Bigr\}.

It follows that the Fourier support of $g$ is exactly

Supp(\widehat{g})=\prod_{i=1}^{r}\{1,\dots,m_{i}-1\},

and therefore

|Supp(\widehat{g})|\;=\;\prod_{i=1}^{r}(m_{i}-1).

We are now ready to give the first proof of Theorem 11.

Proof of Theorem 11.

By Lemma 12 and Example 13, we know that

Supp(\widehat{f})+\prod_{i=1}^{r}\{1,\dots,m_{i}-1\}=\prod_{i=1}^{r}\{0,1,% \dots,m_{i}-1\}.

This implies the following property: for every element

u\in\prod_{i=1}^{r}\{0,1,\dots,m_{i}-1\},

there must exist some $a\in Supp(\widehat{f})$ such that $u_{i}\neq a_{i}$ for all coordinates $i$ .

Now assume, for the sake of contradiction, that

Supp(\widehat{f})=\{b^{1},\dots,b^{t}\},\qquad t\leq r.

That is, suppose the Fourier support has size at most $r$ . Construct a vector $u\in\prod_{i=1}^{r}\{0,1,\dots,m_{i}-1\}$ by setting

u=(b^{1}_{1},b^{2}_{2},\dots,b^{t}_{t},0,\dots,0),

where the first $t$ coordinates are taken from the corresponding elements $b^{1},\dots,b^{t}$ in the support, and the remaining coordinates are set to $0$ .

By the mentioned property, there must exist some $b\in Supp(\widehat{f})$ such that $b_{j}\neq u_{j}$ for every coordinate $j$ . But by construction, for each $i\leq t$ we have $u_{i}=b^{i}_{i}$ , which forces $b\neq b^{i}$ for all $i=1,\dots,t$ . This contradicts the assumption that $Supp(\widehat{f})=\{b^{1},\dots,b^{t}\}$ .

Therefore, our assumption was false, and we conclude that

|Supp(\widehat{f})|\;\geq\;r+1.\

$\hfill\blacktriangleleft$

Second proof (of the first lower bound)

Unlike the first proof, which relied on support-sum arguments, our second proof of Theorem 11 uses a polynomial identity arising from the delta property of $f$ on $\{0,1\}^{r}$ .

Proof.

By assumption, there exists $\omega_{m_{i}}\in\mathbb{F}$ where each $\omega_{m_{i}}$ is an $m_{i}$ -th root of unity. By Lemma 7, we can expand $f$ as

f(x_{1},\dots,x_{r})\;=\;\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}\omega_{m_{i}}^{\,a% _{j}(i)\,x_{i}}.

For convenience, define the vectors $\alpha_{i}\in\mathbb{F}^{t}$ by

\alpha_{i}=\bigl(\alpha_{i}(1),\dots,\alpha_{i}(t)\bigr),\qquad\alpha_{i}(j):=% \omega_{m_{i}}^{\,a_{j}(i)}\quad\text{for }1\leq j\leq t.

With this notation we can rewrite $f$ as

f(x_{1},\dots,x_{r})\;=\;\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}\alpha_{i}(j)^{\,x_% {i}}.

Since $f$ is a delta function on $\{0,1\}^{r}$ , we have

f(x)=0\quad\text{for all }x\in\{0,1\}^{r}\setminus\{0\},\qquad f(0,\dots,0)% \neq 0.

Equivalently,

\sum_{j=1}^{t}b_{j}\prod_{i\in B}\alpha_{i}(j)\;=\;0\quad\text{for every % nonempty }B\subseteq[r],\qquad\sum_{j=1}^{t}b_{j}\;\neq\;0.

Observe that, introducing formal variables $T_{1},\dots,T_{r}$ , expanding

\prod_{i=1}^{r}\bigl(1+T_{i}\alpha_{i}(j)\bigr)

produces terms of the form $\prod_{i\in B}T_{i}\alpha_{i}(j)$ for subsets $B\subseteq[r]$ . Therefore

\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}(1+T_{i}\alpha_{i}(j))=\sum_{B\subseteq[r]}% \Bigl(\prod_{i\in B}T_{i}\Bigr)\Bigl(\sum_{j=1}^{t}b_{j}\prod_{i\in B}\alpha_{% i}(j)\Bigr).

By the vanishing property established above, every inner sum with $B\neq\emptyset$ equals zero, while for $B=\emptyset$ we get $\sum_{j=1}^{t}b_{j}\neq 0$ . This proves the polynomial identity

\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}(1+T_{i}\alpha_{i}(j))=\sum_{j=1}^{t}b_{j}.

If $r\geq t$ , we may choose $T_{i}=-1/\alpha_{i}(i)$ for $1\leq i\leq t$ . With this choice, each term in the left-hand side vanishes, so the entire left-hand side equals $0$ , while the right-hand side is nonzero. This yields a contradiction. $\hfill\blacktriangleleft$

Second lower bound

We again use Lemma 12 and Example 13, but this time in combination with a counting argument, to derive a multiplicative lower bound.

Theorem 14.

Let

f:\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}\;\to\;\mathbb{F}

be a delta function on $\{0,1\}^{r}\subseteq\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{r}}$ , where $m_{1},\dots,m_{r}$ are (not necessarily distinct) positive integers. Then

|Supp(\widehat{f})|\;\geq\;\prod_{i=1}^{r}\frac{m_{i}}{\,m_{i}-1\,}.

Proof.

By Lemma 12 and Example 13, we have

Supp(\widehat{f})+B=\prod_{i=1}^{r}\{0,1,\dots,m_{i}-1\},\qquad B:=\prod_{i=1}% ^{r}\{1,\dots,m_{i}-1\}.

Since $A+B$ has size at most $|A|\cdot|B|$ for any sets $A, B$ , we obtain

|Supp(\widehat{f})|\;\geq\;\frac{|Supp(\widehat{f})+B|}{|B|}.

Here $|Supp(\widehat{f})+B|=\prod_{i=1}^{r}m_{i}$ , while $|B|=\prod_{i=1}^{r}(m_{i}-1)$ . Therefore

|Supp(\widehat{f})|\;\geq\;\frac{\prod_{i=1}^{r}m_{i}}{\prod_{i=1}^{r}(m_{i}-1% )}=\prod_{i=1}^{r}\frac{m_{i}}{m_{i}-1}.\

$\hfill\blacktriangleleft$

Corollary 15.

If $f:\mathbb{Z}_{m}^{r}\rightarrow\mathbb{F}$ is delta on $\{0,1\}^{r}$ , then:

(i)

$|Supp(\widehat{f})|\geq r+1$
(ii)

$|Supp(\widehat{f})|\geq(\frac{m}{m-1})^{r}$

Upper bound

We next study upper bounds for the Fourier sparsity of delta functions on $\{0,1\}^{r}$ . The following construction illustrates how to achieve small support when $m>r$ , and will serve as a building block for further results in this section.

Lemma 16.

Let $m>r$ and let $\omega\in\mathbb{F}$ be an $m$ -th root of unity. Then there exists a function

f:\mathbb{Z}_{m}^{r}\;\to\;\mathbb{F}

which is a delta function on $\{0,1\}^{r}\subseteq\mathbb{Z}_{m}^{r}$ and has exactly $r+1$ nonzero Fourier coefficients.

Proof.

Define

f(x_{1},\dots,x_{r})\;=\;\prod_{i=1}^{r}\bigl(\,\omega^{\,x_{1}+\cdots+x_{r}}-% \omega^{i}\bigr).

We first check the delta property. For any $x\in\{0,1\}^{r}\setminus\{0\}$ we have $1\leq x_{1}+\cdots+x_{r}\leq r$ , hence one of the factors vanishes, and thus $f(x)=0$ . On the other hand, $f(0,\dots,0)=\prod_{i=1}^{r}(1-\omega^{i})\neq 0$ . Therefore $f$ is indeed a delta function on $\{0,1\}^{r}$ .

Finally, observe that $f$ can be expressed as a linear combination of the $r+1$ characters

\psi_{(i,\dots,i)}(x_{1},\dots,x_{r})\;=\;\omega^{\,i(x_{1}+\cdots+x_{r})},% \qquad 0\leq i\leq r.

Thus $f$ has exactly $r+1$ nonzero Fourier coefficients, as claimed. $\hfill\blacktriangleleft$

Corollary 17.

When $m>r$ , the above claim gives a construction of a delta function with Fourier sparsity $r+1$ . By Corollary 15, we also have the lower bound $r+1$ . Thus, in this case, the upper and lower bounds coincide, yielding a tight result.

Theorem 18.

Suppose $m-1$ divides $r$ . Then, there exists a function

f:\mathbb{Z}_{m}^{r}\;\to\;\mathbb{F}

which is a delta function on $\{0,1\}^{r}$ and satisfies

|Supp(\widehat{f})|\;\leq\;m^{\,\tfrac{r}{m-1}}.

Proof.

Partition the index set $\{1,\dots,r\}$ into

\ell\;=\;\frac{r}{m-1}

disjoint subsets, denoted $A_{1},\dots,A_{\ell}$ , each of size $m-1$ . For each $1\leq k\leq\ell$ , define a function $f_{k}$ depending only on the coordinates indexed by $A_{k}$ , as in Lemma 16:

f_{k}\bigl((x_{j})_{j\in A_{k}}\bigr)\;=\;\prod_{i=1}^{m-1}\Bigl(\,\omega^{% \sum_{j\in A_{k}}x_{j}}-\omega^{i}\Bigr),

where $\omega$ is a fixed primitive $m$ -th root of unity. By Lemma 16, each $f_{k}$ is delta on $\{0,1\}^{A_{k}}$ and satisfies

|Supp(\widehat{f_{k}})|\;=\;m.

Now define the overall function

f(x_{1},\dots,x_{r})\;=\;\prod_{k=1}^{\ell}f_{k}\bigl((x_{j})_{j\in A_{k}}% \bigr).

Clearly, $f$ is delta on $\{0,1\}^{r}$ . Applying Corollary 9 , we obtain

|Supp(\widehat{f})|\;\leq\;\prod_{k=1}^{\ell}|Supp(\widehat{f_{k}})|\;=\;m^{% \ell}\;=\;m^{\,\tfrac{r}{m-1}}.\

$\hfill\blacktriangleleft$

3.3 Bounds for Delta Functions on $\{-1,0,1\}^{r}$

We now turn to delta functions on $\{-1,0,1\}^{r}$ . Using a general structural claim, we derive lower bounds on their Fourier sparsity. In particular, we show that such functions must have support size at least $2^{r}$ .

Claim 19.

Let $f:G\to\mathbb{F}$ be a delta function on a set $B\subseteq G$ with $0\in B$ . Suppose $D\subseteq B$ is such

D-D\subseteq B,

where $D-D$ is the difference set $\{d_{1}-d_{2}\mid d_{1},d_{2}\in D\}$ . Then

|Supp(\widehat{f})|\;\geq\;|D|.

Proof.

Write $f$ as a linear combination of characters supported on some set $T\subseteq\widehat{G}$ :

f(x)\;=\;\sum_{a\in T}c_{a}\psi_{a}(x).

For $d\in G$ , define the translate $f_{d}:G\to\mathbb{F}$ by:

f_{d}(x):=f(x-d).

Then we compute the Fourier expansion of $f_{d}$ as follows:

f_{d}(x)=\sum_{a\in T}c_{a}\psi_{a}(x-d)=\sum_{a\in T}\left(c_{a}\psi^{-1}_{a}% (d)\right)\psi_{a}(x),

and thus:

f_{d}\in Span\{\psi_{a}:a\in T\}.

We now show that the functions $\{f_{d}:d\in D\}$ are all linearly independent. Enumerate $D=\{d_{1},\dots,d_{|D|}\}$ . For each $d\in D$ , consider the evaluation vector

v_{d}:=\bigl(f_{d}(d_{1}),\dots,f_{d}(d_{|D|})\bigr)\;\in\;\mathbb{F}^{|D|}.

By construction,

f_{d}(d_{i})=f(d-d_{i}).

If $d\neq d_{i}$ , then $d-d_{i}\in B\setminus\{0\}$ , so $f(d-d_{i})=0$ . If $d=d_{i}$ , then $f_{d}(d_{i})=f(0)\neq 0$ . Thus $v_{d}$ is a nonzero scalar multiple of the $i$ -th standard basis vector $e_{i}$ . Hence the vectors $\{v_{d}:d\in D\}$ are linearly independent.

Therefore, the functions $\{f_{d}:d\in D\}$ are linearly independent, all lying inside $Span\{\psi_{a}:a\in T\}$ . It follows that

|T|\;\geq\;|D|.

Finally, since $T=Supp(\widehat{f})$ , we conclude that $|Supp(\widehat{f})|\geq|D|$ , as claimed. $\hfill\vartriangleleft$

Corollary 20.

If $f:\mathbb{Z}_{m_{1}}\times...\times\mathbb{Z}_{m_{r}}\rightarrow\mathbb{F}$ is delta on $\{-1,0,1\}^{r}$ , then we have:

|Supp(\widehat{f})|\geq 2^{r}

Proof.

Apply the previous claim with $B=\{-1,0,1\}^{r}$ and $D=\{0,1\}^{r}$ . For distinct $d_{1},d_{2}\in D$ , the difference $d_{1}-d_{2}$ lies in $B\setminus\{0\}$ , so the conditions of the claim are satisfied. Since $|D|=2^{r}$ , the result follows. $\hfill\blacktriangleleft$

4 From Fourier Sparsity to Matching Vector PIRs

In this section, we first establish the connections between the Fourier sparsity of delta functions and $S$ -decoding polynomials. We then recall how the sparsity of $S$ -decoding polynomials is related to Matching vector PIRs. Combining this with our results from the previous section we derive new bounds on the number of servers required in such PIR schemes.

4.1 Fourier Sparsity and $𝑺$ -decoding Polynomials

For Matching Vector PIRs, there are two key ingredients: a large $S$ -matching vector family in $\mathbb{Z}_{m}^{k}$ , and a sparse $S$ -decoding polynomial, where $S\subseteq\mathbb{Z}_{m}$ .

For all the superpolynomially large $S$ -matching vector families that we know³³3They all come from the Barrington-Biegel-Rudich method involving the Chinese remainder theorem., $S$ has to have a special form: it must essentially be a canonical set for $m$ , defined below⁴⁴4More precisely, $S$ must contain a product set of the form $S_{1}\times S_{2}\ldots\times S_{r}$ , where $\S_{i}\subseteq\mathbb{Z}_{p_{i}}$ has size at least $2$ , and $\mathbb{Z}_{m}$ is viewed as $\prod_{i}\mathbb{Z}_{p_{i}}$ for distinct primes $p_{1},\ldots,p_{r}$ . $S$ -decoding polynomials for such $S$ easily translate into $S$ -decoding polynomials for the canonical $S$ ..

Definition 21 (Canonical set).

Let $m\in\mathbb{Z}$ be a positive integer. We define the canonical set for $m$ to be the following set:

S=\{x\in\mathbb{Z}_{m}\ s.t.\ x^{2}\equiv x\ mod\ m\}

Note that when $m=p_{1}\cdot\cdot\cdot p_{r}$ is a product of $r$ distinct primes, the canonical set consists of the following $2^{r}$ values:

S=\{s\in\mathbb{Z}_{m},\forall p_{i}\ s\ mod\ p_{i}\in\{0,1\}\}

For example, for $m=6$ we get:

S=\{0,1,3,4\}

which are precisely the four values being $0$ or $1$ mod $2,3$ .

Definition 22 ( $t$ -sparse $S$ -decoding polynomial).

Let $S\subseteq\mathbb{Z}_{m}$ be a set containing $0$ , $\mathbb{F}$ be a field containing an element $\gamma_{m}$ which is a primitive $m$ -th root of $1$ : namely $\gamma_{m}^{m}=1$ and $\gamma_{m}^{i}\neq 1$ for $i=1,2,...,m-1$ .

A polynomial $P(Z)\in\mathbb{F}[Z]$ is called an $t$ -sparse $S$ -decoding polynomial if $P$ has $t$ monomials, and the following conditions hold:

$\blacksquare$

$\forall s\in S\setminus\{0\}:\ P(\gamma_{m}^{s})=0$
$\blacksquare$

$P(\gamma_{m}^{0})=P(1)=1$

For $m=p_{1}\times...\times p_{r}$ , for distinct primes $p_{1},...,p_{r}$ , we use $\phi$ to denote the Chinese remainder isomorphism:

\phi:\mathbb{Z}_{m}\rightarrow\mathbb{Z}_{p_{1}}\times...\times\mathbb{Z}_{p_{% r}}

\phi(a)=(a(1),...,a(r)),\ a(i)=a\ mod\ p_{i}

Also, we use $\phi(a)_{i}$ to denote $a(i)=a\ mod\ p_{i}$ .

The next claim shows the relation between Fourier sparsity and $S$ -decoding polynomials for canonical sets $S$ .

Claim 23.

Let $m=p_{1}...p_{r}$ be a product of $r$ distinct primes and $S$ be the canonical set for $m$ , $\mathbb{F}$ be a field containing an $m$ -th root of unity. Then, having a $t$ -sparse $S$ -decoding polynomial in $\mathbb{F}[Z]$ is equivalent to having a function:

f:\mathbb{Z}_{p_{1}}\times...\times\mathbb{Z}_{p_{r}}\rightarrow\mathbb{F}

such that

f|_{\{0,1\}^{r}}

is a delta function, $|Supp(\widehat{f})|=t.$

Proof.

Let $P(Z)\in\mathbb{F}[Z]$ be an $S$ -decoding polynomial,

P(Z)=\sum_{j=1}^{t}b_{j}Z^{a_{j}}

Let $\gamma_{m}\in\mathbb{F}$ be a primitive $m$ -th root of unity. Then, since $p_{i}$ ’s are pairwise coprime, we can write it as:

\gamma_{m}=\prod_{i=1}^{r}\omega_{p_{i}}

for $\omega_{p_{i}}\in\mathbb{F}$ , $1\leq i\leq r$ , with each $\omega_{p_{i}}$ a primitive $p_{i}$ -th root of unity. Therefore,

\gamma_{m}^{s}=(\prod_{i=1}^{r}\omega_{p_{i}})^{s}=\prod_{i=1}^{r}\omega_{p_{i% }}^{\phi(s)_{i}}

Observe that:

P(\gamma_{m}^{s})=0\iff\sum_{j=1}^{t}b_{j}(\prod_{i=1}^{r}\omega_{p_{i}}^{\phi% (s)_{i}})^{a_{j}}=0\iff\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}\omega_{p_{i}}^{\phi(% a_{j})_{i}\cdot\phi(s)_{i}}=0

Now note that

S=\{s\in\mathbb{Z}_{m}:s\ mod\ p_{i}\in\{0,1\}\}=\{s\in\mathbb{Z}_{m}:\phi(s)% \in\{0,1\}^{r}\}

Hence, having such an $S$ -decoding polynomial is equivalent to constructing a function $f$ such that:

f(x_{1},...,x_{r})=\sum_{j=1}^{t}b_{j}\prod_{i=1}^{r}\omega_{p_{i}}^{a_{j}(i)x% _{i}},

and:

f|_{(\phi(S)\setminus\{0\})}=0,

f(0)\neq 0.

By Lemma 7, $\prod_{i=1}^{r}\omega_{p_{i}}^{a_{j}(i)x_{i}}=\psi_{a_{j}}(x)$ , and so the above expression for $f$ equals:

f(x)=\sum_{j=1}^{t}b_{j}\psi_{a_{j}}(x).

Thus having such an $S$ -decoding polynomial is exactly equivalent to having a function $f:\mathbb{Z}_{m}\cong\mathbb{Z}_{p_{1}}\times...\times\mathbb{Z}_{p_{r}}% \rightarrow\mathbb{F}$ such that $f|_{\phi(S)}$ is delta and $|Supp(\widehat{f})|=|\{b_{j}:j\in[t]\}|=t$ . $\hfill\vartriangleleft$

By applying Theorem 11 to the above claim, we obtain the following corollary:

Corollary 24.

Let $m=p_{1}\times...\times p_{r}$ , $S$ be the canonical set for $m$ , $P(Z)\in\mathbb{F}[Z]$ be an $S$ -decoding polynomial. Then, the number of monomials of $P$ is at least $r+1$ .

4.2 Applications to Matching Vector PIRs

We now discuss the relationship between $S$ -decoding polynomials and Matching Vector based PIRs.

Definition 25 ( $S$ -Matching Vector Family).

Let $S\subset\mathbb{Z}_{m},0\in S$ and $\mathcal{F}=\left(\mathcal{U},\mathcal{V}\right)$ where $\mathcal{U}=\left(u_{1},...,u_{n}\right),\mathcal{V}=\left(u_{1},...,u_{n}\right)$ with $u_{i},v_{i}\in\mathbb{Z}_{m}^{k}$ . Then $\mathcal{F}$ is said to be an $S$ -matching vector family of size $n$ and dimension $k$ if the following conditions hold:

$\blacksquare$

$\langle u_{i},v_{i}\rangle=0$ for every $i\in[n]$
$\blacksquare$

$\langle u_{i},v_{j}\rangle\in S\setminus\{0\}$ for every $i\neq j$

The connection between decoding polynomials and matching vector PIR schemes is made explicit by the following result:

Theorem 26 (Theorem 2.3 in [10]).

Let $m$ be a positive integer with $r$ distinct prime factors, and let $p$ be a prime not dividing $m$ . Set $M=mp$ , and let

\mathcal{F}=(\mathcal{U},\mathcal{V})

be an $S_{M}$ -matching vector family over $\mathbb{Z}_{M}$ of size $n$ and dimension $k$ , where $S_{M}$ denotes the canonical set for $\mathbb{Z}_{M}$ .

Suppose $\mathbb{F}$ is a field of characteristic $p$ such that, for the canonical set $S_{m}\subseteq\mathbb{Z}_{m}$ , there exists an $S_{m}$ -decoding polynomial over $\mathbb{F}$ with sparsity $t$ .

Then there exists a $t$ -server PIR scheme with communication complexity $O(k)$ .

The above theorem highlights the role of $S$ -decoding polynomials in such PIR schemes. In particular, designing sparser $S$ -decoding polynomials leads directly to improved PIR constructions: The same communication complexity can be achieved with fewer servers. In other words, the sparsity of decoding polynomials dictates the number of servers required.

Theorem 27 gives the best known construction of large matching vector families, where the set $S$ is taken to be the canonical set.

Theorem 27 (Large Matching Vector Families, Theorem 1.4 in [11]).

Let $m=p_{1}p_{2}...p_{r}$ where $p_{1},p_{2},...,p_{r}$ are distinct primes and $r\geq 2$ . Then, there exists an explicitly constructible $S$ -matching vector family $\mathcal{F}$ in $\mathbb{Z}_{m}^{k}$ of size $n\geq exp\left(\Omega\left(\frac{(log\ k)^{r}}{(log\ log\ k)^{r-1}}\right)\right)$ where $S$ is the canonical set for $m$ .

Combining this with Theorem 26, we obtain that any $S$ -decoding polynomial for the canonical set directly yields a PIR scheme with parameters determined by the sparsity of the polynomial. In particular, a $t$ -sparse decoding polynomial for the canonical $S$ gives rise to a $t$ -server PIR scheme with communication complexity $\exp(\tilde{O}((\log n)^{\frac{1}{r+1}}))$ and database size $n$ .

For the canonical set $S\subseteq\mathbb{Z}_{m}$ , Corollary 24 shows that every $S$ -decoding polynomial has sparsity at least $r+1$ . Consequently, the Matching Vector PIR scheme based on the above matching vector family requires at least $r+1$ servers.

Stating this another way, the communication complexity of a $t$ server Matching Vector PIR scheme based on the this matching vector family and an arbitrary $S$ -decoding polynomial is bounded below by

\exp\!\left(\bigl((\log n)^{1/t}\bigr)\right).

Hence these PIR schemes cannot achieve polylogarithmic communication with a constant number of servers merely by improving the $S$ -decoding polynomials.

It would be extremely interesting to find $S$ -decoding polynomials matching this sparsity bound. Today, the best known sparsity comes from the results of [4], and is approximately is $(\sqrt{3})^{r}$ under a plausible number theoretic hypothesis.

References

[1] Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, and Sidhant Saraogi. Improved lower bounds for 3-query matching vector codes. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 of LIPIcs, pages 2:1–2:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ITCS.2025.2.
[2] David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Comput. Complex., 4:367–382, 1994. doi:10.1007/BF01263424.
[3] Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett. New bounds for matching vector families. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 823–832, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488713.
[4] Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, and Liang Feng Zhang. Query-Efficient Locally Decodable Codes of Subexponential Length. Computational Complexity, 22:159–189, 2013. doi:10.1007/S00037-011-0017-1.
[5] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. Journal of the ACM, 45:965–981, 1998. doi:10.1145/293347.293350.
[6] David L. Donoho and Philip B. Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 49(3):906–931, 1989. doi:10.1137/0149053.
[7] Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching Vector Codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 705–714. IEEE, 2010. doi:10.1109/FOCS.2010.73.
[8] Zeev Dvir and Sivakanth Gopi. 2-Server PIR with Sub-Polynomial Communication. In STOC ’15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 577–584. Association for Computing Machinery, 2015. doi:10.1145/2746539.2746546.
[9] Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC ’09: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 39–44. Association for Computing Machinery, 2009. doi:10.1145/1536414.1536422.
[10] Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan. Improved pir schemes using matching vectors and derivatives. In STOC ’25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1648–1656, 2025. doi:10.1145/3717823.3718313.
[11] Vince Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica, 20:71–86, 2000. doi:10.1007/S004930070032.
[12] Toshiya Itoh and Yasuhiro Suzuki. Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length. IEICE Trans. Inf. Syst., 93-D:263–270, 2008.
[13] Roy Meshulam. An uncertainty inequality for finite abelian groups. European Journal of Combinatorics, 27(1):63–67, 2006. doi:10.1016/j.ejc.2005.01.004.
[14] Prasad Raghavendra. A Note on Yekhanin’s Locally Decodable Codes. Electron. Colloquium Comput. Complex., TR07, 2007. URL: https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-016/index.html.
[15] Walter Rudin. Real and Complex Analysis. McGraw-Hill, New York, 3 edition, 1987.
[16] Terence Tao. An uncertainty principle for cyclic groups of prime order. Mathematical Research Letters, 12(1):121–127, 2005. doi:10.4310/MRL.2005.v12.n1.a10.
[17] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008. doi:10.1145/1326554.1326555.

Appendix A A more sensitive lower bound

Define $F(m_{1},\ldots,m_{r})$ to be the smallest size of a subset $S\subseteq\prod_{i}\mathbb{Z}_{m_{i}}$ such that:

S+\prod_{i}(\mathbb{Z}_{m_{i}}\setminus\{0\})=\prod_{i}\mathbb{Z}_{m_{i}}.

Our proof in Section 3 actually shows that this quantity is a lower bound on the Fourier sparsity of delta functions on $\{0,1\}^{r}\subseteq\prod_{i}\mathbb{Z}_{m_{i}}$ . It is a common generalization of the bounds $r+1$ and $\prod_{i}\frac{m_{i}}{m_{i}-1}$ . Here we note a simple recursive inequality for it that is stronger than both the above bounds. It implies, for example, that when $r=2m$ , that the Fourier sparsity of delta functions on $\mathbb{Z}_{m}^{r}$ is at least $\approx e\cdot m$ (while the best upper bound we know for this case is that there exist delta functions with Fourier sparsity $\leq m^{2}$ ).

Lemma 28.

F(m_{1},\ldots,m_{r})\geq\lceil\frac{m_{r}}{m_{r}-1}F(m_{1},\ldots,m_{r-1})\rceil.

In particular, we have

F(m_{1},\ldots,m_{r})\geq\max\left(F(m_{1},\ldots,m_{r-1})+1,\frac{m_{r}}{m_{r% }-1}F(m_{1},\ldots,m_{r-1})\right),

and

F(m,m,\ldots,m)\geq\begin{cases}r+1&r\leq m-1\\ m\cdot\left(\frac{m}{m-1}\right)^{r-m+1}&r\geq m\end{cases}

Proof.

Let $G=\prod_{i}\mathbb{Z}_{m_{i}}$ . Let $H=\prod_{i}(\mathbb{Z}_{m_{i}}\setminus\{0\})$ . Suppose $S\subseteq G$ is such that $S+H=G$ .

For $x\in\mathbb{Z}_{m}$ , let $S_{x}$ be the set of all $v\in S$ with $v_{r}=x$ . Choose $x$ with $|S_{x}|$ as large as possible: then $|S_{x}|\geq\frac{1}{m_{r}}|S|$ .

Observe that for any $v\in S_{x}$ and any $w\in v+H$ , we have $w_{r}\neq x$ .

Thus:

\left((S\setminus S_{x})+H\right)\supseteq\left(\prod_{i<r}\mathbb{Z}_{m_{i}}% \right)\times\{x\}.

Projecting to the first $r-1$ coordinates, we see that the projection $S^{\prime}$ of $S\setminus S_{x}$ to the first $r-1$ coordinates satisfies:

S^{\prime}+\prod_{i<r}(\mathbb{Z}_{m_{i}}\setminus\{0\})=\prod_{i<r}\mathbb{Z}% _{m_{i}}.

Thus $|S^{\prime}|\geq F(m_{1},\ldots,m_{r-1})$ . Combined with the inequality:

|S^{\prime}|\leq|S\setminus S_{x}|=|S|-|S_{x}|\leq\frac{m_{r}-1}{m_{r}}|S|,

we get the result. $\hfill\blacktriangleleft$

In fact, the proof even shows that

F(m_{1},\ldots,m_{r-1})\leq F(m_{1},\ldots,m_{r})-\left\lceil\frac{1}{m_{r}}F(% m_{1},\ldots,m_{r})\right\rceil

(since in the notation of the proof, we get $|S^{\prime}|\leq|S|-\lceil\frac{1}{m_{r}}|S|\rceil$ ).

Appendix B Covering the cube by affine hyperplanes over $\mathbb{F}_{p}$

A classical result of Alon and Furedi shows that any set $H$ of affine hyperplanes in $\mathbb{R}^{r}$ that cover all but one of the points of the Boolean hypercube must have size at least $r$ . Specifically, if the hyperplanes of $H$ cover $\left(\{0,1\}^{r}\setminus\{0\}\right)\subseteq\mathbb{R}^{r}$ using affine hyperplanes, none of which contain $0$ , then $|H|\geq r$ .

Our results imply something nontrivial about the analogous covering question for $\left(\{0,1\}^{r}\setminus\{0\}\right)\subseteq\mathbb{F}_{p}^{r}$ for a prime $p$ . Specifically, we show that if $H$ is a set of hyperplanes, and:

H=H_{1}\cup H_{2}\ldots H_{t}

is the partition of $H$ into subsets of parallel hyperplanes, then:

\prod_{i}(|H_{i}|+1)\geq\max\left(r+1,\left(\frac{p}{p-1}\right)^{r}\right).

On the other hand, there exist such sets $H_{i}$ with

\prod_{i}(|H_{i}|+1)\leq\left(p^{1/(p-1)}\right)^{r}

We now prove the lower bound. If $W$ is a set of $w$ parallel hyperplanes, then there is a function $f_{W}:\mathbb{F}_{p}^{r}\to\mathbb{C}$ with Fourier sparsity $w+1$ and which vanishes exactly on the union of those hyperplanes. Taking the product of $f_{H_{i}}$ over all the $i$ and scaling by a constant, we get a delta function with Fourier sparsity $\prod_{i}(|H_{i}|+1)$ . Then our Theorem 2 implies the result.

The upper bound follows by observing that the Fourier sparse function constructed in Claim 18 is of the above form.

Appendix C Sparsity of delta functions on $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ over $\mathbb{C}$

In this appendix we consider the special case of delta functions on $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ over the complex numbers. We show that when $m_{1}$ and $m_{2}$ are coprime, there is no $\mathbb{C}$ -valued delta function on $\{0,1\}^{2}\subseteq G$ with Fourier sparsity $\leq 3$ , and thus the minimum Fourier sparsity of such a function is $4$ . The argument uses complex-analytic tools.

By [9, 12, 4], there are some $G$ of the form $\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ (with $m_{1},m_{2}$ coprime and odd) for which there exists a delta function $f:G\to\overline{\mathbb{F}}_{2}$ (the algebraic closure of $\mathbb{F}_{2}$ ) with Fourier sparsity $3$ . Thus our result needs to use some special property of complex numbers.

In brief, we express the property of being a delta function on $G$ in terms of vanishing of multilinear polynomials $P(X,Y)$ at roots of unity. Vanishing of the multilinear polynomial $P(X,Y)$ can be expressed in terms of an associated Möbius transformation $Y=A_{P}(X)$ . Finally, we use properties of Möbius transformations on the unit disk in $\mathbb{C}$ to get the result.

Proposition 29.

Let $m_{1},m_{2}$ be coprime positive integers and let $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ . Suppose $f:G\to\mathbb{C}$ is a function that is delta on $\{0,1\}^{2}$ , i.e.

f(0,0)=1,\qquad f(1,0)=f(0,1)=f(1,1)=0.

Then the Fourier sparsity of $f$ is at least $4$ .

Proof.

Write $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ and fix primitive $m_{1}$ -th and $m_{2}$ -th roots of unity $\omega_{m_{1}},\omega_{m_{2}}\in\mathbb{C}$ . Characters of $G$ have the form

\psi_{(a,b)}(x,y)\;=\;\omega_{m_{1}}^{ax}\,\omega_{m_{2}}^{by},\qquad(a,b)\in% \mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}.

Assume for contradiction that $f$ is a delta function on $\{0,1\}^{2}$ with Fourier sparsity at most $3$ . Assume that $f$ has a Fourier expansion of the form

f(x,y)\;=\;c_{1}\psi_{(a_{1},b_{1})}(x,y)+c_{2}\psi_{(a_{2},b_{2})}(x,y)+c_{3}% \psi_{(a_{3},b_{3})}(x,y),

with $(a_{i},b_{i})$ pairwise distinct and $c_{1},c_{2},c_{3}\in\mathbb{C}$ . Since $f(0,0)=1$ , not all the $c_{i}$ are zero.

Set

\alpha_{i}:=\omega_{m_{1}}^{a_{i}},\qquad\beta_{i}:=\omega_{m_{2}}^{b_{i}}% \quad(i=1,2,3),

so that each $\alpha_{i}$ is an $m_{1}$ -th root of unity and each $\beta_{i}$ is an $m_{2}$ -th root of unity. The values of the three characters at the four points $(0,0),(1,0),(0,1),(1,1)$ are:

\psi_{(a_{i},b_{i})}(0,0)=1,\quad\psi_{(a_{i},b_{i})}(1,0)=\alpha_{i},\quad% \psi_{(a_{i},b_{i})}(0,1)=\beta_{i},\quad\psi_{(a_{i},b_{i})}(1,1)=\alpha_{i}% \beta_{i}.

Thus, if we form the $4\times 3$ matrix

M\;=\;\begin{pmatrix}1&1&1\\ \alpha_{1}&\alpha_{2}&\alpha_{3}\\ \beta_{1}&\beta_{2}&\beta_{3}\\ \alpha_{1}\beta_{1}&\alpha_{2}\beta_{2}&\alpha_{3}\beta_{3}\end{pmatrix},

the $i$ -th column of $M$ is the column vector of values of $\psi_{(a_{i},b_{i})}$ on $\{0,1\}^{2}$ .

The vector of values of $f$ on $\{0,1\}^{2}$ is then

Mc\;=\;\begin{pmatrix}1\\ 0\\ 0\\ 0\end{pmatrix},\qquad\mbox{ where }c:=\begin{pmatrix}c_{1}\\ c_{2}\\ c_{3}\end{pmatrix}

In other words, the existence of a $3$ -sparse delta function with these three characters is equivalent to the statement that

e_{1}:=\begin{pmatrix}1\\ 0\\ 0\\ 0\end{pmatrix}

lies in the column space of $M$ .

By elementary linear algebra, $e_{1}$ lies in the column space of $M$ if and only if every row vector $v\in\mathbb{C}^{4}$ that is orthogonal to all the columns of $M$ is also orthogonal to $e_{1}$ , i.e.

v\cdot M=0\;\Rightarrow\;v\cdot e_{1}=0.

We now interpret such row vectors $v$ in terms of multilinear polynomials evaluated at the $(\alpha_{i},\beta_{i})$ . Write

v=(v_{1},v_{X},v_{Y},v_{XY})\in\mathbb{C}^{4}

and associate to $v$ the multilinear polynomial

P_{v}(X,Y)\;=\;v_{1}+v_{X}X+v_{Y}Y+v_{XY}XY.

Observe that for $i=1,2,3$ we have

v\cdot\text{(column $i$ of $M$)}\;=\;P_{v}(\alpha_{i},\beta_{i}).

Thus $v\cdot M=0$ is equivalent to

P_{v}(\alpha_{1},\beta_{1})=P_{v}(\alpha_{2},\beta_{2})=P_{v}(\alpha_{3},\beta% _{3})=0.

On the other hand

v\cdot e_{1}=v_{1}=P_{v}(0,0).

We conclude that the existence of a $(\leq 3)$ -sparse delta function with support $\{\psi_{(a_{i},b_{i})}\}_{i=1}^{3}$ is equivalent to the following statement:

Every multilinear polynomial $P(X,Y)$ that vanishes at the three points $(\alpha_{i},\beta_{i})$ , $i=1,2,3$ , must also vanish at $(0,0)$ .

We now show that this statement is false.

Lemma 30.

Let $m_{1},m_{2}$ be relatively prime integers. Let $\alpha_{1},\alpha_{2},\alpha_{3}\in\mathbb{C}$ be $m_{1}$ -th roots of $1$ , and $\beta_{1},\beta_{2},\beta_{3}\in\mathbb{C}$ be $m_{2}$ -th roots of $1$ .

Then there exists a multilinear polynomial $P(X,Y)$ such that: $P(\alpha_{i},\beta_{i})=0$ for each $i$ , and $P(0,0)\neq 0$ .

Proof.

We take cases on whether the $\alpha_{i}$ and $\beta_{i}$ are all distinct or not.

$\blacksquare$

Case 1: Some two (or more) of the $\alpha_{i}$ are equal. Without loss of generality, assume $\alpha_{1}=\alpha_{2}$ . Then $P(X,Y)=(X-\alpha_{1})(Y-\beta_{3})$ is a multilinear polynomial that vanishes at all the $(\alpha_{i},\beta_{i})$ and is nonzero at $(0,0)$ .
$\blacksquare$

Case 2: Some two (or more) of the $\beta_{i}$ are equal. Without loss of generality, assume $\beta_{1}=\beta_{2}$ . Then $P(X,Y)=(X-\alpha_{3})(Y-\beta_{1})$ is a multilinear polynomial that vanishes at all the $(\alpha_{i},\beta_{i})$ and is nonzero at $(0,0)$ .
$\blacksquare$

Case 3: All the $\alpha_{i}$ are distinct and all the $\beta_{i}$ are distinct. In this case, we use the basic fact that Möbius transformations can take any $3$ distinct points to any $3$ distinct points. Thus, there is a Möbius transformation

$A(X)=-\frac{v_{1}+v_{X}X}{v_{Y}+v_{XY}X}$

with $A(\alpha_{i})=\beta_{i}$ for each $i$ . Rearranging this, we get that for the multilinear polynomial $P(X,Y)$ given by:

$\displaystyle P(X,Y)=v_{1}+v_{X}X+v_{Y}Y+v_{XY}XY$ (1)

satisfies, for each $i$ :

$P(\alpha_{i},\beta_{i})=0.$
We now prove that $P(0,0)$ is nonzero. This is equivalent to showing that $A(0)\neq 0$ . Suppose not; namely suppose $A(0)=0$ . Then the map $A:\mathbb{C}\to\mathbb{C}$ satsifies:
- –
  
  $A(\alpha_{i})=\beta_{i}$ for each $i$ . In particular, since all $\alpha_{i}$ are distinct, all $\beta_{i}$ are distinct, they lie on the unit circle $|z|=1$ , and Möbius transformations take circles to circles, we get that $A$ maps the unit circle to itself.
- –
  
  $A(0)=0$ .
- –
  
  Thus $A$ maps the open unit disc $\mathbf{D}=\{z\mid|z|<1\}$ to itself.
It is well known [15, Chapter 12] that Möbius transformations mapping $\mathbf{D}$ to $\mathbf{D}$ are of the form:

$A(z)=\frac{az-\bar{b}}{bz-\bar{a}}.$

If in addition we have $A(0)=0$ , then we get:

$0=A(0)=\frac{-\bar{b}}{-\bar{a}},$

which means that $b=0$ . Thus $A(z)$ is of the form

$A(z)=\lambda z,$

for some $\lambda=\frac{a}{-\bar{a}}\in\mathbb{C}$ .

Now $A(\alpha_{i})=\beta_{i}$ for $i=1,2,3$ implies $\beta_{i}=\lambda\alpha_{i}$ . In particular, for any $i\neq j$ ,

$\frac{\beta_{i}}{\beta_{j}}=\frac{\lambda\alpha_{i}}{\lambda\alpha_{j}}=\frac{% \alpha_{i}}{\alpha_{j}}.$

The left-hand side is an $m_{2}$ -th root of unity, and the right-hand side is an $m_{1}$ -th root of unity. Since $\gcd(m_{1},m_{2})=1$ , the only complex number that is simultaneously an $m_{1}$ -th and an $m_{2}$ -th root of unity is $1$ . So we must have $\beta_{i}/\beta_{j}=1$ and hence $\beta_{i}=\beta_{j}$ , contradicting the fact that we are in the case where the $\beta_{i}$ are all distinct.

Thus our assumption that $P(0,0)=0$ is wrong, and we conclude that the multilinear polynomial $P(X,Y)$ specified by Equation (1) is as desired.

This concludes the proof of Lemma 30. $\hfill\blacktriangleleft$

By the discussion preceding Lemma 30, we conclude that there are no delta functions on $G$ with Fourier sparsity $\leq 3$ . $\hfill\blacktriangleleft$

[bib.bib1] [1] Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, and Sidhant Saraogi. Improved lower bounds for 3-query matching vector codes. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 of LIPIcs, pages 2:1–2:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ITCS.2025.2.

[bib.bib2] [2] David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Comput. Complex., 4:367–382, 1994. doi:10.1007/BF01263424.

[bib.bib3] [3] Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett. New bounds for matching vector families. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 823–832, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488713.

[bib.bib4] [4] Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, and Liang Feng Zhang. Query-Efficient Locally Decodable Codes of Subexponential Length. Computational Complexity, 22:159–189, 2013. doi:10.1007/S00037-011-0017-1.

[bib.bib5] [5] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. Journal of the ACM, 45:965–981, 1998. doi:10.1145/293347.293350.

[bib.bib6] [6] David L. Donoho and Philip B. Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 49(3):906–931, 1989. doi:10.1137/0149053.

[bib.bib7] [7] Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching Vector Codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 705–714. IEEE, 2010. doi:10.1109/FOCS.2010.73.

[bib.bib8] [8] Zeev Dvir and Sivakanth Gopi. 2-Server PIR with Sub-Polynomial Communication. In STOC ’15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 577–584. Association for Computing Machinery, 2015. doi:10.1145/2746539.2746546.

[bib.bib9] [9] Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC ’09: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 39–44. Association for Computing Machinery, 2009. doi:10.1145/1536414.1536422.

[bib.bib10] [10] Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan. Improved pir schemes using matching vectors and derivatives. In STOC ’25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1648–1656, 2025. doi:10.1145/3717823.3718313.

[bib.bib11] [11] Vince Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica, 20:71–86, 2000. doi:10.1007/S004930070032.

[bib.bib12] [12] Toshiya Itoh and Yasuhiro Suzuki. Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length. IEICE Trans. Inf. Syst., 93-D:263–270, 2008.

[bib.bib13] [13] Roy Meshulam. An uncertainty inequality for finite abelian groups. European Journal of Combinatorics, 27(1):63–67, 2006. doi:10.1016/j.ejc.2005.01.004.

[bib.bib14] [14] Prasad Raghavendra. A Note on Yekhanin’s Locally Decodable Codes. Electron. Colloquium Comput. Complex., TR07, 2007. URL: https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-016/index.html.

[bib.bib15] [15] Walter Rudin. Real and Complex Analysis. McGraw-Hill, New York, 3 edition, 1987.

[bib.bib16] [16] Terence Tao. An uncertainty principle for cyclic groups of prime order. Mathematical Research Letters, 12(1):121–127, 2005. doi:10.4310/MRL.2005.v12.n1.a10.

[bib.bib17] [17] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008. doi:10.1145/1326554.1326555.

Fourier Sparsity of Delta Functions and Matching Vector PIRs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Overview of Results

More general groups

Delta functions on {−𝟏,𝟎,𝟏}𝒓

Techniques

1.2 Matching Vector PIRs

1.3 Questions

2 Main Result

Definition 1.

Theorem 2.

Definition 3 (S-decoding polynomial for the canonical set S).

Theorem 4.

Theorem 5.

3 Bounds for Delta Functions

3.1 Basic Facts from Fourier Analysis

Definition 6 (Fourier transform over a finite abelian group, 𝔽-valued).

Lemma 7 (Character basis and explicit parametrization).

Lemma 8.

Corollary 9.

Lemma 10 (Fourier expansion of the total delta function).

3.2 Bounds for Delta Functions on the Boolean Hypercube

First lower bound

Theorem 11.

First proof (of the first lower bound)

Lemma 12.

Proof.

Example 13.

Proof of Theorem 11.

Second proof (of the first lower bound)

Proof.

Second lower bound

Theorem 14.

Proof.

Corollary 15.

Upper bound

Lemma 16.

Proof.

Corollary 17.

Theorem 18.

Proof.

3.3 Bounds for Delta Functions on {−𝟏,𝟎,𝟏}𝒓

Claim 19.

Proof.

Corollary 20.

Proof.

4 From Fourier Sparsity to Matching Vector PIRs

4.1 Fourier Sparsity and 𝑺-decoding Polynomials

Definition 21 (Canonical set).

Definition 22 (t-sparse S-decoding polynomial).

Claim 23.

Proof.

Corollary 24.

4.2 Applications to Matching Vector PIRs

Definition 25 (S-Matching Vector Family).

Theorem 26 (Theorem 2.3 in [10]).

Theorem 27 (Large Matching Vector Families, Theorem 1.4 in [11]).

References

Appendix A A more sensitive lower bound

Lemma 28.

Proof.

Appendix B Covering the cube by affine hyperplanes over 𝔽𝒑

Appendix C Sparsity of delta functions on 𝑮=ℤ𝒎𝟏×ℤ𝒎𝟐 over ℂ

Proposition 29.

Proof.

Lemma 30.

Proof.

Fourier Sparsity of Delta Functions
and Matching Vector PIRs

Delta functions on $\{-1,0,1\}^{r}$

Definition 3 ( $S$ -decoding polynomial for the canonical set $S$ ).

Definition 6 (Fourier transform over a finite abelian group, $\mathbb{F}$ -valued).

3.3 Bounds for Delta Functions on $\{-1,0,1\}^{r}$

4.1 Fourier Sparsity and $𝑺$ -decoding Polynomials

Definition 22 ( $t$ -sparse $S$ -decoding polynomial).

Definition 25 ( $S$ -Matching Vector Family).

Appendix B Covering the cube by affine hyperplanes over $\mathbb{F}_{p}$

Appendix C Sparsity of delta functions on $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ over $\mathbb{C}$