Polytopes in binary field

42 Views Asked by At

So I just stumbled across something kind of interesting.

Say we're in $\{0,1\}^3$ with modulo 2 addition. The convex hull of this is the unit cube. Now, if we want to define a polytope on our cube, we can cut away half the points by imposing a parity check equation. Note that any parity check we conjure will give us a 2-dimensional subspace of $\mathbb{F}_2$ containing four points.

The weird part is this: if we impose even parity on any one or two bits ($x_i = 0$, or $x_i + x_j = 0$), we get a subspace with a 2d-plane as the convex hull. But if we impose $x_1+x_2+x_3 = 0$, we get:

$[0,0,0] \\ [0,1,1] \\ [1,1,0] \\ [1,0,1].$

Note that this is still a subspace in $\mathbb{F}_2$, it still has four points, but its convex hull is now a three-dimensional figure! Is there some deep reason behind this? My amateurish guess would have been that the convex hull of any imposed cutting plane would be a plane as well!

1

There are 1 best solutions below

1
On BEST ANSWER

While an equation $a \cdot x = b$ (over the real numbers) defines a hyperplane in $\mathbb R^n$, $a \cdot x \equiv b \mod p$ (where $a, x \in \mathbb Z^n$ ) picks out those $x$ lying on any of the hyperplanes $a \cdot x = b + k p$. If you have enough points on more than one hyperplane, the convex hull (again over the real numbers) will be $n$-dimensional rather than $n-1$-dimensional.