We study approximation of Boolean functions by low-degree polynomials over the ring Z 2 k Z . More precisely, given a Boolean function F : 0 1 n 0 1 , define its k -lift to be F k : 0 1 n 0 2 k − 1 by F k ( x ) = 2 k − F ( x ) (mod 2 k ). We consider the fractional agreement (which we refer to as d k ( F ) ) of F k with degree d polynomials from Z 2 k Z [ x 1 x n ] . Our results are the following: - Increasing k can help: We observe that as k increases, d k ( F ) cannot decrease. We give two kinds of examples where d k ( F ) actually increases. The first is an infinite family of functions F such that 2 d 2 ( F ) − 3 d − 1 1 ( F ) (1) . The second is an infinite family of functions F such that d 1 ( F ) 2 1 + o (1) --- as small as possible --- but d 3 ( F ) 2 1 + (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 Maj n satisfies d k ( Maj n ) 2 1 + n O ( d ) . In other words, polynomials over Z 2 k Z for large k do not approximate the majority function any better than polynomials over Z 2 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.