Intersection sizes of linear subspaces with the hypercube

Abstract

We continue the study by Melo and Winter (2019) [3] on the possible intersection sizes of a k-dimensional subspace with the vertices of the n-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than 2k−1 (the “large” sizes) are of the form 2k−1+2i. We show that this is almost true: the large intersection sizes are either of this form or of the form 35⋅2k−6. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.