time to find solutions). This question is usually written:
P = NP?
See also POLYNOMIAL TIME.
n th root of unity Any COMPLEX NUMBER z such that
z
n = 1 is called an nth root of unity. When n is 2 or 3,
the relevant roots are usually called square roots and
cube roots, respectively. There are two square roots of
unity, namely, z = 1 and z = –1, and there are three cube
roots of unity: z = 1,
, and
. In
general, as the FUNDAMENTAL THEOREM OF ALGEBRA
shows, there are n nth roots of unity. The number z = 1
is an nth root of unity for all values of n.
EULER’S THEOREM shows that the nth roots of
unity are given by the formula:
for k = 0,1,…,n (since z
n =
= e
i2πk = cos(2πk)
+ isin (2πk) = 1 + 0 = 1). This shows that the n nth
roots of unity all lie on a circle of radius one and are
equidistant along that circle at angles that are multiples
of
. That is, when plotted on the complex plane, the
n nth roots of unity lie at the vertices of a regular ngon
with the point z = 1 on the real axis as one vertex of
the polygon.
An nth root of unity z is called a primitive if z
n = 1,
but z
k
≠ 1 for any positive integer smaller than n. For
example, although z = –1 is a fourth root of unity, it is
not a primitive root, since we also have (–1)
2 = 1. The
numbers z = i and z = –i are both primitive fourth roots
of unity.
An nth root of unity z satisfies the equation z
n – 1
= 0. Factoring yields:
(z – 1)(1 + z + z
2 + z
3 +…+ z
n–1
) = 0
If z is different from 1, then it must be the case that the
second term of the left side of this expression is zero.
This proves:
Each nth root of unity different from 1 satisfies
1 + z + z
2 + z
3 +…+ z
n–1 = 0.
Taking n = 5, for example, and EQUATING REAL AND
IMAGINARY PARTS, this shows, for instance, that:
and
n-tuple (list) A set of n objects taken in a particular
order is called an n-tuple. An n-tuple of numbers a 1 , a 2 ,
…, a n , in that order, is usually denoted (a 1 ,a 2 ,…,a n ) or
〈a 1 ,a 2 ,…,a n 〉. Two n-tuples (a 1 ,a 2 ,…,a n ) and (b 1 ,b 2 ,…,b n )
are equal if, and only if, corresponding entries match:
a 1 = b 1 , a 2 = b 2 ,…, a n = b n . Thus, for instance, (2,1.3)
and (1,2,3) are distinct 3-tuples.
A 3-tuple is called a “triple,” and a 4-tuple a
“quadruple.” When n = 2, an n-tuple is called an
ordered pair.
An n-tuple of numbers can represent a point in ndimensional space, a finite SEQUENCE, or, if angled
brackets are used, an n-dimensional VECTOR. An
ordered PARTITION of a number N is an n-tuple of
numbers whose entries sum to N.
See also ORDERED SET.
number The development of different types of numbers can be seen as motivated by the need for solving
different types of equations. For example, the counting
numbers (that is, the NATURAL NUMBERS N) suffice for
solving any equation of the type x + 2 = 5, for instance,
but not an equation of the type x + 5 = 2. (There is no
solution to this equation within the set of counting
numbers.) This motivates the introduction of NEGATIVE
NUMBERS and the construction of the INTEGERS Z. But
this set is not always sufficient for solving equations of
the type 5x = 3, for instance. Desiring solutions to
equations of this type leads to the construction of
FRACTIONs and the set of all RATIONAL NUMBERS Q.
Unfortunately, again, not all equations can be solved
within this system. For example, the equation x
2 –2 = 0
has no rational solution. Extending the set of rational
numbers to include solutions to equations of this type
introduces IRRATIONAL NUMBERS and the construction
of the REAL NUMBER system R. Yet this new system also
does not suffice for solving all equations. With the
introduction of a single additional number, denoted i,
sin
sin
sin
sin
sin
0
2
5
4
5
6
5
8
5
0
( ) +
+
+
+
=
π
π
π
π
cos
cos
cos
cos
cos
0
2
5
4
5
6
5
8
5
0
( ) +
+
+
+
=
π
π
π
π
2π
– n
( )
e
i n
n
2πκ
z e
n
k i
n
k
i n
=
=
+
2
2
2
πκ
π
π
cos
sin
z
i
=
− −
1
3
2
z
i
=
− +
1
3
2
358 nth root of unity
P = NP?
See also POLYNOMIAL TIME.
n th root of unity Any COMPLEX NUMBER z such that
z
n = 1 is called an nth root of unity. When n is 2 or 3,
the relevant roots are usually called square roots and
cube roots, respectively. There are two square roots of
unity, namely, z = 1 and z = –1, and there are three cube
roots of unity: z = 1,
, and
. In
general, as the FUNDAMENTAL THEOREM OF ALGEBRA
shows, there are n nth roots of unity. The number z = 1
is an nth root of unity for all values of n.
EULER’S THEOREM shows that the nth roots of
unity are given by the formula:
for k = 0,1,…,n (since z
n =
= e
i2πk = cos(2πk)
+ isin (2πk) = 1 + 0 = 1). This shows that the n nth
roots of unity all lie on a circle of radius one and are
equidistant along that circle at angles that are multiples
of
. That is, when plotted on the complex plane, the
n nth roots of unity lie at the vertices of a regular ngon
with the point z = 1 on the real axis as one vertex of
the polygon.
An nth root of unity z is called a primitive if z
n = 1,
but z
k
≠ 1 for any positive integer smaller than n. For
example, although z = –1 is a fourth root of unity, it is
not a primitive root, since we also have (–1)
2 = 1. The
numbers z = i and z = –i are both primitive fourth roots
of unity.
An nth root of unity z satisfies the equation z
n – 1
= 0. Factoring yields:
(z – 1)(1 + z + z
2 + z
3 +…+ z
n–1
) = 0
If z is different from 1, then it must be the case that the
second term of the left side of this expression is zero.
This proves:
Each nth root of unity different from 1 satisfies
1 + z + z
2 + z
3 +…+ z
n–1 = 0.
Taking n = 5, for example, and EQUATING REAL AND
IMAGINARY PARTS, this shows, for instance, that:
and
n-tuple (list) A set of n objects taken in a particular
order is called an n-tuple. An n-tuple of numbers a 1 , a 2 ,
…, a n , in that order, is usually denoted (a 1 ,a 2 ,…,a n ) or
〈a 1 ,a 2 ,…,a n 〉. Two n-tuples (a 1 ,a 2 ,…,a n ) and (b 1 ,b 2 ,…,b n )
are equal if, and only if, corresponding entries match:
a 1 = b 1 , a 2 = b 2 ,…, a n = b n . Thus, for instance, (2,1.3)
and (1,2,3) are distinct 3-tuples.
A 3-tuple is called a “triple,” and a 4-tuple a
“quadruple.” When n = 2, an n-tuple is called an
ordered pair.
An n-tuple of numbers can represent a point in ndimensional space, a finite SEQUENCE, or, if angled
brackets are used, an n-dimensional VECTOR. An
ordered PARTITION of a number N is an n-tuple of
numbers whose entries sum to N.
See also ORDERED SET.
number The development of different types of numbers can be seen as motivated by the need for solving
different types of equations. For example, the counting
numbers (that is, the NATURAL NUMBERS N) suffice for
solving any equation of the type x + 2 = 5, for instance,
but not an equation of the type x + 5 = 2. (There is no
solution to this equation within the set of counting
numbers.) This motivates the introduction of NEGATIVE
NUMBERS and the construction of the INTEGERS Z. But
this set is not always sufficient for solving equations of
the type 5x = 3, for instance. Desiring solutions to
equations of this type leads to the construction of
FRACTIONs and the set of all RATIONAL NUMBERS Q.
Unfortunately, again, not all equations can be solved
within this system. For example, the equation x
2 –2 = 0
has no rational solution. Extending the set of rational
numbers to include solutions to equations of this type
introduces IRRATIONAL NUMBERS and the construction
of the REAL NUMBER system R. Yet this new system also
does not suffice for solving all equations. With the
introduction of a single additional number, denoted i,
sin
sin
sin
sin
sin
0
2
5
4
5
6
5
8
5
0
( ) +
+
+
+
=
π
π
π
π
cos
cos
cos
cos
cos
0
2
5
4
5
6
5
8
5
0
( ) +
+
+
+
=
π
π
π
π
2π
– n
( )
e
i n
n
2πκ
z e
n
k i
n
k
i n
=
=
+
2
2
2
πκ
π
π
cos
sin
z
i
=
− −
1
3
2
z
i
=
− +
1
3
2
358 nth root of unity