How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The finite-table coloring algorithm terminates and is correct
Statement
For , a candidate table given as a finite list of finite lists of integers, either rack or quandle mode, and a finite regular oriented diagram with arcs and crossings, the finite-table algorithm terminates. It reports the first failed table-shape, table-entry, or rack/quandle-axiom condition with a witness; if every selected axiom holds, it returns exactly all rack or quandle colorings of , each once, and their count. For a candidate with rows, shape validation reads its row count and all row lengths. On a shape-valid table it performs at most row-shape, table-entry, column-permutation, triple, and diagonal checks, and tests at most arc assignments, each against the crossing rules.
Statement references
Facts & Assumptions
Given: The finite table, selected mode, and diagram described in the Statement.
Check a finite rack table and enumerate diagram colorings: the algorithm checks table format, right-translation columns, all ordered triples for self-distributivity, and (in quandle mode) the diagonal before enumerating all arc assignments.
Racks, diagram fundamental quandles, and adjoint groups: a rack has bijective right translations and is right self-distributive; a quandle also satisfies .
Regular oriented link diagrams: the diagram has finite crossings and arcs.
Proof
Let be the number of rows in the candidate. The shape check reads the row count and all row lengths, so it terminates after shape checks and returns that witness if the shape fails. If the shape is valid, then ; the entry-range check examines at most values, and the column-permutation checks examine at most entries. Thus shape and format validation use at most checks on a shape-valid table, and a malformed shape stops before any entry or axiom checks.
The triple loop visits exactly ordered triples and checks the right self-distributive identity of [F2]. In quandle mode the diagonal loop visits entries and checks exactly . Thus the total check bound on a shape-valid table is at most . The algorithm accepts exactly the tables satisfying the selected rack axioms, with idempotency required precisely in quandle mode.
If a column passes its permutation check, it defines a bijective right translation and its inverse column is completely determined. The assignment loop enumerates every one of the functions from the ordered arc set to the table elements once. At each crossing it tests exactly the relation from [F2], using that inverse column if required; hence an assignment is retained if and only if it is a coloring.
Every loop has a finite range, so the procedure terminates; it returns the exact failure witness at the first failed check or the complete coloring set and count when all checks pass. For the empty diagram the unique empty assignment is tested once, and for a diagram with zero crossings every one of the assignments passes.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Sam Nelson, Link invariants from finite racks, §§2.1–2.2, arXiv:0808.0029v3, pp. 2–5 (standard reference, not scraped)
- J. Scott Carter, A Survey of Quandle Ideas, §2, arXiv:1002.4429v2, pp. 3–8 (standard reference, not scraped)