Effective results in number theory
Encyclopedia
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. Where it is asserted that some list of integers is finite, the question is whether in principle the list could be printed out after a machine computation.
the differences of both ψ(x) and π(x) with their asymptotic estimates change sign infinitely often. Until the result on the Skewes number of 1933, these results were believed by some experts to be intrinsically ineffective.
In more detail, writing for a numerical sequence f(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(N) and f(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 reflects on and contrasts with the approach used in analytic number theory
to 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
for some explicit function G, say built up from powers, logarithms and exponentials, that means only
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 concrete information that was left theoretically incomplete included lower bounds for class numbers (ideal class group
s for some families of number fields grow); and bounds for the best rational approximations to algebraic number
s in terms of denominators. These latter could be read quite directly as results on Diophantine equations, after the work of Axel Thue
. The result used for Liouville numbers 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.
than to that of computability theory
and computable function
s. It is rather loosely conjectured 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.
Diophantine equation
In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations...
s, results in number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
have been scrutinised more than in other branches of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
to see if their content is effectively computable. Where it is asserted that some list of integers 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, that in the prime number theoremPrime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
the differences of both ψ(x) and π(x) with their asymptotic estimates change sign infinitely often. Until the result on the Skewes number of 1933, these results were believed by some experts to be intrinsically ineffective.
In more detail, writing for a numerical sequence f(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(N) and f(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 reflects on and contrasts with the approach used in analytic number theory
Analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
to prove the results. It for example brings into question any use of Landau notation and its implied constants: are assertions pure existence theorem
Existence theorem
In mathematics, an existence theorem is a theorem with a statement beginning 'there exist ..', or more generally 'for all x, y, ... there exist ...'. That is, in more formal terms of symbolic logic, it is a theorem with a statement involving the existential quantifier. Many such theorems will not...
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 G, say built up from powers, logarithms and 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 HeilbronnHans HeilbronnHans Arnold Heilbronn was a mathematician.He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervised his doctorate...
and Edward LinfootEdward LinfootEdward Hubert Linfoot was a British mathematician, primarily known for his work on optics, but also noted for his work in pure mathematics.- Early life and career :...
on the class number 1 problem - The 1935 result on the Siegel zeroSiegel zeroIn mathematics, more specifically in the field of analytic number theory, a Siegel zero, named after Carl Ludwig Siegel, is a type of potential counterexample to the generalized Riemann hypothesis, on the zeroes of Dirichlet L-function....
- The Siegel-Walfisz theoremSiegel-Walfisz theoremIn analytic number theory, the Siegel–Walfisz theorem was obtained by Arnold Walfisz as an application of a theorem by Carl Ludwig Siegel to primes in arithmetic progressions.-Statement of the Siegel–Walfisz theorem:Define...
based on the Siegel zero.
The concrete information that was left theoretically incomplete included lower bounds for class numbers (ideal class group
Ideal class group
In mathematics, the extent to which unique factorization fails in the ring of integers of an algebraic number field can be described by a certain group known as an ideal class group...
s for some families of number fields grow); and bounds for the best rational approximations to algebraic number
Algebraic number
In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...
s in terms of denominators. These latter could be read quite directly as results on Diophantine equations, after the work of Axel Thue
Axel Thue
Axel Thue was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics....
. The result used for Liouville numbers in the proof is effective in the way it applies the mean value theorem
Mean value theorem
In calculus, the mean value theorem states, roughly, that given an arc of a differentiable curve, there is at least one point on that arc at which the derivative of the curve is equal to the "average" derivative of the arc. Briefly, a suitable infinitesimal element of the arc is parallel to the...
: but improvements (to what is now the Thue-Siegel-Roth theorem) were not.
Later work
Later results, particularly of Alan Baker, changed the position. Weaker theorems, qualitatively speaking, but with explicit constants, 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 theoryProof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
than to that of computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
and computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s. It is rather loosely conjectured that the difficulties may lie in the realm of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. Ineffective results are still being proved in the shape A or B, where we have no way of telling which.