GF(2) (also written as F2, Z/2Z, or Z2) is the simplest possible field in abstract algebra. It contains exactly two elements and provides the mathematical foundation for why XOR operations are reversible.
A field is an algebraic structure with two operations (addition and multiplication) satisfying certain axioms:
Common examples: rational numbers (Q), real numbers (R), complex numbers (C). GF(2) is the smallest finite field.
GF(2) consists of exactly two elements:
GF(2) = { 0, 1 }
With two operations defined by the following tables:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
1 + 1 = 0 (not 2, because 2 doesn't exist in GF(2))
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
This is identical to the AND truth table.
The most important property of GF(2) for HDC is that every element is its own additive inverse:
∀ a ∈ GF(2): a + a = 0
0 + 0 = 0 ✓
1 + 1 = 0 ✓
This means: to subtract in GF(2), you simply add. There is no distinction between + and −.
a + b = c, then c + b = a
c + b = (a + b) + b = a + (b + b) = a + 0 = a
This is the foundation of reversible binding in Hyperdimensional Computing. If we encode C = A xor B, we can recover A by computing C xor B = A.
Named after Évariste Galois (1811-1832), a French mathematician who developed the theory of finite fields before his death at age 20 in a duel. Galois showed that:
GF(2) is particularly important in computer science because computers naturally work with bits (0 and 1).
We can form polynomials with coefficients in GF(2):
P(x) = x7 + x3 + x + 1
When adding polynomials over GF(2), coefficients at each position are added mod 2:
P1(x) = x5 + x3 + x
P2(x) = x3 + x2 + 1
P1 + P2 = x5 + x2 + x + 1
1 + 1 = 0 in GF(2)
A polynomial over GF(2) can be represented as the set of exponents where the coefficient is 1:
x7 + x3 + x + 1 → {0, 1, 3, 7}
{1, 3, 5} + {0, 2, 3} = {0, 1, 2, 5}
This isomorphism is the foundation of SPHDC.
A binary vector of length n can be viewed as n independent GF(2) elements:
a = 010110102
b = 001111002
a xor b = 011001102
The XOR cancellation property extends to entire bit vectors:
(a xor b) xor b = a
(01011010 xor 00111100) xor 00111100
= 01100110 xor 00111100
= 01011010 ✓
Uses XOR (GF(2) addition) directly on fixed-length binary vectors. XOR cancellation enables reversible binding:
Composite = A xor B
A = Composite xor B (exact recovery)
Uses the polynomial interpretation. Each concept is a sparse set of 64-bit exponents, representing an astronomically sparse polynomial over GF(2). Binding uses Cartesian XOR.