Id: palomar/PALOMAR-2026-11-09-000020 Url: https://github.com/bishara74/lowhalf-mul3/tree/b6c00ef8d94ff578585b428270df1af271a96bd6 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-09-000020-v1.json Repo: https://github.com/bishara74/lowhalf-mul3 Tags: cs.CC, msc:68Q06, msc:68Q17, msc:94D10 Score: 0 Title: Unrestricted Boolean multiplicative complexity of the 3x3 low-half multiplier Trust: high Domain: cs.CC Source: palomar Authors: Bshara Alhodali Reviews: 0 Subject: cs.CC Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-09 Formalized: true Formalizes: title=The multiplicative complexity of the three-bit low-half multiplier identifier= relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-09-000020 Formalizes the target lowMul3, the three low bits of the product of two 3-bit integers (the product modulo 8), in the unrestricted XOR--AND circuit model of arXiv:2608.30238v1, where XOR and constants are free and either input of a paid AND gate may reuse arbitrary earlier nonlinear wires. Phase 1 proves that the three ANF coordinates agree with integer multiplication modulo 8 on all 64 inputs, and gives an explicit six-gate circuit, one of whose gates reuses two earlier nonlinear wires. Phase 2 adds the derivative lemma (Lemma 8 of the four-gate note in paper/notes/). Phase 3 proves the…