M15 candidate: polynomial sampling by a positive moment-dominating proposal
Root derivation, accepted consolidation, 22 October 2026.
INTERNALLY REVIEWED COMPLETE-ORIGINAL CANDIDATE. Two reviewing agents
within the same system support the proof; this is not external peer review
or a publication/priority claim. The unchanged original frozen draft and
all review evidence are preserved alongside this consolidation.

Claim. The exact M15 original has a positive answer. For fixed depth d and
peak exponent k, every promised arbitrary-connectivity circuit admits a
uniform classical randomized sampler with worst-case polynomial runtime in
n and the supplied gate description length b, and TV error <=epsilon for
n^-k<=epsilon<=1/4. No heavy output is supplied; no weak-gate, geometric,
commuting, factorization or treewidth promise is imposed. The constants and
polynomial degree below are very large functions of d,k, not practical claims.

New bridge. The source 2610.02146 supplies rooted inclusion-exclusion for
one output and a good-bit cluster expansion. It explicitly leaves sampling
open. Here we sum the truncation errors over ALL outputs using exponential
moments, and supply a positive efficiently sampled dominating measure. Its
normalization is polynomial because connected moment activities have total
mass O(log n). Rejection uses point evaluations only along sampled proposals;
it never enumerates the quasipolynomial Hamming ball. Neither the inherited
source decomposition nor the earlier weak-gate sampler alone proves this.

1. Dependency, marginal centering, and exponential moments

Construct G by joining output bits whose backward input cones overlap. Put
K=4^d (or any integer >=2 greater than its maximum degree). It is computable
in polynomial time and has a K-coloring. Disjoint sets with no joining edge
have independent full measurement vectors, because their back-propagated
projectors act on disjoint product-input factors. This is strong dependency,
not merely pairwise independence. A marginal on s outputs, with any specified
bits, is computable to absolute precision 2^-P in exp(O_d(s)) poly(b,P)
bit operations: contract its O_d(s)-gate, O_d(s)-qubit backward cone. Gate
entry precision P+O_d(s+log(P+1)) suffices by telescoping or direct bounded
arithmetic. No construction of a common exact algebraic number field is used.

If x* has P(x*)>=n^-k, independence within a color gives
  product_(i in color) P(X_i=x*_i) >= P(x*) >= n^-k.
Hence sum_i P(X_i!=x*_i)<=K k log n. Marginal majority bits b_i minimize each
individual mismatch; they do not require finding x*. Compute marginals to
accuracy gamma=min(delta/16,1/(16n^2)), choose their approximate majority,
and put Y_i=1{X_i!=b_i}, p_i=P(Y_i=1). Miscentering increases each p_i by at
most 2 gamma. Thus, for n>=2, with C=K k+4,
                      sum_i p_i <= C log n.                    (1)
The empty/single-qubit cases can be directly sampled. In the exact original
epsilon interval the very smallest n can also be vacuous.

Choose a fixed dyadic delta>0 so
                 2 K^2 2^K delta^(1/K) <=1/8.                 (2)
For example delta=2^(-K ceil(log_2(16 K^2 2^K))) works. Use certified marginal
upper bounds of width <=2 gamma. Call i good if its upper bound is <=delta,
and let H be all other sites, G0 the good sites. Then p_i<=delta on G0 and
p_i>delta/2 on H. Consequently
                        |H|<=2 C log n/delta.                 (3)
No equality comparison of algebraic numbers is required.

For W=sum_(i in G0)Y_i, Holder over the K independent color classes gives,
for every fixed a>=1,
 E a^W <= product_colors [E a^(K W_color)]^(1/K)
       <=exp((a^K-1) sum_(i in G0)p_i/K)<=n^D_a,
                   D_a=C(a^K-1)/K.                           (4)
The same bound holds for the sum over any selected good subset. In particular
choose integer h=ceil((D_2+k+12) log_2 n). Then
                          P(W>h)<=n^-k/4096.                 (5)
All formulae may use ceilings of constants and ell=ceil(log_2 n), which
only enlarge h; fixed constants need no real-number oracle.

Write mu(A)=P(Y_i=1 for every i in A). Nonadjacent connected components
factor: mu(A)=product_components C of G[A] mu(C). We use two distinct
consequences of this fact: a signed zero-event expansion and a positive
dominating proposal. They must not be confused.

2. Uniform good-zero evaluator with a fixed, short arithmetic expression

For A subset G0, define
 Z_A(z)=sum_(T subset A) (-z)^|T| mu(T).
Its connected-component representation is a polymer gas with activity
(-z)^|T| mu(T) for each nonempty connected T, with compatibility requiring
disjoint sets and no joining edge. At z=1 it is the positive probability
Z_A=P(Y_A=0). A K-coloring gives mu(T)<=delta^(|T|/K).

There are at most K^(2s) connected s-vertex sets containing a fixed vertex:
choose a canonical spanning-tree traversal, pad with self-steps, and encode
its visited set by at most 2s steps with K choices. Also |N[T]|<=K s.
For |z|<=2, the sum at any vertex of activity magnitudes multiplied by
2^(|N[T]|-1) is at most
             sum_(s>=1) [2 K^2 2^K delta^(1/K)]^s <=1/7.
Induct on a vertex set A using the exact recurrence
 Z_A(z)=Z_(A-v)(z)+sum_(T connected, v in T subset A)
                              (-z)^|T| mu(T) Z_(A\N[T])(z).
Deletion ratios previously established as >=1/2 in modulus bound each
quotient by 2^(|N[T]|-1). Thus |Z_A/Z_(A-v)-1|<=1/7<1/2 on the closed disk.
Every Z_A is nonzero there, with the analytic logarithm f_A(0)=0 satisfying
                          |f_A(z)|<=n log 2.                  (6)
Summing the principal logarithms of these deletion ratios proves (6).
The physical logarithm f_A(1) is real. Truncating its Taylor series through
r gives error <=n log 2 *2^-r. If r=ceil(log_2(8n/eta)), the expression
          Zhat_A=exp(sum_(j=1)^r [z^j]f_A(z))                 (7)
satisfies |Zhat_A-Z_A|<=eta Z_A for eta<=1/4, with slack.

Compute these coefficients by connected-support Mobius inversion. For a
set F, set c_j(F)=sum_(D subset F)(-1)^(|F|-|D|)[z^j]log Z_D(z).
Only connected F of size<=j contribute; disconnected supports vanish by
factorization and logarithmic additivity. Therefore [z^j]f_A is the sum
of c_j(F) over such F subset A. Enumerate n K^(2r) walks, deduplicate their
connected sets, and compute the needed local moments and formal logarithms
through degree r. Each cluster costs exp(O_d(r)) poly(b,P), hence for
r=O(log n) the whole arithmetic expression has polynomial size.

Important precision distinction: r is chosen ONCE from the inverse-polynomial
analytic error eta. Later evaluating the fixed expression (7) to much higher
arithmetic precision does NOT increase r or rerun a black-box approximation
algorithm at that smaller error. Coefficients are sums of polynomially many
local moments combined by formal logarithms. For clusters of size r their
coefficient magnitudes and error amplification have logarithms O(r^2+log n).
This follows directly from log(1+Q)=sum_(j<=r)(-1)^(j+1)Q^j/j and |mu|<=1:
Z_D has coefficient l1 norm <=2^r, and multiplying at most r copies costs
at most exp(O(r^2)). Thus P+O(r^2+log n) local-moment precision suffices
for P output bits. The real exponential is evaluated by range reduction
and rational Taylor arithmetic; its argument is bounded by n log2+1 by (6).
It follows that (7) can be evaluated to 2^-P in poly(n,b,P) time, without
field-degree growth. This is needed for small acceptance denominators.

3. One rooted estimator, but a global L1 error bound

Represent an output by its good defect set S subset G0 and its full H-bit
pattern u. Only |S|<=h will be kept. Put B=H union S; on B prescribe u and
ones on S. For T subset G0\S such that every connected component of G[T]
has an edge to B, put A_T=[n]\N[B union T], a subset of G0. Rooted inclusion-
exclusion gives the exact identity
 p(S,u)=sum_T (-1)^|T| P(Y_H=u,Y_(S union T)=1) Z_(A_T).       (8)
This is the source2610.02146 Eqs7--10 applied to the present fixed center.
For clarity, expand all required good-zero constraints, split each selected
set into components touching B and those outside N[B union T], factor by
strong dependency, and resum the latter into Z_(A_T). This proves (8)
without any conditional independence assertion after observing B.

Define phat(S,u) by keeping |T|<=R in (8) and replacing Z by (7), using
the same eta,r everywhere. The number of rooted T of size<=R is
exp(O_K(|B|+R)): assign each component to its first adjacent root, distribute
its total size among the roots, and enumerate a connected animal at each
root. There are <=2^(|B|+R) size compositions and K^O(|B|+R) walks.
For B empty, only T empty is allowed. All local marginals in (8) involve
O(|H|+h+R)=O(log n) sites. Thus each queried phat is polynomial-time.

The crucial bound sums over ALL S and H patterns before using absolute
precision. Coefficients in (8) are nonnegative before the alternating sign.
Group a pair of disjoint sets S,T by D=S union T. There are at most 2^|D|
choices of which vertices belong to S. Summing over all u gives mu(D).
Dropping rootedness and |S|<=h only enlarges these nonnegative sums. Since
0<=Z<=1, the discarded part obeys
 sum_(|S|<=h,u) |p(S,u)-p_R(S,u)|
 <= sum_(D subset G0, |D|>R) 2^|D| mu(D)
 <= 2^-R sum_D 4^|D| mu(D)
  = 2^-R E 5^W <=2^-R n^D_5.                              (9)
For the zero-evaluator error, the analogous complete sum is
 sum_(|S|<=h,u) |p_R(S,u)-phat(S,u)|
 <=eta sum_D 2^|D| mu(D)=eta E 3^W<=eta n^D_3.             (10)
No number-of-prefixes or number-of-Hamming-ball-strings factor appears.
Choose R=ceil((D_5+k+12)log_2 n), eta=n^(-D_3-k-12), replacing exponents
by larger integers as needed. Both (9),(10) are <=n^-k/4096. Together with
(5), phat has total L1 error <n^-k/1024 when set to zero outside |S|<=h.
This is a signed approximation at this stage, not yet a sampler.

4. A positive proposal with polynomial normalization

List all nonempty connected good sets C of size<=h, with weight mu(C).
Their number M_poly<=n K^O(h) is polynomial. Their TOTAL weight is O(log n),
although there may be polynomially many tiny weights. To prove this, fix
v in C, |C|=s. Remove N[v], at most K vertices, and take a largest independent
color class among the remaining vertices. Its joint event is independent
of Y_v. Therefore
       mu(C)<=p_v delta^max(0,ceil((s-K)/K))
             <=p_v delta^-1 delta^(s/K).
Using the rooted animal count and (2),
 Lambda=sum_connected C mu(C)
 <=sum_v p_v delta^-1 sum_(s>=1)(K^2 delta^(1/K))^s
 <=delta^-1 C log n.                                      (11)
Overcounting each C at every possible root is harmless for this upper bound.

The H core handles every potentially large marginal. Enumerate pairs
(J,D), where J subset H is the set of ones in H, D subset G0, |D|<=h,
and every connected component of G[D] has an edge to H. The empty D is
allowed; if H is empty it is the only D. Give this core weight mu(J union D).
There are M_core<=2^|H| exp(O_K(|H|+h)) such pairs, hence polynomially many.
They are distinct subsets of [n], so
 A_exact=sum_cores mu(J union D)
 <=sum_(F subset [n])mu(F)=E2^(sum_i Y_i)
 <=2^|H| E2^W<=2^|H| n^D_2.                              (12)

Use dyadic UPPER weights, to avoid rare or zero moment division. Let nu be
a positive dyadic with 1/[32(M_core+M_poly+1)]<=nu<=1/[16(M_core+M_poly+1)].
Each local moment can be bracketed to width <=nu/4 in polynomial time.
Round its upper endpoint upwards to the next multiple of nu and add nu.
The resulting rational weight a satisfies
                         nu<=a<=mu+3nu, a>=mu.              (13)
This includes zero moments; neither an exact zero test nor a tiny nonzero
lower bound is required. Let a_core,a_C denote these weights and A their
core-weight sum. By (11)--(13), the computable normalization
                   Kprop=A product_C(1+a_C)                (14)
is bounded by a fixed polynomial in n: A<=2^|H|n^D_2+1 and
product_C(1+a_C)<=exp(delta^-1 C log n+1). A conservative explicit integer
power n^J(d,k) bounds Kprop for every n>=2, by (3). It is immaterial that
this power is enormous. The rational number Kprop itself has polynomial
bit length, since there are polynomially many O(log n)-bit factors.

One proposal attempt draws a core (J,D) with probabilities a_core/A, then
independently activates each C with probability a_C/(1+a_C). Reject if
any active polymers overlap or are joined by an edge, if an active polymer
meets N[H union D], or if the union of D and the active C has size>h.
Otherwise let S=D union (all active C), with H ones J. The accepted set of
active polymers is exactly the collection of connected components of G[S]
not touching H; D is precisely the union of components touching H. Thus
every |S|<=h output has a UNIQUE valid core/polymer representation. No
partition counting or multiplicity is hidden. Strong dependency gives
 mu(J union S)=mu(J union D) product_active C mu(C).
The unconditional probability that this valid output is proposed is exactly
                         w(S,J)/Kprop,
            w(S,J)=a_core product_active C a_C
                   >=mu(J union S)>=p(S,J).                (15)
The product over inactive polymers contributes the same common denominator
in (14). Invalid proposals are simply failed attempts. This is positive
independent sampling, not sampling signed inclusion-exclusion activities.

5. Acceptance, TV, finite random bits, and worst-case runtime

On a valid proposal, compute phat from (8)--(10), and accept with probability
                   clip(phat(S,J)/w(S,J),0,1).
The unnormalized accepted mass times Kprop is
                   r(S,J)=clip(phat(S,J),0,w(S,J)).          (16)
Since 0<=p<=w, clipping cannot increase pointwise error. Extend r by zero
outside |S|<=h. Equations(5),(9),(10) give ||r-p||_1<e/1024, e=n^-k.
Hence Zr=sum r is at least1-e/1024 and the normalized accepted law r/Zr
has TV distance <=||r-p||_1<e/1024. The success probability per ideal
attempt is Zr/Kprop>=1/(2Kprop). Run at most
                   T=ceil(2 n^J log(16/e))
attempts, outputting b on failure. Failure probability is <=e/16. This is
a worst-case polynomial cap, not an expected-time-only claim.

All discrete and acceptance probabilities are implemented by fixed-precision
dyadic coins; use total TV allowance e/16 over at most T(M_poly+2) choices.
The core distribution can instead be approximated in total variation
e/[32T] by its rational cumulative sums and one fixed random dyadic number.
There is no unbounded exact Bernoulli subroutine. Numerically evaluate each
acceptance ratio sufficiently well that its coin error has the assigned
budget. Every valid proposal has at most h active polymers, and (13) gives
                        w(S,J)>=nu^(h+1).
Thus its denominator is at least exp(-O(log^2 n)); O(log^2 n) arithmetic
bits suffice for the ratio at the inverse-polynomial coin tolerance.
Compute the already FIXED phat expression to the required absolute
precision, using Section2's bit analysis and the polynomially many local
marginals in Section3. This does not change its truncations R,r or its
global L1 analysis. Forming all proposal weights needs only inverse-
polynomial absolute local accuracy. No exponentially accurate invocation
of a black-box FPTAS is hidden. Rounding, cutoff failure and (16) together
give TV<e<=epsilon with ample slack.

Every list has polynomial size, each local contraction touches O(log n)
outputs, every expression has polynomial size, and precision is O(log^2 n)
plus the input evaluator overhead. Runtime and random bits are bounded by
poly_(d,k)(n,b). The heavy string is never used, and the whole output law
is approximated. This would meet the exact original completion criterion.

6. Review and attribution obligations

Inherited: strong light-cone dependency, peaked Hamming concentration,
the rooted decomposition (source2610.02146), connected-support logarithms
and zero-free deletion arguments, and prior R47 bit-complexity accounting.
New claimed bridge: global L1 regrouping (9)--(10), the O(log n) sum of
positive moment-polymer weights, the explicit positive dominating proposal
with a small enumerated high-marginal core, and bounded rejection with
dyadic upper weights. These are one investigation, not separate seats.

Critical checks: (i) every valid output has exactly one proposal
representation; (ii) no conditioned strong-dependency assumption is used;
(iii) summing H patterns in (9) truly gives the unconditioned good moment;
(iv) polynomial normalization, including arbitrary high-marginal H;
(v) arithmetic precision is separated from analytic truncation degree.
The controls and two analytic reviews are now complete and support this
exact-original scope. No new investigation is credited for consolidation.


Appendix: explicit cap and finite-control qualifications (unchanged)

Supplement 1: explicit normalization exponent and finite verification scope
22 October 2026. No change to the mathematical mechanism or original claim.

Take J=ceil(4 C/delta+D_2+10) in Section5. By |H|<=2 C log(n)/delta,
2^|H|<=n^(2C/delta), A<=n^(2C/delta+D_2)+1, and the independent-polymer
factor is at most exp(1)n^(C/delta). For n>=2 these are bounded together
by n^J. One can use the integer cap T=ceil(2 n^J (k+5) ceil(log_2 n))
instead of evaluating log(16/e); it is no smaller. Every exponent depends
only on the fixed d,k. This makes the worst-case cap explicitly computable.

The source formula and inherited sparse-radius/cluster facts are attributed,
not claimed anew. R24's product-marginal envelope fails, and R26's connected
OUTPUT-component factorization is false. The present construction factors
UNCONDITIONAL JOINT MOMENTS only, using them as an upper envelope. Its
acceptance step restores zero-event correlations and hidden parity. It never
claims that the target output-component distribution is a positive gas.

check.py verifies two exact eight-output laws, using all outputs: (a) an
actual depth-four noncommuting circuit with rational rotations and staggered
CNOT gates; (b) the R26 XX-path hidden-edge parity law, which has exactly zero
probability for every odd output. For each it checks three core choices,
including empty and full H, all moment component factorizations, connected
logarithm Mobius coefficients, all rooted probability identities, global
L1 bounds for five truncation cutoffs, independent relative-zero perturbation,
unique core/polymer representations, positive dyadic upper weights and exact
rejection-law reconstruction. The finite controls do not test the extremely
conservative delta regime or asymptotic runtime; those are analytic bounds.
Both complete checker modes were run twice with identical outputs. Neither
finite verification nor this supplement is a separate investigation.
