Parity has approximate degree N and requires at least N over 2 queries

Choose an $ϵ$-approximant $p$ of degree at most $d={\stackrel{}{\mathrm{deg}}}_{ϵ}({\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{Y}}_N)$ by [F1]. By [F2] it yields a univariate polynomial $q(t)$ of degree at most $d$ with $\mathrm{\mid }q(k)-(k<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2)\mathrm{\mid }\le ϵ$ for every integer $0\le k\le N$. Hence $q(k)-1\mathrm{/}2<0$ for even $k$ and $q(k)-1\mathrm{/}2>0$ for odd $k$, because $ϵ<1\mathrm{/}2$ and [F7].

The polynomial $q(t)-1\mathrm{/}2$ is continuous by [F3]. For each $k=0,\dots ,N-1$, its values at $k$ and $k+1$ have opposite signs by step 1.1. The intermediate value theorem [F3] gives a root in each open interval $(k,k+1)$; the root is interior because neither endpoint value is zero. These $N$ open intervals are disjoint, so the roots are $N$ distinct real numbers. Since $q-1\mathrm{/}2$ is not the zero polynomial (its value at $0$ is negative), [F4] implies its degree is at least $N$, and therefore $d\ge N$.

The polynomial $P(X)=\frac{1}{2}(1-{\prod }_{i=0}^{N-1}(1-2X_i))$ has degree at most $N$ by [F6] and equals parity on the Boolean cube, since each factor $1-2x_i$ is $1$ for bit $0$ and $-1$ for bit $1$. Thus the approximate degree is at most $N$; with step 2.1 it equals $N$. The query lower bound follows from [F5].