  We study approximation of Boolean functions by low-degree polynomials over
the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function
$F:\{0,1\}^n \rightarrow \{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}/2^k\mathbb{Z}[x_1,\ldots,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) \geq \Omega(1)$.
The second is an infinite family of functions $F$ such that
$\gamma_{d,1}(F)\leq\frac{1}{2}+o(1)$ -- as small as possible -- but
$\gamma_{d,3}(F) \geq \frac{1}{2}+\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{Maj}_n$ satisfies $\gamma_{d,k}(\mathrm{Maj}_n)
\leq \frac{1}{2}+\frac{O(d)}{\sqrt{n}}$. In other words, polynomials over
$\mathbb{Z}/2^k\mathbb{Z}$ for large $k$ do not approximate the majority
function any better than polynomials over $\mathbb{Z}/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.
