Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Generic Quantum Fourier Transforms

Definition
QAlgorithms_Papers_Independent_Intakenext100_P78

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Generic Quantum Fourier Transforms (arXiv:quant-ph/0304064) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • packDigits: Fixed-length digit packing; no data-dependent choice of binary encoding. Source: PDF p.6, product-coset and path registers.
  • encodedWave: Linear embedding of amplitudes into explicitly named computational codes. Unused wires are zero because every code is a padded binary integer. Source: PDF pp.1–3,6.
  • normalizedAmplitudes: The source's normalization of the entire input, not of each coset piece. Source: PDF pp.1–2 and equation (4), p.6.
  • realizesEncodedTransform: A fixed clean-input/clean-output implementation on every normalized input; the circuit is chosen outside the quantifier over f. Invalid binary strings are unconstrained. Source: Definition 1, p.3, and equations (4)–(5), p.6.
  • SymmetricCosetDigits: The transversal digit at level i+1 specifies the position to which the new letter is moved. This is the point-stabilizer tower of PDF pp.4–5,8.
  • nextIndex: Next letter, with a total harmless value at the unused last position.
  • BoundedYoungPath: A standard tableau is an injective sequence of boxes whose every prefix is a lower ideal. Coordinates are bounded by n; no tableau with n boxes is lost. Source: Bratteli paths, p.4, and Young orthogonal basis, pp.5,8. The concrete convention follows accepted Support21.P07/ Renew46.P26; these paper modules are not imported.
  • youngPathEndpoint: The actual endpoint Young diagram, computed from the path.
  • YoungEndpointPaths: Paths with a fixed endpoint. Unoccupied shapes contribute no rows.
  • SymmetricFrequency: Fourier labels are pairs of paths with the same endpoint, including all diagonal pairs; the endpoint itself is recorded once. Source: PDF pp.4–6.
  • boundedBoxContent: Column minus row, fixing the sign of Young's orthogonal coefficients.
  • youngAdjacent: The Young orthogonal matrix of the adjacent transposition (i,i+1), with row U and column T. Same-row/column cases precede division; the mixed case has positive square root and r=content(i+1)-content(i). Source: named Young orthogonal realization, PDF pp.5,8; coefficient convention is the accepted Support21.P07.youngActionCoefficient, written out locally.
  • symmetricWord: The chosen coset product, largest subgroup first: the level-i factor is s_digit ... s_(i-1). Source: input encoding p.6 and point stabilizers p.8.
  • symmetricElement: The actual permutation specified by the source transversal digits.
  • symmetricMatrix: The representation matrix is computed from that same word, in the fixed Young orthogonal basis, before any implementation is quantified.
  • symmetricFourier: Normalized plus-sign Fourier transform: no conjugation or inverse g. The representation dimension is the number of tableaux of its shape. Source: Definition 1, PDF p.3; symmetric application, pp.5,8.
  • symmetricInputCode: Binary encoding of the chosen transversal digits.
  • tableauDigits: Each tableau is encoded by its successive row/column coordinates. The shape is recoverable from either tableau and is not independently chosen.
  • symmetricOutputCode: Fixed output encoding of the two paths. Extra wires are zero.
  • CliffordElement: Coordinates (-1)^s x_n^u_n ... x_1^u_1, including the central sign. Source: finite Clifford monomial groups, PDF p.8.
  • cliffordCross: The crossing sign for descending monomials: a left x_i crosses a right x_j exactly when i<j. This fixes the actual group law, including -1.
  • cliffordMul: Multiplication of signed ordered monomials.
  • centralSignScalar: Scalar corresponding to a central sign bit.
  • matrixX: Pauli matrices used only to specify the based irreducibles explicitly.
  • matrixY: The Y sign fixes the phase convention of the adapted Clifford rows.
  • matrixZ: The first Clifford generator is diagonal in its adapted row basis.
  • CliffordSector: Even rank has one nonlinear irrep; odd rank has two.
  • cliffordGenerator: The explicit adapted irreducible generators are Y^r Z and Y^r X on successive tensor factors; at odd rank the last is either sign of Y^(tensor m). Thus restriction to the earlier even level repeats literally equal blocks, while the next odd level is selected by the last row bit. Source: p.8.
  • CliffordFrequency: All 2^n linear characters, and all matrix entries of the nonlinear irrep(s). No multiplicity edge is identified with another. Source: p.8.
  • cliffordCoefficient: The based matrix element at an actual signed monomial. The sign acts trivially in the linear characters and as -I in the nonlinear sectors.
  • cliffordDimension: Definition 1's dimension factor for each Clifford Fourier row.
  • cliffordFourier: The source's normalized plus Fourier transform of the signed monomial coordinates, whose group order is 2^(n+1). Source: PDF pp.3,8.
  • cliffordInputCode: Top-down monomial tower coordinates with the central sign at the bottom.
  • cliffordOutputCode: Character sectors followed by nonlinear block/row/column sectors.
  • QuaternionFrequency: All four one-dimensional characters, and the row/column entries of the n-1 two-dimensional induced irreducibles. Source: cyclic subgroup, p.10.
  • quaternionCyclicPhase: The plus-sign cyclic character phase, not its complex conjugate. Used only with N=2n>0 in the quaternion theorem. Source: Definition 1, p.3.
  • quaternionCharacterX: Scalar of gamma in the character whose a-value is (-1)^e. Its square is (-1)^(ne), including odd n; the second bit chooses the root.
  • quaternionTwiddle: The source square root C(gamma), before the separate orbit permutation.
  • quaternionCoefficient: Complete fixed cyclic-subgroup-adapted matrix coefficients. For the 2D sector k=1,...,n-1, a is diag(z,z^-1) and gamma is C_k times the swap, where C_k=1 for even k and C_k=i for odd k, as on source p.10. The orbit permutation and the nonsplit square gamma^2=a^n are retained; the scalar C(gamma) is not substituted for the whole induced matrix. Source: PDF p.10; QuaternionGroup uses constructors a(j), xa(j)=gamma*a^j.
  • quaternionDimension: The irreducible dimension entering the square-root normalization.
  • quaternionFourier: The normalized plus QFT of the actual Mathlib QuaternionGroup. Source: Definition 1 p.3 and the general-n application p.10.
  • quaternionInputCode: Source cyclic-coset encoding: a(j) has code j, gamma*a(j) code 2n+j.
  • quaternionOutputCode: Fixed character/block/row/column ordering, with no arbitrary relabeling.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_SpectralFilter

/-!
Generic Quantum Fourier Transforms, arXiv:quant-ph/0304064v1.
The three concrete targets below are defined independently of their circuits.
Only the literal ideal one/two-qubit gate-count claim is stated. Other planned
nodes are accounted for in HARD.md and GAPS.json, without replacement lemmas.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P78

open QAlgorithms

attribute [local instance] Classical.propDecidable

/-- Fixed-length digit packing; no data-dependent choice of binary encoding.
Source: PDF p.6, product-coset and path registers. -/
def packDigits (width : ℕ) (digits : List ℕ) : ℕ :=
  digits.foldr (fun digit rest => digit + 2 ^ width * rest) 0

/-- Linear embedding of amplitudes into explicitly named computational codes.
Unused wires are zero because every code is a padded binary integer.
Source: PDF pp.1–3,6. -/
def encodedWave {X : Type*} [Fintype X] {q : ℕ}
    (code : X → Qubits q) (f : X → ℂ) : EuclideanSpace ℂ (Qubits q) :=
  ∑ x, f x • ket (code x)

/-- The source's normalization of the entire input, not of each coset piece.
Source: PDF pp.1–2 and equation (4), p.6. -/
def normalizedAmplitudes {X : Type*} [Fintype X] (f : X → ℂ) : Prop :=
  ∑ x, Complex.normSq (f x) = 1

/-- A fixed clean-input/clean-output implementation on every normalized input;
the circuit is chosen outside the quantifier over f. Invalid binary strings
are unconstrained. Source: Definition 1, p.3, and equations (4)–(5), p.6. -/
def realizesEncodedTransform {X Y : Type*} [Fintype X] [Fintype Y] {q : ℕ}
    (c : Circuit oneTwoQubitGateSet q) (input : X → Qubits q)
    (output : Y → Qubits q) (F : (X → ℂ) → (Y → ℂ)) : Prop :=
  ∀ f, normalizedAmplitudes f →
    act c.unitary (encodedWave input f) = encodedWave output (F f)

/-- Empty digit strings have the zero code. -/
example (width : ℕ) : packDigits width [] = 0 := rfl

/-- The zero amplitude function is not a normalized state. -/
example {X : Type*} [Fintype X] : ¬ normalizedAmplitudes (fun _ : X => (0 : ℂ)) := by
  simp [normalizedAmplitudes]

/-- The transversal digit at level i+1 specifies the position to which the
new letter is moved. This is the point-stabilizer tower of PDF pp.4–5,8. -/
abbrev SymmetricCosetDigits (n : ℕ) := (i : Fin n) → Fin (i.val + 1)

/-- Next letter, with a total harmless value at the unused last position. -/
def nextIndex {n : ℕ} (i : Fin n) : Fin n :=
  if h : i.val + 1 < n then ⟨i.val + 1, h⟩ else i

/-- A standard tableau is an injective sequence of boxes whose every prefix
is a lower ideal. Coordinates are bounded by n; no tableau with n boxes is
lost. Source: Bratteli paths, p.4, and Young orthogonal basis, pp.5,8.
The concrete convention follows accepted Support21.P07/ Renew46.P26;
these paper modules are not imported. -/
abbrev BoundedYoungPath (n : ℕ) :=
  {t : Fin n → Fin n × Fin n // Function.Injective t ∧
    ∀ m : ℕ, m ≤ n → IsLowerSet {b | ∃ i : Fin n, i.val < m ∧ t i = b}}

/-- The actual endpoint Young diagram, computed from the path. -/
def youngPathEndpoint {n : ℕ} (T : BoundedYoungPath n) : Finset (Fin n × Fin n) :=
  Finset.univ.image T.val

/-- Paths with a fixed endpoint. Unoccupied shapes contribute no rows. -/
abbrev YoungEndpointPaths (n : ℕ) (shape : Finset (Fin n × Fin n)) :=
  {T : BoundedYoungPath n // youngPathEndpoint T = shape}

/-- Fourier labels are pairs of paths with the same endpoint,
including all diagonal pairs; the endpoint itself is recorded once.
Source: PDF pp.4–6. -/
abbrev SymmetricFrequency (n : ℕ) :=
  (shape : Finset (Fin n × Fin n)) × (YoungEndpointPaths n shape × YoungEndpointPaths n shape)

/-- Column minus row, fixing the sign of Young's orthogonal coefficients. -/
def boundedBoxContent {n : ℕ} (b : Fin n × Fin n) : ℤ :=
  (b.2.val : ℤ) - (b.1.val : ℤ)

/-- The Young orthogonal matrix of the adjacent transposition (i,i+1), with
row U and column T. Same-row/column cases precede division; the mixed case
has positive square root and r=content(i+1)-content(i).
Source: named Young orthogonal realization, PDF pp.5,8; coefficient convention
is the accepted Support21.P07.youngActionCoefficient, written out locally. -/
def youngAdjacent {n : ℕ} (shape : Finset (Fin n × Fin n)) (i : Fin n) :
    Matrix (YoungEndpointPaths n shape) (YoungEndpointPaths n shape) ℂ := fun U T =>
  let a := T.val.val i
  let b := T.val.val (nextIndex i)
  let r : ℝ := ((boundedBoxContent b - boundedBoxContent a : ℤ) : ℝ)
  if a.1 = b.1 then (if U = T then 1 else 0)
  else if a.2 = b.2 then (if U = T then -1 else 0)
  else if U = T then (r⁻¹ : ℝ)
  else if U.val.val = T.val.val ∘ Equiv.swap i (nextIndex i) then
    (Real.sqrt (1 - r⁻¹ ^ 2) : ℝ)
  else 0

/-- The chosen coset product, largest subgroup first: the level-i factor is
s_digit ... s_(i-1). Source: input encoding p.6 and point stabilizers p.8. -/
def symmetricWord {n : ℕ} (x : SymmetricCosetDigits n) : List (Fin n) :=
  (List.finRange n).reverse.flatMap fun level =>
    (List.finRange n).filter fun j => decide ((x level).val ≤ j.val ∧ j.val < level.val)

/-- The actual permutation specified by the source transversal digits. -/
def symmetricElement {n : ℕ} (x : SymmetricCosetDigits n) : Equiv.Perm (Fin n) :=
  ((symmetricWord x).map fun i => Equiv.swap i (nextIndex i)).prod

/-- The representation matrix is computed from that same word, in the fixed
Young orthogonal basis, before any implementation is quantified. -/
def symmetricMatrix {n : ℕ} (x : SymmetricCosetDigits n)
    (shape : Finset (Fin n × Fin n)) :
    Matrix (YoungEndpointPaths n shape) (YoungEndpointPaths n shape) ℂ :=
  ((symmetricWord x).map (youngAdjacent shape)).prod

/-- Normalized plus-sign Fourier transform: no conjugation or inverse g.
The representation dimension is the number of tableaux of its shape.
Source: Definition 1, PDF p.3; symmetric application, pp.5,8. -/
def symmetricFourier {n : ℕ} (f : SymmetricCosetDigits n → ℂ)
    (y : SymmetricFrequency n) : ℂ :=
  (Real.sqrt ((Fintype.card (YoungEndpointPaths n y.1) : ℝ) / (n.factorial : ℝ)) : ℂ) *
    ∑ x, f x * symmetricMatrix x y.1 y.2.1 y.2.2

/-- Binary encoding of the chosen transversal digits. -/
def symmetricInputCode (n q : ℕ) (x : SymmetricCosetDigits n) : Qubits q :=
  natToBits q (packDigits (Nat.clog 2 (n + 1)) (List.ofFn fun i => (x i).val))

/-- Each tableau is encoded by its successive row/column coordinates.
The shape is recoverable from either tableau and is not independently chosen. -/
def tableauDigits {n : ℕ} (T : BoundedYoungPath n) : List ℕ :=
  (List.ofFn fun i => [((T.val i).1).val, ((T.val i).2).val]).flatten

/-- Fixed output encoding of the two paths. Extra wires are zero. -/
def symmetricOutputCode (n q : ℕ) (y : SymmetricFrequency n) : Qubits q :=
  natToBits q (packDigits (Nat.clog 2 (n + 1))
    (tableauDigits y.2.1.val ++ tableauDigits y.2.2.val))

/-- A tableau's shape is computed from its boxes, never from a free label. -/
example {n : ℕ} (T : BoundedYoungPath n) :
    youngPathEndpoint T = Finset.univ.image T.val := rfl

/-- The empty word evaluates to the identity matrix on every shape sector. -/
example {n : ℕ} (shape : Finset (Fin n × Fin n)) :
    (([] : List (Fin n)).map (youngAdjacent shape)).prod = 1 := rfl

/-- Coordinates (-1)^s x_n^u_n ... x_1^u_1, including the central sign.
Source: finite Clifford monomial groups, PDF p.8. -/
abbrev CliffordElement (n : ℕ) := Bool × Qubits n

/-- The crossing sign for descending monomials: a left x_i crosses a right
x_j exactly when i<j. This fixes the actual group law, including -1. -/
def cliffordCross {n : ℕ} (u v : Qubits n) : Bool :=
  decide (Odd (∑ i : Fin n, ∑ j : Fin n,
    if i < j ∧ u i = true ∧ v j = true then (1 : ℕ) else 0))

/-- Multiplication of signed ordered monomials. -/
def cliffordMul {n : ℕ} (g h : CliffordElement n) : CliffordElement n :=
  (Bool.xor (Bool.xor g.1 h.1) (cliffordCross g.2 h.2),
    fun i => Bool.xor (g.2 i) (h.2 i))

/-- Scalar corresponding to a central sign bit. -/
def centralSignScalar (b : Bool) : ℂ := if b then -1 else 1

/-- Pauli matrices used only to specify the based irreducibles explicitly. -/
def matrixX : Matrix Bool Bool ℂ := fun r s => if r = s then 0 else 1

/-- The Y sign fixes the phase convention of the adapted Clifford rows. -/
def matrixY : Matrix Bool Bool ℂ := fun r s =>
  if r = s then 0 else if r then Complex.I else -Complex.I

/-- The first Clifford generator is diagonal in its adapted row basis. -/
def matrixZ : Matrix Bool Bool ℂ := fun r s =>
  if r = s then centralSignScalar r else 0

/-- Even rank has one nonlinear irrep; odd rank has two. -/
abbrev CliffordSector (n : ℕ) := {b : Bool // n % 2 = 1 ∨ b = false}

/-- The explicit adapted irreducible generators are Y^r Z and Y^r X on
successive tensor factors; at odd rank the last is either sign of Y^(tensor m).
Thus restriction to the earlier even level repeats literally equal blocks,
while the next odd level is selected by the last row bit. Source: p.8. -/
def cliffordGenerator {n : ℕ} (sector : CliffordSector n) (i : Fin n) :
    Matrix (Qubits (n / 2)) (Qubits (n / 2)) ℂ := fun r s =>
  if i.val < 2 * (n / 2) then
    ∏ a : Fin (n / 2),
      if a.val < i.val / 2 then matrixY (r a) (s a)
      else if a.val = i.val / 2 then
        (if i.val % 2 = 0 then matrixZ else matrixX) (r a) (s a)
      else if r a = s a then 1 else 0
  else centralSignScalar sector.val * ∏ a : Fin (n / 2), matrixY (r a) (s a)

/-- All 2^n linear characters, and all matrix entries of the nonlinear
irrep(s). No multiplicity edge is identified with another. Source: p.8. -/
abbrev CliffordFrequency (n : ℕ) :=
  Qubits n ⊕ (CliffordSector n × Qubits (n / 2) × Qubits (n / 2))

/-- The based matrix element at an actual signed monomial. The sign acts
trivially in the linear characters and as -I in the nonlinear sectors. -/
def cliffordCoefficient {n : ℕ} (y : CliffordFrequency n) (g : CliffordElement n) : ℂ :=
  match y with
  | .inl v => ∏ i : Fin n, if g.2 i then centralSignScalar (v i) else 1
  | .inr t => centralSignScalar g.1 *
      ((((List.finRange n).reverse.filter fun i => g.2 i).map
        (cliffordGenerator t.1)).prod) t.2.1 t.2.2

/-- Definition 1's dimension factor for each Clifford Fourier row. -/
def cliffordDimension {n : ℕ} : CliffordFrequency n → ℕ
  | .inl _ => 1
  | .inr _ => 2 ^ (n / 2)

/-- The source's normalized plus Fourier transform of the signed monomial
coordinates, whose group order is 2^(n+1). Source: PDF pp.3,8. -/
def cliffordFourier {n : ℕ} (f : CliffordElement n → ℂ) (y : CliffordFrequency n) : ℂ :=
  (Real.sqrt ((cliffordDimension y : ℝ) / (2 ^ (n + 1) : ℝ)) : ℂ) *
    ∑ g, f g * cliffordCoefficient y g

/-- Top-down monomial tower coordinates with the central sign at the bottom. -/
def cliffordInputCode (n q : ℕ) (g : CliffordElement n) : Qubits q :=
  natToBits q ((if g.1 then 2 ^ n else 0) + bitsToNat g.2)

/-- Character sectors followed by nonlinear block/row/column sectors. -/
def cliffordOutputCode (n q : ℕ) (y : CliffordFrequency n) : Qubits q :=
  natToBits q (match y with
    | .inl v => bitsToNat v
    | .inr t => 2 ^ n + (if t.1.val then 2 ^ (2 * (n / 2)) else 0) +
        bitsToNat t.2.1 * 2 ^ (n / 2) + bitsToNat t.2.2)

/-- The central sign is a nontrivial scalar, even though linear characters
kill it. This distinguishes the source group from its Abelian quotient. -/
example : centralSignScalar true = -1 ∧ centralSignScalar false = 1 := ⟨rfl, rfl⟩

/-- One concrete phase convention in the nonlinear adapted basis. -/
example : matrixY false true = -Complex.I := rfl

/-- All four one-dimensional characters, and the row/column entries of the
n-1 two-dimensional induced irreducibles. Source: cyclic subgroup, p.10. -/
abbrev QuaternionFrequency (n : ℕ) :=
  (Bool × Bool) ⊕ (Fin (n - 1) × Bool × Bool)

/-- The plus-sign cyclic character phase, not its complex conjugate.
Used only with N=2n>0 in the quaternion theorem. Source: Definition 1, p.3. -/
def quaternionCyclicPhase (N k j : ℕ) : ℂ :=
  Complex.exp (((2 * Real.pi * (k : ℝ) * (j : ℝ) / (N : ℝ)) : ℝ) * Complex.I)

/-- Scalar of gamma in the character whose a-value is (-1)^e.
Its square is (-1)^(ne), including odd n; the second bit chooses the root. -/
def quaternionCharacterX (n : ℕ) (e b : Bool) : ℂ :=
  centralSignScalar b * (if e = true ∧ Odd n then Complex.I else 1)

/-- The source square root C(gamma), before the separate orbit permutation. -/
def quaternionTwiddle (k : ℕ) : ℂ := if Even k then 1 else Complex.I

/-- Complete fixed cyclic-subgroup-adapted matrix coefficients. For the
2D sector k=1,...,n-1, a is diag(z,z^-1) and gamma is C_k times the swap,
where C_k=1 for even k and C_k=i for odd k, as on source p.10.
The orbit permutation and the nonsplit square gamma^2=a^n are retained;
the scalar C(gamma) is not substituted for the whole induced matrix.
Source: PDF p.10; QuaternionGroup uses constructors a(j), xa(j)=gamma*a^j. -/
def quaternionCoefficient {n : ℕ} (y : QuaternionFrequency n)
    (g : QuaternionGroup n) : ℂ :=
  match y with
  | .inl eb =>
    match g with
    | .a j => centralSignScalar eb.1 ^ j.val
    | .xa j => quaternionCharacterX n eb.1 eb.2 * centralSignScalar eb.1 ^ j.val
  | .inr t =>
    let z := quaternionCyclicPhase (2 * n) (t.1.val + 1)
    match g with
    | .a j => if t.2.1 = t.2.2 then
        (if t.2.1 then star (z j.val) else z j.val) else 0
    | .xa j => if t.2.1 = t.2.2 then 0 else
        quaternionTwiddle (t.1.val + 1) * (if t.2.1 then z j.val else star (z j.val))

/-- The odd character uses the source scalar i, not an entire scalar irrep. -/
example : quaternionTwiddle 1 = Complex.I := by
  norm_num [quaternionTwiddle]

/-- The irreducible dimension entering the square-root normalization. -/
def quaternionDimension {n : ℕ} : QuaternionFrequency n → ℕ
  | .inl _ => 1
  | .inr _ => 2

/-- The normalized plus QFT of the actual Mathlib QuaternionGroup.
Source: Definition 1 p.3 and the general-n application p.10. -/
def quaternionFourier {n : ℕ} [NeZero n] (f : QuaternionGroup n → ℂ)
    (y : QuaternionFrequency n) : ℂ :=
  (Real.sqrt ((quaternionDimension y : ℝ) / (4 * n : ℝ)) : ℂ) *
    ∑ g, f g * quaternionCoefficient y g

/-- Source cyclic-coset encoding: a(j) has code j, gamma*a(j) code 2n+j. -/
def quaternionInputCode (n q : ℕ) : QuaternionGroup n → Qubits q
  | .a j => natToBits q j.val
  | .xa j => natToBits q (2 * n + j.val)

/-- Fixed character/block/row/column ordering, with no arbitrary relabeling. -/
def quaternionOutputCode (n q : ℕ) (y : QuaternionFrequency n) : Qubits q :=
  natToBits q (match y with
    | .inl eb => (if eb.1 then 2 else 0) + (if eb.2 then 1 else 0)
    | .inr t => 4 + 4 * t.1.val + (if t.2.1 then 2 else 0) + (if t.2.2 then 1 else 0))

/-- Q8 has the nonsplit square gamma^2=a^2, not gamma^2=1. -/
example : (QuaternionGroup.xa (0 : ZMod 4) : QuaternionGroup 2) *
    QuaternionGroup.xa 0 = QuaternionGroup.a 2 := by
  rw [QuaternionGroup.xa_mul_xa]
  congr 1

end QAlgorithms.Papers.Independent.Intakenext100.P78
Source
Generic Quantum Fourier Transforms, arXiv:quant-ph/0304064v1, https://arxiv.org/abs/quant-ph/0304064v1
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Intakenext100.P78.BoundedYoungPath

For each natural number nnn, this abbreviates the type of injective maps t:{0,…,n−1}→{0,…,n−1}2t:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}^2t:{0,…,n−1}→{0,…,n−1}2 such that, for every natural number m≤nm\le nm≤n, the prefix set Sm={t(i):0≤i<m}S_m=\{t(i):0\le i<m\}Sm​={t(i):0≤i<m} is downward closed in the coordinatewise order on the grid: whenever (a,b)∈Sm(a,b)\in S_m(a,b)∈Sm​ and 0≤a′≤a0\le a'\le a0≤a′≤a, 0≤b′≤b0\le b'\le b0≤b′≤b, one has (a′,b′)∈Sm(a',b')\in S_m(a′,b′)∈Sm​. This includes the empty prefix m=0m=0m=0 and the complete prefix m=nm=nm=n. For n=0n=0n=0, the single empty map satisfies these conditions.

QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordElement

For every natural number nnn, this abbreviates the type of pairs (b,u)(b,u)(b,u), where bbb is a Boolean and u:{0,…,n−1}→{false,true}u:\{0,\ldots,n-1\}\to\{\mathrm{false},\mathrm{true}\}u:{0,…,n−1}→{false,true} is an nnn-bit string. For n=0n=0n=0, the string is uniquely empty, so there are two such pairs. This abbreviation itself specifies no multiplication.

QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordFrequency

For every natural number nnn, this defines a disjoint union of two kinds of labels: a Boolean string vvv of length nnn, or a triple (b,r,s)(b,r,s)(b,r,s), where r,sr,sr,s are Boolean strings of length ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ and bbb is Boolean with n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false. The two kinds remain distinct even when their component strings are empty. In particular, at n=0n=0n=0 there is one label of each kind.

QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordSector

For every natural number nnn, this defines the type of Boolean values bbb satisfying n mod 2=1n\bmod 2=1nmod2=1 or b=falseb=\mathrm{false}b=false. Thus both Boolean values are allowed when nnn is odd, while only false\mathrm{false}false is allowed when nnn is even, including n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P78.QuaternionFrequency

For every natural number nnn, the frequency-label type is the disjoint union

({false,true}2)  ⊔  ({0,…,n−2}×{false,true}2).(\{\mathrm{false},\mathrm{true}\}^2)\;\sqcup\; \bigl(\{0,\ldots,n-2\}\times\{\mathrm{false},\mathrm{true}\}^2\bigr).({false,true}2)⊔({0,…,n−2}×{false,true}2).

The first summand consists of four Boolean-pair labels; the second consists of triples (t,r,s)(t,r,s)(t,r,s), where t<n−1t<n-1t<n−1 and r,sr,sr,s are Boolean. Here n−1n-1n−1 is natural-number subtraction, so the second summand is empty when n=0n=0n=0 or n=1n=1n=1.

QAlgorithms.Papers.Independent.Intakenext100.P78.SymmetricCosetDigits

For each natural number nnn, this abbreviates the type of sequences (x0,…,xn−1)(x_0,\ldots,x_{n-1})(x0​,…,xn−1​) of natural numbers satisfying 0≤xi<i+10\le x_i<i+10≤xi​<i+1, equivalently 0≤xi≤i0\le x_i\le i0≤xi​≤i, for every 0≤i<n0\le i<n0≤i<n. In particular, x0=0x_0=0x0​=0 whenever n>0n>0n>0. For n=0n=0n=0, this type has the single empty sequence.

QAlgorithms.Papers.Independent.Intakenext100.P78.SymmetricFrequency

For each natural number nnn, this abbreviates the type of triples (S,U,T)(S,U,T)(S,U,T), where SSS is a finite subset of {0,…,n−1}2\{0,\ldots,n-1\}^2{0,…,n−1}2, and U,TU,TU,T are two, not necessarily distinct, injective maps from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} into this grid. Every prefix of each map must be downward closed in the coordinatewise order, and both complete images must equal SSS. Consequently, any triple has a downward-closed shape SSS of cardinality nnn; shapes admitting no such paths contribute no triples. For n=0n=0n=0, there is a single triple consisting of the empty shape and two empty paths.

QAlgorithms.Papers.Independent.Intakenext100.P78.YoungEndpointPaths

For any natural number nnn and finite subset SSS of the grid {0,…,n−1}2\{0,\ldots,n-1\}^2{0,…,n−1}2, this abbreviates the type of injective maps t:{0,…,n−1}→{0,…,n−1}2t:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}^2t:{0,…,n−1}→{0,…,n−1}2 such that every prefix {t(i):i<m}\{t(i):i<m\}{t(i):i<m}, for every natural number m≤nm\le nm≤n, is downward closed in the coordinatewise order, and the complete image {t(i):i<n}\{t(i):i<n\}{t(i):i<n} equals SSS. This type is empty unless SSS is downward closed and has exactly nnn elements. For n=0n=0n=0, the grid and SSS are necessarily empty, and the type contains the single empty path.

QAlgorithms.Papers.Independent.Intakenext100.P78.boundedBoxContent

For any natural number nnn and box (a,b)∈{0,…,n−1}2(a,b)\in\{0,\ldots,n-1\}^2(a,b)∈{0,…,n−1}2, this defines its content to be the integer b−ab-ab−a, using integer subtraction, so negative values are retained. For n=0n=0n=0, there is no box to which the definition can be applied.

QAlgorithms.Papers.Independent.Intakenext100.P78.centralSignScalar

For every Boolean bbb, this defines a complex scalar equal to −1-1−1 when b=trueb=\mathrm{true}b=true and 111 when b=falseb=\mathrm{false}b=false.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordCoefficient

For every natural number nnn, frequency label yyy, and pair g=(η,u)g=(\eta,u)g=(η,u) consisting of a Boolean η\etaη and a Boolean string uuu of length nnn, this defines a complex coefficient ay(g)a_y(g)ay​(g). Write m=⌊n/2⌋m=\lfloor n/2\rfloorm=⌊n/2⌋ and ϵ(t)=1\epsilon(t)=1ϵ(t)=1 for false and −1-1−1 for true. A frequency label is either a string vvv of length nnn, in which case ay(g)=∏i:ui=trueϵ(vi)a_y(g)=\prod_{i:u_i=\mathrm{true}}\epsilon(v_i)ay​(g)=∏i:ui​=true​ϵ(vi​), or a triple (b,r,s)(b,r,s)(b,r,s), where r,sr,sr,s have length mmm and bbb satisfies n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false, in which case

a(b,r,s)(η,u)=ϵ(η)(Gb,i1Gb,i2⋯Gb,it)r,s,i1>i2>⋯>it,{i1,…,it}={i:ui=true}.a_{(b,r,s)}(\eta,u)= \epsilon(\eta)\bigl(G_{b,i_1}G_{b,i_2}\cdots G_{b,i_t}\bigr)_{r,s}, \qquad i_1>i_2>\cdots>i_t,\quad \{i_1,\ldots,i_t\}=\{i:u_i=\mathrm{true}\}.a(b,r,s)​(η,u)=ϵ(η)(Gb,i1​​Gb,i2​​⋯Gb,it​​)r,s​,i1​>i2​>⋯>it​,{i1​,…,it​}={i:ui​=true}.

Here, with X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), Y=(0−ii0)Y=\begin{pmatrix}0&-\mathrm{i}\\\mathrm{i}&0\end{pmatrix}Y=(0i​−i0​), and Z=(100−1)Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}Z=(10​0−1​) in Boolean order false, true, the generator for i<2mi<2mi<2m is

Gb,i=Y⊗⌊i/2⌋⊗{Z,i even,X,i odd⊗I⊗(m−⌊i/2⌋−1),G_{b,i}=Y^{\otimes\lfloor i/2\rfloor}\otimes \begin{cases}Z,&i\text{ even},\\X,&i\text{ odd}\end{cases} \otimes I^{\otimes(m-\lfloor i/2\rfloor-1)},Gb,i​=Y⊗⌊i/2⌋⊗{Z,X,​i even,i odd​⊗I⊗(m−⌊i/2⌋−1),

and the generator for i≥2mi\ge2mi≥2m is ϵ(b)Y⊗m\epsilon(b)Y^{\otimes m}ϵ(b)Y⊗m. An empty matrix product is the identity and an empty scalar product is 111. Thus when uuu is all false the two cases give 111 and ϵ(η)1r=s\epsilon(\eta)\mathbf 1_{r=s}ϵ(η)1r=s​, respectively; at n=0n=0n=0, these are 111 and ϵ(η)\epsilon(\eta)ϵ(η).

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordCross

For every natural number nnn and every pair of nnn-bit strings u,vu,vu,v, this defines a Boolean that is true exactly when the number of ordered index pairs (i,j)(i,j)(i,j) satisfying 0≤i<j<n0\le i<j<n0≤i<j<n, ui=trueu_i=\mathrm{true}ui​=true, and vj=truev_j=\mathrm{true}vj​=true is odd. Equivalently, it is the parity of ∑i<j1{ui=true, vj=true}\sum_{i<j}\mathbf1_{\{u_i=\mathrm{true},\,v_j=\mathrm{true}\}}∑i<j​1{ui​=true,vj​=true}​. For n=0n=0n=0 or n=1n=1n=1, there are no such pairs, and the result is false.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordDimension

For every natural number nnn, this assigns a natural number to each label in the disjoint union of Boolean strings vvv of length nnn and triples (b,r,s)(b,r,s)(b,r,s), where r,sr,sr,s have length ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ and bbb satisfies n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false. The assigned number is 111 for a string label and 2⌊n/2⌋2^{\lfloor n/2\rfloor}2⌊n/2⌋ for a triple label, independently of the components of the label. At n=0n=0n=0 and n=1n=1n=1, both kinds receive the value 111.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordFourier

For every natural number nnn, every complex-valued function fff on pairs (η,u)(\eta,u)(η,u) of a Boolean η\etaη and a length-nnn Boolean string uuu, and every frequency label yyy, this defines

f^(y)=dy2n+1∑η∈{false,true}∑u∈{false,true}nf(η,u) ay(η,u).\widehat f(y)= \sqrt{\frac{d_y}{2^{n+1}}} \sum_{\eta\in\{\mathrm{false},\mathrm{true}\}} \sum_{u\in\{\mathrm{false},\mathrm{true}\}^{n}} f(\eta,u)\,a_y(\eta,u).f​(y)=2n+1dy​​​η∈{false,true}∑​u∈{false,true}n∑​f(η,u)ay​(η,u).

Here m=⌊n/2⌋m=\lfloor n/2\rfloorm=⌊n/2⌋, and yyy is either a length-nnn string vvv, with dy=1d_y=1dy​=1 and ay(η,u)=∏i:ui=trueϵ(vi)a_y(\eta,u)=\prod_{i:u_i=\mathrm{true}}\epsilon(v_i)ay​(η,u)=∏i:ui​=true​ϵ(vi​), or a triple (b,r,s)(b,r,s)(b,r,s), with dy=2md_y=2^mdy​=2m, length-mmm strings r,sr,sr,s, and bbb satisfying n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false. The sign ϵ(t)\epsilon(t)ϵ(t) is 111 for false and −1-1−1 for true. For a triple label, ay(η,u)=ϵ(η)(∏i:ui=truedecreasing iGb,i)r,sa_y(\eta,u)=\epsilon(\eta)(\prod_{i:u_i=\mathrm{true}}^{\mathrm{decreasing}\ i}G_{b,i})_{r,s}ay​(η,u)=ϵ(η)(∏i:ui​=truedecreasing i​Gb,i​)r,s​, where, in Boolean order false, true,

X=(0110),Y=(0−ii0),Z=(100−1),Gb,i={Y⊗j⊗(Z if i even, else X)⊗I⊗(m−j−1),i<2m, j=⌊i/2⌋,ϵ(b)Y⊗m,i≥2m.X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-\mathrm{i}\\\mathrm{i}&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\qquad G_{b,i}= \begin{cases} Y^{\otimes j}\otimes (Z\text{ if }i\text{ even, else }X)\otimes I^{\otimes(m-j-1)}, &i<2m,\ j=\lfloor i/2\rfloor,\\ \epsilon(b)Y^{\otimes m},&i\ge2m. \end{cases}X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​),Gb,i​={Y⊗j⊗(Z if i even, else X)⊗I⊗(m−j−1),ϵ(b)Y⊗m,​i<2m, j=⌊i/2⌋,i≥2m.​

The decreasing product places the largest selected index on the left; an empty matrix product is the identity and an empty scalar product is 111. No normalization is required of fff. These formulas also apply to n=0n=0n=0, when the string label yields (f(false,∅)+f(true,∅))/2(f(\mathrm{false},\varnothing)+f(\mathrm{true},\varnothing))/\sqrt2(f(false,∅)+f(true,∅))/2​ and the triple label yields (f(false,∅)−f(true,∅))/2(f(\mathrm{false},\varnothing)-f(\mathrm{true},\varnothing))/\sqrt2(f(false,∅)−f(true,∅))/2​.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordGenerator

For every natural number nnn, Boolean sector bbb satisfying n mod 2=1n\bmod 2=1nmod2=1 or b=falseb=\mathrm{false}b=false, and index 0≤i<n0\le i<n0≤i<n, this defines a complex matrix Gb,iG_{b,i}Gb,i​ indexed by Boolean strings of length m=⌊n/2⌋m=\lfloor n/2\rfloorm=⌊n/2⌋. Put X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), Y=(0−ii0)Y=\begin{pmatrix}0&-\mathrm{i}\\\mathrm{i}&0\end{pmatrix}Y=(0i​−i0​), Z=(100−1)Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}Z=(10​0−1​), with Boolean order false,true\mathrm{false},\mathrm{true}false,true, and let ϵ(b)\epsilon(b)ϵ(b) be 111 for false and −1-1−1 for true. For strings r,sr,sr,s, its entries are

(Gb,i)r,s={∏a=0m−1{Yra,sa,a<⌊i/2⌋,Zra,sa,a=⌊i/2⌋ and i is even,Xra,sa,a=⌊i/2⌋ and i is odd,1ra=sa,a>⌊i/2⌋,i<2m,ϵ(b)∏a=0m−1Yra,sa,i≥2m.(G_{b,i})_{r,s}= \begin{cases} \displaystyle\prod_{a=0}^{m-1} \begin{cases} Y_{r_a,s_a},&a<\lfloor i/2\rfloor,\\ Z_{r_a,s_a},&a=\lfloor i/2\rfloor\text{ and }i\text{ is even},\\ X_{r_a,s_a},&a=\lfloor i/2\rfloor\text{ and }i\text{ is odd},\\ \mathbf 1_{r_a=s_a},&a>\lfloor i/2\rfloor, \end{cases} &i<2m,\\[6pt] \displaystyle\epsilon(b)\prod_{a=0}^{m-1}Y_{r_a,s_a},&i\ge2m. \end{cases}(Gb,i​)r,s​=⎩⎨⎧​a=0∏m−1​⎩⎨⎧​Yra​,sa​​,Zra​,sa​​,Xra​,sa​​,1ra​=sa​​,​a<⌊i/2⌋,a=⌊i/2⌋ and i is even,a=⌊i/2⌋ and i is odd,a>⌊i/2⌋,​ϵ(b)a=0∏m−1​Yra​,sa​​,​i<2m,i≥2m.​

The second case can occur only for odd nnn, at i=2mi=2mi=2m. Empty scalar products equal 111; consequently for n=1n=1n=1 the sole generator is the one-by-one matrix with entry ϵ(b)\epsilon(b)ϵ(b), while for n=0n=0n=0 there is no index iii.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordInputCode

For all natural numbers n,qn,qn,q and every pair g=(η,u)g=(\eta,u)g=(η,u) of a Boolean η\etaη and a length-nnn Boolean string uuu, this defines a length-qqq Boolean string encoding

(1η=true 2n+Bn(u)) mod 2q,Bn(u)=∑i=0n−11ui=true 2n−1−i,\bigl(\mathbf 1_{\eta=\mathrm{true}}\,2^n+B_n(u)\bigr)\bmod 2^q, \qquad B_n(u)=\sum_{i=0}^{n-1}\mathbf 1_{u_i=\mathrm{true}}\,2^{n-1-i},(1η=true​2n+Bn​(u))mod2q,Bn​(u)=i=0∑n−1​1ui​=true​2n−1−i,

in binary with the most significant bit first. There is no lower bound on qqq, so this encoding retains only the residue modulo 2q2^q2q and may identify different inputs. For q=0q=0q=0 it always returns the unique empty string; for n=0n=0n=0, the integer before reduction is 000 or 111, according to η\etaη.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordMul

For every natural number nnn and every two pairs g=(b,u)g=(b,u)g=(b,u), h=(c,v)h=(c,v)h=(c,v), where b,cb,cb,c are Booleans and u,vu,vu,v are nnn-bit strings, this defines the pair

(b⊕c⊕parity⁡#{(i,j):0≤i<j<n, ui=true, vj=true},(ui⊕vi)i<n),\left(b\oplus c\oplus \operatorname{parity}\#\{(i,j):0\le i<j<n,\ u_i=\mathrm{true},\ v_j=\mathrm{true}\}, \quad (u_i\oplus v_i)_{i<n}\right),(b⊕c⊕parity#{(i,j):0≤i<j<n, ui​=true, vj​=true},(ui​⊕vi​)i<n​),

where ⊕\oplus⊕ is Boolean exclusive-or and parity is true for an odd count. When n=0n=0n=0, the second component is the empty string and the first component is b⊕cb\oplus cb⊕c.

QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordOutputCode

For all natural numbers n,qn,qn,q, put m=⌊n/2⌋m=\lfloor n/2\rfloorm=⌊n/2⌋ and define Bℓ(z)=∑i=0ℓ−11zi=true2ℓ−1−iB_\ell(z)=\sum_{i=0}^{\ell-1}\mathbf 1_{z_i=\mathrm{true}}2^{\ell-1-i}Bℓ​(z)=∑i=0ℓ−1​1zi​=true​2ℓ−1−i for a length-ℓ\ellℓ Boolean string. A frequency label is either a length-nnn string vvv, or a triple (b,r,s)(b,r,s)(b,r,s) with length-mmm strings r,sr,sr,s and Boolean bbb satisfying n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false. This defines its output code to be the most-significant-bit-first length-qqq binary representation, reduced modulo 2q2^q2q, of

{Bn(v),for a string label,2n+1b=true 22m+Bm(r) 2m+Bm(s),for a triple label.\begin{cases} B_n(v),&\text{for a string label},\\ 2^n+\mathbf 1_{b=\mathrm{true}}\,2^{2m}+B_m(r)\,2^m+B_m(s), &\text{for a triple label}. \end{cases}{Bn​(v),2n+1b=true​22m+Bm​(r)2m+Bm​(s),​for a string label,for a triple label.​

No lower bound on qqq is imposed, so distinct labels may have the same code; for q=0q=0q=0 every code is the empty string. At n=0n=0n=0, the integers before reduction are 000 and 111 for the two respective labels.

QAlgorithms.Papers.Independent.Intakenext100.P78.encodedWave

For any finite type XXX, natural number qqq, encoding map e:X→{0,1}qe:X\to\{0,1\}^qe:X→{0,1}q, and function f:X→Cf:X\to\mathbb Cf:X→C, this defines the vector ∑x∈Xf(x)∣e(x)⟩\sum_{x\in X}f(x)|e(x)\rangle∑x∈X​f(x)∣e(x)⟩ in the complex Euclidean space indexed by qqq-bit strings, where ∣z⟩|z\rangle∣z⟩ has coordinate 111 at zzz and 000 elsewhere. Equivalently, its coordinate at zzz is ∑x:e(x)=zf(x)\sum_{x:e(x)=z}f(x)∑x:e(x)=z​f(x). The encoding need not be injective, so amplitudes with the same encoding are added, possibly cancelling; no normalization is required. If XXX is empty, the vector is zero. The definition also includes q=0q=0q=0, when there is a single bit string.

QAlgorithms.Papers.Independent.Intakenext100.P78.matrixX

This defines a complex matrix XXX whose rows and columns are indexed by Boolean values: for every row rrr and column sss, Xr,s=0X_{r,s}=0Xr,s​=0 if r=sr=sr=s, and Xr,s=1X_{r,s}=1Xr,s​=1 otherwise. With the ordering false,true\mathrm{false},\mathrm{true}false,true, this is X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​).

QAlgorithms.Papers.Independent.Intakenext100.P78.matrixY

This defines a complex matrix YYY whose rows and columns are indexed by Boolean values: for every row rrr and column sss, Yr,s=0Y_{r,s}=0Yr,s​=0 if r=sr=sr=s; otherwise it is i\mathrm{i}i when r=truer=\mathrm{true}r=true, and −i-\mathrm{i}−i when r=falser=\mathrm{false}r=false, where i2=−1\mathrm{i}^{2}=-1i2=−1. With the ordering false,true\mathrm{false},\mathrm{true}false,true, this is Y=(0−ii0)Y=\begin{pmatrix}0&-\mathrm{i}\\\mathrm{i}&0\end{pmatrix}Y=(0i​−i0​).

QAlgorithms.Papers.Independent.Intakenext100.P78.matrixZ

This defines a complex matrix ZZZ whose rows and columns are indexed by Boolean values: for every row rrr and column sss, its entry is zero when r≠sr\ne sr=s, and when r=sr=sr=s its entry is 111 for r=falser=\mathrm{false}r=false and −1-1−1 for r=truer=\mathrm{true}r=true. With the ordering false,true\mathrm{false},\mathrm{true}false,true, this is Z=(100−1)Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}Z=(10​0−1​).

QAlgorithms.Papers.Independent.Intakenext100.P78.nextIndex

For any natural number nnn and index i∈{0,…,n−1}i\in\{0,\ldots,n-1\}i∈{0,…,n−1}, this defines i+1i+1i+1 if i+1<ni+1<ni+1<n, and otherwise defines iii itself. Thus the last index is fixed rather than sent back to zero; when n=1n=1n=1, the sole index is fixed. For n=0n=0n=0, there is no index to which the function can be applied.

QAlgorithms.Papers.Independent.Intakenext100.P78.normalizedAmplitudes

For any finite type XXX and function f:X→Cf:X\to\mathbb Cf:X→C, this defines the proposition ∑x∈X∣f(x)∣2=1\sum_{x\in X}|f(x)|^2=1∑x∈X​∣f(x)∣2=1, where ∣f(x)∣2=(Re⁡f(x))2+(Im⁡f(x))2|f(x)|^2=(\operatorname{Re}f(x))^2+(\operatorname{Im}f(x))^2∣f(x)∣2=(Ref(x))2+(Imf(x))2. If XXX is empty, the sum is 000, so the proposition is false.

QAlgorithms.Papers.Independent.Intakenext100.P78.packDigits

For any natural number www and any finite list of natural numbers [d0,…,dL−1][d_0,\ldots,d_{L-1}][d0​,…,dL−1​], this defines the natural number ∑j=0L−1dj2wj\sum_{j=0}^{L-1}d_j2^{wj}∑j=0L−1​dj​2wj. Thus the first list entry occupies the lowest power of 2w2^w2w. The empty list gives 000; when w=0w=0w=0, the result is the sum of the entries. There is no requirement that an entry be less than 2w2^w2w.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCharacterX

For every natural number nnn and Booleans e,be,be,b, identify false with 000 and true with 111. This defines

(−1)b{i,e=true and n is odd,1,otherwise.(-1)^b \begin{cases} \mathrm{i},&e=\mathrm{true}\text{ and }n\text{ is odd},\\ 1,&\text{otherwise}. \end{cases}(−1)b{i,1,​e=true and n is odd,otherwise.​

Thus the sign is determined by bbb, and the additional factor i\mathrm{i}i occurs precisely when eee is true and nnn is odd. The definition includes n=0n=0n=0, for which that additional factor is 111.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCoefficient

For every natural number nnn, every frequency label yyy in the disjoint union of Boolean pairs and triples (t,r,s)(t,r,s)(t,r,s) with t<n−1t<n-1t<n−1, and every g∈QuaternionGroup⁡(n)g\in\operatorname{QuaternionGroup}(n)g∈QuaternionGroup(n), this defines a complex coefficient as follows. Write aja_jaj​ and xajxa_jxaj​ for the two constructor forms of ggg, and J=val⁡(j)J=\operatorname{val}(j)J=val(j) for the natural-number value of their index; identify Booleans with 0,10,10,1. For a first-summand label y=(e,b)y=(e,b)y=(e,b), put χ=(−1)bi\chi=(-1)^b\mathrm{i}χ=(−1)bi if eee is true and nnn is odd, and put χ=(−1)b\chi=(-1)^bχ=(−1)b otherwise; then

Ky(aj)=(−1)eJ,Ky(xaj)=χ (−1)eJ.K_y(a_j)=(-1)^{eJ},\qquad K_y(xa_j)=\chi\,(-1)^{eJ}.Ky​(aj​)=(−1)eJ,Ky​(xaj​)=χ(−1)eJ.

For a second-summand label y=(t,r,s)y=(t,r,s)y=(t,r,s), put k=t+1k=t+1k=t+1, zJ=exp⁡(2πkJ i/(2n))z_J=\exp(2\pi kJ\,\mathrm{i}/(2n))zJ​=exp(2πkJi/(2n)), and τk=1\tau_k=1τk​=1 for even kkk, τk=i\tau_k=\mathrm{i}τk​=i for odd kkk; then

Ky(aj)={zJ,r=s=false,zJ‾,r=s=true,0,r≠s,Ky(xaj)={0,r=s,τkzJ‾,r=false, s=true,τkzJ,r=true, s=false.K_y(a_j)= \begin{cases} z_J,&r=s=\mathrm{false},\\ \overline{z_J},&r=s=\mathrm{true},\\ 0,&r\ne s, \end{cases} \qquad K_y(xa_j)= \begin{cases} 0,&r=s,\\ \tau_k\overline{z_J},&r=\mathrm{false},\ s=\mathrm{true},\\ \tau_k z_J,&r=\mathrm{true},\ s=\mathrm{false}. \end{cases}Ky​(aj​)=⎩⎨⎧​zJ​,zJ​​,0,​r=s=false,r=s=true,r=s,​Ky​(xaj​)=⎩⎨⎧​0,τk​zJ​​,τk​zJ​,​r=s,r=false, s=true,r=true, s=false.​

There is no assumption that nnn is positive; for n=0n=0n=0 or n=1n=1n=1, only the first-summand labels exist.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCyclicPhase

For all natural numbers N,k,jN,k,jN,k,j, this defines the complex number

exp⁡ ⁣(2πkjN i).\exp\!\left(\frac{2\pi kj}{N}\,\mathrm{i}\right).exp(N2πkj​i).

The quotient is computed in the real numbers before multiplication by i\mathrm{i}i. There is no positivity assumption on NNN: when N=0N=0N=0, division by zero has value zero, so the result is 111.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionDimension

For every natural number nnn, this assigns the natural number 111 to each Boolean-pair frequency label and the natural number 222 to each triple label (t,r,s)(t,r,s)(t,r,s) with t<n−1t<n-1t<n−1. For n=0n=0n=0 or n=1n=1n=1, the triple-label summand is empty, so every existing label receives 111.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionFourier

For every natural number nnn assumed nonzero, every complex-valued function fff on QuaternionGroup⁡(n)\operatorname{QuaternionGroup}(n)QuaternionGroup(n), and every frequency label yyy, this defines

f^(y)=dy4n∑g∈QuaternionGroup⁡(n)f(g)Ky(g),\widehat f(y)=\sqrt{\frac{d_y}{4n}}\sum_{g\in\operatorname{QuaternionGroup}(n)}f(g)K_y(g),f​(y)=4ndy​​​g∈QuaternionGroup(n)∑​f(g)Ky​(g),

where dy=1d_y=1dy​=1 for a Boolean-pair label and dy=2d_y=2dy​=2 for a triple label. The coefficients are defined explicitly as follows: identify Booleans with 0,10,10,1, and for g=ajg=a_jg=aj​ or xajxa_jxaj​ write J=val⁡(j)J=\operatorname{val}(j)J=val(j). For y=(e,b)y=(e,b)y=(e,b) in the first summand,

Ky(aj)=(−1)eJ,Ky(xaj)=(−1)b+eJ{i,e=true and n is odd,1,otherwise.K_y(a_j)=(-1)^{eJ},\qquad K_y(xa_j)=(-1)^{b+eJ} \begin{cases}\mathrm{i},&e=\mathrm{true}\text{ and }n\text{ is odd},\\1,&\text{otherwise}.\end{cases}Ky​(aj​)=(−1)eJ,Ky​(xaj​)=(−1)b+eJ{i,1,​e=true and n is odd,otherwise.​

For y=(t,r,s)y=(t,r,s)y=(t,r,s) in the second summand, where t<n−1t<n-1t<n−1, put k=t+1k=t+1k=t+1, zJ=exp⁡(2πkJ i/(2n))z_J=\exp(2\pi kJ\,\mathrm{i}/(2n))zJ​=exp(2πkJi/(2n)), and τk=1\tau_k=1τk​=1 for even kkk, τk=i\tau_k=\mathrm{i}τk​=i otherwise; then

Ky(aj)={zJ,r=s=false,zJ‾,r=s=true,0,r≠s,Ky(xaj)={0,r=s,τkzJ‾,r=false, s=true,τkzJ,r=true, s=false.K_y(a_j)= \begin{cases}z_J,&r=s=\mathrm{false},\\\overline{z_J},&r=s=\mathrm{true},\\0,&r\ne s,\end{cases} \quad K_y(xa_j)= \begin{cases}0,&r=s,\\\tau_k\overline{z_J},&r=\mathrm{false},\ s=\mathrm{true},\\\tau_k z_J,&r=\mathrm{true},\ s=\mathrm{false}.\end{cases}Ky​(aj​)=⎩⎨⎧​zJ​,zJ​​,0,​r=s=false,r=s=true,r=s,​Ky​(xaj​)=⎩⎨⎧​0,τk​zJ​​,τk​zJ​,​r=s,r=false, s=true,r=true, s=false.​

No normalization condition is imposed on fff, and the nonzero assumption permits n=1n=1n=1, when there are only the four first-summand labels.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionInputCode

For all natural numbers n,qn,qn,q, this assigns a qqq-bit string to each element of QuaternionGroup⁡(n)\operatorname{QuaternionGroup}(n)QuaternionGroup(n): an element aja_jaj​ is assigned the binary encoding of val⁡(j)\operatorname{val}(j)val(j) modulo 2q2^q2q, and an element xajxa_jxaj​ is assigned the binary encoding of 2n+val⁡(j)2n+\operatorname{val}(j)2n+val(j) modulo 2q2^q2q. Bits are ordered from most significant to least significant, so a string zzz represents ∑i=0q−1[zi] 2q−1−i\sum_{i=0}^{q-1}[z_i]\,2^{q-1-i}∑i=0q−1​[zi​]2q−1−i, where [zi][z_i][zi​] is 111 for true and 000 for false. No lower bound on qqq or positivity assumption on nnn is imposed; reduction modulo 2q2^q2q can identify different input integers, and q=0q=0q=0 gives the unique empty bit string.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionOutputCode

For all natural numbers n,qn,qn,q, this assigns a qqq-bit string to each frequency label by encoding the following integer modulo 2q2^q2q, with the most significant bit first:

{2[e]+[b],y=(e,b) in the first summand,4+4t+2[r]+[s],y=(t,r,s) in the second summand,t<n−1,\begin{cases} 2[e]+[b],&y=(e,b)\text{ in the first summand},\\ 4+4t+2[r]+[s],&y=(t,r,s)\text{ in the second summand},\quad t<n-1, \end{cases}{2[e]+[b],4+4t+2[r]+[s],​y=(e,b) in the first summand,y=(t,r,s) in the second summand,t<n−1,​

where brackets give the numerical value 000 or 111 of a Boolean. The second summand is empty for n=0n=0n=0 or n=1n=1n=1. There is no lower bound on qqq, so reduction modulo 2q2^q2q can cause collisions; when q=0q=0q=0, every label receives the empty string.

QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionTwiddle

For every natural number kkk, this defines the complex number 111 when kkk is even and i\mathrm{i}i otherwise. In particular, its value at k=0k=0k=0 is 111.

QAlgorithms.Papers.Independent.Intakenext100.P78.realizesEncodedTransform

For any finite types X,YX,YX,Y, natural number qqq, circuit ccc on qqq bits, maps ein:X→{0,1}qe_{\mathrm{in}}:X\to\{0,1\}^qein​:X→{0,1}q and eout:Y→{0,1}qe_{\mathrm{out}}:Y\to\{0,1\}^qeout​:Y→{0,1}q, and arbitrary function F:(X→C)→(Y→C)F:(X\to\mathbb C)\to(Y\to\mathbb C)F:(X→C)→(Y→C), this defines the proposition that, for every f:X→Cf:X\to\mathbb Cf:X→C satisfying ∑x∣f(x)∣2=1\sum_x|f(x)|^2=1∑x​∣f(x)∣2=1, one has Uc(∑xf(x)∣ein(x)⟩)=∑y(F(f))(y)∣eout(y)⟩U_c\bigl(\sum_x f(x)|e_{\mathrm{in}}(x)\rangle\bigr)=\sum_y(F(f))(y)|e_{\mathrm{out}}(y)\rangleUc​(∑x​f(x)∣ein​(x)⟩)=∑y​(F(f))(y)∣eout​(y)⟩. Here ∣z⟩|z\rangle∣z⟩ is the coordinate basis vector at zzz; ccc is a finite list of applications of unitary gates of arity either one or two, each with an injective choice of wires. A gate matrix MMM on wires www is extended to all qqq bits by assigning its (z,z′)(z,z')(z,z′) entry the value M(z∘w,z′∘w)M(z\circ w,z'\circ w)M(z∘w,z′∘w) when z,z′z,z'z,z′ agree outside the selected wires, and 000 otherwise; UcU_cUc​ is the product of these extended matrices in reverse list order, so the first listed gate acts first, and an empty circuit gives the identity. Neither encoding is required to be injective, FFF is not required to be linear, and there is no circuit-size bound or approximation tolerance. If XXX is empty, the proposition is vacuous; if YYY is empty, the right-hand vector is zero. The definition includes q=0q=0q=0.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricElement

For every natural number nnn and every tuple x=(xℓ)ℓ<nx=(x_\ell)_{\ell<n}x=(xℓ​)ℓ<n​ with 0≤xℓ≤ℓ0\le x_\ell\le\ell0≤xℓ​≤ℓ, form a list i1,…,iLi_1,\ldots,i_Li1​,…,iL​ by visiting levels ℓ\ellℓ in decreasing order and appending the indices xℓ,xℓ+1,…,ℓ−1x_\ell,x_\ell+1,\ldots,\ell-1xℓ​,xℓ​+1,…,ℓ−1 in increasing order. This defines the permutation τi1∘⋯∘τiL\tau_{i_1}\circ\cdots\circ\tau_{i_L}τi1​​∘⋯∘τiL​​ of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}, where τi\tau_iτi​ exchanges iii with i+1i+1i+1 if i+1<ni+1<ni+1<n, and is the identity otherwise; thus the rightmost permutation acts first. An empty list gives the identity permutation, including when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricFourier

For every natural number nnn, every complex function fff on the tuples x=(xℓ)ℓ<nx=(x_\ell)_{\ell<n}x=(xℓ​)ℓ<n​ satisfying 0≤xℓ≤ℓ0\le x_\ell\le\ell0≤xℓ​≤ℓ, and every frequency y=(λ,(U,T))y=(\lambda,(U,T))y=(λ,(U,T)), this defines

dλn! ∑xf(x) Mxλ(U,T).\sqrt{\frac{d_\lambda}{n!}}\, \sum_x f(x)\,M_x^\lambda(U,T).n!dλ​​​x∑​f(x)Mxλ​(U,T).

Here λ\lambdaλ is a finite subset of {0,…,n−1}2\{0,\ldots,n-1\}^2{0,…,n−1}2; U,TU,TU,T are injective sequences of nnn boxes whose prefixes are downward closed in the coordinatewise order and whose sets of boxes equal λ\lambdaλ; and dλd_\lambdadλ​ is the number of all such paths with endpoint λ\lambdaλ. To define MxλM_x^\lambdaMxλ​, visit levels ℓ=n−1,…,0\ell=n-1,\ldots,0ℓ=n−1,…,0, append xℓ,…,ℓ−1x_\ell,\ldots,\ell-1xℓ​,…,ℓ−1 in increasing order, obtaining i1,…,iLi_1,\ldots,i_Li1​,…,iL​, and take the matrix product Ai1λ⋯AiLλA_{i_1}^\lambda\cdots A_{i_L}^\lambdaAi1​λ​⋯AiL​λ​, with empty product the identity. For paths V,SV,SV,S, set i+=i+1i^+=i+1i+=i+1 if i+1<ni+1<ni+1<n and i+=ii^+=ii+=i otherwise, a=Sia=S_ia=Si​, b=Si+b=S_{i^+}b=Si+​, and r=(b2−b1)−(a2−a1)∈Rr=(b_2-b_1)-(a_2-a_1)\in\mathbb Rr=(b2​−b1​)−(a2​−a1​)∈R. The entry Aiλ(V,S)A_i^\lambda(V,S)Aiλ​(V,S) is 111 when V=SV=SV=S and a,ba,ba,b have the same first coordinate, and 000 for other VVV in that case; otherwise it is −1-1−1 when V=SV=SV=S and a,ba,ba,b have the same second coordinate, and 000 for other VVV in that case; if neither coordinate agrees, it is r−1r^{-1}r−1 for V=SV=SV=S, 1−(r−1)2\sqrt{1-(r^{-1})^2}1−(r−1)2​ for V≠SV\ne SV=S with V=S∘(i i+)V=S\circ(i\ i^+)V=S∘(i i+), and 000 otherwise. These real entries are viewed in C\mathbb CC, with 0−1=00^{-1}=00−1=0 and square root 000 on negative arguments. There is no normalization assumption on fff. When n=0n=0n=0, the unique frequency consists of the empty endpoint and two empty paths, and the value is fff evaluated at the empty tuple.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricInputCode

For every pair of natural numbers n,qn,qn,q and every tuple x=(xi)i<nx=(x_i)_{i<n}x=(xi​)i<n​ with 0≤xi≤i0\le x_i\le i0≤xi​≤i, let www be the least nonnegative integer satisfying n+1≤2wn+1\le2^wn+1≤2w. This defines the qqq-bit string representing

(∑i=0n−1xi 2wi) mod 2q,\left(\sum_{i=0}^{n-1}x_i\,2^{wi}\right)\bmod 2^q,(i=0∑n−1​xi​2wi)mod2q,

with the most significant bit first. Thus the digit x0x_0x0​ occupies the least significant block of width www; no lower bound on qqq is imposed, so higher bits may be discarded. When n=0n=0n=0, the encoded integer is 000; when q=0q=0q=0, the output is the unique empty bit string.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricMatrix

For every natural number nnn, every tuple x=(xℓ)ℓ<nx=(x_\ell)_{\ell<n}x=(xℓ​)ℓ<n​ with 0≤xℓ≤ℓ0\le x_\ell\le\ell0≤xℓ​≤ℓ, and every finite set λ⊆{0,…,n−1}2\lambda\subseteq\{0,\ldots,n-1\}^2λ⊆{0,…,n−1}2, this defines a complex matrix indexed by pairs of paths with endpoint λ\lambdaλ. Here a path is an injective sequence T=(T0,…,Tn−1)T=(T_0,\ldots,T_{n-1})T=(T0​,…,Tn−1​) of boxes in that square such that every prefix {Ti:i<m}\{T_i:i<m\}{Ti​:i<m}, for 0≤m≤n0\le m\le n0≤m≤n, is downward closed in the coordinatewise order, and its endpoint is {Ti:i<n}\{T_i:i<n\}{Ti​:i<n}. Form i1,…,iLi_1,\ldots,i_Li1​,…,iL​ by visiting levels ℓ\ellℓ in decreasing order and appending the indices xℓ,…,ℓ−1x_\ell,\ldots,\ell-1xℓ​,…,ℓ−1 in increasing order. The matrix is Ai1⋯AiLA_{i_1}\cdots A_{i_L}Ai1​​⋯AiL​​, in that order. To define Ai(U,T)A_i(U,T)Ai​(U,T), put i+=i+1i^+=i+1i+=i+1 when i+1<ni+1<ni+1<n, and i+=ii^+=ii+=i otherwise; write a=Tia=T_ia=Ti​, b=Ti+b=T_{i^+}b=Ti+​, and r=(b2−b1)−(a2−a1)r=(b_2-b_1)-(a_2-a_1)r=(b2​−b1​)−(a2​−a1​), interpreted as a real number. Then

Ai(U,T)={1{U=T},a1=b1,−1{U=T},a1≠b1 and a2=b2,r−1,a1≠b1, a2≠b2, U=T,1−(r−1)2,a1≠b1, a2≠b2, U≠T, U=T∘(i i+),0,otherwise,A_i(U,T)= \begin{cases} \mathbf 1_{\{U=T\}},&a_1=b_1,\\ -\mathbf 1_{\{U=T\}},&a_1\ne b_1\ \text{and }a_2=b_2,\\ r^{-1},&a_1\ne b_1,\ a_2\ne b_2,\ U=T,\\ \sqrt{1-(r^{-1})^2},& a_1\ne b_1,\ a_2\ne b_2,\ U\ne T,\ U=T\circ(i\ i^+),\\ 0,&\text{otherwise}, \end{cases}Ai​(U,T)=⎩⎨⎧​1{U=T}​,−1{U=T}​,r−1,1−(r−1)2​,0,​a1​=b1​,a1​=b1​ and a2​=b2​,a1​=b1​, a2​=b2​, U=T,a1​=b1​, a2​=b2​, U=T, U=T∘(i i+),otherwise,​

with real entries embedded in C\mathbb CC, real inverse 0−1=00^{-1}=00−1=0, and the real square root equal to 000 on negative arguments. An empty product is the identity matrix. No condition on λ\lambdaλ is assumed; if there are no paths with that endpoint, the matrix has an empty index set. For n=0n=0n=0, the only endpoint is empty, there is one empty path, and the matrix is the 1×11\times11×1 identity.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricOutputCode

For every pair of natural numbers n,qn,qn,q and every frequency y=(λ,(U,T))y=(\lambda,(U,T))y=(λ,(U,T)), where U,TU,TU,T are injective sequences of nnn boxes in {0,…,n−1}2\{0,\ldots,n-1\}^2{0,…,n−1}2, every prefix of either sequence is downward closed in the coordinatewise order, and both endpoint sets equal the finite set λ\lambdaλ, write Ui=(ri,ci)U_i=(r_i,c_i)Ui​=(ri​,ci​), Ti=(ri′,ci′)T_i=(r'_i,c'_i)Ti​=(ri′​,ci′​), and let www be the least nonnegative integer with n+1≤2wn+1\le2^wn+1≤2w. This defines the most-significant-bit-first qqq-bit representation, reduced modulo 2q2^q2q, of

∑i=0n−1(ri22wi+ci2w(2i+1))+∑i=0n−1(ri′2w(2n+2i)+ci′2w(2n+2i+1)).\sum_{i=0}^{n-1}\left(r_i2^{2wi}+c_i2^{w(2i+1)}\right) +\sum_{i=0}^{n-1}\left(r'_i2^{w(2n+2i)}+c'_i2^{w(2n+2i+1)}\right).i=0∑n−1​(ri​22wi+ci​2w(2i+1))+i=0∑n−1​(ri′​2w(2n+2i)+ci′​2w(2n+2i+1)).

Thus it packs the alternating coordinates of UUU, followed by those of TTT, with the first coordinate in the least significant block; the shape is not separately included in the packed list. No lower bound on qqq is required. For n=0n=0n=0, the integer is 000; for q=0q=0q=0, the output is the empty bit string.

QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricWord

For every natural number nnn, including 000, and every tuple x=(x0,…,xn−1)x=(x_0,\ldots,x_{n-1})x=(x0​,…,xn−1​) of integers satisfying 0≤xℓ≤ℓ0\le x_\ell\le\ell0≤xℓ​≤ℓ, this defines a list of indices in {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}. Visit the levels ℓ=n−1,n−2,…,0\ell=n-1,n-2,\ldots,0ℓ=n−1,n−2,…,0, and at each level append, in increasing order, all indices jjj satisfying xℓ≤j<ℓx_\ell\le j<\ellxℓ​≤j<ℓ. A level with xℓ=ℓx_\ell=\ellxℓ​=ℓ contributes nothing; when n=0n=0n=0, the entire list is empty.

QAlgorithms.Papers.Independent.Intakenext100.P78.tableauDigits

For every natural number nnn and every injective sequence T=(T0,…,Tn−1)T=(T_0,\ldots,T_{n-1})T=(T0​,…,Tn−1​) in {0,…,n−1}2\{0,\ldots,n-1\}^2{0,…,n−1}2 whose prefix sets {Ti:i<m}\{T_i:i<m\}{Ti​:i<m} are downward closed in the coordinatewise order for every 0≤m≤n0\le m\le n0≤m≤n, write Ti=(ri,ci)T_i=(r_i,c_i)Ti​=(ri​,ci​). This defines the list of natural numbers [r0,c0,r1,c1,…,rn−1,cn−1][r_0,c_0,r_1,c_1,\ldots,r_{n-1},c_{n-1}][r0​,c0​,r1​,c1​,…,rn−1​,cn−1​], of length 2n2n2n. For n=0n=0n=0, it is the empty list.

QAlgorithms.Papers.Independent.Intakenext100.P78.youngAdjacent

For any natural number nnn, finite grid subset S⊆{0,…,n−1}2S\subseteq\{0,\ldots,n-1\}^2S⊆{0,…,n−1}2, and index i<ni<ni<n, this defines a complex matrix whose rows UUU and columns TTT are injective paths into the grid with complete image SSS and with every prefix downward closed in the coordinatewise order. Write u,tu,tu,t for their underlying maps, put j=i+1j=i+1j=i+1 when i+1<ni+1<ni+1<n and j=ij=ij=i otherwise, let a=t(i)a=t(i)a=t(i), b=t(j)b=t(j)b=t(j), and let r=(b2−b1)−(a2−a1)r=(b_2-b_1)-(a_2-a_1)r=(b2​−b1​)−(a2​−a1​), regarded as a real number after taking these differences in the integers. The entry at row UUU, column TTT is determined by the following ordered cases: if a1=b1a_1=b_1a1​=b1​, it is 111 when U=TU=TU=T and 000 otherwise; otherwise, if a2=b2a_2=b_2a2​=b2​, it is −1-1−1 when U=TU=TU=T and 000 otherwise; otherwise, if U=TU=TU=T, it is r−1r^{-1}r−1; otherwise, if u=t∘(i j)u=t\circ(i\ j)u=t∘(i j), where (i j)(i\ j)(i j) swaps the two indices, it is 1−(r−1)2\sqrt{1-(r^{-1})^2}1−(r−1)2​; in every other case it is 000. The real values in these formulas are embedded into C\mathbb CC, with the total-function conventions 0−1=00^{-1}=00−1=0 and x=0\sqrt{x}=0x​=0 for x≤0x\le0x≤0. At the last index, j=ij=ij=i, so the first case makes the matrix the identity. If there are no paths with endpoint SSS, the matrix has an empty index set; when n=0n=0n=0, there is no admissible index iii.

QAlgorithms.Papers.Independent.Intakenext100.P78.youngPathEndpoint

For any natural number nnn and injective map t:{0,…,n−1}→{0,…,n−1}2t:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}^2t:{0,…,n−1}→{0,…,n−1}2 whose every prefix {t(i):i<m}\{t(i):i<m\}{t(i):i<m}, for m≤nm\le nm≤n, is downward closed under decreasing either coordinate, this defines the finite set {t(i):0≤i<n}\{t(i):0\le i<n\}{t(i):0≤i<n}. This set contains exactly nnn boxes and is downward closed. For n=0n=0n=0, it is empty.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me