Need a *trivial* proof of an "obvious" combinatorial result

I've just presented Enflo's theorem on the existence of a Banach space without an approximation property in my Functional Analysis class. The argument is not trivial by itself, but in order to emphasize the really interesting steps, I'd like to dismiss all the "obvious" lemmata in the most efficient way.

I have cleaned up the end quite a bit (if somebody is interested, the right choice of $k_m$ and $t_m$ is $t_{m+1}\in [t_1t_2\dots t_m,4t_1t_2\dots t_m]$ and $k_m=t_1t_2\dots t_{m-1}t_{m+1}$, which ensures that all interesting ratios are integers, so we can do a perfect fit without any dirty tail bounds and the corresponding estimates; also it is easier to use just random horizontal partitions instead of smart number-theoretic definitions). However some unpleasant pieces remain.

The one that irritates me most is the following:

Consider all $n-1$-element subsets $I$ of $\{1,2,\dots,2n\}$ and $m\in[1,2n-1]$. Let $N_o$ and $N_e$ be the numbers of $I$'s having odd and even number of elements in $\{1,\dots,m\}$ respectively. Then $$ |N_o-N_e|\le c_n(N_o+N_e)=c_n{2n\choose n-1} $$ with some $c_n$ depending on $n$ only (so it should serve all $m$ simultaneously) such that $\sum_n \frac{c_n}n<+\infty$.

The sharp bound is, of course, $c_n=\frac 1n$ and Enflo gets it considering $m=1,2$ separately and using a trigonometric integral representation and Holder inequality for other $m$, on which I wasted about 35 minutes of the class time, but this should be just one-liner (OK, perhaps, three) presentable in under 10 minutes (preferably in under 5). Note that I don't care about sharp $c_n$ as long as the series above converges and will gladly trade its size for any simplification in the proof.

So can we make this "obvious" fact formally obvious?

I'm asking here rather than on MO because it is an education question rather than a research one :-)

Solution 1:

You requested a proof in three lines, and conveniently the proof actually consists of three computations :) I'll break the proof up along these computations. However, in the interest of clarity, I will add some extra lines to explain what the formulas mean.

First some definitions:

• $[n]:=\{1,\dots,n\}$ for positive integer $n$.
• For any set $A$, define:
  • Parity $P(A):=|A|\mod 2$, viewed as an integer, 0 or 1.
  • Signature $S(A) = (-1)^{P(A)}$
  • The "is this set even?" function $E(A):=1-P(A)$. (P above is the "is this set odd?" function).
• For any polynomial $p(x)$, define $C_k\{p(x)\}$ to be the coefficient of $x^k$.

Line 1:

$$N_e = \sum_{\substack{I\subset [2n] \\ |I|=n-1}} E(I\cap [m]) = \frac{1}{\binom{2n}{m}} \sum_{\substack{M\subset [2n] \\ |M|=m}} \sum_{\substack{I\subset [2n] \\ |I|=n-1}} E(I\cap M) = \frac{1}{\binom{2n}{m}} \sum_{\substack{I\subset [2n] \\ |I|=n-1}} \sum_{\substack{M\subset [2n] \\ |M|=m}} E(I\cap M) = \frac{\binom{2n}{n-1}}{\binom{2n}{m}} \sum_{\substack{M\subset [2n] \\ |M|=m}} E([n-1]\cap M)$$

Explanation:

• First off, and most importantly, my browser breaks this into two lines, but with a sufficiently large chalkboard it fits in one.
• The first equality says that $N_e$ is the number of $n-1$ subsets of $[2n]$ with even intersection with $[m]$.
• By symmetry, the number of $n-1$ subsets of $[2n]$ with even intersection with $[m]$ is the same if we replace $[m]$ with any other $m$ subset of $[2n]$. The second inequality sums $N_e$ over all $m$ subsets of $[2n]$ and divides by the number of such subsets.
• The third equality changes the order of summation. Now the inner sum represents the number of $m$ subsets of $[2n]$ with even intersection with a particular $n-1$ subset.
• The inner sum doesn't care which $n-1$ subset you have, so the outer sum is a sum of some constant over all $n-1$ subsets of $[2n]$. There are $\binom{2n}{n-1}$ such subsets, and this gives the last equality.
• If you divide through by $\binom{2n}{n-1}$, this equation can be interpreted as the probabilistic statement that the chance of a randomly selected $n-1$ set having even intersection with a given $m$ set is the same as the chance that a random $m$ set has even intersection with a given $n-1$ set. In this form, the truth of the statement is pretty obvious.
• Lastly, analogous equations hold for $N_o$ and $N_e-N_o$, replacing $E$ with $P$ or $S$, respectively. The one with $N_e-N_o$ and $S$ will be used below. Explicitly, it states $$N_e-N_o = \frac{\binom{2n}{n-1}}{\binom{2n}{m}}\sum_{\substack{M\subset [2n] \\ |M|=m}} S([n-1]\cap M)$$

Line 2:

$$ \begin{eqnarray} \sum_{\substack{M\subset [2n] \\ |M|=m}} S([n-1]\cap M) & = & \sum_k (-1)^k \binom{n-1}{k} \binom{n+1}{m-k} \\ & = & C_m\{(1-x)^{n-1}(1+x)^{n+1}\} \\ & = & C_m\{(1-x^2)^{n-1}(1+x)^2\} \\ & = & C_m\{(1-x^2)^{n-1}(1+2x+x^2)\} \\ & = & (C_m + 2C_{m-1} + C_{m-2})\{(1-x^2)^{n-1}\} \\ & = & \begin{cases} (-1)^{m/2} \binom{n-1}{m/2} - (-1)^{m/2}\binom{n-1}{m/2-1} & \quad \text{m even} \\ (-1)^{(m-1)/2} 2\binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{cases} \end{eqnarray} $$

Explanation:

• I broke the equation up deliberately this time, and I make no apologies. If you have a long blackboard yada yada...
• The first equality breaks up the sum over $m$ sets by the number of elements $k$ in the intersection of $m$ and $[n-1]$. For each $k$, there are $\binom{n-1}{k}$ ways to choose the elements in the intersection and $\binom{n+1}{k}$ ways to choose the remaining $m-k$ elements of the $m$ set. Each such set gets a weight $(-1)^k$ in the sum.
• The sum over $k$ can be expressed as the coefficient $x^m$ in some polynomial product, by the binomial theorem, hence the next equality.
• The next couple equalities rearrange the polynomial product.
• Then note that $C_m\{x p(x)\} = C_{m-1}\{p(x)\}$, and some similar properties of polynomial coefficients.
• Lastly, re-expand $(1-x^2)^{n-1}$ via binomial theorem and identify the coefficients $m$, $m-1$, and $m-2$.

This gives an expression for $$\frac{N_e-N_o}{\binom{2n}{n-1}} = \frac{1}{\binom{2n}{m}}\begin{cases} (-1)^{m/2} \binom{n-1}{m/2} - (-1)^{m/2}\binom{n-1}{m/2-1} & \quad \text{m even} \\ (-1)^{(m-1)/2} \binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{cases}$$ All that remains is to put a convenient bound on this, which is the content of the last line.

Line 3:

Assume for now that $m\leq n$. Let $h(x):= -x\ln(x)-(1-x)\ln(1-x)$ be the entropy function. We will use the estimate $$\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}$$ (link to reference) to get the following bound:

$$\begin{eqnarray} \left|\frac{N_e-N_o}{\binom{2n}{n-1}}\right| & \leq & \frac{1}{\binom{2n}{m}}\begin{cases} \binom{n-1}{m/2} + \binom{n-1}{m/2-1} & \quad \text{m even} \\ \binom{n-1}{(m-1)/2} & \quad \text{m odd}\end{cases} \\ & \leq & \frac{1}{\binom{2n}{m}}\begin{cases} \binom{n}{m/2} & \quad \text{m even} \\ \binom{n}{(m-1)/2} & \quad \text{m odd}\end{cases} \\ & \leq & \begin{cases} \binom{n}{m/2}/\binom{2n}{m} & \quad \text{m even} \\ \binom{n}{(m-1)/2}/\binom{2n}{m-1} & \quad \text{m odd}\end{cases} \\ & \leq & \max_{k}\left\{\frac{\binom{n}{k}}{\binom{2n}{2k}}\right\} \\ & \leq & \max_k \left\{\frac{ \sqrt{\frac{n}{2\pi k (n-k)}} e^{n h(k/n)} }{ \sqrt{\frac{2n}{16k(2n-2k)}} e^{2n h(k/n)} } \right\} \\ & \leq & \max_k \left\{ \sqrt{\frac{8}{\pi}} e^{-n h(k/n)} \right\} \\ & \leq & \left\{ \sqrt{\frac{8}{\pi}} e^{-n h(1/n)} \right\} \\ & = & \sqrt{\frac{8}{\pi}} e^{-n \left(\frac{1}{n}\ln(n)-\frac{n-1}{n}\ln\left(\frac{n-1}{n}\right)\right)} \\ & \leq & \sqrt{\frac{8}{\pi}} \frac{1}{n} \\ \end{eqnarray} $$

Explanation:

• First inequality takes a norm of both sides of the equation from line 2, using the triangle inequality for the $m$ even case.
• For the second inequality, for $m$ even just sum the two binomial coefficients. For $m$ odd, note that by the same sum formula $\binom{n-1}{(m-1)/2}\leq \binom{n}{(m\pm 1)/2}$. We choose the minus sign because of the next step, and because we are assuming initially $m\leq n$.
• The next step just uses the fact that $\binom{2n}{m}\geq \binom{2n}{m-1}$ for $m\leq n$. This is the only spot we use this hypothesis, and if $m\geq n$ we just use $\binom{2n}{m}\geq\binom{2n}{m+1}$ instead, also changing the minus sign to a plus sign in the preceding inequality. The rest of the argument goes through the same regardless of whether $m\geq n$ or $m\leq n$.
• The next inequality eliminates the $m$ dependence by looking at the max of the preceding expression (see note below on the range of $k$).
• Then apply the bounds on the binomial coefficients (upper bound for the numerator, lower bound for the denominator).
• Simplify.
• The entropy function $h$ is positive, symmetric about $\frac{1}{2}$, and monotone increasing on $[0,1/2]$, hence its min is at the smallest allowed $k$, which we can take to be $1$ (see note below on range of $k$).
• Simplify. Then note that $e^{n \frac{n-1}{n} \ln\left(\frac{n-1}{n}\right)}<1$.

Note on range of $k$: In order for the minimum of $h(k/n)$ to be at $k=1$, we need the range of $k$ to be from $1$ to $n-1$. Unfortunately, this means we need to exclude the $m=1$ and $m=2n-1$ cases, as they can lead to $k=0$ or $k=n$. These cases are easy to deal with, though, as here $(N_e-N_o)/\binom{2n}{n-1}=1/n$.

Altogether this gives the bound $c_n\leq \sqrt{\frac{8}{\pi}} \frac{1}{n}$.

Some commentary:

• The estimate in line 3 could probably be improved. Once you have the closed form solution, there are probably lots of ways to make the estimates. I don't claim that the one presented here is optimal.
• The bound on $c_n$ can be improved considerably if you exclude $m=1,2n-1$.

Solution 2:

Just an observation building upon Yly's answer which they suggested I put as an answer. Line 3 can be replaced with several more elementary lines.

First note that by line 2 we want to show

$2{{n-1}\choose{(m-1)/2}}/{{2n}\choose{m}} \leq 1/n $ for m odd.

$({{n-1}\choose{m/2}} - {{n-1}\choose{m/2 -1}})/{{2n}\choose{m}} \leq {{n}\choose{m/2}}/{{2n}\choose{m}}\leq 1/n$ for m even.

Certainly these are true for m=1,2, and by symmetry we just need to show them up to m=n. Now we show both expressions are decreasing in m up to n. First the odd case, replacing $m=2k+1$ we have

$2{{n-1}\choose{k+1}}/{{2n}\choose{2k+3}} = \frac{2k+3}{2n-2k-1}*2{{n-1}\choose{k}}/{{2n}\choose{2k+1}}$

While for the even case replacing $m=2k$ we have

${{n}\choose{k+1}}/{{2n}\choose{2k+2}} = \frac{2k+1}{2n-2k-1}*{{n}\choose{k}}/{{2n}\choose{2k}}$

Solution 3:

I am probably too late, but here it is. Let $[x^k]f(x)$ denote a coefficient of $x^k$ in the polynomial $f(x)$.

1. If we replace $m$ to $2n-m$, the difference $N_0-N_e$ is being multiplied by $(-1)^{n-1}$ by obvious reasons. Thus we may suppose that $1\leqslant m\leqslant n$.

2. $N_o-N_e=[x^{n-1}](1-x)^m(1+x)^{2n-m}=[x^{n-1}](1-x^2)^{m}(1+x)^{2n-2m}$, thus $|N_o-N_e|\leqslant [x^{n-1}](1+x^2)^m(1+x)^{2n-2m}\leqslant 2^{2n-m}$, since any specific coefficient does not exceed the total sum of all coefficients. On the other hand, $N_0+N_e=\binom{2n}{n-1}\geqslant \binom{2n-1}{n-1}\geqslant \frac{2^{n-1}}{2n}$, since $\binom{2n-1}{n-1}$ is the maximal among binomial coefficients $\binom{2n-1}i,0\leqslant i\leqslant 2n-1$, and their sum equals $2^{2n-1}$. This implies that whenever $m\geqslant 10\log n$, we get $c_n<1/n$ for sure.

3. Assume that $m< 10\log n$. We write $(1-x)^m(1+x)^{2n-m}=(1-x)(1-x)^{m-1}(1+x)^{2n-m}=\sum_{i=0}^{m-1}\binom{m-1}i(1-x)(-x)^i(1+x)^{2n-m}$. Thus $$|N_o-N_e|\leqslant \sum_{i=0}^{m-1}\binom{m-1}i\left|[x^{n-1}](1-x)x^i(1+x)^{2n-m}\right|.$$ At the same time, analogously we get $$ N_o+N_e= \sum_{i=0}^{m-1}\binom{m-1}i[x^{n-1}](1+x)x^i(1+x)^{2n-m}. $$ Therefore, if we prove the inequality $$\left|[x^{n-1}](1-x)x^i(1+x)^{2n-m}\right|\leqslant c_n [x^{n-1}](1+x)x^i(1+x)^{2n-m}$$ for certain constant $c_n$ and all $i\leqslant m<10\log n$, this constant $c_n$ works. This ratio of coefficients is, if I am not mistaken, $|2i+3-m|/(2n-m+1)=O(\log n/n)$, that is ok for you.

Solution 4:

Update: This proof doesn't work as is, since $c_n$ should be independent of $m$. Maybe it can be massaged into finding a $c_n$ that does not depend on $m$, so I'll leave it here.

Well, one super-uninspired proof would be to write $$ N_e-N_o=\sum_{k}{(-1)^k\binom{m}{k}\binom{2n-m}{n-1-k}}, $$ factor out $\dfrac{(2n-m)!}{(n-1)!(n+1)!}$ so as to clear denominators and common factors in the numerator, and show that the $n^m$ terms in the remaining factor cancel out because $$ \sum_{k}{(-1)^k\binom{m}{k}=0}. $$ That means the remaining factor is a polynomial of degree at most $m-1$, so $c_n=O\left(\frac{1}{n}\right)$.