On polynomial approximations over $\mathbb{Z}\mathrm{/}{2}^k\mathbb{Z}$

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}\mathrm{/}{2}^k\mathbb{Z}$. More precisely, given a Boolean function $F:\{0,1{\}}^n\to \{0,1\}$, define its $k$-lift to be $F_k:{0,1}^n \rightarrow {0,2^{k-1}}$by$F_k(x) = 2^{k-F(x)} \pmod {2^k}$. We consider the fractional agreement (which we refer to as ${\gamma }_{d,k}(F)$) of $F_k$ with degree $d$ polynomials from $\mathbb{Z}\mathrm{/}{2}^k\mathbb{Z}[x_1,\dots ,x_n]$. Our results are the following:

• Increasing $k$ can help: We observe that as $k$ increases, ${\gamma }_{d,k}(F)$ cannot decrease. We give two kinds of examples where ${\gamma }_{d,k}(F)$ actually increases. The first is an infinite family of functions $F$ such that ${\gamma }_{2d,2}(F)-{\gamma }_{3d-1,1}(F)\ge \mathrm{\Omega }(1)$. The second is an infinite family of functions $F$ such that ${\gamma }_{d,1}(F)\le \frac{1}{2}+o(1)$ – as small as possible – but ${\gamma }_{d,3}(F)\ge \frac{1}{2}+\mathrm{\Omega }(1)$.
• Increasing $k$ doesn’t always help: Adapting a proof of Green [Comput. Complexity, 9(1):16-38, 2000], we show that irrespective of the value of $k$, the Majority function ${\mathrm{M}\mathrm{a}\mathrm{j}}_n$ satisfies $\gamma_{d,k}($\mathrm{M}\mathrm{a}\mathrm{j}$_n) \leq \frac{1}{2}+\frac{O(d)}{\sqrt{n}}$\mathrm{.}Inotherwords,polynomialsover$$\mathbb{Z}$/2^k$\mathbb{Z}$$forlarge$k$ do not approximate the majority function any better than polynomials over $\mathbb{Z}\mathrm{/}2\mathbb{Z}$. We observe that the model we study subsumes the model of non-classical polynomials in the sense that proving bounds in our model implies bounds on the agreement of non-classical polynomials with Boolean functions. In particular, our results answer questions raised by Bhowmick and Lovett [In Proc. 30th Computational Complexity Conf., pages 72-87, 2015] that ask whether non-classical polynomials approximate Boolean functions better than classical polynomials of the same degree.