# Computing every boolean function with a polynomial over $\mathbb{F}_3$?

The following 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.

• Asking about a claimed fact in a research paper is definitely grad-student level, which I think is fine for this site. – Suresh Venkat May 6 '12 at 17:44
• @Suresh: That is a very broad statement. – Tsuyoshi Ito May 6 '12 at 19:21
• @TsuyoshiIto: Somehow I knew you'd object to it :) – Suresh Venkat May 6 '12 at 20:23
• @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 May 6 '12 at 21:59

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.