Ugly Duckling Theorem - As A Statement About Boolean Functions

As A Statement About Boolean Functions

Let be a set of vectors of booleans each. The ugly duckling is the vector which is least like the others. Given the booleans, this can be computed using Hamming distance.

However, the choice of boolean features to consider could have been somewhat arbitrary. Perhaps there were features derivable from the original features that were important for identifying the ugly duckling. The set of booleans in the vector can be extended with new features computed as boolean functions of the original features. The only canonical way to do this is to extend it with all possible Boolean functions. The resulting completed vectors have features. The Ugly Duckling Theorem states that there is no ugly duckling because any two completed vectors will either be equal or differ in exactly half of the features.

Proof. Let x and y be two vectors. If they are the same, then their completed vectors must also be the same because any Boolean function of x will agree with the same Boolean function of y. If x and y are different, then there exists a coordinate where the -th coordinate of differs from the -th coordinate of . Now the completed features contain every Boolean function on Boolean variables, with each one exactly once. Viewing these Boolean functions as polynomials in variables over GF(2), segregate the functions into pairs where contains the -th coordinate as a linear term and is without that linear term. Now, for every such pair, and will agree on exactly one of the two functions. If they agree on one, they must disagree on the other and vice versa. (This proof is believed to be due to Watanabe.)