A Geometric Proof of the Gap Theorem

✍ Scribed by David S. Herscovici

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 185 KB
• Volume: 83
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2858

✦ Synopsis

Hollmann, Ko rner, and Litsyn used generalized Steiner systems to prove that it is impossible to partition an n-cube into k Hamming spheres if 2<k<n+2. Furthermore, if k=n+2, they showed the only partition of the n-cube consists of a single sphere of radius n&2 and n+1 spheres of radius 0. We give a geometric proof that this is the only nontrivial partition of an n-cube into fewer than 2p+2 spheres, where p is the largest prime with p n. We also show that k=8 is the only value of k between 4 and 11 such that it is possible to partition a cube other than the (k&2)-cube into k spheres.

1998 Academic Press

1. Introduction

We consider a graph of the n-dimensional cube Q n with vertices (a 1 , a 2 , ..., a n ) where each a i is either 0 or 1. The distance between two points in the cube is the length of the shortest path connecting the points, and a Hamming sphere (or simply a sphere) of radius r on the cube consists of all points whose distance from a fixed center is at most r. If m<n, then Q m can be embedded in Q n as the subgraph consisting of all points of the form (a 1 , a 2 , ..., a m , 0, ..., 0). By abuse of notation, we call this subgraph Q m .

Equivalently, we could study the Hamming space [0, 1] n , and use the Hamming distance as a metric, i.e. the distance between two points is the number of coordinates in which the points differ. This language is more common; it was used by all sources cited in this work. Indeed, Ko rner [3] argues that the Hamming space terminology is more natural for similar questions. However, the approach in this paper suggested the proof to its author, and while the techniques used could be translated into the language of Hamming spaces, they are more naturally developed and Article No. TA972858