Let $C=(\mathbb{Z}/2\mathbb{Z})^N$ be the Hamming cube with its usual graph structure, and assume each edge $e=(x,x+\epsilon)$ (where $x\in C$ and $\epsilon$ has one $1$ and $N-1$ zeros) is given a length $\ell(x,\epsilon)$ satisfying the constraints
$$ \sum\_\epsilon \ell(x,\epsilon) \le 1 \qquad \forall x\in C.$$
Denote by $d\_\ell$ the distance function induced by these lengths.



> 
> **Q1:** What is the growth of the largest possible diameter $D(N)$ for such $(C,d\_\ell)$?
> 
> 
> 


I think I can prove a bound $D(N) \lesssim log(N)$, but I wonder if a constant bound could be true.


In fact, this is not the real question I have, but it seemed a reasonable way to get to it. The real question is about functions $f:C\to \mathbb{R}$ such that
$$(1) \qquad \sum\_\epsilon \lvert f(x+\epsilon) - f(x) \rvert \le 1 \qquad \forall x\in C$$
and of vanishing average.



> 
> **Q2:** What is the largest possible value $\lVert f\rVert\_\infty$ for such a function?
> 
> 
> 


(My motivation is a toy example to test some concentration inequalities for Markov chains. In some cases I figured the semi-norm $\max\_x \sum\_\epsilon \lvert f(x+\epsilon)-f(x)\rvert$ should be efficient for the Glauber dynamic (aka lazy random walk) on $C$, but I need the above to get a good spectral gap in the corresponding functional space)



Diameter of a weighted Hamming cube
It looks like even the sharp upper estimate 1 may be obtained. We use the following


**Lemma.** If $q\_0,\dots,q\_{N-1}$ are non-negative real numbers such that $q\_i-q\_{i+1}+q\_{i+2}-\dots+q\_{i+2s}\geqslant 0$ for all $0\leqslant i\leqslant i+2s\leqslant N-1$, then there exist non-negative numbers $p\_0,\dots,p\_{N}$ such that $q\_i=p\_i+p\_{i+1}$ for $i=0,\dots,N-1$.


**Proof.** Denote $p\_0=t$, then $p\_1=q\_0-t$, $p\_2=q\_1-q\_0+t$, $p\_3=q\_2-q\_1+q\_0-t$, $\dots$, $p\_N=q\_{N-1}-q\_{N-2}+\dots+(-1)^{N-1}q\_0+(-1)^Nt$. We need all $p\_i$'s be non-negative, this gives certain upper and lower estimates for $t$. They must be consistent. It holds if any lower estimate is consistent with any upper estimate. Say, these two estimates come from the inequalities $p\_i\geqslant 0$ and $p\_{i+2s+1}\geqslant 0$, where $0\leqslant i< i+2s+1\leqslant N$. Their consistence rewrites as $p\_i+p\_{i+2s+1}\geqslant 0$ (the left hand side does not depend on $t$), and it is exactly what we supposed.


Note that the assumption of the lemma holds if $q\_0\geqslant q\_1\geqslant q\_2\geqslant \dots \geqslant q\_m\leqslant q\_{m+1}\leqslant q\_{m+2}\dots \leqslant q\_{N-1}$ for some $m$. This is what we actually use. 


We should find a path of length at most 1 between two opposite vertices, say, from $(0,\dots,0)$ to $(1,\dots,1)$ (all other cases reduce to this by induction in $N$). Sum up the lengths of all $N!$ paths (consisting of $n$ edges), denote the sum by $S$. It suffices to prove that $S\leqslant N!$. Using our lemma, we choose non-negative numbers $p\_0,p\_1,\dots,p\_N$ such that $p\_i+p\_{i+1}=i!(N-i-1)!$ for all $i=0,\dots,N-1$. Then $S$ equals $\sum\_{x\in C} p\_{|x|}f(x)$, where $f(x)$ is your sum $\sum\_\epsilon \ell(x,\epsilon)$ which does not exceed 1 (and $|x|$ denotes a number of coordinates 1 in $x$). Indeed, if $|x|=i$, $|x+\epsilon|=i+1$, then the edge between $x$ and $x+\epsilon$ belongs to $i!(N-i-1)!$ our paths, and it goes with coefficient $p\_i+p\_{i+1}$ to our sum. 


So, $S$ does not exceed $\sum\_{i=0}^N p\_i\binom{N}i=\sum\_{i=0}^{N-1}(p\_i+p\_{i+1})\binom{N-1}i=N(N-1)!=N!$ as desired. 


Here is an almost computation-free explanation why Benoît Kloeckner's explicit formula for $p\_i$ works. 


We have $N+1$ levels $L\_0,\dots,L\_N$ of vertices of the cube ($L\_k$ consists of vertices with the sum equal to $k$), and $N$ levels $P\_0,\dots,P\_{N-1}$ of edges ($P\_i$ consists of edges between $L\_i$ and $L\_{i+1}$). Choose $i$ at random uniformly in $\{0,1,\dots,N\}$ and after that choose a random edge from a random (uniformly chosen) vertex $v\in L\_i$. We get a random edge, and I claim that its level is uniformly distributed. Indeed, the probability to get an edge from $P\_k$ equals $\frac1{N+1}(\frac{N-k}N+\frac{k+1}N)=\frac1N$, where the first summand corresponds to $i=k$ and the second to $i=k+1$. Thus the distribution of edges is exactly the same as if we get a random path of length $N$ between $L\_0$ and $L\_N$ and choose its random edge.


