Parity in majority-inverter graphs: exact values for n ≤ 5, an interval for n = 6, and a conjecture

We study opt(PARn), the minimum number of majority gates in a majority-inverter graph (MIG) that computes the parity of n bits, with inverters and the constant free. The upper bound opt(PARn) ≤ 3⌊n/2⌋ is a known construction; we give a complete proof. Two elementary arguments give opt(PARn) ≥ max(opt(PARn−1), n) for n ≥ 2. We determine opt(PARn) = 0, 3, 3, 6, 6 for n = 1, …, 5: by exhaustive enumeration for n ≤ 3, and for n = 4, 5 by unsatisfiability of the exact-synthesis formulas at every positive size below 6, each with a DRAT proof checked by drat-trim and with no symmetry breaking. The values up to n = 4 were already known from exact synthesis; for them, we provide independent checks: exhaustive enumeration for n ≤ 3 and checked DRAT certificates for n = 4. For n = 6 the proved interval is 6 ≤ opt(PAR6) ≤ 9. A solver run without a proof also excludes six gates, and 7 ≤ opt(PAR6) ≤ 9 rests on that run. All values fit opt(PARn) = 3⌊n/2⌋, which we state as a conjecture. Restricting each gate to at most one complemented input, as Soeken et al. and the exact-synthesis tool percy do, loses nothing; the observation is theirs, and we write out its proof. percy returns the same values for n = 4, 5. Finally we record a weighted approach suggested by A. S. Kulikov, which would settle the conjecture for odd n only, and the point where the obvious way of proving it stops.