# Finite element method. Detailed proofs to be formalized in Coq

François Clément, Vincent Martin

<figure><img src="image_1.png" /></figure>

► To cite this version:

François Clément, Vincent Martin. Finite element method. Detailed proofs to be formalized in Coq. RR-9557, Inria Paris. 2024, pp.172. hal-04713897

HAL Id: hal-04713897

https://inria.hal.science/hal-04713897v1

Submitted on 30 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inria

Finite element method.
Detailed proofs to be
formalized in Coq

François Clément, Vincent Martin

RESEARCH
REPORT

Nº 9557

September 2024

Project-Team Serena
<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /></figure>

Finite element method.
Detailed proofs to be formalized in Coq

François Clément*, Vincent Martin†

Project-Team Serena

Research Report n° 9557 — September 2024 — 172 pages

**Abstract:** To obtain the highest confidence on the correction of numerical simulation programs for the resolution of Partial Differential Equations (PDEs), one has to formalize the mathematical notions and results that allow to establish the soundness of the approach. The finite element method is one of the popular tools for the numerical resolution of a wide range of PDEs. The purpose of this document is to provide the formal proof community with very detailed pen-and-paper proofs for the construction of the Lagrange finite elements of any degree on simplices in positive dimension.

**Key-words:** partial differential equation, finite element method, Lagrange finite elements, simplex, detailed mathematical proof, formal proof in real analysis

This work was partly supported by the European Research Council (ERC) under the European Union's Horizon 2020 Research and Innovation Programme – Grant Agreement n°810367.

RESEARCH CENTRE
Centre Inria de Paris

48 rue Barrault
75013 Paris

<footnote>* Inria & CERMICS, École des Ponts, 77455 Marne-la-Vallée Cedex 2, France. **Francois.Clement@inria.fr**.</footnote>

<footnote>† Université de technologie de Compiègne, LMAC, 60203 Compiègne, France. **Vincent.Martin@utc.fr**.</footnote>
# Méthode des éléments finis.

## Preuves détaillées en vue d'une formalisation en Coq

**Résumé** : Pour obtenir la plus grande confiance dans l'exactitude des résultats de programmes de simulation numérique pour la résolution d'Équations aux Dérivées Partielles (EDPs), il faut formaliser les notions mathématiques sur lesquelles ils sont basés. La méthode des éléments finis est l'un des outils les plus utilisés pour la résolution de larges gammes d'EDPs. L'objectif de ce document est de fournir à la communauté des chercheurs en preuve formelle des preuves papiers très détaillées pour la construction des éléments finis de Lagrange de tout degré sur des simplexes en dimension quelconque.

**Mots-clés** : équation aux dérivées partielles, méthode des éléments finis, éléments finis de Lagrange, simplexe, preuve mathématique détaillée, preuve formelle en analyse réelle
# Foreword

This document is intended to evolve over time. Last version is release 1.0 (i.e. version 1).
It is available at https://hal.inria.fr/hal-04713897/.

Version 1 (release 1.0, 2024/09/30) is the first release.
It covers:

* the general definition of finite element;

* some results about simplicial geometry;

* the construction of simplicial Lagrange finite elements on a segment, including results about $\mathbb{P}_k^1$ Lagrange polynomials;

* the construction of simplicial Lagrange finite elements in dimension $d \ge 1$, including:

- the construction of multi-indices of given maximum length;

- results about multivariate polynomials, such as the linear independence of monomials, and the Euclidean division by a monomial;

- results about $\mathbb{P}_1^d$ Lagrange polynomials, such as their view as barycentric coordinates;

- results about affine geometric mappings such as the transformation of $l$-faces of dimension $l \le d$;

- results about Lagrange nodes and Lagrange linear forms of $\mathbb{P}_k^d$;

- the proofs of unisolvence of $\mathbb{P}_k^d$, and of face unisolvence.
# Contents

<table><tr><td>I Overview</td><td>8</td></tr><tr><td>1 Introduction</td><td>9</td></tr><tr><td>1.1 Formal proof</td><td>9</td></tr><tr><td>1.2 Objective</td><td>9</td></tr><tr><td>1.3 The finite elements</td><td>10</td></tr><tr><td>1.3.1 Some references</td><td>11</td></tr><tr><td>1.3.2 The finite element as a triple</td><td>11</td></tr><tr><td>1.3.3 Lagrange finite elements</td><td>12</td></tr><tr><td>1.3.3.1 Typology of geometries: simplex vs quadrangular</td><td>12</td></tr><tr><td>1.3.3.2 Some finite elements</td><td>13</td></tr><tr><td>1.3.3.3 Some nodal finite elements, Lagrange finite elements</td><td>13</td></tr><tr><td>1.4 Our main sources</td><td>14</td></tr><tr><td>1.5 Contents</td><td>14</td></tr><tr><td>1.6 Teaching</td><td>14</td></tr><tr><td>1.7 Disclaimer</td><td>15</td></tr><tr><td>1.8 Organization</td><td>15</td></tr><tr><td>2 Notations</td><td>17</td></tr><tr><td>3 Statements and sketches of proofs</td><td>21</td></tr><tr><td>3.1 Sketch of the proof of unisolvence of $LogP_k^d$</td><td>21</td></tr><tr><td>3.2 Sketch of the proof of Euclidean division by monomial in $P_k^d$</td><td>23</td></tr><tr><td>3.3 Multi-index ordering</td><td>24</td></tr><tr><td>3.3.1 Multi-indices and the finite element method</td><td>24</td></tr><tr><td>3.3.2 Monomial order</td><td>25</td></tr><tr><td>3.3.3 Lexicographic order</td><td>25</td></tr><tr><td>3.3.4 Graded lexicographic order</td><td>27</td></tr><tr><td>3.3.5 Graded colexicographic order</td><td>28</td></tr><tr><td>3.3.6 Graded symmetric lexicographic order</td><td>29</td></tr><tr><td>3.3.7 Graded reverse lexicographic order</td><td>30</td></tr><tr><td>3.3.8 Discussion</td><td>31</td></tr><tr><td>II Detailed proofs</td><td>33</td></tr><tr><td>4 Introduction</td><td>35</td></tr><tr><td>5 Complements</td><td>37</td></tr><tr><td>5.1 Complements on natural numbers</td><td>37</td></tr><tr><td>5.2 Complements on monoids</td><td>41</td></tr><tr><td>5.3 Complements on linear algebra</td><td>41</td></tr><tr><td>5.4 Complements on affine algebra</td><td>42</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>5.4.1 Affine subspaces</td>
      <td>43</td>
    </tr>
    <tr>
      <td>5.4.2 Affine maps and submaps</td>
      <td>45</td>
    </tr>
    <tr>
      <td>5.5 Complements on real affine geometry</td>
      <td>50</td>
    </tr>
    <tr>
      <td>5.6 Complements on univariate polynomials</td>
      <td>51</td>
    </tr>
    <tr>
      <td><b>6 Finite element</b></td>
      <td><b>53</b></td>
    </tr>
    <tr>
      <td><b>7 Simplicial geometry</b></td>
      <td><b>55</b></td>
    </tr>
    <tr>
      <td><b>8 <sup>Log</sup>P<sup>1</sup><sub>k</sub> Lagrange finite element on a segment</b></td>
      <td><b>57</b></td>
    </tr>
    <tr>
      <td>8.1 Multi-indices in dimension d = 1</td>
      <td>57</td>
    </tr>
    <tr>
      <td>8.2 <sup>P<sup>1</sup><sub>k</sub></sup> Lagrange polynomials</td>
      <td>57</td>
    </tr>
    <tr>
      <td>8.3 <sup>Log</sup><sup>P<sup>1</sup><sub>k</sub></sup> Lagrange finite element on the reference segment</td>
      <td>59</td>
    </tr>
    <tr>
      <td>8.4 <sup>Log</sup><sup>P<sup>1</sup><sub>k</sub></sup> Lagrange finite element on a current segment</td>
      <td>60</td>
    </tr>
    <tr>
      <td><b>9 <sup>Log</sup>P<sup>d</sup><sub>k</sub> Lagrange finite element in dimension d &ge; 1</b></td>
      <td><b>65</b></td>
    </tr>
    <tr>
      <td>9.1 Multi-indices</td>
      <td>66</td>
    </tr>
    <tr>
      <td>9.1.1 Some useful notations for multi-indices</td>
      <td>66</td>
    </tr>
    <tr>
      <td>9.1.2 Sets <i>A</i><sup>d</sup><sub>k</sub> and <i>C</i><sup>d</sup><sub>k</sub> of multi-indices</td>
      <td>67</td>
    </tr>
    <tr>
      <td>9.1.3 Slices of <i>C</i><sup>d</sup><sub>k</sub> and its cardinal</td>
      <td>67</td>
    </tr>
    <tr>
      <td>9.1.4 Layers of <i>A</i><sup>d</sup><sub>k</sub> and its cardinal</td>
      <td>70</td>
    </tr>
    <tr>
      <td>9.1.5 Other cardinals</td>
      <td>70</td>
    </tr>
    <tr>
      <td>9.2 Multivariate polynomials</td>
      <td>72</td>
    </tr>
    <tr>
      <td>9.2.1 Monomials and polynomials of <sup>P<sup>d</sup><sub>k</sub></sup></td>
      <td>72</td>
    </tr>
    <tr>
      <td>9.2.2 Product of polynomials</td>
      <td>73</td>
    </tr>
    <tr>
      <td>9.2.3 Linear independence of monomials</td>
      <td>74</td>
    </tr>
    <tr>
      <td>9.2.4 Decomposition of polynomials, isomorphisms of <sup>P<sup>d</sup><sub>k</sub></sup></td>
      <td>76</td>
    </tr>
    <tr>
      <td>9.2.5 Product of polynomials (alternate)</td>
      <td>79</td>
    </tr>
    <tr>
      <td>9.2.6 Composition of polynomials and affine mappings</td>
      <td>80</td>
    </tr>
    <tr>
      <td>9.3 <sup>P<sup>d</sup><sub>1</sub></sup> affine polynomials and affine geometric mapping</td>
      <td>81</td>
    </tr>
    <tr>
      <td>9.3.1 Reference affine Lagrange polynomials</td>
      <td>81</td>
    </tr>
    <tr>
      <td>9.3.2 Affine geometric mapping from <sup>R<sup>d</sup></sup> to <sup>R<sup>d</sup></sup></td>
      <td>82</td>
    </tr>
    <tr>
      <td>9.3.3 Current affine Lagrange polynomials</td>
      <td>84</td>
    </tr>
    <tr>
      <td>9.3.4 Nontrivial current simplex</td>
      <td>86</td>
    </tr>
    <tr>
      <td>9.4 Barycentric coordinates</td>
      <td>86</td>
    </tr>
    <tr>
      <td>9.5 Hyperplanes and <i>l</i>-faces</td>
      <td>88</td>
    </tr>
    <tr>
      <td>9.5.1 Hyperplanes and <i>d</i> &minus; 1-faces</td>
      <td>88</td>
    </tr>
    <tr>
      <td>9.5.2 <i>l</i>-face affine spaces and <i>l</i>-faces</td>
      <td>91</td>
    </tr>
    <tr>
      <td>9.5.3 Geometric <i>l</i>-face mappings</td>
      <td>92</td>
    </tr>
    <tr>
      <td>9.5.4 Geometric hyperface mapping</td>
      <td>94</td>
    </tr>
    <tr>
      <td>9.5.5 Geometric mapping with permutation</td>
      <td>96</td>
    </tr>
    <tr>
      <td>9.6 Lagrange nodes for <sup>Log</sup><sup>P<sup>d</sup><sub>k</sub></sup></td>
      <td>97</td>
    </tr>
    <tr>
      <td>9.6.1 Lagrange nodes for the current element</td>
      <td>97</td>
    </tr>
    <tr>
      <td>9.6.2 Sub-vertices and sub-nodes</td>
      <td>98</td>
    </tr>
    <tr>
      <td>9.6.3 Lagrange nodes for the reference element</td>
      <td>100</td>
    </tr>
    <tr>
      <td>9.6.4 Lagrange nodes and face hyperplanes</td>
      <td>101</td>
    </tr>
    <tr>
      <td>9.7 Lagrange linear forms for <sup>Log</sup><sup>P<sup>d</sup><sub>k</sub></sup></td>
      <td>102</td>
    </tr>
    <tr>
      <td>9.8 Unisolvence for <sup>Log</sup><sup>P<sup>d</sup><sub>0</sub></sup></td>
      <td>103</td>
    </tr>
    <tr>
      <td>9.9 Unisolvence for <sup>Log</sup><sup>P<sup>d</sup><sub>1</sub></sup></td>
      <td>104</td>
    </tr>
    <tr>
      <td>9.10 Unisolvence for <sup>Log</sup><sup>P<sup>d</sup><sub>k</sub></sup></td>
      <td>104</td>
    </tr>
    <tr>
      <td>9.11 <sup>Log</sup><sup>P<sup>d</sup><sub>k</sub></sup> Lagrange finite element</td>
      <td>108</td>
    </tr>
    <tr>
      <td><b>10 Conclusions, perspectives</b></td>
      <td><b>109</b></td>
    </tr>
  </tbody>
</table>
<table><tr><td>Bibliography</td><td>113</td></tr><tr><td>List of Figures</td><td>117</td></tr><tr><td>A Lists of statements</td><td>119</td></tr><tr><td>List of Definitions</td><td>119</td></tr><tr><td>List of Lemmas</td><td>121</td></tr><tr><td>List of Theorems</td><td>125</td></tr><tr><td>B The proof cites explicitly...</td><td>127</td></tr><tr><td>C Is explicitly cited in the proof of...</td><td>149</td></tr></table>
# Part I

## Overview
# Chapter 1

# Introduction

## 1.1 Formal proof

A formal proof is conducted in a logical framework that provides dedicated computer programs to mechanically check the validity of the proof, the so-called formal proof assistants. Such formal proofs may concern known mathematical theorems, but also properties of some piece of other computer programs, e.g. see [25], and [5, Glossary p. 343]. This field of computer science is extremely popular as it allows to certify with no doubt the behavior of critical programs.

Interactive theorem provers are now known to be able to tackle real analysis. For instance, in the field of Ordinary Differential Equations (ODEs) with Isabelle/HOL [27, 26, 28], and Coq [29], or in the field of Partial Differential Equations (PDEs), again with Isabelle/HOL [1], and Coq [4, 5]. In the latter example, the salient aspect is that the round-off error due to the use of IEEE-754 floating-point arithmetic can also be fully taken into account. But the price to pay is that all the details of the proofs has to be dealt with, and thus the availability of very detailed pen-and-paper proofs is a major asset.

## 1.2 Objective

Our current long-term purpose is to formally prove programs implementing the Finite Element Method (FEM). The FEM is widely used to solve a broad class of PDEs, mainly because of its sound mathematical foundation, see Section 1.3.1. A description of the typical various components that are necessary to solve a partial differential equation with the FEM is shown in Figure 1.1.

Consider a physical stationary problem over a domain $\Omega \subset \mathbb{R}^d$, where $d$ is often 1, 2 or 3. First, a *continuous* variational formulation is set on some functional spaces, typically Hilbert or Banach spaces (complete normed vector spaces, equipped or not with a scalar product) over the domain, denoted by $V$. In all cases, $V$ is infinite-dimensional and thus cannot be represented on a computer. In favorable cases, a theorem, such as the Lax–Milgram theorem (e.g. see [14]), provides existence and uniqueness of the continuous solution. Here, “continuous” means that the solution is a general function defined over the *whole* $\Omega$, in contrast to a “discrete” solution that is entirely defined by a *finite* number of data.

Second, a *discrete* variational formulation is built. To do so, a mesh is constructed on $\Omega$, i.e. a finite set of polygons that covers $\Omega$ (with additional properties). These polygons are called geometric elements. A *finite element*, i.e. a space of polynomials up to a certain degree and the type of primary values that are computed (such as values at certain points, means, fluxes), is chosen in these geometric elements. This defines the finite dimensional approximation space $V_h$ that (inexactly) represents the continuous Hilbert or Banach space $V$. The discrete variational formulation is also chosen. In some cases, it is simply the restriction of the continuous variational formula to $V_h$. In most cases, additional terms are introduced to improve some numerical features (such as robustness and convergence), this is often called the numerical scheme. A theorem should
<figure><img src="image_5.png" /><figcaption>Figure 1.1: Brief recall of the various components of a typical (stationary) FEM formulation.
The black thick arrows depict the usual construction steps when solving a problem via the FEM. The black thick
dashed arrow shows the possible feedback loop that a *posteriori* analysis allows, to change the mesh, the finite
element (i.e. the order of polynomial approximation, the quadrature formula or the numerical scheme). The red
dashed arrows depict when a theorem or a numerical tool takes place.</figcaption></figure>

provide existence, uniqueness of the discrete solution, and the convergence in some sense of this
discrete solution towards the continuous solution. This discrete formulation also involves generally
an approximation to compute the integrals, which is called the quadrature.

Finally, the discrete system (linear or nonlinear) is built and solved numerically. The result is
a vector of floating points that can be stored and used to visualize the solution.

In addition, *a posteriori* computations can be devised to improve the results, with a change
of mesh for instance. When the problem is unsteady, the discrete part of the procedure is partly
repeated: one tries to re-use as much as possible the computed data to avoid numerous expensive
computations.

The Lax–Milgram theorem, one of the key ingredients to establish the FEM in some cases, was
already addressed, see [14] for a detailed pen-and-paper proof, and [6] for a formal proof in Coq.
A part of the Lebesgue integration theory was also addressed, see [15] for detailed pen-and-paper
proofs, and [7, 8] for a formalization in Coq.

The present document is a further contribution to our ultimate goal. It focuses only on the
definition of the finite element itself as a triple, see Chapter 6, and on the construction of Lagrange
finite elements of degree k on d-simplices, see Chapter 9. These Lagrange finite elements are defined
over simplices (segments, triangles or tetrahedra when d = 1, 2, 3), with polynomials having a
total degree no greater than k (denoted $\mathbb{P}_k^d$ in the sequel), and with nodal values that are evenly
distributed over the whole simplex, including its vertices.

1.3 The finite elements

In this document, $d \in \mathbb{N}^*$ denotes the space dimension (typically $d \in \{1, 2, 3\}$), and $k \in \mathbb{N}$ denotes
the *degree of approximation*, i.e. some polynomial degree.

Let us first define two polynomial spaces that are useful in the sequel. $\mathbb{P}_k^d$, as already said, is
the vector space of polynomials of $d$ variables and of total degree at most $k$,

$$
\mathbb{P}_k^d \stackrel{\text{def.}}{=} \left\{ \left( \mathbf{x} \mapsto \sum_{\alpha \in \mathbb{N}^d, \sum_{i=1}^d \alpha_i \le k} a_\alpha x_1^{\alpha_1} \dots x_d^{\alpha_d} \right) : \mathbb{R}^d \to \mathbb{R} \mid a_\alpha \in \mathbb{R} \right\}
$$
$Q_k^d$ is the vector space of polynomials of $d$ variables and of degree at most $k$ for each variable,

$$Q_k^d \stackrel{\text{def.}}{=} \left\{ \left( \mathbf{x} \mapsto \sum_{\beta \in \mathbb{N}^d, \forall i \in [1..d], \beta_i \le k} a_\beta x_1^{\beta_1} \dots x_d^{\beta_d} \right) : \mathbb{R}^d \to \mathbb{R} \mid a_\beta \in \mathbb{R} \right\}.$$

$\mathbb{P}_k^d$ is the polynomial approximation space for many simplicial elements, thus it will be used in the whole document, whereas $Q_k^d$, used mainly for hexahedra, is necessary for this introductory part only. For all $k \in \mathbb{N}$, we have obviously $\mathbb{P}_k^1 = Q_k^1$, and, for all $d \ge 2$, $\mathbb{P}_k^d \subsetneq Q_k^d$. Note that $\mathbb{P}_1^d$ is the space of affine functions to $\mathbb{R}$.

### 1.3.1 Some references

The mathematical literature dedicated to the FEM is very rich, FEM is a very active field of research. Thus, it is not intended in the present document to be comprehensive, nor to review the various approaches to this method. We limit ourselves to some books among many other references: Ciarlet [13], Ern [18], Ern and Guermond [19, 20, 21, 22], Babuška and Strouboulis [2], Quarteroni and Valli [31], Brenner and Scott [10], and Zienkiewicz, Taylor and Zhu [34]. The first part of the Handbook of Numerical Analysis is dedicated to the finite element methods [12, 33, 32, 3, 23].

The interested reader will find many references in all these books.

### 1.3.2 The finite element as a triple

To define a finite element, in addition to $d$ and $k$, some other notations are necessary: $q \in \mathbb{N}^*$ denotes the size of the physical unknowns ($q$ is generally 1 or $d$), and $n_{sh} \in \mathbb{N}^*$ represents the number of so-called local shape functions, i.e. a number of linear forms on $P$ (see below). A “correct” finite element needs to satisfy the unisolvence property, that relates $\Sigma$ (see below) and $P$ (and thus $n_{sh}$ and $k$).

Following [13] and [20], a finite element is mathematically defined as a triple $(K, P, \Sigma)$, where:

* $K$ is a geometrical “element”, i.e. a closed bounded set with nonempty interior. Typically, $K$ is a nondegenerate polygonal set (a polyhedron), or the image of such a set by a regular function.

* $P$ is a nonzero, finite-dimensional vector space of functions from $\mathbb{R}^d$ to $\mathbb{R}^q$. It is meant to be a space of polynomial functions, or the image of such a space via regular functions.

* $\Sigma$ is a collection of linear forms on $P$, $\Sigma \stackrel{\text{def.}}{=} (\sigma_i)_{i \in [1..n_{sh}]}$ where each $\sigma_i$ is a linear form on $P$. The application $\phi_\Sigma : P \to \mathbb{R}^{n_{sh}}$ defined by $\phi_\Sigma(p) \stackrel{\text{def.}}{=} (\sigma_i(p))_{i \in [1..n_{sh}]}$ is an isomorphism.

The bijectivity of $\phi_\Sigma$ is called unisolvence. The $\sigma_i$ are the degrees of freedom, and $n_{sh}$ is the number of degrees of freedom. It can be easily seen that the unisolvence requires that the dimension of $P$ be equal to $n_{sh}$.

A finite element is generally defined over what is called a reference geometrical element, a regular polyhedron $\hat{K}$: the reference FE is denoted $(\hat{K}, \hat{P}, \hat{\Sigma})$. Typically, $\hat{K}$ is the unit rectangle simplex, see below Section 1.3.3.1 or Definition 1437. It can also be the unit $d$-cube. This reference geometrical element $\hat{K}$ is transported to a so-called current element of the mesh denoted by $K$, by a geometric mapping that we call $\varphi_{\text{geo}}^K : \mathbb{R}^d \to \mathbb{R}^d$, see a simple 2D example in Figure 9.4. The finite element $(K, P, \Sigma)$ on $K$ is then somewhat the image of $(\hat{K}, \hat{P}, \hat{\Sigma})$ by $\varphi_{\text{geo}}^K$, see [20, Sec. 9.1].

The 1D Lagrange finite element is constructed in this way in Chapter 8. Note that in Chapter 9, the general case $d \ge 1$ is treated the other way around: we deal directly with a general nondegenerate $d$-simplex, and then introduce the reference Lagrange finite element as a particular case. The reason for this is explained at the end of Section 3.1.
According to the hypotheses on $\varphi_{\text{geo}}^K$, $K$ can be a polyhedron with planar faces, or not, and can be convex, or not. Not all geometrical elements are possible, though. In this document, we assume that the mesh is *affine*, which means that $\varphi_{\text{geo}}^K$ is supposed to be invertible and affine. The non-affine meshes are more tricky to handle, see Section 1.3.3.1 below. Note that the geometric mapping is affine iff each of its components is in $\mathbb{P}_1^d$. With a slight abuse of notation, the geometrical element is commonly labelled $\mathbb{P}_1^d$, $\mathbb{Q}_1^d$ or $\mathbb{P}_2^d$... when the components of $\varphi_{\text{geo}}^K$ are in the corresponding space.

In this document, the FE triple is specified in Definition 1424, using the hypothesis of an affine mesh, thus $K$ is assumed to be a polyhedron.

Note that one can also define a finite element as a quadruple, adding to the previous triple a linear interpolation operator that maps continuously functions in a larger space containing $P$ (to be defined) to $P$ itself, see [20, Sec. 5.3.]. The construction of the interpolation operator is not covered in the present version of the document.

### 1.3.3 Lagrange finite elements

There exist various families of finite elements, that are more or less adapted to the considered problem. For each family, there are usually a version for the simplices, and another for the quadrangles (when $d = 2$), or the hexahedra (when $d = 3$). Some finite elements can also be constructed on other geometries such as hexagons ($d = 2$) or prisms ($d = 3$).

First, let us discuss briefly the geometry of the FE. Then, we introduce the most common families of FE, before presenting the nodal finite elements, and in particular Lagrange FE.

#### 1.3.3.1 Typology of geometries: simplex vs quadrangular

When the geometrical element is a simplex, or when it is a $d$-cuboid (defined as $\prod_{i=1}^d [x_i, y_i]$, for some $(x_i)_{i \in [1..d]}$ and $(y_i)_{i \in [1..d]}$ in $\mathbb{R}$, with $x_i < y_i$), the geometrical mapping $\varphi_{\text{geo}}^K$ is affine, thus covered by the assumption in this document. For cuboids, note that the FE can be defined by a tensorization of 1D finite elements, see [20, Sec. 6.4].

However, dealing with non-affine geometric element may be necessary. For instance, to better approximate the geometry of the domain (think of airplane wings for instance), there exist *curved simplicial finite elements*: for instance, $\mathbb{P}_2^d$-simplices are simplices where the geometrical mapping is in $(\mathbb{P}_2^d)^d$. Thus, when $d = 2$, each edge of $K$ is a part of a parabola, see [20, Chap. 13]. Another important non-affine mesh case in practice, is the $\mathbb{Q}_1^d$-quadrangles and hexahedra: in this case, $\varphi_{\text{geo}}^K$ is in $(\mathbb{Q}_1^d)^d$ (thus not affine a priori). In 3D in particular, this may give complicated geometries, as general nondegenerate hexahedra are not always convex, and their faces are not necessarily planar.

This leads to complex numerical issues: meshing the domain $\Omega$ can be a very hard task (it is not simple, even with simplices). One needs to avoid “wrong” geometrical elements (for instance self-intersecting), the approximation results are also more involved, the integration needs more care, and so on.

To conclude on geometrical element, we say once again that we limit ourselves to affine, invertible geometrical mapping, and more specifically to geometrical elements that are nondegenerate standard simplices.

In this case, the reference simplex $\hat{K}$ is the unit rectangle simplex, see Definition 1437. It is the convex envelop of the reference vertices $[[\hat{v}]]^d \stackrel{\text{def.}}{=} (\hat{v}_0, \dots, \hat{v}_n)$, where $\hat{v}_0$ is the canonical origin $\mathbf{0} \stackrel{\text{def.}}{=} (0, \dots, 0)^T \in \mathbb{R}^d$, and for all $i \in [1..d]$, $\hat{v}_i$ corresponds to the $i$-th canonical basis vector $e_i \stackrel{\text{def.}}{=} (0, \dots, 0, 1, 0, \dots, 0)^T \in \mathbb{R}^d$ (the 1 is in position $i$).

Given $d+1$ points $[[v]]^d \stackrel{\text{def.}}{=} (v_0, \dots, v_n)$ in $\mathbb{R}^d$, the simplex $K[[v]]^d$ is the convex envelop of $[[v]]^d$, see Definition 1440. It is proven nondegenerate iff $[[v]]^d$ is affinely independent. The geometrical mapping that maps $\hat{K}$ to $K$ is defined as, see Definition 1547, $\varphi_{\text{geo}}^K(\hat{\mathbf{x}}) \stackrel{\text{def.}}{=} \sum_{i=0}^d \hat{L}_i^{1,d}(\hat{\mathbf{x}}) \mathbf{v}_i$ where
$(\hat{\mathcal{L}}_i^{1,d})_{i \in [0..d]}$ is the Lagrange basis of $\mathbb{P}_1^d$, such that $\hat{\mathcal{L}}_0^{1,d}(\hat{\mathbf{x}}) \stackrel{\text{def.}}{=} 1 - \sum_{j=0}^d \hat{x}_j$, and for all $i \in [1..d]$, $\hat{\mathcal{L}}_i^{1,d}(\hat{\mathbf{x}}) \stackrel{\text{def.}}{=} \hat{x}_i$. It is easy to see that $\varphi_{\text{geo}}^K$ is affine.

### 1.3.3.2 Some finite elements

Various approximation spaces $P$ and linear forms $\Sigma$ exist in the literature. Just to mention some of the most popular (original references can be found in [20]):

* for the *nodal* FE, the linear forms are the evaluation at some points $\mathbf{a}_i$, for $i \in [1..n_{\text{sh}}]$, that are called the FE nodes: $\sigma_i(p) = p(\mathbf{a}_i)$. The Lagrange FE are the most common nodal FE, see [20, Sec. 6.4 and 7.4], and below.

* the Hermite FE are nodal FE, but the linear forms are the evaluation at the nodes of both the function and its derivatives (assuming enough regularity for the function), see [11].

* for the *modal* FE in 1D, the linear forms are the integrals of the product of the function and Legendre polynomials. It can be tensorized for cuboid elements, see [20, Sec. 6.3.2 and 6.4.2].

* canonical hybrid FE mix evaluations at nodal values and integrals of the function over edges, faces, and volumes (in 3D) of the geometrical element, see [20, Sec. 7.6].

* the $\mathbb{R}$, $\mathbb{BDM}$, $\mathbb{BDFM}...$ are *flux* FE, see [20, Chap. 14]. They aim at approximating $\mathbf{H}(\text{div})$ functions (vector functions in $(L^2)^d$ whose divergence is in $L^2$). Some of the linear forms are integrals of the normal of the function across the $(d-1)$-faces of the simplex.

* the Nedelec family $\mathbb{N}$ of FE is meant for the approximation of $\mathbf{H}(\text{curl})$ functions (functions in $(L^2)^d$ whose curl is in $(L^2)^d$). Some of the linear forms are integrals of the tangential of the function along the edges of the simplex, see [20, Chap. 15].

### 1.3.3.3 Some nodal finite elements, Lagrange finite elements

For the nodal finite elements, there exist various choices of nodes. The Lagrange FE are based on Lagrange nodes: these nodes are evenly distributed in the element, and when $k \ge 1$, the vertices are always some of the nodes, see examples for the reference simplices in Figure 9.1. The precise definition using barycentric coordinates is given in Definition 1588. For cuboids, the Lagrange nodes are merely a tensorization of the segment nodes.

For simplices, the approximation space is $\mathbb{P}_k^d$, and the Lagrange FE is denoted $\operatorname{Log} \mathbb{P}_k^d$. In this document, we clearly separate the notations for the approximation space and for the finite element triple. In cuboids, the approximation space is $\mathbb{Q}_k^d$, and the Lagrange FE is denoted $\operatorname{Log} \mathbb{Q}_k^d$. In cuboids, it is possible to remove some internal nodes and to reduce the space dimension of the approximation space, which reduces the computational effort, while preserving the accuracy. These FE are called serendipity finite elements, and the approximation space is denoted $\mathbb{S}_k^d(\subseteq \mathbb{Q}_k^d)$, see [20, Sec. 6.4.3].

The polynomial interpolation problem consists in finding a polynomial $p$ to approximate a given function $f$, with the constraint that $f(\mathbf{x}_i) = p(\mathbf{x}_i)$ for a finite family of chosen points $(\mathbf{x}_i)_{i \in I}$. It is well known that choosing Lagrange nodes as interpolation points gives rise to an interpolating polynomial that can have very large oscillations. These oscillations tend to increase when the polynomial degree $k$ increases. This may lead to poor approximation results and to numerical difficulty for integration. This is why some other nodes may be favored. For instance, in 1D, one can take Gauss–Lobatto nodes, that are the two vertices of the segment and the roots of some Chebyshev polynomials, see [20, Sec. 6.3.5]. This improves drastically the high oscillation effects. The Gauss–Lobatto nodes can be easily tensorized for cuboid elements.

In the present document, we focus on Lagrange simplicial FE, because $\operatorname{Log} \mathbb{P}_1^d$ and $\operatorname{Log} \mathbb{P}_2^d$ are the most popular FE, because treating $\operatorname{Log} \mathbb{P}_k^d$ for all $k$ and $d$ is of great interest by itself, and because $\mathbb{P}_k^d$ is an approximation space that is used for many FE. Thus Lagrange simplicial FE is a natural first step in our development.
## 1.4 Our main sources

Our main source for the proofs in the present text is [20]. The part on affine geometry is inspired by [24].

Note that, because the support for differential calculus is still limited in Coq, we choose to favor proof paths using algebraic arguments over those using analysis results. As a consequence, some of our proofs are distinct from those of [20]. In particular, we do not rely on differential calculus to prove the lemmas on geometric mappings that relate various configurations of simplices or faces. As we assume that the meshes are affine (i.e. in our case, made up of simplices that are nondegenerate and have planar hyperfaces), and as we do not need to integrate to define the Lagrange finite element, the results on affine maps and affine spaces are sufficient. Nonetheless, some results of topology (and of analysis) are obviously required to prove that nondegenerate simplices have nonempty interior.

To obtain the dimension of $\mathbb{P}_k^d$, defined as the linear span of monomials, we prove the linear independence of these monomials by calculating their partial derivatives and taking the value at 0. A possible alternative, that is not followed in the Coq formalization, is to use the Euclidean division to prove an isomorphism between $\mathbb{P}_k^d$ and $\mathbb{P}_{k-1}^d \times \mathbb{P}_k^{d-1}$, and conclude on the dimension by induction (see Remark 1530).

## 1.5 Contents

The present version of this document covers all material up to the construction of the simplicial Lagrange finite elements in dimension $d \ge 1$.

After the general definition of the notion of finite element, and some results about simplicial geometry, it starts with the construction of the simplicial Lagrange finite elements on a segment including results about $\mathbb{P}_k^1$ Lagrange polynomials; this step is mostly for pedagogical purpose. Then, for any dimension $d \ge 1$, it covers the construction of multi-indices of given maximum length. This allows to write the definition of multivariate polynomial spaces as the linear span of monomials, and some results such as the linear independence of monomials using partial derivation and providing the dimension of the considered space of polynomial, the product of polynomials, the composition of polynomials and affine mappings, and the Euclidean division by a monomial. Then, there are some results about $\mathbb{P}_k^d$ Lagrange polynomials, with in particular their view as barycentric coordinates. This provides results about affine geometric mappings, such as the transformation of $l$-faces of dimension $l \le d$. This allows to pass from the reference simplex in dimension $l$ to a current element in dimension $d$. The case $l=d$ is the most important one and is treated first. Next, some results about Lagrange nodes and Lagrange linear forms of $\mathbb{P}_k^d$ are given, before the proof of unisolvence of $\mathbb{P}_k^d$. This allows to conclude with the construction of the simplicial Lagrange finite elements in dimension $d \ge 1$, and the statement and proof of face unisolvence. The formalization in Coq of most of these aspects is presented in [30, 9].

It is planned to add more results in a forthcoming version.

## 1.6 Teaching

This document is not primarily meant for teaching usage. The objective was to be as comprehensive as possible in the proofs. This led to very detailed demonstrations, and to a compact style of writing that is not common, and may seem daunting to the uninformed reader.

However, the authors tried to give some insights on the FEM theory and on the proofs and theorems in the introductory chapters. They also strove to give some indications in the proofs when they felt it necessary. They believe that this document could be useful for interested teachers, and dedicated students, in complement to the usual manuals.
## 1.7 Disclaimer

Note that the manuscript itself is not formally proved (and will never be). Indeed, LATEX compilers are not formal proof tools!

Moreover, formalization is not just straightforward translation of mathematical texts and for-mulas. Some design choices have to be made and proof paths may differ, mainly to favor usability of Coq theorems and ease formal developments. Thus, there may exist differences between the mathematical setting presented here, and the formal setting developed in Coq [30, 9].

Hence, despite the care taken in its writing, this document might still be prone to errors or holes in the demonstrations. There could also exist simpler paths in the proofs. Please, feel free to inform the authors of any such issue, and to share any comments or suggestions...

## 1.8 Organization

Part I of this document is organized as follows. After the present introductory Chapter 1, the notations are collected in Chapter 2. The chosen proof paths of the main results are then sketched in Chapter 3.

Part II (Chapters 4 to 9) is the core of this document. In this part, the definitions are presented, and the lemmas and theorems are stated with their detailed proofs. Its organization is briefly described at the end of the second introductory Chapter 4.

Chapter 10 concludes and gives some perspectives.

Finally, an appendix gathers the list of statements in Chapter A, and explicit dependencies (both ways) in Chapters B and C. The appendix is not intended for printing!
# Chapter 2

## Notations

In this chapter (as in most of the document), we use the following conventions:

• $d$ and $l$ denote a dimension, a (usually nonzero) natural number;

• $k$ denotes the order of a finite element, a natural number, e.g. the maximum degree of polynomials in an approximation space;

• the hat diacritical mark “^” denotes a reference quantity: a reference set, e.g. the reference simplex $\hat{K}^d$, or a reference element in a reference set, e.g. a point $\hat{x}$ in $\hat{K}^d$, see below;

• **boldface** denotes finite families, typically of size $d$, and more generally vectors in a vector space, or points in an affine subspace:

– **boldface** small Greek letters $\alpha$ and $\beta$ denote multi-indices in $\mathbb{N}^d$;

– **boldface** small letters, such as $\mathbf{x}$ and $\hat{\mathbf{x}}$, denote points or vectors in $\mathbb{R}^d$;

– the components of a finite family $\mathbf{x}$ are usually denoted $x_i$, and by default the indices of components start from 1;

• the tilde (resp. check) diacritical mark “~” (resp. “˜”) denotes a family of size $d-1$ that corresponds to the $d-1$ first (resp. last) components of the regular family of size $d$, or a function of such family. For instance, for $\alpha \in \mathbb{N}^d$, the multi-indices $\tilde{\alpha}$ (resp. $\hat{\alpha}$) satisfy $\alpha = (\alpha_1, \tilde{\alpha}) = (\tilde{\alpha}, \alpha_d)$, see below.

The following notations and conventions are used throughout this document.

• Logic:

– Using a compound (tuple of elements of $X$, or subset of $X$) in an expression at a location where only a single element makes sense, is a shorthand for the same expression expanded for all elements of the compound; for instance, “$\forall x, x' \in X$” means “$\forall x \in X, \forall x' \in X$”, “$\forall (x_i)_{i \in I} \in X$” means “$\forall i \in I, x_i \in X$”, and “$x, x' \in \mathcal{R}x''$” means “$x \in \mathcal{R}x''$ and $x' \in \mathcal{R}x'''$”;

– “iff” is a shorthand for “if and only if”.

• Naive set theory:

– $\text{card}(E)$ denotes the cardinal of some set $E$, especially when it is finite, see Lemma 1426;

– the cartesian products $E^{d+1}$, $E^d \times E$ and $E \times E^d$ are assimilated, see Lemma 1533;

– the set of functions from $E$ to $F$ is either denoted $F^E$, or through the type annotation “$E \to F$”. Both compact expressions “let $f \in F^E$” and “let $f : E \to F$” mean “let $f$ be a function from $E$ to $F$”;

– $\text{rg}(f)$ denotes the range of function $f : E \to F$, i.e. the image $f(E)$ of its domain, see Lemma 1408.

• Numbers:

– *positive/negative*, and *increasing/decreasing* are meant in their *strict* sense, i.e. without the possibility of equality. Otherwise, we use *nonnegative/nonpositive*, and *nondecreasing/nonincreasing*;

– $[n.p]$ denotes the integer interval $[n, p] \cap \mathbb{N}$ of values from integer $n$ up to integer $p$ (both included);
– $\binom{n}{p}$ denotes the binomial coefficient, i.e. the number of subsets of $p$ elements of a set of $n$ elements, see Definition 1362;

– $\delta$ denotes the Kronecker delta function, i.e. $\delta_{ii} \stackrel{\text{def.}}{=} 1$ for all $i \in \mathbb{N}$, and $\delta_{ij} \stackrel{\text{def.}}{=} 0$ when $i \neq j$, see Definition 1365;

– $\theta_i^d : [0..d] \to [0..d+1]$ is the “jump” enumeration function that skips $i$, see Lemma 1368;

– **0** denotes the family of zeros $(0, \dots, 0)$, and **1** denotes the family of ones $(1, \dots, 1)$, see Definition 1365;

– **e**<sub>*i*</sub> denotes the *i*-th canonical “basis” family with only a 1 in *i*-th position, see Definition 1365;

– $|\alpha|$ denotes the length of a multi-index, i.e. the sum of its components, see Definition 1480;

– **α!** denotes the factorial of a multi-index, i.e. the product of the factorials of its components, see Definition 1482;

– $\delta_{\alpha,\beta}$ denotes the Kronecker delta of two multi-indices, i.e. the product of the Kronecker deltas of their components, see Definition 1484;

– $\mathcal{A}_k^d$ denotes the set of multi-indices in dimension $d$ of sum at most $k$, see Definitions 1445 (for $d \stackrel{\text{def.}}{=} 1$) and 1486;

– $\mathcal{C}_k^d$ denotes the set of multi-indices in dimension $d$ of sum equal to $k$, see Definition 1486;

– $\mathcal{A}_{k,i}^d$ denotes the subset of $\mathcal{A}_k^d$ of multi-indices with zero *i*-th component, see Definition 1486;

– $\tilde{\alpha}$ denotes the first $d-1$ components of a multi-index $\alpha$ in $\mathbb{N}^d$, see Remark 1490;

– $\tilde{\alpha}$ denotes the last $d-1$ components of a multi-index $\alpha$ in $\mathbb{N}^d$, see Remark 1490;

– $\tilde{S}_{k,i}^d$ (resp. $\tilde{S}_{k,i}^{d-1}$) denotes the *i*-th “vertical” (resp. “horizontal”) slice of $\mathcal{C}_k^d$, see Definition 1491;

– $f_{k,0}^d$ (resp. $\tilde{f}_{k,0}^d$) denotes the function $\mathcal{A}_k^{d-1} \to \mathcal{C}_k^d$ on multi-indices that puts $k$ minus the length at the beginning (resp. at the end), see Lemma 1500;

– $f_{k,i}^d : \mathcal{A}_k^{d-1} \to \mathcal{A}_{k,i}^d$ denotes the function on multi-indices that inserts 0 in *i*-th position, see Lemma 1501.

• General topology:

– $\tilde{K}$ denotes the interior of some subset $K$ of some topological space, see Definition 1424.

• Calculus:

– $\partial^\beta$ denotes the partial derivative of order $\beta$, a multi-index, see Lemma 1517;

– $Df$ denotes the differential of the function $f$ of appropriate type, see Lemma 1545.

• Linear and affine algebra:

– span $(u_1, \dots, u_n)$ denotes the linear span of the family of vectors $(u_i)_{i \in [1..n]}$, with the convention that $\text{span}(\emptyset) \stackrel{\text{def.}}{=} \{0\}$, see Definitions 83 and 1417, and Lemma 1387;

– ker $(f)$ denotes the kernel of morphism $f$ (usually a linear map from a vector space to another), see Definition 101, and Lemma 1369;

– $\dim(E)$ denotes the finite dimension of a vector space $E$, i.e. the common cardinality of its bases, see Lemma 1374;

– $M_{n,p}(\mathbb{R})$, or simply $M_{n,p}$, denotes the space of matrices with $n$ lines and $m$ columns, see Lemma 1399;

– for a matrix $A \in M_{n,p}(\mathbb{R})$, where $n, p > 0$, the line $i \in [1..n]$ of $A$ is denoted by $A_i$, and its column $j \in [1..p]$ is denoted by $A_j$, see Lemma 1556;

– $\mathcal{L}(E, F)$ denotes the vector space of linear maps from vector space $E$ to vector space $F$, see Definition 65, and Lemma 1374;

– $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ denotes the affine subspace of direction $E'$, a vector subspace of $E$, and origin $\mathbf{x}_0 \in E$, see Definition 1379;

– $\mathcal{A}ff(E, F)$ denotes the vector space of affine maps from vector space $E$ to vector space $F$, see Lemma 1396.

• Geometry:
- $[[\mathbf{v}]]^{n,d} \stackrel{\text{def.}}{=} (\mathbf{v}_0, \dots, \mathbf{v}_n)$ denotes a family of $n+1$ points in $\mathbb{R}^d$, usually indexed by $[0..n]$, $[[\mathbf{v}]^d$ is a shorthand for $[[\mathbf{v}]]^{d,d}$, see Definition 1365; it is the notation used to represent the vertices of the geometry of finite elements, see Remark 1433;

- $[[\mathbf{v}]_{\pi^l}^{l,d}$ is the sub-family $(\mathbf{v}_{\pi^l(i)})_{i \in [0..l]}$ where $\pi^l: [0..l] \to [0..n]$, see Lemma 1414;

- $[[\hat{\mathbf{v}}]]^d \stackrel{\text{def.}}{=} (\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_d)$ denotes the family of $d+1$ reference points in $\mathbb{R}^d$, see Definition 1434;

- $\mathbf{g}[[\mathbf{v}]^d$ denotes the isobarycenter of the family of points $[[\mathbf{v}]^d$; see Definition 1401;

- $\hat{\mathbf{g}}^d$ denotes the isobarycenter of the family of reference points $[[\hat{\mathbf{v}}]]^d$; see Lemma 1435;

- $\mathbf{K}[[\mathbf{v}]^d$ denotes the simplex of vertices $[[\mathbf{v}]^d$ in $\mathbb{R}^d$, see Definition 1440;

- $\hat{\mathbf{K}}^d$ denotes the reference simplex in $\mathbb{R}^d$, its vertices are the reference points $[[\hat{\mathbf{v}}]]^d$, see Definition 1437;

- $\{\mathbf{a}\}_{A_k^1}$ denotes $k+1$ nodes in $\mathbb{R}$, see Definitions 1432 and 1448;

- $\{\hat{\mathbf{a}}\}_{A_k^1}$ denotes the reference Lagrange nodes of $\mathbb{P}_k^1$ that are equally distributed over the reference simplex $[0, 1]$ in $\mathbb{R}$, see Definition 1453;

- $\{\mathbf{a}\}_{\mathcal{B}_d}$ denotes a family of card$(\mathcal{B}_d)$ points in $\mathbb{R}^d$, see Definition 1432, it is the notation used to represent the nodes of the geometry of nodal finite elements, see Remark 1433;

- $\{\mathbf{a}\}_{A_k^d}$ denotes the Lagrange nodes of $\mathbb{P}_k^d$ that are equally distributed over the simplex $\mathbf{K}[[\mathbf{v}]^d$ in $\mathbb{R}^d$, see Definition 1588;

- $\{\hat{\mathbf{a}}\}_{A_k^d}$ denotes the reference Lagrange nodes of $\mathbb{P}_k^d$ that are equally distributed over the reference simplex $\hat{\mathbf{K}}^d$ in $\mathbb{R}^d$, see Lemma 1599;

- $[[\mathbf{v}]^d$ denotes the sub-vertices of the Lagrange nodes of $\mathbb{P}_k^d$ with respect to $\mathbf{v}_0$, see Definition 1594;

- $\{\hat{\mathbf{a}}\}_{A_{k-1}^d}$ denotes the Lagrange sub-nodes of $\mathbb{P}_{k-1}^d$ associated with the sub-vertices $[[\mathbf{v}]^d$ with respect to $\mathbf{v}_0$, see Lemma 1598;

- $\varphi_{\text{geo}}^{[\mathbf{v}]^1}$ denotes the geometric mapping associated with $[[\mathbf{v}]^1$, see Definition 1461;

- $\varphi_{\text{geo}}^{[\mathbf{v}]^d}$ denotes the geometric mapping associated with $[[\mathbf{v}]^d$, see Definition 1547;

- $\mathbf{A}_{\text{geo}}^{[\mathbf{v}]^d}$ denotes the square matrix $(\mathbf{v}_1 - \mathbf{v}_0 \quad \mathbf{v}_2 - \mathbf{v}_0 \quad \dots \quad \mathbf{v}_d - \mathbf{v}_0)$, see Lemma 1550;

- $\lambda_i^{[\mathbf{v}]^d}(\mathbf{x})$ denotes the $i$-th barycentric coordinate of $\mathbf{x}$ with respect to $[[\mathbf{v}]^d$, see Lemma 1559;

- $\mathcal{H}_i^{[\mathbf{v}]^d}$ denotes the $i$-th face hyperplane with respect to $\mathbf{K}[[\mathbf{v}]^d$, opposite the vertex $\mathbf{v}_i$, see Definition 1562;

- $\hat{\mathcal{H}}_i^d \stackrel{\text{def.}}{=} \mathcal{H}_i^{[\hat{\mathbf{v}}]^d}$ denotes the $i$-th reference face hyperplane with respect to $\hat{\mathbf{K}}^d$, opposite the reference vertex $\hat{\mathbf{v}}_i$, see Definition 1562;

- $\mathcal{H}_i^{[\mathbf{v}]^d}$ denotes the $i$-th hyperface of simplex $\mathbf{K}[[\mathbf{v}]^d$, opposite the vertex $\mathbf{v}_i$, see Definition 1566;

- $\mathcal{F}_{\pi^l}^{[\mathbf{v}]^d}$ denotes the $l$-face affine space having the vertices $[[\mathbf{v}_{\pi^l}]]^{l,d}$, see Definition 1568;

- $\mathcal{F}_{\pi^l}^{[\mathbf{v}]^d}$ denotes the $l$-face having the vertices $[[\mathbf{v}_{\pi^l}]]^{l,d}$, see Definition 1572;

- $\phi_{\pi^l}^{[\mathbf{v}]^d}$ is the geometric $l$-face mapping associated with the $l$-face $\mathbf{F}_{\pi^l}^{[\mathbf{v}]^d}$, see Definition 1578.

• Polynomials:

- $X_k \stackrel{\text{def.}}{=} (x \in \mathbb{R} \mapsto x^k)$ denotes the monomial of a single variable of degree $k$ in $\mathbb{R}$ (it is simply denoted $1$ when $k \stackrel{\text{def.}}{=} 0$), see Definition 1417;

- $\mathbf{X}^\alpha \stackrel{\text{def.}}{=} (\mathbf{x} \in \mathbb{R}^d \mapsto \prod_{i=1}^d x_i^{\alpha_i})$ denotes the monomial of $d$ variables of degree $\sum_{i=1}^d \alpha_i$, $1$ is a shortcut for $\mathbf{X}^0$ (the constant function of value $1$), and $X_i$ is a shortcut for $\mathbf{X}^{e_i}$, see Definition 1503;

- $\mathcal{P}(\mathbb{R}^d)$ denotes the algebra of polynomials of $d$ variables, see Lemma 1418;

- $\deg(p)$ denotes the degree of polynomial $p$, i.e. the highest degree of its monomials with
nonzero coefficients, where the degree of a monomial is the sum of the degrees for each variable, see Definition 1510;

- $\mathbb{P}_k^d$ denotes the vector space of polynomials of $d$ variables and of degree at most $k$, see Definition 1505;

- $\xi^d$ denotes the isomorphism between $\mathbb{P}_0^d$ and $\mathbb{P}_0^{d-1}$ that keeps the value of (constant) polynomials, see Lemma 1526;

- $\zeta_k^d$ denotes the isomorphism between $\mathbb{P}_k^d$ and $\mathbb{P}_k^{d-1} \times \mathbb{P}_{k-1}^d$ that realizes the Euclidean division by $X_d$, see Lemma 1531;

- $\mathcal{L}_i^{\{a\}_{A_k^1}}$ for $i \in [0..k]$ denotes the family of Lagrange polynomials in $\mathbb{P}_k^1$ associated with nodes $\{\{a\}\}_{A_k^1} \in \mathbb{R}$, see Definition 1448;

- $\hat{\mathcal{L}}_{i}^{k,1} \stackrel{\text{def.}}{=} \mathcal{L}_{i}^{\{\hat{a}\}_{A_k^1}}$ for $i \in [0..k]$ denotes the family of reference Lagrange polynomials in $\mathbb{P}_k^1$ associated with the reference Lagrange nodes $\{\{\hat{a}\}\}_{A_k^1} \in \mathbb{R}$, see Lemma 1455;

- $\hat{\mathcal{L}}_i^{1,d}$ for $i \in [0..d]$ denotes the family of reference Lagrange polynomials of $\mathbb{P}_1^d$, see Definition 1541;

- $\mathcal{L}_i^{[\mathbf{v}]^d} \stackrel{\text{def.}}{=} \hat{\mathcal{L}}_i^{1,d} \circ (\varphi_{\text{geo}}^{[\mathbf{v}]^d})^{-1}$ for $i \in [0..d]$ denotes the family of Lagrange polynomials of $\mathbb{P}_1^d$ associated with $[\mathbf{v}]^d$, see Lemma 1552.

• Finite element:

- $(K, P, \Sigma)$ denotes a finite element where $K$ represents the geometry, $P$ the approximation space, and $\Sigma$ the degrees of freedom, see Definition 1424;

- $\phi_{\Sigma}$ denotes the collection of degrees of freedom applications, see Definition 1424;

- $\sum_{\alpha \in A_k^d}^{\{\mathbf{a}\}_{A_k^d}} = (\sigma_{\alpha})_{\alpha \in A_k^d}$ denote the Lagrange linear forms associated with the Lagrange nodes of $\mathbb{P}_k^d$, see Definition 1608;

- $\hat{\Sigma}_k^d = (\hat{\sigma}_{\alpha})_{\alpha \in A_k^d}$ denote the reference Lagrange linear forms associated with the reference Lagrange nodes of $\mathbb{P}_k^d$, see Definition 1612;

- $\text{Log}_{\mathbb{P}_k^d} \stackrel{\text{def.}}{=} (K[\mathbf{v}]^d, \mathbb{P}_k^d, \sum_{\alpha \in A_k^d}^{\{\mathbf{a}\}_{A_k^d}})$ denotes the Lagrange finite element of degree $k$ associated with vertices $[\mathbf{v}]^d$, see Theorems 1629, and 1478 for $d \stackrel{\text{def.}}{=} 1$;

- $\hat{\text{Log}}_{\mathbb{P}_k^d} \stackrel{\text{def.}}{=} (\hat{K}^d, \mathbb{P}_k^d, \hat{\Sigma}_k^d)$ denotes the reference Lagrange finite element of degree $k$ in dimension $d$, see Theorems 1631, and 1460 for $d \stackrel{\text{def.}}{=} 1$.

Note that the vector space $\mathbb{P}_k^d$ of polynomials of total degree at most $k$ does not have the same notation as the Lagrange finite element $\text{Log}_{\mathbb{P}_k^d}$. We have tried to visually separate the two concepts, although specialists often use the same notation.
# Chapter 3

# Statements and sketches of proofs

This chapter gathers the sketches of the proofs of the main results that are detailed in Part II. Namely: the theorem of unisolvence of $^{Lag}\mathbb{P}_k^d$, the lemma of Euclidean division by monomial in $\mathbb{P}_k^d$, and a more technical discussion about ordering the multi-indices.

## 3.1 Sketch of the proof of unisolvence of $^{Lag}\mathbb{P}_k^d$

**Theorem of unisolvence of $^{Lag}\mathbb{P}_k^d$.**

Let $d \ge 1$. Let $k \ge 1$. Let $[[v]]^d$ be $d+1$ affinely independent points in $\mathbb{R}^d$.

Then, $(K[[v]]^d, \mathbb{P}_k^d, \Sigma^{\{\mathbf{a}\}}_{\mathcal{A}_k^d})$ satisfies the unisolvence property.

See Theorem 1626, and the proof of Lemma 1625. The definition of unisolvence is explained in Section 1.3.2.

The proof of the theorem of unisolvence of $^{Lag}\mathbb{P}_k^d$ uses a double induction scheme, and the Euclidean division of polynomials (see Section 3.2). The proof of the theorem of unisolvence of $^{Lag}\mathbb{P}_k^d$ goes as follows:

* prove that $\phi_{\sum_{\mathcal{A}_k^d}^{\{\mathbf{a}\}}}^{}$ is injective by a double induction on $d, k \ge 1$ (see Lemma 1625).

This amounts to prove that if $[[v]]^d$ are $d+1$ affinely independent points in $\mathbb{R}^d$, and if the polynomial $p \in \mathbb{P}_k^d$ is zero on all Lagrange nodes $\{\mathbf{a}\}_{\mathcal{A}_k^d}$ (i.e. for all $\alpha \in \mathcal{A}_k^d$, $p(\mathbf{a}_{\alpha}) = 0$), then $p$ is zero. We recall that the Lagrange nodes $\{\mathbf{a}\}_{\mathcal{A}_k^d}$ are evenly distributed over the simplex whose vertices are $[[v]]^d$.

- **for $d=1$,** the components of any polynomial in $\mathbb{P}_k^1$ on the Lagrange basis are the values at the Lagrange nodes (see Lemma 1450), thus the cancellation of the latter implies the cancellation of the polynomial itself (see Lemma 1476);

- **for $k=1$,** the components of any polynomial in $\mathbb{P}_1^d$ on the Lagrange basis are the values at the vertices (which are the Lagrange nodes in this case, see Lemmas 1593 and 1555), thus the cancellation of the latter implies the cancellation of the polynomial itself (see Lemma 1619);

- **for $d, k \ge 2$,** assume that the injectivity result holds for $(d-1, k)$ and $(d, k-1)$, and let $p \in \mathbb{P}_k^d$ vanishing on $\{\mathbf{a}\}_{\mathcal{A}_k^d}$, the Lagrange nodes of $\mathbb{P}_k^d$ defined for the vertices $[[v]]^d$, then:

* **step 1:** factorization using the injectivity result for $(d-1, k)$. This is done by using the fact that $p$ is zero on the nodes of a hyperface of the current $d$-simplex, and passing this information on the reference $(d-1)$-simplex via an affine bijective mapping between $\mathbb{R}^{d-1}$ and this hyperface:
· show that $p_0 \stackrel{\text{def.}}{=} p \circ \phi_0^{[\mathbf{v}]^d}$ vanishes on $\{\hat{\mathbf{a}}\}_{\mathcal{A}_k^{d-1}}$, the reference Lagrange nodes of $\mathbb{P}_k^{d-1}$, where $\phi_0^{[\mathbf{v}]^d}$ is the bijective geometric hyperface mapping (see Lemma 1584) from $\mathbb{R}^{d-1}$ onto $\mathcal{H}_0^{[\mathbf{v}]^d}$, the face hyperplane opposite the vertex $\mathbf{v}_0$;

· then, apply the injectivity result for $(d-1, k)$ to obtain the cancellation of $p_0$ on $\mathbb{R}^{d-1}$, and thus the cancellation of $p$ on the whole hyperplane $\mathcal{H}_0^{[\mathbf{v}]^d}$ (and not only the nodes on this hyperplane);

· finally, use the Euclidean division on $\mathbb{P}_k^d$ to show the existence of $q \in \mathbb{P}_{k-1}^d$ such that $p = \lambda_0^{[\mathbf{v}]^d} \times q$, where $\lambda_0^{[\mathbf{v}]^d}$ is the barycentric coordinate associated with the vertex $\mathbf{v}_0$, (the hyperplane $\mathcal{H}_0^{[\mathbf{v}]^d}$ is the place where $\lambda_0^{[\mathbf{v}]^d}$ vanishes, see Lemmas 1563 and 1623);

* step 2: cancellation using the injectivity result for $(d, k-1)$. The principle here is to observe that $q \in \mathbb{P}_{k-1}^d$ is zero on all the Lagrange nodes except the ones on $\mathcal{H}_0^{[\mathbf{v}]^d}$, and that these cancelling nodes are precisely the Lagrange nodes of $\mathbb{P}_{k-1}^d$ that are defined from sub-vertices (see Figure 9.8):

· show that $q$ vanishes on the first Lagrange nodes of $\mathbb{P}_k^d$, indexed by $\mathcal{A}_{k-1}^d$;

· then, show that those nodes are equal to $\{\hat{\mathbf{a}}\}_{\mathcal{A}_{k-1}^d}$, the Lagrange nodes of $\mathbb{P}_{k-1}^d$ associated with the sub-vertices with respect to $\mathbf{v}_0$ (see Lemma 1598);

· finally, apply the injectivity result for $(d, k-1)$ to obtain cancellation of $q$, then of $p$, and thus the injectivity result for $(d, k)$;

• use equivalence between injectivity and bijectivity of linear maps when the dimensions of input and output spaces coincide.

The theorem of unisolvence of $\text{Log}\mathbb{P}_k^d$ is used in the present document to build the $\text{Log}\mathbb{P}_d^k$ Lagrange finite element of degree $k$ associated with simplicial vertices $[[\mathbf{v}]^d]$ (see Theorem 1629).

Note that in this proof, one needs in step 2 to take sub-nodes in order to use the induction hypothesis for $(d, k-1)$. This requires to pass from the initial simplex to a different simplex. This new simplex is the first one, minus a slice that is comprised between the hyperplane $\mathcal{H}_0^{[\mathbf{v}]^d}$ opposite $\mathbf{v}_0$, and the hyperplane parallel to $\mathcal{H}_0^{[\mathbf{v}]^d}$ that passes through the nodes closest to the hyperplane, see Figure 9.8. From this remark, note that if the initial simplex is the reference one, the new simplex cannot be the reference simplex. Thus, this proof requires to treat general nondegenerate simplices and not only the *reference* simplex.

This is why the unisolvence is proved directly in all generality for any nondegenerate simplices. The unisolvence for the reference simplex is then simply a particular case.
## 3.2 Sketch of the proof of Euclidean division by monomial in $\mathbb{P}_k^d$

**Lemma of Euclidean division by monomial in $\mathbb{P}_k^d$.** Let $d \ge 2$. Let $k \ge 1$. Let $p \in \mathbb{P}_k^d$. Then, there exist unique $\tilde{p}_0 \in \mathbb{P}_k^{d-1}$ and $p_1 \in \mathbb{P}_{k-1}^d$, such that $p = \tilde{p}_0 + X_d p_1$, which also writes for all $(x_1, \dots, x_d) \in \mathbb{R}^d$, $p(x_1, \dots, x_d) = \tilde{p}_0(x_1, \dots, x_{d-1}) + x_d p_1(x_1, \dots, x_d)$.

See Lemma 1529. The proof of the lemma of Euclidean division by monomial in $\mathbb{P}_k^d$ uses the “~” notation for functions for which the last variable is dropped (see $p$ and $\tilde{p}_0$ above, and Remark 1490). The proof of the lemma of Euclidean division by monomial in $\mathbb{P}_k^d$ goes as follows:

* **existence:** by induction on $k \ge 1$,

- for $k=1$, the result is straightforward as $\mathbb{P}_1^d \stackrel{\text{def.}}{=} \text{span}(1, X_1, X_2, \dots, X_d)$ (the constant on $X_d$ is $p_1$);

- for $k \ge 1$, assume that the result holds for $k$, and let $p = \sum_{\alpha \in \mathcal{A}_{k+1}^d} a_\alpha \mathbf{X}^\alpha \in \mathbb{P}_{k+1}^d$, then:

* from the partition of the multi-index sets $\mathcal{A}_{k+1}^d = \mathcal{A}_k^d \uplus \mathcal{C}_{k+1}^d$ (see Definition 1486 and Lemma 1496), we have $p = q+r$ with $q = \sum_{\alpha \in \mathcal{A}_k^d} a_\alpha \mathbf{X}^\alpha \in \mathbb{P}_k^d$ and $r = \sum_{\alpha \in \mathcal{C}_{k+1}^d} a_\alpha \mathbf{X}^\alpha \in \mathbb{P}_{k+1}^d$;

* then, apply the result for $k$ to $q$, and obtain existence of $\tilde{q}_0 \in \mathbb{P}_k^{d-1} \subset \mathbb{P}_{k+1}^{d-1}$ and $q_1 \in \mathbb{P}_{k-1}^d \subset \mathbb{P}_k^d$ such that $q = \tilde{q}_0 + X_d q_1$;

* for all $i \in [0..k+1]$, for all $\tilde{\alpha}_i \in \mathcal{C}_{k+1-i}^{d-1}$, let $b_{\tilde{\alpha}_i} \stackrel{\text{def.}}{=} a(\tilde{\alpha}_i, i)$, let

$$ \tilde{r}_0 \stackrel{\text{def.}}{=} \sum_{\tilde{\alpha}_0 \in \mathcal{C}_{k+1}^{d-1}} b_{\tilde{\alpha}_0} \tilde{\mathbf{X}}^{\tilde{\alpha}_0} \quad \text{and} \quad r_1 \stackrel{\text{def.}}{=} \sum_{i=1}^{k+1} \sum_{\tilde{\alpha}_i \in \mathcal{C}_{k+1-i}^{d-1}} b_{\tilde{\alpha}_i} \tilde{\mathbf{X}}^{\tilde{\alpha}_i} X_d^{i-1}, $$

then show that $\tilde{r}_0 \in \mathbb{P}_{k+1}^{d-1}$, $r_1 \in \mathbb{P}_k^d$ and $r = \tilde{r}_0 + r_1$;

* finally show that $\tilde{p}_0 \stackrel{\text{def.}}{=} \tilde{q}_0 + \tilde{r}_0 \in \mathbb{P}_{k+1}^{d-1}$, $p_1 \stackrel{\text{def.}}{=} q_1 + r_1 \in \mathbb{P}_k^d$ and $p = \tilde{p}_0 + X_d p_1$;

* **uniqueness:** assume that $\tilde{q}_0 + X_d q_1 = \tilde{r}_0 + X_d r_1$ with $\tilde{q}_0, \tilde{r}_0 \in \mathbb{P}_k^{d-1}$ and $q_1, r_1 \in \mathbb{P}_{k-1}^d$,

- applying the equality to $\mathbf{x} = (\tilde{\mathbf{x}}, 0) \in \mathbb{R}^d$ provides $\tilde{q}_0 = \tilde{r}_0$;

- let $\sum_{\alpha \in \mathcal{A}_{k-1}^d} a_\alpha \mathbf{X}^\alpha$ be the decomposition on the monomial basis of $q_1 - r_1 \in \mathbb{P}_{k-1}^d$, then the linear independence of the monomial family in $\mathbb{P}_k^d$ and the cancellation $X_d(q_1 - r_1) = 0$ provide $(a_\alpha)_{\alpha \in \mathcal{A}_{k-1}^d} = \mathbf{0}$, thus $q_1 = r_1$.

The lemma of Euclidean division by monomial in $\mathbb{P}_k^d$ is used in the present document to build an isomorphism between $\mathbb{P}_k^d$ and $\mathbb{P}_k^{d-1} \times \mathbb{P}_{k-1}^d$ in Lemma 1531, to express a multivariate polynomial as a polynomial of $x_d$ in Lemma 1534, to establish the degree of the product of two polynomials in Lemma 1537, and the factorization of a polynomial vanishing in the last reference face hyperplane $\hat{\mathcal{H}}_d^d$ in Lemma 1621 (used for Lemma 1623, see Section 3.1).

Note that, instead of building $\mathbb{P}_k^d$ as the linear span of monomials as done here (see Definition 1505), it is possible to build it by incrementing the dimension of the polynomial by setting the components of 1D polynomial as polynomials of other variables. The Lemma 1534 somewhat establishes the link between these two views.
## 3.3 Multi-index ordering

The second part of the present document does not focus on the ordering of multi-indices, but it may be interesting to say a few words on this topic.

### 3.3.1 Multi-indices and the finite element method

For Lagrange finite elements in $d$-simplices, we deal with multi-indices whose sum is at most $k$.

**Definition of multi-indices $A_k^d$ and $C_k^d$.** Let $d \ge 1$. Let $k \in \mathbb{N}$. The set of multi-indices of length at most $k$ (resp. of length $k$) is denoted $A_k^d$ (resp. $C_k^d$), and is defined by

$$A_k^d \stackrel{\text{def.}}{=} \{\alpha \in \mathbb{N}^d \mid |\alpha| \le k\} \quad (\text{resp. } C_k^d \stackrel{\text{def.}}{=} \{\alpha \in \mathbb{N}^d \mid |\alpha| = k\}),$$

$$\text{where } \forall \alpha \in \mathbb{N}^d, |\alpha| \stackrel{\text{def.}}{=} \sum_{i=1}^d \alpha_i.$$

Let $i \in [1..d]$. $A_{k,i}^d \stackrel{\text{def.}}{=} \{\alpha \in A_k^d | \alpha_i = 0\}$ is the subset of $A_k^d$ of multi-indices with zero $i$-th component.

(See also Definition 1486.) These multi-indices are used for two purposes in this document. First, they provide the multi-exponent of the multivariate monomial $X^\alpha \stackrel{\text{def.}}{=} \prod_{i=1}^d X_i^{\alpha_i}$ (whose total degree is $|\alpha|$, see Definition 1503). Thus, a polynomial of total degree at most $k$ is the sum of such monomials: for $(a_\alpha)_{\alpha \in A_k^d} \in \mathbb{R}$, $p \stackrel{\text{def.}}{=} \sum_{\alpha \in A_k^d} a_\alpha X^\alpha$ (see Definition 1505 and the following statements).

Second, they index the Lagrange nodes in a (nondegenerate) $d$-simplex. Let $K^{[\mathbf{v}]^d}$ be a simplex defined by its $d+1$ (affinely independent) vertices in $\mathbb{R}^d$, denoted by $[\mathbf{v}]^d \stackrel{\text{def.}}{=} (\mathbf{v}_0, \dots, \mathbf{v}_d)$. Then, the Lagrange nodes $\{\mathbf{a}\}_{A_k^d}$ are defined by

**Definition of Lagrange nodes.** Let $d \ge 1$. Let $k \in \mathbb{N}$. Let $[\mathbf{v}]^d$ be $d+1$ points in $\mathbb{R}^d$. The Lagrange nodes of $\mathbb{P}_k^d$ are denoted $\{\mathbf{a}\}_{A_k^d} = (\mathbf{a}_\alpha)_{\alpha \in A_k^d}$, and are defined by

$$(k=0) \qquad \mathbf{a}_0 \stackrel{\text{def.}}{=} \mathbf{g}^{[\mathbf{v}]^d} \left( = \frac{1}{d+1} \sum_{i=0}^{d} \mathbf{v}_i \right),$$

$$(k \ge 1) \qquad \forall \alpha \in A_k^d, \quad \mathbf{a}_\alpha \stackrel{\text{def.}}{=} \mathbf{v}_0 + \sum_{i=1}^d \frac{\alpha_i}{k} (\mathbf{v}_i - \mathbf{v}_0).$$

(See also Definition 1588.) The case of constant polynomials ($k=0$) is special, as the node is set at the isobarycenter of $[\mathbf{v}]^d$. We focus here on the general case when $k \ge 1$. In this case, the Lagrange nodes can be written equivalently

$$\mathbf{a}_{\alpha} = \frac{k - |\alpha|}{k} \mathbf{v}_0 + \sum_{i=1}^{d} \frac{\alpha_i}{k} \mathbf{v}_i, \quad \text{with} \quad \frac{k - |\alpha|}{k} + \sum_{i=1}^{d} \frac{\alpha_i}{k} = 1,$$

which exhibits the barycentric coordinates $(\frac{k-|\alpha|}{k}, \frac{\alpha_1}{k}, \dots, \frac{\alpha_d}{k})$ of $\mathbf{a}_\alpha$ with respect to $[\mathbf{v}]^d$ (see Section 9.4). For instance, in the reference simplex $\hat{K}^d$, whose reference vertices are $\hat{v}_0 \stackrel{\text{def.}}{=} \mathbf{0}$ and for $i \in [1..d]$, $\hat{v}_i \stackrel{\text{def.}}{=} \mathbf{e}_i$, this expression shows that each reference node $\hat{\mathbf{a}}_\alpha$ has coordinates $(\hat{\mathbf{a}}_\alpha)_i = \frac{\hat{\alpha}_i}{k}$. It is thus natural to represent a Lagrange node in a simplex by its multi-index in $A_k^d$, and to link it to the corresponding monomial, see Figure 3.1. These correspondences are used throughout the document.
<figure><img src="image_6.png" /><figcaption>Figure 3.1: Lagrange nodes $\{\hat{\mathbf{a}}_j\}_{j \in \mathcal{N}}$ of the reference simplex $\hat{K}_d$ when $d \in \{2, 3\}$ and $k=3$ (see Section 3.3.1).</figcaption></figure>

Each node is depicted as a colored ball, and corresponds to a unique element of $\mathcal{A}_3^d$. The colors correspond to degrees $l \le 3$ of polynomials, or equivalently to lengths of multi-indices (i.e. in $C_l^d$ for $l \le 3$). In magenta, the node $\hat{\mathbf{a}}_0$ corresponds to constant polynomials (with degree 0) in $\mathbb{P}_0^d$, and to the multi-index $\mathbf{0}$ in the singleton $C_0^d$. In green, the nodes correspond to non-constant affine polynomials (with degree 1), and to the multi-indices $e_1, \dots, e_d$ in $C_1^d$. In red, the nodes correspond to non-affine quadratic polynomials (with degree 2), and to multi-indices in $C_2^d$. In blue, the nodes correspond to non-quadratic cubic polynomials (with degree 3), and to multi-indices in $C_3^d$. We observe in this picture that $\mathcal{A}_3^d = C_0^d \uplus C_1^d \uplus C_2^d \uplus C_3^d$.

### 3.3.2 Monomial order

Once these notations are set, we can present the various possibilities to order multi-indices. Such ordering should be a *monomial order*, i.e. a total order that is compatible with the monoid structure of the monomials: for all $\alpha, \beta, \gamma \in \mathcal{A}_k^d$, $X^\alpha < X^\beta$ implies $X^\alpha X^\gamma < X^\beta X^\gamma$, which means that $\alpha < \beta$ implies $\alpha + \gamma < \beta + \gamma$. It is also generally required that for all $\alpha \neq \mathbf{0}$, $X^0 = 1 < X^\alpha$.

Among various possibilities, e.g. see [17, Chap. 2] and [16], we present commonly used monomial orders, and variants including one that reveals more convenient in our context (and that we call “grsymlex”, see Section 3.3.6).

In the sequel, $\alpha$ and $\beta$ denote any multi-indices in $\mathcal{A}_k^d$.

Note that we use the following notations when $d \ge 2$: the check notation $\check{\alpha}$ denotes the last $d-1$ components of $\alpha$, and the tilde notation $\tilde{\alpha}$ denotes the first ones. Thus, when $\alpha \stackrel{\text{def.}}{=} (\alpha_1, \dots, \alpha_d)$, we have $\alpha = (\alpha_1, \check{\alpha}) = (\tilde{\alpha}, \alpha_d)$, see also Remark 1490.

### 3.3.3 Lexicographic order

The *lexicographic order*, or simply “lex” order, can be recursively defined as

$$ (3.1) \qquad \alpha <^{\text{lex}} \beta \iff \begin{cases} \alpha_1 < \beta_1, & \text{or} \\ \alpha_1 = \beta_1 \wedge d \ge 2 \wedge \check{\alpha} <^{\text{lex}} \beta. \end{cases} $$

We have $\alpha <^{\text{lex}} \beta$ iff $\alpha_i < \beta_i$ for the first index $i$ for which $\alpha_i$ and $\beta_i$ differ.

Starting from the right, the *colexicographic order*, or simply “colex” order, can be recursively defined as

$$ (3.2) \qquad \alpha <^{\text{colex}} \beta \iff \begin{cases} \alpha_d < \beta_d, & \text{or} \\ \alpha_d = \beta_d \wedge d \ge 2 \wedge \tilde{\alpha} <^{\text{colex}} \tilde{\beta}. \end{cases} $$

We have $\alpha <^{\text{colex}} \beta$ iff $\alpha_i < \beta_i$ for the last index $i$ for which $\alpha_i$ and $\beta_i$ differ. The *colex* order is also called *inverse lexicographic order*, or simply “invlex” order, e.g. see [17, p. 61].
<figure><img src="image_7.png" /><figcaption>Figure 3.2: Lex (top left), colex (top right), symlex (bottom left), and revlex (bottom right) orderings of $\mathcal{A}_k^d$ when $d=2$ and $k=3$ (see Section 3.3.3).</figcaption></figure>

The increase in the order is represented by dashed arrows. For $\mathcal{A}_3^2$, we have $(0,0) <^{\text{lex}} (0,1) <^{\text{lex}} (0,2) <^{\text{lex}} (0,3)$, $<^{\text{lex}} (1,0)$, $<^{\text{lex}} (1,1)$, $<^{\text{lex}} (1,2)$, $<^{\text{lex}} (2,0)$, $<^{\text{lex}} (2,1)$, $<^{\text{lex}} (3,0)$, and $(0,0) <^{\text{colex}} (1,0)$, $<^{\text{colex}} (2,0)$, $<^{\text{colex}} (3,0)$, $<^{\text{colex}} (0,1)$, $<^{\text{colex}} (1,1)$, $<^{\text{colex}} (2,1)$, $<^{\text{colex}} (0,2)$, $<^{\text{colex}} (1,2)$, $<^{\text{colex}} (0,3)$.

The symlex order is the symmetrical of the lex order, and the revlex order is the symmetrical of the colex order. For instance, when the length is 3 (hypotenuse of the triangles, blue nodes), we have $(0,3) <^{\text{lex}} (1,2) <^{\text{lex}} (2,1) <^{\text{lex}} (3,0)$, and also $(0,3) <^{\text{revlex}} (1,2) <^{\text{revlex}} (2,1) <^{\text{revlex}} (3,0)$.

We may introduce the *symmetrical lexicographic order*, or simply “symlex” order, as

$$ (3.3) \qquad \alpha <^{\text{symlex}} \beta \underset{\text{def.}}{\Longrightarrow} \beta <^{\text{lex}} \alpha. $$

It is the symmetrical of the lex order, we have $\alpha <^{\text{symlex}} \beta$ iff $\beta_i < \alpha_i$ for the first index $i$ for which $\alpha_i$ and $\beta_i$ differ.

We may also define the *reverse lexicographic order*, or simply “revlex” order, as

$$ (3.4) \qquad \alpha <^{\text{revlex}} \beta \underset{\text{def.}}{\Longrightarrow} \beta <^{\text{colex}} \alpha. $$

It is the symmetrical of the colex order, we have $\alpha <^{\text{revlex}} \beta$ iff $\beta_i < \alpha_i$ for the last index $i$ for which $\alpha_i$ and $\beta_i$ differ. The *revlex* order is also called *reverse inverse lexicographic order*, or simply *“rinvlex” order*, e.g. see [17, p. 61].

The lex, colex, symlex, and revlex orders are monomial orders. Note also that lex and colex are obviously equivalent when $d=1$ (and so are symlex and revlex). Moreover, when $d=2$ and the multi-indices have the same length, lex and colex orders are symmetrical. Indeed, assume that $\alpha_1 + \alpha_2 = \beta_1 + \beta_2$. Then, we have $\alpha_1 < \beta_1 \Leftrightarrow \beta_2 < \alpha_2$ and $\alpha_1 = \beta_1 \Leftrightarrow \alpha_2 = \beta_2$, i.e. $(\alpha_1, \alpha_2) <^{\text{lex}} (\beta_1, \beta_2) \Leftrightarrow (\beta_1, \beta_2) <^{\text{colex}} (\alpha_1, \alpha_2)$. Thus, in that case ($|\alpha| = |\beta|$ and $d=2$), lex and revlex orders are equivalent, as well as colex and symlex. See a 2D example in Figure 3.2.

The lex order and its variants are not convenient in practice here, as they do not sort the monomials of a given polynomial according to their total degrees: for instance, for $d=2$, let $p \stackrel{\text{def.}}{=} X_1^0 X_2^8$ and $q \stackrel{\text{def.}}{=} X_1^1 X_2^2$, we have $p <^{\text{lex}} q$ (as $0 < 1$), but $\text{deg}(p) = 8 > 3 = \text{deg}(q)$. Thus, in the sequel, they are only be used to define other monomial orders.
<figure><img src="image_8.png" /><figcaption>Figure 3.3: Grlex (or deglex) ordering of $A_k^d$ when $d \in \{2, 3\}$ and $k = 3$ (see Section 3.3.4).</figcaption></figure>

The increase in the order is represented by dashed arrows (only in the case $l = 3$ when $d = 3$, see Figure 3.1).

For $A_3^2$ ($d = 2$), we have $(0, 0) < \text{grlex} (0, 1) < \text{grlex} (1, 0) < \text{grlex} (0, 2) < \text{grlex} (1, 1) < \text{grlex} (2, 0) < \text{grlex} (0, 3) < \text{grlex} (1, 2) < \text{grlex} (2, 1) < \text{grlex} (3, 0)$.

For $C_3^3$ ($d = 3$), we have $(0, 0, 3) < \text{grlex} (0, 1, 2) < \text{grlex} (0, 2, 1) < \text{grlex} (0, 3, 0) < \text{grlex} (1, 0, 2) < \text{grlex} (1, 1, 1) < \text{grlex} (1, 2, 0) < \text{grlex} (2, 0, 1) < \text{grlex} (2, 1, 0) < \text{grlex} (3, 0, 0)$.

### 3.3.4 Graded lexicographic order

The graded lexicographic order, or simply “grlex” order, is defined by

$$ (3.5) \qquad \alpha <_{\text{grlex}} \beta \iff_{\text{def.}} \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \alpha <_{\text{lex}} \beta. \end{cases} $$

This amounts to first compare the length of multi-indices, and in case of equality, use the standard lex order (3.1). Thus, when $|\alpha| = |\beta|$, we have $\alpha <_{\text{grlex}} \beta$ iff $\alpha_i < \beta_i$ for the first index $i$ for which $\alpha_i$ and $\beta_i$ differ.

We have the following equivalence, which may be seen as an alternative recursive definition,

$$ (3.6) \qquad \alpha <_{\text{grlex}} \beta \iff \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \alpha_1 < \beta_1, \text{ or} \\ |\alpha| = |\beta|, & \alpha_1 = \beta_1 \quad \wedge \ d \ge 2 \quad \wedge \ \tilde{\alpha} <_{\text{grlex}} \tilde{\beta}, \end{cases} $$

as when $|\alpha| = |\beta|$ and $\alpha_1 = \beta_1$, we have $|\tilde{\alpha}| = |\tilde{\beta}|$, and lex and grlex are identical. Note that the second case ($|\alpha| = |\beta|$ and $\alpha_1 < \beta_1$) implies $d \ge 2$.

This ordering is a monomial order. It is also called degree lexicographic order, or simply “deglex” order. See 2D and 3D examples in Figure 3.3.
<figure><img src="image_9.png" /><figcaption>Figure 3.4: Grcolex ordering of $A_k^d$ when $d \in \{2, 3\}$ and $k = 3$ (see Section 3.3.5).</figcaption></figure>

The increase in the order is represented by dashed arrows (only in the case $l = 3$ when $d = 3$, see Figure 3.1).

For $A_3^2$ ($d = 2$), we have $(0, 0) <_{\text{grcolex}} (1, 0) <_{\text{grcolex}} (0, 1) <_{\text{grcolex}} (2, 0) <_{\text{grcolex}} (1, 1) <_{\text{grcolex}} (0, 2) <_{\text{grcolex}} (3, 0) <_{\text{grcolex}} (2, 1) <_{\text{grcolex}} (1, 2) <_{\text{grcolex}} (0, 3)$.

For $C_3^3$ ($d = 3$), we have $(3, 0, 0) <_{\text{grcolex}} (2, 1, 0) <_{\text{grcolex}} (1, 2, 0) <_{\text{grcolex}} (0, 3, 0) <_{\text{grcolex}} (2, 0, 1) <_{\text{grcolex}} (1, 1, 1) <_{\text{grcolex}} (0, 2, 1) <_{\text{grcolex}} (1, 0, 2) <_{\text{grcolex}} (0, 1, 2) <_{\text{grcolex}} (0, 0, 3)$.

### 3.3.5 Graded colexicographic order

We design the *graded colexicographic order*, or simply “grcolex” order, defined by

$$ (3.7) \qquad \alpha <_{\text{grcolex}} \beta \underset{\text{def.}}{\implies} \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \alpha <_{\text{colex}} \beta. \end{cases} $$

This amounts to first compare the length of multi-indices, and in case of equality, use the colex order (3.2). Thus, when $|\alpha| = |\beta|$, we have $\alpha <_{\text{grcolex}} \beta$ iff $\alpha_i < \beta_i$ for the last index $i$ where $\alpha_i$ and $\beta_i$ differ.

We have the following equivalence, which may be seen as an alternative recursive definition,

$$ (3.8) \qquad \alpha <_{\text{grcolex}} \beta \iff \left\{ \begin{array}{l} |\alpha| < |\beta|, \text{ or} \\ |\alpha| = |\beta| \wedge \alpha_d < \beta_d, \text{ or} \\ |\alpha| = |\beta| \wedge \alpha_d = \beta_d \wedge d \ge 2 \wedge \tilde{\alpha} <_{\text{grcolex}} \tilde{\beta}. \end{array} \right. $$

as when $|\alpha| = |\beta|$ and $\alpha_d = \beta_d$, we have $|\tilde{\alpha}| = |\tilde{\beta}|$, and colex and grcolex are identical. Note that the second case ($|\alpha| = |\beta|$ and $\alpha_d < \beta_d$) implies $d \ge 2$.

This ordering is a monomial order. Compare on the same 2D and 3D examples the grcolex order in Figure 3.4 and the grlex order in Figure 3.3.
<figure><img src="image_10.png" /><figcaption>Figure 3.5: Grsymlex ordering of $A_k^d$ when $d \in \{2, 3\}$ and $k = 3$ (see Section 3.3.6).</figcaption></figure>

The increase in the order is represented by dashed arrows (only in the case $l = 3$ when $d = 3$, see Figure 3.1).

For $A_3^2$ ($d = 2$), we have (as in the case of grcolex) $(0, 0) < \text{grsymlex}(1, 0) < \text{grsymlex}(0, 1) < \text{grsymlex}(2, 0) < \text{grsymlex}(1, 1) < \text{grsymlex}(0, 2) < \text{grsymlex}(3, 0) < \text{grsymlex}(2, 1) < \text{grsymlex}(1, 2) < \text{grsymlex}(0, 3)$.

When $d \ge 3$, grcolex and grsymlex differ. For instance, for $C_3^3$ (compare with Figure 3.4), we have $(3, 0, 0) < \text{grsymlex}(2, 1, 0) < \text{grsymlex}(2, 0, 1) < \text{grsymlex}(1, 2, 0) < \text{grsymlex}(1, 1, 1) < \text{grsymlex}(1, 0, 2) < \text{grsymlex}(0, 3, 0) < \text{grsymlex}(0, 2, 1) < \text{grsymlex}(0, 1, 2) < \text{grsymlex}(0, 0, 3)$.

### 3.3.6 Graded symmetric lexicographic order

We also design the graded symmetric lexicographic order, or simply “grsymlex” order, defined by

$$ (3.9) \qquad \alpha <_{\text{grsymlex}} \beta \quad \overset{\text{def.}}{\implies} \quad \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \alpha <_{\text{symlex}} \beta. \end{cases} $$

This amounts to first compare the length of multi-indices, and in case of equality, use the symlex order (3.3). Thus, when $|\alpha| = |\beta|$, we have $\alpha <_{\text{grsymlex}} \beta$ iff $\beta_i < \alpha_i$ for the first index $i$ where $\alpha_i$ and $\beta_i$ differ.

We have the following equivalence, which may be seen as an alternative recursive definition,

$$ (3.10) \qquad \alpha <_{\text{grsymlex}} \beta \iff \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \beta_1 < \alpha_1, \text{ or} \\ |\alpha| = |\beta|, & \beta_1 = \alpha_1, \quad d \ge 2, \quad \check{\alpha} <_{\text{grsymlex}} \check{\beta}. \end{cases} $$

as when $|\alpha| = |\beta|$ and $\beta_1 = \alpha_1$, we have $|\check{\alpha}| = |\check{\beta}|$, and symlex and grsymlex are identical. Note that the second case ($|\alpha| = |\beta|$ and $\beta_1 < \alpha_1$) implies $d \ge 2$.

Moreover, the recursive definition may be simplified with the following equivalence,

$$ (3.11) \qquad \alpha <_{\text{grsymlex}} \beta \iff \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & d \ge 2, \quad \check{\alpha} <_{\text{grsymlex}} \check{\beta}. \end{cases} $$

as when $|\alpha| = |\beta|$ and $\beta_1 < \alpha_1$, we have $d \ge 2$ and $|\check{\alpha}| < |\check{\beta}|$, i.e. $\check{\alpha} <_{\text{grsymlex}} \check{\beta}$. Note that this simplification is made possible by the symmetric aspect of symlex. Note also that it is not possible for the grlex and grcolex orders: indeed, for instance for grlex, $|\alpha| = |\beta| \land \alpha_1 < \beta_1$ implies $|\check{\beta}| < |\check{\alpha}|$, i.e. $\check{\beta} <_{\text{grlex}} \check{\alpha}$, but not $\check{\alpha} <_{\text{grlex}} \check{\beta}$.

This ordering is a monomial order. Note that the grcolex and grsymlex orders are identical when $d = 1$ or $2$, but differ as soon as $d \ge 3$. Compare on the same 2D and 3D examples the grsymlex order in Figure 3.5, and the grcolex order in Figure 3.4.
<figure><img src="image_11.png" /><figcaption>Figure 3.6: Grevlex ordering of $A_k^d$ when $d \in \{2, 3\}$ and $k = 3$ (see Section 3.3.7).</figcaption></figure>

The increase in the order is represented by dashed arrows (only in the case $l = 3$ when $d = 3$, see Figure 3.1).

For $A_3^2$ ($d = 2$), we have (as in the case of grlex) $(0,0) <_{\text{grevlex}} (0,1) <_{\text{grevlex}} (1,0) <_{\text{grevlex}} (0,2) <_{\text{grevlex}} (1,1) <_{\text{grevlex}} (2,0) <_{\text{grevlex}} (0,3) <_{\text{grevlex}} (1,2) <_{\text{grevlex}} (2,1) <_{\text{grevlex}} (3,0)$.

When $d \ge 3$, grlex and grevlex differ. For instance, for $C_3^3$ (compare with Figure 3.3), we have $(0,0,3) <_{\text{grevlex}} (0,1,2) <_{\text{grevlex}} (1,0,2) <_{\text{grevlex}} (0,2,1) <_{\text{grevlex}} (1,1,1) <_{\text{grevlex}} (2,0,1) <_{\text{grevlex}} (0,3,0) <_{\text{grevlex}} (1,2,0) <_{\text{grevlex}} (2,1,0) <_{\text{grevlex}} (3,0,0)$.

### 3.3.7 Graded reverse lexicographic order

The graded reverse lexicographic order, or simply “grevlex” order, is defined by

$$ (3.12) \qquad \alpha <_{\text{grevlex}} \beta \quad \overset{\text{def.}}{\implies} \quad \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \alpha <_{\text{revlex}} \beta. \end{cases} $$

This amounts to first compare the length of multi-indices, and in case of equality, use the revlex order (3.4). Thus, when $|\alpha| = |\beta|$, we have $\alpha <_{\text{grevlex}} \beta$ iff $\beta_i < \alpha_i$ for the last index $i$ where $\alpha_i$ and $\beta_i$ differ.

We have the following equivalence, which may be seen as an alternative recursive definition,

$$ (3.13) \qquad \alpha <_{\text{grevlex}} \beta \quad \iff \quad \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & \beta_d < \alpha_d, \text{ or} \\ |\alpha| = |\beta|, & \beta_d = \alpha_d, \quad d \ge 2 \quad \land \quad \tilde{\alpha} <_{\text{grevlex}} \tilde{\beta}, \end{cases} $$

as when $|\alpha| = |\beta|$ and $\beta_d = \alpha_d$, we have $|\tilde{\alpha}| = |\tilde{\beta}|$, and revlex and grevlex are identical. Note that the second case ($|\alpha| = |\beta|$ and $\beta_d < \alpha_d$) implies $d \ge 2$.

Moreover, the recursive definition may be simplified with the following equivalence,

$$ (3.14) \qquad \alpha <_{\text{grevlex}} \beta \quad \iff \quad \begin{cases} |\alpha| < |\beta|, & \text{or} \\ |\alpha| = |\beta|, & d \ge 2 \quad \land \quad \tilde{\alpha} <_{\text{grevlex}} \tilde{\beta}, \end{cases} $$

as when $|\alpha| = |\beta|$ and $\beta_d < \alpha_d$, we have $d \ge 2$ and $|\tilde{\alpha}| < |\tilde{\beta}|$, i.e. $\tilde{\alpha} <_{\text{grevlex}} \tilde{\beta}$.

This ordering is a monomial order. Note that the grlex and grevlex orders are identical when $d = 1$ or $2$, but differ as soon as $d \ge 3$. Compare on the same 2D and 3D examples the grevlex order in Figure 3.6, and the grlex order in Figure 3.3.
### 3.3.8 Discussion

Several orders on $\mathbb{N}^d$ may be used to number multi-indices and the grevlex order of Section 3.3.7 is known to be well-suited for the division of multivariate polynomials using Gröbner bases, e.g. see [16, 17]. However, in the context of the FEM, other desired properties enter the picture. In this framework, a practical order should be consistent with

(i) an increase of the degree (from $k$ to $k+1$): multi-indices of length at most $k$ should be numbered before those of length $k+1$, i.e. for all $\alpha \in \mathcal{C}_k^d \subset \mathcal{A}_k^d$ and for all $\beta \in \mathcal{C}_{k+1}^d$, we should have $\alpha < \beta$;

(ii) an increase of the dimension (from $d-1$ to $d$): “natural” bijections between $d-1$-multi-indices of length at most $k$ and $d$-multi-indices of length $k$ should be increasing,

$f_{k,0}^d \stackrel{\text{def.}}{=} (\tilde{\alpha} \in \mathcal{A}_k^{d-1} \mapsto (k - |\tilde{\alpha}|, \tilde{\alpha}) \in \mathcal{C}_k^d)$, or
$\tilde{f}_{k,0}^d \stackrel{\text{def.}}{=} (\tilde{\alpha} \in \mathcal{A}_k^{d-1} \mapsto (\tilde{\alpha}, k - |\tilde{\alpha}|) \in \mathcal{C}_k^d)$ from Lemma 1500, and

* for any $i \in [1..d]$, $f_{k,i}^d \stackrel{\text{def.}}{=} (\alpha' \in \mathcal{A}_k^{d-1} \mapsto (\alpha'_1, \dots, \alpha'_{i-1}, 0, \alpha'_i, \dots, \alpha'_{d-1}) \in \mathcal{A}_{k,i}^d)$ from Lemma 1501,

i.e. $\mathcal{A}_k^{d-1}$, $\mathcal{C}_k^d$ ($= f_{k,0}^d(\mathcal{A}_k^{d-1}) = \tilde{f}_{k,0}^d(\mathcal{A}_k^{d-1})$), and $\mathcal{A}_{k,i}^d$ ($= f_{k,i}^d(\mathcal{A}_k^{d-1})$) share the same numbering;

(iii) the natural numbering of the multi-indices corresponding to the reference vertices $(\hat{v}_i)_{i \in [0..d]}$ of the reference simplex, i.e. $0 < ke_1 < ke_2 < \dots < ke_d$.

Indeed, condition (i) allows to easily sort monomials with respect to their total degree. Condition (ii) allows to easily relate the face nodes and the volume nodes during the computations. And condition (iii) allows to have positive simplices (i.e. positively oriented) when computing the integrals.

Obviously, condition (i) disqualifies the **lex** order and its variants of Section 3.3.3, but all “graded” orders are designed to comply with it.

Obviously, we also have $0 < ke_1$ (from condition (iii)) for all “graded” orders.

Conditions (ii) and (iii) are not met for the **grlex** order of Section 3.3.4, which is thus disqualified for our purpose. To see this, here are some counter-examples, cf. Figure 3.3. For (ii), with $d=k=3$, we have $(1,0) < \text{grlex}(0,2)$, while $f_{3,0}^3(0,2) = (1,0,2) < \text{grlex}(2,1,0) = f_{3,0}^3(1,0)$, and $\tilde{f}_{3,0}^3(0,2) = (0,2,1) < \text{grlex}(1,0,2) = \tilde{f}_{3,0}^3(1,0)$. For (iii), with $d=2$ and $k=3$, the vertex $\hat{v}_1 = \hat{a}_{(3,0)}$ is numbered after the vertex $\hat{v}_2 = \hat{a}_{(0,3)}$.

The **grcolex** order of Section 3.3.5 complies with (iii). Indeed, if $i < j$, then $|ke_i| = |ke_j| = k$, $j$ is the last index where the components of $ke_i$ and $ke_j$ differ, and the $j$-th component of $ke_i$ is 0, whereas $(ke_j)_j = k > 0$, thus $ke_i < \text{colex} ke_j$, i.e. $ke_i < \text{grcolex} ke_j$ (see Figure 3.4 in the cases $d \in \{2,3\}$ and $k=3$).

However, condition (ii) is not met for the **grcolex** order, which is thus also disqualified for our purpose. Indeed, from Figure 3.4 with $d=k=3$, we have $(0,1) < \text{grcolex}(2,0)$, while

$$f_{3,0}^3(2,0) = (1,2,0) < \text{grcolex}(2,0,1) = f_{3,0}^3(0,1), \quad \text{and} \\ \tilde{f}_{3,0}^3(2,0) = (2,0,1) < \text{grcolex}(0,1,2) = \tilde{f}_{3,0}^3(0,1).$$

The **grevlex** order of Section 3.3.7 satisfies condition (ii) with $\tilde{f}_{k,0}^d$ and $f_{k,i}^d$ (for all $i \in [1..d]$). Indeed, we have the following.
• Let $\tilde{\alpha}, \tilde{\beta} \in \mathcal{A}_k^{d-1}$ such that $\tilde{\alpha} <_{\text{grevlex}} \tilde{\beta}$. Let $\gamma \stackrel{\text{def.}}{=} \tilde{f}_{k,0}^d(\tilde{\alpha})$ and $\delta \stackrel{\text{def.}}{=} \tilde{f}_{k,0}^d(\tilde{\beta})$. Both $\gamma$ and $\delta$ have length $k$, and by removing their last component, we obtain $\tilde{\gamma} = \tilde{\alpha}$ and $\tilde{\delta} = \tilde{\beta}$. Hence, (3.14) yields $\tilde{f}_{k,0}^d(\tilde{\alpha}) <_{\text{grevlex}} \tilde{f}_{k,0}^d(\tilde{\beta})$. Thus, $\tilde{f}_{k,0}^d$ is increasing with respect to **grevlex**.

• Let $i \in [1..d]$, and $\alpha', \beta' \in \mathcal{A}_k^{d-1}$ such that $\alpha' <_{\text{grevlex}} \beta'$. We have $|f_{k,i}^d(\alpha')| = |\alpha'|$ and $|f_{k,i}^d(\beta')| = |\beta'|$. Thus, from (3.12), we have two cases:

- if $|\alpha'| < |\beta'|$, then we have $|f_{k,i}^d(\alpha')| < |f_{k,i}^d(\beta')|$, and thus $f_{k,i}^d(\alpha') <_{\text{grevlex}} f_{k,i}^d(\beta')$.

- if $|\alpha'| = |\beta'|$, then $\alpha' <_{\text{revlex}} \beta'$, and $|f_{k,i}^d(\alpha')| = |f_{k,i}^d(\beta')|$. The insertion of a "0" in position $i$ in $\alpha'$ and $\beta'$ does not alter the revlex order, and thus we also have $f_{k,i}^d(\alpha') <_{\text{revlex}} f_{k,i}^d(\beta')$, i.e. $f_{k,i}^d(\alpha') <_{\text{grevlex}} f_{k,i}^d(\beta')$.

Thus, in both cases, $f_{k,i}^d$ is increasing with respect to **grevlex**.

However, **grevlex** does not comply with condition (iii), as the vertex $\hat{v}_1 = \hat{a}_{(3,0)}$ is numbered after the vertex $\hat{v}_2 = \hat{a}_{(0,3)}$, see Figure 3.6 (left). For this reason, we also avoided **grevlex**.

Finally, the **grsymlex** order of Section 3.3.6 satisfies the three conditions. Indeed, for condition (ii), using $f_{k,0}^d$ instead of $\tilde{f}_{k,0}^d$ as for **grevlex**, we have the following.

• Let $\tilde{\alpha}, \tilde{\beta} \in \mathcal{A}_k^{d-1}$ such that $\tilde{\alpha} <_{\text{grsymlex}} \tilde{\beta}$. Let $\gamma \stackrel{\text{def.}}{=} f_{k,0}^d(\tilde{\alpha})$ and $\delta \stackrel{\text{def.}}{=} f_{k,0}^d(\tilde{\beta})$. Both $\gamma$ and $\delta$ have length $k$, and by removing their first component, we obtain $\tilde{\gamma} = \tilde{\alpha}$ and $\tilde{\delta} = \tilde{\beta}$. Hence, (3.11) yields $f_{k,0}^d(\tilde{\alpha}) <_{\text{grsymlex}} f_{k,0}^d(\tilde{\beta})$. Thus, $f_{k,0}^d$ is increasing with respect to **grsymlex**.

• Let $i \in [1..d]$, and $\alpha', \beta' \in \mathcal{A}_k^{d-1}$ such that $\alpha' <_{\text{grsymlex}} \beta'$. We have $|f_{k,i}^d(\alpha')| = |\alpha'|$ and $|f_{k,i}^d(\beta')| = |\beta'|$. Thus, from (3.9), we have two cases:

- if $|\alpha'| < |\beta'|$, then we have $|f_{k,i}^d(\alpha')| < |f_{k,i}^d(\beta')|$, and thus $f_{k,i}^d(\alpha') <_{\text{grsymlex}} f_{k,i}^d(\beta')$.

- if $|\alpha'| = |\beta'|$, then $\alpha' <_{\text{symlex}} \beta'$, and $|f_{k,i}^d(\alpha')| = |f_{k,i}^d(\beta')|$. The insertion of a "0" in position $i$ in $\alpha'$ and $\beta'$ does not alter the symlex order, and thus we also have $f_{k,i}^d(\alpha') <_{\text{symlex}} f_{k,i}^d(\beta')$, i.e. $f_{k,i}^d(\alpha') <_{\text{grsymlex}} f_{k,i}^d(\beta')$.

Thus, in both cases, $f_{k,i}^d$ is increasing with respect to **grsymlex**.

The **grsymlex** order also complies with (iii). Indeed, if $i < j$, then we have $|ke_i| = |ke_j| = k$, $i$ is the first index where the components of $ke_i$ and $ke_j$ differ, and the $i$-th component of $ke_j$ is 0, whereas $(ke_i)_i = k > 0$, thus $ke_i <_{\text{symlex}} ke_j$, i.e. $ke_i <_{\text{grsymlex}} ke_j$ (see Figure 3.5 in the cases $d \in \{2, 3\}$ and $k = 3$).

This is why the **grsymlex** order was chosen for the **Coq** implementation.

Note that the numbering of $\mathcal{A}_k^d$ is not used in the present version of this document, but is essential in the **Coq** formalization of the present work in [30, 9].
# Part II

## Detailed proofs
# Chapter 4

# Introduction

Statements are displayed inside colored boxes. Their nature can be identified at a glance by using the following color code:

<figure><img src="image_12.png" /></figure>

Definitions and results have a number and a name. Inside the bodies of proofs, pertinent statements are referenced using both their number and name. When appropriate, some hints are given about the application of the result, either to specify arguments, or to provide justification or consequences; they are *underlined*. Some useful definitions and results were already stated in [14] or in [15], which were respectively devoted to the detailed proofs of the Lax-Milgram theorem and for Lebesgue integration. Those are numbered up to 1356, and the statements in the present document are numbered starting from 1357.

Furthermore, as in [14, 15], the most basic results are supposed to be known and are not detailed further; they are displayed in **bold dark red**. These include:

• Naive set theory: definition and results about injective and bijective functions.

• Numbers:

– ordered abelian monoid properties of $\mathbb{N}$;

– ordered valued field properties of $\mathbb{R}$.

• Linear algebra:

– basic definitions and results about vector spaces and subspaces, such as freedom, generator, linear span, basis, dimension, and linear operations over functions;

– basic definitions and results about linear maps, such as distributivity of composition over addition, range/rank and kernel/nullity, the rank-nullity theorem, the characterization of surjectivity with the rank and injectivity with the nullity;

– some results in finite dimension, such as the rules for matrix-vector product, the incomplete basis theorem, and the dimension of the dual space.

• Topology in metric spaces: definitions of interior, open ball, and continuity.

• Calculus: basic definitions and results in $\mathbb{R}^n$, such as the usual norms, the differentiability of affine maps ($C^\infty$), and the rules of differentiation.

• Real analysis: basic definitions and results in $\mathbb{R}$, such as the rules of derivation.

• Polynomials: basic definitions about univariate polynomials, such as the degree.

This part is organized as follows. Chapter 5 contains some results from various fields of mathematics (arithmetic, linear and affine algebra, geometry, and univariate polynomials), that
are needed in the proofs for the finite element method. We recall that the material stated in [14, 15]
may also be used. Then, Chapter 6 is devoted to the general definition of finite element, and
Chapter 7 addresses simplicial geometry. Lagrange finite elements on segments are presented in
Chapter 8, and finally Chapter 9 is dedicated to the general case of dimension $d \ge 1$.
# Chapter 5

# Complements

## Contents

<table><tr><td>5.1</td><td>Complements on natural numbers</td><td>37</td></tr><tr><td>5.2</td><td>Complements on monoids</td><td>41</td></tr><tr><td>5.3</td><td>Complements on linear algebra</td><td>41</td></tr><tr><td>5.4</td><td>Complements on affine algebra</td><td>42</td></tr><tr><td>5.4.1</td><td>Affine subspaces</td><td>43</td></tr><tr><td>5.4.2</td><td>Affine maps and submaps</td><td>45</td></tr><tr><td>5.5</td><td>Complements on real affine geometry</td><td>50</td></tr><tr><td>5.6</td><td>Complements on univariate polynomials</td><td>51</td></tr></table>

## 5.1 Complements on natural numbers

Remark 1357. In Figures 5.1 and 5.2, we provide illustrations for the double inductions used in this document.

In Figure 5.1, a double induction “by diagonal” is presented, see Lemma 1358. The proof of unisolvence of $\mathbb{P}_k^d$ relies on it, see Lemma 1625. In Figure 5.2, the strong double induction is shown, see Lemma 1360. It is used in Lemma 1537.

**Lemma 1358 (double induction by diagonal).** Let $P$ be a predicate on $\mathbb{N}^2$. Then, we have

$$ (\forall m \in \mathbb{N}, P(m, 0)) \wedge (\forall n \in \mathbb{N}, P(0, n)) \wedge \\ (\forall m, n \in \mathbb{N}, P(m, n+1) \wedge P(m+1, n) \implies P(m+1, n+1)) \\ (5.1) \qquad \implies \forall m, n \in \mathbb{N}, P(m, n). $$

*Proof.* Let $H_0, H_1$, and $H_2$ be the three hypotheses in the implication (5.1).

For all $m \in \mathbb{N}$, let $Q(m) \stackrel{\text{def.}}{=} [\forall n \in \mathbb{N}, P(m, n)]$.

**Induction:** $Q(0)$. Trivial (hypothesis $H_1$).

**Induction:** $Q(m) \Rightarrow Q(m+1)$. Let $m \in \mathbb{N}$, assume that $Q(m)$ holds.

**Induction:** $P(m+1, 0)$. The property $P(m+1, 0)$ holds by hypothesis $H_0$.

**Induction:** $P(m+1, n) \Rightarrow P(m+1, n+1)$. Let $n \in \mathbb{N}$, assume that $P(m+1, n)$ holds.

Then, from $Q(m)$, we also have $P(m, n+1)$, and thus, from $H_2$, we have $P(m+1, n+1)$.

This concludes the induction on $n$, and we have for all $n \in \mathbb{N}$, $P(m+1, n)$, i.e., $Q(m+1)$.

This concludes the induction on $m$, and we have for all $m \in \mathbb{N}$, $Q(m)$.

Therefore, we have $\forall m, n \in \mathbb{N}, P(m, n)$. $\square$
<figure><img src="image_13.png" /><figcaption>Figure 5.1: Double induction scheme “by diagonal” (see Lemma 1358).</figcaption></figure>

Let a predicate $P(m, n)$. Assume the initializations $P(0, n)$ and $P(m, 0)$ for all $m$ and $n$ (symbolized by green dots along the two axes). Then, if $P(m, n+1)$ and $P(m+1, n)$ implies $P(m+1, n+1)$ (represented by green dots and arrows), then $P(m, n)$ holds everywhere. It is proven by induction on $m$, then on $n$. Thus, fixing $m$, one proves successively $P(m+1, k)$, for all $k$ (red arrows and dots).

**Remark 1359.** The strong induction principle stipulates that a predicate $P$ on $\mathbb{N}$ holds everywhere if it satisfies the property

$$ \forall n \in \mathbb{N}, \quad (\forall n_1 < n, \ P(n_1)) \implies P(n). $$

Note that there is no need to assume the base case $P(0)$ since it follows from the previous hypothesis. Indeed, for all $n_1 \in \mathbb{N}$, $n_1 < 0$, which is false, implies anything, such as $P(n_1)$.

In the next lemma, the condition $m_1 \le m \land n_1 \le n \land (m_1, n_1) \ne (m, n)$ can be reformulated as $(m_1 < m \land n_1 \le n) \lor (m_1 = m \land n_1 < n)$. As in the strong induction for a single integer, the initialization steps $P(m, 0)$ and $P(0, n)$ are not needed for the double strong induction.

<figure><img src="image_14.png" /><figcaption>Figure 5.2: Strong double induction scheme (see Lemma 1360).</figcaption></figure>

The induction hypothesis is as follows: if the proposition holds on all the green nodes, then it holds on the red one.

**Lemma 1360 (strong double induction).**

Let $P$ be a predicate on $\mathbb{N}^2$. Then, we have

$$ (5.2) \qquad \left[ \begin{array}{l} \forall m, n \in \mathbb{N}, \quad (\forall m_1 \le m, \forall n_1 \le n, (m_1, n_1) \ne (m, n) \Rightarrow P(m_1, n_1)) \\ \qquad \implies P(m, n)] \\ \forall m, n \in \mathbb{N}, \quad P(m, n). \end{array} \right. $$

*Proof.* For all $m \in \mathbb{N}$, let $Q(m) \stackrel{\text{def.}}{=} [\forall n \in \mathbb{N}, P(m, n)]$.
**Strong induction on $m$: ($\forall m_1 < m, Q(m_1) \Rightarrow Q(m)$).**

Let $m \in \mathbb{N}$, assume that $H_1: \forall m_1 < m, Q(m_1)$ holds. Let us show that $Q(m)$ holds.

**Strong induction on $n$: ($\forall n_1 < n, P(m, n_1) \Rightarrow P(m, n)$).**

Let $n \in \mathbb{N}$, assume that $H_2: \forall n_1 < n, P(m, n_1)$ holds. Let us show that $P(m, n)$ holds.

Let $m_1 \le m$ and $n_1 \le n$, assume that $(m_1, n_1) \ne (m, n)$. **Case $m_1 < m$.** Then, $P(m_1, n_1)$ holds by $H_1$. **Case $m_1 = m$.** Then, $n_1 < n$, and $P(m_1, n_1) = P(m, n_1)$ holds by $H_2$. Thus, in both cases, $P(m_1, n_1)$ holds, and from the hypothesis in (5.2), we have $P(m, n)$.

This concludes the strong induction on $n$, and we have for all $n \in \mathbb{N}$, $P(m, n)$, i.e., $Q(m)$.

This concludes the strong induction on $m$, and we have for all $m \in \mathbb{N}$, $Q(m)$.

Therefore, we have $\forall m, n \in \mathbb{N}, P(m, n)$.

**Remark 1361.**

Note that, for $n, p \in \mathbb{N}$, we use the convention $n - p \stackrel{\text{def.}}{=} 0$ when $n < p$ (to have a result in $\mathbb{N}$).

**Definition 1362 (binomial coefficient).**

Let $n, p \in \mathbb{N}$. Then, the binomial coefficient is defined as

$$ (5.3) \qquad \binom{n}{p} \stackrel{\text{def.}}{=} \frac{n!}{p! (n-p)!} \quad \text{when } p \le n, \quad \text{and} \quad \binom{n}{p} \stackrel{\text{def.}}{=} 0 \text{ otherwise.} $$

**Remark 1363.** Note that the formula with factorials on the left of (5.3) can be extended to the irregular case when $n < p$ (and yields the value 0) provided the use of the Euclidean division. Indeed, in this case $\binom{n}{p} = \frac{n!}{p!0!}$, whose Euclidean division is 0 because $n! < p!$.

In the Pascal triangle formula (5.7), the regular case $1 \le p \le n-1$ (with $n \ge 1$) is extended with the convention of (5.3) and the remark that $\binom{0-1}{p} = \binom{0}{p}$, for $p \in \mathbb{N}$.

**Lemma 1364 (properties of the binomial coefficient).**

Let $n, p \in \mathbb{N}$. Then, we have

$$ (5.4) \qquad \binom{n}{0} = \binom{n}{n} = 1, $$

$$ (5.5) \qquad n \ge 1 \quad \Longrightarrow \quad \binom{n}{1} = \binom{n}{n-1} = n, $$

$$ (5.6) \qquad p \le n \quad \Longrightarrow \quad \binom{n}{n-p} = \binom{n}{p}, $$

$$ (5.7) \qquad (n \ne 0 \lor p \ne 1) \quad \land \quad p \ne 0 \quad \Longrightarrow \quad \binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}, $$

$$ (5.8) \qquad p \ge 1 \quad \Longrightarrow \quad \sum_{j=0}^{n} \binom{j+p-1}{p-1} = \binom{n+p}{p}, $$

$$ (5.9) \qquad \binom{n}{p} \in \mathbb{N}. $$

**Proof.**

Properties (5.4), (5.5) and (5.6) are direct consequences of Definition 1362 (binomial coefficient).

(5.7). **Case $p < n$.** Then, $n \ge 1$ and $1 \le p \le n-1$, and all binomials are regular. Thus, from Definition 1362 (binomial coefficient), we have

$$ \binom{n-1}{p-1} + \binom{n-1}{p} = \frac{(n-1)!}{(p-1)!(n-p)!} + \frac{(n-1)!}{p!(n-p-1)!} = \frac{(n-1)!(p+(n-p))}{p!(n-p)!} = \binom{n}{p}. $$

**Case $p = n$.** Then, $n \ge 1$, $\binom{n-1}{n} = 0$, and from (5.4), the equality holds.

**Case $n < p$.** Then, $p \ge 2$, all three binomials are equal to 0, and the equality holds.
(5.8). Let $p \ge 1$. For all $n \in \mathbb{N}$, let $P(n) \stackrel{\text{def.}}{=} \left[ \sum_{j=0}^{n} \binom{j+p-1}{p-1} \right] = \binom{n+p}{p}$.

**Induction: $P(0)$.** Direct consequence of (5.4).

**Induction: $P(n) \Rightarrow P(n+1)$.** Let $n \in \mathbb{N}$, assume that $P(n)$ holds. Then, from **abelian monoid properties of $\mathbb{N}$**, and (5.7) (with $(n+p+1, p) \ne (0, 1)$ and $p \ne 0$), we have

$$ \sum_{j=0}^{n+1} \binom{j+p-1}{p-1} = \sum_{j=0}^{n} \binom{j+p-1}{p-1} + \binom{n+p}{p-1} = \binom{n+p}{p} + \binom{n+p}{p-1} = \binom{n+1+p}{p}. $$

This concludes the induction on $n$, and we have for all $n \in \mathbb{N}$, $P(n)$.

(5.9). Let $P(n) \stackrel{\text{def.}}{=} [\forall p \in \mathbb{N}, \binom{n}{p} \in \mathbb{N}]$. **Strong induction on $n$: ($\forall n_1 < n$, $P(n_1)$) $\Rightarrow$ $P(n)$**.

**Case $n=0$ and $p=1$.** Then, from Definition 1362 (**binomial coefficient**), we have $\binom{n}{p} = 0 \in \mathbb{N}$.

**Case $p=0$.** Then, from (5.4), we have $\binom{n}{p} = 1 \in \mathbb{N}$.

**Case ($n \ne 0 \lor p \ne 1$) and $p \ne 0$.** Let $n_1 < n$, assume that $\binom{n_1}{p} \in \mathbb{N}$ for all $p \in \mathbb{N}$.

Then, from (5.7), and **monoid properties of $\mathbb{N}$**, we have $\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p} \in \mathbb{N}$.

This concludes the strong induction on $n$, and we have for all $n \in \mathbb{N}$, $P(n)$. $\square$

**Definition 1365 (canonic families).** Let $d \ge 1$.

The notation **0**, resp. **1**, represents the constant family of value 0, resp. 1, either in $\mathbb{N}^d$ or in $\mathbb{R}^d$. For all $i \in [1..d]$, $e_i$ denotes the element of the canonical “basis” family in $\mathbb{N}^d$ or in $\mathbb{R}^d$, such that $(e_i)_j = \delta_{ij}$ for all $j \in [1..d]$.

Let $n \in \mathbb{N}$. The notation $[[\mathbf{v}]]^{n,d} \stackrel{\text{def.}}{=} (\mathbf{v}_0, \dots, \mathbf{v}_n)$ represents a family of $n+1$ points in $\mathbb{R}^d$. When $n \stackrel{\text{def.}}{=} d$, it is simply written $[[\mathbf{v}]]^d$.

**Lemma 1366 (circular permutation).**

Let $d \in \mathbb{N}$, and $i \in [0..d]$. Let $c_i^d$ be the function defined by

$$ (5.10) \qquad \forall j \in [0..d], \qquad c_i^d(j) \stackrel{\text{def.}}{=} \begin{cases} j+i+1 & \text{when } j < d-i, \\ j-(d-i) & \text{otherwise.} \end{cases} $$

Then, $c_i^d$ is bijective from $[0..d]$ onto $[0..d]$, and we have $c_i^d(d) = i$ and $d = (c_i^d)^{-1}(i)$.

In particular, we have $c_d^d = \text{Id}_{[0..d]}$.

**Proof.** From **monoid properties of $\mathbb{N}$**, the fact that monotony on disjoint parts implies injectivity, and the fact that injectivity and cardinal equality imply bijectivity, the permutation $c_i^d$ is increasing from $[0..d-i-1]$ to $[i+1..d]$ and from $[d-i..d]$ to $[0..i]$, both $[0..d-i-1] \cap [d-i..d]$ and $[i+1..d] \cap [0..i]$ are empty, and $[0..d] = [0..d-i-1] \cup [d-i..d]$ equals $[i+1..d] \cup [0..i]$, thus it is bijective from $[0..d]$ onto itself.

If $j=d$, then $j \ge d-i$, and we have $c_i^d(d) = d-(d-i) = i$.

If $i=d$, the set $\{j < d-d\}$ is empty, and we have $c_d^d(j) = j-(d-d) = j$ for all $j \in [0..d]$. $\square$

**Lemma 1367 (transposition).** Let $d \in \mathbb{N}$, and $i \in [0..d]$. Let $\tau_i^d$ be the function defined by

$$ (5.11) \qquad \forall j \in [0..d], \qquad \tau_i^d(j) \stackrel{\text{def.}}{=} \begin{cases} d & \text{when } j \stackrel{\text{def.}}{=} i, \\ i & \text{when } j \stackrel{\text{def.}}{=} d, \\ j & \text{otherwise.} \end{cases} $$

Then, $\tau_i^d$ is involutive and bijective from $[0..d]$ onto $[0..d]$.

In particular, we have $\tau_d^d = \text{Id}_{[0..d]}$.

**Proof.** From **monoid properties of $\mathbb{N}$**, we have $\tau_i^d([0..d]) \subset [0..d]$, and $\tau_i^d \circ \tau_i^d = \text{Id}_{[0..d]}$, thus it is involutive and bijective from $[0..d]$ onto itself.

If $i=d$, we have $\tau_d^d(d) = d$, and, for all $j \in [0..d-1]$, $\tau_d^d(j) = j$, hence the result. $\square$
**Lemma 1368 (jump enumeration).**

Let $d \in \mathbb{N}$, and $i \in [0..d+1]$. Let $\theta_i^d$ be the function defined by

$$ (5.12) \qquad \forall j \in [0..d], \quad \theta_i^d(j) \stackrel{\text{def.}}{=} \begin{cases} j & \text{when } j < i, \\ j+1 & \text{otherwise.} \end{cases} $$

Then, $\theta_i^d$ is injective from $[0..d]$ to $[0..d+1]$, and we have $\theta_i^d([0..d]) = [0..d+1] \setminus \{i\}$.

In particular, we have $\theta_0^d = \text{Id}_{[0..d]} + 1$ and $\theta_{d+1}^d = \text{Id}_{[0..d]}$.

*Proof.* **Injectivity.** Let $j, k \in [0..d]$. Assume that $r \stackrel{\text{def.}}{=} \theta_i^d(j) = \theta_i^d(k)$.

**Case i $\le$ j, k.** Then $r = j + 1 = k + 1$, and thus, from **monoid properties of $\mathbb{N}$**, $j = k$.

**Case j < i $\le$ k.** Then $r = j = k + 1$, which contradicts $j < k$.

**Case k < i $\le$ j.** Then $r = j + 1 = k$, which contradicts $k < j$.

**Case j, k < i.** Then $r = j = k$.

Thus, from **the definition of injectivity**, we have $j = k$ in all cases, and $\theta_i^d$ is injective.

**Image.** Direct consequence of **monotony of image**, and **monoid properties of $\mathbb{N}$**, with $[0..d] = [0..i-1] \cup [i..d]$, $\theta_i^d([0..i-1]) = [0..i-1]$, $\theta_i^d([i..d]) = [i+1..d+1]$, and $[0..i-1] \cup [i+1..d+1]$ equals $[0..d+1] \setminus \{i\}$.

**Cases i = 0 and i = d.** Direct consequence of **monoid properties of $\mathbb{N}$**. $\square$

<figure><img src="image_15.png" /></figure>

## 5.2 Complements on monoids

**Lemma 1369 (image of ker is included in ker).** Let $E, F$ be sets, and $G$ be a monoid.

Let $f : E \to F$ and $g : F \to G$ be functions. Then, we have

$$ (5.13) \qquad f(\ker (g \circ f)) \subseteq \ker(g). $$

*Proof.* Let $x \in \ker(g \circ f)$. Then, from Definition 101 (**kernel**, extended to functions taking values in a monoid), we have $g(f(x)) = 0$, and thus, $f(x) \in \ker(g)$. $\square$

<figure><img src="image_16.png" /></figure>

**Lemma 1370 (image of ker is ker).** Let $E, F$ be sets, and $G$ be a monoid.

Let $f : E \to F$ and $g : F \to G$ be functions. Assume that $f$ is surjective. Then, we have

$$ (5.14) \qquad f(\ker(g \circ f)) = \ker(g). $$

*Proof.* From Lemma 1369 (**image of ker is included in ker**), we have $f(\ker(g \circ f)) \subseteq \ker(g)$.

Reciprocally, let $y \in \ker(g)$. Then, from Definition 101 (**kernel**, $g(y) = 0$), and **the definition of surjectivity (let $x$ such that $y = f(x)$)**, we have $g(f(x)) = g(y) = 0$, and $x \in \ker(g \circ f)$.

Thus, $y = f(x)$ belongs to $f(\ker(g \circ f))$. $\square$

<figure><img src="image_17.png" /></figure>

## 5.3 Complements on linear algebra

*Remark 1371.*

In this section, vector spaces are supposed to be defined over some scalar field $\mathbb{K}$, such as $\mathbb{R}$ or $\mathbb{C}$.

**Lemma 1372 (vector subspace is invariant by translation).** Let $E$ be a vector space.

Let $E'$ be a vector subspace of $E$. Let $u'_0 \in E'$. Then, we have $E' + u'_0 \stackrel{\text{def.}}{=} \{u' + u'_0 | u' \in E'\} = E'$.

*Proof.* Direct consequence of Lemma 81 (**closed under vector operations is subspace**). $\square$

<figure><img src="image_18.png" /></figure>

**Lemma 1373 (range of linear map is vector subspace).**

Let $E$ and $F$ be vector spaces. Let $f \in \mathcal{L}(E, F)$. Then, the range $f(E)$ is a vector subspace of $F$.
**Proof.** Direct consequence of Definition 64 (**linear map**), **the definition of the range of a function**, and Lemma 81 (**closed under vector operations is subspace**). □

**Lemma 1374 (injectivity or surjectivity and dimension implies bijectivity).**
Let E and F be vector spaces. Let $f \in \mathcal{L}(E, F)$ be a linear map from E to F. Then, we have

$$ (5.15) \qquad (\infty > \dim E \ge \dim F \wedge f \text{ injective}) \implies f \text{ bijective,} $$

$$ (5.16) \qquad (\dim E \le \dim F < \infty \wedge f \text{ surjective}) \implies f \text{ bijective.} $$

**Proof.** Direct consequences of **the rank-nullity theorem**, **the characterization of surjectivity with the rank**, Lemma 103 (**injective linear map has zero kernel**), and $\dim\{0\} = 0$. □

**Lemma 1375 (inverse of isomorphism is linear map).** Let E and F be vector spaces. Let $f \in \mathcal{L}(E, F)$ be a linear map from E to F. Assume that $f$ is an isomorphism from E onto F. Then, $f^{-1}$ is a linear map from F to E.

**Proof.** From Definition 100 (**isomorphism**, $f$ is bijective), there exists a mapping $f^{-1}$ from F to E. Let $\lambda, \lambda' \in \mathbb{K}$ be scalars. Let $v, v' \in F$ be vectors. Let $u, u' \in E$ be the preimages of $v$ and $v'$ ($f(u) = v$ and $f(u') = v'$). Then, from Definition 100 (**isomorphism**, $f$ is linear), and Lemma 95 (**linear map preserves linear combinations**), we have

$$ f(\lambda u + \lambda' u') = \lambda f(u) + \lambda' f(u') = \lambda v + \lambda' v'. $$

Thus, $\lambda u + \lambda' u'$ is the preimage of $\lambda v + \lambda' v'$, i.e.

$$ f^{-1}(\lambda v + \lambda' v') = \lambda u + \lambda' u' = \lambda f^{-1}(v) + \lambda' f^{-1}(v'). $$

Therefore, from Lemma 95 (**linear map preserves linear combinations**), $f^{-1}$ is a linear map. □

**Lemma 1376 (free family of dim elements is basis).**
Let E be a vector space of dimension $n > 0$. Then, any free family of $n$ elements is a basis of E.

**Proof.** Direct consequence of **the incomplete basis theorem** in the case where the free family is completed with an empty family. □

## 5.4 Complements on affine algebra

**Remark 1377.** In this section, vector spaces are supposed to be defined over some scalar field $\mathbb{K}$, but some results are only stated for $\mathbb{K} \stackrel{\text{def.}}{=} \mathbb{R}$. Even though most of the latter can be extended to any field of characteristic not 2, such as $\mathbb{C}$, this is not considered here.

**Remark 1378.** Note that the notion of affine space associated with a vector space can be defined in an abstract way, either through a function that builds a vector from any two points, or equivalently, through a *translation function* that builds a point from any point and any vector. Barycenters correspond to linear combinations with coefficients of sum 1. Then, affine subspaces are those closed under barycenter, and affine functions (from an affine space to another) are those that preserve barycenters. Affine functions between two given affine spaces can be proved to form an affine space.

Actually, any vector space can be equipped with an affine structure, and vice versa. Moreover, in the present work, in most cases, we encounter affine structures associated to the vector spaces $\mathbb{R}^n$, and the abstract vision is not mandatory. Thus, we choose to only define affine subspaces of a vector space, and affine maps between two affine subspaces. Elements are called *vectors* to emphasize their linear properties, or *points* to emphasize their affine properties.
### 5.4.1 Affine subspaces

**Definition 1379 (affine subspace).**

Let $E$ be a vector space. A subset $\mathcal{E}'$ of $E$ is said to be an affine subspace of $E$ iff there exists a vector subspace $E'$ of $E$ and $\mathbf{x}_0 \in E$ such that $\mathcal{E}' = \mathbf{x}_0 + E' \stackrel{\text{def.}}{=} \{\mathbf{x}_0 + \mathbf{u}' | \mathbf{u}' \in E'\}$.

Then, $E'$ is called the direction of the affine subspace $\mathcal{E}'$, and $\mathbf{x}_0$ its origin. Elements of affine subspaces are called points.

**Lemma 1380 (origin is in affine subspace).**

Let $E$ be a vector space. Let $E'$ be a vector subspace of $E$, and $\mathbf{x}_0 \in E$. Then, we have $\mathbf{x}_0 \in \mathcal{E}'$.

*Proof.* Direct consequence of Definition 1379 (affine subspace), and Lemma 81 (closed under vector operations is subspace, $0 \in E'$). □

**Lemma 1381 (equivalent definition of affine subspace).**

Let $E$ be a vector space. Let $\mathcal{E}' \subset E$. Let $\mathbf{x}'_0 \in \mathcal{E}'$.

Then, $\mathcal{E}'$ is an affine subspace of $E$ iff $\mathcal{E}' - \mathbf{x}'_0 \stackrel{\text{def.}}{=} \{\mathbf{x}' - \mathbf{x}'_0 | \mathbf{x}' \in \mathcal{E}'\}$ is a vector subspace of $E$. Moreover, let $E'$ be a vector subspace of $E$, and let $\mathbf{x}_0 \in E$, then we have

$$ (5.17) \qquad \forall \mathbf{x} \in E, \quad \mathbf{x} \in \mathbf{x}_0 + E' \iff \mathbf{x} - \mathbf{x}_0 \in E'. $$

*Proof.* First equivalence. Direct consequence of Definition 1379 (affine subspace, thus $\mathcal{E}'$ equals $\mathbf{x}_0 + E'$ with $E' \subset E$ subspace and $\mathbf{x}_0 \in E$, $\mathbf{x}'_0 = \mathbf{x}_0 + \mathbf{u}'_0$ and $\mathbf{x}' = \mathbf{x}_0 + \mathbf{u}'$ for all $\mathbf{x}' \in \mathcal{E}'$ with $\mathbf{u}'_0$, $\mathbf{u}' \in E'$), Lemma 1372 (vector subspace is invariant by translation, with $-\mathbf{u}'_0$), and Definition 61 (vector space, additive group properties, thus $\mathbf{x}' - \mathbf{x}'_0 = \mathbf{u}' - \mathbf{u}'_0$, and $\mathcal{E}' - \mathbf{x}'_0 = E' - \mathbf{u}'_0 = E'$).

(5.17). Direct consequence of Definition 1379 (affine subspace), Lemma 81 (closed under vector operations is subspace). □

**Lemma 1382 (affine subspace is invariant by change of origin).**

Let $E$ be a vector space. Let $E'$ be a vector subspace of $E$ and $\mathbf{x}_0 \in E$. Let $\mathbf{y}' \in \mathbf{x}_0 + E'$. Then, we have $\mathbf{x}_0 + E' = \mathbf{y}' + E'$. □

*Proof.* Direct consequence of Definition 1379 (affine subspace, thus $\mathbf{y}' = \mathbf{x}_0 + \mathbf{u}'_0$ with $\mathbf{u}'_0 \in E'$), Lemma 81 (closed under vector operations is subspace), Lemma 1372 (vector subspace is invariant by translation, with $-\mathbf{u}'_0$ thus $E' - \mathbf{u}'_0 = E'$), and Lemma 1381 (equivalent definition of affine subspace, thus $\mathbf{x} \in \mathbf{y}' + E'$ iff $(\mathbf{x} - \mathbf{x}_0) - \mathbf{u}'_0 \in E' = E' - \mathbf{u}'_0$ iff $\mathbf{x} - \mathbf{x}_0 \in E'$ iff $\mathbf{x} \in \mathbf{x}_0 + E'$). □

**Lemma 1383 (vector subspace is affine subspace).**

Let $E$ be a vector space. Let $E'$ be a vector subspace of $E$. Then, $E'$ is an affine subspace of $E$, of direction itself and of origin any of its points.

*Proof.* Direct consequence of Lemma 1372 (vector subspace is invariant by translation), and Lemma 1381 (equivalent definition of affine subspace). □

**Remark 1384.** For instance, note that $E$ is also an affine subspace of itself, e.g. with origin $0$. □

**Lemma 1385 (affine subspace plus vector subspace is affine subspace).** Let $E$ be a vector space. Let $E'$ be a vector subspace of $E$, let $\mathbf{x}_0 \in E$, and let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$. Let $F'$ be a vector subspace of $E'$. Then, we have $\mathcal{E}' + F' \stackrel{\text{def.}}{=} \{\mathbf{x}' + \mathbf{v}' | \mathbf{x}' \in \mathcal{E}' \wedge \mathbf{v}' \in F'\} = \mathcal{E}'$.

*Proof.* $\mathcal{E}' + F' \subset \mathcal{E}'$. Direct consequence of Definition 61 (vector space, additive abelian group properties, thus $\mathbf{x}' + \mathbf{v}' = \mathbf{x}_0 + ((\mathbf{x}' - \mathbf{x}_0) + \mathbf{v}')$), Lemma 1381 (equivalent definition of affine subspace, (5.17), thus $\mathbf{x}' - \mathbf{x}_0 \in E'$), and Lemma 81 (closed under vector operations is subspace, thus $(\mathbf{x}' - \mathbf{x}_0) + \mathbf{v}' \in E'$).

$\mathcal{E}' + F' \supset \mathcal{E}'$. Direct consequence of Definition 1379 (affine subspace), and Lemma 81 (closed under vector operations is subspace, thus $0 \in F'$). □
**Lemma 1386 (closed under barycenter is affine subspace).** Let E be a real vector space. Let $\mathcal{E}' \subset E$ be nonempty. Then, $\mathcal{E}'$ is an affine subspace of E iff it is closed under barycenter,

$$ (5.18) \quad \forall n \in \mathbb{N}, \forall (\mathbf{v}_i)_{i \in [0..n]} \in \mathcal{E}', \forall (\mu_i)_{i \in [0..n]} \in \mathbb{R}, \quad \sum_{i=0}^{n} \mu_i = 1 \quad \implies \quad \sum_{i=0}^{n} \mu_i \mathbf{v}_i \in \mathcal{E}'. $$

*Proof. From left to right.* Direct consequence of Definition 1379 (affine subspace, thus $\mathcal{E}'$ is of the form $\mathbf{x}_0 + E'$), Lemma 1381 (equivalent definition of affine subspace, (5.17)), Definition 61 (vector space, thus $\sum_{i=0}^{n} \mu_i \mathbf{v}_i - \mathbf{x}_0 = \sum_{i=0}^{n} \mu_i (\mathbf{v}_j - \mathbf{x}_0)$), and Lemma 82 (closed under linear combination is subspace, with $\mathbf{v}_i - \mathbf{x}_0 \in E'$).

**From right to left.** Let $\mathbf{x}'_0 \in \mathcal{E}'$. Assume that $\mathcal{E}'$ is closed under barycenter.

1. $0 \in \mathcal{E}' - \mathbf{x}'_0$. Trivial.

2. $\mathcal{E}' - \mathbf{x}'_0$ is closed under scalar multiplication.

Let $a \in \mathbb{R}$ and $\mathbf{u} \in \mathcal{E}' - \mathbf{x}'_0$, i.e. $\mathbf{x}'_0 + \mathbf{u} \in \mathcal{E}'$. Then, from Definition 61 (vector space), and hypothesis (with $(1-a)+a=1$), we have $\mathbf{x}'_0 + a\mathbf{u} = (1-a)\mathbf{x}'_0 + a(\mathbf{x}'_0 + \mathbf{u}) \in \mathcal{E}'$. Thus, $a\mathbf{u} \in \mathcal{E}' - \mathbf{x}'_0$.

3. $\mathcal{E}' - \mathbf{x}'_0$ is closed under addition.

Let $\mathbf{u}, \mathbf{v} \in \mathcal{E}' - \mathbf{x}'_0$, i.e. $\mathbf{x}'_0 + \mathbf{u}, \mathbf{x}'_0 + \mathbf{v} \in \mathcal{E}'$. Then, from Definition 61 (vector space), and hypothesis (with $\frac{1}{2} + \frac{1}{2} = 1$), we have $\mathbf{x}'_0 + \frac{1}{2}(\mathbf{u} + \mathbf{v}) = \frac{1}{2}(\mathbf{x}'_0 + \mathbf{u}) + \frac{1}{2}(\mathbf{x}'_0 + \mathbf{v}) \in \mathcal{E}'$. Thus, $\frac{1}{2}(\mathbf{u} + \mathbf{v}) \in \mathcal{E}' - \mathbf{x}'_0$, and from 2 (with $a \stackrel{\text{def.}}{=} 2$), we have $u + v = 2(\frac{1}{2}(\mathbf{u} + \mathbf{v})) \in \mathcal{E}' - \mathbf{x}'_0$.

Finally, from Lemma 81 (closed under vector operations is subspace), and Lemma 1381 (equivalent definition of affine subspace), $\mathcal{E}' - \mathbf{x}'_0$ is a vector subspace, and $\mathcal{E}'$ is an affine subspace. $\square$

**Lemma 1387 (barycenter closure is affine subspace).**

Let $d \ge 1$. Let $n \in \mathbb{N}$. Let $[\mathbf{v}]^{n,d}$ be $n+1$ points in $\mathbb{R}^d$. Let $\mathcal{F} \stackrel{\text{def.}}{=} \mathbf{v}_0 + \text{span}(\mathbf{v}_j - \mathbf{v}_0)_{j \in [1..n]}$. Then, $\mathcal{F}$ is an affine subspace of $\mathbb{R}^d$, and we have

$$ (5.19) \quad \forall i \in [0..n], \quad \mathcal{F} = \mathbf{v}_i + \text{span}(\mathbf{v}_j - \mathbf{v}_i)_{j \in [0..n] \setminus \{i\}}, $$

$$ (5.20) \quad \mathcal{F} = \left\{ \sum_{j=0}^{n} \mu_j \mathbf{v}_j \in \mathbb{R}^d \mid (\mu_j)_{j \in [0..n]} \in \mathbb{R} \quad \wedge \quad \sum_{j=0}^{n} \mu_j = 1 \right\}, $$

with the convention that $\text{span}(\emptyset) \stackrel{\text{def.}}{=} \{0\}$, thus $\mathcal{F} = \{\mathbf{v}_0\}$ when $n \stackrel{\text{def.}}{=} 0$.

*Proof. Case $n = 0$. Direct consequence of Definition 1379 (affine subspace, with $E' = \{0\}$), and Lemma 80 (trivial subspaces).*

**Case $n \ge 1$.** From Definition 1379 (affine subspace), $\mathcal{F}$ is an affine subspace.

Let $i \in [0..n]$. Let $\mathcal{F}_i \stackrel{\text{def.}}{=} \mathbf{v}_i + \text{span}(\mathbf{v}_j - \mathbf{v}_i)_{j \in [0..n] \setminus \{i\}}$ and

$$ \mathcal{H} \stackrel{\text{def.}}{=} \left\{ \sum_{j=0}^{n} \mu_j \mathbf{v}_j \in \mathbb{R}^d \mid \forall j \in [0..n], \mu_j \in \mathbb{R} \quad \wedge \quad \sum_{j=0}^{n} \mu_j = 1 \right\}. $$
Then, from Definition 85 (finite dimensional subspace), and ring properties of $\mathbb{R}$, we have

$$
\begin{align*}
\mathbf{x} \in \mathcal{F}_i &\iff \exists (\lambda_j)_{j \in [0..n] \setminus \{i\}} \in \mathbb{R}^n, \quad \mathbf{x} = \mathbf{v}_i + \sum_{j=0, j \neq i}^{n} \lambda_j (\mathbf{v}_j - \mathbf{v}_i) \\
&\iff \exists (\lambda_j)_{j \in [0..n] \setminus \{i\}} \in \mathbb{R}^n, \quad \mathbf{x} = \left( 1 - \sum_{j=0, j \neq i}^{n} \lambda_j \right) \mathbf{v}_i + \sum_{j=0, j \neq i}^{n} \lambda_j \mathbf{v}_j \\
&\iff \exists (\mu_j)_{j \in [0..n]} \in \mathbb{R}^{n+1}, \quad \mathbf{x} = \sum_{j=0}^{n} \mu_j \mathbf{v}_j \in \mathbb{R}^d \quad \wedge \quad \sum_{j=0}^{n} \mu_j = 1 \\
&\iff \mathbf{x} \in \mathcal{H},
\end{align*}
$$

where $\mu_j \stackrel{\text{def.}}{=} \lambda_j$ for all $j \in [0..n] \setminus \{i\}$, and $\mu_i \stackrel{\text{def.}}{=} (1 - \sum_{j=0, j \neq i}^n \lambda_j)$, so that $\sum_{j=0}^n \mu_j = 1$ (from left to right), and $\lambda_j \stackrel{\text{def.}}{=} \mu_j$ for all $j \in [0..n] \setminus \{i\}$ (from right to left).
Therefore, we have the two equalities. $\square$

### 5.4.2 Affine maps and submaps

**Definition 1388 (affine map).**

Let $E$ and $F$ be vector spaces.

Let $E'$ be a vector subspace of $E$ and $\mathbf{x}_0 \in E$. Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$. A function $f : \mathcal{E}' \to F$ is said to be an *affine map* iff there exists $\phi \in \mathcal{L}(E', F)$ and $\mathbf{c} \in F$ such that

$$ (5.21) \qquad \forall \mathbf{u}' \in E', \quad f(\mathbf{x}_0 + \mathbf{u}') = \mathbf{c} + \phi(\mathbf{u}'), $$

also denoted $f = \mathbf{c} + \phi$ with origin $\mathbf{x}_0$ (and we may omit the origin when there is no ambiguity).

*Remark 1389.* For instance, note that a function $f : E \to F$ (i.e. with $\mathcal{E}' \stackrel{\text{def.}}{=} E'$ $\stackrel{\text{def.}}{=} E$, and origin $\mathbf{0}$) is an *affine mapping* iff there exists $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$ such that $f = \mathbf{c} + \phi$, i.e. for all vector $\mathbf{u} \in E$, $f(\mathbf{0} + \mathbf{u}) = \mathbf{c} + \phi(\mathbf{u})$, or equivalently, for all point $\mathbf{x} \in E$, $f(\mathbf{x}) = \mathbf{c} + \phi(\mathbf{x} - \mathbf{0})$.

**Lemma 1390 (equivalent definition of affine map).**

Let $E$ and $F$ be vector spaces.

Let $E'$ be a vector subspace of $E$ and $\mathbf{x}_0 \in E$. Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$. Let $f : \mathcal{E}' \to F$.

Then, $f$ is an *affine map* iff there exists $\phi \in \mathcal{L}(E', F)$ and $\mathbf{c} \in F$ such that

$$ (5.22) \qquad \forall \mathbf{x}' \in \mathcal{E}', \quad f(\mathbf{x}') = \mathbf{c} + \phi(\mathbf{x}' - \mathbf{x}_0). $$

*Proof.* Direct consequence of Definition 1388 (affine map), Definition 1379 (affine subspace), and Lemma 1381 (equivalent definition of affine subspace, (5.17), thus $\mathbf{x}' - \mathbf{x}_0 \in E'$). $\square$

**Lemma 1391 (change of origin in affine map).**

Let $E$ and $F$ be vector spaces.

Let $E'$ be a vector subspace of $E$ and $\mathbf{x}_0 \in E$. Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$. Let $\phi \in \mathcal{L}(E', F)$ and $\mathbf{c} \in F$.

Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi$ be an *affine map* (with origin $\mathbf{x}_0$). Let $\mathbf{y}'_0 \in \mathcal{E}'$. Then, we have

$$ (5.23) \qquad \forall \mathbf{u}' \in E', \quad f(\mathbf{y}'_0 + \mathbf{u}') = (\mathbf{c} + \phi(\mathbf{y}'_0 - \mathbf{x}_0)) + \phi(\mathbf{u}'). $$

Thus, setting $\mathbf{c}' \stackrel{\text{def.}}{=} \mathbf{c} + \phi(\mathbf{y}'_0 - \mathbf{x}_0)$, we have $f = \mathbf{c}' + \phi$ with origin $\mathbf{y}'_0$.

*Proof.* Direct consequence of Definition 1388 (affine map), Definition 1379 (affine subspace), Lemma 1381 (equivalent definition of affine subspace, (5.17), thus $\mathbf{y}'_0 - \mathbf{x}_0 \in E'$), Lemma 81 (closed under vector operations is subspace, thus $\mathbf{y}'_0 - \mathbf{x}_0 + \mathbf{u}' \in E'$), Lemma 95 (linear map preserves linear combinations), and Definition 61 (vector space, additive abelian group properties). $\square$
**Remark 1392.** One can thus change the origin of an affine mapping defined over $E$. Indeed, let an affine mapping $f: E \to F$ (i.e. with $\mathcal{E}' \stackrel{\text{def.}}{=} \mathcal{E}' \stackrel{\text{def.}}{=} E$, and origin $0$) such that $f = c + \phi$. Thus, we have for all point $\mathbf{x}_0 \in E$ and for all vector $\mathbf{u} \in E$, $f(\mathbf{x}_0 + \mathbf{u}) = (c + \phi(\mathbf{x}_0 - \mathbf{0})) + \phi(\mathbf{u})$.

**Lemma 1393 (range of affine map is affine subspace).**

Let $E$ and $F$ be vector spaces. Let $E'$ be a vector subspace of $E$ and $\mathbf{x}_0 \in E$. Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$.
Let $\phi \in \mathcal{L}(E', F)$ and $c \in F$. Let $f \stackrel{\text{def.}}{=} c + \phi : \mathcal{E}' \to F$ be an affine map.
Then, $f(\mathcal{E}') = c + \phi(E')$ is an affine subspace of $F$.

*Proof.* Direct consequence of Definition 1388 (affine map), Lemma 1373 (range of linear map is vector subspace), and Definition 1379 (affine subspace). $\square$

**Remark 1394.** Thus, affine maps can be considered as functions from an affine subspace $\mathcal{E}'$ of $E$ to another affine subspace $\mathcal{F}'$ of $F$.

**Definition 1395 (set of affine maps).**

Let $E$ and $F$ be vector spaces. Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$).
Let $\mathcal{E}'$ (resp. $\mathcal{F}'$) be an affine subspace of $E$ (resp. $F$) of direction $E'$ (resp. $F'$).
The set of affine maps from $\mathcal{E}'$ to $\mathcal{F}'$ is $\mathcal{A}\mathcal{F}(\mathcal{E}', \mathcal{F}') \stackrel{\text{def.}}{=} \{f : \mathcal{E}' \to \mathcal{F}' \mid f \text{ is affine map}\}$.

**Lemma 1396 (space of affine maps).**

Let $E$ and $F$ be vector spaces. Then, $\mathcal{A}\mathcal{F}(E, F)$ is a vector subspace of $F^E$.

*Proof.* Direct consequence of Definition 1395 (set of affine maps, with $\mathcal{E}' \stackrel{\text{def.}}{=} \mathcal{E}' \stackrel{\text{def.}}{=} E$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathcal{F}' \stackrel{\text{def.}}{=} F$), Lemma 93 (space of functions to space, $\mathcal{A}\mathcal{F}(E, F) \subset F^E$), Lemma 82 (closed under linear combination is subspace, $\lambda f + \lambda' f' = (\lambda \mathbf{c}_0 + \lambda' \mathbf{c}'_0) + (\lambda \phi + \lambda' \phi')$), and Lemma 96 (space of linear maps). $\square$

**Lemma 1397 (output restriction of affine map).**

Let $E$ and $F$ be vector spaces.

Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$). Let $\mathbf{x}_0 \in E$ and $\mathbf{y}_0 \in F$.

Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{y}_0 + F'$. Let $\phi \in \mathcal{L}(E', F)$ and $c \in F$. Let $f \stackrel{\text{def.}}{=} c + \phi \in \mathcal{A}\mathcal{F}(\mathcal{E}', F)$.
Assume that $\phi(E') \subset F'$ and $c \in \mathcal{F}'$. Then, we have $f(\mathcal{E}') \subset \mathcal{F}'$ and $f \in \mathcal{A}\mathcal{F}(\mathcal{E}', \mathcal{F}')$.

*Proof.* Direct consequence of Lemma 1393 (range of affine map is affine subspace), Lemma 1382 (affine subspace is invariant by change of origin, thus $f(\mathcal{E}') = c + \phi(E') \subset c + F' = \mathcal{F}'$), and Definition 1395 (set of affine maps). $\square$

**Lemma 1398 (affine submap).**

Let $E$ and $F$ be vector spaces.

Let $\phi \in \mathcal{L}(E, F)$ and $c \in F$. Let $f \stackrel{\text{def.}}{=} c + \phi \in \mathcal{A}\mathcal{F}(E, F)$ with origin $0$.

Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$). Let $\mathbf{x}_0 \in E$ and $\mathbf{y}_0 \in F$. Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{y}_0 + F'$. Let $\phi' \stackrel{\text{def.}}{=} \phi|_{E'}$ and $f' \stackrel{\text{def.}}{=} f|_{\mathcal{E}'}$. Let $\mathbf{c}' \stackrel{\text{def.}}{=} c + \phi(\mathbf{x}_0 - \mathbf{0}) \in F$.
Then, we have $f' = \mathbf{c}' + \phi'$ with origin $\mathbf{x}_0$, and $f' \in \mathcal{A}\mathcal{F}(\mathcal{E}', F)$.

Moreover, if $\phi'(E') \subset F'$ and $c' \in \mathcal{F}'$, then we have $f' \in \mathcal{A}\mathcal{F}(\mathcal{E}', \mathcal{F}')$, and $f'$ is called the affine submap of $f$ on $\mathcal{E}'$.

*Proof.* $f' = c' + \phi' \in \mathcal{A}\mathcal{F}(\mathcal{E}', F)$. Let $u' \in E'$. Then, from Definition 1379 (affine subspace, thus $\mathbf{x}_0 + \mathbf{u}' \in \mathcal{E}'$), Definition 1388 (affine map, with $\mathcal{E}' \stackrel{\text{def.}}{=} \mathcal{E}' \stackrel{\text{def.}}{=} E$ and origin $0$), and Lemma 1391 (change of origin in affine map, for $f$, with $\mathbf{x}_0 \stackrel{\text{def.}}{=} \mathbf{0}$ and $\mathbf{y}'_0 \stackrel{\text{def.}}{=} \mathbf{x}_0$), we have

$$f'(\mathbf{x}_0 + \mathbf{u}') = f(\mathbf{x}_0 + \mathbf{u}') = (c + \phi(\mathbf{x}_0 - \mathbf{0})) + \phi(\mathbf{u}') = c' + \phi'(\mathbf{u}')$$
Then, from **restriction to subspace preserves linearity** (thus $\phi'$ belongs to $\mathcal{L}(E', F)$),
Definition 1388 (affine map, with $f'$, $\phi'$, $c'$, $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$), and Definition 1395 (set of affine maps, with $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{F}' \stackrel{\text{def.}}{=} \mathbf{F}$), we have $f' = c' + \phi'$ (with origin $\mathbf{x}_0$) and $f' \in \mathcal{A}ff(\mathcal{E}', \mathbf{F})$.
$f' \in \mathcal{A}ff(\mathcal{E}', \mathcal{F}')$.

Direct consequence of Lemma 1397 (output restriction of affine map, with $f'$, $\phi'$ and $c'$). $\square$

**Lemma 1399 (equivalent definition of affine map (finite dimension)).**

Let $p, q \ge 1$. Let $f : \mathbb{R}^p \to \mathbb{R}^q$. Then, we have

$$ (5.24) \qquad f \in \mathcal{A}ff(\mathbb{R}^p, \mathbb{R}^q) \iff \exists A \in \mathcal{M}_{q,p}, \exists \mathbf{c} \in \mathbb{R}^q, \forall \mathbf{x} \in \mathbb{R}^p, f(\mathbf{x}) = \mathbf{c} + A\mathbf{x}. $$

*Proof.* Direct consequence of Definition 1388 (affine map, with $\mathcal{E}' \stackrel{\text{def.}}{=} \mathcal{E}' \stackrel{\text{def.}}{=} \mathbb{R}^p$, $F \stackrel{\text{def.}}{=} \mathbb{R}^q$, $\mathbf{x}_0 \stackrel{\text{def.}}{=} \mathbf{0}$, and $\phi \stackrel{\text{def.}}{=} (\mathbf{u} \mapsto A\mathbf{u})$), and **the definition of matrix-vector product**. $\square$

**Lemma 1400 (affine map preserves barycenter).** Let $E$ and $F$ be real vector spaces.

Let $f \in \mathcal{A}ff(E, F)$. Let $n \in \mathbb{N}$. Let $[[\mathbf{v}]]^n$ be $n+1$ points in $E$. Let $(\mu_i)_{i \in [0..n]} \in \mathbb{R}$. Then, we have

$$ (5.25) \qquad \sum_{i=0}^{n} \mu_j = 1 \quad \Longrightarrow \quad f\left(\sum_{i=0}^{n} \mu_j \mathbf{v}_j\right) = \sum_{i=0}^{n} \mu_j f(\mathbf{v}_j). $$

*Proof.* Assume that $\sum_{i=0}^n \mu_j = 1$. Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Then, from Definition 1388 (affine map), Lemma 95 (linear map preserves linear combinations), and Definition 61 (vector space, $(F, +)$ is an abelian group, distributivity), we have

$$ \begin{aligned} f\left(\sum_{i=0}^{n} \mu_j \mathbf{v}_j\right) &= \mathbf{c} + \phi\left(\sum_{i=0}^{n} \mu_j \mathbf{v}_j\right) = \left(\sum_{i=0}^{n} \mu_j\right) \mathbf{c} + \sum_{i=0}^{n} \mu_j \phi(\mathbf{v}_j) \\ &= \sum_{i=0}^{n} \mu_j (\mathbf{c} + \phi(\mathbf{v}_j)) = \sum_{i=0}^{n} \mu_j f(\mathbf{v}_j). \end{aligned} $$

$\square$

**Definition 1401 (isobarycenter).** Let $E$ be a real vector space. Let $n \in \mathbb{N}$.

Let $[[\mathbf{v}]]^n$ be $n+1$ points in $E$. The isobarycenter of $[[\mathbf{v}]]^n$ is denoted $\mathbf{g}[[\mathbf{v}]]^n$, and is defined by

$$ (5.26) \qquad \mathbf{g}[[\mathbf{v}]^n] \stackrel{\text{def.}}{=} \frac{1}{n+1} \sum_{i=0}^{n} \mathbf{v}_i. $$

**Lemma 1402 (affine map preserves isobarycenter).** Let $E$ and $F$ be real vector spaces.

Let $f \in \mathcal{A}ff(E, F)$. Let $n \in \mathbb{N}$. Let $[[\mathbf{v}]]^n$ be $n+1$ points in $E$. Let $[[f(\mathbf{v})]]^n \stackrel{\text{def.}}{=} (f(\mathbf{v}_i))_{i \in [0..n]} \in F$. Then, we have $f(\mathbf{g}[[\mathbf{v}]^n]) = \mathbf{g}[[f(\mathbf{v})]]^n$.

*Proof.* Direct consequence of Definition 1401 (isobarycenter), Definition 61 (vector space, properties of linear operations), **field properties of $\mathbb{R}$ (with $n+1 > 0$, thus $\sum_{i=0}^n \frac{1}{n+1} = 1$), and**

Lemma 1400 (affine map preserves barycenter, with $\mu_i \stackrel{\text{def.}}{=} \frac{1}{n+1}$). $\square$

**Lemma 1403 (affine maps are closed by composition).**

Let $E, F$, and $G$ be vector spaces. Let $\phi \in \mathcal{L}(E, F)$, $\mathbf{c} \in F$, $\psi \in \mathcal{L}(F, G)$ and $\mathbf{d} \in G$.

Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}ff(E, F)$ and $g \stackrel{\text{def.}}{=} \mathbf{d} + \psi \in \mathcal{A}ff(F, G)$, both with origin $\mathbf{0}$.

Then, we have

$$ (5.27) \qquad g \circ f = \mathbf{d} + \psi(\mathbf{c} - \mathbf{0}) + \psi \circ \phi \text{ with origin } \mathbf{0} \quad \wedge \quad g \circ f \in \mathcal{A}ff(E, G). $$
**Proof.** Direct consequence of **the definition of composition of functions**, Definition 1388 (affine map, with $f$ and $\mathbf{x}_0 \stackrel{\text{def.}}{=} \mathbf{0}$), Lemma 1390 (equivalent definition of affine map, with $g$, $\mathbf{x}_0 \stackrel{\text{def.}}{=} \mathbf{0}$ and $\mathbf{x}' \stackrel{\text{def.}}{=} (\mathbf{c}' - \mathbf{0}) + \phi(\mathbf{u})$ for any $\mathbf{u} \in E$), Definition 61 (vector space, properties of linear operations), Definition 64 (linear map), Lemma 99 (composition of linear maps is bilinear, thus $\psi \circ \phi \in \mathcal{L}(E, G)$), and Definition 1395 (set of affine maps). $\square$

**Lemma 1404 (continuous affine map is continuous linear map).**

Let $(E, \|\cdot\|_E)$ and $(F, \|\cdot\|_F)$ be normed vector spaces. Let $\phi \in \mathcal{L}(E, F)$, $\mathbf{x}_0 \in E$ and $\mathbf{c} \in F$.

Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}ff(E, F)$ with origin $\mathbf{x}_0$. Then, $f$ is continuous iff $\phi \in \mathcal{L}_c(E, F)$.
Moreover, in this case, $f$ is $\|\phi\|_{F,E}$-Lipchitz continuous.

**Proof.** Direct consequence of Lemma 1390 (equivalent definition of affine map), Definition 61 (vector space, properties of linear operations, thus $f(\mathbf{x}') - f(\mathbf{x}) = \phi(\mathbf{x}' - \mathbf{x}_0) - \phi(\mathbf{x} - \mathbf{x}_0)$, and $\mathbf{x} - \mathbf{x}_0 = \mathbf{x} - \mathbf{0} - (\mathbf{x}_0 - \mathbf{0})$), Definition 64 (linear map, thus $f(\mathbf{x}') - f(\mathbf{x}) = \phi(\mathbf{x}' - \mathbf{0}) - \phi(\mathbf{x} - \mathbf{0})$), Definition 44 (pointwise continuity), Definition 43 (continuity in a point), Theorem 145 (continuous linear map), and Theorem 150 (normalized vector space of continuous linear maps). $\square$

**Lemma 1405 (injective affine submap is zero linear kernel).**

Let $E$ and $F$ be vector spaces. Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}ff(E, F)$ with origin $\mathbf{0}$. Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$). Let $\mathbf{x}_0 \in E$ and $\mathbf{y}_0 \in F$.

Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{y}_0 + F'$. Let $\phi' \stackrel{\text{def.}}{=} \phi|_{E'}$ and $f' \stackrel{\text{def.}}{=} f|_{\mathcal{E}'}$. Let $\mathbf{c}' \stackrel{\text{def.}}{=} \mathbf{c} + \phi(\mathbf{x}_0 - \mathbf{0}) \in F$.
Let $f' = \mathbf{c}' + \phi'$ with origin $\mathbf{x}_0$ be the affine submap of $f$ on $\mathcal{E}'$.

Then, $f'$ is injective iff $\ker(\phi') = \{\mathbf{0}\}$.

**Proof.** Direct consequence of Lemma 1398 (affine submap), Definition 61 (vector space, properties of linear operations, thus $f'(\mathbf{x}_0 + \mathbf{v}') - f'(\mathbf{x}_0 + \mathbf{u}') = \phi'(\mathbf{v}') - \phi'(\mathbf{u}')$), Definition 64 (linear map, thus $\phi'(\mathbf{v}') - \phi'(\mathbf{u}') = \phi'(\mathbf{v}' - \mathbf{u}')$), **the definition of injectivity**, and Lemma 103 (injective linear map has zero kernel). $\square$

**Lemma 1406 (injective affine map is zero linear kernel).** Let $E$ and $F$ be vector spaces.

Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}ff(E, F)$ with origin $\mathbf{0}$.

Then, $f$ is injective iff $\ker(\phi) = \{\mathbf{0}\}$.

**Proof.** Direct consequence of Lemma 1405 (injective affine submap is zero linear kernel, with $\mathcal{E}' \stackrel{\text{def.}}{=} E'$, $\mathcal{F}' \stackrel{\text{def.}}{=} F'$, $\stackrel{\text{def.}}{=} F$ and $\mathbf{x}_0 = \mathbf{y}_0 \stackrel{\text{def.}}{=} \mathbf{0}$, thus $\phi' = \phi$, $f' = f$ and $\mathbf{c}' = \mathbf{c}$). $\square$

**Lemma 1407 (surjective affine submap is full linear range).**

Let $E$ and $F$ be vector spaces. Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}ff(E, F)$ with origin $\mathbf{0}$. Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$). Let $\mathbf{x}_0 \in E$ and $\mathbf{y}_0 \in F$.

Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{y}_0 + F'$. Let $\phi' \stackrel{\text{def.}}{=} \phi|_{E'}$ and $f' \stackrel{\text{def.}}{=} f|_{\mathcal{E}'}$. Let $\mathbf{c}' \stackrel{\text{def.}}{=} \mathbf{c} + \phi(\mathbf{x}_0 - \mathbf{0}) \in F$.
Assume that $\phi'(E') \subset F'$ and $\mathbf{c}' \in \mathcal{F}'$.

Let $f' = \mathbf{c}' + \phi'$ with origin $\mathbf{x}_0$ be the affine submap of $f$ on $\mathcal{E}'$.

Then, $f'$ is surjective iff $\phi'(E') = F'$.

**Proof.** **From left to right.** Assume that $f'$ is surjective onto $\mathcal{F}'$.

Let $\mathbf{v}' \in F'$. Then, from Definition 1379 (affine subspace, with $\mathcal{F}'$), and Lemma 1382 (affine subspace is invariant by change of origin, with $\mathbf{y}' \stackrel{\text{def.}}{=} \mathbf{c}' \in \mathbf{y}_0 + F'$), we have $\mathbf{c}' + \mathbf{v}' \in \mathbf{c}' + F' = \mathcal{F}'$.
Thus, from **the definition of surjectivity**, Lemma 1390 (equivalent definition of affine map), Lemma 82 (closed under linear combination is subspace), and Lemma 1381 (equivalent definition of affine subspace, (5.17)), there exists $\mathbf{x}' \in \mathcal{E}'$ such that $f'(\mathbf{x}') = \mathbf{c}' + \mathbf{v}'$, and $\phi'(\mathbf{x}' - \mathbf{x}_0) = f'(\mathbf{x}') - \mathbf{c}' = \mathbf{v}'$ with $\mathbf{x}' - \mathbf{x}_0 \in E'$.

Therefore, we have $F' \subset \phi'(E')$, and thus $\phi'(E') = F'$.
**From right to left.** Assume that $\phi'(E') = F'$. Let $\mathbf{y}' \in \mathcal{F}'$. Then, from Definition 61 (vector space, properties of linear operations), Lemma 1381 (equivalent definition of affine subspace, (5.17) with $\mathbf{y}'$ and $\mathbf{c}'$), Lemma 82 (closed under linear combination is subspace), and Definition 1388 (affine map), and Definition 1379 (affine subspace, with $\mathcal{E}'$), we have $\mathbf{y}' - \mathbf{c}' = (\mathbf{y}' - \mathbf{y}_0) - (\mathbf{c}' - \mathbf{y}_0) \in F'$, thus there exists $\mathbf{u}' \in E'$ such that $\phi'(\mathbf{u}') = \mathbf{y}' - \mathbf{c}'$, and $f'(\mathbf{x}_0 + \mathbf{u}') = \mathbf{c}' + \phi'(\mathbf{u}') = \mathbf{y}'$ with $\mathbf{x}_0 + \mathbf{u}' \in \mathcal{E}'$.
Therefore, from **the definition of surjectivity**, $f'$ is surjective. $\square$

**Lemma 1408 (surjective affine map is full linear range).** Let $E$ and $F$ be vector spaces.
Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}\mathit{ff}(E, F)$ with origin $\mathbf{0}$.
Then, $f$ is surjective iff $\phi(E) = F$.

*Proof.* Direct consequence of Lemma 1407 (surjective affine submap is full linear range, with $\mathcal{E}' \stackrel{\text{def.}}{=} E' \stackrel{\text{def.}}{=} E$, $\mathcal{F}' \stackrel{\text{def.}}{=} F' \stackrel{\text{def.}}{=} F$ and $\mathbf{x}_0 = \mathbf{y}_0 \stackrel{\text{def.}}{=} \mathbf{0}$, thus $\phi' = \phi$, $f' = f$, and $\mathbf{c}' = \mathbf{c} \in F$, and $\phi(E) \subset F$). $\square$

**Lemma 1409 (inverse of affine submap is affine submap).**
Let $E$ and $F$ be vector spaces. Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}\mathit{ff}(E, F)$ with origin $\mathbf{0}$. Let $E'$ (resp. $F'$) be a vector subspace of $E$ (resp. $F$). Let $\mathbf{x}_0 \in E$ and $\mathbf{y}_0 \in F$.
Let $\mathcal{E}' \stackrel{\text{def.}}{=} \mathbf{x}_0 + E'$ and $\mathcal{F}' \stackrel{\text{def.}}{=} \mathbf{y}_0 + F'$. Let $\phi' \stackrel{\text{def.}}{=} \phi|_{E'}$ and $f' \stackrel{\text{def.}}{=} f|_{\mathcal{E}'}$. Let $\mathbf{c}' \stackrel{\text{def.}}{=} \mathbf{c} + \phi(\mathbf{x}_0 - \mathbf{0}) \in F$.
Assume that $\phi'(E') \subset F'$ and $\mathbf{c}' \in \mathcal{F}'$.
Let $f' = \mathbf{c}' + \phi'$ with origin $\mathbf{x}_0$ be the affine submap of $f$ on $\mathcal{E}'$.

Then, $f'$ is bijective in $\mathcal{A}\mathit{ff}(\mathcal{E}', \mathcal{F}')$ iff $\phi'$ is an isomorphism in $\mathcal{L}(E', F')$.

Moreover, in this case, we have $(f')^{-1} \in \mathcal{A}\mathit{ff}(\mathcal{F}', \mathcal{E}')$, and with $\mathbf{x}'_0 \stackrel{\text{def.}}{=} \mathbf{x}_0 + (\phi')^{-1}(\mathbf{y}_0 - \mathbf{c}') \in \mathcal{E}'$,

$$ (5.28) \qquad \forall \mathbf{y}' \in \mathcal{F}', \quad (f')^{-1}(\mathbf{y}') = \mathbf{x}_0 + (\phi')^{-1}(\mathbf{y}' - \mathbf{c}') = \mathbf{x}'_0 + (\phi')^{-1}(\mathbf{y}' - \mathbf{y}_0), $$

$$ (5.29) \qquad \forall \mathbf{v}' \in F', \quad (\phi')^{-1}(\mathbf{v}') = (f')^{-1}(\mathbf{c}' + \mathbf{v}') - \mathbf{x}_0. $$

*Proof.* **Equivalence.** Direct consequence of **the definition of bijectivity**, Lemma 1405 (injective affine submap is zero linear kernel), Lemma 1407 (surjective affine submap is full linear range), Lemma 103 (injective linear map has zero kernel), **the characterization of surjectivity with full range**, and Definition 100 (isomorphism).

(5.28) and $(f')^{-1} \in \mathcal{A}\mathit{ff}(\mathcal{F}', \mathcal{E}')$. Let $\mathbf{y}' \in \mathcal{F}'$. Let $\mathbf{x}' \stackrel{\text{def.}}{=} (f')^{-1}(\mathbf{y}') \in \mathcal{E}'$. Then, from **the definition of the inverse**, Lemma 1390 (equivalent definition of affine map), Lemma 1381 (equivalent definition of affine subspace, thus $\mathbf{c}' - \mathbf{y}_0, \mathbf{y}' - \mathbf{y}_0 \in F'$), Lemma 81 (closed under vector operations is subspace, thus $\mathbf{y}_0 - \mathbf{c}' = -(\mathbf{c}' - \mathbf{y}_0) \in F'$ and $\mathbf{y}' - \mathbf{c}' = (\mathbf{y}_0 - \mathbf{c}') + (\mathbf{y}' - \mathbf{y}_0) \in F'$), Definition 1379 (affine subspace, with $(\phi')^{-1}(\mathbf{y}_0 - \mathbf{c}') \in E'$, thus $\mathbf{x}'_0 \in \mathcal{E}'$), Definition 61 (vector space, additive abelian group properties for $E'$ and $F'$), Lemma 1375 (inverse of isomorphism is linear map), and Definition 1388 (affine map), we have successively $\mathbf{y}' = f'(\mathbf{x}') = \mathbf{c}' + \phi'(\mathbf{x}' - \mathbf{x}_0)$, $\phi'(\mathbf{x}' - \mathbf{x}_0) = \mathbf{y}' - \mathbf{c}' = (\mathbf{y}_0 - \mathbf{c}') + (\mathbf{y}' - \mathbf{y}_0)$, and thus

$$ (f')^{-1}(\mathbf{y}') = \mathbf{x}' = \mathbf{x}_0 + (\phi')^{-1}(\mathbf{y}' - \mathbf{c}') = \mathbf{x}'_0 + (\phi')^{-1}(\mathbf{y}' - \mathbf{y}_0) \quad \text{and} \quad (f')^{-1} \in \mathcal{A}\mathit{ff}(\mathcal{F}', \mathcal{E}') $$

(5.29). Direct consequence of (5.28), and Lemma 82 (closed under linear combination is subspace, for both $E$ and $F$). $\square$

**Lemma 1410 (inverse of affine map is affine map).** Let $E$ and $F$ be vector spaces.
Let $\phi \in \mathcal{L}(E, F)$ and $\mathbf{c} \in F$. Let $f \stackrel{\text{def.}}{=} \mathbf{c} + \phi \in \mathcal{A}\mathit{ff}(E, F)$ with origin $\mathbf{0}$.
Then, $f$ is bijective iff $\phi$ is an isomorphism.

Moreover, in this case, we have $f^{-1} \in \mathcal{A}\mathit{ff}(F, E)$, and with $\mathbf{x}'_0 \stackrel{\text{def.}}{=} \mathbf{0} + \phi^{-1}(\mathbf{0} - \mathbf{c}) \in E$,

$$ (5.30) \qquad \forall \mathbf{y} \in F, \quad f^{-1}(\mathbf{y}) = \mathbf{0} + \phi^{-1}(\mathbf{y} - \mathbf{c}) = \mathbf{x}'_0 + \phi^{-1}(\mathbf{y} - \mathbf{0}), $$

$$ (5.31) \qquad \forall \mathbf{v} \in F, \quad \phi^{-1}(\mathbf{v}) = f^{-1}(\mathbf{c} + \mathbf{v}) - \mathbf{0}. $$
*Proof.* Direct consequence of Lemma 1409 (inverse of affine submap is affine submap, with $\mathcal{E}' \stackrel{\text{def.}}{=} \mathcal{E}' \stackrel{\text{def.}}{=} E$, $\mathcal{F}' \stackrel{\text{def.}}{=} \mathcal{F}' \stackrel{\text{def.}}{=} F$ and $\mathbf{x}_0 = \mathbf{y}_0 \stackrel{\text{def.}}{=} \mathbf{0}$, thus $\phi' = \phi$, $f' = f$, and $\mathbf{c}' = \mathbf{c} \in F$, and $\phi(E) \subset F$). □

## 5.5 Complements on real affine geometry

**Definition 1411 (affinely independent family).**

Let $d \ge 1$. Let $n \in \mathbb{N}$. Let $[[\mathbf{v}]]^{n,d}$ be $n+1$ points in $\mathbb{R}^d$.

Then, $[[\mathbf{v}]]^{n,d}$ is said *affinely independent* iff $(\mathbf{v}_1 - \mathbf{v}_0, \dots, \mathbf{v}_n - \mathbf{v}_0)$ is free in the vector space $\mathbb{R}^d$.

**Lemma 1412 (equivalent definition of affinely independent family).**

Let $d \ge 1$. Let $n \in \mathbb{N}$. Let $[[\mathbf{v}]]^{n,d}$ be $n+1$ points in $\mathbb{R}^d$. Let $j \in [0..n]$.

Then, $[[\mathbf{v}]]^{n,d}$ is affinely independent iff $(\mathbf{v}_i - \mathbf{v}_j)_{i \in [0..n] \setminus \{j\}}$ is free in the vector space $\mathbb{R}^d$.

*Proof.* Case $n = 0$. Direct consequence of Definition 1411 (affinely independent family), and **the definition of freedom (the empty family in any vector space is free)**.

**Case j = 0.** Direct consequence of Definition 1411 (affinely independent family).

**Case n ≥ 1 and j ≠ 0. (1).** Let $k, l \in [0..n]$, such that $k \ne l$. Let $(\mu_i)_{i \in [0..n] \setminus \{k\}} \in \mathbb{R}^n$. Then, from Definition 61 (vector space, properties of linear operations), we have

$$ 
\begin{align*}
\sum_{i=0, i \neq k}^{n} \mu_i (\mathbf{v}_i - \mathbf{v}_k) &= \sum_{\substack{j=0 \\ i \neq k, i \neq l}}^{n} \mu_i \mathbf{v}_i - \left( \sum_{i=0, i \neq k}^{n} \mu_i \right) \mathbf{v}_k + \mu_l \mathbf{v}_l \\
&= \sum_{i=0, i \neq l}^{n} \tilde{\mu}_i (\mathbf{v}_i - \mathbf{v}_l) + \left( \mu_l + \sum_{i=0, i \neq l}^{n} \tilde{\mu}_i \right) \mathbf{v}_l \\
&= \sum_{i=0, i \neq l}^{n} \tilde{\mu}_i (\mathbf{v}_i - \mathbf{v}_l) + \left( \tilde{\mu}_k + \sum_{i=0, i \neq k}^{n} \mu_i \right) \mathbf{v}_l \\
&= \sum_{i=0, i \neq l}^{n} \tilde{\mu}_i (\mathbf{v}_i - \mathbf{v}_l),
\end{align*}
$$

where we have set $\tilde{\mu}_k \stackrel{\text{def.}}{=} - \sum_{i=0, i \neq k}^{n} \mu_i$, and $\tilde{\mu}_i \stackrel{\text{def.}}{=} \mu_i$ for $i \in [0..n] \setminus \{k, l\}$.

**(2) ($\mathbf{v}_i - \mathbf{v}_l)_{i \in [0..n] \setminus \{l\}}$ free $\Rightarrow (\mathbf{v}_i - \mathbf{v}_k)_{i \in [0..n] \setminus \{k\}}$ free.**

Let $k, l \in [0..n]$, such that $k \ne l$. Assume that $(\mathbf{v}_i - \mathbf{v}_l)_{i \in [0..n] \setminus \{l\}}$ is free.

Let $(\mu_i)_{i \in [0..n] \setminus \{k\}} \in \mathbb{R}^n$, such that $\sum_{i=0, i \neq k}^{n} \mu_i (\mathbf{v}_i - \mathbf{v}_k) = 0$. Then, from (1), and **the definition of freedom**, we have $\sum_{i=0, i \neq l}^{n} \tilde{\mu}_i (\mathbf{v}_i - \mathbf{v}_l) = 0$, and

$$ \forall i \in [0..n] \setminus \{k, l\}, \quad \tilde{\mu}_i = \mu_i = 0, \quad \text{and} \quad \tilde{\mu}_k = - \sum_{i=0, i \neq k}^{n} \mu_i = -\mu_l = 0. $$

Thus, for all $i \in [0..n] \setminus \{k\}$, $\mu_i = 0$, and the family $(\mathbf{v}_i - \mathbf{v}_k)_{i \in [0..n] \setminus \{k\}}$ is free.

**(3).** The equivalence is a direct consequence of (2), first with $k \stackrel{\text{def.}}{=} j$ and $l \stackrel{\text{def.}}{=} 0$ (from left to right), then with $k \stackrel{\text{def.}}{=} 0$ and $l \stackrel{\text{def.}}{=} j$ (from right to left). □

**Lemma 1413 (affinely independent family of 2 elements).**

Let $d \ge 1$.

Let $[[\mathbf{v}]]^{1,d} \stackrel{\text{def.}}{=} (\mathbf{v}_0, \mathbf{v}_1)$ be 2 points in $\mathbb{R}^d$. Then, $[[\mathbf{v}]]^{1,d}$ is affinely independent iff $\mathbf{v}_0 \neq \mathbf{v}_1$.

*Proof.* Direct consequence of Definition 1411 (affinely independent family), and **a free vector is nonzero**. □
**Lemma 1414 (affinely independent family is closed by sub-family).**

Let $d \ge 1$. Let $n \in \mathbb{N}$. Let $\|\mathbf{v}\|^{n,d}$ be $n+1$ affinely independent points in $\mathbb{R}^d$.

Let $l \in [0..n]$, and let $\pi^l$ be an injective map from $[0..l]$ into $[0..n]$. Let $j \in [0..l]$.

Then, $(\mathbf{v}_{\pi^l(i)} - \mathbf{v}_{\pi^l(j)})_{i \in [0..l] \setminus \{j\}}$ is free in the vector space $\mathbb{R}^d$.

In other terms, the family $\|\mathbf{v}_{\pi^l}\|^{l,d} \stackrel{\text{def.}}{=} (\mathbf{v}_{\pi^l(i)})_{i \in [0..l]}$ is affinely independent in $\mathbb{R}^d$.

*Proof.* Let $(\mu_i)_{i \in [0..l] \setminus \{j\}}$ in $\mathbb{R}^l$ such that $\sum_{i \in [0..l] \setminus \{j\}} \mu_i(\mathbf{v}_{\pi^l(i)} - \mathbf{v}_{\pi^l(j)}) = 0$.

Let $I \stackrel{\text{def.}}{=} \pi^l([0..l]) \subset [0..n]$, and $J \stackrel{\text{def.}}{=} [0..n] \setminus I$. Thus, from **the definition of bijectivity**, $\pi^l$ is bijective from $[0..l]$ to $I$, and $[0..n] = I \uplus J$ is a partition. Let $j' \stackrel{\text{def.}}{=} \pi^l(j) \in I$. Thus, we have

$$0 = \sum_{i' \in I \setminus \{j'\}} \mu_{(\pi^l)^{-1}(i')}(\mathbf{v}_{i'} - \mathbf{v}_{j'}) + \sum_{i' \in J} 0(\mathbf{v}_{i'} - \mathbf{v}_{j'}) = \sum_{i' \in [0..n] \setminus \{j'\}} \tilde{\mu}_{i'}(\mathbf{v}_{i'} - \mathbf{v}_{j'}),$$

where we have set $\forall i' \in I \setminus \{j'\}$, $\tilde{\mu}_{i'} \stackrel{\text{def.}}{=} \mu_{(\pi^l)^{-1}(i')}$, and $\forall i' \in J$, $\tilde{\mu}_{i'} \stackrel{\text{def.}}{=} 0$. Thus, from Lemma 1412 (equivalent definition of affinely independent family, with $j \stackrel{\text{def.}}{=} j'$), and **the definition of free-dom**, we deduce that for all $i' \in I \setminus \{j'\}$, $\mu_{(\pi^l)^{-1}(i')} = 0$, and thus for all $i \in [0..l] \setminus \{j\}$, $\mu_i = 0$. Thus, from **the definition of freedom**, and Definition 1411 (affinely independent family), $(\mathbf{v}_{\pi^l(i)} - \mathbf{v}_{\pi^l(j)})_{i \in [0..l] \setminus \{j\}}$ is free, and $\|\mathbf{v}_{\pi^l}\|^{l,d}$ is affinely independent. $\square$

## 5.6 Complements on univariate polynomials

*Remark 1415.* See also Sections 8.2 and 9.2.

**Definition 1416 (monomial of a single variable).** Let $\alpha \in \mathbb{N}$. The monomial of degree $\alpha$ of a single variable is denoted $X^\alpha$, and is defined by $X^\alpha \stackrel{\text{def.}}{=} (x \in \mathbb{R} \mapsto x^\alpha \in \mathbb{R})$.

**Definition 1417 (polynomial space $\mathbb{P}_k^1$).** Let $k \in \mathbb{N}$. The space of polynomials of degree at most $k$ of a single variable is denoted $\mathbb{P}_k^1$, and is defined by

$$(5.32) \qquad \mathbb{P}_k^1 \stackrel{\text{def.}}{=} \operatorname{span} (1, X, X^2, \dots, X^k) = \left\{ \left( x \mapsto \sum_{\alpha=0}^k a_\alpha x^\alpha \right) : \mathbb{R} \to \mathbb{R} \;\middle|\; (a_\alpha)_{\alpha \in [0..k]} \in \mathbb{R} \right\}.$$

**Lemma 1418 ($\mathbb{P}_k^1$ is space of degree at most $k$).** Let $\mathcal{P}(\mathbb{R})$ be the infinite-dimensional space of polynomials of a single variable on $\mathbb{R}$. Let $k \in \mathbb{N}$. Then, we have

$$(5.33) \qquad \mathbb{P}_k^1 = \{p \in \mathcal{P}(\mathbb{R}) \mid \deg p \le k\}.$$

For instance, we have

$$(5.34) \qquad \mathbb{P}_0^1 = \operatorname{span}(1) = \{(x \mapsto a_0) \mid a_0 \in \mathbb{R}\},$$

$$(5.35) \qquad \mathbb{P}_1^1 = \operatorname{span}(1, X) = \{(x \mapsto a_0 + a_1 x) \mid a_0, a_1 \in \mathbb{R}\} = \mathcal{A}\mathcal{F}(\mathbb{R}, \mathbb{R}).$$

*Proof.* Direct consequence of **the definition of the degree a univariate polynomial**, Definition 1417 (polynomial space $\mathbb{P}_k^1$), Definition 1416 (monomial of a single variable), Lemma 1399 (equivalent definition of affine map (finite dimension), with $p = q = 1$), and Lemma 1396 (space of affine maps). $\square$

**Lemma 1419 (monomials are free in $\mathbb{P}_k^1$).** Let $k \in \mathbb{N}$. Then, $(1, X, \dots, X^k)$ is free in $\mathbb{P}_k^1$.

*Proof.* Let $(a_\alpha)_{\alpha \in [0..k]}$ such that for all $x \in \mathbb{R}$, $\sum_{\alpha=0}^k a_\alpha x^\alpha = 0$. Let $l \in [0..k]$. Then, from **the linearity of derivation, the positivity of factorial, the zero-product property in $\mathbb{R}$, and the definition of freedom**, the $l$-th derivative taken in $x = 0$ provides $l! a_l = 0$, thus $a_l = 0$, and the family is free. $\square$
**Lemma 1420 (dimension of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Then, $\mathbb{P}_k^1$ is a vector space of dimension $\dim \mathbb{P}_k^1 = k + 1$.

*Proof.* Direct consequence of Definition 1417 (*polynomial space $\mathbb{P}_k^1$*), Lemma 1419 (*monomials are free in $\mathbb{P}_k^1$*), Lemma 1376 (*free family of dim elements is basis*), and **the definition of the dimension of a vector space.** □

*Remark 1421.* Note in the next lemma that when $p$ or $q$ is 0, then by convention, its degree is $-\infty$ (which is absorbing for addition in $\{-\infty\} \oplus \mathbb{N}$), and the formula $\deg(pq) = -\infty = \deg(p) + \deg(q)$ is still valid.

**Lemma 1422 (product of two univariate polynomials).**

Let $k, l \in \mathbb{N}$. Let $p \in \mathbb{P}_k^1$, and $q \in \mathbb{P}_l^1$. Then, we have $pq \in \mathbb{P}_{k+l}^1$.

Moreover, if $\deg(p) = k$ and $\deg(q) = l$, then $\deg(pq) = k + l$.

*Proof.* From **the definition of univariate polynomial**, let $(a_i)_{i \in [0..k]} \in \mathbb{R}^{k+1}$ and $(b_j)_{j \in [0..l]} \in \mathbb{R}^{l+1}$ such that we have $p = \sum_{i=0}^k a_i X^i$ and $q = \sum_{j=0}^l b_j X^j$. Thus, from **commutative ring properties of $\mathbb{R}$**, and **the fact that $a_j b_{n-j}$ is a priori nonzero iff $0 \le j \le k$ and $0 \le n - j \le l$ (i.e. $n - l \le j \le n$)**, we obtain

$$ (5.36) \qquad pq = \sum_{n=0}^{k+l} \sum_{j=\max\{0, n-l\}}^{\min\{n,k\}} a_j b_{n-j} X^n. $$

Thus, $pq \in \mathbb{P}_{k+l}^1$.

**Degree formula.**

Direct consequence of **the definition of univariate polynomial**, **the zero-product property in $\mathbb{R}$**, and formula (5.36) (coefficients of highest degree, $a_k, b_l$ and $a_k b_l$ are all nonzero). □
# Chapter 6

## Finite element

Remark 1423. The next definition is from from Ciarlet [13], it is taken from [20, pp. 50–52].

**Definition 1424 (finite element triple).** Let $d \ge 1$. Let $n_{\text{sh}} \ge 1$. Let $q \in \{1, d\}$. Let $K \subset \mathbb{R}^d$. Let $P \subset \mathcal{F}(K, \mathbb{R}^q)$. Let $\Sigma \stackrel{\text{def.}}{=} (\sigma_i)_{i \in [1..n_{\text{sh}}]} \in \mathcal{L}(P, \mathbb{R})$. The triple $(K, P, \Sigma)$ is called *finite element* iff

1. $K$ is a nontrivial polyhedron, $\mathring{K} \neq \emptyset$. The polyhedron $K$ represents the *geometry* of the finite element.

2. $P$ is a nontrivial finite-dimensional vector space of functions, $P \neq \{0\}$. The vector space $P$ is called *approximation space* of the finite element.

3. $\Sigma$ is such that $\phi_{\Sigma}: P \to \mathbb{R}^{n_{\text{sh}}}$ defined by $\phi_{\Sigma}(p) \stackrel{\text{def.}}{=} (\sigma_i(p))_{i \in [1..n_{\text{sh}}]}$ is an isomorphism. The linear forms $\sigma_i$ are called *degrees of freedom* of the finite element, $n_{\text{sh}}$ is the *number of degrees of freedom*, and the bijectivity of $\phi_{\Sigma}$ is called *unisolvence*.

Remark 1425. The functions of $P$ are typically polynomial functions, possibly composed with some smooth diffeomorphism. For any finite collection of linear forms $\Sigma$, the mapping $\phi_{\Sigma}$ is obviously linear.

**Lemma 1426 (injectivity implies unisolvence).** Let $d \ge 1$. Let $n_{\text{sh}} \ge 1$. Let $q \in \{1, d\}$. Let $K \subset \mathbb{R}^d$ be a nontrivial polyhedron. Let $P \subset \mathcal{F}(K, \mathbb{R}^q)$ be a nontrivial finite-dimensional vector space. Let $\Sigma \stackrel{\text{def.}}{=} (\sigma_i)_{i \in [1..n_{\text{sh}}]} \in \mathcal{L}(P, \mathbb{R})$ be linear forms on $P$. If $\dim P \ge n_{\text{sh}} = \text{card}(\Sigma)$ and $\phi_{\Sigma}$ is injective, then $(K, P, \Sigma)$ is unisolvent

*Proof*. Direct consequence of Definition 1424 (finite element triple), and Lemma 1374 (injectivity or surjectivity and dimension implies bijectivity). $\square$

**Lemma 1427 (dimension of approximation space).** Let $(K, P, \Sigma)$ be a finite element. Then, we have $\dim P = n_{\text{sh}} = \text{card}(\Sigma)$.

*Proof*. Direct consequence of **the rank–nullity theorem**. $\square$

**Lemma 1428 (degrees of freedom are basis).** Let $(K, P, \Sigma)$ be a finite element. Then, $\Sigma$ is a basis of the dual vector space $\mathcal{L}(P, \mathbb{R})$.

*Proof*. From Lemma 1376 (free family of dim elements is basis), Lemma 1427 (dimension of approximation
space), and the fact that $dim(\mathcal{L}(P, \mathbb{R})) = dim P$, it suffices to show that $\Sigma$ is free.
Let $a \stackrel{\text{def.}}{=} (a_i)_{i \in [1..n_{\text{sh}}]} \in \mathbb{R}$ such that $\sum_{i \in [1..n_{\text{sh}}]} a_i \sigma_i = 0$. Then, with $p \stackrel{\text{def.}}{=} \phi_{\Sigma}^{-1}(a)$, we have

$$ \sum_{i \in [1..n_{\text{sh}}]} a_i \sigma_i(p) = \sum_{i \in [1..n_{\text{sh}}]} a_i^2 = 0, $$

and thus for all $i \in [1..n_{\text{sh}}]$, $a_i = 0$. Therefore, $\Sigma$ is free, and it is a basis of $\mathcal{L}(P, \mathbb{R})$. $\square$

*Remark 1429.* In the next definition, the *predual basis* of a basis $B' = (b'_i)_{i \in [1..n]}$ of $E' \stackrel{\text{def.}}{=} \mathcal{L}(E, \mathbb{K})$, the dual of some vector space $E$ of dimension $n$, is a basis $B = (b_i)_{i \in [1..n]}$ of $E$ such that its dual basis is $B'$. This means that, for all $i, j \in [1..n]$, we have $b'_i(b_j) = \delta_{ij}$.

**Definition 1430 (shape function).**
Let $(K, P, \Sigma)$ be a finite element.
The elements of the predual basis of $\Sigma$ are called *shape functions*.
# Chapter 7

## Simplicial geometry

**Remark 1431.** This is an important example, see [20, Chap 7, pp. 75–86].

In this section, $d \in \mathbb{N}^*$ denotes the dimension and $k \in \mathbb{N}$ the maximal degree of the polynomial approximation. The case $k = 0$ corresponds to constant functions and is often excluded. In the same way, the case $d = 0$ (points) is a limit case that is note considered (at least in a first step).

**Definition 1432 (family of points).** Let $d \ge 1$. Let $\mathcal{B}_d \subset \mathbb{N}^d$ be a finite set.
For all $\beta \in \mathcal{B}_d$, let $\mathbf{a}_\beta \in \mathbb{R}^d$. Then, the whole family is denoted $\{\{\mathbf{a}\}\}_{\mathcal{B}_d}^{\text{def.}} = (\mathbf{a}_\beta)_{\beta \in \mathcal{B}_d}$.

**Remark 1433.** The notation $\{\{\mathbf{a}\}\}_{\mathcal{B}_d}$ is used to collect the nodes (i.e. points where the nodal degrees of freedom are computed through the linear forms $\sigma_\beta$, with $\beta \in \mathcal{B}_d$). They are numbered with multi-indices in $\mathbb{N}^d$.

In contrast, the notation $[[\mathbf{v}]]^d$ defined in Definition 1365 are typically used to collect the vertices of the geometry, with the canonical numbering of $[0..n]$.

**Definition 1434 (family of reference points).** Let $d \ge 1$. The family of reference points (in $\mathbb{R}^d$) is denoted $[[\hat{\mathbf{v}}]]^d$, and is defined by $\hat{\mathbf{v}}_0^{\text{def.}} = \mathbf{0}$ and for all $i \in [1..d]$, $\hat{\mathbf{v}}_i^{\text{def.}} = \mathbf{e}_i$.

**Lemma 1435 (reference isobarycenter).** Let $d \ge 1$.

The reference isobarycenter (in $\mathbb{R}^d$) is denoted by $\hat{\mathbf{g}}^d$ and is defined as the isobarycenter of $[[\hat{\mathbf{v}}]]^d$.

Thus, we have $\hat{\mathbf{g}}^d = \frac{1}{d+1} \sum_{i=0}^{d} \hat{\mathbf{v}}_i = \frac{1}{d+1} \sum_{i=1}^{d} \mathbf{e}_i$, and for all $i \in [1..d]$, $(\hat{\mathbf{g}}^d)_i = \frac{1}{d+1}$.

*Proof.* Direct consequence of Definition 1401 (isobarycenter), and Definition 1434 (family of reference points). $\square$

**Lemma 1436 (family of reference points is affinely independent).**
Let $d \ge 1$. Then, the family of reference points $[[\hat{\mathbf{v}}]]^d$ is affinely independent.

*Proof.* Direct consequence of Definition 1434 (family of reference points) Definition 1365 (canonical families), Definition 1411 (affinely independent family), the canonical family is basis, and basis is free. $\square$

**Definition 1437 (reference simplex).**
Let $d \ge 1$. The reference simplex is denoted $\hat{\mathbf{K}}^d$, and is defined as the unit rectangular simplex in $\mathbb{R}^d$,

$$ (7.1) \qquad \hat{\mathbf{K}}^d \stackrel{\text{def.}}{=} \left\{ \hat{\mathbf{x}} \in \mathbb{R}^d \mid \forall i \in [1..d], \ \hat{x}_i \ge 0 \ \wedge \ \sum_{i=1}^d \hat{x}_i \le 1 \right\}. $$

Its vertices are the reference points $[[\hat{\mathbf{v}}]]^d$.
**Lemma 1438 (coordinates in reference simplex are smaller than 1).**

Let $d \ge 1$. Let $\hat{x} \in \hat{K}^d$. Then, we have for all $i \in [1..d]$, $\hat{x}_i \le 1$.

*Proof.*

By contradiction, assume that there exists $i$ such that $\hat{x}_i > 1$, then from Definition 1437 (reference simplex), and **monotony of addition in $\mathbb{R}_+$**, we have $\sum_{j=1}^d \hat{x}_j \ge \hat{x}_i > 1$, which is impossible. $\square$

**Lemma 1439 (nontrivial reference simplex).** Let $d \ge 1$. Then, $\hat{K}^d$ has nonempty interior.

*Proof.* Let $\mathcal{B} \stackrel{\text{def.}}{=} \mathcal{B}_{\infty}^o((\frac{1}{2d}, \dots, \frac{1}{2d}), \frac{1}{2d})$. Let $\hat{x} \in \mathcal{B}$. Then, from the **definition of the $\infty$-norm, valued field properties of $\mathbb{R}$**, and Definition 1437 (reference simplex), we have $\forall i \in [1..d]$, $|\hat{x}_i - \frac{1}{2d}| < \frac{1}{2d}$, i.e. $0 < \hat{x}_i < \frac{1}{d}$, thus $\hat{x}_i > 0$ and $\sum_{j=0}^d \hat{x}_j < 1$, and $\hat{x} \in \hat{K}^d$. Therefore, from **open ball is open in metric space, open ball with positive radius is nonempty (with $\frac{1}{2d} > 0$)**, and **the definition of the interior, $\mathcal{B} \ne \emptyset$, is open, and included in of $\hat{K}^d$, and thus $\hat{K}^d$ has a nonempty interior.** $\square$

**Definition 1440 (simplex).**

Let $d \ge 1$. Let $[[\mathbf{v}]^d$ be $d+1$ points in $\mathbb{R}^d$.

The simplex of vertices $[[\mathbf{v}]^d$ is denoted $K[[\mathbf{v}]^d$, and is defined as the convex envelop of $[[\mathbf{v}]^d$,

$$ (7.2) \quad K[[\mathbf{v}]^d \stackrel{\text{def.}}{=} \left\{ \mathbf{x} = \sum_{i=0}^{d} \mu_i \mathbf{v}_i \in \mathbb{R}^d \;\middle|\; \forall i \in [0..d], \ \mu_i \ge 0 \ \wedge \ \sum_{i=0}^{d} \mu_i = 1 \right\}. $$

*Remark 1441.* The proof that a simplex $K[[\mathbf{v}]^d$ with affinely independent vertices has nonempty interior is given later, once the geometrical transformation that maps the reference simplex $\hat{K}^d$ to $K[[\mathbf{v}]^d$ is defined, see Lemma 1557.

**Lemma 1442 (coordinates in simplex are smaller than 1).** Let $d \ge 1$. Let $[[\mathbf{v}]^d$ be $d+1$ points in $\mathbb{R}^d$. Let $\mathbf{x} = \sum_{i=0}^d \mu_i \mathbf{v}_i \in K[[\mathbf{v}]^d$. Then, we have for all $i = [0..d]$, $\mu_i \le 1$.

*Proof.* By contradiction, assume that there exists $i$ such that $\mu_i > 1$, then from Definition 1440 (simplex), and **monotony of addition in $\mathbb{R}_+$**, we have $\sum_{i=0}^d \mu_i \ge \mu_i > 1$, which is impossible. $\square$

**Lemma 1443 (simplex of reference vertices is reference simplex).**

Let $d \ge 1$. Then, we have $K[[\hat{\mathbf{v}}]]^d = \hat{K}^d$.

*Proof.* Let $\hat{x} \in \mathbb{R}^d$. Then, since **the canon family is basis**, we have $\hat{x} = \sum_{i=1}^d \hat{x}_i e_i$.

Let $\mu_j \stackrel{\text{def.}}{=} \hat{x}_j$ for all $j \in [1..d]$, and $\mu_0 \stackrel{\text{def.}}{=} 1 - \sum_{j=1}^d \hat{x}_j$. Then, from Definition 1434 (family of reference points), we also have $\hat{x} = \sum_{i=0}^d \mu_i \hat{v}_i$ with $\sum_{i=0}^d \mu_i = 1$. Thus, from **ordered field properties of $\mathbb{R}$**, we obviously have the equivalence

$$ \forall i \in [0..d], \quad \mu_i \ge 0 \iff \sum_{j=1}^{d} \hat{x}_j \le 1, \quad \text{and} \quad \forall i \in [1..d], \quad \hat{x}_i \ge 0. $$

And finally, from Definition 1437 (reference simplex), and Definition 1440 (simplex), we have $\hat{x} \in K[[\hat{\mathbf{v}}]]^d$ iff $\hat{x} \in \hat{K}^d$, hence the equality. $\square$
**Definition 1448 (Lagrange polynomials of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Let $\{\{a\}\}_{\mathcal{A}_k^1}$ be $k+1$ points in $\mathbb{R}$. Assume that there is no double in $\{\{a\}\}_{\mathcal{A}_k^1}$. The Lagrange polynomials associated with $\{\{a\}\}_{\mathcal{A}_k^1}$ are denoted $\left(\mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}\right)_{i \in [0..k]}$, and are defined by

$$ (8.3) \qquad \forall x \in \mathbb{R}, \quad \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}(x) \stackrel{\text{def.}}{=} \prod_{j=0, j \neq i}^{k} \frac{x - a_j}{a_i - a_j}, $$

with the convention that a product indexed by the empty set equals 1 (i.e. when $k \stackrel{\text{def.}}{=} 0$).

**Lemma 1449 (Lagrange polynomials is basis of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Let $\{\{a\}\}_{\mathcal{A}_k^1}$ be $k+1$ points in $\mathbb{R}$. Assume that there is no double in $\{\{a\}\}_{\mathcal{A}_k^1}$. Then, the Lagrange polynomials associated with $\{\{a\}\}_{\mathcal{A}_k^1}$ form a basis of $\mathbb{P}_k^1$, that satisfies

$$ (8.4) \qquad \forall i \in [0..k], \quad \deg \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1} = k, $$

$$ (8.5) \qquad \forall i, j \in [0..k], \quad \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}(a_j) = \delta_{ij}, $$

$$ (8.6) \qquad \sum_{i=0}^{k} \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1} = 1. $$

**Proof. Degree (8.4), in $\mathbb{P}_k^1$, and identity (8.5).** Direct consequence of Definition 1448 (Lagrange polynomials of $\mathbb{P}_k^1$), Lemma 1422 (product of two univariate polynomials), Lemma 1418 ($\mathbb{P}_k^1$ is space of degree at most $k$), and field properties of $\mathbb{R}$.

**Basis.** Let $(\lambda_i)_{i \in [0..k]}$ in $\mathbb{R}$, such that $\sum_{i=0}^k \lambda_i \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1} = 0$. This implies that for all $x \in \mathbb{R}$, $\sum_{i=0}^k \lambda_i \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}(x) = 0$. Then, from (8.5), and **ring properties of $\mathbb{R}$**, taking $x \stackrel{\text{def.}}{=} a_j$ provides $\sum_{i=0}^k \lambda_i \delta_{ij} = \lambda_j = 0$. Thus, from **the definition of freedom**, Lemma 1420 (dimension of $\mathbb{P}_k^1$), and Lemma 1376 (**free family of dim elements is basis**), the Lagrange polynomials form a basis of $\mathbb{P}_k^1$.

**Identity (8.6).** From Definition 1417 (polynomial space $\mathbb{P}_k^1$, $1$ is in $\mathbb{P}_k^1$), the previous point (basis), and **the definition of basis (basis is generator)**, there exists $(\alpha_i)_{i \in [0..k]}$ in $\mathbb{R}$ such that $1 = \sum_{i=0}^k \alpha_i \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}$, and thus for all $x \in \mathbb{R}$, $1 = \sum_{i=0}^k \alpha_i \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}(x)$. Let $j \in [0..k]$. Then, from (8.5), taking $x \stackrel{\text{def.}}{=} a_j$ provides $1 = \sum_{i=0}^k \alpha_i \delta_{ij} = \alpha_j$, and we obtain (8.6). $\square$

**Lemma 1450 (decomposition of $\mathbb{P}_k^1$ polynomial in Lagrange basis).**

Let $\{\{a\}\}_{\mathcal{A}_k^1}$ be $k+1$ points in $\mathbb{R}$. Assume that there is no double in $\{\{a\}\}_{\mathcal{A}_k^1}$. Then, we have

$$ (8.7) \qquad \forall p \in \mathbb{P}_k^1, \quad p = \sum_{i=0}^{k} p(a_i) \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}. $$

**Proof.** Let $p \in \mathbb{P}_k^1$. Then, from Lemma 1449 (Lagrange polynomials is basis of $\mathbb{P}_k^1$, **basis**), there exists a unique $(\alpha_i)_{i \in [0..k]}$ in $\mathbb{R}$ such that for all $x \in \mathbb{R}$, $p(x) = \sum_{i=0}^k \alpha_i \mathcal{L}_i^{\{a\}}_{\mathcal{A}_k^1}(x)$.

Let $j \in [0..k]$. Then, from Lemma 1449 (Lagrange polynomials is basis of $\mathbb{P}_k^1$, (8.5)), taking $x \stackrel{\text{def.}}{=} a_j$ provides $p(a_j) = \sum_{i=0}^k \alpha_i \delta_{ij} = \alpha_j$. Thus, the result. $\square$

**Remark 1451.** In the following, instead of directly defining the finite element on a current cell, we choose to define the finite element on the reference cell first, then obtain the one on any current cell by the affine geometric transformation.
## 8.3 $\mathbb{L}^{\log} \hat{\mathbb{P}}_k^1$ Lagrange finite element on the reference segment

**Lemma 1452 (reference simplex is nontrivial in $\mathbb{R}$).** The reference simplex $\hat{\mathbb{K}}^1$ is the segment $[0, 1]$ of $\mathbb{R}$, whose vertices are $\hat{v}_0 = 0$ and $\hat{v}_1 = 1$ in $\mathbb{R}$. Its interior $\hat{\mathbb{K}}^1$ is nonempty.

*Proof.* Direct consequence of Definition 1437 (reference simplex), and Lemma 1439 (nontrivial reference simplex). □

**Definition 1453 (reference Lagrange nodes of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. The reference Lagrange nodes of $\mathbb{P}_k^1$ are denoted $\{\hat{a}_j\}_{\mathbb{A}_k^1}$, and are defined by

$$ (8.8) \qquad (k=0) \qquad \hat{a}_0 \stackrel{\text{def.}}{=} \hat{g}^1 = \frac{1}{2}, $$

$$ (8.9) \qquad (k \ge 1) \qquad \forall i \in [0..k], \quad \hat{a}_i \stackrel{\text{def.}}{=} i \hat{h} \quad \text{where } \hat{h} \stackrel{\text{def.}}{=} \frac{1}{k}. $$

**Lemma 1454 (reference Lagrange nodes are distinct).**

Let $k \in \mathbb{N}$. Let $i, j \in \mathbb{N}$. Then, the $(k+1)$ reference Lagrange nodes $\{\hat{a}_j\}_{\mathbb{A}_k^1}$ are distinct, and $0 \le i < j \le k$ implies $\hat{a}_i < \hat{a}_j$.

*Proof.* Direct consequence of Definition 1453 (reference Lagrange nodes of $\mathbb{P}_k^1$), and ordered field properties of $\mathbb{R}$. □

**Lemma 1455 (reference Lagrange basis of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Then, the Lagrange polynomials associated with the reference Lagrange nodes form a basis of $\mathbb{P}_k^1$ that satisfies (8.4), (8.5) and (8.6).

They are called reference Lagrange polynomials in $\mathbb{P}_k^1$, and for all $i \in [0..k]$, we define the shorthand notation $\hat{\mathcal{L}}_i^{k,1} \stackrel{\text{def.}}{=} \mathcal{L}_i^{\{\hat{a}_j\}_{\mathbb{A}_k^1}}$.

*Proof.* Direct consequence of Lemma 1454 (reference Lagrange nodes are distinct), and Lemma 1449 (Lagrange polynomials is basis of $\mathbb{P}_k^1$). □

**Definition 1456 (reference Lagrange linear forms for $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. The reference Lagrange linear forms associated with the reference Lagrange nodes of $\mathbb{P}_k^1$ are denoted $\hat{\Sigma}_k^1 = (\hat{\sigma}_i)_{i \in [0..k]}$, and are defined by

$$ (8.10) \qquad \forall i \in [0..k], \quad \forall \hat{f} : \mathbb{R} \to \mathbb{R}, \quad \hat{\sigma}_i(\hat{f}) \stackrel{\text{def.}}{=} \hat{f}(\hat{a}_i). $$

**Lemma 1457 (reference Lagrange linear forms for $\mathbb{P}_k^1$ are linear).**

Let $k \in \mathbb{N}$. Let $i \in [0..k]$. Then, the reference Lagrange linear form $\hat{\sigma}_i$ is linear.

*Proof.* Direct consequence of Definition 1456 (reference Lagrange linear forms for $\mathbb{P}_k^1$), and the definition of linear operations over functions. □

**Lemma 1458 (reference Lagrange linear forms for $\mathbb{P}_k^1$ are injective).**

Let $k \in \mathbb{N}$. Then, $\phi_{\hat{\Sigma}_k^1}$ is injective.

*Proof.* Direct consequence of Definition 1424 (finite element triple), Lemma 1454 (reference Lagrange nodes are distinct), Definition 1456 (reference Lagrange linear forms for $\mathbb{P}_k^1$, thus for all $\hat{p} \in \mathbb{P}_k^1$, $\hat{\sigma}_i(\hat{p})$ is zero implies $\hat{p}(\hat{a}_i) = 0$), Lemma 1450 (decomposition of $\mathbb{P}_k^1$ polynomial in Lagrange basis, thus $\hat{p} = 0$), Definition 101 (kernel), and Lemma 103 (injective linear map has zero kernel). □
**Lemma 1459 (unisolvence of $\mathbb{P}_k^1$ (reference)).**

Let $k \in \mathbb{N}$. Then, $(\hat{K}^1, \mathbb{P}_k^1, \hat{\Sigma}_k^1)$ satisfies the unisolvence property.

*Proof.* Direct consequence of Lemma 1420 (*dimension of $\mathbb{P}_k^1$*), Lemma 1454 (*reference Lagrange nodes are distinct*), **the definition of order (reflexivity, thus $\dim \mathbb{P}_k^1 = k + 1$ is greater than or equal to $k + 1 = \text{card}(\hat{\Sigma}_k^1)$**), Lemma 1458 (*reference Lagrange linear forms for $\mathbb{P}_k^1$ are injective*), and Lemma 1426 (*injectivity implies unisolvence*). $\square$

**Theorem 1460 ($\text{Log} \hat{\mathbb{P}}_k^1$ reference Lagrange finite element).**

Let $k \in \mathbb{N}$. Then, $^{\text{Log}}\hat{\mathbb{P}}_k^1 \stackrel{\text{def.}}{=} (\hat{K}^1, \mathbb{P}_k^1, \hat{\Sigma}_k^1)$ is a finite element.

It is called the reference Lagrange finite element of degree $k$ in dimension 1.

*Proof.* Direct consequence of Lemma 1452 (*reference simplex is nontrivial in $\mathbb{R}$*), Lemma 1420 (*dimension of $\mathbb{P}_k^1$*), Lemma 1459 (*unisolvence of $\mathbb{P}_k^1$ (reference)*), and Definition 1424 (*finite element triple, with $q \stackrel{\text{def.}}{=} 1$*). $\square$

## 8.4 $^{\text{Log}}\mathbb{P}_k^1$ Lagrange finite element on a current segment

**Definition 1461 (geometric mapping in dimension 1).** Let $[[v]]^1$ be two points in $\mathbb{R}$.

The geometric mapping associated with $[[v]]^1$ is denoted $\varphi_{\text{geo}}^{[[v]]^1}$, and is defined by

$$ (8.11) \qquad \forall \hat{x} \in \mathbb{R}, \quad \varphi_{\text{geo}}^{[[v]]^1}(\hat{x}) \stackrel{\text{def.}}{=} (v_1 - v_0)\hat{x} + v_0. $$

**Lemma 1462 (properties of geometric mapping in dimension 1).**

Let $[[v]]^1$ be two points in $\mathbb{R}$. Then, $\varphi_{\text{geo}}^{[[v]]^1} \in \mathbb{P}_1^1$, i.e. is affine, and we have

$$ (8.12) \qquad \forall \hat{x} \in \mathbb{R}, \quad \varphi_{\text{geo}}^{[[v]]^1}(\hat{x}) = (1 - \hat{x})v_0 + \hat{x}v_1 = \hat{\mathcal{L}}_0^{1,1}(\hat{x})v_0 + \hat{\mathcal{L}}_1^{1,1}(\hat{x})v_1, $$

$$ (8.13) \qquad \forall \hat{x} \in \mathbb{R}, \quad (\varphi_{\text{geo}}^{[[v]]^1})'(\hat{x}) = v_1 - v_0. $$

Moreover, if $v_0 \neq v_1$, then $\varphi_{\text{geo}}^{[[v]]^1}$ is bijective, $(\varphi_{\text{geo}}^{[[v]]^1})^{-1}$ is affine, and we have

$$ (8.14) \qquad \forall x \in \mathbb{R}, \quad (\varphi_{\text{geo}}^{[[v]]^1})^{-1}(x) = \frac{x - v_0}{v_1 - v_0}. $$

*Proof.* Direct consequence of Definition 1461 (*geometric mapping in dimension 1*), Lemma 1399 (*equivalent definition of affine map (finite dimension)*), Lemma 1418 ($\mathbb{P}_k^1$ is space of degree at most $k$), Definition 1453 (*reference Lagrange nodes of $\mathbb{P}_k^1$, with $k \stackrel{\text{def.}}{=} 1$, thus $\{[\hat{a}]\}_{\mathcal{A}_k} \stackrel{\text{def.}}{=} [[\hat{v}]^1]$*), Lemma 1455 (*reference Lagrange basis of $\mathbb{P}_k^1$, with $k \stackrel{\text{def.}}{=} 1$*), **the rules of derivation in $\mathbb{R}$**, and Lemma 1410 (*inverse of affine map is affine map, with $\phi^{-1}(y) \stackrel{\text{def.}}{=} \frac{y}{v_1 - v_0}$*). $\square$

**Lemma 1463 (current simplex is nontrivial in $\mathbb{R}$).** Let $[[v]]^1$ be two points in $\mathbb{R}$.

Then, the current simplex $K[[v]]^1$ is the segment $[\min\{v_0, v_1\}, \max\{v_0, v_1\}]$ of $\mathbb{R}$.

Moreover, we have

$$ (8.15) \qquad v_0 \neq v_1 \iff K[[v]]^1 \neq \emptyset. $$
**Proof.** $K^{\llbracket v \rrbracket^1}$. Direct consequence of Definition 1440 (simplex), and **the definition of a segment**.

**Equivalence.** Let $w_0 \stackrel{\text{def.}}{=} \min\{v_0, v_1\}$ and $w_1 \stackrel{\text{def.}}{=} \max\{v_0, v_1\}$. Then, from **ordered field properties of $\mathbb{R}$**, and **the interior of a segment**, we have

$$v_0 \neq v_1 \iff w_0 < w_1 \iff (w_0, w_1) \neq \emptyset \iff K^{\llbracket v \rrbracket^1} \neq \emptyset.$$

□

**Lemma 1464 (current simplex is image of reference in $\mathbb{R}$).**

Let $\llbracket v \rrbracket^1$ be two points in $\mathbb{R}$. Then, we have $K^{\llbracket v \rrbracket^1} = \varphi_{\text{geo}}^{\llbracket v \rrbracket^1}(\hat{K}^1)$.

**Proof.** Direct consequence of Definition 1461 (geometric mapping in dimension 1), Lemma 1452 (reference simplex is nontrivial in $\mathbb{R}$), and Lemma 1463 (current simplex is nontrivial in $\mathbb{R}$). □

**Definition 1465 (Lagrange nodes of $\mathbb{P}_k^1$).** Let $k \in \mathbb{N}$. Let $\llbracket v \rrbracket^1$ be two points in $\mathbb{R}$. The Lagrange nodes of $\mathbb{P}_k^1$ are denoted $\{\mathfrak{a}\}_{\mathbb{P}_k^1}$, and are defined by

$$(8.16) \qquad (k = 0) \qquad a_0 \stackrel{\text{def.}}{=} g^{\llbracket v \rrbracket^1} = \frac{v_0 + v_1}{2},$$

$$(8.17) \qquad (k \ge 1) \qquad \forall i \in [0..k], \quad a_i \stackrel{\text{def.}}{=} v_0 + i h \quad \text{where } h \stackrel{\text{def.}}{=} \frac{v_1 - v_0}{k}.$$

*Remark 1466.* The isobarycenter $g^{\llbracket v \rrbracket^1}$ is defined in Definition 1401.

**Lemma 1467 (Lagrange nodes are distinct).**

Let $k \in \mathbb{N}$. Let $i, j \in \mathbb{N}$. Let $\llbracket v \rrbracket^1$ be two distinct points in $\mathbb{R}$.

Then, the $(k+1)$ Lagrange nodes $\{\mathfrak{a}\}_{\mathbb{P}_k^1}$ are distinct, and $0 \le i < j \le k$ implies $a_i \neq a_j$.

Moreover, if $v_0 < v_1$, then $h > 0$, and $0 \le i < j \le k$ implies $a_i < a_j$, and if $v_0 > v_1$, then $h < 0$, and $0 \le i < j \le k$ implies $a_i > a_j$.

**Proof.** Direct consequence of Definition 1465 (Lagrange nodes of $\mathbb{P}_k^1$), and **ordered field properties of $\mathbb{R}$**. □

**Lemma 1468 (Lagrange nodes of $\mathbb{P}_k^1$ are images of reference).**

Let $k \in \mathbb{N}$. Let $\llbracket v \rrbracket^1$ be two points in $\mathbb{R}$. Then, we have $\forall i \in [0..k]$, $a_i = \varphi_{\text{geo}}^{\llbracket v \rrbracket^1}(\hat{a}_i)$.

**Proof.** Direct consequence of Definition 1461 (geometric mapping in dimension 1), Definition 1453 (reference Lagrange nodes of $\mathbb{P}_k^1$), and Definition 1465 (Lagrange nodes of $\mathbb{P}_k^1$). □

**Lemma 1469 (Lagrange basis of $\mathbb{P}_k^1$).** Let $k \in \mathbb{N}$. Let $\llbracket v \rrbracket^1$ be two distinct points in $\mathbb{R}$.

Then, the Lagrange polynomials associated with the Lagrange nodes form a basis of $\mathbb{P}_k^1$ that satisfies (8.4), (8.5) and (8.6). They are called current Lagrange polynomials in $\mathbb{P}_k^1$.

**Proof.** Direct consequence of Lemma 1467 (Lagrange nodes are distinct), and Lemma 1449 (Lagrange polynomials is basis of $\mathbb{P}_k^1$). □

**Lemma 1470 (Lagrange polynomials of $\mathbb{P}_k^1$ are images of reference).**

Let $k \in \mathbb{N}$. Let $\llbracket v \rrbracket^1$ be two distinct points in $\mathbb{R}$. Then, we have for all $i \in [0..k]$,

$$(8.18) \qquad \mathcal{L}_i^{\{\mathfrak{a}\}_{\mathbb{P}_k^1}} = \hat{\mathcal{L}}_{i,1}^{k,1} \circ (\varphi_{\text{geo}}^{\llbracket v \rrbracket^1})^{-1} \quad \text{and} \quad \hat{\mathcal{L}}_i^{k,1} = \mathcal{L}_i^{\{\mathfrak{a}\}_{\mathbb{P}_k^1}} \circ \varphi_{\text{geo}}^{\llbracket v \rrbracket^1}.$$
**Proof.** Direct consequence of Definition 1448 (Lagrange polynomials of $\mathbb{P}_k^1$), Lemma 1455 (reference Lagrange basis of $\mathbb{P}_k^1$), Lemma 1469 (Lagrange basis of $\mathbb{P}_k^1$), Lemma 1468 (Lagrange nodes of $\mathbb{P}_k^1$ are images of reference), Definition 1461 (geometric mapping in dimension 1), and field properties of $\mathbb{R}$ (providing the following identities

$$ \frac{x - a_j}{a_i - a_j} = \frac{(v_1 - v_0)\hat{x} + v_0 - (v_1 - v_0)\hat{a}_j - v_0}{(v_1 - v_0)\hat{a}_i + v_0 - (v_1 - v_0)\hat{a}_j - v_0} = \frac{\hat{x} - \hat{a}_j}{\hat{a}_i - \hat{a}_j}, \\ \forall f: \mathbb{R} \to \mathbb{R}, \quad 1 = 1 \circ f). $$

□

**Lemma 1471 (geometric mapping of $\mathbb{P}_k^1$ is $\mathbb{P}_k^1$).** Let $k \in \mathbb{N}$. Let $[[v]]^1$ be two points in $\mathbb{R}$.
Then, for all $p \in \mathbb{P}_k^1$, $p \circ \varphi_{\text{geo}}^{[[v]]^1} \in \mathbb{P}_k^1$. Moreover, if $v_0 \neq v_1$, then, $p \circ (\varphi_{\text{geo}}^{[[v]]^1})^{-1} \in \mathbb{P}_k^1$.

**Proof.** Let $p \in \mathbb{P}_k^1$.

**Case $v_0 = v_1$.** Direct consequence of Definition 1461 (geometric mapping in dimension 1, thus, $\varphi_{\text{geo}}^{[[v]]^1} = v_0$ is constant), and Definition 1417 (polynomial space $\mathbb{P}_k^1$, thus, we have $p \circ \varphi_{\text{geo}}^{[[v]]^1} = p(v_0)$ lives in $\mathbb{P}_0^1 \subset \mathbb{P}_k^1$).

**Case $v_0 \neq v_1$.** Then, from Lemma 1469 (Lagrange basis of $\mathbb{P}_k^1$, basis), Lemma 1470 (Lagrange polynomials of $\mathbb{P}_k^1$ are images of reference), and Lemma 1455 (reference Lagrange basis of $\mathbb{P}_k^1$, basis), there exists $(\alpha_i)_{i \in [0..k]}$ in $\mathbb{R}$ such that $p = \sum_{i=0}^k \alpha_i \mathcal{L}_i^{\{a\}_{\mathbb{P}_k^1}}$, and we have

$$ p \circ \varphi_{\text{geo}}^{[[v]]^1} = \sum_{i=0}^{k} \alpha_i \mathcal{L}_i^{\{a\}_{\mathbb{P}_k^1}} \circ \varphi_{\text{geo}}^{[[v]]^1} = \sum_{i=0}^{k} \alpha_i \hat{\mathcal{L}}_i^{k,1} \in \mathbb{P}_k^1. $$

Similarly, from Lemma 1455 (reference Lagrange basis of $\mathbb{P}_k^1$, basis), Lemma 1470 (Lagrange polynomials of $\mathbb{P}_k^1$ are images of reference), and Lemma 1469 (Lagrange basis of $\mathbb{P}_k^1$, basis), there exists $(\alpha_i)_{i \in [0..k]}$ in $\mathbb{R}$ such that $p = \sum_{i=0}^k \alpha_i \hat{\mathcal{L}}_i^{k,1}$, and we have

$$ p \circ (\varphi_{\text{geo}}^{[[v]]^1})^{-1} = \sum_{i=0}^{k} \alpha_i \hat{\mathcal{L}}_i^{k,1} \circ (\varphi_{\text{geo}}^{[[v]]^1})^{-1} = \sum_{i=0}^{k} \alpha_i \mathcal{L}_i^{\{a\}_{\mathbb{P}_k^1}} \in \mathbb{P}_k^1. $$

□

**Definition 1472 (Lagrange linear forms for $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Let $[[v]]^1$ be two points in $\mathbb{R}$. The Lagrange linear forms associated with the Lagrange nodes of $\mathbb{P}_k^1$ are denoted $\sum_{i=0}^k \alpha_i^{\{a\}_{\mathbb{P}_k^1}} = (\sigma_i)_{i \in [0..k]}$, and are defined by

$$ (8.19) \qquad \forall i \in [0..k], \quad \forall f: \mathbb{R} \to \mathbb{R}, \quad \sigma_i(f) \stackrel{\text{def.}}{=} f(a_i). $$

**Lemma 1473 ($\mathbb{P}_k^1$ Lagrange linear forms are linear).** Let $k \in \mathbb{N}$.
Let $[[v]]^1$ be two points in $\mathbb{R}$. Let $i \in [0..k]$. Then, the Lagrange linear form $\sigma_i$ is linear.

**Proof.** Direct consequence of Definition 1472 (Lagrange linear forms for $\mathbb{P}_k^1$), and the definition of linear operations over functions. □

**Lemma 1474 ($\mathbb{P}_k^1$ Lagrange linear forms are images of reference).** Let $k \in \mathbb{N}$. Let $[[v]]^1$ be two points in $\mathbb{R}$. Then, we have $\forall i \in [0..k], \forall f: \mathbb{R} \to \mathbb{R}, \sigma_i(f) = \hat{\sigma}_i(\hat{f})$, where $\hat{f} = f \circ \varphi_{\text{geo}}^{[[v]]^1}$.

**Proof.** Direct consequence of Definition 1472 (Lagrange linear forms for $\mathbb{P}_k^1$), Lemma 1468 (Lagrange nodes of $\mathbb{P}_k^1$ are images of reference), and Definition 1456 (reference Lagrange linear forms for $\mathbb{P}_k^1$). □
Remark 1475. Note that Lemmas 1464, 1471, and 1474 imply that the current $\mathbb{P}_k^1$ FE ($K[\llbracket v \rrbracket^1, \mathbb{P}_k^1, \Sigma^{\{a\}}_{\mathcal{A}_k^1}$) can be considered as the image of the reference $\mathbb{P}_k^1$ FE ($\hat{K}^1, \hat{\mathbb{P}}_k^1, \hat{\Sigma}_k^1$) by $\varphi_{\text{geo}}^{\llbracket v \rrbracket^1}$.

**Lemma 1476 (Lagrange linear forms for $\mathbb{P}_k^1$ are injective).**

Let $k \in \mathbb{N}$. Let $[\llbracket v \rrbracket^1]$ be two distinct points in $\mathbb{R}$. Then, $\phi_{\Sigma^{\{a\}}_{\mathcal{A}_k^1}}$ is injective.

*Proof*. Direct consequence of Definition 1424 (finite element triple), Lemma 1467 (Lagrange nodes are distinct), Definition 1472 (Lagrange linear forms for $\mathbb{P}_k^1$, thus for all $p \in \mathbb{P}_k^1$, $\sigma_i(p) = 0$ implies $p(a_i) = 0$), Lemma 1450 (decomposition of $\mathbb{P}_k^1$ polynomial in Lagrange basis, thus $p=0$), Definition 101 (kernel), and Lemma 103 (injective linear map has zero kernel). $\square$

**Lemma 1477 (unisolvence of $\mathbb{P}_k^1$).**

Let $k \in \mathbb{N}$. Let $[\llbracket v \rrbracket^1]$ be two distinct points in $\mathbb{R}$.
Then, $(K[\llbracket v \rrbracket^1, \mathbb{P}_k^1, \Sigma^{\{a\}}_{\mathcal{A}_k^1})$ satisfies the unisolvence property.

*Proof*. Direct consequence of Lemma 1420 (dimension of $\mathbb{P}_k^1$), Lemma 1467 (Lagrange nodes are distinct), the definition of order (reflexivity, thus $\dim \mathbb{P}_k^1 = k + 1$ is greater than or equal to $k + 1 = \text{card}(\Sigma^{\{a\}}_{\mathcal{A}_k^1}))$, Lemma 1476 (Lagrange linear forms for $\mathbb{P}_k^1$ are injective), and Lemma 1426 (injectivity implies unisolvence). $\square$

**Theorem 1478 ($\text{Log}\mathbb{P}_k^1$ Lagrange finite element).** Let $k \in \mathbb{N}$. Let $[\llbracket v \rrbracket^1]$ be two distinct points in $\mathbb{R}$. Then, $\text{Log}\mathbb{P}_k^1 \stackrel{\text{def.}}{=} (K[\llbracket v \rrbracket^1, \mathbb{P}_k^1, \Sigma^{\{a\}}_{\mathcal{A}_k^1})$ is a finite element.

It is called the Lagrange finite element of degree $k$ in dimension 1 associated with vertices $[\llbracket v \rrbracket^1]$.

*Proof*. Direct consequence of Lemma 1463 (current simplex is nontrivial in $\mathbb{R}$), Lemma 1420 (dimension of $\mathbb{P}_k^1$), Lemma 1477 (unisolvence of $\mathbb{P}_k^1$), and Definition 1424 (finite element triple, with $q \stackrel{\text{def.}}{=} 1$). $\square$
# Chapter 9

## Lagrange finite element in dimension $d \ge 1$

### Contents

<table><tbody><tr><td>9.1</td><td>Multi-indices</td><td>66</td></tr><tr><td>9.1.1</td><td>Some useful notations for multi-indices</td><td>66</td></tr><tr><td>9.1.2</td><td>Sets $A_k^d$ and $C_k^d$ of multi-indices</td><td>67</td></tr><tr><td>9.1.3</td><td>Slices of $C_k^d$ and its cardinal</td><td>67</td></tr><tr><td>9.1.4</td><td>Layers of $A_k^d$ and its cardinal</td><td>70</td></tr><tr><td>9.1.5</td><td>Other cardinals</td><td>70</td></tr><tr><td>9.2</td><td>Multivariate polynomials</td><td>72</td></tr><tr><td>9.2.1</td><td>Monomials and polynomials of $\mathbb{P}_k^d$</td><td>72</td></tr><tr><td>9.2.2</td><td>Product of polynomials</td><td>73</td></tr><tr><td>9.2.3</td><td>Linear independence of monomials</td><td>74</td></tr><tr><td>9.2.4</td><td>Decomposition of polynomials, isomorphisms of $\mathbb{P}_k^d$</td><td>76</td></tr><tr><td>9.2.5</td><td>Product of polynomials (alternate)</td><td>79</td></tr><tr><td>9.2.6</td><td>Composition of polynomials and affine mappings</td><td>80</td></tr><tr><td>9.3</td><td>$\mathbb{P}_k^d$ affine polynomials and affine geometric mapping</td><td>81</td></tr><tr><td>9.3.1</td><td>Reference affine Lagrange polynomials</td><td>81</td></tr><tr><td>9.3.2</td><td>Affine geometric mapping from $\mathbb{R}^d$ to $\mathbb{R}^d$</td><td>82</td></tr><tr><td>9.3.3</td><td>Current affine Lagrange polynomials</td><td>84</td></tr><tr><td>9.3.4</td><td>Nontrivial current simplex</td><td>86</td></tr><tr><td>9.4</td><td>Barycentric coordinates</td><td>86</td></tr><tr><td>9.5</td><td>Hyperplanes and $l$-faces</td><td>88</td></tr><tr><td>9.5.1</td><td>Hyperplanes and $d-1$-faces</td><td>88</td></tr><tr><td>9.5.2</td><td>$l$-face affine spaces and $l$-faces</td><td>91</td></tr><tr><td>9.5.3</td><td>Geometric $l$-face mappings</td><td>92</td></tr><tr><td>9.5.4</td><td>Geometric hyperface mapping</td><td>94</td></tr><tr><td>9.5.5</td><td>Geometric mapping with permutation</td><td>96</td></tr><tr><td>9.6</td><td>Lagrange nodes for $\mathbb{P}_k^d$</td><td>97</td></tr><tr><td>9.6.1</td><td>Lagrange nodes for the current element</td><td>97</td></tr><tr><td>9.6.2</td><td>Sub-vertices and sub-nodes</td><td>98</td></tr><tr><td>9.6.3</td><td>Lagrange nodes for the reference element</td><td>100</td></tr><tr><td>9.6.4</td><td>Lagrange nodes and face hyperplanes</td><td>101</td></tr><tr><td>9.7</td><td>Lagrange linear forms for $\mathbb{P}_k^d$</td><td>102</td></tr><tr><td>9.8</td><td>Unisolvence for $\mathbb{P}_0^d$</td><td>103</td></tr></tbody></table>
<table><tr><td>9.9</td><td>Unisolvency for <sup>Log</sup><sub>P</sub><sup>d</sup></td><td>104</td></tr><tr><td>9.10</td><td>Unisolvency for <sup>Log</sup><sub>k</sub><sup>d</sup></td><td>104</td></tr><tr><td>9.11</td><td>Log<sub>k</sub> Lagrange finite element</td><td>108</td></tr></table>

Remark 1479. In this chapter, we consider a simplex in $\mathbb{R}^d$ with $d \ge 1$. The case $d = 1$ corresponds to a segment, and is treated in detail in Chapter 8.

In Figure 9.1, we present the Lagrange nodes on simplices for several dimensions and degrees.

<figure><img src="image_19.png" /><figcaption>Figure 9.1: Lagrange nodes of the reference simplex for $d = 1, 2, 3$ (from top to bottom), and $k = 0, 1, 2, 3, 4$ (from left to right). The nodes corresponding to the highest degree are depicted in red, and the others in blue. The multi-indices are indicated in all cases when $d = 1, 2$, and only for the highest degree when $d = 3$.</figcaption></figure>

# 9.1 Multi-indices

## 9.1.1 Some useful notations for multi-indices

**Definition 1480 (length of multi-indices).** Let $d \ge 1$. Let $\alpha \in \mathbb{N}^d$ be a multi-index. The length of $\alpha$ is denoted $|\alpha|$, and is defined by $|\alpha| \stackrel{\text{def.}}{=} \sum_{i=1}^d \alpha_i \in \mathbb{N}$.

**Lemma 1481 (length of multi-indices is additive).**
Let $d \ge 1$. Then, the length of multi-indices is additive, for all $\alpha, \beta \in \mathbb{N}^d$, $|\alpha + \beta| = |\alpha| + |\beta|$.

*Proof.* Direct consequence of Definition 1480 (length of multi-indices), and abelian monoid properties of $\mathbb{N}$. $\square$

**Definition 1482 (factorial of multi-indices).** Let $d \ge 1$. Let $\alpha \in \mathbb{N}^d$ be a multi-index. The factorial of $\alpha$ is denoted $\alpha!$, and is defined by $\alpha! \stackrel{\text{def.}}{=} \prod_{i=1}^d (\alpha_i!) \in \mathbb{N}^*.$

**Lemma 1483 (factorial of multi-index is positive).** Let $d \ge 1$. Let $\alpha \in \mathbb{N}^d$. Then, $\alpha! > 0$.

*Proof.* Direct consequence of Definition 1482 (factorial of multi-indices), the positivity of factorial, and closedness of multiplication in $\mathbb{N}^*$. $\square$
**Definition 1484 (Kronecker delta of multi-indices).**
Let $d \ge 1$. Let $\alpha, \beta \in \mathbb{N}^d$.
The Kronecker delta of $\alpha$ and $\beta$ is denoted $\delta_{\alpha,\beta}$, and is defined by $\delta_{\alpha,\beta} \stackrel{\text{def.}}{=} \prod_{i=1}^d \delta_{\alpha_i \beta_i}$.

**Lemma 1485 (value of Kronecker delta of multi-indices).**
Let $d \ge 1$. Let $\alpha, \beta \in \mathbb{N}^d$.
Then, we have $\delta_{\alpha,\beta}$ equals 1 when $\alpha = \beta$, and 0 otherwise.

*Proof.* Direct consequence of Definition 1484 (Kronecker delta of multi-indices), **the definition of the (scalar) Kronecker delta**, and **the zero-product property in $\mathbb{N}$**. $\square$

### 9.1.2 Sets $A_k^d$ and $C_k^d$ of multi-indices

**Definition 1486 (sets of multi-indices $A_k^d$ and $C_k^d$).** Let $d \ge 1$. Let $k \in \mathbb{N}$. The set of multi-indices of length at most $k$ (resp. of length $k$) is denoted $A_k^d$ (resp. $C_k^d$), and is defined by

$$ (9.1) \qquad A_k^d \stackrel{\text{def.}}{=} \{\alpha \in \mathbb{N}^d \mid |\alpha| \le k\}, $$

$$ (9.2) \qquad C_k^d \stackrel{\text{def.}}{=} \{\alpha \in \mathbb{N}^d \mid |\alpha| = k\}. $$

Let $i \in [1..d]$. The subset of $A_k^d$ of multi-indices with zero $i$-th component is defined by

$$ (9.3) \qquad A_{k,i}^d \stackrel{\text{def.}}{=} \{\alpha \in A_k^d \mid \alpha_i = 0\}. $$

**Lemma 1487 (multi-indices $A_k^d$ for $d=1$ is $A_k^1$).**

Let $k \in \mathbb{N}$. Then, $A_k^d$ for $d \stackrel{\text{def.}}{=} 1$ and $A_k^1$ from Definition 1445 coincide.

*Proof.* Direct consequence of Definition 1486 (sets of multi-indices $A_k^d$ and $C_k^d$, (9.1) with $d \stackrel{\text{def.}}{=} 1$), Definition 1480 (length of multi-indices, with $d \stackrel{\text{def.}}{=} 1$, thus $|\alpha| = \alpha_1$), and Definition 1445 (multi-indices $A_k^1$). $\square$

**Lemma 1488 (indices are smaller than maximal length).**

Let $d \ge 1$. Let $k \in \mathbb{N}$. Let $\alpha \in A_k^d \cup C_k^d$. Let $i \in [1..d]$. Then, we have $\alpha_i \le k$.

*Proof.*

Direct consequence of Definition 1480 (length of multi-indices, thus $\alpha_i \le |\alpha|$), Definition 1486 (sets of multi-indices $A_k^d$ and $C_k^d$, thus $|\alpha| \le k$), and **the definition of order (transitivity)**. $\square$

**Lemma 1489 (first $C_k^d$).**
Let $d \ge 1$. Let $k \in \mathbb{N}$. Then, we have

$$ (9.4) \qquad (d=1) \qquad C_k^1 = \{k\}, \quad \text{and} \quad \text{card}(C_k^1) = 1, $$

$$ (9.5) \qquad (d=2) \qquad C_k^2 = \{(k-i, i) \in \mathbb{N}^2 \mid i \in [0..k]\}, \quad \text{and} \quad \text{card}(C_k^2) = k+1, $$

$$ (9.6) \qquad (k=0) \qquad C_0^d = \{\mathbf{0} \in \mathbb{N}^d\}, \quad \text{and} \quad \text{card}(C_0^d) = 1, $$

$$ (9.7) \qquad (k=1) \qquad C_1^d = \{\mathbf{e}_i \in \mathbb{N}^d \mid i \in [1..d]\}, \quad \text{and} \quad \text{card}(C_1^d) = d. $$

*Proof.* Direct consequence of Definition 1365 (canonic families), Definition 1486 (sets of multi-indices $A_k^d$ and $C_k^d$), and Lemma 1488 (indices are smaller than maximal length). $\square$

### 9.1.3 Slices of $C_k^d$ and its cardinal

*Remark 1490.* In the sequel, when $d \ge 2$, the check notation $\tilde{\alpha}$ denotes the last $d-1$ components of the multi-index $\alpha \in \mathbb{N}^d$, and the tilde notation $\tilde{\alpha}$ denotes the first ones.

Thus, for all $\alpha \stackrel{\text{def.}}{=} (\alpha_1, \dots, \alpha_d) \in \mathbb{N}^d$, we have $\alpha = (\alpha_1, \tilde{\alpha}) = (\tilde{\alpha}, \alpha_d)$.

The notation naturally extends to vectors in $\mathbb{R}^d$, and other objects such as subsets and functions may also inherit the check or tilde decoration, e.g. see Definition 1491 and Lemma 1494.
**Definition 1491 (slices $\tilde{S}_{k,i}^d$ and $\tilde{S}_{k,i}^d$).**
Let $d \ge 2$. Let $k \in \mathbb{N}$. Let $i \in [0..k]$.

The $i$-th "vertical" (resp. "horizontal") slice of $C_k^d$ is denoted $\tilde{S}_{k,i}^d$ (resp. $\tilde{S}_{k,i}^d$), and is defined by

$$ (9.8) \qquad \tilde{S}_{k,i}^d \stackrel{\text{def.}}{=} \{(i, \tilde{\alpha}) \in \mathbb{N}^d \mid \tilde{\alpha} \in C_{k-i}^{d-1}\}, \quad \text{and} \quad \tilde{S}_{k,i}^d \stackrel{\text{def.}}{=} \{(\tilde{\alpha}, i) \in \mathbb{N}^d \mid \tilde{\alpha} \in C_{k-i}^{d-1}\}. $$

**Remark 1492.** Geometrically, the “vertical” slice $\tilde{S}_{k,i}^d$ is the intersection of $C_k^d$ (subset in $\mathbb{N}^d$ of the hyperplane of equation $\sum_{i=1}^d \alpha_i = k$) with the (vertical) first canonical hyperplane of equation $\alpha_1 = i$, see Figure 9.2. The order discussed in Section 3.3.8 is consistent with the decomposition of $C_k^d$ in slices as $C_k^d = \bigsqcup_{i=k}^0 \tilde{S}_{k,i}^d$ (decreasing from $k$ to 0), see Lemma 1493.

In the same way, the “horizontal” slice $\tilde{S}_{k,i}^d$ is the intersection of $C_k^d$ with the (horizontal) last canonical hyperplane of equation $\alpha_d = i$.

<figure><img src="image_20.png" /><figcaption>Figure 9.2: Vertical slices $\tilde{S}_{k,i}^d$ (left) and horizontal slices $\tilde{S}_{k,i}^d$ (right), in the case $d=k=3$ (see Definition 1491). The reference Lagrange node $\hat{a}_{(\alpha_1, \alpha_2, \alpha_3)}$ in blue corresponds to the element $(\alpha_1, \alpha_2, \alpha_3) \in C_k^d$. For instance, the set $\tilde{S}_{k,1}^d = \{(1, 2, 0), (1, 1, 1), (1, 0, 2)\}$ is depicted by the nodes linked by a dashed arrow.</figcaption></figure>

**Lemma 1493 (slices of $C_k^d$).**

Let $d \ge 2$. Let $k \in \mathbb{N}$. Let $i \in [0..k]$. Then, $\tilde{S}_{k,i}^d$ and $\tilde{S}_{k,i}^d$ are subsets of $C_k^d$, and we have

$$ (9.9) \qquad C_k^d = \bigsqcup_{i=0}^k \tilde{S}_{k,i}^d = \bigsqcup_{i=0}^k \tilde{S}_{k,i}^d. $$

**Proof. Case of $\tilde{S}_{k,i}^d$.** Let $\alpha \in \tilde{S}_{k,i}^d$. Then, from Definition 1491 (slices $\tilde{S}_{k,i}^d$ and $\tilde{S}_{k,i}^d$), and Definition 1486 (sets of multi-indices $A_k^d$ and $C_k^d$), there exists $\tilde{\alpha} \in C_{k-i}^{d-1}$ such that $\alpha = (i, \tilde{\alpha})$, and we have $|\alpha| = i + |\tilde{\alpha}| = i + k - i = k$, i.e. $\alpha \in C_k^d$, and $\tilde{S}_{k,i}^d \subset C_k^d$. Thus, we have $\bigsqcup_{i=0}^k \tilde{S}_{k,i}^d \subset C_k^d$.

Let $i, j \in [0..k]$. Let $\alpha \in \tilde{S}_{k,i}^d \cap \tilde{S}_{k,j}^d$. Then, from Definition 1491 (slices $\tilde{S}_{k,i}^d$ and $\tilde{S}_{k,j}^d$), there exist $\tilde{\alpha}^i \in C_{k-i}^{d-1}$ and $\tilde{\alpha}^j \in C_{k-j}^{d-1}$ such that $\alpha = (i, \tilde{\alpha}_i) = (j, \tilde{\alpha}_j)$. Thus, we have $i = j$ and $\tilde{\alpha}_i = \tilde{\alpha}_j$, and by contrapositive, we have $\tilde{S}_{k,i}^d \cap \tilde{S}_{k,j}^d = \emptyset$ when $i \ne j$.