text:
# Upper bound for different sums having the same value

Let $\Lambda :=\{\lambda_1, \dots, \lambda_n\}$ be a set of $n$ distinct real numbers.

For a given $p \in \mathbb N$, consider further the set

$$I_p := \{ \{i_1, i_2, \dots, i_p\} : i_j \in \{1, \dots,n\} \text{ for all } j=1, \dots, p\}.$$

It is not hard to see that $|I_p| = \binom{n+p-1}{p}$. For example, if $n=3$ and $p=2$, then

$$I_2 = \{ \{1,1\}, \{1,2\}, \{1,3\}, \{2,2\}, \{2,3\}, \{3,3\} \}.$$

Now for a given $p \in \mathbb N$ we write down all $\binom{n+p-1}{p}$ sums $$\lambda_{i_1} + \lambda_{i_2} + \dots + \lambda_{i_p}.$$

Clearly it can happen that "different" sums have the same value, e.g. if

$$\Lambda = \{0,1,2\}$$

and $p=2$, then we get the sums $0, 1, 2, 2, 3, 4$ given by considering the elements of $I_2$.

My question is the following: Is there in general an upper bound on how many "different" sums there are that lead to one particular value?

Another interesting question would be the following: Given a fixed upper bound $N^*$, are there conditions on $\Lambda$ such that for all $p \in \mathbb N$, at most $N^*$ different $p$'th order sums yield the same value. For $N^* = 1$ one gets the condition that $\lambda_1, \dots, \lambda_n$ need to linearly independent over $\mathbb Q$.

• If you let the $\lambda_i$ be linearly independent over $\mathbb{Q}$, you will obtain the upper bound. That is, just pretend the $\lambda_i$ are unknowns, with no relations. Oct 2, 2014 at 18:48
• @PerAlexandersson I think you misunderstood the question. What was wanted was an upper bound on the number of elements of $I_p$ that can have the same sum. In your example that number is $1$, which is a lower bound. Oct 2, 2014 at 18:52
• Taking a set symmetric about 0, one get n/2 choose p/2 as a bigger lower bound. Since any two choices for the same sum will differ by at least two members, no choice of p-1 members is repeated, so that provides a weak upper bound. Oct 2, 2014 at 19:10
• Also, considering the first n whole numbers, there are np-p+1 possible sums, so that gives a lower bound not far from the weak upper bound. Oct 2, 2014 at 19:27

I answer the first question in Corollary 4.1 of my paper at http://math.mit.edu/~rstan/pubs/pubfiles/42.pdf. The maximum number of sums that have the same value is the middle coefficient of the $q$-binomial coefficient $\left[ n+p-1\atop p \right]$. This is achieved by taking $\Lambda=\{ 1,2,\dots,n\}$ and the sum to be $\lfloor \frac 12 p(n+1)\rfloor$. A more elementary proof follows from the work of Proctor and is given in my book Algebraic Combinatorics.

Addendum. For fixed $p$, it follows from http://math.mit.edu/~rstan/papers/qbc.pdf that the middle coefficient of $\left[ n+p-1\atop p\right]$ is asymptotic to $$\frac{A(p-1,\lceil p/2\rceil)n^{p-1}}{(p-1)!p!}$$ as $n\to \infty$, where $A(p-1,\lceil p/2\rceil)$ denotes an Eulerian number.

• I always thought Corollary 4.1 of your paper applied to an arbitrary set of real numbers (not just a set of positive reals). Am I mistaken? Oct 2, 2014 at 20:18
• Indeed, it seems like the general case can be deduced from the all $\lambda_i > 0$ case by adding a large positive constant $C$ to each $\lambda_i$. Oct 2, 2014 at 20:23
• You are right! I have corrected this. Oct 2, 2014 at 20:25
• I am sorry, but I am not familiar with the notion of middle coefficient?
– user45183
Oct 2, 2014 at 23:36
• @Zeno44 Just note that the q-binomial coefficients are symmetric polynomials in q. Oct 3, 2014 at 6:43

A trivial upper bound is ${n+p-1} \choose p$. Somewhat less trivial is ${{n+p - 1} \choose p}/(p+1)$, which can be obtained as follows.
Suppose we put the elements in increasing order. Consider the "stars and bars" representation of $I_p$ (where if there are bars at positions $1 \le b_1 < b_2 < \ldots < b_{n-1} \le n+p-1$, there are $b_1 - 1$ of $\lambda_1$, $b_2 - b_1$ of $\lambda_2$, ..., $b_{n-1} - b_{n-2}$ of $\lambda_{n-1}$ and $n+p-1 - b_{n-1}$ of $\lambda_n$). Suppose we put bars in vacant positions one-by-one. Each of the $p+1$ possible positions for the last bar to be placed produces a different sum (each time you move it to the next available position to the right, you substitute a smaller $\lambda$ in place of a larger one and decrease the sum)). So the probability of getting a particular sum is at most $1/(p+1)$.

This bound is actually attained in your example with $n = 3$ and $p = 2$.


text:
# Tag Info

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions: Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$. Such functions are known to exist; see, e.g., Chapter 6....

format: plain


text:
## Math Word Problems: Solving Number Problems Part 3

This is the third part of the Solving Number Problems Series. The first part can be read here and the second part can be read here.  In this post I will continue worked examples using problems which are slightly more complicated than the problems in the previous two parts. Without further ado, lets start with the seventh problem in the series.

PROBLEM 7

Twice a number added to $18$ is $5$ times that number. What is the number?

Solution

In the two previous posts, we have learned that if $n$ is a number, then twice that number is $2n$. So, twice a number added to $5$ is represented by $2n + 5$. Now, that number, the $2n + 5$ is five times that number of $5n$. So, we can now set up the equation

$2n + 18 = 5n$.

If we solve for $n$, we have $n = 6$» Read more

## GeoGebra Institute of Manila’s New Site

The website of the GeoGebra Institute of Metro Manila (GIMM)  has been transferred here: http://geogebrainstituteph.blogspot.com/

We are still waiting for our official URL. Starting October 2012, we will be accepting post contributions from GeoGebra users in the Philippines. If you are interested, please contact me or email me at nismedmultimedia@gmail.com.

If I were you, I would immediately inform my employer that I can’t accept this paycheck since $e^{i\pi} = -1$ and $\sum_{n=1}^{\infty}\frac{1}{2^n}=1$ (Why?). This is only worth 0.002 dollars.


text:
# How do you write an equation of an ellipse in standard form given foci = (0,-3) and (0,3);length of major axis: 10?

Mar 20, 2016

${x}^{2} / 25 + {y}^{2} / 16 = 1$.

#### Explanation:

Foci are on the major axis. So, the major axis is x-axis . Center is the midpoint of the the line joining the foci, (0, 0).
So, the equation of the ellipse is
${x}^{22} / \left({a}^{2}\right) + {y}^{2} / \left({b}^{2}\right) = 1$,
where a and b are the lengths of semi-major and semi-minor axes.

The eccentricity e = (distance between the foci)$/$(the length of the major axis) = (2ae)/(2a)=3/5.

The semi-minor axis b = a$\sqrt{1 - {e}^{2}}$ = 5$\sqrt{1 - \frac{9}{25}}$ = 4
Answer: ${x}^{2} / 25 + {y}^{2} / 16 = 1$.


text:
### Overview of Python Lists and Tuples

Two of the most commonly used built-in data types in Python are the list and the tuple.

Lists and tuples are part of the group of sequence data types—in other words, lists and tuples store one or more objects or values in a specific order. The objects stored in a list or tuple can be of any type, including the nothing type defined by the None keyword.

The big difference between lists and tuples is that lists are mutable, however tuples are immutable. Meaning once tuples are created, objects can’t be added or removed, and the order cannot be changed. However, certain objects in tuples can be changed, as we’ll see later.

### Creating a Python List or Tuple

Creating a list or tuple is easy, here are some empty ones:

# Lists must be surrounded by brackets
>>> emptylst = []
# Tuples may or may not be surrounded by parenthesis
>>> emptytup = ()

To create non-empty lists or tuples, values are separated by commas:

# Lists must be surrounded by brackets
>>> lst = [1, 2, 3]
>>> lst
[1, 2, 3]
# Tuples may or may not be surrounded by parenthesis
>>> tup = 1, 2, 3
>>> tup
(1, 2, 3)
>>> tup = ('one', 'two', 'three')
>>> tup
('one', 'two', 'three')

Note: To create a tuple with only one value, add a trailing comma to the value.

# The length of this tuple is 1
>>> tup2 = 0,
>>> tup2
(0,)

### Get Python List or Tuple Values

The values in lists and tuples, as with other sequence types, are referenced by an index. This is a number, referring to the sequence of the value, that begins with 0 for the first value. Such as the following:

>>> lst[0]
1
>>> tup[1]
'two'

Using an index below zero gets the values starting from the end of the list or tuple:

>>> lst[-1]
3
>>> tup[-2]
'two'

### Slicing Python Lists and Tuples

Multiple values can be referenced by “slicing” the list or tuple (referencing a range[start:stop]):

>>> lst[0:2]
[1, 2]
# Note an out-of-range stopindex translates to the end
>>> tup[1:5]
('two', 'three')

### Assigning a Python List Value by Index

Values for lists can be assigned with indexes (as long as the index already exists), but not for tuples:

>>> lst[2] = 'three'
>>> lst
[1, 2, 'three']
>>> tup[2] = 3
Traceback (most recent call last):
File "<pyshell#68>", line 1, in <module>
tup[2] = 3
TypeError: 'tuple' object does not support item assignment

### Adding to a Python List

Values can also be added to lists (and lists can be combined, or concatenated) with the ‘+’ operator, or with the standard append method:

# concatenation, the same as lst = lst + [None]
>>> lst += [None]
>>> lst
[1, 2, 'three', None]
>>> lst.append(5)
>>> lst
[1, 2, 'three', None, 5]

### The Python del Keyword for Lists

Values can be removed from lists with the del keyword:

>>> del lst[3]
>>> lst
[1, 2, 'three', 5]
# Slicing deletion; no stop index means through the end
>>> del lst[2:]
>>> lst
[1, 2]

Assignment and deletion methods for lists don’t work for tuples, but concatenation works:

# Note only tuples can be added to tuples
>>> tup += (4,)
>>> tup
('one', 'two', 'three', 4)

Even though tuples are not mutable like lists, with the slicing technique and a little creativity, tuples can be manipulated like lists:

# Almost like slice deletion
>>> tup = tup[0:2]
>>> tup
('one', 'two')
>>> tup2 += tup
>>> tup2
# almost like index assignment
>>> tup2 = tup2[0:1] + (1,) + tup2[2:]
>>> tup2
(0, 1, 'two')

In addition, if a tuple contains a list, the mutability of the list in that tuple is preserved:

>>> tup3 = 0, 'one', None, []
>>> tup3[3].append('three')
>>> tup3
(0, 'one', None, ['three'])

Aside from the methods described here more exist for lists and tuples, but these cover the most common list and tuple operations. And remember, lists and tuples can be nested (can contain lists and tuples, and other data types that store sets of values, such as dictionaries), and can store different types simultaneously, making them very useful.


text:
+1 vote
125 views

A planet is revolving around sun in elliptical orbit. Maximum & minimum distance of planet from sun are respectively 1.6 × 1012 m and 6 × 1010 m. Find minimum speed if maximum speed of planet is 8 × 104 m/s?

(1) 3 × 104 m/s (2) 3 × 103 m/s (3) 8 × 103 m/s (4) 4 × 104 m/s

in Physics | 125 views

Correct answer is 3) 8$$\times 10^3 m/s$$


text:
# Unramified Morphisms

In this post we will develop the notion of unramified morphisms, in their various guises.

In this post we will be assuming the reader is familiar with the (relative) cotangent sheaf. If not, I suggest they first read chapter 21 of Vakil’s Foundations of Algebraic Geometry or II.8 of Hartshorne. I’ll try to be explicit when I can though, and reference the needed theorems, and sometimes be overly hand-holdy with computations.

# Motivation

Our current goal is to construct the right analogue of “local isomorphisms” that were hinted at in our motivation for etale cohomology. Unramified morphisms, along with flatness, will be the properties that end up defining this correct idea of local isomorphisms.

Just like flat morphisms, unramified morphisms are a type of map that plays correctly into our intuition of a “nice morphisms”. They also have the pleasant property of not only being intuitive to understand, but relatively painless to work with technically, thanks to the formalism of the cotangent sheaf.

To understand the idea behind unramified morphisms, let us look at a picture (taken from Wikipedia):

In this picture, what we say is that generically $f$ is a $3$-to-$1$ function, and that $X$ is split into $3$ sheets. Of course, the $3$-to-$1$ness is only generic since over two points of $Y$, the ones marked with dots, we see that $f$ does stop being $3$-to-$1$. At these points, we see that the three sheets that generically make up $X$ come together, or “ramify”.

If we think about this picture in the analytic topology (the “usual one” from complex analysis) these points of ramification are precisely the points of $X$ for which no neighborhood is injective. Indeed, the other points of $x$ have neighborhoods where $f$ is injective by just taking an open segment (the intersection of a small Euclidean ball in the ambient space with $X$) along the sheet they reside. But, at the point of ramification, every Euclidean ball intersects all three sheets, and so no neighborhood of these points verifies $f$‘s injectivity.

Now, we see that if we want to create a type of morphisms modeling “local isomorphisms” (something like a local biholomorphism in complex geometry), we clearly want to exclude ramified morphisms. Indeed, since “local isomorphisms” should, in particular, be locally injective, we see that ramification points are a clear and present obstruction to “local isomorphism”ness.

So, how do we formalize unramifiedness? The problem with the above intuition is that it is just that–intuition. General schemes don’t usually have the luxury of some kind of analytic topology from which to work off of (the whole point of etale cohomology!) and so we must use some other properties which are intrinsic to the schemes themselves. But, what are possible properties of a general scheme for which the above picture violates at the point of ramification?

It turns out, fortunately, that there are several ways to proceed:

## Open Diagonal

Perhaps the most easily explained is the openess of the diagonal map. Let us suppose that we have a morphism $f:X\to Y$. Very informally, we can think about the fiber product $X\times_Y X$ as being the pairs of points $(x,x')\in X\times X$ such that $f(x)=f(x')$. The diagonal $\Delta_X\subseteq X\times_Y X$ can then be thought of merely as the set of points $(x,x)$ or, said differently, points of the fiber product whose coordinates are equal.

Now, notice that in the picture above each point $y\in Y$, which is not the image of a ramification point, there are points in the set $X\times_Y X-\Delta_X$ where each coordinate is in $f^{-1}(y)$. Indeed, just pick a tuple $(x,x')$ where $x$ and $x'$ both lie above $y$, but are in different sheets. Now, a point of ramification, call it $c$, is one where two sheets come together. This intuitively allows us to take a sequence of points $(x_n,x'_n)$ in $X\times_Y X-\Delta_X$, where $x_n$ is in one of the sheets coming together and $x'_n$ is in the other, whose limit is precisely the point $(c,c)$. And, intuitively, this is how all ramification points should arise, as points of the diagonal which are limits of points not in the diagonal.

This gives us one way to define unramifiedness. In particular, being ramified is the ability to find points of the diagonal which are limits of points in the fiber product, but not on the diagonal. This is precisely the statement that $X\times_Y X-\Delta_X$ is not closed. Thus, if we want to force this to not happen, we merely want to specify that $X\times_Y X-\Delta_X$ is closed or, in other words, $\Delta_X$ is open.

## Unicity of Tangent Vector Lifts

Another point of attack is through the notion of “unicity of tangent vector lifts”. This point of view falls under the banner of “formally unramified”, but, it is also a fairly intuitive idea. It shows that unramified morphisms are the algebraic geometry analogue of the notion of immersion from differential topology.

Let’s consider, once again, a morphism $f:X\to Y$. Let’s fix a point $y\in Y$, and a point $x\in X$ which is in the fiber $f^{-1}(y)$. Given a tangent vector $p$ of $X$ based at $x$ we can push it forward, through $f$, to a tangent vector of $Y$ based at $y$. Or, in other terms, we have the derivative map $df_x:T_x X\to T_yY$.

Let’s consider this derivative map in the case of the following picture.

Clearly here this is only one ramification point (the intersection of the two sheets). Notice that if $x$ is not a ramification point, then the derivative map is injective. Indeed, fix a point $y\in Y$, and a tangent vector at that point. For example, the following picture:

Then, there is clearly only one choice of tangent vector at the point above $y\in Y$ in the top sheet, whose image is the specified tangent vector. Namely:

But, consider the following tangent vector lying below the ramification point

Then, there are two tangent vectors at the ramification point that could map to this tangent vector. Namely:

Thus, we might hope to to define unramified via some type of “injectivity on tangent vectors”, or “unicity of tangent vector lifts” criterion. Of course, it’s not quite that simple. To correctly define it, we must, in fact, specify injectivity on all “differential like data”.

What this means rigorously is the following. Let $f:X\to Y$ be a morphism. For any ring $A$, square-zero ideal $I$ (i.e. $I^2=0$), and morphism $\text{Spec}(A)\to Y$ the map

$\text{Hom}_Y(\text{Spec}(A),X)\to\text{Hom}_Y(\text{Spec}(A/I),X)$

is injective, where $\text{Spec}(A/I)$ is considered a $Y$-scheme via the composition

$\text{Spec}(A/I)\to\text{Spec}(A)\to Y$

To see how this relates to our picture above, let’s consider the case where $X$ and $Y$ are $k$-varieties, $A=k[\varepsilon]$ (where $\varepsilon^2=0$), and $I=(\varepsilon)$. Then, intuitively, giving a morphism $\text{Spec}(k[\varepsilon])\to Y$ amounts to choosing a tangent vector $p$ on $Y$. The induced map $\text{Spec}(k)\to Y$ (note that $k[\varepsilon]/I=k$) is merely picking out the base $y$ of this tangent vector. Note that for the rest of this discussion, this choice of tangent vector (and induced choice of base point) on $Y$ is fixed.

An element of $\text{Hom}_Y(\text{Spec}(k),X)$ is then choosing a point of $X$ which maps, under $f$, to the chosen point $y$ of $Y$. Or, in other words, $\text{Hom}_Y(\text{Spec}(k),X)$ is just $f^{-1}(y)$. An element $\text{Hom}_Y(\text{Spec}(k[\varepsilon]),X)$ is just a choice of tangent vector on $X$ which, under $f$, maps to the chosen tangent vector on $Y$. Finally, the map

$\text{Hom}_Y(\text{Spec}(k[\varepsilon]),X)\to\text{Hom}_Y(\text{Spec}(k),X)=f^{-1}(y)$

just takes a tangent vector in the domain, and picks out its base point (an element of the codomain).

Thus, the injectivity of map

$\text{Hom}_Y(\text{Spec}(k[\varepsilon]),X)\to\text{Hom}_Y(\text{Spec}(k),X)=f^{-1}(y)$

amounts to the assertion that given a point of the fiber $f^{-1}(y)$, there is at most one tangent vector at that point which maps to the prechosen tangent vector at $y$. This is precisely the property we were pictorially describing above. One can even make the connection to the tangent space rigorous by taking all of the above discussion relative $k$.

Thus, we see via an example, of how rings and square-zero ideals come into play. The full definition is then just an expansion to all “differential like data”. In other words, each ring $A$ and square-zero ideal $I$, is some analogue of $k[\varepsilon]$ and $(\varepsilon)$. In other words, it’s an affine scheme $\text{Spec}(A)$ with some “fuzz” (representing differential data) and the underlying space $\text{Spec}(A/I)$ with the fuzz removed. It’s not shocking that in the total generality of schemes (to which the notion of unramified applies), we need much stronger conditions than just the injectivity when $A=k[\varepsilon]$ and $I=(\varepsilon)$.

Note that these other “differential like data” don’t just consist of ‘strange’ affine schemes with fuzz, but also consist of examples in the same vein of $k[\varepsilon]$ but with higher order data–think about $A=k[\varepsilon^n]$ and $I=(\varepsilon^{n-1})$. Thus, if this makes sense to you, this injectivity condition is not only keeping track of injectivity of tangent spaces, but injectivity of jet spaces.

## Vanishing Relative Cotangent Sheaf

Another avenue of attack, is through the relative cotangent sheaf $\Omega_{X/Y}:=\Omega^1_{X/Y}$.

Recall that, intuitively, the relevant cotangent sheaf is the analogy of the “relative cotangent bundle”, or the cotangent space of $X$ “modulo” that of $Y$. So, at a point $p\in X$, we can imagine $(\Omega_{X/Y})_p$ being non-zero as saying, roughly, that the space of “tangent vectors” or “directions” at $p$ is more than the corresponding set of “tangent vectors” or “directions” at $f(p)$ since, again, $(\Omega_{X/Y})_p$ is the “quotient” of these.

Of course, this then allows us to use our intuition from the “unicity of tangent vector lifts” to tell that non-vanishing of $\Omega_{X/Y}$ at a point should indicate ramification. So, to guarantee unramifiedness we should specify that $(\Omega_{X/Y})_p=0$ for all $p\in X$ or, equivalently, that $\Omega_{X/Y}=0$.

## Ideals Lifting Correctly

The last intuitive condition for unramifiedness, takes a heavy hint from its complex geometric cousin. Namely, let’s recall that if $f:X\to Y$ is a non-constant map of compact Riemann surfaces, then we define the ramification index of a point $p\in X$ as follows. There exists a unique integer $e_p\geqslant 1$ such that, up to a change of coordinates, $f$ looks like $z\mapsto z^{e_p}$ near $p$. Intuitively, this says that near $p$ (but not at $p$), $f$ always looks like a $e_p$-to-$1$ cover of its image. In particular, $f$ is never a local biholomorphism at $p$ unless $e_p=1$. It was then the maps of Riemann surfaces $f:X\to Y$ for which $e_p=1$ for all $p\in X$ which we called unramified. They were, as alluded to above, precisely the local biholomorphisms (holomorphic covering maps, in fact).

Now, it seems impossible to rephrase this notion of unramifiedness, from the geometry of compact Riemann surfaces, in the language of schemes–the above is very reliant upon analysis to make precise what “locally looks like” means. But, this is just because we’ve cast it this way. There is another, equivalent, way to phrase the notion of ramification index of a map of Riemann surfaces which is wholly amenable to algebraic recasting.

Namely, let us denote the meromorphic function fields of $X$ and $Y$ by $M(X)$ and $M(Y)$ respectively. We know that our map $f:X\to Y$ induces a morphism $f^\ast:M(Y)\to M(X)$. For our point $p\in X$ we have the subring $\mathcal{O}_p\subseteq M(X)$ consisting of those meromorphic functions which are holomorphic at $p$. If $q:=f(p)$, then we similarly have the subring $\mathcal{O}_q\subseteq M(Y)$. Note then that the mapping $M(Y)\to M(X)$ induces a mapping $\mathcal{O}_q\to\mathcal{O}_p$. Moreover, a little thought shows that $\mathfrak{m}_q\mathcal{O}_p=\mathfrak{m}_p^{e_p}$. Thus, we see that the non-local injectivity of a map of Riemann surfaces can be measured by the inability of $\mathfrak{m}_q$ to generate all of $\mathfrak{m}_p$. In particular, we would get that $f:X\to Y$ is unramified at $p$ if and only if $\mathfrak{m}_q\mathcal{O}_p=\mathfrak{m}_p$.

This is precisely one of the ways to define unramifiedness in the context of schemes. Namely, given a morphism $X\to Y$, if $x$ is to be unramified, we want $\mathfrak{m}_{f(x)}$ to be able to take up all of $\mathcal{O}_{X,x}$ just as in the above. The only difference is one of geometric vs. arithmetic. Namely, in the case of Riemann surfaces, all of our points are visible (i.e. all our points are closed points). In the case of schemes, this is not the case. There may exist “hidden” points, that come from things like base changing our scheme to extensions of the base field, if we were dealing with varieties. These hidden points always manifest themselves in the residue field. And, since unramifiedness is a geometric notion, and “sees all the points” (e.g. if we were on a variety it can’t distinguish between the variety and its base change to the algebraic closure of the base field) we need to take these “hidden” points into account. For more intuition about “hidden” points, see this math.se answer of mine.

So, how do we measure “unramifiedness” for the extension of residue fields? Namely, if $f:X\to Y$ is a morphism of schemes, with $y=f(x)$, then how does one attempt to measure ramification for the extension $k(x)/k(y)$? For clarity, let’s assume that the extension is finite (we’ll see below that finiteness is, in fact, forced). Now, if $[k(x):k(y)]=n$ then this should mean that, in some sense, there are $n$ “points” of $k(x)$ lying above the one point of $k(y)$. But, how can we make rigorous sense of this? Taking a cue from the previous paragraph, to make these hidden points become seen, we need to move to the geometric setting. Or, in other words, we need to base change our situation to $\overline{k(y)}$ where all points become visible.

But, the base change of $k(x)$ to $\overline{k(y)}$ is merely $k(x)\otimes_{k(y)}\overline{k(y)}$. So, we would want to say that $k(x)/k(y)$ is unramified if and only if $k(x)\otimes_{k(y)}\overline{k(y)}$ has $n$ points. But, this happens precisely when $k(x)/k(y)$ is separable. Thus, we see that the right notion of unramifiedness for extensions of fields is separability.

So, finally, using our intuition from Riemann surfaces, appropriately adapted to the general, possibly arithmetic, world of schemes, we see that we should define $f:X\to Y$ to be unramified at $x$ if $\mathfrak{m}_{f(x)}\mathcal{O}_{X,x}=\mathfrak{m}_x$ (it is unramified at the visible points) and $k(x)/k(y)$ is separable (it is unramified at the “hidden” points).

# Unramified Morphisms

## Definition ands Basic Theorems

Let us now show that, when defined correctly, the three notions above, which are conducive to definitions pointwise (all but unicity of tangent vector lifts), coincide:

Theorem 1: Let $f:X\to Y$ be locally of finite type and let $x\in X$. Then, the following are equivalent:

1. If $y=f(x)$, then $\mathfrak{m}_y\mathcal{O}_{X,x}=\mathfrak{m}_x$, and $k(x)/k(y)$ is a finite separable extension.
2. The equality $(\Omega_{X/Y})_x=0$ holds.
3. There is a neighborhood $U$ of $x$ for which the restriction of the diagonal map $\Delta:X\to X\times_Y X$ is an open immersion.

Proof: Let’s prove that 1. implies 2. Since this is clearly a local condition, let us assume that $X=\text{Spec}(B)$ and $Y=\text{Spec}(A)$, with $x=\mathfrak{q}$ and $y=\mathfrak{p}$. By assumption, we then have that $\mathfrak{p}B_\mathfrak{q}=\mathfrak{q}B_\mathfrak{q}$. Now, let us then note that

$B_\mathfrak{q}\otimes_{A_\mathfrak{p}} k(\mathfrak{p})=B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q}=B_\mathfrak{q}/\mathfrak{q}B_\mathfrak{q}=k(\mathfrak{q})$

Thus, we see that the diagram

$\begin{matrix}\text{Spec}(k(\mathfrak{q})) & \rightarrow & \text{Spec}(B_\mathfrak{q})\\ \downarrow & & \downarrow\\ \text{Spec}(k(\mathfrak{p})) & \rightarrow & \text{Spec}(A_\mathfrak{p})\end{matrix}$

is fibered. Thus, we know (Hartshorne Proposition II.8.2.A) that

$\Omega_{B_\mathfrak{q}/A_\mathfrak{p}}\otimes_{B_\mathfrak{q}}k(\mathfrak{q})=\Omega_{k(\mathfrak{q})/k(\mathfrak{p})}$

Now, since $k(\mathfrak{q})/k(\mathfrak{p})$ is finite separable, we know that $\Omega_{k(\mathfrak{q})/k(\mathfrak{p})}=0$ (see discussion in “Geometric Examples” for proof). Since $\Omega_{B_\mathfrak{q}/A\mathfrak{p}}$ is a finitely generated $B_\mathfrak{q}$-module (because we assumed locally of finite type) we can conclude from Nakayama’s lemma that $\Omega_{B_\mathfrak{q}/A_\mathfrak{p}}=0$. Next, we note that $\Omega_{B_\mathfrak{q}/A_\mathfrak{p}}=\Omega_{B_\mathfrak{q}/A}$. This is because we have the set of ring maps $A\to A_\mathfrak{p}\to B_\mathfrak{q}$ which (by Hartshorne II.8.3.A) gives us a short exact sequence

$\Omega_{A_\mathfrak{p}/A}\otimes_{A_\mathfrak{p}}B_\mathfrak{q}\to \Omega_{B_\mathfrak{q}/A}\to \Omega_{B\mathfrak{q}/A_\mathfrak{p}}\to 0$

which implies our desired inequality since

$\Omega_{A_\mathfrak{p}/A}=(\Omega_{A/A})_\mathfrak{p}=0$

Finally, we see that $\Omega_{B_\mathfrak{q}/A}=(\Omega_{B/A})_\mathfrak{q}$. Thus, $(\Omega_{B/A})_\mathfrak{q}=0$ as desired.

To prove that 2. implies 3., we may, once again, assume that we’re affine, and that $f$ is of finite type. Say, $X=\text{Spec}(B)$ and $Y=\text{Spec}(A)$. Now, since we’ve restricted to the affine case, we know that the diagonal map $\Delta:X\to X\times_Y X$ is a closed embedding, corresponding to the usual (surjective!) multiplication map $\mu:B\otimes_A B\to B$. Note then that the ideal sheaf corresponding to the closed subset $\Delta(X)$ (with the reduced structure) is $I:=\ker\mu$. Now, since $\Omega_{B/A}=\widetilde{I/I^2}$ (Hartshorne 8.1.A), we know, by assumption, that

$0=(\Omega_{B/A})_\mathfrak{p}=(I/I^2)_{\Delta(\mathfrak{p})}=I_{\Delta(\mathfrak{p})}/I^2_{\Delta(\mathfrak{p})}$

Now, since $f$ is of finite type, it’s easy to see that $I_{\Delta(\mathfrak{p})}$ is a finitely generated $(B\otimes_A B)_{\Delta(\mathfrak{p})}$-module. Thus, by Nakayama’s lemma we may conclude that $I_{\Delta(\mathfrak{p})}=0$. But, then, by geometric Nakayama’s lemma (see Vakil exercise 13.7.E) we may conclude that $I$ vanishes in a neighborhood $U$ of $\Delta(x)$. Then, by definition, the map $\Delta\mid_{\Delta^{-1}(U)}:\Delta^{-1}(U)\to U$ is an isomorphism. Thus, $\Delta$ is an open immersion in a neighborhood of $x$ as desired.

Finally, to prove that 3. implies 1., we make a set of reductions. As always, we may assume that $X=\text{Spec}(B)$, $Y=\text{Spec}(A)$, $x=\mathfrak{q}$, and $y=\mathfrak{p}$, and by shrinking small enough we may assume that $\Delta_{X/Y}$ is an open immersion. Let us first claim that we can base change to the fiber over $y$. Namely, consider the following fibered diagram

$\begin{matrix}\text{Spec}(B_\mathfrak{p}/\mathfrak{p}B_\mathfrak{p}) & \to & \text{Spec}(B)\\ \downarrow & & \downarrow\\ \text{Spec}(k(\mathfrak{p})) & \to & \text{Spec}(A)\end{matrix}$

For notational convenience, let us denote ideals of $B_{\mathfrak{p}}/\mathfrak{p}B_\mathfrak{p}$ by $\overline{I}$, where $I$ is an ideal of $B_\mathfrak{p}$. Note then that if $\overline{\mathfrak{q}B_\mathfrak{p}}$ is the point corresponding to $x$, then the localization of $B_\mathfrak{p}/\mathfrak{p}B_\mathfrak{p}$ at this prime is $B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q}$, and the residue field at this point is $(B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q})/(\mathfrak{q}B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q})\cong k(\mathfrak{q})$. Thus, the property of 1. holding for $\text{Spec}(B_\mathfrak{p}/\mathfrak{p}B_\mathfrak{p})$ for the point $\overline{\mathfrak{q}B_\mathfrak{p}}$ (in the domain) and $(0)$ (in the codomain) are equivalent to

$0=(0)B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q}=\mathfrak{q}B_\mathfrak{q}/\mathfrak{p}B_\mathfrak{q}$

and that $k(\overline{\mathfrak{q}B_\mathfrak{p}})=k(\mathfrak{q})$ is a finite separable extension of $k(\mathfrak{p})$. Since the centered equation is equivalent to $\mathfrak{p}B_\mathfrak{q}=\mathfrak{q}B_\mathfrak{q}$, we may thus conclude that the property of 1. holding for $\text{Spec}(B_\mathfrak{p}/\mathfrak{p}B_\mathfrak{p})$ for the point $\overline{\mathfrak{q}B_\mathfrak{p}}$ and $(0)$ is equivalent to 1. holding for $X\to Y$ with $x$ and $y$.

So, since base change of open immersions are open immersions (and the base change of the diagonal is the diagonal of the base change), we can assume, without loss of generality, that $X=\text{Spec}(B)$, $Y=\text{Spec}(k)$ (for some field $k$).

To prove that 3. implies 1. in this case, let’s first prove it in the even more specific case when $k=\overline{k}$. Let us first show that $X$ must be finite. Since $X$ is quasi-compact, it suffices to show that it’s closed points are discrete. Indeed, this will then imply (from basic algebra) that $B$ is Artinian, and so has finite spectrum. So, take any closed point $p\in X$, and consider the associated morphism $s:\text{Spec}(k)\to X$ (here we are using that $k=\overline{k}$ so that all closed points are $k$-points). Now, we have the following fibered diagram

$\begin{matrix}\text{Spec}(k) & \to & \text{Spec}(k)\times_{\text{Spec}(k)} X\\ \downarrow & & \downarrow\\ X & \to & X\times_{\text{Spec}(k)} X\end{matrix}$

where $\text{Spec}(k)\to\text{Spec}(k)\times_{\text{Spec}(k)} X$ is the identity on the first entry, and $s$ on the second (this makes clear why we needed that all closed points are $k$-rational). But, there is a natural isomorphism $\text{Spec}(k)\times_{\text{Spec}(k)}X\to X$, and so the composition

$\text{Spec}(k)\to\text{Spec}(k)\times_{\text{Spec}(k)}X\to X$

is open. But, the composition is just $s$. Thus, $p$ is an open point. Thus, from the above (and the fact that $B/k$ is finite type) we may conclude that $B$ is Artinian, and so $X$ is finite. But, we’ve also shown that for each point $p$ we have an isomorphism $k \to \mathcal{O}_{X,p}$ which implies, in particular that 1. holds in this setup.

Finally, let us deduce the result for a general $k$. Now, we have a surjection $X_{\overline{k}}\to X$ (where $X_{\overline{k}}$ is base change to $\text{Spec}(\overline{k})$) and since base change of open immersions are open immersions (and base change of the diagonal is the diagonal of the base change) we know from the previous paragraph that $X_{\overline{k}}$ is finite. Thus, so is $X$, and so $B$ is Artinian. Since this problem is purely local, we may as well now work with $\text{Spec}(\mathcal{O}_{X,x})$ which is an open subscheme of $X$. Now, we know from the previous paragraph that $\mathcal{O}_{X,x}\otimes_k \overline{k}$ is $\overline{k}^m$, for some $m$, and thus $\mathcal{O}_{X,x}$ is reduced. We claim that this implies that $\mathcal{O}_{X,x}$ is a finite separable field extension of $k$. It’s finite since

$\dim_k\mathcal{O}_{X,x}=\dim_{\overline{k}}(\mathcal{O}_{X,x}\otimes_k \overline{k})=m$

It’s reduced since $\mathcal{O}_{X,x}$ embeds into $\mathcal{O}_{X,x}\otimes_k\overline{k}$ which is reduced. This implies it’s a field since it’s then a reduced local Artinian ring. Finally, it’s separable since it’s base change to $\overline{k}$ is reduced which is a common equivalent definition of separability. $\blacksquare$

Thus, we may unabashedly define a morphism $f:X\to Y$, locally of finite presentation, to be unramified at $x$ if any of the equivalent properties in Theorem 1 hold. We then define $f$ to be unramified if it is locally of finite presentation and it is unramified at all $x\in X$. If $f$ is not unramified at a point $x\in X$, we say that $f$ is ramified there.

One important thing to note, is that implicit in our proof of Theorem 1 (namely in 3. implies 1.) we’ve shown that

Corollary 2: If $f:X\to Y$ is unramified, then it is locally quasifinite.

This intuitively makes sense, insomuch as the obvious case of non-quasifiniteness is ramified. In particular, when one things of a point for which has no neighborhood on which $f$ is quasifinite, one probably thinks of a point where infinitely many sheets (maybe so many that they can’t be ‘discretely’ distinguished!) come together. This is clearly not a picture of an unramified morphism.

Just as in the case of flatness, unramifiedness is not necessarily a black-and-white notion. Some points of $f$ can be unramified, and others can be ramified. In particular, we can define the unramified locus of a, locally of finite presentation, morphism $f:X\to Y$ to be the set of $x\in X$ for which $f$ is unramified at $x$. Similarly, we define the ramification locus of $f$ to be the points of $X$ for which $f$ is ramified there.

Note that the unramified locus is simply the complement of the support of $\Omega_{X/Y}$ (as a sheaf). Said differently, the ramification locus of $f$ is the support of $\Omega_{X/Y}$. In particular, we see that $f$ is unramified if and only if the unramified locus is all of $X$, if and only if $\text{Supp}(\Omega_{X/Y})=0$. But, this is equivalent to $\Omega_{X/Y}=0$. Thus, we see that unramifiedness, for a morphism locally of finite presentation, is equivalent to $\Omega_{X/Y}$ being the zero sheaf.

Also, this point of view allows us to see that if $X$ is locally Noetherian, then $\text{Supp}(\Omega_{X/Y})$, being the support of a coherent sheaf on a locally Noetherian scheme, is closed. Thus, we have the following:

Theorem 3: If $f:X\to Y$ is unramified, and $X$ is locally Noetherian, then the unramified locus of $f$ is open.

## Geometric Examples

Let us now do some examples, to show that our intuition about unramified morphisms developed in the motivation, does translate well into this formal setting.

Let us first consider the natural example of a map $\mathbb{A}^n_k\to\mathbb{A}^m_k$, where $k$ is a field, and $n> m$. Now, intuitively we would expect this to be unramified. For example. it’s somewhat obvious that there is not unicity of tangent vector lifts–this isn’t a “differential immersion” (it is a differential submersion, which will be validated when we discuss smooth morphisms). To prove this though, we need to compute $\Omega_{\mathbb{A}^n/\mathbb{A}^m}=\widetilde{\Omega_{A/B}}$ where $B=k[x_1,\ldots,x_n]$ and $A=k[x_1,\ldots,x_m]$. Since $B$ is a free $A$-algebra of rank $n-m$, it follows from the basic theory of differentials that $\Omega_{B/A}$ is a free $B$-module of rank $n-m$. In particular, we see that not only is $\mathbb{A}^n_k\to\mathbb{A}^m_k$ not unramified (i.e. $\Omega_{X/Y}=0$), but that it’s ramification locus is empty–it is everywhere ramified. This matches our intuitive picture.

Let’s now consider another classic geometric example. In particular, let’s consider the normalization $\mathbb{A}^1_k\to C$, where $C$ is the cuspidal cubic curve $C=\text{Spec}(k[x,y]/(y^2-x^3))=\text{Spec}(k[t^2,t^3])$. For the sake of convenience, we assume that $\text{char}(k)\ne 2$.

This normalization map corresponds to the $k$-algebra map coming from the inclusion mapping $A=[t^2,t^3]\to k[t]=B$. To find the ramification locus we need to compute $\Omega_{\mathbb{A}^1/C}=\widetilde{\Omega_{B/A}}$. To do this, we note that $B=A[x]/(x^2-t^2)$. Thus, from the basic theory of differentials, we know that $\Omega_{B/A}$ is the $B$-module generated by the symbol $dx$, and subject to the relation

$0=d(x^2-t^2)=d(x^2)-d(t^2)=2dx-0=2dx$

Thus, $\Omega_{B/A}$ is isomorphic, as a $B$-module, to $Bdx/B(2dx)$ which, is isomorphic to

$A[x]/(2x,x^2-t^2)=k[t]/(2t)=k[t]/(t)$

So, we see that the ramification locus of the normalization, $\text{Supp}(\Omega_{X/Y})$, which is just the support of $k[t]/(t)$ as a $k[t]$-module, is just $(t)$. Thus, we see that the unramified locus of the normalization is $\mathbb{A}^1_k-\{(t)\}$. So, the only point of ramification is the origin. This is not unexpected, since we know that the normalization is an isomorphism off of the cusp, and there the picture “looks ramified”, since the cusp has “several directions” in which to lift tangent vectors.

Let us compute another geometric example. Consider the squaring map $\mathbb{A}^1_k\to\mathbb{A}^1_k$, where $\text{char}(k)\ne 2$. This corresponds to the inclusion $A=k[t^2]\hookrightarrow k[t]=B$. To find there this squaring map is ramified, we should, as always, compute the differentials. Namely, we want to compute $\Omega_{\mathbb{A}^1_k/\mathbb{A}^1_k}$, which is just $\widetilde{\Omega_{B/A}}$. But, just as in the last computation, we find that

$\Omega_{B/A}=\Omega_{B[x]/(x^2-t^2)/B}=Bdx/B(2dx)=k[t]/(t)$

and so the squaring map is ramified only at the origin. This is not shocking. In fact, if one thinks about it, the squaring map was the map depicted in the “Unicity of Tangent Vectors” section.

Intuitively, for every $p\in k^\times$, we have that there are two preimages of the squaring map. But, at the point $0$, there is only one preimage. Of course, this isn’t totally correct since there is no reason that $k$ must be closed under squareroots, but since ramification is an intuitively geometric notion, and shouldn’t depend on base change to field extensions, we may as well assume $k=\overline{k}$.

A good example to talk about, even though we implicitly used it in the proof of Theorem 1, is the case of $f:\text{Spec}(L)\to\text{Spec}(K)$ where $L/K$ is a finite field extension. In particular, if $L/K$ is finite and separable, then $f$ is unramified. To prove this, we must merely show that $\Omega_{L/K}=0$. But, since $L/K$ is finite separable, the primitive element theorem tells us that $L=K[x]/(p(x))$ for some irreducible, separable $p(x)\in K[x]$. So,

$\Omega_{L/K}=L dx/ L d(p(x))=Ldx/L p'(x)dx$

which, if we write $L=K[x]/(p(x))$ is the same as $K[x]/(p(x),p'(x))$. But, this is equal to zero since $p$ is separable so that $(p(x),p'(x))=K[x]$.

Of course, while all of the above examples have been affine, since ramification is a local (stalk-local!) condition, we can always reduce to the affine case. For example, we know that the structure map $\mathbb{P}^1_k\to\text{Spec}(k)$ to be ramified everywhere. Indeed, locally, this is just the $n=1$ and $m=0$ case of our first example. That being said, one can compute though that $\Omega_{\mathbb{P}^1_k/k}=\mathcal{O}(-2)$. This is just because a rational section of $\Omega_{\mathbb{P}^1_k/k}$, where $\mathbb{P}^1_k$ has coordinates $[x:y]$, is $dx$. But, at infinity this section transforms to $d(x^{-1})=x^{-2}dx$, which gives the desired equality. Then the everywhere ramifiedness is clear since $\Omega_{\mathbb{P}^1_k/k}$ is vector bundle of positive rank, and so has nowhere vanishing stalks.

Just to mention, there is not a general formula for $\Omega_{\mathbb{P}^n_k/k}$. There is just the Euler sequence which says that $\Omega_{\mathbb{P}^n_k/k}$ sits in the exact sequence of sheaves

$0\to\Omega_{\mathbb{P}^n_k/k}\to \mathcal{O}_{\mathbb{P}^n_k}^{\oplus (n+1)}\to \mathcal{O}_{\mathbb{P}^n_k}\to 0$

This tells us that $\Omega_{\mathbb{P}^n_k/k}$ is locally free of rank $n$ (which, once we talk about smooth morphisms, will be obvious). Also, taking determinants, this shows that the canonical sheaf of $\mathbb{P}^n$ is just $\mathcal{O}_{\mathbb{P}^n_k}(-n-1)$. Our computation for $n=1$ is a coincidence, since in dimension one the differentials and the cotangent sheaf coincide.

## Relation to Number Theory

Let us now address which, to the arithmetically minded, may be the elephant in the room. While we have just defined the notion of ramification for schemes, there is already a well-developed theory of ramification for Dedekind domains. In particular, for an extension of number fields $L/K$, there is the well-known notion of ramification for the associated extension of number rings $\mathcal{O}_L/\mathcal{O}_K$.

Just to recall, suppose that $R\subseteq S$ is an integral extension of Dedekind domains. Then, for any non-zero prime $\mathfrak{p}\in\text{Spec}(R)$, we can look at its extension to $S$, defined to be $\mathfrak{p}S$. Note that $\mathfrak{p}S$ is a proper ideal of $S$. Indeed, since $R\subseteq S$ is an integral extension, the Lying Over Theorem implies that there is some prime $\mathfrak{P}\in\text{Spec}(S)$ restricting to $\mathfrak{p}$. Thus, $\mathfrak{p}S\subseteq\mathfrak{P}$. Thus, since $S$ is a Dedekind domain, we can factor $\mathfrak{p}S$ as a finite product of primes

$\mathfrak{p}S=\mathfrak{P}_1^{e_1}\cdots\mathfrak{P}_n^{e_n}$

One then says that $\mathfrak{p}$ is ramified if one of the $e_i$ is greater than one. Of course, we say that a prime $\mathfrak{p}$ is unramified, if it is not ramified.

The obvious question is how ramification of the ring extensions $R\subseteq S$, a number theoretic consideration, corresponds to ramification of the associated map $\text{Spec}(S)\to\text{Spec}(R)$, a geometric consideration. The first step towards understanding the connection, is the realization that the two different notions of ramification are focused on different parts of the map $\text{Spec}(S)\to\text{Spec}(R)$. Namely, ramification in the sense of algebraic geometry is a $\text{Spec}(S)$-centric notion, whereas the number theoretic idea of ramification is $\text{Spec}(R)$-centric.

With this disparity in mind, we can make clear the connection between the two uses of the word “ramified”. Namely, we claim that $R\subseteq S$ is unramified at a prime $\mathfrak{p}\in\text{Spec}(R)$ if and only if $\text{Spec}(S)\to\text{Spec}(R)$ is unramified at all primes $\mathfrak{P}\in\text{Spec}(S)$ which lie above $\mathfrak{p}$. Indeed, note that for any prime $\mathfrak{P}_i$ lying above $\mathfrak{p}$, we have that

\begin{aligned}\mathfrak{p} S_{\mathfrak{P}_i} &=(\mathfrak{p} S)_{\mathfrak{P}_i}\\ &=(\mathfrak{P}_1^{e_1}\cdots\mathfrak{P}_n^{e_n})_{\mathfrak{P}_i}\\ &= (\mathfrak{P}_1 S_{\mathfrak{P}_i})^{e_1}\cdots (\mathfrak{P}_n S_{\mathfrak{P}_i})^{e_n}\\ &= (\mathfrak{P}_i S_{\mathfrak{P}_i})^{e_i}\end{aligned}

But, $\text{Spec}(S)\to\text{Spec}(R)$ being unramified (in the algebraic geometry sense) at $\mathfrak{P}_i$, is equivalent to $\mathfrak{p}S_{\mathfrak{P}_i}=\mathfrak{P}_i S_{\mathfrak{P}_i}$. So, we see that being unramified at $\mathfrak{P}_i$ is equivalent to $e_i=1$. From this, our claim follows.

In fact, there is an even stronger connection of the algebro-geometric theory of ramification to the ramification theory in number theory. Let us assume that $L/K$ is an extension of number fields, and $\mathcal{O}_L/\mathcal{O}_K$ the associated extension of number rings. Then, we know that cotangent sheaf associated to the map $\text{Spec}(\mathcal{O}_L)\to\text{Spec}(\mathcal{O}_K)$ is just $\widetilde{\Omega_{\mathcal{O}_L/\mathcal{O}_K}}$. Now, let us consider the points of ramification, the support $\text{Supp}(\Omega_{\mathcal{O}_L/\mathcal{O}_K})$. Then, from basic commutative algebra, since $\Omega_{\mathcal{O}_L/\mathcal{O}_K}$ is a finite $\mathcal{O}_L$-module, we have the following equality

$\text{Supp}(\Omega_{\mathcal{O}_L/\mathcal{O}_K})=V(\mathfrak{d})$

where $\mathfrak{d}=\text{Ann}_{\mathcal{O}_L}(\Omega_{\mathcal{O}_L/\mathcal{O}_K})$. Now, in general, if $R$ is any Dedekind domain, and $I$ an ideal of $R$, then $V(I)$ is exactly the same as the set of primes which divide $I$. Thus, we see that $\mathfrak{d}$ is an ideal of $\mathcal{O}_L$ with the property that a prime $\mathfrak{P}\in\text{Spec}(\mathcal{O}_L)$ divides $\mathfrak{d}$ if and only if $\mathfrak{P}\in\text{Supp}(\Omega_{\mathcal{O}_L/\mathcal{O}_K})$ which is true if and only if $\mathfrak{P}$ is a ramified prime.

But, there is another ideal of $\mathcal{O}_L$, familiar to any number theory fans, which satisfies similar properties. Namely, the different (if you are unfamiliar, I suggest you read these fantastic notes of Keith Conrad) of $L/K$, denoted $\mathfrak{d}_{L/K}$, is an ideal of $\mathcal{O}_L$ which satisfies the same properties as our above $\mathfrak{d}$. Namely, that $\mathfrak{P}\mid\mathfrak{d}_{L/K}$ if and only if $\mathfrak{P}$ is a ramified prime (with respect to $L/K$). It is not as well-known as it’s brother, the discriminant, the ideal $\Delta_{L/K}\subseteq\mathcal{O}_K$ which satisfies similar properties (a prime divides it if and only if it ramifies in the sense of number theory). They are related by the ideal norm $N_{L/K}$–in particular, $\Delta_{L/K}=N_{L/K}(\mathfrak{d}_{L/K})$.

The similarities between $\mathfrak{d}$ and $\mathfrak{d}_{L/K}$ aren’t coincidental. As a matter of fact, $\mathfrak{d}=\mathfrak{d}_{L/K}$. The proof of this is not too difficult, and can be found as Proposition 14, III.7 of Serre’s Local Fields. This is nice, because it tells us that not only is our notion of ramification in algebraic geometry consistent with that of number theory, but the objects dictating ramification (cotangent sheaf vs. different/discriminant) are actually intimately related.

Conversely, this connection is also nice since it validates a common, but slightly confusing, practice in number theory. In particular, when one is usually introduced to the notion of ramification, they are often give some sort of geometric motivation. They are drawn a pretty picture like those in the motivation section of this post, and told “look, ramification!” Usually one is told that they should analogize to ramification in, say, the theory or Riemann surfaces, and that these pictures are “actually accurate”. It is never made clear, or was never made clear to me at least, in what way this random geometric picture was “accurate” (beyond the obvious similarities). The above tells us how. The pictures we drew do have logical and easy-to-see connections to our geometric definition of ramification, and the above discussion tells us that this really is what is going on in the arithmetic case. Those pictures aren’t made up, they really are describing the geometry of the situation!

## Arithmetic Examples

With the above theory, we see that giving geometrically minded, but arithmetically motivated, examples is actually entirely arithmetic–this is just plain old number theory. Regardless, we shall give two examples to illustrate the concepts.

Consider first the map $\text{Spec}(\mathbb{Z}[i])\to\text{Spec}(\mathbb{Z})$. It is a classic theorem of number theory, that the only ramified primes of $\mathbb{Z}$ (i.e. ramified in the sense of number theory) in this case are $(2)$. And, since the only prime of $\mathbb{Z}[i]$ which lies above $(2)$ is $(1+i)$, we know (from our above analysis) that the only ramified prime in this situation (in the sense of algebraic geometry) is $(1+i)$. Let us verify this by hand though, just to see that it all works out. Namely, let us being by computing $\Omega_{\mathbb{Z}[i]/\mathbb{Z}}$. To do this, we first express $\mathbb{Z}[i]$ as $\mathbb{Z}[T]/(T^2+1)$. Then, we can compute $\Omega_{\mathbb{Z}[i]/\mathbb{Z}}$ in the usual way. It is the $\mathbb{Z}[i]$-module generated by the symbol $dT$, subject to the relation that $0=d(T^2+1)=2dT$. In particular, we see that

$\Omega_{\mathbb{Z}[i]/\mathbb{Z}}\cong \mathbb{Z}[i]dT/\mathbb{Z}[i]2dT\cong \mathbb{Z}[i]/2\mathbb{Z}[i]$

From this, it’s easy to see that if $2\notin\mathfrak{P}$, for $\mathfrak{P}\in\text{Spec}(\mathbb{Z}[i])$, then $(\Omega_{\mathbb{Z}[i]/\mathbb{Z}})_\mathfrak{P}$, being just $(\mathbb{Z}[i]/2\mathbb{Z}[i])_\mathfrak{P}$, is zero. And, if $2\in\mathfrak{P}$, then $(\Omega_{\mathbb{Z}[i]/\mathbb{Z}})_\mathfrak{P}$, being just $(\mathbb{Z}[i]/2\mathbb{Z}[i])_\mathfrak{P}$, is non-zero since $2$ is not inverted. Thus, we see that the only ramified primes are those containing $2$. Or, in other words, the only ramified prime is $(1+i)$. Thus, we arrive at the same conclusion as in number theory (like we knew we must).

Consider now the extension of number field $L/K$, where $L=\mathbb{Q}(\sqrt{-5},\sqrt{3})$ and $K=\mathbb{Q}(\sqrt{-15})$. The number theoretic amongst us might recognize $L$ as the Hilbert class field of $K$. Thus, in particular, we know that $\mathcal{O}_L/\mathcal{O}_K$ is unramified. So, we know that

$X=\text{Spec}(\mathcal{O}_L)\to\text{Spec}(\mathcal{O}_K)=Y$

must be unramified, and so

$0=\Omega_{X/Y}=\widetilde{\Omega_{\mathcal{O}_L/\mathcal{O}_K}}$

from which we may conclude that $\Omega_{\mathcal{O}_L/\mathcal{O}_K}=0$. Of course, if we really wanted to get our hands really dirty, we could work the other way. Namely, to show that $\mathcal{O}_L/\mathcal{O}_K$ is unramified, we could show that $\Omega_{\mathcal{O}_L/\mathcal{O}_K}=0$. This would be computationally intensive though. Indeed, we’d have to find a presentation for $\mathcal{O}_L$ as a $\mathcal{O}_K$-algebra, and then proceed our normal way. This isn’t totally infeasible, with computer assistance from something like SAGE, but is not particularly enlightening in this instance.

## Properties of Unramified Morphisms

Let us now discuss some of the properties that hold true for unramified morphisms.

First and foremost the permanence properties of unramified morphisms

Theorem 4: The class of unramified morphisms is closed under composition and base-change.

Proof: Suppose that $f:X\to Y$ and $g:Y\to Z$ is unramified. Let us show that $g\circ f:X\to Z$ is unramified. To see this, let $x\in X$ be arbitrary. We then want to show that $\mathfrak{m}_z\mathcal{O}_{X,x}=\mathfrak{m}_x$, and $k(x)/k(z)$ is finite separable. But,

$\mathfrak{m}_z\mathcal{O}_{X,x}=(\mathfrak{m}_z\mathcal{O}_{Y,y})\mathcal{O}_{X,x}=\mathfrak{m}_y\mathcal{O}_{X,x}=\mathfrak{m}_x$

and since $k(x)/k(z)$ has the subextension $k(x)/k(y)$, and both $k(x)/k(y)$ and $k(y)/k(z)$ are finite separable, so is $k(x)/k(z)$.

Suppose now that we have a fibered diagram of the following form

$\begin{matrix}P & \xrightarrow{p} & X\\ \downarrow & & \downarrow\\ Y & \to & S\end{matrix}$

where $X\to S$ is unramified. We want to show that $P\to Y$ is unramified. But, from basic theory of differentials we know that $\Omega_{P/Y}=p^\ast(\Omega_{X/S})$. In particular, since $p^\ast$ is additive, and $\Omega_{X/S}=0$, we know that $\Omega_{P/Y}=0$ from which the conclusion follows. $\blacksquare$

Now, while we gave many examples of ramified and unramified morphisms above, we have yet to discuss an entire class of morphisms which belong to either camp. To this end, we have the following:

Theorem 5: Every monomorphism, locally of finite presentation, is unramified.

Proof: Let $f:X\to Y$ be a monomorphism locally of finite presentation. Then, it suffices to show that the diagonal morphism of $f$ is an open embedding. But, since $f$ is a monomorphism, we know that the diagonal map is actually an isomorphism. $\blacksquare$

Corollary 6: Every locally closed embedding is unramified.

This allows us to prove that the class of unramified morphisms has the so-called “cancellation property”. Namely:

Theorem 7: If $f:X\to Y$ and $g:Y\to Z$ be morphisms, and $g\circ f$ is unramified, then $f$ is unramified.

Proof: We may apply the Cancellation Theorem (cf. Vakil’s Fundamentals of Algebraic Geometry 10.1.19), since $\Delta_g$, being locally closed, is unramified. $\blacksquare$

We also have somewhat of a converse to “base change of unramified morphisms are unramified”, if we assume the extra condition of faithful flatness:

Theorem 8: Suppose that the following diagram is fibered:

$\begin{matrix} P & \xrightarrow{p} & X\\ ^{g}\downarrow & & \downarrow ^{f}\\ Y & \xrightarrow{q} & S\end{matrix}$

$f$ is locally of finite presentation, and $p$ faithfully flat. Then, if $g$ is unramified, then so is $f$.

Proof: Since $f$ is locally of finite presentation, it suffices to check that $\Omega_{X/S}=0$. But, s

$0=\Omega_{P/Y}=p^\ast(\Omega_{X/S})$

Since $p$ is faithfully flat, this implies that $\Omega_{X/S}=0$ as desired. $\blacksquare$

In particular, this tells us that unramifiedness really is a “geometric” notion, as hinted at in the motivation. Namely, let’s suppose that $X$ and $Y$ are $k$-schemes. Then, the following diagram is fibered

$\begin{matrix}X_{\overline{k}} & \to & X\\ \downarrow & & \downarrow\\ Y_{\overline{k}} & \to & Y\end{matrix}$

and, since $Y_{\overline{k}}\to Y$ is faithfully flat (being the base change of the faithfully flat map $\text{Spec}(\overline{k})\to\text{Spec}(k)$) Theorem 8 tells us that $X_{\overline{k}}\to Y_{\overline{k}}$ is unramified if and only if $X\to Y$ is.

Finally, we prove a theorem which says that it’s hard to be a section of an unramified morphism. Indeed, intuitively, from our pictures, if you’re a section, then by continuity you should stay within one of the sheets. So, intuitively, sections of “nice” unramified morphisms should be just picking out one of (or a subset of) the sheets. This is what the following proposition says:

Theorem 9:  Let $f:X\to Y$ be unramified and separated. Then, the sections of $f$ are open embeddings.

We can’t prove this quite yet–we need first to talk about etale morphisms, and in particular characterize open embeddings as radiciel etale morphisms.

## Lifting Lemma: Unicity of Tangent Vectors

Let us now discuss the final rigorous definition of unramifiedness, and relate it back to the above definitions. As the header suggests, this is the unicity of tangent vector lifts. More rigorously, let $f:X\to Y$ be any morphism. We say that $f$ is formally unramified if for all pairs $(A,I)$, where $A$ is a ring, and $I$ is a square-zero ideal (i.e. $I^2=0$), and for any choice of a $Y$-structure $\text{Spec}(A)\to Y$ for $\text{Spec}(A)$, the following map is injective

$\text{Hom}_Y(\text{Spec}(A),X)\to\text{Hom}_Y(\text{Spec}(A/I),X)$

where, of course, $\text{Spec}(A/I)$ is given the structure of a $Y$-scheme via the natural composition $\text{Spec}(A/I)\to\text{Spec}(A)\to Y$.

Our formal claim then becomes the following:

Theorem 10: Let $f:X\to Y$ be locally of finite presentation. Then, $f$ is unramified if and only if it is formally unramified.

Before we prove this though, we need one quick, but important lemma:

Lemma 11: Let $B$ be a ring, and $A$ and $C$ two $B$-algebras. Let $I$ be a square-zero ideal of $A$ and $p$ the projection map $A\to A/I$. Suppose that $\phi:C\to A$ is a $B$-algebra map. Then there exists a bijective correspondence between the set

$\{\psi:C\to A\mid \psi\text{ is a }B\text{-morphism satisfying }p\circ\phi=p\circ\psi\}$

and $\text{Hom}_{A/I}(\Omega_{C/B}\otimes_C (A/I),I)$, where $A/I$ is regarded as a $C$-algebra via the composition $p\circ\phi$.

This is a somewhat nebulous lemma, but is quite familiar to those who have studied some amount of deformation theory. Good intuition for this lemma, and a proof, can be found in Hartshorne’s Deformation Theory–the actual theorem is Lemma 4.5.

Proof: Let’s first suppose that $f$ is unramified. Let $A$ be a ring, and $I$ a square-zero ideal. Suppose further that we have given $\text{Spec}(A)$ the structure of a $Y$-scheme. We want to show that the natural map

$\text{Hom}_Y(\text{Spec}(A),X)\to\text{Hom}_Y(\text{Spec}(A/I),X)$

is injective. But,

$\text{Hom}_Y(\text{Spec}(A),X)=\text{Hom}_A (\text{Spec}(A),X\times_Y \text{Spec}(A))$

and

$\text{Hom}_A(\text{Spec}(A),X\times_Y \text{Spec}(A)$

Thus, by base-change, we may assume that $Y=\text{Spec}(A)$. Or, in other words, we need to show that if $A$ is a ring and $I$ is any square-zero ideal, then

$\text{Hom}_A(\text{Spec}(A),X)\to\text{Hom}_A(\text{Spec}(A/I),X)$

is injective. But, now any element $\varphi$ of $\text{Hom}_A(\text{Spec}(A),X)$ is, by definition, a section of the unramified map $f:X\to\text{Spec}(A)$. But, by Theorem 9, we know then that $\varphi$ is an open embedding. In particular, $\varphi$ is determined by its image. But, if $\varphi,\psi\in\text{Hom}_A(\text{Spec}(A),X)$ are mapped to the same element of $\text{Hom}_A(\text{Spec}(A/I),X)$ then they have the same images, since $\text{Spec}(A/I)\to\text{Spec}(A)$ is surjective. From previous comment, it follows that $\varphi=\psi$.

Conversely, let’s suppose that we have unicity of tangent vector lifts. Since unramifiedness is a local condition, we may as well assume that $X$ and $Y$ are affine, say $X=\text{Spec}(C)$ and $Y=\text{Spec}(B)$. We must show that $\Omega_{C/B}=0$. Now, note that under the assumptions of the unicity of tangent vector lifts, we have that $C$ and $A$ are both $B$-algebras. Now, if there is a $B$-algebra homomorphism $\phi:C\to A$ then, note that

$\{\psi:C\to A\mid \psi\text{ is a }B\text{-morphism satisfying }p\circ\phi=p\circ\psi\}$

is nothing more than the preimage of $p\circ\phi$ under

$\text{Hom}_\text{Spec}(B)(\text{Spec}(A),\text{Spec}(C))\to\text{Hom}_\text{Spec}(B)(\text{Spec}(A/I),\text{Spec}(C))$

Indeed, “un-affinizing” this, we see that this is merely the (natural) map of sets

$\text{Hom}_B(C,A)\to\text{Hom}_B(C,A/I)$

Then, $p\circ\phi\in \text{Hom}_B(C,A/I)$, and $\psi\in\text{Hom}_B(C,A)$ is in the preimage of of $p\circ\phi$ if and only if $\psi$ is a $B$-algebra homomorphism $C\to A$ such that $p\circ\psi=p\circ\phi$.

Thus, we see that for any $B$-algebra map $\phi:C\to A$, we have, by the injectivity of

$\text{Hom}_\text{Spec}(B)(\text{Spec}(A),\text{Spec}(C))\to\text{Hom}_\text{Spec}(B)(\text{Spec}(A/I),\text{Spec}(C))$

that

$\{\psi:C\to A\mid \psi\text{ is a }B\text{-morphism satisfying }p\circ\phi=p\circ\psi\}$

is a singleton. But, by the lemma, this implies that

$\text{Hom}_{A/I}(\Omega_{C/B}\otimes_C (A/I),I)$

is a singleton, and so must be the zero module.

Now, the goal is to cleverly choose $A$ such that the zeroness of this Hom-module implies $\Omega_{C/B}$. But, we know that $\Omega_{C/B}=0$ if and only if $\text{Hom}_C(\Omega_{C/B},\Omega_{C/B})=0$ (where this is Hom of $C$-modules). But, $\Omega_{C/B}$ is merely $J/J^2$, where $J=\ker(\mu)$ where $\mu$ is the multiplication map $C\otimes_B C\to C$. Thus, we see that if we let $A=C\otimes_B C/J^2$, and $I=J/J^2$, then by the tensor-hom adjunction:

$\text{Hom}_C(\Omega_{C/B},\Omega_{C/B})=\text{Hom}_C(\Omega_{C/B},I)=\text{Hom}_{A/I}(\Omega_{C/B}\otimes_C (A/I),I)$

But, note that $C$ and $A$ are both $B$-algebras, $I^2=0$, and $\phi:C\to A$ defined by the natural composition $C\to C\otimes_B C\to C\otimes_B C/J^2$ (where we can map into either side of the tensor in the first map) is a $B$-algebra map. Thus, from the above discussion, we may conclude that $\Omega_{C/B}=0$ as desired. $\blacksquare$

1. It is easy to figure out examples of schemes X,S and an algebra A over S with a square zero ideal I such that X/S is ramified and the lifting lemma fails for this particular choice. For instance take the squaring map on $\mathbb A^1$ and A = k[e] with $e^2 = 0$.

There is a similar lifting characterization of (formal) smoothness where we want the induced map on Hom spaces to be surjective instead of injective. Do you know an example of a non smooth scheme X/S such that one can explicitly demonstrate the failure of the lifting lemma?

I tried the nodal/cuspidal curve over k and over $\mathbb A^1$ but I wasn’t able to find an A that worked…

1. Perhaps I should add that I do know an example which works: the squaring map. It looks like the tangent spaces at 0 gets mapped all to 0 (which one should expect from non injectivity anyway…). I would still like to understand the case of a cusp or a node over the field…

1. Hey Asvin,

I haven’t verified it, but I have a hunch that $\text{Spec}(k[s,t]/(s^2 t^2))$ might work.

2. Thanks for the suggestion Alex. The algebra seems quite difficult but I am really after intuition anyway, could you explain what intuition guided you towards that example?

2. Hi Alex, I found out that simply taking $A = k[\epsilon]/(\epsilon^3)$ and $A/I = k[\epsilon]/(\epsilon^2)$ works in the cuspidal case, thanks for the help anyway!


text:
# What is the naming reason of poles in complex analysis?

A function $f: \textbf{C} \to \textbf{C}$ has a pole of order $k$ if $f(z) = \frac{g(z)}{(z-z_0)^{k}}$ where $g(z)$ is a nonzero analytic function. Why do we call it poles?

• It's because they correspond to the north pole when considered as holomorphic functions onto the riemann sphere. – muad Sep 21 '10 at 20:50
• Insert your favorite Polish joke here. – Nate Eldredge Sep 21 '10 at 21:21
• I, too, would like this question stay open. Please, count it as a vote against closing per old meta discussion. – Victor Protsak Sep 21 '10 at 22:21
• @Nate: There was a transatlantic flight and the pilot and copilot dropped dead. A desperate flight attendant asked if anyone knew how to fly a plane. An old polish man said "Well, I used to fly planes in WWII, but nothing like this". When she brought him into the cockpit, his jaw dropped. There was so many buttons, levers, and fancy dials. "What's wrong?" the flight attendant asked. "I'm just a simple pole in a complex plane" he responded. – David Carchedi Sep 21 '10 at 23:20
• I hope this comment counts as a vote against closing too. The question seems to be a hard one, well worth the attention of the MO community. I notice that the historian Judith Grabiner asked this question on an internet forum in 1998, and she apparently did not receive an answer. – John Stillwell Sep 22 '10 at 0:10

The answer suggested by @muad’s comment is supported by both P. Ullrich (1989, p. 163):

The expressions “pole” and “polar singularity” were apparently first used in the 1865 book “Vorlesungen über Riemann’s Theorie der Abel’schen Integrale” of Carl Neumann (1832–1925): they are precisely the points that the function maps to the “pole” of the Riemann sphere. Neumann’s book, by the way, is also the first to develop the theory of the Riemann sphere, which Riemann himself had only presented in his lectures. (See Neuenschwander (1978) (...).)

(my emphasis) and A. Markushevich (1996, p. 191):

The classification of the singularities of an algebraic function as poles and critical points was carried out, for example, in the Théorie des fonctions elliptiques of Briot and Bouquet (1875). However, the term “pole,” as pointed out by E. Neuenschwander (1978) was first used in this sense by K. Neumann in his Vorlesungen über Riemann’s Theorie der Abelschen Integrale (1865) in connection with the fact that the point at infinity was depicted as the pole of the sphere in this book.

The quoted article of Neuenschwander notes that the histories by Brill-Noether (1894, p. 170) and Osgood in the Encyklopädie (1901, p. 18) both miscredit Briot and Bouquet. So does (as of now) the earliest uses site — quoting an edition (1859) where the word pôle does not even appear.

I have wondered if Neumann was perhaps inspired by prior uses of “pole” for homographies or inversions, $$f(z)=\frac{az+b}{cz+d}\qquad\text{or}\qquad f(z) = a+\frac k{\bar z-\bar a},$$ (presumably then traceable to Stubbs, Chasles, Servois,...) but couldn't find solid evidence.

As Martin O remarks, the French word "pôle" (or the German "Pol") does not include the meaning "pillar", that's why the explanation "looks like a pillar" seems a bit dubious, at least to me.

Being a native German speaker, I have always associated the word "pole" to the electrical pole and thus to the function $\frac1{r^2}$. It seems entirely natural to me to use this special example as a prototype for any singularity of a (complex) function.

• According to the online etymological dictionary, the English word pole derives from the Latin word palus meaning stake. So the term could be handed down to us from when mathematicians still wrote in Latin. The term could also derive from Greek, polos (axis of a sphere), or it could be a coincidence. Simply because the direct cognate of a word in German doesn't correspond to the current meaning of an English word doesn't mean the words didn't have similar meanings long ago. The English word table is related to the German word Tafel even though Tafel only infrequently means table. – Peter Luthy Sep 22 '10 at 18:11
• A word derived from the Latin palus=stake does exist in German: Pfahl. In contrast, the Greek word polos becomes polus in Latin. So it appears that the North pole and the pole that is used to mark it actually have different etymological origins. – Michael Renardy Aug 13 '17 at 1:55

This may be apocryphal folk etymology, but I always thought it was because if you plot, or envision plotting, the surface z = |f(x + iy)|, at poles of f, the surface, if you imagine it sitting over the xy plane, looks like it is being supported by a really tall pole. Like a circus tent. I have no citations to support this belief, but I must have gotten it from somewhere. Anyway it makes a good deal of sense.

I'm posting this, despite not having an MO account, because genuinely can't understand why nobody has posted it yet. (Nikita's "because poles stick up" comes close, but seems to have been drowned out by posts about poles being "big", or invocations of the north pole, which seem to be entirely different explanations.)

• This is a nice explanation, but I don't think that this is the correct one since in French (and German) the translation of your use of pole would not be "pôle" (or "Pol"). I guess it is rather related to the poles of a magnet. – Martin O Sep 21 '10 at 23:21
• Perhaps an explanation that would also make sense in French and German is that the value of a function at a pole is equal to infinity, the North pole of the Riemann sphere. – Faisal Sep 21 '10 at 23:52
• Upon reading the question, I figured something very close to Faisal's comment above. Poles are where $f(z)$ is the (North) Pole in the Riemann sphere. This, by the way, would make sense also in Italian (where "polo" is used both for Earth's poles and for, well, poles of meromorphic functions, whereas the "tall pole" in anon's answer is a "palo"). – Andrea Mori Sep 22 '10 at 8:12
• On second thought, I'm not so sure. For instance because the sphere has two poles (and for the Riemann sphere interpretation a zero should be called a "southern pole"). So I thought that maybe the two names are not directly related and they both derive from some other older meaning of the term. So, a relevant side question may be "why the Earth's poles are called such and who was the first to name them so?". Is a question for cartographers too off topic for MO? :-) – Andrea Mori Sep 22 '10 at 8:16
• @Martin: According to the online etymological dictionary, the English word pole derives from the Latin word palus meaning stake. So the term could be handed down to us from when mathematicians still wrote in Latin. The term could also derive from Greek, polos (axis of a sphere), or it could be a coincidence. Simply because the direct cognate of a word in German doesn't correspond to the current meaning of an English word doesn't mean the words didn't have similar meanings long ago. The English word table is related to the German word Tafel even though Tafel only infrequently means table. – Peter Luthy Sep 22 '10 at 18:09

According to these pages, the earliest known appearance of the term pole might be in "Théorie des fonctions elliptiques" (1875, p. 15) by Briot and Bouquet:

Lorsqu'une fonction $u$ est holomorphe dans une certaine partie du plan, excepté en un point $z_1$, où elle devient infinie, de manière toutefois que la fonction $\frac{1}{u}$ reste holomorphe dans le voisinage de ce point, on dit que ce point est un pôle ou un infini de la fonction $u$.

They don't provide any motivation for this choice of a term though.

By the way, in their first memoir on the subject, "Étude des fonctions d'une variable imaginaire" (1856), Briot and Bouquet refer to a pole of a function only as un infini du degré fini.

• To add to this, I have looked at the pages referred to for other words and they seem well-researched to me (who is not a mathematical historian). – Torsten Ekedahl Nov 7 '10 at 5:41
• "When a function u is holomorphic in a certain part of the plane, except for one point z_1, where it becomes infinite, similar to the function 1/u which remains holomorphic at the neighborhood of that point, we say that this point is a pole or an infinity of the function u." In the earlier paper, it's called "an infinity of finite degree". – Yuval Filmus Nov 7 '10 at 6:47
• I posted this as a comment to the main question a while back, but it apparently got buried... – j.c. Nov 7 '10 at 12:45
• @jc: I haven't noticed your previous comment, sorry. I'm making this answer Community Wiki. – Andrey Rekalo Nov 7 '10 at 12:56

This picture

should make it clear why they are called poles.

• These pictures used to be included in many complex analysis texts a few decades ago. I haven't encountered them in any of the recent book, though. – Andrés E. Caicedo Sep 22 '10 at 4:34


text:
C. Machine Programming
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One remarkable day company "X" received k machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story.

The company has now n tasks, for each of them we know the start time of its execution si, the duration of its execution ti, and the company profit from its completion ci. Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from si to si + ti - 1, inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these k machines, and which will bring the maximum total profit.

Input

The first line contains two integer numbers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 50) — the numbers of tasks and machines, correspondingly.

The next n lines contain space-separated groups of three integers si, ti, ci (1 ≤ si, ti ≤ 109, 1 ≤ ci ≤ 106), si is the time where they start executing the i-th task, ti is the duration of the i-th task and ci is the profit of its execution.

Output

Print n integers x1, x2, ..., xn. Number xi should equal 1, if task i should be completed and otherwise it should equal 0.

If there are several optimal solutions, print any of them.

Examples
Input
3 12 7 51 3 34 1 3
Output
0 1 1
Input
5 21 5 41 4 51 3 24 1 25 6 1
Output
1 1 0 0 1
Note

In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).


text:
# What is connection between Pearson correlation coefficient and proportion of variance explained in PCA?

PCA procedure includes SVD of Covariance matrix. Based on eigenvalues we can find a proportion of variance explained by related Principal Components (eigenvectors).

variance explained by PC1 (in case symmetric matrix) = eigenvalue1 / (sum of all eigenvalues) * 100%

We form a covariance matrix as [ [SD1^2, RO*SD1*SD2], [RO*SD1*SD2, SD2^2]] (SD = standard deviation, RO = Pearson correlation coefficient)

It is clear that if RO = 1 then PC1 explains ~100% of the variance.

Can you please suggest intuition and a general (mathematical) connection between Pearson correlation coefficient and proportion of variance explained in PCA?


text:
# Stable marriage problem

In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is not stable if:

1. There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
2. B also prefers A over the element to which B is already matched.

In other words, a matching is stable when there does not exist any match (A, B) which both prefer each other to their current partner under the matching.

The stable marriage problem has been stated as follows:

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

Note that the existence of two classes that need to be paired with each other (men and women in this example), distinguishes this problem from the stable roommates problem.

## Applications

Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments.[1] In 2012, The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel was awarded to Lloyd S. Shapley and Alvin E. Roth "for the theory of stable allocations and the practice of market design."[2]

An important and large-scale application of stable marriage is in assigning users to servers in a large distributed Internet service.[3] Billions of users access web pages, videos, and other services on the Internet, requiring each user to be matched to one of (potentially) hundreds of thousands of servers around the world that offer that service. A user prefers servers that are proximal enough to provide a faster response time for the requested service, resulting in a (partial) preferential ordering of the servers for each user. Each server prefers to serve users that it can with a lower cost, resulting in a (partial) preferential ordering of users for each server. Content delivery networks that distribute much of the world's content and services solve this large and complex stable marriage problem between users and servers every tens of seconds to enable billions of users to be matched up with their respective servers that can provide the requested web pages, videos, or other services.[3]

## Solution

Animation showing an example of the Gale–Shapley algorithm

In 1962, David Gale and Lloyd Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.[4][5]

The Gale–Shapley algorithm (also known as the Deferred Acceptance algorithm) involves a number of "rounds" (or "iterations"):

• In the first round, first a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her.
• In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, she rejects her current provisional partner who becomes unengaged). The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).
• This process is repeated until everyone is engaged.

The runtime complexity of this algorithm is ${\displaystyle O(n^{2})}$ where ${\displaystyle n}$ is the number of men or women.[6]

This algorithm guarantees that:

Everyone gets married
At the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being proposed to, she would necessarily be engaged (to someone) thereafter.
The marriages are stable
Let Alice and Bob both be engaged, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

## Algorithm

function stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = first woman on m's list to whom m has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
m' becomes free
(m, w) become engaged
else
(m', w) remain engaged
}
}

## Different stable matchings

In general, there may be many different stable matchings. For example, suppose there are three men (A,B,C) and three women (X,Y,Z) which have preferences of:

A: YXZ   B: ZYX   C: XZY
X: BAC   Y: CBA   Z: ACB

There are three stable solutions to this matching arrangement:

• men get their first choice and women their third - (AY, BZ, CX);
• all participants get their second choice - (AX, BY, CZ);
• women get their first choice and men their third - (AZ, BX, CY).

All three are stable, because instability requires one of the participants to be happier with an alternative match. Giving one group their first choices ensures that the matches are stable because they would be unhappy with any other proposed match. Giving everyone their second choice ensures that any other match would be disliked by one of the parties.

## Optimality of the solution

Proof that deferred acceptance is optimal for men

The existence of different stable matchings raises the question: which matching is returned by the Gale-Shapley algorithm? Is it the matching better for men, for women, or the intermediate one? In the above example, the algorithm converges in a single round on the men-optimal solution because each woman receives exactly one proposal, and therefore selects that proposal as her best choice, ensuring that each man has an accepted offer, ending the match.

This is a general fact: the Gale-Shapley algorithm in which men propose to women always yields a stable matching that is the best for all men among all stable matchings. Similarly, if the women propose then the resulting matching is the best for all women among all stable matchings.

To see this, consider the illustration at the right. Let A be the matching generated by the men-proposing algorithm, and B an alternative stable matching that is better for at least one man, say m0. Suppose m0 is matched in B to a woman w1, which he prefers to his match in A. This means that in A, m0 has visited w1, but she rejected him (this is denoted by the green arrow from m0 to w1). w1 rejected him in favor of some man that she prefers, say m2. So in B, w1 is matched to m0 but "yearns" (wants but unmatched) to m2 (this is denoted by the red arrow from w1 to m2).

Since B is a stable matching, m2 must be matched in B to some woman he prefers to w1, say w3. This means that in A, m2 has visited w3 before arriving at w1, which means that w3 has rejected him. By similar considerations, and since the graph is finite, we must eventually have a directed cycle in which each man was rejected in A by the next woman in the cycle, who rejected him in favor of the next man in the cycle. But this is impossible since such "cycle of rejections" cannot start anywhere: suppose by contradiction that it starts at e.g. m0 - the first man rejected by his adjacent woman (w1). By assumption, this rejection happens only after m2 comes to w1. But this can happen only after w3 rejects m2 - contradiction to m0 being the first.

## Strategic considerations

The GS algorithm is a truthful mechanism from the point of view of men (the proposing side). I.e, no man can get a better matching for himself by misrepresenting his preferences. Moreover, the GS algorithm is even group-strategy proof for men, i.e., no coalition of men can coordinate a misrepresentation of their preferences such that all men in the coalition are strictly better-off.[7] However, it is possible for some coalition to misrepresent their preferences such that some men are better-off and the other men retain the same partner.[8]

The GS algorithm is non-truthful for the women (the reviewing side): each woman may be able to misrepresent her preferences and get a better match.

## Counting the stable matchings

In a uniformly-random instance of the stable marriage problem with n men and n women, the average number of stable matchings is asymptotically ${\displaystyle e^{-1}n\ln n}$.[9]

The maximum grows at least exponentially with n, and counting the number of stable matchings in a given instance is ♯P-complete.[10]

## Implementation in software packages

• R: The Gale–Shapley algorithm (also referred to as deferred-acceptance algorithm) for the stable marriage and the hospitals/residents problem is available as part of the matchingMarkets[11][12] and matchingR[13] packages.
• API: The MatchingTools API provides a free application programming interface for the Gale–Shapley algorithm.[14]
• Python: The Gale–Shapley algorithm is included along with several others for generalized matching problems in the QuantEcon/MatchingMarkets.py package[15]
• Matlab: The Gale–Shapley algorithm is implemented in the assign2DStable function that is part of the United States Naval Research Laboratory's free Tracker Component Library.[16]

## Similar problems

In stable matching with indifference, some men might be indifferent between two or more women and vice versa.

The stable roommates problem is similar to the stable marriage problem, but differs in that all participants belong to a single pool (instead of being divided into equal numbers of "men" and "women").

The hospitals/residents problem – also known as the college admissions problem – differs from the stable marriage problem in that a hospital can take multiple residents, or a college can take an incoming class of more than one student. Algorithms to solve the hospitals/residents problem can be hospital-oriented (as the NRMP was before 1995)[17] or resident-oriented. This problem was solved, with an algorithm, in the same original paper by Gale and Shapley, in which the stable marriage problem was solved.[18]

The hospitals/residents problem with couples allows the set of residents to include couples who must be assigned together, either to the same hospital or to a specific pair of hospitals chosen by the couple (e.g., a married couple want to ensure that they will stay together and not be stuck in programs that are far away from each other). The addition of couples to the hospitals/residents problem renders the problem NP-complete.[19]

The assignment problem seeks to find a matching in a weighted bipartite graph that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.

The matching with contracts problem is a generalization of matching problem, in which participants can be matched with different terms of contracts.[20] An important special case of contracts is matching with flexible wages.[21]

## References

1. ^ Stable Matching Algorithms
2. ^ "The Prize in Economic Sciences 2012". Nobelprize.org. Retrieved 2013-09-09.
3. ^ a b Bruce Maggs and Ramesh Sitaraman (2015). "Algorithmic nuggets in content delivery" (PDF). ACM SIGCOMM Computer Communication Review. 45 (3).
4. ^ Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly. 69 (1): 9–14. doi:10.2307/2312726. JSTOR 2312726.
5. ^ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
6. ^ Iwama, Kazuo; Miyazaki, Shuichi (2008). "A Survey of the Stable Marriage Problem and Its Variants". International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008): 131–136. doi:10.1109/ICKS.2008.7. hdl:2433/226940. ISBN 978-0-7695-3128-1.
7. ^ Dubins, L. E.; Freedman, D. A. (1981-08-01). "Machiavelli and the Gale-Shapley Algorithm". The American Mathematical Monthly. 88 (7): 485–494. doi:10.1080/00029890.1981.11995301. ISSN 0002-9890.
8. ^ Huang, Chien-Chung (2006). Azar, Yossi; Erlebach, Thomas (eds.). "Cheating by Men in the Gale-Shapley Stable Matching Algorithm". Algorithms – ESA 2006. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 4168: 418–431. doi:10.1007/11841036_39. ISBN 9783540388760.
9. ^ "SIAM (Society for Industrial and Applied Mathematics)". doi:10.1137/0402048. Cite journal requires |journal= (help)
10. ^ "SIAM (Society for Industrial and Applied Mathematics)". doi:10.1137/0215048. Cite journal requires |journal= (help)
11. ^ Klein, T. (2015). "Analysis of Stable Matchings in R: Package matchingMarkets" (PDF). Vignette to R Package MatchingMarkets.
12. ^ "matchingMarkets: Analysis of Stable Matchings". R Project.
13. ^ "matchingR: Matching Algorithms in R and C++". R Project.
14. ^
15. ^ "matchingMarkets.py". Python package.
16. ^ "Tracker Component Library". Matlab Repository. Retrieved January 5, 2019.
17. ^ Robinson, Sara (April 2003). "Are Medical Students Meeting Their (Best Possible) Match?" (PDF). SIAM News (3): 36. Retrieved 2 January 2018.
18. ^ Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly. 69 (1): 9–14. doi:10.2307/2312726. JSTOR 2312726.
19. ^ Gusfield, D.; Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. p. 54. ISBN 0-262-07118-5.
20. ^ Hatfield, John William; Milgrom, Paul (2005). "Matching with Contracts". American Economic Review. 95 (4): 913–935. doi:10.1257/0002828054825466. JSTOR 4132699.
21. ^ Crawford, Vincent; Knoer, Elsie Marie (1981). "Job Matching with Heterogeneous Firms and Workers". Econometrica. 49 (2): 437–450. doi:10.2307/1913320. JSTOR 1913320.


text:
# Running a loop to check for multiple congruences

I have the code for a loop to run. Right now it can check if a number is a square and at the same time check if it is congruent 0 mod 47. My questions is, how can I alter the code to see if it is congruent for more than one prime. SO for instance I would like it to check that a number is congruent, 0 mod 5, 0 mod 13 and 0 mod 17 all at once and only keep or print the numbers which are. I would try something like: 'Select[Range[10^7]^2, Divisible[7 # + 4, 5], Divisible[7 # + 4, 13], Divisible[7 # + 4, 17] &]' but it just prints numbers most of which I am assuming do not satisfy the desired effect

• Select[Range[10^5]^2, Divisible[#, 5] && Divisible[#, 13] && Divisible[#, 17] &]? – Henrik Schumacher Mar 20 '19 at 23:14
• also I would really like to be able to check whether (4^n)-1 is congruent 0 mod5 0 mod 13 and 0 mod 17 not for 7n+4 – argamon Mar 20 '19 at 23:15
• thank you @HenrikSchumacher, I actually do not care if the number is a perfect square rather it must have the form (4^n)-1. I apologize for my ignorance but your help is greatly appreciated – argamon Mar 20 '19 at 23:17
• Well, I don't see any problem here. You already found that you may use Select. The only thing you did wrong is not to use And (&&). The selection function is required to produce either True or False. And, of course, you may use any list you like as first argument of Select. – Henrik Schumacher Mar 20 '19 at 23:21

To find solutions, for example, the code:

FindInstance[{n == a^2, 7 n + 4 == m, m == 5 b}, {n, m, a, b}, Integers]

returns {} to indicate no solutions. The alternative code

Reduce[{n == a^2, 7 n + 4 == m, m == 5 b}, {m}, Integers]

returns False similarly. Try variations of these codes depending on your needs.

However, both Reduce[] and FindInstance[] are not good with exponential equations.

For that, you can use some code

Select[2^Range[0, 20] - 1, Divisible[#, 5] && Divisible[#, 13] &]

which returns {0, 4095} and you can try variations of this.

• Thank you, I just want to adjust it so that it does it for numbers of the form (4^n)-1 so I tried the following code and it does nothing: – argamon Mar 20 '19 at 23:29
• Select[Table[Divisible[(4^i)-1,5] && Divisible [(4^i)-1, 13] && Divisible[(4^i)-1,17] {i,200} &] – argamon Mar 20 '19 at 23:29
• That is helpful but how could I use that to check for it being divisible by 5 and 13 and 17 at the same time or if I change the base 4 to 3 lets say? – argamon Mar 20 '19 at 23:49
• I tried adjusting the base and it tells me that everything is zero: – argamon Mar 20 '19 at 23:51
• {In[3]:= FindInstance[{2^i-1 == n, n == 5 a}, {i, a, n}, Integers] Out[3]= {{i -> 0, a -> 0, n -> 0}} – argamon Mar 20 '19 at 23:51

For the question, expressed in a comment by argamon, of finding numbers of the form (4^n)-1 congruent to 0 mod 5, 0 mod 13, and 0 mod 17, please consider the function ChineseRemainder.

Block[{c},
Flatten[Table[
c = ChineseRemainder[{0, 0, 0}, {5, 13, 17}, m];
If[c == m, m, {}],
{m, Table[4^k - 1, {k, 1, 50}]}]]
]

{16777215, 281474976710655, 4722366482869645213695, 79228162514264337593543950335}


text:
# Easy Sudoku Puzzles Printable

Easy Sudoku Puzzles Printable | Encouraged to be able to my weblog, in this particular moment We’ll provide you with in relation to Easy Sudoku Puzzles Printable. Now, this can be a initial graphic: beginner sudoku puzzles printable, easy sudoku puzzles printable, easy sudoku puzzles printable pdf, easy sudoku puzzles printable with answers, printable easy sudoku puzzles 4 per page,

Why don’t you consider graphic over? can be which remarkable???. if you think maybe therefore, I’l l show you a number of image once again underneath: printable sudoku puzzles easy #1,

Thanks for visiting my blog, article above(Easy Sudoku Puzzles Printable) published by admin at June, 4 2020.


text:
## 2015 AIME II Problem 6

The other day I came across a problem which reminded me vaguely of the infamous Cheryl’s Birthday Problem (more technical but somewhat easier). Have a go!

2015 AIME II 6. Steve says to Jon, “I am thinking of a polynomial whose roots are all positive integers. The polynomial has the form $P(x) = 2x^3 - 2ax^2 + (a^2 - 81)x - c$ for some positive integers $a$ and $c$. Can you tell me the values of $a$ and $c$?

After some calculations, Jon says, “There is more than one such polynomial.”

Steve says, “You’re right. Here is the value of $a$.” He writes down a positive integer and asks, “Can you tell me the value of $c$?”

Jon says, “There are still two possible values of $c$.”

Find the sum of the two possible values of $c$.