Effective results in number theory

Last updated

For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable [ citation needed ]. 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.

Contents

Littlewood's result

An early example of an ineffective result was J. E. Littlewood's theorem of 1914, [1] that in the prime number theorem the differences of both ψ(x) and π(x) with their asymptotic estimates change sign infinitely often. [2] In 1933 Stanley Skewes obtained an effective upper bound for the first sign change, [3] now known as Skewes' number.

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 is reflected in and contrasts with the approach used in the 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 theorems 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 concrete information that was left theoretically incomplete included lower bounds for class numbers (ideal class groups for some families of number fields grow); and bounds for the best rational approximations to algebraic numbers 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.

Later work

Later results, particularly of Alan Baker, changed the position. Qualitatively speaking, Baker's theorems 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 functions. 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 AorB, where we have no way of telling which.

Related Research Articles

<i>abc</i> conjecture The product of distinct prime factors of a,b,c, where c is a+b, is rarely much less than c

The abc conjecture is a conjecture in number theory that arose out of a discussion of Joseph Oesterlé and David Masser in 1985. It is stated in terms of three positive integers and that are relatively prime and satisfy . The conjecture essentially states that the product of the distinct prime factors of is usually not much smaller than . A number of famous conjectures and theorems in number theory would follow immediately from the abc conjecture or its versions. Mathematician Dorian Goldfeld described the abc conjecture as "The most important unsolved problem in Diophantine analysis".

<span class="mw-page-title-main">Geometry of numbers</span>

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski.

In number theory, Skewes's number is any of several large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number for which

<span class="mw-page-title-main">Analytic number theory</span> Exploring properties of the integers with complex analysis

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 Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.

<span class="mw-page-title-main">Diophantine approximation</span> Rational-number approximation of a real number

In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria.

In the mathematical field of complex analysis, Nevanlinna theory is part of the theory of meromorphic functions. It was devised in 1925, by Rolf Nevanlinna. Hermann Weyl called it "one of the few great mathematical events of (the twentieth) century." The theory describes the asymptotic distribution of solutions of the equation f(z) = a, as a varies. A fundamental tool is the Nevanlinna characteristic T(r, f) which measures the rate of growth of a meromorphic function.

In mathematics, a Pisot–Vijayaraghavan number, also called simply a Pisot number or a PV number, is a real algebraic integer greater than 1, all of whose Galois conjugates are less than 1 in absolute value. These numbers were discovered by Axel Thue in 1912 and rediscovered by G. H. Hardy in 1919 within the context of Diophantine approximation. They became widely known after the publication of Charles Pisot's dissertation in 1938. They also occur in the uniqueness problem for Fourier series. Tirukkannapuram Vijayaraghavan and Raphael Salem continued their study in the 1940s. Salem numbers are a closely related set of numbers.

In mathematics, the Gauss class number problem, as usually understood, is to provide for each n ≥ 1 a complete list of imaginary quadratic fields having class number n. It is named after Carl Friedrich Gauss. It can also be stated in terms of discriminants. There are related questions for real quadratic fields and for the behavior as .

In mathematics, Roth's theorem or Thue–Siegel–Roth theorem is a fundamental result in diophantine approximation to algebraic numbers. It is of a qualitative type, stating that algebraic numbers cannot have many rational number approximations that are 'very good'. Over half a century, the meaning of very good here was refined by a number of mathematicians, starting with Joseph Liouville in 1844 and continuing with work of Axel Thue, Carl Ludwig Siegel, Freeman Dyson, and Klaus Roth.

In mathematics, a Thue equation is a Diophantine equation of the form

Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.

In number theory, Dirichlet's theorem on Diophantine approximation, also called Dirichlet's approximation theorem, states that for any real numbers and , with , there exist integers and such that and

MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as:

In mathematics, an impossibility theorem is a theorem that demonstrates a problem or general set of problems cannot be solved. These are also known as proofs of impossibility, negative proofs, or negative results. Impossibility theorems often resolve decades or centuries of work spent looking for a solution by proving there is no solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a proof that works in general, rather than to just show a particular example. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic.

In mathematics, Siegel's theorem on integral points states that for a smooth algebraic curve C of genus g defined over a number field K, presented in affine space in a given coordinate system, there are only finitely many points on C with coordinates in the ring of integers O of K, provided g > 0.

In mathematics, the subspace theorem says that points of small height in projective space lie in a finite number of hyperplanes. It is a result obtained by Wolfgang M. Schmidt.

In mathematics, specifically in transcendental number theory and Diophantine approximation, Siegel's lemma refers to bounds on the solutions of linear equations obtained by the construction of auxiliary functions. The existence of these polynomials was proven by Axel Thue; Thue's proof used Dirichlet's box principle. Carl Ludwig Siegel published his lemma in 1929. It is a pure existence theorem for a system of linear equations.

In mathematics, auxiliary functions are an important construction in transcendental number theory. They are functions that appear in most proofs in this area of mathematics and that have specific, desirable properties, such as taking the value zero for many arguments, or having a zero of high order at some point.

The Duffin–Schaeffer theorem is a theorem in mathematics, specifically, the Diophantine approximation proposed as a conjecture by R. J. Duffin and A. C. Schaeffer in 1941 and proven in 2019 by Dimitris Koukoulopoulos and James Maynard. It states that if is a real-valued function taking on positive values, then for almost all , the inequality

References

  1. ↑ Littlewood, J. E. (1914). "Sur la distribution des nombres premiers". Comptes Rendus . 158: 1869–1872. JFM   45.0305.01.
  2. ↑ Feferman, Solomon (1996). "Kreisel's "unwinding" program" (PDF). Kreiseliana. Wellesley, MA: A K Peters. pp. 247–273. MR   1435765. See p. 9 of the preprint version.
  3. ↑ Skewes, S. (1933). "On the difference π(x) − Li(x)". Journal of the London Mathematical Society . 8: 277–283. doi:10.1112/jlms/s1-8.4.277. JFM   59.0370.02. Zbl   0007.34003.
  4. ↑ Heilbronn, H.; Linfoot, E. H. (1934). "On the imaginary quadratic corpora of class-number one". Quarterly Journal of Mathematics . Oxford Series. 5 (1): 293–301. doi:10.1093/qmath/os-5.1.293..
  5. ↑
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.