MATH 669: COMBINATORICS, GEOMETRY AND COMPLEXITY OF ...
MATH 669: COMBINATORICS, GEOMETRY AND COMPLEXITY OF INTEGER POINTS
Alexander Barvinok
Abstract. These are rather condensed notes, not really proofread or edited, presenting key definitions and results of the course that I taught in Winter 2011 term. Problems marked by are easy and basic, problems marked by may be difficult.
Typeset by AMS-TEX
1
Contents
1. Lattices: definition and examples
3
2. Lattice subspaces
4
3. A basis of a lattice
5
4. The determinant of a lattice
7
5. A sublattice of a lattice
9
6. Minkowski Theorem
11
7. The volume of a unit ball
13
8. An application: Lagrange's four squares theorem
14
9. An application: rational approximations of real numbers
16
10. Sphere packings
19
11. The Leech lattice
21
12. The Minkowski - Hlawka Theorem
24
13. The reciprocity relation for the packing radius
27
14. The Korkin-Zolotarev basis of a lattice
28
15. The covering radius of a lattice
30
16. An application: Kronecker's Theorem
33
17. The Poisson summation formula for lattices
34
18. The covering radius via the Poisson summation formula
36
19. The packing density via the Poisson summation formula
39
20. Approximating a convex body by an ellipsoid
40
21. The Flatness Theorem
42
22. The successive minima of a convex body
43
23. An almost orthogonal basis of the lattice
47
24. Successive minima via the Poisson summation formula
49
25. The Lenstra - Lenstra - Lov?asz basis of a lattice
52
26. Some applications of the Lenstra - Lenstra - Lov?asz basis
56
27. The algebra of polyhedra and the Euler characteristic
59
28. Linear transformations and polyhedra
62
29. Minkowski sum
64
30. The structure of polyhedra
65
31. Rational generating functions for integer points in polyhedra
69
32. Tangent cones
76
33. The Ehrhart polynomial of an integer polytope
79
34. The reciprocity relation for cones
82
35. The reciprocity relation for the Ehrhart polynomial
85
36. Polarity for cones
87
37. The constant term of the Ehrhart polynomial
90
38. Unimodular cones
92
2
1. Lattices: definition and examples
We work in a finite-dimensional real vector space V endowed with an inner product x, y (hence V is Euclidean space) and the corresponding Euclidean norm
x = x, x .
(1.1) Definitions. A lattice V is a discrete additive subgroup of V which spans V . That is, span() = V , x - y for all x, y (additive subgroup) and there is an > 0 such that B = {0}, where B = {x V : x } is the ball of radius (discrete). The dimension of the ambient space V is called the rank of lattice and denoted rank .
Lattices 1 V1 and 2 V2 are isomorphic if there is an invertible linear transformation : V1 - V2 such that (x) = x for all x V1 (so that is an isometry) and (1) = 2.
(1.2) Problem. Let V be a lattice. Show that K is a finite set for every bounded set K V .
(1.3) Examples.
(1.3.1) Lattice Zn. Let V = Rn with the standard inner product
n
x, y = xiyi where x = (x1, . . . , xn) and y = (y1, . . . , yn) .
i=1
Let Zn Rn be the set consisting of the points with integer coordinates,
Zn = (x1, . . . , xn) : xi Z for i = 1, . . . , n .
(1.3.2) Lattice An. Let us identify V with the hyperplane H Rn+1 defined by the equation x1 + . . . + xn+1 = 0. We let
An = Zn+1 H.
(1.3.3) Lattice Dn. Let V = Rn and let
Dn = (x1, . . . , xn) Zn : x1 + . . . + xn 0 mod 2 .
(1.3.4) Lattice Dn+. Suppose that n is even. Let Dn Rn be the lattice of Example 1.3.3 and let us define u Rn by
u=
1 2
,
.
.
.
,
1 2
.
n times
We let Dn+ = Dn (Dn + u) .
(1.3.5) Lattices E8, E7 and E6. We denote E8 = D8+, E7 = E8 H, where H R8 is the hyperplane defined by the equation x1+. . .+x8 = 0, and E6 = E8L, where L R8 is the subspace defined by the equations x1 + x8 = x2 + x3 + x4 + x5 + x6 + x7 = 0.
(1.4) Problem. Prove that Zn, An, Dn, Dn+, E8, E7 and E6 are indeed lattices.
3
2. Lattice subspaces (2.1) Definitions. Let V be a lattice and let L V be a subspace. We say that L is a -subspace or just a lattice subspace if L is spanned by points from , or, equivalently, if L is a lattice in L.
For a set A V and a point x V , we define the distance
dist(x, A) = inf x - y .
yA
In what follows, we denote by the largest integer not exceeding a real number and we denote {} = - . Clearly,
0 {} < 1 for all R.
The main result of this section is that if L V is a lattice subspace such that L = V then among all lattice points not in L there is a point nearest to L.
(2.2) Lemma. Let V be a lattice and let L V , L = V , be a -subspace. Then there exists a point v \ L such that
dist(v, L) dist(w, L) for all w \ L.
Proof. Let k = dim L and let u1, . . . , uk be a basis of L consisting of lattice points, so ui for i = 1, . . . , k. Let
k
=
iui : 0 i 1 for i = 1, . . . , k
i=1
be the parallelepiped spanned by u1, . . . , uk. We claim that among the lattice points that are not in L there is a point nearest to . For > 0, let us consider the -neighborhood of ,
= x V : dist(x, ) .
Clearly, is bounded and hence is a finite set, cf. Problem 1.2. Let us choose a sufficiently large so that
( \ L) =
and let us choose a point v ( \ L) nearest to . Clearly,
(2.2.1)
dist(v, ) dist(w, ) for all w \ L. 4
Let us choose any w \ L and let x L be the point such that
dist(w, L) = w - x .
We can write
k
k
k
x = iui = u + y where u = iui and y = {i} ui.
i=1
i=1
i=1
Clearly, u L and y . Moreover, w - u \ L and by (2.2.1)
dist(w, L) = w - x = (w - u) - (x - u) = (w - u) - y dist(w - u, ) dist(v, ) dist(v, L),
which completes the proof.
(2.3) Problems. 1. Let V be a lattice and let L V be a -subspace. Let us consider a
decomposition V = L W and the projection pr : V - W with the kernel L. Prove that pr() is a lattice in W .
2. Let L R2 be a line with an irrational slope. Prove that there exist points w Z2 \ L arbitrarily close to L.
3. Let L R2 be a line with an irrational slope and let pr : R2 - L be the orthogonal projection. Prove that pr Z2 is dense in L.
3. A basis of a lattice
We prove the following main result.
(3.1) Theorem. Let V be a d-dimensional Euclidean space, d > 0. (1) Let V be a lattice. Then there exist vectors u1, . . . , ud such that every point u admits a unique representation
d
u = miui where mi Z for i = 1, . . . , d.
i=1
The set {u1, . . . , ud} is called a basis of . (2) Let u1, . . . , ud be a basis of V and let
d
=
miui where mi Z .
i=1
Then V is a lattice. 5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- nutrition information s s ns hot beverages
- c4591001 covid 19 bla safety and efficacy data for
- oof silver 0 11 tr z 0 6 0 3 5 6 00 nny bull
- rb series threaded rigid conduit and imc reducers
- relative and differential huba control
- math 669 combinatorics geometry and complexity of
- pdb18 series 17 mm rotary potentiometer
- homework 4 solutions university of california berkeley
- 6 1 1 0 2 1 2 9 81 7 675 7 1 0 8 1
- mccord pmccord hw5 chemical equilibria ii acids bases
Related searches
- the role of culture in teaching and learning of english as a foreign language
- electron geometry and molecular geometry
- complexity of insertion sort
- happiness is the meaning and the purpose of life the whole aim and end of human
- time complexity of fibonacci series
- time complexity of fibonacci
- math mode median mean and range
- similarities and differences of debit and credit
- game of states and capitals of us
- searching sorting and complexity analysis
- chapter 03 searching sorting and complexity analysis
- geometry and trigonometry online and download