Saturated homogeneous connected layer families have length at most
ProvedHirsch.clf_saturated_quadratic_boundLet be a connected layer family of rank on symbols, , which is saturated homogeneous with respect to a fixed partition of the symbols into blocks: every layer has a single profile (number of symbols in each block) and contains a base above every subset of fewer than symbols whose profile is pointwise . Then
This subclass contains the mesh constructions of Eisenbrand--Hähnle--Razborov--Rothvoß, whose length is ; so on this subclass the exponent two is optimal up to a logarithm, and the almost-quadratic mechanism of the known lower bounds cannot be pushed further by more blocks or by incomplete saturated phases.
Proof idea. For each block and threshold , saturation makes the set of layers whose profile has -coordinate equal to the interval of layers containing a fixed -subset of the block, hence an interval. A maximal run of layers with a fixed mixed profile is paid for by a newly crossed threshold and has at most layers, because all of them must contain a fixed -subset and differ in the remaining symbol of block . Pure layers of a block are paid from one reservoir of size by the same completion count. Summing the disjoint budgets and subtracting the initial profile's credit gives .
Formalization Note IsSaturatedHomogeneous blk F is the definition in Hirsch_clf; the block set G is an arbitrary finite type.
import Mathlib import Definitions.Def_Hirsch_clf
namespace Hirsch
theorem clf_saturated_quadratic_bound
{V : Type*} [DecidableEq V] [Fintype V] {G : Type*} [DecidableEq G] [Fintype G]
(d : ℕ) (hd : 1 ≤ d) (hdV : d ≤ Fintype.card V)
(blk : V → G) (F : CLF V d) (hF : CLF.IsSaturatedHomogeneous blk F) :
F.len ≤ d * (Fintype.card V - d) := by sorry
end Hirsch