Proof. Discard true and tautological clauses from \(H\), and list the remaining clauses as \(C_1,\ldots,C_N\), retaining their indices even if clauses repeat. Let \(E_i\subseteq[d]\) be the scope of \(C_i\). Thus \(|E_i|\leq k\) and violation of \(C_i\) prescribes one pattern on \(E_i\). A false clause has empty scope and is always violated. All sums and families below are finite; there is no restriction on the finite number \(N\).

Building the finite expansion. Fix \(T,\rho\), and write \(v_i(z)\) for the violation indicator of \(C_i\) under this restriction. Put \(q=\sum_i v_i\). For \(U\subseteq T\), define \[ a_U=\sum_{i:\,|E_i\cap(T\setminus U)|\leq b}v_i, \qquad c_U=\sum_{i:\,E_i\cap(T\setminus U)=\varnothing}v_i. \tag{6}\] Call an index easy at \(U\) if it occurs in the first sum, and hard at \(U\) otherwise. Once the coordinates in \(U\) are prescribed, an easy clause has at most \(b\) variables still free. The classifications depend only on scopes, not on the values of \(z\). In particular, \[K=\mathbf 1[a_{\varnothing}=0]\] is the width-at-most-\(b\) CNF obtained by conjoining the initially easy clauses after substituting \(\rho\).

We will correct \(K\) to obtain \(H_{T,\rho}\). They already agree where \(K=0\) and where \(q=0\). At a point with \(K=1\) and \(q>0\), however, \(K-H_{T,\rho}=1\), and every violated clause is initially hard. Dividing this unit excess among the violated clauses gives \[1=\sum_{i\text{ hard at }\varnothing}\frac{v_i}{q}.\] The next step replaces the common denominator \(q\) by counts of easy clauses. This produces further corrections, indexed by paths of successive clause violations.

A path \(P=(i_1,\ldots,i_j)\) starts with \(U_0=\varnothing\) and satisfies \[ i_h\text{ hard at }U_{h-1}, \qquad U_h=U_{h-1}\cup(E_{i_h}\cap T) \quad(1\leq h\leq j). \tag{7}\] Write \(\mathcal P_j(T)\) for the family of these indexed paths. Each step adds at least \(b+1\) coordinates, so their lengths are bounded by \(L=\left\lfloor|T|/(b+1)\right\rfloor\). The selected indices are distinct: once an index is selected, its whole live scope belongs to \(U_h\), and it stays easy thereafter. If all selected clauses are violated, their first \(h\) indices are counted in \(c_{U_h}\), and hence \[ a_{U_h}\geq c_{U_h}\geq h. \tag{8}\] Throughout this expansion, a path fraction is defined to be zero when its numerator vanishes. The displayed bound makes every denominator positive on the numerator’s support.

Continue to work at a point with \(K=1\) and \(q>0\). For a nonempty path \(P=(i_1,\ldots,i_j)\), distinguish its remaining correction \[r_P=\frac{\prod_{h=1}^{j}v_{i_h}} {q\prod_{h=1}^{j-1}a_{U_h}}\] from the contribution obtained by replacing the remaining factor \(q\) in its denominator with \(a_{U_j}\): \[t_P=\frac{\prod_{h=1}^{j}v_{i_h}} {\prod_{h=1}^{j}a_{U_h}}.\] Since \(q=a_{U_j}+\sum_{i\text{ hard at }U_j}v_i\), this replacement gives \[ r_P=t_P-\sum_{i\text{ hard at }U_j}r_{Pi}, \tag{9}\] where \(Pi\) denotes extension by \(i\). Indeed, on the support of the prefix numerator, the sum over extensions is \(t_P(q-a_{U_j})/q\), leaving \(t_Pa_{U_j}/q=r_P\). If the prefix numerator vanishes, all extension numerators vanish too, so the identity still holds.

Initially \(\sum_{P\in\mathcal P_1(T)}r_P=1\). Substituting (9) repeatedly gives, for \(0\leq s\leq L\), \[0=1+\sum_{j=1}^{s}(-1)^j\sum_{P\in\mathcal P_j(T)}t_P +(-1)^{s+1}\sum_{P\in\mathcal P_{s+1}(T)}r_P.\] At \(s=L\) there are no further paths, so the residual sum is empty. Together with the cases \(K=0\) and \(q=0\), this proves the pointwise identity on the whole live cube \[ H_{T,\rho} =K+K\sum_{j=1}^{L}(-1)^j \sum_{P\in\mathcal P_j(T)} \frac{\prod_{h=1}^{j}v_{i_h}} {\prod_{h=1}^{j}a_{U_h}}. \tag{10}\] The construction is finite; no convergence argument is involved.

Each path is a positive weight times a finite convex mixture. A path is compatible with \(\rho\) if all its selected clauses can be violated simultaneously. Such violations prescribe exactly one pattern \(\sigma_P\in\{0,1\}^{U_j}\), with no conditions on \(T\setminus U_j\). Indeed, each selected clause prescribes its unique violating pattern; compatibility says that the prescriptions agree on overlaps and with \(\rho\). Write \[\mathcal Z_P=\{z\in\{0,1\}^T:z|_{U_j}=\sigma_P\}\] for this cylinder. Then \(\prod_hv_{i_h}=\mathbf 1_{\mathcal Z_P}\). An incompatible path has zero numerator everywhere and can be omitted.

For a compatible path and each \(h\), the function \(c_{U_h}\) is constant on \(\mathcal Z_P\). Every clause in its defining sum uses only coordinates already fixed by \(\rho\) and the pattern on \(U_h\). Denote this positive integer constant by \(c_h\), and set \[ \omega(P)=\prod_{h=1}^{j}\frac{1}{c_h}. \tag{11}\] On \(\mathcal Z_P\) we have \(a_{U_h}=c_h+w_h\), where \[w_h=\sum_{i\in I_h}v_i, \qquad I_h=\{i:0<|E_i\cap(T\setminus U_h)|\leq b\}.\] Substitute both \(\rho\) and the final pattern \(\sigma_P\) into each clause indexed by \(I_h\). The resulting clauses on \(T\setminus U_j\) have width at most \(b\), since \(U_h\subseteq U_j\). Keep their original indices in this family, including clauses that become true or false and any repetitions. Thus \(w_h\) remains exactly the number of violated clauses in this indexed family, even when some violations become constant after the final substitution.

We use the following elementary finite mixture. Given an indexed family of \(a\) clauses and an integer \(c\geq1\), uniformly permute the \(a\) clause objects and \(c\) distinct marker objects. Take the conjunction of the clauses appearing before the first marker. This finite uniform experiment defines a convex mixture of conjunctions of the indexed clauses. If an assignment violates exactly \(w\) of the indexed clauses, the sampled conjunction holds precisely when the first object among those \(w\) clauses and the \(c\) markers is a marker. By symmetry its expectation is \[ \frac{c}{c+w}. \tag{12}\] The argument includes \(a=0\), \(w=0\), repeated clauses, and constant clauses.

Independently apply this mixture at each \(h\) to the reduced clauses indexed by \(I_h\), with \(c=c_h\). Form \(J_P\) by conjoining all sampled clauses, \(K\), and the unit clauses prescribing \(\sigma_P\) on \(U_j\). Every realization of \(J_P\) lies in \(\mathcal C_b(T)\); here the assumption \(b\geq1\) permits the unit clauses. On the cylinder the independent mixtures have expected product \(\prod_h c_h/(c_h+w_h)\), while off the cylinder \(J_P\) vanishes. Consequently, as functions on the entire live cube, \[ K\frac{\prod_{h=1}^{j}v_{i_h}} {\prod_{h=1}^{j}a_{U_h}} =\omega(P)\,\mathbb E[J_P]. \tag{13}\] The expectation here is over a finite auxiliary probability space. It does not involve the test function \(G\).

Define \(W_0(H,T,\rho)=1\), and, for \(j\geq1\), let \[ W_j(H,T,\rho)= \sum_{\substack{P\in\mathcal P_j(T)\\P\text{ compatible with }\rho}} \omega(P), \qquad W(H,T,\rho)=\sum_{j=0}^{\left\lfloor d/(b+1)\right\rfloor}W_j(H,T,\rho). \tag{14}\] For each fixed restriction, combine (10) and (13), then take the correlation with \(G\) and use the triangle inequality. Since \(K\) and every realization of every \(J_P\) have width at most \(b\), this gives (5). Both \(W\) and all the mixtures were chosen without reference to \(G\), so the inequality holds simultaneously for every real-valued \(G\).

Reweighting by a full assignment. It remains to bound \(\mathbb EW_j\). Generate a uniform full assignment \(y\in\{0,1\}^d\) independently of \(T\), and set \(\rho=y|_{[d]\setminus T}\). This gives exactly the required distribution of restrictions. Conditional on \(T,\rho\), the live part of \(y\) is uniform. For a compatible path \(P\), it lies in \(\mathcal Z_P\) with probability \(2^{-|U_j|}\); on that event every selected clause is violated and every \(c_{U_h}\) equals \(c_h\). Thus, conditional on each \(T,\rho\), multiplying by \(2^{|U_j|}\) exactly undoes the probability of its cylinder. In particular, \[ \mathbb E_{T,\rho} W_j(H,T,\rho) =\mathbb E_{T,y}\!\left[ \sum_{\substack{P\in\mathcal P_j(T)\\ C_{i_1},\ldots,C_{i_j}\text{ violated at }y}} 2^{|U_j|}\prod_{h=1}^{j}\frac{1}{c_{U_h}(y|_T)} \right]. \tag{15}\] The identity holds separately for every path before summing. It does not assume that compatibility or the denominator counts are independent of the restriction.

Counting paths backwards. Fix \(y\). For \(R\subseteq[d]\), let \[V_R=\{i:C_i\text{ is violated at }y,\ E_i\cap R=\varnothing\}.\] For a path counted in (15), put \[ D_h=U_h\setminus U_{h-1},\qquad R_h=T\setminus U_h \quad(0\leq h\leq j), \tag{16}\] where \(D_h\) is used only for \(h\geq1\). These sets satisfy \[ i_h\in V_{R_h},\quad D_h\subseteq E_{i_h},\quad |D_h|>b, \quad R_{h-1}=R_h\mathbin{\dot\cup}D_h, \quad c_{U_h}(y|_T)=|V_{R_h}|. \tag{17}\] In particular, all displayed denominator counts are positive. Figure 1 depicts how a forward step removes \(D_h\) from the live remainder and a reverse step adds it back.

The pair consisting of \(T\) and its indexed path is determined by the terminal set \(R_j\) and the successive reverse choices \((i_j,D_j),\ldots,(i_1,D_1)\). Indeed, each choice reconstructs \(R_{h-1}=R_h\cup D_h\), recovering \(T=R_0\) and every selected index. It is therefore enough to count reverse sequences starting from an arbitrary set \(R\), allowing a choice of any \(i\in V_R\) and any \(D\subseteq E_i\) with \(|D|>b\), followed by the state \(R\cup D\). Because \(E_i\cap R=\varnothing\), this step always adds \(D\) disjointly. All actual reversed paths are included, and allowing additional sequences can only increase a sum of nonnegative weights.

Write \[\alpha=\frac{2p}{1-p},\qquad \pi(R)=p^{|R|}(1-p)^{d-|R|}.\] The sets \(D_1,\ldots,D_j\) partition \(U_j\), and \(T=R_j\mathbin{\dot\cup}U_j\). The contribution of a given pair \((T,P)\), including the probability of its live set, therefore factors as \[ \pi(T)\,2^{|U_j|}\prod_{h=1}^{j}\frac{1}{c_{U_h}(y|_T)} =\pi(R_j)\prod_{h=1}^{j} \frac{\alpha^{|D_h|}}{|V_{R_h}|}. \tag{18}\] This formula explains the useful direction of counting: at state \(R\), the reciprocal count is exactly \(1/|V_R|\), the normalization for averaging over the possible clause indices at that state.

For completeness, define the total weight of \(s\) reverse steps from \(R\) recursively by \(F_0(R)=1\) and \[ F_s(R)= \begin{cases} \displaystyle\frac{1}{|V_R|}\sum_{i\in V_R} \sum_{\substack{D\subseteq E_i\\|D|>b}} \alpha^{|D|}F_{s-1}(R\cup D),&V_R\ne\varnothing,\\[3mm] 0,&V_R=\varnothing, \end{cases} \qquad(s\geq1). \tag{19}\] The total weight of the choices at a state with \(V_R\ne\varnothing\) is \[\begin{align*} \frac{1}{|V_R|}\sum_{i\in V_R} \sum_{\substack{D\subseteq E_i\\|D|>b}}\alpha^{|D|} &=\frac{1}{|V_R|}\sum_{i\in V_R} \sum_{\ell=b+1}^{|E_i|}\binom{|E_i|}{\ell}\alpha^\ell \\ &\leq\sum_{\ell=b+1}^{k}\binom{k}{\ell}\alpha^\ell =\theta. \tag{20}\end{align*}\] When \(V_R\) is empty the total weight is zero. Induction in (19) now yields \(F_s(R)\leq\theta^s\) for every \(R\) and every fixed \(y\). Notice that (20) averages over the clause indices instead of multiplying by their number. Repeated clauses cause no difficulty: their multiplicities occur in both the sum and \(|V_R|\).

Use the injective reverse encoding and (18) to bound the expectation over \(T\) inside (15), for this fixed \(y\), by \[\sum_{R\subseteq[d]}\pi(R)F_j(R) \leq\theta^j\sum_{R\subseteq[d]}\pi(R)=\theta^j.\] Averaging over \(y\) gives \(\mathbb EW_j\leq\theta^j\). Finally, all terms are nonnegative and \(\theta<1\), so \[\mathbb EW \leq\sum_{j=0}^{\left\lfloor d/(b+1)\right\rfloor}\theta^j \leq\frac{1}{1-\theta},\] as required. Empty formulas, false clauses, and empty live sets are already covered by the construction; if \(k\leq b\), there are no nonempty paths and \(W=1\). ◻

Proof. For \(s=0\) there is at most one distinct set, so the hypothesis is impossible. Proceed by induction on \(s\). If the family contains \(r\) pairwise disjoint sets, these already form a sunflower with empty core. Otherwise, take a maximal pairwise disjoint subfamily. It has at most \(r-1\) members, and its union \(U\) has at most \(s(r-1)\) elements. Maximality implies that every set in the original family meets \(U\). Some element of \(U\) therefore belongs to more than \[\frac{s!(r-1)^s}{s(r-1)}=(s-1)!(r-1)^{s-1}\] members. Delete this element from all those members. The resulting sets remain distinct and have cardinality \(s-1\). By induction, \(r\) of them form a sunflower. Restoring the deleted element gives the required sunflower in the original family. ◻

Proof of Lemma 3. We regard clauses as sets of literals. Discard true and tautological clauses, duplicates, and any clause that contains another clause. If an empty clause remains, use the empty partition and stop. Otherwise the remaining clauses are nonempty and form an antichain under inclusion. The empty family is allowed and represents the constant true function.

The partition will come from a binary branching tree. Fix for now arbitrary integers \(r_2,\ldots,r_b\ge2\); we will choose their values after bounding the number of leaves. A sunflower is eligible at size \(i\) if it consists of \(r_i\) size-\(i\) clauses and has nonempty core. All set operations below concern literals. In particular, disjoint petals may contain opposite literals of one variable, and a branch may be unsatisfiable.

Branching and disjointness. Each state consists of an active antichain and a separate conjunction of unit clauses, called its side condition. Initially the side condition is true. It is never used to select sunflowers or to delete active clauses. Whenever an eligible sunflower exists, choose one of the smallest possible size \(i\), with fixed deterministic tie-breaking, and write its clauses as \[C\cup P_1,\ldots,C\cup P_{r_i}.\] The core \(C\) is nonempty. The petals are nonempty, pairwise disjoint, and all of the same size; their nonemptiness follows from distinctness and equal size of the sunflower members. Make two updates:

• On branch \(0\), insert the clause \(C\) into the active family.

• On branch \(1\), insert all petal clauses \(P_1,\ldots,P_{r_i}\) and append to the side condition the requirement that every literal of \(C\) be false.

After either insertion, delete all subsumed active clauses to restore the antichain. Every inserted clause has size strictly less than \(i\), so width never increases; the side condition uses only unit clauses. The extra requirement on branch \(1\) is the disjointness device of [2]. Keeping it separate ensures that every deletion from the active family is caused by an active insertion, a fact needed in the counting argument below.

Every clause in an insertion batch is new and remains active immediately after the update. Indeed, an inserted clause \(D\) is a strict subset of some current clause \(A\). A current clause \(B\subseteq D\) would satisfy \(B\subsetneq A\), contrary to the antichain property. Within a petal batch, distinct equal-size clauses do not subsume one another either.

Let \(F\) be the active CNF indicator before a step, and let \(F_0,F_1\) be the active indicators after its two updates, without side conditions. Subsumption deletion preserves the conjunction, so \[F_0=F\,\mathbf 1[C\text{ is true}],\qquad F_1=F\prod_{j=1}^{r_i}\mathbf 1[P_j\text{ is true}].\] When \(C\) is false, the selected clauses in \(F\) require every petal to be true. Therefore \[ F=F_0+\mathbf 1[C\text{ is false}]F_1, \tag{21}\] with disjoint supports on the right. Multiplying by the accumulated side condition gives the corresponding disjoint identity for the state. Once we prove termination, iteration of this identity will give a partition into leaf indicators.

Occurrence bounds and insertion budgets. We next bound the number of steps on every finite path prefix. The smallest-size rule bounds how many active clauses inserted in earlier branching steps can contain any one literal. Define \[e_1=1,\qquad e_i=(i-1)!(r_i-1)^{i-1}\quad(2\le i\le b).\] If the current size-\(i\) clauses contain no eligible sunflower, each literal occurs in at most \(e_i\) of them. For \(i\ge2\), remove a fixed literal from the clauses containing it. More than \(e_i\) distinct resulting sets would contain an \(r_i\)-member sunflower by Lemma 4; restoring the literal gives an eligible sunflower with nonempty core. For \(i=1\), the claim follows because the clauses are distinct.

Call an active clause added if it was inserted in a branching step. At every state, for every size \(u\) and every literal, we claim \[ \#\{\text{active added size-$u$ clauses containing this literal}\} \le e_u+1. \tag{22}\] Initially there are no added clauses. A step can increase this count only by inserting size-\(u\) clauses, and such a step processes a size \(i>u\). The smallest-size rule then guarantees that there is no eligible size-\(u\) sunflower before the insertion. Thus the occurrence bound applies to all current size-\(u\) clauses, giving at most \(e_u\) occurrences of each literal. The insertion adds at most one further occurrence, because it adds either one core or pairwise disjoint petals. Deletions only decrease the count. This proves the invariant; the initial family itself need not satisfy an occurrence bound.

For any finite path prefix, let \(N_u\) count the size-\(u\) insertions, counting members of a batch individually. Every deleted added size-\(u\) clause was subsumed by a newly inserted strictly smaller clause. Equality is excluded by the freshness of insertions, and side conditions never delete active clauses. Charge each such deletion to one smaller inserted clause that caused it. A fixed inserted clause \(D\) receives at most \(e_u+1\) charges: choose a literal of the nonempty clause \(D\), and apply (22) just before its batch was inserted. Every size-\(u\) clause subsumed by \(D\) contains that literal. If several batch members could receive a charge, choose only one of them.

At the end of the prefix, at most \(2m(e_u+1)\) added size-\(u\) clauses are still active, since each is nonempty and there are only \(2m\) literals. Counting deleted and surviving insertions therefore gives \[ N_u\le(e_u+1)\left(2m+\sum_{v<u}N_v\right). \tag{23}\] Define the positive integers \[ D_1=4,\qquad D_i=(e_i+1)\left(2+\sum_{u<i}D_u\right)\quad(2\le i\le b). \tag{24}\] The same recurrence holds for \(i=1\) with an empty sum. Induction on \(u\) in (23) proves \[ N_u\le D_um. \tag{25}\] These bounds hold on every finite prefix, without assuming termination. Every step inserts at least one clause of size less than \(b\), so every path has at most \(m\sum_{u<b}D_u\) steps. The binary tree is therefore finite.

For \(2\le i\le b\), put \(F_i=\sum_{u<i}D_u\). Each step processing size \(i\) contributes at least one insertion below size \(i\), and each branch-\(1\) step contributes exactly \(r_i\) such insertions. Hence \[ \#\{\text{steps processing size }i\}\le F_im,\qquad \#\{\text{branch-$1$ steps processing size }i\}\le F_im/r_i. \tag{26}\] Insertions caused by other processed sizes may also use this budget; including them only enlarges the upper bound.

Counting leaves and choosing thresholds. For each leaf and each \(i=2,\ldots,b\), record in order the decisions made at steps processing size \(i\), and pad this binary string with zeros to length \(F_im\). By (26), it has at most \(F_im/r_i\) ones. The tuple of strings determines the leaf. Indeed, distinct leaf paths have a first differing branch: neither can be a proper prefix of the other. Before this difference their states agree, so their selected size and their positions in that size’s stream agree. The different bits occur before padding in both streams, so the padded tuples remain different.

Write \(h_2(x)=-x\log_2x-(1-x)\log_2(1-x)\) for \(0<x<1\). For integer \(N\) and \(0<x\le1/2\), the number of binary strings of length \(N\) with at most \(Nx\) ones is at most \(2^{Nh_2(x)}\). A string with \(j\le Nx\) ones has Bernoulli-\(x\) probability \[x^j(1-x)^{N-j}\ge x^{Nx}(1-x)^{N-Nx}=2^{-Nh_2(x)},\] because \(x/(1-x)\le1\). Their total probability is at most one, proving the bound even when \(Nx\) is not an integer. Applied to the decision streams, this gives \[\#\{\text{leaves}\}\le \prod_{i=2}^{b}2^{mF_i h_2(1/r_i)}.\] We can now choose the thresholds to make this exponent small. The constant \(F_i\) depends only on \(r_2,\ldots,r_{i-1}\), because it involves only \(D_u\) with \(u<i\). Choose \(r_2,r_3,\ldots,r_b\) in order, each large enough that \[ F_i h_2(1/r_i)\le\eta/b,\qquad r_i\in\mathbb N,\quad r_i\ge2. \tag{27}\] This is possible since \(h_2(1/r)\to0\). An explicit choice is \(r_i=2^{q_i}\), where \(q_i\ge1\) is the least integer satisfying \(F_i(q_i+2)2^{-q_i}\le\eta/b\): the inequality \(-(1-x)\ln(1-x)\le x\) implies \(h_2(2^{-q})\le(q+\log_2e)2^{-q}<(q+2)2^{-q}\). For these choices, \[ \#\{\text{leaves}\}\le \prod_{i=2}^{b}2^{mF_i h_2(1/r_i)} \le2^{\eta m(b-1)/b}\le2^{\eta m}. \tag{28}\]

Clause counts at the leaves. At a terminal state no eligible sunflower remains. The occurrence bound now applies to the entire active antichain: each literal occurs in at most \(e_i\) size-\(i\) clauses, so there are at most \(2me_i\) such clauses. The side condition contributes at most \(2m\) distinct unit clauses after repetitions are removed. Thus the leaf indicator has width at most \(b\) and at most \(Mm\) clauses, where \[ M=2+2\sum_{i=1}^{b}e_i. \tag{29}\] All constants depend only on \(b,\eta\). An inconsistent side condition gives an empty piece, which may be discarded. The branching identities (21) give coverage and disjointness, and (28) bounds the number of pieces.

When \(b=1\) there are no branching sizes or streams. The tree has one leaf, its empty product of stream counts is one, and at most \(2m\) distinct unit clauses suffice; (29) gives \(M=4\). The constant true function has the empty conjunction representation, and the constant false function can use the empty partition. This covers every \(m\ge1\). ◻

Proof. After the small-length check, the integer parameters can be computed without real arithmetic: \(r\) is the least positive integer with \(r^3\ge d^2\), and \(t\) can be found by testing even integers until their sixth powers exceed \(d\). Searching integers up to \(n\) and using ordinary integer arithmetic takes polynomial time. Reading and checking the block boundaries does also.

Since \(P\) is monic, division by \(P\) gives a unique remainder of degree less than \(r\), whether or not \(P\) is irreducible. Thus every allowed polynomial block gives well-defined ring operations. Direct multiplication of two coefficient arrays and reduction by \(P\) use \(O(r^2)\) bit operations: form a polynomial of degree at most \(2r-2\), then successively cancel its highest coefficients by shifted copies of \(P\). Addition uses \(O(r)\) bit operations. Formula (30) uses \(O(rd)\) bit operations, and Horner evaluation of (31) uses \(O(t)\) ring multiplications and additions. The evaluation therefore uses \(O(rd+tr^2)\) bit-array operations and polynomial storage.

These are fixed loops on finite bit arrays, with counters of polynomial size. They can be implemented by a fixed Turing machine using direct tape scans, which incur only polynomial overhead per array operation. Together with the initial integer computations this yields a polynomial time bound; increasing its coefficient and exponent to positive integers gives the stated \(C,a\) and covers the finitely many small lengths as well. In particular, the machine does not test irreducibility or search for any choice of parameter bits. Neither its instructions nor its running-time constants depend on the proof parameters used below. ◻

Proof. Fix \(b,B\) and take \(d\) large enough that \(0<p<1\) and \(t\ge2\). Choose a monic irreducible polynomial \(P\) of degree \(r\), and identify \(R_P\) with its field \(F\) of size \(2^r\). Initially choose all the hash bits \(u\) independently and uniformly, and choose \(\beta_0,\ldots,\beta_{t-1}\) independently and uniformly in \(F\). We estimate the failure probability jointly over these choices and the restriction; the final step will fix one choice of these input bits.

Proof of Theorem 1. Proposition 6 supplies the single polynomial-time machine. Fix \(A>0\), and put \[\begin{gathered} d=\left\lfloor n/5\right\rfloor,\qquad s=3A,\qquad B=64(s+1),\\ p=\frac{B}{\sqrt d},\qquad m_0=B\sqrt d,\qquad k=\left\lceil 3(s+1)\sqrt d\right\rceil. \end{gathered}\] All subsequent assertions hold for every sufficiently large \(n\), with the threshold allowed to depend on \(A\). In particular, \(0<p\le1/2\) and \(n\le9d\), so \[ 2^{A\sqrt n}\le2^{s\sqrt d}. \tag{44}\]

Proof. First construct an extension field in which \(X^{2^r}-X\) splits. Any nonconstant polynomial over a field has an irreducible factor, by choosing a nonconstant divisor of least degree. The quotient by an irreducible polynomial is a field: the Euclidean algorithm expresses \(1\) as a linear combination of that polynomial and any nonzero residue representative, giving the inverse of the latter. Adjoining a root by this quotient and factoring out the corresponding linear factor can be repeated. Each step reduces the degree still to be split, so finitely many such extensions suffice.

In the resulting field the roots of \(X^{2^r}-X\) are distinct, since its formal derivative is \(-1=1\). There are exactly \(2^r\) roots. Their set \(F\) contains \(0,1\) and is closed under addition and multiplication: in characteristic two, repeated squaring gives \((a+b)^{2^r}=a^{2^r}+b^{2^r}\), and the analogous product identity is immediate. For a nonzero root \(a\), the identity \((a^{-1})^{2^r}=(a^{2^r})^{-1}=a^{-1}\) gives closure under inversion. Negatives equal the original elements in characteristic two. Thus \(F\) is a field with \(2^r\) elements. A basis of \(F\) over \(\mathbb F_2\) has exactly \(r\) elements, because a vector space of dimension \(v\) over \(\mathbb F_2\) has \(2^v\) elements.

For \(a\in F\), let its monic polynomial of smallest positive degree over \(\mathbb F_2\) that vanishes at \(a\) have degree \(e\). Such a polynomial exists by linear dependence in \(F\), and it is irreducible: a proper factorization would give a smaller vanishing factor in the field \(F\). Polynomial division shows that evaluation identifies \(\mathbb F_2[a]\) with its quotient field, with basis \(1,a,\ldots,a^{e-1}\). It therefore has \(2^e\) elements. Regarding \(F\) as a vector space over this subfield shows \(e\mid r\): if its dimension is \(v\), the products of the two bases give an \(\mathbb F_2\)-basis of size \(ev=r\).

Every element of a field with \(2^e\) elements satisfies \(a^{2^e}=a\). For nonzero \(a\), multiplication by \(a\) permutes the nonzero elements; taking their product and cancelling gives \(a^{2^e-1}=1\). Zero satisfies the identity as well. Hence each element of \(F\) of degree \(e\) is among the at most \(2^e\) roots of \(X^{2^e}-X\). Here the usual root bound follows by repeatedly dividing by \(X-a\) for distinct roots. If \(e<r\) and \(e\mid r\), then \(e\le\left\lfloor r/2\right\rfloor\). The number of elements of degree less than \(r\) is consequently at most \[\sum_{e=1}^{\left\lfloor r/2\right\rfloor}2^e<2^r,\] with the sum empty for \(r=1\). Some element of \(F\) has degree \(r\), and its monic minimal polynomial is the required irreducible polynomial. ◻