Parity function
In Boolean algebra, the parity function is a Boolean function that takes an input vector from \{0,1\}^n and outputs 1 if and only if the number of 1s in the vector is odd, and 0 otherwise; equivalently, it computes the exclusive or (XOR) of all input bits.[1] This function is symmetric, meaning its output depends solely on the Hamming weight (number of 1s) of the input rather than the positions of those 1s, and it generalizes to checking the parity of any subset of bits.[2] The parity function plays a pivotal role in computational complexity theory, serving as a benchmark for establishing lower bounds on the resources required to compute certain problems. It exhibits high sensitivity to input changes—flipping any single bit alters the output—and requires querying all n inputs in the worst case for decision tree algorithms, yielding a decision tree complexity of exactly n.[2] In the Fourier analysis of Boolean functions over \{-1,1\}^n, the parity function has its entire Fourier mass concentrated on the highest-degree monomial \chi_{}(x) = \prod_{i=1}^n x_i, making it a canonical example of a function with maximal influence imbalance.[1] A landmark result in circuit complexity is that the parity function cannot be computed by constant-depth, polynomial-size circuits (the class AC^0), requiring superpolynomial size for any fixed depth d > 2, specifically at least \exp(n^{\Omega(1/(d-1))}). This was independently proven by Ajtai (1983) using combinatorial methods on finite structures[3] and by Furst, Saxe, and Sipser (1984) via a switching lemma and connections to the polynomial-time hierarchy,[4] kickstarting the field of AC^0 lower bounds and demonstrating the limitations of constant-depth parallel computation models. Beyond theory, parity functions underpin practical applications in error detection (e.g., parity bits in data transmission) and randomized algorithms, where they model unbiased coin flips or modular arithmetic modulo 2.[1]Fundamentals
Definition
The parity function on n bits, denoted PARITY_n(x), is a Boolean function that takes a binary input vector x \in \{0,1\}^n and outputs 1 if the number of 1s in x is odd, and 0 if even.[1] Equivalently, it computes the sum of the input bits modulo 2.[1] Mathematically, PARITY_n(x) can be expressed as the XOR (exclusive or) operation over all bits: PARITY_n(x) = \bigoplus_{i=1}^n x_i, where \oplus denotes addition modulo 2, or equivalently, the product \prod_{i=1}^n (1 - 2x_i) when viewing inputs in \{-1,1\}^n (after a suitable encoding).[1] This formulation highlights its direct connection to modulo 2 arithmetic in the vector space \mathbb{F}_2^n.[1] For illustration, consider n=3. The truth table below lists all $2^3 = 8 possible inputs and their corresponding outputs:| Input (x_1, x_2, x_3) | Number of 1s | Output PARITY_3(x) |
|---|---|---|
| (0, 0, 0) | 0 | 0 |
| (1, 0, 0) | 1 | 1 |
| (0, 1, 0) | 1 | 1 |
| (0, 0, 1) | 1 | 1 |
| (1, 1, 0) | 2 | 0 |
| (1, 0, 1) | 2 | 0 |
| (0, 1, 1) | 2 | 0 |
| (1, 1, 1) | 3 | 1 |
Basic Properties
The parity function PARITY_n: \{0,1\}^n \to \{0,1\}, defined as PARITY_n(x) = \sum_{i=1}^n x_i \mod 2, is linear over the finite field \mathbb{F}_2, meaning it satisfies additivity: PARITY_n(x + y) = PARITY_n(x) + PARITY_n(y) for all x, y \in \{0,1\}^n, where addition is componentwise modulo 2.[1] This linearity positions PARITY_n as an element of the dual space of \{0,1\}^n viewed as a vector space over \mathbb{F}_2, and more generally, the parity functions on subsets form a basis for the space of all Boolean functions.[1] In terms of influence and sensitivity, PARITY_n exhibits maximal properties among n-variable Boolean functions: the influence of each coordinate i is 1, as flipping x_i always changes the output, leading to a total influence of n.[1] This uniform sensitivity underscores its role as a highly unstable function, where every input bit is pivotal.[1] The Fourier (Walsh) expansion of PARITY_n, when viewed as a function to \{-1,1\} via \chi_{}(x) = (-1)^{\sum x_i}, consists solely of the term corresponding to the all-1s character, with Fourier coefficient \hat{f}(\mathbf{1}) = 1 and all others zero, concentrating its spectrum at degree n.[1] This pure high-degree structure distinguishes it in harmonic analysis of Boolean functions.[1] PARITY_n is unique as the only linear Boolean function of degree n that is balanced, outputting 0 and 1 each on exactly $2^{n-1} inputs.[1] Furthermore, it is invariant under any permutation of its inputs, as its value depends only on the parity of the Hamming weight, rendering it fully symmetric.[1] This symmetry, combined with its linearity, finds application as a parity check in error-correcting codes.[1]Computation and Algorithms
Finite Algorithms
The parity function for a finite binary string of length n can be computed iteratively using the XOR operation, which is associative and commutative, allowing sequential accumulation of bits modulo 2. The algorithm initializes a result variable to 0 and iteratively XORs each input bit into the result. This approach achieves O(n) time complexity and O(1) space complexity, making it suitable for sequential processing on standard hardware.[5] Pseudocode for the iterative XOR algorithm is as follows:This method is widely implemented in programming languages supporting bitwise operations, such as C or Python, where large n (e.g., multi-word integers) can be handled by processing bits in chunks via shifts and masks to avoid explicit loops over individual bits. For instance, in 64-bit architectures, folding the word with successive XOR shifts (e.g., v \oplus (v \gg 32), then v \oplus (v \gg 16), etc.) reduces the effective size logarithmically before a final parity check.[5][6] In parallel computing models, such as PRAM, the parity can be computed using a tree-based reduction of XOR operations, where bits are paired and XORed level by level until a single result remains. This structure forms a binary tree of depth \log n, enabling O(\log n) time complexity with O(n) processors, as each level halves the number of active operands. Such reductions are standard in parallel algorithms for associative operations like XOR.[6][7] Hardware implementations of the parity function often leverage XOR trees integrated into arithmetic logic units (ALUs) for generating parity bits or flags. In adders and ALUs, parity computation corresponds to carry-less addition modulo 2, where partial products or sums are reduced via a cascade of XOR gates without carry propagation, ensuring efficient combinational logic for status register updates. This is evident in designs like ripple-carry or tree-based adders extended for parity prediction.[8][9] For sparse inputs, where most bits are 0, optimizations focus on processing only the set bits (1s), as XORing 0 has no effect. Algorithms like the population count variant toggle parity iteratively over set bits using bit manipulation (e.g., v \& (v-1) to clear the least significant set bit), achieving time proportional to the Hamming weight rather than n. Early termination occurs naturally in such loops upon exhausting set bits; for subset-based processing (e.g., dividing into words or blocks), if a subset's parity is even (0), it can be skipped in the final XOR accumulation, further reducing operations in highly sparse cases.[5]function parity(input_bits: array of bits) -> bit: result = 0 for each bit in input_bits: result = result XOR bit return resultfunction parity(input_bits: array of bits) -> bit: result = 0 for each bit in input_bits: result = result XOR bit return result