Lecture 6.Formula complexity Il 1.From Khrapchenko's bound to convex rectangle measures In the last lecture,we proved a result by Khrapchenko for any Af-1(1),B f-1(0),define S= cyW:x∈Ay∈B,lx⊕y=}and we have L()≥g-The astrcodredthe that A=f-1(1)and B=f-1(0),but convince yourself that the lower bound holds even A and B are subsets of f-1(1)and f-1(0).)We then used it to prove that L(Parityn)2n2.We of course hope to prove stronger lower bounds.So a natural question is:Can we use the same technique to prove better lower bounds?In general,understanding the power and limit ofa prevailing lower bound technique is an important task.For Khrapchenko's method,unfortunately,the answer is pretty negative:n2 is the best lower bound we can get. Exereise.Showthat for.ndas defined above,itaays holdsth IAl-BI S nz So it's a bad news.But maybe we can use a similar technique?Well,that depends on the exact definition of"similar".In this lecture,we'll investigate the power of this type of technique along one specific direction. Next we will 1.define a concept ofconvex rectangle measures 2.show that Kharpchenko's bound uses a convex rectangle measure, 3.show that all convex rectangle measures cannot give lower bounds better than 0(n2). Fix a rectangle R.Consider a function u on subrectangles ofR.(As the name suggests,a set is a subrectangle of R if it's a subset of R and it's a rectangle.)The function is a rectangle measure if it satisfies subadditive:u(R)<u(R)+u(R2),where R is partitioned into the disjoint union of R and R2,which are both rectangles themselves, ● normalized:u(R')<1 for any monochromatic subrectangle R'.Lecture 6. Formula complexity II 1. From Khrapchenko’s bound to convex rectangle measures In the last lecture, we proved a result by Khrapchenko for any 𝐴 ⊆ 𝑓 −1 (1), 𝐵 ⊆ 𝑓 −1 (0), define 𝑆 = {(𝑥,𝑦): 𝑥 ∈ 𝐴, 𝑦 ∈ 𝐵,|𝑥 ⊕ 𝑦| = 1} and we have 𝐿(𝑓) ≥ |𝑆| 2 |𝐴|⋅|𝐵| . (The last lecture considered the case that 𝐴 = 𝑓 −1 (1) and 𝐵 = 𝑓 −1(0), but convince yourself that the lower bound holds even A and B are subsets of 𝑓 −1 (1) and 𝑓 −1 (0).) We then used it to prove that 𝐿(Parity𝑛 ) ≥ 𝑛 2 . We of course hope to prove strongerlower bounds. So a natural question is: Can we use the same technique to prove better lower bounds? In general, understanding the power and limit of a prevailing lower bound technique is an important task. For Khrapchenko’s method, unfortunately, the answer is pretty negative: n 2 is the best lower bound we can get. Exercise. Show that for A, B and S as defined above, it always holds that |𝑆| 2 |𝐴|⋅|𝐵| ≤ 𝑛 2 . So it’s a bad news. But maybe we can use a similar technique? Well, that depends on the exact definition of “similar”. In this lecture, we’ll investigate the power of this type of technique along one specific direction. Next we will 1. define a concept of convex rectangle measures, 2. show that Kharpchenko’s bound uses a convex rectangle measure, 3. show that all convex rectangle measures cannot give lower bounds better than 𝑂(𝑛 2 ). Fix a rectangle R. Consider a function 𝜇 on subrectangles of R. (As the name suggests, a set is a subrectangle of R if it’s a subset of R and it’s a rectangle.) The function is a rectangle measure if it satisfies ⚫ subadditive: 𝜇(𝑅) ≤ 𝜇(𝑅1 ) + 𝜇(𝑅2), where R is partitioned into the disjoint union of 𝑅1 and 𝑅2, which are both rectangles themselves, ⚫ normalized: 𝜇(𝑅′) ≤ 1 for any monochromatic subrectangle R’