We apply the pigeonhole principle to show that there must exist Boolean functions on 7 inputs with a multiplicative complexity of at least 7, i.e., that cannot be computed with only 6 multiplications in the Galois field with two elements.
['Michael Codish', 'Luís Cruz-Filipe', 'Michael Frank', 'Peter Schneider-Kamp']
When Six Gates are Not Enough