Theory Suzuki_Order

theory Suzuki_Order
  imports Trotter_Product_Formula Matrix_Sums
begin

section ‹Order conditions for product formulas›

text ‹Taylor coefficients of products $e^{tY_1}\cdots e^{tY_m}$ as convolutions of matrix sequences.
A palindromic product has odd error order (‹sym_order›), and Suzuki's five-fold recursion
raises the order by two (‹scaled_copies›), so $S_{2k+2}$ agrees with $e^{itH}$ up to degree
$2k+2$ (‹suzuki_order›).›

text ‹A sequence $f_0,f_1,\dots$ of $n\times n$ matrices stands for the power series $\sum_pf_pt^p$, and the
product of two series has the coefficients of the Cauchy product
\[ (f\ast g)_p=\sum_{q\le p}f_q\,g_{p-q}. \]›

definition cauchy_prod :: "nat ⇒ (nat ⇒ complex Matrix.mat) ⇒ (nat ⇒ complex Matrix.mat) ⇒ nat ⇒ complex Matrix.mat" where
  "cauchy_prod n f g p = matrix_sum n (λq. f q * g (p - q)) (Suc p)"

text ‹All terms of the sequence are $n\times n$.›

definition seq_carrier :: "nat ⇒ (nat ⇒ complex Matrix.mat) ⇒ bool" where
  "seq_carrier n f ⟷ (∀p. f p ∈ carrier_mat n n)"

lemma seq_carrier_in [simp]: "seq_carrier n f ⟹ f q ∈ carrier_mat n n"
  by (simp add: seq_carrier_def)

lemma seq_carrier_row [simp]: "seq_carrier n f ⟹ dim_row (f q) = n"
  by (rule carrier_matD(1)[OF seq_carrier_in])

lemma seq_carrier_col [simp]: "seq_carrier n f ⟹ dim_col (f q) = n"
  by (rule carrier_matD(2)[OF seq_carrier_in])

lemma seq_carrier_mult [simp]: "seq_carrier n f ⟹ seq_carrier n g ⟹ f q * g r ∈ carrier_mat n n"
  by (rule mult_carrier_mat[OF seq_carrier_in seq_carrier_in])

lemma cauchy_prod_carrier: "seq_carrier n f ⟹ seq_carrier n g ⟹ seq_carrier n (cauchy_prod n f g)"
  unfolding seq_carrier_def cauchy_prod_def by (intro allI matrix_sum_dim, rule mult_carrier_mat) auto

lemma cauchy_prod_index:
  assumes "seq_carrier n f" "seq_carrier n g" "i < n" "j < n"
  shows "cauchy_prod n f g p $$ (i, j) = (∑q≤p. ∑c<n. f q $$ (i, c) * g (p - q) $$ (c, j))"
proof -
  have "cauchy_prod n f g p $$ (i, j) = (∑q<Suc p. (f q * g (p - q)) $$ (i, j))"
    unfolding cauchy_prod_def by (rule matrix_sum_index) (use assms in simp_all)
  also have "… = (∑q≤p. ∑c<n. f q $$ (i, c) * g (p - q) $$ (c, j))"
      using assms unfolding lessThan_Suc_atMost
    by (intro sum.cong refl) (auto simp: scalar_prod_def atLeast0LessThan)
  finally show ?thesis .
qed

lemma triple_reindex:
  fixes F :: "nat ⇒ nat ⇒ nat ⇒ 'a::comm_monoid_add"
  shows "(∑q≤p. ∑r≤q. F r (q - r) (p - q)) = (∑r≤p. ∑s≤p - r. F r s (p - r - s))"
proof -
  have "(∑q≤p. ∑r≤q. F r (q - r) (p - q)) = (∑(q, r)∈Sigma {..p} (λq. {..q}). F r (q - r) (p - q))"
    by (rule sum.Sigma) auto
  also have "… = (∑(r, s)∈Sigma {..p} (λr. {..p - r}). F r s (p - r - s))"
    by (rule sum.reindex_bij_witness[where i = "λ(r, s). (r + s, r)" and j = "λ(q, r). (r, q - r)"]) auto
  also have "… = (∑r≤p. ∑s≤p - r. F r s (p - r - s))"
    by (rule sum.Sigma[symmetric]) auto
  finally show ?thesis .
qed

text ‹The Cauchy product is associative:›

lemma cauchy_prod_assoc:
  assumes f: "seq_carrier n f" and g: "seq_carrier n g" and h: "seq_carrier n h"
  shows "cauchy_prod n (cauchy_prod n f g) h p = cauchy_prod n f (cauchy_prod n g h) p"
proof (rule eq_matI)
  fix i j assume i: "i < dim_row (cauchy_prod n f (cauchy_prod n g h) p)" and j: "j < dim_col (cauchy_prod n f (cauchy_prod n g h) p)"
  have ij: "i < n" "j < n" using i j cauchy_prod_carrier[OF f cauchy_prod_carrier[OF g h]] by simp_all
  have fg: "seq_carrier n (cauchy_prod n f g)" and gh: "seq_carrier n (cauchy_prod n g h)" using cauchy_prod_carrier f g h by auto
  have sw1: "(∑c<n. ∑r≤q. ∑e<n. T c r e) = (∑r≤q. ∑e<n. ∑c<n. T c r e)" for T :: "nat ⇒ nat ⇒ nat ⇒ complex" and q
    by (subst sum.swap) (rule sum.cong[OF refl], rule sum.swap)
  have sw2: "(∑e<n. ∑s≤m. ∑c<n. T e s c) = (∑s≤m. ∑e<n. ∑c<n. T e s c)" for T :: "nat ⇒ nat ⇒ nat ⇒ complex" and m
    by (rule sum.swap)
  have "cauchy_prod n (cauchy_prod n f g) h p $$ (i, j)
      = (∑q≤p. ∑c<n. (∑r≤q. ∑e<n. f r $$ (i, e) * g (q - r) $$ (e, c)) * h (p - q) $$ (c, j))"
    unfolding cauchy_prod_index[OF fg h ij] using cauchy_prod_index[OF f g ij(1)] by (intro sum.cong refl) simp
  also have "… = (∑q≤p. ∑r≤q. ∑e<n. ∑c<n. f r $$ (i, e) * g (q - r) $$ (e, c) * h (p - q) $$ (c, j))"
    by (simp only: sum_distrib_right sw1)
  also have "… = (∑r≤p. ∑s≤p - r. ∑e<n. ∑c<n. f r $$ (i, e) * g s $$ (e, c) * h (p - r - s) $$ (c, j))"
    by (rule triple_reindex)
  also have "… = (∑r≤p. ∑e<n. f r $$ (i, e) * (∑s≤p - r. ∑c<n. g s $$ (e, c) * h (p - r - s) $$ (c, j)))"
    unfolding sum_distrib_left sw2 by (simp add: mult_ac)
  also have "… = cauchy_prod n f (cauchy_prod n g h) p $$ (i, j)"
    unfolding cauchy_prod_index[OF f gh ij] using cauchy_prod_index[OF g h _ ij(2)] by (intro sum.cong refl) simp
  finally show "cauchy_prod n (cauchy_prod n f g) h p $$ (i, j) = cauchy_prod n f (cauchy_prod n g h) p $$ (i, j)" .
qed (use cauchy_prod_carrier[OF cauchy_prod_carrier[OF f g] h] cauchy_prod_carrier[OF f cauchy_prod_carrier[OF g h]] in ‹simp_all add: seq_carrier_def›)


text ‹The unit series $1,0,0,\dots$; scaling $f_p\mapsto u^pf_p$, which substitutes $ut$ for $t$; and the
coefficients $X^p/p!$ of $e^{tX}$.›

definition seq_one :: "nat ⇒ nat ⇒ complex Matrix.mat" where
  "seq_one n p = (if p = 0 then 1m n else 0m n n)"

definition seq_scale :: "complex ⇒ (nat ⇒ complex Matrix.mat) ⇒ nat ⇒ complex Matrix.mat" where
  "seq_scale u f p = (u ^ p) ⋅m f p"

definition exp_coeff :: "complex Matrix.mat ⇒ nat ⇒ complex Matrix.mat" where
  "exp_coeff X p = complex_of_real (1 / fact p) ⋅m X ^m p"

lemma seq_one_carrier [simp]: "seq_carrier n (seq_one n)"
  by (simp add: seq_carrier_def seq_one_def)

lemma seq_scale_carrier [simp]: "seq_carrier n f ⟹ seq_carrier n (seq_scale u f)"
  by (simp add: seq_carrier_def seq_scale_def)

lemma exp_coeff_carrier [simp]: "X ∈ carrier_mat n n ⟹ seq_carrier n (exp_coeff X)"
  by (simp add: seq_carrier_def exp_coeff_def)

text ‹The unit is neutral and scaling commutes with products:›

lemma cauchy_prod_unit_left: "seq_carrier n f ⟹ cauchy_prod n (seq_one n) f p = f p"
proof (induction p)
  case 0
  thus ?case by (simp add: cauchy_prod_def seq_one_def)
next
  case (Suc p)
  have "matrix_sum n (λq. seq_one n q * f (Suc p - q)) (Suc p) = matrix_sum n (λq. if q = 0 then f (Suc p) else 0m n n) (Suc p)"
    by (rule matrix_sum_cong) (use Suc.prems in ‹auto simp: seq_one_def›)
  also have "… = f (Suc p)"
  proof -
    have z: "matrix_sum n (λq. if q = 0 then f (Suc p) else 0m n n) m = f (Suc p)" if "0 < m" for m
      using that by (induction m) (use Suc.prems in ‹auto simp: gr0_conv_Suc›)
    show ?thesis by (rule z) simp
  qed
  finally show ?case using Suc.prems by (simp add: cauchy_prod_def seq_one_def)
qed

lemma cauchy_prod_unit_right: "seq_carrier n f ⟹ cauchy_prod n f (seq_one n) p = f p"
proof (rule eq_matI)
  fix i j assume f: "seq_carrier n f" and i: "i < dim_row (f p)" and j: "j < dim_col (f p)"
  have ij: "i < n" "j < n" using i j f by simp_all
  have "cauchy_prod n f (seq_one n) p $$ (i, j) = (∑q≤p. ∑c<n. f q $$ (i, c) * seq_one n (p - q) $$ (c, j))"
    by (rule cauchy_prod_index[OF f seq_one_carrier ij])
  also have "… = (∑q≤p. if q = p then f p $$ (i, j) else 0)"
  proof (rule sum.cong[OF refl])
    fix q assume q: "q ∈ {..p}"
    show "(∑c<n. f q $$ (i, c) * seq_one n (p - q) $$ (c, j)) = (if q = p then f p $$ (i, j) else 0)"
    proof (cases "q = p")
      case True
      have "(∑c<n. f p $$ (i, c) * (if c = j then 1 else 0)) = (∑c<n. if c = j then f p $$ (i, c) else 0)"
        by (intro sum.cong) auto
      also have "… = f p $$ (i, j)" using ij by simp
      finally have "(∑c<n. f p $$ (i, c) * (if c = j then 1 else 0)) = f p $$ (i, j)" .
      thus ?thesis using True ij by (simp add: seq_one_def one_mat_def)
    qed (use q ij in ‹auto simp: seq_one_def›)
  qed
  also have "… = f p $$ (i, j)" by simp
  finally show "cauchy_prod n f (seq_one n) p $$ (i, j) = f p $$ (i, j)" .
qed (simp_all add: cauchy_prod_carrier[THEN seq_carrier_row] cauchy_prod_carrier[THEN seq_carrier_col])

lemma seq_scale_cauchy_prod: "seq_carrier n f ⟹ seq_carrier n g ⟹ cauchy_prod n (seq_scale u f) (seq_scale u g) p = seq_scale u (cauchy_prod n f g) p"
proof (rule eq_matI)
  fix i j assume f: "seq_carrier n f" and g: "seq_carrier n g" and i: "i < dim_row (seq_scale u (cauchy_prod n f g) p)"
    and j: "j < dim_col (seq_scale u (cauchy_prod n f g) p)"
  have ij: "i < n" "j < n" using i j cauchy_prod_carrier[OF f g] by (simp_all add: seq_scale_def)
  have "cauchy_prod n (seq_scale u f) (seq_scale u g) p $$ (i, j) = (∑q≤p. ∑c<n. (u ^ q * f q $$ (i, c)) * (u ^ (p - q) * g (p - q) $$ (c, j)))"
    unfolding cauchy_prod_index[OF seq_scale_carrier[OF f] seq_scale_carrier[OF g] ij] using ij f g by (intro sum.cong refl) (simp add: seq_scale_def)
  also have "… = (∑q≤p. ∑c<n. u ^ p * (f q $$ (i, c) * g (p - q) $$ (c, j)))"
    by (intro sum.cong refl) (simp add: mult_ac power_add[symmetric])
  also have "… = seq_scale u (cauchy_prod n f g) p $$ (i, j)"
    unfolding seq_scale_def using ij cauchy_prod_index[OF f g ij] cauchy_prod_carrier[OF f g] by (simp add: sum_distrib_left)
  finally show "cauchy_prod n (seq_scale u f) (seq_scale u g) p $$ (i, j) = seq_scale u (cauchy_prod n f g) p $$ (i, j)" .
qed (simp_all add: seq_scale_def cauchy_prod_carrier[THEN seq_carrier_row] cauchy_prod_carrier[THEN seq_carrier_col])

lemma smult_pow_mat: "X ∈ carrier_mat n n ⟹ (u ⋅m X) ^m p = (u ^ p) ⋅m (X ^m p)"
  for X :: "complex Matrix.mat"
proof (induction p)
  case 0
  thus ?case by simp (intro eq_matI, auto)
next
  case (Suc p)
  have Xp: "X ^m p ∈ carrier_mat n n" using Suc.prems by simp
  have "(u ⋅m X) ^m Suc p = (u ^ p ⋅m X ^m p) * (u ⋅m X)" using Suc by simp
  also have "… = u ^ p ⋅m (X ^m p * (u ⋅m X))"
    by (rule mult_smult_assoc_mat[where nr = n and n = n and nc = n]) (use Xp Suc.prems in simp_all)
  also have "X ^m p * (u ⋅m X) = u ⋅m (X ^m p * X)"
    by (rule mult_smult_distrib[where nr = n and n = n and nc = n]) (use Xp Suc.prems in simp_all)
  also have "u ^ p ⋅m (u ⋅m (X ^m p * X)) = (u ^ Suc p) ⋅m (X ^m p * X)"
    by (rule eq_matI) (auto simp: mult_ac)
  finally show ?case by simp
qed

lemma smult_mult_smult:
  fixes A B :: "complex Matrix.mat"
  assumes "A ∈ carrier_mat n n" "B ∈ carrier_mat n n"
  shows "(c ⋅m A) * (d ⋅m B) = (c * d) ⋅m (A * B)"
proof -
  have "(c ⋅m A) * (d ⋅m B) = c ⋅m (A * (d ⋅m B))"
    by (rule mult_smult_assoc_mat[where nr = n and n = n and nc = n]) (use assms in simp_all)
  also have "A * (d ⋅m B) = d ⋅m (A * B)"
    by (rule mult_smult_distrib[where nr = n and n = n and nc = n]) (use assms in simp_all)
  also have "c ⋅m (d ⋅m (A * B)) = (c * d) ⋅m (A * B)" by (rule eq_matI) auto
  finally show ?thesis .
qed

lemma exp_coeff_smult: "X ∈ carrier_mat n n ⟹ exp_coeff (u ⋅m X) p = seq_scale u (exp_coeff X) p"
  by (simp add: exp_coeff_def seq_scale_def smult_pow_mat) (rule eq_matI, auto simp: mult_ac)

lemma exp_coeff_zero: "exp_coeff (0m n n) p = seq_one n p"
  by (cases p) (simp_all add: exp_coeff_def seq_one_def one_smult_mat)

text ‹$e^{taX}e^{tbX}=e^{t(a+b)X}$, coefficient by coefficient:
\[ \sum_{q\le p}\frac{(aX)^q}{q!}\,\frac{(bX)^{p-q}}{(p-q)!}=\frac{((a+b)X)^p}{p!}. \]›

lemma exp_coeff_add:
  assumes X: "X ∈ carrier_mat n n"
  shows "cauchy_prod n (exp_coeff (a ⋅m X)) (exp_coeff (b ⋅m X)) p = exp_coeff ((a + b) ⋅m X) p"
proof -
  have Xq: "⋀q. X ^m q ∈ carrier_mat n n" using X by simp
  have tm: "exp_coeff (a ⋅m X) q * exp_coeff (b ⋅m X) (p - q)
      = (a ^ q * b ^ (p - q) / (fact q * fact (p - q))) ⋅m X ^m p" if "q ≤ p" for q
  proof -
    have "X ^m q * X ^m (p - q) = X ^m p" using that X by (simp add: pow_mat_add[OF X, symmetric])
    hence "(1 / fact q * a ^ q) ⋅m X ^m q * ((1 / fact (p - q) * b ^ (p - q)) ⋅m X ^m (p - q))
        = (a ^ q * b ^ (p - q) / (fact q * fact (p - q))) ⋅m X ^m p"
      by (simp add: smult_mult_smult[OF Xq Xq] field_simps)
    moreover have "exp_coeff (a ⋅m X) q = (1 / fact q * a ^ q) ⋅m X ^m q"
      "exp_coeff (b ⋅m X) (p - q) = (1 / fact (p - q) * b ^ (p - q)) ⋅m X ^m (p - q)"
      by (simp_all add: exp_coeff_def smult_pow_mat[OF X]) (rule eq_matI, auto)+
    ultimately show ?thesis by simp
  qed
  have "cauchy_prod n (exp_coeff (a ⋅m X)) (exp_coeff (b ⋅m X)) p
      = matrix_sum n (λq. (a ^ q * b ^ (p - q) / (fact q * fact (p - q))) ⋅m X ^m p) (Suc p)"
    unfolding cauchy_prod_def by (rule matrix_sum_cong) (simp add: tm)
  also have "… = (∑q<Suc p. a ^ q * b ^ (p - q) / (fact q * fact (p - q))) ⋅m X ^m p"
    by (rule matrix_sum_scalar[OF Xq])
  also have "(∑q<Suc p. a ^ q * b ^ (p - q) / (fact q * fact (p - q))) = (a + b) ^ p / fact p"
  proof -
    have "(a + b) ^ p = (∑q≤p. of_nat (p choose q) * a ^ q * b ^ (p - q))" by (rule binomial_ring)
    also have "… = fact p * (∑q≤p. a ^ q * b ^ (p - q) / (fact q * fact (p - q)))"
      unfolding sum_distrib_left by (intro sum.cong refl) (simp add: binomial_fact field_simps)
    finally show ?thesis by (simp add: lessThan_Suc_atMost field_simps)
  qed
  also have "((a + b) ^ p / fact p) ⋅m X ^m p = exp_coeff ((a + b) ⋅m X) p"
    by (simp add: exp_coeff_def smult_pow_mat[OF X]) (rule eq_matI, auto)
  finally show ?thesis .
qed

text ‹The coefficients of $e^{tY_1}\cdots e^{tY_m}$.›

fun prod_coeff :: "nat ⇒ complex Matrix.mat list ⇒ nat ⇒ complex Matrix.mat" where
  "prod_coeff n [] = seq_one n"
| "prod_coeff n (Y # Ys) = cauchy_prod n (exp_coeff Y) (prod_coeff n Ys)"

lemma prod_coeff_carrier: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ seq_carrier n (prod_coeff n Ys)"
  by (induction Ys, auto intro: cauchy_prod_carrier)

text ‹Concatenating factor lists multiplies the series, scaling all factors scales the series, and
$e^{-tY_m}\cdots e^{-tY_1}$ inverts $e^{tY_1}\cdots e^{tY_m}$:›

lemma prod_coeff_append:
  assumes "∀Y ∈ set Ys. Y ∈ carrier_mat n n" "∀Y ∈ set Zs. Y ∈ carrier_mat n n"
  shows "prod_coeff n (Ys @ Zs) = cauchy_prod n (prod_coeff n Ys) (prod_coeff n Zs)"
  using assms(1)
proof (induction Ys)
  case Nil
  show ?case using prod_coeff_carrier[OF assms(2)] by (simp add: fun_eq_iff cauchy_prod_unit_left)
next
  case (Cons Y Ys)
  have c: "seq_carrier n (exp_coeff Y)" "seq_carrier n (prod_coeff n Ys)" "seq_carrier n (prod_coeff n Zs)"
    using Cons.prems prod_coeff_carrier[OF assms(2)] prod_coeff_carrier[of Ys n] by auto
  have ih: "prod_coeff n (Ys @ Zs) = cauchy_prod n (prod_coeff n Ys) (prod_coeff n Zs)" using Cons by simp
  show ?case unfolding append_Cons prod_coeff.simps ih using cauchy_prod_assoc[OF c] by (simp add: fun_eq_iff)
qed

lemma seq_scale_seq_one: "seq_scale u (seq_one n) = seq_one n"
  by (auto simp: fun_eq_iff seq_scale_def seq_one_def one_smult_mat)

lemma prod_coeff_scale: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ prod_coeff n (map ((⋅m) u) Ys) = seq_scale u (prod_coeff n Ys)"
proof (induction Ys)
  case Nil
  thus ?case by (simp add: seq_scale_seq_one)
next
  case (Cons Y Ys)
  have Y: "Y ∈ carrier_mat n n" and F: "seq_carrier n (prod_coeff n Ys)" using Cons.prems prod_coeff_carrier[of Ys n] by auto
  have t: "exp_coeff (u ⋅m Y) = seq_scale u (exp_coeff Y)" by (simp add: fun_eq_iff exp_coeff_smult[OF Y])
  have ih: "prod_coeff n (map ((⋅m) u) Ys) = seq_scale u (prod_coeff n Ys)" using Cons by simp
  show ?case unfolding list.map prod_coeff.simps t ih using seq_scale_cauchy_prod[OF exp_coeff_carrier[OF Y] F] by (simp add: fun_eq_iff)
qed

lemma zero_smult_mat: "A ∈ carrier_mat n n ⟹ (0::complex) ⋅m A = 0m n n"
  by (rule eq_matI) auto

lemma exp_coeff_inverse:
  assumes Y: "Y ∈ carrier_mat n n"
  shows "cauchy_prod n (exp_coeff ((-1) ⋅m Y)) (exp_coeff Y) = seq_one n"
proof -
  have "cauchy_prod n (exp_coeff ((-1) ⋅m Y)) (exp_coeff (1 ⋅m Y)) p = exp_coeff ((-1 + 1) ⋅m Y) p" for p
    by (rule exp_coeff_add[OF Y])
  thus ?thesis using zero_smult_mat[OF Y] by (simp add: fun_eq_iff one_smult_mat exp_coeff_zero)
qed

lemma cauchy_prod_assoc_fun: "seq_carrier n f ⟹ seq_carrier n g ⟹ seq_carrier n h ⟹ cauchy_prod n (cauchy_prod n f g) h = cauchy_prod n f (cauchy_prod n g h)"
  by (simp add: fun_eq_iff cauchy_prod_assoc)

lemma cauchy_prod_unit_right_fun: "seq_carrier n f ⟹ cauchy_prod n f (seq_one n) = f"
  by (simp add: fun_eq_iff cauchy_prod_unit_right)

lemma cauchy_prod_unit_left_fun: "seq_carrier n f ⟹ cauchy_prod n (seq_one n) f = f"
  by (simp add: fun_eq_iff cauchy_prod_unit_left)

lemma prod_coeff_inverse:
  "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ cauchy_prod n (prod_coeff n (rev (map ((⋅m) (-1)) Ys))) (prod_coeff n Ys) = seq_one n"
proof (induction Ys)
  case Nil
  thus ?case by (simp add: fun_eq_iff cauchy_prod_unit_left)
next
  case (Cons Y Ys)
  have Y: "Y ∈ carrier_mat n n" and Ys: "∀Z ∈ set Ys. Z ∈ carrier_mat n n" using Cons.prems by auto
  let ?A = "rev (map ((⋅m) (-1)) Ys)"
  have A: "∀Z ∈ set ?A. Z ∈ carrier_mat n n" using Ys by auto
  have nY: "(-1) ⋅m Y ∈ carrier_mat n n" using Y by simp
  have c: "seq_carrier n (prod_coeff n ?A)" "seq_carrier n (exp_coeff ((-1) ⋅m Y))" "seq_carrier n (exp_coeff Y)" "seq_carrier n (prod_coeff n Ys)"
    using prod_coeff_carrier[OF A] prod_coeff_carrier[OF Ys] Y nY by auto
  have "prod_coeff n (rev (map ((⋅m) (-1)) (Y # Ys))) = cauchy_prod n (prod_coeff n ?A) (exp_coeff ((-1) ⋅m Y))"
    using prod_coeff_append[OF A, of "[(-1) ⋅m Y]"] nY by (simp add: cauchy_prod_unit_right_fun)
  hence "cauchy_prod n (prod_coeff n (rev (map ((⋅m) (-1)) (Y # Ys)))) (prod_coeff n (Y # Ys))
      = cauchy_prod n (cauchy_prod n (prod_coeff n ?A) (exp_coeff ((-1) ⋅m Y))) (cauchy_prod n (exp_coeff Y) (prod_coeff n Ys))" by simp
  also have "… = cauchy_prod n (prod_coeff n ?A) (cauchy_prod n (cauchy_prod n (exp_coeff ((-1) ⋅m Y)) (exp_coeff Y)) (prod_coeff n Ys))"
    by (simp only: cauchy_prod_assoc_fun[OF c(1,2) cauchy_prod_carrier[OF c(3,4)]] cauchy_prod_assoc_fun[OF c(2,3,4), symmetric])
  also have "… = cauchy_prod n (prod_coeff n ?A) (prod_coeff n Ys)"
    by (simp only: exp_coeff_inverse[OF Y] cauchy_prod_unit_left_fun[OF c(4)])
  finally show ?case using Cons.IH[OF Ys] by simp
qed

text ‹$f$ vanishes below degree $q$: $f_p=0$ for $p<q$.›

definition vanishes_below :: "nat ⇒ nat ⇒ (nat ⇒ complex Matrix.mat) ⇒ bool" where
  "vanishes_below n q f ⟷ (∀p<q. f p = 0m n n)"

lemma cauchy_prod_add_left:
  "seq_carrier n f ⟹ seq_carrier n g ⟹ seq_carrier n h ⟹ cauchy_prod n (λp. f p + g p) h p = cauchy_prod n f h p + cauchy_prod n g h p"
proof -
  assume a: "seq_carrier n f" "seq_carrier n g" "seq_carrier n h"
  have "cauchy_prod n (λp. f p + g p) h p = matrix_sum n (λq. f q * h (p - q) + g q * h (p - q)) (Suc p)"
    unfolding cauchy_prod_def by (rule matrix_sum_cong) (rule add_mult_distrib_mat[where nr = n and n = n and nc = n], use a in simp_all)
  also have "… = cauchy_prod n f h p + cauchy_prod n g h p"
    unfolding cauchy_prod_def by (rule matrix_sum_add_distrib) (use a in simp_all)
  finally show ?thesis .
qed

lemma cauchy_prod_add_right:
  "seq_carrier n f ⟹ seq_carrier n g ⟹ seq_carrier n h ⟹ cauchy_prod n h (λp. f p + g p) p = cauchy_prod n h f p + cauchy_prod n h g p"
proof -
  assume a: "seq_carrier n f" "seq_carrier n g" "seq_carrier n h"
  have "cauchy_prod n h (λp. f p + g p) p = matrix_sum n (λq. h q * f (p - q) + h q * g (p - q)) (Suc p)"
    unfolding cauchy_prod_def by (rule matrix_sum_cong) (rule mult_add_distrib_mat[where nr = n and n = n and nc = n], use a in simp_all)
  also have "… = cauchy_prod n h f p + cauchy_prod n h g p"
    unfolding cauchy_prod_def by (rule matrix_sum_add_distrib) (use a in simp_all)
  finally show ?thesis .
qed

lemma matrix_sum_zero: "matrix_sum n (λr. 0m n n) m = 0m n n"
  by (induction m) simp_all

lemma matrix_sum_single:
  assumes "⋀q. q < m ⟹ F q ∈ carrier_mat n n" and "⋀q. q < m ⟹ q ≠ k ⟹ F q = 0m n n" and "k < m"
  shows "matrix_sum n F m = F k"
  using assms
proof (induction m)
  case (Suc m)
  show ?case
  proof (cases "k = m")
    case True
    have "matrix_sum n F m = 0m n n"
    proof -
      have "matrix_sum n F m = matrix_sum n (λq. 0m n n) m" by (rule matrix_sum_cong) (use Suc.prems True in auto)
      also have "… = 0m n n" by (induction m) simp_all
      finally show ?thesis .
    qed
    thus ?thesis using True Suc.prems(1)[of m] by simp
  next
    case False
    thus ?thesis using Suc.IH[OF Suc.prems(1,2)] Suc.prems by (simp add: less_Suc_eq matrix_sum_dim)
  qed
qed simp

text ‹If $d$ vanishes below $q$, then $(d\ast g)_q=d_qg_0$, $(g\ast d)_q=g_0d_q$, both products vanish below
$q$, and the product of two such sequences vanishes at $q>0$ too:›

lemma cauchy_prod_low_left:
  assumes d: "seq_carrier n d" "vanishes_below n q d" and g: "seq_carrier n g"
  shows "cauchy_prod n d g q = d q * g 0"
proof -
  have "matrix_sum n (λr. d r * g (q - r)) (Suc q) = d q * g (q - q)"
    by (rule matrix_sum_single) (use d g in ‹auto simp: vanishes_below_def›)
  thus ?thesis by (simp add: cauchy_prod_def)
qed

lemma cauchy_prod_low_right:
  assumes d: "seq_carrier n d" "vanishes_below n q d" and g: "seq_carrier n g"
  shows "cauchy_prod n g d q = g 0 * d q"
proof -
  have "matrix_sum n (λr. g r * d (q - r)) (Suc q) = g 0 * d (q - 0)"
    by (rule matrix_sum_single, use d g in ‹auto simp: vanishes_below_def›)
  thus ?thesis by (simp add: cauchy_prod_def)
qed

lemma cauchy_prod_low_below:
  assumes d: "seq_carrier n d" "vanishes_below n q d" and g: "seq_carrier n g" and p: "p < q"
  shows "cauchy_prod n d g p = 0m n n" "cauchy_prod n g d p = 0m n n"
proof -
  have "cauchy_prod n d g p = matrix_sum n (λr. 0m n n) (Suc p)"
    unfolding cauchy_prod_def by (rule matrix_sum_cong) (use d g p in ‹auto simp: vanishes_below_def›)
  thus "cauchy_prod n d g p = 0m n n" by (simp only: matrix_sum_zero)
  have "cauchy_prod n g d p = matrix_sum n (λr. 0m n n) (Suc p)"
    unfolding cauchy_prod_def by (rule matrix_sum_cong) (use d g p in ‹auto simp: vanishes_below_def›)
  thus "cauchy_prod n g d p = 0m n n" by (simp only: matrix_sum_zero)
qed

lemma cauchy_prod_low_both:
  assumes "seq_carrier n d" "vanishes_below n q d" "seq_carrier n e" "vanishes_below n q e" "0 < q"
  shows "cauchy_prod n d e q = 0m n n"
proof -
  have "cauchy_prod n d e q = matrix_sum n (λr. 0m n n) (Suc q)"
    unfolding cauchy_prod_def
  proof (rule matrix_sum_cong)
    fix r assume "r < Suc q"
    hence "r < q ∨ q - r < q" using assms(5) by linarith
    thus "d r * e (q - r) = 0m n n" using assms by (auto simp: vanishes_below_def)
  qed
  thus ?thesis by (simp only: matrix_sum_zero)
qed

text ‹A palindromic formula has odd error order: agreement with $e^{tX}$ below an even degree $q$
extends to degree $q$.›

lemma sym_order:
  assumes Ys: "∀Y ∈ set Ys. Y ∈ carrier_mat n n" and X: "X ∈ carrier_mat n n"
      and pal: "rev Ys = Ys" and ord: "∀p<q. prod_coeff n Ys p = exp_coeff X p" and q: "even q" "0 < q"
  shows "prod_coeff n Ys q = exp_coeff X q"
proof -
  let ?F = "prod_coeff n Ys" and ?E = "exp_coeff X"
  define D where "D = (λp. ?F p - ?E p)"
  have F: "seq_carrier n ?F" and E: "seq_carrier n ?E" using prod_coeff_carrier[OF Ys] X by auto
  have Dc: "seq_carrier n D" unfolding seq_carrier_def D_def using seq_carrier_in[OF E] by (simp add: minus_carrier_mat)
  have Dl: "vanishes_below n q D" using ord seq_carrier_in[OF E] by (auto simp: vanishes_below_def D_def minus_r_inv_mat)
  have FE: "?F = (λp. ?E p + D p)"
    using F E by (auto simp: fun_eq_iff D_def intro!: eq_matI)
  let ?mE = "seq_scale (-1) ?E" and ?mD = "seq_scale (-1) D"
  have mEc: "seq_carrier n ?mE" and mDc: "seq_carrier n ?mD" and mDl: "vanishes_below n q ?mD"
    using E Dc Dl by (auto simp: vanishes_below_def seq_scale_def)
  have mF: "seq_scale (-1) ?F = (λp. ?mE p + ?mD p)"
    using E Dc unfolding FE by (auto simp: fun_eq_iff seq_scale_def add_smult_distrib_left_mat[where nr = n and nc = n])
  have rv: "rev (map ((⋅m) (-1)) Ys) = map ((⋅m) (-1)) Ys" using pal by (metis rev_map)
  have inv: "cauchy_prod n (seq_scale (-1) ?F) ?F = seq_one n"
    using prod_coeff_inverse[OF Ys] unfolding rv prod_coeff_scale[OF Ys] .
  have invE: "cauchy_prod n ?mE ?E q = 0m n n"
  proof -
    have "?mE = exp_coeff ((-1) ⋅m X)" by (simp add: fun_eq_iff exp_coeff_smult[OF X])
    thus ?thesis using exp_coeff_inverse[OF X] q(2) by (simp add: seq_one_def)
  qed
  have E0: "?E 0 = 1m n" and mE0: "?mE 0 = 1m n" using X by (simp_all add: exp_coeff_def seq_scale_def one_smult_mat)
  have "0m n n = cauchy_prod n (λp. ?mE p + ?mD p) (λp. ?E p + D p) q"
    using inv q(2) unfolding mF FE[symmetric] by (simp add: seq_one_def)
  also have "… = cauchy_prod n ?mE ?E q + cauchy_prod n ?mE D q + (cauchy_prod n ?mD ?E q + cauchy_prod n ?mD D q)"
    using mEc mDc E Dc by (simp add: cauchy_prod_add_left cauchy_prod_add_right seq_carrier_def)
  also have "… = D q + (-1) ^ q ⋅m D q"
    using invE cauchy_prod_low_right[OF Dc Dl mEc] cauchy_prod_low_left[OF mDc mDl E] cauchy_prod_low_both[OF mDc mDl Dc Dl q(2)] E0 mE0 Dc
    by (simp add: seq_scale_def)
  also have "… = 2 ⋅m D q" using q(1) Dc by (auto intro!: eq_matI)
  finally have z: "0m n n = 2 ⋅m D q" .
  show ?thesis
  proof (rule eq_matI)
    fix i j assume i: "i < dim_row (exp_coeff X q)" and j: "j < dim_col (exp_coeff X q)"
    have ij: "i < n" "j < n" using i j E by simp_all
    have "0 = 2 * D q $$ (i, j)" using arg_cong[OF z, of "λM. M $$ (i, j)"] Dc ij by simp
    hence "D q $$ (i, j) = 0" by simp
    thus "prod_coeff n Ys q $$ (i, j) = exp_coeff X q $$ (i, j)" using F E ij by (simp add: D_def)
  qed (use F E in simp_all)
qed

text ‹Perturbations of degree $q$ add: if $A_0=B_0=I$ and $D_a$, $D_b$ vanish below $q$, then up to degree $q$
\[ (A+D_a)\ast(B+D_b)=A\ast B+D_a+D_b. \]›

lemma pert2:
  assumes A: "seq_carrier n A" "A 0 = 1m n" and B: "seq_carrier n B" "B 0 = 1m n"
      and Da: "seq_carrier n Da" "vanishes_below n q Da" and Db: "seq_carrier n Db" "vanishes_below n q Db" and q: "0 < q" and p: "p ≤ q"
  shows "cauchy_prod n (λp. A p + Da p) (λp. B p + Db p) p = cauchy_prod n A B p + Da p + Db p"
proof -
  have e: "cauchy_prod n (λp. A p + Da p) (λp. B p + Db p) p
      = cauchy_prod n A B p + cauchy_prod n A Db p + (cauchy_prod n Da B p + cauchy_prod n Da Db p)"
    using A B Da Db by (simp add: cauchy_prod_add_left cauchy_prod_add_right seq_carrier_def)
  have AB: "cauchy_prod n A B p ∈ carrier_mat n n" using cauchy_prod_carrier[OF A(1) B(1)] by simp
  show ?thesis
  proof (cases "p < q")
    case True
    thus ?thesis unfolding e using cauchy_prod_low_below[OF Db A(1) True] cauchy_prod_low_below[OF Da B(1) True]
        cauchy_prod_low_below[OF Da Db(1) True] Da Db AB by (simp add: vanishes_below_def)
  next
    case False
    hence pq: "p = q" using p by simp
    have "cauchy_prod n A Db q = Db q" "cauchy_prod n Da B q = Da q" "cauchy_prod n Da Db q = 0m n n"
      using cauchy_prod_low_right[OF Db A(1)] cauchy_prod_low_left[OF Da B(1)] cauchy_prod_low_both[OF Da Db q] A B Da Db by simp_all
    thus ?thesis unfolding e unfolding pq using Da Db cauchy_prod_carrier[OF A(1) B(1)] by (auto intro!: eq_matI)
  qed
qed

lemma cauchy_prod_congr:
  assumes "∀p≤q. f p = f' p" "∀p≤q. g p = g' p" "p ≤ q"
  shows "cauchy_prod n f g p = cauchy_prod n f' g' p"
  unfolding cauchy_prod_def by (rule matrix_sum_cong) (use assms in auto)

text ‹The key step of Suzuki's recursion.  If the formula $\Phi$ (with factors $Y$) agrees with $e^{tX}$ below
degree $q$, then the formula made of copies of $\Phi$ with the factors scaled by $c_1,\dots,c_k$ satisfies,
up to degree $q$,
\[ \mathrm{coeff}_p=\frac{\bigl((\sum_jc_j)X\bigr)^p}{p!}+\Bigl(\sum_jc_j^{\,p}\Bigr)\bigl(\mathrm{coeff}_p(\Phi)-X^p/p!\bigr), \]
so the error at degree $q$ vanishes when $\sum_jc_j^{\,q}=0$.›

lemma scaled_copies:
  assumes Ys: "∀Y ∈ set Ys. Y ∈ carrier_mat n n" and X: "X ∈ carrier_mat n n"
      and ord: "∀p<q. prod_coeff n Ys p = exp_coeff X p" and q: "0 < q"
  shows "∀p≤q. prod_coeff n (concat (map (λc. map ((⋅m) c) Ys) cs)) p
           = exp_coeff (sum_list cs ⋅m X) p + (∑c←cs. c ^ p) ⋅m (prod_coeff n Ys p - exp_coeff X p)"
proof (induction cs)
  case Nil
  show ?case
  proof (intro allI impI)
    fix p assume "p ≤ q"
    have "exp_coeff (0 ⋅m X) p = seq_one n p" using zero_smult_mat[OF X] exp_coeff_zero by simp
    show "prod_coeff n (concat (map (λc. map ((⋅m) c) Ys) [])) p
        = exp_coeff (sum_list [] ⋅m X) p + (∑c←[]. c ^ p) ⋅m (prod_coeff n Ys p - exp_coeff X p)"
    proof -
      have "prod_coeff n Ys p - exp_coeff X p ∈ carrier_mat n n" using X by (simp add: minus_carrier_mat)
      hence z: "(0::complex) ⋅m (prod_coeff n Ys p - exp_coeff X p) = 0m n n" by (rule zero_smult_mat)
      show ?thesis using ‹exp_coeff (0 ⋅m X) p = seq_one n p› by (simp add: z seq_one_def)
    qed
  qed
next
  case (Cons c cs)
  let ?F = "prod_coeff n Ys" and ?E = "exp_coeff X"
  define D where "D = (λp. ?F p - ?E p)"
  let ?R = "concat (map (λc. map ((⋅m) c) Ys) cs)"
  have F: "seq_carrier n ?F" and E: "seq_carrier n ?E" using prod_coeff_carrier[OF Ys] X by auto
  have Dc: "seq_carrier n D" unfolding seq_carrier_def D_def using seq_carrier_in[OF E] by (simp add: minus_carrier_mat)
  have Dl: "vanishes_below n q D" using ord seq_carrier_in[OF E] by (auto simp: vanishes_below_def D_def)
  have cY: "∀Y ∈ set (map ((⋅m) c) Ys). Y ∈ carrier_mat n n" and cR: "∀Y ∈ set ?R. Y ∈ carrier_mat n n"
    using Ys by auto
  define Ac where "Ac = exp_coeff (c ⋅m X)"
  define Dc' where "Dc' = seq_scale c D"
  define Ar where "Ar = exp_coeff (sum_list cs ⋅m X)"
  define Dr where "Dr = (λp. (∑c←cs. c ^ p) ⋅m D p)"
  have Acc: "seq_carrier n Ac" "Ac 0 = 1m n" and Arc: "seq_carrier n Ar" "Ar 0 = 1m n"
    using X by (simp_all add: Ac_def Ar_def exp_coeff_def one_smult_mat)
  have Dcc: "seq_carrier n Dc'" "vanishes_below n q Dc'" using Dc Dl by (auto simp: Dc'_def seq_scale_def vanishes_below_def)
  have Drc: "seq_carrier n Dr" "vanishes_below n q Dr" using Dc Dl by (auto simp: Dr_def seq_carrier_def vanishes_below_def)
  have sF: "seq_scale c ?F = (λp. Ac p + Dc' p)"
  proof -
    have "?F = (λp. ?E p + D p)" using F E by (auto simp: fun_eq_iff D_def intro!: eq_matI)
    hence "seq_scale c ?F = (λp. seq_scale c ?E p + seq_scale c D p)"
      using E Dc by (auto simp: fun_eq_iff seq_scale_def add_smult_distrib_left_mat[where nr = n and nc = n])
    thus ?thesis by (simp add: Ac_def Dc'_def fun_eq_iff exp_coeff_smult[OF X])
  qed
  have IH: "∀p≤q. prod_coeff n ?R p = Ar p + Dr p" using Cons.IH by (simp add: Ar_def Dr_def D_def)
  show ?case
  proof (intro allI impI)
    fix p assume p: "p ≤ q"
    have "prod_coeff n (concat (map (λc. map ((⋅m) c) Ys) (c # cs))) p = cauchy_prod n (seq_scale c ?F) (prod_coeff n ?R) p"
      using prod_coeff_append[OF cY cR] prod_coeff_scale[OF Ys] by simp
    also have "… = cauchy_prod n (λp. Ac p + Dc' p) (λp. Ar p + Dr p) p"
      unfolding sF by (rule cauchy_prod_congr) (use IH p in auto)
    also have "… = cauchy_prod n Ac Ar p + Dc' p + Dr p" by (rule pert2[OF Acc Arc Dcc Drc q p])
    also have "cauchy_prod n Ac Ar p = exp_coeff (sum_list (c # cs) ⋅m X) p"
      unfolding Ac_def Ar_def using exp_coeff_add[OF X, of c "sum_list cs" p] by simp
    finally have r: "prod_coeff n (concat (map (λc. map ((⋅m) c) Ys) (c # cs))) p
        = exp_coeff (sum_list (c # cs) ⋅m X) p + Dc' p + Dr p" .
    have d: "Dc' p + Dr p = (∑c←c # cs. c ^ p) ⋅m D p"
      using Dc by (simp add: Dc'_def Dr_def seq_scale_def add_smult_distrib_right_mat[OF seq_carrier_in[OF Dc], symmetric])
    have "exp_coeff (sum_list (c # cs) ⋅m X) p + Dc' p + Dr p = exp_coeff (sum_list (c # cs) ⋅m X) p + (Dc' p + Dr p)"
      by (rule assoc_add_mat[where nr = n and nc = n]) (use X Dcc Drc in simp_all)
    thus "prod_coeff n (concat (map (λc. map ((⋅m) c) Ys) (c # cs))) p
        = exp_coeff (sum_list (c # cs) ⋅m X) p + (∑c←c # cs. c ^ p) ⋅m (prod_coeff n Ys p - exp_coeff X p)"
      using r d by (simp add: D_def)
  qed
qed

text ‹The constant term of a product is $I$ and its linear term the sum of the factors; the sum of the
factors is additive, symmetric under reversal, and linear under scaling.›

lemma prod_coeff_zero: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ prod_coeff n Ys 0 = 1m n"
  by (induction Ys) (auto simp: cauchy_prod_def seq_one_def exp_coeff_def one_smult_mat)

lemma prod_coeff_one: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ prod_coeff n Ys 1 = hamiltonian_sum n Ys"
proof (induction Ys)
  case Nil
  thus ?case by (simp add: seq_one_def)
next
  case (Cons Y Ys)
  have Y: "Y ∈ carrier_mat n n" and Ys: "∀Z ∈ set Ys. Z ∈ carrier_mat n n" using Cons.prems by auto
  have F1: "prod_coeff n Ys 1 ∈ carrier_mat n n" and H: "hamiltonian_sum n Ys ∈ carrier_mat n n"
    using prod_coeff_carrier[OF Ys] hamiltonian_sum_carrier[of Ys n] Ys by auto
  have "prod_coeff n (Y # Ys) 1 = exp_coeff Y 1 * prod_coeff n Ys 0 + exp_coeff Y 0 * prod_coeff n Ys 1"
    using seq_carrier_mult[OF exp_coeff_carrier[OF Y] prod_coeff_carrier[OF Ys], of 0 1] by (simp add: cauchy_prod_def)
  also have "… = Y + prod_coeff n Ys 1" using Y F1 prod_coeff_zero[OF Ys] by (simp add: exp_coeff_def one_smult_mat)
  finally show ?case using Cons.IH[OF Ys] by simp
qed

lemma hamiltonian_sum_append: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ ∀Y ∈ set Zs. Y ∈ carrier_mat n n ⟹ hamiltonian_sum n (Ys @ Zs) = hamiltonian_sum n Ys + hamiltonian_sum n Zs"
proof (induction Ys)
  case Nil
  thus ?case using hamiltonian_sum_carrier[of Zs n] by simp
next
  case (Cons Y Ys)
  have c: "Y ∈ carrier_mat n n" "hamiltonian_sum n Ys ∈ carrier_mat n n" "hamiltonian_sum n Zs ∈ carrier_mat n n"
    using Cons.prems hamiltonian_sum_carrier[of Ys n] hamiltonian_sum_carrier[of Zs n] by auto
  thus ?case using Cons by (simp add: assoc_add_mat[OF c])
qed

lemma hamiltonian_sum_rev: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ hamiltonian_sum n (rev Ys) = hamiltonian_sum n Ys"
proof (induction Ys)
  case (Cons Y Ys)
  have c: "Y ∈ carrier_mat n n" "hamiltonian_sum n Ys ∈ carrier_mat n n" using Cons.prems hamiltonian_sum_carrier[of Ys n] by auto
  have "hamiltonian_sum n (rev (Y # Ys)) = hamiltonian_sum n (rev Ys) + (Y + 0m n n)" using Cons.prems by (simp add: hamiltonian_sum_append)
  thus ?case using Cons c by (simp add: comm_add_mat[OF c(2) c(1)])
qed simp

lemma hamiltonian_sum_scale: "∀Y ∈ set Ys. Y ∈ carrier_mat n n ⟹ hamiltonian_sum n (map ((⋅m) c) Ys) = c ⋅m hamiltonian_sum n Ys"
proof (induction Ys)
  case Nil
  show ?case by (rule eq_matI) auto
next
  case (Cons Y Ys)
  thus ?case using hamiltonian_sum_carrier[of Ys n] by (simp add: add_smult_distrib_left_mat[where nr = n and nc = n])
qed

text ‹A product formula is a list of factors $(a,H)$ standing for $e^{iatH}$; its coefficients are those
of the matrices ‹factor_gen (a, H)› $=iaH$.  The symmetric Strang formula
$e^{itH_1/2}\cdots e^{itH_m/2}e^{itH_m/2}\cdots e^{itH_1/2}$ and Suzuki's recursion
$S_{2k+2}=S_{2k}(u)^2\,S_{2k}(1-4u)\,S_{2k}(u)^2$ with $4u^q+(1-4u)^q=0$, $q=2k+3$.›

definition factor_gen :: "real × complex Matrix.mat ⇒ complex Matrix.mat" where
  "factor_gen x = (𝗂 * complex_of_real (fst x)) ⋅m snd x"

definition strang :: "complex Matrix.mat list ⇒ (real × complex Matrix.mat) list" where
  "strang Hs = map (λH. (1 / 2, H)) Hs @ rev (map (λH. (1 / 2, H)) Hs)"

definition suzuki_weight :: "nat ⇒ real" where
  "suzuki_weight q = 1 / (4 - root q 4)"

definition suzuki_weights :: "nat ⇒ real list" where
  "suzuki_weights q = (let u = suzuki_weight q in [u, u, 1 - 4 * u, u, u])"

fun suzuki :: "nat ⇒ complex Matrix.mat list ⇒ (real × complex Matrix.mat) list" where
  "suzuki 0 Hs = strang Hs"
| "suzuki (Suc k) Hs = concat (map (λc. map (λx. (c * fst x, snd x)) (suzuki k Hs)) (suzuki_weights (2 * k + 3)))"

text ‹Suzuki's weights: for odd $q\ge3$, $u=1/(4-4^{1/q})$ satisfies $4u^q+(1-4u)^q=0$, and the weights
$u,u,1-4u,u,u$ add up to $1$.›

lemma suzuki_weight_cond:
  assumes q: "odd q" "3 ≤ q"
  shows "4 * suzuki_weight q ^ q + (1 - 4 * suzuki_weight q) ^ q = 0"
proof -
  define s where "s = root q 4"
  have sq: "s ^ q = 4" using q by (simp add: s_def)
  have s4: "4 - s ≠ 0"
  proof
    assume "4 - s = 0"
    hence "s ^ q = 4 ^ q" by simp
    moreover have "(4::real) ^ q > 4" using power_strict_increasing[of 1 q "4::real"] q by simp
    ultimately show False using sq by simp
  qed
  have "1 - 4 * suzuki_weight q = - s / (4 - s)" using s4 by (simp add: suzuki_weight_def s_def[symmetric] field_simps)
  hence "4 * suzuki_weight q ^ q + (1 - 4 * suzuki_weight q) ^ q = (4 - s ^ q) / (4 - s) ^ q"
    using q(1) s4 by (simp add: suzuki_weight_def s_def[symmetric] power_divide power_minus_odd field_simps)
  thus ?thesis using sq by simp
qed

text ‹Scaling a factor scales its generator; the formulas consist of factors of the given Hamiltonians, are
$n\times n$, and are palindromes:›

lemma factor_gen_scale: "factor_gen (c * a, H) = complex_of_real c ⋅m factor_gen (a, H)"
  by (rule eq_matI) (auto simp: factor_gen_def)

lemma suzuki_snd: "x ∈ set (suzuki k Hs) ⟹ snd x ∈ set Hs"
  by (induction k arbitrary: x) (auto simp: strang_def)

lemma suzuki_carrier: "∀H ∈ set Hs. H ∈ carrier_mat n n ⟹ ∀Y ∈ set (map factor_gen (suzuki k Hs)). Y ∈ carrier_mat n n"
  using suzuki_snd by (fastforce simp: factor_gen_def)

lemma suzuki_palindrome: "rev (suzuki k Hs) = suzuki k Hs"
  by (induction k) (simp_all add: strang_def suzuki_weights_def Let_def rev_map)

text ‹The Strang formula agrees with $e^{itH}$, $H=\sum_jH_j$, up to degree $2$:›

lemma strang_order:
  assumes Hs: "∀H ∈ set Hs. H ∈ carrier_mat n n"
  shows "∀p≤2. prod_coeff n (map factor_gen (strang Hs)) p = exp_coeff (𝗂 ⋅m hamiltonian_sum n Hs) p"
proof -
  let ?Z = "map ((⋅m) (𝗂 / 2)) Hs"
  have st: "map factor_gen (strang Hs) = ?Z @ rev ?Z"
    by (simp add: strang_def factor_gen_def rev_map comp_def)
  have Z: "∀Y ∈ set ?Z. Y ∈ carrier_mat n n" using Hs by auto
  have St: "∀Y ∈ set (map factor_gen (strang Hs)). Y ∈ carrier_mat n n" unfolding st using Z by auto
  have pal: "rev (map factor_gen (strang Hs)) = map factor_gen (strang Hs)" unfolding st by simp
  have H: "hamiltonian_sum n Hs ∈ carrier_mat n n" using hamiltonian_sum_carrier[of Hs n] Hs by auto
  have X: "𝗂 ⋅m hamiltonian_sum n Hs ∈ carrier_mat n n" using H by simp
  have h2: "hamiltonian_sum n (map factor_gen (strang Hs)) = 𝗂 ⋅m hamiltonian_sum n Hs"
  proof -
    have "hamiltonian_sum n (map factor_gen (strang Hs)) = (𝗂 / 2) ⋅m hamiltonian_sum n Hs + (𝗂 / 2) ⋅m hamiltonian_sum n Hs"
      unfolding st hamiltonian_sum_append[OF Z] by (simp add: Z hamiltonian_sum_rev hamiltonian_sum_scale[OF Hs] hamiltonian_sum_append)
    also have "… = 𝗂 ⋅m hamiltonian_sum n Hs" using H by (auto intro!: eq_matI)
    finally show ?thesis .
  qed
  have ord1: "∀p<2. prod_coeff n (map factor_gen (strang Hs)) p = exp_coeff (𝗂 ⋅m hamiltonian_sum n Hs) p"
  proof (intro allI impI)
    fix p :: nat assume "p < 2"
    hence "p = 0 ∨ p = 1" by auto
    thus "prod_coeff n (map factor_gen (strang Hs)) p = exp_coeff (𝗂 ⋅m hamiltonian_sum n Hs) p"
      using prod_coeff_zero[OF St] prod_coeff_one[OF St] h2 X by (auto simp: exp_coeff_def one_smult_mat)
  qed
  have "prod_coeff n (map factor_gen (strang Hs)) 2 = exp_coeff (𝗂 ⋅m hamiltonian_sum n Hs) 2" by (rule sym_order[OF St X pal ord1]) simp_all
  thus ?thesis using ord1 by (auto simp: le_less)
qed

text ‹By induction on $k$, using the palindrome property (odd order) and ‹scaled_copies› with
$\sum_jc_j=1$ and $\sum_jc_j^{2k+3}=0$:
\[ \mathrm{coeff}_p\bigl(S_{2k+2}\bigr)=\frac{(iH)^p}{p!}\qquad(p\le 2k+2). \]›

theorem suzuki_order:
  assumes Hs: "∀H ∈ set Hs. H ∈ carrier_mat n n"
  shows "∀p≤2 * k + 2. prod_coeff n (map factor_gen (suzuki k Hs)) p = exp_coeff (𝗂 ⋅m hamiltonian_sum n Hs) p"
proof (induction k)
  case 0
  thus ?case using strang_order[OF Hs] by simp
next
  case (Suc k)
  let ?S = "map factor_gen (suzuki k Hs)" and ?q = "2 * k + 3" and ?X = "𝗂 ⋅m hamiltonian_sum n Hs"
  let ?cs = "map complex_of_real (suzuki_weights ?q)"
  have S: "∀Y ∈ set ?S. Y ∈ carrier_mat n n" by (rule suzuki_carrier[OF Hs])
  have X: "?X ∈ carrier_mat n n" using hamiltonian_sum_carrier[of Hs n] Hs by auto
  have ordS: "∀p<?q. prod_coeff n ?S p = exp_coeff ?X p" using Suc.IH by auto
  have mt: "map factor_gen (suzuki (Suc k) Hs) = concat (map (λc. map ((⋅m) c) ?S) ?cs)"
    by (simp add: map_concat comp_def factor_gen_scale)
  define u where "u = complex_of_real (suzuki_weight ?q)"
  have cs: "?cs = [u, u, 1 - 4 * u, u, u]" by (simp add: suzuki_weights_def u_def Let_def)
  have sum1: "sum_list ?cs = 1" by (simp add: cs)
  have sumq: "(∑c←?cs. c ^ ?q) = 0"
  proof -
    have "(∑c←?cs. c ^ ?q) = complex_of_real (4 * suzuki_weight ?q ^ ?q + (1 - 4 * suzuki_weight ?q) ^ ?q)"
      by (simp add: cs u_def)
    thus ?thesis using suzuki_weight_cond[of ?q] by simp
  qed
  have sc: "∀p≤?q. prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) p
      = exp_coeff (sum_list ?cs ⋅m ?X) p + (∑c←?cs. c ^ p) ⋅m (prod_coeff n ?S p - exp_coeff ?X p)"
    unfolding mt by (rule scaled_copies[OF S X ordS]) simp
  have ordq: "∀p≤?q. prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) p = exp_coeff ?X p"
  proof (intro allI impI)
    fix p assume p: "p ≤ ?q"
    have z: "(∑c←?cs. c ^ p) ⋅m (prod_coeff n ?S p - exp_coeff ?X p) = 0m n n"
    proof (cases "p < ?q")
      case True
      hence "prod_coeff n ?S p - exp_coeff ?X p = 0m n n" using ordS seq_carrier_in[OF exp_coeff_carrier[OF X]] by simp
      thus ?thesis by (auto intro!: eq_matI)
    next
      case False
      hence "p = ?q" using p by simp
      have "prod_coeff n ?S p - exp_coeff ?X p ∈ carrier_mat n n" using X by (simp add: minus_carrier_mat)
      thus ?thesis using sumq ‹p = ?q› by (simp add: zero_smult_mat)
    qed
    have e: "prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) p
        = exp_coeff (sum_list ?cs ⋅m ?X) p + (∑c←?cs. c ^ p) ⋅m (prod_coeff n ?S p - exp_coeff ?X p)"
      using sc p by blast
    show "prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) p = exp_coeff ?X p"
      unfolding e z sum1 using seq_carrier_in[OF exp_coeff_carrier[OF X]] X by (simp add: one_smult_mat)
  qed
  have S': "∀Y ∈ set (map factor_gen (suzuki (Suc k) Hs)). Y ∈ carrier_mat n n" by (rule suzuki_carrier[OF Hs])
  have pal': "rev (map factor_gen (suzuki (Suc k) Hs)) = map factor_gen (suzuki (Suc k) Hs)"
    using suzuki_palindrome[of "Suc k" Hs] by (metis rev_map)
  have top: "prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) (?q + 1) = exp_coeff ?X (?q + 1)"
    by (rule sym_order[OF S' X pal']) (use ordq in auto)
  show ?case
  proof (intro allI impI)
    fix p assume "p ≤ 2 * Suc k + 2"
    hence "p ≤ ?q ∨ p = ?q + 1" by arith
    thus "prod_coeff n (map factor_gen (suzuki (Suc k) Hs)) p = exp_coeff ?X p" using ordq top by blast
  qed
qed

end