:: wikimiki.org ::

Arithmetic Function

Arithmetic function

In number theory, an arithmetic function (or number-theoretic function) f(n) is a function defined for all positive integers and having values in the complex numbers. In other words: an arithmetic function is nothing but a sequence of complex numbers. The most important arithmetic functions are the additive and the multiplicative ones. An important operation on arithmetic functions is the Dirichlet convolution. Arithmetic functions may be studied with Bell series.

Examples

The articles on additive and multiplicative functions contain several examples of arithmetic functions. Here are some examples that are neither additive nor multiplicative:
- c₄(n) - the number of ways that n can be expressed as the sum of four squares of nonnegative integers, where we distinguish between different orders of the summands. For example: ::1 = 1²+0²+0²+0² = 0²+1²+0²+0² = 0²+0²+1²+0² = 0²+0²+0²+1², :hence c₄(1)=4.
- P(n), the Partition function - the number of representations of n as a sum of positive integers, where we don't distinguish between different orders of the summands. For instance: P(2 · 5) = P(10) = 42 and P(2)P(5) = 2 · 7 = 14 ≠ 42.
- π (n), the Prime counting function - the number of primes less than or equal to a given number n. We have π(1) = 0 and π(10) = 4 (the primes below 10 being 2, 3, 5, and 7).
- Λ(n), the von Mangoldt function - ln(p) if n is an integer power of a prime p; 0 for all other n.
- ko:수론적 함수

Number theory

Traditionally, number theory is the branch of pure mathematics concerned with the properties of integers. It contains many results and open problems that are easily understood, even by non-mathematicians. More generally, the field has come to be concerned with wider classes of problems that have arisen naturally from the study of integers. Number theory may be subdivided into several fields, according to the methods used and the type of questions investigated. See for example the list of number theory topics. Mathematicians working in the field of number theory are called number theorists. The term "arithmetic" is also used to refer to number theory. This is a somewhat older term, which is no longer as popular as it once was. Number theory used to be called the higher arithmetic, but this is dropping out of use. Nevertheless, it still shows up in the names of mathematical fields (arithmetic functions, arithmetic of elliptic curves, fundamental theorem of arithmetic). This sense of the term arithmetic should not be confused either with elementary arithmetic, or with the branch of logic which studies Peano arithmetic as a formal system.

Fields

Elementary number theory

In elementary number theory, the integers are studied without use of techniques from other mathematical fields. Questions of divisibility, the Euclidean algorithm to compute greatest common divisors, factorization of integers into prime numbers, investigation of perfect numbers and congruences belong here. Typical statements are Fermat's little theorem and Euler's theorem extending it, the Chinese remainder theorem and the law of quadratic reciprocity. The properties of multiplicative functions such as the Möbius function and Euler's φ function are investigated; so are integer sequences such as factorials and Fibonacci numbers. Many questions in elementary number theory appear simple but may require very deep consideration and new approaches. Examples are
- The Goldbach conjecture concerning the expression of even numbers as sums of two primes,
- Catalan's conjecture regarding successive integer powers,
- The twin prime conjecture about the infinitude of prime pairs, and
- The Collatz conjecture concerning a simple iteration. The theory of Diophantine equations has even been shown to be undecidable (see Hilbert's tenth problem).

Analytic number theory

Analytic number theory employs the machinery of calculus and complex analysis to tackle questions about integers. The prime number theorem and the related Riemann hypothesis are examples. Waring's problem (representing a given integer as a sum of squares, cubes etc.), the Twin Prime Conjecture (finding infinitely many prime pairs with difference 2) and Goldbach's conjecture (writing even integers as sums of two primes) are being attacked with analytical methods as well. Proofs of the transcendence of mathematical constants, such as π or e, are also classified as analytical number theory. While statements about transcendental numbers may seem to be removed from the study of integers, they really study the possible values of polynomials with integer coefficients evaluated at, say, e; they are also closely linked to the field of Diophantine approximation, where one investigates "how well" a given real number may be approximated by a rational one.

Algebraic number theory

In algebraic number theory, the concept of number is expanded to the algebraic numbers which are roots of polynomials with rational coefficients. These domains contain elements analogous to the integers, the so-called algebraic integers. In this setting, the familiar features of the integers (e.g. unique factorization) need not hold. The virtue of the machinery employed -- Galois theory, group cohomology, class field theory, group representations and L-functions -- is that it allows to recover that order partly for this new class of numbers. Many number theoretical questions are best attacked by studying them modulo p for all primes p (see finite fields). This is called localization and it leads to the construction of the p-adic numbers; this field of study is called local analysis and it arises from algebraic number theory.

Geometric number theory

Geometric number theory (traditionally called geometry of numbers) incorporates all forms of geometry. It starts with Minkowski's theorem about lattice points in convex sets and investigations of sphere packings.

Combinatorial number theory

Combinatorial number theory deals with number theoretic problems which involve combinatorial ideas in their formulations or solutions. Paul Erdős is the main founder of this branch of number theory. Typical topics include covering system, zero-sum problems, various restricted sumsets, and arithmetic progressions in a set of integers. Algebraic or analytic methods are powerful in this field.

Computational number theory

Computational number theory studies algorithms relevant in number theory. Fast algorithms for prime testing and integer factorization have important applications in cryptography.

History

Early history

Number theory was a favorite study among the Ancient Greeks, who were aware of the Diophantine equation concept in numerous special cases. It revived in the sixteenth and seventeenth centuries, in Europe, with François Viète, Bachet de Meziriac, and especially Fermat, whose infinite descent method was the first general idea for dealing with diophantine questions. In the eighteenth century Euler and Lagrange made major contributions.

Beginnings of a systematic theory

Around the beginning of the nineteenth century books of Legendre (1798), and Gauss put together the first systematic theories. Gauss's Disquisitiones Arithmeticae (1801) may be said to begin the modern theory of numbers. The formulation of the theory of congruences starts with Gauss's Disquisitiones. He introduced the symbolism :

a \equiv b \pmod c,

and explored most of the field. Chebyshev published in 1847 a work in Russian on the subject, and in France Serret popularised it. Besides summarizing previous work, Legendre stated the law of quadratic reciprocity. This law, discovered by induction and enunciated by Euler, was first proved by Legendre in his Théorie des Nombres (1798) for special cases. Independently of Euler and Legendre, Gauss discovered the law about 1795, and was the first to give a general proof. To the subject have also contributed: Cauchy; Dirichlet whose Vorlesungen über Zahlentheorie is a classic; Jacobi, who introduced the Jacobi symbol; Liouville, Zeller(?), Eisenstein, Kummer, and Kronecker. The theory extends to include cubic and biquadratic reciprocity, (Gauss, Jacobi who first proved the law of cubic reciprocity, and Kummer). To Gauss is also due the representation of numbers by binary quadratic forms.

Prime number theory

A recurring and productive theme in number theory is the study of the distribution of prime numbers. Gauss conjectured the limit of the number of primes not exceeding a given number (the prime number theorem) as a teenager. Chebyshev (1850) gave useful bounds for the number of primes between two given limits. Riemann introduced complex analysis into the theory of the Riemann zeta function. This led to a relation between the zeros of the zeta function and the distribution of primes, eventually leading to a proof of prime number theorem independently by Hadamard and de la Vallée Poussin in 1896. However, an elementary proof was given later by Paul Erdős and Atle Selberg in 1949+. Here elementary means that it does not use techniques of complex analysis; however, the proof is still very ingenious and difficult. The Riemann hypothesis, which would give much more accurate information, is still an open question.

Nineteenth-century developments

Cauchy, Poinsot (1845), Lebesgue(?) (1859, 1868), and notably Hermite have added to the subject. In the theory of ternary forms Eisenstein has been a leader, and to him and H. J. S. Smith is also due a noteworthy advance in the theory of forms in general. Smith gave a complete classification of ternary quadratic forms, and extended Gauss's researches concerning real quadratic forms to complex forms. The investigations concerning the representation of numbers by the sum of 4, 5, 6, 7, 8 squares were advanced by Eisenstein and the theory was completed by Smith. Dirichlet was the first to lecture upon the subject in a German university. Among his contributions is the extension of Fermat's theorem on :

x^n+y^n \neq z^n,

which Euler and Legendre had proved for

n = 3, 4

, Dirichlet showing that

x^5+y^5 \neq az^5

. Among the later French writers are Borel; Poincaré, whose memoirs are numerous and valuable; Tannery, and Stieltjes. Among the leading contributors in Germany were Kronecker, Kummer Schering, Bachmann, and Dedekind. In Austria Stolz's Vorlesungen über allgemeine Arithmetik (1885-86), and in England Mathews' Theory of Numbers (Part I, 1892) were scholarly of general works. Genocchi, Sylvester, and J. W. L. Glaisher have also added to the theory.

Quotations

- Mathematics is the queen of the sciences and number theory is the queen of mathematics. — Gauss
- God invented the integers; all else is the work of man. — Kronecker
- I know numbers are beautiful. If they aren't beautiful, nothing is. — Erdős

References

-
-
-
-
-
-
- Smith, David. [http://www.gutenberg.net/etext05/hsmmt10p.pdf History of Modern Mathematics (1906)] (adapted public domain text)
- Important publications in number theory

External links

- [http://www.numbertheory.org Number Theory Web] Category:Discrete mathematics ko:수론 ja:数論 th:ทฤษฎีจำนวน

Function (mathematics)

In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). The concept of a function is fundamental to virtually every branch of mathematics and every quantitative science. The terms function, mapping, map and transformation are usually used synonymously. The term operation is frequently used for binary functions; functions whose domain is a set of functions, or a vector space, are often called operators (see also operator (programming)).

Intuitive introduction

Essentially, a function is a "rule" or procedure that assigns an "output" value to each given "input" value. The following are examples of functions:
- In a group of people, each person has a favorite colour—from the set of red, orange, yellow, green, cyan, blue, indigo, or violet. Here, the input is the person, and the output is one of the 8 colours. The favorite colour is a function of the person. For example, John has favorite colour red, while Kim has favorite colour violet. Note that more than one person may be associated with a given colour (e.g., John and Kim may both like red), but one person cannot have more or less than one favorite color.
- A stone is dropped from different stories of a tall building. The dropped stone may take 2 seconds to fall from the second story, and 4 seconds to fall from the 8th story. Here, the input is the story, and the output is the number of seconds. The relevant function describes the relationship between the time it takes the stone to reach the ground and the story. (See acceleration) The "rule" defining a function can be specified by a formula, a relationship, or simply a table listing the outputs against inputs. The most important feature of a function is that it is consistent, or deterministic, always producing the same output from a given input. In this way, a function may be thought of as a mechanism or "machine" (a "black box") consistently converting a given valid input into its unique associated output. In certain technical contexts, the input is often called the argument of the function, and the output the value of the function. A very common type of function occurs when the argument (input) and the value (output) are both numbers, the functional relationship is expressed by a formula, and the value (output) of the function is obtained by direct substitution of the argument into the formula. Consider for example :

f(x)=x^

which for any number x, assigns to x the associated value the square of x. A straightforward generalization is to allow functions depending on several arguments. For instance, :

g(x,y) = xy

is a function which takes the input, two expressions x and y, and assigns to it its product (output), xy. It might seem that this is not really a function as we described above, because this "rule" depends on two inputs. However, if we think of the two inputs together as a single pair (x, y), then we can interpret g as a function -- the argument (unified single input) is the ordered pair (x, y), and the function value (output) is xy. Such functions whose input consists of ordered pairs are called "binary" or "2-ary". In the sciences, we often encounter functions that are not given by (known) formulas. Consider for instance the temperature distribution on earth over time: this is a function which takes location and time as arguments and gives as output value the temperature at the indicated location at the indicated moment in time. We have seen that the intuitive notion of function is not limited to computations using single numbers and not even limited to computations; the mathematical notion of function is still more general and is not limited to situations involving numbers. Rather, a function links a "domain" (set of inputs) to a "codomain" (set of possible outputs) in such a way that every element of the domain is associated to precisely one element of the codomain. Functions are abstractly defined as certain relations, as will be seen below. Because of this generality, the function concept is fundamental to virtually every branch of mathematics and the quantitative sciences.

History

As a mathematical term, "function" was coined by Leibniz in 1694, to describe a quantity related to a curve, such as a curve's slope or a specific point of a curve. The functions Leibniz considered are today called differentiable functions, and they are the type of function most frequently encountered by nonmathematicians. For this type of function, one can talk about limits and derivatives; both are measurements of the change of output values associated to a change of input values, and these measurements are the basis of calculus. The word function was later used by Euler during the mid-18th century to describe an expression or formula involving various arguments, e.g. f(x) = sin(x) + x³. During the 19th century, mathematicians started to formalize all the different branches of mathematics. Weierstrass advocated building calculus on arithmetic rather than on geometry, which favoured Euler's definition over Leibniz's (see arithmetization of analysis). By broadening the definition of functions, mathematicians were then able to study "strange" mathematical objects such as continuous functions that are nowhere differentiable. These functions were first thought to be only theoretical curiosities, and they were collectively called "monsters" as late as the turn of the 20th century. However, powerful techniques from functional analysis have shown that these functions are in some sense "more common" than differentiable functions. Such functions have since been applied to the modeling of physical phenomena such as Brownian motion. Towards the end of the 19th century, mathematicians started trying to formalize all of mathematics using set theory, and they sought to define every mathematical object as a set. Dirichlet and Lobachevsky independently and almost simultaneously gave the modern "formal" definition of function (see formal definition below). In this definition, a function is a special case of a relation. In most cases of practical interest, however, the differences between the modern definition and Euler's definition are negligible. The notion of function as a rule for computing, rather than a special kind of relation, has been formalized in mathematical logic and theoretical computer science by means of several systems, including the lambda calculus, the theory of recursive functions and the Turing machine.

Formal definition

Formally a function f from a set X to a set Y, written f : X → Y, is an ordered triple (X, Y, G(f)), where G(f) is a subset of the cartesian product X × Y, such that for each x in X, there is a unique y in Y such that the ordered pair (x, y) is in G(f). X is called the domain of f, Y is called the codomain of F, and G(f) is called the graph of f. For each "input value" x in the domain, the corresponding unique "output value" y in the codomain is denoted by f(x). Equivalently a function f can be defined as a relation between X and Y which satisfies: # f is total, or entire: for all x in X, there exists a y in Y such that x f y (x is f-related to y), i.e. for each input value, there is at least one output value in Y. # f is many-to-one, or functional: if x f y and x f z, then y = z. i.e., many input values can be related to one output value, but one input value cannot be related to many output values. A relation between X and Y that satisfies condition (1) is a multivalued function. Every function is a multivalued function, but not every multivalued function is a function. A relation between X and Y that satisfies condition (2) is a partial function. Every function is a partial function, but not every partial function is a function. In this encyclopedia, the term "function" will mean a relation satisfying both conditions (1) and (2), unless otherwise stated. Consider the following three examples:

image:notMap1.png This relation is total but not many-to-one; the element 3 in X is related to two elements b and c in Y. Therefore, this is a multivalued function, but not a function.

image:notMap2.png This relation is many-to-one but not total; the element 1 in X is not related to any element of Y. Therefore, this is a partial function, but not a function.

image:mathmap2.png

This relation is both total and many-to-one, and so it is a function from X to Y. Note that the emphasis is on "-to-one" as "many" may actually mean "one". The function can be given explicitly by specifying its graph G(f) = or as :

f(x)=\left\

Integer

The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. They are also known as the whole numbers, although that term is also used to refer only to the positive integers (with or without zero). Like the natural numbers, the integers form a countably infinite set. The set of all integers is usually denoted in mathematics by a boldface Z (or blackboard bold,

\mathbb

), which stands for Zahlen (German for "numbers"). The term rational integer is used, in algebraic number theory, to distinguish these 'ordinary' integers, in the rational numbers, from other concepts such as the Gaussian integers.

Algebraic properties

Like the natural numbers, Z is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer. However, with the inclusion of the negative natural numbers, and, importantly, zero, Z (unlike the natural numbers) is also closed under subtraction. Z is not closed under the operation of division, since the quotient of two integers (e.g., 1 divided by 2), need not be an integer. The following table lists some of the basic properties of addition and multiplication for any integers a, b and c. In the language of abstract algebra, the first five properties listed above for addition say that Z under addition is an abelian group. As a group under addition, Z is a cyclic group, since every nonzero integer can be written as a finite sum 1 + 1 + ... 1 or (−1) + (−1) + ... + (−1). In fact, Z under addition is the only infinite cyclic group, in the sense that any infinite cyclic group is isomorphic to Z. The first four properties listed above for multiplication say that Z under multiplication is a commutative monoid. However, note that not every integer has a multiplicative inverse; e.g. there is no integer x such that 2x = 1, because the left hand side is even, while the right hand side is odd. This means that Z under multiplication is not a group. All the properties from the above table taken together say that Z together with addition and multiplication is a commutative ring with unity. In fact, Z provides the motivation for defining such a structure. The lack of multiplicative inverses, which is equivalent to the fact that Z is not closed under division, means that Z is not a field. The smallest field containing the integers is the field of rational numbers. This process can be mimicked to form the quotient field of any integral domain, where an integral domain is a commutative ring with unity such that whenever ab = 0, either a = 0 or b = 0. Although ordinary division is not defined on Z, it does possess an important property called the division algorithm: that is, given two integers a and b with b ≠ 0, there exist unique integers q and r such that a = q × b + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b. The integer q is called the quotient and r is called the remainder, resulting from division of a by b. This is the basis for the Euclidean algorithm for computing greatest common divisors. Again, in the language of abstract algebra, the above says that Z is a Euclidean domain. This implies that Z is a principal ideal domain and any positive integer can be written as the products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.

Order-theoretic properties

Z is a totally ordered set without upper or lower bound. The ordering of Z is given by : ... < −2 < −1 < 0 < 1 < 2 < ... An integer is positive if it is greater than zero and negative if it is less than zero. Zero is defined as neither negative nor positive. The ordering of integers is compatible with the algebraic operations in the following way: # if a < b and c < d, then a + c < b + d # if a < b and 0 < c, then ac < bc. (From this fact, one can show that if c < 0, then ac > bc.)

Integers in computing

An integer (sometimes known as an "int", from the name of a datatype in the C programming language) is often a primitive datatype in computer languages. However, integer datatypes can only represent a subset of all integers, since practical computers are of finite capacity. Variable-length representations of integers, such as bignums, can store any integer that fits in the computers memory. Other integer datatypes are implemented with a fixed size, usually a number of bits which is a power of 2 (4, 8, 16, etc.) or a memorable number of decimal digits (e.g., 9 or 10). In contrast, theoretical models of digital computers, such as Turing machines, typically do have infinite (but only countable) capacity.

Quotations

God invented the integers, all else is the work of man. Kronecker

External links

- [http://www.positiveintegers.org The Positive Integers - divisor tables and numeral representation tools] Category:Elementary mathematics Category:Group theory Category:Integers Category:Elementary number theory Category:Set theory ko:정수 ja:整数 th:จำนวนเต็ม

Complex number

In mathematics, a complex number is an expression of the form a + bi, where a and b are real numbers, and i stands for the square root of minus one (−1), which cannot be represented by any real number. For example, :3 + 2i is a complex number, where 3 is called the real part and 2 the imaginary part. Since a complex number a + bi is uniquely specified by an ordered pair (a, b) of real numbers, the complex numbers are in one-to-one correspondence with points on a plane, called the complex plane. The set of all complex numbers is usually denoted by C, or in blackboard bold by

\mathbb

. It includes the real numbers because every real number can be regarded as complex: a = a + 0i. Complex numbers are added, subtracted, and multiplied by formally applying the associative, commutative and distributive laws of algebra, together with the equation i ² = −1: :(a + bi) + (c + di) = (a+c) + (b+d)i :(a + bi) − (c + di) = (a−c) + (b−d)i :(a + bi)(c + di) = ac + bci + adi + bd i ² = (ac−bd) + (bc+ad)i Division of complex numbers can also be defined (see below). Thus the set of complex numbers forms a field which, in contrast to the real numbers, is algebraically closed. In mathematics, the adjective "complex" means that the field of complex numbers is the underlying number field considered, for example complex analysis, complex matrix, complex polynomial and complex Lie algebra.

Definition

The complex number field

Formally, the complex numbers can be defined as ordered pairs of real numbers (a, b) together with the operations:
-

( a , b ) + ( c , d ) = ( a + c , b + d ) \,

( a , b ) \cdot ( c , d ) = ( ac - bd , bc + ad ). \,

So defined, the complex numbers form a field, the complex number field, denoted by C. We identify the real number a with the complex number (a, 0), and in this way the field of real numbers R becomes a subfield of C. The imaginary unit i is the complex number (0, 1). In C, we have:
- additive identity ("zero"): (0, 0)
- multiplicative identity ("one"): (1, 0)
- additive inverse of (a,b): (−a, −b)
- multiplicative inverse (reciprocal) of non-zero (a, b):

\left(,\right).

C can also be defined as the topological closure of the algebraic numbers or as the algebraic closure of R, both of which are described below.

The complex plane

image:complex.png

A complex number can be viewed as a point or a position vector on a two-dimensional Cartesian coordinate system called the complex plane or Argand diagram (named after Jean-Robert Argand). The Cartesian coordinates of the complex number are the real part x and the imaginary part y, while the circular coordinates are r = |z|, called the absolute value or modulus, and φ = arg(z), called the complex argument of z (mod-arg form). Together with Euler's formula we have :

z = x + iy = r (\cos \phi + i\sin \phi ) = r e^. \,

Additionally the notation r cis φ is sometimes used. Note that the complex argument is unique modulo 2π, that is, if any two values of the complex argument exactly differ by an integer multiple of 2π, they are considered equivalent. By simple trigonometric identities, we see that :

r_1 e^ \cdot r_2 e^ 
= r_1 r_2 e^ \,

and that :

\frac

= \frac e^. \,

Now the addition of two complex numbers is just the vector addition of two vectors, and the multiplication with a fixed complex number can be seen as a simultaneous rotation and stretching. Multiplication with i corresponds to a counter clockwise rotation by 90 degrees (

\pi/2

radians). The geometric content of the equation i² = −1 is that a sequence of two 90 degree rotations results in a 180 degree (

\pi

radians) rotation. Even the fact (−1) · (−1) = +1 from arithmetic can be understood geometrically as the combination of two 180 degree turns.

Absolute value, conjugation and distance

The absolute value (or modulus or magnitude) of a complex number z = r e^iφ is defined as |z| = r. Algebraically, if z = a + ib, then

| z | = \sqrt.

One can check readily that the absolute value has three important properties: :

| z | = 0 \,

iff

z = 0 \,

| z + w | \leq | z | + | w | \,

| z w | = | z | \; | w | \,

for all complex numbers z and w. It then follows, for example, that

| 1 | = 1

and

|z/w|=|z|/|w|

. By defining the distance function d(z, w) = |z − w| we turn the complex numbers into a metric space and we can therefore talk about limits and continuity. The addition, subtraction, multiplication and division of complex numbers are then continuous operations. Unless anything else is said, this is always the metric being used on the complex numbers. The complex conjugate of the complex number z = a + ib is defined to be a - ib, written as

\bar

z^ - \,

. As seen in the figure,

\bar

is the "reflection" of z about the real axis. The following can be checked: :

\overline = \bar + \bar

\overline = \bar\bar

\overline = \bar/\bar

\bar=z

\bar=z

iff z is real :

|z|=|\bar|

|z|^2 = z\bar

z^ = \bar|z|^

if z is non-zero. The latter formula is the method of choice to compute the inverse of a complex number if it is given in rectangular coordinates. That conjugation commutes with all the algebraic operations (and many functions; e.g.

\sin\bar z=\overline

) is rooted in the ambiguity in choice of i (−1 has two square roots); note, however, that conjugation is not differentiable (see holomorphic).

Complex number division

Given a complex number (a + ib) which is to be divided by another complex number (c + id) whose magnitude is non-zero, there are two ways to do this; in either case it is the same as multiplying the first by the multiplicative inverse of the second. The first way has already been implied: to convert both complex numbers into exponential form, from which their quotient is easy to derive. The second way is to express the division as a fraction, then to multiply both numerator and denominator by the complex conjugate of the denominator. This causes the denominator to simplify into a real number: :

=  =

:::

= \left(\right) + i\left(  \right).

Matrix representation of complex numbers

While usually not useful, alternative representations of complex fields can give some insight into their nature. One particularly elegant representation interprets every complex number as 2×2 matrix with real entries which stretches and rotates the points of the plane. Every such matrix has the form :

\begin
  a &   -b  \\
  b & \;\; a  
\end

with real numbers a and b. The sum and product of two such matrices is again of this form. Every non-zero such matrix is invertible, and its inverse is again of this form. Therefore, the matrices of this form are a field. In fact, this is exactly the field of complex numbers. Every such matrix can be written as :

\begin
  a &     -b  \\
  b & \;\; a  
\end
=
a \begin
  1 & \;\; 0  \\
  0 & \;\; 1 
\end
+
b \begin
  0 &     -1  \\
  1 & \;\; 0 
\end

which suggests that we should identify the real number 1 with the matrix :

\begin
  1 & \;\; 0  \\
  0 & \;\; 1 
\end

and the imaginary unit i with :

\begin
  0 &     -1  \\
  1 & \;\; 0  
\end

a counter-clockwise rotation by 90 degrees. Note that the square of this latter matrix is indeed equal to −1. The absolute value of a complex number expressed as a matrix is equal to the square root of the determinant of that matrix. If the matrix is viewed as a transformation of a plane, then the transformation rotates points through an angle equal to the argument of the complex number and scales by a factor equal to the complex number's absolute value. The conjugate of the complex number z corresponds to the transformation which rotates through the same angle as z but in the opposite direction, and scales in the same manner as z; this can be described by the transpose of the matrix corresponding to z. If the matrix elements are themselves complex numbers, then the resulting algebra is that of the quaternions. In this way, the matrix representation can be seen as a way of expressing the Cayley-Dickson construction of algebras.

Geometric interpretation of the operations on complex numbers

Cayley-Dickson construction Choose a point in the plane which will be the origin,

0

. Given two points A and B in the plane, their sum is the point X in the plane such that the triangles with vertices 0, A, B and X, B, A are similar. similar Choose in addition a point in the plane different from zero, which will be the unity, 1. Given two points A and B in the plane, their product is the point X in the plane such that the triangles with vertices 0, 1, A, and 0, B, X are similar. similar Given a point A in the plane, its complex conjugate is a point X in the plane such that the triangles with vertices 0, 1, A and 0, 1, X are mirror image of each other.

Some properties

Real vector space

C is a two-dimensional real vector space. Unlike the reals, complex numbers cannot be ordered in any way that is compatible with its arithmetic operations: C cannot be turned into an ordered field. R-linear maps C → C have the general form :

f(z)=az+b\overline

with complex coefficients a and b. Only the first term is C-linear; also only the first term is holomorphic; the second term is real-differentiable, but does not satisfy the Cauchy-Riemann equations. The function :

f(z)=az\,

corresponds to rotations combined with scaling, while the function :

f(z)=b\overline

corresponds to reflections combined with scaling.

Solutions of polynomial equations

A root of the polynomial p is a complex number z such that p(z) = 0. A most striking result is that all polynomials of degree n with real or complex coefficients have exactly n complex roots (counting multiple roots according to their multiplicity). This is known as the fundamental theorem of algebra, and shows that the complex numbers are an algebraically closed field. Indeed, the complex number field is the algebraic closure of the real number field, and Cauchy constructed complex numbers in this way. It can be identified as the quotient ring of the polynomial ring R[X] by the ideal generated by the polynomial X² + 1: :

\mathbb = \mathbb[ X ] / ( X^2 + 1). \,

This is indeed a field because X² + 1 is irreducible, hence generating a maximal ideal, in R[X]. The image of X in this quotient ring becomes the imaginary unit i.

Algebraic characterization

The field C is (up to field isomorphism) characterized by the following three facts:
- its characteristic is 0
- its transcendence degree over the prime field is the cardinality of the continuum
- it is algebraically closed Consequently, C contains many proper subfields which are isomorphic to C. Another consequence of this characterization is that the Galois group of C over the rational numbers is enormous, with cardinality equal to that of the power set of the continuum.

Characterization as a topological field

As noted above, the algebraic characterization of C fails to capture some of its most important properties. These properties, which underpin the foundations of complex analysis, arise from the topology of C. The following properties characterize C as a topological field:
- C is a field.
- C contains a subset P of nonzero elements satisfying:
- P is closed under addition, multiplication and taking inverses.
- If x and y are distinct elements of P, then either x-y or y-x is in P
- If S is any nonempty subset of P, then S+P=x+P for some x in C.
- C has a nontrivial involutive automorphism x->x
- , fixing P and such that xx
- is in P for any nonzero x in C. Given these properties, one can then define a topology on C by taking the sets
-

B(x,p) = \

as a base, where x ranges over C, and p ranges over P. To see that these properties characterize C as a topological field, one notes that P ∪ ∪ -P is an ordered Dedekind-complete field and thus can be identified with the real numbers R by a unique field isomorphism. The last property is easily seen to imply that the Galois group over the real numbers is of order two, completing the characterization. Pontryagin has shown that the only connected locally compact topological fields are R and C. This gives another characterization of C as a topological field, since C can be distinguished from R by noting the nonzero complex numbers are connected whereas the nonzero real numbers are not.

Complex analysis

The study of functions of a complex variable is known as complex analysis and has enormous practical use in applied mathematics as well as in other branches of mathematics. Often, the most natural proofs for statements in real analysis or even number theory employ techniques from complex analysis (see prime number theorem for an example). Unlike real functions which are commonly represented as two dimensional graphs, complex functions have four dimensional graphs and may usefully be illustrated by color coding a three dimensional graph to suggest four dimensions, or by animating the complex function's dynamic transformation of the complex plane.

Applications

Control theory

In control theory, systems are often transformed from the time domain to the frequency domain using the Laplace transform. The system's poles and zeros are then analyzed in the complex plane. The root locus, Nyquist plot, and Nichols plot techniques all make use of the complex plane. In the root locus method, it is especially important whether the poles and zeros are in the left or right half planes, i.e. have real part greater than or less than zero. If a system has poles that are
- in the right half plane, it will be unstable,
- all in the left half plane, it will be stable,
- on the imaginary axis, it will be marginally stable. If a system has zeros in the right half plane, it is a nonminimum phase system.

Signal analysis

Complex numbers are used in signal analysis and other fields as a convenient description for periodically varying signals. The absolute value |z| is interpreted as the amplitude and the argument arg(z) as the phase of a sine wave of given frequency. If Fourier analysis is employed to write a given real-valued signal as a sum of periodic functions, these periodic functions are often written as the real part of complex valued functions of the form :

f ( t ) = z e^ \,

where ω represents the angular frequency and the complex number z encodes the phase and amplitude as explained above. In electrical engineering, the Fourier transform is used to analyze varying voltages and currents. The treatment of resistors, capacitors, and inductors can then be unified by introducing imaginary, frequency-dependent resistances for the latter two and combining all three in a single complex number called the impedance. (Electrical engineers and some physicists use the letter j for the imaginary unit since i is typically reserved for varying currents and may come into conflict with i.) This use is also extended into digital signal processing and digital image processing, which utilize digital versions of Fourier analysis (and Wavelet analysis) to transmit, compress, restore, and otherwise process digital audio signals, still images, and video signals.

Improper integrals

In applied fields, the use of complex analysis is often used to compute certain real-valued improper integrals, by means of complex-valued functions. Several methods exist to do this, see methods of contour integration.

Quantum mechanics

The complex number field is also of utmost importance in quantum mechanics since the underlying theory is built on (infinite dimensional) Hilbert spaces over C.

Relativity

In special and general relativity, some formulas for the metric on spacetime become simpler if one takes the time variable to be imaginary.

Applied mathematics

In differential equations, it is common to first find all complex roots r of the characteristic equation of a linear differential equation and then attempt to solve the system in terms of base functions of the form f(t) = e^rt.

Fluid dynamics

In fluid dynamics, complex functions are used to describe potential flow in 2d.

Fractals

Certain fractals are plotted in the complex plane e.g. Mandelbrot set and Julia set.

History

The earliest fleeting reference to square roots of negative numbers occurred in the work of the Greek mathematician and inventor Heron of Alexandria in the 1st century AD, when he considered the volume of an impossible frustum of a pyramid. They became more prominent when in the 16th century closed formulas for the roots of third and fourth degree polynomials were discovered by Italian mathematicians (see Niccolo Fontana Tartaglia, Gerolamo Cardano). It was soon realized that these formulas, even if one was only interested in real solutions, sometimes required the manipulation of square roots of negative numbers. For example, Tartaglia's cubic formula gives the following solution to the equation

x^3-x=0

: :

\frac\left(\sqrt^+\frac\right).

At first glance this looks like nonsense. However formal calculations with complex numbers show that the equation

z^3=i

has solutions −i,

\frac+\fraci

and

\frac+\fraci

. Substituting these in turn for

\sqrt^

into the cubic formula and simplifying, one gets 0, 1 and -1 as the solutions of

x^3-x=0.

This was doubly unsettling since not even negative numbers were considered to be on firm ground at the time. The term "imaginary" for these quantities was coined by René Descartes in the 17th century and was meant to be derogatory (see imaginary number for a discussion of the "reality" of complex numbers). A further source of confusion was that the equation

\sqrt^2=\sqrt\sqrt=-1

seemed to be capriciously inconsistent with the algebraic identity

\sqrt\sqrt=\sqrt

, which is valid for positive real numbers a and b, and which was also used in complex number calculations with one of a, b positive and the other negative. The incorrect use of this identity (and the related identity

\frac=\sqrt

) in the case when both a and b are negative even bedeviled Euler. This difficulty eventually led to the convention of using the special symbol i in place of

\sqrt

to guard against this mistake. The 18th century saw the labors of Abraham de Moivre and Leonhard Euler. To De Moivre is due (1730) the well-known formula which bears his name, de Moivre's formula: :

(\cos \theta + i\sin \theta)^ = \cos n \theta + i\sin n \theta \,

and to Euler (1748) Euler's formula of complex analysis: :

\cos \theta + i\sin \theta = e ^. \,

The existence of complex numbers was not completely accepted until the geometrical interpretation (see below) had been described by Caspar Wessel in 1799; it was rediscovered several years later and popularized by Carl Friedrich Gauss, and as a result the theory of complex numbers received a notable expansion. The idea of the graphic representation of complex numbers had appeared, however, as early as 1685, in Wallis's De Algebra tractatus. Wessel's memoir appeared in the Proceedings of the Copenhagen Academy for 1799, and is exceedingly clear and complete, even in comparison with modern works. He also considers the sphere, and gives a quaternion theory from which he develops a complete spherical trigonometry. In 1804 the Abbé Buée independently came upon the same idea which Wallis had suggested, that

\pm\sqrt

should represent a unit line, and its negative, perpendicular to the real axis. Buée's paper was not published until 1806, in which year Jean-Robert Argand also issued a pamphlet on the same subject. It is to Argand's essay that the scientific foundation for the graphic representation of complex numbers is now generally referred. Nevertheless, in 1831 Gauss found the theory quite unknown, and in 1832 published his chief memoir on the subject, thus bringing it prominently before the mathematical world. Mention should also be made of an excellent little treatise by Mourey (1828), in which the foundations for the theory of directional numbers are scientifically laid. The general acceptance of the theory is not a little due to the labors of Augustin Louis Cauchy and Niels Henrik Abel, and especially the latter, who was the first to boldly use complex numbers with a success that is well known. The common terms used in the theory are chiefly due to the founders. Argand called

\cos \phi + i  -  \sin \phi

the direction factor, and

r = \sqrt

the modulus; Cauchy (1828) called

\cos \phi + i  - \sin \phi

the reduced form (l'expression réduite); Gauss used i for

\sqrt

, introduced the term complex number for

a+bi

, and called

a^2+b^2

the norm. The expression direction coefficient, often used for

\cos \phi + i - 
\sin \phi

, is due to Hankel (1867), and absolute value, for modulus, is due to Weierstrass. Following Cauchy and Gauss have come a number of contributors of high rank, of whom the following may be especially mentioned: Kummer (1844), Leopold Kronecker (1845), Scheffler (1845, 1851, 1880), Bellavitis (1835, 1852), Peacock (1845), and De Morgan (1849). Möbius must also be mentioned for his numerous memoirs on the geometric applications of complex numbers, and Dirichlet for the expansion of the theory to include primes, congruences, reciprocity, etc., as in the case of real numbers. A complex ring or field is a set of complex numbers which is closed under addition, subtraction, and multiplication. Gauss studied complex numbers of the form

a + bi

, where a and b are integral, or rational (and i is the root of

x^2 + 1 = 0

). His student, Ferdinand Eisenstein, studied the type

a + b\omega

, where

\omega

is a complex root of

x^3 - 1 = 0

. Other such classes (called cyclotomic fields) of complex numbers are derived from the roots of unity

x^k - 1 = 0

for higher values of

k

. This generalization is largely due to Kummer, who also invented ideal numbers, which were expressed as geometrical entities by Felix Klein in 1893. The general theory of fields was created by Évariste Galois, who studied the fields generated by the roots of any polynomial equation :

\ F(x) = 0

The late writers (from 1884) on the general theory include Weierstrass, Schwarz, Richard Dedekind, Otto Hölder, Berloty, Henri Poincaré, Eduard Study, and Alexander MacFarlane. The formally correct definition using pairs of real numbers was given in the 19th century.

External links

- Complex numbers at Wikibooks
- [http://mathforum.org/johnandbetty/ John and Betty's Journey Through Complex Numbers]
- [http://mathworld.wolfram.com/ComplexNumber.html Complex Number from MathWorld]
- [http://www.sosmath.com/complex/complex.html SOS Math - Complex Variables]
- [http://www.binarythings.com/hidigit/ Windows calculator that supports complex numbers] Category:Complex numbers Category:Elementary mathematics ko:복소수 ja:複素数 nb:Komplekst tall th:จำนวนเชิงซ้อน

Additive function

In number theory, an additive function is an arithmetic function f(n) of the positive integer n such that whenever a and b are coprime we have: :f(ab) = f(a) + f(b).

Completely additive

Outside number theory, the term additive is usually used for all functions with the property f(ab) = f(a) + f(b) for all arguments a and b. This article discusses number theoretic additive functions. An additive function f(n) is said to be completely additive if f(ab) = f(a) + f(b) holds for all positive integers a and b, even when they are not coprime. Every completely additive function is additive, but not vice versa.

Examples

Arithmetic functions which are completely additive are:
- The restriction of the logarithmic function to N, a₀(n) - the sum of primes dividing n, sometimes called sopfr(n). We have a₀(20) = a₀(2² · 5) = 2 + 2+ 5 = 9. Some values: ([http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001414 SIDN A001414]). ::a₀(4) = 4 ::a₀(27) = 9 ::a₀(144) = a₀(2⁴ · 3²) = a₀(2⁴) + a₀(3²) = 8 + 6 = 14 ::a₀(2,000) = a₀(2⁴ · 5³) = a₀(2⁴) + a₀(5³) = 8 + 15 = 23 ::a₀(2,003) = 2003 ::a₀(54,032,858,972,279) = 1240658 ::a₀(54,032,858,972,302) = 1780417 ::a₀(20,802,650,704,327,415) = 1240681 :: ...
- a₁(n) - the sum of the distinct primes dividing n, sometimes called sopf(n). We have a₁(1) = 0, a₁(20) = 2 + 5 = 7. Some more values: ([http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A008472 SIDN A008472]) ::a₁(4) = 2 ::a₁(27) = 3 ::a₁(144) = a₁(2⁴ · 3²) = a₁(2⁴) + a₁(3²) = 2 + 3 = 5 ::a₁(2,000) = a₁(2⁴ · 5³) = a₁(2⁴) + a₁(5³) = 2 + 5 = 7 ::a₁(2,001) = 55 ::a₁(2,002) = 33 ::a₁(2,003) = 2003 ::a₁(54,032,858,972,279) = 1238665 ::a₁(54,032,858,972,302) = 1780410 ::a₁(20,802,650,704,327,415) = 1238677 :: ...
- The function Ω(n), defined as the total number of prime factors of n, counting multiple factors multiple times. This implies Ω(1) = 0 since 1 has no prime factors. Some more values: ([http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001222 SIDN A001222]) ::Ω(4) = 2 ::Ω(27) = 3 ::Ω(144) = Ω(2⁴ · 3²) = Ω(2⁴) + Ω(3²) = 4 + 2 = 6 ::Ω(2,000) = Ω(2⁴ · 5³) = Ω(2⁴) + Ω(5³) = 4 + 3 = 7 ::Ω(2,001) = 3 ::Ω(2,002) = 4 ::Ω(2,003) = 1 ::Ω(54,032,858,972,279) = 3 ::Ω(54,032,858,972,302) = 6 ::Ω(20,802,650,704,327,415) = 7 :: ...
- An example of an arithmetic function which is additive but not completely additive is ω(n), defined as the total number of different prime factors of n. Some values (compare with Ω(n)) ([http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001221 SIDN A001221]) : ::ω(4) = 1 ::ω(27) = 1 ::ω(144) = ω(2⁴ · 3²) = ω(2⁴) + ω(3²) = 1 + 1 = 2 ::ω(2,000) = ω(2⁴ · 5³) = ω(2⁴) + ω(5³) = 1 + 1 = 2 ::ω(2,001) = 3 ::ω(2,002) = 4 ::ω(2,003) = 1 ::ω(54,032,858,972,279) = 3 ::ω(54,032,858,972,302) = 5 ::ω(20,802,650,704,327,415) = 5 :: ...

Multiplicative functions

From any additive function f(n) it is easy to create a related multiplicative function g(n) i.e. with the property that whenever a and b are coprime we have: :g(ab) = g(a) × g(b). One such example is g(n) = 2^f(n).

References

# Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp 97 - 108) (MSC (2000) 11A25)

Multiplicative function

In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then :f(ab) = f(a) f(b). An arithmetic function f(n) is said to be completely (totally) multiplicative if f(1) = 1 and f(ab) = f(a) f(b) holds for all positive integers a and b, even when they are not coprime. Outside number theory, the term multiplicative is usually used for functions with the property f(ab) = f(a) f(b) for all arguments a and b; this requires either f(1) = 1, or f(a) = 0 for all a except a = 1. This article discusses number theoretic multiplicative functions.

Examples

Examples of multiplicative functions include many functions of importance in number theory, such as:
-

\phi

(n): Euler's totient function

\phi

, counting the positive integers coprime to (but not bigger than) n
-

\mu

(n): the Möbius function, related to the number of prime factors of square-free numbers
- gcd(n,k): the greatest common divisor of n and k, where k is a fixed integer.
- d(n): the number of positive divisors of n,
-

\sigma

(n): the sum of all the positive divisors of n,
-

\sigma

_k(n): the divisor function, which is the sum of the k-th powers of all the positive divisors of n (where k may be any complex number). In special cases we have
-

\sigma

₀(n) = d(n) and
-

\sigma

₁(n) =

\sigma

(n),
- 1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
- Id(n): identity function, defined by Id(n) = n (completely multiplicative)
- Id_k(n): the power functions, defined by Id_k(n) = n^k for any natural (or even complex) number k (completely multiplicative). As special cases we have
- Id₀(n) = 1(n) and
- Id₁(n) = Id(n),
-

\epsilon

(n): the function defined by

\epsilon

(n) = 1 if n = 1 and = 0 if n > 1, sometimes called multiplication unit for Dirichlet convolution or simply the unit function; sometimes written as u(n), not to be confused with

\mu

(n) (completely multiplicative).
- (n/p), the Legendre symbol, where p is a fixed prime number (completely multiplicative).
-

\lambda

(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
-

\gamma

(n), defined by

\gamma

(n)=(-1)^{$\omega$ (n)}, where the additive function

\omega

(n) is the number of distinct primes dividing n.
- All Dirichlet characters are completely multiplicative functions. An example of a non-multiplicative function is the arithmetic function r₂(n) - the number of representations of n as a sum of squares of two integers, positive, negative, or zero, where in counting the number of ways, reversal of order is allowed. For example: :1 = 1² + 0² = (-1)² + 0² = 0² + 1² = 0² + (-1)² and therefore r₂(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r₂(n)/4 is multiplicative. In the On-Line Encyclopedia of Integer Sequences, sequences of values of a multiplicative function have the keyword "mult." See arithmetic function for some other examples of non-multiplicative functions.

Properties

A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if n is a product of powers of distinct primes, say n = p^a q^b ..., then f(n) = f(p^a) f(q^b) ... This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 2⁴ · 3²: : d(144) =

\sigma

₀(144) =

\sigma

₀(2⁴)

\sigma

₀(3²) = (1⁰ + 2⁰ + 4⁰ + 8⁰ + 16⁰)(1⁰ + 3⁰ + 9⁰) = 5 · 3 = 15, :

\sigma

(144) =

\sigma

₁(144) =

\sigma

₁(2⁴)

\sigma

₁(3²) = (1¹ + 2¹ + 4¹ + 8¹ + 16¹)(1¹ + 3¹ + 9¹) = 31 · 13 = 403, :

\sigma

^-(144) =

\sigma

^-(2⁴)

\sigma

^-(3²) = (1¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170. Similarly, we have: :

\phi

(144)=

\phi

(2⁴)

\phi

(3²) = 8 · 6 = 48 In general, if f(n) is a multiplicative function and a, b are any two positive integers, then :f(a) · f(b) = f(gcd(a,b)) · f(lcm(a,b)). Every completely multiplicative function is a homomorphism of monoids and is completely determined by its restriction to the prime numbers.

Convolution

If f and g are two multiplicative functions, one defines a new multiplicative function f
- g, the Dirichlet convolution of f and g, by :(f
- g)(n) = ∑_{d |n} f(d)g(n/d) where the sum extends over all positive divisors d of n. With this operation, the set of all multiplicative functions turns into an abelian group; the identity element is

\epsilon

. Relations among the multiplicative functions discussed above include:
-

\epsilon

\mu

- 1 (the Möbius inversion formula)
-

\phi

\mu

- Id
- d = 1
- 1
-

\sigma

= Id
- 1 =

\phi

- d
-

\sigma

_k = Id_k
- 1
- Id =

\phi

- 1 =

\sigma

\mu

- Id_k =

\sigma

_k
-

\mu

The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the Dirichlet ring.

References

- Tom M.Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. ISBN 0-387-90163-9 (See Chapter 2.)
- ko:곱셈적 함수

Bell series

In mathematics, the Bell series is a formal power series used to study properties of multiplicative arithmetical functions. Bell series were introduced and developed by Eric Temple Bell. Given an arithmetic function

f

and a prime

p

, define the formal power series

f_p(x)

, called the Bell series of

f

modulo

p

as :

f_p(x)=\sum_^\infty f(p^n)x^n.

Uniqueness theorem. Given multiplicative functions

f

and

g

, one has

f=g

if and only if :

f_p(x)=g_p(x)

for all primes

p

. Multiplication theorem: For any two arithmetic functions

f

and

g

, let

h=f - g

be their Dirichlet convolution. Then for every prime

p

, one has :

h_p(x)=f_p(x) g_p(x).\,

In particular, this makes it trivial to find the Bell series of a Dirichlet inverse. If

f

is completely multiplicative, then :

f_p(x)=\frac.

Examples

The following is a table of the Bell series of well-known arithmetic functions.
- The Moebius function

\mu

has

\mu_p(x)=1-x.

- Euler's Totient

\phi

has

\phi_p(x)=\frac.

- The identity function

I

has

I_p(x)=1.

- The Liouville function

\lambda

has

\lambda_p(x)=\frac.

- The power function Id_k has

(\textrm_k)_p(x)=\frac.

- The divisor function

\sigma_k

has

(\sigma_k)_p(x)=\frac.

References

- Tom M. Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York Category:Arithmetic functions Category:Mathematical series

Prime number theorem

In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. Roughly speaking, the prime number theorem states that if you randomly select a number nearby some large number N, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. This means that the prime numbers "thin out" as one looks at larger and larger numbers, and the prime number theorem gives a precise description of exactly how much they thin out.

Statement of the theorem

Let π(x) be the prime counting function that gives the number of primes less than or equal to x, for any real number x. For example, π(10) = 4 because there are four prime numbers (2, 3, 5 and 7) less than or equal to 10. The prime number theorem then states that the limit of the quotient of the two functions π(x) and x / ln(x) as x approaches infinity is 1. Using Landau notation this result can be written as :

\pi(x)\sim\frac

. This does not mean that the limit of the difference of the two functions as x approaches infinity is zero. Based on the tables by Anton Felkel and Jurij Vega, the theorem was conjectured by Adrien-Marie Legendre in 1798 and proved independently by Hadamard and de la Vallée Poussin in 1896. The proof used methods from complex analysis, specifically the Riemann zeta function.

The prime counting function in terms of the logarithmic integral

Gauss conjectured that an even better approximation to π(x) is given by the offset logarithmic integral function Li(x), defined by :

\mbox(x) = \int_2^x \frac1 \,\mboxt.

This function is related to the logarithm by :

\mbox(x) = \frac \sum_^\infty \frac 
= \frac + \frac + \frac + \cdots

So, the prime number theorem can also be written as π(x) ~ Li(x). The advantage of this formulation is that the error term is less. In fact, it follows from the proof of Hadamard and de la Vallée Poussin that :

\pi(x)= (x) + O \left(x \mathrm^\right) \quad\mbox x \to \infty

for some positive constant a, where O(…) is the big O notation. This has been improved to :

\pi(x)= (x) + O \left(x \, \exp \left( -\frac \right) \right).

Because of the connection between the Riemann zeta function and π(x), the Riemann hypothesis has considerable importance in number theory: if established, it would yield a far better estimate of the error involved in the prime number theorem than is available today. More specifically, Helge von Koch showed in 1901 that, if and only if the Riemann hypothesis is true, the error term in the above relation can be improved to :

\pi(x) =  (x) + O\left(\sqrt x \ln x\right).

The constant involved in the remainder term is unknown. The logarithmic integral Li(x) is larger than π(x) for "small" values of x. However, in 1914, J. E. Littlewood proved that this is not always the case. The first value of x where π(x) exceeds Li(x) is around x = 10³¹⁶; see the article on Skewes' number for more details.

The issue of "depth"

In the first half of the twentieth century, some mathematicians felt that there exists a hierarchy of techniques in mathematics, and that the prime number theorem is a "deep" theorem, whose proof requires complex analysis. Methods with only real variables were supposed to be inadequate. G. H. Hardy was one notable member of this group. The formulation of this belief was somewhat shaken by a proof of the prime number theorem based on Wiener's tauberian theorem, though this could be circumvented by awarding Wiener's theorem "depth" itself equivalent to the complex methods. However, Paul Erdős and Atle Selberg found a so-called "elementary" proof of the prime number theorem in 1949, which uses only number-theoretic means. The Selberg-Erdős work effectively laid rest to the whole concept of "depth", showing that technically "elementary" methods (in other words combinatorics) were sharper than previously expected. Subsequent development of sieve methods showed they had a definite role in prime number theory.

The prime number theorem for arithmetic progressions

Let

\pi_(x)

denote the number of primes in the arithmetic progression n, n + a, n + 2a, n + 3a, … less than x. Dirichlet and Legendre conjectured, and Vallée Poussin proved, that, if n and a are coprime, then :

\pi_(x) \sim \frac\mathrm(x),

where φ(·) is the Euler's totient function. In other words, the primes are distributed evenly among the residue classes [a] modulo n with gcd(a, n) = 1.

Bounds on the prime counting function

The prime number theorem is an asymptotic result. Hence, it cannot be used to bound π(x). However, some bounds on π(x) are known, for instance :

\frac < \pi(x) < 1.25506 \, \frac.

The first inequality holds for all x ≥ 17 and the second one for x > 1. Another useful bound is :

\frac  < \pi(x) < \frac  \quad\mbox x \ge 55.

Approximations for the nth prime number

As a consequence of the prime number theorem, one gets an asymptotic expression for the nth prime number, denoted by p_n: :

p_n \sim n \ln n.

A better approximation is :

p_n = n \ln n +  n \ln \ln n + \frac \big( \ln \ln n - \ln n- 2 \big) 
+ O\left( \frac  \right).

Rosser's theorem states that p_n is larger than n ln n. This can be improved by the following pair of bounds: :

n \ln n + n\ln\ln n - n  < p_n <  n \ln n + n \ln \ln n \quad\mbox n \ge 6.

The left inequality is due to Pierre Dusart (1999) and is valid for n ≥ 2.

Gaps between primes

The prime number theorem says that the "average" length of the gap between a prime p and the next prime is ln p. Of course, the actual length of the gap might be much more or less than this. For instance, the gap between a pair of twin primes contains only one number. On the other hand, the error term in the prime number theorem implies an upper bound on the length of a gap: for every ε > 0, there is a number q such that the gap is smaller than εp for all primes p larger than q. This result has been improved steadily. Baker et al. (2001) proved that gap is at most p^0.525 for sufficiently large p. Even better results are possible if it is assumed that the Riemann hypothesis is true. Harald Cramér proved that, under this assumption, the gap g(p) satisfies :

g(p) = O(\sqrt \ln p).

Later, he conjectured that the gaps are even smaller, namely :

g(p) = O\left((\ln x)^2\right).

At the moment, the numerical evidence seems to point in this direction. See Cramér's conjecture for more details.

Table of π(x), x / ln x, and Li(x)

Here is a table that shows how the three functions π(x), x / ln x and Li(x) compare: : The first column is sequence [http://www.research.att.com/projects/OEIS?Anum=A006880 A006880] in OEIS; the second column is sequence [http://www.research.att.com/projects/OEIS?Anum=A057835 A057835]; and the third column is sequence [http://www.research.att.com/projects/OEIS?Anum=A057752 A057752].

Analogue for irreducible polynomials over a finite field

There is an analogue of the prime number theorem that describes the "distribution" of irreducible polynomials over a finite field; the form it takes is strikingly similar to the case of the classical prime number theorem. To state it precisely, let F = GF(q) be the finite field with q elements, for some fixed q, and let N_n be the number of monic irreducible polynomials over F whose degree is equal to n. That is, we are looking at polynomials with coefficients chosen from F, which cannot be written as products of polynomials of smaller degree. In this setting, these polynomials play the role of the prime numbers, since all other monic polynomials are built up of products of them. One can then prove that :

N_n \sim \frac.

If we make the substitution x = qⁿ, then the right hand side is just :

\frac,

which makes the analogy clearer. Since there are precisely qⁿ monic polynomials of degree n (including the reducible ones), this can be rephrased as follows: if you select a monic polynomial of degree n randomly, then the probability of it being irreducible is about 1/n. One can even prove an analogue of the Riemann hypothesis, namely that :

N_n = \fracn + O\left(\frac\right).

The proofs of these statements are far simpler than in the classical case. It involves a short combinatorial argument, summarised as follows. Every element of the degree n extension of F is a root of some irreducible polynomial whose degree d divides n; by counting these roots in two different ways one establishes that :

q^n = \sum_ d N_d,

where the sum is over all divisors d of n. Mobius inversion then yields :

N_n = \frac1n \sum_ \mu(n/d) q^d,

where μ(k) is the Mobius function. The main term occurs for d = n, and it is not difficult to bound the remaining terms. The "Riemann hypothesis" statement depends on the fact that the largest proper divisor of n can be no larger than n/2.

References

- Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 233 in section 8.8.
- R. C. Baker, G. Harman, G. and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society, vol. 83, pages 532–562, 2001.
- Andrew Granville, [http://www.dms.umontreal.ca/~andrew/Postscript/cramer Harald Cramér and the distribution of prime numbers], Scandanavian Actuarial Journal, vol. 1, pages 12–28, 1995.
- Donald Knuth, The Art of Computer Programming, volume 2, section 4.5.4, exercise 36, ISBN 0-201-89684-2.
- Ivan Soprounov, [http://www.math.umass.edu/~isoprou/pdf/primes.pdf A Short Proof of the Prime Number Theorem for Arithetic Progressions], 1998.

External links

- [http://www.scs.uiuc.edu/~mainzv/exhibitmath/exhibit/felkel.htm Table of Primes by Anton Felkel].
- [http://mathworld.wolfram.com/PrimeFormulas.html Prime formulas] and [http://mathworld.wolfram.com/PrimeNumberTheorem.html Prime number theorem] at MathWorld.
-
- [http://primes.utm.edu/howmany.shtml How Many Primes Are There?] and [http://primes.utm.edu/notes/gaps.html The Gaps between Primes] by Chris Caldwell, University of Tennessee at Martin. Category:Analytic number theory Category:Prime numbers Category:Mathematical theorems ja:素数定理

Von Mangoldt function

The von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. The von Mangoldt function, conventionally written as Λ(n), is defined as :

\Lambda(n) = \begin \ln p & \mboxn=p^k \mbox p \mbox k \ge 1 \\ 0 & \mbox \end

It is an example of an important arithmetic function that is neither multiplicative nor additive. The von Mangoldt function satisfies the identity :

\ln n  = \sum_ \Lambda(n),\,

that is, the sum is taken over all integers d which divide n. The summatory von Mangoldt function, ψ(x), also known as the Chebyshev function, is defined as :

\psi(x) = \sum_ \Lambda(n).

von Mangoldt provided a rigorous proof of an explicit formula for ψ(x) involving a sum over the non-trivial zeros of the Riemann zeta function. This was an important part of the first proof of the prime number theorem. The Riemann zeta function may be expressed in terms of the von Mangoldt function by (see Allan Gut reference): :

\zeta(\sigma+it)=\exp\left\

for

\sigma > 1

References

- Allan Gut, [http://www.math.uu.se/research/pub/Gut10.pdf Some remarks on the Riemann zeta distribution] Category:Arithmetic functions

Category:Arithmetic functions

Category:Number theory

Template:MLS team

pozycjonowanie stron Casino Hotele w Rzym penisy sprzet

k-little code archiwum allegro bicomet archiwum aukcji Przewóz osób ciecie layoutow kredyty bez zaświadczeń Kredyt Lukas Bank

:: RELATED NEWS ::

Xanh thủy tinh
Màu xanh thủy tinh là màu xanh lam sẫm. Tuy nhiên, nó cũng có thể chỉ tới các biến thể nhạt hơn của màu xanh lam, có lẽ là do kết quả của sự mập mờ về nguồn gốc của từ này.

Tọa độ màu

Số Hex = #993366 RGB (r, g, b) = (0, 51, 153) CMYK (c, m, y, k) = (100, 80, 40, 0) <

Arithmetic function

Examples

Number theory

Fields

Elementary number theory

Analytic number theory

Algebraic number theory

Geometric number theory

Combinatorial number theory

Computational number theory

History

Early history

Beginnings of a systematic theory

Prime number theory

Nineteenth-century developments

Quotations

References

External links

Function (mathematics)

Intuitive introduction

History

Formal definition

Integer

Algebraic properties

Order-theoretic properties

Integers in computing

Quotations

External links

Complex number

Definition

The complex number field

The complex plane

Absolute value, conjugation and distance

Complex number division

Matrix representation of complex numbers

Geometric interpretation of the operations on complex numbers

Some properties

Real vector space

Solutions of polynomial equations

Algebraic characterization

Characterization as a topological field

Complex analysis

Applications

Control theory

Signal analysis

Improper integrals

Quantum mechanics

Relativity

Applied mathematics

Fluid dynamics

Fractals

History

See also

Further reading

External links

Additive function

Completely additive

Examples

Multiplicative functions

References

See also

Multiplicative function

Examples

Properties

Convolution

See also

References

Bell series

Examples

References

Prime number theorem

Statement of the theorem

The prime counting function in terms of the logarithmic integral

The issue of "depth"

The prime number theorem for arithmetic progressions

Bounds on the prime counting function

Approximations for the nth prime number

Gaps between primes

Table of π(x), x / ln x, and Li(x)

Analogue for irreducible polynomials over a finite field