<p>Every function $\mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independent.</p>

CC BY-SA 3.0
2012-05-06T18:04:57.133Z
2012-05-06T18:04:57.133Z
Yuval Filmus
<p>The <a href="http://www.cs.toronto.edu/~arkadev/singleLayer2G.pdf" rel="nofollow">following</a> paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\mathbb{F}_3$. I'm not sure how this is done.</p>

CC BY-SA 3.0
2012-05-06T17:44:21.487Z
Asking about a claimed fact in a research paper is definitely grad-student level, which I think is fine for this site.
Suresh Venkat
CC BY-SA 3.0
2012-05-06T19:21:51.183Z
@Suresh: That is a very broad statement.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-06T20:23:47.370Z
@TsuyoshiIto: Somehow I knew you'd object to it :)
Suresh Venkat
CC BY-SA 3.0
2012-05-06T21:59:29.057Z
@Suresh: Honestly, I do not know why you posted that obviously incorrect claim.  In addition, I do not know what those four users who voted your comment up are thinking.  If you wanted to provoke me for some reason, you won.
Tsuyoshi Ito
<cc.complexity-theory><circuit-complexity><boolean-functions><arithmetic-circuits>
Computing every boolean function with a polynomial over $\mathbb{F}_3$?
Gadi A
# Computing every boolean function with a polynomial over $\mathbb{F}_3$?

(Asked by: username_0 on 2012-05-06)

The [following](http://www.cs.toronto.edu/~arkadev/singleLayer2G.pdf) paper briefly mentions the power of $MOD\_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\mathbb{F}\_3$. I'm not sure how this is done.

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, arithmetic-circuits
> **Comments:**
> **username_1**: Asking about a claimed fact in a research paper is definitely grad-student level, which I think is fine for this site.  
> **username_2**: @Suresh: That is a very broad statement.  
> **username_1**: @TsuyoshiIto: Somehow I knew you'd object to it :)  
> **username_2**: @Suresh: Honestly, I do not know why you posted that obviously incorrect claim.  In addition, I do not know what those four users who voted your comment up are thinking.  If you wanted to provoke me for some reason, you won.  

---

## 1 answers

### Answer by username_3 on 2012-05-06. Score: 2 | Accepted answer

Every function $\mathbb{F}\_p^n \longrightarrow \mathbb{F}\_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independent.


---

