The Taylor cut lemma #

Let a straight-line program have gates that are polynomials with coefficients in a commutative ring K, of any degree and any arity, so that it computes a polynomial f_w ∈ K[X₀, …, X_{n-1}] on every wire w (wirePolynomial). Fix a field L that is a K-algebra, a point a ∈ L ^ n, and a set S of wires with complement T; let X_S and X_T be the inputs on the two sides and w(S) = |forward S| + |backward S| the number of signals crossing the split.

The Taylor cut lemma (exists_cut). There are subspaces V of directions supported on X_S and W of directions supported on X_T, with dim V + dim W ≥ n - w(S), such that

(a) every v ∈ V fixes every wire of T to first order: ∇f_t(a) · v = 0;
(b) every u ∈ W fixes every wire of S to first order: ∇f_s(a) · u = 0;
(c) for every wire, the Hessian at a pairs V with W to zero: vᵀ ∇²f_w(a) u = 0.

Proof. Run the program over the algebra L[s, t] = L[s][t] with s² = t² = 0, where at the input a + s v + t u every wire carries f(a) + s ∇f(a)·v + t ∇f(a)·u + s t vᵀ ∇²f(a) u. Let Z be the directions along which no crossing wire moves to first order; it is cut out by w(S) linear equations. Two jets a + s v and a + t u with v, u ∈ Z give every crossing wire the same value, so they have the same boundary key, and cut and paste (SingleCut.trace_mix) and the vanishing mixed second difference (trace_add_trace_eq_trace_mix_add_trace_mix) hold for them over L[s, t]. Comparing the coefficients of s, t and s t shows that Z is the sum of its parts V on X_S and W on X_T, and gives (a), (b) and (c).

The Jacobian consequence (blockRank_jacobian_add_blockRank_le). For the outputs O_S carried in S and O_T carried in T, rank J[O_T, X_S] + rank J[O_S, X_T] ≤ w(S), where J is the Jacobian of the outputs at a: by (a) and (b), V and W lie in the kernels of the two blocks.

The Hessian consequence (blockRank_hessian_le). For every combination ∑ₒ μₒ fₒ of the outputs, with coefficients in L, rank H[X_S, X_T] ≤ w(S), where H = ∑ₒ μₒ ∇²fₒ(a): by (c), V and W are orthogonal through H[X_S, X_T], which forces dim V + dim W ≤ n - rank H[X_S, X_T].

Both consequences hold over every field: no counting is involved, and the coefficients μ and the point a may lie in an extension of the coefficient field. Over a finite field the counting arguments of MultiOutput.Rank and MultiOutput.Quadratic give the same bounds for arbitrary gate functions; here the gates must be polynomials and the polynomials are the formal ones (FormallyComputes), which over an infinite field are determined by the functions (formallyComputes_of_computes).

Prior art. The use of the rank of a Hessian block to bound the communication between two parties evaluating a function of their inputs is due to Abelson (Lower bounds on information transfer in distributed computations, JACM 1980). Here it is applied to every cut of a circuit at once, as an algebraic counterpart of the single-cut criterion.

The Taylor cut lemma #

Formal evaluation #

The cut lemma #