<p>For arithmetic circuits over $\mathbb{Z}$ your argument is exactly right. The same argument works for arithmetic circuits over $\mathbb{Q}$ which don't use any fractions $a/b$ where $b$ is even.</p>

<p>However, the argument no longer works if you talk about arithmetic circuits over other rings, such as: general arithmetic circuits over $\mathbb{Q}$ (i.e. without the restriction above), $\mathbb{R}$, algebraic number fields, $\mathbb{C}$, or finite fields $\mathbb{F}_{q}$ with $q \neq 2$. </p>

<p>(This is essentially the same reason that in algebraic geometry $\mathbb{Z}$ is often considered of so-called "mixed characteristic," rather than characteristic zero.)</p>

<p>However, depth 3 Boolean lower bounds for circuits with {AND,OR,NOT} are less easily related to lower bounds for arithmetic circuits over $\mathbb{Z}$. (Yes, {AND,XOR} is a complete basis, but typically depth 3 circuits over {AND, OR, NOT} you consider NOT gates free, whereas implementing NOT with XOR you're then using an XOR gate, which you actually count. Similarly, although $a \vee b = \neg (\neg a \wedge \neg b)$, when you implement this single OR gate with AND and XOR, you get a little gadget of depth 3.)</p>

<p>The general statement is: let $f$ be a polynomial with coefficients in a ring $R$, and suppose $\varphi\colon R \to S$ is a ring homomorphism. By applying $\varphi$ to every coefficient of $f$ you get a polynomial with coefficients in $S$, which I'll denote $f_S$. Then a lower bound for computing $f_S$ by $S$-arithmetic circuits implies the same lower bound for computing $f$ by $R$-arithmetic circuits.</p>

CC BY-SA 3.0
2012-11-30T03:31:23.283Z
what is the significance of $b$ even ?
Suresh Venkat
CC BY-SA 3.0
2012-11-30T04:00:41.677Z
So that when you take things mod 2 $b$ has an inverse mod 2, i.e. $a/b \in \mathbb{Q}$ becomes $ab^{-1} \pmod{2}$ and the latter is well-defined.
Joshua Grochow
CC BY-SA 3.0
2012-11-30T05:27:43.183Z
Does it mean that proving some kind of theorem like von-division(i.e. that you do not need to divide by two) will imply circuit lower bounds over C?
Klim
CC BY-SA 3.0
2012-11-30T05:55:43.307Z
@Klim: No. The issue is that a circuit over C can still use irrational (or even non-real) constants, which you still can't take "mod 2."
Joshua Grochow
CC BY-SA 3.0
2012-11-30T02:02:11.647Z
2012-11-30T06:03:04.573Z
2012-11-30T06:03:04.573Z
Joshua Grochow
<p>My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?</p>

<p>What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant.     </p>

<cc.complexity-theory><circuit-complexity><arithmetic-circuits>
Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds
Somebody
# Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds

(Asked by: username_0 on 2012-11-30)

My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?

What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant.

**Tags:** cc.complexity-theory, circuit-complexity, arithmetic-circuits

---

## 1 answers

### Answer by username_1 on 2012-11-30. Score: 12 | Accepted answer

For arithmetic circuits over $\mathbb{Z}$ your argument is exactly right. The same argument works for arithmetic circuits over $\mathbb{Q}$ which don't use any fractions $a/b$ where $b$ is even.

However, the argument no longer works if you talk about arithmetic circuits over other rings, such as: general arithmetic circuits over $\mathbb{Q}$ (i.e. without the restriction above), $\mathbb{R}$, algebraic number fields, $\mathbb{C}$, or finite fields $\mathbb{F}\_{q}$ with $q \neq 2$.

(This is essentially the same reason that in algebraic geometry $\mathbb{Z}$ is often considered of so-called "mixed characteristic," rather than characteristic zero.)

However, depth 3 Boolean lower bounds for circuits with {AND,OR,NOT} are less easily related to lower bounds for arithmetic circuits over $\mathbb{Z}$. (Yes, {AND,XOR} is a complete basis, but typically depth 3 circuits over {AND, OR, NOT} you consider NOT gates free, whereas implementing NOT with XOR you're then using an XOR gate, which you actually count. Similarly, although $a \vee b = \neg (\neg a \wedge \neg b)$, when you implement this single OR gate with AND and XOR, you get a little gadget of depth 3.)

The general statement is: let $f$ be a polynomial with coefficients in a ring $R$, and suppose $\varphi\colon R \to S$ is a ring homomorphism. By applying $\varphi$ to every coefficient of $f$ you get a polynomial with coefficients in $S$, which I'll denote $f\_S$. Then a lower bound for computing $f\_S$ by $S$-arithmetic circuits implies the same lower bound for computing $f$ by $R$-arithmetic circuits.

> **Comments:**
> **username_2**: what is the significance of $b$ even ?  
> **username_1**: So that when you take things mod 2 $b$ has an inverse mod 2, i.e. $a/b \in \mathbb{Q}$ becomes $ab^{-1} \pmod{2}$ and the latter is well-defined.  
> **username_3**: Does it mean that proving some kind of theorem like von-division(i.e. that you do not need to divide by two) will imply circuit lower bounds over C?  
> **username_1**: @Klim: No. The issue is that a circuit over C can still use irrational (or even non-real) constants, which you still can't take "mod 2."  

---

