On hypercube statistics

Abstract

Let $d\ge 1$ and $s\le 2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n\ge d$, let $\hat{I}»(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $\hat{I}»(n,d,s)$ denote the maximum possible value of $\hat{I}»(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $\hat{I}»(d,s)$ denote the limit of this quantity as $n$ tends to infinity. We prove several lower and upper bounds on $\hat{I}»(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than $0.28$. We also show that the values of $s=s(d)$ such that $\hat{I}»(d,s)=1$ are exactly $\{0,2^{d-1},2^d\}$. In addition we prove that if $0<s<d/8$, then $\hat{I}»(d,s)\le 1-\hat{I}\text{c◯}(1/s)$, and that if $s$ is divisible by a power of $2$ which is $\hat{I}\text{c◯}(s)$ then $\hat{I}»(d,s)\ge 1-O(1/s)$. We suspect that $\hat{I}»(d,1)=(1+o(1))/e$ where the $o(1)$-term tends to $0$ as $d$ tends to infinity, but this remains open, as does the problem of obtaining tight bounds for essentially all other quantities $\hat{I}»(d,s)$.

10 pages