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 ˙ = a 1 0 1 , b 1 0 1 if b = 0 a b
signsv.w W = Base ndx 1 0 1 + ndx ˙
signsv.t T = f Word n 0 ..^ f W i = 0 n sgn f i
signsv.v V = f Word j 1 ..^ f if T f j T f j 1 1 0
Assertion signsvfn F Word F 0 0 K V F ++ ⟨“ K ”⟩ = V F + if T F F 1 K < 0 1 0

Proof

Step Hyp Ref Expression
1 signsv.p ˙ = a 1 0 1 , b 1 0 1 if b = 0 a b
2 signsv.w W = Base ndx 1 0 1 + ndx ˙
3 signsv.t T = f Word n 0 ..^ f W i = 0 n sgn f i
4 signsv.v V = f Word j 1 ..^ f if T f j T f j 1 1 0
5 eldifi F Word F Word
6 s1cl K ⟨“ K ”⟩ Word
7 ccatcl F Word ⟨“ K ”⟩ Word F ++ ⟨“ K ”⟩ Word
8 5 6 7 syl2an F Word K F ++ ⟨“ K ”⟩ Word
9 1 2 3 4 signsvvfval F ++ ⟨“ K ”⟩ Word V F ++ ⟨“ K ”⟩ = j 1 ..^ F ++ ⟨“ K ”⟩ if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0
10 8 9 syl F Word K V F ++ ⟨“ K ”⟩ = j 1 ..^ F ++ ⟨“ K ”⟩ if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0
11 ccatlen F Word ⟨“ K ”⟩ Word F ++ ⟨“ K ”⟩ = F + ⟨“ K ”⟩
12 5 6 11 syl2an F Word K F ++ ⟨“ K ”⟩ = F + ⟨“ K ”⟩
13 s1len ⟨“ K ”⟩ = 1
14 13 oveq2i F + ⟨“ K ”⟩ = F + 1
15 12 14 eqtrdi F Word K F ++ ⟨“ K ”⟩ = F + 1
16 15 oveq2d F Word K 1 ..^ F ++ ⟨“ K ”⟩ = 1 ..^ F + 1
17 16 sumeq1d F Word K j 1 ..^ F ++ ⟨“ K ”⟩ if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = j 1 ..^ F + 1 if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0
18 eldifsn F Word F Word F
19 lennncl F Word F F
20 18 19 sylbi F Word F
21 nnuz = 1
22 20 21 eleqtrdi F Word F 1
23 22 adantr F Word K F 1
24 1cnd F Word K j 1 F T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1
25 0cnd F Word K j 1 F ¬ T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 0
26 24 25 ifclda F Word K j 1 F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0
27 fveq2 j = F T F ++ ⟨“ K ”⟩ j = T F ++ ⟨“ K ”⟩ F
28 fvoveq1 j = F T F ++ ⟨“ K ”⟩ j 1 = T F ++ ⟨“ K ”⟩ F 1
29 27 28 neeq12d j = F T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1
30 29 ifbid j = F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0
31 23 26 30 fzosump1 F Word K j 1 ..^ F + 1 if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 + if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0
32 10 17 31 3eqtrd F Word K V F ++ ⟨“ K ”⟩ = j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 + if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0
33 32 adantlr F Word F 0 0 K V F ++ ⟨“ K ”⟩ = j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 + if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0
34 simpl F Word K F Word
35 34 eldifad F Word K F Word
36 35 adantr F Word K j 1 ..^ F F Word
37 simplr F Word K j 1 ..^ F K
38 fzo0ss1 1 ..^ F 0 ..^ F
39 38 a1i F Word K 1 ..^ F 0 ..^ F
40 39 sselda F Word K j 1 ..^ F j 0 ..^ F
41 1 2 3 4 signstfvp F Word K j 0 ..^ F T F ++ ⟨“ K ”⟩ j = T F j
42 36 37 40 41 syl3anc F Word K j 1 ..^ F T F ++ ⟨“ K ”⟩ j = T F j
43 elfzoel2 j 1 ..^ F F
44 43 adantl F Word K j 1 ..^ F F
45 1nn0 1 0
46 eluzmn F 1 0 F F 1
47 44 45 46 sylancl F Word K j 1 ..^ F F F 1
48 fzoss2 F F 1 0 ..^ F 1 0 ..^ F
49 47 48 syl F Word K j 1 ..^ F 0 ..^ F 1 0 ..^ F
50 elfzo1elm1fzo0 j 1 ..^ F j 1 0 ..^ F 1
51 50 adantl F Word K j 1 ..^ F j 1 0 ..^ F 1
52 49 51 sseldd F Word K j 1 ..^ F j 1 0 ..^ F
53 1 2 3 4 signstfvp F Word K j 1 0 ..^ F T F ++ ⟨“ K ”⟩ j 1 = T F j 1
54 36 37 52 53 syl3anc F Word K j 1 ..^ F T F ++ ⟨“ K ”⟩ j 1 = T F j 1
55 42 54 neeq12d F Word K j 1 ..^ F T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 T F j T F j 1
56 55 ifbid F Word K j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = if T F j T F j 1 1 0
57 56 sumeq2dv F Word K j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = j 1 ..^ F if T F j T F j 1 1 0
58 1 2 3 4 signsvvfval F Word V F = j 1 ..^ F if T F j T F j 1 1 0
59 35 58 syl F Word K V F = j 1 ..^ F if T F j T F j 1 1 0
60 57 59 eqtr4d F Word K j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = V F
61 60 adantlr F Word F 0 0 K j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 = V F
62 1 2 3 4 signstfvn F Word K T F ++ ⟨“ K ”⟩ F = T F F 1 ˙ sgn K
63 62 adantlr F Word F 0 0 K T F ++ ⟨“ K ”⟩ F = T F F 1 ˙ sgn K
64 35 adantlr F Word F 0 0 K F Word
65 simpr F Word F 0 0 K K
66 fzo0end F F 1 0 ..^ F
67 20 66 syl F Word F 1 0 ..^ F
68 67 ad2antrr F Word F 0 0 K F 1 0 ..^ F
69 1 2 3 4 signstfvp F Word K F 1 0 ..^ F T F ++ ⟨“ K ”⟩ F 1 = T F F 1
70 64 65 68 69 syl3anc F Word F 0 0 K T F ++ ⟨“ K ”⟩ F 1 = T F F 1
71 63 70 neeq12d F Word F 0 0 K T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 T F F 1 ˙ sgn K T F F 1
72 1 2 3 4 signstfvcl F Word F 0 0 F 1 0 ..^ F T F F 1 1 1
73 68 72 syldan F Word F 0 0 K T F F 1 1 1
74 rexr K K *
75 sgncl K * sgn K 1 0 1
76 74 75 syl K sgn K 1 0 1
77 76 adantl F Word F 0 0 K sgn K 1 0 1
78 1 2 signswch T F F 1 1 1 sgn K 1 0 1 T F F 1 ˙ sgn K T F F 1 T F F 1 sgn K < 0
79 73 77 78 syl2anc F Word F 0 0 K T F F 1 ˙ sgn K T F F 1 T F F 1 sgn K < 0
80 65 rexrd F Word F 0 0 K K *
81 sgnsgn K * sgn sgn K = sgn K
82 80 81 syl F Word F 0 0 K sgn sgn K = sgn K
83 82 oveq2d F Word F 0 0 K sgn T F F 1 sgn sgn K = sgn T F F 1 sgn K
84 83 breq1d F Word F 0 0 K sgn T F F 1 sgn sgn K < 0 sgn T F F 1 sgn K < 0
85 neg1rr 1
86 1re 1
87 prssi 1 1 1 1
88 85 86 87 mp2an 1 1
89 88 73 sselid F Word F 0 0 K T F F 1
90 sgnclre K sgn K
91 90 adantl F Word F 0 0 K sgn K
92 sgnmulsgn T F F 1 sgn K T F F 1 sgn K < 0 sgn T F F 1 sgn sgn K < 0
93 89 91 92 syl2anc F Word F 0 0 K T F F 1 sgn K < 0 sgn T F F 1 sgn sgn K < 0
94 sgnmulsgn T F F 1 K T F F 1 K < 0 sgn T F F 1 sgn K < 0
95 89 94 sylancom F Word F 0 0 K T F F 1 K < 0 sgn T F F 1 sgn K < 0
96 84 93 95 3bitr4d F Word F 0 0 K T F F 1 sgn K < 0 T F F 1 K < 0
97 71 79 96 3bitrd F Word F 0 0 K T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 T F F 1 K < 0
98 97 ifbid F Word F 0 0 K if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0 = if T F F 1 K < 0 1 0
99 61 98 oveq12d F Word F 0 0 K j 1 ..^ F if T F ++ ⟨“ K ”⟩ j T F ++ ⟨“ K ”⟩ j 1 1 0 + if T F ++ ⟨“ K ”⟩ F T F ++ ⟨“ K ”⟩ F 1 1 0 = V F + if T F F 1 K < 0 1 0
100 33 99 eqtrd F Word F 0 0 K V F ++ ⟨“ K ”⟩ = V F + if T F F 1 K < 0 1 0