Editing Effective results in number theory

{{short description|Theorems whose content is effectively computable}}

For historical reasons and in order to have application to the solution of [[Diophantine equation]]s, results in [[number theory]] have been scrutinised more than in other branches of [[mathematics]] to see if their content is [[effectively computable]]{{Citation needed|date=January 2022}}. Where it is asserted that some list of [[integer]]s is finite, the question is whether in principle the list could be printed out after a machine computation.

==Littlewood's result==

An early example of an ineffective result was [[J. E. Littlewood]]'s theorem of 1914,<ref>{{cite journal | first=J. E. | last= Littlewood | authorlink=J. E. Littlewood |title=Sur la distribution des nombres premiers|journal=[[Comptes Rendus]]|volume= 158 |year=1914|pages= 1869–1872 | jfm=45.0305.01 }}</ref> that in the [[prime number theorem]] the differences of both ψ(''x'') and π(''x'') with their asymptotic estimates change sign infinitely often.<ref>{{cite book
 | last = Feferman | first = Solomon | authorlink = Solomon Feferman
 | contribution = Kreisel's "unwinding" program
 | contribution-url = http://math.stanford.edu/~feferman/papers/unwind.pdf
 | mr = 1435765
 | pages = 247–273
 | publisher = A K Peters | location = Wellesley, MA
 | title = Kreiseliana
 | year = 1996}} See p.&nbsp;9 of the preprint version.</ref>  In 1933 [[Stanley Skewes]] obtained an effective upper bound for the first sign change,<ref>{{cite journal | first= S.|last= Skewes|authorlink= Stanley Skewes |title=On the difference π(''x'')&nbsp;−&nbsp;Li(''x'')|journal=[[Journal of the London Mathematical Society]]|volume=8|year=1933|issue= 4|pages= 277–283 | zbl=0007.34003 | jfm=59.0370.02 | doi=10.1112/jlms/s1-8.4.277}}</ref> now known as [[Skewes' number]].

In more detail, writing for a numerical sequence ''f''{{hairsp}}(''n''), an ''effective'' result about its changing sign infinitely often would be a theorem including, for every value of ''N'', a value ''M'' > ''N'' such that ''f''{{hairsp}}(''N'') and ''f''{{hairsp}}(''M'') have different signs, and such that ''M'' could be computed with specified resources. In practical terms, ''M'' would be computed by taking values of ''n'' from ''N'' 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 values of ''n'' up to a billion.

The requirement of computability is reflected in and contrasts with the approach used in the [[analytic number theory]] to [[mathematical proof|prove]] the results. It for example brings into question any use of [[Landau notation]] and its implied constants: are assertions pure [[existence theorem]]s 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 ''M'' > ''N'' with a change of sign and such that

:''M'' = O(''G''(''N''))

for some explicit [[function (mathematics)|function]] ''G'', say built up from powers, [[logarithm]]s and [[exponentiation|exponentials]], that means only

:''M'' < ''A''.''G''(''N'')

for some absolute constant ''A''. The value of ''A'', the so-called ''implied constant'', may also need to be made explicit, for computational purposes. One reason Landau notation was a popular introduction is that it hides exactly what ''A'' is. In some indirect forms of proof it may not be at all obvious that the implied constant can be made explicit.

==The 'Siegel period'==

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:

*The [[Thue–Siegel–Roth theorem]]
*[[Siegel's theorem on integral points]], from 1929
*The 1934 theorem of [[Hans Heilbronn]] and [[Edward Linfoot]] on the [[class number 1 problem]]<ref>{{cite journal
 | last1 = Heilbronn | first1 = H. | author1-link = Hans Heilbronn
 | last2 = Linfoot | first2 = E. H. | author2-link = Edward Linfoot
 | doi = 10.1093/qmath/os-5.1.293
 | issue = 1
 | journal = [[Quarterly Journal of Mathematics]]
 | pages = 293–301
 | series = Oxford Series
 | title = On the imaginary quadratic corpora of class-number one
 | volume = 5
 | year = 1934}}.</ref>
*The 1935 result on the [[Siegel zero]]<ref>*{{SpringerEOM| title=Diophantine approximation, problems of effective | id=Diophantine_approximation,_problems_of_effective | oldid=12671 | first=V.G. | last=Sprindzhuk }} –  comments on the ineffectiveness of the bound.</ref>
* The [[Siegel–Walfisz theorem]] based on the Siegel zero.

The concrete information that was left theoretically incomplete included lower bounds for [[Class number (number theory)|class numbers]] ([[ideal class group]]s for some families of [[number field]]s grow); and bounds for the best [[rational number|rational]] approximations to [[algebraic number]]s in terms of [[denominator]]s. These latter could be read quite directly as results on Diophantine equations, after the work of [[Axel Thue]]. The result used for [[Liouville number]]s in the proof is effective in the way it applies the [[mean value theorem]]: but improvements (to what is now the Thue–Siegel–Roth theorem) were not.

==Later work==

Later results, particularly of [[Alan Baker (mathematician)|Alan Baker]], changed the position. Qualitatively speaking, [[Baker's theorem]]s 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.

==Theoretical issues==

The difficulties here were met by radically different proof techniques, taking much more care about [[proofs by contradiction]]. The logic involved is closer to [[proof theory]] than to that of [[computability theory]] and [[computable function]]s. It is rather loosely [[conjecture]]d that the difficulties may lie in the realm of [[computational complexity theory]]. Ineffective results are still being proved in the shape '''A''' ''or'' '''B''', where we have no way of telling which.

==References==
{{Reflist}}

==External links==
*{{SpringerEOM| title=Diophantine approximations | id=Diophantine_approximations | oldid=11927 | first=V.G. | last=Sprindzhuk}}

[[Category:Analytic number theory]]
[[Category:Diophantine equations]]