Uniform output-probability bias
DefinitionDetSupportRank_DeterminantSupport_Supplement_UniformBiasalgebracombinatoricsdeterminantsupportp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a function on a finite set, define
The two cardinalities are converted to real numbers before subtraction. On the source domain is the nonempty space of all entries of a multilinear input, so the denominator is positive. The extension on an empty input set is zero. This generic definition is independent of any special polynomial or rank estimate.
Definition code
import Mathlib
noncomputable section
open scoped BigOperators
namespace DetSupportRank.DeterminantSupport.Supplement
/-- Uniform probability of output zero minus that of output one, §1, p.2.
The subtraction is in ℝ, before normalization; no truncated cardinal subtraction. -/
def uniformBias {A F : Type*} [Fintype A] [Zero F] [One F] (T : A → F) : ℝ := by
classical
exact (((Finset.univ.filter (fun x => T x = 0)).card : ℝ) -
((Finset.univ.filter (fun x => T x = 1)).card : ℝ)) / (Fintype.card A : ℝ)
end DetSupportRank.DeterminantSupport.Supplement
Source
Neil Krishnan, Guy Moshkovitz, Optimal partition rank bounds for the determinant and other multilinear polynomials, STOC 2027 submission #631 (October 2026), §1, definition of bias, p. 2 (PDF p. 2); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/631.pdf