Theory Expander_Graphs_TTS

section ‹Setup for Types to Sets\label{sec:tts}›

theory Expander_Graphs_TTS

text ‹This section sets up a sublocale with the assumption that there is a finite type with the same
cardinality as the vertex set of a regular graph. This allows defining the adjacency matrix for
the graph using type-based linear algebra.

Theorems shown in the sublocale that do not refer to the local type are then lifted to the
@{locale regular_graph} locale using the Types-To-Sets mechanism.›

locale regular_graph_tts = regular_graph +
  fixes n_itself :: "('n :: finite) itself"
  assumes td: "(f :: ('n  'a)) g. type_definition f g (verts G)"

definition td_components :: "('n  'a) × ('a  'n)"
  where "td_components = (SOME q. type_definition (fst q) (snd q) (verts G))"

definition enum_verts where "enum_verts = fst td_components"
definition enum_verts_inv where "enum_verts_inv = snd td_components"

sublocale type_definition "enum_verts" "enum_verts_inv" "verts G"
proof -
  have 0:"q. type_definition ((fst q)::('n  'a)) (snd q) (verts G)"
    using td by simp
  show "type_definition enum_verts enum_verts_inv (verts G)"
    unfolding td_components_def enum_verts_def enum_verts_inv_def using someI_ex[OF 0] by simp

lemma enum_verts: "bij_betw enum_verts UNIV (verts G)"
  unfolding bij_betw_def by (simp add: Rep_inject Rep_range inj_on_def)

text ‹The stochastic matrix associated to the graph.›

definition A :: "('c::field)^'n^'n" where
  "A = (χ i j. of_nat (count (edges G) (enum_verts j,enum_verts i))/of_nat d)"

lemma card_n: "CARD('n) = n"
  unfolding n_def card by simp

lemma symmetric_A: "transpose A = A"
proof -
  have "A $ i $ j = A $ j $ i" for i j
    unfolding A_def count_edges arcs_betw_def using symmetric_multi_graphD[OF sym]
    by auto
  thus ?thesis
    unfolding transpose_def
    by (intro iffD2[OF vec_eq_iff] allI) auto

lemma g_step_conv:
  "(χ i. g_step f (enum_verts i)) = A *v (χ i. f (enum_verts i))"
proof -
  have "g_step f (enum_verts i) = (jUNIV. A $ i $ j * f (enum_verts j))" (is "?L = ?R") for i
  proof -
    have "?L = (xin_arcs G (enum_verts i). f (tail G x) / d)"
      unfolding g_step_def by simp
    also have "... = (x∈#vertices_to G (enum_verts i). f x/d)"
      unfolding verts_to_alt sum_unfold_sum_mset by (simp add:image_mset.compositionality comp_def)
    also have "... = (jverts G. (count (vertices_to G (enum_verts i)) j) * (f j / real d))"
      by (intro sum_mset_conv_2 set_mset_vertices_to) auto
    also have "... = (jverts G. (count (edges G) (j,enum_verts i)) * (f j / real d))"
      unfolding vertices_to_def count_mset_exp
      by (intro sum.cong arg_cong[where f="real"] arg_cong2[where f="(*)"])
       (auto simp add:filter_filter_mset image_mset_filter_mset_swap[symmetric] prod_eq_iff ac_simps)
    also have "...=(jUNIV.(count(edges G)(enum_verts j,enum_verts i))*(f(enum_verts j)/real d))"
      by (intro sum.reindex_bij_betw[symmetric] enum_verts)
    also have "... = ?R"
      unfolding A_def by simp
    finally show ?thesis by simp
  thus ?thesis
    unfolding matrix_vector_mult_def by (intro iffD2[OF vec_eq_iff] allI) simp

lemma g_inner_conv:
  "g_inner f g = (χ i. f (enum_verts i))  (χ i. g (enum_verts i))"
  unfolding inner_vec_def g_inner_def vec_lambda_beta inner_real_def conjugate_real_def
  by (intro sum.reindex_bij_betw[symmetric] enum_verts)

lemma g_norm_conv:
  "g_norm f = norm (χ i. f (enum_verts i))"
proof -
  have "g_norm f^2 = norm (χ i. f (enum_verts i))^2"
    unfolding g_norm_sq power2_norm_eq_inner g_inner_conv by simp
  thus ?thesis
    using g_norm_nonneg norm_ge_zero by simp


lemma eg_tts_1:
  assumes "regular_graph G"
  assumes "(f::('n::finite)  'a) g. type_definition f g (verts G)"
  shows "regular_graph_tts TYPE('n) G"
  using assms
  unfolding regular_graph_tts_def  regular_graph_tts_axioms_def by auto

context regular_graph

lemma remove_finite_premise_aux:
  assumes "(Rep :: 'n   'a) Abs. type_definition Rep Abs (verts G)"
  shows "class.finite TYPE('n)"
proof -
  obtain Rep :: "'n  'a" and Abs where d:"type_definition Rep Abs (verts G)"
    using assms by auto
  interpret type_definition Rep Abs "verts G"
    using d by simp

  have "finite (verts G)" by simp
  thus ?thesis
    unfolding class.finite_def univ by auto

lemma remove_finite_premise:
  "(class.finite TYPE('n)  (Rep :: 'n   'a) Abs. type_definition Rep Abs (verts G)  PROP Q)
   ((Rep :: 'n   'a) Abs. type_definition Rep Abs (verts G)  PROP Q)"
  (is "?L  ?R")
proof (intro Pure.equal_intr_rule)
  assume e:"(Rep :: 'n   'a) Abs. type_definition Rep Abs (verts G)" and l:"PROP ?L"
  hence f: "class.finite TYPE('n)"
    using remove_finite_premise_aux[OF e] by simp

  show "PROP ?R"
    using l[OF f] by auto
  assume "(Rep :: 'n   'a) Abs. type_definition Rep Abs (verts G)" and l:"PROP ?R"
  show "PROP ?L"
    using l by auto