A superquadratic separation between sensitivity and block sensitivity

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

Here k\le3M^2, r\ge\sqrt M, and M\ge3. Thus a labelling with the required property exists.□

Proof. Fix a predicate of radius R=H_0-q\in\{0,\ldots,d\} and an input x at which it is zero. If flipping one bit makes it one, some centre must be at distance exactly R+1 from x. There is at most one centre within distance d+1 of x: two such centres would have distance at most 2d+2<2L. Thus every successful bit flip must move towards the same centre, giving at most R+1\le d+1\le L possibilities. The bound on S_{0,1} is simply the number LM of input bits.

For adjacent inputs x,y, the triangle inequality gives D(x)\le D(y)+1, and the reverse inequality follows by symmetry. Hence |D(x)-D(y)|\le1. To change both predicates with distinct integer radii from zero to one, or both from one to zero, would require D to change by at least two. Both joint sensitivities are therefore zero.□

Proof. At level zero, D(0)=L>d, and the blocks E_j have the stated property because 0^{E_j}=z_j. Suppose the claim holds at level \ell-1. At the all-zero input, every target predicate is zero, so every clause fails at level \ell.

Enumerate the preceding-level block family as B_1,\ldots,B_{Mk^{\ell-1}}. For each row i and each family index h, take the union of the copies of B_h in all r children of row i. Flipping this union makes the strongest predicate in each of those children equal to one, so all targets for clause i hold. All gate children of clause i lie in other rows and remain zero, so its gates hold for every q. Thus every P_{\ell,q} is one after the flip. Within a row these unions are disjoint because the preceding-level blocks are disjoint in every child; unions from different rows are also disjoint. There are k\cdot Mk^{\ell-1}=Mk^\ell of them, each of size r\cdot Lr^{\ell-1}=Lr^\ell, as required.□

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

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.1. 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

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

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

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 3.1 by the corresponding powers of M gives

Consequently,

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

Let U_0=L, V_0=0, and define the comparison sequences by

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,

These bounds hold at \ell=0. Suppose they hold at every index less than some 1\leq\ell\leq d. First,

Next, summing the increments of U_j and using only the bounds at indices j<\ell, we obtain

The last inequality follows from (5), since

This completes the simultaneous induction. In particular, u_\ell\leq2L, which is the desired bound.□

Proof of Theorem 1.1. Fix any integer d\geq1 and choose an integer M\geq9^{d+1}. Lemma 2.1 provides the required tournament labels. Following the OR-balancing principle of Ambainis and Sun [AS11, Section 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

bits. By Lemma 2.3, 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 4.1 therefore gives

Each copy supplies M k^d pairwise disjoint blocks sensitive at zero, by Lemma 2.3. Taking their union over the disjoint copies gives a family of M^2k^d pairwise disjoint sensitive blocks for f at zero. In particular,

Since f is nonconstant, s(f)>0. Combining (8) and (9) yields

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.1 and form f as above. The resulting finite-dimensional total nonconstant function satisfies \bs(f)>C s(f)^2. Hence no universal quadratic constant exists.□

Proof. For an input x=(x_1,\ldots,x_a), put y=(g(x_1),\ldots,g(x_a)). A bit in child x_i is sensitive for f\circ g precisely when it is sensitive for g at x_i and coordinate i is sensitive for f at y. Thus

Now suppose g(0)=0. Let C_1,\ldots,C_p\subseteq[a] and D_1,\ldots,D_q\subseteq[b] be disjoint nonempty sensitive blocks for f and g at zero. Identify the coordinates of the composition with [a]\times[b]. For each 1\leq i\leq p and 1\leq j\leq q, set

These blocks are nonempty and pairwise disjoint: different i use disjoint sets of children, while for fixed i different j use disjoint coordinate sets in each child. Flipping E_{i,j} at zero makes precisely the children indexed by C_i output one, because g(0)=0 and D_j is sensitive there. The outer input therefore becomes 0^{C_i}, which changes the value of f. Hence every E_{i,j} is sensitive for f\circ g at zero. Choosing maximum families proves the stated block-sensitivity inequality; if either maximum is zero, the inequality is immediate.□

Proof. Fix d=9, choose an integer M\geq9^{10}, and choose any admissible labelling. Let f be the function constructed in the proof of Theorem 1.1 for these fixed parameters. Put

Here L=11, so (8) and (9) give s(f)\leq A and \bs(f,0)\geq B, while f(0)=0. Moreover,

In particular, A>1, B>A^2, and the fixed number

is greater than two.

Set F_1=f and, for m\geq1, set F_{m+1}=f\circ F_m using disjoint copies of F_m. Inductively, F_m is a total function on n^m bits, where n is the fixed seed dimension in (7), and F_m(0)=0. Lemma 4.2 gives

The latter bound proves nonconstancy and tends to infinity. Since A^\alpha=B, we also obtain

The same estimates give the explicit ratio bound

□