=2(PrIT>P-TnSI>pk/2IIT>k]+Pr[ITI≤k]Pr[lT nSl>pk/2IITI≤k]） 22 Pr[ITI k]Pr[lT n Sl pk/2 I ITI>k] >2Pr[ITI>k](1/2) Pr[IT n Sl pk/2I ITI>k]>1/2 by Chernoff Pr[ITI>k] =LHS 0 Lemma2.4 Suppose that Sn]with S=1.By r ES we mean to draw r from (0.1s uniformly at random. 1.For any fired ts,f(t)2=Eresf(ts)2 2.∑(t2=E,es∑sf(ts)]≤Pr,edeg(fr)>I. Proof 1. ∑foP=∑(Eesk.ts)its）°=∑(E.cslx.sxts)is)ts =Eres[(∑七(s)x.(ts)f元ts)fts) -E.esj-(ts)j(ts)-Eres[j-(ts)] 2.By the above result, ∑ft2=∑E,eslf-(ts)]=Ees∑ftsP] t:Its >l ts:ts ts:ts> For the second part:For a function f,denote by W>t the sum of Fourier coefficients f(s)with s>l.that E,es[∑ts月] ts:ts> =Pr[deg(f)IEW>(f)I deg(f)+Pr[deg(f)>E[w(f)I deg(f)> =Pr[deg(f)>IE[W>(f)I deg(f)> ≤Pr[deg(fn)>I where the second step is because EW(f)deg(f)<1]=0 by definition of deg.= 2 (Pr T [|𝑇| > 𝑘] Pr S [|𝑇 ∩ 𝑆| > 𝑝𝑘/2| |𝑇| > 𝑘] + Pr 𝑇 [|𝑇| ≤ 𝑘] Pr 𝑆 [|𝑇 ∩ 𝑆| > 𝑝𝑘/2| |𝑇| ≤ 𝑘]) ≥ 2 Pr T [|𝑇| > 𝑘] Pr 𝑆 [|𝑇 ∩ 𝑆| > 𝑝𝑘/2 | |𝑇| > 𝑘] > 2 Pr 𝑇 [|𝑇| > 𝑘] (1/2) ( Pr 𝑆 [|𝑇 ∩ 𝑆| > 𝑝𝑘/2 | |𝑇| > 𝑘] > 1/2 by Chernoff ) = Pr 𝑇 [|𝑇| > 𝑘] = LHS □