The arithmetic semiring is the semiring $(\mathbb{N},+,\cdot,0,1)$ with usual addition and multiplication. The circuits over this semiring are (monotone) arithmetic circuits. Our goal is to show that $\mathrm{BPP}\subseteq \mathrm{P/poly}$ holds over the arithmetic semiring in the following strong sense.
Theorem: If a polynomial $f(x_1,\ldots,x_n)$ can be computed by a probabilistic arithmetic circuit of size $s$, then $f$ can be also computed by a deterministic arithmetical circuit of the same size $s$.We will need the following three facts. The voting function $\mathrm{Maj}(y_1,\ldots,y_m)$ of $m$ variables is a partial function whose value is $y$ if the element $y$ appears more than $m/2$ times among the $y_1,\ldots,y_m$, and is undefined, if no such element $y$ exists. A simple application of Chernoff's and union bounds yields the following.
Fact 1 ("Majority Trick"):
If a probabilistic circuit $\mathsf{C}$ computes a function $f:S^n\to S$ on a finite set $X\subseteq S^n$, and if $m\geq 18 \log|X|$, then there are $m$ realizations $C_1,\ldots,C_m$ of $\mathsf{C}$ such that $f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$ holds for all $x\in X$.
Under an $(n,k)$-clique I will understand a cartesian product $S_1\times \cdots\times S_n$ with $S_i\subset \mathbb{N}$ and $|S_i|=k$.
Fact 2 ("Naive Nullstellensatz"):Let $[M]^n$ denote the set of all $M^n$ vectors of length $n$ with positions in $[M]=\{1,\ldots,M\}$.
Let $f(x_1,\ldots,x_n)$ be a polynomial in which each variable $x_i$ has degree at most $k-1$. If $f$ vanishes on some $(n,k)$-clique, then $f\equiv 0$.
Fact 3 (Zarankiewicz problem for hypergraphs):Proof: Erdos and Spencer prove a more general result: If $X\subseteq V^n$ and $|X|\geq \alpha M^n$, then the number of $(n,k)$-grids in $X$ is at least $\alpha_n\cdot \binom{M}{k}^n$, where $\alpha_n$ is the last number in the sequence $\alpha_0,\alpha_1,\ldots,\alpha_n$ defined by $\alpha_0:=\alpha$ and $\alpha_{i+1}:=\binom{\alpha_i M}{k}/\binom{M}{k}$. By using the estimates $(M/k)^k\leq \binom{M}{k}\leq (\euler M/k)^k$, we obtain that $\alpha_n\geq (\alpha/\euler)^{k^n}$. So, by taking $\alpha:=1/m$, we have only to ensure that $(M/k)^n$ is at least $(\euler m)^{k^n}$, or equivalently, that $n\log M$ is at least $k^n\log m+k^n\log \euler + n\log k$, which holds because we even have $\log M\geq k^n \log m$. $\Box$
Let $2\leq k\leq n$ and $\log M\geq k^n \log m$. Then every set $X\subseteq V^n$ of $|X|\geq M^n/m$ vectors contains at least one $(n,k)$-clique.
Proof of Theorem: Take now $X=[M]^n$, where $M$ is an indeed large number when compared to $n$. By Fact 1, at least one realization $C$ of $\mathsf{C}$ is correct on a subset $Y\subseteq X$ of $|Y|\geq |X|/m \approx M^n/n\log M$ inputs. Our goal is to show that, actually, the circuit $C$ must correctly compute $f$ on all inputs $x\in \mathbb{N}^n$. If our probabilistic arithmetic circuit $\mathsf{C}$ had size $s$, then the circuit $C$ has also size at most $s$, and the degree $k$ of the computed by $C$ polynomial is at most $2^s\leq 2^{2^n}$.
Consider the polynomial $p(x):=C(x)-f(x)$. Hence, $p(x)=0$ holds for all $x\in Y$. Recall that $Y$ is large, $|Y|\geq M^n/m$ for $m\leq 18n\log M$. The degree of polynomial $p(x)$ is at most $k\leq 2^s\leq 2^{2^n}$. By taking, say, $M:=2^{2^{2^{2^n}}}$ and $m:=18n\log M=18n2^{2^{2^n}}$, we have $\log M=2^{2^{2^n}}$ and $k^n\log m\leq 2^{2n2^n}\ll \log M$. So, by Fact 3, there must be an $(n,k)$-clique $S=S_1\times \cdots\times S_n$ such that $p(x)=0$ holds for all $x\in S$. Since the polynomial $p(x)$ has degree at most $k$, Fact 2 implies that $p(x)=0$ must hold for all $x\in \mathbb{N}^n$. Thus, the circuit $C$ must compute our polynomial $f$ correctly on all inputs $x\in \mathbb{N}^n$. $\Box$
S. Jukna