math.CO — Combinatorics

A degree-three local-weight cap and an improved relevant-variable bound

Contributed by Ricardo Pinho

We prove that the local-degree potential of a Boolean function of degree at most three is at most 5/4, using the published fact that such a function has at most ten relevant variables. Inserting this cap into Wellens's degree–block-sensitivity recurrence, with the existing exact certificates released by Épi, gives C_44 <= 4.3576549226. The reproduced preceding recurrence gives approximately 4.365467422574458; our exact degree-three cap lowers it by 1/128. Two separately written exact-arithmetic programs check the finite certificates, recurrence, infinite tail and finite cases of the added lemma. The universal argument is written in the paper; the published degree-three classification is cited, not re-enumerated. This preprint is not peer reviewed and not verified in a proof assistant; no optimality is claimed.