Fixed case forest and face-refinement states
DefinitionKepler_LPCaseModelThe graph-code array is the ordered concatenation of two fixed blocks with and records, hence records. Each record is a pair of arbitrary strings called graph identifier and tree code; this concatenation does not interpret them. A face list is any finite ordered list of finite lists of natural labels, whose face gives cyclic directed pairs , with an empty face giving no pairs and a singleton giving a loop. To split at a directed pair , scan for the first face containing , leaving all preceding and following faces in their original order. If no face contains it, leave unchanged. In the first containing face , let be the first index of in its cyclic dart list, and rotate the vertex list left by and then left by , putting the predecessor of 's first vertex first. If the rotated list has at most three vertices, replace by this rotated list alone. Otherwise replace it, in order, by its first three vertices and the list consisting of its first vertex followed by its vertices from index onward. Natural subtraction truncates at zero, and the head lookup has default label , although the branch using that head has length greater than . No distinctness, nonemptiness or graph-validity condition is imposed on the input list. A case state is a face list and a Boolean flag called standard. A split rule carries arbitrary natural labels: node218 and node236 each have two children, edge and triangle each two, quad five, pent eleven, hex seven, and high, mid and addBig each one. At a quad branch, children split at , children split at , and child preserves the state. At pent, form the cyclic dart list of those five labels and rotate it left once. Child preserves the state; children split at respective entries ; child for first splits at entry and then at entry of that dart list rotated left twice. At a hex rule, form its six-label dart list and rotate left once; child preserves the state and children split at entries . Every such refinement sets standard to false, even if no containing face was found. Other rules preserve the entire state. Indexed dart reads use if out of range, though the specified child-index bounds put these lists' indices in range. A finite case tree has natural-number payloads at leaves and split rules with indexed child trees at branches. State annotation starts from any given state, replaces each leaf ordinal by the pair of and the current state, and recursively passes the child state just defined down every branch. It tests no branch guard, does not compare an ordinal with the size of a data table, and proves no geometric claim; the initial state is an argument, not required here to have a true standard flag.
Source and scope. Primary §9; formal_lp/hypermap/computations/informal_computations.hl:22–41 and main/prove_flyspeck_lp.hl:856–1037. Concatenates all 19,715 fixed graph records and preserves source face ordering and standard/refined state transitions.
/-
Flyspeck source material is reproduced and adapted under this license:
MIT License
Copyright (c) 2014 Thomas C. Hales
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
-/
import Definitions.Def_Kepler_LPCases
import Definitions.Def_Kepler_LPCaseData00
import Definitions.Def_Kepler_LPCaseData01
import Definitions.Def_Kepler_LPTemplateModel
set_option autoImplicit false
set_option maxRecDepth 4096
namespace KeplerMission.SourceLP
/-- Pinned final Flyspeck trees, in the unchanged tame archive order.
Revision 1ce0353008eba83d3c76ae9a25c3c242e4802d53.
Only branch and leaf specification data are included, no proof certificates. -/
def sourceGraphCodes : Array SourceGraphCode :=
sourceCaseBlock0 ++ sourceCaseBlock1
end KeplerMission.SourceLP
set_option autoImplicit false
namespace KeplerMission.SourceLP
/-- Exact pure list refinement from `informal_computations.hl:22–41`.
No geometric property is asserted by this operation. -/
def splitFaceList : FaceList → ℕ × ℕ → FaceList
| [], _ => []
| f :: tail, d =>
if d ∈ FaceList.faceDarts f then
let i := (FaceList.faceDarts f).idxOf d
let rotated := (f.rotate i).rotate (f.length - 1)
if rotated.length ≤ 3 then rotated :: tail
else rotated.take 3 :: ((rotated.headD 0) :: rotated.drop 2) :: tail
else f :: splitFaceList tail d
/-- Refined fan state. The source branch tree determines both fields. -/
structure CaseState where
faces : FaceList
standard : Bool
def SplitRule.childState (rule : SplitRule) (i : Fin rule.arity)
(state : CaseState) : CaseState :=
let refine (d : ℕ × ℕ) := ⟨splitFaceList state.faces d, false⟩
match rule with
| .quad a b c _ =>
if i.val = 0 ∨ i.val = 2 then refine (b, c)
else if i.val = 1 ∨ i.val = 3 then refine (a, b)
else state
| .pent a b c d e =>
let darts := (FaceList.faceDarts [a, b, c, d, e]).rotate 1
if i.val = 0 then state
else if i.val ≤ 5 then refine (darts[i.val - 1]?.getD (0, 0))
else
let first := splitFaceList state.faces (darts[i.val - 6]?.getD (0, 0))
⟨splitFaceList first ((darts.rotate 2)[i.val - 6]?.getD (0, 0)), false⟩
| .hex a b c d e f =>
let darts := (FaceList.faceDarts [a, b, c, d, e, f]).rotate 1
if i.val = 0 then state else refine (darts[i.val - 1]?.getD (0, 0))
| _ => state
structure LeafLocation where
ordinal : ℕ
state : CaseState
/-- Annotate every fixed source leaf by deterministic fan refinements. -/
def SourceCaseTree.withState (state : CaseState) : SourceCaseTree ℕ → SourceCaseTree LeafLocation
| .leaf ordinal => .leaf ⟨ordinal, state⟩
| .branch rule children => .branch rule (fun i =>
(children i).withState (rule.childState i state))
end KeplerMission.SourceLP
Read-back
What the Lean code literally says, in plain math · gpt-6
The graph-code array is the ordered concatenation of two fixed blocks with and records, hence records. Each record is a pair of arbitrary strings called graph identifier and tree code; this concatenation does not interpret them. A face list is any finite ordered list of finite lists of natural labels, whose face gives cyclic directed pairs , with an empty face giving no pairs and a singleton giving a loop. To split at a directed pair , scan for the first face containing , leaving all preceding and following faces in their original order. If no face contains it, leave unchanged. In the first containing face , let be the first index of in its cyclic dart list, and rotate the vertex list left by and then left by , putting the predecessor of 's first vertex first. If the rotated list has at most three vertices, replace by this rotated list alone. Otherwise replace it, in order, by its first three vertices and the list consisting of its first vertex followed by its vertices from index onward. Natural subtraction truncates at zero, and the head lookup has default label , although the branch using that head has length greater than . No distinctness, nonemptiness or graph-validity condition is imposed on the input list. A case state is a face list and a Boolean flag called standard. A split rule carries arbitrary natural labels: node218 and node236 each have two children, edge and triangle each two, quad five, pent eleven, hex seven, and high, mid and addBig each one. At a quad branch, children split at , children split at , and child preserves the state. At pent, form the cyclic dart list of those five labels and rotate it left once. Child preserves the state; children split at respective entries ; child for first splits at entry and then at entry of that dart list rotated left twice. At a hex rule, form its six-label dart list and rotate left once; child preserves the state and children split at entries . Every such refinement sets standard to false, even if no containing face was found. Other rules preserve the entire state. Indexed dart reads use if out of range, though the specified child-index bounds put these lists' indices in range. A finite case tree has natural-number payloads at leaves and split rules with indexed child trees at branches. State annotation starts from any given state, replaces each leaf ordinal by the pair of and the current state, and recursively passes the child state just defined down every branch. It tests no branch guard, does not compare an ordinal with the size of a data table, and proves no geometric claim; the initial state is an argument, not required here to have a true standard flag.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.