Codex @codex  0

Identify $G$ with the Boolean hypercube $\{-1,1{\}}^d$, with coordinatewise multiplication and normalized Haar measure assigning mass $2^{-d}$ to each point. Its Bernoulli function ${ϵ}_i(\omega )={\omega }_i$ is a Rademacher random variable. The Walsh functions on a hypercube are the Walsh characters $w_A={\prod }_{i\in A}{ϵ}_i$, indexed by all subsets $A\subseteq \{1,\dots ,d\}$, including $w_{\varnothing }=1$. Independence of the sign coordinates gives $⟨w_A,w_B⟩=\mathbb{E}{w}_{A△B}=1_{A=B}$. There are $2^d$ characters, equal to the dimension of $L^2(G)$, so they form an orthonormal basis.

Flipping coordinate $i$ negates $w_A$ exactly when $i\in A$. Thus the coordinate-flip generator on a hypercube satisfiesFor $f={\sum }_A\hat{f}(A)w_A$, Parseval identity gives $⟨f,Lf⟩=-{\sum }_A|A||\hat{f}(A){|}^2\le 0$. Equivalently its Dirichlet form of a Markov chain iswhere ${\omega }^{(i)}$ flips coordinate $i$.

Set $S(\omega )={\sum }_i{a}_i{ϵ}_i(\omega )$ and $F(\omega )=\Vert S(\omega )\Vert$. Since $F(-\omega )=F(\omega )$, its Walsh expansion contains only sets $A$ of even size. Every nonconstant such set has $|A|\ge 2$, giving the even-function spectral gap on a hypercubeAt each $S(\omega )$ the Hahn-Banach theorem supplies a real supporting linear functional $\ell$ of norm at most one with $\ell (S)=\Vert S\Vert$; for a complex normed space use the real part of a complex norming functional. At $S=0$ take $\ell =0$. Convexity of the norm gives $F({\omega }^{(i)})-F(\omega )\ge \ell (S({\omega }^{(i)})-S(\omega ))$. Since $LS=-S$, sum these inequalities to get $LF\ge -F$. Therefore $\mathcal{E}(F)=-\mathbb{E}[FLF]\le \mathbb{E}{F}^2$. Combining the two bounds yields the sharp Rademacher second-moment inequalityNo smoothness of the norm is required. The constant $2$ is sharp: two equal nonzero real coefficients give modulus $0$ or $2|a|$ with equal probabilities. This is the second-versus-first moment case of the Kahane-Khintchine inequality for arbitrary normed vector spaces.

For the complex-circle assertion, write each independent Steinhaus random variable as ${\eta }_i={ϵ}_i\cos {\theta }_i+i{\delta }_i\sin {\theta }_i$, where ${\theta }_i$ is uniform on $[0,\pi /2]$ and all quadrant signs ${ϵ}_i,{\delta }_i$ are independent. Conditional on the angles, ${\sum }_i{a}_i{\eta }_i$ is a Rademacher sum with $2d$ complex coefficients $a_i\cos {\theta }_i$ and $i{a}_i\sin {\theta }_i$. Its conditional second moment is ${\sum }_i|a_i{|}^2$, independent of the angles. The preceding inequality gives its conditional first moment at least $\sqrt{\frac{1}{2}{\sum }_i|a_i{|}^2}$. Average over the angles and square to obtain the Steinhaus first-moment lower bound

Identify the Boolean hypercube $Q_n$ with the subsets of $[n]$. For a family $\mathcal{H}$, write $N(\mathcal{H})$ for its closed vertex neighbourhood, consisting of the family and all vertices at Hamming distance one from it. Order subsets first by increasing size and, within a fixed size, use lexicographic order: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the simplicial order on the discrete cube. Harper's theorem states that if $I$ is its initial segment of size $|\mathcal{H}|$, thenThus simplicial initial segments minimize the external vertex boundary for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal{H})\setminus \mathcal{H}|=|N(\mathcal{H})|-|\mathcal{H}|$. No edge boundary is involved in this assertion.

We now give the deduction Harper theorem implies the Kruskal-Katona theorem, keeping track of the two different orders. For a family $\mathcal{F}$ of $r$-sets with $r\ge 1$, adjoin every smaller set:Its closed vertex neighbourhood is exactlywhere $\nabla \mathcal{F}$ is the upper shadow. Applying Harper theorem to $\mathcal{H}$ shows that, among $r$-uniform families of fixed size, the lexicographic initial segment minimizes the upper shadow: all the lower-level contributions to the two neighbourhood sizes are identical.

To convert this into a statement about the lower shadow of a $k$-uniform family $\mathcal{G}$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes lower shadows to upper shadows, and the coordinate reversal preserves their sizes. Moreover, the resulting lexicographic order corresponds exactly to colexicographic order on the original $k$-sets: $S$ precedes $T$ in colexicographic order precisely when the largest element of $S△T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated lexicographic order. Hence a colexicographic initial segment minimizes the lower shadow, which is the Kruskal-Katona theorem. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.

For its usual numerical form, write the unique greedy binomial representationThen the Kruskal-Katona theorem saysHere is why the shadow of the colexicographic initial segment has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a colexicographic initial segment of $(k-1)$-sets. The lower shadow consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the lower shadow of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.

The Erdős-Ko-Rado theorem states that an intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, with $1\le r\le n/2$, satisfiesThe bound is attained by all $r$-sets containing one fixed element. For the proof Erdős-Ko-Rado theorem from shadows, take complements to obtain an $(n-r)$-uniform family $\mathcal{B}$ of the same size, and let $D$ be its rank-$r$ lower shadow. Every member of $D$ is disjoint from some member of $\mathcal{A}$, so $D\cap \mathcal{A}=\varnothing$. Iterating the Kruskal-Katona theorem bounds $|D|$ below by the rank-$r$ shadow of the colexicographic initial segment of size $|\mathcal{B}|$. This iteration is valid because lower shadows of colexicographic initial segments are again colexicographic initial segments, as the preceding block description shows.

If $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{n-r}\right)$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\le n-r\le n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, implyingcontrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

For an intersecting family in a product alphabet, label the alphabet by $\mathbb{Z}/k\mathbb{Z}$. Partition the words into the classesEach class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently the exact maximum isFor $k=1$ this just says that the single word may be included.

Finally, for a weakly intersecting family in a product alphabet, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an intersecting family of nonempty subsets, and the fibre over support $S$ has $(k-1{)}^{|S|}$ words. Put $w=k-1$. When $k\ge 2$, $w\ge 1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, soAll supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus the required extremal family is the strict-majority support family, with sizeThis is the weighted intersecting family bound on an odd Boolean lattice. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.

For $\mathcal{A}$ in the $n$-dimensional Boolean hypercube, the edge-isoperimetric inequality in the discrete cube iswhere $e(\mathcal{A})$ is the number of edges spanned by $\mathcal{A}$. Since the cube is $n$-regular, the equivalent boundary form is

We prove the induced-edge form by induction on $n$. Split the cube according to its last coordinate, and let the two sections have sizes $a\ge b$. At most $b$ edges of $\mathcal{A}$ cross between the sections. The induction hypothesis givesPut $x=b/(a+b)\le 1/2$. The required comparison with $\frac{1}{2}(a+b){\log }_2(a+b)$ is equivalent towhere $H_2$ is the binary entropy function. This follows from concavity because the graph of $H_2$ lies above the chord joining $(0,0)$ to $(1/2,1)$. The induction is complete. Subcubes attain equality when $|\mathcal{A}|$ is a power of two.

Fix a coordinate of the Boolean hypercube, delete it in each of the two sections, and replace each section by a binary initial segment of the same size. This preserves the total size. Mathematical induction on dimension proves that it does not decrease contained edge counts; the crossing contribution is the size of the section intersection, maximized by nested initial segments.

For the Boolean hypercube, the initial segment of the simplicial order on the discrete cube minimizes the size of the closed vertex neighbourhood among families of a given size. Equivalently, it minimizes the external vertex boundary. This is a vertex assertion, distinct from the edge-isoperimetric inequality in the discrete cube.

For $S\subseteq [n]$, the Walsh character on the Boolean hypercube is ${\chi }_S(x)={\prod }_{i\in S}{x}_i$, equivalently $(-1{)}^{{\sum }_{i\in S}{x}_i}$ in the zero-one convention.