Metamath Proof Explorer


Theorem bposlem9

Description: Lemma for bpos . Derive a contradiction. (Contributed by Mario Carneiro, 14-Mar-2014) (Proof shortened by AV, 15-Sep-2021)

Ref Expression
Hypotheses bposlem7.1 F=n2Gn+94Gn2+log22n
bposlem7.2 G=x+logxx
bposlem9.3 φN
bposlem9.4 φ64<N
bposlem9.5 φ¬pN<pp2 N
Assertion bposlem9 φψ

Proof

Step Hyp Ref Expression
1 bposlem7.1 F=n2Gn+94Gn2+log22n
2 bposlem7.2 G=x+logxx
3 bposlem9.3 φN
4 bposlem9.4 φ64<N
5 bposlem9.5 φ¬pN<pp2 N
6 6nn0 60
7 4nn 4
8 6 7 decnncl 64
9 8 a1i φ64
10 ere e
11 8re 8
12 egt2lt3 2<ee<3
13 12 simpri e<3
14 3lt8 3<8
15 3re 3
16 10 15 11 lttri e<33<8e<8
17 13 14 16 mp2an e<8
18 10 11 17 ltleii e8
19 0re 0
20 epos 0<e
21 19 10 20 ltleii 0e
22 8pos 0<8
23 19 11 22 ltleii 08
24 le2sq e0e808e8e282
25 10 21 11 23 24 mp4an e8e282
26 18 25 mpbi e282
27 11 recni 8
28 27 sqvali 82=88
29 8t8e64 88=64
30 28 29 eqtri 82=64
31 26 30 breqtri e264
32 31 a1i φe264
33 10 resqcli e2
34 33 a1i φe2
35 8 nnrei 64
36 35 a1i φ64
37 3 nnred φN
38 ltle 64N64<N64N
39 35 37 38 sylancr φ64<N64N
40 4 39 mpd φ64N
41 34 36 37 32 40 letrd φe2N
42 1 2 9 3 32 41 bposlem7 φ64<NFN<F64
43 4 42 mpd φFN<F64
44 1 2 bposlem8 F64F64<log2
45 44 a1i φF64F64<log2
46 45 simpld φF64
47 2fveq3 n=NGn=GN
48 47 oveq2d n=N2Gn=2GN
49 fvoveq1 n=NGn2=GN2
50 49 oveq2d n=N94Gn2=94GN2
51 48 50 oveq12d n=N2Gn+94Gn2=2GN+94GN2
52 oveq2 n=N2n=2 N
53 52 fveq2d n=N2n=2 N
54 53 oveq2d n=Nlog22n=log22 N
55 51 54 oveq12d n=N2Gn+94Gn2+log22n=2GN+94GN2+log22 N
56 ovex 2GN+94GN2+log22 NV
57 55 1 56 fvmpt NFN=2GN+94GN2+log22 N
58 3 57 syl φFN=2GN+94GN2+log22 N
59 sqrt2re 2
60 3 nnrpd φN+
61 60 rpsqrtcld φN+
62 fveq2 x=Nlogx=logN
63 id x=Nx=N
64 62 63 oveq12d x=Nlogxx=logNN
65 ovex logNNV
66 64 2 65 fvmpt N+GN=logNN
67 61 66 syl φGN=logNN
68 61 relogcld φlogN
69 68 61 rerpdivcld φlogNN
70 67 69 eqeltrd φGN
71 remulcl 2GN2GN
72 59 70 71 sylancr φ2GN
73 9re 9
74 4re 4
75 4ne0 40
76 73 74 75 redivcli 94
77 60 rphalfcld φN2+
78 fveq2 x=N2logx=logN2
79 id x=N2x=N2
80 78 79 oveq12d x=N2logxx=logN2N2
81 ovex logN2N2V
82 80 2 81 fvmpt N2+GN2=logN2N2
83 77 82 syl φGN2=logN2N2
84 77 relogcld φlogN2
85 84 77 rerpdivcld φlogN2N2
86 83 85 eqeltrd φGN2
87 remulcl 94GN294GN2
88 76 86 87 sylancr φ94GN2
89 72 88 readdcld φ2GN+94GN2
90 2rp 2+
91 relogcl 2+log2
92 90 91 ax-mp log2
93 rpmulcl 2+N+2 N+
94 90 60 93 sylancr φ2 N+
95 94 rpsqrtcld φ2 N+
96 rerpdivcl log22 N+log22 N
97 92 95 96 sylancr φlog22 N
98 89 97 readdcld φ2GN+94GN2+log22 N
99 58 98 eqeltrd φFN
100 92 a1i φlog2
101 45 simprd φF64<log2
102 nnrp 44+
103 7 102 ax-mp 4+
104 relogcl 4+log4
105 103 104 ax-mp log4
106 remulcl Nlog4Nlog4
107 37 105 106 sylancl φNlog4
108 60 relogcld φlogN
109 107 108 resubcld φNlog4logN
110 rpre 2 N+2 N
111 rpge0 2 N+02 N
112 110 111 resqrtcld 2 N+2 N
113 94 112 syl φ2 N
114 3nn 3
115 nndivre 2 N32 N3
116 113 114 115 sylancl φ2 N3
117 2re 2
118 readdcl 2 N322 N3+2
119 116 117 118 sylancl φ2 N3+2
120 94 relogcld φlog2 N
121 119 120 remulcld φ2 N3+2log2 N
122 remulcl 4N4 N
123 74 37 122 sylancr φ4 N
124 nndivre 4 N34 N3
125 123 114 124 sylancl φ4 N3
126 5re 5
127 resubcl 4 N354 N35
128 125 126 127 sylancl φ4 N35
129 remulcl 4 N35log24 N35log2
130 128 92 129 sylancl φ4 N35log2
131 121 130 readdcld φ2 N3+2log2 N+4 N35log2
132 remulcl 4 N3log24 N3log2
133 125 92 132 sylancl φ4 N3log2
134 133 108 resubcld φ4 N3log2logN
135 3 nnzd φN
136 df-5 5=4+1
137 74 a1i φ4
138 6nn 6
139 4nn0 40
140 4lt10 4<10
141 138 139 139 140 declti 4<64
142 141 a1i φ4<64
143 137 36 37 142 4 lttrd φ4<N
144 4z 4
145 zltp1le 4N4<N4+1N
146 144 135 145 sylancr φ4<N4+1N
147 143 146 mpbid φ4+1N
148 136 147 eqbrtrid φ5N
149 5nn 5
150 149 nnzi 5
151 150 eluz1i N5N5N
152 135 148 151 sylanbrc φN5
153 breq2 p=qN<pN<q
154 breq1 p=qp2 Nq2 N
155 153 154 anbi12d p=qN<pp2 NN<qq2 N
156 155 cbvrexvw pN<pp2 NqN<qq2 N
157 5 156 sylnib φ¬qN<qq2 N
158 eqid nifnnnpCnt(2 NN)1=nifnnnpCnt(2 NN)1
159 eqid 2 N3=2 N3
160 eqid 2 N=2 N
161 152 157 158 159 160 bposlem6 φ4NN<2 N2 N3+224 N35
162 reexplog 4+N4N=eNlog4
163 103 135 162 sylancr φ4N=eNlog4
164 60 reeflogd φelogN=N
165 164 eqcomd φN=elogN
166 163 165 oveq12d φ4NN=eNlog4elogN
167 107 recnd φNlog4
168 108 recnd φlogN
169 efsub Nlog4logNeNlog4logN=eNlog4elogN
170 167 168 169 syl2anc φeNlog4logN=eNlog4elogN
171 166 170 eqtr4d φ4NN=eNlog4logN
172 94 rpcnd φ2 N
173 94 rpne0d φ2 N0
174 119 recnd φ2 N3+2
175 172 173 174 cxpefd φ2 N2 N3+2=e2 N3+2log2 N
176 2cn 2
177 2ne0 20
178 128 recnd φ4 N35
179 cxpef 2204 N3524 N35=e4 N35log2
180 176 177 178 179 mp3an12i φ24 N35=e4 N35log2
181 175 180 oveq12d φ2 N2 N3+224 N35=e2 N3+2log2 Ne4 N35log2
182 121 recnd φ2 N3+2log2 N
183 130 recnd φ4 N35log2
184 efadd 2 N3+2log2 N4 N35log2e2 N3+2log2 N+4 N35log2=e2 N3+2log2 Ne4 N35log2
185 182 183 184 syl2anc φe2 N3+2log2 N+4 N35log2=e2 N3+2log2 Ne4 N35log2
186 181 185 eqtr4d φ2 N2 N3+224 N35=e2 N3+2log2 N+4 N35log2
187 161 171 186 3brtr3d φeNlog4logN<e2 N3+2log2 N+4 N35log2
188 eflt Nlog4logN2 N3+2log2 N+4 N35log2Nlog4logN<2 N3+2log2 N+4 N35log2eNlog4logN<e2 N3+2log2 N+4 N35log2
189 109 131 188 syl2anc φNlog4logN<2 N3+2log2 N+4 N35log2eNlog4logN<e2 N3+2log2 N+4 N35log2
190 187 189 mpbird φNlog4logN<2 N3+2log2 N+4 N35log2
191 109 131 134 190 ltsub1dd φNlog4-logN-4 N3log2logN<2 N3+2log2 N+4 N35log2-4 N3log2logN
192 37 recnd φN
193 mulcom 2N2 N= N2
194 176 192 193 sylancr φ2 N= N2
195 194 oveq1d φ2 Nlog2= N2log2
196 92 recni log2
197 mulass N2log2 N2log2=N2log2
198 176 196 197 mp3an23 N N2log2=N2log2
199 192 198 syl φ N2log2=N2log2
200 196 2timesi 2log2=log2+log2
201 relogmul 2+2+log22=log2+log2
202 90 90 201 mp2an log22=log2+log2
203 2t2e4 22=4
204 203 fveq2i log22=log4
205 200 202 204 3eqtr2i 2log2=log4
206 205 oveq2i N2log2=Nlog4
207 199 206 eqtrdi φ N2log2=Nlog4
208 195 207 eqtrd φ2 Nlog2=Nlog4
209 208 oveq1d φ2 Nlog24 N3log2=Nlog44 N3log2
210 125 recnd φ4 N3
211 3rp 3+
212 rpdivcl 2 N+3+2 N3+
213 94 211 212 sylancl φ2 N3+
214 213 rpcnd φ2 N3
215 4p2e6 4+2=6
216 215 oveq1i 4+2 N=6 N
217 4cn 4
218 adddir 42N4+2 N=4 N+2 N
219 217 176 192 218 mp3an12i φ4+2 N=4 N+2 N
220 216 219 eqtr3id φ6 N=4 N+2 N
221 220 oveq1d φ6 N3=4 N+2 N3
222 6cn 6
223 3cn 3
224 3ne0 30
225 223 224 pm3.2i 330
226 div23 6N3306 N3=63 N
227 222 225 226 mp3an13 N6 N3=63 N
228 192 227 syl φ6 N3=63 N
229 3t2e6 32=6
230 229 oveq1i 323=63
231 176 223 224 divcan3i 323=2
232 230 231 eqtr3i 63=2
233 232 oveq1i 63 N=2 N
234 228 233 eqtrdi φ6 N3=2 N
235 123 recnd φ4 N
236 remulcl 2N2 N
237 117 37 236 sylancr φ2 N
238 237 recnd φ2 N
239 divdir 4 N2 N3304 N+2 N3=4 N3+2 N3
240 225 239 mp3an3 4 N2 N4 N+2 N3=4 N3+2 N3
241 235 238 240 syl2anc φ4 N+2 N3=4 N3+2 N3
242 221 234 241 3eqtr3d φ2 N=4 N3+2 N3
243 210 214 242 mvrladdd φ2 N4 N3=2 N3
244 243 oveq1d φ2 N4 N3log2=2 N3log2
245 100 recnd φlog2
246 238 210 245 subdird φ2 N4 N3log2=2 Nlog24 N3log2
247 244 246 eqtr3d φ2 N3log2=2 Nlog24 N3log2
248 133 recnd φ4 N3log2
249 167 248 168 nnncan2d φNlog4-logN-4 N3log2logN=Nlog44 N3log2
250 209 247 249 3eqtr4d φ2 N3log2=Nlog4-logN-4 N3log2logN
251 116 recnd φ2 N3
252 176 a1i φ2
253 120 recnd φlog2 N
254 251 252 253 adddird φ2 N3+2log2 N=2 N3log2 N+2log2 N
255 relogmul 2+N+log2 N=log2+logN
256 90 60 255 sylancr φlog2 N=log2+logN
257 256 oveq2d φ2log2 N=2log2+logN
258 252 245 168 adddid φ2log2+logN=2log2+2logN
259 257 258 eqtrd φ2log2 N=2log2+2logN
260 259 oveq2d φ2 N3log2 N+2log2 N=2 N3log2 N+2log2+2logN
261 254 260 eqtrd φ2 N3+2log2 N=2 N3log2 N+2log2+2logN
262 5cn 5
263 262 a1i φ5
264 210 263 245 subdird φ4 N35log2=4 N3log25log2
265 264 oveq1d φ4 N35log24 N3log2logN=4 N3log2-5log2-4 N3log2logN
266 262 196 mulcli 5log2
267 266 a1i φ5log2
268 248 267 168 nnncan1d φ4 N3log2-5log2-4 N3log2logN=logN5log2
269 265 268 eqtrd φ4 N35log24 N3log2logN=logN5log2
270 261 269 oveq12d φ2 N3+2log2 N+4 N35log2-4 N3log2logN=2 N3log2 N+2log2+2logN+logN5log2
271 134 recnd φ4 N3log2logN
272 182 183 271 addsubassd φ2 N3+2log2 N+4 N35log2-4 N3log2logN=2 N3+2log2 N+4 N35log2-4 N3log2logN
273 262 223 196 subdiri 53log2=5log23log2
274 3p2e5 3+2=5
275 274 oveq1i 3+2-3=53
276 pncan2 323+2-3=2
277 223 176 276 mp2an 3+2-3=2
278 275 277 eqtr3i 53=2
279 278 oveq1i 53log2=2log2
280 273 279 eqtr3i 5log23log2=2log2
281 280 a1i φ5log23log2=2log2
282 mulcl 2logN2logN
283 176 168 282 sylancr φ2logN
284 df-3 3=2+1
285 284 oveq1i 3logN=2+1logN
286 1cnd φ1
287 252 286 168 adddird φ2+1logN=2logN+1logN
288 285 287 eqtrid φ3logN=2logN+1logN
289 168 mullidd φ1logN=logN
290 289 oveq2d φ2logN+1logN=2logN+logN
291 288 290 eqtrd φ3logN=2logN+logN
292 291 oveq1d φ3logN5log2=2logN+logN-5log2
293 283 168 267 292 assraddsubd φ3logN5log2=2logN+logN-5log2
294 281 293 oveq12d φ5log23log2+3logN-5log2=2log2+2logN+logN5log2
295 relogdiv N+2+logN2=logNlog2
296 60 90 295 sylancl φlogN2=logNlog2
297 296 oveq2d φ3logN2=3logNlog2
298 subdi 3logNlog23logNlog2=3logN3log2
299 223 196 298 mp3an13 logN3logNlog2=3logN3log2
300 168 299 syl φ3logNlog2=3logN3log2
301 297 300 eqtrd φ3logN2=3logN3log2
302 div23 2N3302 N3=23 N
303 176 225 302 mp3an13 N2 N3=23 N
304 192 303 syl φ2 N3=23 N
305 223 176 223 176 177 177 divmuldivi 3232=3322
306 3t3e9 33=9
307 306 203 oveq12i 3322=94
308 305 307 eqtr2i 94=3232
309 308 a1i φ94=3232
310 304 309 oveq12d φ2 N394=23 N3232
311 176 223 224 divcli 23
312 223 176 177 divcli 32
313 mul4 23N323223 N3232=2332N32
314 312 312 313 mpanr12 23N23 N3232=2332N32
315 311 192 314 sylancr φ23 N3232=2332N32
316 divcan6 2203302332=1
317 176 177 223 224 316 mp4an 2332=1
318 317 oveq1i 2332N32=1N32
319 mulcl N32N32
320 192 312 319 sylancl φN32
321 320 mullidd φ1N32=N32
322 318 321 eqtrid φ2332N32=N32
323 2cnne0 220
324 div12 N3220N32=3N2
325 223 323 324 mp3an23 NN32=3N2
326 192 325 syl φN32=3N2
327 322 326 eqtrd φ2332N32=3N2
328 310 315 327 3eqtrd φ2 N394=3N2
329 328 83 oveq12d φ2 N394GN2=3N2logN2N2
330 76 recni 94
331 330 a1i φ94
332 86 recnd φGN2
333 214 331 332 mulassd φ2 N394GN2=2 N394GN2
334 223 a1i φ3
335 77 rpcnd φN2
336 84 recnd φlogN2
337 77 rpne0d φN20
338 336 335 337 divcld φlogN2N2
339 334 335 338 mulassd φ3N2logN2N2=3N2logN2N2
340 336 335 337 divcan2d φN2logN2N2=logN2
341 340 oveq2d φ3N2logN2N2=3logN2
342 339 341 eqtrd φ3N2logN2N2=3logN2
343 329 333 342 3eqtr3d φ2 N394GN2=3logN2
344 223 196 mulcli 3log2
345 344 a1i φ3log2
346 mulcl 3logN3logN
347 223 168 346 sylancr φ3logN
348 267 345 347 npncan3d φ5log23log2+3logN-5log2=3logN3log2
349 301 343 348 3eqtr4d φ2 N394GN2=5log23log2+3logN-5log2
350 117 92 remulcli 2log2
351 350 recni 2log2
352 351 a1i φ2log2
353 subcl logN5log2logN5log2
354 168 266 353 sylancl φlogN5log2
355 352 283 354 addassd φ2log2+2logN+logN5log2=2log2+2logN+logN5log2
356 294 349 355 3eqtr4d φ2 N394GN2=2log2+2logN+logN5log2
357 356 oveq2d φ2 N3log2 N+2 N394GN2=2 N3log2 N+2log2+2logN+logN5log2
358 mulcl 2 N3log22 N3log2
359 251 196 358 sylancl φ2 N3log2
360 251 168 mulcld φ2 N3logN
361 88 recnd φ94GN2
362 214 361 mulcld φ2 N394GN2
363 359 360 362 addassd φ2 N3log2+2 N3logN+2 N394GN2=2 N3log2+2 N3logN+2 N394GN2
364 256 oveq2d φ2 N3log2 N=2 N3log2+logN
365 251 245 168 adddid φ2 N3log2+logN=2 N3log2+2 N3logN
366 364 365 eqtrd φ2 N3log2 N=2 N3log2+2 N3logN
367 366 oveq1d φ2 N3log2 N+2 N394GN2=2 N3log2+2 N3logN+2 N394GN2
368 58 oveq2d φ2 N3FN=2 N32GN+94GN2+log22 N
369 89 recnd φ2GN+94GN2
370 97 recnd φlog22 N
371 214 369 370 adddid φ2 N32GN+94GN2+log22 N=2 N32GN+94GN2+2 N3log22 N
372 368 371 eqtrd φ2 N3FN=2 N32GN+94GN2+2 N3log22 N
373 72 recnd φ2GN
374 214 373 361 adddid φ2 N32GN+94GN2=2 N32GN+2 N394GN2
375 94 rpge0d φ02 N
376 remsqsqrt 2 N02 N2 N2 N=2 N
377 237 375 376 syl2anc φ2 N2 N=2 N
378 377 oveq1d φ2 N2 N3=2 N3
379 113 recnd φ2 N
380 224 a1i φ30
381 379 379 334 380 div23d φ2 N2 N3=2 N32 N
382 378 381 eqtr3d φ2 N3=2 N32 N
383 382 oveq1d φ2 N32GN=2 N32 N2GN
384 251 379 373 mulassd φ2 N32 N2GN=2 N32 N2GN
385 0le2 02
386 117 385 pm3.2i 202
387 60 rprege0d φN0N
388 sqrtmul 202N0N2 N=2N
389 386 387 388 sylancr φ2 N=2N
390 389 oveq1d φ2 N2GN=2N2GN
391 59 recni 2
392 391 a1i φ2
393 61 rpcnd φN
394 70 recnd φGN
395 392 393 392 394 mul4d φ2N2GN=22NGN
396 remsqsqrt 20222=2
397 117 385 396 mp2an 22=2
398 397 a1i φ22=2
399 67 oveq2d φNGN=NlogNN
400 68 recnd φlogN
401 61 rpne0d φN0
402 400 393 401 divcan2d φNlogNN=logN
403 399 402 eqtrd φNGN=logN
404 398 403 oveq12d φ22NGN=2logN
405 400 2timesd φ2logN=logN+logN
406 61 61 relogmuld φlogNN=logN+logN
407 remsqsqrt N0NNN=N
408 387 407 syl φNN=N
409 408 fveq2d φlogNN=logN
410 406 409 eqtr3d φlogN+logN=logN
411 404 405 410 3eqtrd φ22NGN=logN
412 390 395 411 3eqtrd φ2 N2GN=logN
413 412 oveq2d φ2 N32 N2GN=2 N3logN
414 383 384 413 3eqtrd φ2 N32GN=2 N3logN
415 414 oveq1d φ2 N32GN+2 N394GN2=2 N3logN+2 N394GN2
416 374 415 eqtrd φ2 N32GN+94GN2=2 N3logN+2 N394GN2
417 382 oveq1d φ2 N3log22 N=2 N32 Nlog22 N
418 251 379 370 mulassd φ2 N32 Nlog22 N=2 N32 Nlog22 N
419 95 rpne0d φ2 N0
420 245 379 419 divcan2d φ2 Nlog22 N=log2
421 420 oveq2d φ2 N32 Nlog22 N=2 N3log2
422 417 418 421 3eqtrd φ2 N3log22 N=2 N3log2
423 416 422 oveq12d φ2 N32GN+94GN2+2 N3log22 N=2 N3logN+2 N394GN2+2 N3log2
424 360 362 addcld φ2 N3logN+2 N394GN2
425 424 359 addcomd φ2 N3logN+2 N394GN2+2 N3log2=2 N3log2+2 N3logN+2 N394GN2
426 372 423 425 3eqtrd φ2 N3FN=2 N3log2+2 N3logN+2 N394GN2
427 363 367 426 3eqtr4rd φ2 N3FN=2 N3log2 N+2 N394GN2
428 251 253 mulcld φ2 N3log2 N
429 addcl 2log22logN2log2+2logN
430 351 283 429 sylancr φ2log2+2logN
431 428 430 354 addassd φ2 N3log2 N+2log2+2logN+logN5log2=2 N3log2 N+2log2+2logN+logN5log2
432 357 427 431 3eqtr4d φ2 N3FN=2 N3log2 N+2log2+2logN+logN5log2
433 270 272 432 3eqtr4rd φ2 N3FN=2 N3+2log2 N+4 N35log2-4 N3log2logN
434 191 250 433 3brtr4d φ2 N3log2<2 N3FN
435 100 99 213 ltmul2d φlog2<FN2 N3log2<2 N3FN
436 434 435 mpbird φlog2<FN
437 46 100 99 101 436 lttrd φF64<FN
438 46 99 437 ltnsymd φ¬FN<F64
439 43 438 pm2.21dd φψ