The Flatness Theorem - New York University

```Transference Theorems in the Geometry of
Numbers
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
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .

ℤ2
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
ℤ2
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
∀   span  ,    +  ⇔ ∀     ,  −  ∩  ≠ ∅
⇔ ∀     ,  +  ∩  ≠ ∅

ℤ2
Condition from
Flatness Theorem
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
∀   span  ,    +  ⇔ ∀     ,  −  ∩  ≠ ∅
⇔ ∀     ,  +  ∩  ≠ ∅

ℤ2
Condition from
Flatness Theorem
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
∀   span  ,    +  ⇔ ∀     ,  −  ∩  ≠ ∅
⇔ ∀     ,  +  ∩  ≠ ∅
Must scale  by factor 2 about  to hit .
Therefore  ,  ≥ 2.

2 − +
ℤ2
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
∀   span  ,    +  ⇔ ∀     ,  +  ∩  ≠ ∅
,  ≤ 1 ⇔
contains a fundamental domain

ℤ2
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
∀   span  ,    +  ⇔ ∀     ,  +  ∩  ≠ ∅
,  ≤ 1 ⇔
contains a fundamental domain

ℤ2
Definition:  ,  = inf { ≥ 0: span  ⊆  + }
Covering radius of  with respect to .
det  1/
vol  ,   ≥ det  ⇔  ,  ≥
vol  1/
,  ≤ 1 ⇔
contains a fundamental domain

ℤ2
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
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!)
```