AFTD Auto-Formalizing Theoretical Domains

is_rank_one_product

def

A function R on the n-dimensional Boolean cube is a nonnegative rank-one product if it factors as the product of n nonnegative one-variable functions.

Statement

def is_rank_one_product {n : ℕ} (R : (Fin n → Bool) → ℝ) : Prop
Defined in
arXiv:2611.01055, Section 2.3, Eq. (2)
Verified
03 Nov 2026
Axioms
none listed
Used by 3
  • depth_three_amc_soundnessFor any natural number n, any DNF formula A : List (List (CnfLit (Fin n))), any real shift parameter ε > 0, and any proof size r : ℕ, if A…
  • depth_three_amc_of_bounded_biasFor every natural number n, every DNF formula A : List (List (CnfLit (Fin n))), every real shift parameter ε, and every proof size s : ℕ,…
  • has_depth_three_amc_proofLet n be a natural number, A a DNF formula represented as a list of terms where each term is a list of literals of type CnfLit (Fin n), ε…

Read back from the Lean

Given a natural number n and a function R : (Fin n → Bool) → ℝ, is_rank_one_product R asserts that there exists a function g : Fin n → Bool → ℝ such that: 1. for all i : Fin n and all b : Bool, 0 ≤ g i b, and 2. for all τ : Fin n → Bool, R τ = ∏ i : Fin n, g i (τ i) (the product over all i : Fin n of g i (τ i)).

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

/-- A rank-one product function on {0, 1}^n with nonnegative factors. -/
def is_rank_one_product {n : ℕ} (R : (Fin n → Bool) → ℝ) : Prop := ∃ g : Fin n → Bool → ℝ, (∀ i b, 0 ≤ g i b) ∧ ∀ τ, R τ = ∏ i : Fin n, g i (τ i)
See it in the graphDiscuss this resultChallenge it