Steinberg relations and symbol computations

Given a field F, Quillen defined K-groups K_n(F) to be the higher homotopy groups of a space K(F). Though apparently the space itself can be easily and explicitly constructed, the K-groups are mysterious gadgets. However the homology groups of the connected component of K(F) containing its base point coincide with the homology groups of the general linear group.

Anyway, back to Quillen K-groups. For n\leq 2, these groups coincide with the Milnor K groups K^M_n(F) which are more algebraic in nature and much easier to define. The n-th Milnor K group of a field F is defined as follows :

Let F^* denote the abelian group of non-zero elements of the field F. Then

K^M_n(F) = (F^*\otimes_{\mathbb{Z}} F^*\otimes_{\mathbb{Z}}\otimes_{\mathbb{Z}} \ldots F^*)/J

where J is the subgroup generated by tensors a_1\otimes a_2\otimes \ldots \otimes a_n where for some i\neq j, a_i+a_j=0. The class of the tensor a_1\otimes a_2\otimes \ldots \otimes a_n in K^M_n(F) is denoted \{a_1,a_2,\ldots,a_n\}.

Thus for a\in F^*, we have \{\ldots, a, \ldots, 1-a, \ldots \} = 0. These are the the so-called Steinberg relations.

Thus, we have

  • K^M_0(F) = \mathbb{Z}
  • K^M_1(F) = F^*
  • K^M_2(F) = (F^*\otimes_{\mathbb{Z}} F^*)/(a\otimes 1-a)

Let us do some symbolic computations in K^M_2(F) to get a feel for this object (and also because it is fun!)

The Rules

  1. Since \otimes is bilinear, \{a, b\} + \{a, c\} = \{a, bc\}.
  2. Similarly \{a, b\} + \{c, b\} = \{ac, b\}.

So  \{a,1\} + \{a,1\} = \{a,1\} which implies \{a,1\} =0. Similarly \{1,b\}=0. Using bilinearity repeatedly, n\{a,b\} = \{a^n, b\} = \{a,b^n\}\forall n\in \mathbb{Z}.

If n<0, maybe this needs some further explanation. For instance if n=-1 say, then  0= \{1,b\} =  \{a,b\}  +\{a^{-1},b\}..

 

The Game


I. Show \{x,-x\}=0.

This is because  \{x,-x\} = \{x,-x\} - \{1-x,x\} = \{\frac{x}{1-x},x\}= -\{\frac{x+1}{x}, x\} = - \{1+\frac{1}{x}, x\} = \{1+\frac{1}{x}, \frac{1}{x}\} = 0.


II. Show -\{a,b\}=\{b,a\}.

This is because  \{a,b\}+\{b,a\} = \{a,b\} + \{a,-a\}+\{b,-b\} + \{b,a\}=\{a,-ab\}+\{b, -ab\}=\{ab,-ab\}=0.


III. Show \{a,-1\}=\{a,a\}.

This is because  \{a,a\}=\{a,a\}-\{a,-a\} = \{a,a\} + \{a,\frac{-1}{a}\} = \{a,-1\}.


 

Euclid’s first postulate

postulate1

To draw a straight line from any point to any point.

A postulate, to quote from dictionary.com is something taken as self-evident or assumed without proof as a basis for reasoning. And according to Euclid, nothing can be more self-evident than the fact that given two points, one can draw a straight line segment joining them.

Now, it is also obviously self-evident that there is exactly one such line joining two given points, i.e. that there is a unique line joining any two points.

However Euclid does not mention the uniqueness, though he seems to assume it in the subsequent proofs .. So probably a more accurate first postulate would be

To draw a straight line (which will be unique) from any point to any point.

The Processing code

int time1 = 500;
   int time2 = 2500;
   PFont f;
   
   void setup() {
     size(600, 120);
     smooth();
     f = createFont("Arial",20,true); 
}
   void draw() {
     int currentTime = millis();
     background(204);
     if (currentTime > time2) {
       ellipse(100,60,10,10);
text("A",95,90);
  fill(0);
ellipse(500,60,10,10);
text("B",495,90);
       line(100,60,500,60);
     } else if (currentTime > time1) {
       textFont(f,20); 
         fill(0);
ellipse(100,60,10,10);
text("A",95,90);
  fill(0);
ellipse(500,60,10,10);
text("B",495,90);}
    
   }

A series of posts on Euclid’s Elements

Why, pourquoi ?!

OK, this series of posts on Euclid’s Elements serve a dual purpose.

  1. To recall my vague memories of Euclidean geometry, the subject that first made me like mathematics in general
  2. To learn animation using the software called Processing. So the terrible gifs that you see here record my baby attempts at learning to draw geometrical figures with some time lapse on the computer. I’ve decided to go the immersion route, … meaning I have a clear cut goal of exactly what gif I want to make and I will make it even if it means I write the dumbest code to get it working. Hopefully, as time progresses, I will get better at figuring out more efficient and elegant ways to do it.

Is each post going to be bit-sized or byte-sized or giga-byte sized ?

I hope to be very brief with the text and let the gifs do the talking. You know, “Show, don’t tell”. Also, the posts will mostly be distraction free, so you won’t have a link every second sentence.

I vaguely know what an isosceles triangle is and that parallel lines never meet. Can I still follow what’s going on or are you going to talk Latin ?

I guess ‘talking Greek’ would be a more appropriate phrase since Euclid wrote his Elements in Greek. But leaving frivolity aside for a second, the beauty of Euclid’s elements is that he builds everything from scratch. So you don’t need to know anything to begin with. However, each step will heavily rely on previous steps, so it might be slightly advantageous to go in sequential order

Who are you ? Do you really know Euclidean geometry ? Can I trust what you are saying ?

Well, I’m a working mathematician. I did know some Euclidean geometry when i was in high school. Sadly due to lack of use, I have forgotten many of the cool things I used to know, so hopefully this will be a me-and-you-learning-together.

You should never trust what is being said blindly. But I will try prove most of the things I say here, so trust me after reading the proofs!

What is Processing ? 

It is a software where you write some code to draw/animate some nice figures on your computer. I’m a novice at programming and helpless with technology, though I can write some if and for loops in various languages. So don’t ask me more.

 

Will you post your code for the gifs that you make ?

Yup

Are the posts going to be periodical ? 

No. It ought to be, I wish it could be, but I’ll probably end up doing this once in a blue moon when I have some time to kill..

Are criticisms welcome ?

Yes. Also error correction is doubly welcome

Is this pointless post ever going to end ?

Point taken. Until the next time!

The Legendre symbol

2 is not a square. Sure, if you are working over the field of rationals, fondly denoted \mathbb{Q}. However imagine if your world is now the field of seven elements \mathbb{F}_7, then 2=3^2 is very much a square ! Over \mathbb{F}_3, 2 is NOT a square. Here the only squares are numbers congruent to 0 or 1 mod 3.

The natural question to ask, if you are amused easily by numbers is whether there is a nice way to determine when a given number a is going to be a square or not modulo a given prime p. This is precisely what the Legendre symbol sets out to do.

Notes :

  1. The case p=2 is uninteresting because every number is a square mod 2, so from now on in this post we only deal with odd primes p
  2. Terminology alert (!) : If is a square modulo p, it is called a quadratic residue modulo p

Screen Shot 2014-11-19 at 8.37.44 AM

So for instance, our above number game with 2 and 7 and 3 can be written up in Legendre symbols as \left(\frac{2}{7}\right)= 1 whereas \left(\frac{2}{3}\right)= -1. So depending on whether the Legendre symbol spits out 0, 1 or -1, we know whether it is a quadratic residue or not modulo the given prime.

All this is fine, but HOW do you compute \left(\frac{a}{p}\right) ? Clearly, if divides a we are relieved and output \left(\frac{a}{p}\right)=0. If p does not divide a, the cry goes up ..Now what ?!

It is time to investigate some basic arithmetic that is happening over these finite fields \mathbb{F}_p or more generally \mathbb{F}_{p^n} where is an odd prime.

Question 1 : Exactly how many squares (and non-squares) are in there in \mathbb{F}_q, where q=p^n, p an odd prime.

This is easy to answer, 0 is a square. And if a\neq 0\in \mathbb{F}_q, a\neq -a (since p is odd) but a^2 = (-a)^2 Thus,

  1. The number of squares is given by 1+\frac{q-1}{2} = \frac{q+1}{2} = \frac{p^n+1}{2}.
  2. The number of non-squares is given by q-\frac{q+1}{2} = \frac{q-1}{2}= \frac{p^n-1}{2}.

Question 2 : How do the squares and the non-squares in \mathbb{F}_q interact with each other under multiplication ?

This is again mostly easy to answer (with just a little bit of thinking). There are three cases

  1. A square multiplied by another square is still a square. Also 1\times 1 = 1 (CLEAR!)
  2. A square multiplied by a non-square is a non-square. Also 1\times -1 = -1 (CLEAR!)
  3. A non-square multiplied by a non-square is a square. Also -1 \times -1 = 1 (Er, not so clear)

The third point needs some clarification. Let be a non-square (so it is not 0 for instance). Look at the map which is multiplication by a, that is f : \mathbb{F}_q \to \mathbb{F}_q, x\leadsto ax. This is a bijection of sets (we are in a field!)

Leave 0 aside, it goes to itself under f. The \frac{q-1}{2} squares go to \frac{q-1}{2} non-squares under the map f (by point 2). So the \frac{q-1}{2} non-squares HAVE TO GO TO non-zero squares under f. This clears up point 3. We have basically proved that the Legendre symbol multiplies !

Screen Shot 2014-11-19 at 8.38.06 AM

Great, but are we any closer to actually computing \left(\frac{a}{p}\right) ?

With a little more work, yes ! Remember that if you delete zero from a field \mathbb{F}_q, the rest of the elements form a (multiplicative) group of order q-1. Thus for any nonzero in the field \mathbb{F}_q , we have x^{q-1}=1.

Let us now work with the finite field \mathbb{F}_p where is an odd prime. Then the equation x^{\frac{p-1}{2}}=1 has as solutions all the non-zero quadratic residues mod which are exactly \frac{q-1}{2} in number ! So the quadratic residues are precisely the solutions to x^{\frac{p-1}{2}}=1 !

What happens to a non-quadratic residue mod p ? Well a^{p-1}=1 and a^{\frac{p-1}{2}}\neq 1, so it has to be the other square root of 1, namely -1. Thus, in fact, we have found an explicit formula for the Legendre symbol ! [The case when a=0 is clear.]

Screen Shot 2014-11-19 at 8.38.18 AM

So for instance now we know exactly for which odd primes, -1 is a square.

  • -1 is a square mod primes which are 1 mod 4
  • -1 is NOT a square mod primes which are 3 mod 4

Let us part with the following question which we left out discussing :

We know that in \mathbb{F}_q where q=p^n and p is an odd prime, there are exactly \frac{q+1}{2} squares [including 0]. What about the field \mathbb{F}_{2^n} of 2^n elements. How many elements of it are squares ?

[Hint : Psst, Think Frobenius ]

The Lion and the Man

(apparently was known as the Lion and the Christian)

Attended a really nice colloquium about this problem at school yesterday. So the problem is as follows :

A lion and a man are placed in a circular arena of radius 1m (think ancient Rome). Both can run at equal top-speed 1 m/s say. Imagine the man and the lion to be points. The lion wants to catch the man and the man wants to escape being caught by the lion. Let’s assume that after time T, both man and lion are so tired that they decide to not move anymore. So er.. the “game” ends when the lion wins (catches the man) or after time T, the man is still alive (not caught by the lion). Is there a winning strategy for the man, is there a winning strategy for the lion, is there perhaps no winning strategy for either player or are there winning strategies for BOTH ?? (can that ever be possible)

Of course, being a mathematician, you allow your arena to be any compact metric space and wonder what happens if the space is not compact etc etc. And if you are interested, you can also see by what distance the man escapes the lion throughout the game, and what happens if you allow T to become larger and larger … i.e., the unbounded time game

This problem came into being in the early 1900s, after being posed by a mathematician called Rado and was tackled by the amateur mathematicians with great enthusiasm. Here are a few early attempts. (Let’s say the lion is at the center of the circle) :

  • Say the Lion decides to just run straight towards the man, wherever he is. That is an obvious strategy, but maybe it is not very good for the Lion though. If the man decides to keep running around the circumference of the circle, say. Then what happens ?
  • It was widely believed that the best the man could do was run around the circumference of the arena at his top speed. But then the Lion could have the following (better) strategy. It decides to be on the line joining the man and the center always, running at top speed 1 m/s …

Let us see what happens in this case [high school trig alert]. Assume the man starts at (1,0). Then at time t, he is at (\cos t, \sin t) at time t because remember he is running at top speed 1 m/s..

man

Where is the lion ? He is at (f(t), f(t)\tan t) [because he should be on the line joining the center and the man which has slope \tan t.] The question is, what is f(t) ? Note that the lion’s top speed is 1m/s. So the “magnitude” of his derivative would be 1.

\sqrt{f'^2 + (f\tan t)'^2 }=1, giving us the differential equation (after some manipulation)

(f'+f\tan t)^2+f^2=\cos^2 t

At this point, I have forgotten how to solve this differential equation. Is there a nice substitution trick which leads to the solution ? Update : Check the end of the post for a solution

 

But even if you don’t solve the differential equation, with a little vague plotting, you can guess that the Lion will trace a semicircle centered at (0,\frac{1}{2}). Armed with this guess, you can either do some simple high school trignometry/geometry to check that this satisfies the differential equation.

Namely f(t)=\sin t\cos t =\frac{\sin 2t}{2}. Here’s a terribly drawn picture to convince you that the semicircle travels distance t in time t (hence the speed is 1m/s)

 Lionandman

So after \pi/2 seconds, the Lion catches the man. And it was believed that the Lion could always catch the man since the man’s best would be to run around the circle at top speed..

  • It was in 1952, that Besicovitch, a mathematician pointed out that the man could do much better, in fact he has a winning strategy, which is quite pretty to describe.

The man’s strategy is to do the following. Let us say at the beginning, he finds the radius on which he is standing (say he is at distance r_1 from the center) and checks on which side of the radius the Lion is and runs perpendicular to the radius on the opposite side for t_1 seconds. So now he is at a distance for \sqrt{r_1^2+t_1^2} from the center. Here’s a picture to explain that :

Manstrategy1

Then he does this again and runs for t_2 seconds exactly as above .. And if it happens that the lion is on the SAME radius that he is, he makes a choice (say he runs right if this happens at any point in time). Note that therefore it is not a “continuous” strategy, because even if the lion a teeny weeny bit to the right of his radius, he runs left, but if the lion is on the radius, he runs right.

Now, we have to determine t_1,t_2,\ldots (ie, for how long his first run is and how long his second run is etc) Let’s in fact assume we are in the unbounded time game, so the man and the lion run forever, and the man wins if we can prove he will never get caught.

Obviously, we don’t want the man to get caught, so \sum t_i = \infty. And also he should stay inside the circle, so it is better that r^2 + \sum t_i^2 be finite (we can scale to make it land inside the circle). And of course, you should think of the harmonic series, namely \sum \frac{1}{n} for t_i.

Now, is it clear that the man wins? Here’s a picture to illustrate why the Lion can never catch the man. [Note that everything is squared to make avoid square roots in the distances in the picture]

whymanwins

So the man has a winning strategy, yaay!

Now the question the colloqium proceeded to ask and address was whether the Lion could also have a winning strategy… Er, this is a bit weird, how can both players have winning strategies? What is each plays his winning strategy, then you get a contradiction ..? Yes?

Well, this “let each player play his strategy” is not well-defined apparently. If man’s strategy is called S, it means he takes the lion’s path “l” so far and S(l) tells him what happens to his own path “m”. And similarly, if the lion’s strategy is G, then G(m)=l.

The question then would be, why are we guaranteed paths “l”, “m” so that G(m)=l and S(l)=m? That is there is no contradiction in each player having a winning strategy .. (This still blows my mind).

And it turns out for the circle arena, the lion DOES NOT have a winning strategy, but there are compact metric spaces for which both players have winning strategies .. It involved some nice analysis concepts like Ascoli Arzela etc, Brower’s fixed point theorem etc. But for now, let’s be content with Bescovitch’s ingenious solution.

And here’s the paper on arxiv [Lion and Man –Can both win ?] if you are curious.


 

Thanks to Fred, here’s a way to solve the differential equation (f'+f\tan t)^2+f^2=\cos^2 t

 Use f(t) = v(t)\cos t because clearly f(t) is bounded by \cos t. So you get that f'=v'\cos t - v\sin t and hence v'^2 \cos^2 t + v^2\cos^2 t = \cos^2 t \implies v'^2 + v^2 = 1

This is a separable differential equation . \frac{dv}{dt}=\pm \sqrt{1-v^2}\implies \frac{dv}{\sqrt{1-v^2}}=\pm dt or v=1. This leads to the solution sin^{-1}v = \pm t + c which gives us v = sin(\pm t +c) or v=1

Thus f(t)=\sin(\pm t+c)\cos t or f(t)=\cos t.

Always some right angle or the other

Q : Given an n\times n grid and a set of at least 2n-1 marked points on it, prove that you always end up with a right angle.

Proof : You can see that this number is optimal because of the following picture :

Optimal

Fred’s very cute solution :

Let S denote the set of marked points. We say a point s\in S has a horizontal neighbour if you can find a t(\neq s)\in S such that s,t lie on one horizontal line on the grid. Similarly define when a point s\in S has a vertical neighbour.

Now there are n rows, so atmost n-1 points don’t have horizontal neighbours. Since there are |S|=2n+r\geq 2n-1 where -1\leq r\leq n^2-2n marked points, there are atleast |S|-(n-1)=(2n+r)+1-n=n+r+1\geq n points which DO have horizontal neighbours. Let H denote the set of marked points with horizontal neighbours, so |H|\geq n+r+1\geq n.

Play a similar game and conclude that there are atleast |S|+1-n=n+r+1\geq n points which DO have vertical neighbours. Let V denote the set of marked points having vertical neighbours. So |V|\geq n+r+1\geq n.

Since |S|=2n+r and |V|+|H|=2n+2r+2 and 2n+2r+2>2n+r because r>-2, V\cap H\neq \emptyset. So there is a point which has a horizontal AND a vertical neighbour and hence you get a right triangle !