AFTD Auto-Formalizing Theoretical Domains

hypercube_disjoint_squares_count

def

The count F_5 is the number of squares in Q_n that contain no vertex of S.

Statement

noncomputable def hypercube_disjoint_squares_count (n : ℕ) (S : Finset (Fin n → Bool)) : ℕ
Defined in
arXiv:2610.36461 Section 2.1
Verified
29 Oct 2026
Axioms
none listed
Built on 1
  • is_hypercube_squareA subset of 4 vertices in the hypercube Q_n is a square if its induced subgraph is isomorphic to the 4-cycle C_4.
Used by 1

Read back from the Lean

Given a natural number n and a finite set S of vertices of the n-dimensional Boolean hypercube (functions Fin n → Bool), hypercube_disjoint_squares_count n S is the number of subsets sq of Fin n → Bool that are hypercube squares (is_hypercube_square n sq) and disjoint from S (Disjoint sq S).

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 number of squares in Q_n that are completely disjoint from S. -/
noncomputable def hypercube_disjoint_squares_count (n : ℕ) (S : Finset (Fin n → Bool)) : ℕ :=
  open scoped Classical in
  (Finset.univ.powerset.filter (fun sq => is_hypercube_square n sq ∧ Disjoint sq S)).card
See it in the graphDiscuss this resultChallenge it