# Submodular measures on the hypercube

By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the meet and join operations $\wedge$ and $\vee$ that take the pointwise max and min. For example $010 \wedge 110 = 010$ and $001 \vee 100 = 101$. A submodular measure $\mu$ is a function from the hypercube to nonnegative reals satisfying $\mu(x) + \mu(y) \geq \mu(x \wedge y) + \mu(x \vee y)$ for all $x$ and $y$.

My question is, what is a minimal set of $(x,y)$ such that if the inequality above holds for these $(x,y)$ then it holds for all $(x,y)$ (and hence $\mu$ is submodular)?

The question comes out of mere curiousity (I want to understand submodularity in a more intuitive way) - I first guessed it suffices to check all pairs of elements of same rank. I'm still not sure whether that's true. If $x$ and $y$ are comparable, then the inequality is vacuous by itself.

-

These submodular measures on the hypercube are the same as non-negative submodular set functions. A minimal set of inequalities is $$f(x+e_j)+f(x+e_j)\geq f(x)+f(x+e_i+e_j)$$ over all $x\in\{0,1\}^n$ and $1\leq i < j\leq n$ such that $x_i=x_j=0$. I'm using $e_i$ to denote the bit-string that is $1$ exactly at $i$. These inequalities are the third equivalent definition listed on the Wikipedia page. To see these are a minimal set, given $z\in\{0,1\}^n$ and all $1\leq I< J\leq n$ with $z_I=z_J=0$ we can define $$f(x)=\begin{cases} n^2+2-(\sum x_i)^2&\text{ if x=z or x=z+e_I+e_J}\\ n^2-(\sum x_i)^2 &\text{ otherwise} \end{cases}$$ for all bit-strings $x$.
Then $f(x+e_j)+f(x+e_j)-f(x)-f(x+e_i+e_j)$ is non-negative except when $(x,i,j)=(z,I,J)$.