Proposition

Lemma 21. Let σ satisfy the joint cap in. Outside a set of σ -probability 2^ -Ω(N) , ∑_ e∈ ( P_ 1,e ∩ P_ 2,e )≤2D. For any unit outside that exceptional set and any U_1λ_1=U_2λ_2 , both λ_i have total component rank at most 2D . Each has a …

Lemma 21. Let σ satisfy the joint cap in. Outside a set of σ -probability 2-Ω(N) , ∑e∈ ( P1,e ∩ P2,e )≤2D. For any unit outside that exceptional set and any U1λ1=U2λ2 , both λi have total component rank at most 2D . Each has a unique representation (wi,l )l vanishing at a strict majority of tags, and | l:wi,l ≠0 |≤4D/g, χ*(w1)=χ*(w2).

Prove 1Disprove 0Cited as proposition 3Chain graphAdd Your Proof

Add Your Proof1

Prove
If the summed intersection dimension exceeds 2D , choose 2D independent common-image vectors, componentwise. Write each as P_ 1,e a=P_ 2,e b . Their nominal relation directions (a,b) are independent in the direct sum of the two primal coefficient spaces at that component. Indeed a dependence between the pairs would, after applying P_ 1,e , be the corresponding dependence between the selected common-image vectors. Across components their ranks add. There are at most 2^ O(n) ways to choose this bounded number of coefficient pairs and their component indices. For each choice, bounds the probability of their zero images by 2^ -(1-ε)2DN under ^2 . After paying 2^ DN for σ , and making the coefficient count a sufficiently small fraction of N by the choice of M_0 , the union bound is 2^ -Ω(N) . Suppose U_1λ_1=U_2λ_2=ξ . The column space of ξ_e lies in both primal plus spans. Since multiplication by the two injective frame maps preserves matrix rank, (λ_ i,e )=(ξ_e) ≤( P_ 1,e ∩ P_ 2,e ). This proves the total-rank assertion. Take any representation (w_l)_l of one of the profiles. A component w_l+w_ l' is nonzero whenever w_l≠w_ l' , so there are at most 2D unequal unordered pairs. If no value occurred at a strict majority of tags, write c_v for its multiplicities. Then # unequal pairs =12(g^2-∑_vc_v^2) ≥12(g^2- g2∑_vc_v) =(g^2)/(4)>2D, a contradiction. Let the majority have size g-z . There are at least z(g-z)≥zg/2 unequal pairs, hence z≤4D/g . Its common value belongs to W_* by Lemma 15, so subtract it from every coordinate. The resulting representation vanishes at a strict majority. It is unique: two such representations differ by a constant, and their two majority zero sets intersect. Finally, equality of the component tensors gives equality of their ambient traces. By cyclicity of trace and, (P_ i,e λ_ i,e Q_ i,e ) = P_ i,e Q_ i,e λ_ i,e =η(λ_ i,e ). For e= l,l' , it follows that η(w_ 1,l )+η(w_ 2,l ) =η(w_ 1,l' )+η(w_ 2,l' ). This value is independent of the tag. The two sparse representations together have at most 8D/g=32000<g nonzero coordinates, so some tag has both entries zero. The common value is therefore zero. Summing over tags proves equality of the two specified χ_* -values.