# Extremal families for the Kruskal–Katona theorem

Oriol Serra Department of Mathematics, Universitat Politècnica de Catalunya,
Barcelona<EMAIL_ADDRESS>Supported by the Spanish Research Agency under
project MTM2017-82166-P Lluís Vena Department of Mathematics, Universitat
Politècnica de Catalunya, Barcelona<EMAIL_ADDRESS>Supported by the a
Beatriu de Pinós Fellowship BP2018-0030 of the AGAUR, Horizon’s 2020 program
cofund.

###### Abstract

Given a family $S$ of $k$–subsets of $[n]$, its lower shadow $\Delta(S)$ is
the family of $(k-1)$–subsets which are contained in at least one set in $S$.
The celebrated Kruskal–Katona theorem gives the minimum cardinality of
$\Delta(S)$ in terms of the cardinality of $S$. Füredi and Griggs (and Mörs)
showed that the extremal families for this shadow minimization problem in the
Boolean lattice are unique for some cardinalities and asked for a general
characterization of these extremal families.

In this paper we prove a new combinatorial inequality from which yet another
simple proof of the Kruskal–Katona theorem can be derived. The inequality can
be used to obtain a characterization of the extremal families for this
minimization problem, giving an answer to the question of Füredi and Griggs.
Some known and new additional properties of extremal families can also be
easily derived from the inequality.

###### Contents

  1. 1 Introduction
  2. 2 The theorems of Kruskal-Katona and Füredi-Griggs
  3. 3 Characterization of extremal families
    1. 3.1 Examples on the necessity of the conditions
  4. 4 The key inequality
    1. 4.1 Proof of Lemma 2 from Lemma 10 and Corollary 11
    2. 4.2 General comments for Lemma 10 and Corollary 11
    3. 4.3 Translation invariance
    4. 4.4 A geometric representation
    5. 4.5 Walls, rubble, and pavement
    6. 4.6 Sketch of the proof of Lemma 10
    7. 4.7 Reducing the wall and pair of $k$-binomial decompositions
    8. 4.8 Proof of Lemma 10
    9. 4.9 Proof of Corollary 11, or (5) of Lemma 2
  5. 5 Unicity of the colex order
  6. 6 Final remarks

##  1 Introduction

The well–known Kruskal–Katona Theorem [8, 11] on the minimum shadow of a
family of $k$–subsets of $[n]=\\{1,2,\ldots,n\\}$ is a central result in
Extremal Combinatorics with multiple applications, see e.g. [4]. The _shadow_
of a family $S\subset\binom{[n]}{k}$ is the family
$\Delta(S)\subset\binom{[n]}{k-1}$ of $(k-1)$–subsets which are contained in
some set in $S$. The Shadow Minimization Problem asks for the minimum
cardinality of $\Delta(S)$ for families of $k$-sets $S$ with a given
cardinality $m=|S|$. The answer given by the Kruskal–Katona theorem can be
stated in terms of $k$–binomial decompositions. The _ $k$–binomial
decomposition_ of a positive integer $m$ is

$m=\binom{a_{0}}{k}+\binom{a_{1}}{k-1}+\cdots+\binom{a_{t}}{k-t},$ (1)

where the coefficients satisfy $a_{0}>a_{1}>\cdots>a_{t}\geq k-t\geq 1$,
$t\in[0,k-1]$, and are uniquely determined by $m$ and $k$. We also refer to
the decreasing sequence $\mathbf{a}=(a_{0}>a_{1}>\cdots>a_{t})$ from above as
the $k$–binomial decomposition of $m$. More generally, for an integer sequence
$\mathbf{a}=(a_{0},a_{1},\ldots,a_{t})$ we denote by

$\binom{{\mathbf{a}}}{k}=\binom{a_{0}}{k}+\binom{a_{1}}{k-1}+\cdots+\binom{a_{t}}{k-t},$

and, for positive integers $i,j$ we also denote by

$\binom{{\mathbf{a}}-i}{k-j}=\binom{a_{0}-i}{k-j}+\binom{a_{1}-i}{k-j-1}+\cdots+\binom{a_{t}-i}{k-j-t}.$

We denote the length of the sequence $\mathbf{a}$ by $\ell(\mathbf{a})=t+1$.
If $\mathbf{a}$ is strictly decreasing, $\ell(\mathbf{a})\leq k$ and
$a_{t}\geq k-t$ then $m=\binom{\mathbf{a}}{k}$ is the _$k$ –binomial
decomposition_ of a strictly positive integer $m$; in this case we use the
shorthand $m\stackrel{{\scriptstyle b}}{{=}}\binom{\mathbf{a}}{k}$. If
$\mathbf{a}$ is the empty sequence we set $\binom{\mathbf{a}}{k}=0$ by
convention and write $0\stackrel{{\scriptstyle b}}{{=}}\binom{\mathbf{a}}{k}$.
We use the usual conventions for binomial coefficients that $\binom{n}{k}=0$
for all $k<0$ and $\binom{0}{0}=1$.

For $i\leq k-1$ the $i$–shadow $\Delta^{i}(S)$ of $S$ is defined recursively
as $\Delta^{i}(S)=\Delta(\Delta^{i-1}(S))$ and $\Delta^{0}(S)=S$. With this
notation, the Kruskal–Katona theorem is expressed as follows.

######  Theorem 1 (Kruskal–Katona [7, 11]).

Let $n\geq k\geq 1$. Let $S\subset\binom{[n]}{k}$ be a non-empty family of
$k$–subsets of $[n]$ and let $\binom{\mathbf{a}}{k}$ be the $k$–binomial
decomposition of $m=|S|$. Then, for each $1\leq i\leq k-1$,

$|\Delta^{i}S|\geq\binom{\mathbf{a}}{k-i}.$ (2)

The lower bound in Theorem 1 is tight. We say that a family $S$ is _extremal_
if the cardinality of its lower shadow $\Delta(S)$ achieves the lower bound in
Theorem 1 for $i=1$. It turns out that, for an extremal family, equality holds
in (2) as well for all $i\geq 1$ (see [5, Theorem 2.1]). In other words, the
shadow of an extremal family is also extremal.

We recall that the colex order on the $k$–subsets of $[n]$ is defined by
$X\leq_{\text{colex}}Y$ if and only if $\max((X\setminus Y)\cup(Y\setminus
X))\in Y$. We denote by $I_{n,k}(m)$ the initial segment of length $m$ in the
colex order in $\binom{[n]}{k}$. In what follows, we refer to initial segments
of the colex order up to automorphisms of the Boolean lattice, induced by any
permutation of $[n]$. It can be easily checked that, for every $m$, the
initial segment $I_{n,k}(m)$ of length $m$ in the colex order is an extremal
family.

Füredi and Griggs [5] (see also Mörs [12]) proved that, for cardinalities $m$
for which the $k$–binomial decomposition has length $\ell(\mathbf{a})<k$,
these initial segments $I_{n,k}(m)$ are in fact the unique extremal families.
They also exhibit nontrivial examples which show that this may not be the case
when $\ell(\mathbf{a})=k$. We note that, for fixed $k$, the set of integers
with $k$–binomial decomposition of length $k$ has upper asymptotic density one
111In the interval $[\binom{n}{k},\binom{n+1}{k}]$ there are
$\binom{n-1}{k-1}$ numbers whose $k$–binomial decomposition has length $k$,
one for each choice of an increasing sequence of length $k-1$ of numbers in
$[n-1]$, and $\lim_{n\to\infty}\binom{n}{k-1}/\binom{n-1}{k-1}=1$.. Thus, the
unicity of the extremal families can only be ensured on a thin set of
cardinalities. This prompted the authors of [5] to ask about a general
characterization of the extremal families. The aim of this paper is to address
this question, an answer to which can be found in Theorem 3 below.

The proof of Theorem 3 involves three ingredients. The main one is the
following new numerical inequality of binomial sequences.

######  Lemma 2.

Let $m$ and $k$ be positive integers. Let
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}m$, and let $\mathbf{b}$
and $\mathbf{c}$ be strictly decreasing sequences of non-negative integers
($\mathbf{b}$ not empty, $\mathbf{c}$ possibly empty). Assume that

$\binom{\mathbf{a}}{k}=\binom{\mathbf{b}}{k}+\binom{\mathbf{c}}{k-1},$ (3)

If

$\mathbf{b}\geq_{lex}\mathbf{a}-1,$ (4)

then, for each $i\geq 0$,

$\displaystyle\binom{\mathbf{a}}{k-i}\leq\binom{\mathbf{b}}{k-i}+\binom{\mathbf{c}}{k-i-1}.$
(5)

Moreover, if there is equality in (5) for $i=1$, and $c_{j}\geq k-1-j-1$ and
$b_{j}\geq k-j-1$ for all $j$ for which the terms exists, then the equality
(5) holds for all $i\geq 1$.

We note that the condition (4) in Lemma 2 can not be ommitted. For instance,
we have $\binom{2n-1}{n}=\binom{2n-1}{n-1}$ for every $n$ (so $\mathbf{b}$ is
the empty sequence in (3)) while $\binom{2n-1}{n-1}>\binom{2n-1}{n-2}$. There
are sequences $\mathbf{a}$ and integers $k$ for which the condition is in fact
necessary for the conclusion of the Lemma to hold. The non-negativity
condition on $\mathbf{b}$ and $\mathbf{c}$ is also necessary (see the case
$k=3$, $\mathbf{a}=(4,2)$, $\mathbf{b}=(3,2,-10)$, $\mathbf{c}=(-10,-42)$);
the non-emptyness condition on $\mathbf{b}$ is necessary so that (4) imposes a
non-trivial condition (see $k=1$, $\mathbf{a}=(1)$, $\mathbf{b}=\emptyset$,
$\mathbf{c}=(0)$); the lower bounds on $c_{j}$ and $b_{j}$ in the second part
is also necessary (see the case $k=3$, $\mathbf{a}=(3,2,1)$,
$\mathbf{b}=(3,0)$, $\mathbf{c}=(2,1)$). Moraly, all three $\mathbf{a}$,
$\mathbf{b}$, and $\mathbf{c}$ ought to be binomial decompositions, yet the
condition imposed by (4) enlarges the context of the statement beyond the
binomial decompositions for the sequences $\mathbf{b}$ and $\mathbf{c}$.

Based on the numerical inequality (5) with $i=1$ one can easily derive the
Kruskal–Katona theorem. Unlike some existing proofs, the one derived from
Lemma 2 does not involve compression or any transformation of the families of
$k$–subsets, and it is therefore suitable to analyze the structure of the
extremal ones. Our proof is closer in spirit to the one given by Kruskal in
[11] where there is some implicit use of (5) (see [11, Lemma 7, Section 6]),
which is however in itself not sufficient to provide the characterization of
extremal families given in this paper. Furthermore, inequality (5) provides
also a simple proof of a result by Füredi and Griggs [6, Theorem 2.1] which
shows that the lower shadow of an extremal family is itself extremal. These
simple proofs of both results are given in Section 2. A common feature of
these proofs is that they rely on numerical inequalities that hold
independently of their potential connection to families of $k$–subsets of a
ground set.

Lemma 2 provides the following recursive characterization of extremal
families, which is the main result of this paper and gives an answer to the
question posed by Füredi and Griggs in [6]. We use the following notation. For
a family $S\subset\binom{[n]}{k}$ of $k$–subsets of $[n]$ and $x\in[n]$ we
denote by

$S(x)=\\{X\in S:x\in X\\}$

the family of sets in $S$ containing $x$, and by

$d_{S}(x)=|S(x)|$

the degree of $x$ in $S$, which is always assumed to be nonzero, that is, we
assume (without loss of generality) that $\cup_{X\in S}X=[n]$. We also denote
by

$S(x)\setminus x=\\{X\setminus x:X\in S(x)\\}.$

######  Theorem 3.

Let $n\geq k\geq 2$ and let $S\subset\binom{[n]}{k}$ be a non-empty family of
$k$–subsets of $[n]$, where $[n]$ is the support of $S$. Let
$\binom{{\mathbf{a}}}{k}\stackrel{{\scriptstyle b}}{{=}}|S|$ be the
$k$–binomial decomposition of $m=|S|$. For each $x\in[n]$, let

$\binom{{\mathbf{c}}(x)}{k-1}\stackrel{{\scriptstyle
b}}{{=}}|S(x)|=|S(x)\setminus
x|\qquad\text{and}\qquad\binom{{\mathbf{b}}(x)}{k}\stackrel{{\scriptstyle
b}}{{=}}|S|-|S(x)|.$

(the binomial decomposition of the $0$ being the empty sequence.)

The family $S$ is extremal if and only if, for every $x\in[n]$, the inequality

$|S|-|S(x)|\geq\binom{{\mathbf{a}}-1}{k}$ (6)

holds, and either

  1. (i)

the inequality (6) is strict and

    1. (i.1)

(inclusion) $S(x)\setminus x\subseteq\Delta(S\setminus S(x))$,

    2. (i.2)

(extremality) both $S\setminus S(x)$ and $S(x)\setminus x$ are extremal, and

    3. (i.3)

(numerical equality)
$\binom{{\mathbf{a}}}{k-1}=\binom{{\mathbf{b}}(x)}{k-1}+\binom{{\mathbf{c}}(x)}{k-2}$;

or

  1. (ii)

there is equality in (6) and

    1. (ii.1)

(inclusion) $\Delta(S\setminus S(x))\subseteq S(x)\setminus x$, and

    2. (ii.2)

(extremality) $S(x)\setminus x$ is extremal.

Additionally, if (i) or (ii) holds for a $x\in[n]$, then $S$ is extremal.

With the characterization of Theorem 3 one can show the unicity of the colex
order for cardinalities $m$ whose $k$–binomial sequence $\mathbf{a}$ has
length $\ell(\mathbf{a})<k$, a result proved in [5, Theorem 2.6] and [12,
Theorem 7]. We also characterize those cardinalities where the initial segment
of the colex order is the unique extremal family.

######  Theorem 4.

Let $n\geq k>0$ and $0<m\leq\binom{n}{k}$. Let
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}m$ be the $k$–binomial
decomposition of $m$.

The initial segment of length $m$ in the colex order in $\binom{[n]}{k}$ is
the unique extremal set (up to automorphism) if and only if either

  1. (i)

$\ell(\mathbf{a})<k$, or

  2. (ii)

$m=\binom{n^{\prime}}{k}-1=\binom{n^{\prime}-1}{k}+\binom{n^{\prime}-2}{k-1}+\cdots+\binom{n^{\prime}-k}{1}$
for some $n^{\prime}$ with $k<n^{\prime}\leq n$.

The paper is organized as follows. The proof of Lemma 2 is postponed to
Section 4, where we state more general versions of the result as Lemma 10 and
Corollary 11, and discuss some technical details related to it. Section 2
derives the Kruskal–Katona theorem and [6, Theorem 2.1] from Lemma 2. The
simple proof of these known results illustrates the use of Lemma 2 and it is
also used in the proof of Theorem 3 on the characterization of extremal
families, which is the contents of Section 3. In subsection 3.1 we include
examples of nonextremal sets showing that the conditions in Theorem 3 are
independent of each other, so none of them can be ommitted in the
characterization. Section 5 contains the proof of Theorem 4 on the unicity of
the initial segments of the colex order as extremal sets. The paper concludes
with final remarks in Section 6.

##  2 The theorems of Kruskal-Katona and Füredi-Griggs

We next show how Lemma 2 implies both Kruskal-Katona’s theorem [7, 10] as well
as [6, Theorem 2.1], which we combine as Theorem 5 below.

######  Theorem 5 ([8, 11, 5]).

Let $n,k$ be positive integers with $n\geq k$ and $S\subset\binom{[n]}{k}$ be
a family of $k$–subsets of $[n]$ with cardinality $|S|=m>0$. If
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}m$ then

$|\Delta(S)|\geq\binom{{\mathbf{a}}}{k-1}$

Furthermore, if $|\Delta(S)|=\binom{{\mathbf{a}}}{k-1}$, then
$|\Delta^{i}(S)|=\binom{{\mathbf{a}}}{k-i}$ for each $i\geq 0$.

We will use the following Lemma to ensure that condition (4) in Lemma 2 holds.

######  Lemma 6.

Let $n,k$ be positive integers with $n>k>1$ and $S\subset\binom{[n]}{k}$ be a
family of $k$–subsets of $[n]$ with cardinality $|S|=m>1$ and support $[n]$.
Let $x\in[n]$ be an element with minimum degree in $S$. Let
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}m$ be the $k$–binomial
decomposition of $m$ and $\binom{\mathbf{b}}{k}\stackrel{{\scriptstyle
b}}{{=}}|S|-d_{S}(x)$. Then, $\mathbf{b}$ is not the empty sequence and

$\mathbf{b}\geq_{lex}\mathbf{a}-1.$ (7)

###### Proof.

Since $n>k>1$, $|S|>1$ and $x$ has minimum degree, then not all the sets in
$S$ contain $x$ and hence $|S|-d_{S}(x)>0$. This implies that $\mathbf{b}$ is
not the empty sequence.

Let $\binom{\mathbf{a}}{k}=\sum_{i=0}^{t}\binom{a_{i}}{k-i}$. If $|S|\leq k$
then $\binom{\mathbf{a}-1}{k}=0$ and the statement trivially follows as
$\binom{\mathbf{b}}{k}>0$. Assume $|S|>k$. The statement also follows
trivially if $|S|=\binom{n}{k}$. Assume $|S|<\binom{n}{k}$. In particular,
$a_{0}\leq n-1$ and therefore $a_{i}\leq n-i-1$ for each $i=0,\ldots,t$. The
average degree in $S$ of elements in $[n]$ is $\frac{k}{n}|S|$. Therefore, if
$t^{\prime}\leq t$ is the largest subscript $i$ such that $a_{i}>k-i$ (which
exists as $|S|>k$), we have

$|S|-d_{S}(x)\geq|S|\left(1-\frac{k}{n}\right)=\sum_{i=0}^{t}\binom{a_{i}}{k-i}\left(1-\frac{k}{n}\right)=\sum_{i=0}^{t^{\prime}}\binom{a_{i}}{k-i}\left(1-\frac{k}{n}\right)+(t-t^{\prime})\left(1-\frac{k}{n}\right),$
(8)

Let us show that, for each $j\leq t^{\prime}$,

$\sum_{i=0}^{j}\binom{a_{i}}{k-i}\left(1-\frac{k}{n}\right)\geq\sum_{i=0}^{j}\binom{a_{i}-1}{k-i}+\frac{j+1}{n}\binom{a_{j}-1}{k-j-1}.$
(9)

For $j=0$ we have, using $a_{0}\leq n-1$,

$\binom{a_{0}}{k}(1-\frac{k}{n})=\binom{a_{0}}{k}-\frac{k}{n}\frac{a_{0}}{k}\binom{a_{0}-1}{k-1}\geq\binom{a_{0}}{k}-(1-\frac{1}{n})\binom{a_{0}-1}{k-1}=\binom{a_{0}-1}{k}+\frac{1}{n}\binom{a_{0}-1}{k-1},$

and (9) holds for $j=0$. Let $j>0$. By using induction and
$a_{j}\leq\min\\{a_{j-1}-1,n-j-1\\}$, we similarly have

$\displaystyle\sum_{i=0}^{j}$
$\displaystyle\binom{a_{i}}{k-i}(1-\frac{k}{n})\geq\sum_{i=0}^{j-1}\binom{a_{i}-1}{k-i}+\frac{j}{n}\binom{a_{j-1}-1}{k-j}+(1-\frac{k}{n})\binom{a_{j}}{k-j}$
$\displaystyle\stackrel{{\scriptstyle a_{j-1}-1\geq a_{j}}}{{\geq}}$
$\displaystyle\sum_{i=0}^{j-1}\binom{a_{i}-1}{k-i}+\binom{a_{j}}{k-j}(1-\frac{k-j}{n})=\sum_{i=0}^{j}\binom{a_{i}-1}{k-i}+\binom{a_{j}-1}{k-j-1}(1-\frac{k-j}{n}-\frac{a_{j}-(k-j)}{n})$
$\displaystyle\stackrel{{\scriptstyle-a_{j}\geq-n+j+1}}{{\geq}}$
$\displaystyle\sum_{i=0}^{j}\binom{a_{i}-1}{k-i}+\frac{j+1}{n}\binom{a_{j}-1}{k-j-1}.$

The statement of the Lemma follows from (8) and (9) with $j=t^{\prime}$, as
$\binom{\mathbf{a}-1}{k}=\sum_{i=0}^{t^{\prime}}\binom{a_{i}-1}{k-i}$ (the
additional unit needed when $a_{i}=k-i$ for some $i$, comes from the integer
part of the last summand). ∎

###### Proof.

(of Theorem 5) We prove the result by a triple induction on $m$, $n$ and $k$.
The result holds with equality when $k=1$ for all $n$ and $m$ as
$\Delta(S)=\\{\emptyset\\}$ in this case. Moreover, when $n=k$ the result also
holds since $|S|=1=\binom{k}{k}$ and $|\Delta(S)|=k=\binom{k}{k-1}$. The
result also holds for $m=1$ and all $n\geq k$ by the same reason.

Let $n>k>1$. We may assume that $n$ is an element with minimum degree in $S$,
and assume that $|S|>1$, and thus $d_{S}(n)<|S|$. Let
$\binom{\mathbf{b}}{k}\stackrel{{\scriptstyle b}}{{=}}|S|-d_{S}(n)$. Partition
$S=S_{0}\sqcup S_{1}$ with $S_{0}=S(n)=\\{x\in S\>|\>n\in x\\}$ and
$S_{1}=S\setminus S_{0}$. Denote by

$S^{\prime}_{0}=S_{0}\setminus n=\\{x\setminus n\>|\>x\in S_{0},n\in
x\\}\subseteq\binom{[n-1]}{k-1}.$

We observe that

$|\Delta(S)|\geq|\Delta(S_{1})|+|\Delta(S_{0}^{\prime})|.$ (10)

as all the sets in $\Delta(S_{0}^{\prime})$ can be though of as the sets in
$\Delta(S)$ containing $n$. Let
$\binom{{\mathbf{c}}}{k-1}\stackrel{{\scriptstyle
b}}{{=}}|S_{0}|=|S^{\prime}_{0}|$, so that

$\binom{\mathbf{a}}{k}=\binom{\mathbf{b}}{k}+\binom{\mathbf{c}}{k-1}.$ (11)

By induction,

$|\Delta(S_{0}^{\prime})|\geq\binom{{\mathbf{c}}}{k-2}.$ (12)

On the other hand, we have $S_{1}\subseteq\binom{n-1}{k}$ and
$\binom{\mathbf{b}}{k}\stackrel{{\scriptstyle b}}{{=}}|S_{1}|=|S|-d_{S}(n)$.
By induction,

$|\Delta(S_{1})|\geq\binom{{\mathbf{b}}}{k-1}.$ (13)

By Lemma 6, the conditions of Lemma 2 are fullfilled and therefore (11) (10),
(12) and (13) give

$|\Delta(S)|\geq\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}}{k-2}\geq\binom{\mathbf{a}}{k-1},$
(14)

completing the induction step and the proof of the first part of the Theorem.

Suppose now that equality holds along (14). Thus, we have the equalities

$\displaystyle|\Delta(S_{0}^{\prime})|$
$\displaystyle=\binom{\mathbf{c}}{k-2},$ (15) $\displaystyle|\Delta(S_{1})|$
$\displaystyle=\binom{\mathbf{b}}{k-1},$ (16)
$\displaystyle\binom{\mathbf{a}}{k-1}$
$\displaystyle=\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}}{k-2},\;\text{and}$
(17) $\displaystyle|\Delta(S)|$
$\displaystyle=|\Delta(S_{1})|+|\Delta(S_{0}^{\prime})|.$ (18)

By (17) and the second part of Lemma 2, for each $i\geq 0$, we have

$\binom{\mathbf{a}}{k-i}=\binom{\mathbf{b}}{k-i}+\binom{\mathbf{c}}{k-i-1}.$
(19)

On the other hand, by induction, equalities in (15) and (16) lead to

$|\Delta^{i}(S_{0}^{\prime})|=\binom{\mathbf{c}}{k-i-1}\;\text{and}\;|\Delta^{i}(S_{1})|=\binom{\mathbf{b}}{k-i},$
(20)

and moreover,

$|\Delta^{i}(S)|=|\Delta^{i}(S^{\prime}_{0})|+|\Delta^{i}(S_{1})|,$ (21)

as the equality in (18) implies that no other sets in $\Delta(S)$ exist beyond
those containing $n$ (accounted in $\Delta(S_{1})$), and those not containing
$n$ (accounted in $\Delta(S^{\prime}_{0})$). In particular, all the sets in
$\Delta^{i}(S)$ are either accounted in $\Delta^{i}(S^{\prime}_{0})$ if they
do not contain $n$, or accounted in $\Delta^{i}(S_{1})$ if they contain $n$.

By combining (19) with (20) and (21) we get

$|\Delta^{i}(S)|=\binom{\mathbf{c}}{k-i-1}+\binom{\mathbf{b}}{k-i}=\binom{\mathbf{a}}{k-i},$

completing the proof of the second part of the statement. ∎

##  3 Characterization of extremal families

In this section we prove Theorem 3.

###### Proof of Theorem 3.

Assume first that $S$ is extremal. We follow an argument by Frankl [3].
Arguing for a contradiction, suppose that there is $i\in[n]$ such that
$|S(i)|>\binom{\mathbf{a}-1}{k-1}$. Let
$\binom{\mathbf{c}}{k-1}\stackrel{{\scriptstyle
b}}{{=}}|S(i)|>\binom{\mathbf{a}-1}{k-1}$ and $S_{i}^{\prime}=S(i)\setminus
i$. We have

$|\Delta(S(i))|=|\Delta(S^{\prime}_{i})|+|S^{\prime}_{i}|.$ (22)

as the set in $\Delta(S(i))$ either contains $i$, and hence is accounted in
$\Delta(S^{\prime}_{i})$, or it does not contain $i$, and hence there are
$|S^{\prime}_{i}|$ of them. By Theorem 5 and our assumption on $|S(i)|$,

$|\Delta(S)|\geq|\Delta(S(i))|=|\Delta(S^{\prime}_{i})|+|S^{\prime}_{i}|>\binom{{\mathbf{c}}}{k-2}+\binom{\mathbf{a}-1}{k-1}\geq\binom{\mathbf{a}-1}{k-2}+\binom{\mathbf{a}-1}{k-1}=\binom{\mathbf{a}}{k-1},$
(23)

contradicting the extremality of $S$. Therefore, we reach a contradiction and
conclude that, $|S(i)|\leq\binom{\mathbf{a}-1}{k-1}$ for each $i\in[n]$.

The same argument shows that, if $|S(i)|=\binom{\mathbf{a}-1}{k-1}$, then
equality must hold along the above inequalities and
$|\Delta(S(i))|=\binom{{\mathbf{c}}}{k-2}$ so that $S(i)$ is extremal, proving
(ii)(ii.2). Moreover, there is equality in (23) and thus
$|\Delta(S)|=|\Delta(S(i))|$, proving (ii)(ii.1).

Suppose that $|S(i)|<\binom{\mathbf{a}-1}{k-1}$. Let
$\binom{\mathbf{b}}{k}\stackrel{{\scriptstyle b}}{{=}}|S\setminus S(i)|$ which
is strictly positive and satisfies
$\binom{\mathbf{b}}{k}>\binom{\mathbf{a}-1}{k}$ by
$|S(i)|<\binom{\mathbf{a}-1}{k-1}$. As in (10) we have

$|\Delta(S)|\geq|\Delta(S\setminus S(i)|+|\Delta(S^{\prime}_{i})|,$ (24)

as adding $i$ to the subsets in $\Delta(S^{\prime}_{i})$ we obtain subsets in
$\Delta(S)\setminus\Delta(S\setminus S(i))$. As
$\binom{\mathbf{b}}{k}>\binom{\mathbf{a}-1}{k}$ then
$\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$ (actually
$\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ as $\mathbf{b}$ is the sequence of a
non-zero $k$-binomial decomposition), thus we can apply Lemma 2 and we have

$|\Delta(S)|\geq|\Delta(S\setminus
S(i))|+|\Delta(S^{\prime}_{i})|\geq\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}}{k-2}\geq\binom{\mathbf{a}}{k-1}=|\Delta(S)|,$

so equality holds along the above inequalities. In particular, both $S(i)$ and
$S\setminus S(i)$ are extremal, proving (i)(i.2), and the equality (i)(i.3)
holds, and there is equality in (24) thus proving (i)(i.1).

The reciprocal implication follows by just considering one element $i\in[n]$,
thus showing the second part of the result. If $i$ is such that
$S(i)<\binom{{\mathbf{a}}-1}{k-1}$, then we can repeat the argument above to
conclude that there is equality everywhere (due to the four assumptions), and
hence $S$ is extremal. If $i$ is such that $S(i)=\binom{{\mathbf{a}}-1}{k-1}$,
then the extremality on $S^{\prime}_{i}$ implies that
$|S^{\prime}_{i}|+|\Delta(S^{\prime}_{i})|=\binom{{\mathbf{a}}}{k-1}$. Then
the containment $\Delta(S\setminus S(i))\subseteq S^{\prime}_{i}$ implies that
$\Delta(S)$ (whose sets are either in $\Delta(S\setminus S(i))$, or in
$\Delta(S^{\prime}_{i})\times\\{i\\}$ or in $S_{i}^{\prime}$), have all the
sets accounted for with just $|S^{\prime}_{i}|+|\Delta(S^{\prime}_{i})|$, so
$|S^{\prime}_{i}|+|\Delta(S^{\prime}_{i})|\geq|\Delta(S)|$ implies that there
is equality in (23) and the extremality of $S$ follows. ∎

###  3.1 Examples on the necessity of the conditions

In this section we give examples showing that the conditions for the
characterization of extremal sets in Theorem 3 are mutually independent, so
none of them can be ommitted. Conditions (i)(i.1) and (i)(i.2) are of
structural nature while condition (i)(i.3) is of quantitative nature. A
natural question is to ask if the structural conditions may imply the
quantitative one. We next give an example of a set $S$ which satisfies
conditions (i)(i.1) and (i)(i.2) for each $x\in[n]$ but fails to be extremal
because the condition (i)(i.3) fails to hold, showing that the last
quantitative condition is independent from the structural ones.

######  Example 7.

For each $m\geq 3$, $n\geq m+3\geq 6$ we denote by $S_{n,k,m}$ the family

$S_{n,k,m}=\binom{[n]}{k}\setminus\left[\cup_{\\{i,j\\}\in\binom{[m]}{2}}\nabla^{k-2}(\\{i,j\\})\right],$

where $\nabla^{k-2}(X)$ denotes the $(k-2)$–iterated upper shadow of the
family $X$. The family $S_{n,k,m}$ consists of all $k$–subsets of $[n]$ which
contain none of the sets $\\{i,j\\}$ with $i\neq j$ and $i,j\leq m$. Its
cardinality is

$|S_{n,k,m}|=\binom{n}{k}-\sum_{i=2}^{k}\binom{m}{i}\binom{n-m}{k-i}=\binom{n-m}{k}+\binom{n-m}{k-1}\binom{m}{1},$

and its lower shadow is the family of all $(k-1)$–subsets of $[n]$ containing
no pair of elements in $[m]$:

$\Delta(S_{n,k,m})=S_{n,k-1,m}.$

For every $x\in[n]$ we have

$\displaystyle|S_{n,k,m}(x)|$
$\displaystyle=\begin{cases}|S_{n-1,k-1,m}|,&x\in[n]\setminus[m],\\\
|S_{n-1,k-1,m-1}|,&x\in[m],\end{cases}$ $\displaystyle|\Delta(S_{n,k,m}(x))|$
$\displaystyle=\begin{cases}|S_{n-1,k-2,m}|,&x\in[n]\setminus[m],\\\
|S_{n-1,k-2,m-1}|,&x\in[m],\end{cases},$ $\displaystyle|S_{n,k,m}\setminus
S_{n,k,m}(x)|$
$\displaystyle=\begin{cases}|S_{n-1,k,m}|,&x\in[n]\setminus[m],\\\
|S_{n-1,k,m-1}|,&x\in[m],\end{cases},$
$\displaystyle|\Delta(S_{n,k,m}\setminus S_{n,k,m}(x))|$
$\displaystyle=\begin{cases}|S_{n-1,k-1,m}|,&x\in[n]\setminus[m],\\\
|S_{n-1,k-1,m-1}|,&x\in[m],\end{cases}.$

The example will be constructed from $S_{n,k,m}$ by deleting a family
$L\subset\binom{[n]\setminus[m]}{k}$. For every such choice of $L$, let

$S=S_{n,k,m}\setminus L.$

Since every set $y$ in the shadow of $\binom{[n]\setminus[m]}{k}$ is contained
in the shadow of $y\cup\\{i\\}\in S$ for each $i\in[m]$ we have

$\Delta(S)=\Delta(S_{n,k,m}).$

Moreover, by the same reason, for every $x\in[n]$, we also have

$\Delta(S(x))=\Delta(S_{n,k,m}(x))\quad\text{and}\quad\Delta(S\setminus
S(x))=\Delta(S_{n,k,m}\setminus S_{n,k,m}(x)).$

For positive integers $t$ and $r$ with $t\geq r$, let $n=tk+m$ and let $L$ be
an $r$–regular family of $k$–subsets of $[n]\setminus[m]$, each element in
$[n]\setminus[m]$ belongs to $r$ subsets of $L$ (such a family exists since
$n-m=tk$ is a multiple of $k$, and $|L|=tr$).

Appropriate choices of the parameters $k,m$ and $t$ provide examples of sets
$S$ satisfying conditions (i)(i.1) and (i)(i.2) for each $x\in[n]$ but fail to
be extremal because the condition (i)(i.3) does not hold.

For example, for $m=k=4$, $t=29$ and $r=2$ we have $n=tk+4=120$ and
$|L|=tr=58$ and $S_{n,k,m}$ satisfies

$\displaystyle|S_{n,k,m}|$
$\displaystyle=\binom{119}{4}+\binom{112}{3}+\binom{104}{2}+\binom{58}{1}$
$\displaystyle|\Delta(S_{n,k,m})|=|S_{n,k-1,m}|$
$\displaystyle=\binom{119}{3}+\binom{112}{2}+\binom{105}{1},$

so that $S_{n,k,m}$ is an extremal set. However, for the set
$S=S_{n,m,k}\setminus L$

$\displaystyle|S|=|S_{n,k,m}|-|L|$
$\displaystyle=\binom{119}{4}+\binom{112}{3}+\binom{104}{2},$

and $\Delta(S)=\Delta(S_{n,k,m})=S_{n,k-1,m}$, so that $S$ is not extremal.
Nevertheless, the families $S(x)$ and $S\setminus S(x)$ are extremal for all
$x\in[n]$. Indeed, if $x\in[n]\setminus[m]$, then $x$ is contained in $r=2$
sets in $L$ and

$\displaystyle|S(x)|=|S_{n-1,k-1,m}(x)|-2$
$\displaystyle=\binom{118}{3}+\binom{111}{2}+\binom{102}{1}$
$\displaystyle|\Delta(S(x))|=|S_{n-1,k-2,m}|$
$\displaystyle=\binom{1182}{+}\binom{112}{1},$ $\displaystyle|S\setminus
S(x)|=|S_{n-1,k,m}|-(tr-2)$
$\displaystyle=\binom{118}{4}+\binom{111}{3}+\binom{103}{2}+\binom{1}{1},$
$\displaystyle|\Delta(S\setminus S(x)|=|S_{n-1,k-1,m}|$
$\displaystyle=\binom{118}{3}+\binom{111}{2}+\binom{104}{1}.$

On the other hand, if $x\in[m]$ then $S(x)=S_{n,k,m}(x)$, which is extremal
since $S_{n,k,m}$ is extremal itself, and

$\displaystyle|S\setminus S(x)|=|S_{n-1,k,m-1}|-tr$
$\displaystyle=\binom{118}{4}+\binom{114}{3}+\binom{112}{2}+\binom{52}{1},$
$\displaystyle|\Delta(S\setminus S(x)|=|S_{n-1,k-1,m}|$
$\displaystyle=\binom{118}{3}+\binom{114}{2}+\binom{113}{1}.$

Moreover, in all cases we have $S(x)\setminus\\{x\\}\subset\Delta(S\setminus
S(x))$ so that the set $S$ fails to be extremal because (i)(i.3) alone does
not hold. ∎

The structural conditions are also easily seen to be independent of each
other. Some examples are given below. We recall that $I_{n,k}(m)$ denotes the
initial segment of length $m$ in the colex order. We use the notation $S\vee
S^{\prime}=\\{x\cup y:x\in S,y\in S^{\prime}\\}$ to denote the family of all
sets obtained by unions of a set in $S$ and a set in $S^{\prime}$.

######  Example 8.

A set $S$ satisfying (6) strictly and (i)(i.1) and (i)(i.3) but not (i)(i.2).
Let $k\geq 3$ and $n>k$. Let
$m_{1}=\binom{n-1}{k}+\binom{n-2}{k-1}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{b}}{k}$ and
$m_{2}=\binom{n-2}{k-2}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{c}}{k-1}$. Let $m^{\prime}_{1}=\binom{n-1}{k}$ and let
$B$ be the family of $(k-1)$–subsets of $[n+1,2n-2]$. Define

$S=(I_{n,k}(m^{\prime}_{1})\cup(B\vee\\{2n\\}))\cup(I_{n,k-1}(m_{2})\vee\\{n\\}).$

We have,

$|S|=\binom{n-1}{k}+\binom{n-2}{k-1}+\binom{n-2}{k-2}=\binom{n}{k}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{a}}{k},$

so that $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ and (6) holds. Now

$\binom{\mathbf{a}}{k-1}=\binom{n}{k-1}=\binom{n-1}{k-1}+\binom{n-2}{k-2}+\binom{n-2}{k-3}=\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}}{k-2},$

and (i)(i.3) holds. Moreover, with the choice $x=n$, $S(x)\setminus x$ is an
initial segment of length $\binom{n-2}{k-2}$ which is contained in the initial
segment of length $\binom{n-1}{k-1}$ contained in $\Delta(S\setminus S(x))$,
so (i)(i.1) holds.

However, $S\setminus S(x)$ is not extremal, as

$|\Delta(S\setminus
S(x))|=\binom{n-1}{k-1}+|\Delta(B)|=\binom{n-1}{k-1}+\binom{n-2}{k-2}+\binom{n-2}{k-3}>\binom{n-1}{k-1}+\binom{n-2}{k-2}.$

and (i)(i.2) does not hold.

By choosing instead

$S=I_{n,k}(m_{1})\cup(C\vee\\{n+1\\}),$

with $C$ an arbitrary nonextremal family of $(k-1)$-sets with cardinality
$|C|=\binom{n-2}{k-2}$ satisfying $C\subset\Delta(I_{n,k}(m_{1}))$ we obtain a
set satisfying (6) and, with the choice $x=n+1$, also satisfying (i)(i.1) and
(i)(i.2) but now $S(x)\setminus x$ is not extremal. ∎

######  Example 9.

A set $S$ satisfying (6) strictly and (i)(i.2) and (i)(i.3) but not (i)(i.1).
Let $k\geq 3$ and $n>k$. Let
$m_{1}=\binom{n-1}{k}+\binom{n-2}{k-1}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{b}}{k}$ and
$m_{2}=\binom{n-2}{k-2}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{c}}{k-1}$. Define

$S=I_{n,k}(m_{1})\cup(I_{[n+2,2n],k-1}(m_{2})\vee\\{2n+1\\}),$

where $I_{[n+2,2n],k-1}(m_{2})$ is an initial segment of length $m_{2}$ of
$(k-1)$–subsets of the interval $[n+2,2n]$. As before, we have,

$|S|=\binom{n-1}{k}+\binom{n-2}{k-1}+\binom{n-2}{k-2}=\binom{n}{k}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{a}}{k},$

so that $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ and (6) holds. We also have

$\binom{\mathbf{a}}{k-1}=\binom{n}{k-1}=\binom{n-1}{k-1}+\binom{n-2}{k-2}+\binom{n-2}{k-3}=\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}}{k-2},$

and (i)(i.3) holds. Moreover, with the choice $x=2n+1$, both $S(x)$ and
$S\setminus S(x)$ are initial segments, and hence extremal sets, so that
(i)(i.2) holds, but $S(x)\setminus x$ is not contained in $\Delta(S\setminus
S(x))$, so (i)(i.1) does not hold.∎

##  4 The key inequality

In this section we give the proof of Lemma 2. As mentioned in the
Introduction, Lemma 2 follows from the slightly more general Lemma 10 and
Corollary 11 below. The first statement shows the case $i=1$ of (5) in a more
general form (the reason being mostly technical, as the base cases of the
induction argument we have fit this scenario better). The second statement,
Corollary 11, shows the inequaliy (5) for $i>1$ and deal with the case of
equality in Lemma 2, plus some further information that allows us to show the
characterization of the cardinalities for which the colex is the unique
extremal family (up to isomorphism) in Theorem 4.

######  Lemma 10.

Let $m$ and $k,k^{\prime},k^{\prime\prime}$ be positive integers. Let
$\mathbf{a},\mathbf{b},\mathbf{c}$ be such that
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}m$, and $\mathbf{b}$ and
$\mathbf{c}$ be

  * •

strictly decreasing sequences of non-negative integers

  * •

$b_{j}\geq k^{\prime}-j-1$ and $c_{j}\geq k^{\prime\prime}-j-1$ for all $j$
for which they exists ($\mathbf{b}$ or $\mathbf{c}$ may be the empty
sequence).

Assume that

$\binom{\mathbf{a}}{k}=\binom{\mathbf{b}}{k^{\prime}}+\binom{\mathbf{c}}{k^{\prime\prime}},$
(25)

If $k^{\prime},k^{\prime\prime}\geq k$, then

$\displaystyle\binom{\mathbf{a}}{k-1}\leq\binom{\mathbf{b}}{k^{\prime}-1}+\binom{\mathbf{c}}{k^{\prime\prime}-1}.$
(26)

and

$\displaystyle\binom{\mathbf{a}-1}{k-1}\leq\binom{\mathbf{b}-1}{k^{\prime}-1}+\binom{\mathbf{c}-1}{k^{\prime\prime}-1}.$
(27)

Moreover, if $k^{\prime}=k\geq 2$ and $k^{\prime\prime}=k-1$ then (26) and
(27) holds provided that $\mathbf{b}$ is not empty and

$\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1.$ (28)

######  Corollary 11.

Let $\mathbf{a}$ be a $k$-binomial decomposition of a positive integer, and
$\mathbf{b}$ and $\mathbf{c}$ be possibly empty strictly decreasing sequences
of non-negative integers, with $b_{j}\geq k-j-1$ and $c_{j}\geq k-1-j-1$ for
all $j$ for which they exists and satisfying

$\binom{\mathbf{a}}{k}\leq\binom{\mathbf{b}}{k}+\binom{\mathbf{c}}{k-1}$ (29)

If $\mathbf{b}$ is not empty and $\mathbf{b}\geq_{lex}\mathbf{a}-1$ then, for
each $i\geq 1$,

$\binom{\mathbf{a}}{k-i}\leq\binom{\mathbf{b}}{k-i}+\binom{\mathbf{c}}{k-i-1},$
(30)

and

$\binom{\mathbf{a}-i}{k-i}\leq\binom{\mathbf{b}-i}{k-i}+\binom{\mathbf{c}-i}{k-i-1},$
(31)

Moreover, if there is equality in (30) for $i=1$ and $i=0$, then,

  * •

for each $0\leq j\leq i$,

$\binom{\mathbf{a}-j}{k-i}=\binom{\mathbf{b}-j}{k-i}+\binom{\mathbf{c}-j}{k-i}.$
(32)

  * •

if $\textbf{a}=(a_{0},\ldots,a_{t})$ with $a_{i}>a_{i+1}$ and $t<k-1$, then

$\binom{\mathbf{a}}{k}\doteq\binom{\mathbf{b}}{k}+\binom{\mathbf{c}}{k-1}$
(33)

In particular, the only choices for $\mathbf{c}$ and $\mathbf{b}$ are:

$\begin{cases}\mathbf{c}=(a_{0}-1,\ldots,a_{i-1}-1,a_{i+1},\ldots,a_{t})&\text{
and }\mathbf{b}=(a_{0}-1,\ldots,a_{i-1}-1,a_{i})\\\
\mathbf{c}=(a_{0}-1,\ldots,a_{i-1}-1)&\text{ and
}\mathbf{b}=(a_{0}-1,\ldots,a_{i-1}-1,a_{i},a_{i+1},\ldots,a_{t})\end{cases}$
(34)

for each $i\in[0,t+1]$ such that $a_{i-1}-1>a_{i}$ (with no condition when
$i=t+1$ or $i=0$).

###  4.1 Proof of Lemma 2 from Lemma 10 and Corollary 11

If $\mathbf{a}$ is a k-binomial decomposition of a strictly positive number,
then to satisfy the inequality $\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$, it
suffices to ask $\mathbf{b}$ to be, from among the strictly decreasing
sequences of non-negative numbers, one for which $b_{i}\geq k-i-1$.

If $\mathbf{b}$ and $\mathbf{c}$ are strictly decreasing sequences of non-
negative integers, then we let $\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$
be those elements for which $b_{i}\geq k-i-1$ and $c_{i}\geq k-i-1-1$, then
$\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$ are also strictly decreasing
sequences of non-negative integers, and we have

$\binom{\mathbf{b}}{k}=\binom{\mathbf{b}^{\prime}}{k},\binom{\mathbf{c}}{k-1}=\binom{\mathbf{c}^{\prime}}{k-1},\binom{\mathbf{b}}{k-1}=\binom{\mathbf{b}^{\prime}}{k-1},\binom{\mathbf{c}}{k-1-1}=\binom{\mathbf{c}^{\prime}}{k-1-1}$

the last two equalities following by the non-negativity assumption (then
$c_{k-1-1}\geq 0=k-(k-1-1)-1-1$ and $b_{k-1}\geq 0=k-(k-1)-1$, if they
exists). This shows why it is enough to show (5) when $i=1$ for those
decreasing sequences satisfying $b_{i}\geq k-i-1$ and $c_{i}\geq k-i-1-1$. In
general, for $i\geq 1$, we have that

$\binom{\mathbf{b}}{k-i}\leq\binom{\mathbf{b}^{\prime}}{k-i},\binom{\mathbf{c}}{k-i-1}\leq\binom{\mathbf{c}^{\prime}}{k-i-1}$
(35)

and thus (5) follows from Corollary 11. Observe also that, in order to show
(5) in the case of equality, we are also demanding the condition $b_{i}\geq
k-i-1$ and $c_{i}\geq k-i-1-1$, as in Corollary 11; the reason being that, if
there is a term with $0\leq b_{i}<k-i-1$ or $0\leq c_{i}<k-i-1-1$, then the
there is an $i$ for which (35) follows with an strict inequality, this,
combined with Corollary 11, shows that, in order to demand equality in (5), we
should impose the condition $b_{i}\geq k-i-1$ and $c_{i}\geq k-i-1-1$ on the
decreasing sequences of non-negative integers.

###  4.2 General comments for Lemma 10 and Corollary 11

The condition $b_{j}\geq k^{\prime}-j-1$ and $c_{j}\geq k^{\prime\prime}-j-1$
for all $j$ for which they exists on $\mathbf{b}$ and $\mathbf{c}$ can be
removed to show (26) and (30), but is needed to show (27) and (32).

The non-negativity condition on the coefficients, and the fact that they are
strictly decreasing, implies that, although there is no restriction on
$\ell(\mathbf{c})$ or $\ell(\mathbf{b})$, if there exists an element with
$b_{j}^{\prime}=k^{\prime}-j-1$ (or resp.
$c_{j}^{\prime}=k^{\prime\prime}-j-1$), then $\ell(\mathbf{b})\leq k^{\prime}$
(or, resp. $\ell(\mathbf{c})\leq k^{\prime\prime}$).

The condition $k-j-1\leq b_{j}$, the fact that they are strictly decreasing,
and $b_{j}\geq 0$, also implies that if $\binom{\mathbf{b}}{k}>0$ and
$\binom{\mathbf{b}^{\prime}}{k}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{b}}{k}$ is its $k$-binomial decomposition, then, for
each $i\geq 0$

$\binom{\mathbf{b}^{\prime}-i}{k-i}\leq\binom{\mathbf{b}-i}{k-i}$

with some inequality being strict only whenever there exists a $b_{j}$ with
$k-j-1=b_{j}$, as then the term $\binom{b_{j}-(k-j)+1}{k-j-(k-j)+1}$ turns
from $0$ to something positive by increasing $i$ from $(k-j-1)$ to $(k-j)$.

######  Observation 12.

If $\mathbf{b}$ is a $k$-binomial decomposition, then, for every $i>0$, if

  * •

$\mathbf{b}_{i}$ is defined as
$\binom{\mathbf{b}_{i}}{k-i}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{b}}{k-i}$ and

  * •

$\mathbf{b}_{i}^{\prime}$ is defined as
$\binom{\mathbf{b}_{i}^{\prime}}{k-i}\stackrel{{\scriptstyle
b}}{{=}}\binom{\mathbf{b}-i}{k-i}$

then

$\binom{\mathbf{b}_{i}}{k-i-1}=\binom{\mathbf{b}}{k-i-1},\qquad\binom{\mathbf{b}_{i}^{\prime}-1}{k-i-1}=\binom{\mathbf{b}-i-1}{k-i-1}$

###### Proof.

If there is no term $b_{k-i}$ in $\mathbf{b}$, then the result holds trivially
as $\mathbf{b}_{i}=\mathbf{b}$ and $\mathbf{b}_{i}^{\prime}=\mathbf{b}-i$. If
there is a term $b_{k-i}$, then

${\mathbf{b}\choose k-i}=\sum_{j=1}^{k-i-1}{b_{i}\choose
k-i-j}+{b_{k-i}\choose 0}=\sum_{j=1}^{k-i-1}{b_{i}\choose k-i-j}+1$

so let $s$ be the largest integer, $s\geq i+1$ for which
$b_{k-s-1}-1=b_{k-s}$. Then

$(\mathbf{b}_{i})_{j}=\begin{cases}b_{j}&\text{ if $s$ exists and
$j<k-s-1$}\\\ b_{k-s-1}+1&\text{ if $s$ exists}\\\ \text{no element}&\text{ if
$s$ exists and $j>k-s-1$}\\\ b_{j}&\text{ if $s$ does not exist and $j\neq
k-i-1$}\\\ b_{k-i-1}+1&\text{ if $s$ does not exist and $j=k-i-1$}\\\
\end{cases}$

one can then check that the equality ${\mathbf{b}_{i}\choose
k-i-1}={\mathbf{b}\choose k-i-1}$ holds (the point being that the index $s$,
if it exists for one value, it will exists also for the next value of $i$,
until it is exhausted, in which case, the other term $+1$ when $s$ does not
exists takes over). The equality ${\mathbf{b}_{i}^{\prime}-1\choose
k-i-1}={\mathbf{b}-i-1\choose k-i-1}$ follows similarly. ∎

######  Claim 1.

In Lemma 10 and Corollary 11 it suffices to show the statements whenever

$\mathbf{b}$ and $\mathbf{c}$ are $k^{\prime}$ and $k^{\prime\prime}$-binomial
decompositions, and $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ in the case
$(k^{\prime},k^{\prime\prime})=(k,k-1)$. (36)

###### Proof of Claim 1.

If $\mathbf{b}$ and $\mathbf{c}$ are strictly decreasing sequences of non-
negative integers, then we let $\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$
be those elements for which $b_{i}\geq k^{\prime}-i$ and $c_{i}\geq
k^{\prime}-i$, then $\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$ are also
strictly decreasing sequences of non-negative and are $k^{\prime}$ and
$k^{\prime\prime}$ binomial decompositions respectively (perhaps the empty
sequence). Then we have

$\displaystyle\binom{\mathbf{b}}{k^{\prime}}$
$\displaystyle=\binom{\mathbf{b}^{\prime}}{k^{\prime}},\binom{\mathbf{c}}{k^{\prime\prime}}=\binom{\mathbf{c}^{\prime}}{k^{\prime\prime}},\text{
and thus}$ $\displaystyle\binom{\mathbf{a}}{k}$
$\displaystyle=\binom{\mathbf{b}^{\prime}}{k^{\prime}}+\binom{\mathbf{c}^{\prime}}{k^{\prime\prime}},$

and also

$\displaystyle\binom{\mathbf{b}}{k^{\prime}-i}$
$\displaystyle\geq\binom{\mathbf{b}^{\prime}}{k^{\prime}-i},\binom{\mathbf{b}-i}{k^{\prime}-i}\geq\binom{\mathbf{b}^{\prime}-i}{k^{\prime}-i}$
$\displaystyle\binom{\mathbf{c}}{k^{\prime\prime}-i}$
$\displaystyle\geq\binom{\mathbf{c}^{\prime}}{k^{\prime\prime}-i},\binom{\mathbf{c}-i}{k^{\prime\prime}-i}\geq\binom{\mathbf{c}^{\prime}-i}{k^{\prime\prime}-i}$

therefore, if the inequalities (26),(27), (30), (31) can be shown for
$\mathbf{b}^{\prime}$, $\mathbf{c}^{\prime}$, then they also hold for
$\mathbf{b},\mathbf{c}$. Further, if
$\mathbf{b}^{\prime}\neq\mathbf{b}^{\prime}$ and
$\mathbf{c}^{\prime}\neq\mathbf{c}$, then the inequality for $i=1$ is strict,
and thus if we show the result with equality for binomial decompositions, then
it does not hold for sequences not corresponding to non-binomial
decompositions.

Let us now assume that $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$. Then, as
$\mathbf{a}$ is a $k$-binomial decomposition, all the terms of $\mathbf{a}-1$
are $a_{i}-1\geq k-i-1$. Furthermore, the equalities: ${\mathbf{a}\choose
k}={\mathbf{a}-1\choose k}+{\mathbf{a}-1\choose k-1}$, ${\mathbf{a}\choose
k}={\mathbf{b}\choose k}+{\mathbf{c}\choose k-1}$, and
$\mathbf{b}=_{\text{lex}}\mathbf{a}-1$, implies that ${\mathbf{a}-1\choose
k}={\mathbf{b}\choose k}$ and thus ${\mathbf{a}-1\choose
k-1}={\mathbf{c}\choose k-1}$. As $\mathbf{a}$ is a $k$ binomial
decomposition, $\mathbf{a}-1$ is a $k-1$-binomial decomposition (perhaps with
the exception that ${\mathbf{a}-1\choose k-1}$ has a term of the type
${a_{k-1}-1\choose 0}$); however, it is not hard to see that the condition
${\mathbf{a}-1\choose k-1}={\mathbf{c}\choose k-1}$ implies that
${\mathbf{a}-1\choose k-1}={\mathbf{c}^{\prime}\choose k-1}$ (as before,
$\mathbf{c}^{\prime}$ is obtained from $\mathbf{c}$ by removing the terms with
$k-i-1-1=c_{i}$, then all these terms in $\mathbf{c}$ contribute as $0$
contribute as $0$ in the binomial expression ${\mathbf{c}\choose k-1}$) and
that actually we can let ${\mathbf{a}-1\choose k-1}\stackrel{{\scriptstyle
b}}{{=}}{\mathbf{c}^{\prime}\choose k-1}$, which also implies that
${\mathbf{a}-1\choose k-1-1}={\mathbf{c}^{\prime}\choose k-1-1}$ (see
Observation 12); now the fact that $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$
implies that ${\mathbf{a}-1\choose k-1}={\mathbf{b}\choose k-1}$ which,
together with ${\mathbf{a}\choose k-1}\doteq{\mathbf{a}-1\choose
k-1}+{\mathbf{a}-1\choose k-1-1}$ shows (26) for the case
$\mathbf{b}=_{\text{lex}}\mathbf{a}-1$. The arguments for (27), (30) and (31)
follows similarly.

Finally, observe that if $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ due to an
coefficient of the type $\binom{i-1}{i}$ (so
$\mathbf{b}^{\prime}=_{\text{lex}}\mathbf{a}-1$ by removing some binomial
coefficients of the type $\binom{i-1}{i}$ from $\mathbf{b}$ to form
$\mathbf{b}^{\prime}$), and letting $\mathbf{c}^{\prime}$ obtained by removing
those elements with $c_{i}<k-1-i$, then the above argument shows that
$\binom{\mathbf{a}}{k}=\binom{\mathbf{b}^{\prime}}{k}+\binom{\mathbf{c}^{\prime}}{k-1}$
yet
$\binom{\mathbf{a}}{k-1}<\binom{\mathbf{b}^{\prime}}{k-1}+\binom{\mathbf{c}^{\prime}}{k-1-1}$
as
$\binom{\mathbf{a}}{k-1}=\binom{\mathbf{b}}{k-1}+\binom{\mathbf{c}^{\prime}}{k-1-1}$
and $\binom{\mathbf{b}}{k-1}<\binom{\mathbf{b}^{\prime}}{k-1}$. Also, if
$\mathbf{b}^{\prime}$ (obtained by removing those $b_{i}=k-i-1$ from
$\mathbf{b}$) is such that $\mathbf{b}^{\prime}<_{\text{lex}}\mathbf{a}-1$,
yet $\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$, then there exists a
$\mathbf{b}^{\prime\prime}$ obtained from $\mathbf{b}$ by removing some (and
not all) elements with $b_{i}=k-i-1$ so that
$\mathbf{b}^{\prime\prime}=_{\text{lex}}\mathbf{a}-1$. Then the argument
discussed above shows that equality holds for
$\mathbf{b}^{\prime\prime}=_{\text{lex}}\mathbf{a}-1$ and
$\mathbf{c}^{\prime}$ throughout, and strict inequality follows for
$\mathbf{b}$ (if some element has been removed), and strict inequality in the
other direction for $\mathbf{b}^{\prime}$ in (26) and (30). The cases (27) and
(31) follow with strict inequalities depending on which elements have been
removed from $\mathbf{b}$ to form $\mathbf{b}^{\prime\prime}$. This completes
the proof of the claim. ∎

Case $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$. Then, as $\mathbf{a}$ is a
$k$-binomial decomposition, all the terms of $\mathbf{a}-1$ are $a_{i}-1\geq
k-i-1$. Furthermore, the equalities: ${\mathbf{a}\choose
k}\doteq{\mathbf{a}-1\choose k}+{\mathbf{a}-1\choose k-1}$,
${\mathbf{a}\choose k}\doteq{\mathbf{b}\choose k}+{\mathbf{c}\choose k-1}$,
and $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$, implies that ${\mathbf{a}-1\choose
k}={\mathbf{b}\choose k}$ and thus ${\mathbf{a}-1\choose
k-1}={\mathbf{c}\choose k-1}$. As $\mathbf{a}$ is a $k$ binomial
decomposition, $\mathbf{a}-1$ is a $k-1$-binomial decomposition (perhaps with
the exception that ${\mathbf{a}-1\choose k-1}$ has a term of the type
${a_{k-1}-1\choose 0}$); however, it is not hard to see that the condition
${\mathbf{a}-1\choose k-1}={\mathbf{c}\choose k-1}$ implies that
${\mathbf{a}-1\choose k-1}={\mathbf{c}^{\prime}\choose k-1}$ (all the terms in
$\mathbf{c}$ not in $\mathbf{c}^{\prime}$ contribute as $0$ in the binomial
expression) and that actually ${\mathbf{a}-1\choose
k-1}\stackrel{{\scriptstyle b}}{{=}}{\mathbf{c}^{\prime}\choose k-1}$, which
also implies that ${\mathbf{a}-1\choose k-1-1}={\mathbf{c}^{\prime}\choose
k-1-1}$ (see Observation 12); now the fact that
$\mathbf{b}=_{\text{lex}}\mathbf{a}-1$ implies that ${\mathbf{a}-1\choose
k-1}={\mathbf{b}\choose k-1}$ which, together with ${\mathbf{a}\choose
k-1}\doteq{\mathbf{a}-1\choose k-1}+{\mathbf{a}-1\choose k-1-1}$ shows (26)
for the case $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$.

Case $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$. If the inequality
$\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ follows from an inequality
$b_{i}^{\prime}>_{\text{lex}}a_{i}-1$, then $b_{j}^{\prime}=b_{j}>k-j-1$ for
$j\in[0,i]$ (as $\mathbf{a}$ is a $k$-binomial decomposition), which means
that $\mathbf{b}^{\prime}>_{\text{lex}}\mathbf{a}-1$, and we may argue with
the pair $(\mathbf{b}^{\prime},\mathbf{c}^{\prime})$ instead of
$(\mathbf{b},\mathbf{c})$; if the inequality
$\mathbf{b}>_{\text{lex}}\mathbf{a}-1$ occurs only by the existence of a
$b_{i}$ for which there is no corresponding $a_{i}$ (as it does not exists),
and yet $\mathbf{b}^{\prime}<_{\text{lex}}\mathbf{a}-1$, then we have
$b_{i}=a_{i}-1$ for those $i$’s for which $a_{i}$ exists; letting
$\mathbf{b}^{\prime\prime}=_{\text{lex}}\mathbf{a}-1$ we have
$\mathbf{b}^{\prime\prime}<_{\text{lex}}\mathbf{b}$ which implies (by the non-
negativity condition on the coefficients) ${\mathbf{b}^{\prime\prime}\choose
k-1}\leq{\mathbf{b}\choose k-1}$, also that ${\mathbf{a}\choose
k}={\mathbf{b}^{\prime\prime}\choose k}+{\mathbf{c}^{\prime}\choose k-1}$ and
hence if we can show the result for
$(\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime})$ then the result also holds
for $(\mathbf{b},\mathbf{c})$. We can apply the argument for the preceeding
paragraph to show that, $\mathbf{b}^{\prime\prime}=_{\text{lex}}\mathbf{a}-1$,
then (26) holds for the pair
$(\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime})$, and thus (26) holds for
this case.

We give a sketch of the proof of Lemma 10 in Section 4.6 below. We first
discuss the notion of translation invariant identities of binomial sums which
is used in the proof and also allows us to identify the cases of equality in
(26) in relevant cases. The proof of the remaining cases of (5) in Lemma 2
(including the “moreover” part) is given in Section 4.9 as Corollary 11.

###  4.3 Translation invariance

We say that an identity $\sum_{i}\alpha_{i}{x_{i}\choose
y_{i}}=\sum_{j}\alpha_{j}^{\prime}{x^{\prime}_{j}\choose y^{\prime}_{j}}$ of
two sums of binomial coefficients is translation invariant (or simply
invariant) if, for every pair of integers $r,s$ we have

$\sum_{i}\alpha_{i}{x_{i}+r\choose
y_{i}+s}=\sum_{j}\alpha_{j}^{\prime}{x^{\prime}_{j}+r\choose
y^{\prime}_{j}+s}.$

We use the notation $\doteq$ as in $\sum_{i}\alpha_{i}{x_{i}\choose
y_{i}}\doteq\sum_{j}\alpha_{j}^{\prime}{x^{\prime}_{j}\choose y^{\prime}_{j}}$
to indicate that the identity is translation invariant.

The _binomial recurrence_

${n\choose k}\doteq{n-1\choose k}+{n-1\choose k-1}$ (37)

is an example of an invariant identity. By applying it term by term, the
binomial recurrence naturally translates to binomial sequences.

######  Lemma 13.

For a sequence ${\mathbf{a}}$ and integer $k$ we have

${{\mathbf{a}}\choose k}\doteq{{\mathbf{a}}-1\choose k}+{{\mathbf{a}}-1\choose
k-1}.$

In particular, repeated application of the binomial recurrence to a binomial
sum $\sum_{i}\alpha_{i}{x_{i}\choose y_{i}}$ gives rise to an invariant
identity. For example, for $i\geq 1$, the two usual binomial identities, that
will be used in the proof of Lemma 10,

$\displaystyle{n\choose k}$ $\displaystyle\doteq{n-1\choose k}+{n-2\choose
k-1}+\cdots+{n-i\choose k-i+1}+{n-i\choose k-i},$ (38) $\displaystyle{n\choose
k}$ $\displaystyle\doteq{n-1\choose k-1}+{n-2\choose k-1}+\cdots+{n-i\choose
k-1}+{n-i\choose k},$ (39)

are translation invariant.

We remark that a translation invariant identity may involve “hidden” binomial
coefficients. For example, the identity

${1\choose 0}={0\choose 0}+{0\choose-1},$

is translation invariant, while the identity

${1\choose 0}={0\choose 0},$

is not.

The following Proposition shows that, in fact, all translation invariant
identities arise from repeated application of the binomial recurrence (37).

######  Proposition 14 (Translation invariant characterization).

If

$A:=\sum_{i}\alpha_{i}{x_{i}\choose
y_{i}}\doteq\sum_{j}\alpha_{j}^{\prime}{x^{\prime}_{j}\choose
y^{\prime}_{j}}=:B$

for some real numbers $\alpha_{i},\alpha_{j}^{\prime}$, and integers $x_{i}$,
$x_{i}^{\prime}$, $y_{i}^{\prime}$ and $y_{i}$ and both $A$ and $B$ being
finite sums, then there exists a $C=\sum_{i}\beta_{i}{x_{i}\choose y_{i}}$
such that $A\doteq C$, $B\doteq C$, and $C$ is obtained from $A$ and from $B$
by repeated application of the binomial recurrence and cancellation of
identical terms.

###### Proof of Proposition 14.

By moving $B$ to the left hand side, the statement is equivalent to show
$A\doteq 0$ if and only if we can transform $A$ into $0$ by a sequence of
applications of the binomial recurrence ${n\choose k}={n-1\choose
k-1}+{n-1\choose k},$ and cancellation of identical terms; both these
operations are translation invariant. For convenience, let us change the index
of summation in $A$ to write

$A=\sum_{t\in\mathbb{Z}}\sum_{j\in\mathbb{Z}}\alpha_{j,t}{j\choose t}\doteq
0,$

Let $j_{0}$ and $j_{m}$ be respectively the maximal and minimal values of $j$
for which $\alpha_{j,t}\neq 0$. By repeated use of (38) or (39), we can reduce
the binomial numerators and find $A^{\prime}\doteq A$ with

$A^{\prime}=\sum_{t}\alpha_{j_{m},t}^{\prime}{j_{m}\choose t}$

Now we claim that $\alpha_{j_{m},t}^{\prime}=0$ for each $t$. Indeed, assume
that is not the case and let $t_{0}$ and $t_{m}$ be respectively maximal and
minimal index $t$ for which $\alpha_{j_{m},t}^{\prime}$ is nonzero. Then, by
translation invariance,

$0=\sum_{t_{m}\leq t\leq t_{0}}\alpha_{j_{m},t}{j_{m}\choose
t-t_{0}}=\alpha_{j_{m},t_{0}}{j_{m}\choose 0}$

and since ${j_{m}\choose 0}=1$ then $\alpha_{j_{m},t_{0}}=0$. Then the same
reasoning applies for all indices between $t_{m}$ and $t_{0}$ by an
appropriate shifting of the binomial denominators.

∎

###  4.4 A geometric representation

The following geometric representation of binomial coefficients will be handy
for the developments in this section. A binomial coefficient ${y\choose x}$ is
identified with a point $(x,y)$ in the two–dimensional integer lattice
$\mathbb{Z}^{2}$. By a diagonal in this lattice we mean a line $y=x+a$ for
some $a$ and we say that ${y\choose x}$ lies on the diagonal $y-x$. Figure 1
illustrates the geometric representation of the two invariant equalities (38)
and (39). Note that each $k$-binomial decomposition gives at most $k$ points
on the positive quarter plane, strictly between the vertical line $x=0$ and
the diagonal $y=x-1$, which can be seen as the _boundary_ of the cone of
binomial decompositions.

Figure 1: The equality of the binomial coefficient represented by the black
point and the sum of binomial coefficients represented by white points is
invariant by translations.

###  4.5 Walls, rubble, and pavement

A wall is a binomial sum which has precisely one binomial coefficient in each
_diagonal_ of a set of nonnegative consecutive diagonals (the binomial
coefficient $\binom{n}{k}$ belongs to the diagonal $n-k$, see Section 4.4).
For example, the right–hand side of (39) excluding the last binomial
coefficient is a wall. Let ${\ell}$ be a non-negative integer and let
${\mathbf{w}}=(w_{0},w_{1},\ldots,w_{h})$ be a nonincreasing sequence of
integers with $h\leq\ell$. The wall $({\mathbf{w}},\ell)$ is the binomial sum

$({\mathbf{w}},\ell)=\sum_{i=0}^{h}{w_{i}+\ell-i\choose w_{i}},$

which has one binomial coefficient in each of the diagonals
$\ell-h,\ell-h+1,\cdots,\ell$. The walls have the lex ordering between them,
but this identification between a wall and its sum of binomial coefficients
allows for a natural comparaison between the walls and binomial expressions.
(A $k$-binomial expression is a sum of binomial coefficients and it is not
necessarily a $k$-binomial decomposition.)

We say that the wall $({\mathbf{w}},\ell)=\sum_{i=0}^{h}{w_{i}+\ell-i\choose
w_{i}}$ dominates a $k$–binomial expression ${\mathbf{b}\choose
k}=\sum_{i=0}^{t}{b_{i}\choose k-i}$ if the following three conditions hold:

  1. (D1)

$b_{0}-k\leq\ell$

  2. (D2)

if $w_{i}=k-j\geq k-t$ then $b_{j}<w_{i}+\ell-i$

  3. (D3)

$w_{0}\leq k$

We write ${\mathbf{b}\choose k}\preceq({\mathbf{w}},\ell)$ to denote that
$({\mathbf{w}},\ell)$ dominates ${\mathbf{b}\choose k}$. In this case, by
(D1), no term in the binomial expression lies in a diagonal higher than the
first term in $({\mathbf{w}},\ell)$ and, by (D2), if there is a term in
$({\mathbf{w}},\ell)$ in the same vertical line than a term in
${\mathbf{b}\choose k}$ then the latter lies on a strictly lower diagonal than
the former. Furthermore, by (D3) the first column of the wall is more to the
left (see Section 4.4) than the first column of the $k$-binomial expression.
Overall, if a wall cominates a binomial expression, then the wall is to the
top left of the binomial expression, in the geometric representation following
Section 4.4.

A binomial sum of the form $R=\sum_{i\in I}\alpha_{i}{x_{i}\choose 0}$, where
the binomial denominator of all the binomial coefficients are $0$, is called
_rubble_.

A binomial sum of the form $C=\sum_{i\in I}\alpha_{i}{i-1\choose i}$, where
the binomial denominator of all the binomial coefficients is one more than the
binomial numerator, is said to be a _pavement_.

Given two sequences $\mathbf{b}$ and $\mathbf{c}$ of length $\leq t$, we let

$\displaystyle\max\\{\mathbf{b},\mathbf{c}\\}$
$\displaystyle=(\max\\{b_{0},c_{0}\\},\ldots,\max\\{b_{t},c_{t}\\})$
$\displaystyle\min\\{\mathbf{b},\mathbf{c}\\}$
$\displaystyle=(\min\\{b_{0},c_{0}\\},\ldots,\min\\{b_{t^{\prime}},c_{t^{\prime}}\\})$

where $t^{\prime}$ is the minimal index for which both and $b_{t^{\prime}}$
and $c_{t^{\prime}}$ exist.

###  4.6 Sketch of the proof of Lemma 10

The proof of Lemma 10, (26) and (27), is by induction on $k$ and $m$. Let us
sketch the case for (26) ((27) is done similarly).

Step 1:

The base cases for the induction are for $k=1$ and all $m$, and for $m\leq k$
and all $k$.

Step 2:

The induction step assumes $m>k>1$. Then we argue that $\ell(\mathbf{b})\leq
k^{\prime}$ and $\ell(\mathbf{c})\leq k^{\prime\prime}$ and that they are
binomial decompositions can be assumed by the nature of the statements (see
Claim 1).

Step 3 (key step):

Then we find a nonzero binomial sum $S$, a rubble $R$, and a pavement $C$
where each term has value zero (each term ${i-1\choose i}$ satisfies $0<i$),
such that the following translation invariant identities hold:

$\displaystyle{\mathbf{a}\choose k}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k}+S+R$ (40)
$\displaystyle{\mathbf{b}\choose k^{\prime}}+{\mathbf{c}\choose
k^{\prime\prime}}$ $\displaystyle\doteq{\mathbf{b}^{\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}}+S+C,$ (41)

for some $k$-binomial decomposition $\mathbf{a}^{\prime}<_{lex}\mathbf{a}$,
and $\mathbf{b}^{\prime}\leq_{lex}\mathbf{b}$ and
$\mathbf{c}^{\prime}\leq_{lex}\mathbf{c}$ where $\mathbf{b}^{\prime}$ and
$\mathbf{c}^{\prime}$ are $k^{\prime}$ and $k^{\prime\prime}$ binomial
decompositions (perhaps being the empty ones).

Step 4 (small touches):

Then using that $C$ is a binomial sum representing the zero, we obtain the
equality (removing $S$ in both sides)

${\mathbf{a}^{\prime}\choose k}+R={\mathbf{b}^{\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}},$ (42)

and, as $R\geq 0$, we let

${\mathbf{a}^{\prime}\choose k}={\mathbf{b}^{\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime}\choose k^{\prime\prime}}$ (43)

with $\mathbf{b}^{\prime\prime}\leq_{\text{lex}}\mathbf{b}^{\prime}$ and
$\mathbf{c}^{\prime\prime}\leq_{\text{lex}}\mathbf{c}^{\prime}$ (prioritizing
reducing $\mathbf{c}^{\prime}$ before $\mathbf{b}^{\prime}$ so that
$\mathbf{b}^{\prime\prime}\geq_{\text{lex}}\mathbf{a}^{\prime}-1$ if such
condition is required).

Step 5 (induction):

If $S\neq\emptyset$, then ${\mathbf{b}^{\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}}\leq{\mathbf{b}^{\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}}<{\mathbf{b}\choose
k^{\prime}}+{\mathbf{c}\choose k^{\prime\prime}}$. If $S=\emptyset$ then
$R\neq\emptyset$ and ${\mathbf{b}^{\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}}<{\mathbf{b}^{\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}}={\mathbf{b}\choose
k^{\prime}}+{\mathbf{c}\choose k^{\prime\prime}}$. In both cases, we use the
induction hypothesis on (43) to conclude

${\mathbf{a}^{\prime}\choose k-1}\leq{\mathbf{b}^{\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime}\choose k^{\prime\prime}-1},$ (44)

Step 6 (concluding argument):

By using the translation invariance of (40) and (41) we obtain

$\displaystyle{\mathbf{a}\choose k-1}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k-1}+S^{\prime}+R^{\prime}$
$\displaystyle{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1}$ $\displaystyle\doteq{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose
k^{\prime\prime}-1}+S^{\prime}+C^{\prime},$

(where $S^{\prime}$, $C^{\prime}$, and $R^{\prime}$ are obtained,
respectively, from $S$, $C$ and $R$ by substracting one unit to each binomial
denominator). Now combining the above with (44), and $C^{\prime}\geq 0$, and
$R^{\prime}=0$, yields that

$\displaystyle{\mathbf{a}\choose k-1}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k-1}+S^{\prime}+R^{\prime}$
$\displaystyle={\mathbf{a}^{\prime}\choose k-1}+S^{\prime}\qquad\text{as
$R^{\prime}=0$, since $R$ is rubble}$
$\displaystyle\leq{\mathbf{b}^{\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}-1}+S^{\prime}\qquad\text{by \eqref{eq:abck-1}}$
$\displaystyle\leq{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose
k^{\prime\prime}-1}+S^{\prime}\qquad\text{as
$\mathbf{b}^{\prime\prime}\leq_{\text{lex}}\mathbf{b}^{\prime}$ and
$\mathbf{c}^{\prime\prime}\leq_{\text{lex}}\mathbf{c}^{\prime}$}$
$\displaystyle\leq{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose
k^{\prime\prime}-1}+S^{\prime}+C^{\prime}\qquad\text{$C^{\prime}\geq 0$}$
$\displaystyle\doteq{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1}\qquad\text{by translation invariance}$ (45)

which gives the desired inequality (26).

The detail of the implementation of this strategy can be found in the
following subsections. The most challenging condition is to find the $R$, $S$,
$C$ with the desired properties. We use Lemma 15 below to perform such
reduction, with some additional case analysis.

The reduction from Lemma 15 is based on pushing the elements of $\mathbf{b}$,
$\mathbf{c}$ and a part of $\mathbf{a}$ (forming a wall) away from each other,
pushing the $\mathbf{b}$ towards the bottom border (coefficients of the type
${i-1\choose i}$ with $i>0$ grouped in the pavement $C$), and the $\mathbf{a}$
towards the left-hand-side vertical line (coefficients of the type ${i\choose
0}$ grouped in the rubble); when $\mathbf{b}$ or $\mathbf{c}$ collide with the
wall, they are grouped in $S$.

The case analysis is done as the induction jumps through the sequence
$\mathbf{a}$ substracting one unit to one of its elements not necessarily the
last one (the case we are substracting one to ${a_{k-1}\choose 1}$ is treated
separately). We also should control the condition
$\mathbf{b}^{\prime}\geq_{\text{lex}}\mathbf{a}^{\prime\prime}-1$, which is
handled “externally” to the reduction argument.

###  4.7 Reducing the wall and pair of $k$-binomial decompositions

######  Lemma 15 (Recursive reduction).

Let $k\geq 1$ be an integer, $({\mathbf{w}},\ell)$ be a wall of height $h$,
$\mathbf{b}$ and $\mathbf{c}$ be $k$-binomial decompositions.

Assume $\max\\{\mathbf{b},\mathbf{c}\\}=\mathbf{b}$,
$\min\\{\mathbf{b},\mathbf{c}\\}=\mathbf{c}$, $\mathbf{b}$ and
$({\mathbf{w}},\ell)$ are not the empty set, ${\mathbf{b}\choose
k}\preceq({\mathbf{w}},\ell)$, ${\mathbf{c}\choose
k}\preceq({\mathbf{w}},\ell)$, and $w_{h}\geq 1$. Then,

  1. (i)

there exist: a wall $({\mathbf{w}}^{\prime},\ell)$, $k$-binomial decomposition
$\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$, a rubble $R=\sum_{i\in
I}{i\choose 0}$, a pavement $C=\sum_{i\in J}{i-1\choose i}$ with $j\geq 1$ for
all $j$ in the multiset of integers $J$, and a sum of binomial coefficients
$S$ such that

${\mathbf{b}\choose k}+{\mathbf{c}\choose k}\doteq{\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k}+C+S$

and

$({\mathbf{w}},\ell)\doteq({\mathbf{w}}^{\prime},\ell)+R+S$

with ${\mathbf{w}}^{\prime}<_{\text{lex}}{\mathbf{w}}$ and $w_{i}^{\prime}\leq
w_{i}$ for each $i$ (for which it makes sense), ${\mathbf{b}^{\prime}\choose
k}\preceq({\mathbf{w}}^{\prime},\ell)$, ${\mathbf{c}^{\prime}\choose
k}\preceq({\mathbf{w}}^{\prime},\ell)$, $b_{0}^{\prime}\leq b_{0}$,
$c_{0}^{\prime}\leq c_{0}$, ${\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k}<{\mathbf{b}\choose k}+{\mathbf{c}\choose
k}$.

  2. (ii)

Furthermore,
$\max\\{\mathbf{b}^{\prime},\mathbf{c}^{\prime}\\}=\mathbf{b}^{\prime}$,
$\min\\{\mathbf{b}^{\prime},\mathbf{c}^{\prime}\\}=\mathbf{c}^{\prime}$.

  3. (iii)

If, additionally, $b_{0}-k\geq\ell$, then (i) holds, and
$({\mathbf{w}}^{\prime},\ell)$ is the empty wall.

  4. (iv)

If, additionally, $w_{0}\geq k$, then (i) holds and $\mathbf{b}^{\prime}$ is
the empty sequence and $\mathbf{c}^{\prime}=\mathbf{c}$.

Before proceeding further, let us show the immediate consequence of Lemma 15
that we use in the arguments.

######  Corollary 16 (Recursive Reduction, final form).

With the same assumptions as Lemma 15, there exist a wall
$({\mathbf{w}}^{\prime},\ell)$, $k$-binomial decompositions
$\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$, a rubble $R=\sum_{i\in
I}{i\choose 0}$, a pavement $C=\sum_{i\in J}{i-1\choose i}$ with $j\geq 1$ for
all $j$ in the multiset of integers $J$, and a sum of binomial coefficients
$S$ such that

${\mathbf{b}\choose k}+{\mathbf{c}\choose k}\doteq{\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k}+C+S$

and

$({\mathbf{w}},\ell)\doteq({\mathbf{w}}^{\prime},\ell)+R+S$

with either $({\mathbf{w}}^{\prime},\ell)$ the empty wall, or both
$\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$ being the empty sequences.

###### Proof of Corollary 16.

Apply Lemma 15 to $({\mathbf{w}},\ell)$, $\mathbf{b}$, $\mathbf{c}$ and obtain
$[({\mathbf{w}}^{\prime},\ell),\mathbf{b}^{\prime},\mathbf{c}^{\prime},R,S,C]$.
Now,

  * •

If Lemma 15 part (i)+(ii) are satisfied, then we apply again Lemma 15 with
$k\leftarrow k$, $({\mathbf{w}},\ell)\leftarrow({\mathbf{w}}^{\prime},\ell)$,
$\mathbf{b}\leftarrow\mathbf{b}^{\prime}$, and
$\mathbf{c}\leftarrow\mathbf{c}^{\prime}$ with strictly smaller
${\mathbf{w}}^{\prime}<_{\text{lex}}{\mathbf{w}}$ and
${\mathbf{b}^{\prime}\choose k}+{\mathbf{c}^{\prime}\choose
k}<{\mathbf{b}\choose k}+{\mathbf{c}\choose k}$.

  * •

If Lemma 15 part (iii) is satisfied, then we are done.

  * •

If Lemma 15 part (iv) is satisfied, and $({\mathbf{w}},\ell)$ is not the empty
wall, then we apply Lemma 15 again with $k\leftarrow k$,
$({\mathbf{w}},\ell)\leftarrow({\mathbf{w}}^{\prime},\ell)$,
$\mathbf{b}\leftarrow\mathbf{c}^{\prime}$, and
$\mathbf{c}\leftarrow\emptyset$.

  * •

If $({\mathbf{w}},\ell)$ is the empty set, then the statement is satisfied.

  * •

If $\mathbf{b}$ and $\mathbf{c}$ are the empty set, then the statement is
satisfied.

Thus, repeating one of the points above, and as we are always reducing either
$({\mathbf{w}},\ell)$, $\mathbf{b}$ or $\mathbf{c}$ we finish in one of the
conditions given in the statement of the corollary. ∎

###### Proof of Lemma 15.

Observe that we are actually showing three results, (i)+(ii), (iii), and (iv).
All the results are shown by induction on ${\mathbf{w}}$, and
${\mathbf{b}\choose k}+{\mathbf{c}\choose k}$, with the base cases begin when
$({\mathbf{w}},\ell)$ is the empty set, or $\mathbf{b}$ (and hence
$\mathbf{c}$) being the empty set. In those cases, the respective
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}$ and
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}},\ell)$ satisfy the
conditions.

Let $j=b_{t}-(k-t)$ be the diagonal where the last term of ${\mathbf{b}\choose
k}$ lies on. We perform a case analysis in $j$.

Case 1: $\ell-h\leq j\leq\ell$. In this case the “$\mathbf{b}$ hits the wall”.
Some case analysis.

Case 1.1: If $k-t<k$. We use (iii) on $k\leftarrow k-t$
$\mathbf{b}\leftarrow(b_{t})$, $\mathbf{c}\leftarrow\emptyset$,
$({\mathbf{w}},\ell)\leftarrow((w_{\ell-j},\ldots,w_{h}),j)$, to obtain
$\mathbf{b}^{\prime\prime}$, $\mathbf{c}^{\prime\prime}$,
$({\mathbf{w}}^{\prime\prime},j)$ as the empty set, $R^{\prime\prime}$,
$S^{\prime\prime}$, $C^{\prime\prime}$.

To show (iv), we apply (iv) again with
$\mathbf{b}\leftarrow(b_{0},\ldots,b_{k-t-1},\mathbf{b}^{\prime\prime})$,
$\mathbf{c}\leftarrow\mathbf{c}$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{\ell-j-1}),\ell)$, to obtain
$\mathbf{b}^{\prime\prime\prime}$ the empty set,
$\mathbf{c}^{\prime\prime\prime}$, $({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R^{\prime\prime\prime}$, $S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$.
Then (iv) follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$ the empty set,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

To show [(i)+(ii), (iii)] we apply [(i)+(ii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,b_{k-t-1},\max\\{\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime\prime}\\})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{t-1},\min\\{\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime\prime}\\})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{\ell-j-1}),\ell)$, to obtain
$\mathbf{b}^{\prime\prime\prime}$, $\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime\prime\prime},\ell)$, $R^{\prime\prime\prime}$,
$S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$. Then [(i)+(ii), (iii)]
follows with $\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

Case 1.2: If $k-t=k$. Then $b_{t}-(k-t)=b_{0}-k=\ell$, and
$b_{0}-(k-w_{0})=w_{0}+\ell$. The condition ${\mathbf{b}\choose
k}\preceq({\mathbf{w}},\ell)$ prevents this case from occuring when showing
(iv).

We let

${b_{0}\choose k}\doteq\sum_{i=0}^{k-w_{0}-1}{b_{0}-i-1\choose
k-i}+{b_{0}-(k-w_{0})\choose w_{0}}.$

There is a further case analysis.

Case 1.2.1: If $b_{0}>k$.

Then we inductively apply (iii) (as we are in this case when $k-t=k$), again
with $\mathbf{b}\leftarrow(b_{0}-1,b_{0}-2,\ldots,b_{0}-(k-w_{0}))$,
$\mathbf{c}\leftarrow\emptyset$,
$({\mathbf{w}},\ell^{\prime\prime})\leftarrow((w_{1},\ldots,w_{h}),\ell-1)$
and obtain $\mathbf{b}^{\prime\prime}$, $\mathbf{c}^{\prime\prime}$ the empty
set, $({\mathbf{w}}^{\prime\prime},\ell^{\prime\prime})$ the empty set,
$R^{\prime\prime}$, $S^{\prime\prime}$, $C^{\prime\prime}$.

Then (iii) follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}$, $({\mathbf{w}}^{\prime},\ell)$ the
empty wall, $R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$,
$S\leftarrow S^{\prime\prime\prime}+S^{\prime\prime}+{b_{0}-(k-w_{0})\choose
w_{0}}$, $C\leftarrow C^{\prime\prime\prime}+C^{\prime\prime}$.

Then (i)+(ii) follows with
$\mathbf{b}^{\prime}\leftarrow\max\\{\mathbf{b}^{\prime\prime\prime},\mathbf{c}\\}$,
$\mathbf{c}^{\prime}\leftarrow\min\\{\mathbf{b}^{\prime\prime\prime},\mathbf{c}\\}$,
$({\mathbf{w}}^{\prime},\ell)$ the empty wall, $R\leftarrow
R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}+{b_{0}-(k-w_{0})\choose w_{0}}$,
$C\leftarrow C^{\prime\prime\prime}+C^{\prime\prime}$.

Case 1.2.2: If $b_{0}=k$. Then $\ell=0$, and there is no more wall after
removing the term ${b_{0}-(k-w_{0})\choose w_{0}}$.

Then (iii) follows with $\mathbf{b}^{\prime}$ the empty sequence,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}$, $({\mathbf{w}}^{\prime},\ell)$ the
empty wall, $R\leftarrow\emptyset$, $S\leftarrow{b_{0}-(k-w_{0})\choose
w_{0}}$,
$C\allowbreak\leftarrow\allowbreak\sum_{i=0}^{k-w_{0}-1}\allowbreak{b_{0}-i-1\choose
k-i}$.

Then (i)+(ii) follows with $\mathbf{b}^{\prime}\leftarrow\mathbf{c}$,
$\mathbf{c}^{\prime}$ the empty sequence, $({\mathbf{w}}^{\prime},\ell)$ the
empty wall, $R\leftarrow\emptyset$, $S\leftarrow{b_{0}-(k-w_{0})\choose
w_{0}}$, $C\leftarrow\sum_{i=0}^{k-w_{0}-1}{b_{0}-i-1\choose k-i}$.

Case 2: $0\leq j<\ell-h$. In this case the “wall is above $\mathbf{b}$”.

Case 2.1: $w_{h}>k-t$. So $\mathbf{b}$ streches strictly beyond the vertical
given by $w_{h}$. Use the column of $w_{h}$ to kill the corresponding part of
$\mathbf{b}$, then add the part of $c$ and continue. That is to say.

We use (iii) on $k\leftarrow w_{h}$
$\mathbf{b}\leftarrow(b_{k-w_{h}},\ldots,b_{t})$,
$\mathbf{c}\leftarrow\emptyset$,
$({\mathbf{w}},\ell-h)\leftarrow((w_{h}),\ell-h)$, to obtain
$\mathbf{b}^{\prime\prime}$ as the empty set, $\mathbf{c}^{\prime\prime}$ as
the empty set, $({\mathbf{w}}^{\prime\prime},\ell-h)$, $R^{\prime\prime}$,
$S^{\prime\prime}$, $C^{\prime\prime}$.

To show (iv), we apply (iv) with
$\mathbf{b}\leftarrow(b_{0},\ldots,b_{k-t-1},\mathbf{b}^{\prime\prime})$,
$\mathbf{c}\leftarrow\mathbf{c}$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{\ell-j-1}),\ell)$, to obtain
$\mathbf{b}^{\prime\prime\prime}$ the empty set,
$\mathbf{c}^{\prime\prime\prime}$, $({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R^{\prime\prime\prime}$, $S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$.
Then (iv) follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$ the empty set,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

To show [(i)+(ii), (iii),(iv)] we apply [(i)+(ii),(iii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,b_{w_{h}-1},c_{w_{h}},\ldots,c_{t^{\prime}})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{w_{h}-1})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{h-1},{\mathbf{w}}^{\prime\prime}),\ell)$,
to obtain $\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime\prime\prime}$, $({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R^{\prime\prime\prime}$, $S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$.
Then [(i)+(ii), (iii),(iv)] follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

Case 2.2: $w_{h}=k-t$. So $\mathbf{b}$ streches right until the vertical of
the last part of the wall. We use $w_{h}$ to explicitly remove $b_{t}$ and
continue.

Let

${w_{h}+\ell-h\choose w_{h}}\doteq\sum_{i=0}^{w_{h}+\ell-h-
b_{t}-1}{w_{h}+\ell-h-i-1\choose w_{h}-1}+{b_{t}\choose w_{h}}$ (46)

Case 2.2.1: $w_{h}>1$. To show [(i)+(ii), (iii),(iv)] we apply
[(i)+(ii),(iii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,\allowbreak b_{t-1},c_{t})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{t-1})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{h-1},w_{h}-1,\ldots,w_{h}-1),\ell)$
($w_{h}+\ell-h-b_{t}$ copies of $w_{h}-1$), to obtain
$\mathbf{b}^{\prime\prime\prime}$, $\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime\prime\prime},\ell)$, $R^{\prime\prime\prime}$,
$S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$. Then [(i)+(ii),
(iii),(iv)] follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+{b_{t}\choose w_{h}}$, $C\leftarrow
C^{\prime\prime\prime}$.

Case 2.2.2: $w_{h}=1$. To show [(i)+(ii), (iii),(iv)] we apply
[(i)+(ii),(iii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,\allowbreak b_{t-1},c_{t})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{t-1})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{h-1}),\ell)$, to obtain
$\mathbf{b}^{\prime\prime\prime}$, $\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime\prime\prime},\ell)$, $R^{\prime\prime\prime}$,
$S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$. Then [(i)+(ii),
(iii),(iv)] follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+\sum_{i=0}^{w_{h}+\ell-h-
b_{t}-1}{w_{h}+\ell-h-i-1\choose w_{h}-1}$, $S\leftarrow
S^{\prime\prime\prime}+{b_{t}\choose w_{h}}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

Case 2.3: $w_{h}<k-t$. Extend $b_{t}$ until beneath $w_{h}$, which will be
above the extended part of $b_{t}$; then erase that part with $w_{h}$ using
(iii), and continue. this involve a case analysis depending on the leftover
part of $b_{t}$.

Let

${b_{t}\choose k-t}\doteq\sum_{i=0}^{k-w_{h}-1}{b_{t}-i-1\choose
k-i}+{b_{t}-(k-w_{h})\choose w_{h}}$ (47)

We use (iii) on $k\leftarrow w_{h}$ $\mathbf{b}\leftarrow(b_{t}-(k-w_{h}))$,
$\mathbf{c}\leftarrow\emptyset$,
$({\mathbf{w}},\ell-h)\leftarrow((w_{h}),\ell-h)$, to obtain
$\mathbf{b}^{\prime\prime}$ as the empty set, $\mathbf{c}^{\prime\prime}$ as
the empty set, $({\mathbf{w}}^{\prime\prime},\ell-h)$, $R^{\prime\prime}$,
$S^{\prime\prime}$, $C^{\prime\prime}$.

Note that $S^{\prime\prime}$ will be ${b_{t}-(k-w_{h})\choose w_{h}}$, as we
will use case 2.2 in the following step. Now there is a case analysis, as we
should decide where to put the leftover from the decomposition of
${\mathbf{b}_{t}\choose k-t}$ from (47).

Case 2.3.1: $b_{t}>k$. To show [(i)+(ii), (iii),(iv)] we apply
[(i)+(ii),(iii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,\allowbreak
b_{t-1},\max\\{(b_{t}-1,\ldots,b_{t}-(k-w_{h}-1)-1),(c_{t})\\})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{t-1},\max\\{(b_{t}-1,\ldots,b_{t}-(k-w_{h}-1)-1),(c_{t})\\})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{h-1},{\mathbf{w}}^{\prime\prime}),\ell)$,
to obtain $\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime\prime\prime}$, $({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R^{\prime\prime\prime}$, $S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$.
Then [(i)+(ii), (iii),(iv)] follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}$.

Case 2.3.2: $b_{t}=k$. To show [(i)+(ii), (iii),(iv)] we apply
[(i)+(ii),(iii), (iv)] inductively to
$\mathbf{b}\leftarrow(b_{0},\ldots,\allowbreak b_{t-1},c_{t})\\})$,
$\mathbf{c}\leftarrow(c_{0},\ldots,c_{t-1})$,
$({\mathbf{w}},\ell)\leftarrow((w_{0},\ldots,w_{h-1},{\mathbf{w}}^{\prime\prime}),\ell)$,
to obtain $\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime\prime\prime}$, $({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R^{\prime\prime\prime}$, $S^{\prime\prime\prime}$, $C^{\prime\prime\prime}$.
Then [(i)+(ii), (iii),(iv)] follows with
$\mathbf{b}^{\prime}\leftarrow\mathbf{b}^{\prime\prime\prime}$,
$\mathbf{c}^{\prime}\leftarrow\mathbf{c}^{\prime\prime\prime}$,
$({\mathbf{w}}^{\prime},\ell)\leftarrow({\mathbf{w}}^{\prime\prime\prime},\ell)$,
$R\leftarrow R^{\prime\prime\prime}+R^{\prime\prime}$, $S\leftarrow
S^{\prime\prime\prime}+S^{\prime\prime}$, $C\leftarrow
C^{\prime\prime\prime}+C^{\prime\prime}+\sum_{i=0}^{k-w_{h}-1}{b_{t}-i-1\choose
k-i}$. ∎

In Figure 2 we can find a geometric representation of the reductions performed
in Lemma 15.

(1.a)

(1.b)

(2.1)

(2.2)

Figure 2: The solid blue points are from ${\mathbf{b}\choose k}$, the solid
red points are from $({\mathbf{w}},\ell)$, the hollow points are the result of
the reductions in the various cases of Lemma 15 and the bicolored points are
the terms in $S$.

######  Remark 1.

Lemma 15 is used in two places: the proof of Lemma 10 and the proof of
Corollary 11. One could define the $n$-rubble ($n$ for negative) to be a sum
of binomial terms of the form ${\cdot\choose-1}$. Then a statement similar to
Lemma 15 follows with $w_{h}\geq 0$, and were the rubble $R$ is an $n$-rubble.
The proof of such statement is similar as the argument leading to Lemma 15,
but the boundary cases for $w_{h}$ are $0$ instead of $1$. This implies that
the cases 2.2.1 and 2.2.2 dissapear, and the new boundary cases occur in Case
2.3, where the separate case when $w_{h}=k-t-1=0$ should be distinguished;
this is the one creating the rubble with binomial denominators $-1$. The
rubble of the type ${\cdot\choose-1}$ very slightly simplifies the argument
leading Lemma 10 and sketched in Section 4.6. On the other hand, it gives
difficulties in showing Corollary 11, as there we crucually use the properties
of the rubble with ${\cdot\choose 0}$.

###  4.8 Proof of Lemma 10

The proof of inequality (26) in Lemma 10 is by induction on $k$ and
$m={\mathbf{a}\choose k}$.

#### Base cases 1: $k=1$ and any $m>0$.

For $k=1$ the result holds for each $m$. Indeed, we have ${\mathbf{a}\choose
k-1}=1$. If $k^{\prime},k^{\prime\prime}\geq k$, then at least of
${\mathbf{b}\choose k^{\prime}}$ or ${\mathbf{c}\choose k^{\prime\prime}}$ is
non-empty, and it contains a binomial coefficient that is larger or equal to
${i\choose i}$ with $i\geq 1$, hence ${\mathbf{b}\choose
k^{\prime}-1}+{\mathbf{c}\choose k^{\prime\prime}-1}\geq 1$. If $k^{\prime}=1$
and $k^{\prime\prime}=k-1$, and ${\mathbf{b}\choose k}\geq 1$, then
${\mathbf{b}\choose k-1}\geq 1$ and the result also holds (as
${\mathbf{c}\choose k-2}$ is $\geq 0$ if ${\mathbf{c}\choose k-1}$ is non-
empty and $=0$ if it is the empty sequence). If $k^{\prime}=1$ and
$k^{\prime\prime}=k-1$, and ${\mathbf{b}\choose k}=0$, then the condition
$\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$ forces $b_{0}=k-1$, which implies
that ${\mathbf{b}\choose k-1}\geq 1$, and thus shows the statement in these
first base cases.

#### Base cases 2: any $k>1$ and $m\leq k$.

We have

${\mathbf{a}\choose k}=\sum_{i=0}^{m-1}{k-i\choose k-i},$ ${\mathbf{b}\choose
k^{\prime}}=\sum_{i=0}^{m^{\prime}-1}{k^{\prime}-i\choose
k^{\prime}-i}+\sum_{i=m^{\prime}}^{m^{\prime\prime\prime}-1}{k^{\prime}-i-1\choose
k^{\prime}-i}$

and

${\mathbf{c}\choose
k^{\prime\prime}}=\sum_{i=0}^{m^{\prime\prime}-1}{k^{\prime\prime}-i\choose
k^{\prime\prime}-i}+\sum_{i=m^{\prime\prime}}^{m^{\prime\prime\prime\prime}-1}{k^{\prime\prime}-i-1\choose
k^{\prime\prime}-i}$

while

${\mathbf{a}\choose k-1}=\sum_{i=0}^{m-1}{k-i\choose k-i-1},$
${\mathbf{b}\choose
k^{\prime}-1}=\sum_{i=0}^{m^{\prime}-1}{k^{\prime}-i\choose
k^{\prime}-i-1}+\sum_{i=m^{\prime}}^{m^{\prime\prime\prime}-1}{k^{\prime}-i-1\choose
k^{\prime}-i-1}$

and

${\mathbf{c}\choose
k^{\prime\prime}-1}=\sum_{i=0}^{m^{\prime\prime}-1}{k^{\prime\prime}-i\choose
k^{\prime\prime}-i-1}+\sum_{i=m^{\prime\prime}}^{m^{\prime\prime\prime\prime}-1}{k^{\prime\prime}-i-1\choose
k^{\prime\prime}-i-1}\;.$

The case $k^{\prime},k^{\prime\prime}\geq k$ clearly holds as, for each $i$
for which $b_{i}\geq k^{\prime}-i$ exists then ${b_{i}\choose
k^{\prime}-i-1}\geq{a_{i}\choose k-i-1}$ (and the same holds whenever
$c_{i}\geq k^{\prime\prime}-i$), and there is the same number of terms in both
places of binomial coefficients at both sides of the equality
${\mathbf{a}\choose k}={\mathbf{b}\choose k^{\prime}}+{\mathbf{c}\choose
k^{\prime\prime}}$. To show the case $k^{\prime}=k,k^{\prime\prime}=k-1$ we
either have ${\mathbf{b}\choose k}>0$ and then we may use a similar argument
as before, or we have ${\mathbf{b}\choose k}=0$. In this second case, the
condition $\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$ imposed on the
representation of zero implies that ${\mathbf{b}\choose k-1}\geq m$. Then, if
$m\leq k-1$ we have ${\mathbf{c}\choose k-2}=(k-1)+(k-2)+\ldots+(k-m)$ while
${\mathbf{a}\choose k-1}=k+(k-1)+\ldots+(k-(m-1))$ and thus showing the
result. The case when $m=k$ we have ${\mathbf{a}\choose k-1}=\binom{k+1}{2}$
while ${\mathbf{c}\choose k-2}=\binom{k}{2}$ and ${\mathbf{b}\choose k-1}\geq
k$, thus showing the result as well in this case.

#### Induction step.

Assume that $m>k>1$. We assume that $k^{\prime}\geq k^{\prime\prime}$. We may
also assume that

$(b_{0},k^{\prime})\neq(a_{0},k)$ (48)

since otherwise we may delete ${b_{0}\choose k^{\prime}}$ and ${a_{0}\choose
k}$ in (3) and apply induction on $k$. Similarly,
$(c_{0},k^{\prime\prime})\neq(a_{0},k)$.

Using Claim 1, it suffices to show the statement when (36) is satisfied.

Let $r$ be the largest subscript such that $a_{r}-(k-r)=a_{0}-k$. Thus
${a_{r}\choose k-r}$ corresponds to the smaller binomial coefficient in
${\mathbf{a}\choose k}$ on the same diagonal as ${a_{0}\choose k}$. We write
${a_{r}\choose k-r}={a_{r}-1\choose k-r}+{a_{r}-1\choose k-r-1}$ and let
$\mathbf{a}^{\prime}$ be the sequence obtained from $\mathbf{a}$ by replacing
$a_{r}$ by $a_{r}-1$. By the definition of $r$ and the fact that $m>k$,
${\mathbf{a}^{\prime}\choose k}$ is a $k$–binomial decomposition.

Now there is a small case analysis on $r$. Observe that, as $\mathbf{a}$ is a
$k$-binomial decomposition, $0\leq r\leq k-1$.

Case $r=k-1$. Then $k-r-1=0$. We have

${\mathbf{a}\choose k}\doteq{\mathbf{a}^{\prime}\choose k}+{a_{r}-1\choose
k-r-1}\doteq{\mathbf{a}^{\prime}\choose k}+{a_{r}-1\choose
0}\doteq{\mathbf{a}^{\prime}\choose k}+{a_{r}-1\choose
0}\doteq{\mathbf{a}^{\prime}\choose k}+R={\mathbf{a}^{\prime}\choose k}+1$

Now, if $\mathbf{c}$ is a $k^{\prime\prime}$-binomial decomposition different
from $0$, then we consider ${\mathbf{c}^{\prime}\choose
k^{\prime\prime}}\stackrel{{\scriptstyle b}}{{=}}{\mathbf{c}\choose
k^{\prime\prime}}-1$ and $\mathbf{b}^{\prime}=\mathbf{b}$; if $\mathbf{c}$ is
a $k^{\prime\prime}$-binomial decomposition equal to $0$, then we consider
${\mathbf{b}^{\prime}\choose k^{\prime}}\stackrel{{\scriptstyle
b}}{{=}}{\mathbf{b}\choose k^{\prime}}-1$ and $\mathbf{c}^{\prime}=\mathbf{c}$
the empty decomposition. In both cases we have
$\mathbf{b}^{\prime}\leq_{\text{lex}}\mathbf{b}$,
$\mathbf{c}^{\prime}\leq_{\text{lex}}\mathbf{c}$, and binomial decompositions,
and $\mathbf{b}^{\prime}\geq_{\text{lex}}\mathbf{a}^{\prime}-1$. Then we also
have

$\displaystyle{\mathbf{a}^{\prime}\choose k}$
$\displaystyle={\mathbf{b}^{\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}}$ (49)
$\displaystyle{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}-1}$
$\displaystyle\leq{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1}$ $\displaystyle{\mathbf{a}^{\prime}\choose k-1}$
$\displaystyle={\mathbf{a}\choose k-1}$

The last equality follows as ${\mathbf{a}\choose k-1}>k$, and $r$ is on the
largest diagonal and $r=k-1$, so $a_{k-1}-1\geq 1$, and we are only
substracting $1$ unit to ${\mathbf{a}\choose k}$. Since
$\mathbf{a}^{\prime}\leq_{\text{lex}}\mathbf{a}$, and is a $k$-binomial
decomposition, and $\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$ are
$k^{\prime},k^{\prime\prime}$-binomial decompositions (and
$\mathbf{b}^{\prime}\geq_{\text{lex}}\mathbf{a}^{\prime}-1$ in the $(k,k-1)$
case), by (49) we may apply the induction hypothesis on
$\mathbf{a}^{\prime},\mathbf{b}^{\prime},\mathbf{c}^{\prime}$ to conclude that

${\mathbf{a}^{\prime}\choose k-1}\leq{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose k^{\prime\prime}-1}$

and then, if $R^{\prime}={a_{r}-1\choose-1}=0$, we have:

${\mathbf{a}\choose k-1}\doteq{\mathbf{a}^{\prime}\choose
k-1}+R^{\prime}\leq{\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose
k^{\prime\prime}-1}+R^{\prime}={\mathbf{b}^{\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime}\choose
k^{\prime\prime}-1}\leq{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1}$

showing the claim in this case.

Case $0\leq r<k-1$. Then $k-r-1\geq 1$, and we consider the wall
$W={a_{r}-1\choose k-r-1}$ which satisfies $w_{0}=w_{h}=k-r-1\geq 1$. By (36),
$\mathbf{b},\mathbf{c}$ are $k^{\prime}$ and $k^{\prime\prime}$ binomial
decompositions. Let us further assume that:

there exists the term $b_{k^{\prime}-k+r+1}$ in $\mathbf{b}$ or the term
$c_{k^{\prime\prime}-k+r+1}$ in $\mathbf{c}$. (50)

The case when (50) is not satisfied is given in the “Otherwise” case below.

Let $k^{\prime\prime\prime}=k-r-1$, and lets define ${\mathbf{b}^{+}\choose
k^{\prime\prime\prime}}$ and ${\mathbf{c}^{-}\choose k^{\prime\prime\prime}}$
as

$\displaystyle\mathbf{b}^{+}$
$\displaystyle=\max\\{(b_{k^{\prime}-k+r+1},b_{k^{\prime}-k+r+1+1},\ldots,b_{k^{\prime}-1}),(c_{k^{\prime\prime}-k+r+1},c_{k^{\prime\prime}-k+r+1},\ldots,c_{k^{\prime\prime}-1})\\},$
$\displaystyle\mathbf{c}^{-}$
$\displaystyle=\min\\{(b_{k^{\prime}-k+r+1},b_{k^{\prime}-k+r+1+1},\ldots,b_{k^{\prime}-1}),(c_{k^{\prime\prime}-k+r+1},c_{k^{\prime\prime}-k+r+1},\ldots,c_{k^{\prime\prime}-1})\\}$

Using (50), the resulting binomial sums ${\mathbf{b}^{+}\choose
k^{\prime\prime\prime}}$ and ${\mathbf{c}^{-}\choose k^{\prime\prime\prime}}$
are $k^{\prime\prime}$–binomial decompositions, and at least
${\mathbf{b}^{+}\choose k^{\prime\prime\prime}}$ is non-empty. We denote by

$\displaystyle\mathbf{b}^{in}$
$\displaystyle=\begin{cases}(b_{0},\ldots,b_{k^{\prime}-k+r})&\text{if
$b_{k^{\prime}-k+r+1}$ exists}\\\ \mathbf{b}&\text{otherwise}\end{cases}$
$\displaystyle\mathbf{c}^{in}$
$\displaystyle=\begin{cases}(c_{0},\ldots,c_{k^{\prime\prime}-k+r})&\text{if
$c_{k^{\prime\prime}-k+r+1}$ exists}\\\
\mathbf{c}&\text{otherwise}\end{cases}$

the initial segments of the sequences $\mathbf{b}$ and $\mathbf{c}$, so that
${\mathbf{b}^{in}\choose k^{\prime}}$ is a $k^{\prime}$–binomial decomposition
and ${\mathbf{c}^{in}\choose k^{\prime\prime}}$ is a
$k^{\prime\prime}$–binomial decomposition

Note: if (50) is not satisfied, then $\mathbf{b}=\mathbf{b}^{in}$ and
$\mathbf{c}=\mathbf{c}^{in}$. (51)

Since these simply involve a rearrangement of the binomial sums, we certainly
have

${\mathbf{b}^{in}\choose k^{\prime}}+{\mathbf{b}^{+}\choose
k^{\prime\prime\prime}}+{\mathbf{c}^{in}\choose
k^{\prime\prime}}+{\mathbf{c}^{-}\choose
k^{\prime\prime\prime}}\;\;\doteq\;\;{\mathbf{b}\choose
k^{\prime}}+{\mathbf{c}\choose k^{\prime\prime}}$ (52)

######  Claim 2.

The wall $W={a_{r}-1\choose k-r-1}$ (equivalently $((k-r-1),a_{r}-1-(k-r-1))$)
dominates ${\mathbf{b}\choose k^{\prime}}$ and ${\mathbf{c}\choose
k^{\prime\prime}}$, and ${\mathbf{b}^{+}\choose k^{\prime\prime\prime}}$ and
${\mathbf{c}^{-}\choose k^{\prime\prime\prime}}$.

###### Proof.

Since $k^{\prime},k^{\prime\prime}\geq k^{\prime\prime\prime}$, and
$k^{\prime\prime\prime}=k-r-1=w_{0}$, then condition (D3) also holds for
${\mathbf{b}\choose k^{\prime}}$, ${\mathbf{c}\choose k^{\prime\prime}}$,
${\mathbf{b}^{+}\choose k^{\prime\prime\prime}}$, ${\mathbf{c}^{-}\choose
k^{\prime\prime\prime}}$. In particular, and since each binomial coefficient
of ${\mathbf{b}^{+}\choose k^{\prime\prime}}$ and ${\mathbf{c}^{-}\choose
k^{\prime\prime}}$ comes from ${\mathbf{b}\choose k^{\prime}}$ and
${\mathbf{c}\choose k^{\prime\prime}}$, it suffices to show that $W$ dominates
${\mathbf{b}\choose k^{\prime}}$ and ${\mathbf{c}\choose k^{\prime\prime}}$.

We observe that ${b_{0}\choose k^{\prime}}\leq{\mathbf{b}\choose
k^{\prime}}\leq{\mathbf{a}\choose k}<{a_{0}+1\choose k}$. Since binomial
coefficients are increasing along diagonals and vertical lines and
$k^{\prime}\geq k$, then ${b_{0}\choose k^{\prime}}$ lies on a diagonal not
larger than $a_{0}-k$, and so do all terms of ${\mathbf{b}\choose
k^{\prime}}$. A similar argument applies to ${\mathbf{c}\choose
k^{\prime\prime}}$ if $k^{\prime\prime}\geq k$. If $k^{\prime\prime}=k-1$ and
$k^{\prime}=k$ then (36) implies that $\mathbf{c}\leq_{lex}\mathbf{a}-1$. This
proves condition (D1) for ${\mathbf{b}\choose k^{\prime}}$ and
${\mathbf{c}\choose k^{\prime\prime}}$.

Let us show that (D2) holds. By (D1), all terms in ${\mathbf{b}\choose
k^{\prime}}$ and in ${\mathbf{c}\choose k^{\prime\prime}}$ lie in not larger
diagonals than $a_{0}-k$. Suppose that ${b_{0}\choose k^{\prime}}$ is in the
same diagonal as ${a_{0}\choose k}$. Then $k^{\prime}>k$ as we are assuming
${b_{0}\choose k^{\prime}}\neq{a_{0}\choose k}$ (see (48)). Hence,
${b_{0}\choose k^{\prime}}>{a_{0}\choose k}$ and ${\mathbf{b}\choose
k^{\prime}}\leq{\mathbf{a}\choose k}$ imply that, if there is a term of
${\mathbf{b}\choose k^{\prime}}$ in the vertical line of ${a_{r}-1\choose
k-r-1}$ then it should lie below it, as the tail $\sum_{i>r}{a_{i}\choose
k-i}<{a_{r}-1\choose k-r-1}$ (note that $r$ is the largest index on the
largest diagonal). If ${b_{0}\choose k^{\prime}}$ is in a lower diagonal than
${a_{0}\choose k}$ (which is the same as the diagonal of ${a_{r}-1\choose
k-r-1}$), then a term of ${\mathbf{b}\choose k^{\prime}}$ in the vertical line
of ${a_{r}-1\choose k-r-1}$, if exists, is below it. A similar argument
applies to ${\mathbf{c}\choose k^{\prime\prime}}$ in the case that
$k^{\prime\prime}\geq k$. In the case that $k^{\prime\prime}=k-1$ then
$k^{\prime}=k$ and as before (36) implies that
$\mathbf{c}\leq_{lex}\mathbf{a}-{\mathbf{1}}$. It follows that a term of
${\mathbf{c}\choose k^{\prime\prime}}$ in the vertical line of
${a_{j}-1\choose k-j-1}$, if exists, is below it. This shows (D2). ∎

Using Claim 2, and the definition of ${\mathbf{b}^{+}\choose
k^{\prime\prime\prime}}$ and ${\mathbf{c}^{-}\choose k^{\prime\prime\prime}}$,
we conclude that the triple $\left[W,{\mathbf{b}^{+}\choose
k^{\prime\prime\prime}},{\mathbf{c}^{-}\choose k^{\prime\prime\prime}}\right]$
satisfy the assumptions of Corollary 16 with $k\leftarrow k^{\prime\prime}$,
$({\mathbf{w}},\ell)\leftarrow((k-r-1),a_{r}-1-(k-r-1))=W$ wall of height $0$,
$\mathbf{b}\leftarrow\mathbf{b}^{+}$, and
$\mathbf{c}\leftarrow\mathbf{c}^{-}$. Hence, we obtain the pentuple
$\left(\left[W^{\prime},{\mathbf{b}_{1}\choose
k^{\prime\prime\prime}},{\mathbf{c}_{1}\choose
k^{\prime\prime\prime}}\right],S_{1},R_{1},C_{1}\right)$ with

> $W^{\prime}$ is the empty sum or, $\mathbf{b}_{1}$ and $\mathbf{c}_{1}$ are
> the empty sequences.

Now we do a case analysis. We shall observe that, if $b_{k^{\prime}-k+r+1}$ or
$c_{k^{\prime\prime}-k+r+1}$ does not exists, then ${\mathbf{c}^{-}\choose
k^{\prime\prime\prime}}$ is the empty sequence all along the process involved
in Corollary 16 (see the condition $c_{0}^{\prime}\leq c_{0}$ in Part (i)).

If $W^{\prime}$ is the empty sum. Then the reduction process is finished. We
let

${\mathbf{b}^{\prime\prime}\choose
k^{\prime}}=\begin{cases}{\mathbf{b}^{in}\choose
k^{\prime}}+{\mathbf{b}_{1}\choose k^{\prime\prime\prime}}&\text{if
$b_{k^{\prime}-k+r+1}$ exists and $(\mathbf{b}^{in},\mathbf{b}_{1})$ is
strictly decreasing}\\\ {\mathbf{b}^{in}\choose
k^{\prime}}+{\mathbf{c}_{1}\choose k^{\prime\prime\prime}}&\text{if
$b_{k^{\prime}-k+r+1}$ exists and $(\mathbf{b}^{in},\mathbf{b}_{1})$ is not
strictly decreasing}\\\ {\mathbf{b}^{in}\choose k^{\prime}}&\text{
otherwise}\end{cases}$

and

${\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}}=\begin{cases}{\mathbf{c}^{in}\choose
k^{\prime\prime}}+{\mathbf{c}_{1}\choose k^{\prime\prime\prime}}&\text{if
$b_{k^{\prime}-k+r+1}$ exists and $(\mathbf{b}^{in},\mathbf{b}_{1})$ is
strictly decreasing}\\\ {\mathbf{c}^{in}\choose
k^{\prime\prime}}+{\mathbf{b}_{1}\choose k^{\prime\prime\prime}}&\text{if
$b_{k^{\prime}-k+r+1}$ exists and $(\mathbf{b}^{in},\mathbf{b}_{1})$ is not
strictly decreasing}\\\ {\mathbf{c}^{in}\choose
k^{\prime\prime}}+{\mathbf{b}_{1}\choose k^{\prime\prime\prime}}&\text{
otherwise}\end{cases}$

and $S=S_{1}$, $R=R_{1}$, $C=C_{1}$. The argument for the case
$k^{\prime},k^{\prime\prime}\geq k$ continues below.

For the case $k^{\prime}=k,k^{\prime\prime}=k-1$: if
$b^{in}_{0}=b_{0}^{\prime\prime}$ does not exist correspond to cases with
$m<k$ (by the condition $\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$), which are
treated in the base cases. Now, since $a_{r}^{\prime}=a_{r}-1\geq k-r$
(otherwise $m<k$), we have that if $\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$,
then $\mathbf{b}^{in}>_{\text{lex}}\mathbf{a}^{\prime}-1$, as
$b^{in}_{r}=b_{r}$ if $b_{r}$ exists, or there exists a smaller index $0\leq
r^{\prime}<r$ with
$b_{r}=b^{in}_{r^{\prime}}>a_{r^{\prime}}=a^{\prime}_{r^{\prime}}$, and thus
$\mathbf{b}^{in}>_{\text{lex}}\mathbf{a}^{\prime}-1$ follows as well, which
implies that $\mathbf{b}^{\prime\prime}>_{\text{lex}}\mathbf{a}^{\prime}-1$.

Otherwise: $\mathbf{b}_{1}$ and $\mathbf{c}_{1}$ are the empty sequences. We
certainly have $W^{\prime}<{\mathbf{b}^{in}\choose
k^{\prime}}+{\mathbf{c}^{in}\choose k^{\prime\prime}}$ (as
$W<{\mathbf{b}^{in}\choose k^{\prime}}+{\mathbf{b}^{+}\choose
k^{\prime\prime\prime}}+{\mathbf{c}^{in}\choose
k^{\prime\prime}}+{\mathbf{c}^{-}\choose k^{\prime\prime\prime}}$). We also
have ${\mathbf{b}^{in}\choose k^{\prime}}\preceq W^{\prime}$ and
${\mathbf{c}^{in}\choose k^{\prime}}\preceq W^{\prime}$. This instance also
handles the case when (50) is not satisfied using (51). We apply the Corollary
16 to $[W^{\prime},{\mathbf{c}^{in}\choose k^{\prime}},\emptyset]$ with return
either $([\emptyset,{\mathbf{c}_{2}\choose
k^{\prime}},\emptyset],S_{2},R_{2},D_{2})$ or
$[W^{\prime\prime},\emptyset,\emptyset]$; in the first case we stop, and in
the second we apply Corollary 16 again to
$[W^{\prime\prime},{\mathbf{b}^{in}\choose k^{\prime}},\emptyset]$ and will
obtain $([\emptyset,{\mathbf{b}_{3}\choose
k^{\prime}},\emptyset],S_{3},R_{3},D_{3})$ (as
$W^{\prime}<{\mathbf{b}^{in}\choose k^{\prime}}+{\mathbf{c}^{in}\choose
k^{\prime\prime}}$ and the reduction of the wall leaves some non-zero summand,
the ruble, while the reductions of $\mathbf{b}$ and $\mathbf{c}$ leave a non-
zero summan, the pavement). In the first case, we let
$\mathbf{b}^{\prime\prime}=\mathbf{b}^{in}$,
$\mathbf{c}^{\prime\prime}=\mathbf{c}_{3}$, $C=C_{1}+C_{2}$, $R=R_{1}+R_{2}$,
$S=S_{1}+S_{2}$; in the second case, we let
$\mathbf{b}^{\prime\prime}=\mathbf{b}_{3}$,
$\mathbf{c}^{\prime\prime}=\emptyset$, $C=C_{1}+C_{2}+C_{3}$,
$R=R_{1}+R_{2}+R_{3}$, $S=S_{1}+S_{2}+S_{3}$.

Resume the argumentIn both cases ($W^{\prime}$ being empty, or
$\mathbf{b}_{1}$ and $\mathbf{a}_{1}$ being empty), we can write the invariant
identities

$\displaystyle{\mathbf{b}\choose k^{\prime}}+{\mathbf{c}\choose
k^{\prime\prime}}$ $\displaystyle\doteq{\mathbf{b}^{\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime}\choose k^{\prime\prime}}+S+C,$ (53)
$\displaystyle{\mathbf{a}\choose k}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k}+{a_{r}-1\choose
k-r-1}\doteq{\mathbf{a}^{\prime}\choose k}+S+R.$ (54)

As $C=0$, it follows that

${\mathbf{a}^{\prime}\choose k}+R={\mathbf{b}^{\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime}\choose k^{\prime\prime}},$

Now, let ${\mathbf{b}^{\prime\prime\prime}\choose k^{\prime}}$
${\mathbf{c}^{\prime\prime\prime}\choose k^{\prime\prime}}$ be two binomial
decompositions such that

${\mathbf{a}^{\prime}\choose k}={\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}}+{\mathbf{c}^{\prime\prime\prime}\choose k^{\prime\prime}},$

and where $\mathbf{b}^{\prime\prime\prime}$ and
$\mathbf{c}^{\prime\prime\prime}$ have been obtained by first decreasing
$\mathbf{c}^{\prime\prime\prime}$ and then $\mathbf{b}^{\prime\prime\prime}$
if $\mathbf{c}^{\prime\prime\prime}$ turns to be the empty sequence. In
particular,
$\mathbf{b}^{\prime\prime\prime}\leq_{\text{lex}}\mathbf{b}^{\prime\prime}$
and
$\mathbf{c}^{\prime\prime\prime}\leq_{\text{lex}}\mathbf{c}^{\prime\prime}$
which means that

${\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime\prime}\choose
k^{\prime\prime}-1}\leq{\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime\prime}\choose k^{\prime\prime}-1}.$
(55)

Overall, we have that either $R\neq\emptyset$ or $S\neq\emptyset$, which in
particular implies that ${\mathbf{b}^{\prime\prime\prime}\choose k^{\prime}}$
${\mathbf{c}^{\prime\prime\prime}\choose k^{\prime\prime}}<{\mathbf{b}\choose
k^{\prime}}+{\mathbf{c}\choose k^{\prime\prime}}$. Furthermore, in the case
that $k^{\prime}=k$ and $k^{\prime\prime}=k-1$ we also have
$\mathbf{b}^{\prime\prime}\geq_{\text{lex}}\mathbf{a}^{\prime}-1$, and thus
$\mathbf{b}^{\prime\prime\prime}\geq_{\text{lex}}\mathbf{a}^{\prime}-1$
Therefore, by induction,

${\mathbf{a}^{\prime}\choose k-1}\leq{\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime\prime}\choose k^{\prime\prime}-1}.$
(56)

On the other hand, by translation invariance, (53), (54), we conclude that

$\displaystyle{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1}$ $\displaystyle\doteq{\mathbf{b}^{\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}-1}+S^{\prime}+C^{\prime},$ (57)
$\displaystyle{\mathbf{a}\choose k-1}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k-1}+S^{\prime}+R^{\prime},$
(58)

where $S^{\prime}$, $C^{\prime}$ and $R^{\prime}$ are obtained by sustracting
one unit to all lower terms of binomial coefficients in $S$, $C$ and $R$
respectively. As the pavement $C$ has the extra property that the terms
${i-1\choose i}$ satisfy $i\geq 1$, then $C^{\prime}\geq 0$, and as all the
binomial denominators of the terms in $R$ are $0$, then $R^{\prime}=0$. It
follows that

$\displaystyle{\mathbf{a}\choose k-1}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose
k-1}+S^{\prime}+R^{\prime}\qquad\eqref{eq:ind_step_3}$
$\displaystyle={\mathbf{a}^{\prime}\choose k-1}+S^{\prime}\qquad\text{as
$R^{\prime}=0$}$ $\displaystyle\leq{\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime\prime}\choose
k^{\prime\prime}-1}+S^{\prime}\qquad\text{by \eqref{eq:ind_step}}$
$\displaystyle\leq{\mathbf{b}^{\prime\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime\prime}\choose
k^{\prime\prime}-1}+S^{\prime}+C^{\prime}\qquad\text{$C^{\prime}\geq 0$}$
$\displaystyle\leq{\mathbf{b}^{\prime\prime}\choose
k^{\prime}-1}+{\mathbf{c}^{\prime\prime}\choose
k^{\prime\prime}-1}+S^{\prime}+C^{\prime}\qquad\eqref{eq:ind_step_2}$
$\displaystyle\doteq{\mathbf{b}\choose k^{\prime}-1}+{\mathbf{c}\choose
k^{\prime\prime}-1},\qquad\eqref{eq:ind_step_4}$ (59)

completing the proof for this general case.

######  Observation 17.

If $C$ is not the empty set in this induction step, then there is an strict
inequality in (59) and thus in (26).

The proof of inequality (27) of Lemma 10 follows with similar arguments as the
one above for (26). Let us highlight the differences. The term $C^{\prime}$
does not contribute to the inequality, unless the terms are of the type
${0\choose 1}$ in $C$, that turn into ${-1\choose 0}=1$ in $C^{\prime}$; in
particular, Observation 17 holds only in this case. $R^{\prime}$ behaves as in
the previous case. The base cases are similar: for $k=1$, as it only matters
that we are achieving the terms with binomial denominator being $0$, the same
argument holds. For the case $k>1$ and $m<k$, since we have the same number of
terms in both sides, and they continue to be of the type ${i\choose i}$, (27)
holds; this argument also can be extended to $m=k$.

###  4.9 Proof of Corollary 11, or (5) of Lemma 2

Let us first show (30) and (31).

Now:

  1. 1.

Use Claim 1 on the given $(\mathbf{a},\mathbf{b},\mathbf{c})$ to obtain
$(\mathbf{a},\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime\prime})$ with
$\mathbf{b}^{\prime\prime}$ and $\mathbf{c}^{\prime\prime}$ being binomial
decompositions.

  2. 2.

Reduce the $\mathbf{c}^{\prime\prime}$ to $\mathbf{c}^{\prime\prime\prime}$,
if needed, to obtain an equality ${\mathbf{a}\choose
k}={\mathbf{b}^{\prime\prime}\choose
k}+{\mathbf{c}^{\prime\prime\prime}\choose k-1}$. If
$\mathbf{c}^{\prime\prime\prime}$ turn into zero, then
$\mathbf{b}^{\prime\prime}=\mathbf{a}$ and the results are obtained.

  3. 3.

Apply Lemma 10 to
$(\mathbf{a},\mathbf{b}^{\prime\prime},\mathbf{c}^{\prime\prime\prime})$

  4. 4.

Use Observation 12 on the result to obtain new $k-1$, $k-1$, and $k-2$
binomial decompositions
$(\mathbf{a}^{\prime},\mathbf{b}^{\prime\prime\prime},\mathbf{c}^{\prime\prime\prime\prime})$.

  5. 5.

Repeat this procedure beginning at Step 2, until the first binomial
decomposition is comprised of a ${\cdot\choose 0}$ term; at this point, the
argument is finished and the inequalities (30) and (31) are shown.

Let us now move on towards the “moreover” part. The hypothesis states that we
have equalities for the quadruples: $(\mathbf{a},\mathbf{b},\mathbf{c},k)$ and
$(\mathbf{a},\mathbf{b},\mathbf{c},k-1)$. That is,

${\mathbf{a}\choose k}={\mathbf{b}\choose k}+{\mathbf{c}\choose
k-1},{\mathbf{a}\choose k-1}={\mathbf{b}\choose k-1}+{\mathbf{c}\choose k-2}$

then we consequently have

${\mathbf{a}+1\choose k}={\mathbf{b}+1\choose k}+{\mathbf{c}+1\choose k-1},$

and $\mathbf{a}+1,\mathbf{b}+1,\mathbf{c}+1$ are all binomial decompositions.
Then we have, by (31) applied to $(\mathbf{a}+1,\mathbf{b}+1,\mathbf{c}+1,k)$
with $i=2$, and (31) to $(\mathbf{a},\mathbf{b},\mathbf{c},k-1)$, which are
also binomial decompositions for such “$k$”, and obtain that:

${\mathbf{a}-1\choose k-2}\leq{\mathbf{b}-1\choose k-2}+{\mathbf{c}\choose
k-3},{\mathbf{a}-1\choose k-1}\leq{\mathbf{b}-1\choose k-1}+{\mathbf{c}\choose
k-2}$

with the previous equality

${\mathbf{a}\choose k-1}={\mathbf{b}\choose k-1}+{\mathbf{c}\choose k-2}$

we conclude that, actually,

${\mathbf{a}-1\choose k-2}={\mathbf{b}-1\choose k-2}+{\mathbf{c}\choose
k-3},{\mathbf{a}-1\choose k-1}={\mathbf{b}-1\choose k-1}+{\mathbf{c}\choose
k-2}$

so we have equalities for $(\mathbf{a}-1,\mathbf{b}-1,\mathbf{c}-1,k-1)$ and
$(\mathbf{a}-1,\mathbf{b}-1,\mathbf{c}-1,k-2)$. Then a similar argument will
claim equalities for all $(\mathbf{a}-i,\mathbf{b}-i,\mathbf{c}-i,k-i)$ and
$(\mathbf{a}-i,\mathbf{b}-i,\mathbf{c}-i,k-i-1)$ for all $i\geq 0$ (the first
pair of equalities being the ones of the hypothesis).

In particular, we have equality for $k-i=1$, so
$(\mathbf{a}-(k-1),\mathbf{b}-(k-1),\mathbf{c}-(k-1),1)$ and
$(\mathbf{a}-(k-1),\mathbf{b}-(k-1),\mathbf{c}-(k-1),0)$. Now, this implies
that we have also all the equalities:

$(\mathbf{a}-(k-1)+j,\mathbf{b}-(k-1)+j,\mathbf{c}-(k-1)+j,1)$ and for all
$j\geq 0$.

Now we use $(\mathbf{a}-(k-1)+1,\mathbf{b}-(k-1)+1,\mathbf{c}-(k-1)+1,1)$ and
the equality for $(\mathbf{a}-i,\mathbf{b}-i,\mathbf{c}-i,k-i)$ with $i=k-2$
to obtain an equality for
$(\mathbf{a}-(k-2)+1,\mathbf{b}-(k-2)+1,\mathbf{c}-(k-2)+1,2)$; then we use
the equality for
$(\mathbf{a}-(k-2)+1,\mathbf{b}-(k-2)+1,\mathbf{c}-(k-2)+1,2)$ and
$(\mathbf{a}-(k-1)+j,\mathbf{b}-(k-1)+j,\mathbf{c}-(k-1)+j,1)$ with $j=2$ to
obtain an equality
$(\mathbf{a}-(k-2)+2,\mathbf{b}-(k-2)+2,\mathbf{c}-(k-2)+2,2)$. We repeat this
procedure for $j=3,4,\ldots$ to obtain all the equalities claimed in (32).

Let us now show (34) using an inductive argument. The result holds true for
$m<k$ and all $k>1$ as one can check. Assume the result holds for some
$k^{\prime}<k$ and $m^{\prime}<m$. First we use the same argument as in Claim
1 to conclude that, if we want equality

${\mathbf{a}\choose k-1}={\mathbf{b}\choose k-1}+{\mathbf{c}\choose k-2}$ (60)

then we can assume that $\mathbf{c}$ is a $k-1$ binomial decomposition and
that $\mathbf{b}$ is a $k$-binomial decomposition with
$\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$. The assumption that $\mathbf{b}$ is
a $k$-binomial decomposition only excludes, under the premise that
${\mathbf{a}\choose k-1}={\mathbf{b}\choose k-1}+{\mathbf{c}\choose k-2}$, the
case where $\mathbf{b}=\mathbf{a}-1=\mathbf{c}$ which is a valid decomposition
and it is covered by (34) with $i=t+1$. Thus, we may assume that
$\mathbf{a},\mathbf{b},\mathbf{c}$ are binomial decompositions, and we proceed
as the decomposition in the proof of Lemma 10. So, let $r$ be the largest
index for which $a_{r}-(k-r)=a_{0}-k>0$ (the $>0$ holding by the assumption
$m\geq k$). Let
$\mathbf{a}^{\prime}=(a_{0},a_{1},\ldots,a_{r-1},a_{r}-1,a_{r+1},\ldots,a_{t})$
which still have $t<k-1$, and is a $k$-binomial decomposition as $m\geq k$.
Then we obtain a decomposition (using Corollary 16 and the arguments in the
final steps of the proof of Lemma 10 to remove the wall to the empty set):

$\displaystyle{\mathbf{a}\choose k}$
$\displaystyle\doteq{\mathbf{a}^{\prime}\choose k}+{a_{r}-1\choose
k-r-1}\doteq{\mathbf{a}^{\prime}\choose k}+S+R$
$\displaystyle{\mathbf{b}\choose k}+{\mathbf{c}\choose k}$
$\displaystyle\doteq{\mathbf{b}^{\prime}\choose k}+{\mathbf{c}^{\prime}\choose
k-1}+S+C$ $\displaystyle{\mathbf{a}^{\prime}\choose k}+S+R$
$\displaystyle={\mathbf{b}^{\prime}\choose k}+{\mathbf{c}^{\prime}\choose
k-1}+S+C$ (61)

with $S$ different from the empty set. Since $\mathbf{b}$ and $\mathbf{c}$ are
binomial decompositions, then we use Observation 17 to conclude that $C$ is
the empty set (for otherwise we conclude that the hypothesis (60) does not
hold). Thus, we have that (61) reads as

${\mathbf{a}^{\prime}\choose k}+S+R={\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k}+S$ (62)

Now we know that:

${\mathbf{a}^{\prime}\choose
k-1}+S^{\prime}+R^{\prime}={\mathbf{b}^{\prime}-\choose
k}+{\mathbf{c}^{\prime}-1\choose k-2}+S^{\prime}$ (63)

as ${\mathbf{a}\choose k-1}={\mathbf{b}\choose k-1}+{\mathbf{c}\choose k-2}$
and thus

${\mathbf{a}^{\prime}\choose k-1}={\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}-1\choose k-2}$ (64)

since $R$ is just a bunch of binomial coefficients of the type ${x\choose 0}$
with $x\geq 0$ being an integer, then $R^{\prime}=\sum{x\choose-1}=0$.
However, by letting $\mathbf{a}^{\prime\prime}$ such that
${\mathbf{a}^{\prime\prime}\choose k}\stackrel{{\scriptstyle
b}}{{=}}{\mathbf{a}^{\prime}\choose k}+R$, if $R$ is not the empty set then
${\mathbf{a}^{\prime}\choose k}+R>{\mathbf{a}^{\prime}\choose k}$, and since
$\mathbf{a}^{\prime}$ has $t+1<k$ coefficients, then
${\mathbf{a}^{\prime\prime}\choose k-1}>{\mathbf{a}^{\prime}\choose k-1}$, as
${\mathbf{a}^{\prime\prime\prime}\choose k}\stackrel{{\scriptstyle
b}}{{=}}{\mathbf{a}^{\prime}\choose k}+1$ is such that
$a_{t+1}^{\prime\prime\prime}=k-(t+1)\geq 1$, which means that
${\mathbf{a}^{\prime\prime\prime}\choose k-1}>{\mathbf{a}^{\prime}\choose
k-1}$, and since
$\mathbf{a}^{\prime\prime}\geq_{\text{lex}}\mathbf{a}^{\prime\prime\prime}$,
then ${\mathbf{a}^{\prime\prime}\choose
k-1}\geq{\mathbf{a}^{\prime\prime\prime}\choose
k-1}>{\mathbf{a}^{\prime}\choose k-1}$ as claimed.

Therefore, we have that $R$ is the empty set, and thus

${\mathbf{a}^{\prime}\choose k}+S={\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k-1}+S,\qquad{\mathbf{a}^{\prime}\choose
k-1}+S^{\prime}={\mathbf{b}^{\prime}\choose k-1}+{\mathbf{c}^{\prime}\choose
k-1-1}+S^{\prime}$ (65)

and so

${\mathbf{a}^{\prime}\choose k}={\mathbf{b}^{\prime}\choose
k}+{\mathbf{c}^{\prime}\choose k-1},\qquad{\mathbf{a}^{\prime}\choose
k-1}={\mathbf{b}^{\prime}\choose k-1}+{\mathbf{c}^{\prime}\choose k-1-1}$ (66)

which, by induction hypothesis and since $\mathbf{a}^{\prime}$ has $t$
coefficients, then (34) is also satisfied. Indeed, observe that

$\displaystyle{\mathbf{a}^{\prime}\choose k}$
$\displaystyle\doteq{\mathbf{b}^{\prime}\choose k}+{\mathbf{c}^{\prime}\choose
k-1}\qquad\text{ by induction hypothesis}$ $\displaystyle{\mathbf{a}\choose
k}$ $\displaystyle\doteq{\mathbf{a}^{\prime}\choose k}+S,S={a_{r}-1\choose
k-r-1},\qquad\text{ by construction of $S$ and argument on $R=\emptyset$}$
$\displaystyle{\mathbf{b}\choose k}+{\mathbf{c}\choose k-1}$
$\displaystyle\doteq{\mathbf{b}^{\prime}\choose k}+{\mathbf{c}^{\prime}\choose
k-1}+S\qquad\text{ by construction of $S$ and argument on $D=\emptyset$}$ thus
(translation invariance is transitive) $\displaystyle{\mathbf{a}\choose k}$
$\displaystyle\doteq{\mathbf{b}\choose k}+{\mathbf{c}\choose k-1}$ (67)

which implies (33). The part (34) follows by using the induction hypothesis on
$(\mathbf{a}^{\prime},\mathbf{b}^{\prime},\mathbf{c}^{\prime})$, and then the
fact that $S$ should be produced from ${\mathbf{b}\choose
k}+{\mathbf{c}\choose k-1}$ using the operations described in Proposition 14
(in fact, depending on $\mathbf{a}$, $\mathbf{b}^{\prime}$ and
$\mathbf{c}^{\prime}$, the choices for $\mathbf{b}$ and $\mathbf{c}$ are very
limited, for instance, if the term ${a_{r}-1\choose k-r}$ is split into
${a_{r}-2\choose k-r}+{a_{r}-2\choose k-r-1}$, between $\mathbf{b}^{\prime}$
and $\mathbf{c}^{\prime}$, and $a_{r+1}\leq a_{r}-3$, then $\mathbf{b}$ and
$\mathbf{c}$ would split the term into two ${a_{r}-1\choose
k-r}+{a_{r}-1\choose k-r-1}$ as well); one may perform a small case analysis
together with the fact that the term ${a_{r}-1\choose k-r-1}$ should be spared
among $\mathbf{b}^{\prime}$ and $\mathbf{c}^{\prime}$ without leaving any
rubble. The proof is completed.

##  5 Unicity of the colex order

In this section we prove Theorem 4 on the unicity of the colex order. We start
with part (i) of the Theorem. We call a sequence noncomplete (at level $k$) if
$\ell(\mathbf{a})<k$.

######  Lemma 18.

Let $S$ be an extremal family of $\binom{[n]}{k}$ and
$\binom{\mathbf{a}}{k}\stackrel{{\scriptstyle b}}{{=}}|S|$. If $\mathbf{a}$ is
noncomplete at level $k$, then $S$ is the initial segment of length $m=|S|$ in
the colex order.

###### Proof.

The proof is by induction on $m=|S|$ and $k$. We recall that, without loss of
generality, we assume that $[n]$ is the support of $S$. Since $S$ is an
extremal set, the support is $\Delta^{k-1}(S)$ with cardinality $a_{0}$ if
$\ell(\mathbf{a})=1$ or $a_{0}+1$ if $\ell(\mathbf{a})>1$.

Choose an element $i\in[n]$ with minimum degree and let
$\binom{\mathbf{b}}{k}\stackrel{{\scriptstyle b}}{{=}}|S\setminus S(i)|$ and
$\binom{\mathbf{c}}{k-1}\stackrel{{\scriptstyle b}}{{=}}|S(i)|$. For $m\leq k$
the result holds trivially as all families of $k$–sets of $[k+1]$ are
isomorphic to initial segments of the colex order. Suppose $m>k$. Then
$a_{0}>k$ and by Theorem 3 $\mathbf{b}$ is not empty and by Lemma 6,
$\mathbf{b}\geq_{\text{lex}}\mathbf{a}-1$.

If $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$ then Theorem 3 implies that
$S(i)\setminus i$ is extremal and $\Delta(S\setminus S(i))\subset
S(i)\setminus i$. Since $\mathbf{b}=_{\text{lex}}\mathbf{a}-1$ we have
$\mathbf{c}=_{\text{lex}}\mathbf{a}-1$ as well, namely,
$|S(i)|={\mathbf{a}-1\choose k-1}$. By Theorem 1 we have $\Delta(S\setminus
S(i))\geq{\mathbf{a}-1\choose k-1}$ and the inclusion $\Delta(S\setminus
S(i))\subset S(i)\setminus i$ implies that equality holds. It follows that
$S\setminus S(i)$ is an extremal set as well. By induction, as
${\mathbf{b}\choose k}={\mathbf{a}-1\choose k}$ is noncomplete, $S\setminus
S(i)$ is an initial segment in the colex order. Therefore $\Delta(S\setminus
S(i))=S(i)\setminus i$ is also an initial segment in the colex order. By
choosing $i=1$, $S(i)$ is also an initial segment in the colex order. It
follows that $S=(S\setminus S(i))\cup S(i)$ is also an initial segment in the
colex order. This completes this case.

Suppose $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$. Then Theorem 3 implies that
both $S(i)\setminus i$ and $S\setminus S(i)$ are extremal and $S(i)\setminus
i\subset\Delta(S\setminus S(i))$. By (34), both ${\mathbf{b}\choose k}$ and
${\mathbf{c}\choose k-1}$ are incomplete. By induction both sets are initial
segments in the colex order. It remains to show that there is a common
ordering of the elements of the support in order that their union is also an
initial segment in the colex order.

We observe that, in the initial segment of the colex order $I$ with support
$[n]$, then we have $d_{I}(1)\geq d_{I}(2)\ldots\geq d_{I}(n)$. Reciprocally,
if $d_{I}(i_{1})\geq d_{I}(i_{2})\geq\cdots\geq d_{I}(i_{n})$ then $I$ is
isomorphic to the initial segment in the colex order (the isomorphism is given
by the ordering $i_{1}<i_{2}<\cdots<i_{n}$ of the support). In oher words, two
elements with the same degree can be exchanged while preserving the property
that $I$ is an initial segment in the colex order. Therefore the Claim below
completes the proof of the Theorem.

Given $i$ in the support $[n]$ of $S$, let us use the notation
$A_{i}=S(i)\setminus i$, $B_{i}=\Delta(S\setminus S(i))$ and
$C_{i}=[n]\setminus\\{i\\}$.

######  Claim 3.

Suppose $\mathbf{b}>_{\text{lex}}\mathbf{a}-1$. There is an ordering
$x_{1}<x_{2}<\cdots<x_{n-1}$ of the elements of $C_{i}$ such that
$d_{A_{i}}(x_{1})\leq\cdots\leq d_{A_{i}}(x_{n-1})$ and
$d_{B_{i}}(x_{1})\leq\cdots\leq d_{B_{i}}(x_{n-1})$.

###### Proof.

As just discussed (using (34) and the induction hypothesis) if
$\mathbf{b}>_{\text{lex}}\mathbf{a}-1$, both $A_{i}$ and $B_{i}$ are initial
segments in the colex order of $[n]\setminus\\{i\\}$. We consider three
possible cases in (34):

Case 1.

The splitting is as in (34), first equation, and $i=0$ ($i$ in (34)). Then
$|S\setminus S(i)|={a_{0}\choose k}$, $|\Delta(S\setminus S(i))|={a_{0}\choose
k-1}$ and $\Delta(S\setminus S(i))$ is the initial segment isomorphic to
${[a_{0}]\choose k}$, in which all elements have the same degree. Therefore
all orderings of elements of its support are eligible for an initial segment
in the colex order, in particular the one ordering for which $S(i)\setminus i$
is an initial segment in the colex order.

Case 2.

The splitting is as the second equation in (34). Since
$\mathbf{b}>_{\text{lex}}\mathbf{a}-1$, then $i<t+1$ ($i$ in (34)). In this
case $|\Delta(S\setminus S(i))|=\sum_{i=0}^{j}{a_{i}-1\choose
k-i-1}+\sum_{i=j+1}^{t}{a_{i}\choose k-i-1}$ and $|S(i)\setminus
i|=\sum_{i=0}^{j}{a_{i}-1\choose k-i-1}$ for $j<t+1$. Since both are initial
segments, there is one element with maximum degree ${a_{0}-1\choose k-2}$ in
both sets. Since $S(i)\setminus i\subset\Delta(S\setminus S(i))$, this should
be the same element. The next largest degree is common to
$(a_{0}-1)-(a_{1}-1+1)+1$ elements with degree

$\binom{a_{0}-2}{k-1}+\binom{a_{1}-1}{k-1-1}+\cdots+\binom{a_{j}-1}{k-j-1}+\binom{a_{j+1}}{k-(j+1)-1}+\cdots+\binom{a_{t}}{k-t-1}.$

Again the condition $S(i)\setminus i\subset\Delta(S\setminus S(i))$ implies
that both sets of $(a_{0}-1)-(a_{1}-1+1)+1$ elements are the same. We proceed
in a similar way up to the $(j-1)$–th largest degree. For the remaining points
in the support, they have the same degree in $A_{i}$ and at least this degree
in $B_{i}$, so every ordering of these elements in $B_{i}$ is suitable for the
ones in $A_{i}$.

Case 3.

If the splitting is as the first equation in (34) with $i>0$. A similar
argument as in the Case 2 yet exchanging the roles of $A_{i}$ and $B_{i}$
applies.

∎

This finishes the proof of the statement. ∎

The following example show that, if $\ell(\mathbf{a})=k$ and
$m\neq{n^{\prime}\choose k}-1$, then there are extremal families different
from the initial segment of the colex order. Let

$m=|S|\stackrel{{\scriptstyle b}}{{=}}{a_{0}\choose k}+{a_{1}\choose
k-1}+\cdots+{a_{k-1}\choose 1},a_{k-1}\geq 1.$

The initial segment of length $m$ in the colex order is

$I_{n,k}(m)={[a_{0}]\choose k}\cup\left(\\{a_{0}+1\\}\vee{[a_{1}]\choose
k-1}\right)\cup\cdots\cup\left(\\{a_{0}+1,a_{1}+1,\cdots,a_{k-2}+1\\}\vee{a_{k-1}\choose
1}\right).$

Let $r$ be the smallest index with the property that $a_{r}-(k-r)=a_{k-1}-1$,
that is, the binomial coefficient ${a_{r}\choose k-r}$ is in the same diagonal
as ${a_{k-1}\choose 1}$. Assume $r>0$ (for otherwise
$m=\binom{n^{\prime}}{k}-1$). Take the set
$X=\\{a_{0}+1,a_{1}+1,\ldots,a_{k-2}+1,a_{k-1}\\}\in I_{n,k}(m)$ and replace
$a_{r}+1$ by $a_{k-1}+1$. Let $X^{\prime}$ be the resulting set. Then

$S=(I_{n,k}(m)\setminus\\{X\\})\cup\\{X^{\prime}\\},$

has cardinality $m$, it has the same shadow as $I_{n,k}(m)$ and it is not
isomorphic to the initial segment of the colex order. If $r=0$ then
$m={a_{0}+1\choose k}-1$ and the support of $S$ is $[a_{0}]$. In this case, by
the last part of Theorem 5, the only examples of extremal sets are of the form
${[a_{0}+1]\choose k}\setminus\\{x\\}$ for some $x$, and all these are
isomorphic to the initial segment of the colex order. This completes the proof
of Theorem 4.

##  6 Final remarks

In this paper we have focussed in the arithmetic nature of the Kruskal–Katona
theorem. The key inequality in Lemma 2 has interest in its own. Even if
binomial decompositions appear mostly in connection to the Kruskal–Katona
theorem, they are also related to the study of simplicial complexes and
combinatorial geometry (the initial motivation in the Kruskal paper), and in
isoperimetric problems in the $n$–cube, where the characterization of extremal
sets is still an open problem (see e.g. Bezrukov [1, section 4]). We think
that the role of the arithmetic inequality (3) in the shadow optimization
problem is remarkable and gives perhaps the more natural way to prove the
Kruskal–Katona theorem. In particular, it easily leads to the characterization
of the extremal families given in Theorem 3. We note that the key inequality
in Lemma 10 for $k^{\prime},k^{\prime\prime}\geq k$ can be obtained from the
Kruskal–Katona theorem, but we have not found a way to derive the significant
case $k^{\prime}=k,k^{\prime\prime}=k-1$ from it.

In most relevant applications the simpler form by Lovász of the Kruskal–Katona
theorem is usually enough. Lovász formulation states that, if $x$ is the real
number defined by $m={x\choose k}$, then every family $S$ of $k$–sets with
cardinality $m=|S|$ has lower shadow of cardinality

$|\Delta(S)|\geq{x\choose k-1},$

For the above inequality, the only cases of equality are the families
${[n]\choose k}$. It may be of interest to investigate the analogous version
of Lemma 10 for this case, which we conjecture to hold.

######  Conjecture 19.

Let $x,y,z\in\mathbb{R}$ such that ${x\choose k}={y\choose k}+{z\choose k-1}$
with $y\geq x-1$. Then,

${x\choose k-1}\leq{y\choose k-1}+{z\choose k-2}.$

The analogous statement replacing $k$ and $k-1$ in the right–hand side of the
first equality by $k^{\prime},k^{\prime\prime}\geq k$ indeed holds and it is
simple to verify.

Further insight on the structural properties of the extremal families can be
obtained by an additional approach which we develop in a separate paper (see
[14] for an extended abstract and also [13]). For an extremal family $S$
(actually any family of $k$–sets), $\Delta^{k-1}(S)$ is trivially an initial
segment of the colex order. One possible measure of the distance between
extremal sets and initial segments of the colex order is the minimum $r$ such
that $\Delta^{r}(S)$ is an initial segment of the colex order ($r=0$ if $S$ is
an initial segment itself, and extremal families with $r=1$ can be seen as
small perturbations of initial segments). We show in [14] that we actually
have $r=O(loglog(n))$, which shows that extremal sets are not far from initial
segments in that sense. Moreover, large values of $r$ involve a fast
decreasing (doubly exponential) of the sequence of coefficients in the
binomial decomposition of $m=|S|$, thus making such extremal sets rather rare.
We also provide an explicit algorithm polynomial in $n$ to construct extremal
families which are at a given distance to initial segments of the colex order
in the above sense. The algorithm provides examples of extremal sets which are
structurally further away from initial segments than the simple examples given
at the end of Section 5.

Our original motivation of the current paper is the isoperimetric problem in
Johnson graphs (see e.g. [2, 9, 13]). The Johnson graph $J(n,k)$ has vertex
set ${[n]\choose k}$ and the set of neighbours of a set $S$ is
$\Delta(\nabla(S))$. The problem asks to minimize the boundary of sets $S$ of
vertices in $J(n,k)$ for each given cardinality of $S$. A family of solutions
to the problem is not known and, unlike closely related problems of this kind,
a family of nested solutions is known not to exist. Extremal families for the
Kruskal–Katona theorem provide asymptotic examples of extremal sets for the
isoperimetric problem in the Johnson graphs. It turns out that there are
extremal families different from initial segments in the colex order that beat
the initial segments in such asymptotic constructions. Therefore, a better
understanding of the extremal families for the Kruskal–Katona theorem is
instrumental in this isoperimetric problem as well.

## References

  * [1] S. L. Bezrukov.  Isoperimetric problems in discrete spaces.  Extremal problems for finite sets, 3:59–91, 1994.
  * [2] B. Bollobás and I. Leader.  Isoperimetric problems for r-sets.  Combinatorics, Probability and Computing, 13(2):277–279, 2004.
  * [3] P. Frankl.  A new short proof for the kruskal-katona theorem.  Discrete Mathematics, 48(2-3):327–329, 1984.
  * [4] P. Frankl and N. Tokushige.  The Kruskal-Katona theorem, some of its analogues and applications.  In Extremal problems for finite sets (Visegrád, 1991), volume 3 of Bolyai Soc. Math. Stud., pages 229–250. János Bolyai Math. Soc., Budapest, 1994.
  * [5] Z. Füredi and J. R. Griggs.  Families of finite sets with minimum shadows.  Combinatorica, 6(4):355–363, 1986.
  * [6] Z. Füredi and J. R. Griggs.  Families of finite sets with minimum shadows.  Combinatorica, 6(4):355–363, Dec. 1986.
  * [7] G. Katona.  A theorem of finite sets.  Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 187-207 (1968)., 1968.
  * [8] G. Katona.  A theorem of finite sets.  In Classic Papers in Combinatorics, pages 381–401. Springer, 2009.
  * [9] P. Keevash.  Shadows and intersections: stability and new proofs.  Advances in Mathematics, 218(5):1685–1703, 2008.
  * [10] M. Krivelevich and B. Sudakov.  Pseudo-random graphs.  In More sets, graphs and numbers, volume 15 of Bolyai Soc. Math. Stud., pages 199–262. Springer, Berlin, 2006.
  * [11] J. B. Kruskal.  The number of simplices in a complex.  Mathematical optimization techniques, 10:251–278, 1963.
  * [12] M. Mörs.  A generalization of a theorem of Kruskal.  Graphs Combin., 1(2):167–183, 1985.
  * [13] O. Serra and L. Vena.  Extremal families for kruskal-katona theorem.  Acta Mathematica Universitatis Comenianae, 88(3):1043 – 1048, 2019\.
  * [14] O. Serra and L. Vena.  On a problem of füredi and griggs.  Trends in Mathematics, 14:752 – 757, 2021.