2
votes
3answers
47 views

Boolean endomorphisms vs endofunctions on finite sets

I stumbled upon a funny fact: Let $\mathbf{Bool} = \{0, 1 \}$. For all functions $f: \mathbf{Bool} \to \mathbf{Bool}$ it is the case that $f^3 = f$. This got me excited and I was wondering whether ...
0
votes
2answers
176 views

The Rotate and Shift operations in a Finite Field

Do the Rotate and Shift operations in $GF_2$ have simple expressions in a finite field? The Rotate operation $ROT[x,n]$ left rotates by n-bits. So $ROT[(0,1,1,1),2]=(1,1,0,1)$. The Shift operation ...
0
votes
2answers
21 views

Boolean bit OR operation on a Finite Field

How can I express $x \vee y$ in $GF_2$? I know that XOR is $GF_2[x]+GF_2[y]$ and AND is $GF_2[x]*GF_2[y]$ for instance. But I cannot figure out bitwise disjunction. This may be because OR does not ...
1
vote
2answers
92 views

Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...
2
votes
1answer
118 views

Extending the logical-or function to a low degree polynomial over a finite field

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Is there ...
28
votes
1answer
1k views

Universal binary operation and finite fields (ring)

Take Boolean Algebra for instance, the underlying finite field/ring $0, 1, \{AND, OR\}$ is equivalent to $ 0, 1, \{NAND\} $ or $ 0, 1, \{ NOR \}$ where NAND and NOR are considered as universal gates. ...