Gate Complexity of the Algebraic Torus: the General Case
Yipin Wang
Preprint, 2026
We determine the gate complexity $t(p,q,n)$ for all primes $p$ and prime powers $q$ with $\mathrm{char}(\mathbb{F}_q) \neq p$.
A dichotomy emerges: $t(p,q,n) = (q-1)^{n-1}$ when $p \mid (q-1)$, and
$t(p,q,n) = (q^n - 1)/(q-1)$ when $p \nmid (q-1)$.
The split is governed by the $\mathbb{F}_{p^k}$-Fourier support of the torus indicator,
which is $(\mathbb{F}_q^*)^n$ in the first case and $\mathbb{F}_q^n \setminus \{0\}$ in the second.
Cross-Characteristic Gate Complexity of the Algebraic Torus
Yipin Wang
ECCC, 2026
We determine the gate complexity $t(2,q,n) = (q-1)^{n-1}$ for all odd prime powers $q$,
where a gate is a composition of an affine map $\mathbb{F}_q^n \to \mathbb{F}_q$ with an
arbitrary function $\mathbb{F}_q \to \mathbb{F}_2$. The upper bound is an explicit
character-sum construction; the lower bound uses a Frobenius orbit counting argument
over $\mathbb{F}_{2^k}$, exploiting the self-duality $\widehat{\mathbf{1}_T} = \mathbf{1}_T$.
A Fourier-Analytic Switching Lemma over $\mathbb{F}_p$ and the AC$^0$ Lower Bound for Generalized Parity
Yipin Wang
ECCC, 2026
We prove a switching lemma for constant-depth circuits over $\mathbb{F}_p$
with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting.
The key ingredient is an exact computation of the $L_1$ Fourier mass of AND/OR gates over $\mathbb{F}_p$.
As a consequence, constant-depth circuits of sub-exponential size
over $\mathbb{F}_p$ cannot compute $\mathbf{1}[\sum_i x_i \equiv 0 \pmod{p}]$.
A Switching Lemma for DNFs over $\mathbb{F}_p$: the Canonical Decision Tree Approach
Yipin Wang
Preprint, 2026
We prove an $M$-independent switching lemma for width-$w$ DNFs over $\mathbb{F}_p$ via the canonical decision tree method:
$\Pr[\mathrm{DT}(f|_\rho) \geq s] \leq (2pwq/(1-q))^s$, with no dependence on the number of terms.
The key observation is that the $p$-ary branching of the CDT is effectively binary,
since all $p-1$ nonzero values have the same effect on literal satisfaction.
Spanning Trees, Modular Symbols, and a New Arithmetic Invariant of Elliptic Curves
Yipin Wang
Preprint, 2026
Averaging the plus modular symbol $\{0, t/u\}^+$ over spanning-tree-weighted feasible vectors
gives a rational invariant $c_f \in \mathbb{Q}$ for each weight-2 newform $f$.
The proof reduces to a Markov chain on $\mathbb{P}^1(\mathbb{Z}/N\mathbb{Z})$.
We compute $c_f$ for all optimal curves of conductor $\leq 100$ and study the
prime structure of its denominators.
On the 2-adic Structure of Zagier's MZV Matrices
Yipin Wang
Preprint, 2026
We prove that all coefficients in the decomposition of $\zeta(2)^{K-1}\zeta(3)$ into the
Hoffman basis are odd integers, and establish a row minimum formula for the 2-adic
valuation of $(M_K)^{-1}$. As a companion result, we give a closed-form inverse for the
binomial core matrix $B_N[a,i] = \binom{2i}{2a}$ in terms of Euler–secant numbers.