Probabilistic number theory

 

Probabilistic number theory[edit]

Main article: Probabilistic number theory

Much of probabilistic number theory can be seen as an important special case of the study of variables that are almost, but not quite, mutually independent. For example, the event that a random integer between one and a million be divisible by two and the event that it be divisible by three are almost independent, but not quite.

It is sometimes said that probabilistic combinatorics uses the fact that whatever happens with probability greater than ${\displaystyle 0}$ must happen sometimes; one may say with equal justice that many applications of probabilistic number theory hinge on the fact that whatever is unusual must be rare. If certain algebraic objects (say, rational or integer solutions to certain equations) can be shown to be in the tail of certain sensibly defined distributions, it follows that there must be few of them; this is a very concrete non-probabilistic statement following from a probabilistic one.

At times, a non-rigorous, probabilistic approach leads to a number of heuristic algorithms and open problems, notably Cramér's conjecture.

Arithmetic combinatorics[edit]

Main articles: Arithmetic combinatorics and Additive number theory

If we begin from a fairly "thick" infinite set ${\displaystyle �}$, does it contain many elements in arithmetic progression: ${\displaystyle �}$, ${\displaystyle �+�,�+2�,�+3�,\dots ,�+10�}$, say? Should it be possible to write large integers as sums of elements of ${\displaystyle �}$?

These questions are characteristic of arithmetic combinatorics. This is a presently coalescing field; it subsumes additive number theory (which concerns itself with certain very specific sets ${\displaystyle �}$ of arithmetic significance, such as the primes or the squares) and, arguably, some of the geometry of numbers, together with some rapidly developing new material. Its focus on issues of growth and distribution accounts in part for its developing links with ergodic theory, finite group theory, model theory, and other fields. The term additive combinatorics is also used; however, the sets ${\displaystyle �}$ being studied need not be sets of integers, but rather subsets of non-commutative groups, for which the multiplication symbol, not the addition symbol, is traditionally used; they can also be subsets of rings, in which case the growth of ${\displaystyle �+�}$ and ${\displaystyle �}$·${\displaystyle �}$ may be compared.

Computational number theory[edit]

Main article: Computational number theory

A Lehmer sieve, a primitive digital computer used to find primes and solve simple Diophantine equations.

While the word algorithm goes back only to certain readers of al-Khwārizmī, careful descriptions of methods of solution are older than proofs: such methods (that is, algorithms) are as old as any recognisable mathematics—ancient Egyptian, Babylonian, Vedic, Chinese—whereas proofs appeared only with the Greeks of the classical period.

An early case is that of what we now call the Euclidean algorithm. In its basic form (namely, as an algorithm for computing the greatest common divisor) it appears as Proposition 2 of Book VII in Elements, together with a proof of correctness. However, in the form that is often used in number theory (namely, as an algorithm for finding integer solutions to an equation ${\displaystyle ��+��=�}$, or, what is the same, for finding the quantities whose existence is assured by the Chinese remainder theorem) it first appears in the works of Āryabhaṭa (5th–6th century CE) as an algorithm called kuṭṭaka ("pulveriser"), without a proof of correctness.

There are two main questions: "Can we compute this?" and "Can we compute it rapidly?" Anyone can test whether a number is prime or, if it is not, split it into prime factors; doing so rapidly is another matter. We now know fast algorithms for testing primality, but, in spite of much work (both theoretical and practical), no truly fast algorithm for factoring.

The difficulty of a computation can be useful: modern protocols for encrypting messages (for example, RSA) depend on functions that are known to all, but whose inverses are known only to a chosen few, and would take one too long a time to figure out on one's own. For example, these functions can be such that their inverses can be computed only if certain large integers are factorized. While many difficult computational problems outside number theory are known, most working encryption protocols nowadays are based on the difficulty of a few number-theoretical problems.

Some things may not be computable at all; in fact, this can be proven in some instances. For instance, in 1970, it was proven, as a solution to Hilbert's 10th problem, that there is no Turing machine which can solve all Diophantine equations.^[85] In particular, this means that, given a computably enumerable set of axioms, there are Diophantine equations for which there is no proof, starting from the axioms, of whether the set of equations has or does not have integer solutions. (We would necessarily be speaking of Diophantine equations for which there are no integer solutions, since, given a Diophantine equation with at least one solution, the solution itself provides a proof of the fact that a solution exists. We cannot prove that a particular Diophantine equation is of this kind, since this would imply that it has no solutions.)

Applications[edit]

This section needs expansion with: Modern applications of Number theory. You can help by adding to it. (March 2016)

The number-theorist Leonard Dickson (1874–1954) said "Thank God that number theory is unsullied by any application". Such a view is no longer applicable to number theory.^[86] In 1974, Donald Knuth said "...virtually every theorem in elementary number theory arises in a natural, motivated way in connection with the problem of making computers do high-speed numerical calculations".^[87] Elementary number theory is taught in discrete mathematics courses for computer scientists; on the other hand, number theory also has applications to the continuous in numerical analysis.^[88] As well as the well-known applications to cryptography, there are also applications to many other areas of mathematics.^{[89][90][specify]}