Metamath Proof Explorer


Theorem signsvfn

Description: Number of changes in a word compared to a shorter word. (Contributed by Thierry Arnoux, 12-Oct-2018)

Ref Expression
Hypotheses signsv.p ˙=a101,b101ifb=0ab
signsv.w W=Basendx101+ndx˙
signsv.t T=fWordn0..^fWi=0nsgnfi
signsv.v V=fWordj1..^fifTfjTfj110
Assertion signsvfn FWordF00KVF++⟨“K”⟩=VF+ifTFF1K<010

Proof

Step Hyp Ref Expression
1 signsv.p ˙=a101,b101ifb=0ab
2 signsv.w W=Basendx101+ndx˙
3 signsv.t T=fWordn0..^fWi=0nsgnfi
4 signsv.v V=fWordj1..^fifTfjTfj110
5 eldifi FWordFWord
6 s1cl K⟨“K”⟩Word
7 ccatcl FWord⟨“K”⟩WordF++⟨“K”⟩Word
8 5 6 7 syl2an FWordKF++⟨“K”⟩Word
9 1 2 3 4 signsvvfval F++⟨“K”⟩WordVF++⟨“K”⟩=j1..^F++⟨“K”⟩ifTF++⟨“K”⟩jTF++⟨“K”⟩j110
10 8 9 syl FWordKVF++⟨“K”⟩=j1..^F++⟨“K”⟩ifTF++⟨“K”⟩jTF++⟨“K”⟩j110
11 ccatlen FWord⟨“K”⟩WordF++⟨“K”⟩=F+⟨“K”⟩
12 5 6 11 syl2an FWordKF++⟨“K”⟩=F+⟨“K”⟩
13 s1len ⟨“K”⟩=1
14 13 oveq2i F+⟨“K”⟩=F+1
15 12 14 eqtrdi FWordKF++⟨“K”⟩=F+1
16 15 oveq2d FWordK1..^F++⟨“K”⟩=1..^F+1
17 16 sumeq1d FWordKj1..^F++⟨“K”⟩ifTF++⟨“K”⟩jTF++⟨“K”⟩j110=j1..^F+1ifTF++⟨“K”⟩jTF++⟨“K”⟩j110
18 eldifsn FWordFWordF
19 lennncl FWordFF
20 18 19 sylbi FWordF
21 nnuz =1
22 20 21 eleqtrdi FWordF1
23 22 adantr FWordKF1
24 1cnd FWordKj1FTF++⟨“K”⟩jTF++⟨“K”⟩j11
25 0cnd FWordKj1F¬TF++⟨“K”⟩jTF++⟨“K”⟩j10
26 24 25 ifclda FWordKj1FifTF++⟨“K”⟩jTF++⟨“K”⟩j110
27 fveq2 j=FTF++⟨“K”⟩j=TF++⟨“K”⟩F
28 fvoveq1 j=FTF++⟨“K”⟩j1=TF++⟨“K”⟩F1
29 27 28 neeq12d j=FTF++⟨“K”⟩jTF++⟨“K”⟩j1TF++⟨“K”⟩FTF++⟨“K”⟩F1
30 29 ifbid j=FifTF++⟨“K”⟩jTF++⟨“K”⟩j110=ifTF++⟨“K”⟩FTF++⟨“K”⟩F110
31 23 26 30 fzosump1 FWordKj1..^F+1ifTF++⟨“K”⟩jTF++⟨“K”⟩j110=j1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110+ifTF++⟨“K”⟩FTF++⟨“K”⟩F110
32 10 17 31 3eqtrd FWordKVF++⟨“K”⟩=j1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110+ifTF++⟨“K”⟩FTF++⟨“K”⟩F110
33 32 adantlr FWordF00KVF++⟨“K”⟩=j1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110+ifTF++⟨“K”⟩FTF++⟨“K”⟩F110
34 simpl FWordKFWord
35 34 eldifad FWordKFWord
36 35 adantr FWordKj1..^FFWord
37 simplr FWordKj1..^FK
38 fzo0ss1 1..^F0..^F
39 38 a1i FWordK1..^F0..^F
40 39 sselda FWordKj1..^Fj0..^F
41 1 2 3 4 signstfvp FWordKj0..^FTF++⟨“K”⟩j=TFj
42 36 37 40 41 syl3anc FWordKj1..^FTF++⟨“K”⟩j=TFj
43 elfzoel2 j1..^FF
44 43 adantl FWordKj1..^FF
45 1nn0 10
46 eluzmn F10FF1
47 44 45 46 sylancl FWordKj1..^FFF1
48 fzoss2 FF10..^F10..^F
49 47 48 syl FWordKj1..^F0..^F10..^F
50 elfzo1elm1fzo0 j1..^Fj10..^F1
51 50 adantl FWordKj1..^Fj10..^F1
52 49 51 sseldd FWordKj1..^Fj10..^F
53 1 2 3 4 signstfvp FWordKj10..^FTF++⟨“K”⟩j1=TFj1
54 36 37 52 53 syl3anc FWordKj1..^FTF++⟨“K”⟩j1=TFj1
55 42 54 neeq12d FWordKj1..^FTF++⟨“K”⟩jTF++⟨“K”⟩j1TFjTFj1
56 55 ifbid FWordKj1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110=ifTFjTFj110
57 56 sumeq2dv FWordKj1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110=j1..^FifTFjTFj110
58 1 2 3 4 signsvvfval FWordVF=j1..^FifTFjTFj110
59 35 58 syl FWordKVF=j1..^FifTFjTFj110
60 57 59 eqtr4d FWordKj1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110=VF
61 60 adantlr FWordF00Kj1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110=VF
62 1 2 3 4 signstfvn FWordKTF++⟨“K”⟩F=TFF1˙sgnK
63 62 adantlr FWordF00KTF++⟨“K”⟩F=TFF1˙sgnK
64 35 adantlr FWordF00KFWord
65 simpr FWordF00KK
66 fzo0end FF10..^F
67 20 66 syl FWordF10..^F
68 67 ad2antrr FWordF00KF10..^F
69 1 2 3 4 signstfvp FWordKF10..^FTF++⟨“K”⟩F1=TFF1
70 64 65 68 69 syl3anc FWordF00KTF++⟨“K”⟩F1=TFF1
71 63 70 neeq12d FWordF00KTF++⟨“K”⟩FTF++⟨“K”⟩F1TFF1˙sgnKTFF1
72 1 2 3 4 signstfvcl FWordF00F10..^FTFF111
73 68 72 syldan FWordF00KTFF111
74 rexr KK*
75 sgncl K*sgnK101
76 74 75 syl KsgnK101
77 76 adantl FWordF00KsgnK101
78 1 2 signswch TFF111sgnK101TFF1˙sgnKTFF1TFF1sgnK<0
79 73 77 78 syl2anc FWordF00KTFF1˙sgnKTFF1TFF1sgnK<0
80 65 rexrd FWordF00KK*
81 sgnsgn K*sgnsgnK=sgnK
82 80 81 syl FWordF00KsgnsgnK=sgnK
83 82 oveq2d FWordF00KsgnTFF1sgnsgnK=sgnTFF1sgnK
84 83 breq1d FWordF00KsgnTFF1sgnsgnK<0sgnTFF1sgnK<0
85 neg1rr 1
86 1re 1
87 prssi 1111
88 85 86 87 mp2an 11
89 88 73 sselid FWordF00KTFF1
90 sgnclre KsgnK
91 90 adantl FWordF00KsgnK
92 sgnmulsgn TFF1sgnKTFF1sgnK<0sgnTFF1sgnsgnK<0
93 89 91 92 syl2anc FWordF00KTFF1sgnK<0sgnTFF1sgnsgnK<0
94 sgnmulsgn TFF1KTFF1K<0sgnTFF1sgnK<0
95 89 94 sylancom FWordF00KTFF1K<0sgnTFF1sgnK<0
96 84 93 95 3bitr4d FWordF00KTFF1sgnK<0TFF1K<0
97 71 79 96 3bitrd FWordF00KTF++⟨“K”⟩FTF++⟨“K”⟩F1TFF1K<0
98 97 ifbid FWordF00KifTF++⟨“K”⟩FTF++⟨“K”⟩F110=ifTFF1K<010
99 61 98 oveq12d FWordF00Kj1..^FifTF++⟨“K”⟩jTF++⟨“K”⟩j110+ifTF++⟨“K”⟩FTF++⟨“K”⟩F110=VF+ifTFF1K<010
100 33 99 eqtrd FWordF00KVF++⟨“K”⟩=VF+ifTFF1K<010