Mod-2 degree
Degree of f as a multilinear polynomial over F_2.
also written:
F_2-degree, algebraic degree, GF(2) degree
Definition
The degree of the unique multilinear polynomial over $\mathbb{F}_2$ representing $f$. Very different from real degree: $\deg_2(\mathrm{PARITY})=1$ but $\deg(\mathrm{PARITY})=n$.
Basic facts
- $\deg_2(f)\le\deg(f)$ and $\deg_2(f)\le\mathrm{D}(f)$.
- A function of $\mathbb{F}_2$-degree $d$ is determined by, and can be computed from, structure of "$2^d$-flavoured" size; the tight relation between $\deg_2$ and $\mathrm{D}$ (and between $\deg_2$ and $\mathrm{s}$) is not settled here -- see the TODO.
- The mod-$p$ generalisation $\deg_p$ behaves similarly.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\deg_2(f)\). “\(\deg_2(f)\) in terms of it” is the pair with \(\deg_2(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | Over $\mathbb{F}_2$, $\mathrm{OR}=1-\prod_i(1-x_i)$ contains the monomial $x_1\cdots x_n$. |
| AND total | \(n\) | The $p=2$ case of the line above: $\mathrm{AND} = x_1\cdots x_n$ over $\mathbb{F}_2$. |
| PARITY total | \(1\) | Over $\mathbb{F}_2$ parity is linear -- the reason $\mathrm{D}^{\oplus}=1$. |
| MAJORITY total | \((n+1)/2\) putative | Recorded along the subfamily $n = 2^m - 1$. The $p=2$ case of the $\deg_p$ line below. The restriction to $n = 2^m-1$ is only for tidiness: running the same Lucas computation for every $n$ gives $\deg_2(\mathrm{MAJ}_n) = 2^{\lfloor \log_2 n\rfloor}$, so $\deg_2$ is always a power of two: it equals $n$ exactly when $n$ is one, and bottoms out at $(n+1)/2$ at $n = 2^m-1$, which is the case recorded here. Either way $\deg_2 = \Theta(n)$ while $\deg = n$ -- unlike \(\mathrm{IP}_n\), majority gets essentially no discount from characteristic $2$. |
| Threshold total | \(\Theta(n)\) putative | Over $\mathbb{F}_2$, $\mathrm{THR}^n_k = \sum_{|S|\ge k}\binom{|S|-1}{k-1}\prod_{i\in S}x_i$, so $\deg_2 = \max\{s \le n : \binom{s-1}{k-1} \text{ odd}\}$, which by Lucas is the largest $s-1 \le n-1$ whose binary expansion contains that of $k-1$. Let $2^t \le n-1 < 2^{t+1}$. If $k-1 < 2^t$ then $s-1 = 2^t-1$ qualifies and $\deg_2 \ge 2^t \ge (n-1)/2$; otherwise $k-1 \ge 2^t$ and already $s-1 = k-1$ gives $\deg_2 \ge k > (n-1)/2$. So thresholds get at most a factor-two discount from characteristic $2$; see the exact $\deg_2(\mathrm{MAJ}_n) = 2^{\lfloor\log_2 n\rfloor}$ on \(\mathrm{MAJ}_n\). |
| EXACT-HALF total | \(n-1\) putative | Recorded along the subfamily $n = 2^m$. The $\mathbb{F}_2$ coefficient of the monomial $\prod_{i\in S}x_i$ in $\mathrm{EH}_n$ is $\binom{|S|}{n/2} \bmod 2$, so $\deg_2$ is the largest $s \le n$ whose binary expansion contains that of $n/2$ (Lucas). For $n = 2^m$ the bit $2^{m-1}$ is absent from $n$ itself, and the largest admissible $s$ is $n-1 = 2^m-1$. For other $n$ the answer jumps around -- e.g. $\deg_2(\mathrm{EH}_6) = 3$ -- which is why the value is recorded on a subfamily. |
| ODD-MAX-BIT total | \(n\) putative | The same expansion over $\mathbb{F}_2$, with the same top monomial and coefficient $1$. |
| ADDRESS / multiplexer total | \(k+1\) putative | Over $\mathbb{F}_2$, $\mathrm{ADDR}_k = \sum_a \big(\prod_{i:\,a_i=1} z_i \prod_{i:\,a_i=0} (1+z_i)\big)\, y_a$ with $z$ the address. Each summand has the top monomial $z_1\cdots z_k\, y_a$, and these carry distinct table variables, so nothing cancels: $\deg_2 = k+1$. |
| Binary tree navigation total | \(k\) putative | The same recursion over $\mathbb{F}_2$: $\mathrm{Nav}_k = L + x_0(L+R)$. |
| TRIBES total | \(n\) putative | Over $\mathbb{F}_2$, $\bigvee_j y_j = 1 + \prod_j(1+y_j)$ contributes the monomial $\prod_j y_j$ with coefficient $1$, and each $y_j$ is the product of its tribe's variables. So the full monomial $x_1\cdots x_n$ survives, exactly as over $\mathbb{R}$. |
| AND-OR tree (depth 2) total | \(N = n^2\) putative | Over $\mathbb{F}_2$, $\mathrm{OR}_n = 1 + \prod_i(1+x_i)$ has top monomial $x_1\cdots x_n$ with coefficient $1$, and the outer AND multiplies the blocks' polynomials, so the full monomial survives. Characteristic $2$ buys nothing on a read-once formula. |
| NAND tree (balanced AND-OR formula) total | \(N\) putative | Over $\mathbb{F}_2$, $\mathrm{NAND}(u,v) = 1 + uv$, so each gate multiplies its children's polynomials and the top monomial of a subtree is the product of its leaves' -- with coefficient $1$ throughout. By induction the full monomial survives: $\deg_2 = \deg = N$. |
| Recursive MAJORITY-of-3 total | \(2^d = N^{0.6309}\) putative | Over $\mathbb{F}_2$, $\mathrm{MAJ}_3 = xy+xz+yz$ has degree $2$, and mod-$2$ degree is exactly multiplicative under composition (the top-degree monomials of the outer function live on disjoint blocks, so their expansions cannot cancel). So $\deg_2 = 2^d = \mathrm{s}$, quadratically below $\deg = N$. |
| Kushilevitz's function (iterated) total | \(3^k = N^{0.6131}\) putative | Mod-$2$ degree is exactly multiplicative under composition: the degree-$d_f$ part of $f$ over $\mathbb{F}_2$ is a sum of monomials in disjoint blocks, each of which becomes a product of the blocks' degree-$d_g$ parts, and distinct top monomials of $f$ land on distinct monomials, so nothing cancels. The base has $\deg_2(K)=3=\deg(K)$ (checked on the truth table), so $\deg_2 = \deg = 3^k$ here: characteristic $2$ buys nothing, and the $\mathrm{s}$-vs-$\deg$ separation is simultaneously an $\mathrm{s}$-vs-$\deg_2$ separation. |
| Rubinstein's function total | \(\Theta(N)\) putative | Over $\mathbb{F}_2$, $\mathrm{OR}_n = 1 + \prod_j(1+g_j)$ and the blocks are disjoint, so the top monomial of $\prod_j g_j$ survives with coefficient $1$ and $\deg_2(f) = n\deg_2(g)$. For the gadget the coefficient of $y_1\cdots y_n$ is $n/2 \bmod 2$, so $\deg_2(g) = n$ when $n/2$ is odd and $n-1$ when $n/2$ is even; brute force gives $3, 6, 7$ at $n = 4,6,8$. Hence $\deg_2 = N$ or $N - \sqrt N$. |
| Ambainis-Sun function total | \((3k+2)^2\) putative | Over $\mathbb{F}_2$, $\mathrm{OR} = 1 + \prod_i(1+g_i)$ on disjoint blocks, so $\deg_2$ adds over the blocks; the gadget has $\deg_2(g) = \deg(g) = 3k+2$ (brute force at $k = 1,2$). |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2) = \Theta(N)\) putative | Over $\mathbb{F}_2$ the composition is the product $\prod_j \overline{\mathrm{EH}}_n(x^j)$ of polynomials on disjoint blocks, so $\deg_2$ adds: $\deg_2(f) = n\deg_2(\overline{\mathrm{EH}}_n)$. For the gadget the coefficient of a degree-$k$ monomial is $\binom{k}{n/2} \bmod 2$, so $\deg_2(\overline{\mathrm{EH}}_n)$ is the largest $k \le n$ whose binary expansion contains that of $n/2$ (Lucas); this is between $n/2$ and $n-1$, since $\binom{n}{n/2}$ is always even. Brute force gives $3,3,7,7$ at $n = 4,6,8,10$. |
| Meiburg's tournament-subcube function total | \(\le 7923.9^{\,d}\) putative | The unique multilinear representation of a Boolean function has integer coefficients, so reducing it mod $2$ computes $f$ over $\mathbb{F}_2$: $\deg_2 \le \deg \le 7923.9^{\,d}$ by the \(\deg(f)\) entry. No lower bound is available. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients (Moebius inversion of $f$), so reducing it mod $2$ represents $f$ over $\mathbb{F}_2$ and $\deg_2\le\deg=\widetilde O(\sqrt n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n)\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\deg_2\le\deg=\widetilde O(n)$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\deg_2\le\deg=\widetilde O(\sqrt n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | The exact multilinear representation over $\mathbb{R}$ has integer coefficients, so reducing mod $2$ gives $\deg_2\le\deg=\widetilde O(n^{1/3})$. |
| Ambainis' exact-quantum function total | \(2^d\) putative | Exact. Over $\mathbb{F}_2$, $\mathrm{NE}=x_1+x_2+x_3+x_1x_2+x_1x_3+x_2x_3$, of degree $2$. Composing on disjoint blocks, the top-degree part of $\mathrm{NE}^d$ is $T_1T_2+T_1T_3+T_2T_3$ in the children's top parts $T_i$; the three products live on different pairs of blocks, so no cancellation is possible and the degree doubles at every level: $\deg_2(\mathrm{NE}^d)=2^d=\deg(\mathrm{NE}^d)$ (checked exhaustively for $d\le2$). Unlike $\oplus_n$, whose $\mathbb{F}_2$-degree collapses to $1$, this function is exactly as hard mod $2$ as over the reals. |
| Surjectivity total | \(\Theta(n)\) putative | Restrict: fix slots $1,\dots,R-1$ to the values $1,\dots,R-1$, encode the remaining value $R$ by the all-ones codeword, and leave the other $R+1$ slots free. Any non-all-ones codeword names an already covered value, so the restriction is exactly $\mathrm{OR}_{R+1}\circ\mathrm{AND}_{\log_2 R}$ on $(R+1)\log_2 R=\Theta(n)$ free bits. Over $\mathbb{F}_2$ that is $1+\prod_i(1+\prod_j x_{ij})$, whose top monomial is the product of every free bit, so $\deg_2\ge(R+1)\log_2 R$. Mod-$2$ degree never increases under restriction, and $\deg_2\le n$. |
| Triangle finding total | \(\Theta(m^2)\) putative | Set every edge at vertex $1$ to $1$ and leave the rest free: the graph then has a triangle exactly when some edge survives among the other $m-1$ vertices, so the restriction is $\mathrm{OR}_t$ with $t=\binom{m-1}2$. Over $\mathbb{F}_2$, $\mathrm{OR}_t=1+\prod_i(1+x_i)$ has degree $t$, and mod-$2$ degree never increases under restriction; the ceiling is $\binom m2$. |
| Inner product mod 2 total | \(2\) | Over $\mathbb{F}_2$ it is literally $\sum_i x_iy_i$. The gap between this and $\deg = n$ is the whole reason IP is used as a lifting gadget. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) putative | As for any read-once AND-OR formula: over $\mathbb{F}_2$, $\bigvee_i x_i = 1 + \prod_i(1+x_i)$ contributes the full monomial of its box with coefficient $1$, and the outer AND multiplies the boxes. |
| Sink of a tournament total | \(m-1 = \Theta(\sqrt N)\) putative | Over $\mathbb{F}_2$ the same disjoint decomposition works: $\mathrm{SINK}_m = \sum_v \prod_{u\ne v}[u\to v]$, and each product is a degree-$(m-1)$ polynomial whose top monomial is the star at $v$ (an oriented edge variable is $x_e$ or $1+x_e$ mod $2$, so the top term is unaffected). The $m$ stars are distinct sets, so nothing cancels and $\deg_2 = \deg = m-1$. Confirmed exhaustively for $3 \le m \le 6$. SINK is therefore not a $\deg$-versus-$\deg_2$ separator, unlike \(\mathrm{IP}_n\). |
| Graph connectivity total | \(\lfloor m^2/4 \rfloor\) putative | Over $\mathbb{F}_2$ the coefficient of $x_S$ is the number of connected spanning subgraphs of $(V,S)$ mod $2$, and that count is odd exactly when $(V,S)$ is connected and bipartite. (Proof: both sides satisfy the deletion-contraction recursion $N(H) = N(H/e)+N(H-e)$ mod $2$ -- contracting a non-bridge of a bipartite graph creates an odd cycle, contracting a bridge preserves bipartiteness -- with the same base cases.) So $\deg_2$ is the largest number of edges in a connected bipartite graph on $m$ vertices, namely $K_{\lfloor m/2\rfloor,\lceil m/2\rceil}$. Verified exhaustively over all graphs on $m \le 6$ vertices, and the value $2,4,6,9,12$ for $m = 3,\dots,7$. So $\deg_2 = (\tfrac12+o(1))\deg$ -- connectivity loses exactly half its degree over $\mathbb{F}_2$. |