Message
par nael » 28 avr. 2010 21:16
Alors la par contre, j'avais pas trouvé un truc simple.
Donc pour commencer j'ai montré que le poids d'un $ B_i $ est plus grand que tous ceux des $ C_k $ qui apparaissent dans sa decomposition dans la base $ C $.
C'est (encore) une recurrence, en gros, si $ B_i = \sum_j C_{k_j} $, alors $ ( B_i | S_{k_p}) \ket = \sum_{j \geq p} ( C_{k_j} | S_{k_p}) \ket $.
Donc, soit $ (B_i | S_{k_p}) = 1 $ et donc $ w(B_i) \geq w(C_{k_p}) $ car l'algorithme prends un cycle minimal etc.
Soit, ca fait zero, donc un des termes d'après, mettons $ (C_{k_q} | S_{k_q}) $ fait un, donc, $ w(C_{k_q}) \geq w(C_{k_p}) $ et d'après l'hypothèse de recurrence, $ w(B_i) \geq w(C_{k_q}) $.
Après il faut plus ou moins mettre les $ B_i $ et les $ C_i $ ensembles. Quitte a réordonner, on prends les $ C_i $ dans l'ordre de poids décroissant.
On va construire iterativement une extraction $ (B_{k_j})_j $ de $ B $ telle que $ w(B_{k_j}) \geq w(C_j) $.
Si on a construit $ B_{k_1}\dots B_{k_p} $ (p pouvant etre nul pour l'initialisation).
Si un des $ (C_j)_{j \leq p} $, disons $ C_r $ apparait encore dans la décomposition d'un des $ (B_j)_j $ pas encore utilisé, disons $ B_q $, c'est fini, car en posant $ k_{p+1} = q $, on a bien $ w(B_{k_{p+1}}) \geq w(C_r) \geq w(C_{p+1}) $ car les $ C $ sont en ordre décroissant de poids et $ r < p+1 $.
Sinon, il faut montrer que $ C_{p+1} $ apparait forcemment dans une des décompositions des $ (B_j) $ restants. Si ce n'etait pas le cas, on engendrerait une famille de rang $ N - p $ (les $ B $ restants) avec une famille de rang $ N - (p+1) $ (les $ (C_j)_{j > p+1} $), c'est impossible.
Donc on peut continuer l'éxtraction jusqu'a avoir placé tous les $ (B_j) $.
Ensuite plus qu'a sommer les inégalitées pour recuperer $ w(B) \geq w(C) $
Ouf... C'est un peu lourd a rédiger proprement, et je suis interessé si quelqun à plus simple.
)