Exercise PLAN-318

Permutation-invariant operators on the tensor power of a fixed-dimension system are determined by only polynomially many parameters, via Schur-Weyl blocks and polynomial dimension bounds.

1. Schur-Weyl gives blocks indexed by diagrams with at most d rows.
2. Permutation invariance makes the operator identity on symmetric-group factors and free on unitary-group factors.
3. The parameter count is the sum over diagrams of squared unitary-piece dimensions.
4. Polynomially many diagrams times polynomially bounded dimensions give a polynomial total in n.

By Schur-Weyl duality the tensor power decomposes into blocks indexed by Young diagrams with at most d rows, each block a tensor product of a symmetric-group piece and a unitary-group piece. Permutation invariance, via the mutual-commutant structure, forces the operator to act as the identity on each symmetric-group factor and to be an arbitrary operator on each unitary-group factor; concretely the operator is a direct sum over diagrams of the identity on the symmetric-group piece tensored with a free operator on the unitary-group piece. The number of free parameters is therefore the sum over admissible diagrams of the squared dimension of the unitary-group piece. Two polynomial bounds control this. First, the number of admissible diagrams is at most the number of ways to fill d row lengths each between zero and n, bounded by n plus one to the power d, which is polynomial in n for fixed d. Second, the dimension of each unitary-group piece is bounded by a fixed polynomial in n of degree depending only on d, namely at most n plus one to the power d times d minus one over two. Multiplying a polynomial number of diagrams by a polynomial squared dimension gives a total parameter count polynomial in n with d fixed. Hence a permutation-invariant operator, though living in an exponentially large space, is pinned down by only polynomially many numbers.

1. Invokes the Schur-Weyl block decomposition into diagram-indexed blocks with at most d rows (1 weight)
2. Uses permutation invariance to force the operator to be identity on each symmetric-group factor and free on each unitary-group factor (1 weight)
3. States the parameter count is the sum over diagrams of the squared unitary-piece dimension (1 weight)
4. Applies the polynomial bound on the number of diagrams and the polynomial bound on unitary-piece dimensions to conclude a polynomial total in n (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

• website/research/sources.json

  leditzky-2025-repth-qit

  Source SHA-256: 9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae · MIT metadata only
• Primary source

Contract: 5211b9366f7a00d99bdc4a0ad1177369cd3538d680a2b99bec804d8695d60feb

Item digest: 73006cfae26652d2f1fde105a380b1da7f1b3994b6721ccaca20df28436a9ecc

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

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