Proof. Choose all edge labels independently and uniformly from \([r]\). For fixed \(I\) and fixed choices \((m_j)_{j\in I}\), the probability of all the stated equalities is \(r^{-\binom t2}\). There are at most \(k^t r^t\) choices to consider, so the probability of any violation is at most \[k^{16}r^{-104}\le (3M^2)^{16}(\sqrt M)^{-104} =3^{16}M^{-20}<1.\] Here \(k\le3M^2\), \(r\ge\sqrt M\), and \(M\ge3\). Thus a labelling with the required property exists. ◻

Proof. Fix \(\ell\), put \(H=H_\ell\) and \(Q=H+1\), and recall Equation (1). For predicate index \(q\), every target tests \(P_{\ell-1,Q}=1\) and every gate tests \(P_{\ell-1,Q-q}=0\) on its specified child. The targets of clause \(i\) lie in row \(i\), and its gates lie in distinct other rows. Thus each condition of a fixed clause uses a different child.

All flips below are flips of individual coordinates of the original Boolean input. Such a flip affects exactly one child. It may change several nested predicates of that child; we make no restriction on the number of thresholds it crosses. Nevertheless, at a fixed parent index it can change at most one condition of any fixed clause. A child may occur in several different clauses, so when counting possible flips over clauses we use a union bound.

Transitions from one. Fix an input where \(P_{\ell,q}=1\), and choose a clause satisfied there. Every flip taking this predicate to zero must break that fixed clause. It either changes a gate predicate from zero to one or changes a target predicate from one to zero. There are \(M^2\) gate children and \(r\) target children, giving at most \(M^2S'_0+rS'_1\) such flips.

Next fix \(q<q'\) and an input where both parent predicates are one. Choose a clause initially satisfied for \(q'\); nesting makes it satisfied for \(q\) as well. This same clause is fixed for all flips being counted. A flip taking both parent predicates to zero must either break one of its targets, accounting for at most \(rS'_1\) flips, or leave all its targets true and fail a gate even for \(q\). Put \[g=Q-q,\qquad g'=Q-q',\qquad 1\leq g'<g<Q.\] At such a gate, initially \(P_{\ell-1,g'}=0\) because the clause holds for \(q'\), and nesting gives \(P_{\ell-1,g}=0\). Failure of the gate for \(q\) after the flip means \(P_{\ell-1,g}=1\), and nesting then gives \(P_{\ell-1,g'}=1\). The two distinct child predicates therefore both change from zero to one. Each of the \(M^2\) gates contributes at most \(J'_0\) such flips. This proves both inequalities on the one side.

The initial candidate clauses at a zero. Fix \(q\) and an input \(x\) with \(P_{\ell,q}(x)=0\). Let \(\mathcal T\) be the set of clauses that at \(x\) fail exactly one target and no gate, and let \(\mathcal G\) be the set that fail exactly one gate and no target. These sets are determined by \(x\) and \(q\), before a flipped coordinate is chosen. Every flip making \(P_{\ell,q}\) one satisfies some previously false clause. Since only one condition of that clause can change, the clause belongs to \(\mathcal T\cup\mathcal G\), and its unique failed condition must be repaired.

For each \(j\in\mathcal T\), let \(m_j\in[r]\) be the position of its unique failed target. If \(i,j\in\mathcal T\) and \(i\to j\), clause \(i\) has a passing gate in child \((j,a(i,j))\). Its gate predicate \(P_{\ell-1,Q-q}\) is zero, so by nesting its target predicate \(P_{\ell-1,Q}\) is also zero. The unique failed target in row \(j\) is at position \(m_j\), forcing \(a(i,j)=m_j\). Consequently a set of \(t\) vertices in \(\mathcal T\) would violate Lemma 2. Thus \(|\mathcal T|<t\). Repairing a clause in this list requires changing its unique failed target from zero to one, and accounts for at most \(S'_0\) flips per clause. Their total contribution is at most \(tS'_0\).

All targets in the row of a vertex of \(\mathcal G\) are initially true. Hence an edge \(i\to j\) within \(\mathcal G\) gives a failed gate of clause \(i\): the gate child in row \(j\) has \(P_{\ell-1,Q}=1\), which forces \(P_{\ell-1,Q-q}=1\). A clause in \(\mathcal G\) has just one failed gate, so every outdegree in the induced tournament on \(\mathcal G\) is at most one. With \(m=|\mathcal G|\), counting its edges gives \[\frac{m(m-1)}2\leq m, \qquad\text{and hence}\qquad m\leq3.\] There is at most one vertex of outdegree zero in this induced tournament, since the edge between any two vertices leaves one of them.

If \(i\in\mathcal G\) has an outgoing edge \(i\to j\) inside \(\mathcal G\), that edge is its unique failed gate. On the corresponding child, initially \[P_{\ell-1,Q-q}=P_{\ell-1,Q}=1.\] Repairing the gate sets \(P_{\ell-1,Q-q}=0\) and therefore also sets \(P_{\ell-1,Q}=0\). The indices \(Q-q\) and \(Q\) are distinct because \(q\geq1\), so at most \(J'_1\) flips repair this clause. The fact that such a flip destroys a target in row \(j\) causes no problem: the accepting witness is clause \(i\), whose own targets and other gates are unchanged. The possible vertex with no outgoing edge inside \(\mathcal G\) contributes at most \(S'_1\), by counting flips of its unique failed gate. Since \(|\mathcal G|\leq3\), its entire contribution is at most \(S'_1+3J'_1\). Together with the target contribution this proves \(S_{\ell,0}\leq tS'_0+S'_1+3J'_1\).

Joint transitions from zero. Fix \(q<q'\) and an input \(x\) where both parent predicates are zero, and form the same initial lists \(\mathcal T,\mathcal G\) for the weaker index \(q\). Consider a flip making both predicates one, and choose any clause satisfied afterward for \(q'\). It is also satisfied afterward for \(q\), so it belongs to those fixed initial lists. The choice of this final witness may depend on the flipped coordinate; the lists themselves do not. A genuine final witness also had exactly one failed condition at \(q'\) initially, by the same distinct-child argument. Members of the weaker lists that have additional unrepaired failures at \(q'\) simply contribute no flips.

A witness in \(\mathcal T\) is counted by the preceding target bound \(tS'_0\). For a witness in \(\mathcal G\), let \(g=Q-q\) and \(g'=Q-q'\), so \(1\leq g'<g<Q\). Its unique failed gate at index \(q\) has \(P_{\ell-1,g}=1\) initially, and nesting gives \(P_{\ell-1,g'}=1\) initially as well. To satisfy the clause for \(q'\) afterward, the same child must have \(P_{\ell-1,g'}=0\), which forces \(P_{\ell-1,g}=0\). Thus both distinct child predicates change from one to zero, and each such clause contributes at most \(J'_1\). This reasoning applies also to the possible vertex with no outgoing edge inside \(\mathcal G\): the second parent index supplies the second child threshold, without requiring any initial target value at the failed gate. The gate contribution is therefore at most \(3J'_1\).

Every joint-success coordinate is thus counted by a clause in the fixed lists \(\mathcal T\) or \(\mathcal G\), so a union bound gives \(J_{\ell,0}\leq tS'_0+3J'_1\).

All bounds hold for every relevant input and for each fixed index or pair of indices, so taking the maxima gives the proposition. If \(H=1\), there is no pair of distinct parent indices and both joint inequalities hold by the empty-maximum convention. ◻

Proof. Define \[u_\ell=\max_{b\in\{0,1\}}\frac{S_{\ell,b}}{M^{\ell+b}}, \qquad v_\ell=\max_{b\in\{0,1\}}\frac{J_{\ell,b}}{M^{\ell+b}}, \qquad \epsilon=\frac{\max(r,t)}{M}.\] The base bounds in (2) give \(u_0\leq L\) and \(v_0=0\). For \(1\leq\ell\leq d\), dividing the four inequalities in Proposition 5 by the corresponding powers of \(M\) gives \[\begin{align*} \frac{S_{\ell,1}}{M^{\ell+1}} &\leq \left(1+\frac rM\right)u_{\ell-1}, &\qquad \frac{S_{\ell,0}}{M^\ell} &\leq \left(1+\frac tM\right)u_{\ell-1}+3v_{\ell-1},\\ \frac{J_{\ell,1}}{M^{\ell+1}} &\leq \frac rM u_{\ell-1}+v_{\ell-1}, & \frac{J_{\ell,0}}{M^\ell} &\leq \frac tM u_{\ell-1}+3v_{\ell-1}. \end{align*}\] Consequently, \[ \begin{split} u_\ell&\leq (1+\epsilon)u_{\ell-1}+3v_{\ell-1},\\ v_\ell&\leq \epsilon u_{\ell-1}+3v_{\ell-1}. \end{split} \tag{4}\] The forcing term for \(v_\ell\) is at most \(\epsilon u_{\ell-1}\), while its inherited contribution is multiplied by at most three. We therefore make \(\epsilon\) small compared with \(3^{-d}\). Since \(M\geq81\), both \(r=\lceil\sqrt M\rceil\leq2\sqrt M\) and \(t=16\leq2\sqrt M\). It follows that \[ \epsilon\leq\frac{2}{\sqrt M}\leq\frac{2}{3^{d+1}}. \tag{5}\]

Let \(U_0=L\), \(V_0=0\), and define the comparison sequences by \[U_\ell=(1+\epsilon)U_{\ell-1}+3V_{\ell-1}, \qquad V_\ell=\epsilon U_{\ell-1}+3V_{\ell-1}.\] All coefficients are nonnegative, so (4) implies \(u_\ell\leq U_\ell\) and \(v_\ell\leq V_\ell\) by induction. We prove simultaneously that, for \(0\leq\ell\leq d\), \[ U_\ell\leq2L, \qquad V_\ell\leq\epsilon L(3^\ell-1). \tag{6}\] These bounds hold at \(\ell=0\). Suppose they hold at every index less than some \(1\leq\ell\leq d\). First, \[V_\ell \leq 2\epsilon L+3\epsilon L(3^{\ell-1}-1) =\epsilon L(3^\ell-1).\] Next, summing the increments of \(U_j\) and using only the bounds at indices \(j<\ell\), we obtain \[\begin{align*} U_\ell &=L+\sum_{j=0}^{\ell-1}(\epsilon U_j+3V_j)\\ &\leq L+2\epsilon L\ell +3\epsilon L\sum_{j=0}^{\ell-1}(3^j-1)\\ &=L+\epsilon L\left[\frac32(3^\ell-1)-\ell\right] <2L. \end{align*}\] The last inequality follows from (5), since \[\epsilon\left[\frac32(3^\ell-1)-\ell\right] \leq\frac{3^{\ell+1}-3-2\ell}{3^{d+1}}<1.\] This completes the simultaneous induction. In particular, \(u_\ell\leq2L\), which is the desired bound. ◻

Proof of Theorem 1. Fix any integer \(d\geq1\) and choose an integer \(M\geq9^{d+1}\). Lemma 2 provides the required tournament labels. Following the OR-balancing principle of Ambainis and Sun (Ambainis and Sun 2011, sec. 4, Lemma 1), take \(f\) to be the OR of \(M\) disjoint copies of \(P_{d,1}\). Each copy has dimension \(LM(kr)^d\), so \(f\) is a total Boolean function on \[ n=LM^2(kr)^d \tag{7}\] bits. By Lemma 4, every copy is zero at its zero input, and a block from its stated family makes that copy one. Thus \(f(0)=0\) and \(f\) is nonconstant.

At a zero input of \(f\), every copy is zero, and its sensitivity is at most \(M S_{d,0}\). At a one input, either at least two copies accept, in which case no single bit can change the OR to zero, or exactly one copy accepts. In the latter case every sensitive bit belongs to that accepting copy, so there are at most \(S_{d,1}\) such bits. Lemma 6 therefore gives \[ s(f)\leq\max\{M S_{d,0},S_{d,1}\} \leq2L M^{d+1}. \tag{8}\]

Each copy supplies \(M k^d\) pairwise disjoint blocks sensitive at zero, by Lemma 4. Taking their union over the disjoint copies gives a family of \(M^2k^d\) pairwise disjoint sensitive blocks for \(f\) at zero. In particular, \[ \operatorname{bs}(f,0)\geq M^2k^d. \tag{9}\] Since \(f\) is nonconstant, \(s(f)>0\). Combining (8) and (9) yields \[ \frac{\operatorname{bs}(f)}{s(f)^2} \geq\frac{\operatorname{bs}(f,0)}{s(f)^2} \geq\frac{(k/M^2)^d}{4L^2} \geq\frac{2^d}{4(d+2)^2}. \tag{10}\] The last expression tends to infinity as \(d\) tends to infinity. For any proposed constant \(C\), first choose \(d\) so that this expression exceeds \(C\), then choose \(M\geq9^{d+1}\), then choose labels supplied by Lemma 2 and form \(f\) as above. The resulting finite-dimensional total nonconstant function satisfies \(\operatorname{bs}(f)>C s(f)^2\). Hence no universal quadratic constant exists. ◻