Crc Concise Encyclopedia Mathematics_3.pdf

Kiss Surface

Kissing Number

STEINER TRIPLE SYSTEMS of order 3 and 9 are Kirkman

triple systems with 12 = 0 and 1. Solution to KIRKMAN'S

SCHOOLGIRL PROBLEM requires construction

of a Kirk-

Kissing Number

The number of equivalent HYPERSPHERES in n-D which

can touch an equivalent HYPERSPHERE without any in-

tersections, also sometimes called the NEWTON NUM-

BER, CONTACT NUMBER, COORDINATION NUMBI~R,~~

LIGANCY. Newton correctly believed that the kissing

number in 3-D was 12, but the first proofs were not pro-

duced until the 19th century (Conway and Sloane 1993,

p. 21) by Bender (1874), Hoppe (1874), and Giinther

(1875). More concise proofs were published by Schiitte

and van der Waerden (1953) and Leech (1956). Exact

values for lattice pacbings are known for n = 1 to 9 and

n = 24 (Conway and Sloane 1992, Sloane and Nebe).

Odlyzko and Sloane (1979) found the exact value for

24-D.

man triple system of order n = 2.

Ray-Chaudhuri and Wilson (1971) showed that there ex-

ists at least one Kirkman triple system for every NON-

NEGATIVE order n. Earlier editions of Ball and Cox-

eter (1987) gave constructions of Kirkman triple systems

with 9 5 w 5 99. For n = 1, there is a single unique (up

to an isomorphism) solution, while there are 7 different

systems for n = 2 (Mulder 1917, Cole 1922, Ball and

Coxeter 1987).

see also COXETER-TOD

D LATTICE,

HERMITE

CON-

fCeferences

Nordstrand,

STANTS, HYPERSPHERE

PACKING,

LEECH LATTICE,

T. “Surfaces.”

http://www.uib.no/people/

MINKOWSKI-HLAWKA

THEOREM

nf ytn/surf aces. htm.

Kissing Circles Problem

see DESCARTES CIRCLE THEOREM, SODDY CIRCLES

References

Bender, C. “Bestimmung der grEjssten Anzahl gleich Kugeln,

welche sich auf eine Kugel von demselben Radius, wie die

iibrigen, auflegen lassen.” Archiv

Math.

Physik

(Grunert)

56, 302-306,1874.

Conway, J. H. and Sloane, N. J. A. “The Kissing Number

Problem” and ‘&Bounds on Kissing Numbers.”

51.2 and

Ch. 13 in Sphere

Packings,

Lattices,

and Groups,

2nd ed.

New York: Springer-Verlag,

pp. 21-24 and 337-339, 1993.

Kite

Klein-Be1 trami Mudel

E&l, Y.; Rains, E. M.; Sloane, N. J. A. “On Kissing Numbers

in Dimensions 32 to 128.” Electronic

J. Combinatorics

(Cohn 1994), where 4 = eirrt is the NOME, X(q) is the

ELLIPTIC LAMBDA FUNCTION

No. 1, R22, 1-5, 1998. http: //wuw. combinatorics,

erg/

Volume,5/v5iltoc,html.

Giinther,

[ 1

S. “Ein stereometrisches

Problem.”

Archiv

Math.

X(q) E k2(q) = $f

Physik 57, 209-215, 1875.

Hoppe, R. “Bemerkung

der Redaction.”

Archiv

Math.

Physik. (Grunert) 56, 307-312, 1874.

Kuperberg, G. “Average Kissing Numbers for Sphere Pack-

ings.” Preprint.

Kuperberg, G. and Schramm, 0. “Average Kissing Numbers

for Non-Congruent

&(q) is a THETA FUNCTION,

and the Ei(q) are

RAMANUJAN-EISENSTEIN

SERIES.

J(t) is GAMMA-

Sphere Packings.”

Math.

Res. Let. 1,

MODULAR.

see UZSO ELLIPTIC

LAMBDA FUNCTION,

~-FUNCTION,

339-344, 1994.

Leech, J. “The Problem of Thirteen Spheres.”

PI, RAMANUJAN-EISENSTEIN

SERIES, THETA FUNC-

Math.

Gax.

40, 22-23, 1956.

Odlyzko, A. M. and Sloane, N. J. A. “New Bounds on the

Number of Unit Spheres that Can Touch a Unit Sphere in

n Dimensions.” J. Combin. Th. A 26, 210-214, 1979.

Schiitte, K. and van der Waerden, B. L. “Das Problem der

dreizehn Kugeln.” Math. Ann. 125, 325-334, 1953.

Sloane, N. J. A. Sequence A001116/M1585 in “An On-Line

Version of the Encyclopedia of Integer Sequences.”

Sloane, N. J. A. and Nebe, G. “Table of Highest Kissing

Numbers Presently Known.”

TION

References

Borwein, J. M. and Borwein, P. B. Pi & the AGM.. A Study

Analytic

Number

Theory

and Computational

Complexity.

New York: Wiley, pp. 115 and 179, 1987.

Cohn, H. Introduction

to the Construction

of Class Fields.

New York: Dover, p. 73, 1994.

@ Weisstein,

E. W. “j-Function.”

http://uuu.astro.

http: //www.research.

att .

virginia.edu/-ewu6n/math/notebooks/jFunction+m.

corn/-njas/lattices/kiss.html.

Stewart, I. The Problems of Mathematics, 2nd ed. Oxford,

England: Oxford University Press, pp. 82-84, 1987.

Klein-Beltrami Model

The Klein-Beltrami model of HYPERBOLIC GEOMETRY

consists of an OPEN DISK in the Euclidean plane whose

open chords correspond to hyperbolic lines. Two lines I

and m are then considered parallel if their chords fail to

intersect and are PERPENDICULAR

Kite

see DIAMOND,

LOZENGE, PARALLELOGRAM,

PENROSE

TILES,QUADRILATERAL,RHOMBUS

under the following

Klarner-Rado Sequence

The thinnest sequence which contains 1, and whenever

it contains 2, also contains 22, 33 + 2, and 6~ + 3: 1, 2,

4, 5, 8, 9, 10, 14, 15, 16, 17, . . . (Sloane’s A005658).

conditions,

1. If at least one of 2 and nz is a diameter of the DISK,

they are hyperbolically

perpendicular

IFF they are

perpendicular in the Euclidean sense.

2. If neither is a diameter, 2 is perpendicular to vt IFF

the Euclidean line extending I passes through the

pole of m (defined as the point of intersection of the

tangents to the disk at the “endpoints”

References

Guy, R. K+ “Klarner-Rado

Sequences.”

SE36 in Unsolved

Problems

in Number

Theory,

2nd ed. New York: Springer-

of m).

Verlag, p. 237, 1994.

Klarner, D. A. and Rado, R. “Linear Combinations

of Sets of

There is an isomorphism between the POINCAR~ HY-

PERBOLIC DISK model and the Klein-Beltrami model.

Consider a Klein disk in Euclidean 3-space with a

SPHERE of the same radius seated atop it, tangent at the

ORIGIN. If we now project chords on the disk orthog-

onally upward onto the SPHERE'S lower HEMISPHERE,

they become arcs of CIRCLES orthogonal to the equator.

If we then stereographically project the SPHERE'S lower

HEMISPHERE back onto the plane of the Klein disk from

the north pole, the equator will map onto a disk some-

what larger than the Klein disk, and the chords of the

original Klein disk will now be arcs of CIRCLES orthog-

onal to this larger disk. That is, they will be Poincare

lines. Now we can say that two Klein lines or angles are

congruent iff their corresponding

Consecutive Integers.” Amer.

Math.

Monthly

80, 985-989,

1973.

Sloane, N. J. A. Sequence A005658/M0969 in “An On-Line

Version of the Encyclopedia of Integer Sequences.”

Klarner’s Theorem

An a x b RECTANGLE can be packed with 1 x n strips

IFF nla or nib.

see also Box-PACKING THEOREM, CONWAY PUZ-

ZLE,DE BRUIJN'S THEOREM,~LOTHOUBER-GRAATSMA

PUZZLE

References

Honsberger, R. Mathematical Gems

Math. Assoc. Amer., p. 88, 1 976,

II. Washington,

DC:

Poincark lines and an-

Klein’s

Absolute

Invariant

gles under this isomorphism

are congruent in the sense

of the Poincarh model.

see ~SO HYPERBOLIC

GEOMETRY,

POINCAR~ HYPER-

4 [l - V4) + x”(d13

J(4) = ?i? X2(q)[l - A(q)]”

P44)13

BOLIC DISK

= [Ed(

- [EGO]

Klein Bottle

Klein Quartic

991

Klein

Bottle

The image of the CROSS-CAP map of a TORUS centered

at the ORIGIN is a Klein bottle (Gray 1993, p. 249).

Any set of regions on the Klein bottle can be colored

using ss colors only (Franklin 1934, Saaty 1986).

see also CROSS-CAP, ETRUSCAN VENUS SURFACE, IDA

SURFACE, MAP COLORING M&IUS

STRIP

Aclosed NONORIENTABLE SURFACE of GENUS onehav-

ing no inside or outside. It can be physically realized

only in 4-D (since it must pass through itself without

the presence of a HOLE). Its TOPOLOGY is equivalent

to a pair of CROSS-CAPS with coinciding boundaries.

References

Dickson, S. “Klein Bottle Graphic.” http:// www .

mathsource . corn/ cgi -bin / Math Source / Applications

Graphics/3D/OZOl-801.

Franklin, P. “A Six Colour Problem.”

J. A&X%. Phys. 13,

363-369, 1934.

Geometry Center. “The Klein Bottle.”

http: //www l geom.

umn. edu/zoo/toptype/klein/.

Geometry Center. “The Klein Bottle in Four-Space.”

http : //uua , geom. umn . edu/ -banchoff

can be cut in half along its length to make two MOBIUS

STRIPS.

The above picture is an IMMERSION of the Klein bottle in

Iw3 (3-space). There is also another possible IMMERSION

called the “figure-8” IMMERSION (Geometry Center).

The equation for the usual IMMERSION is given by the

implicit equation

Klein4D.html.

Gray, A. “The Klein Bottle.” $12.4 in Modern D#erential

Geometry of Curves and Surfaces. Boca Raton, FL: CRC

Press, pp. 239-240, 1993.

Nordstrand, T. “The Famed Klein Bottle.” http: //wuw .uib .

no/people/nf ytn/kleintxt .htm.

Pappas, T. “The Moebius Strip & the Klein Bottle.” The

Joy of Mathematics. San Carlos, CA: Wide World Publ./

Tetra, pp. 44-46, 1989.

Saaty, T. L. and Kainen, P. C. The Four-Color Problem:

Assaults and Conquest. New York: Dover, p. 45, 1986.

Stewart, I. Game, Set and Math. New York: Viking Penguin,

1991.

Wang, P. “Renderings .” http://www.ugcs.caltech.edu/

-peterw/portfolio/rsnderings/.

/Klein4D/

(x” + y2 + z2 + 2y - l)[(z” + y2 + z2 - 2y - l>” - 8z2]

+162z(z2 + y2 + x2 - 2y - 1) = 0 (1)

(Stewart 1991), Nordstrand

gives the parametric

form

x = cos u[cos( $u)(Jz + cos w) + sin( +) sinu cos v]

(2)

Klein’s Equation

If a REAL curve has no singularities except nodes and

CUSPS, &TANGENTS, and INFLECTION POINTS, then

y = sinu[cos(+u)(fi

+ cos w) + sin( $u) sin wcos w]

(3)

z = -sin(+)(JZ+

cosw) + cos(+) sinvcosv.

(4)

where n is the order, r’ is the number of conjugate tan-

gents, L’ is the number of REAL inflections, TTCis the

class, S’ is the number of REAL conjugate points, and

IG’ is the number of REAL CUSPS. This is also called

KLEIN'S THEOREM.

see UZSO PL~~CKER'S EQUATION

References

Coolidge, J. L. A Treatise

on Algebraic

Plane Curves. New

York: Dover, p. 114, 1959.

The “figure-8” form of the Klein bottle is obtained by

rotating a figure eight about an axis while placing a twist

in it, and is given by parametric

equations

Klein Four-Group

see VIERGRUPPE

x(u, w) = [a + cos( +) sin(w) - sin( +) sin(2w)] cos(u)

Klein-Gordon

Equation

(5)

----

c2 at2 - ax2

a2$

- P2*-

y(u, w) = [a + cos( $L) sin(w) - sin( $u) sin(2w)] sin(u)

(6)

see UZSO SINE-GORDON EQUATION, WAVE EQUATION

4% 4 = sin( +) sin(w) + cos( +u) sin(2w)

(7)

for u E [O, 2~), w E [0,2x), and a > 2 (Gray 1993).

Klein Quartic

The 3-holed TORUS.

1 d2$

992

Klein’s Theorem

Knights Problem

Klein’s Theorem

see KLEIN’S EQUATION

Knapsack Problem

Given a SUM and a set of WEIGHTS, find the WEIGHTS

which were used to generate the SUM. The values of

the weights are then encrypted in the sum. The system

relies on the existence of a class of knapsack problems

which can be solved trivially (those in which the weights

are separated such that they can be “peeled off” one at

a time using a GREEDY-like algorithm), and transfor-

mations which convert the trivial problem to a difficult

one and vice versa. Modular multiplication is used as

the TRAPDOOR FUNCTION. The simple knapsack sys-

tem was broken by Shamir in 1982, the Graham-Shamir

system by Adleman, and the iterated knapsack by Ernie

Brickell in 1984.

Kleinian Group

A finitely generated discontinuous

group of linear frac-

tional transformation

acting on a domain in the COM-

PLEX PLANE.

References

Iyanaga, S. and Kawada, Y. (Eds.). Encyclopedic

Dictionary

of Mathematics.

Cambridge, MA: MIT Press, p. 425, 1980.

Kra, I. Automorphic

Forms

and Kleinian

Groups.

Reading,

MA: W. A. Benjamin, 1972.

Kloosterman’s

Sum

+ vi;.> 9

(1)

S(u, v, n) E

2&h

References

Coppersmith,

D. “Knapsack

Used in Factoring.”

$4.6 in

Open Problems

in Communication

and Computation

(Ed.

[

T. M. Cover and B. Gopinath).

New York: Springer-

Verlag, pp. 117-119, 1987.

Honsberger,

where h runs through a complete set of residues RELA-

TIVELY PRIME to n, and h is defined by

R. Mathematical

Gems III. Washington,

DC:

Math. Assoc. Amer., pp. 163-166, 1985.

hE E 1 (mod n) .

(2)

Kneser-Sommerfeld Formula

Let JV bea BESSEL FUNCTION OFTHEFIRST KIND&

a NEUMANN FUNCTION, and &the zeros of z-V,(z) in

order of ascending REAL PART. Then for 0 < x < X < 1

and !@[z] > 0,

If (n,n’) = 1 (if n and n’ are RELATIVELY PRIME), then

S(u,u,n)S(u,v’,n’)

= S(~,vn’~ + vtn2,nnf).

(3)

Kloosterman’s sum essentially solves the problem intro-

duced by Ramanujan of representing sufficiently large

numbers by QUADRATIC FORMS atc12 + bx22 +cxs2 +

dxd2. Weil improved on Kloosterman’s estimate for Ra-

manujan’s problem with the best possible estimate

~[J,(z)Nv(Xz)

- N,(z)Jv(Xz)]

Jv (jv& Jv (j,,,X)

n=l ( z2 - jvn2

, ) J&n2(jv,n) ’

S(u, u, n>l =c26

References

Iyanaga, S. and Kawada, Y. (Eds.). Encyclopedic

Dictionary

(Duke 1997).

see also GAUSSIAN

of Mathematics.

Cambridge, MA: MIT Press, p. 1474,

1980.

SUM

References

Knights

Problem

Duke, W* “Some Old Problems and New Results about Quad-

ratic Forms.” Not. Amer. Math. Sot. 44, 190-196, 1997.

Hardy, G. H. and Wright, E. M. An Introduction

to the Z’he-

ory of Numbers,

5th ed. Oxford, England: Clarendon

Press, p. 56, 1979.

Katz, N. M. Gauss Sums, Kloosterman

Sums, and Mon-

odromy

Groups.

Princeton,

NJ: Princeton University

Press, 1987.

Kloosterman, H. ID. “On the Representation of Numbers in

the Form ax2 + by2 + cx2 + dt2.” Acta Math. 49, 407-464,

1926.

Ramanujan, S. “On the Expression of a Number in the Form

ax2 + by2 + cx2 + du2.”

Collected

Papers.

New York:

The problem of determining how many nonattacking

knights K(n) can be placed on an n x n CHESSBOARD.

For n = 8, the solution is 32 (illustrated

Chelsea, 1962.

above). In

general, the solutions are

K(n) =

ln2

i(n2 + 1)

n > 2 even

n > 1 odd,

Knights of the Round Table

Knight ‘s Tour

993

giving the sequence 1, 4, 5, 8, 13, 18, 25, l . . (Sloane’s

A030978, Dudeney 1970, p. 96; Madachy 1979).

The minimal number of knights needed to occupy or

attack every square on an rz x n CHESSBOARD is given

by 1, 4, 4, 4, 5, 8, 10, . . . (Sloane’s A006075). The

number of such solutions are given by 1, 1, 2, 3, 8, 22,

3, ..* (Sloane’s AOO6076).

see UZSO BISHOPS PROBLEM, CHESS, KINGS PROBLEM,

KNIGHT'S TOUR, QUEENS PROBLEM, ROOKS PROBLEM

A knight’s tour of a CHESSBOARD (or any other grid)

is a sequence of moves by a knight CHESS piece (which

may only make moves which simultaneously shift one

square along one axis and two along the other) such

that each square of the board is visited exactly once

(i.e., a HAMILTONIAN CIRCUIT). If the final position is

a knight’s move away from the first position, the tour is

called re-entrant. The first figure above shows a knight’s

tour on a 6 x 6 CHESSBOARD. The second set of figures

shows six knight’s tours on an 8 x 8 CHESSBOARD, all

but the first of which are re-entrant. The final tour has

the additional property that it is a SEMIMAGIC SQUARE

with row and column sums of 260 and main diagonal

sums of 348 and 168,

Lijbbing and Wegener (1996) computed the number

of cycles covering the directed knight’s graph for an

8 x 8 CHESSBOARD. They obtained a2, where a =

2,849,759,680, i.e., 8,121,130,233,753,702,400. They

also computed the number of undirected tours, obtain-

ing an incorrect answer 33,439,123,484,294 (which is not

divisible by 4 as it must be), and so are currently redoing

the calculation.

References

Dudeney, H. E. “The Knight-Guards.” 5319 in Amusements

in Mathematics. New York: Dover, pm 95, 1970.

Madachy, J. S. Madachy’s

Mathematical

Recreations.

New

York: Dover, pp. 38-39, 1979.

Moser, L. “King Paths on a Chessboard.”

Math.

Gax.

39,

54, 1955.

Sloane, N. J. A. Sequences A030978, A006076/M0884, and

A006075/M3224 in “An On-Line Version of the Encyclo-

pedia of Integer Sequences.”

Sloane, N. J. A. and Plouffe, S. Extended entry for M3224 in

The Encyclopedia

of Integer

Sequences.

San Diego: Aca-

demic Press, 1995.

Vardi; I. Computational

Recreations

in Mathematics.

Red-

wood City, CA: Addison-Wesley,

pp. 196-197, 1991.

Wilf, H. S. “The Problem of Kings.”

Electronic

J. Combi-

natorics

2, 3, l-7, 1995. http : //www . combinatorics,

erg/

Volume,2/volume2.html#3.

Knights

of the Round

Table

The following results are given by Kraitchik (1942). The

number of possible tours on a 4k x 4k: board for k: = 3,

4, . . . are 8, 0, 82, 744, 6378, 31088, 189688, 1213112,

. . . (Kraitchik 1942, p. 263). There are 14 tours on the

3 x 7 rectangle, two of which are symmetrical. There are

376 tours on the 3 x 8 rectangle, none of which is closed,

There are 16 symmetric tours on the 3 x 9 rectangle and

8 closed tours on the 3 x 10 rectangle. There are 58

symmetric tours on the 3 x 11 rectangle and 28 closed

tours on the 3 x 12 rectangle. There are five doubly

symmetric tours on the 6 x 6 square. There are 1728

tours on the 5 x 5 square, 8 of which are symmetric.

The longest “uncrossed” knight’s tours on an n x n board

for n = 3, 4, , . . are 2, 5, 10, 17, 24, 35, . . . (Sloane’s

A003192).

see also CHESS, KINGS PROBLEM, KNIGHTS PROBLEM,

MAGIC TOUR, QUEENS PROBLEM,TOUR

~~~NECKLACE

Knight’s

Tour

References

Ball, W. W* R. and Coxeter, H. S. M. Mathematical

Recre-

ations and Essays,

13th ed. New York: Dover, pp. 175-

186, 1987.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: