130:
onwards, and the question is 'how far must you go?' A special case is to find the first sign change. The interest of the question was that the numerical evidence known showed no change of sign: Littlewood's result guaranteed that this evidence was just a small number effect, but 'small' here included
339:
look weaker, but they have explicit constants and can actually be applied, in conjunction with machine computation, to prove that lists of solutions (suspected to be complete) are actually the entire solution set.
154:
for such constants, or can one recover a version in which 1000 (say) takes the place of the implied constant? In other words, if it were known that there was
560:
231:, may also need to be made explicit, for computational purposes. One reason Landau notation was a popular introduction is that it hides exactly what
243:
Many of the principal results of analytic number theory that were proved in the period 1900–1950 were in fact ineffective. The main examples were:
478:
589:
253:
530:
248:
615:
369:
235:
is. In some indirect forms of proof it may not be at all obvious that the implied constant can be made explicit.
620:
599:
570:
288:
39:
is finite, the question is whether in principle the list could be printed out after a machine computation.
594:
565:
332:
280:
348:
The difficulties here were met by radically different proof techniques, taking much more care about
311:. These latter could be read quite directly as results on Diophantine equations, after the work of
349:
86:
result about its changing sign infinitely often would be a theorem including, for every value of
268:
182:
139:
32:
138:
The requirement of computability is reflected in and contrasts with the approach used in the
450:
357:
52:
20:
507:
499:
417:
287:
The concrete information that was left theoretically incomplete included lower bounds for
8:
361:
435:
336:
320:
143:
292:
151:
68:
539:
503:
495:
487:
431:
413:
399:
316:
304:
48:
446:
300:
147:
543:
525:
521:
465:
404:
264:
260:
193:
64:
491:
609:
24:
353:
323:: but improvements (to what is now the Thue–Siegel–Roth theorem) were not.
296:
19:
For historical reasons and in order to have application to the solution of
67:
obtained an effective upper bound for the first sign change, now known as
308:
274:
63:) with their asymptotic estimates change sign infinitely often. In 1933
28:
365:
312:
189:
528:(1934). "On the imaginary quadratic corpora of class-number one".
36:
118:
could be computed with specified resources. In practical terms,
146:
the results. It for example brings into question any use of
372:. Ineffective results are still being proved in the shape
27:
have been scrutinised more than in other branches of
402:(1914). "Sur la distribution des nombres premiers".
319:
in the proof is effective in the way it applies the
561:"Diophantine approximation, problems of effective"
74:In more detail, writing for a numerical sequence
607:
574:– comments on the ineffectiveness of the bound.
520:
335:, changed the position. Qualitatively speaking,
16:Theorems whose content is effectively computable
445:. Wellesley, MA: A K Peters. pp. 247–273.
150:and its implied constants: are assertions pure
368:that the difficulties may lie in the realm of
47:An early example of an ineffective result was
587:
558:
479:Journal of the London Mathematical Society
398:
382:, where we have no way of telling which.
35:. Where it is asserted that some list of
430:
608:
464:
455:See p. 9 of the preprint version.
238:
122:would be computed by taking values of
114:) have different signs, and such that
42:
343:
162:with a change of sign and such that
254:Siegel's theorem on integral points
13:
352:. The logic involved is closer to
14:
632:
581:
531:Quarterly Journal of Mathematics
51:'s theorem of 1914, that in the
436:"Kreisel's "unwinding" program"
370:computational complexity theory
331:Later results, particularly of
299:grow); and bounds for the best
551:
514:
458:
424:
392:
1:
468:(1933). "On the difference π(
385:
326:
590:"Diophantine approximations"
188:, say built up from powers,
7:
595:Encyclopedia of Mathematics
566:Encyclopedia of Mathematics
219:for some absolute constant
31:to see if their content is
10:
637:
588:Sprindzhuk, V.G. (2001) ,
559:Sprindzhuk, V.G. (2001) ,
55:the differences of both ψ(
283:based on the Siegel zero.
544:10.1093/qmath/os-5.1.293
249:Thue–Siegel–Roth theorem
492:10.1112/jlms/s1-8.4.277
364:. It is rather loosely
350:proofs by contradiction
273:The 1935 result on the
616:Analytic number theory
315:. The result used for
281:Siegel–Walfisz theorem
269:class number 1 problem
140:analytic number theory
33:effectively computable
621:Diophantine equations
295:for some families of
21:Diophantine equations
362:computable functions
358:computability theory
259:The 1934 theorem of
53:prime number theorem
239:The 'Siegel period'
43:Littlewood's result
344:Theoretical issues
321:mean value theorem
303:approximations to
293:ideal class groups
196:, that means only
181:for some explicit
152:existence theorems
534:. Oxford Series.
472:) − Li(
432:Feferman, Solomon
400:Littlewood, J. E.
317:Liouville numbers
305:algebraic numbers
135:up to a billion.
628:
602:
575:
573:
555:
549:
547:
518:
512:
511:
462:
456:
454:
440:
428:
422:
421:
396:
356:than to that of
337:Baker's theorems
229:implied constant
227:, the so-called
49:J. E. Littlewood
636:
635:
631:
630:
629:
627:
626:
625:
606:
605:
584:
579:
578:
556:
552:
519:
515:
463:
459:
438:
429:
425:
397:
393:
388:
346:
329:
241:
223:. The value of
148:Landau notation
45:
17:
12:
11:
5:
634:
624:
623:
618:
604:
603:
583:
582:External links
580:
577:
576:
550:
538:(1): 293–301.
526:Linfoot, E. H.
513:
457:
423:
405:Comptes Rendus
390:
389:
387:
384:
345:
342:
328:
325:
285:
284:
277:
271:
265:Edward Linfoot
261:Hans Heilbronn
257:
251:
240:
237:
217:
216:
179:
178:
69:Skewes' number
65:Stanley Skewes
44:
41:
15:
9:
6:
4:
3:
2:
633:
622:
619:
617:
614:
613:
611:
601:
597:
596:
591:
586:
585:
572:
568:
567:
562:
554:
545:
541:
537:
533:
532:
527:
523:
522:Heilbronn, H.
517:
509:
505:
501:
497:
493:
489:
485:
481:
480:
475:
471:
467:
461:
452:
448:
444:
437:
433:
427:
419:
415:
412:: 1869–1872.
411:
407:
406:
401:
395:
391:
383:
381:
378:
375:
371:
367:
363:
359:
355:
351:
341:
338:
334:
324:
322:
318:
314:
310:
306:
302:
298:
297:number fields
294:
290:
289:class numbers
282:
278:
276:
272:
270:
266:
262:
258:
255:
252:
250:
246:
245:
244:
236:
234:
230:
226:
222:
214:
210:
206:
202:
199:
198:
197:
195:
191:
187:
184:
176:
172:
168:
165:
164:
163:
161:
157:
153:
149:
145:
141:
136:
134:
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
81:
77:
72:
70:
66:
62:
58:
54:
50:
40:
38:
34:
30:
26:
25:number theory
23:, results in
22:
593:
564:
553:
535:
529:
516:
483:
477:
473:
469:
460:
442:
426:
409:
403:
394:
379:
376:
373:
354:proof theory
347:
330:
309:denominators
307:in terms of
286:
242:
232:
228:
224:
220:
218:
212:
208:
204:
200:
194:exponentials
185:
180:
174:
170:
166:
159:
155:
137:
132:
127:
123:
119:
115:
111:
107:
103:
99:
95:
91:
87:
83:
79:
75:
73:
60:
56:
46:
18:
486:: 277–283.
443:Kreiseliana
366:conjectured
275:Siegel zero
256:, from 1929
29:mathematics
610:Categories
508:0007.34003
500:59.0370.02
466:Skewes, S.
418:45.0305.01
386:References
333:Alan Baker
327:Later work
190:logarithms
131:values of
98:such that
90:, a value
600:EMS Press
571:EMS Press
313:Axel Thue
84:effective
434:(1996).
301:rational
183:function
110: (
102: (
78: (
59:) and π(
37:integers
451:1435765
267:on the
506:
498:
449:
416:
106:) and
82:), an
439:(PDF)
203:<
158:>
144:prove
126:from
94:>
476:)".
360:and
279:The
263:and
247:The
192:and
169:= O(
540:doi
504:Zbl
496:JFM
488:doi
414:JFM
410:158
142:to
612::
598:,
592:,
569:,
563:,
524:;
502:.
494:.
482:.
447:MR
441:.
408:.
377:or
177:))
71:.
557:*
548:.
546:.
542::
536:5
510:.
490::
484:8
474:x
470:x
453:.
420:.
380:B
374:A
291:(
233:A
225:A
221:A
215:)
213:N
211:(
209:G
207:.
205:A
201:M
186:G
175:N
173:(
171:G
167:M
160:N
156:M
133:n
128:N
124:n
120:M
116:M
112:M
108:f
104:N
100:f
96:N
92:M
88:N
80:n
76:f
61:x
57:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.