Exercise SP-114

An additive polynomial array q(u(x)+v(y)) factorizes with inner dimension deg(q)+1 via shifted Taylor coefficients, bounding its rank by the degree alone.

1. Taylor-expanding q about u(x) gives q(u(x)+v(y)) = sum_{i<=d} c_i(u(x)) v(y)^i, a sum of d+1 separable terms.
2. These terms assemble into a product A*B with inner dimension d+1 (the explicit finite-width factorization).
3. A matrix product has rank at most its inner dimension, so rank F <= d+1, controlled only by deg q.

Step 1 (shifted-Taylor expansion of an additive argument): fix a row x and let a = u(x). Expand q about a: for any real s, q(a + s) = sum_{i=0}^{d} c_i(a) s^i, where c_i(a) is the degree-i coefficient of the Taylor expansion of q about a (the sum stops at d because deg q <= d, so the shifted polynomial also has degree <= d). Step 2 (separate the variables): apply this with a = u(x) and s = v(y): F(x,y) = q(u(x) + v(y)) = sum_{i=0}^{d} c_i(u(x)) * v(y)^i. Each summand is a product of a function of x alone, A(x,i) := c_i(u(x)), and a function of y alone, B(i,y) := v(y)^i. Step 3 (read off the matrix product): define A as the (number of rows) by (d+1) matrix with entries A(x,i) and B as the (d+1) by (number of columns) matrix with entries B(i,y). Then (A B)(x,y) = sum_{i=0}^{d} A(x,i) B(i,y) = F(x,y), i.e. F = A * B exactly, with inner dimension d+1. Step 4 (rank bound): the rank of a product A*B is at most the number of columns of A, which is d+1; equivalently the inner dimension bounds the rank. Hence rank F <= d+1. Why the inner dimension is degree-controlled: the only data that produce the finite factorization are the d+1 Taylor coefficients of q; the number of distinct values of u and v (i.e. the matrix dimensions) is irrelevant. The additive structure u(x)+v(y) is essential — it is what lets the single-variable Taylor expansion separate the two indices into a sum of d+1 rank-one pieces. A generic bivariate function without this additive polynomial structure would have no such bound.

1. Expands q about a=u(x) as a degree-<=d polynomial in the shift s, truncating at d because deg q <= d. (1 weight)
2. Substitutes s=v(y) to write F(x,y)=sum_{i=0}^d c_i(u(x)) v(y)^i, separating each term into a function of x times a function of y. (1 weight)
3. Assembles the matrices A (rows x (d+1)) and B ((d+1) x cols) so that A*B = F with inner dimension d+1. (1 weight)
4. Concludes rank F <= d+1 via rank(A*B) <= inner dimension, and explains the bound depends only on deg q, not matrix size, with additivity essential. (1 weight)

No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.

Read the Lean track and existing diagnostic warmups

• QuantumBlockEncoding/HermiteCutRank.lean

  lines 23-50: FactorsThrough F := exists A : Matrix a i R, B : Matrix i b R, F = A*B; FactorsThrough.rank_le : F.rank <= Fintype.card i; polynomial_add_factorization (p) (d) (hd: p.natDegree <= d) (u v) : FactorsThrough (i := Fin (d+1)) (fun x y => p.eval (u x + v y)) via A x i = (taylor (u x) p).coeff i, B i y = v y^i; polynomial_add_rank_le : rank <= d+1

  Source SHA-256: c0f038bd889c77163967c71df5f5987082f4b79ab7db2b7822efcdda7234aaf2 · MIT (repository LICENSE)

Contract: 6e2d748a68eaa027d7f2a2b760f7eea213c3a9f48c6b1eda1d5c108347afef37

Item digest: 8692de94902e02e828e3bcd36f059d65ad388327e3f3824390ab974de1fa729b

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 3. This is not measured graph distance or model difficulty.