u(R)โคโ๏ผbib4(Rb) โฅassumption of convexity ofฮผ =2-n-i0โbk(Rb)โฅeach=2-n-0 โค2-r-0bๅท2 /โฅabove Fact. =m2+0 where the last step follows from some basic manipulation of binomial coefficients. 2.Monotone formula size When we restrict the formula to be monotone,then we can get better lower bounds.How much better? Exponential.It's probably a bit too technical to write down full details,but we can sketchan approach. Recall that a rectangle Ax B is 1-monochromatic if there exists an i E [n],s.t.for all x E A and y E B,it holds that xi=1 and yi =0.A rectangle Ax B is 0-monochromatic if there existsan iE [n],s.t.for all xEA and yE B,it holds that xi=0 and yi 1.For monotone functions,the monotone leaf size L(f)is the minimal number of leaves of any monotone formula that computes f. Consider a rectangle R=Ax B f-1(1)x f-1(0).We associate with R a matrix MR.Formally, use a map R(R)=MR.Suppose that is linear,thus if R hasa decomposition R=iRi then so does Mg:Mg=iMg Consider all 1-monochromatic subrectangles R',which corresponds to a submatrix Mg,of Mg.If we can bound rank(Mg)sr for all 1-monochromatic subrectangles R',then we obtain a lower bound of L+(f): L+(f)โฅrank(MR)/r. Actually,if R=Ri wherer=+f)and each Ri is 1-monochromatic,we have Mg= โ=1MR.Thus rank(MR)โคโ1rank(MR)โคkr,thus L+ๆโฅX+0=kโฅrank(Mg๐(๐
) โค โ ๐๐ผ,๐๐(๐
๐ผ,๐ ) ๐ผ,๐ // assumption of convexity of ฮผ = 2 โ(๐โ1)โ ๐(๐
๐ผ,๐ ) ๐ผ,๐ // each ๐๐ผ,๐ = 2 โ(๐โ1) โค 2 โ(๐โ1)โ 9 8 |๐ผ|2 ๐ผ,๐ // above Fact. = 9 8 (๐ 2 + ๐). where the last step follows from some basic manipulation of binomial coefficients. โก 2. Monotone formula size When we restrict the formula to be monotone, then we can get better lower bounds. How much better? Exponential. Itโs probably a bit too technical to write down full details, but we can sketch an approach. Recall that a rectangle ๐ด × ๐ต is 1-monochromatic if there exists an ๐ โ [๐], s.t. for all ๐ฅ โ ๐ด and ๐ฆ โ ๐ต, it holds that ๐ฅ๐ = 1 and ๐ฆ๐ = 0. A rectangle ๐ด × ๐ต is 0-monochromatic if there exists an i โ [n], s.t. for all ๐ฅ โ ๐ด and ๐ฆ โ ๐ต, it holds that ๐ฅ๐ = 0 and ๐ฆ๐ = 1. For monotone functions, the monotone leaf size ๐ฟ+(๐) is the minimal number of leaves of any monotone formula that computes f. Consider a rectangle ๐
= ๐ด × ๐ต โ ๐ โ1(1) × ๐ โ1 (0). We associate with R a matrix ๐๐
. Formally, use a map ๐: ๐
โ ๐(๐
) = ๐๐
. Suppose that ๐ is linear, thus if R has a decomposition ๐
= โ๐๐
๐ then so does ๐๐
: ๐๐
= โ ๐๐
๐ ๐ . Consider all 1-monochromatic subrectangles Rโ, which corresponds to a submatrix ๐๐
โฒ of ๐๐
. If we can bound rank(๐๐
โฒ ) โค ๐ for all 1-monochromatic subrectangles Rโ, then we obtain a lower bound of ๐ฟ+(๐): ๐ฟ+(๐) โฅ ๐๐๐๐(๐๐
)/๐. Actually, if ๐
= โ ๐
๐ ๐ ๐=1 where ๐ = ๐+(๐) and each ๐
๐ is 1-monochromatic, we have ๐๐
= โ ๐๐
๐ ๐ ๐=1 . Thus ๐๐๐๐(๐๐
) โค โ ๐๐๐๐(๐๐
๐ ) ๐ ๐=1 โค ๐๐, thus ๐ฟ+(๐) โฅ ๐+(๐) = ๐ โฅ ๐๐๐๐(๐๐
) ๐