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 𝐿+(𝑓) ≥ 𝜒+(𝑓) = 𝑘 ≥ 𝑟𝑎𝑛𝑘(𝑀𝑅 ) 𝑟