Smallest formulas for the parity of 2k2k variables are essentially unique

For n=2kn=2k, we know that the size of a smallest AND/OR/NOT formula computing the Boolean function Parity(x1,…,xn)=Odd(x1,…,xn) is exactly n2n2: For any nn, it is at least n2n2 by the classical Khrapchenko bound, and for n=2kn=2k we easily obtain a formula of size n2n2 by writing and recursively expanding Odd(x1,…,xn)=[Odd(x1,…,xn/2)∧Even(xn/2+1,…,xn)]∨[Even(x1,…,xn/2)∧Odd(xn/2+1,…,xn)]. We show that for n=2kn=2k the formula obtained above is an essentially unique one that computes Parity(x1,…,xn) with size n2n2. In the equivalent framework of the Karchmer–Wigderson communication game, our result means that an optimal protocol for the parity of 2k2k variables is essentially unique.