MAJORITY is not in ACC0

MAJORITY is not in ACC0

Definitions and mathematical statement

Let $\operatorname{MAJ}_n(x)=1$ when $\sum_{i=1}^n x_i\ge n/2$. A nonuniform $\mathrm{ACC}^0$ family has fixed constant depth, polynomial size, and gates AND, OR, NOT, and $\mathrm{MOD}_m$, for one fixed integer $m\ge2$. AND, OR and modular gates have unbounded fan-in; a modular gate outputs one when its input sum is divisible by $m$. The question is \[ (\operatorname{MAJ}_n)_{n\ge1}\notin\mathrm{ACC}^0\ ? \] Thus every possible fixed depth and modulus must be ruled out together with every polynomial-size family. Circuits can be chosen separately at each length. A lower bound for prime modulus alone, or for a fixed size exponent, is not the whole separation.

Formulation and concept references: [S1].

Short English statement

Can majority be excluded from every constant-depth polynomial-size circuit family built from Boolean and fixed-modulus counting gates?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, proves lower bounds for depth-two Boolean formulas, computes the exact real polynomial degree of majority, and tests whether symmetrization survives the torus-polynomial representation in [S1]. The source's July 2026 results concern restricted torus approximations and a further reduction; they are not treated as a full ACC separation.

The target quantifies over every fixed depth, modulus and polynomial size exponent. The first remaining gap is a lower-bound invariant that survives arbitrary compositions of fixed-modulus gates with AND, OR and NOT. The elementary invariants below fail that test in identifiable ways.

An exponential DNF lower bound.

Put $h=\lceil n/2\rceil$. Consider a disjunctive normal form computing the exact threshold $\sum_i x_i\ge h$, with arbitrary positive and negative literals in each term. Discard contradictory terms, since they accept no input.

Every remaining term must contain at least $h$ positive literals. Otherwise set precisely those positive-literal variables to one and all other variables to zero. All negative literals are satisfied, so the term accepts an input of weight less than $h$, contradicting correctness.

Now take an input of weight exactly $h$. A term accepting it must have all its positive literals among that input's ones. The preceding bound forces those positive literals to be exactly the set of its $h$ ones. Consequently a single term accepts at most one weight-$h$ input. Since every such input must be accepted, the number of terms is at least \[ \binom nh. \tag{266.1} \] This grows exponentially with $n$: the largest binomial coefficient is at least $2^n/(n+1)$, and the middle coefficient is one of the largest.

The argument permits negative literals, repeated occurrences and arbitrary term widths; none of these removes the counting obstruction. It is a complete lower bound for this representation, not merely for monotone DNFs.

The dual CNF lower bound.

Negating a CNF for majority gives a DNF for its complement. Replace each input by its complement, $y_i=1-x_i$. The resulting function is the threshold \[ \sum_i y_i\ge n-h+1. \] Applying $266.1$ to that threshold proves that the original CNF has at least \[ \binom n{n-h+1}=\binom n{h-1} \] clauses. This is also exponential as $n$ grows. Thus polynomial-size depth-two AND--OR forms with literal inputs do not compute majority.

The conclusion does not extend by simply calling every constant-depth circuit a DNF. Distributing AND over OR can expand the representation exponentially. A polynomial-size deeper circuit may have an enormous DNF, and a circuit containing modular gates need not admit a small DNF either. The lower bound's representation cost must remain visible.

Exact real polynomial degree is also large.

Every function on $\{0,1\}^n$ has a unique multilinear real polynomial representation. The coefficient of $x_1\cdots x_n$ is the finite difference \[ \sum_{S\subseteq[n]}(-1)^{n-|S|}f(\mathbf1_S). \] For the threshold function this equals \[ \sum_{j=h}^n(-1)^{n-j}\binom nj =(-1)^{n-h}\binom{n-1}{h-1}\ne0. \tag{266.2} \] The alternating-binomial identity follows from Pascal's rule: substitute $\binom nj=\binom{n-1}j+\binom{n-1}{j-1}$ and cancel all interior terms. Hence majority has exact real degree $n$.

This is another rigorous lower bound, but it does not separate majority from ACC. Parity already has the exact real representation \[ \operatorname{PARITY}_n(x) =\frac{1-\prod_{i=1}^n(1-2x_i)}2, \] whose degree is $n$. Yet parity is computed by a single $\mathrm{MOD}_2$ gate followed, if needed, by NOT. Exact real degree can therefore be maximal for an extremely small allowed modular circuit.

Replacing exact degree by a suitable approximate representation is a different route. Its validity requires proving that every circuit in the target class has the specified approximation, with controlled depth, modulus, size and error dependence.

A restricted periodicity obstruction.

Suppose a proposed symmetric rule depends only on Hamming weight modulo a fixed $m$. For $n\ge2m$, the weights $h-m$ and $h$ both lie in $[0,n]$, have the same residue modulo $m$, and lie on opposite sides of the majority threshold. Such a rule cannot compute majority.

This excludes, for example, any function of the single residue $\sum_i x_i\bmod m$, regardless of how its $m$ residue classes are relabeled. It does not exclude a general ACC circuit. Its gates can examine different subsets and combinations of inputs, and AND/OR composition need not leave the output as a function of this one residue. Symmetry of the final Boolean function is not a guarantee that an arbitrary circuit computing it has that restricted internal structure.

Likewise ruling out every prime modulus would not by itself cover circuits with a fixed composite modulus. The catalogue quantifies over the complete fixed-modulus family, and no prime-field substitution is made here.

What real symmetrization can legitimately do.

For a real polynomial $P(x)$ approximating a symmetric Boolean function in ordinary absolute value, average $P$ over all input permutations. The resulting polynomial has no greater degree. At an input $x$, every permuted input has the same target value, and the triangle inequality gives \[ \left|\frac1{n!}\sum_\pi P(x_\pi)-f(x)\right| \le \frac1{n!}\sum_\pi |P(x_\pi)-f(x)|. \] Thus an ordinary real approximation error bound is preserved.

This is an existence argument for a symmetric polynomial, not a polynomial-size circuit transformation. Even in the polynomial setting, the conclusion depends on the error being measured on the real line and on the linear averaging operation respecting that measurement.

The torus countertest: averaging can destroy exact correctness.

Torus polynomial approximation instead measures distance modulo integers, conventionally from $P(x)$ to $f(x)/2$ in $\mathbb R/\mathbb Z$. Integer shifts are invisible separately at each Boolean input.

Take the symmetric zero function on two bits and the nonsymmetric polynomial \[ P(x_1,x_2)=x_1. \] At every Boolean input $P$ is an integer, so it represents the zero function exactly on the torus. Average over the coordinate swap: \[ \overline P(x_1,x_2)=\frac{x_1+x_2}{2}. \] At $(1,0)$ and $(0,1)$ this equals $1/2$, at torus distance $1/2$ from zero. Exact approximation has been destroyed by symmetrization.

The issue is that the input-dependent integer lifts average to a noninteger. Small torus errors do not select coherent real representatives whose ordinary average has the desired target. The example is intentionally as simple as possible; it invalidates a general averaging lemma independently of the degree or the majority function.

Therefore a degree lower bound established only for symmetric torus polynomials cannot be applied to arbitrary torus approximants by the preceding real-polynomial trick. Source [S1] explicitly distinguishes symmetric and asymmetric behavior. A successful proof needs an argument valid for the asymmetric representation, or a different justified reduction to symmetry.

How a representation lower bound would transfer.

The torus route has two distinct obligations. One needs a representation theorem placing every fixed-depth, fixed-modulus polynomial-size circuit into a class of low-degree torus approximants with a specified error. One then needs to show that majority has no approximant in that entire class.

The parameters may depend on the circuit family's fixed depth, modulus and size exponent. To rule out all polynomial-size families, the degree lower bound must eventually defeat each such fixed parameter choice. A computation excluding finitely many degrees or linear programs is evidence only for those finite cases. It is not the universal lower bound required to finish the transfer.

The present attempt neither reproves nor strengthens the representation results in [S1]. It audits two tempting shortcuts to the second obligation and gives explicit reasons each is inadequate.

Verification and outcome.

Exact finite calculations check $266.2$, enumerate the minimal-weight acceptance patterns underlying the DNF bound, and evaluate the torus symmetrization counterexample. They also compare the two same-residue weights in the periodicity test. These calculations do not enumerate all constant-depth modular circuits.

UNRESOLVED. Exponential depth-two Boolean bounds and exact real-degree bounds are proved. The modular-gate and torus countertests show why they do not settle the full target. The remaining gap is an unrestricted ACC-compatible lower bound for majority that covers every fixed modulus and depth.

Sources

• S1 Vaibhav Krishan and Sundar Vishwanathan, Degree Lower Bounds for Torus Polynomials and MAJORITY vs ACC0; v1 July14,2026. https://arxiv.org/pdf/2607.12346. Formulation source.