text:
#### GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networks

##### Ping Li, Weijie Zhao

We develop the "generalized consistent weighted sampling" (GCWS) for hashing the "powered-GMM" (pGMM) kernel (with a tuning parameter $p$). It turns out that GCWS provides a numerically stable scheme for applying power transformation on the original data, regardless of the magnitude of $p$ and the data. The power transformation is often effective for boosting the performance, in many cases considerably so. We feed the hashed data to neural networks on a variety of public classification datasets and name our method GCWSNet''. Our extensive experiments show that GCWSNet often improves the classification accuracy. Furthermore, it is evident from the experiments that GCWSNet converges substantially faster. In fact, GCWS often reaches a reasonable accuracy with merely (less than) one epoch of the training process. This property is much desired because many applications, such as advertisement click-through rate (CTR) prediction models, or data streams (i.e., data seen only once), often train just one epoch. Another beneficial side effect is that the computations of the first layer of the neural networks become additions instead of multiplications because the input data become binary (and highly sparse). Empirical comparisons with (normalized) random Fourier features (NRFF) are provided. We also propose to reduce the model size of GCWSNet by count-sketch and develop the theory for analyzing the impact of using count-sketch on the accuracy of GCWS. Our analysis shows that an 8-bit'' strategy should work well in that we can always apply an 8-bit count-sketch hashing on the output of GCWS hashing without hurting the accuracy much. There are many other ways to take advantage of GCWS when training deep neural networks. For example, one can apply GCWS on the outputs of the last layer to boost the accuracy of trained deep neural networks.

arrow_drop_up


text:
# A question about a stochastic process being Markov

Let $(X_{s},\mathcal{F}_{s})$ be a stochastic process adapted to a given filtration. I was told that, in order to prove that $X$ is Markov, it suffice to prove that for any nonnegative, Borel-measurable function $f$, $$E[f(X_{t}) \vert \mathcal{F}_{s}]=g(X_{s}) \quad a.s.$$ for $\textbf{some}$ Borel function $g$. I get confused here about the arbitrariness of the function g, shouldn't we expect that $g=P_{s,t} \circ f$, where $P_{s,t}$ is a transition function?

So I'm wondering if the above characterization for Markov processes is correct. I know this may be a stupid question. Any help or comment is greatly appreciated.

-
What is your definition of a Markov process? Anyway, this statement should be read as "for any $f$ there exists $g$"; does that help? – Nate Eldredge Aug 18 '12 at 2:50
@NateEldredge Is it too strong of a requirement to demand $g = f$? – Sasha Aug 18 '12 at 3:08
@Sasha: Yes, that definitely won't hold in general. (It holds iff $f$ is harmonic. In particular, for a finite-state irreducible Markov chain it will fail for every non-constant $f$.) – Nate Eldredge Aug 18 '12 at 3:21

Suppose that for $t\geq s$, we have some function $g$ so that $$E[f(X_{t}) \,\vert\, \mathcal{F}_{s}]=g(X_{s}) \quad \mbox{a.s.}\tag1$$ Conditioning on $X_s$ in (1) gives $$E[f(X_{t}) \,\vert\, X_s]=g(X_{s}) \quad \mbox{a.s.}\tag2$$ From this we deduce $$E[f(X_{t}) \,\vert\, \mathcal{F}_{s}]=E[f(X_{t}) \,\vert\, X_s] \quad \mbox{a.s.}\tag3$$ Equation (3) is one of the equivalent ways of expressing the Markov property. Notice that the arbitrary function $g$ has dropped out of the picture.

format: plain


text:
Unit of Temperature

Temperature like any other physical quantity is basically defined as the measure of the warmth or the coldness of a substance or object with reference to some standard value. While it is used to express hot and cold conditions, the temperature is usually measured with a thermometer which is marked in several temperature scales mainly Celsius and Fahrenheit. There are also various other units of temperature and we will look at them below.

SI Unit of Temperature

The SI unit of temperature as per the International System of Units is Kelvin which is represented by the symbol K. The Kelvin scale is widely accepted or used in the field of science and engineering. However, in most parts of the world, Celsius or Fahrenheit scale is used for measuring temperature.

In any case, here is the relation between Celcius Fahrenheit, and Kelvin;

Temperature Conversion

Celsius, Fahrenheit and Kelvin are the three common temperature scales. Each of the scales has its uses, so it is likely that you will encounter them and would require you to convert between them. In the table below, we have listed the conversion formula.

 From To Fahrenheit To Celsius To Kelvin Fahrenheit (°F) $^{\circ}F$ $(^{\circ}F-32)/1.8$ $(^{\circ}F-32)/1.8+273.15$ Celsius (°C) $(^{\circ}C\times1.8)+32$ $(^{\circ}C\times1.8)+32$ $^{\circ}C+273.15$ Kelvin (K) $(K-273.15)\times1.8+32$ $K-273.15$ K

Other Temperature Units

Some of the other common temperature units are Rankine, Newton, Rømer, Réaumur, and Delisle.

 Conversion of Units Units From Celsius To Celsius Kelvin [K] = [°C] + 273.15 [°C] = [K] − 273.15 Fahrenheit [°F] = [°C] × 9 ⁄ 5 + 32 [°C] = ([°F] − 32) × 5 ⁄ 9 Rankine [°R] = ([°C] + 273.15) × 9 ⁄5 [°C] = ([°R] − 491.67) × 5 ⁄ 9 Newton [°N] = [°C] × 33 ⁄ 100 [°C] = [°N] × 100 ⁄ 33 Rømer [°Rø] = [°C] × 21⁄40 + 7.5 [°C] = ([°Rø] − 7.5) × 40 ⁄ 21 Réaumur [°Ré] = [°C] × 4 ⁄ 5 [°C] = [°Ré] × 5 ⁄ 4 Delisle [°De] = (100 − [°C]) × 3 ⁄ 2 [°C] = 100 − [°De] × 2 ⁄ 3

Related articles:


text:
## Eurocrypt 2017

Eurocrypt 2017 was hosted by the ENS crypto group in Paris, France. There were four talks of special interest to researchers in curve-based cryptography, and a couple of items in the Rump Session.

## Twisted $\mu_4$-normal form for elliptic curves

David Kohel introduced the $\mu_4$-normal form for elliptic curves five years ago (at Indocrypt 2012). These curves are basically the “right way” to generalize Edwards curve arithmetic to characteristic 2. And they’re the right generalization not only mathematically, but also NIST-ically: existing standardized characteristic 2 curves cannot be transformed into $\mu_4$-normal form. David’s paper twists its way around that obstruction, for a small cost of two extra multiplications per point addition. These twisted $\mu_4$-normal curves are clearly the fastest and prettiest standard-compatible characteristic-2 elliptic curves out there. This is great news for binarophiles, and it will be interesting to see if implementers working on the hardware level can get much benefit from this.

## Efficient compression of SIDH public keys

Joost Renes gave a remarkably accessible talk about his work with Craig Costello, David Jao, Patrick Longa, Michael Naehrig, and David Urbanik on compressing public keys for the Supersingular Isogeny Diffie–Hellman protocol. SIDH is the best-known supposedly-quantum-resistant elliptic curve cryptosystem; while it might be slow compared with other postquantum alternatives, its principal attraction for cryptographers is its particularly small keys. Well, those keys are now even smaller (330 bytes for 128-bit security)—but the interesting thing in this paper is a much-improved key compression algorithm, which runs an order of magnitude faster than previous methods.

## Computation of a 768-bit prime field discrete logarithm

Thorsten Kleinjung gave a really nice talk on his record discrete logarithm computation with Claus Diem, Arjen Lenstra, Christine Priplata, and Colin Stahlke. Together they computed a discrete logarithm in a 768-bit prime field.
Why 768 bits? Because that matches the record for general integer factorization (from 2009, in a project that also included Thorsten and Arjen), which was computed with the General Number Field Sieve (GNFS); and GNFS is also what we use for prime-field discrete logs. In contrast to most recent finite-field discrete-log results which attack small-characteristic or pairing-related fields, this computation represents the state-of-the-art in the classic prime-field case.

The prime in question was $p = [2^{766}\pi] + 6272$, which is the smallest “safe prime” larger than $2^{766}\pi$ (“safe” meaning that $(p-1)/2$ is also prime, so that this represents the hardest case for generic algorithms applied to finite fields of the same size). The element 11 generates the multiplicative group of $\mathbb{F}_p$.

No doubt the question you are asking yourself right now is “what is the discrete logarithm of $[2^{766}e]$ with respect to the base 11?”  Ask no more, for Thorsten has the answer: it’s 325923617918270562238615985978623709128341338833721058543950813521768156295091638348030637920237175638117352442299234041658748471079911977497864301995972638266781162575370644813703762423329783129621567127479417280687495231463348812.

…So now you know. But as Thorsten points out, the journey is more interesting than the final destination: using some clever techniques detailed in the paper, this calculation took much less time and effort (a whole order of magnitude!) than the authors expected. Before you get too excited, it still took 5300 core years—but if this isn’t the exact discrete logarithm you are looking for, computing another one in the same field will now only take two core days. From a cryptographic perspective, that two-core-day figure is especially interesting, because that’s the time required to break actual keys, after a 5-core-millennium precomputation depending only on the field.

## A kilobit hidden SNFS discrete logarithm computation

Joshua Fried spoke about his work on with Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé about discrete logarithms in an even bigger prime field: 1024 bits. How can you compute discrete logs in such a large prime field? You cheat—or, I should say, the parameter generator cheats. Our estimates of the difficulty of these problems, and the cryptosystems that depend on them, are based on the performance of the General Number Field Sieve algorithm (GNFS). But Dan Gordon explained 25 years ago how to choose primes that are vulnerable to the much faster Special Number Field Sieve (SNFS)—but only if we know a secret backdoor, and detecting that backdoor is apparently infeasible. This project set up an instance of a backdoored 1024-bit prime, and then solved it.  This means that if you’re still using 1024-bit fields (and why are you doing such a thing in the twenty-first century?), then you should be extremely careful about their provenance. Kevin McCurley asked an interesting question: is Gordon’s backdoor optimal?

## Speeding up the Huff form of elliptic curves

Gamze Orhon gave a lightning-fast presentation of her work with Huseyin Hisil on optimizing Huff curve arithmetic during the rump session. The key is viewing these curves as curves in $\mathbb{P}^1\times\mathbb{P}^1$, rather than $\mathbb{P}^2$. The details are in their preprint.

## A database of discrete logarithm computations

Aurore Guillevic and Laurent Grémy have established a new reference website to help you keep track of records progress and progress in finite field discrete logarithm computations. It was about time we had a better solution than trawling the archives of the NMBRTHRY list! Laurent is hosting a front-end on his website, but what’s really nice is that the database itself is git-able.

—Ben Smith

This entry was posted in Uncategorized. Bookmark the permalink.

### 3 Responses to Eurocrypt 2017

1. David wong says:

> it still took 5300 core years

What I want to understand is how long 5300 core years takes in practice? Depending on the machines we use. I always see this core years numbers thrown around but never really understand them 🙂

• Leon says:

1 core year: 1 CPU core running for a full year at 100% load
5300 core years: 1 year of 5300 CPU cores running at 100% load

5300 core years can even run in a few seconds if you have a lot of cores (~ 1,67*10^11) 🙂

• David wong says:

Thanks for the answer Leon. I guess a better question would be: how affordable/practical is it to run 5300 CPUs? If it is affordable and practical, how much more CPUs can I get to make the running time practical as well (1 year is way too much :))


text:
### Archive

Archive for the ‘Probability’ Category

## Questions: Probability And and OR

A bag contains 4 gold(G) balls and 7 silver(S) balls.  A ball is taken out its colour is noted and then it is put back.  Then this is repeated a second time.

What is the:

$P(G,G)$

$P(S,S)$

$P(\mbox{exactly one G})$

You have a biased die.  From a single roll the P(3)=0.1 and P(5)=0.4.  If the die is rolled twice what is the:

$P(3,3)$

$P(5,5)$

$P(\overline{3},\overline{3})$

$P(\mbox{exactly one 5})$

Becky wakes up one morning and is really tired and does not want to open her eyes.  In her draw she has 5 white(W) socks and 9 blue polka(P) dot socks, the two odd ones have gone to that place where all odd socks go.  She takes out a sock and puts it on and then takes out another to place on the other foot.  What is the:

$P(W then P)$

$P(P then W)$

$P(pair)$

Nicola and Louise are playing a very dangerous game and it is winner takes all.  In a bag there are 5 chocolates, 4 are praline flavour and 1 is a disgusting orange flavour.  To look at they are identical.  Whoever eats the orange chocolate loses.  Nicola is to take the first two chocolates and louise is to take the next two.  What is the:

P(Nicola looses)

P(Its a draw)

P(Louise looses)

Categories: Probability

## Probability: An event not happening

Consider the situation of a bag with 3 gold(G) balls and 2 silver(S) balls.

What is:

• P(G)?
• P(not G)?

$P(G)=\frac{3}{5}$, 3 gold balls and 5 balls in total.

$P(\text{not }G)=\frac{2}{5}$, 2 not gold (silver) balls and 5 balls altogether.

The important point to notice here is that the number of gold balls + number of not gold balls is equal to the total number of balls.

$\implies P(\text{not }A)=1-P(A)$

#### Notation

We can write P(not A) as $P(\overline{A})$, where the over bar means not.

Examples

If the $P(A)=0.7$, what is $P(\overline{A})$?

$P(\overline{A})=1-P(A)=1-0.7=0.3$

If the $P(win)=15\%$, what is $P(\overline{win})$

$P(\overline{win})=100\%-P(A)=100\%-15\%=85\%$

If the $P(blue)=\frac{4}{15}$, what is $P(\overline{blue})$

$P(\overline{blue})=1-P(blue)=1-\frac{4}{15}=\frac{11}{15}$

Categories: Probability

## Probability: AND & OR rule

### The ‘OR’ rule

The ‘OR’ rule states $P(A\text{ or } B)=P(A)+P(B)$

This makes sense since the number of successes(NoS) = (NOS of A) + (NoS of B)

The number of outcomes has not changed.

So $P(A\mbox{ or } B)=\frac{\mbox{(NOS of A) + (NoS of B)}}{\mbox{possible outcomes}}=\frac{\mbox{(NOS of A)}}{\mbox{possible outcomes}}+\frac{\mbox{(NOS of A)}}{\mbox{possible outcomes}}$

$\implies P(A\mbox{ or } B)=P(A)+P(B)$

Examples

A bag contains a red ball, 5 blue ball and 4 green balls.

1) P(red)

2) P(blue)

3) P(green)

4) P(red or green)

5) P(red or green or blue)

1) $P(red)=\frac{1}{10}$

2) $P(blue)=\frac{5}{10}$

3) $P(green)=\frac{4}{10}$

4) $P(\mbox{red or green})=P(red)+P(green)=\frac{1}{10}+\frac{4}{10}=\frac{5}{10}$

5) $P(\mbox{red or green or blue})=P(red)+P(green)+(blue)=\frac{1}{10}+\frac{4}{10}+\frac{5}{10}=1$

### The ‘AND’ rule

Here we are considering the probability of something happening and then something else happening.

Let’s consider a die rolled twice.

What is the P(two sixes)?

Well we will get a ‘6’ $\frac{1}{6}$ of the time.  Of these times we will get another ‘6’ $\frac{1}{6}$ of the time.

So $P(\mbox{two sixes})=\frac{1}{6}\text { of }\frac{1}{6}=\frac{1}{6}\times \frac{1}{6}=\frac{1}{36}$

So $P(\mbox{A and B})=P(A)\times P(B)$

Examples

A bag contains 4 red(R) balls and 3 black(B) balls.  I take out a ball, look at it and then put it back.  I then take out another ball and record its colour.  What is the:

1. P(R,R) $\rightarrow$ means getting two reds.
2. P(R then B)
3. P(R,B) $\rightarrow$ means getting a red and blue in any order. i.e. red then blue or blue then red

$P(R)=\frac{4}{7}$

$P(B)=\frac{3}{7}$

So

$P(R,R)=\frac{4}{7} \times\frac{4}{7} =\frac{16}{49}$

$P(\mbox{R then B})=\frac{4}{7}\times \frac{3}{7}=\frac{12}{49}$

$P(\mbox{R, B})=P(\mbox{R then B}) + P(\mbox{B then R})$

$P(\mbox{B then R})=\frac{3}{7}\times \frac{4}{7}=\frac{12}{49}$

$P(R,B)=\frac{12}{49}+\frac{12}{49}=\frac{24}{49}$

#### Questions

Categories: Probability

## Questions: Equilikely outcomes

1.

Freya has a bag with 3 red balls and 2 green balls.  A ball is taken out and its colour is recorded.

What is P(red)?

The ball she took out was red.  Freya keeps the ball, she thinks it is lucky.

What is the probability that the next ball is red as well?

The ball she took out was green.  Freya didn’t like this ball, it reminded her of custard, so she flushed it down the toilet.

What is the probability the next ball is red?

2.

Inhoo was watching butterflies landing on a flower in a garden.  There were 7 white butterflies (Inhoo’s favourite) and 3 red butterflies.

What is the probability that the next butterfly to land on a flower is a white one?

In fact a red butterfly landed on the flower.  Inhoo was so angry set caught the butterfly and threw it in a nearby spiders web.

What is the probability that the next butterfly to land on a flower is a white one?

Again a red butterfly landed on the flower.  Inhoo almost cried, but she gathered herself together, caught the butterfly and put it in a jar.

What is the probability that the next butterfly to land on a flower is a white one?

Yet again a red butterfly landed on the flower.  This time Inhoo took no chances, she caught the butterfly and ate it there and then.

What is the probability that the next butterfly to land on a flower is a white one?

3.

From a pack of cards what is:

P(black)?

P(king)?

P(2 or 3)?

P(red ace)?

4.

Lydia has a set of cards.  On them she has either drawn a heart or a dagger.  She has drawn 6 daggers.  If $P(\text{dagger})=\frac{2}{5})$, how many hearts did she draw?

Categories: Probability

## Probability: Equilikely outcomes

The probability of an event happening is how likely it is to happen or how frequently it happens.

In a perfectly fair world if a die was thrown a five would come up every six throws.  That means that the probability of getting a 5 = $\frac{1}{6}$.

Generally the probability of something happening $=\frac{\text{possible successes}}{\text{possible outcomes}}$

#### Notation

The probability of A happening can be written as P(A).

So P(red) could be what is the probability of getting red?

Examples

What is the probability of rolling a 3 with a die?

There is 1 possible success (getting 3)

There are 6 possible outcomes (1, 2, 3, 4, 5 or 6)

So $P(3)=\frac{1}{6}$

When rolling a die what is the probability of getting a square number?There are 2 possible successes (1 or 4)There are 6 possible outcomes (1, 2, 3, 4, 5 or 6)

So $P(\text{square})=\frac{2}{6}=\frac{1}{3}$

When playing cards what is the probability of getting a red heart?There are 13 possible successes (13 hearts)There are 52 possible outcomes (52 cards in total)

So $P(\text{heart})=\frac{13}{52}=\frac{1}{2}$

A bag contains 5 red discs and 7 blue discs.I take out a red disc and keep it.  What is the probability the next disc is also red?There are 4 successes (there are only 4 red discs left as we have taken one our already)

There are 11 possible outcomes (there are only 11 discs left now)

So $P(\text{red})=\frac{4}{11}$

Important note: Probabilities can only be given as fractions, decimals or percentages

Questions

Categories: Probability


text:
## raycasting – How to find if a Ray intersects a Triangle Clockwise or Counter Clockwise

Assume the triangle’s vertices are wound in the order A, B, C

Form a normal to the triangle N = (B – A) x (C – A)

Now you can detect whether your triangle is clockwise or counter-clockwise by the sign of the dot product between this normal and the ray direction

In a left-handed coordinate system:

• Negative = Clockwise from ray’s point of view
• Positive = Counter-clockwise from ray’s point of view

In a right-handed coordinate system, it’s the opposite:

• Negative = Counter-clockwise from ray’s point of view
• Positive = Clockwise from ray’s point of view

## unity – Efficient way to build a 360 rotation system with clockwise and counterclockwise direction

I’ve been struggle with rotation for sometime now, maybe it isn’t that hard for someone who dominates the mathematical side of things regarding rotation and angles but, I need to build a rotation system that rotates the player to either clockwise or counterclockwise direction according to the nearest direction to the target angle.

I.E.

If my player is rotated to 45° and the direction is changed to 135°, he must rotate 90º clockwise (from 45° to 135°).
If my player is rotated to the same 45° and the direction is changed to 315°, he must rotate 90° counterclockwise (from 45° to 315º).

This didn’t seemed a big deal when I started, but it’s been hard for me to build something that cover all the rotation possibilities, which tells me that I’m doing something wrong here. I mean, there’s must be a couple of formulas that fit this problem and cover all the possible rotations or something.

Right now, my rotation system is configured to a minimal of 5 degrees of rotation, wich means that the possible degrees goes from 0 to 355(it never get to 360, going back to 0 instead).

I don’t have a code to show cause everytime I try to build this, I reach to a point where there are so many possibilities that aren’t covered by my tests that I end up deleting everything to try again, but I’m tired of this seemingly endless loop (for me anyway lol).

Does anyone knows a way to build this?

-EDIT-

My project is 3D and the camera perspective is similar to sports games like NBA 2K or soccer games in general. The input is a Vector2 obtained with the new input system. I need to move my player around with root motion, which means that my goal with this system is to calculate the rotation data to be passed as an animation parameter (using a event), so the correct animation is played and the player finally rotate according to the animation. The main part of the code (calculation part) was built by a friend of mine, who has more knowledge than me. This is my current code:

``````if (movementVector != Vector2.zero)
{
targetRotationAngle = Mathf.Atan2(movementVector.x, movementVector.y) * Mathf.Rad2Deg + cameraTransform.eulerAngles.y; //FUNCTIONAL CODE BUILT BY A FRIEND
targetRotationAngle = Mathf.CeilToInt(targetRotationAngle / 5) * 5; //FUNCTIONAL CODE BUILT BY A FRIEND
if (targetRotationAngle < 0)
targetRotationAngle += 360;
if (currentRotationAngle == targetRotationAngle)
return;
else
{
if (currentRotationAngle < targetRotationAngle)
{
Debug.Log("Clockwise rotation in " + (targetRotationAngle - currentRotationAngle) + " degrees");
}
if (currentRotationAngle > targetRotationAngle)
{
Debug.Log("Counterclockwise rotation in " + ((360-currentRotationAngle)+targetRotationAngle) + " degrees");
}
}
currentRotationAngle = targetRotationAngle;
}
``````

This is a summarized version of my previous attempts (the ELSE part), I know my formula is wrong, cause it doesn’t cover all the rotation scenarios, the more I tried to build, more of this IF’s were nesting. That’s why I’ve decided to ask…

## Algorithms – Do you prove that if \$ p_1 times p_2 \$ is positive, \$ p_1 \$ of \$ p_2 \$ is clockwise?

In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $$p_1 times p_2$$ is then positive $$p_1$$ is clockwise from $$p_2$$ and if it's negative, then $$p_1$$ is counterclockwise from $$p_2$$?

I found the following solution:
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch33.pdf

To sum it up again, consider the angles that both vectors make with the x-axis. We know that the angle is $$arctan y / x$$. We also know the cross product $$p_1 times p_2 = x_1y_2 – y_1x_2$$. If this product is greater than zero, it means that $$y_2 / x_2> y_1 / x_1$$. Since $$arctan$$ then the angle is monotonous $$p_2$$ makes bigger with the x-axis. That's why, $$p_2$$ is relative to clockwise $$p_1$$.

BUT the question demands to prove it $$p_1$$ is relatively clockwise $$p_2$$. What am i missing Is the above proof wrong?

## c – Rotate the square matrix 90 degrees clockwise

``````#include
#include
#include

void nl(void) {     //function to print new line
printf("n");
}

int** allocate(_size) {
int** matrix=(int**)malloc(sizeof(int*)*_size);
for(int i=0;i<_size;i++) {
matrix(i)=(int*)malloc(sizeof(int)*_size);
}
return matrix;
}

void scanMatrix(_matrix,_size)
int** _matrix;
{
printf("Enter the values: ");
for(int i=0;i<_size;i++) {
for(int j=0;j<_size;j++) {
scanf("%d",&_matrix(i)(j));
}
}
}

void printMatrix(_matrix,_size)
int** _matrix;
{
for(int i=0;i<_size;i++) {
for(int j=0;j<_size;j++) {
printf("%d ",_matrix(i)(j));
}
nl();
}
}

void swap(num1,num2)
int* num1;
int* num2;
{
*num1=*num1+*num2;
*num2=*num1-*num2;
*num1=*num1-*num2;
}

void rotateMatrix(_matrix,_size)
int** _matrix;
{
for(int i=0;i<_size;i++) {
for(int j=i+1;j<_size;j++) {
swap(&_matrix(i)(j),&_matrix(j)(i));
}
}
for(int i=0;i<_size;i++) {
for(int j=0;j<_size/2;j++) {
swap(&_matrix(i)(j),&_matrix(i)(_size-1-j));
}
}
}

main(argc,argv)
const char** argv;
{
int size=0;
printf("Enter the size of the square matrix: ");
scanf("%d",&size);
int** matrix=allocate(size);
scanMatrix(matrix,size);
printMatrix(matrix,size);
nl();
rotateMatrix(matrix,size);
nl();
printMatrix(matrix,size);
return 0;
}
``````

This code does not take up additional memory and also uses runtime allocation using `malloc`, However, it has a temporal complexity of O (n ^ 2). How do I optimize it further?

## Plotting – polar curve with zero up and clockwise

You can rotate your data to zoom clockwise by generating it as follows:

``````datar = Import("https://pastebin.com/raw/CM7Rj6jC", "Table");
datar((All, 1)) = 2 (Pi) (datar((All, 1)))/360;
nlm1 = NonlinearModelFit(datar((All, {1, 2})), a Cos(t + (Phi))^2, {a, (Phi)}, t);
nlm2 = NonlinearModelFit(datar((All, {1, 3})), a Cos(t + (Phi))^2, {a, (Phi)}, t);
datar((All, 1)) = 2 Pi - (# - Pi/2) & /@ datar((All, 1));
``````

And draw the polar curve as follows:

``````PolarPlot(
{nlm1(2 Pi - (t - Pi/2)), nlm2(2 Pi - (t - Pi/2))},
{t, 0, 2 (Pi)}
)
``````

And add the following two options `ListPolarPlot` adjust the hooks and the axle accordingly

``````PolarTicks -> {Table({(360 - (deg - 90)) Degree, deg}, {deg, 0, 350, 10}), None},
PolarAxesOrigin -> {{Top, Up}, Automatic},
``````

`PolarAxes` will issue a warning, but this warning also appears for examples in the documentation. So it seems that this is a mistake that was introduced sometime. It's best to just ignore it. `Quiet` can get rid of it altogether.

To check if the formula works, we can use some points for illustration. For example, we see that what used to be zero is now 90, and what was 180 before has now turned 270. If we calculate this with the given formula, we get the following results as expected:

``````Mod(360 - (0 - 90), 360)
``````

90

``````Mod(360 - (180 - 90), 360)
``````

270

## unity – Should a `Vector2.Rotate (float angle)` method in a universe turn clockwise in a counterclockwise direction?

I'm doing a 2D game in Unity and from what I understand The convention is that an angle of 0 is up and by increasing the angle, the object is rotated counterclockwise,

By the way, I have made this assumption by myself the `rotation.z` Value in the inspector window of a transformation. If it is 0, the object is `transform.up` points towards positive y. Increasingly `rotation.z` turns the object counterclockwise, d. H. the object `transform.up` Point to a negative X at 90 degrees. Let me know if this is wrong.

Given the convention where increasing the angle counter-clockwise, what should be my extension method `Vector2.Rotate(this Vector2 vector, float angle)` do? My question is if that works `Vector2.up.Rotate(90)` would result in a clockwise or counterclockwise rotation, where would be clockwise `Vector2.right` and counterclockwise would give `Vector2.left`,

At first it seemed to me an initiative that this would be the case obviously rotate clockwise. It's a positive number, so it turns clockwise. I am not sure where this bias comes from, but with `Rotate(90)` feels like it should turn right (clockwise).

After thinking about it, I think it makes more sense to do so `Rotate(90)` turn counterclockwise. Since the universe assumes a higher / positive angle that results in a counterclockwise rotation, the method must also adhere to this rule. But for some reason, it does not seem intuitive to me that I would need to call rotates with a negative number to spin clockwise. `Rotate(-90) // clockwise`,

Feedback, anecdotes, ideas or conventions highly appreciated, thanks!

## Interview Questions – Turn a matrix clockwise in Scala

For a given matrix, rotate elements clockwise.
Examples:

``````entrance
1 2 3
4 5 6
7 8 9

Output:
4 1 2
7 5 3
8 9 6

Entrance:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output:
5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12
``````

Scala implementation is below. I feel like I do not need a predefined rotated matrix (which I fill with -1), and I can build it during my recursive calls, but I can not.
Thank you in advance for helping me with this.

``````import scala.util.Random

object MatrixRotate extends App {

def getCol (c: int, m: array)[Array[Int]]): Seq[Int] = (0 to (m (0). Length - 1)) Map (r => m (r) (c))
def getRow (r: int, m: array)[Array[Int]]): Seq[Int] = m (r) · zuSeq
def innerMatrix (m: Array[Array[Int]]): Array[Array[Int]]= {
if (m.length == 0) Array.empt
miscellaneous
val row = m.length - 1
Val Cols = m (0) · length - 1

(1 to rows) .map {r =>
(1 to columns) .map {c =>
m (r) (c)
} .toArray
} .toArray
}
}

val rotatedMatrix = Array.Fill (6) (Array.Fill (6) (-1))
def turnByOne (m: Array)[Array[Int]], startRow: Int, startCol: Int,
endRow: Int, endCol: Int): Unit = {
m.size match {
Case 0 =>
case _ =>
getRow (0, m) match {
Case zero =>
case x => x.init.zipWithIndex foreach {case (e, index) => rotatedMatrix (startRow) (startCol + index + 1) = e}
}
getCol (m (0) .length - 1, m) match {
Case zero =>
case x => x.init.zipWithIndex foreach {case (e, index) => rotatedMatrix (startRow + index + 1) (endCol) = e}
}
getRow (m.length - 1, m) match {
Case x :: Nil =>
case x => x.tail.zipWithIndex foreach {case (e, index) => rotatedMatrix (endRow) (startCol + index) = e}
}
getCol (0, m) match {
Case x :: Nil =>
case x => x.tail.zipWithIndex foreach {case (e, index) => rotatedMatrix (startRow + index) (startCol) = e}
}
rotateByOne (innerMatrix (m), startRow + 1, startCol + 1, endRow - 1, endCol - 1)
}

}

val matrix = Array.fill (6) (Array.fill (6) (Random.nextInt (100)))
Matrix foreach (row => println (row.mkString (",")))

println ("----------")

Rotate ByOne (Matrix, 0, 0, 5, 5)
rotatedMatrix foreach (row => println (row.mkString (",")))
}
``````


text:
### Chapter 2 - Convergences and error estimates - Exercises

Exercise 2.1 (central limit theorem with various rates)
Let $(X_m)_{m\geq 1}$ be a sequence of i.i.d. random variables having the symmetric Pareto distribution with parameter $\alpha>0$, whose density is
$$\frac{\alpha}{2|z|^{\alpha+1}} 1_{|z|\geq 1}.$$
Set $\overline{X}_M:=\frac{1}{M}\sum_{m=1}^M X_m$.
1. For $\alpha>1$, justify the a.s. convergence of $\overline{X}_M$ to 0 as $M\to +\infty$.
2. For $\alpha>2$, prove a central limit theorem for $\overline{X}_M$ at rate $\sqrt M$.
3. For $\alpha\in (1,2]$, determine the rate $u_M\to +\infty$ such that $u_M \overline{X}_M$ converges in distribution to a limit.
Hint: to distinguish the cases $\alpha=2$ and $\alpha\in (1,2)$, use the Levy criterion (Theorem A.1.3) with the representation of the characteristic function  $$\mathbb{E}(e^{iu X})=1 + \alpha |u|^\alpha\int_{|u|}^{+\infty} \frac{\cos(t)-1}{t^{\alpha+1}} {\mathrm d}t.$$

Exercise 2.2 (
substitution method)
We aim at estimating the Laplace transform $$\phi(u):=\mathbb{E}(e^{uX})=e^{\sigma^2u^2/2}$$ of a Gaussian random variable $X\overset d= {\cal N}(0,\sigma^2)$, using a sample of size $M$ of i.i.d. copies of $X$. The parameter $\sigma^2$ is unknown.
Which procedure is the most accurate?
1.  Computing the empirical mean $\phi_{1,M}(u):= \frac{ 1 }{M }\sum_{m=1}^M e^{u X_m}$;

or
2. Estimating $\sigma^2$ by the empirical variance $\sigma^2_M$, then estimating $\phi(u)$ by $\phi_{2,M}(u):= e^{\frac{ u^2 }{2 }\sigma^2_M}$.
We will compare  estimators using related confidence intervals.
Solution.

Exercise 2.3 (central limit theorem, substitution method)
Consider  the setting of Proposition 2.2.6, with the estimation of  $\max(\mathbb{E}(X),a)$. Let $\overline X_{1,M}=\frac{ 2 }{ M}\sum_{m=1}^{M/2} X_i$ and $\overline X_{2,M}=\frac{ 2 }{ M}\sum_{m=M/2+1}^{M} X_i$. Set
$$\overline f_M=\max(\frac{ 1 }{ M}\sum_{m=1}^{M} X_i,a),\qquad \underline f_M=\mathbb{1}_{\overline X_{1,M}\geq a} \overline X_{2,M}+\mathbb{1}_{\overline X_{1,M}< a} a.$$
1. Assume  $a> \mathbb{E}(X)$. Prove that  both  the upper estimator $\overline f_M$ and the lower estimator  $\underline f_M$ converge to $\max(\mathbb{E}(X),a)$ in $L_1$ at the rate $M$.
2. Assume  $a< \mathbb{E}(X)$. Establish a central limit theorem at rate $\sqrt M$ for  $\overline f_M-\max(\mathbb{E}(X),a)$,  for $\underline f_M-\max(\mathbb{E}(X),a)$, and for the pair $(\overline f_M-\max(\mathbb{E}(X),a),\underline f_M-\max(\mathbb{E}(X),a))$.
3. Investigate the case $a=\mathbb{E}(X)$.
Exercise 2.4 (sensitivity formulas, exponential distribution)
Let $Y\overset d={\cal E}xp(\lambda)$ with $\lambda > 0$ and set $F (\lambda) = \mathbb{E}(f (Y))$ for a given bounded function  $f$.
1. Use the likelihood ratio method to represent $F'$ as an expectation.
2.  Use the pathwise differentiation method to get another representation for smooth $f$ (use the formula $X=-\frac{1}{\lambda}\log(U)$).
3.  By integrating by parts, show that both formulas coincide.

Exercise 2.5 (sensitivity formulas, multidimensional Gaussian distribution)
In dimension 1, Example 2.2.11 gives, for $Y^{m,\sigma}\overset d= {\cal N}(m,\sigma^2)$,
\begin{align*}
\partial_m \mathbb{E}(f(Y^{m,\sigma}))&=\mathbb{E}\Big(f(Y^{m,\sigma})\frac{(Y^{m,\sigma}-m)}{\sigma^2}
\Big),\\
\partial_\sigma \mathbb{E}(f(Y^{m,\sigma}))&=\mathbb{E}\Big(f(Y^{m,\sigma}){\frac1 \sigma}\big[\frac{(Y^{m,\sigma}-m)^2}{\sigma^2}-1\big]
\Big).
\end{align*}
Extend this to the multidimensional case for the sensitivity with respect to the mean $\mathbb{E}(Y)$ and to the covariance matrix $\mathbb{E}(Y Y^*)$ (assumed to be invertible).
Hint: for the sensitivity w.r.t. elements of $\mathbb{E}(Y Y^*)$, one has to perturb the matrix $\mathbb{E}(Y Y^*)$ in a symmetric way to keep it symmetric.

Exercise 2.6 (sensitivity formulas, resimulation method)
We aim at illustrating the benefit of using Common Random Numbers (CRN) in the evaluation of $\partial_\theta \mathbb{E}(f(Y^\theta))$ and the impact of the smoothness of $f$ on the estimator variance. We consider the Gaussian model $Y\overset d={\cal N}(\theta,1)$.
1. Denote by $(G_1,\dots,G_M,G'_1,\dots,G'_M)$ i.i.d. copies of ${\cal N}(0,1)$ and consider a smooth function $f$, bounded with bounded derivatives. Compute the variance of the estimator with different random numbers $$\frac 1M\sum_{m=1}^M \frac{f(\theta+\varepsilon+G_m)-f(\theta-\varepsilon+G'_m)}{2\varepsilon}$$ as $\varepsilon\to0$ ($M$ fixed).
2.  Compare it with that of the CRN estimator $$\frac 1M\sum_{m=1}^M \frac{f(\theta+\varepsilon+G_m)-f(\theta-\varepsilon+G_m)}{2\varepsilon}.$$
3. Analyze the variance of the CRN estimator when $f(x)=\mathbf{1}_{x\geq 0}$. What is its dependency w.r.t. $\varepsilon\to0$?
Write a simulation program illustrating these features.

Exercise 2.7 (concentration inequality, maximum of Gaussian variables)
Corollary 2.4.1 states that if $Y$ is a random vector in $\mathbb{R}^d$ with distribution $\mu$ satisfies a logarithmic Sobolev inequality with constant $c_\mu>0$, then for any Lipschitz function $f:\mathbb{R}^d\mapsto \mathbb{R}$, we have
$$\mathbf{P}(|f(Y)-\mathbf{E}(f(Y))|>\varepsilon)\leq 2\exp\left(-\frac{ \varepsilon^2 }{c_\mu |f|_{\rm Lip}^2}\right), \qquad \forall \varepsilon\geq 0.$$
1. Use the above concentration inequality in the Gaussian case to establish the Borell inequality (1975): for any centered $d$-dimensional Gaussian vector $Y=(Y_1,\dots,Y_d)$, we have $$\mathbb{P}\left(|\max_{1\leq i\leq d} Y_i-\mathbb{E}(\max_{1\leq i\leq d} Y_i)|>\varepsilon\right)\leq 2\exp\Big(-\frac{ \varepsilon^2 }{2\sigma^2}\Big), \qquad \forall \varepsilon\geq 0$$ where $\sigma^2=\max_{1\leq i\leq d}\mathbb{E}(Y^2_i)$ (Observe that the constants do not depend much on the dimension, thus passing to infinite dimension is possible).
Hint: first assume that $(Y_i)_i$ are i.i.d. standard Gaussian random variables. To prove  the general case, use the representation of Proposition 1.4.1.
2. We consider the case $d\to+\infty$ and assume that $\sigma^2=\max_{1\leq i\leq d}\mathbb{E}(Y^2_i)$ is bounded as $d\to+\infty$. Assuming that $\mathbb{E}(\max_{1\leq i\leq d} Y_i)\to+\infty$, and deduce that $$\frac{\max_{1\leq i\leq d} Y_i }{\mathbb{E}(\max_{1\leq i\leq d} Y_i)}\underset{d\to+\infty}{\overset{{\rm Prob.}}\longrightarrow 1}.$$
Application: in the standard i.i.d. case, since $\mathbb{E}(\max_{1\leq i\leq d} Y_i)\sim\sqrt{2\log(d)}$ as $d\to+\infty$ (see [J. Galambos. The Asymptotic Theory of Extreme Order Statistics. R.E. Kreiger, Malabar, FL, 1987]), we obtain a nice deterministic equivalent (in probability) of $\max_{1\leq i\leq d} Y_i$.
Solution.


text:
## Using the terminal

Here is a simple screenshot of a terminal interacting with the REPL (Read-Print-Eval Loop):

Note:
If you have the GNU library readline (or the Editline Library (aka libedit)) installed, you will be able to do line editing as in usual shells.

## Introduction to GUI Programming

STklos permits to easily program GUI (Graphical User Interfaces). To program a GUI, you need to install some packages which are available through the ScmPkg mechanism.

The packages can easily be downloaded through the command line with the stklos-pkg command. See the ScmPkg for more information.

Note:
The packages described below search the system GUI toolkit libraries in some standard places (mainly /usr/lib and /usr/local/lib). If your libraries are installed in another directory, you can set the shell variable STKLOS_GTK_DIR to that directory name. This variable is used both for installing the ScmPkg and for running your program.

Programming a GUI in STklos can be done at three different methods:

• The first method uses a simple wrapping of the GTK+ library. This wrapping is provided by the stklos-gtk-base package. Programming at this level is very similar to programming a GUI in C. In particular, standard GTK+ documentation can easily be followed to build a GUI. An example of GUI using this package is given below.

Code and explanations

• The second method uses the Glade interface builder. Glade home page describes it as “a RAD tool to enable quick & easy development of user interfaces for the GTK+ toolkit and the GNOME desktop environment, released under the GNU GPL License. The user interfaces designed in Glade are saved as XML, and by using the libglade library these can be loaded by applications dynamically as needed.”

To build an interface with the Glade interface builder, you need to install the stklos-gtk-glade package. An example of GUI using this package is given below.

Code and explanations

• The third method uses an OO model for GUI programming GUIs. This model is very similar to the one originally defined in STk Scheme. This model is described in the JFP and ISOTAS papers.

Programming interfaces with the OO model permits to define your own widgets thanks to the MOP of STklos. With the stklos-gtklos package you can define the following GUI:

Code and explanations


text:
# Group Theory 5: Subgroups

In this lecture, we study subgroups. A nonempty subset $H$ of a group $G$ is called a subgroup of $G$ if $H$ itself forms a group relative to the operation $\cdot$ in $G$. If $H$ is a subgroup of $G$, we simply write $H\leq G$. Clearly $G\leq G$ and $\{e\}\leq G$. $G$ and $\{e\}$ are called trivial subgroups of $G$. Before we discuss subgroups further we need to go over some basic properties of a group as we need them.

Lemma. If $G$ is a group, then:

(a) Its identity element is unique.

(b) Each $a\in G$ has a unique inverse $a^{-1}\in G$.

(c) $\forall a\in G$, $(a^{-1})^{-1}=a$.

(d) $\forall a,b\in G$, $(ab)^{-1}=b^{-1}a^{-1}$.

The proof of this lemma is pretty much straightforward and is left to readers.

In order to show that a nonempty subset $H$ of a group $G$ is a subgroup we need to check:

1. $H$ is closed under $\cdot$, the operation in $G$. That is, $\forall a,b\in H$, $ab\in H$.

2. $e\in H$.

3. $\forall a\in H$, $a^{-1}\in H$.

Note that the associative law holds automatically. It turns out that there is a simpler criterion to check if a nonempty subset is a subgroup of a group.

Lemma. A nonempty subset $H\subset G$ is a subgroup of $G$ if and only of $\forall a,b\in H$, $ab^{-1}\in H$.

Proof. ($\Longrightarrow$) Clear.

($\Longleftarrow$) Let $a,b\in H$. Then by assumption, $aa^{-1}=e\in H$. Since $a,e\in H$, $ea^{-1}=a^{-1}\in H$. Since $b^{-1}\in H$, $a(b^{-1})^{-1}=ab\in H$. Therefore, $H$ is a subgroup of $G$.

Example. $\forall n\in\mathbb{N}\cup\{0\}$, $n\mathbb{Z}\leq(\mathbb{Z},+)$. Here, $n\mathbb{Z}=\{nx: x\in\mathbb{Z}\}$. In fact, they are all the subgroups of $(\mathbb{Z},+)$.

Definition. The cyclic subgroup of $G$ generated by $a\in G$ is $\{a^k: k\in\mathbb{Z}\}$. It is denoted by $\langle a\rangle$.

Example. Let $G$ be a group and $a\in G$. Let $C(a)=\{g\in G: ga=ag\}$. Then $C(a)\leq G$. $C(a)$ is called the centralizer of $a$ in $G$.

Example. Let $G$ be a group and let $Z(G)=\{z\in G: zx=xz\ \forall x\in G\}$. Then $Z(G)$ is a subgroup of $G$, called the center of $G$.

Let $G$ be a group and $H\leq G$. $\forall a\in G$, $a^{-1}Ha=\{a^{-1}ha: h\in H\}$ is also a subgroup of $G$.

Lemma. Suppose that $(G,\cdot)$ is a group and $H$ is a finite nonempty subset of $H$. If $H$ is closed under $\cdot$, then $H$ is a subgroup of $G$.

Proof. Let $H=\{a_1,a_2,\cdots,a_n\}$. Then $\forall a\in H$, $aH=\{aa_1,aa_2,\cdots,aa_n\}\subset H$. On the other hand, if $aa_i=aa_j$ then $a_i=a_j$. So, $|aH|=|H|$. This implies that $aH=H$ and hence
\begin{align*}
a\in aH &\Longrightarrow a=aa_i\ \mbox{for some}\ i\\
&\Longrightarrow a_i=e\in H.
\end{align*}
Since $e\in aH$, $e=aa_j$ for some $j$ $\Longrightarrow$ $a_j=a^{-1}$.

Example. The symmetric group $S_3=\{1,(123),(132),(23),(13),(12)\}$ has 5 subgroups
$\{1\}$, $\{1,(12)\}$, $\{1,(13)\}$, $\{1,(23)\}$, and $A_3=\{1,(123),(132)\}$. $A_3$ is called alternating group of degree 3. Cycles of length 2 such as (12), (13), (23) are called transpositions. Any permutation can be written as a product of either an even number of transpositions or an odd number of transpositions. If a permutation is a product of an even number of transpositions, the permutation is called an even permutation. If a permutation is a product of an odd number of transpositions, the permutation is called an odd permutation. The identity permutation 1 is an even permutation as $\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}$ can be written as (12)(21)(23)(32)(31)(13). The permutation (123) can be written as (12)(13). So, (123) is an even permutation. Similarly (132) is an even permutation as well. So it turns out that the alternating group $A_3$ is the set of all even permutations. In general, the set $A_n$ of all even permutations of $\{1,2,3,\cdots,n\}$ form a subgroup of the symmetric group $S_n$. Remember that $S_n$ has order $n!$. Since there are exactly the same number of even permutations and odd permutations, the alternating group $A_n$ of degree $n$ has order $\frac{n!}{2}$.

In this lecture, we study subgroups. A nonempty subset $H$ of a group $G$ is called a subgroup of $G$ if $H$ itself forms a group relative to the operation $\cdot$ in $G$. If $H$ is a subgroup of $G$, we simply write $H\leq G$. Clearly $G\leq G$ and $\{e\}\leq G$. $G$ and $\{e\}$ are called trivial subgroups of $G$. Before we discuss subgroups further we need to go over some basic properties of a group as we need them.

Lemma. If $G$ is a group, then:

(a) Its identity element is unique.

(b) Each $a\in G$ has a unique inverse $a^{-1}\in G$.

(c) $\forall a\in G$, $(a^{-1})^{-1}=a$.

(d) $\forall a,b\in G$, $(ab)^{-1}=b^{-1}a^{-1}$.

The proof of this lemma is pretty much straightforward and is left to readers.

In order to show that a nonempty subset $H$ of a group $G$ is a subgroup we need to check:

1. $H$ is closed under $\cdot$, the operation in $G$. That is, $\forall a,b\in H$, $ab\in H$.

2. $e\in H$.

3. $\forall a\in H$, $a^{-1}\in H$.

Note that the associative law holds automatically. It turns out that there is a simpler criterion to check if a nonempty subset is a subgroup of a group.

Lemma. A nonempty subset $H\subset G$ is a subgroup of $G$ if and only of $\forall a,b\in H$, $ab^{-1}\in H$.

Proof. ($\Longrightarrow$) Clear.

($\Longleftarrow$) Let $a,b\in H$. Then by assumption, $aa^{-1}=e\in H$. Since $a,e\in H$, $ea^{-1}=a^{-1}\in H$. Since $b^{-1}\in H$, $a(b^{-1})^{-1}=ab\in H$. Therefore, $H$ is a subgroup of $G$.

Example. $\forall n\in\mathbb{N}\cup\{0\}$, $n\mathbb{Z}\leq(\mathbb{Z},+)$. Here, $n\mathbb{Z}=\{nx: x\in\mathbb{Z}\}$. In fact, they are all the subgroups of $(\mathbb{Z},+)$.

Definition. The cyclic subgroup of $G$ generated by $a\in G$ is $\{a^k: k\in\mathbb{Z}\}$. It is denoted by $\langle a\rangle$.

Example. Let $G$ be a group and $a\in G$. Let $C(a)=\{g\in G: ga=ag\}$. Then $C(a)\leq G$. $C(a)$ is called the centralizer of $a$ in $G$.

Example. Let $G$ be a group and let $Z(G)=\{z\in G: zx=xz\ \forall x\in G\}$. Then $Z(G)$ is a subgroup of $G$, called the center of $G$.

Let $G$ be a group and $H\leq G$. $\forall a\in G$, $a^{-1}Ha=\{a^{-1}ha: h\in H\}$ is also a subgroup of $G$.

Lemma. Suppose that $(G,\cdot)$ is a group and $H$ is a finite nonempty subset of $H$. If $H$ is closed under $\cdot$, then $H$ is a subgroup of $G$.

Proof. Let $H=\{a_1,a_2,\cdots,a_n\}$. Then $\forall a\in H$, $aH=\{aa_1,aa_2,\cdots,aa_n\}\subset H$. On the other hand, if $aa_i=aa_j$ then $a_i=a_j$. So, $|aH|=|H|$. This implies that $aH=H$ and hence
\begin{align*}
a\in aH &\Longrightarrow a=aa_i\ \mbox{for some}\ i\\
&\Longrightarrow a_i=e\in H.
\end{align*}
Since $e\in aH$, $e=aa_j$ for some $j$ $\Longrightarrow$ $a_j=a^{-1}$.

Example. The symmetric group $S_3=\{1,(123),(132),(23),(13),(12)\}$ has 5 subgroups
$\{1\}$, $\{1,(12)\}$, $\{1,(13)\}$, $\{1,(23)\}$, and $A_3=\{1,(123),(132)\}$. $A_3$ is called alternating group of degree 3. Cycles of length 2 such as (12), (13), (23) are called transpositions. Any permutation can be written as a product of either an even number of transpositions or an odd number of transpositions. If a permutation is a product of an even number of transpositions, the permutation is called an even permutation. If a permutation is a product of an odd number of transpositions, the permutation is called an odd permutation. The identity permutation 1 is an even permutation as $\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}$ can be written as (12)(21)(23)(32)(31)(13). The permutation (123) can be written as (12)(13). So, (123) is an even permutation. Similarly (132) is an even permutation as well. So it turns out that the alternating group $A_3$ is the set of all even permutations. In general, the set $A_n$ of all even permutations of $\{1,2,3,\cdots,n\}$ form a subgroup of the symmetric group $S_n$. Remember that $S_n$ has order $n!$. Since there are exactly the same number of even permutations and odd permutations, the alternating group $A_n$ of degree $n$ has order $\frac{n!}{2}$.

Example. $\mathrm{SL}(n,\mathbb{R})=\{A\in\mathrm{GL}(n,\mathbb{R}): \det A=1\}$ is a subgroup of the general linear group $\mathrm{GL}(n,\mathbb{R})$ of degree $n$. $\mathrm{SL}(n,\mathbb{R})$ is called the special linear group of degree $n$. The general linear group $\mathrm{GL}(n,\mathbb{R})$ is the group of isometries of $\mathbb{R}^n$. An isometry of $\mathbb{R}^n$ is a linear bijective map from $\mathbb{R}^n$ onto itself which preserves the inner product. What this means is that if $T: \mathbb{R}^n\longrightarrow\mathbb{R}^n$ is an isometry then for any two vectors $v,w\in\mathbb{R}^n$, $\langle Tv,Tw\rangle=\langle v,w\rangle$. The special linear group $\mathrm{SL}(n,\mathbb{R})$ is the group of all orientation preserving isometries of $\mathbb{R}^n$.

# Functional Analysis 4: Convergence, Cauchy Sequence, Completeness

The set $\mathbb{Q}$ of rational numbers is not complete (or not a continuum) since it has gaps or holes. For instance, $\sqrt{2}$ is not in $\mathbb{Q}$. On the other hand, the set $\mathbb{R}$ of real numbers has no gaps or holes, so it is complete (or is a continuum). Let $(x_n)$ be a sequence of real numbers. Suppose that $(x_n)$ converges to a real number $x$. Then by the triangle inequality, for any $m,n\in\mathbb{N}$, we have
$$|x_m-x_n|\leq |x_m-x|+|x-x_n|.$$
Hence, $\displaystyle\lim_{m,n\to\infty}|x_m-x_n|=0$, i.e. $(x_n)$ is a Cauchy sequence. Conversely, Georg Cantor introduced the completeness axiom that every Cauchy sequence of real numbers converges and defined a real number as the limit of a Cauchy sequence of rational numbers. For instance, consider the Cauchy sequence $(x_n)$ defined by
$$x_1=1,\ x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n},\ \forall n\geq 2.$$
If $(x_n)$ converges to a number $x$, it would satisfy $x^2=2$ i.e. $(x_n)$ converges to $\sqrt{2}$. There is another way to obtain the completeness of $\mathbb{R}$ by a Dedekind cut, though we are not going to delve into that here.

More generally, one can also consider a complete metric space and that is what we are going to study in this lecture.

Definition. A sequence $(x_n)$ is a metric space $(X,d)$ is said to converge or to be convergent to $x\in X$ if
$$\lim_{n\to\infty}d(x_n,x)=0.$$
$x$ is called the limit if $(x_n)$ and we write
$$\lim_{n\to\infty}x_n=x\ \mbox{or}\ x_n\rightarrow x.$$
If $(x_n)$ is not convergent, it is sad to be divergent. We can generalize the definiton of the convergence of a sequence we learned in calculus in terms of a metric as:

Definition. $\displaystyle\lim_{n\to\infty}d(x_n,x)=0$ if and only if given $\epsilon>0$ $\exists$ a positive integer $N$ s.t. $x_n\in B(x,\epsilon)$ $\forall n\geq N$.

A nonempty subset $M\subset X$ is said to be bounded if
$$\delta(M)=\sup_{x,y\in M}d(x,y)<\infty.$$

Lemma. Let $(X,d)$ be a metric space.

(a) A convergent sequence in $X$ is bounded and its limit is unique.

(b) If $x_n\rightarrow x$ and $y_n\rightarrow y$, then $d(x_n,y_n)\rightarrow d(x,y)$.

Proof. (a) Suppose that $x_n\rightarrow x$. Then one can find a positive integer $N$ such that $d(x_n,x)<1$ $\forall n\geq N$. Let $M=2\max\{d(x_1,x),\cdots,d(x_{N-1},x),1\}$. Then for all $m,n\in\mathbb{N}$,
\begin{align*}
d(x_m,x_n)&\leq d(x_m,x)+d(x,x_n)\ (\mbox{ (M3) triangle inequality)}\\
&\leq M.
\end{align*}
This means that $\delta((x_n))\leq M<\infty$ i.e. $(x_n)$ is bounded.

Suppose that $x_n\rightarrow x$ and $x_n\rightarrow y$. Then
\begin{align*}
0\leq d(x,y)&\leq d(x,x_n)+d(x_ny)\\
&\rightarrow 0
\end{align*}
as $n\to\infty$. So, $d(x,y)=0\Rightarrow x=y$ by (M1).

(b) By (M3),
$$d(x_n,y_n)\leq d(x_n,x)+d(x,y)+d(y,y_n)$$
and so we obtain
$$d(x_n,y_n)-d(x,y)\leq d(x_n)+d(y,y_n).$$
Similarly, we also obtain the inequality
$$d(x,y)-d(x_n,y_n)\leq d(x,x_n)+d(y_n,y).$$
Hence,
$$0\leq |d(x_n,y_n)-d(x,y)|\leq d(x_n,x)+d(y_n,y)\rightarrow 0$$
as $n\to\infty$.

Definition. A sequence $(x_n)\subset (X,d)$ is said to be Cauchy if given $\epsilon>0$ $\exists$ a positive integer $N$ such that
$$d(x_m,x_n)<\epsilon\ \forall m,n\geq N.$$
The space $X$ is said to be complete if every Cauchy sequence in $X$ converges.

Examples. The real line $\mathbb{R}$ and the complex plane $\mathbb{C}$ are complete.

Theorem. Every convergent sequence is Cauchy.

Proof. Suppose that $x_n\rightarrow x$. Then given $\epsilon>0$ $\exists$ a poksitive integer $N$ s.t. $d(x_n,x)<\frac{\epsilon}{2}$ for all $n\geq N$. Now, $\forall m,n\geq N$
$$d(x_m,x_n)\leq d(x_m,x)+d(x,x_n)<\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$$
Therefore, $(x_n)$ is Cauchy.

Theorem. Let $M$ be a nonempty subset of a metric space $(X,d)$. Then

(a) $x\in\bar M\Longleftrightarrow \exists$ a seqence $(x_n)\subset M$ such that $x_n\rightarrow x$.

(b) $M$ is closed $\Longleftrightarrow$ given a sequence $(x_n)\subset M$, $x_n\rightarrow x$ implies $x\in M$.

Proof. (a) ($\Longrightarrow$) Since $x\in\bar M$, $\forall n\in\mathbb{N}$ $\exists x_n\in B\left(x,\frac{1}{n}\right)\cap M\ne\emptyset$. Let $\epsilon>0$ be given. Then by the Archimedean property, $\exists$ a positive integer $N$ s.t. $N\geq\frac{1}{\epsilon}$. Now,
$$n\geq N\Longrightarrow d(x_n,x)<\frac{1}{n}\leq\frac{1}{N}<\epsilon.$$

($\Longleftarrow$) Suppose that $\exists$ a sequence $(x_n)\subset M$ s.t. $x_n\rightarrow x$. Then given $\epsilon>0$ $\exists$ a positive integer $N$ s.t. $x_n\in B(x,\epsilon)$ $\forall n\geq N$. This means that $\forall\epsilon>0$, $B(x,\epsilon)\cap M\ne\emptyset$. So, $x\in\bar M$.

(b) ($\Longrightarrow$) Clear

($\Longleftarrow$) It suffices to show that $\bar M\subset M$. Let $x\in\bar M$. Then $\exists$ a sequence $(x_n)\subset M$ such that $x_n\rightarrow x$. By assumption, $x\in M$.
Theorem. A subspace $M$ of a complete metric space $X$ itself is complete if and only if $M$ is closed in $X$.

Proof. ($\Longrightarrow$) Let $M\subset X$ be complete. Let $(x_n)$ be a sequence in $M$ such that $x_n\rightarrow x$. Then $(x_n)$ is Cauchy. Since $M$ is complete, every Cauchy sequence must converge and hence $x\in M$. This means that $M$ is closed.

($\Longleftarrow$) Suppose that $M\subset X$ is closed. Let $(x_n)$ be a Cauchy sequence in $M\subset X$. Since $X$ is complete, $\exists x\in X$ such that $x_n\rightarrow x$. Since $M$ is closed, $x\in M$. Therefore, $M$ is complete.

Theorem. A mapping $T: X\longrightarrow Y$ is continuous at $x_0\in X$ if and only if $x_n\rightarrow x$ implies $Tx_n\rightarrow Tx_0$.

Proof. ($\Longrightarrow$) Suppose that $T$ is continuous and $x_n\rightarrow x$ in $X$. Let $\epsilon>0$ be given. Then $\exists\delta>0$ s.t. whenever $d(x,x_0)<\delta$, $d(Tx,Tx_0)<\epsilon$. Since $x_n\rightarrow x$, $\exists$ a positive integer $N$ s.t. $d(x_n,x_0)<\delta$ $\forall n\geq N$. So, $\forall n\geq N$, $d(Tx_n,Tx_0)<\epsilon$. Hence, $Tx_n\rightarrow Tx_0$.

($\Longleftarrow$) Suppose that $T$ is not continuous. Then $\exists\epsilon>0$ s.t. $\forall\delta>0$, $\exists x\ne x_0$ satisfying $d(x,x_0)<\delta$ but $d(Tx,tx_0)\geq\epsilon$. So, $\forall n=1,2,\cdots$, $\exists x_n\ne x_0$ satisfying $d(x_n,x_0)<\frac{1}{n}$ but $d(Tx_n,Tx_0)\geq\epsilon$.

# Group Theory 4: Examples of Groups

In the first lecture here, we defined a group. We have also seen an example of a group here, which is a symmetric group. In this lecture, we study some well-known examples of groups of finite and infinite orders. Recall that the order of a group os the number of elements in the group.

Examples of Groups

1. $(\mathbb{Z},+)$, $(\mathbb{Q},+)$, $(\mathbb{R},+)$, and $(\mathbb{C},+)$ are abelian groups of infinite order.
2. $(\mathbb{Q}\setminus\{0\},\cdot)$ is an abelian group of infinite order.
3. $(\mathbb{R}^+,\cdot)$ is an abelian group of infinite order. Here $\mathbb{R}^+$ denotes the set of all positive real numbers.
4. Let $E_n=\{e^{\frac{2k\pi i}{n}}: k=0,1,2,\cdots,n-1\}$. $e^{\frac{2k\pi i}{n}}$, $k=0,1,2,\cdots,n-1$ are the $n$-th roots of unity i.e. the zeros of $z^n=1$. $E_n$ forms an abelian group of order $n$. It is generated by a single element $e^{\frac{2\pi i}{n}}$. Such a group is called a cyclic group.

Definition. A group $G$ is said to be a finite group if it has a finite number of elements. The number of elements in $G$ is called the order of $G$ as mentioned previously and it is denoted by $|G|$ or $\mathrm{ord}(G)$. We use the notation $|G|$ for the order of the group $G$.

Example.Let $\mathbb{Z}_n=\{0,1,2,\cdots,n-1\}$. $\mathbb{Z}_n$ is the set of all possible remainders when an integer is divided by 2. The addition $+$ on $\mathbb{Z}_n$ is defined naturally as follows.
\begin{aligned} \mathbb{Z}_2\\ \begin{array}{|c||c|c|} \hline + & 0 & 1\\ \hline \hline 0 & 0 & 1\\ \hline 1 & 1 & 0\\ \hline \end{array} \end{aligned}
\begin{aligned} \mathbb{Z}_3\\ \begin{array}{|c||c|c|c|} \hline + & 0 & 1 & 2\\ \hline \hline 0 & 0 & 1 & 2\\ \hline 1 & 1 & 2 & 0\\ \hline 2 & 0 & 1 & 2\\ \hline \end{array} \end{aligned}
$(\mathbb{Z}_n,+)$ is an abelian group of order $n$. We will see later that the group $E_n$ and $\mathbb{Z}_n$ are indeed the same group.

Example. The set $M_{m\times n}(\mathbb{R})$ of all $m\times n$ matrices of real entries under matrix addition is an abelian group of infinite order.

Example. The set $\mathrm{GL}(n,\mathbb{R})$ of alll $n\times n$ non-singular matrices of real entries under matrix multiplication is a non-abelian group of infinite order. $\mathrm{GL}(n,\mathbb{R})$ is called the general linear group of degree $n$. It can be viewed as the set of all invertible linear transformations $T: \mathbb{R}^n\longrightarrow\mathbb{R}^n$ that preserve the standard Euclidean inner product. A map $T: \mathbb{R}^n\longrightarrow\mathbb{R}^n$ is said to be an isometry if it is a linear isomorphism (i.e linear, one-to-one and onto, but remember from linear algebra that a linear map $T: \mathbb{R}^n\longrightarrow\mathbb{R}^n$ is one-to-one, it is also onto) and it preserves inner product i.e. for any vectors $v$ and $w$ in $\mathbb{R}$, $\langle Tv,Tw\rangle=\langle v,w\rangle$.

Example. [Klein four-group (Vierergruppe in German)]

Klein four-group

Let $V=\{e,a,b,c\}$ where $a$ is counterclockwise rotation of the rectangle in the picture about the $x$-axis by $180^\circ$, $b$ is counterclockwise rotation of the rectangle about the $y$-axis by $180^\circ$ and $c$ is counterclockwise rotation of the rectangle about the $z$-axis (the axis coming out of the origin toward you) by $180^\circ$. Then $a$, $b$ and $c$ satisfy the following relationship
\begin{align*}
a^2=b^2=c^2=e,\ ab&=ba=c,\ bc=cb=a,\\
ca&=ac=b.
\end{align*}
Here, $\cdot$ is the function composition i.e. successive application of rotations. By labling the vertices of the rectangle as 1, 2, 3, 4 as seen in the picture, we can define each rotation as a permutation of $\{1,2,3,4\}$.
\begin{align*}
e&=\begin{pmatrix}
1 & 2 & 3 & 4\\
1 & 2 & 3 & 4
\end{pmatrix},\ a=\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 1 & 4 &3
\end{pmatrix},\\
b&=\begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix},\ c=\begin{pmatrix}
1 & 2 & 3 & 4\\
3 & 4 & 1 &2
\end{pmatrix}.
\end{align*}
For instance, we calculate $ab$:
\begin{align*}
ab&=\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 1 & 4 &3
\end{pmatrix}\begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 1 & 4 &3
\end{pmatrix}\begin{pmatrix}
4 & 3 & 2 & 1\\
3 & 4 & 1 & 2
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 2 & 3 & 4\\
3 & 4 & 1 &2
\end{pmatrix}\\
&=c.
\end{align*}

Example. [The $n$-th dihedral group $D_n$, $n\geq 3$]

Consider an equilateral triangle shown in the following picture.

Dihedral group D3

$\rho$ is counterclockwise rotation about the axis coming out of the origin by $\frac{360^\circ}{3}=120^\circ$ and $\mu_i$, $i=1,2,3$ is counterclockwise rotation about the axis of rotation through each vertex $i$ by $180^\circ$. As permutations of the vertices $\{1,2,3\}$, $\rho$ and $\mu_i$ , $i=1,2,3$ are given by
\begin{align*}
\rho&=\begin{pmatrix}
1 & 2 & 3\\
2 & 3 & 1
\end{pmatrix},\ \mu_1=\begin{pmatrix}
1 & 2 & 3\\
1 & 3 & 2
\end{pmatrix}\\
\mu_2&=\begin{pmatrix}
1 & 2 & 3\\
3 & 2 & 1
\end{pmatrix},\ \mu_3=\begin{pmatrix}
1 & 2 & 3\\
2 & 1 &3
\end{pmatrix}.
\end{align*}
$D_3=\{e,\rho,\rho^2,\mu_1,\mu_2,\mu_3\}$ is a group called the 3rd dihedral group. $$\mu_1\mu_2=\rho^2\ne\rho=\mu_2\mu_1.$$
So, we see that $D_3$ is not an abelian group. $D_3$ is the group of symmetries of an equilateral triangle.

Now this time let us consider a square as shown in the following picture.

Dihedral group D4

$\rho$ is counterclockwise rotation about the $z$-axis coming out of the origin by $\frac{360^\circ}{4}=90^\circ$. $\mu_i$, $i=1,2$ are counterclockwise rotations about $y$-axis and $x$-axis, respectively by $180^\circ$. $\delta_i$, $i=1,2$ are counterclockwise rotations about the axis through the vertices 2 and 4 and the vertices through 1 and 3, respectively by $180^\circ$. As permutations of the vertices $\{1,2,3,4\}$, $\rho$, $\mu_i$ and $\delta_i$, $i=1,2$ are given by
\begin{align*}
\rho&=\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{pmatrix},\\
\mu_1&=\begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 1 & 4 & 3
\end{pmatrix},\ \mu_2=\begin{pmatrix}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{pmatrix},\\
\delta_1&=\begin{pmatrix}
1 & 2 & 3 & 4\\
3 & 2 & 1 & 4
\end{pmatrix},\ \delta_2=\begin{pmatrix}
1 & 2 & 3 & 4\\
1 & 4 & 3 & 2
\end{pmatrix}.
\end{align*}
$D_4=\{e,\rho,\rho^2,\rho^3,\mu_1,\mu_2,\delta_1,\delta_2\}$ is the group of symmetries of a square, called the 4th dihedral group. It is also called the octic group. Note that $|D_n|=2n$, $n\geq 3$.

# Functional Analysis 3: Basic (Metric) Topology

Let $(X,d)$ be a metric space.

Definition. A subset $U\subset X$ is said to be open if $\forall x\in U$ $\exists\epsilon>0$ s.t. $B(x,\epsilon)\subset U$.

If $U\subset X$ is open then $U$ can be expressed as union of open balls $B(x,\epsilon)$. Hence, the set of all open balls in $X$, $\mathcal{B}=\{B(x,\epsilon): x\in X,\ \epsilon>0\}$ form a basis for a topology (a metric topology, the topology induced by the metric $d$) on $X$. Those who have not studied topology before may simply understand it as the set of all open sets in $X$.

Definition. A subset $F\subset X$ is said to be closed if its complement, $F^c=X\setminus F$ is open in $X$.

The following is the definition of a continuous function that you are familiar with from calculus. The definition is written in terms of metrics.

Definition. Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces. A mapping $T:X\longrightarrow Y$ is said to be continuous at $x_0\in X$ if $\forall\epsilon>0$ $\exists\delta>0$ s.t $d_Y(Tx,Tx_0)<\epsilon$ whenever $d_X(x,x_0)<\delta$.

$T$ is said to be continuous if it is continuous at every point of $X$.

The above definition can be generalized in terms of open sets as follows.

Theorem. A mapping $T: (X,d_X)\longrightarrow(Y,d_Y)$ is continuous if and only if $\forall$ open set $U$ in $Y$, $T^{-1}U$ is open in $X$.

Proof. (Only if, $\Rightarrow$) Suppose that $T:X\longrightarrow Y$ is continuous. Let $U$ be open in $Y$. Then we show that $T^{-1}U$ is open in $X$. Let $x_0\in T^{-1}U$. Then $Tx_0\in U$. Since $U$ is open in $Y$, $\exists\epsilon>0$ s.t. $B(Tx_0,\epsilon)\subset U$. By the continuity of $T$, for this $\epsilon>0$ $\exists\delta>0$ s.t. whenever $d(x,x_0)<\delta$, $d(Tx,Tx_0)<\epsilon$. This means that
$$TB(x_0,\delta)\subset B(Tx_0,\epsilon)\subset U\Longrightarrow B(x_0,\delta)\subset T^{-1}(TB(x_0,\delta))\subset T^{-1}U.$$ Hence, $T^{-1}U$ is open in $X$.

(If, $\Leftarrow$) Suppose that $\forall$ open set $U$ in $Y$, $T^{-1}U$ is open in $X$. We show that $T$ is continuous. Let $x_0\in X$ and let $\epsilon>0$ be given. Then $B(Tx_0,\epsilon)$ is open in $Y$. So by the assumption, $x_0\in T^{-1}B(Tx_0,\epsilon)$ is open in $X$. This means that $\exists\delta>0$ s.t.
$$B(x_0,\delta)\subset T^{-1}B(Tx_0,\epsilon)\Longrightarrow TB(x_0,\delta)\subset T(T^{-1}B(Tx_0,\epsilon))\subset B(Tx_0,\epsilon).$$ This is equivalent to saying that $\exists\delta>0$ s.t. whenever $d(x,x_0)<\delta$, $d(Tx,Tx_0)<\epsilon$. That is, $T$ is continuous at $x_0$. Since the choice $x_0\in X$ was arbitrary, the proof is complete.

Let $A\subset X$. $x\in X$ is called an accumulation point or a limit point of $A$ if $\forall$ open set $U(x)$ in $X$, $(U(x)-\{x\})\cap A\ne\emptyset$. Here the notation $U(x)$ means that it contains $x$. The set of all accumulation points of $A$ is denoted by $A’$ and is called the derived set of $A$. $\bar A:=A\cup A’$ is called the closure of $A$. $\bar A$ is the smallest closed set containing $A$.

Theorem. Let $A\subset X$. Then $x\in\bar A$ if and only if $\forall$ open set $U(x)$, $U(x)\cap A\ne\emptyset$.

Definition. $D\subset X$ is said to be dense if $\bar D=X$. This means that $\forall$ open set $U$ in $X$, $U\cap D\ne\emptyset$.

Definition. $X$ is said to be separable if it has a countable dense subset.

Examples. The real line $\mathbb{R}$ is separable. The complex plane $\mathbb{C}$ is also separable.

Theorem. The space $\ell^\infty$ is not separable.

Proof. Let $y=(\eta_1,\eta_2,\eta_3,\cdots)$ be a sequence of zeros and ones. Then $y\in\ell^\infty$. We can then associate $y$ with the binary representation
$$\hat y=\frac{\eta_1}{2}+\frac{\eta_2}{2^2}+\frac{\eta_3}{2^3}+\cdots\in [0,1].$$ Each $\hat y\in [0,1]$ has a binary representation and different $\hat y$’s have different binary representations. So, there are uncountably many sequences of zeros and ones. If $y$ and $z$ are sequences of zeros and ones and $y\ne z$, then $d(y,z)=1$. This means that for any two distinct sequences $y$ and $z$ of zeros and ones, $B\left(y,\frac{1}{3}\right)\cap B\left(z,\frac{1}{3}\right)=\emptyset$. Let $A$ be a dense subset of $\ell^\infty$. Then for each sequence $y$ of zeros and ones, $B\left(y,\frac{1}{3}\right)$ has at least one element of $A$. This means that $A$ cannot be countable.

Theorem. The space $\ell^p$ with $1\leq p<\infty$ is separable.

Proof. Let $A$ be the set of all sequences $y$ of the form
$$y=(\eta_1,\eta_2,\cdots,\eta_n,0,0,\cdots,0),$$ where $n$ is a positive integer and the $\eta_j$’s are rational. For each $n=1,2,\cdots$, the number of sequences of the form $y=(\eta_1,\eta_2,\cdots,\eta_n,0,0,\cdots,0)$ is the same as the number of functions from $\{1,2,3,\cdots,n\}$ to $\mathbb{Q}$, the set of all rational numbers. $\mathbb{Q}$ has the cardinality $\aleph_0$ and so the number is $\aleph_0^n=\aleph_0$. The cardinality of $A$ is then $\aleph_0\cdot\aleph_0=\aleph_0$ i.e. $A$ is countable. Now we show that $A$ is dense in $\ell^p$. Let $x=(\xi_j)\in\ell^p$. Let $\epsilon>0$ be given. Since $\displaystyle\sum_{j=1}^\infty|\xi_j|^p<\infty$, $\exists$ a positive integer $N$ s.t. $\displaystyle\sum_{j=N+1}^\infty|\xi_j|^p<\frac{\epsilon^p}{2}$. Since rationals are dense in $\mathbb{R}$, one can find $y=(\eta_1,\eta_2,\cdots,\eta_N,0,0,\cdots)\in A$ s.t. $\displaystyle\sum_{j=1}^N|\xi_j-\eta_j|^p<\frac{\epsilon^p}{2}$. Hence,
$$[d(x,y)]^p=\sum_{j=1}^N|\xi_j-\eta_j|^p+\sum_{j=N+1}^\infty|\xi_j|^p<\epsilon^p,$$
i.e. $d(x,y)<\epsilon$. This means that $y\in B(x,\epsilon)\cap A\ne\emptyset$. This completes the proof.

# Group Theory 3: Preliminaries (Basic Number Theory)

In this lecture, we study some basic number theory as it is needed to study group theory.

Let $\mathbb{Z}$ denote the set of integers. $\mathbb{Z}$ satisfies well-ordering principle, namely any non-empty set of nonnegative integers has a smallest member.

One of the most fundamental theorems regarding numbers is Euclid’s Algorithm. Although we will not discuss its proof, it can be proved using well-ordering principle.

Theorem. [Euclid's Algorithm] If $m$ and $n$ are integers with $n>0$, then $\exists$ integers $q$ and $r$ with $0\leq r<n$ such that $m=qn+r$.

Euclid’s algorithm hints us how we can define the notion that one integer divides another.

Definition. Given $m\ne 0, n\in\mathbb{Z}$, we say $m$ divides $n$ and write $m|n$ if $n=cm$ for some $c\in\mathbb{Z}$.

Examples. $2|14$, $(-7)|14$, $4|(-16)$.

If $m|n$, we call $m$ a divisor or a factor of $n$, and $n$ a multiple of $m$. To indicate $m$ is not a divisor of $n$, we write $m\not|n$. For example, $3\not|5$.

Lemma. The following properties hold.

(a) $1|n$ $\forall n$.

(b) If $m\ne 0$ then $m|0$.

(c) If $m|n$ and $n|q$, then $m|q$.

(d) If $m|n$ and $m|q$ then $m|(\mu n+\nu q)$ $\forall \mu,\nu$.

(e) If $m|1$ then $m=\pm 1$.

(f) If $m|n$ and $n|m$ then $m=\pm n$.

Definition. Given $a,b$ (not both 0), their greatest common divisor (in short gcd) $c$ is defined by the following properties:

(a) $c>0$

(b) $c|a$ and $c|b$

(c) If $d|a$ and $d|b$ then $d|c$.

If $c$ is the gcd of $a$ and $b$, we write $c=(a,b)$.

$(24,9)=3$. Note that the gcd 3 can be written in terms of 24 and 9 as $3\cdot 9+1\cdot (-24)$ or $(-5)9+2\cdot 24$. In general, we have the following theorem holds.

Theorem. If $a,b$ are not both 0, their gcd exists uniquely. Moreover, $\exists m,n\in\mathbb{Z}$ s.t. $c=ma+nb$.

Now let us talk about how to find the gcd of two positive numbers $a$ and $b$. W.L.O.G. (Without Loss Of Generality), we may assume that $b<a$. Then by Euclid’s algorithm we have
$$a=bq+r,\ \mbox{where}\ 0\leq r<b.$$
Let $c=(a,b)$. Then $c|r$, so $c$ is a common divisor of $b$ and $r$. If $d$ is a common divisor of $b$ and $r$, it is also a common divisor of $a$ and $b$. This implies that $d\leq c$ and so $c=(b,r)$. Finding $(b,r)$ is of course easier because one of the numbers is smaller than before.

Example. [Finding GCD]
\begin{aligned} (100,28)&=(28,16)\ &(100&=28\cdot 3+16)\\ &=(16,12)\ &(28&=16\cdot 1+12)\\ &=(12,4)\ &(16&=12\cdot 1+14)\\ &=4. \end{aligned}
By working backward, we can also find integers $m$ and $n$ such that
$$4=m\cdot 100+n\cdot 28.$$
\begin{align*}
4&=16+12(-1)\\
&=16+(-1)[28+(-1)16]\\
&=(-1)28+2\cdot 16\\
&=(-1)28+2[100+(-3)28]\\
&=2\cdot 100+(-7)28.
\end{align*}
Therefore, $m=2$ and $n=-7$.

Definition. We say that $a$ and $b$ are relatively prime if $(a,b)=1$.

Theorem. The integers $a$ and $b$ are relatively prime if and only if $1=ma+nb$ for some $m$ and $n$.

Theorem. If $(a,b)=1$ and $a|bc$ then $a|c$.

Theorem. If $b$ and $c$ are both relatively prime to $a$, then $bc$ is also relatively prime to $a$.

Definition. A prime number, or shortly prime, is an integer $p>1$ such that $\forall a\in\mathbb{Z}$, either $p|a$ or $(p,a)=1$.

Suppose that $p$ is a prime as defined above and $p=ab$, where $1\leq a<p$. Then $p\not|a$ since $a<p$, so $(p,a)=1$. This implies that $p|b$. On the other hand, $b|p(=ab)$ and hence $p=b$ and $a=1$. So, the above definition coincides with the definition of a prime we are familiar with.

Theorem. If $p$ is a prime and $p|a_1a_2\cdots a_n$, then $p|a_i$ for some $i$ with $1\leq i\leq n$.

Proof. If $p|a_1$, we are done. If not, $(p,a_1)=1$ and so $p|a_2a_3\cdots a_n$. Continuing this, we see that $p|a_i$ for some $i$.

Regarding primes, we have the following theorems.

Theorem. If $n>1$, then either $n$ is a prime or the product of primes.

Theorem. [Unique Factorization Theorem] Given $n>1$, there is a unique way to write $n$ in the form $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_1<p_2<\cdots<p_k$ are primes and the exponents $a_1,\cdots,a_k$ are all positive.

Theorem. [Euclid] There is an infinite number of primes.

# Functional Analysis 2: $\ell^p$ and $L^p$ as Metric Spaces

Let $p\geq 1$ be a fixed number and let
$$\ell^p=\left\{x=(\xi_j): \sum_{j=1}^\infty|\xi_j|^p<\infty\right\}.$$
Define $d:\ell^p\times\ell^p\longrightarrow\mathbb{R}^+\cup\{0\}$ by
$$d(x,y)=\left(\sum_{j=1}^\infty|\xi_j-\eta_j|^p\right)^{\frac{1}{p}}.$$
Then $(\ell^p,d)$ is a metric space. The properties (M1) and (M2) are clearly satisfied. We prove the remaining property (M3) the triangle inequality. $p=1$ case can be easily shown by the triangle inequality of numbers. We need a few steps to do this. First we prove the following inequality: $\forall\alpha>0,\beta>0$,
$$\alpha\beta\leq\frac{\alpha^p}{p}+\frac{\beta^q}{q},$$
where $p>1$ and $\frac{1}{p}+\frac{1}{q}=1$. The numbers $p$ and $q$ are called conjugate exponenets. It follows from $\frac{1}{p}+\frac{1}{q}=1$ that $(p-1)(q-1)=1$ i.e. $\frac{1}{p-1}=q-1$. If we let $u=t^{p-1}$ then $t=u^{\frac{1}{p-1}}=u^{q-1}$. By comparing areas, we obtain
$$\alpha\beta\leq\int_0^{\alpha}t^{p-1}dt+\int_0^{\beta}u^{q-1}du=\frac{\alpha^p}{p}+\frac{\beta^q}{q}.$$
Next, using this inequality we prove the Hölder inequality
$$\sum_{j=1}^\infty|\xi_j\eta_j|\leq\left(\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}\left(\sum_{m=1}^\infty|\eta_m|^q\right)^{\frac{1}{q}}$$
where $p>1$ and $\frac{1}{p}+\frac{1}{q}=1$. When $p=2$ and $q=2$, we obtain the well-known Cauchy-Schwarz inequality.

Proof. Let $(\tilde\xi_j)$ and $(\tilde\eta_j)$ be two sequences such that
$$\sum_{j=1}^\infty|\tilde\xi_j|^p=1,\ \sum_{j=1}^\infty|\tilde\eta_j|^q=1.$$
Let $\alpha=|\tilde\xi_j|$ and $\beta=|\tilde\eta_j|$. Then by the inequality we proved previously,
$$|\tilde\xi_j\tilde\eta_j|\leq\frac{|\tilde\xi_j|^p}{p}+\frac{|\tilde\eta_j|^q}{q}$$
and so we obtain
$$\sum_{j=1}^\infty|\tilde\xi_j\tilde\eta_j|\leq\sum_{j=1}^\infty\frac{|\tilde\xi_j|^p}{p}+\sum_{j=1}^\infty\frac{|\tilde\eta_j|^q}{q}=1.$$
Now take any nonzero $x=(\xi_j)\in\ell^p$, $y=(\eta_j)\in\ell^q$. Setting
$$\tilde\xi_j=\frac{\xi_j}{\left(\displaystyle\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}},\ \tilde\eta_j=\frac{\eta_j}{\left(\displaystyle\sum_{m=1}^\infty|\eta_m|^q\right)^{\frac{1}{q}}}.$$
results the Hölder inequality.

Next, we prove the Minkowski inequality
$$\left(\sum_{j=1}^\infty|\xi_j+\eta_j|^p\right)^{\frac{1}{p}}\leq\left(\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}+\left(\sum_{m=1}^\infty|\eta_m|^p\right)^{\frac{1}{p}}$$
where $x=(\xi_j)\,y=(\eta_j)\in\ell^p$ and $p\geq 1$. $p=1$ case comes from the triangle inequality for numbers. Let $p>1$. Then
\begin{align*}
|\xi_j+\eta_j|^p&=|\xi_j+\eta_j||\xi_j|\eta_j|^{p-1}\\
&=(|\xi_j|+|\eta_j|)|\xi_j+\eta_j|^{p-1}\ (\mbox{triangle inequality for numbers}).
\end{align*}
For a fixed $n$, we have
$$\sum_{j=1}^n|\xi_j+\eta_j|^p\leq\sum_{j=1}^n|\xi_j||\xi_j+\eta_j|^{p-1}+\sum_{j=1}^n|\eta_j||\xi_j+\eta_j|^{p-1}.$$
Using the Hölder inequality, we get the following inequality
\begin{align*}
\sum_{j=1}^n|\xi_j||\xi_j+\eta_j|^{p-1}&\leq \sum_{j=1}^\infty |\xi_j||\xi_j+\eta_j|^{p-1}\\
&\leq\left(\sum_{k=1}^\infty |\xi_k|^p\right)^{\frac{1}{p}}\left(\sum_{m=1}^\infty(|\xi_m+\eta_m|^{p-1})^q\right)^{\frac{1}{q}}\ (\mbox{Hölder})\\
&=\left(\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}\left(\sum_{m=1}^\infty|\xi_m+\eta_m|^p\right)^{\frac{1}{q}}.
\end{align*}
Similarly we also get the inequality
$$\sum_{j=1}^n|\eta_j||\xi_j+\eta_j|^{p-1}\leq \left(\sum_{k=1}^\infty|\eta_k|^p\right)^{\frac{1}{p}}\left(\sum_{m=1}^\infty|\xi_m+\eta_m|^p\right)^{\frac{1}{q}}.$$
Combining these two inequalities, we get
$$\sum_{j=1}^n|\xi_j+\eta_j|^p\leq\left\{\left(\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}+\left(\sum_{k=1}^\infty|\eta_k|^p\right)^{\frac{1}{p}}\right\}\left(\sum_{m=1}^\infty|\xi_m+\eta_m|^p\right)^{\frac{1}{q}}$$
and by taking the limit $n\to \infty$ on the left hand side, we get
$$\sum_{j=1}^\infty|\xi_j+\eta_j|^p\leq\left\{\left(\sum_{k=1}^\infty|\xi_k|^p\right)^{\frac{1}{p}}+\left(\sum_{k=1}^\infty|\eta_k|^p\right)^{\frac{1}{p}}\right\}\left(\sum_{m=1}^\infty|\xi_m+\eta_m|^p\right)^{\frac{1}{q}}.$$
Finally dividing this inequality by $\displaystyle\left(\sum_{m=1}^\infty|\xi_m+\eta_m|^p\right)^{\frac{1}{q}}$ results the Minkowski inequality. The Minkowski inequality tells that
$$d(x,y)=\left(\sum_{j=1}^\infty|\xi_j-\eta_j|^p\right)^{\frac{1}{p}}<\infty$$
for $x,y\in\ell^p$. Let $x=(\xi_j), y=(\eta_j),\ z=(\zeta_j)\in\ell^p$. Then
\begin{align*}
d(x,y)&=\left(\sum_{j=1}^\infty|\xi_j-\eta_j|^p\right)^{\frac{1}{p}}\\
&\leq\left(\sum_{j=1}^\infty[|\xi_j-\zeta_j|+|\zeta_j-\eta_j|]^p\right)^{\frac{1}{p}}\\
&\leq\left(\sum_{j=1}^\infty|\xi_j-\zeta_j|^p\right)^{\frac{1}{p}}+\left(\sum_{j=1}^\infty|\zeta_j-\eta_j|^p\right)^{\frac{1}{p}}\\
&=d(x,z)+d(z,y).
\end{align*}

A measurable function $f$ on a closed interval $[a,b]$ is said to belong to $L^p$ if $\int_a^b|f(t)|^p dt<\infty$. $L^p$ is a vector space. For functions $f,g\in L^p$, we define
$$d(f,g)=\left\{\int_a^b|f(t)-g(t)|^pdt\right\}^{\frac{1}{p}}.$$
Then clearly (M2) symmetry is satisfied and one can also prove that (M3) triangle inequality holds. However, (M1) is not satisfied since what we have is that if $d(f,g)=0$ then $f=g$ a.e. (almost everywhere) i.e. the set $\{t\in[a,b]: f(t)\ne g(t)\}$ has measure $0$. It turns out that $=$ a.e. is an equivalence relation on $L^p$, so by considering $f\in L^p$ as its equivalence class $[f]$, $d$ can be defined as a metric on $L^p$ (actually the quotient space of $L^p$). Later, we will be particularly interested in the case when $p=2$ in which case $L^p$ as well as $\ell^p$ become Hilbert spaces. Those of you who want to know details about $L^p$ space are referred to

Real Analysis, H. L. Royden, 3rd Edition. Macmillan Publishing Company, 1988

# Group Theory 2: Preliminaries (Functions)

In my previous notes here, I mentioned some about logical symbols. The logical symbols I will use often are $\forall$ which means “for all”, “for any”, “for each”, or “for every” depending on the context, $\exists$ which means “there exists”, and $\ni$ which means “such that” (don’t be confused with $\in$ which means “be an element of”). We also use s.t. for “such that.” There are also $\Longrightarrow$ which means “implies” and $\Longleftrightarrow$ which means “if and only if.” I guess these pretty much cover what we use most of time.

Now lets review about functions in a more formal way. Let $X$ and $Y$ be two non-empty sets. The the Cartesian product $X\times Y$ of $X$ and $Y$ is defined as the set
$$X\times Y=\{(x,y): x\in X,\ y\in Y\}.$$
A subset $f$ of the Cartesian product $X\times Y$ (we write $f\subset X\times Y$) is called a graph from $X$ to $Y$. A graph $f\subset X\times Y$ is called a function from $X$ to $Y$ (we write $f: X\longrightarrow Y$) if whenever $(x,y_1),(x,y_2)\in f$, $y_1=y_2$. If $f: X\longrightarrow Y$ and $(x,y)\in f$, we also write $y=f(x)$. A function $f: X\longrightarrow Y$ is said to be one-to-one or injective if whenever $(x_1,y),(x_2,y)\in f$, $x_1=x_2$. This is equivalent to saying $f(x_1)=f(x_2)$ implies $x_1=x_2$. A function $f: X\longrightarrow Y$ is said to be onto or surjective if $\forall y\in Y$ $\exists x\in X$ s.t. $(x,y)\in f$. A function $f: X\longrightarrow Y$ is said to be one-to-one and onto (or bijective) if it is both one-to-one and onto (or both injective and surjective).

Let $f: X\longrightarrow Y$ and $g: Y\longrightarrow Z$ be two functions. Then the composition or the composite function $g\circ f: X\longrightarrow Z$ is defined by $g\circ f(x)=g(f(x))$ $\forall x\in X$. The function composition $\circ$ may be considered as an operation and it is associative.

Lemma. If $h: X\longleftrightarrow Y$, $g:Y\longleftrightarrow Z$ and $f:Z\longleftrightarrow W$, then $f\circ(g\circ h)=(f\circ g)\circ h$.

Note that $\circ$ is not commutative i.e. it is not necessarily true that $f\circ g=g\circ f$ even when both $f\circ g$ and $g\circ f$ are defined.

The following lemmas will be useful when we study group theory later.

Lemma. If both $f: X\longrightarrow Y$ and $g: Y\longrightarrow Z$ are one-to-one, so is $g\circ f: X\longrightarrow Z$.

Lemma. If both $f: X\longrightarrow Y$ and $g: Y\longrightarrow Z$ are onto, so is $g\circ f: X\longrightarrow Z$.

As an immediate consequence of combining these two lemmas, we obtain

Lemma. If both $f: X\longrightarrow Y$ and $g: Y\longrightarrow Z$ are bijective, so is $g\circ f: X\longrightarrow Z$.

If $f\subset X\times Y$, then the inverse graph $f^{-1}\subset Y\times X$ is defined by
$$f^{-1}=\{(y,x)\in Y\times X: (x,y)\in f\}.$$
If $f: X\longrightarrow Y$ is one-to-one and onto (bijective) then its inverse graph $f^{-1}$ is a function $f^{-1}: Y\longrightarrow X$. The inverse $f^{-1}$ is also one-to-one and onto.

Lemma. If $f: X\longrightarrow Y$ is a bijection, then $f\circ f^{-1}=\imath_Y$ and $f^{-1}\circ f=\imath_X$, where $\imath_X$ and $\imath_Y$ are the identity mappings of $X$ and $Y$, respectively.

Let $A(X)$ be the set of all one-to-one functions of $X$ onto $X$ itself. Then $(A(X),\circ)$ is a group. If $X$ is a finite set of $n$-elements (we may conveniently say $X=\{1,2,\cdots,n\})$, then $(A(X),\circ)$ is a finite group of order $n!$, called the symmetric group of degree $n$. The symmetric group of degree $n$ is denoted by $S_n$ and the elements of $S_n$ are called permutations.

# Analytic Continuation

The function $f(z)=\displaystyle\frac{1}{1+z}$ has an isolated singularity at $z=-1$. It has the Maclaurin series representation

$$f(z)=\sum_{n=0}^\infty(-1)^nz^n$$
for $|z|<1$. The power series $f_1(z)=\displaystyle\sum_{n=0}^\infty(-1)^nz^n$ converges only on the open unit disk $D_1:\ |z|<1$. For instance, the series diverges at $z=\frac{3}{2}i$ i.e. $f_1\left(\frac{3}{2}i\right)$ is not defined. The first 25 partial sums of the series $f_1\left(\frac{3}{2}i\right)$ are listed below and they do not appear to be approaching somewhere.

S[1] = 1.
S[2] = 1. – 1.500000000 I
S[3] = -1.250000000 – 1.500000000 I
S[4] = -1.250000000 + 1.875000000 I
S[5] = 3.812500000 + 1.875000000 I
S[6] = 3.812500000 – 5.718750000 I
S[7] = -7.578125000 – 5.718750000 I
S[8] = -7.578125000 + 11.36718750 I
S[9] = 18.05078125 + 11.36718750 I
S[10] = 18.05078125 – 27.07617188 I
S[11] = -39.61425781 – 27.07617188 I
S[12] = -39.61425781 + 59.42138672 I
S[13] = 90.13208008 + 59.42138672 I
S[14] = 90.13208008 – 135.1981201 I
S[15] = -201.7971802 – 135.1981201 I
S[16] = -201.7971802 + 302.6957703 I
S[17] = 455.0436554 + 302.6957703 I
S[18] = 455.0436554 – 682.5654831 I
S[19] = -1022.848225 – 682.5654831 I
S[20] = -1022.848225 + 1534.272337 I
S[21] = 2302.408505 + 1534.272337 I
S[22] = 2302.408505 – 3453.612758 I
S[23] = -5179.419137 – 3453.612758 I
S[24] = -5179.419137 + 7769.128706 I
S[25] = 11654.69306 + 7769.128706 I

Also shown below are the graphics of partial sums of the series $f_1\left(\frac{3}{2}i\right)$.

The first 10 partial sums

The first 20 partial sums

The first 30 partial sums

Let us expand $f(z)=\displaystyle\frac{1}{1+z}$ at $z=i$. Then we obtain
\begin{align*}
f(z)&=\frac{1}{1+z}\\
&=\frac{1}{1+i}\cdot\frac{1}{1+\frac{z-i}{1+i}}\\
&=\sum_{n=0}^\infty (-1)^n\frac{(z-i)^n}{(1+i)^{n+1}}
\end{align*}
for $|z-i|<\sqrt{2}$. Let $f_2(z)=\displaystyle\sum_{n=0}^\infty (-1)^n\frac{(z-i)^n}{(1+i)^{n+1}}$. This series converges only on the open disk $D_2:\ |z-i|<\sqrt{2}$, in particular at $z=\frac{3}{2}i$ and $f_2\left(\frac{3}{2}i\right)=f\left(\frac{3}{2}i\right)=\frac{4}{13}-\frac{6}{13}i$. The first 25 partial sums of the series $f_2\left(\frac{3}{2}i\right)$ are listed below and it appears that they are approaching a number. In fact, they are approaching the complex number $f\left(\frac{3}{2}i\right)=\frac{4}{13}-\frac{6}{13}i$.

S[1] = 0.5000000000 – 0.5000000000 I
S[2] = 0.2500000000 – 0.5000000000 I
S[3] = 0.3125000000 – 0.4375000000 I
S[4] = 0.3125000000 – 0.4687500000 I
S[5] = 0.3046875000 – 0.4609375000 I
S[6] = 0.3085937500 – 0.4609375000 I
S[7] = 0.3076171875 – 0.4619140625 I
S[8] = 0.3076171875 – 0.4614257812 I
S[9] = 0.3077392578 – 0.4615478516 I
S[10] = 0.3076782227 – 0.4615478516 I
S[11] = 0.3076934814 – 0.4615325928 I
S[12] = 0.3076934814 – 0.4615402222 I
S[13] = 0.3076915741 – 0.4615383148 I
S[14] = 0.3076925278 – 0.4615383148 I
S[15] = 0.3076922894 – 0.4615385532 I
S[16] = 0.3076922894 – 0.4615384340 I
S[17] = 0.3076923192 – 0.4615384638 I
S[18] = 0.3076923043 – 0.4615384638 I
S[19] = 0.3076923080 – 0.4615384601 I
S[20] = 0.3076923080 – 0.4615384620 I
S[21] = 0.3076923075 – 0.4615384615 I
S[22] = 0.3076923077 – 0.4615384615 I
S[23] = 0.3076923077 – 0.4615384616 I
S[24] = 0.3076923077 – 0.4615384615 I
S[25] = 0.3076923077 – 0.4615384615 I

The following graphics shows that the real parts of the partial sums of the series $f_2\left(\frac{3}{2}i\right)$ are approaching $\frac{3}{14}$ (blue line).

The real parts of the first 25 partial sums

The next graphics shows that the imaginary parts of the partial sums of the series $f_2\left(\frac{3}{2}i\right)$  are approaching $-\frac{6}{13}$ (blue line).

The imaginary parts of the first 25 partial sums

Also shown below is the graphics of the first 25 partial sums of the series $f_2\left(\frac{3}{2}i\right)$. They are approaching the complex number $f\left(\frac{3}{2}i\right)=\frac{4}{13}-\frac{6}{13}i$ (the intersection of horizontal and vertical blue lines).

The first 25 partial sums

Note that $f_1(z)=f_2(z)$ on $D_1\cap D_2$. Define $F(z)$ as

$$F(z)=\left\{\begin{array}{ccc} f_1(z) & \mbox{if} & z\in D_1,\\ f_2(z) & \mbox{if} & z\in D_2. \end{array}\right.$$

Analytic continuation

Then $F(z)$ is analytic in $D_1\cup D_2$. The function $F(z)$ is called the analytic continuation into $D_1\cup D_2$ of either $f_1$ or $f_2$, and $f_1$ and $f_2$ are called elements of $F$. The function $f_1(z)$ can be continued analytically to the punctured plane $\mathbb{C}\setminus\{-1\}$ and the function $f(z)=\frac{1}{1+z}$ is indeed the analytic continuation into $\mathbb{C}\setminus\{-1\}$ of $f_1$. In general, whenever analytic continuation exists it is unique.

# Functional Analysis 1: Metric Spaces

This is the first of series of lecture notes I intend to write for a graduate Functional Analysis course I am teaching in the Fall.

What is functional analysis? Functional analysis is an abstract branch of mathematics, especially of analysis, concerned with the study of vector spaces of functions. These vector spaces of functions arise naturally when we study linear differential equations as solutions of a linear differential equation form a vector space. Functional analytic methods and results are important in various fields of mathematics (for example, differential geometry, ergodic theory, integral geometry, noncommutative geometry, partial differential equations, probability, representation theory etc.) and its applications, in particular, in economics, finance, quantum mechanics, quantum field theory, and statistical physics. Topics in this introductory functional analysis course include metric spaces, Banach spaces, Hilbert spaces, bounded linear operators, the spectral theorem, and unbounded linear operators.

While functional analysis is a branch of analysis, due to its nature linear algebra is heavily used. So, it would be a good idea to brush up on linear algebra among other things you need to study functional analysis.

In functional analysis, we study analysis on an abstract space $X$ rather than the familiar $\mathbb{R}$ or $\mathbb{C}$. In order to consider fundamental notions in analysis such as limits and convergence, we need to have distance defined on $X$ so that we can speak of nearness or closeness. A distance on $X$ can be defined as a function, called a distance function or a metric, $d: X\times X\longrightarrow\mathbb{R}^+\cup\{0\}$ satisfying the following properties:

(M1) $d(x,y)=0$ if and only if $x=y$.

(M2) $d(x,y)=d(y,x)$ (Symmetry)

(M3) $d(x,y)\leq d(x,z)+d(z,y)$ (Triangle Inequality)

Here $\mathbb{R}^+$ denotes the set of all positive real numbers. You can easily see how mathematicians came up with this definition of a metric. (M1)-(M3) are the properties that the familiar distance on $\mathbb{R}$, $d(x,y)=|x-y|$ satisfies. The space $X$ with a metric $d$ is called a metric space and we usually write it as $(X,d)$.

Example. Let $x=(\xi_1,\cdots,\xi_n), y=(\eta_1,\cdots,\eta_n)\in\mathbb{R}^n$. Define
$$d(x,y)=\sqrt{(\xi_1-\eta_1)^2+\cdots+(\xi_n-\eta_n)^2}.$$
Then $d$ is a metric on $\mathbb{R}^n$ called the Euclidean metric.

This time, let $x=(\xi_1,\cdots,\xi_n), y=(\eta_1,\cdots,\eta_n)\in\mathbb{C}^n$ and define
$$d(x,y)=\sqrt{|\xi_1-\eta_1|^2+\cdots+|\xi_n-\eta_n|^2}.$$
Then $d$ is a metric on $\mathbb{C}^n$ called the Hermitian metric. Here $|\xi_i-\eta_i|^2=(\xi_i-\eta_i)\overline{(\xi_i-\eta_i)}$.

Of course these are pretty familiar examples. If there can be only these familiar examples, there would be no point of considering abstract space. In fact, the abstraction allows to discover other examples of metrics that are not so intuitive.

Example. Let $X$ be the set of all bounded sequences of complex numbers
$$X=\{(\xi_j): \xi_j\in\mathbb{C},\ j=1,\cdots\}.$$
For $x=(\xi_j), y=(\eta_j)\in X$, define
$$d(x,y)=\sup_{j\in\mathbb{N}}|\xi_j-\eta_j|.$$
Then $d$ is a metric on $X$. The metric space $(X,d)$ is denoted by $\ell^\infty$.

Example. Let $X$ be the set of continuous real-valued functions define on the closed interval $[a,b]$. Let $x, y:[a,b]\longrightarrow\mathbb{R}$ be continuous and define
$$d(x,y)=\max_{t\in [a,b]}|x(t)-y(t)|.$$
Then $d$ is a metric on $X$. The metric space $(X.d)$ is denoted by $\mathcal{C}[a,b]$.

In a metric space $(X,d)$, nearness or closeness can be described by a neighbourhood called an $\epsilon$-ball ($\epsilon>0$) centered at $x\in X$
$$B(x,\epsilon)=\{y\in X: d(x,y)<\epsilon\}.$$
These $\epsilon$-balls form a base for the topology on $X$, called the topology on $X$ induced by the metric $d$.

Next time, we will discuss two more examples of metric spaces $\ell^p$ and $L^p$. These examples are particularly important in functional analysis as they become Banach spaces. In particular, they become Hilbert spaces when $p=2$.

# Group Theory 1: An Overview

This is the first of a series of lecture notes on group theory I intend to write for undergraduate Modern Algebra I course I am teaching in the fall semester. Before we begin to discuss the subject, I would like to give an overview of what we study in group theory or more generally in algebra.

Algebra (as a subject) is the study of algebraic structures. So, what is an algebraic structure? An algebraic structure or an algebra in short $\underline{A}$ is a non-empty set $A$ with a binary operation $f$. $\underline{A}$ is usually written as the ordered pair
$$\underline{A}=(A,f).$$
A binary operation $f$ on a set $A$ is a function $f: A\times A\longrightarrow A$. An example of a binary operation is addition $+$ on the set of integers $\mathbb{Z}$. $+$ is a function $+:\mathbb{Z}\times\mathbb{Z}\longrightarrow\mathbb{Z}$ defined by $+(1,1)=2$, $+(1,2)=3$, and so on. We usually write $+(1,1)=2$ as $1+1=2$. In general, one may consider an $n$-ary operation $f:\prod_{i=1}^n A\longrightarrow A$, where $\prod_{i=1}^n A$ denotes the $n$-copies of $A$, $A\times A\times\cdots\times A$.

There are many different kinds of algebras. Let me mention some of algebras with a binary operation here. For starter, $(A,\cdot)$, a non-empty set $A$ with a binary operation $\cdot$ is called a groupoid. A groupoid $(A,\cdot)$ with associative law
$$(ab)c=a(bc)$$
for any $a,b,c\in A$ is callaed a semigroup. If the semigroup has an identity element $e\in A$ i.e.
$$ae=ea=a$$
for any $a\in A$, it is called a monoid. If for every element $a$ of the monoid $A$, there exists an inverse element $a^{-1}\in A$ such that $aa^{-1}=a^{-1}a=e$, the monoid is called a group. A group $(A,\cdot)$ with commutative law i.e.
$$ab=ba,$$
for any $a,b\in A$ is called an abelian group named after a Norwegian mathematician Niels Abel. Note the inverse ${}^{-1}$ can be regarded as an operation on $A$, a unary operation ${}^{-1}: A\longrightarrow A$ defined by ${}^{-1}(a)=a^{-1}$ for each $a\in A$. The identity element $e$ can be also regarded as an operation, a nullary operation $e:\{\varnothing\}\longrightarrow A$. Thus, formally a group can be written as $(A,\cdot,{}^{-1},e)$, a quadrupple of a nonempty set, a binary operation, a unary operation, and a nullary operation.

Now we know what a group is and apparently, group theory is the study of groups. But what exactly are we studying there? What I am about to say is not really limited to group theory but commonly applies to studying other algebraic structures as well. There are briefly two main objectives with studying groups. One is the classification of groups. This becomes particularly interesting with groups of finite order. Here the order of a group means the number of elements of a group. We would like to answer the question “how many different groups of order $n$ are there for each $n$ and what are they?” The classification gets harder as $n$ gets larger. There are groups with the same order that appear to be different. But don’t be decieved by the appearance. They may actually be the same group. What do we mean by same here? We say two groups of the same order same if there is a one-to-one and onto map (a bijection) that preserves operations. Such a map is called an isomorphism. It turns out that if a map $\psi: G\longrightarrow G’$ from a group $G$ to another group $G’$ preserves binary operation, it automatically preserves unary and nullary operations. Here we mean preserving binary operation by
$$\psi(ab)=\psi(a)\psi(b)$$
for any $a,b\in G$. If you have taken linear algebra (and I believe you have), you would notice that a linear map is a map that preserves vector addition and scalar multiplication. A map $\psi: G\longrightarrow G’$ which preserves binary operation is called a homomorphism. If a homomorphism $\psi: G\longrightarrow G’$ is one-to-one and onto, it is an isomorphism. An isomorphism $\psi: G\longrightarrow G$ from a group $G$ onto itself is called an automorphism. In group theory, if there is an isomorphism from a group to another group, we do not distinguish them no matter how different they appear to look. The other objective is to discover new groups from old groups. Some of the new groups may be smaller in size than the old ones. Here we mean smaller in size by having a smaller number of elements i.e. having a lesser order. Some examples are subgroups and quotient groups. Some of the new groups are larger in size than the old ones. An example is direct products. Subgroups, quotient groups (also called factor groups), direct products are the things we will study as means to get new groups from old groups.

Group theory has a significance in geometry. In geometry, symmetry plays an important role. There are different types of symmetries: reflections, rotations, and translations. An interesting connection between geometry and group theory is that these symmetries form groups (symmetry groups). The most general symmetry group of finite order is called a symmetric group. In mathematics, the embedding theorem is conceptually and philosophically important (though it may be practically less important). When we study mathematics, we often feel that the structures we study are highly abstract and we feel like they only exist in our consciousness but not in the physical world. The embedding theorem tells that those abstract structures we study are indeed substructures of a larger structure that we are familiar with in the physical world. The embedding theorem implicates that we are not making up those abstract mathematical structures but we are merely discovering them which already exist in the universe. This kind of view point is called Mathematical Platonism. It turns out that there is an embedding theorem in finite group theory, namely every group of finite order is a subgroup of a symmetric group. The embedding theorem is called Cayley theorem. This means that the study of finite groups boils down to studying symmetric groups.

Remark. There is a mathematical structure called algebras over field $K$ (usually $K=\mathbb{R}$ or $K=\mathbb{C}$). An algebra $\mathcal{A}$ over field $K$ is a vector space over $K$ with a product $\cdot:\mathcal{A}\times\mathcal{A}\longrightarrow\mathcal{A}$ which is distributive over addition:
$$a(b+c)=ab+ac,\ (a+b)c=ac+bc,\ \forall\ a,b,c\in\mathcal{A}.$$
(Here, the symbol $\forall$ is a logical symbol which has meaning “for each”, “for any”, “for every”, or “for all” depending on the context. I will talk more about logical symbols next time as I will use them often.) Note that an algebra $\mathcal{A}$ over field $K$ is not an algebra because the scalar product is not an operation on $\mathcal{A}$. The scalar product is in fact an action of the multiplicative group $K\setminus\{0\}$ on $\mathcal{A}$. Algebras over field $K$ are important structures in functional analysis.