AFTD Auto-Formalizing Theoretical Domains

alon_tarsi_number_circulant_1_3

def

The Alon-Tarsi number of the circulant graph C_n(1,3), defined as the least integer k such that its graph polynomial has a non-vanishing monomial with all exponents strictly less than k.

Statement

noncomputable def alon_tarsi_number_circulant_1_3 (n : ℕ) [NeZero n] : ℕ
Defined in
arXiv:2610.41820 Section 1, p. 2
Verified
03 Nov 2026
Axioms
none listed
Built on 1
  • circulant_1_3_graph_polynomialThe graph polynomial of C_n(1,3) with orientation along jumps 1 and 3, defined as the product over i in ZMod n of (x_i - x_{i+1}) * (x_i -…

Read back from the Lean

For a natural number n with [NeZero n] (i.e., n ≠ 0), alon_tarsi_number_circulant_1_3 n is defined as the infimum in ℕ of the set of all k : ℕ such that there exists a monomial exponent d : ZMod n →₀ ℕ where the coefficient of X^d in circulant_1_3_graph_polynomial n ℂ is non-zero and d(v) < k for all v : ZMod n.

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 Alon-Tarsi number of C_n(1,3) defined via non-vanishing monomials of its graph polynomial. -/
noncomputable def alon_tarsi_number_circulant_1_3 (n : ℕ) [NeZero n] : ℕ := sInf {k : ℕ | ∃ (d : ZMod n →₀ ℕ),
    MvPolynomial.coeff d (circulant_1_3_graph_polynomial n ℂ) ≠ 0 ∧ ∀ v, d v < k}
See it in the graphDiscuss this resultChallenge it