Cube packings, second moment and holes

We consider tilings and packings of Rd by integral translates of cubes [0,2[d[0,2[d, which are 4Zd-periodic. Such cube packings can be described by cliques of an associated graph, which allow us to classify them in dimensions d≤4d≤4. For higher dimensions, we use random methods for generating some examples.Such a cube packing is called non-extendible   if we cannot insert a cube in the complement of the packing. In dimension 3, there is a unique non-extendible cube packing with 4 cubes. We prove that dd-dimensional cube packings with more than 2d−32d−3 cubes can be extended to cube tilings. We also give a lower bound on the number NN of cubes of non-extendible cube packings.Given such a cube packing and z∈Zd, we denote by NzNz the number of cubes inside the 4-cube z+[0,4[dz+[0,4[d and call the second moment   the average of Nz2. We prove that the regular tiling by cubes has maximal second moment and gives a lower bound on the second moment of a cube packing in terms of its density and dimension.