AFTD Auto-Formalizing Theoretical Domains

sparse_graph_state_fisher_core_k

deforiginal

For integers d >= 2 and c >= 0, k(d, c) is the least positive integer k such that floor(k^2 / 4) >= d*k + c.

Statement

def sparse_graph_state_fisher_core_k (d c : ℕ) : ℕ
Related work
arXiv:2611.08593
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • core_constant_bFor natural numbers d and c, let k = sparse_graph_state_fisher_core_k d c. The core constant B(d, c) is the supremum of Q(J) - 1 over all…

Read back from the Lean

Given two natural numbers $d$ and $c$, sparse_graph_state_fisher_core_k d c is defined as the least natural number $k$ such that $0 < k$ and $d \cdot k + c \le \lfloor k^2 / 4 \rfloor$ (where division is natural number/floor division).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The core size k(d, c), defined as the least positive integer k such that floor(k^2 / 4) >= d*k + c. -/
def sparse_graph_state_fisher_core_k (d c : ℕ) : ℕ :=
  Nat.find (by
    have h : ∃ k : ℕ, 0 < k ∧ d * k + c ≤ k ^ 2 / 4 := by
      use 4 * (d + c + 1)
      have h1 : 0 < 4 * (d + c + 1) := by omega
      refine ⟨h1, ?_⟩
      have h2 : (4 * (d + c + 1)) ^ 2 / 4 = 4 * (d + c + 1) ^ 2 := by
        have : (4 * (d + c + 1)) ^ 2 = 4 * (4 * (d + c + 1) ^ 2) := by ring
        rw [this, Nat.mul_div_cancel_left _ (by omega)]
      rw [h2]
      nlinarith
    exact h)
See it in the graphDiscuss this resultChallenge it