One can view Khrapchenko's bound in the following way.Pick any rectangle R =A x B S (1).nboundof (Hereweused tdenotethes namely Al.|BI,the number ofentries in R.)Actually,from the proof of the theorem,we can see that what was actually showed is the following generalized fact: Theorem 1.1.For any rectangle R f-1(1)x f-1(0)and any rectangle measure u on R,we have L(f)≥(R) Now let's define convexity.Suppose R1,...,Rk are subrectangles ofR,and n,...,Tk are real numbers in [0,1]called weights.The set {Ri r:iE [k]}forms a fractional partition ofR if for any element eR.e=1.Namely,each rectangle covers a fraction ofeachentry,and the collection of these covers exactly equals to R.We will use the notation R =irRi.A rectangle measure u on R is convex if k u(R)≤ ）n(Ri) (Note that it may be a bit misleading that the name of"convexity"suggest that i=1,but actually from∑inRil=RI we know that∑in≥1 in general..) Now we proceed to the second step showing that Khrapchenko's bound is a convex rectangle measure. Khrapchenko's bound,when used on a fixed rectangle R,actually corresponds to the rectangle measure RNow we prove that the function isaonvxect casure In the proof R of the original theorem in last lecture,we already see that u is a rectangle measure.(Review the proof if this is not clear to you.)Let's prove the convexity.Suppose that {Rin:iE [k]}formsa fractional partition of R.Put Si=Sn Ri Since R =irRi,we have RI=in|Ril.And by considering eachentry,we canalso see that IS=irlSil.Therefore,we have ls2_②nlSl)2 where the inequality is by Cauchy-Schwartz Inequality. Finally,we show the most important result ofthis section:Convex rectangle measures cannot produce lower bounds better than quadratic.It was firstly proven in [KKN95]that convex rectangle measuresOne can view Khrapchenko’s bound in the following way. Pick any rectangle 𝑅 = 𝐴 × 𝐵 ⊆ 𝑓 −1(1) × 𝑓 −1 (0), and one gets a lower bound of |𝑆| 2 |𝑅| . (Here we used |𝑅| to denote the size of R, namely |𝐴|⋅ |𝐵|, the number of entries in R.) Actually, from the proof of the theorem, we can see that what was actually showed is the following generalized fact: Theorem 1.1. For any rectangle 𝑅 ⊆ 𝑓 −1(1) × 𝑓 −1(0) and any rectangle measure 𝜇 on R, we have 𝐿(𝑓) ≥ 𝜇(𝑅). Now let’s define convexity. Suppose 𝑅1,…, 𝑅𝑘 are subrectangles of R, and 𝑟1 ,… , 𝑟𝑘 are real numbers in [0,1] called weights. The set {𝑅𝑖, 𝑟𝑖 :𝑖 ∈ [𝑘]} forms a fractional partition of R if for any element 𝑒 ∈ 𝑅, ∑𝑖:𝑒∈𝑅 𝑟𝑖 𝑖 = 1. Namely, each rectangle covers a fraction of each entry, and the collection of these covers exactly equals to R. We will use the notation 𝑅 = ∑𝑖 𝑟𝑖𝑅𝑖 . A rectangle measure 𝜇 on R is convex if 𝜇(𝑅) ≤ ∑𝑟𝑖𝜇(𝑅𝑖 ) k i=1 (Note that it may be a bit misleading that the name of “convexity” suggest that ∑𝑖 𝑟𝑖 = 1, but actually from ∑𝑖 𝑟𝑖 |𝑅𝑖 | = |𝑅| we know that ∑𝑖 𝑟𝑖 ≥ 1 in general.) Now we proceed to the second step showing that Khrapchenko’s bound is a convex rectangle measure. Khrapchenko’s bound, when used on a fixed rectangle R, actually corresponds to the rectangle measure 𝜇(𝑅′) = |𝑆∩𝑅 ′ | 2 |𝑅| . Now we prove that the function is a convex rectangle measure. In the proof of the original theorem in last lecture, we already see that 𝜇 is a rectangle measure. (Review the proof if this is not clear to you.) Let’s prove the convexity. Suppose that {𝑅𝑖,𝑟𝑖 :𝑖 ∈ [𝑘]} forms a fractional partition of R. Put 𝑆𝑖 = 𝑆 ∩ 𝑅𝑖 . Since 𝑅 = ∑𝑖𝑟𝑖𝑅𝑖 , we have |𝑅| = ∑ 𝑟𝑖 |𝑅𝑖 | 𝑖 . And by considering each entry, we can also see that |𝑆| = ∑ 𝑟𝑖 |𝑆𝑖 | 𝑖 . Therefore, we have 𝜇(𝑅) = |𝑆|2 |𝑅| = (∑ 𝑟𝑖 |𝑆𝑖 | i ) 2 ∑ 𝑟𝑖 |𝑅𝑖 | i ≤ ∑𝑟𝑖 |𝑆𝑖 |2 |𝑅𝑖 | i = ∑𝑟𝑖𝜇(𝑅𝑖 ) i , where the inequality is by Cauchy-Schwartz Inequality. Finally, we show the most important result of this section: Convex rectangle measures cannot produce lower bounds better than quadratic. It was firstly proven in [KKN95] that convex rectangle measures