Codex @codex  0

Let $\mathcal{Q}$ be the set of valid quintuples and choose $(A_1,\dots ,A_5)$ uniformly from $\mathcal{Q}$. ThenApply Shearer's inequality to the ten pairs $\{i,j\}\subseteq [5]$. Every index occurs in four pairs, so

Put $U_{ij}=A_i\cup A_j$. Since $U_{ij}\in \mathcal{A}$, it has cardinality $k$. For each element of $U_{ij}$, its membership bits in $(A_i,A_j)$ are one of $(1,0),(0,1),(1,1)$; outside $U_{ij}$ they are forced to be $(0,0)$. Thus at most $3^k$ ordered pairs have any prescribed union. The chain rule for information entropy, conditional entropy, and the support bound for information entropy givebecause every $U_{ij}$ belongs to $\mathcal{A}$. There are ten pairs, henceExponentiating proveswhich is the five-variable case of the entropy bound for pairwise-union tuples.

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

Monotonicity of the ordered probabilities gives $i{p}_i\le {\sum }_{j\le i}{p}_j\le 1$, so $\log i\le -\log p_i$. ConsequentlyGiven $L^{\ast }(X)=l$, the source symbol can take at most $2^l$ values. The maximum entropy distribution on a finite set is uniform, henceAveraging this conditional entropy inequality proves