Report

Transference Theorems in the Geometry of Numbers Daniel Dadush New York University Convex Bodies Convex body ⊆ ℝ . (convex, full dimensional and bounded). Convexity: Line between and in . Equivalently + 1 − Non convex set. Integer Programming Problem (IP) convex set 1 Input: ℚ× , ℚ ≤ ℤ 2 ℤ Classic NP-Hard problem (integrality makes it hard) IP Problem: Decide whether above system has a solution. Focus for this talk: Geometry of Integer Programs Integer Programming Problem (IP) Linear Programming (LP) convex set 1 Input: ℚ× , ℚ ≤ ℝ 2 ℤ (integrality makes it hard) LP Problem: Decide whether above system has a solution. Polynomial Time Solvable: Khachiyan `79 (Ellipsoid Algorithm) Integer Programming Problem (IP) 1 2 ℤ Input: ℚ× , ℚ −1 ≤ : Invertible Transformation ℤ Remark: can be restricted to any lattice = ℤ . Integer Programming Problem (IP) 1 2 Input: ℚ× , ℚ ≤ Remark: can be restricted to any lattice . Central Geometric Questions 1 2 ℤ2 1) When can we guarantee that a convex set contains a lattice point? (guarantee IP feasibility) 2) What do lattice free convex sets look like? (sets not containing integer points) Examples “Hidden cube” 1 ℤ2 If a convex set very ``fat’’, then it will always contain a lattice point. Examples 1 ℤ2 If a convex set very ``fat’’, then it will always contain a lattice point. Examples Infinite band ℤ2 Volume does NOT guarantee lattice points (in contrast with Minkowski’s theorem). Examples ℤ2 However, lattice point free sets must be ``flat’’ in some direction. Lattice Width ℤ2 1 =1 1 =4 … 1 =8 For each example, there is hyperplane decomposition of ℤ2 with a small number of intersecting hyperplanes. Lattice Width 2 =4 2 =3 2 =2 2 =1 ℤ2 For each example, there is hyperplane decomposition of ℤ2 with a small number of intersecting hyperplanes. Lattice Width ℤ2 1 − 2 =1 1 − 2 =4 For each example, there is hyperplane decomposition of ℤ2 with a small number of intersecting hyperplanes. Note: axis parallel hyperperplanes do NOT suffice. Lattice Width 2 =4 1 subproblems 2 =3 2 =2 2 =1 subproblems 2 ℤ2 Why is this useful? IP feasible regions: hyperplane decomposition enables reduction into − 1 dimensional sub-IPs. # intersections = # subproblems Lattice Width 2 =4 1 subproblems 2 =3 2 =2 2 =1 subproblems 2 ℤ2 Why is this useful? # intersections = # subproblems If # intersections is small, can solve IP via recursion. Lattice Width 1 − 2 =1 1, −1) ℤ2 1 − 2 =4 Integer Hyperplane : Hyperplane where dim ∩ ℤ = − 1. Fact: is an integer hyperplane ⇔ = { ℝ : , = }, ℤ ∖ {0}, ℤ, gcd 1 , … , = ( called primitive if = 1) Lattice Width 1, 0) ℤ2 1 =1 … 1 =8 Hyperplane Decomposition of ℤ : For ℤ ∖ {0} ℤ ⊆ ℤ ℝ : , = (parallel hyperplanes) Lattice Width 2 2, 0) ℤ2 21 =2 21 =5 … 21 =9 … 21 =16 Hyperplane Decomposition of ℤ : For ℤ ∖ {0} ℤ ⊆ ℤ ℝ : , = (parallel hyperplanes) Note: If is not primitive, decomposition is finer than necessary. Lattice Width 7.2 1.9 1 =1 1, 0) ℤ2 2 3 6 4 7 1 =8 How many intersections with ? ℤ ⊆ ℤ ℝ : , = (parallel hyperplanes) # INTs = |{ ℤ: inf , ≤ ≤ sup , }| = sup , − inf , + 1 ≤ sup , − inf , + 1 (tight within +2) K K Lattice Width width = 1.2 ℤ2 Width Norm of : for any ℝ width = sup , − inf , = sup 1 ,2 , 1 − 2 = sup , Lattice Width: width , ℤ = inf width ) ∖ 0 − Kinchine’s Flatness Theorem Theorem: For a convex body , ∩ ℤ = ∅, width , ℤ = 4/3 log . Bounds improvements: Khinchine `48: + 1)! Babai `86: 2 ) Lenstra-Lagarias-Schnorr `87: 5/2 Kannan-Lovasz `88: 2 Banaszczyk et al `99: 3/2 Rudelson `00: 4/3 log c [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Properties of width − 2 2 Convex & Centrally Symmetric 0 22 Width Norm of : for any ℝ width = sup , − 22 Properties of width − 2 Convex & Centrally Symmetric 2 0 22 Width Norm of : for any ℝ 22 width = sup , − Bounds: 2 2 = sup , ≤ sup , = width 22 − Properties of width − 2 2 Convex & Centrally Symmetric 0 22 Width Norm of : for any ℝ 22 width = sup , − Bounds: width = sup , ≤ sup , = 2 − 22 2 Properties of width − 2 2 Convex & Centrally Symmetric 0 22 Width Norm of : for any ℝ 22 width = sup , − Symmetry: By symmetry of − sup , = sup max{ , , , − } = sup | , | − − − Properties of width − 2 2 Convex & Centrally Symmetric 0 22 Width Norm of : for any ℝ 22 width = sup , − Symmetry: Therefore width = sup | , | = sup − − −, = width − Properties of width − 2 2 0 Convex & Centrally Symmetric 22 Width Norm of : for any ℝ 22 width = sup , − Homogeneity: For ≥ 0, width = width (Trivial) Properties of width − 2 Convex & Centrally Symmetric 2 0 22 Width Norm of : for any ℝ width = sup , − Triangle Inequality: width 1 + 2 = sup 1 + 2 , − 22 Properties of width − 2 Convex & Centrally Symmetric 2 0 22 Width Norm of : for any ℝ width = sup , − Triangle Inequality: sup 1 + 2 , = sup 1 , + 2 , − − 22 Properties of width − 2 0 Convex & Centrally Symmetric 2 22 Width Norm of : for any ℝ 22 width = sup , − Triangle Inequality: sup 1 , + 2 , ≤ sup 1 , + sup 2 , − − − Properties of width − 2 Convex & Centrally Symmetric 2 0 22 Width Norm of : for any ℝ 22 width = sup , − Triangle Inequality: sup 1 , + sup 2 , = width 1 + width 2 − − Properties of width width ) is invariant under translations of . ℎ = − Properties of width width ) is invariant under translations of . + + , + , ℎ+ = + , − + , = max − min = ℎ Properties of width width ) is invariant under translations of . Also follows since + − + = − . (width only looks at differences between vectors of ). + + , + , ℎ+ = + , − + , = max − min = ℎ Kinchine’s Flatness Theorem Theorem: For a convex body , such that ∩ ℤ = ∅, width , ℤ = 4/3 log . Remark: Finding flatness direction is a general norm SVP! width , ℤ = inf ℤ ∖{0} width ) [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Kinchine’s Flatness Theorem Theorem: For a convex body , such that ∩ ℤ = ∅, width , ℤ = 4/3 log . Easy generalize to arbitrary lattices. (note , = , − ) width , ℤ = inf ℤ ∖{0} width − ) [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Kinchine’s Flatness Theorem Theorem: For a convex body , such that ∩ ℤ = ∅, width , ℤ = 4/3 log . Easy generalize to arbitrary lattices. (note , = , − ) width , ℤ = inf − ℤ ∖{0} width ) [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Kinchine’s Flatness Theorem Theorem: For a convex body and lattice , such that ∩ = ∅, width , = 4/3 log . Easy generalize to arbitrary lattices. width , = inf ∗ ∖{0} width ) where ∗ = { : , ℤ, ∀ } is dual lattice. [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Kinchine’s Flatness Theorem Theorem: For a convex body and lattice , such that ∩ = ∅, width , = 4/3 log . Homegeneity of Lattice Width: , > 0 width , = inf 1 ∗ ∖ 0 width = width , [Khinchine `48, Babai `86, Hastad `86, Lenstra-Lagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Bound conjectured to be ) (best possible). Lower Bound: Simplex Bound cannot be improved to ≤ . No interior lattice points. 1 0 2 = ℝ : ≥ 0, ≤ } = conv {0,e1 , … , en int = { ℝ : > 0, < } (interior of S) Pf: If ℤ and int ), then ≥ 1 ∀ ⇒ ≥ a contradiction. Lower Bound: Simplex Bound cannot be improved to ≤ . 1 2 0 ℤ2 = ℝ : ≥ 0, ≤ } = conv {0,e1 , … , en Pf: For ℤ ∖ {0}, then width ≥ max | , − 0 | ≥ max | | ≥ i Flatness Theorem Theorem*: For a convex body and lattice , if ∃ ℝ such that + ∩ = ∅, then width , = 4/3 polylog . By shift invariance of width . + ℤ2 Flatness Theorem Theorem**: For a convex body and lattice , either 1) ∀ ℝ + ∩ ≠ ∅, or 2) width , = 4/3 log . + ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ∀ span , + ⇔ ∀ , − ∩ ≠ ∅ ⇔ ∀ , + ∩ ≠ ∅ ℤ2 Condition from Flatness Theorem Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ∀ span , + ⇔ ∀ , − ∩ ≠ ∅ ⇔ ∀ , + ∩ ≠ ∅ ℤ2 Condition from Flatness Theorem Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ∀ span , + ⇔ ∀ , − ∩ ≠ ∅ ⇔ ∀ , + ∩ ≠ ∅ Must scale by factor 2 about to hit . Therefore , ≥ 2. 2 − + ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ∀ span , + ⇔ ∀ , + ∩ ≠ ∅ , ≤ 1 ⇔ contains a fundamental domain ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . ∀ span , + ⇔ ∀ , + ∩ ≠ ∅ , ≤ 1 ⇔ contains a fundamental domain ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Covering radius of with respect to . det 1/ vol , ≥ det ⇔ , ≥ vol 1/ , ≤ 1 ⇔ contains a fundamental domain ℤ2 Covering Radius Definition: , = inf { ≥ 0: span ⊆ + } Further Properties: + , = , , = , , , > 0 −, = , ℤ2 Flatness Theorem Theorem**: For a convex body and lattice , either 1) , ≤ 1, or 2) width , = 4/3 log . + ℤ2 Flatness Theorem Theorem: For a convex body and lattice : , width , ≤ 4/3 log By homogeneity of , and width , . + ℤ2 Flatness Theorem Theorem [Banaszczyk `93]: For a lattice in ℝ : 2 , width 2 , = ) width 2 , = inf ∗ sup , ∖{0} 2 2 =2 inf ∗ ∖{0} Bound Improvements: Khinchine `48: Babai `86: Lenstra-Lagarias-Schnorr `87: Kannan-Lovasz `88: Banaszczyk `93: 2 (since 2 -2 =22 ) = 2 1 ∗ ) ! 2 ) 2 3/2 (asymptotically optimal) Flatness Theorem Theorem [Banaszczyk `93]: For a lattice in ℝ : 2 , 1 ∗ ) = ) 2 , is max distance to Flatness Theorem Theorem [Banaszczyk `96]: For a symmetric convex body : , width , = log ) ℤ2 Bound Improvements: Khinchine `48: Babai `86: Kannan-Lovasz `88: Banaszczyk `93: Banaszczyk `96: ! 2 ) 2 3/2 log Lower Bounds: Random Lattices Theorem: For a convex body and ``random’’ lattice in ℝ : , width , = Θ ) (Minkowski Hlawka + Volume Product Bound) ℤ2 Norms and Convex Bodies Symmetric convex body ⊆ ℝ ( = −). Gauge function: ≝ inf { ≥ 0: } 0 - 1. + ≤ + 2. = , ≥ 0 3. = − = { ℝ : ≤ 1} is unit ball of ∙ (triangle inequality) (homogeneity) (symmetry) Norms and Convex Bodies Convex body ⊆ ℝ containing origin in its interior. Gauge function: ≝ inf { ≥ 0: } 0 1. + ≤ + 2. = , ≥ 0 3. = − = { ℝ : ≤ 1} is unit ball of ∙ (triangle inequality) (homogeneity) (symmetry) Norms and Convex Bodies Gauge function: Triangle Inequality: Want to show + ≝ inf { ≥ 0: } = , = ≤+ By definition , . May assume , > 0. Need to show + + . + + + = + = + + + convex combination Norms and Convex Bodies ∙ asymmetric norm in ℝ . Unit ball = { ℝ : ≤ 1}. + 1-) 0 is convex: Take , ≤ 1, [0,1] + 1 − ≤ + 1 − ≤+ 1− =1 Minkowski’s Convex Body Theorem Symmetric convex body and lattice in ℝ . If vol > 2 det L), ∃ such that ∖ {0}. 0 Minkowski’s Convex Body Theorem Symmetric convex body and lattice in ℝ . If vol > 2 det L), ∃ such that ∖ {0}. 0 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2 with parallelepiped 2. 2 = det 2 = 2 det < . 1 0 2 21 22 2 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2. Let 2 be parallelepiped. Tile space with 2 using 2. 0 2 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2. Let 2 be parallelepiped. Tile space with 2 using 2. 0 2 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2. Let 2 be parallelepiped. Shift tiles intersecting into 2 using 2. 0 2 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2. Let 2 be parallelepiped. Since vol > vol 2), must have intersections. 0 2 Minkowski’s Convex Body Theorem Pf: 21 , … , 2 basis for 2. Let 2 be parallelepiped. Since vol > vol 2), must have intersections. +2 +2 0 2 Minkowski’s Convex Body Theorem Here (a) + 2 ≠ + 2, (b) + 2, + 2 , (c) 2, 2 2 +2 +2 0 2 Minkowski’s Convex Body Theorem Then 2 − = + 2 − + 2 − = + = 2 (by symmetry of ) and 2 − ≠ 0. +2 2 − ) +2 0 2 Minkowski’s Convex Body Theorem Then 2 − = + 2 − + 2 − = + = 2 (by symmetry of ) and 2 − ≠ 0. 0 2 − ) 2 Minkowski’s Convex Body Theorem So 2 − 2 and 2 − 2 ∖ {0} ⇒ − ∩∖ 0 . − 0 Successive Minima Symmetric convex body and lattice in ℝ . , = inf ≥ 0: dim ∩ ≥ , [] 0 Successive Minima Symmetric convex body and lattice in ℝ . , = inf ≥ 0: dim ∩ ≥ , [] -1 1 0 1 Successive Minima Symmetric convex body and lattice in ℝ . , = inf ≥ 0: dim ∩ ≥ , [] 2 -1 -2 1 0 2 1 Minkowski’s First Theorem Symmetric convex body and lattice in ℝ . det 1/ 1 , ≤ 2 vol 1/ -1 1 0 1 Minkowski’s First Theorem Symmetric convex body and lattice in ℝ . Pf: Let = det 1 2 . For 1 >0 1 + = 1 + = 1 + 2 det > 2 det 0 Minkowski’s First Theorem Symmetric convex body and lattice in ℝ . Pf: By Minkowski’s convex body theorem, 1 + ∩ ∖ 0 ⇒ 1 , ≤ 1 + . Since this holds as → 0, 1 , ≤ . 0 Minkowski’s Second Theorem Symmetric convex body and lattice in ℝ . Π=1 , ≤ 2 det ≤ ! Π=1 , ) vol 2 -1 -2 1 0 2 1 Covering Radius vs Successive Minima Theorem [Kannan-Lovasz 88]: − , ≤ , ≤ Σ=1 − , ) For symmetric becomes 1 1 , ≤ , ≤ Σ=1 , ) 2 2 “Naïve” Babai rounding Separator Theorem For a closed convex set and ∉ , there exists ℝ such that sup , < , ∗ Can use y = − ∗ where ∗ is the closest point in to . Separator Theorem For a closed convex set and ∉ , there exists ℝ such that sup , < , ∗ ∗∗ If not separator can get closer to on line segment ∗ , . Polar Bodies and Dual Norms For compact convex with 0 in relative interior, the polar is ∗ = { : , ≤ 1 ∀ } (-1,1) (-1,-1) (0,1) (1,1) 0 (-1,0) (1,-1) 0 (1,0) (0,-1) For ), the dual norm ∗ = inf ≥ 0: = sup , Remark: width = sup , = − − ∗ Polar Bodies and Dual Norms Def: ∗ = { : , ≤ 1 ∀ } Theorem: compact convex with 0 in rel. int., then ∗∗ = . In particular ∗∗ = sup , = . ∗ 0 Polar Bodies and Dual Norms Def: ∗ = { : , ≤ 1 ∀ } Theorem: compact convex with 0 in rel. int., then ∗∗ = . In particular ∗∗ = sup , = . ∗ Pf: Easy to check that = ∗ . Hence ⊆ ∗∗ . Must show ∗∗ ⊆ . 0 Polar Bodies and Dual Norms Def: ∗ = { : , ≤ 1 ∀ } Theorem: compact convex with 0 in rel. int., ∗∗ = . In particular ∗∗ = sup , = . ∗ Pf: Take ∉ and in ). By separator theorem ∃ ) such that 0 ≤ sup , < , 0 Scale such that sup , ≤ 1 < , Polar Bodies and Dual Norms Def: ∗ = { : , ≤ 1 ∀ } Theorem: compact convex with 0 in rel. int., ∗∗ = . In particular ∗∗ = sup , = . ∗ sup , ≤ 1 < , ∗ Then and 1 < , therefore ∉ ∗∗ . 0 Banaszczyk’s Transference Theorem Theorem [Banaszczyk `95,`96]: For a symmetric convex body and lattice in ℝ 1 ≤ , −+1 ∗ , ∗ = log ) , ∀ [] Pf of lower bnd: Take linearly independent vectors 1 , … , where ‖ ‖ ≤ , , and 1 , … , −+1 ∗ where ‖ ‖ ≤ −+1 ∗ , ∗ Since + − + 1 > , ∃ , s.t. , ≠ 0. Hence 1 ≤ , ≤ ∗ ≤ , −+1 ∗ , ∗ ) Volume Product Bounds Theorem [Blashke `18, Santalo `49] : For a symmetric convex body ⊆ ℝ vol 1 vol ∗ 1 ≤ vol 2 2 2e ≈ Theorem [Bourgain-Milman `87, Kuperberg `08]: For a symmetric convex body ⊆ ℝ 1 ∗ 1 vol vol ≥ 1− 1 ) Mahler Conjecture: minimized when is cube. Minkowski Transference Theorem [Kannan-Lovasz `88] : For a symmetric convex body and lattice 4 ∗ ∗ 1 , 1 , ≤ 1 + 1 ) Pf: By Minkowski’s first theorem 1 2 det ∗ 1 2 det 1 , 1 ∗ , ∗ ≤ vol 1 vol ∗ 1 = 4 vol −1 vol ∗ −1 4 (Bourgain-Milman) ≤ 1 + 1 ) Projected Norms and Lattices a symmetric convex body and lattice L. Let the orthogonal projection onto a subspace . Then for any ℝ ) ) = inf ⊥ + ∈ ≤ The following identities hold: 1. ∗ = ∗ ∩ and 2. ∗ = ∗ ∩ . Flatness Theorem We will follow the proof of Kannan and Lovasz `88: Theorem: For a convex body and lattice : , width , = 2 ) + ℤ2 Flatness Theorem We will follow the proof of Kannan and Lovasz `88: Theorem: For a convex body and lattice : 1 ≤ , 1 − ∗ , ∗ ) = 2 ) Proof of lower bound: , 1 − ∗ , ∗ ≥ − , 1 − ∗ , ∗ ≥ 1 + ℤ2 Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: Let = 1 1 Δ ) . Can write 1 = 1 − 2 , 1 , 2 . Note that 1 −2 ≤ since 1 − 2 ). By shifting → − 2 , can assume that 1 (all quantities are invariant under shifts of ) ≤ and 0 . Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: By shifting → − 2 , have 1 ≤ and 0 . 1 2 1 ℤ2 Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: By shifting → − 2 , have 1 ≤ and 0 . 1 ℤ2 Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: Let = Σ= Δ ) . Note that 1 = + 2 . Suffices to show that ∀ ℝ that + 1 ∩ ≠ ∅ Let = 2 ), = 2 , = 2 . By induction , ≤ 2 , hence ∃ ∈ such + 2 . Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: By induction , ≤ 2 , hence ∃ ∈ such + 2 . 2 1 2 ℤ2 Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: Have ∈ such + 2 . By definition can find + 2 s.t. 2 = . −1 Since , we have 2 = ℤ1 + , for some shift . Therefore ∃ [0,1], such that + 1 . Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: By definition can find + 2 s.t. 2 = . 2 11 ℤ2 Generalized Babai Rounding Lemma [Kannan-Lovasz `88]: Let 1 , … , denote a basis of . Let be orthogonal projection onto 1 , … , −1 ⊥ . Then , ≤ Σ=1 Δ ) where = ) (Gram-Schmidt Orth.) and Δ = − . Pf: Since , we have 2 . −1 = ℤ1 + , for some shift Therefore ∃ [0,1], such that + 1 . Since 0 , note that ⊆ . Hence + 1 + 2 + ⊆ + 2 + = + 2 + = + 1 Generalized HKZ Basis For a symmetric convex body and lattice in ℝ A generalized HKZ basis 1 , … , for with respect to satisfies ‖1 ‖ = 1 , 2 2 ) = 1 2 , 2 ) ⋮ ⋮ ) = 1 , ) where is orthogonal projection onto 1 , … , −1 ⊥. Flatness Theorem Theorem: For a convex body and lattice : 1 ≤ , 1 − ∗ , ∗ ) = 2 ) Pf: Let 1 , … , be a HKZ basis with respect to Δ . Pick j such that Δ ) = max [] By generalized Babai, , ≤ Σ=1 By definition Δ ) Δ Δ ) . ≤ Δ ) = 1 Δ , ), hence , ≤ 1 Δ , ) Flatness Theorem Theorem: For a convex body and lattice : 1 ≤ , 1 − ∗ , ∗ ) = 2 ) For = span 1 , … , −1 Δ ∗ = Δ ∗ ⊥ , we have ∩ and ∗ = ∗ ∩ . By the Minkowski transference 1 Δ , 1 ∗ Δ ∩ , ∗ ∩ V = ) Flatness Theorem Theorem: For a convex body and lattice : 1 ≤ , 1 − ∗ , ∗ ) = 2 ) By the Minkowski transference 1 Δ , 1 ∗ Δ ∩ , ∗ ∩ V = ) By inclusion 1 Hence , 1 ∗ ∗ Δ , ≤ 1 ∗ Δ ∗ ∩ , ∗ ∩ V . Δ , ∗ ≤ 1 Δ , ≤ 2 ) 1 ∗ Δ , ∗ Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . : r=2 = {0} 0 ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . : r=2 Integral shifts of 0 ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . : r=2 Integral shifts of intersecting ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . : r=1 = { x, y : y = 0} 0 ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . Integral shifts of 0 ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . Integral shifts of intersecting ℤ2 Subspace Flatness Theorem Theorem [Kannan-Lovasz `88, D. 12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most 2 ) integral shifts of . If = 1, is a hyperplane. Forcing = 1 corresponds to Classical Flatness Theorem. ℤ2 Subspace Flatness Theorem Conjecture [KL `88, D.12]: For ⊆ ℝ convex, either 1. contains an integer point in every translation, or 2. ∃ subspace of dimension − s.t. every translation of intersects at most log n r integral shifts of . ℤ2 Generalized HKZ Basis For a symmetric convex body and lattice in ℝ A generalized HKZ basis 1 , … , for with respect to satisfies ‖1 ‖ = 1 , 2 2 ) = 1 2 , 2 ) ⋮ ⋮ ) = 1 , ) where is orthogonal projection onto 1 , … , −1 ⊥. Inhomogeneous Minkowski Theorem [Kannan-Lovasz `88]: Convex body K and lattice . ∃ a subspace , of some dimension 1 ≤ ≤ , such that 1 ≤ , vol det 1 1 ≤ Hence having ``large’’ volume (i.e. relative to determinant) in every projection implies ``always’’ contains lattice points. In this sense, we get a generalization of Minkowski’s theorem for arbitrary convex bodies. Inhomogeneous Minkowski Theorem [Kannan-Lovasz `88]: Convex body K and lattice . ∃ a subspace , of some dimension 1 ≤ ≤ , such that 1 ≤ , vol det 1 1 ≤ Pf: Let 1 , … , be a HKZ basis with respect to Δ with satisfying Δ ) = max Δ ) as before. [] Inhomogeneous Minkowski Theorem [Kannan-Lovasz `88]: Convex body K and lattice . ∃ a subspace , of some dimension 1 ≤ ≤ , such that 1 ≤ , 1 vol det 1 ≤ ⊥ Pf: Let = − + 1 and = 1 , … , −1 . By Generalized Babai and Minkowski’s first theorem , ≤ Δ = 1 − , ≤ 1 2 det − Brunn-Minkowski: + 1 1/ ≤ det ≥ 1 1 1/ + . 1/ Gaussian Heuristic Lemma: For a convex body and lattice , and , ≤ 1, then for any ℝ vol + ∩ ≤2 det ) Gaussian Heuristic Want to bound | + ) ∩ |. By shifting may assume = 0. + Gaussian Heuristic Since covers space, exists fundamental domain ⊆ . Gaussian Heuristic Place around each point in ∩ . ∩ vol = vol ∩ + ≤ vol + = 2 vol Gaussian Heuristic Place around each point in ∩ . Hence ∩ ≤ 2 = 2 det ) Subspace Flatness Theorem Corollary: Convex body K and lattice . Assume , ≥ 1/ for ≥ 1. ∃ a subspace , of some dimension 1 ≤ ≤ , such that max | + ∩ )| ≤ 2 ℝ Pf: May assume , = 1 ≤ 1, since this is worst case. Picking from inhomogeneous Minkowski theorem, we have 2 vol det 1 1 ≤2 = 2 , By Gaussian Heuristic, for any ℝ , + ) ∩ ) ≤ 2 . Subspace Flatness Have , ≥ 1/2. 1 2 Subspace Flatness Hence can find projection such that ∩ is small. Subspace Flatness Can find projection such that ∩ is small. ) ) Subspace Flatness Corresponds to small number of shifts of ⊥ intersecting . 1 + ⊥ … 3 + ⊥ ) ) Subspace Flatness Theorem Conjecture [Kannan-Lovasz `88]: Convex body K and lattice . ∃ a subspace , of some dimension 1 ≤ ≤ , such that 1 ≤ , vol det 1 1 = O log ) Corollary of Conjecture: Convex body K and lattice . Assume , ≥ 1/ for ≥ 1. ∃ a subspace , of some dimension 1 ≤ ≤ , such that max | + ∩ )| ≤ 2 ) c log ℝ Subspace Flatness for 2 norm Conjecture [Kannan-Lovasz `88, D `12]: 1 ≤ 2 , min vol 2 subspace W 1≤dim =≤ det 1 1 =O log ) ⇔ 1 ≤ 2 , min . subspace W 1≤dim =≤ det ∗ ∩ /2 1/ =O log ) Subspace Flatness for 2 norm Conjecture [Kannan-Lovasz `88, D `12]: 1 ≤ 2 , min .subspace W 1≤dim =≤ det ∗ ∩ 1/ /2 Lower bound valid for all . Given lower bound is polytime computable. =O log ) Subspace Flatness for 2 norm Conjecture [Kannan-Lovasz `88, D `12]: 1 ≤ 2 , min .subspace W 1≤dim =≤ det ∗ ∩ /2 1/ =O log ) Promise problem: -coGapCRP (Covering Radius Problem) where > 1 YES instances: 2 , ≥ No instances: 2 , ≤ 1 Subspace Flatness for 2 norm Conjecture [Kannan-Lovasz `88, D `12]: 1 ≤ 2 , min .subspace W 1≤dim =≤ det ∗ ∩ /2 1/ =O log ) Promise problem: -coGapCRP (Covering Radius Problem) Conjecture implies log -coGapCRP NP. Current best: -coGapCRP NP. (Exponential Improvement!)