Mod-p degree
Degree over F_p.
Definition
Least degree of a polynomial over $\mathbb{F}_p$ agreeing with $f$ on the domain.
Parameters
\(p\) (p) default \(2\)
prime modulus
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\deg_p(f)\). “\(\deg_p(f)\) in terms of it” is the pair with \(\deg_p(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 3 above are this entry’s hand-picked neighbours; the other 90 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | For every prime $p$. Over $\mathbb{F}_p$ the multilinear representation is still $1 - \prod_i(1 - x_i)$, which contains $x_1\cdots x_n$ with coefficient $(-1)^{n+1} \ne 0$. Unlike \(\oplus_n\), OR gets no help from small characteristic -- which is why the value can be recorded as a bare $n$ with no choice of $p$ to make. |
| AND total | \(n\) | For every prime $p$: $\mathrm{AND} = \prod_i x_i$ over every field, so there is no choice of $p$ to make and the value is a bare $n$. |
| PARITY total | \(1 \text{ if } p = 2;\ n \text{ if } p > 2\) | Over $\mathbb{F}_2$ parity is the linear form $\sum_i x_i$. For odd $p$ the multilinear representation is $\tfrac12\big(1 - \prod_i(1-2x_i)\big)$, whose top coefficient $\pm 2^{n-1}$ is a unit mod $p$, so the degree jumps back to $n$. This single function is the whole content of the $\deg_p$ column. |
| MAJORITY total | \((n+1)/2 \text{ for } p = 2,\ n = 2^m - 1\) | The $\mathbb{F}_2$ multilinear expansion of the threshold $\mathrm{Th}_k^n$ is $\sum_{|S| \ge k} \binom{|S|-1}{k-1}\prod_{i \in S} x_i$. By Lucas' theorem $\binom{s-1}{k-1}$ is odd iff the binary digits of $k-1$ are a submask of those of $s-1$; with $n = 2^m-1$ and $k = 2^{m-1}$ the only $s-1 \le n-1$ containing the mask $0\underbrace{1\cdots1}_{m-1}$ is $2^{m-1}-1$ itself, so the degree is exactly $2^{m-1} = (n+1)/2$. For $n = 3$ this is the familiar $\mathrm{MAJ}_3 = xy + yz + zx$. |
| Threshold total | \(\Theta(n)\) putative | For every prime $p$. Over the integers $\mathrm{THR}^n_k = \sum_{|S| \ge k} (-1)^{|S|-k}\binom{|S|-1}{k-1}\prod_{i \in S} x_i$ (the \(\deg(f)\) line), and reducing this unique multilinear form mod $p$ shows $\deg_p = \max\{s \le n : \binom{s-1}{k-1} \not\equiv 0 \bmod p\}$. Taking $s = k$ gives the coefficient $\binom{k-1}{k-1} = 1$, so $\deg_p \ge k$; substituting $x_i \mapsto 1-x_i$ preserves degree and maps $\mathrm{THR}^n_k$ to the complement of $\mathrm{THR}^n_{n-k+1}$, so also $\deg_p \ge n-k+1$. Hence $\deg_p \ge \max\{k,\ n-k+1\} \ge (n+1)/2$, and $\deg_p \le n$. No prime helps, in contrast with \(\mathrm{ADDR}_k\). |
| EXACT-HALF total | \(\Theta(n)\) putative | For every prime $p$. The coefficient of $\prod_{i \in S}x_i$ in the integer multilinear expansion is $(-1)^{|S|-n/2}\binom{|S|}{n/2}$, so $\deg_p$ is the largest $s \le n$ with $\binom{s}{n/2} \not\equiv 0 \pmod p$. Taking $s = n/2$ gives $\binom{n/2}{n/2} = 1$, so $\deg_p \ge n/2$ in every characteristic, and $\deg_p \le n$ trivially. Which $s$ is largest jumps around with $p$ and $n$ by Lucas -- see the \(\deg_2(f)\) line for the $p=2$ story -- but the order is always $n$. |
| ODD-MAX-BIT total | \(n\) putative | For every prime $p$. The expansion $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$ has the top monomial $x_1\cdots x_n$ only from the $i=1$ term, with coefficient $(-1)^{n-1}$, which is nonzero in every characteristic. So small characteristic buys nothing, exactly as for \(\mathrm{OR}_n\). |
| ADDRESS / multiplexer total | \(k+1\) putative | For every prime $p$: the expansion $\sum_a \big(\prod_{i:a_i=1} z_i \prod_{i:a_i=0}(1-z_i)\big) y_a$ used for $\deg_2$ has top monomials $z_1\cdots z_k\,y_a$ with coefficient $\pm1$, nonzero in every characteristic, and they cannot cancel because they carry distinct table variables. |
| Binary tree navigation total | \(k\) putative | The recursion $\mathrm{Nav}_k = L + x_0(R-L)$ over $\mathbb{F}_p$: by induction $R$ carries a degree-$(k-1)$ monomial with coefficient $\pm1$ in variables disjoint from those of $L$, so $x_0$ times it survives with coefficient $\pm1 \ne 0$ for every $p$. Unlike \(\oplus_n\) and \(\mathrm{MAJ}_n\), navigation gets no discount in any characteristic. |
| TRIBES total | \(n\) putative | For every prime $p$. Over $\mathbb{F}_p$ the representation is still $1 - \prod_j(1 - \prod_{i\in T_j} x_i)$, whose top monomial $x_1\cdots x_n$ has coefficient $(-1)^{s+1} \ne 0$ in every characteristic. Consistent with the $\deg_2 = n$ entry above. |
| AND-OR tree (depth 2) total | \(N = n^2\) putative | For every prime $p$. Over $\mathbb{F}_p$ one has $\mathrm{OR}_n(y) = 1-\prod_i(1-y_i)$, whose top monomial $\prod_i y_i$ carries coefficient $(-1)^{n+1}$, and $\mathrm{AND}_n$ is the plain product of its arguments; the blocks are disjoint, so the top monomial $\prod_{i,j}x_{ij}$ of the composition survives with coefficient $((-1)^{n+1})^n \ne 0$. Hence $\deg_p = \deg = N$ for all $p$, matching the recorded $\deg_2$. |
| NAND tree (balanced AND-OR formula) total | \(N\) putative | For every prime $p$. Over $\mathbb{F}_p$, $\mathrm{NAND}(u,v) = 1-uv$, so if $c_{d-1}$ is the coefficient of the top monomial of $f_{d-1}$ then $c_d = -c_{d-1}^2$; starting from $c_0 = 1$ this stays $\pm 1$ and never vanishes mod $p$. Hence $\deg_p = \deg = N$ for all $p$, consistent with the recorded $\deg_2 = N$. |
| Kushilevitz's function (iterated) total | \(3^k = N^{0.6131}\) putative | For every prime $p$. In the $0/1$ multilinear expansion $K = \tfrac12 - \tfrac18(\sum_{T\in\mathcal{F}}\chi_T - \sum_i\chi_i)$ with $\chi_S = \prod_{i\in S}(1-2x_i)$, the degree-$3$ part of $\chi_T$ is $-8\prod_{i\in T}x_i$, so each of the ten monomials $\prod_{i\in T}x_i$ carries coefficient exactly $+1$ -- nonzero modulo every $p$. Under self-composition the top-degree part is $\sum_{T\in\mathcal{F}}\prod_{i\in T}(\text{top part of the } i\text{-th copy})$, a sum of distinct monomials over disjoint blocks, so no cancellation is possible and $\deg_p = 3^k$ for all $p$, matching the recorded $\deg_2$. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Same integrality argument as the $\deg_2$ line, for every prime $p$: $\deg_p\le\deg=\widetilde O(\sqrt n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n)\) | Same integrality argument as the $\deg_2$ line, for every prime $p$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | Same integrality argument as the $\deg_2$ line, for every prime $p$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Same integrality argument as the $\deg_2$ line, for every prime $p$. |
| Ambainis' exact-quantum function total | \(2^d\) putative | Exact for every prime $p$. The multilinear representation over any field is unique on $\{0,1\}^n$ and is the reduction of the integer one obtained by Mobius inversion, so $\deg_p\le\deg=2^d$ with equality iff the top coefficient survives mod $p$. Here the real form is $\mathrm{NE}=x_1+x_2+x_3-(x_1x_2+x_1x_3+x_2x_3)$ and a top-degree coefficient obeys $c_d=-c_{d-1}^2$ with $c_0=1$, so $|c_d|=1$ and it is nonzero modulo every $p$. |
| Surjectivity total | \(\Theta(n)\) putative | Same restriction as \(\deg_2(f)\): over $\mathbb{F}_p$ the restriction $\mathrm{OR}_{R+1}\circ\mathrm{AND}_{\log_2 R}$ is $1-\prod_i(1-\prod_j x_{ij})$, whose top monomial has coefficient $\pm1\ne0$, so $\deg_p\ge(R+1)\log_2 R=\Theta(n)$; and $\deg_p\le\deg=n$. |
| Triangle finding total | \(\Theta(m^2)\) putative | Same restriction as \(\deg_2(f)\): $\mathrm{OR}_t=1-\prod_i(1-x_i)$ has $\mathbb{F}_p$-degree $t=\binom{m-1}2$, and $\deg_p\le\deg\le\binom m2$. |
| Ordered search partial | \(1\) putative | Same construction as the $\deg=1$ entry, over $\mathbb{F}_p$: with $p(x)=\sum_i c_ix_i$ one has $p(x^{(k)})=\sum_{i>k}c_i$, and choosing $c_i=\pm1$ alternating makes the partial sums alternate between $0$ and $1$, which is $k\bmod 2$ on the promise. |
| Inner product mod 2 total | \(2 \text{ for } p = 2;\ n \text{ for } p > 2\) | Over $\mathbb{F}_2$ the inner product literally is $\sum_{i} x_i y_i$, a quadratic form -- degree $2$ on $n = 2m$ variables. Over any other field the representation is $\tfrac12\big(1 - \prod_i (1 - 2x_iy_i)\big)$ and the degree is $n$. Together with $\deg = n$, $\mathrm{s} = n$ and $\mathrm{D} = n$, this makes IP the standard example that $\deg_2$ carries no information about query complexity. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) putative | For every prime $p$. The multilinear representation has integer coefficients, and its top coefficient is $\prod_{j}\big(\!-(-1)^{m^2}\big) = \pm1$, which survives reduction mod any $p$. So unlike \(\mathrm{IP}_n\) and \(\mathrm{CONN}_m\), MP loses no degree over any finite field. |
| Sink of a tournament total | \(m-1 = \Theta(\sqrt N)\) putative | For every prime $p$, by the same disjoint decomposition that gives $\deg$ and $\deg_2$: the $m$ star monomials are distinct sets and each carries coefficient $\pm1$ over $\mathbb{Z}$, so nothing cancels in any characteristic. |
| Scorpion graphs total | \(3m-6 \text{ for } p \ge 5\) putative | Reduce the integer multilinear polynomial mod $p$: the top coefficient of $\prod_{e \in T}x_e$ is exactly $-6$, the six orderings of one triple $\{s,t,b\}$ each contributing $-1$ (see \(\deg(f)\)), so it survives modulo every prime $p \ge 5$ and $\deg_p = \deg = 3m-6$. It does not survive mod $2$ or mod $3$, and indeed exhaustive computation gives $\deg_2 = 6,\,10,\,13$ at $m = 5,6,7$ against $3m-6 = 9,\,12,\,15$ -- small characteristic genuinely helps on the scorpion, which is why \(\deg_2(f)\) is left unrecorded rather than guessed. |
| Graph connectivity total | \(N \text{ for } p \ge m\) putative | The top coefficient of the multilinear expansion is $\pm(m-1)!$ (see \(\deg(f)\)), invertible modulo every prime $p \ge m$, so $\deg_p = \deg = N$ there. For small primes it does vanish, and dramatically so: \(\deg_2(f)\) is only $\lfloor m^2/4\rfloor$. |