text:
Fix YAML parsing errors in WebGen

After a clean install of Mac OS X Yosemite I’ve had to reinstall much of my development environment. This process was mostly beneficial as I moved to the latest and greatest tooling but several of my static websites leverage the prior major version of Thomas Leitner’s Webgen and getting version 0.5.x up and running has been a challenge.

After working through several Ruby & Gem issues I ran into a particularly opaque error when executing webgen on a project that previously generated without issue: “(): found character that cannot start any token while scanning for the next token”

This error is usually a sign that your content contains tab characters but I’d already ensured that wasn’t the case. Instead of diving deep into the workings of the libraries at play I was able to use this post from Thomas to resolve the issue by reverting to the syck TAML implementation instead of its replacement. Problem solved!


text:
# How do I get from $-4(x+\frac{1}{2})^2+4$ to $4-(2x+1)^2$?

I'm trying to follow along with printed solutions to previous exam questions, and I'm completely stumped as to how this makes any sense.

I had to complete the square for the function $3-4x-4x^2$, and I got $-4(x+\frac{1}{2})^2+4$. But that's not the final form I need it in because I"m trying to use the solution to integrate a function... so the solution says that I need it in the form $4-(2x+1)^2$, but I cannot figure out how to transform it to that. It could very well be because I'm a bit tired right now, but could somebody point out how it's happening?

$$-4(x+\frac{1}{2})^2 + 4$$ $$-4(x^2 + \frac{1}{2}x + \frac{1}{2}x + \frac{1}{4}) + 4$$ $$-4x^2 - 2x - 2x - 1 + 4$$ $$4 + (-4x^2 - 4x - 1)$$ $$4 - (4x^2 + 4x + 1)$$ $$4 - (2x + 1)^2$$

• I recommend not undoing and then redoing completing the square. Rather, one can use the identity $4(\text{stuff})^2=(2\text{stuff})^2$. – Jonas Meyer Apr 16 '13 at 3:53
• Well I definitely agree, but I thought the OP wanted a very step-by -step answer! – Tyler McAtee Apr 16 '13 at 3:58
• Upvote for your answer! :) – Tyler McAtee Apr 16 '13 at 3:58
• @Mathbro: If you think that $4(\text{stuff})^2=(2\text{stuff})^2$ is not step-by-step, you can just introduce an expression in between: write it as $(4)(\text{stuff}^2)=(2)^2(\text{stuff})^2 = (2\text{stuff})^2$ – ShreevatsaR Apr 16 '13 at 18:58
• You do not need to put it in that form to integrate. The form you have it in is fine.
• You can use the identities $-a+b=b-a$, and $4a^2=(2a)^2$. Note that there is no need to redo your completing the square; you can just absorb the $4=2^2$ into the square.

You can use either forms (they are equivalent) to integrate: the solution you are referring to just offers one form of the function for integrating purposes; it's not the only "correct" form of the function.

Applying the suggestions posted by by @Jonas Meyer:

\begin{align} -4\left(x + \dfrac 12\right)^2 + 4 & \;= \;4 - 4\left( x +\dfrac 12 \right)^2 \\ & =\; 4 - 2^2\left( x +\dfrac 12 \right)^2 \\ & = \;4 - \left(2\left(x + \dfrac 12 \right)\right)^2 \\ \\ & = \;4 - \left(2x+1\right)^2 \end{align}

The process involved in obtaining the given "solution", if you begin from the start, is just another way to "complete the square": \begin{align} 3 - 4x - 4x^2 \; & =\; 4 - 1 - 4x - 4x^2 \\ \\ & =\; 4 - (4x^2 + 4x + 1) \\ \\ & =\; 4 - (2x+1 )^2 \\ \end{align}

giving you a function of the form $a^2 - b^2$ where $a = 2$, and $b = (2x+1)$. Depending on the method used to evaluate the relevant integral, one form may be easier to work with than the other.

• I didn't mention what exactly I was trying to integrate - this is only part of a much bigger question. I needed to convert $\int\frac{6}{\sqrt{3-4x-4x^2}}\ dx$ to a form that I can integrate to $\arcsin{u/a}$. Thanks for the input anyhow. – agent154 Apr 16 '13 at 19:06

$-4(x+ \dfrac{1}{2})^2+4$

$=-2 \cdot2(x^2+\dfrac{1}{4}+x)+4$

$=-4x^2-1-4x+4$

$=4-(4x^2+1+4x)$

$=4-(2x+1)^2$

format: plain


text:
The current GATK version is 3.7-0
Examples: Monday, today, last week, Mar 26, 3/26/04

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

GATK 3.7 is here! Be sure to read the Version Highlights and optionally the full Release Notes.
Register now for the upcoming GATK Best Practices workshop, Feb 20-22 in Leuven, Belgium. Open to all comers! More info and signup at http://bit.ly/2i4mGxz

Rare variants from annotated vcf file

New YorkMember Posts: 5
edited February 2014

Hi,

I have annotated my vcf file of 20 samples from Unified genotyper using the following steps.

Unified genotyper->Variantrecalibration->Applyrecalibration->VariantAnnotator

My question is how should I proceed if I have to select rare variants (MAF<1%) for the candidate genes that I have,for each of these 20 samples?

Post edited by rohan1925 on
Tagged:

edited February 2014

Hi there,

If you're asking how you should design your analysis, I'm afraid this question is beyond our current scope of support. I can only point you to the variant manipulation tools (e.g. SelectVariants) and answer specific questions about how to use them.

Geraldine Van der Auwera, PhD

• New YorkMember Posts: 5
edited February 2014

I want to use SelectVariants only since I have used all the tools from GATK until Variant Annotator for variants.So in this how should I get MAF (minor allele frequency) to be less than 1%,using -AF parameter?

Also,I need to select variants only for candidate genes that I have.

Ah, sorry to get back to you so late. I believe you should be able to do that simply using -select "AF < 0.01". Let me know if that doesn't work for you.

Geraldine Van der Auwera, PhD

• New YorkMember Posts: 5

Hi,

Thanks for your response! I am using this command,and getting some error.

java -Xmx2g -jar /GenomeAnalysisTK-2.7-4-g6f46d11/GenomeAnalysisTK.jar -T SelectVariants -R human_g1k_v37.fasta --variant annotated.vcf -o annotated.select.vcf -select "AF<0.01"

ERROR stack trace

java.lang.IllegalArgumentException: Invalid JEXL expression detected for select-0 with message ![0,9]: 'AF < 0.01;' < error


text:
# Green's function for Laplacian in the plane. Why does the constant matter?

The Green's function for the Laplacian in the plane is $$G(\mathbf{x},\mathbf{x_0}) = \frac{1}{4\pi}\log(||\mathbf{x}-\mathbf{x_0}||^2)$$

That is to say, $G$ satisfies $$\triangle_{\mathbf{x}}G = \delta(\mathbf{x}-\mathbf{x_0})$$

where $\triangle$ is the Laplacian operator, and $\delta$ is the Dirac function.

In an effort to convince myself of this, I computed by hand the Laplacian of $G$, and obtained $$\triangle_{\mathbf{x}}G = \frac{-1}{2\pi}\frac{2r^2-2r^2}{r^4}$$ where $r= ||\mathbf{x}-\mathbf{x_0}||^2$.

Two questions:

Is this really equal to the $\delta$ function? Certainly it's equal to $0$ for $r \neq 0$, but for $r=0$ can we really say that it blows up? I suppose since $r > 0$, the value tends to $\infty$.

The more important question: Why does the initial factor of $\frac{1}{4\pi}$ even matter? We could have started out with any arbitrary constant and obtained the same property for the Laplacian.

• The prefactor $\require{cancel}\cancel{1 \over 4\pi}$ must be, indeed $\color{#f00}{-\,{1 \over 2\pi}}$. Usually, the Green function is defined as $\ln\left\vert\,\vec{r} - \vec{R}\,\right\vert$ such that $\nabla^{2}\ln\left\vert\,\vec{r} - \vec{R}\,\right\vert = -2\pi\,\delta\left(\,\vec{r} - \vec{R}\,\right)$. – Felix Marin May 15 '17 at 3:18

We can redefine the problem to circumvent use of the Dirac Delta. So, rather than describing the problem by the expression $\nabla^2 G(\vec \rho|\vec \rho')=\delta(\vec \rho-\vec \rho')$ we describe the function $G(\vec \rho|\vec \rho')$ to satisfy the equations

\begin{align} \nabla^2 G(\vec \rho|\vec \rho')&=0\,\,\ \dots\vec \rho\ne \vec \rho'\tag 1\\\\ \lim_{\epsilon\to 0}\oint_{|\vec \rho-\vec \rho'|=\epsilon}\nabla' G(\vec \rho|\vec \rho')\cdot \hat n'\,d\ell'&=1\tag2 \end{align}

As determined in the OP, $(1)$ is satisfied for $G(\vec \rho|\vec \rho')=\frac{1}{2\pi }\log(|\vec \rho-\vec \rho'|)$.

To see that this form of $G$ satisfies $(2)$ we see that on $|\vec \rho-\vec \rho'|=\epsilon$, we have $\color{blue}{\nabla' G(\vec \rho|\vec \rho')=\frac{1}{2\pi}\frac{\vec \rho'-\vec \rho}{|\vec \rho-\vec \rho'|^2}}$, $\color{red}{\hat n'=\frac{\vec \rho'-\vec \rho}{|\vec \rho-\vec \rho'|}}$, and $\color{green}{d\ell'=|\vec \rho-\vec \rho'|\,d\phi'}$, where $\phi'\in [0,2\pi]$. Putting everything together reveals

$$\oint_{|\vec \rho-\vec \rho'|=R} \color{blue}{\nabla'G(\vec \rho|\vec \rho')}\cdot \color{red}{\hat n'}\,\color{green}{d\ell'}=\int_0^{2\pi} \color{blue}{\left(\frac{1}{2\pi}\frac{\vec \rho'-\vec \rho}{|\vec \rho-\vec \rho'|^2}\right)}\cdot \color{red}{\left(\frac{\vec \rho'-\vec \rho}{|\vec \rho-\vec \rho'|}\right)}\,\color{green}{\left(|\vec \rho-\vec \rho'|\,d\phi'\right)}=1$$

as was to be shown! In fact, note that we didn't need to let $\epsilon\to 0$. We only require that $\epsilon$ is small enough so that the disk $|\vec \rho-\vec \rho'|=\epsilon$ is contained inside the open domain of interest.

Establishing that Solution to $(1)$ and $(2)$ is the Green (Green's) Function

We show now the motivation for describing the Green (or Green's) function to the problem $\nabla^2 \phi(\rho)=f(\rho)$, where $f$ is a smooth function with compact support. We write $\phi(\vec \rho)$ as the superposition integral

$$\phi(\vec \rho)=\int_S G(\vec\rho|\vec\rho')f(\vec \rho')\,dS'\tag 3$$

We have $\nabla^2 G(\vec \rho|\vec\rho')=0$ for $\vec\rho\ne\vec\rho'$. In addition, we require $\phi$ to satisfy $\nabla^2 \phi(\vec \rho)=f(\vec \rho)$.

Accordingly, we apply the Laplacian to $(3)$ and write

\begin{align} \nabla^2 \phi(\vec \rho)&=\nabla \cdot \int_S \nabla G(\vec\rho|\vec\rho')f(\vec \rho')\,dS'\\\\ &=-\nabla \cdot \int_S \nabla' G(\vec\rho|\vec\rho')f(\vec \rho')\,dS'\\\\ &=-\nabla \cdot \int_S \left(\nabla'\left(G(\vec\rho|\vec\rho')f(\vec \rho')\right)-G(\vec\rho|\vec\rho')\nabla'f(\vec \rho')\right)\,dS'\\\\ &=-\nabla \cdot \underbrace{\oint_{\partial S} G(\vec\rho|\vec\rho')f(\vec \rho') \,\hat n'\,d\ell'}_{=0\,\,\text{since}\,f\,\text{is of compact support}}+\nabla \cdot \int_S G(\vec\rho|\vec\rho')\nabla'f(\vec \rho')\,dS'\\\\ &=-\int_S \nabla' G(\vec\rho|\vec\rho')\cdot \nabla'f(\vec \rho')\,dS'\\\\ &=-\int_S \nabla' \cdot \left(\nabla' G(\vec\rho|\vec\rho')f(\vec \rho')-f(\vec \rho')\underbrace{\nabla'^2 G(\vec \rho|\vec \rho')}_{=0}\right)\,dS'\\\\ &=-\underbrace{\oint_{\partial S}\hat n'\cdot\nabla' G(\vec\rho|\vec\rho')f(\vec \rho')\,d\ell'}_{=0,\,\text{since}\,f\,\text{is of compact support}}+\oint_{|\vec \rho-\vec \rho'|=\epsilon}\hat n'\cdot \nabla' G(\vec\rho|\vec\rho')f(\vec \rho')\,d\ell'\\\\ &=\underbrace{\oint_{|\vec \rho-\vec \rho'|=\epsilon}\hat n'\cdot \nabla' G(\vec\rho|\vec\rho')(f(\vec \rho')-f(\vec \rho))\,d\ell'}_{\to 0\,\,\text{as}\,\,\epsilon \to 0}+f(\vec \rho)\oint_{|\vec \rho-\vec \rho'|=\epsilon}\nabla' G(\vec\rho|\vec\rho')\cdot \hat n'\,d\ell' \end{align}

Therefore, we see that $\nabla^2 \phi(\vec \rho)=f(\vec \rho)$ if $\nabla^2 G(\vec\rho|\vec\rho')=0$ for $\vec \rho\ne \vec \rho'$ and

$$\lim_{\epsilon \to 0}\oint_{|\vec \rho-\vec \rho'|=\epsilon}\nabla' G(\vec\rho|\vec\rho')\cdot \hat n'\,d\ell'=1$$

This is precisely the description given by $(1)$ and $(2)$ and establishes a way forward without using distributions.

• There is still a bit of "formal integration by parts" going on in order to obtain your second identity, which is the whole idea of the distribution theory calculation, but still, nice. – Ian May 14 '17 at 22:14
• @Ian No, there is not. I'm redefining the problem in a way that circumvents generalized functions. – Mark Viola May 14 '17 at 22:29
• How do you arrive at (2) then? – Ian May 14 '17 at 22:40
• @Ian I've edited to provide the answer to your question. ;-)) – Mark Viola May 14 '17 at 23:45
• What a well-explained and thoughtful answer. Many thanks! – Alex May 15 '17 at 13:19

You need distribution theory to really know what's going on. In the sense of distribution theory, the equation $\Delta G(x) = \delta(x)$ means that whenever $\phi$ is a smooth function with compact support, you have the "formal" equation

$$\int_{\mathbb{R}^2} (\Delta G)(x) \phi(x) dx = \int_{\mathbb{R}^2} \phi(x) \delta(x) dx.$$

The right side is understood by the definition of the delta function to be $\phi(0)$. The left side is understood through the definition of the distributional derivative as meaning

$$\int_{\mathbb{R}^2} G(x) (\Delta \phi)(x) dx.$$

This has meaning because the singularity in $G$ at $x=0$ is integrable.

This also tells you why the constant factor matters: if you replace $G$ with $cG$ for a constant $c \neq 1$ then you get $c \phi(0)$ out of the integration, which is not what you should have for the Green's function.

• Another way to understand what's going on is to consider instead some nascent delta function $\delta_t(\mathbf{x})$ which converges (in an appropriate weak sense) to $\delta(\mathbf{x})$ as $t\to 0^+$. In that case, the requirement that $\int_{\mathbb{R}^2}\delta(\mathbf{x})\,d\mathbf{x}=1$ again fixes the overall normalization constant. – Semiclassical May 14 '17 at 21:50

Here is a non-rigorous argument (along the lines of SemiClassical's comment), which I hope you find satisfying nonetheless:

Without loss of generality, set $\mathbf x_0 = 0$. So $$G(\mathbf x, \mathbf 0) = \frac 1 {4\pi} \ln r^2 = \frac 1 {2\pi} \ln r,$$ where $r$ is the radial polar coordinate.

Let's consider the integral $$\int_{B(0, \epsilon)} \nabla^2_{\mathbf x} G(\mathbf x, \mathbf 0) \ dA,$$ where $B(0, \epsilon)$ is the disk of radius $\epsilon$ centred at the origin. Since $$\nabla^2_{\mathbf x} G(\mathbf x, \mathbf 0) = \delta (\mathbf x),$$ we expect the integral to be equal to one.

Now, let's check this, by "computing" the integral using the divergence theorem: \begin{multline} \int_{B(0, \epsilon)} \nabla^2_{\mathbf x} G(\mathbf x, \mathbf 0) \ dA = \int_{\partial B(0, \epsilon)} \nabla_{\mathbf x} G(\mathbf x, \mathbf 0) . \mathbf n \ dl \\ = \int_{\phi = 0}^{\phi = 2\pi} \frac{\partial }{\partial r} \left( \frac{1}{2\pi} \ln r \right) \big\rvert_{r = \epsilon} .\epsilon d \phi = \frac{1}{2\pi\epsilon}.(2\pi \epsilon) = 1,\end{multline} which is what we want.

The reason why this argument is non-rigorous is that the "function" we're integrating is not a genuine function: it takes "values" of zero and infinity. As Ian explained, we need to think about the delta function as a distribution in order to do this properly. (See also Section 2.2.4 of Evans's PDEs book.) Nonetheless, I hope my intuitive argument manages to convince you that we need the factor of $\frac 1 {4\pi}$ in the Green's function.

Integrate, for example, along a circle in the $\ds{xy}$ plane which encloses the origin. Namely,

\begin{align} \int\nabla^{2}\ln\pars{r}\,\dd^{2}\vec{r} & = \int\nabla\cdot\nabla\ln\pars{r}\,\dd^{2}\vec{r} = \int\braces{\partiald{}{x}\bracks{\partiald{\ln\pars{r}}{x}} - \partiald{}{y}\bracks{-\,\partiald{\ln\pars{r}}{y}}}\,\dd^{2}\vec{r} \\[5mm] & = \int\braces{\nabla \times \bracks{-\,\partiald{\ln\pars{r}}{y}\,\hat{x} + \partiald{\ln\pars{r}}{x}\,\hat{y}}}_{\ z}\,\dd^{2}\vec{r} \\[5mm] &= \int\nabla \times \bracks{-\,\partiald{\ln\pars{r}}{y}\,\hat{x} + \partiald{\ln\pars{r}}{x}\,\hat{y}}\cdot \dd\vec{S} \\[5mm] & = \int\bracks{-\,\partiald{\ln\pars{r}}{y}\,\hat{x} + \partiald{\ln\pars{r}}{x}\,\hat{y}}\cdot\dd\vec{r}\qquad\qquad\pars{~Stokes\ Theorem~} \\[5mm] & = \int\bracks{-\,{y \over r^{2}}\,\hat{x} + {x \over r^{2}}\,\hat{y}}\cdot\dd\vec{r} = -\int{ x\,\dd y - y\,\dd x \over r^{2}} = -\int{\pars{\vec{r} \times \,\dd\vec{r}}_{z} \over r^{2}} \\[5mm] & = -\int{r\verts{\dd\vec{r}} \over r^{2}} = -\,{1 \over r}\ \overbrace{\int\verts{\dd\vec{r}}}^{\ds{2\pi r}} = \bbx{-2\pi}\,,\qquad\quad \nabla^{2}\ln\pars{r} = -2\pi\,\delta\pars{\vec{r}} \end{align}

Another approach, similar in spirit to my comment on Ian's answer, is to modify the Green's function to $G_a(\mathbf{x}-\mathbf{x}_0)=\dfrac{1}{4\pi}\ln[a^2+(\mathbf{x}-\mathbf{x}_0)^2]$. Then $$\Delta G_a(\mathbf{x}-\mathbf{x}_0)=\left(\partial_x^2+\partial_y^2\right)\left(\frac{1}{4\pi}\ln[a^2+(x-x_0)^2+(y-y_0)^2]\right)=\frac{1}{\pi}\frac{a^2}{(a^2+(\mathbf{x}-\mathbf{x_0}^2)^2}.$$ One can then verify that $\int_{\mathbb{R}^2} \Delta G_a(\mathbf{x}-\mathbf{x}_0)\,dA=1$ for all $a>0$; if the constant factor wasn't there, this integral wouldn't equal 1.


text:
## SadieK Group Title math (algebra 1) ASAP one year ago one year ago

1. zepdrix Group Title

When we divide terms of similar base, we subtract the exponents. $\large \frac{7^4}{7^2} \qquad = \qquad 7^{4-2}$ Can you solve it from there? :)

I think it is =, because 7^4 - 7^2 = 7^2. 7^2 = 7 x 7, which equals 49, so i think the answer is = to.

3. zepdrix Group Title

Yay good job :)

Thank you!!!

5. LoveYou*69 Group Title

7^4 = 2401 7^2 = 49 2401/49 = 49 49 = 49


text:
Abstract Algebra I
 Level: 0 1 2 3 4 5 6 7
MSC Classification: 20, 12 (Group theory, Field theory and polynomials)

# Getting Oriented

 Rough Guides to Algebra
 General Algebra Special Topics

The main goal in abstract algebra is extending the operations and properties we take for granted on sets we're used to working with (like integers, reals, complex numbers, etc.) to arbitrary sets. This requires precise definitions and requirements on the structure of the set in order to ensure the desired properties are present.

The starting point of abstract algebra is the group, which is just a set with an operation such as addition. A surprising number of sets fit into this category, allowing us to analyze things as diverse as the integers modulo k, invertible matrices, and symmetries of a polygon all at once. We'll eventually turn to the question of classification of groups, which is done both by size and by type.

Later, we will encounter the ring, which is just a set with two operations (traditionally addition and multiplication) such as the real numbers. A related structure is the field, which also has two operations but allows for division as well. Several more definitions fall somewhere between rings and fields with specific defining properties, such as the existence of a division algorithm. Our last goal will be proving the insolvability of the quintic, a subject which demonstrates a strong relationship between groups and fields.

Groups, rings, and fields are the first structures usually encountered in abstract algebra, and the definitions intended to make them look like known sets give rise to a much more general theory. More definitions are made to accommodate this theory than in perhaps any other field of mathematics. Memorizing the most basic definitions is recommended, and will prove to make the rest more palatable.

# Groups

## The Basics

Without further ado, here is the definition of a group:

Definition

A group is a set G with a binary operation * that satisfies the following axioms:

1. Associativity axiom: $(a*b)*c=a*(b*c)$ for all $a,b,c\in G$
2. Identity axiom: there is an element $e\in G$ such that $a*e=e*a$ for all $a \in G$
3. Inverse axiom: for each $a\in G$, there is an element $a^{-1}\in G$ such that $a*a^{-1}=a^{-1}* a=e$.

If, in addition, the operation is commutative ($a*b=b*a$ for all $a,b \in G$), then the group is abelian.

The group is denoted $(G,*)$ if one wishes to specify the operation explicitly. Typical examples of group operation include addition and multiplication. Subtraction and division are usually not group operations since they are not associative.

Some essential group properties include uniqueness of the identity, left and right cancellation laws, and uniqueness of inverses.

The order of a group is the number of elements it contains. Groups may be finite or infinite. The order of an element $a\in G$ is the smallest $k\in\mathbb{Z}^+$ such that $a^k=e$, where exponentiation denotes repeated operation. An element has infinite order if no such integer exists.

### Examples

• Sets that are groups under addition include the integers $\mathbb{Z}$, the rationals $\mathbb{Q}$, the reals $\mathbb{R}$, complex numbers $\mathbb{C}$, vectors, and matrices.
• The set $\mathbb{Z}_n=\{0,1,2,\ldots,n-1\}$ becomes a group under addition modulo n.
• Groups under multiplication include the rationals, the reals, and complex numbers, when 0 is omitted.
• Invertible matrices form a group under matrix multiplication.
• The complex roots of unity $\{e^{2\pi i k/n}\}_{i=0}^{n-1}$ form a group under the operation of complex multiplication. This is actually the same group as addition modulo n.
• The symmetries of a polygon with n sides form the dihedral group $D_n$. It has $2n$ elements: n rotations and n reflections.
• The positive integers less than n that are relatively prime to n form a group under multiplication, denoted $U(n)$. The order of this group defines the Euler phi function: $\phi(n)=|U(n)|$.

## Subgroups and Cyclic Groups

Definition

A subgroup H of a group G is a subset that is itself a group under the operation of G. One writes H < G to indicate this relationship.

For example, under addition one has a chain of subgroups $\mathbb{Z} < \mathbb{Q} < \mathbb{R} < \mathbb{C}$.

A subset is a subgroup if and only if it is closed under both the group operation and inversion. For a finite group, one only needs to test for closure under the group operation.

Here are a few ways to construct a subgroup (in the notation of multiplicative groups):

• The cyclic subgroup $\langle{a}\rangle$ generated by a is $\{e,a,a^{-1},a^2,a^{-2},\ldots,\}$.
• The center $Z(G)$ of G consists of the elements of G that commute with all other elements.
• The centralizer $C(a)$ of $a\in G$ consists of the elements of G that commute with a.

The subgroups $\langle{a}\rangle$ and $Z(G)$ are always abelian. In general, a cyclic group is one generated by a single element (and its inverse). These groups are all abelian and behave like either the integers $\mathbb{Z}$ or the finite group $\mathbb{Z}_n$. Some elementary properties of cyclic groups follow, with $G=\langle{a}\rangle$ having order n:

• if $a^k=e$, then k|n (k divides n);
• $G=\langle{a^k}\rangle$ if and only if $\mathrm{gcd}(n,k)=1$ (these are the generators of the group);
• each divisor $k$ of n corresponds to one subgroup of order k, namely $\langle{a^{n/k}}\rangle$;
• the number of elements of order n is given by $\phi(n)$, the Euler phi function.

## Cosets and Factor Groups

Any subgroup naturally partitions a group into disjoint subsets, called cosets:

Definition

A left coset of a subgroup $H<G$ is a subset $aH=\{ah:h\in H\}$ for some $a\in G$, while a right coset is given analogously by $Ha=\{ha:h\in H\}$.

The fact that the cosets partition the group, and also that $aH=H$ if and only if $a\in H$, follows from:

Lagrange's Theorem

The index $[G:H]=|G|/|H|$ of any subgroup is an integer, equal to the number of distinct left (or right) cosets of H.

It follows immediately that all groups of prime order are cyclic (since they have no nontrivial subgroups), that $a^{|G|}=e$ for all elements $a\in G$, and that $a^p \equiv a \mod p$ for p prime (Fermat's Little Theorem).

When the left and right cosets of a group always coincide, the set of cosets has a group structure:

Definition

A normal subgroup H is one with $aH=Ha$ for all $a\in G$, or equivalently $aH a^{-1}=H$. Normalcy is denoted by $H\lhd G$. The set of cosets of a normal subgroup form the factor group (or quotient group) $G/H$, with operation inherited from the group.

By Lagrange's Theorem, $|G/H|=|G|/|H|$. Elements of a factor group $G/H$ are usually denoted gH for some $g\in G$.

## Group Morphisms

Any "interesting" map between groups should preserve the group operation:

Definition

A homomorphism from one group G to another group G' is a map $\phi:G\to G'$ that preserves the group operation, so that $\phi(ab)=\phi(a)\phi(b)$.

Homomorphisms preserve many properties of a group, taking (abelian or normal) subgroups to (abelian or normal) subgroups. The same is true for the inverse image of a homomorphism.

The notion of group equivalence arises when the map is also bijective.

Definition

An isomorphism is a bijective homomorphism $\phi:G\to G'$ whose inverse $\phi^{-1}:G'\to G$ is also a homomorphism. The groups G and G' are isomorphic, and we write $G\cong G'$.

Every property of a group (other than the names of its elements), is preserved under isomorphism. A fundamental question is classifying non-isomorphic groups. Proving that two groups are not isomorphic is usually not too hard: one just needs to find properties of the two that differ. But proving that two groups are isomorphic requires one to identify a specific isomorphism.

An automorphism is an isomorphism from a group to itself, and such maps form the automorphism group $(\mathrm{Aut}(G),\circ)$ under function composition. Maps of the form $\phi_a(x)=axa^{-1}$ for some $a\in G$ are always automorphisms and form the inner automorphism group $\mathrm{Inn}(G)<\mathrm{Aut}(G)$. As a quick example, $\mathrm{Aut}(\mathbb{Z}_n)\cong U(n)$. Homomorphisms from G to another group G' also form a group, denoted $\mathrm{Hom}(G,G')$, with group operation inherited from the operation on G'.

The center of a group $Z(G)$ is always normal, and the factor group $G/Z(G)$ is isomorphic to the inner automorphism group $\mathrm{Inn}(G)$. In particular, it is cyclic if and only if G is abelian (the G / Z Theorem), and if G is abelian then $Z(G)=G$ so $G/Z(G)$ is trivial. This can be used to show that an abelian group G has elements of each prime order dividing $|G|$.

## Permutation Groups

A permutation group is a group of bijective maps from a set A to itself under the group operation of composition. A first example is the automorphisms $\mathrm{Aut}(G)$. Permutation groups are key in understanding groups:

Cayley's Theorem

Every group is isomorphic to a subgroup of a permutation group.

To specify a permutation, one must clearly show where each element of the set A is taken. In the finite case, one can use the following notation:

(1)
\begin{align} \alpha=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 6 & 5 & 4\end{bmatrix}. \end{align}

This indicates that 1 is mapped to 2, 2 to 3, and so on.

A more compact notation is cycle notation. This would give the above as $(1\:2\:3)(4\:6)$, which means swap 4 and 6, and then rotate 1, 2, and 3. As for function compositions, the process starts on the right and works left. The permutation can also be written as $(2\:3)(1\:3)(4\:6)$. Disjoint cycles commute, and all permutations can be written as a product of disjoint cycles. The order of the permutation is the least common multiple of the cycle lengths.

The group of all $n!$ permutations on n elements is known as the symmetric group $S_n$. Every finite permutation can be written as the product of transpositions, or 2-cycles, and the number of such cycles always has the same parity. Thus, we can speak of even or odd permutations. The even permutations form the Alternating Group An, which has exactly $n!/2$ elements.

Given a group of permutations G on a set A, each element $a\in A$ determines a subgroup of permutations called the stabilizer subgroup, denoted by $\mathrm{stab}(a)$ or Ga, which consists of the permutations that fix a. The element also determines a subset of A called the orbit, denoted by $\mathrm{orb}(a)$ or Ga, which consists of all the elements mapping to a under permutations in the group. The Orbit-Stabilizer Theorem says that $|G|=|\mathrm{orb}(a)||\mathrm{stab}(a)|$ for any $a\in A$.

## The Isomorphism Theorems

In this section we look at three theorems that are also true, with slight modifications, for rings and other algebraic structures besides groups.

The kernel $\ker\phi$ of a homomorphism $\phi:G\to G'$ is the set of elements of G that map to the identity: $\ker\phi = \{g\in G : \phi(g)=e\}$. The image of the homomorphism will be denoted $\phi(G)$.

First Isomorphism Theorem

For any group homomorphism $\phi:G\to G'$, there is an isomorphism $G/\ker\phi \cong \phi(G)$ given by $g\:\ker\phi\mapsto\phi(g)$.

This is somewhat intuitive: it says that the image of a homomorphism looks like a factor group of G with the elements mapping to the identity being trivial.

A corollary is the N/C Theorem, which states that $N(H)/C(H)$ is isomorphic to a subgroup of $\mathrm{Aut}(H)$. (Recall that $N(H)$ is the normalizer of H, the set of elements $g\in G$ with $gH g^{-1}\in H$, and $C(H)$ is the centralizer of H, the elements of G commuting with all elements of H). The isomorphism takes an element $g\in G$ to the inner automorphism $\phi_g:h\mapsto gh g^{-1}$, which is a group homomorphism with kernel $C(H)$.

A simple application of this result is the proof that every group of order 35 is cyclic. First, counting arguments show that G must have elements of order both 5 and 7. Let H be a cyclic subgroup of order 7. One can show that $N(H)=G$ and that $H<C(H)$. But $|N(H)/C(H)|$ must divide 6, the order of $\mathrm{Aut}(H)$, which is possible only if $|C(H)|=35$. Then, an element hk, where $h\in H$ is nontrivial and k has order 5, will generate the group.

The second and third isomorphism theorems have a similar flavor:

• Second Isomorphism Theorem: Given a subgroup $K\leq G$ and a normal subgroup $N\lhd G$, $K/K\cap N \cong KN/N$.
• Third Isomorphism Theorem : Given subgroups $N\lhd M\lhd G$, $\frac{G/N}{M/N}\cong G/M$.

## Direct Products and Finite Abelian Groups

Having analyzed subgroups and factor groups, which in a sense make a group smaller, we now look at direct products, which form bigger groups out of smaller ones. The simplest product group is the external direct product of groups G and G', denoted $G\oplus G'$ and defined as the set of elements $(g,g')$ with operation acting separately on each coordinate. $(G,e')\cong G$ and $(e,G')\cong G'$ are then subgroups.

The order of an element $(g,g')$ is the least common multiple of the orders of g and g'. Thus, a group $G\oplus G'$ is cyclic if and only if both G and G' are cyclic, with $|G|$ and $|G'|$ relatively prime. In particular, for $(m,n)=1$, we have $\mathbb{Z}_m\oplus \mathbb{Z}_n=\mathbb{Z}_{mn}$ and $U(m)\oplus U(n)=U(mn)$.

The internal direct product is a way of representing a given group as a direct product of its subgroups; we write $G=H\times K$ if $G=HK$ where H and K are normal subgroups and $H\cap K=\{e\}$. Since $H\oplus K \cong H\times K$, the only difference between the products in this case is that the external sum builds bigger groups from smaller ones, while the internal sum breaks groups into smaller pieces.

Finite abelian groups are completely classified by the following theorem:

Fundamental Theorem of Finite Abelian Groups

Every finite abelian group is isomorphic to a unique direct product of cyclic groups whose orders are prime powers, that is $G\cong \mathbb{Z}_{p_1}^{n_1}\oplus \cdots\oplus \mathbb{Z}_{p_k}^{n_k}$.

This fundamental result usually caps one's first exposure to groups. As a corollary, such a group has subgroup of order m for each m dividing the group order.

# Rings

## The Basics

Having studied sets with one operation, it is time to move on to sets with two operations, called rings.

Definition

A ring is a set R with two operations + and * (usually suppressed) such that:

1. R is an abelian group under +;
2. R is associative under *;
3. R is distributive, meaning $a*(b+c)=a*b+a*c$.

The additive identity is denoted 0. If $ab=ba$, R is a commutative ring, and if there is a multiplicative identity 1, R is a ring with unity. A commutative ring with unity which is an abelian group under *, excluding 0, is called a field.

In a ring with unity, elements with multiplicative inverses are called units, so in a field every element but 0 is a unit. Inverses and identities, if they exist, are unique.

The characteristic of a ring R is the smallest integer n such that $na=0$ for all $a\in R$, or 0 if no such exists. If the ring has a unity, the characteristic is the order of the unity (or 0 if it has infinite order).

Subrings are subsets of rings that are themselves rings; equivalently they are closed under subtraction and multiplication. For example, $\mathbb{Q}$ is a subring of $\mathbb{R}$, and $2\mathbb{Z}$ is a subring of $\mathbb{Z}$.

### Examples

• The integers $\mathbb{Z}$ are a commutative ring with unity. The units are +1 and -1.
• The even integers $2\mathbb{Z}$ are a commutative ring without unity.
• The integers modulo n, $\mathbb{Z}_n$, are a commutative ring with unity. The units are $U(n)$.
• Integer $2\times2$ matrices are a noncommutative ring with unity $\binom{1\:0}{0\:1}$.

The example $\mathbb{Z}_n$ above has characteristic n, while the remaining examples have characteristic 0.

### Polynomial Rings

Given a ring R, the ring of polynomials in $\diamondsuit$ with coefficients in R is $R[\diamondsuit] = \{a_0+a_1\diamondsuit+\cdots+a_k\diamondsuit^k : a_0, a_1, \ldots, a_k \in R\}$. Elements of $R[\diamondsuit]$ are sometimes denoted as "functions" $f(\diamondsuit)$, but it is important to note that they are not actual functions; they could just as easily be described by the coefficients only: $[a_0,a_1,\ldots,a_k]$.

The ring of polynomials is itself a ring, and R is one of its subrings. In some cases, one assumes that $\diamondsuit^k \in R$ for some k, so the only polynomials of interest have small order. For instance, the Gaussian Integers are $\mathbb{Z}[i]$, where it is assumed that $i^2=-1$.

## Ideals and Factor Rings

With groups, we needed a normal subgroup to form a factor group; with rings, we need a:

Definition

A (2-sided) ideal is a subring A of R such that $ra,ar\in A$ for all $a\in A, r\in R$. This gives a well-defined factor ring $R/A$, consisting of the cosets of the ideal A, which are typically denoted $r+A$ for some $r\in R$.

A simple example is $\mathbb{Z}/4\mathbb{Z}$, consisting of the elements $\{0,1,2,3\}$ with addition and multiplication modulo 4.

Any single element $a\in R$ generates a principal ideal, defined as $\langle{a}\rangle=\{ar,ra:r\in R\}$. For example, the factor ring $\mathbb{R}[x]/\langle{x^2+1}\rangle$ is defined using a principal ideal. It can be thought of as polynomials with real coefficients and the relation $x^2=-1$, and is thus equivalent to the complex ring $\mathbb{C}$.

A prime ideal $A\subset R$ is one in which $ab\in A$ implies either $a\in A$ or $b\in B$. This is a similar notion to prime numbers; indeed, $\mathbb{Z}/n\mathbb{Z}$ is a prime ideal of $\mathbb{Z}$ if and only if n is prime. A maximal ideal is a proper ideal A such that if $A\subseteq B \subseteq R$ for another ideal B, then either $B=A$ or $B=R$. The ideal $\langle{x^2+1}\rangle$ in $\mathbb{R}[x]$ is an example of a maximal ideal. These ideals are important because $R/A$ is a field if and only if A is maximal, and $R/A$ is an integral domain (the topic of the next section) if and only if A is prime.

## Integral Domains

An integral domain is one of many types of rings with a specific structure, in this case meant to ensure behavior like the integers (hence the name).

Definition

An integral domain is a commutative ring with unity and no zero divisors (elements with $ab=0$). Equivalently, the cancellation laws $ab=ac \Rightarrow b=c$ and $ba=ca \Rightarrow b=c$ hold.

Integral domains have characteristic 0 or p prime.

Examples of integral domains include $\mathbb{Z}/3\mathbb{Z}[i]$ and $\mathbb{Q}[\sqrt{2}]$ (recall this notation from the previous section). The first is also a finite field, since all finite integral domains are fields. In general, the structure of finite fields is very well understood.

For every integral domain D, there is a field F with D as a subring, called the field of quotients. This is the analog of the rationals for integers. As can be expected, F is constructed by looking at all pairs (quotients) of elements of D and an appropriate equivalence relation.

The study of polynomials is central to ring theory. A ring of polynomials $D[x]$ over an integral domain D is itself an integral domain. Working in an integral domains allows us to say that if $(x-a)(x-b)=0$, then either $x=a$ or $x=b$; this is not always the case in a ring with zero divisors. If D is a field, then one has a division algorithm in $D[x]$, and polynomials are factored in the usual manner.

A principal ideal domain, or PID, is an integral domain in which every ideal is a principal ideal (generated by a single element). The polynomials $F[x]$ over a field form a PID. In fact, an ideal I of $F[x]$ is generated by the polynomials of minimal degree in I.

Other than the special elements 0 and 1, integral domains also lack nilpotent elements (those satisfying $a^n=0$ for some n) and idempotent elements (those satisfying $a^2=a$).

## Ring Morphisms

With rings, homomorphisms and isomorphisms are defined in a way similar to groups. The main difference is that ring homomorphisms preserve both group operations.

An example for polynomial rings is the evaluation homomorphism $\mathbb{R}[x]\to\mathbb{R}$ defined by $f(x)\mapsto f(1)$.

Analogous to the situation for groups, kernels of homomorphisms are ideals, and all ideals are kernels of some ring homomorphism. We also have:

First Isomorphism Theorem for Rings

Given a ring homomorphism $\phi:R\to S$, there is an isomorphism $R/\mathrm{ker}\:\phi\cong\phi(R)$ given by the map $r+\mathrm{ker}\phi\mapsto\phi(r)$.

Thus, for example, $\mathbb{Z}[x]/\langle{x}\rangle\cong\mathbb{Z}$. Since $\mathbb{Z}$ is an integral domain but not a field, this means that $\langle{x}\rangle$ is a prime ideal, but not maximal.

Another important homomorphism is the map $\phi:\mathbb{Z}\to R$ taking $n\mapsto 1+\cdots+1$, where the unity $1\in R$ is added to itself n times. Since this is a ring homomorphism, every ring with unity has a subring isomorphic to either $\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$, and the choice between these is determined by the characteristic of the ring. Analogously, a field always has a subfield isomorphic to either $\mathbb{Q}$ or $\mathbb{Z}/n\mathbb{Z}$, again depending on the characteristic. This subfield, called the prime subfield, is actually the intersection of all nontrivial subfields.

## More on Polynomial Rings

Polynomials are widely studied in ring theory because they are the simplest generalization of the integers, with many properties carrying over.

Definition

Given an integral domain D, an irreducible polynomial $f(x)\in D[x]$ is one for which $f(x)=g(x)h(x)$ implies either g or h is a unit. Otherwise, the polynomial is reducible.

A primitive polynomial $f(x)\in\mathbb{Z}[x]$ is one with no common factor among its coefficients. The product of two primitive polynomials is also primitive (the Gauss Lemma). This property is frequently used to simplify proofs.

In a field F, a polynomial of degree 2 or 3 is reducible if and only if it has a zero in F. If a polynomial in $\mathbb{Z}[x]$ is reducible over $\mathbb{Q}$, then it is also reducible over $\mathbb{Z}$. Equivalently, if it is irreducible over $\mathbb{Z}$, then it is irreducible over $\mathbb{Q}$. Hinting at some properties we'll see later, every polynomial of degree greater than 1 is reducible over some (extension) field. Actually, every polynomial $\mathbb{Z}[x]$ can be uniquely factored into a product of nonunits of degree 0 and irreducible polynomials, similar to the unique factorization of integers.

Here are a few tests for irreducibility over $\mathbb{Z}[x]$. First, given a prime p, a polynomial $f(x)\in\mathbb{Z}[x]$ gives a unique polynomial $\bar f(x)\in\mathbb{Z}/p\mathbb{Z}[x]$, found by reducing the coefficients modulo p. If this polynomial has the same degree and is irreducible over $\mathbb{Z}/p\mathbb{Z}$, then $f(x)$ is irreducible over $\mathbb{Z}$. Second, the Eisenstein criterion states that if $f(x)=a_nx^n+\cdots+a_0\in\mathbb{Z}[x]$ and some prime p divides $a_0,\ldots,a_{n-1}$ but $p\not{|}a_n$ and $p^2\not{|}a_0$, then f is irreducible over $\mathbb{Q}$. For example, when p is prime the cyclotomic polynomial $\Phi_p(x)=x^{p-1}+\cdots+x+1$ is irreducible over $\mathbb{Q}$.

In a field, $p(x)$ is irreducible if and only if $\langle{p(x)}\rangle$ is a maximal ideal. In this case, $F[x]/\langle{p(x)}\rangle$ is also a field. This provides a general technique for cosntructing fields. A simple consequence of this result is that for irreducible $p(x)|a(x)b(x)$, one must have either $p(x)|a(x)$ or $p(x)|b(x)$.

## General Integral Domains

Many properties of integers and polynomials carry over to general integral domains. In place of prime numbers/irreducible polynomials, an irreducible element $a\in D$ is one for which $a=bc$ implies either b or c is a unit; a prime element $a\in D$ is one for which $a|bc$ implies either $a|b$ or $a|c$ (which happens if and only if $\langle{a}\rangle$ is a prime ideal). All prime elements are irreducible, but the converse is not true. In $\mathbb{Z}[\sqrt{-3}]$, the element $1+\sqrt{-3}$ is irreducible but not prime. However, in a PID, elements are irreducible if and only if they are prime.

We now introduce a few more classes of integral domains. Unique factorization holds in all PIDs; a general integral domain with this property is called a Unique Factorization Domain, or UFD. Thus, for example, unique factorization holds in $F[x]$ for F a field (and if D is a UFD, then $D[x]$ is also a UFD). The proof that every PID is a UFD uses the fact that a strictly increasing chain of ideals $I_1\subset I_2\subset\cdots$ in a PID must be finite (this property in general is what characterizes a Noetherian Domain).

Another class of PID is the Euclidean domain, basically an integral domain with a division algorithm. Precisely, in a Euclidean domain D, there is a function $d:D^*\to\mathbb{Z}_0^+$ from the nonzero elements to the nonnegative integers such that whenever $d(a)\leq d(ab)$ and $b\neq 0$ there are elements $q,r\in D$ such that $a=bq+r$ and $d(r)<d(b)$. The obvious prototype is $\mathbb{Z}$, with $d(a)=|a|$. A less obvious example is $F[x]$ with $d(f(x))=\deg{f(x)}$.

One may summarize the inclusions described above by the diagram

(2)
\begin{align} \text{field} \:\Rightarrow\: \text{Euclidean domain} \:\Rightarrow\: \text{PID} \:\Rightarrow\: \text{UFD} \:\Rightarrow\: \text{integral domain} \:\Rightarrow\: \text{commutative ring with unity}. \end{align}

# Fields

Definition

A field is a set F with two operations + and * such that both $(F,+)$ and $(F,*)$ (sometimes denoted $F^*$) are abelian groups and the distributive property is satisfied.

Important areas of study in field theory include vector spaces, which are most generally defined over arbitrary fields, the study of finite fields, which are relatively easy to classify, and Galois theory, which was originally used to study the roots of polynomial equations.

## Vector Spaces

Vector spaces may be defined over arbitrary fields.

Definition

A vector space V (over a field F) is a space with a map $F\times V\to V$ such that for $a,b\in F$ and $u,v\in V$ one has $a(u+v)=au+av$, $(a+b)v=av+bv$, $a(bv)=(ab)v$, and $1v=v$.

Elements of F are the scalars, and elements of V are the vectors. A few examples include $\mathbb{R}^n$, the matrix group $M_2(\mathbb{Q})$, and $\mathbb{Z}/p\mathbb{Z}[x]$ for p prime (its basis is $\{1,x,\ldots,x^{p-1}\}$). Notions such as subspace, linear dependence/independence, basis, dimension, linear combination, and span carry over from linear algebra. It is true in general that all bases for a vector space have the same number of elements, although that number might be infinite.

## Extension Fields

Definition

An extension field E of F a field including E as a subfield. The relationship is denoted E > F. Given a polynomial $f(x)\in F[x]$, a splitting field for f is an extension field E > F that contains all the zeros of f.

The condition defining a splitting field ensures that f may be factored into a product of linear factors, hence it "splits". An important example is the extension $\mathbb{Q}[i] > \mathbb{Q}$, which is a splitting field for $f(x)=x^2+1$. In the more general context of $\mathbb{R}[x]$, the same polynomial splits over $\mathbb{C} > \mathbb{R}$.

Fundamental Theorem of Field Theory

Given a field F and a polynomial $f(x)\in F[x]$, there exists an extension field E > F in which f has a zero.

Using this theorem, it makes sense to define $F(a_1,\ldots,a_n)$ to be the smallest extension of F containing all ai. Note that the parentheses here distinguish the result as a field rather than a ring of polynomials. This extension is precisely the splitting field for the polynomial $f(x)=\prod (x-a_i)$. Some properties of splitting fields follow:

• Every polynomial has a splitting field.
• Splitting fields are unique up to isomorphism.
• Given an irreducible polynomial $p(x)\in F[x]$, with a zero a in an extension field of F, then $F(a)\cong F[x]/\langle{p(x)}\rangle$, and the elements of $F(a)$ can be expressed uniquely as polynomials of degree less than $\deg{p(x)}$.
• In the previous case, if a and b are both zeros of f, then $F(a)\cong F(b)$.

## Algebraic Extensions

Definition

Given a field extension E > F, an element $a\in E$ is algebraic over F if it is a zero of a polynomial in $F[x]$. Otherwise it is transcendental.

Standard examples are $\sqrt{2}$, an algebraic element over $\mathbb{Q}$, and$\pi$, which is transcendental. If every element of an extension field E is algebraic, E is an algebraic extension.

An extension $F(a)$ generated by a single element is a simple extension. Actually, all finite extensions over a
field of characteristic 0 are simple. An element a of an extension E > F that generates E, meaning $E\cong F(a)$, is called a primitive element.

If a is transcendental, then $F(a)\cong F(x)$, the field of quotients. Otherwise, a is algebraic and $F(a)\cong F[x]/\langle{p(x)}\rangle$, where $p(x)$ is irreducible over F and $p(a)=0$. In fact, the polynomial p is unique if taken to be monic, and it divides any other polynomial $f(x)$ with $f(a)=0$.

Every extension E > F has a subfield consisting of all algebraic elements over F, called the algebraic closure of F in E. An algebraically closed field is one with no proper algebraic extensions, such as $\mathbb{C}$, so that every polynomial has its zeros in the field.

The degree of an extension E > F is the dimension of E considered as a vector space over F, or $\infty$ if the extension is transcendental. It is denoted $[E:F]$. For example, the degree of $F(a)\supset F$ is the degree of the minimal polynomial. For $K\supset E\supset F$, the degrees satisfy $[K:F]=[K:E][E:F]$.

## Finite Fields

Finite fields are as easy to classify as finite abelian groups. For each prime p and integer n, there is a unique field $GF(p^n)$ of order pn, called the Galois field, and these are the only finite fields. As an additive group, $GF(p^n)\cong \mathbb{Z}/p\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/p\mathbb{Z}$, and as a multiplicative group, $GF(p^n)^*$ is cyclic and isomorphic to $\mathbb{Z}/(p^n-1)\mathbb{Z}$. The degree of $GF(p^n)$ over $GF(p)$ is n, and a generator of $GF(p^n)^*$ is algebraic over $GF(p)$ with degree n. The field $GF(p^n)$ has a unique subfield of order pm for every m|n, and these are the only subfields. An example is $GF(16)$, which may be constructed as $\{a_3x^3+a_2x^2+a_1x+a_0+\langle{x^4+x+1}\rangle: a_i\in\mathbb{Z}_2\}$, with generator x.

## Galois Theory

Galois theory concerns the relationship between extensions of fields and groups. It was originally used to prove the insolvability of the quintic, i.e., the nonexistence of an algebraic formula giving the roots of a fifth-order polynomial.

Definition

Given a field extension E > F, the Galois group $\mathsf{Gal}(E/F)$ is the group of automorphisms of E that fix every element of F.

We also define the fixed field $E_H$ of a group $H<\mathsf{Gal}(E/F)$ as the set of elements $x\in E$ fixed by every automorphism in H.

There is a remarkable relationship between the subgroups of $\mathsf{Gal}(E/F)$ and intermediate extension fields K with E > K > F.

Fundamental Theorem of Galois Theory

Given a field extension E > F, there is a map $K\mapsto\mathsf{Gal}(E/K)$ taking intermediate extension fields K with E > K > F to subgroups of $\mathsf{Gal}(E/F)$. If E is a splitting field for a polynomial over F, then the map is a one-to-one correspondence.

Some additions to this result follow:
• The index $[E:K]$ of E over K as a vector field equals $|\mathsf{Gal}(E/K)|$ and $[K:F]=|\mathsf{Gal}(E/F)|/|\mathsf{Gal}(E/K)|$.
• If K is the splitting field of a polynomial in $F[x]$ and $\mathsf{Gal}(E/K) \lhd \mathsf{Gal}(E/F)$, then $\mathsf{Gal}(K/F)\cong\mathsf{Gal}(E/F)/\mathsf{Gal}(E/K)$.
• The fixed field of $\mathsf{Gal}(E/K)$ is $E_{\mathsf{Gal}(E/K)}=K$, and for $H<\mathsf{Gal}(E/F)$ we have $H=\mathsf{Gal}(E/E_H)$.

The simplest Galois extensions, those satisfying the requirements in the above theorem, are those adjoining a root of a polynomial. The extension $\mathbb{Q}(\sqrt{2}) > \mathbb{Q}$ can be viewed as $\{a+b\sqrt{2}:a,b\in\mathbb{Q}\}$, and the Galois group $\mathsf{Gal}(\mathbb{Q}(\sqrt{2})/\mathbb{Q})$ is $\mathbb{Z}/2\mathbb{Z}$, with the nonidentity automorphism taking $\sqrt{2}\mapsto -\sqrt{2}$. The fixed field of $\mathsf{Gal}(\mathbb{Q}(\sqrt{2})/\mathbb{Q})$ is $\mathbb{Q}$, as must be the case since any automorphism must fix $\mathbb{Q}$. A second example is the extension $\mathbb{Q}(\omega,\sqrt[3]{2})$ with $\omega=-\frac{1}{2}+i\frac{\sqrt{3}}{2}$ a root of $x^3-1$. The Galois group in this case is actually S3 and thus non-abelian.

A more general example is the extension $GF(p^n) > GF(p) = F$. This can actually be viewed as $F(b)$, where b is the zero of some irreducible degree n polynomial $p(x)\in F[x]$. Any automorphism of $GF(p^n)$ fixes 1 and therefore $GF(p)$ as well. So if $p(b)=0$ then $p(\phi(b))=0$. Thus, there are at most n possibilities for $\phi(b)$. On the other hand, the map $a\mapsto a^p$ is an automorphism of E with order n, since $GF(p^n)^*$ is cyclic. Therefore, $\mathsf{Gal}(GF(p^n)/GF(p))\cong\mathbb{Z}_n$.

# Going Further

## Sylow Theory

Classifying finite abelian groups is relatively easy. It is much more difficult to write down all the nonabelian groups of a certain order. The answer is best achieved with the Sylow theorems, a collection of tools for determining properties of groups of a certain order. We begin by developing some of the theory used in the proofs of the Sylow theorems.

Two subgroups H and K of a group G are conjugate if $H=gKg^{-1}$ for some $g\in G$. For a single element $a\in G$, the conjugacy class $\mathrm{Cl}(a)$ is the set of elements of the form $xax^{-1}$ for $x\in G$. These sets partition the group, but not like cosets since $\mathrm{Cl}(e)=\{e\}$. It is easy to show that $|\mathrm{Cl}(a)|=|G:C(a)|$, where $C(a)$ is the centralizer subgroup. This is used to derive the class equation.

Theorem (Class Equation)

The order of a group G may be written $|G|=\sum |G:C(a)|$, where the sum is taken over conjugacy classes. Alternately, $|G|=|Z(G)|+\sum |G:C(a)|$, where the sum is taken over the nontrivial conjugacy classes. (All elements in $Z(G)$ are in their own conjugacy class.)

This formula reveals a lot about the orders of subgroups. First, if $|G|=p^n$, we can divide the class equation by p to see that $Z(G)$ must be nontrivial. Applying the $G/Z$ Theorem, one finds that all groups of order p2 are abelian. Further consequences follow.

• Sylow's First Theorem: If pk divides |G|, then G has a subgroup of order pk, called a Sylow p-subgroup.
• Sylow's Second Theorem: Every subgroup H < G of order pk is contained in some Sylow p-subgroup.
• Sylow's Third Theorem: The number of Sylow p-subgroups, denoted np, is equal to 1 modulo p and divides |G|. Any two such subgroups are conjugate.

The first theorem is proven inductively using the class equation. The second and third proofs are harder, using the notion of conjugate subgroups and the Orbit-Stabilizer Theorem.

The second theorem implies that a group G has an element of order p for every p dividing |G|. The third theorem implies that a Sylow p-subgroup is unique, meaning $n_p=1$, if and only if it is a normal subgroup.

The above results are extremely useful in classifying the groups of a certain order. As an example, Sylow's Third Theorem implies that a group of order 40 has only one Sylow 5-subgroup; hence that group is normal. A group of order 30 must have either 1 or 6 Sylow 5-subgroups, and 1 or 10 Sylow 3-subgroups. There are not enough elements for both of these subgroups to be non-unique, so one of them must be normal. Therefore, there exists a cyclic, normal subgroup of order 15.

A more general case is $|G|=2p$, for p an odd prime. In this case G is isomorphic to either $\mathbb{Z}/(2p)\mathbb{Z}$ or the dihedral group Dp. In fact, there are at most 2 groups of order pq for any primes p and q. It is also true that for $|G|=pq$, with p < q not dividing $q-1$, then $G\cong\mathbb{Z}/(pq)\mathbb{Z}$.

## Finite Simple Groups

This section continues the theme of understanding and classifying finite groups by looking at the particular case of finite simple groups.

Definition

A simple group is one with no nontrivial normal subgroups. Hence, it has no factor groups.

One can think of simple groups as the building blocks of larger groups. Factoring out the largest normal subgroup G1 of a group G0 gives a simple group $H_1=G_0/G_1$. This process may be continued, and the groups $H_i=G_{i-1}/G_i$ are called the composition factors. Using this decomposition and induction, many problems in group theory can be reduced to the special case of simple groups.

Finite simple groups have been completely classified, divided into seven infinite families and an additional 26 sporadic groups fitting no specific criterion. There are a variety of tests for nonsimplicity. Two of these follow:

• 2*Odd Test: If n = 2m for m odd, then there is no simple group of order n.
• Sylow Test: If p|n and 1 is the only divisor of n that is equivalent to 1 modulo p, then there is no simple group of order n.

The first test is proven using Cayley's Theorem. The second is proven using Sylow's Third Theorem and the fact that prime power groups have nontrivial centers.

Cayley's Theorem on permutations can be generalized to the following: if H < G and S is the group of permutations of left cosets of H in G, then there is a homomorphism $G\to S$ whose kernel is in H and that contains every normal subgroup of G that is also in H. This result gives two more tests:

• Index Test: If G is a finite group and H < G with |G| not dividing $|G:H|!$, then H contains a nontrivial normal subgroup and is not simple.
• Embedding Test: If a finite non-abelian group G with a subgroup of index n is not isomorphic to a subgroup of An, then it is not simple.

A simple application of these four tests shows that the only possible orders less than 200 for a non-abelian simple group are 60, 72, 112, 120, 144, 168, and 180. Of these, only 60 are 168 actually correspond to simple groups. The others may be eliminated with some additional work. In the case of 72, Sylow's Third Theorem implies that there are either 1 or 4 Sylow 3-subgroups. The first case would imply a normal subgroup, so $n_3=4=|G:N(H)|$. But then G cannot be simple by the Index Test, since |G| does not divide 4!. The order 60 simple group is A5, which may be proven to be simple by eliminating also possible orders for subgroups.

Further study of abstract algebra involves several additional algebraic structures, beyond groups, rings, and fields. The most useful is probably the module, which is a generalization of a vector space, this time over a ring. It also generalizes the notion of a group acting on a set (like a permutation group). All groups are modules, and many theorems for groups (like the classification of finite abelian ones) carry over to modules. Another structure is the algebra, which one can think of as a ring with a little less structure. Other combinations of axioms may lead to other kinds of structures.

Representation theory analyzes a group using its homomorphisms, and particularly by its homomorphisms into particular matrix groups. In this case, the properties of the traces of the map's image provide a great deal of information about the group itself. Lie groups and Lie algebras are another key idea that are often tied directly to representation theory. A Lie group is a group with a differential structure, or equivalently a manifold with a group structure. A Lie algebra is an algebra with an anti-commutative product $[X,Y]=-[Y,X]$ that satisfies a particular identity. Lie algebras can be completely classified, and, amazingly, there is a close correspondence between Lie groups and Lie algebras; with a few minor conditions on the Lie group, there is in fact a 1:1 correspondence. Lie theory lies at the intersection of geometry, topology, and algebra, which makes it useful to a huge range of mathematicians.

Finally, category theory attempts to encapsulate the commonalities between various structures. Often, theorems can be phrased in terms of category theory so as to generalize theorems that exist separately in different contexts. The basic objects in category theory are objects and morphisms, which are special functions between the objects. Examples here include groups and homomorphisms between groups, or rings and ring homomorphisms between rings. There are lots of additional examples; category theory is general enough to encompass many diverse mathematical structures.

# References

The following are two recommended texts frequently used for undergraduate courses in abstract algebra.

1. John B. Fraleigh, "A First Course in Abstract Algebra", Addison Wesley, 2002.
2. Joseph A. Gallian, "Contemporary Abstract Algebra", Brooks Cole, 2004.
page revision: 43, last edited: 19 Sep 2009 21:32


text:
# Mathematics Challenge

For a chance to win the first prize (£100 Amazon voucher), or one of our prizes for runners-up, submit your typed or neatly written solutions of the following problems to maths@lincoln.ac.uk or by post to Mathematics Challenge, School of Mathematics and Physics, University of Lincoln, Lincoln, LN6 7TS. Please include your full name, postal address and email, as well as the name and address of your school. The closing date is 5 January, 2017. The competition is open to all young pre-university people in UK aged 16–18 years. It is not open to current university students. See full Terms and Conditions. The problems can also be downloaded from here.

1. Suppose that alloy A contains 40% gold by weight, and alloy B contains 25% gold. How much of each of these alloys should be taken to be melted together so as to produce 600 grams of alloy containing 30% gold?

2. In a rectangle $ABCD$, the perpendicular $BE$ dropped from the vertex $B$ onto the diagonal $AC$ divides $AC$ in the ratio $1:3=AE:EC$. Find the length of $BC$ given the length $AB=1\,{\rm cm}$.

3. Solve the inequality  $\displaystyle \frac{1}{3^x+1} \ + \ \frac{1}{3^x-3} \ \leq \ 0$.

4. Given an arbitrary convex quadrangle $ABCD$, each side of it is divided by two points in the ratio $1:\sqrt{2}:1$. Then a new quadrangle $PQRS$ is formed by constructing straight lines through pairs of these points as shown in the picture. Prove that the areas of the quadrangles $ABCD$ and $PQRS$ are equal.5. Prove that, given any 11 integers, one can choose some of them and put signs $+$ or $-$ between these chosen integers in such a way that the resulting sum is divisible by 2016.

(Recall that an integer $m$ is divisible by an integer $n$ if there is an integer $k$ such that $m=kn$; in particular, $0$ is also divisible by $n$.)

6. Given $2016$ non-zero real numbers, one can perform the following operation: replace any two of these numbers $a$ and $b$ by the numbers $(a-b)/2$ and $(a+b)/2$. Prove that one cannot return to the initial set of numbers after several such steps.

Notes: Full solutions are required – not just answers – with complete proofs of any assertions you may make. A winning submission may not necessarily be based on all six problems – so you are encouraged to submit solutions even if you do only some of the problems.

1. Reblogged this on Algebra in Lincoln.

Like


text:
# hard

1. ### Hard PDE

Solve \frac{\partial Z }{\partial x} =2x\cdot (1-\frac{\partial Z}{\partial y})\; , for Z(x,0)=Z(0,y)=1 .
2. ### Hard inequality

Given a,b,c>=1 and a+b+c=9. Prove that (âˆša+âˆšb+âˆšc)^2>=ab+bc+ca.

4. ### Hard Limit

Evaluate the limit without L'hÃ´pitalâ€™s rule. \lim_{y\rightarrow \infty }\frac{\ln(yn)}{y^n } \; , n\in \mathbb{N}.
5. ### Hard problem

Evaluate L(s)=\lim_{n\rightarrow \infty } s^{n} \: , s\in \mathbb{R}^{+} .
6. ### Hard limit

Evaluate \lim_{x\rightarrow \infty } e^{-x} \cdot x^{n} \; ; n-positive integer .
7. ### Tennis court surfaces.

https://en.m.wikipedia.org/wiki/Tennis Tennis is played using the following ground surface viz Grass, Hard & Clay surfaces. Which could be considered among the three as the most difficult and most easy court surface to play? Thanks & Regards, Prashant S Akerkar
8. ### A simple Proof by the Easy Or Hard Way?

Given the equations below prove that v^2 = v_0^2 + 2a(x-x_0) 1) v = v_0 + at 2) x-x_0 = v_ot + \frac{1}{2}at^2 Easy Solution: v = v_0 + at \Leftrightarrow t = \frac{v-v_0}{a} Substituting t into equation 2 \Delta{x} = v_0\frac{v-v_0}{a} +...
9. ### Hard Inverse function f(x) problem

So I have this problem f(x)=x^3+x+1 and I need to find the inverse of this function.I know that you have to use differentiation but the problem is I see this solution (f^-1)(3)=1 but I don't understand the steps to reach that conclusion.There was another one (f^-1)(3)=5 and this looked the same...

12. ### Need help in hard exercise

Settle, whether there exist in pairs different rational numbers, such that polynomials have a common irrational element.
13. ### Riemann's Sum Problem

Brief Overview What I've done so far: The Question If the safety capacity for the benign use of a camping gas lamp inside a confined space is (104Ã·5) m^3, calculate whether it would be safe to use the lamp within the lightweight â€˜pop-upâ€™ tent. I know the height of my tent is...
14. ### How to solve this problem? (HARD)

A giant rabbit is tied to a pole in the ground by an infinitely stretchy elastic cord attached to its tail. A hungry flea is on the pole watching the rabbit. The rabbit sees the flea, jumps into the air and lands one kilometre from the pole (with its tail still attached to the...
15. ### Light Hard Drives Question

http://fav.me/dbw3yek how far do I have to place the holograms for optimal capacity?
16. ### Help for the hard prove question

If n is a positive integer and n is even, prove: (2^(n!)-1) is divisible by (n^2-1). This question confuse me some days. Please help me or give me some hint. Thank you very much.
Made errors in earlier posts. This is my question. I have been trying to solve this since summer. It is a question from the book: 7th edition Adams calculus. 2.1.3 Using Newton quotient to solve the problem (not any chain rule, power rule or l'HÃ´pital's rule is allowed). If the function $f$...


text:
# Archimedean Review

In the last couple of posts[1][2] we've been taking a look at Archimedean copulas which define the dependency between the elements of vector values of a multivariate random variable by applying a generator function $$\phi$$ to the values of the cumulative distribution functions, or CDFs, of their distributions when considered independently, known as their marginal distributions, and applying the inverse of the generator to the sum of the results to yield the value of the multivariate CDF.
We have seen that the densities of Archimedean copulas are rather trickier to calculate and that making random observations of them is trickier still. Last time we found an algorithm for the latter, albeit with an implementation that had troubling performance and numerical stability issues, and in this post we shall add an improved version to the ak library that addresses those issues.

### A Brief Review

Recall that for a continuous function $$\phi$$, the conditions
$\phi : [0,1] \mapsto [0,\infty]\\ \phi(1) = 0\\ x > y \rightarrow \phi(x) < \phi(y)\\ (-1)^k \frac{\mathrm{d}^k}{\mathrm{d}t^k} \phi^{-1}(t) \geqslant 0$
where $$\mapsto$$ means maps to, $$\rightarrow$$ means implies and $$\frac{\mathrm{d}^k}{\mathrm{d}t^k}\phi^{-1}(t)$$ is the $$k^\mathrm{th}$$ derivative of the inverse of $$\phi$$ evaluated at $$t$$, for $$k$$ less than or equal to $$n$$, are sufficient to ensure that the function
$C\left(\mathbf{u}\right) = \phi^{-1}\left(\min\left(\sum_{i=0}^{n-1} \phi(u_i), \phi(0)\right)\right)$
where $$\sum$$ is the summation sign, is an $$n$$ dimensional Archimedean copula which, like any copula, is the CDF of a multivariate distribution with standard uniform marginals.
To make observations of the random variable $$\mathbf{u}$$ governed by that distribution we first defined a vector $$\mathbf{v}$$ with the elements
$v_i = \phi\left(u_i\right)$
so that
$C\left(\mathbf{u}\right) = \phi^{-1}\left(\min\left(\sum_{i=0}^{n-1} v_i, \phi(0)\right)\right)$
We then defined another one $$\mathbf{v}^\prime$$ with the elements
$v^\prime_i = \begin{cases} \sum_{j=0}^{n-1} v_j & i = 0\\ v_i & \mathrm{otherwise} \end{cases}$
to yield
$C\left(\mathbf{u}\right) = \phi^{-1}\left(\min\left(v^\prime_0, \phi(0)\right)\right)$
From this we were able to work out that the probability density function, or PDF, and CDF of $$v^\prime_0$$ were
$f^\ast\left(v^\prime_0\right) = \begin{cases} (-1)^n \times \frac{{v^\prime_0}^{n-1}}{(n-1)!} \times \frac{\mathrm{d}^n}{\mathrm{d}t^n}\phi^{-1}\left(v^\prime_0\right) & v^\prime_0 < \phi(0)\\ 0 & \mathrm{otherwise} \end{cases}$
where the exclamation mark represents the factorial of the term preceding it, and
$F^\ast\left(v^\prime_0\right) = \begin{cases} 0 & v^\prime_0 \leqslant 0\\ \sum_{i=1}^n \frac{(-1)^{n+i-1}}{(n-i)!} \times \left[t^{n-i} \frac{\mathrm{d}^{n-i}}{\mathrm{d}t^{n-i}}\phi^{-1}(t)\right]_0^{{v^\prime_0}} & 0 < v^\prime_0 < \phi(0)\\ 1 & \phi(0) \leqslant v^\prime_0 \end{cases}$
respectively. We numerically inverted the latter using Newton's method[3] so that we could make a random observation of $$v^\prime_0$$ with
\begin{align*} u &\sim U(0,1)\\ v^\prime_0 &= {F^\ast}^{-1}(u) \end{align*}
where $$\sim$$ means drawn from and $$U(0,1)$$ is the standard uniform distribution.
Next, we noted that $$v_1$$ to $$v_{n-1}$$ must be uniformly distributed over the $$n-1$$ dimensional analogue of a triangle, known as a simplex, with vertices at the origin and at $$v^\prime_0$$ on each of their axes and that we could consequently divide up the observed value of $$v^\prime_0$$ by generating $$n-1$$ uniform random values between zero and it, labelling them in increasing order as $$x_i$$, counting from $$i$$ equal to zero, and defining
\begin{align*} v_i &= \begin{cases} x_i - x_{i-1} & 1 \leqslant i < n-1\\ v^\prime_0 - x_{i-1} & i = n-1 \end{cases}\\ v_0 &= v^\prime_0 - \sum_{i=1}^{n-1} v_i \end{align*}
which is, in fact, equivalent to
$v_i = \begin{cases} x_i & i = 0\\ x_i - x_{i-1} & 1 \leqslant i < n-1\\ v^\prime_0 - x_{i-1} & i = n-1 \end{cases}\\$
The final step was to transform this observation of $$\mathbf{v}$$ into an observation of $$\mathbf{u}$$ with
$u_i = \phi^{-1}\left(v_i\right)$

### A Robust Implementation

Recall that we rearranged the formulae for $$f^\ast$$ and $$F^\ast$$ into
\begin{align*} f^\ast\left(v^\prime_0\right) &= \begin{cases} 0 & v^\prime_0 \leqslant 0\\ (-1)^n \times {v^\prime_0}^{n-1} \times n \times \frac{1}{n!} \times \frac{\mathrm{d}^n}{\mathrm{d}t^n}\phi^{-1}\left(v^\prime_0\right) & 0 < v^\prime_0 < \phi(0)\\ 0 & \phi(0) \leqslant v^\prime_0 \end{cases}\\ F^\ast\left(v^\prime_0\right) &= \begin{cases} 0 & v^\prime_0 \leqslant 0\\ \left(\sum_{i=1}^n (-1)^{n+i-1} \times {v^\prime_0}^{n-i} \times \frac{1}{(n-i)!} \times \frac{\mathrm{d}^{n-i}}{\mathrm{d}t^{n-i}}\phi^{-1}\left(v^\prime_0\right)\right) - 1 & 0 < v^\prime_0 < \phi(0)\\ 1 & \phi(0) \leqslant v^\prime_0 \end{cases} \end{align*}
allowing us to use our ak.surreal[4] type to calculate the
$\frac{1}{n!} \times \frac{\mathrm{d}^n}{\mathrm{d}t^n}\phi^{-1}\left(v^\prime_0\right)$
terms in a single shot with its coeffs method. The coeffs function given in listing 1 returns those values if the result of the dnq function that calculates the $$n^\mathrm{th}$$ derivative of $$\phi^{-1}$$ returns an ak.surreal and otherwise fills an array with the derivatives that it returns divided by the factorials of their orders to the same effect.

Listing 1: Calculating The Coefficients
function coeffs(v, n, dnq) {
var dq = dnq(v, n);
var a, f, i;

if(ak.type(dq)===ak.SURREAL_T) return dq.coeffs();
a = new Array(n+1);
f = 1;
i = 0;
while(i<n) {
a[i] = dnq(v, i)/f;
f *= ++i;
}
a[n] = dq/f;
return a;
}

These are used in the dist function, given in listing 2, to calculate the results of $$F^\ast$$ and $$f^\ast$$ that it returns in the first and second elements of an array respectively.

Listing 2: Calculating The CDF And PDF Of The Sum
function dist(v, n, p0, dnq) {
var c, df, f, i;

if(v<=0)  return [0,0];
if(v>=p0) return [1,0];

c = coeffs(v, n, dnq);
df = Math.pow(-1, n) * Math.pow(v, n-1) * n * c[n];

f = 1 - c[0];
for(i=1;i<n;++i) f += Math.pow(-1, n+i-1) * Math.pow(v, n-i) * c[n-i];
return [Math.max(Math.min(f,1),0), Math.max(df,0)];
}

A significant weakness in the last post's implementation of Archimedean copula random variables was the direct use of Newton's method which can lead to numerical instability. This time we shall use our ak.newtonInverse function instead which creates a function that safeguards the search by switching to the bisection method whenever Newton's method misbehaves.
This will still be a relatively expensive calculation, however, and so instead of using it to search for $${F^\ast}^{-1}(u)$$ directly we shall use it to find the values at a set of interpolation nodes which we shall use to create a linear interpolation with our ak.linearInterpolate function[5] to efficiently approximate the inverse.
This approximation will be most accurate if the nodes $$u_i$$ are equally spaced in probability so that for $$m$$ nodes
$u_i = \frac{i}{m}$
which also means that the interpolation will be as efficient as possible since we will be able to locate the node immediately before a probability $$u$$ with
$i = \lfloor m \times u \rfloor$
where the oddly shaped brackets represent the largest integer less than or equal to the value between them.
In order to find the inverse quickly we need to pass the inverter an as small as possible interval $$[v_l,v_u]$$ that contains it. A reasonable first guess at bounds for the inverse of $$u_{i+1}$$ are simply
\begin{align*} v_l &= v_i\\ v_u &= v_i + 2\times\left(v_i-v_{i-1}\right) \end{align*}
since $$v_{i+1}$$ cannot be smaller than $$v_i$$ if the distribution is valid and, if the probability isn't changing too quickly, won't be very much greater than it, relatively speaking.
If this first guess at the upper bound is beneath $$v_{i+1}$$ then we can make a second guess with
\begin{align*} v^\prime_l &= v_u\\ v^\prime_u &= v_u + 2\times\left(v_u-v_l\right) \end{align*}
then replace $$v_l$$ and $$v_u$$ with $$v^\prime_l$$ and $$v^\prime_u$$ respectively, repeating the process until we have bounds that satisfy
$F^\ast\left(v_l\right) \leqslant u_{i+1} \leqslant F^\ast\left(v_u\right)$
The interpolate function given in listing 3 receives $$\phi$$ as p and $$\phi^{-1}$$ as q and uses this scheme to update the bounds at each step from those of $$v_1$$ which it searches for by repeatedly halving an initial guess of
\begin{align*} v_l &= \tfrac12\phi\left(\tfrac12\right)\\ v_u &= \phi\left(\tfrac12\right) \end{align*}
until $$F^\ast\left(v_l\right)$$ falls beneath it.

Listing 3: Approximating The Inverse
function interpolate(n, p, q, dnq, m, threshold) {
var p0 = p(0);
var nodes = isFinite(p0) ? new Array(m+1) : new Array(m);
var du = 1/m;
var fdf = function(v){return dist(v, n, p0, dnq);};
var inv = ak.newtonInverse(fdf, threshold);
var vu = Math.max(p(0.5), ak.EPSILON);
var vl = vu*0.5;
var i, u, v, interp, extrap;

if(p0<=0 || isNaN(p0) || !isFinite(vu)) {
throw new Error('invalid generator result in ak.archimedeanCopulaRnd');
}
while(vl>0 && fdf(vl)[0]>du) {vu = vl; vl *= 0.5;}

nodes[0] = {x:0,y:0};
for(i=1;i<m;++i) {
u = i*du;
while(isFinite(vu) && fdf(vu)[0]<u) {v = vu; vu += 2*(vu-vl); vl = v;}
if(!isFinite(vu)) {
throw new Error('invalid CDF of sum in ak.archimedeanCopulaRnd');
}
v = inv(u, [vl, vu]);
if(!(v>nodes[i-1].y)) {
throw new Error('invalid CDF of sum in ak.archimedeanCopulaRnd');
}
nodes[i] = {x:u, y:v};
vu = v + 2*(v-nodes[i-1].y);
vl = v;
}
if(!(p0>nodes[m-1].y)) {
throw new Error('invalid CDF of sum in ak.archimedeanCopulaRnd');
}

if(isFinite(p0)) {
nodes[m] = {x:1, y:p0};
return ak.linearInterpolate(nodes);
}

interp = ak.linearInterpolate(nodes);
extrap = extrapolate(nodes[m-2], nodes[m-1]);
return function(x) {return x<=u ? interp(x) : extrap(x);};
}

Note that if $$\phi(0)$$ is finite then we simply need to add a final node and value of $$\left(1, \phi(0)\right)$$ and we're done.
If it isn't, however, this won't work since linear interpolation can't cope with infinite values. Instead we shall, somewhat arbitrarily I must admit, assume that the CDF takes the form
$F(v) = 1 - e^{a \times v + b}$
beyond $$v_{m-1}$$ so that we can extrapolate the inverse with
$v = \frac{\ln(1-u)-b}{a}$
for
\begin{align*} a &= \frac{u_0 - u_1}{\left(1-u_1\right) \times \left(v_1-v_0\right)}\\ b &= \ln\left(1-u_1\right) - a \times v_1 \end{align*}
where $$\left(u_0,v_0\right)$$ and $$\left(u_1,v_1\right)$$ represent the penultimate and last nodes and values respectively, as justified by derivation 1.

Derivation 1: The Tail Extrapolation
Given the assumed tail CDF
$F(v) = 1 - e^{a \times v+b}$
we can fix the parameters $$a$$ and $$b$$ by requiring that it passes through the point $$\left(u_1,v_1\right)$$ and has a derivative at $$u_1$$ that's equal to the gradient from $$\left(u_0,v_0\right)$$ to $$\left(u_1,v_1\right)$$
\begin{align*} 1 - e^{a \times v_1+b} &= u_1\\ -a \times e^{a \times v_1+b} &= \frac{u_1-u_0}{v_1-v_0} \end{align*}
so that the transition from interpolation to extrapolation is both continuous and smooth.

First we solve these equations for $$a$$
\begin{align*} e^{a \times v_1+b} &= 1 - u_1\\ -a \left(1-u_1\right) &= \frac{u_1-u_0}{v_1-v_0}\\ a &= \frac{u_0 - u_1}{\left(1-u_1\right) \times \left(v_1-v_0\right)} \end{align*}
and then for $$b$$
\begin{align*} \ln\left(e^{a \times v_1+b}\right) &= \ln\left(1 - u_1\right)\\ a \times v_1+b &= \ln\left(1 - u_1\right)\\ b &= \ln\left(1 - u_1\right) - a \times v_1 \end{align*}
Note that $$a$$ must be negative since $$u_0$$ is less than $$u_1$$, $$u_1$$ is less than one and $$v_0$$ is less than $$v_1$$, and consequently when $$v$$ equals infinity the exponential term must equal zero and the CDF one.

Finally, inverting the CDF yields the extrapolation
\begin{align*} 1 - e^{a \times v+b} &= u\\ e^{a \times v+b} &= 1-u\\ a \times v+b &= \ln(1-u)\\ v & = \frac{\ln(1-u) - b}{a} \end{align*}

The extrapolate function, which was used by the interpolate function to create the extrapolation, implements this scheme and is defined in listing 4.

Listing 4: Creating The Extrapolation
function extrapolate(node0, node1) {
var u0 = node0.x; var v0 = node0.y;
var u1 = node1.x; var v1 = node1.y;
var a = (u0-u1)/((1-u1)*(v1-v0));
var b = Math.log(1-u1) - a*v1;

a = 1/a;
return function(u) {return (Math.log(1-u)-b)*a;};
}

Another source of inefficiency in our original implementation is the sort operation that we used when splitting up an observation of $$v^\prime_0$$ into the terms $$v_i$$ of its sum. Fortunately we can do without it by instead defining
\begin{align*} e_i &\sim Exp(1)\\ v_i &= e_i \times \frac{v^\prime_0}{\sum_{j=0}^{n-1} e_j} \end{align*}
where $$Exp(1)$$ is the exponential distribution with a rate of one.
This works because of two properties of the exponential distribution; running sums of exponential observations that fall within an interval are uniformly distributed on that interval and a constant multiple of an exponential random variable is also an exponential random variable, albeit with a different rate.
The first of these properties is proven in derivation 2 and the second follows trivially from the definition of the exponential CDF. Specifically, an exponential random variable $$E_\lambda$$, having a rate of $$\lambda$$, has a CDF of
$P_\lambda\left(x\right) = 1 - e^{-\lambda \times x} = \Pr\left(E_\lambda \leqslant x\right)$
so that
$\Pr\left(a \times E_\lambda \leqslant x\right) = \Pr\left(E_\lambda \leqslant \frac{x}{a}\right) = 1 - e^{-\lambda \times \tfrac{x}{a}} = 1 - e^{-\tfrac{\lambda}{a} \times x} = P_{\lambda/a}\left(x\right)$
Together, these properties imply that this new definition of the $$v_i$$ yields results that are identically distributed to those produced by the old one but, crucially, without the sort operation.

Derivation 2: Sums Of Exponentials Are Uniforms
Given a uniform random variable $$U(0,T)$$ and $$n$$ independent observations $$U_i$$ of it we have
$\Pr\left(\bigwedge_{i=0}^{n-1} U_i \leqslant u_i\right) = \prod_{i=0}^{n-1} \Pr\left(U_i \leqslant u_i\right) = \prod_{i=0}^{n-1} F_U\left(u_i\right)$
where $$\wedge$$ means and for the condition following it for all of the indices from that defined beneath it to that above, $$\prod$$ is the product sign and $$F_U\left(x\right)$$ is the uniform CDF
$F_U\left(x\right) = \min\left(\max\left(\frac{x}{T},0\right),1\right)$
The joint PDF of those observations is therefore
$f_U\left(u_0, \dots, u_{n-1}\right) = \prod_{i=0}^{n-1} \frac{\mathrm{d}F_U}{\mathrm{d}x} \left(u_i\right) = \begin{cases} 0 & \left(\exists \, u_i < 0\right) \vee \left(\exists \, u_i > T\right)\\ \frac{1}{T^n} & \mathrm{otherwise} \end{cases}$
where $$\exists$$ means there exists and $$\vee$$ means or.

If we define $$u^\prime_j$$ as the $$j^\mathrm{th}$$ largest of the $$u_i$$ then they must have a joint density of
$f_{U^\prime}\left(u^\prime_0, \dots, u^\prime_{n-1}\right) = \begin{cases} \frac{n!}{T^n} & 0 \leqslant u^\prime_0 \leqslant u^\prime_1 \leqslant \dots \leqslant u^\prime_{n-2} \leqslant u^\prime_{n-1} \leqslant T\\ 0 & \mathrm{otherwise} \end{cases}$
since the densities of all but one of the $$n!$$ orderings of the $$u_i$$ must be transferred to the one non-decreasing set of $$u^\prime_j$$ that has a non-zero density.

Given $$n+1$$ independent observations $$E_i$$ of an exponential random variable $$Exp(\lambda)$$ that satisfy
$\left(\sum_{i=0}^{n-1} E_i \leqslant T\right) \wedge \left(\sum_{i=0}^n E_i > T\right)$
we have
$\Pr\left(\bigwedge_{i=0}^{n-1} E_i \leqslant e_i\right) = \dfrac{\left(\prod_{i=0}^{n-1} \Pr\left(E_i \leqslant e_i\right)\right) \times \Pr\left(E_n > T - \sum_{i=0}^{n-1} E_i\right)}{\Pr\left(N_T = n\right)}\\$
where the denominator is the probability that a Poisson process with an arrival rate of $$\lambda$$ will have $$n$$ arrivals in time $$T$$. The joint density of $$E_0$$ to $$E_{n-1}$$ is consequently
$f_E\left(e_0, \dots, e_{n-1}\right) = \begin{cases} 0 & \left(\sum_{i=0}^{n-1}e_i > T\right) \vee \left(\exists e_i < 0\right) \\ \dfrac{\left(\prod_{i=0}^{n-1} \frac{\mathrm{d}F_E}{\mathrm{d}x}\left(e_i\right)\right) \times \left(1-F_E\left(T - \sum_{i=0}^{n-1} e_i\right)\right)}{p_{\lambda T}(n)} & \mathrm{otherwise} \end{cases}$
where $$F_E$$ is the exponential CDF and $$p_{\lambda T}$$ is the Poisson probability mass function
\begin{align*} F_E(x) &= 1 - e^{-\lambda x}\\ p_{\lambda T}(n) &= \frac{(\lambda T)^n e^{-\lambda T}}{n!} \end{align*}
so that
\begin{align*} \dfrac{\left(\prod_{i=0}^{n-1} \frac{\mathrm{d}F_E}{\mathrm{d}x}\left(e_i\right)\right) \times \left(1-F_E\left(T - \sum_{i=0}^{n-1} e_i\right)\right)}{p_{\lambda T}(n)} &= \dfrac{\left(\prod_{i=0}^{n-1} \lambda e^{-\lambda e_i}\right) \times e^{-\lambda\left(T - \sum_{i=0}^{n-1} e_i\right)}}{\frac{1}{n!} (\lambda T)^n e^{-\lambda T}}\\ &= \dfrac{\lambda^n e^{-\lambda \sum_{i=0}^{n-1} e_i} e^{-\lambda T} e^{\lambda \sum_{i=0}^{n-1} e_i}}{\frac{1}{n!} \lambda^n T^n e^{-\lambda T}} = \frac{n!}{T^n} \end{align*}
Finally, defining
$s_i = \sum_{j=0}^i e_j$
which we can write as $$\mathbf{s} = \mathbf{M}\times\mathbf{e}$$ for vectors $$\mathbf{s}$$ and $$\mathbf{e}$$ whose elements are $$s_i$$ and $$e_i$$ respectively, and a matrix $$\mathbf{M}$$ with elements
$M_{i,j} = \begin{cases} 1 & j \leqslant i\\ 0 & \mathrm{otherwise} \end{cases}$
Now $$\mathbf{M}$$ is the Jacobian of the transformation from $$\mathbf{e}$$ to $$\mathbf{s}$$ and since it is lower triangular with a leading diagonal of ones it, and its inverse, must have a determinant of one. This means that, for some subset $$S$$ of the possible values of $$\mathbf{s}$$, the subset $$E$$ of the possible values of $$\mathbf{e}$$ that $$\mathbf{M}$$ maps to them and the joint PDF $$f_S$$ of $$\mathbf{s}$$, we have
$\int_S f_S(\mathbf{x_s}) \, \mathrm{d}\mathbf{x_s} = \int_E f_E(\mathbf{x_e}) \, \mathrm{d}\mathbf{x_e} = \int_S f_E(\mathbf{\mathbf{M}^{-1} \times x_s}) \, \mathrm{d}\mathbf{x_s} = \int_S \frac{n!}{T^n} \, \mathrm{d}\mathbf{x_s}$
by the rule of integration by substitution. It is therefore the case that
$f_S\left(\mathbf{s}\right) = f_{U^\prime}\left(u^\prime_0, \dots, u^\prime_{n-1}\right)$
and so the running sums of observations of an exponentially distributed random variable that fall within an interval $$[0,T]$$ must be uniformly distributed within that interval, as required.

The draw function defined in listing 5 uses this scheme to generate values of $$v_i$$ and then applies $$\phi^{-1}$$ to them to yield a random observation of an Archimedian copula.

Listing 5: Making A Random Observation Of An Archimedian Copula
function draw(q, inv, rnd, a) {
var n = a.length;
var v = inv(rnd());
var s = 0;
var i;

if(v===0) return ak.vector(n, 1);
for(i=0;i<n;++i) {
a[i] = -Math.log(1-rnd());
s += a[i];
}
if(s===0) return ak.vector(n, q(v/n));
v /= s;
for(i=0;i<n;++i) a[i] = Math.max(Math.min(q(a[i]*v), 1), 0);
return ak.vector(a);
}

The last step is to write a function to create Archimedean random variables using this implementation, as done with ak.archimedeanCopulaRnd in listing 6.

Listing 6: ak.archimedeanCopulaRnd
ak.archimedeanCopulaRnd = function(n, p, q, dnq, arg4, arg5, arg6) {
var m, threshold, rnd, v, f, inv;

if(ak.nativeType(arg4)!==ak.NUMBER_T) rnd = arg4;
else if(ak.nativeType(arg5)!==ak.NUMBER_T) {m = arg4; rnd = arg5;}
else {m = arg4; threshold = arg5; rnd = arg6;}

if(ak.nativeType(n)!==ak.NUMBER_T || !isFinite(n) || n!==ak.floor(n) || n<0) {
throw new Error('invalid dimension in ak.archimedeanCopulaRnd');
}

if(ak.nativeType(p)!==ak.FUNCTION_T) {
throw new Error('invalid generator in ak.archimedeanCopulaRnd');
}

if(ak.nativeType(q)!==ak.FUNCTION_T) {
throw new Error('invalid generator inverse in ak.archimedeanCopulaRnd');
}

if(ak.nativeType(dnq)!==ak.FUNCTION_T) {
throw new Error('invalid generator inverse derivative in ak.archimedeanCopulaRnd');
}

if(ak.nativeType(m)===ak.UNDEFINED_T) {
m = 1024;
}
else if(!isFinite(m) || m!==ak.floor(m) || m<2) {
throw new Error('invalid number of nodes in ak.archimedeanCopulaRnd');
}

if(ak.nativeType(rnd)===ak.UNDEFINED_T) {
rnd = Math.random;
}
else if(ak.nativeType(rnd)!==ak.FUNCTION_T) {
throw new Error('invalid random number generator in ak.archimedeanCopulaRnd');
}

switch(n) {
case 0:  f = function() {return ak.vector(0);};
break;

case 1:  f = function() {return ak.vector(1, rnd());};
break;

default: v = new Array(n);
inv = interpolate(n, p, q, dnq, m, threshold);
f = function() {return draw(q, inv, rnd, v);};
break;
}

f.dims = function() {return n;};
f.p = function() {return p;};
f.q = function() {return q;};
f.dnq = function() {return dnq;};
f.rnd = function() {return rnd;};

return Object.freeze(f);
};

Here we're allowing optional arguments specifying the number of interpolation nodes m, the convergence threshold of the inversion and the standard uniform random number generator rnd to be passed in as arg4, arg5 and arg6 so that we can call this function with any of
ak.archimedeanCopulaRnd(n, p, q, dnq) ak.archimedeanCopulaRnd(n, p, q, dnq, rnd) ak.archimedeanCopulaRnd(n, p, q, dnq, m, rnd) ak.archimedeanCopulaRnd(n, p, q, dnq, m, threshold, rnd)

Apart from this we're simply checking that the arguments are valid and providing defaults for the optional arguments before defining the function to make the random observations and adding property access methods to it. Note that we're treating zero and one dimensions as special cases that result in an empty vector and a vector with a single standard uniform element respectively.

### An Effective Implementation

To demonstrate this implementation of Archimedean random variables we shall again use the generator and inverse
\begin{align*} \phi_\theta(u) &= (-\ln u)^\theta\\ \phi_\theta^{-1}(t) &= e^{-t^{\frac{1}{\theta}}} \end{align*}
which are valid for $$\theta$$ greater than or equal to one.

Program 1 plots the density of the Archimedean copula defined by this generator with $$\theta$$ equal to two

which you can compare to the output of program 2, which begins by plotting pairs of independent standard uniforms, with the tenth of each plotted on the left hand side and the bottom of the graph, and ends by doing the same for a sample of vectors generated by ak.archimedeanCopulaRnd.

Program 2: ak.archimedeanCopulaRnd

The concentration of that sample clearly reflects the density of the copula and the plots of the marginals to the left and below are clearly uniformly distributed, illustrating that our algorithm is correctly generating random observations of it.

Finally, you can find the implementation of all of the Archimedean copula functions in ArchimedeanCopula.js.

### References

[1] Archimedean Skew, www.thusspakeak.com, 2018.

[2] Archimedean View, www.thusspakeak.com, 2018.

[3] On The Shoulders Of Gradients, www.thusspakeak.com, 2014.

[4] You're Going To Have To Think! Why Automatic Differentiation Won't Cure Your Calculus Blues, www.thusspakeak.com, 2014.

[5] Chalk The Lines, www.thusspakeak.com, 2018.