text:
## Monday, December 28, 2015

### Classical Mechanics Primer

There are at least two senses in which the term “Classical Physics” is used. First, classical may be used to mean “all physics that is not quantum physics”. The second sense is more similar to what most people usually have in mind, and basically refers to all physics which is not “modern”—that is, physics before General Relativity and Quantum Mechanics.  Physicists always mean to use the first sense of the term, and laypeople usually switch from one to the other, sometimes without noticing. From this point on, I’ll be using the physicist’s sense unless noted otherwise.

Now, the expression “not quantum” needs some unpacking. As an example, consider a toaster with a knob that you can turn at your leisure over some period of time, t. If you were to plot the energy flowing through the toaster’s resistance as you turn the knob, the graph that you will get might look something like this:

In Classical Physics, there is no limit to the number of times that you could zoom into any section of this plot, and every single time you would see a smooth, continuous line like the figure above. If you moved along the curve, you could always ride the line like a smooth ramp to any value of E that you liked, and in doing so you would pass through all points in between.

This is not the case in Quantum Mechanics, where many physical quantities are said to be quantized.  In the toaster example above, the plot will look the same initially, but after zooming in a finite number of times, eventually you will reach a plot that looks more like this:

This is what makes Quantum Mechanics so weird. And so, Classical Physics includes all the branches of physics where this effect is not taken into account, regardless of when said branch developed. This includes theories such as Classical Mechanics, Electromagnetism, Thermodynamics, Fluid Mechanics, and General Relativity, among others. Usually, classical theories are an excellent approximation for all kinds of real world phenomena, even though the real world is actually quantized.

#### Newton

Newton’s Three Laws of Motion are as follows, though you may find some different wording depending on who you ask:
1. Objects move at constant velocity as long as there is no net force acting upon them. Velocity is not the same as speed, as it also includes direction and is therefore a vector quantity (usually notated in bold). Also, zero is a perfectly valid value for a constant velocity.
2. If there is a net force acting upon an object this will cause it to accelerate, according to the relation $$\mathbf{F} = m\boldsymbol{a}$$.
3. Every action produces a reaction of equal magnitude and opposite direction. So if a certain object A pushes or pulls on B, B will answer with a push or pull of its own. This is usually notated like this: $$\mathbf{F_{AB}} = -\mathbf{F_{BA}}$$.
The whole of Classical Mechanics emerges from these three laws, though by far the one used the most in calculations is the second one. At the high school level, this usually means doing lots of trigonometry for setups such as the following, which may distress some readers:

A typical problem in mechanics is to figure out the equation of motion of a body, given some initial conditions. We begin with some information about the object’s starting position, forces and constraints it is subjected to, and work our way up to the equation that will tell us how the object will actually move thereafter. In the case of Newton’s Second Law, all solutions are essentially variations on solving the differential equation $$\mathbf{F} = m\mathbf{a} = m\frac{\mathrm{d} \mathbf{v}}{\mathrm{d} t}= m\frac{\mathrm{d} }{\mathrm{d} t}\frac{\mathrm{d} \mathbf{x}}{\mathrm{d} t}=m\mathbf{\ddot{x}},$$ which would yield x as a function of t, or x=x( t ).

Unfortunately, most real world problems are not as clear cut as blocks on inclined planes, and Newton’s Laws are utterly impractical in their original formulation for solving anything but the most simple physical systems. Fortunately, there exist a couple of alternative approaches that manage to elegantly generalize Newton’s Laws so that they’re applicable to nearly any classical system one can think of, at the cost of introducing some abstraction. These approaches are absolutely equivalent to Newton’s Laws, and indeed incorporate them at their core, but their mathematical appearance is quite different.

#### Lagrangian Mechanics

If we think of space in three dimensions, then the position of a particle at any given moment can be described by a position vector from the origin, with individual components in the x, y, and z directions: $$\mathbf{r}=(x,y,z)$$. The path that the particle will take over time will once again depend on the forces, constraints, and initial conditions it is subjected to. So, what we’re looking for is the way that $$\mathbf{r}$$ will evolve over time, $$\mathbf{r}= \mathbf{r}(t)$$.

However, working with cartesian coordinates (x,y,z) doesn’t help very much when, in general, physical systems aren’t easily describable by them. So instead, we introduce some abstraction and think of generalized coordinates, each of which we call $$q_{i}$$. Each one of these coordinates could be cartesian $$(x,y,z)$$, cylindrical $$(\rho ,\theta ,z)$$, spherical $$(\rho ,\theta ,\phi)$$, or even other ways of placing a particle in space, such as a distance traveled along a constrained path, or an angle defined by the movement of a particle, or anything that suits us. Each generalized coordinate can also change in time, yielding a generalized velocity, and these are denoted using the dot notation for derivatives as $$\dot{q}_{i}$$. By a simple extension, we can speak of other generalized quantities, such as generalized momentum $$p_{i} = \frac{\partial L}{\partial \dot{q}_{i}}$$. This particular quantity will come in handy in later on.

A Lagrangian is defined as the difference of the kinetic and potential energies of the system in question, and it will have the following form: $$L = \frac{1}{2}m\mathbf{\dot{r}}^{2}-U(\mathbf{r}).$$ The function U corresponds to the potential energy, and in general it will depend on the particle’s position. The first term is the familiar kinetic energy term $$\frac{1}{2}m\mathbf{v}^{2}$$ from kindergarten, with the velocity expressed in terms of r.

Notice that the Lagrangian depends on the generalized coordinates and velocities, since each r is defined in those terms. L being a vector equation, we can separate the different $$q_{i}$$’s and their velocities into what are known as the Euler-Lagrange equations, which can be conveniently abbreviated as $$\frac{\partial L}{\partial q_{i}} = \frac{\mathrm{d} }{\mathrm{d} t}\frac{\partial L}{\partial \dot{q_{i}}}.$$
So the rough strategy for solving problems in the Lagrangian formulation of Classical Mechanics is this: write L explicitly in terms of your generalized coordinates and velocities, making sure to include the specific (mathematical) description of U as well if it’s available. Then, plug the resulting expression for L into the Euler-Lagrange equation for as many coordinates as you have, perform the corresponding derivatives, and finally integrate whatever is left to solve each equation (i.e., get rid of whatever time derivatives are left over after you plug things in). If you’re successful, you will end up with as many equations of motion as you had generalized coordinates, and those equations of motion combine to give you the overall motion of the particle.

There are many nuances and neat things to go into with regards to the Lagrangian approach, but I’ll leave them aside for now. As a summary, notice that you end up with a second-order differential equation for each coordinate involved, and also notice that the setup for solving a problem begins with considerations of energy rather than forces. One important consequence of this is that any forces of constraint that may act on the object are naturally incorporated into the equations, without the necessity of force diagrams.

#### Hamiltonian Mechanics

A second approach to generalizing Newton’s laws is that of Hamiltonian Mechanics, which is a similar abstraction to that of Lagrange. First, we remember the concept of a generalized momentum, and also consider that for many systems the Lagrangian doesn’t depend explicitly on time $$\frac{\partial L}{\partial t} = 0.$$ When this is the case, we can define another quantity, the Hamiltonian, as $$H = \sum_{i=1}^{n}p_{i}\dot{q}_{i} – L.$$In addition, if the relationship between generalized and cartesian coordinates doesn’t depend on time either, the Hamiltonian is equal to the sum of the kinetic and potential energies of the system: $$H = T + U .$$In the same way that we used L in the Lagrangian formulation to derive our equations of motion, the Hamiltonian formulation relies on operating on H. In this case, the Hamiltonian is plugged into the equations $$\dot{q}_{i} = \frac{\partial H}{\partial p_{i}}\: ,\: \dot{p}_{i} = -\frac{\partial H}{\partial q_{i}}$$ to yield the equations of motion. This may seem like more work than the Lagrangian approach, but notice that we are left with sets of first-degree differential equations instead of second-degree ones. Even though we have twice as many equations as the Lagrangian approach, they are usually trivial to solve, and they include all the advantages of the Euler equations as far as dealing with constraints.

Hamiltonian mechanics in particular is important for later use in Quantum Mechanics and, as was the case with the Lagrangian formulation, there’s many details and asides that I left out for the sake of brevity. Both formulations are usually overkill for problems about blocks sliding down incline planes, but they become indispensable when working with more complicated systems. As I re-study mechanics for my PhD, I will try to post more on the details of each of these approaches, as well as practical examples of their use.

This post was the result of summarizing some of my notes on the subject, but obviously you would do well to look up these topics online. The Wikipedia entries are quite good, and then there are several recommendable textbooks. First, the Wiki links:
Newtonian Mechanics
Lagrangian Mechanics
Hamiltonian Mechanics
Books that I’m familiar with include the following:
1) Taylor, John R., Classical Mechanics. Great for undergraduate level students and laymen with calculus background. Informal, conversational style.
2) Goldstein, H. Classical Mechanics. Standard graduate text for students who want to get serious and be grown-ups. Very long-winded at times, but solid.
3) Landau & Lifshitz, Mechanics. Standard graduate text for masochists and people who like their textbooks lean and mean.


text:
# 4 The existence theorem and the formal theory of modules

Grothendieck, A. “Technique de descente et théorèmes d’existence en géométrie algébrique, II: Le théorème d’existence et théorie formelle des modules”. Séminaire Bourbaki 12 (1959–60), Talk no. 195.

([Trans.] Sections 4.1 to 4.5 were numbered A.1 to A.5 in the original; sections 4.6 to 4.10 were numbered C.1 to C.5.)

## 4.1 Representable functors

Let {\mathcal{C}} be a category. For all X\in{\mathcal{C}}, let h_X be the contravariant functor from {\mathcal{C}} to the category \mathtt{Set} of sets given by \begin{aligned} h_X\colon {\mathcal{C}} &\to \mathtt{Set} \\Y&\mapsto \operatorname{Hom}(Y,X). \end{aligned} If we have a morphism X\to X' in {\mathcal{C}}, then this evidently induces a morphism h_X\to h_{X'} of functors; h_X is a covariant functor in X, i.e. we have defined a canonical covariant functor h\colon {\mathcal{C}} \to \operatorname{Hom}({\mathcal{C}}^o,\mathtt{Set}) from {\mathcal{C}} to the category of covariant functors from the dual {\mathcal{C}}^o of {\mathcal{C}} to the category of sets. We then recall:

This functor h is faithfully flat; in other words, for every pair X,X' of objects of {\mathcal{C}}, the natural map \operatorname{Hom}(X,X') \to \operatorname{Hom}(h_X,h_{X'}) is bijective.

In particular, if a functor F\in\operatorname{Hom}({\mathcal{C}}^o,\mathtt{Set}) is isomorphic to a functor of the form h_X, then X is determined up to unique isomorphism. We then say that the functor F is representable. The above proposition then implies that the canonical functor h defines an equivalence between the category {\mathcal{C}} and the full subcategory of \operatorname{Hom}({\mathcal{C}}^o,\mathtt{Set}) consisting of representable functors. This fact is the basis of the idea of a “solution of a universal problem”, with such a problem always consisting of examining if a given (contravariant, as here, or covariant, in the dual case) functor from {\mathcal{C}} to \mathtt{Set} is representable. Note further that, even by the definition of products in a category [9], the functor h\colon X\mapsto h_X commutes with products whenever they exist (and, more generally, with finite or infinite projective limits, and, in particular, with fibred products, taking “kernels” [11], etc., whenever such things exist): we have an isomorphism of functors h_{X\times X'} \xrightarrow{\sim}h_X\times h_{X'} whenever X\times X' exists, i.e. we have functorial (in Y) bijections h_{X\times X'} \xrightarrow{\sim}h_X(Y)\times h_{X'}(Y). In particular, the data of a morphism X\times X' \to X'' in {\mathcal{C}} (i.e. of a “composition law” in {\mathcal{C}} between X, X', and X'') is equivalent to the data of a morphism h_{X\times X'}=h_X\times h_{X'}\to h_{X''}, i.e. to the data, for all Y\in{\mathcal{C}}, of a composition law of sets h_X(Y)\times h_{X'}(Y) \to h_{X''}(Y) such that, for every morphism Y\to Y' in {\mathcal{C}}, the system of set maps h_{X^{(i)}}(Y) \to h_{X^{(i)}}(Y') \qquad\text{(for }i=0,1,2\text{)} is a morphism for the two composition laws, with respect to Y and Y'. In this way, we see that the idea of a “{\mathcal{C}}-group” structure, or a “{\mathcal{C}}-ring” structure, etc. on an object X of {\mathcal{C}} can be expressed in the most manageable way (in theory as much as in practice) by saying that, for every Y\in{\mathcal{C}}, we have a group law (resp. ring law, etc.) in the usual sense on the set h_X(Y), with the maps h_X(Y)\to h_X(Y') corresponding to morphisms Y\to Y' that should be group homomorphisms (resp. ring homomorphisms, etc.). This is the most intuitive and manageable way of defining, for example, the various classical groups \operatorname{G_a}, \operatorname{G_m}, \operatorname{GL}(n), etc. on a prescheme S over an arbitrary base, and of writing the classical relations between these groups, or of placing a “vector bundle” structure on the affine scheme V({\mathscr{F}}) over S defined by a quasi-coherent sheaf {\mathscr{F}}, and of defining and studying the many associated flag varieties (Grassmannians, projective bundles), etc.; the general yoga is purely and simply identifying, using the canonical functor h, the objects of {\mathcal{C}} with particular contravariant functors (namely, representable functors) from {\mathcal{C}} to the category of sets.

The usual procedure of reversing the arrows that is necessary, for example, in the case of affine schemes in order to pass from the geometric language to the language of commutative algebra, leads us to dualise the above considerations, and, in particular, to also introduce covariant representable functors {\mathcal{C}}\to\mathtt{Set}, i.e. those of the form Y\mapsto\operatorname{Hom}(X,Y)=h'_X(Y).

## 4.2 Pro-representable functors, pro-objects

Let {\mathcal{X}}=(X_i)_{i\in I} be a projective system of objects of {\mathcal{C}}; there is a corresponding covariant functor h'_{{\mathcal{X}}} = \varinjlim_i h'_{X_i} which can be written more explicitly as h'_{{\mathcal{X}}}(Y) = \varinjlim_i h'_{X_i}(Y) = \varinjlim_i\operatorname{Hom}(X_i,Y) which is a functor from {\mathcal{C}} to \mathtt{Set}. A functor from {\mathcal{C}} to \mathtt{Set} that is isomorphic to a functor of this type with I filtered is said to be pro-representable. By the previous section, these are exactly the functors that are isomorphic to filtered inductive limits of representable functors. Let {\mathcal{X}}'=(X_j)_{j\in J} be another filtered projective system in {\mathcal{C}} (indexed by another filtered pre-ordered set of indices J). Then we can easily show that we have a canonical bijection \operatorname{Hom}(h_{{\mathcal{X}}'},h_{{\mathcal{X}}}) = \varprojlim_j\varinjlim_i\operatorname{Hom}(X_i,X'_j) (generalising §A, Proposition 1). This leads to introducing the category \operatorname{Pro}({\mathcal{C}}) of pro-objects of {\mathcal{C}}, whose objects are projective systems of objects of {\mathcal{C}} (indexed by arbitrary filtered pre-ordered sets of indices), and whose morphisms between objects {\mathcal{X}}=(X_i)_{i\in I} and {\mathcal{X}}'=(X_j)_{j\in J} are given by \operatorname{Pro}\operatorname{Hom}({\mathcal{X}},{\mathcal{X}}') = \varprojlim_j\varinjlim_i\operatorname{Hom}(X_i,X'_j), with the composition of pro-homomorphisms being evident. By the very construction itself, {\mathcal{X}}\mapsto h'_{{\mathcal{X}}} can be considered as a contravariant functor in {\mathcal{X}}, establishing an equivalence between the dual category of the category \operatorname{Pro}({\mathcal{C}}) of pro-objects of {\mathcal{C}} and the category of pro-representable covariant functors from {\mathcal{C}} to \mathtt{Set}. Of course, an object X of {\mathcal{C}} canonically defines a pro-object, denoted again by X, so that {\mathcal{C}} is equivalent to a full subcategory of \operatorname{Pro}({\mathcal{C}}). Then, if {\mathcal{X}}=(X_i)_{i\in I} is an arbitrary pro-object of {\mathcal{C}}, then (with the above identification) we have that {\mathcal{X}} = \varprojlim_i X_i with the projective limit being taken in \operatorname{Pro}({\mathcal{C}}) (since h_{{\mathcal{X}}}=\varinjlim_i h_{X_i}).

We draw attention to the fact that, even if the projective limit of the X_i exists in {\mathcal{C}}, it will generally not be isomorphic to the projective limit {\mathcal{X}} in \operatorname{Pro}({\mathcal{C}}), as is already evident in the case where {\mathcal{C}} is the category of sets. We note that, by the definition itself, \varprojlim{}_{{\mathcal{C}}}X_i=L is defined by the condition that the functor \varprojlim_i\operatorname{Hom}_{{\mathcal{C}}}(Y,X_i)=\operatorname{Hom}_{\operatorname{Pro}({\mathcal{C}})}(Y,{\mathcal{X}}) in Y\in{\mathcal{C}} and with values in \mathtt{Set} be representable via {\mathcal{L}}, i.e. that it be isomorphic to \operatorname{Hom}_{{\mathcal{C}}}(Y,{\mathcal{L}}); then \lim{}_{{\mathcal{C}}}X_i is already defined in terms of the pro-object {\mathcal{X}}, and, in a precise way, depends functorially on the pro-object {\mathcal{X}} whenever it is defined; there is therefore no problem with denoting it by \lim{}_{{\mathcal{C}}}({\mathcal{X}}). If projective limits in {\mathcal{C}} always exist, then \lim{}_{{\mathcal{C}}}({\mathcal{X}}) is a functor from \operatorname{Pro}({\mathcal{C}}) to {\mathcal{C}}, and there is a canonical homomorphism of functors \lim_{\mathcal{C}}({\mathcal{X}})\to{\mathcal{X}}. Since every (covariant, say, for simplicity) functor F\colon {\mathcal{C}} \to {\mathcal{C}}' can be extended in an obvious way to a functor \operatorname{Pro}(F)\colon \operatorname{Pro}({\mathcal{C}}) \to \operatorname{Pro}({\mathcal{C}}'), it follows that, if projective limits always exist in {\mathcal{C}}', then F also canonically defines a composite functor \overline{F} = \varprojlim{}_{{\mathcal{C}}'}\colon \operatorname{Pro}({\mathcal{C}}) \to {\mathcal{C}}' sending {\mathcal{X}}=(X_i)_{i\in I} to \varprojlim{}_{{\mathcal{C}}'}F(X_i).

A pro-object {\mathcal{X}} is said to be a strict pro-object if it is isomorphic to a pro-object (X_i)_{i\in I}, where the transition morphisms X_i\to X_j are epimorphisms; a functor defined by such an object is said to be strictly pro-representable. We can thus further demand that I be a filtered ordered set, and that every epimorphism X_i\to X' be equivalent to an epimorphism X_i\to X_j for some suitable j\in I (uniquely determined by this condition). Under these conditions, the projective system (X_i)_{i\in I} is determined up to unique isomorphism (in the usual sense of isomorphisms of projective systems). It thus follows that the projective limit of a projective system {\mathcal{X}}^{(\alpha)} of strict pro-objects always exists in \operatorname{Pro}({\mathcal{C}}), and that, with the above notation of F and \overline{F}, we have that \overline{F}\varprojlim_\alpha{\mathcal{X}}^{(\alpha)} = \varprojlim_\alpha{}_{{\mathcal{C}}'}F(X^{(\alpha)}). In particular, if every pro-object of {\mathcal{C}} is strict (cf. the previous section), then the extended functor \overline{F} commutes with projective limits.

## 4.3 Characterisation of pro-representable functors

Let {\mathcal{C}} and {\mathcal{C}}' be categories in which all finite projective limits (i.e. limits over finite, not necessarily filtered, pre-ordered sets) exist, or, equivalently, in which finite products and finite fibred products exist (which implies, in particular, the exists of a “right-unit object” e such that \operatorname{Hom}(X,e) consists of only on element for all X). Let F be a covariant functor from {\mathcal{C}} to {\mathcal{C}}'. Then the following conditions are equivalent:

1. F commutes with finite projective limits;
2. F commutes with finite products and with finite fibred products;
3. F commutes with finite products, and, for every exact diagram X\to X'\rightrightarrows X'' in {\mathcal{C}} (cf. [12, A, Definition 2.1]), the image of the diagram under F F(X)\to F(X')\rightrightarrows F(X'') is exact.

We then say that F is left exact.

In what follows, we assume that finite projective limits always exist in {\mathcal{C}}. It is then immediate from the definitions that a representable functor is left exact, and, by taking the limit, that a pro-representable functor is left exact.

To obtain a converse, let F\colon {\mathcal{C}} \to \mathtt{Set} be a covariant functor, and let X\in{\mathcal{C}} and \xi\in F(X). We say that \xi (or the pair (X,\xi)) is minimal if, for all X'\in{\mathcal{C}} and all \xi'\in F(X'), and for every strict monomorphism (cf. [12, A, §2]) u\colon X'\to X such that \xi=F(u)(\xi'), u is an isomorphism. We also say that a pair (X,\xi) dominates (X'',\xi'') (where xi\in F(X) and \xi''\in F(X'')) if there exists a morphism v\colon X\to X'' such that \xi''=F(v)(\xi); if \xi is minimal, and if F is left exact, then this morphism v is unique; if \xi'' is minimal, then v is surjective. From this we easily deduce the following proposition:

For F to be strictly pro-representable, it is necessary and sufficient for it to satisfy the following two conditions:

1. F is left exact; and
2. every pair (X,\xi), with \xi\in F(X), is dominated by some minimal pair.

This second condition is trivial if every object of {\mathcal{C}} is Artinian (by taking a sub-object X' of X that is minimal amongst those for which there exists some \xi'\in F(X') such that \xi is the image of \xi'). Whence:

Let {\mathcal{C}} be a category whose objects are all Artinian and in which all finite projective limits exist. Then the pro-representable functors from {\mathcal{C}} to \mathtt{Set} are exactly the left exact functors, and they are in fact strictly pro-representable.

This last fact also implies that every pro-object of {\mathcal{C}} is then strict.

## 4.4 Example: groups of Galois type, pro-algebraic groups

If {\mathcal{C}} is the category of ordinary finite groups, then \operatorname{Pro}({\mathcal{C}}) is equivalent to the category of totally disconnected compact topological9 groups. It is groups of this type, and their generalisations, obtained by replacing ordinary finite groups with schemes of finite groups over a given base prescheme (for example, finite algebraic groups over a field k), that serve as fundamental groups, homotopy groups, and absolute and relative homology groups for preschemes. In all these examples, the corollary to Proposition 3.1 applies, and it is indeed by the associated functor that the \pi_1 should be defined [11]. It is the same if we start with the category of algebraic or quasi-algebraic groups over a field (or, more generally, over a Noetherian prescheme): we recover the “pro-algebraic groups” of Serre [27].

## 4.5 Example: “formal varieties”

Let \Lambda be a Noetherian ring, {\mathcal{C}} the category of \Lambda-algebras that are Artinian modules of finite type over \Lambda (or, more concisely, Artinian \Lambda-algebras). The conditions of the corollary to Proposition 3.1 are then satisfied. Here, the category \operatorname{Pro}({\mathcal{C}}) is equivalent to the category of topological algebras O over \Lambda that are isomorphic to topological projective limits O = \varprojlim O_i of algebras O_i\in{\mathcal{C}}, i.e. those whose topology is linear, separated, and complete, and such that, for every open ideal {\mathfrak{J}}_i of O, the algebra O/{\mathfrak{J}}_i is an Artinian algebra over \Lambda. The functor {\mathcal{C}}\to\mathtt{Set} associated to such an algebra is exactly \begin{aligned} F(A) &= h'_{O}(A) \\&= \{\text{continuous homomorphisms of topological }\Lambda\text{-algebras }O\to A\} \\&= \varinjlim_i \operatorname{Hom}_{\Lambda\text{-algebras}}(O_i,A). \end{aligned} Note also that the category {\mathcal{C}} is essentially the product of analogous categories, corresponding to the local rings that are the completions of the \Lambda_{{\mathfrak{m}}} for the maximal ideals {\mathfrak{m}} of \Lambda; we can thus, if so desired, restrict to the case where A is such a complete local ring. In any case, O decomposes canonically as the topological product of its local components, which correspond to the “points” of the formal scheme [11] defined by O. Such a point is defined by an object \xi of some F(K), where K\in{\mathcal{C}} is a field (for example, the residue field of the local component in question), and where two pairs (\xi,K) and (\xi',K') define the same point if and only if they are both dominated by the same (\xi'',K''), or if they both dominate the same (\xi''',K'''). (If the \Lambda/{\mathfrak{m}} are algebraically closed, then it suffices to take the set given by the sum of the F(\Lambda/{\mathfrak{m}})).

It is important to give conditions that ensure that the local component O_\xi of O corresponding to some \xi\in F(K) be a Noetherian ring. If \Lambda is a complete local ring (Noetherian, we recall), then it is equivalent to say that O_\xi is isomorphic to a quotient ring of a formal series ring \Lambda[[t_1,\ldots,t_n]]. To give such a criteria, we introduce (for every ring A) the A-algebra I_A of “dual numbers” of A, defined by I_A = A[t]/t^2A[t]. Let \varepsilon\colon I_A\to A be the augmentation homomorphism, which defines (if A\in{\mathcal{C}}) a map F(\varepsilon)\colon F(I_A) \to F(A). Using the fact that F is left exact, we intrinsically define the structure of an A-module on the subset F(I_A,\xi) = F(\xi)^{-1}(\xi) \subset F(I_A) consisting of the \xi'\in F(I_A) that are “reducible along \xi”; using the explicit form of F in terms of O, we find that this K-module can be identified with \operatorname{Hom}_\Lambda({\mathfrak{m}}_\xi/{\mathfrak{m}}_\xi^2,A, where m_\xi is the kernel of the homomorphism \xi\colon O\to A, i.e. if A is a field, then the maximal ideal of the local component O_\xi of O. From this, we immediately deduce the following proposition:

Let \xi\in F(K), where K\in{\mathcal{C}} is a field. For the corresponding local component O_\xi of O to be a Noetherian ring, it is necessary and sufficient for the set F(I_K,\xi) of elements of F(I_K) that are reducible along \xi to be a vector space of finite dimension over K. Under these conditions, we have a canonical isomorphism F(I_K,\xi) = \operatorname{Hom}({\mathfrak{m}}_\xi/{\mathfrak{m}}_\xi^2+{\mathfrak{n}}_\xi{\mathscr{O}}_\xi, K) (where {\mathfrak{n}}_\xi is the maximal ideal of \Lambda given by the kernel of the homomorphism \Lambda\to K), and so, in particular, the dimension of the K-vector space F(I_K,\xi) is equal to the dimension of the vector space {\mathfrak{m}}_\xi/{\mathfrak{m}}_\xi^2 over the field O_\xi/{\mathfrak{m}}_\xi=K(\xi).

[Comp.] The formula given above is only correct when \Lambda is a field; in the general case, we must replace {\mathfrak{m}}_\xi/{\mathfrak{m}}_\xi^2 with the quotient of this space by the image of {\mathfrak{n}}_\xi/{\mathfrak{n}}_\xi^2, where {\mathfrak{n}} is the maximal ideal of \Lambda.

Suppose that O_\xi is Noetherian, and suppose, for notational simplicity, that \Lambda is complete and local, and that O=O_\xi. ([Comp.] The following definition is correct only when the residue extension k'/k is separable; for the general case, see SGA III, 1.1.) We say that O is simple over \Lambda if O is a finite and étale algebra over the completion algebra of the localisation of \Lambda[t_1,\ldots,t_n] at one of its maximal ideals that induces the maximal ideal of \Lambda; if the residue extension of O over \Lambda is trivial (for example, if the residue field of \Lambda is algebraically closed), then this is equivalent to saying that O itself is isomorphic to such a formal series algebra. Finally, if we no longer necessarily suppose that O is Noetherian, then we again say that O is simple over \Lambda if O is isomorphic to a topological projective limit of quotient \Lambda-algebras that are Noetherian and \Lambda-simple in the above sense. We can immediately generalise to the case where \Lambda and O are no longer assumed to be local. With this, we have the following proposition:

For O to be simple over \Lambda, it is necessary and sufficient for the associated functor F to send epimorphisms to epimorphisms.

If this is the case, then this implies that, for every surjective homomorphism A\to A' in {\mathcal{C}}, the morphism F(A)\to F(A') is also surjective. Of course, it suffices to verify this condition in the case where A is local, and (proceeding step-by-step) where the ideal of A given by the kernel of A\to A' is annihilated by the maximal ideal of A. This leads, in practice, to verifying that a certain obstruction, linked to infinitesimal invariants of the situation that give us a functor F, is null; this is a problem of a cohomological nature.

To finish, we say some words, in the above context, about rings of definition. Let F still be a functor from {\mathcal{C}} to \mathtt{Set}, assumed to be pro-representable via a topological \Lambda-algebra O. Then, for every A\in{\mathcal{C}} and every \xi\in F(A), there exists a smallest subring A' of A such that \xi is the image of an element \xi' of F(A') (which is then uniquely determined): indeed, it suffices to think of \xi as a homomorphism from O to A, and to take A' to be the image of O under this \xi. We then say that A' is the ring of definition of the object \xi\in F(A). If u\colon A\to B is an algebra homomorphism, and if \eta=F(u)(\xi), then the ring of definition of \eta is the image under u of the ring of definition of \xi. If we start with a functor F from {\mathcal{C}} to \mathtt{Set}, then the existence of rings of definition, along with their properties that we have just discussed, is more or less equivalent to the condition that F be pro-representable; that is, they are usually far from being trivial.

## B. The two existence theorems

Keeping the notation of §A.5, and, given a covariant functor F\colon {\mathcal{C}} \to \mathtt{Set}, we wish to find manageable criteria for F to be pro-representable, i.e. expressible via a \Lambda-algebra O as above. By the corollary of Proposition 3.1, to ensure this, it is necessary and sufficient for F to be left exact. In the current state of the technique of descent (cf. the questions asked in [12]), this criterion is not directly verifiable, in this form, in the most important cases, and we need criteria that seem less demanding.

For the functor F to be pro-representable, it is necessary and sufficient for it to satisfy the two followings conditions:

1. F commutes with finite products;
2. for every algebra A\in{\mathcal{C}} and every homomorphism A\to A' in {\mathcal{C}} such that the diagram A \to A' \rightrightarrows A'\otimes_A A' is exact (cf. [12, A, Definition 1.2]), the diagram F(A) \to F(A') \rightrightarrows F(A'\otimes_A A') is also exact.

Furthermore, it suffices to verify condition (ii) in the case where A is local, and when, further, we are in one of the two following cases:

1. A is a free module over A;
2. the quotient module A'/A is an A-module of length 1.

The proof of this theorem is rather delicate, and cannot be sketched here. We content ourselves with pointing out that it relies essentially on a study of equivalence relations (in the sense of categories) in the spectrum of an Artinian algebra (the study of which poses even more problems, whose solutions seems essential for the further development of the theory).

In applications, the verification of condition (i) is always trivial. The verification of condition (ii) splits into two cases: case (a), where A' is a free A-module, can be dealt with using the technique of descent by flat morphisms (cf. [12, Theorems 1, 2, and 3]), which offers no difficulty; to deal with case (b), we will use the following result:

Let A be a local Artinian ring with maximal ideal {\mathfrak{m}}, and let A' be an A-algebra containing A, and such that {\mathfrak{m}}A'\subset A, and A\to A'\rightrightarrows A'\otimes_A A' is exact (which is the case, in particular, if A'/A is an A-module of length 1). Let {\mathcal{F}} be the fibred category (cf. [12, A, Definition 1.1]) of quasi-coherent sheaves that are flat over varying preschemes. Then the morphism \operatorname{Spec}(A')\to\operatorname{Spec}(A) is a strict {\mathcal{F}}-descent morphism (cf. [12, A, Definition 1.7]).

In other words, the data of a flat A-module M is completely equivalent to the data of a flat A'-module M' endowed with an (A'\otimes_A A')-isomorphism from M'\otimes_A A' to A'\otimes_A M' satisfying the usual transitivity condition for a descent data (loc. cit.).

We prove Theorem 2 by first proving that \operatorname{H}^i(A'/A,\operatorname{G_a}) = 0 \qquad\text{(for }i\geqslant 1\text{)} (cf. [12]), with the hypothesis that {\mathfrak{m}}A'\subset A allowing us to easily reduce to the case where A is a field (namely A/{\mathfrak{m}}). We can then apply the equivalences described in [12].

## 4.6 General remarks on functors represented by preschemes

Let S be a locally Noetherian prescheme. A prescheme X over S is said to be locally of finite type over S if, for all x\in X that project to y\in Y, there exists an affine neighbourhood of y of ring A, and an affine neighbourhood of x (over the aforementioned affine neighbourhood of y) of ring B, such that B is an A-algebra of finite type. There are many important examples of preschemes locally of finite type over S, that are not of finite type over S, given by solutions of classical universal problems; thus it is important to be able to consider the Picard scheme of a curve as a union of infinitely-many connected components (that we must avoid confusing with the connected component of the identity element, i.e. the “Picard variety”). It is thus sometimes useful to place ourselves in the category {\mathcal{C}} of preschemes locally of finite type over S, in order to study the question of representability of a contravariant functor F. The main goal of these articles is to develop a general technique that allows us to recognise when such a functor F is representable, and to study the properties of the corresponding S-prescheme X by means of the properties of F. We note in passing that, in this study, we find non-pathological examples of preschemes over S that are not separated over S, notably as “Picard preschemes” of excellent S-schemes; we must thus refrain from banishing preschemes that are not schemes from algebraic geometry.

Let X be a prescheme locally of finite type over S, and let F\colon Y \mapsto \operatorname{Hom}_S(Y,X) be the associated contravariant functor. We can consider the restriction F_0 of F to the subcategory {\mathcal{C}}_0 of {\mathcal{C}} consisting of preschemes Y over S that are Artinian and finite over S: if S=\operatorname{Spec}(\Lambda), then {\mathcal{C}}_0 is the category dual to the category of Artinian \Gamma-algebras considered in §B. If Y=\operatorname{Spec}(A), where A is a local Artinian ring, then Y consists of a single point y living above a closed point s of S, and an S-homomorphism from Y to X (i.e. an element of F(Y)) is defined by the data of a point x\in X over s, along with an {\mathscr{O}}_s-homomorphism from {\mathscr{O}}_x to A. If there exists such a homomorphism, then x is necessarily a closed point of X (since its residue field is algebraic over the residue field of s). This thus shows that the restriction F_0 of F to “Artinian Y-algebras” is pro-representable, and is represented by the topological Y-algebra whose local components are the completions \widehat{{\mathscr{O}}_x} of the local rings of X at the points x of X that are closed and live above closed points of Y. This shows that only knowing F_0 gives precise information about the structure of X (that is, the structure of the completions of its local rings at the aforementioned points). We note that, even in the case where S is the spectrum of an algebraically closed field, it is only thanks to the systematic consideration of “varieties” Y such that {\mathscr{O}}_Y may admit nilpotent elements (and, in particular, working with the spectra of local Artinian rings) that we can arrive at the “good formulation” of classical universal problems, and understand the “infinitesimal” aspect.

If we start with a given functor F, and we want to know whether or not it is representable, then studying the functor F_0 (using Theorem 1 and Theorem 2) will give quasi-complete hints; either, as is often the case (by simply testing, for example, the nature of the sets F(I_K,\xi) and their functorial behaviour, cf. §A), F_0 is already not pro-representable (which explains the failure of attempts made up until now to define varieties of modules in a reasonably natural way for the classification of vector bundles of rank >1); or we might be able to show that F_0 is indeed representable, but that that vector spaces F(I_K,\xi) are not of finite dimension, in which case we must be content with the “formal” solution; or it could be the case that F_0 is indeed representable by a product of complete Noetherian local rings, which gives very strong assumptions for F itself to be representable, and, combined with the analogous properties (but of a more global nature) that we will later develop, will in all likelihood suffice to imply that it is indeed so. Finally, we come across interesting geometric problems (see sections §C.4 and §C.5 below) where we have only the functor F_0 (not coming from any “global” functor F), and where we will consider ourselves content if we can associate to it a “formal scheme of modules”.

To finish these generalities, we note how the theory of schemes explains some apparent anomalies, such as the Igusa surface V whose “Picard variety” P consists of a single point, and for which, however, \operatorname{H}^1(V,{\mathscr{O}}_V)\neq0; in this case, P is a non-trivial “purely infinitesimal” group, i.e. defined by a local algebra {\mathscr{O}} of finite rank over the base field k and endowed with a diagonal map corresponding to the multiplicative structure of P; if {\mathfrak{m}} is the maximal ideal of {\mathscr{O}}, then the dual of {\mathfrak{m}}/{\mathfrak{m}}^2 is canonically isomorphic to \operatorname{H}^1(V,{\mathscr{O}}_V) (cf. section §C.3 below). It is only when the Picard group is an algebraic group in the classical sense (i.e. simple over the base field k) that the dimension of \operatorname{H}^1(V,{\mathscr{O}}_V) (which is always equal to that of {\mathfrak{m}}/{\mathfrak{m}}^2) is equal to that of the Picard group.

## 4.7 The schemes \underline{\operatorname{Hom}}_S(X,Y), \prod_{X/S}Z, \underline{\operatorname{Aut}}(X), etc.

Let X and Y be preschemes over S; for every prescheme T over S, let X_T=X\times_S T and Y_T=Y\times_S T, and consider the set F(T) = \operatorname{Hom}_T(X_T,Y_T) = \operatorname{Hom}_S(X_T,Y) = \operatorname{Hom}_S(X\times_S T,Y) as a contravariant functor in T. If it is representable, then we denote by \underline{\operatorname{Hom}}_S(X,Y) the prescheme over S that represents it, and we then have a functorial isomorphism \operatorname{Hom}_S(T,\underline{\operatorname{Hom}}_S(X,Y)) \xrightarrow{\sim}\operatorname{Hom}_S(T\times_S X,Y). There are variants of this universal problem, the solutions to which can be summarised as follows: a prescheme of S-automorphisms of an S-prescheme X (which will be a prescheme in groups), a prescheme of S-homomorphisms from an S-prescheme in groups to another (which will be a prescheme in commutative groups if the latter scheme in groups is commutative), etc. We can also generalise the definition of \underline{\operatorname{Hom}}_S(X,Y) by considering a prescheme Z over the prescheme X over S, and the functor F(T) = \operatorname{Hom}_{X_T}(X_T,Z_T) (the set of “sections” of Z_T over X_T); if this functor is representable, then the S-prescheme that represents it will be denoted by \Pi_{X/S}Z, and we will thus have, by definition, a functorial isomorphism \operatorname{Hom}_S(T,\Pi_{X/S}Z) = \operatorname{Hom}_{X_T}(X_T,Z_T). Setting Z=Y\times_S X, we recover \underline{\operatorname{Hom}}_S(X,Y). From these definitions follows a formula for the new preschemes thus introduced that is as trivial as it is useful, that we will not give here (given that it holds in every category where products and fibred products exist). More serious is the question of existence of schemes of the type \underline{\operatorname{Hom}}_S(X,Y). We note first of all that, for fixed X, \underline{\operatorname{Hom}}_S(X,Y) (resp. \Pi_{X/S}Z) can only exist for all Y over S (resp. for all Z over X) if X is flat over S. Furthermore, we can convince ourselves that it is not reasonable to expect the existence of a solution, for general enough Y, except in the case where X is further proper over S. It seems, however, that these conditions are sufficient for the existence of \underline{\operatorname{Hom}}_S(X,Y) and \Pi_{X/S}Z, with the condition that, if necessary, we make some sort of “quasi-projective” hypothesis on Y/S (resp. Z/X); this is what we can verify anyway in numerous cases (for example, when Y is affine over S, or, by direct elementary constructions, when X is finite over S). Here is what Theorem 1 and Theorem 2 give:

Let \Lambda be a Noetherian ring, and X and Y arbitrary preschemes over \Lambda. Consider the functor F(A) = \operatorname{Hom}_A(X_A,Y_A) on the category {\mathcal{C}}_0 of Artinian \Lambda-algebras. If X is flat over \Lambda, then this functor is pro-representable.

Furthermore, we can show that, for all A\in{\mathcal{C}}_0 and all \xi\in F(A), we have a canonical isomorphism F(I_A,\xi) = \operatorname{H}^1\Big(X_A,\underline{\operatorname{Hom}}_{{\mathscr{O}}_{X_A}}\big(\xi^*(\Omega_{Y_A/A}^1),{\mathscr{O}}_{X_A}\big)\Big) where \Omega_{Y_A/A}^1 is the sheaf of K"{a}hler 1-differentials of Y_A with respect to A. Taking A to be a field, we find, using §A, Proposition 5.1 and the finiteness theorem from [11], the following corollary:

Suppose that X is flat and proper over S, and that Y is of finite type over S. Then F is pro-representable, and the local components of the corresponding topological \Lambda-algebra are Noetherian rings.

The problems considered in this section, and many others, having been generally studied, in the framework of classical algebraic geometry, via the “Chow coordinates” of cycles in projective space, allow us to consider these cycles as points of suitable projective varieties. This procedure, and, more generally, the use of Chow coordinates, seems irredeemably insufficient from the point of view of schemes, since it destroys the nilpotent elements in the parameterised varieties, and, in particular, do not lend themselves to a satisfying study of infinitesimal variations of cycles (without taking its non-intrinsic nature, linked to the projective space, into account). The language of Chow coordinates has sadly been the only one used by many algebraic geometers for the study of families of varieties or families of cycles, which seems to have been a serious obstacle to the understanding of these notions, despite its certain technical interest (probably temporary). If we wish to obtain the analogue of Chow varieties in the theory of schemes, we are led to the following universal problem: let X be a prescheme over S, and, for every prescheme T over S, consider the set F(T) of closed sub-preschemes of X_T=X\times_S T that are flat over T; we want to represent this functor in T via some prescheme over S. More generally, we can start with a quasi-coherent sheaf {\mathscr{G}} on X, and take F(T) to be the set of quotient sheaves of {\mathscr{G}}_T that are flat over T. It seems that there exists a solution to this problem, with a scheme C that is locally of finite type over S, if X is proper over S, if S is locally Noetherian, and if F is furthermore coherent. In any case, supposing only that S is locally Noetherian, the restriction of F to “Artinian S-algebras” is pro-representable, and, if, furthermore, X is proper over S, and F is coherent, then the local components of the corresponding topological ring {\mathscr{O}} are Noetherian. Of course, even after having proven the existence of the “Chow scheme” of X over S, it remains to find a decomposition of it into disjoint open subsets C_i (corresponding to fixing continuous invariants, such as degree and dimension of the cycles that we vary) over S, as well as to make precise the relations between this scheme with the classical Chow varieties, and to make precise when a C_i is projective (or at least quasi-projective) over S.

[Comp.] The problems described here are completely resolved in the projective case by “Hilbert schemes” (cf. FGA 3.IV). Examples by Nagata and Hironaka show, however, that the functors described are not necessarily representable if we do not make the projective hypothesis, even if we restrict to the classification of subvarieties of dimension 0 of a complete non-singular variety of dimension 3; this is linked to the fact that the symmetric square of such a variety does not necessarily exist.

## 4.8 Picard schemes

[Comp.] For a more complete study, see FGA 3.V.

Let f\colon X\to S be an S-prescheme, and consider the multiplicative sheaf {\mathscr{O}}_X^* of units of the structure sheaf of X, along with the group P(X/S) = \operatorname{H}^0(S,\operatorname{R}^1f_*({\mathscr{O}}_X^*)), called the relative Picard group of X/S. An element of this group is thus defined by giving an open cover (U_i) of S, along with an invertible sheaf {\mathscr{L}}_i on each f^{-1}(U_i), such that {\mathscr{L}}_i|f^{-1}(U_i\cap U_j) is isomorphic to {\mathscr{L}}_j|f^{-1}(U_i\cap U_j) for all i,j, or, at least locally over U_i\cap U_j (i.e. these two sheaves are “equivalent” in the sense of [12]). If X/S admits a section, then P(X/S) is exactly the set of classes of invertible sheaves on X/S up to “equivalence” (loc. cit.). We now set, for all T over S, F(T) = P(X_T/T) which gives a covariant functor in T, that we call the Picard functor of X/S; if this functor is representable, then the prescheme over S that represents it is called the Picard prescheme of X/S, and denoted by {\mathscr{P}}(X/S). In this case, we then have an isomorphism of functors: \operatorname{Hom}_S(T,{\mathscr{P}}(X/S)) \xrightarrow{\sim}P(X_T/T). Taking the Picard prescheme is compatible with extension of the base, and, in particular, the Picard preschemes of the fibres of X over S (which are preschemes over the residue fields K(s) of the s\in S) are the fibres of {\mathscr{P}}(X/S). Of course, since P(X_T/T)=F(T) is a commutative group, the Picard preschemes are preschemes in groups. Note as well that the generalised Jacobians of Rosenlicht are exactly the connected components of the identity in the Picard schemes of complete curves (possibly with singularities), which should make most of their properties clear (once their existence has been proven).

The definition adopted here is only reasonable when every point of Y admits an open neighbourhood U over which X admits a section. In the general case, it is necessary to slightly modify the definition of the Picard functor in order to still obtain an existence theorem.

Here, the plausible existence conditions for a Picard prescheme are the following: X is proper and flat over S; f_*({\mathscr{O}}_X)={\mathscr{O}}_S; and X locally admits a section over S. This condition naturally arises in the application of the technique of descent, in eliminating the automorphisms of an invertible sheaf {\mathscr{L}} on X by endowing them with a marked section over the section s ([12]). Notably, we find the following:

Suppose that X is flat over S=\operatorname{Spec}(\Lambda), where \Lambda is Noetherian, and suppose that, for all T of finite type over S, we have {f_T}_*({\mathscr{O}}_{X_T})={\mathscr{O}}_T (if f is proper and separable and has separable fibres, or if S is the spectrum of a field, then it follows from K"{u}nneth that the latter condition is equivalent to f_*({\mathscr{O}}_X)={\mathscr{O}}_S). Then the Picard functor of X/S on the category of Artinian \Lambda-algebras is pro-representable.

Furthermore, we then have F(I_A,\xi) = \operatorname{H}^1(X_A,{\mathscr{O}}_{X_A}), and, in particular:

If X is proper over S, then the local components of the topological \Lambda-algebra corresponding to the Picard functor are Noetherian.

We can generalise the definitions and results from this section to the classification of principal bundles on X, with structure group G being a scheme in groups over S that is affine and flat over S, and also commutative. In the case where G would not be commutative, and thus where the adjoint bundle in groups of a principal bundle (whose sections of the automorphisms of the principal bundle) would no longer be trivial, Proposition 3.1 no longer holds true as it is stated. We can, however, modify the universal problem in such a way that we again obtain a solution (at least, for now, in formal geometry). The golden rule to remember, in the context of the current section and in the following, and every time we are looking for “schemes of modules” for classes of objects that are only defined up to isomorphism, is always the following: eliminate the possible automorphisms of the objects that we want to classify, by introducing, if necessary, auxiliary structures (points or elements of marked sections, fixing differential forms, etc.) that we take to be insignificant enough that we do not substantially modify the initial problem.

[Comp.] I have recently shown that the formal scheme of modules for an abelian variety over a field is indeed simple over the Witt ring, or, in other words, that every abelian scheme X over a local Artinian ring that is the quotient of another such scheme Y comes, by reduction, from an abelian scheme over Y. The proof simply uses the variance properties of the obstruction class of the covering, introduced in FGA II, p. 12. Recall also that the schemes of modules for curves of genus g or for polarised abelian schemes have been constructed by Mumford (cf. Séminaire Mumford–Tate, Harvard University (1961–62)).

## 4.9 Formal modules of a variety

Let \Lambda be a local Noetherian ring of residue field k (more often than not, \Lambda will be equal to k, or to a Cohen p-ring), and let X_0 be a prescheme over k. For every local Artinian \Lambda-algebra A, consider the set F(A) of isomorphism classes of A-preschemes X that are flat over A, endowed with an isomorphism

X\otimes_A\mathfrak{K}(A) \xleftarrow{\sim}X_0\otimes_k\mathfrak{K}(A) \tag{$*$}

where \mathfrak{K}(A) is the residue field of A; of course, the isomorphisms between such flat A-preschemes should respect the above isomorphism given in the structure. If A is a (not necessary local) Artinian \Lambda-algebra, with local components A_i, then we take F(A) to be the product of the F(A_i). Then F becomes a multiplicative functor in A, and we call it the functor of modules for X_0 (and \Lambda). If this functor is representable, then it has a corresponding local topological \Lambda-algebra O, of residue field k, and the formal spectrum of O is called the formal scheme of modules for X_0 (and \Lambda) (cf. [11] for some details on this).

Here, if we wish to apply the technique of descent, the “finite” automorphisms of X_0 are inoffensive, since they have no influence on the existence of automorphisms (in the precise sense above) of A-preschemes X; the necessary and sufficient condition, if A is not simply a field, for X to not have any non-trivial A-automorphisms is that \operatorname{H}^0(X_0,{\mathfrak{G}}_{X_0/k}) = 0 where {\mathfrak{G}}_{X_0/k} denotes the sheaf of k-derivations (i.e. the tangent sheaf) of X_0. We can easily show (at least, if X_0 is simple over k) that F(I_A,\xi) = \operatorname{H}^1(X_A,{\mathfrak{G}}_{X_A/A}). We thus conclude, as per usual:

Suppose that \operatorname{H}^0(X_0,{\mathfrak{G}}_{X_0/k})=0. Then the formal scheme of modules for X_0 exists. If, furthermore, X_0 is proper over k, then the formal scheme of modules is Noetherian.

1. If X_0 is not assumed to be simple over k, then F(I_A,\xi) can be identified with a sub-A-module of \operatorname{Ext}_{{\mathscr{O}}_{P_A}}^1(P_A;{\mathscr{I}}_{X_A},{\mathscr{O}}_{X_A}) where we set P_A=X_A\times_A X_A, where {\mathscr{O}}_{X_A} is considered as a coherent sheaf on P_A via the diagonal morphism X_A\to P_A, and where {\mathscr{I}}_{X_A} denotes the coherent sheaf of ideals on P_A defined by the diagonal morphism. More precisely, an easy globalisation of Hochschild theory shows that the \operatorname{Ext}^1 above can be identified with the set of classes, up to isomorphism, of sheaves of I_A-algebras {\mathscr{O}} that are flat over X_A, and endowed with an augmentation isomorphism {\mathscr{O}}\otimes_{I_A}A\to{\mathscr{O}}_{X_A} (recall that we set I_A=At/(t^2)). The submodule F(I_A,\xi) is that which corresponds to the sheaves of commutative algebras. The simplicity hypotheses are thus not essential in the theory of modules, as [11] implies.

2. Recall (loc. cit.) that, in particular, every simple and proper algebraic curve X_0 over k admits a formal scheme of modules that is simple over \Lambda, and of relative dimension equal to 3g-3 if the genus g is \geqslant 2, and to g if g=0,1. These two latter cases no longer figure directly in Proposition 4.1. We can, however, recover them in the case of elliptic curves (g=1) thanks to the remarks that will follow.

We can, of course, vary Proposition 4.1 ad libitum by considering systems of schemes over k endowed with various structures. Suppose, for example, that X_0 is an abelian scheme over k, with a marked origin (i.e. X_0 is considered as a scheme in groups over k), and let F(A) be the set of isomorphism classes of abelian schemes over A (i.e. of schemes in groups that are proper and simple over A) endowed with an isomorphism (*) of abelian schemes. We can show that imposing a multiplicative structure (or even only a “unit section”) eliminates the infinitesimal automorphisms, and that there thus exists a formal scheme of modules that corresponds to a complete local Noetherian ring O. We can also show that, if X is a proper and simple scheme with “absolutely connected” fibres over a locally Noetherian prescheme S, then every multiplicative structure on X that admits a unit section is necessarily associative and commutative (provided that it is associative and commutative on one fibre, and provided that S is connected), and is furthermore uniquely determined by the knowledge of the unit section. Further, supposing that S is the spectrum of a local Artinian ring A of residue field k, that X is proper over A and endowed with a section s, and finally that X\otimes_A k is endowed with the structure of an abelian scheme over k, admitting the point of X\otimes_A k corresponding to s as the zero element, an easy calculation of obstructions, combined with an argument due to Serre, allows us to prove that there exists on X a multiplicative structure admitting the section s as the unit section. (From here, using the “existence theorem” of [11] to pass to the case where A is complete local Noetherian, and then the technique of descent from [12] for the general case, we can prove the analogous claim for all locally Noetherian connected S). This proves that the functor F(A) considered here is isomorphic to the analogous functor defined at the start of this section by abstracting the multiplicative structure on X_0. It then follows that, in particular, if {\mathfrak{m}} is the maximal ideal of O, then {\mathfrak{m}}/{\mathfrak{m}}^2 is canonically isomorphic to the dual of \operatorname{H}^1(X_0,{\mathfrak{G}}_{X_0/k}), and is thus of dimension n^2, where n=\dim X_0. It would be very interesting to determine if O is indeed simple over \Lambda, i.e. isomorphic to an algebra of formal series in n^2 variables over \Lambda. Now §A, Proposition 5.2 allows us to give an equivalent formulation of this problem as an existence problem of abelian schemes that are reducible along a given abelian scheme. In any case, we see, by a transcendental way, that the answer is affirmative if k is of characteristic 0. In characteristic p\neq0, it evidently suffices to restrict to the case where \Lambda is the ring of Witt vectors constructed over an algebraically closed field k. This could be the moment for the “Greenberg functor” to prove its worth…

## 4.10 Extension of coverings

Let {\mathfrak{X}} be a formal Noetherian prescheme [11], U an open subset of {\mathfrak{X}} defined locally by the “non-vanishing” of a section of {\mathscr{O}}_{\mathfrak{X}} that is not a zero divisor (and thus large enough that every section of {\mathscr{O}}_{\mathfrak{X}} over an open subset V that is zero on U\cap V is zero). ([Comp.] It is also necessary to assume that the section defining U is not a zero divisor not only on {\mathfrak{X}}, but also on every X_n.) Let {\mathfrak{J}} be an “ideal of definition” for {\mathfrak{X}}, and let X_n=({\mathfrak{X}},{\mathscr{O}}_{\mathfrak{X}}/{\mathfrak{J}}^{n+1}), which is thus a ordinary Noetherian prescheme. Then, if {\mathfrak{X}}' and {\mathfrak{X}}'' are flat coverings of {\mathfrak{X}} (i.e. preschemes over {\mathfrak{X}} defined by sheaves of algebras that are coherent and locally free as sheaves of modules) that are unramified over U, the evident map \operatorname{Hom}_{\mathfrak{X}}({\mathfrak{X}}',{\mathfrak{X}}'') \to \operatorname{Hom}_{X_0}(X'_0,X''_0) is injective; in particular, an automorphism of {\mathfrak{X}}' that induces the identity on X'_0 is the identity. This allows us to apply the technique of descent to the situation. We start, in particular, with a flat covering X'_0 of X_0, unramified over U_0, and let G({\mathfrak{X}}) be the set of classes, up to isomorphism (inducing the identity on X'_0), of flat coverings {\mathfrak{X}}' of {\mathfrak{X}} that induce X'_0 on X_0 (and that are thus necessarily unramified over U). We similarly define G(V) for every open subset V of {\mathfrak{X}}, and, more generally, G({\mathfrak{Y}}) for every formal prescheme {\mathfrak{Y}} over {\mathfrak{X}}. With this, the results of [11] and [12] imply, first of all, the following results:

1. If V varies amongst open subset of {\mathfrak{X}}, then the G(V) form a sheaf on {\mathfrak{X}}, say {\mathscr{G}}_{\mathfrak{X}}={\mathscr{G}}. The restriction of this sheaf to U is the constant sheaf whose fibres consist of a single element.

More generally, describing the fibres of {\mathscr{G}}_{\mathfrak{X}} is a question of complete local rings, in a precise way:

2. For all x\in{\mathfrak{X}}, we have {\mathscr{G}}_x = G(\operatorname{Spec}({\mathscr{O}}_{{\mathfrak{X}},x})) \subset G(\operatorname{Spec}(\widehat{{\mathscr{O}}}_{{\mathfrak{X}},x})) (i.e. isomorphism classes of finite free algebras B over \widehat{{\mathscr{O}}}_{{\mathfrak{X}},x} endowed with an isomorphism from B\otimes_{\widehat{{\mathscr{O}}}_{{\mathfrak{X}},x}}{\mathscr{O}}_{X_0,x} to (\widehat{{\mathscr{O}}}'_0)_x, where {\mathscr{O}}'_0 is the sheaf of algebras on X_0 that defines X'_0).

3. We have a canonical isomorphism {\mathscr{G}}_{\mathfrak{X}}=\varprojlim{\mathscr{G}}_{{\mathfrak{X}}_n}; in other words, for every open subset V of {\mathfrak{X}}, we have G(V)=\varprojlim G(V_n).

4. Suppose that {\mathfrak{X}} comes from an ordinary proper scheme X over a complete local Noetherian ring \Lambda that has ideal of definition {\mathfrak{m}} by taking the {\mathscr{J}}-adic completion of {\mathscr{O}}_X, where {\mathscr{J}}={\mathfrak{m}}\cdot{\mathscr{O}}_X. Then G({\mathfrak{X}}) is canonically isomorphic to the set of classes of flat coverings of the ordinary scheme X that are “reducible along X'_0”.

Figuratively speaking, we can say that (a) and (b) establish the fundamental relations between the local and global aspects of the problem; (c) gives the relations between the “finite” and “infinitesimal” aspects; and finally (d) remembers (under precise conditions) the identity between the “formal” and “algebraic” aspects.

Now suppose that {\mathfrak{X}} is defined by a local complete Noetherian ring \Lambda, with {\mathscr{J}}={\mathfrak{m}}\cdot{\mathscr{O}}_X (and so X_0 is a prescheme over \Lambda/{\mathfrak{m}}). For every algebra A that is finite over \Lambda, we set F(A) = G({\mathfrak{X}}\times_\Lambda A). This is a covariant functor in A, with values in the category of sets, and, by (c), this functor is completely determined by how it acts on Artinian algebras A; it is equivalent to say either that this functor is pro-representable, i.e. of the form F(A) = \operatorname{Hom}_{\text{top. }\Lambda\text{-algebras}}({\mathscr{O}},A) where {\mathscr{O}} is a topological \Lambda algebra of the type described in §A.5, or that this is true when we restrict to only Artinian algebras A. The combination of Theorem 1 and Theorem 2 then effectively implies:

The above functor is pro-representable.

Of course, by (a), if U={\mathfrak{X}}, then G({\mathfrak{Y}}) consists of a single element for all {\mathfrak{Y}} over {\mathfrak{X}}, and the functor F is then not very interesting (we will have {\mathscr{O}}=\Lambda). It seems that, in practically every other case, the topological local ring {\mathscr{O}} is not Noetherian. Its existence, however, shows, in a striking manner, the “continuous” nature of the set G({\mathfrak{X}}) of solutions (corresponding intuitively to the fact that there is a “continuous” choice in the way in which the ramification spreads when we take an extension of X'_0). We will compare this result with the point of view of J.-P. Serre [27] via local class field theory, drawing attention as well to the continuous character of the topological Galois group of the maximal abelian extension of a “geometric” local field, with the dual group (in the sense of Pontrjagin) appearing as an inductive limit of algebraic (or at least quasi-algebraic) groups; here as well, the classification of extensions is given by infinite-dimensional “varieties”. We can also take, in the above, {\mathfrak{X}} to be the formal spectrum of a complete local ring (of which \Lambda will be, for example, a Cohen subring), and we might hope that the results of this section can be used in the study of extensions of a local complete ring of dimension >1. Just as much in the local case as in the global case, they might allow us to formulate precise relations between the phenomena of higher ramification and phenomena in characteristic 0 (approachable via a transcendental way). In any case, it is the preliminary analysis of Proposition 5.1 that allows us to extend the methods described in [11] for the study of the fundamental group to the “tamely ramified” case, and to resolve, by a transcendental way, the “problem of three points”.

To finish, we note that the situation simplifies if X_0 is of dimension 1; then, by (a) and (b), G({\mathfrak{X}}) can be identified with \prod_i G(\operatorname{Spec}({\mathscr{O}}_{{\mathfrak{X}},x_i})), where the x_i are the points of X_0\setminus U: we can take arbitrary “local” extensions at the ramification points. Further, if X_0 is normal, then we note that the formal scheme of modules guaranteed by Proposition 5.1 is simple over \operatorname{Spec}(\Lambda).

### References

[9]
A. Grothendieck. “Sur quelques points d’algèbre homologique.” Tohoku Math. J. 9 (1957), 119–221.
[11]
A. Grothendieck. “Géométrie formelle et géométrie algébrique.” Séminaire Bourbaki. 11 (1958-59), Talk no. 182.
[12]
A. Grothendieck. “Technique de descente et théorèmes d’existence en géométrie algébrique, I: Généralités, descente pas morphismes fidèlement plats.” Séminaire Bourbaki. 12 (1959-60), Talk no. 190.
[27]
J.-P. Serre. “Corps locaux et isogénies.” Séminaire Bourbaki. 11 (1958-59), Talk no. 185.

1. [Trans.] Here the word “Hausdorff” is implicit.↩

format: plain


text:
Philippe Delsarte (An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10:vi+97, 1973) generalised the “MacWilliams transform” of coding theory to the theory of association schemes, and there have been numerous powerful applications of this object, particulary in finding the maximum size of a clique in some particular kinds of graphs. These graphs are regular and they are in fact a union of graphs from some association scheme. Let $\omega(\Gamma)$ be the maximum size of a clique of a graph $\Gamma$.

Theorem (Delsarte): If $\Gamma$ is the graph of an association scheme with valency $k$, and if $\lambda$ is a negative eigenvalue of $\Gamma$, then

$\omega(\Gamma)\le 1-k/\lambda$.

I will give a proof I’ve seen in one of Chris Godsil’s notes as it bypasses the usual theory on inner distribution vectors and the MacWilliams transform.

Proof: Suppose we have an association scheme $\mathcal{A}$ with primitive idempotents $J=E_0,E_1,\ldots,E_d$ and suppose $\Gamma$ is a graph for one of the relations of $\mathcal{A}$, of order $n$. Let $C$ be a clique of $\Gamma$ and let $\theta$ be an eigenvalue of $\Gamma$ with multiplicity $m_\theta$. Let us denote by $E_\theta$ the primitive idempotent whose rowspace is the eigenspace corresponding to $\theta$. Then the submatrix of $E_\theta$ with rows and columns indexed by the vertices of $C$ has the form

$\alpha I + \beta J.$

Since $E_\theta$ is positive semidefinite, the eigenvalues of $\alpha I + \beta J$ are non-negative. The constant row-sum value of $E_\theta$ is an eigenvalue, and so $\alpha + (|C| - 1)\beta$ is an eigenvalue and thus is non-negative. This implies that

$|C|\le 1-\alpha/\beta$.

Since $\alpha I$ is the Hadamard product $I\circ E_\theta$ we have $n\alpha = \mathrm{Trace}(E_\theta) = m_\theta$. Let $A$ be the adjacency matrix for $\Gamma$. Since $AE_\theta = \theta E_\theta$ and $A\circ E_\theta = \beta A$, we have

$\beta n k = \sum(\beta A) = \sum(A\circ E_\theta) = \mathrm{Trace}(AE_\theta) = \theta m_\theta$. Therefore $\beta=\theta \alpha/k$. Hence, if we consider all cliques and the least eigenvalue $\lambda$, we have $\omega(\Gamma)\le 1-k/\lambda.$

$\square$

This bound doesn’t hold for all regular graphs, as we shall see.

Consider a generalised quadrangle of order $(s,t)$ and its collinearity graph $\Gamma$. Then $\Gamma$ is regular of valency $s(t+1)$ and a maximal clique of $\Gamma$ is simply the set of points incident with some line. So $\omega(\Gamma)=s+1$. The eigenvalues of $\Gamma$ are $s(t+1)$, $s-1$ and $-t-1$. Now $\Gamma$ is strongy regular and so is the graph of an association scheme, and Delsarte’s bound applies and is tight:

$\omega(\Gamma)\le 1-s(t+1)/(-t-1)=s+1$.

Now consider what we get when we remove a line $\ell$ of $\Gamma$. If $s\ge 2$, then the biggest clique of $\Gamma-\ell$ is still the set of points of a line of the original generalised quadrangle. The valency of $\Gamma-\ell$ is $s(t+1)-1$. So if Delsarte’s bound applies, then the least negative eigenvalue $\tau$ of $\Gamma-\ell$ satisfies $s+1\le 1-(s(t+1)-1)/\tau$, and hence,

$\tau\ge 1/s-(t+1).$

However, by the theory of interlacing eigenvalues, we must have $\tau\le -(t+1)$; a contradiction.

Question

For what families of regular graphs does this bound hold?

5 thoughts on “When does Delsarte’s bound hold?”

1. I don’t understand the argument in the last sentence, as the minimal eigenvalue of an induced subgraph is always bigger than or equal to the minimal eigenvalue of the graph (by interlacing!).

By the way, is there a description of eigenvectors of collinearity graphs of GQs which correspond to eigenvalue s-1 ?

1. Gordon Royle says:

By “generalised interlacing”, deleting $m$ vertices from a graph alters the minimum eigenvalue from $\lambda_n$ to somewhere between $\lambda_{n-m}$ and $\lambda_n$. As the original collinearity graph has got lots of eigenvalues equal to $-t-1$ (that is, more than $s+1$) the minimum eigenvalue of the graph after deleting the vertices of a line is still equal to $-t-1$, and the bound fails.

As for the eigenvectors of the collinearity graph, consider the following set: take two intersecting lines and put a weight of +1 on each point of the first line, -1 on each point of the second line, 0 on the point of intersection and 0 elsewhere. Unless I screwed up, this is an eigenvector with eigenvalue $s-1$. I don’t know if this is all of them though.

2. There are heaps of eigenvectors with eigenvalue $s-1$, they form a vector space! The ones that Gordon describes form a spanning set.

1. Thanks. Indeed, I meant to ask for a combinatorial description…

1. Yes, in a way there is. Let $S$ be a set of points of a GQ of order $(s,t)$. Now consider the average valency of $S$, that is, the average number of points $a$ of $S$ collinear with a given point of $S$. Then it can be shown that $a\le s-1+|S|/(s+1)$, and if equality is attained, then $S$ is what is called a tight set of the GQ. If we let $A$ be the collinearity matrix of the GQ, we have an equivalent definition of a tight set in terms of the characteristic vector of $S$:
$A\chi_S=(s-1)\chi_S+ \frac{|S|}{s+1}\mathbf{j}$ where ${\mathbf{j}}$ is the all-ones vector. So $-(st+1)\chi_S-\frac{|S|}{s+1}\mathbf{j}$ is an eigenvector of $A$ with eigenvalue $s-1$.


text:
# If tan x=1, how do you find sin x/2 , cos x/2 , and tan x/2?

##### 1 Answer
Apr 25, 2015

Not enough information is provided. If $\tan x = 1$ then x is in either quadrant 1 or 3 with reference angle $\frac{\pi}{4}$. So ${\cos}^{2} x = \frac{1}{2}$.

Without more information it is impossible to determine the signs of the trig functions of the half angle.

If $x = \frac{\pi}{4}$ then for $\frac{x}{2}$ all trig values are positive.

If $x = \frac{- 7 \pi}{4}$ then $\frac{x}{2}$ has negative sine and cosine.

For some other possibilities for $x$, the half angle has sine positive and cosine negative, for still others, it is opposite.


text:
# Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?

Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a bunch of binary strings $x_1,...,x_m$ of length $n$ it holds that for every $i$, for $k_i$ different pairs {$j_1,j_2$}, $$e_i = x_{j_1} \oplus x_{j_2}.$$ Then m is at least exponential in n, where the exponent depends linearly on the average ratio of $k_i/m$.

Another (related) example is some isoperimetric inequalities on the Boolean cube (feel free to elaborate on this in your answers).

Do you have more nice examples? Preferably, short and easy to explain.

-
can someone give a ref on "Another (related) example is some isoperimetric inequalities on the Boolean cube"? –  vzn Jan 5 '13 at 0:58

Moser's proof of the constructive Lovasz Local Lemma. He basically shows that, under the conditions of the local lemma, the second-simplest algorithm for SAT you can think of works. (The first simplest might be to just try a random assignment until one works. The second simplest is took pick a random assignment, find an unsatisfied clause, satisfy it, then see what other clauses you broke, recurse, and repeat until done.) The proof that this runs in polynomial time is perhaps the most elegant use of information theory (or Kolmogorov complexity, whatever you want to call it in this case) I've ever seen.

-
The beautiful Kolmogorov complexity proof of Moser is explained here: blog.computationalcomplexity.org/2009/06/…, but I have to admit I was looking more for an entropy/mutual-information/-calculation type of example... –  Dana Moshkovitz Nov 3 '10 at 2:02
There are some pretty interesting applications of Kolmogorov complexity given as answers to this question: cstheory.stackexchange.com/questions/286 –  arnab Nov 3 '10 at 4:52
Terry Tao also discussed Moser's argument on his blog: terrytao.wordpress.com/2009/08/05/… –  Anthony Leverrier Nov 3 '10 at 8:32
Actually, in his second paper (with Tardos) you no longer need recourse to recursion. You just look for an unsatisfied clause, pick a random assignment for its variables, and iterate. That's it. For some reason the simpler algorithm (having the same analysis) hasn't stuck. –  Yuval Filmus Feb 8 '11 at 2:11
@DanaMoshkovitz: I don't know why this didn't occur to me to say sooner in response to your comment: Kolmogorov complexity and entropy are, in many ways, essentially equivalent. See e.g. Hammer-Romaschenko-Shen-Vershchagin: dx.doi.org/10.1006/jcss.1999.1677. For example, based on [HRSV], the proof of Shearer's Lemma in arnab's answer can be proved with essentially the same proof using Kolmogorov complexity in place of entropy. The difference is just viewpoint: K is about description length, H is about $\sum p_i \log p_i$... Sometimes one is easier/more natural than the other. –  Joshua Grochow Feb 12 at 0:30

My favorite example of this type is the entropy-based proof of Shearer's Lemma. (I learned of this proof and several other very pretty ones from Jaikumar Radhakrishnan's Entropy and Counting.)

Claim: Suppose you have $n$ points in $\mathbb{R}^3$ that have $n_x$ distinct projections on the $yz$-plane, $n_y$ distinct projections on the $xz$-plane and $n_z$ distinct projections on the $xy$-plane. Then, $n^2 \leq n_x n_y n_z$.

Proof: Let $p = (x,y,z)$ be a point uniformly chosen at random from the $n$ points. Let $p_x$, $p_y$, $p_z$ denote its projections onto the $yz$, $xz$ and $xy$ planes respectively.

On the one hand, $H[p] = \log n$, $H[p_x] \leq \log n_x$, $H[p_y] \leq \log n_y$ and $H[p_z] \leq \log n_z$, by basic properties of entropy.

On the other hand, we have $$H[p] = H[x] + H[y|x] + H[z | x,y]$$ and also $$H[p_x] = H[y] + H[z|y]$$ $$H[p_y] = H[x] + H[z|x]$$ $$H[p_z] = H[x] + H[y|x]$$ Adding the last three equations gives us: $H[p_x] + H[p_y] + H[p_z] =$ $2H[x] + H[y]+$ $H[y|x] +$ $H[z|x]$ $+ H[z|y]$ $\geq 2H[x] + 2H[y|x] + 2H[z|x,y] =$ $2H[p]$, where we used the fact that conditioning decreases the entropy (in general, $H[a] \geq H[a|b]$ for any random variables $a,b$).

Thus, we have $2 \log n \leq \log n_x + \log n_y + \log n_z$, or $n^2 \leq n_x n_y n_z$.

-
A related paper to check out is 'Hypergraphs, Entropy, and Inequalities' by Ehud Friedgut. It shows how an entropy perspective, specifically a generalized Shearer's Lemma, can easily recover many standard inequalities, and also some nonstandard, complicated-looking ones. I think it gives an illuminating perspective. Link: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf –  Andy Drucker Nov 3 '10 at 16:42

Radhakrishnan's entropy proof of Bregman's Theorem, that the number of perfect matchings $p$ in a bipartite graph $(L\cup R, E)$ is at most $\prod_{v \in L} (d(v)!)^{1/d(v)}$. The proof uses two very clever ideas. Here is a sketch of the proof:

• Select a perfect matching $M$ uniformly. The entropy of this variable is $H(M) = \log p$.
• For $v \in L$, let $X_v$ be the vertex in $R$ that is matched with $v$ in $M$.
• The variable $X = (X_v : v \in L)$ has the same information as $M$, so $H(M) = H(X)$.
• Clever Idea 1: By randomly (and uniformly) selecting an order $\leq$ on $L$, Radhakrishnan provides a "randomized chain rule" stating $H(X) = \sum_{v\in L} H(X_v | { X_u : u < v }, \leq)$.
• From the information in the conditions (${X_u : u < v}, \leq$) we can determine $N_v = |N(v) \setminus { X_u : u < v }|$ (roughly: the number of choices for matching $v$).
• Since $N_v$ is determined from this information, the conditioned entropy doesn't change in the equality $H(X_v | { X_u : u < v }, \leq) = H(X_v | { X_u : u < v }, \leq, N_v)$.
• Clever Idea 2: By "forgetting" the information ${X_u : u < v}, \leq$, we can only increase the entropy: $H(X_v | { X_u : u < v }, \leq, N_v) \leq H(X_v | N_v)$.
• Crazy Fact: The variable $N_v$ is uniformly distributed on the set ${1,\dots, d(v)}$.
• Now, to compute the entropy $H(X_v | N_v)$, we sum over all values of $N_v$: $H(X_v | N_v) = \sum_{i=1}^{d(v)} \frac{1}{d(v)}H(X_v|N_v=i) \leq \frac{1}{d(v)}\sum_{i=1}^{d(v)}\log i = \log((d(v)!)^{1/d(v)}).$
• The result follows by combining all inequalities together and taking exponents.

The generalization of this inequality is the Kahn-Lovász Theorem: The number of perfect matchings in any graph $G$ is at most $\prod_{v \in V(G)} (d(v)!)^{1/2d(v)}$. An entropy proof of this result was proven by Cutler and Radcliffe.

-
Great example! A small point: When you estimate $H(X_v\mid N_v)$, you probably can only say that $H(X_v\mid N_v = i)$ is upper bounded by $\log i$. –  Srikanth Nov 3 '10 at 17:57
You are absolutely correct and I've edited the answer to use an inequality. –  Derrick Stolee Nov 3 '10 at 18:07

Very nice examples are contained in two papers by Pippenger An Information-Theoretic Method in Combinatorial Theory. J. Comb. Theory, Ser. A 23(1): 99-104 (1977) and Entropy and enumeration of boolean functions. IEEE Transactions on Information Theory 45(6): 2096-2100 (1999). Actually, several papers by Pippenger contain cute proofs of combinatorial facts by means of entropy/mutual information. Also, the two books: Jukna, Extremal Combinatorics With Applications in Computer Science and Aigner, Combinatorial Search have some nice examples. I also like the two papers Madiman et al. Information-theoretic Inequalities in Additive Combinatorics, and Terence Tao, Entropy sumset estimates (you can find them with Google Scholar). Hope it helps.

-
Looks like a great reading list! –  Dana Moshkovitz Nov 3 '10 at 14:28

Another great example is Terry Tao's alternate proof of the Szemerédi graph regularity lemma. He uses an information-theoretic perspective to prove a strong version of the regularity lemma, which turns out to be extremely useful in his proof of the regularity lemma for hypergraphs. Tao's proof is, by far, the most concise proof for the hypergraph regularity lemma.

Let me try to explain at a very high level this information-theoretic perspective.

Suppose you have a bipartite graph $G$, with the two vertex sets $V_1$ and $V_2$ and the edge set E a subset of $V_1 \times V_2$. The edge density of $G$ is $\rho = |E|/|V_1||V_2|$. We say $G$ is $\epsilon$-regular if for all $U_1 \subseteq V_1$ and $U_2 \subseteq V_2$, the edge density of the subgraph induced by $U_1$ and $U_2$ is $\rho \pm \epsilon |U_1||U_2|/|V_1||V_2|$.

Now, consider selecting a vertex $x_1$ from $V_1$ and a vertex $x_2$ from $V_2$, independently and uniformly at random. If $\epsilon$ is small and $U_1, U_2$ are large, we can interpret $\epsilon$-regularity of $G$ as saying that conditioning $x_1$ to be in $U_1$ and $x_2$ to be in $U_2$ does not affect much the probability that $(x_1,x_2)$ forms an edge in $G$. In other words, even after we are given the information that $x_1$ is in $U_1$ and $x_2$ is in $U_2$, we haven't acquired much information about whether $(x_1,x_2)$ is an edge or not.

The Szemeredi regularity lemma (informally) guarantees that for any graph, one can find a partition of $V_1$ and a partition of $V_2$ into subsets of constant density such that for most such pairs of subsets $U_1 \subset V_1, U_2 \subset V_2$, the induced subgraph on $U_1 \times U_2$ is $\epsilon$-regular. Making the above interpretation, given any two high-entropy variables $x_1$ and $x_2$, and given any event $E(x_1,x_2)$, it is possible to find low-entropy variables $U_1(x_1)$ and $U_2(x_2)$ -- "low-entropy" because the subsets $U_1$ and $U_2$ are of constant density -- such that $E$ is approximately independent of $x_1 | U_1$ and $x_2 | U_2$, or that the mutual information between the variables is very small. Tao actually formulates a much stronger version of the regularity lemma using this setup. For example, he doesn't require that $x_1$ and $x_2$ be independent variables (though there hasn't yet been an application of this generalization, as far as I know).

-

There is basically an entire course devoted to this question:

https://catalyst.uw.edu/workspace/anuprao/15415/86751

The course is still ongoing. So not all notes are available as of writing this. Also, some examples from the course were already mentioned.

-
nice pointer: looks like a great class. –  Suresh Venkat Nov 9 '10 at 19:56
As far as I can tell, this offering is half course, with notes containing some examples that make good answers to my question, and half seminar, covering examples like communication lower bounds, extractors, parallel repetition, etc, that require much more than just information theory (here there are no notes, just links to the original papers). –  Dana Moshkovitz Nov 9 '10 at 22:18

Suppose we have $n$ points in $\ell_2^d$ and want to do a dimension reduction. If we want pairwise distances change by at most $1 \pm \epsilon$, then we can reduce our dimension from $d$ to $O(\log n / \epsilon^2)$. This is Johnson-Lindenstrauss Lemma. For a decade the best known lower bound for a dimension was $\Omega(\log n / (\epsilon^2 \log(1 / \epsilon)))$ by Alon, so there was a gap of size $\sim \log(1 / \epsilon)$. Recently, Jayram and Woodruff closed this gap by improving Alon's lower bound. Their proof barely relies on geometrical structure. What they do is they prove that if a better bound was possible, it would violate one particular communication complexity lower bound. And this bound is proved using information-theoretical tools.

-
Another example in metric embeddings: Regev has recently shown a very short proof of the best bounds for embedding into $\ell_1^d$, using entropy arguments. –  arnab Dec 6 '11 at 0:01
It seems very natural and nice that these purely geometric results were proved by TCS people! –  ilyaraz Dec 6 '11 at 0:06

Consider the following rather fundamental problem in the world of data structures. You have a universe of size $m$. You want to store an element $u \in [m]$ as a static data structure, so that when a user wants to know if for some $x \in [m]$ whether $x=u$, only $t$ bit probes into the data structure are needed, where $t$ is some fixed constant. The goal is to minimize the space complexity of the data structure (in terms of number of bits stored).

One can construct such a data structure of size $O(m^{1/t})$. The idea is simple. Divide the $\log m$ bits needed to describe $u$ into $t$ blocks. For each $i \in [t]$ and for each possible bistring of length $(\log m)/t$, store in the data structure whether the $i$'th block of $u$ equals that bitstring.

Now, for the lower bound. Let $X$ be an element uniformly chosen at random from $[m]$. Clearly, $H[X] = \log m$. If $X_1, \dots, X_t$ are the $t$ bits probed in the data structure (possibly adaptively) in that sequence, then: $H[X] = H[X_1] + H[X_2 | X_1] + \cdots + H[X_t | X_1, \dots, X_{t-1}] \leq t \log s$, where $s$ is the size of the data structure. This gives: $s \geq m^{1/t}$.

Tight bounds are not known if we want to store two elements and $t > 1$. See here for the best results in this direction.

-

A great example is the paper "Sorting and Entropy" by Kahn and Kim. The entropy method is used to find an algorithm that given a known poset $P$ and an unknon linear extension of $P$, find the linear extension by $O(\log |X|)$ queries where $X$ is the set of linear extensions of $P$.

-

Average-Case Analysis of Algorithms Using Kolmogorov Complexity by Jiang, Li, Vitanyi.

'Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method [7]. In this paper we use several simple examples to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queueusort or Stacksort.'

-


text:
## Commutative Algebra and Algebraic Geometry: The implicitization problem for rational normal scrolls

Seminar | March 14 | 5-6 p.m. | 939 Evans Hall

Alessio Sammartano, Purdue University

Department of Mathematics

We study the defining ideals of the Rees algebra and of the special fiber ring for ideals of a rational normal scroll in $P^n$. In particular, we show that these rings are Koszul algebras.

de@math.berkeley.edu


text:
## Abstract and Applied Analysis

### Existence and Multiplicity of Positive Solutions for Dirichlet Problems in Unbounded Domains

Tsung-Fang Wu

#### Abstract

We consider the elliptic problem $-\Delta u+u=b(x){|u|}^{p-2}u+h(x)$ in $\Omega$, $u\in {H}_{0}^{1}(\Omega )$, where $2\lt p \lt (2N/(N-2)) (N\geq 3), 2 \lt p \lt \infty (N=2), \Omega$ is a smooth unbounded domain in ${\mathbb{R}}^{N}, b(x)\in C(\Omega)$, and $h(x)\in {H}^{-1} (\Omega )$. We use the shape of domain $\Omega$ to prove that the above elliptic problem has a ground-state solution if the coefficient $b(x)$ satisfies $b(x)\rightarrow {b}^{\infty} > 0$ as $|x|\rightarrow \infty$ and $b(x)\geq c$ for some suitable constants $c\in (0,{b}^{\infty})$, and $h(x)\equiv 0$. Furthermore, we prove that the above elliptic problem has multiple positive solutions if the coefficient $b(x)$ also satisfies the above conditions, $h(x)\geq 0$ and $0\lt \Vert h\Vert_{{H}^{-1}} \lt (p-2){(1/(p-1))}^{(p-1)/(p-2)}{[{b}_{\sup}{S}^{p}({\Omega})]}^{1/(2-p)}$, where $S({\Omega })$ is the best Sobolev constant of subcritical operator in ${H}_{0}^{1}({\Omega })$ and ${b}_{\sup }={\sup }_{x\in {\Omega }}b(x)$.

#### Article information

Source
Abstr. Appl. Anal., Volume 2007 (2007), Article ID 18187, 25 pages.

Dates
First available in Project Euclid: 27 February 2008

https://projecteuclid.org/euclid.aaa/1204126588

Digital Object Identifier
doi:10.1155/2007/18187

Mathematical Reviews number (MathSciNet)
MR2302187

Zentralblatt MATH identifier
1157.35377

#### Citation

Wu, Tsung-Fang. Existence and Multiplicity of Positive Solutions for Dirichlet Problems in Unbounded Domains. Abstr. Appl. Anal. 2007 (2007), Article ID 18187, 25 pages. doi:10.1155/2007/18187. https://projecteuclid.org/euclid.aaa/1204126588

#### References

• P. H. Rabinowitz, Minimax Methods in Critical Point Theory with Applications to Differential Equations, vol. 65 of CBMS Regional Conference Series in Mathematics, American Mathematical Society, Providence, RI, USA, 1986.
• A. Ambrosetti and P. H. Rabinowitz, “Dual variational methods in critical point theory and applications,” Journal of Functional Analysis, vol. 14, no. 4, pp. 349–381, 1973.
• M. Willem, Minimax Theorems, vol. 24 of Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser, Boston, Mass, USA, 1996.
• H.-C. Wang and T.-F. Wu, “Symmetry breaking in a bounded symmetry domain,” NoDEA. Nonlinear Differential Equations and Applications, vol. 11, no. 3, pp. 361–377, 2004.
• H. Berestycki and P.-L. Lions, “Nonlinear scalar field equations. I. Existence of a ground state,” Archive for Rational Mechanics and Analysis, vol. 82, no. 4, pp. 313–345, 1983.
• W. C. Lien, S. Y. Tzeng, and H.-C. Wang, “Existence of solutions of semilinear elliptic problems on unbounded domains,” Differential and Integral Equations, vol. 6, no. 6, pp. 1281–1298, 1993.
• K.-J. Chen and H.-C. Wang, “A necessary and sufficient condition for Palais-Smale conditions,” SIAM Journal on Mathematical Analysis, vol. 31, no. 1, pp. 154–165, 1999.
• M. A. Del Pino and P. L. Felmer, “Local mountain passes for semilinear elliptic problems in unbounded domains,” Calculus of Variations and Partial Differential Equations, vol. 4, no. 2, pp. 121–137, 1996.
• M. A. Del Pino and P. L. Felmer, “Least energy solutions for elliptic equations in unbounded domains,” Proceedings of the Royal Society of Edinburgh. Section A, vol. 126, no. 1, pp. 195–208, 1996.
• M. K. Kwong, “Uniqueness of positive solutions of ${\Delta{}}u-u+{u}^{p}=0$ in ${{\mathbb{R}}}^{N}$,” Archive for Rational Mechanics and Analysis, vol. 105, no. 3, pp. 243–266, 1989.
• A. Bahri and P.-L. Lions, “On the existence of a positive solution of semilinear elliptic equations in unbounded domains,” Annales de l'Institut Henri Poincaré. Analyse Non Linéaire, vol. 14, no. 3, pp. 365–413, 1997.
• V. Benci and G. Cerami, “Positive solutions of some nonlinear elliptic problems in exterior domains,” Archive for Rational Mechanics and Analysis, vol. 99, no. 4, pp. 283–300, 1987.
• M. J. Esteban and P.-L. Lions, “Existence and nonexistence results for semilinear elliptic problems in unbounded domains,” Proceedings of the Royal Society of Edinburgh. Section A, vol. 93, no. 1-2, pp. 1–14, 1982-1983.
• D.-M. Cao, “Positive solution and bifurcation from the essential spectrum of a semilinear elliptic equation on ${{\mathbb{R}}}^{N}$,” Nonlinear Analysis, vol. 15, no. 11, pp. 1045–1052, 1990.
• A. Bahri and Y. Y. Li, “On a min-max procedure for the existence of a positive solution for certain scalar field equations in ${{\mathbb{R}}}^{N}$,” Revista Matemática Iberoamericana, vol. 6, no. 1-2, pp. 1–15, 1990.
• T.-F. Wu, “Multiplicity of single-bump solutions for semilinear elliptic equations in multi-bump domains,” Nonlinear Analysis, vol. 59, no. 6, pp. 973–992, 2004.
• X. P. Zhu, “A perturbation result on positive entire solutions of a semilinear elliptic equation,” Journal of Differential Equations, vol. 92, no. 2, pp. 163–178, 1991.
• D.-M. Cao and H.-S. Zhou, “Multiple positive solutions of nonhomogeneous semilinear elliptic equations in ${{\mathbb{R}}}^{N}$,” Proceedings of the Royal Society of Edinburgh. Section A, vol. 126, no. 2, pp. 443–463, 1996.
• L. Jeanjean, “Two positive solutions for a class of nonhomogeneous elliptic equations,” Differential and Integral Equations, vol. 10, no. 4, pp. 609–624, 1997.
• S. Adachi and K. Tanaka, “Multiple positive solutions for nonhomogeneous elliptic equations,” Nonlinear Analysis, vol. 47, no. 6, pp. 3783–3793, 2001.
• S. Adachi and K. Tanaka, “Four positive solutions for the semilinear elliptic equation: $-{\Delta{}}u+u=a(x){u}^{p}+f(x)$ in ${{\mathbb{R}}}^{N}$,” Calculus of Variations and Partial Differential Equations, vol. 11, no. 1, pp. 63–95, 2000.
• H.-L. Lin, H.-C. Wang, and T.-F. Wu, “A Palais-Smale approach to Sobolev subcritical operators,” Topological Methods in Nonlinear Analysis, vol. 20, no. 2, pp. 393–407, 2002.
• G. Tarantello, “On nonhomogeneous elliptic equations involving critical Sobolev exponent,” Annales de l'Institut Henri Poincaré. Analyse Non Linéaire, vol. 9, no. 3, pp. 281–304, 1992.
• H. Brézis and E. Lieb, “A relation between pointwise convergence of functions and convergence of functionals,” Proceedings of the American Mathematical Society, vol. 88, no. 3, pp. 486–490, 1983.
• I. Ekeland, “On the variational principle,” Journal of Mathematical Analysis and Applications, vol. 47, no. 2, pp. 324–353, 1974.


text:
# 2nd order differential equations

## The Attempt at a Solution

I managed to find dy/dx as follows:

But I'm having difficulty finding the second derivative. I've looked at examples using the chain rule but I'm still confused.

Would someone mind shedding some light on this for me?

#### Attachments

• xn4AxR5.png
46.7 KB · Views: 479
• dXyGySZ.png
17 KB · Views: 488

## Answers and Replies

Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
2021 Award
I managed to find dy/dx as follows:
This is not particular for dy/dx. It holds if you replace y by any function. In particular, what do you get if you replace y by dy/dx?

trew
Stephen Tashi
Science Advisor

## Homework Equations

The product rule and the chain rule are relevant equations.

But I'm having difficulty finding the second derivative.

Part of applying the product rule to find ##\frac{d^2 y}{dx^2} = \frac{d}{dx} ( \frac{dy}{dz} cos(x))## requires evaluating the factor ##\frac{d}{dx} \frac{dy}{dz}##. The chain rule, in words, says "the derivative with respect to x of a function of z is equal to the derivative of the function with respect to z times the derivative of z with respect to x". As @Orodruin pointed out, you can apply this rule when "a function of z" is ##\frac{dy}{dz}##. What do you get when you differentiate ##\frac{dy}{dz}## with respect to ##z## ?

trew