AFTD Auto-Formalizing Theoretical Domains

song_route_type

def

The type (A = true, B = false) of the local route of a vertex, as in Table 1 of arXiv:2610.33042: a block holding the internal M-diagonal ad carries a single route c-d-a-b of type B; a block holding the internal M-diagonal bc carries a single route a-b-c-d of type A; a block holding neither carries the type A route a-d and the type B route c-b, so a and d are type A and b and c are type B.

Statement

def song_route_type (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) (x : Fin (2 * k) × Fin (2 * k)) : Bool
Source
step towards admissible_diagonal_selection_isometric_path_cover
Verified
28 Oct 2026
Axioms
none listed
Built on 3
  • song_block_projThe block projection pi(r,c) = (r/2, c/2) (integer division) from the (2k)x(2k) grid onto the k x k block grid.
  • song_corner_labelThe label of a grid vertex inside its block, given by its two coordinate parities: (r mod 2, c mod 2), so that a = (0,0), b = (0,1), c =…
  • song_block_vertexCorner (u,v) of the 2x2 block B_{ij} of the (2k)x(2k) grid: song_block_vertex k i j u v = (2i+u, 2j+v). With (u,v) =…

Lean source view module on GitHub

/-- Type of the local route through a vertex: `true` = type A (ports a,d) and `false` = type B (ports c,b), read off from the block's internal M-diagonal and the vertex's corner label. -/
def song_route_type (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) (x : Fin (2 * k) × Fin (2 * k)) : Bool := let p := song_block_proj k x
   if s(song_block_vertex k p.1 p.2 0 0, song_block_vertex k p.1 p.2 1 1) ∈ M then false
   else if s(song_block_vertex k p.1 p.2 0 1, song_block_vertex k p.1 p.2 1 0) ∈ M then true
   else decide ((song_corner_label k x).1 = (song_corner_label k x).2)
See it in the graphDiscuss this resultChallenge it