Permutations and supports

See also the Blogger version of this post at https://explaining-maths.blogspot.com/2021/07/permutations-and-supports.html where the maths looks a bit clearer.

Here are a post and a follow-up comment of mine from my first-year Pure Piazza forum, in response to a question asking about the notation \mathrm{supp}(\sigma) (the support of a permutation \sigma).

My original response

The support of the permutation is the set of elements where the permutation has any effect.
Points outside the support are left where they are by the permutation.
Points in the support are all moved around (to other points in the support), and none of them stay where they were. So all the action takes place in the support.
The identity permutation has empty support.
Two permutations have disjoint support if … well, if their supports are disjoint! You can just say that such permutations are disjoint for short.
When you write a permutation as a product of disjoint cycles (including 1-cycles if you want), then the support of the whole permutation is the union of the supports of the disjoint cycles. For most cycles the support is the set of elements mentioned in the cycle, but 1-cycles have empty support! (A 1-cycle is just the identity permutation.)
For example, consider the permutation \rho of the 7-set \{1,2,3,4,5,6,7\} written, as a product of disjoint cycles (including some 1-cycles), as
      \rho=(1\,5\,7)(2\,6)(3)(4)\,.
(The 1-cycles are optional here and have no effect). Then
      \mathrm{supp}(\rho)= \{1,5,7\} \cup \{2,6\} = \{1,2,5,6,7\}.
This only works for products of disjoint cycles, though. For example, you can quickly check that (1\,2) (3\,2\,1) = (1\,3). In this example, 2 is actually in the support of both cycles, but not in the support of the product of these cycles.

Follow-up post

Here (below, after an introduction) is a nice exercise related to the above.

Introduction concerning transpositions

Note that a transposition is another name for a 2-cycle. These just swap two different elements of the set you are working with (which must have at least two elements). Note that if you multiply a transposition by itself you get the identity permutation (the second application puts the two elements back where they started). So if \tau is a transposition we can say that \tau^2 is the identity permutation. (There are also some other permutations with this property which are not transpositions. What are they?)
To be clear, for any permutation \tau, \tau^2 means that you multiply the permutation \tau by itself, using the usual multiplication of permutations, which is the same as composition of functions. So for any permutation \tau, we have
          \tau^2=\tau\tau=\tau \circ \tau.
If \tau is a transposition, then \tau^2 is the identity permutation. (But the converse is not true, unless your set has fewer than 4 elements and you assume that \tau is not the identity permutation!)

Exercise

Let X be a non-empty set. (If you want, you can assume that X is finite, or even that X=\{1,2,\dots,n\} for some natural number n if you like, but it isn’t necessary.) Here is a fact about permutations of X. (Where we talk about transpositions below, we mean permutations of X that are 2-cycles.)
Let \rho be a permutation of X and suppose that supp(\rho) is a non-empty, finite set. (So \rho is not the identity permutation, but \rho only moves finitely many elements.) Note here that supp(\rho) must have at least two elements. (Why?)
Let k be the number of elements in supp(\rho).
Prove that \rho is a product of some finite number of transpositions, and that it is possible to do this using strictly fewer than k transpositions in the product.
(You won’t need to use the same transposition more than once, but if you do it counts more than once.)

Hint: Induction on k, or design an algorithm based on the following idea.
Suppose you have some bottles in front of you numbered 1 to 10, but they are in the “wrong” order. How can you put them into the right order (left to right, 1 to 10) if all you are allowed to do is swap two bottles at a time? How would you guarantee to do it with at most 9 swaps, even if all of the bottles are in the wrong places? Can you think of several different strategies?
Warning! if you can do a particular case with exactly 8 swaps then it turns out that you can’t do that case with exactly 9 swaps, even if you tried completely different swaps! (But that’s another story, about “odd” and “even” permutations.)

Have a go!

Proving “there exists” statements

See also the version of this post on Blogger at https://explaining-maths.blogspot.com/2021/07/proving-there-exists-statements.html where the maths (using MathJax) looks a bit clearer.

Here is another question I was asked on my first-year pure maths Piazza discussion forum.

When proving there exists statements, is it enough to give just one example or do you have to prove it using the definitions, etc.?

Here is my reply:

Note: I use \mathbb{Q}^c to denote the set of irrational numbers, so
            \mathbb{Q}^c = \mathbb{R}\setminus \mathbb{Q}\,.

Hi,
The answer is really “yes, as long as you know what it means to give one example”.
Let me give two examples, one relatively easy, one more complicated.

First a fairly straightforward example. In practice coursework one, we discovered that the following statement is true:
(S1)      There exists x \in \mathbb{Q}^c such that x^2 \in \mathbb{Q}.
This statement can be proven true using one specific example, e.g. x=\sqrt 2: it is standard that \sqrt 2 is irrational, and (\sqrt 2)^2 = 2 \in \mathbb{Q}.
Notice that we could use any other letter in place of x and the meaning of (S1) does not change. But we wouldn’t usually use m, n or k (for example) as those letters usually represent integers.

Now for a slightly more complicated example. Consider the following statement:
(S2)      \forall x \in \mathbb{Q}, \exists n \in \mathbb{N}: nx \in \mathbb{Z}
In words, in an optionally expanded form, this says
 (S2b)      For every rational number x, it is true that there exists at least one positive integer n such that nx is an integer.
(There are many other ways to express this, all of which mean the same thing.)

This is really claiming that an infinite number of “There exists” statements are all true. These statements depend on the rational number x involved. If all of these statements are true, then they can each be proven true using one example of an integer n. But the n you need will depend on x. And it would not be enough to just check a few values of x, because the “outer” statement is a “for all” statement. So we would need a general proof, valid for all rational numbers x, which shows, for each rational number, how we can choose a suitable value of n.

Now (S2) and (S2b) are true, and each of these “there exists” statements can be proven true using one example n, but where the n you choose depends on x.

Here is how a proof of (S2) goes.

Let x \in \mathbb{Q}. Then there are m \in \mathbb{Z} and n \in \mathbb{N} such that x=m/n. But then n \in\mathbb{N} and nx=m \in \mathbb{Z}. Thus it is true that \exists n \in \mathbb{N}: nx \in \mathbb{Z}.
Since x was an arbitrary element of \mathbb{Q}, this shows that
          \forall x \in \mathbb{Q}, \exists n \in \mathbb{N}: nx \in \mathbb{Z},
i.e. (S2) is true, as required.

Notice that our “one example” here depends on x, and we could use any positive integer that works as a denominator for x. If you wanted to, you could use lowest terms, and that would then give you the smallest positive integer n that works. But you don’t have to do this here.

Best wishes,
Dr Feinstein

Greatest common divisors

See also the version of this post on Blogger at https://explaining-maths.blogspot.com/2021/07/greatest-common-divisors.html where the maths (using MathJax) looks a bit clearer.

Earlier this term there was a question on my first-year pure Piazza forum about greatest common divisors (highest common factors).

Question: I know how to show that something is a common divisor of two numbers but how do you show that it is the greatest common divisor of those two numbers?

The Students’ Answer was sensible:

Try the Euclidean Algorithm

with a reference to the relevant lecture (“Lecture 7b”)

I then responded with two posts:

Main response:

Hi,

There are, in fact, lots of different ways to investigate the greatest common divisor of two integers a and b, as long as we know that they are not both 0. (I’ll assume this below.)

To make things simple, let’s assume that a and b are non-negative. (Replacing a with -a and/or b with -b has no effect on the GCD, so we can always change the numbers to arrange this without changing the GCD.)

If, for example, b=0, then we must have a > 0, and

\textrm{GCD}(a,b) =\textrm{GCD}(a,0)=a.

Similarly if a=0 then we must have b>0 and

\textrm{GCD}(a,b)=\textrm{GCD}(0,b)=b.

So now we can suppose that a and b are natural numbers. Then, if either a or b is 1, the GCD is obviously 1, so we can ignore this case.

So now we can assume that a and b are natural numbers and that both are at least 2. By the FTA (Fundamental Theorem of Arithmetic, Lecture 6) we can, in theory, find the prime factorizations of a and b, and use that to find the GCD. This works reasonably well for small numbers. For example, suppose a=63 and b=147. Then a=3^2 \times 7 and b=3 \times 7^2. (Not too hard to work out with small numbers.) Then you can read off the GCD by raising each prime to the highest power available (ensuring that this divides both a and b) and then multiplying the resulting prime powers together. (If there are no common prime divisors, you end up multiplying the 0th powers together and end up with 1.) Here we get

\textrm{GCD}(a,b)=3^1 \times 7^1 = 21.

In a similar way, if you have one small number and one much larger number, you can sometimes use the prime factorization of the smaller number to limit the possibilities for what the GCD could be, and then use e.g. modular arithmetic to determine which of these possibilities is the right one. (I’ll give you some examples of this type in a quiz soon! But see also past exam papers.)

For example, can you determine \textrm{GCD}(36,10^{23}+11)? Well, 36=2^2 \times 3^2, so there are not that many possibilities, and this is reduced further by the fact that 10^{23}+11 is odd. So you find that you just need to determine the highest power of 3 dividing 10^{23}+11, and this is easily done using modular arithmetic.

But if both numbers are large, then you probably won’t easily be able to determine the prime factorization of either!
In this case, as suggested above, you may want to use the Euclidean Algorithm, as we did in Lecture 7b. Note that we proved some theory first in order to justify why the Euclidean Algorithm always works to find the GCD. Of course, it may take a lot of steps before it finishes, and it does involve repeatedly finding quotient and remainder (the Division Agorithm). This basically boils down to long division, but it may not be so easy with large numbers. Still, the Euclidean Algorithm is generally the most systematic approach.

Yet another approach uses theory associated with the proof of Bézout’s Lemma from Workshop 4: if we somehow manage to find integers m and n so that y=ma+nb is a (strictly) positive common divisor of a and b, then y must actually be the GCD of a and b. So if you happen to spot a nice way to combine multiples of a and b in this way to produce a relatively small positive integer y, and if you spot that y is a positive common divisor of a and b, then y must be the GCD. For example, if a=2^{100}-1 and b=2^{99}+1 then we might spot that 2b-a=3. Then modular arithmetic (for example) helps us to spot that 3 really is a common divisor of a and b, so (by the result we proved in Workshop 4) 3 must actually be the greatest common divisor.

Well, I’ve given you so  many possible methods, how can you choose between them? I don’t know! But I’ll set you some quiz questions, and let you try the different methods for yourselves.

But to give you one to think about, can you determine \textrm{GCD}(a,b) when a=10^{1000}-1 and b=10^{998}-1?

Best wishes,
Dr Feinstein

Follow up response:

Here is an interesting variant: what if, instead,

a=10^{1000}-1 and b=10^{998}+1?

You can do this with the Euclidean algorithm, as long as you can find the correct q and r for the first division. But have another look at the proof of the lemma on annotated slide 4 of Lecture 7b.

[This is the result which says that when you use the Division Algorithm to write a=qb+r in the usual way, then \textrm{GCD}(a,b)=\textrm{GCD}(b,r).]

We used the fact that a=qb+r. But although we were most interested in the case where 0 \leq r < b, we never used that inequality in the proof of the lemma! So in fact, the same result works whenever a\in \mathbb{Z}, b\in \mathbb{N} and q and r are integers, even if you haven’t found the “best”  integers q and r. That is not a standard fact, though, so if you want to use it or something similar you should prove it. 

The reason we wanted to use the standard remainder r is because this guarantees that the remainders are strictly decreasing and non-negative, so they have to stabilise. But there are alternatives based on careful generalisations of that lemma.

If you choose to use an r which is negative, it is probably best to take the modulus of r before continuing with the process. This does not affect the GCD, but the second line of the lemma, about what happens when the remainder is 0, does assume that b>0, and anyway we usually divide by positive integers in this module.

Best wishes,
Dr Feinstein

Poll on students writing proofs for themselves

At Nottingham, lots of us are now using Piazza discussion forums for our modules.
For my first-year introductory pure module, I set up a poll:

I only had 23 responses (a little over 10% of the class). Here are the results. (Actually, I never closed the poll! But I’m not expecting any new responses. Perhaps I should repeat the poll after the exam?)

As usual, knowing where to start was perceived to be the hardest thing, with “How did anyone think of that?” coming in second. The others, which students do usually find quite hard in practice, were well behind. Perhaps students felt that they understood how to do these things in theory.

Below is a follow-up post I made to the poll after 18 votes were in. I don’t know whether many students read this, though! No-one marked it as a good comment … maybe it would have been better as a separate post?

A question sheet I refer to below is available here:

______________________________

Well, 18 votes isn’t much, but so far “knowing where to start” is a clear winner, with “How did anyone think of that?” second.

So, here is a general recipe for a typical direct proof in this module:

  • What have you been told about the numbers (or other mathematical objects) in the question/statement?
  • What do the definitions of the terms used there tell you? It is often good to substitute in the definitions to try to make the statement you are working with more “elementary”.
  • What is the desired conclusion (the target statement, not yet proven)?
  • What do the definitions of the terms in the target statement tell you? Substitute in the definitions to try to make the statement you are working towards more “elementary”. But make sure to note that you haven’t proved it yet! (Writing down a statement that you want to prove, without carefully labelling it as “not yet proven”, is very risky, because you might accidentally start making deductions from it, which could lead to an invalid “backwards” proof.)
  • Do we know some useful standard facts from the module that could help us, or at least save us some work? (E.g. the Algebra of Rationals is often helpful.)
  • Can you now see how to deduce the target statement from the information you have? (At this point it is often only a couple of lines to get from the starting information to the desired conclusion.)

Most of the direct proofs in the module follow this pattern!
Once you are used to this, such proofs almost write themselves. But it takes time and practice to get used to it.

You may find the FPM question sheet (with 53 questions) Practice with definitions proofs and examples useful to help you to hone your skills. For example, here is a “recipe” for answering question 10 from that sheet.

  • Substitute in the definition to see what the information given tells you about A, N and the sequence.
  • Substitute in the definition to see what you are expected to prove about A, N' and the sequence.
  • Note that the latter is a very quick/immediate consequence of the former. (About one line.)

Of course, we also have other types of proof in the module. But there are a lot of direct proofs, and it would be good if these didn’t look “mysterious” to you.

Best wishes,
Dr Feinstein

An unusual issue involving contrapositives

See also https://explaining-maths.blogspot.com/2021/07/an-unusual-issue-involving.html for a version of this post on Blogger (using MathJax) where the maths looks a bit clearer.

For the last question on my recent first-year pure mathematics assessed coursework (involving subsets of \mathbb{R}), one of the possible solutions involved first proving the following true statement about real numbers x:

     If x is irrational, then 1/x is irrational.

But the contrapositive of this appears to say

      If 1/x is rational, then x is rational.

Now the first statement is surely true, but the second looks dodgy to me, because unless you know x is non-zero, 1/x may not even make sense!

If you interpret “If 1/x is rational” as “If 1/x makes sense and is rational” then you are OK. But I’m not convinced that is reasonable.

Perhaps the first “true” statement would be better stated as

    If x is irrational then 1/x makes sense and is irrational.

Then the contrapositive appears to be

If 1/x does not make sense or 1/x is rational then x is rational.

I suppose that one may be OK?

Teaching this Semester

Well, I’ve been too busy teaching this semester to Blog about teaching!
As well as being Outreach Officer and Teaching Foundations of Pure Mathematics (FPM) again this semester, this year I am the Teaching support Officer. Among other things, this means that I am involved in providing additional support for the three year-long Core modules: Analytical and Computational Foundations (ACF), Linear Mathematics (LMA), and Calculus (CAL). In this role I have Drop-in sessions, I help with Problem Classes, and I’m generally available to answer questions about the Core. I expect that I may see increased demand as we approach the January assessments!
Although I haven’t been posting here, I have made a lot of posts on our local FPM Piazza forum and a number of posts on our Core Piazza forum. I’m going to have a look at those posts and transfer some of the content to this Blog over the next few weeks (but not just yet!), because I think there is some interesting material there.

Foundations of Pure Mathematics (FPM) archives

Videos are available from 2014-15, 2018-19, 2019-20 and 2020-21 editions of Foundations of Pure Mathematics (FPM)

The complete set of videos from the 2014-15 edition of Foundations of Pure Mathematics (FPM) is available on YouTube and iTunes. Since then, I have opened up some of the Echo360 recordings (also known as “Echoes”) from previous years. These have the (possible) advantage that you have two separate windows, one with the screen recording (the “screencast”) and one with the footage of me. These windows can be resized or hidden according to your taste! Another nice feature of these Echoes is that you can change the speed of the video if you find my pace either too slow or too fast. (This often varies from student to student, from lecture to lecture, and also within lectures). If you click on the settings cog near the bottom right of the video window, and click on the speed (default 1), there are plenty of options!

I don’t advise anyone to watch several versions of every class! But if there is a specific point you are interested in, then there is a possibility that I did say something different about it each year.

The 2018-19 edition of FPM is available at https://echo360.org.uk/section/4c490e8b-27f7-4fb8-b97f-251bad1ed2ad/public

The syllabus in 2018-19 was essentially the same as in 2014-15. But the syllabus then changed slightly in 2019-20. The main difference now is that the last topic from 2014-15 and 2018-19 (on countability and uncountability) is no longer in the syllabus for this module. Instead there is further coverage of equivalence relations and modular arithmetic, and some material on the Euclidean Algorithm for integers (See the new material in lectures 7b and 9b)

The 2019-20 edition of FPM is available at
https://echo360.org.uk/section/513af027-1220-409a-aa7a-711cb7567c33/public

Note that, because of industrial action, not all classes in 2019-20 were given live, so the set of videos is incomplete. However the new material is there, in lectures 7b and 9b.

In 2020-21, all of my teaching was online, due to the pandemic. I put together a set of lecture videos using my recordings from 2018-19 and 2019-20, and asked students to watch these, think about the questions asked in the videos, and attempt some Moodle quizzes to test their understanding. We then had online discussion/Q&A sessions on Teams, and we also held the Workshops online on Teams. The lecture videos are available from
https://echo360.org.uk/section/51b130f8-35dc-4f0e-b91a-3b75279d9d73/public

I have also made a TinyURL for this last set of videos: https://tinyurl.com/fpmvod20-21

Please let me know if there are problems with these links!

Virtually Nottingham

In view of the coronavirus crisis, the University of Nottingham is running many online activities over the summer. This includes “Virtually Nottingham” (see https://www.nottingham.ac.uk/virtual/). There are live talks and recorded catch-up sessions. I contributed a “mini-lecture” to this on Tuesday 7th July 2020 with a new edition of my take on Hilbert’s Hotel, “Beyond Infinity?”. Thanks to Helen Preston for converting my original pdf file (produced using LaTeX) into a suitable PowerPoint presentation.

The main talk was pre-recorded this time, but I was live for the Q&A. I look forward to seeing the combined video in due course via the catch-up page https://www.nottingham.ac.uk/virtual/catch-up/index.aspx

My most popular video

Of all of my videos published anywhere that I know of, the one which has the most views appears to be this one in China:

http://open.163.com/newview/movie/free?pid=MBLPJQES7&mid=MBLPK7DB2

(This may not be viewable in all countries, but is currently working here. It was unavailable for a few months in the UK, but I noticed that it came back after Brexit, so maybe it is unavailable in the EU!)

[Notes added: On 18/6/20 I noticed that I couldn’t watch the video on that site any more: they were asking you to download an app, which I haven’t tried myself. However, as of 2/8/20 it seems to be available directly from that site again.]

It’s the “About this module” introductory class from my old Mathematical Analysis module (2009-10). At the time of writing it has had 261,000 views.

I don’t know why this one is so much more “popular” than all the other videos. But generally, when I have a series (sequence?) of videos, the first one in the series is always the most popular. And I suppose lots of people may search for Mathematical Analysis.

I am very impressed by the work they must have put in to add subtitles (English and Chinese) to lots of my videos! So far I know about subtitled versions (Chinese and English) in China for Mathematical Analysis and for Functional Analysis. If any more turn up, please let me know!

Funny auto-generated subtitles

As I gradually edit subtitles for my Measure Theory videos, I should make a note of some of the funnier errors in the auto-generated subtitles. A challenge (often impossible) for the reader is to try to work out what I really said. But as a hint, the topic is measure theory, including the extended real line, sigma algebras (also known as sigma fields), Borel sets, measures, etc.
These are all genuine attempts by the software to generate text from what I said. But, to be fair, the sound quality of these recordings isn’t great, and I don’t always speak slowly and clearly enough to give the software a real chance.

Here are some of my favourites so far. (There are many more which I didn’t write down and have now forgotten.)

I haven’t kept a systematic set of “solutions” to these, but they are mostly in order of appearance in my Measure Theory videos. So hopefully I can still work out what (I think) I really said if I need to!

Continue reading

Measure Theory videos on YouTube

As newly mentioned in a (new) note added at the end of my previous post
https://explainingmaths.wordpress.com/2020/04/15/subtitles-for-measure-theory-videos/
and also now mentioned at the top of my Measure Theory blog page, the University of Nottingham is now beginning to release my Measure Theory videos on YouTube. See the playlist at
https://www.youtube.com/playlist?list=PLpRE0Zu_k-Bz6I691nDbE0qLsCFKwx5ku

The plan is to release about two episodes per week. If you are impatient, all the videos are already available from the blog page above. At the time of writing, I am still in the process of making subtitles/closed captions available for those. The versions released on YouTube will/do have subtitles available.

Subtitles for Measure Theory videos

I am considering publishing my Measure Theory videos (as available on https://explainingmaths.wordpress.com/measure-theory/ ) on some of the official University of Nottingham channels. However, the latest rules say that University of Nottingham videos must have subtitles available.

The recommendation is that I upload the videos to MediaSpace. There is a facility there to auto-generate captions. I have tried this, and the results were better than I expected, but still very funny! So, as a holiday treat, I have been doing some corrections by hand. I found that it took me several hours to correct the subtitles/captions for the first 14-minute recording. But I think I am getting faster now!

If you look on https://explainingmaths.wordpress.com/measure-theory/  you will see that, of the 15 Measure Theory recordings, parts 6 and 7 now have subtitles available (you click the [cc] closed captions button under the video to turn these on or off). Part 1 also now has a two versions, and the version on MediaSpace has subtitles available.

Please let me know whether you find the subtitles helpful!

Note added 20/4/20: I am continuing to correct subtitles on more episodes, but it is hard work! Gradually more episodes will be available on MediaSpace (and I’ll link to those from the above blog page). Also, the University of Nottingham will release about two episodes a week on YouTube: see the playlist at
https://www.youtube.com/playlist?list=PLpRE0Zu_k-Bz6I691nDbE0qLsCFKwx5ku

Time for a break!

Right, it is now the end of term. Time for the Easter Break, I suppose!

I’m going to miss the online teaching a bit. It’s been quite interesting getting everything working. And it helps that (at least for me) the recordings have started working properly in Microsoft Teams.

I’m mostly happy with my setup now, in case I have to do a lot more of this. Of course, I am broadcasting from my living room, so random family members and/or pets may be audible at times. In particular, our dog Lily sometimes gets overexcited and starts barking, and I can’t do much about that. Fortunately my wife and children can usually help distract her or tempt her out of the room.

Technically, most things are working well now. In today’s class, my Surface Pro was clearly thinking about something else again, because there was some lag between writing with the tablet pen and the digital ink actually appearing. But I did forget to restart the tablet this morning, so I have to take some of the blame! Otherwise, my main technical issues now are caused by the pen’s side button: the way I hold the pen, I find it hard to avoid pressing this button unintentionally. I must have another look to see if I can deactivate it.

I have at least deactivated some of the touch features in DrawBoard PDF. I used to keep double-tapping accidentally and this was set by default to zoom in massively on that portion of the document. (I am happy to do zooming in and out using finger-pinching etc.)

Anyway, things are now going to be relatively quiet on the online live teaching front for the next few weeks.

Microsoft announce fix for problem with recording screensharing in Teams

The latest announcement (quoted/posted by Michel Bosch) showing on
looks promising!
 

Title: Some meeting recordings are not capturing screensharing

User Impact: Some meeting recordings were not capturing screensharing or other videos.

Final status: We’ve confirmed that the fix has been completely deployed the affected environment and our testing and telemetry indicated that the issue has been mitigated.

Scope of impact: Your organization was affected by this event, and any user may have experienced impact if they were viewing a meeting recording that has a screensharing session or other videos.

Start time: Monday, March 16, 2020, 7:00 PM (6:00 PM UTC)

End time: Saturday, March 28, 2020, 9:44 PM (8:44 PM UTC)

Root cause: A decoding issue within the video pipeline resulted in the record meetings feature to not work as expected.

Next steps: – We’re investigating why the increase in traffic degraded the video pipeline to find ways of preventing this issue from reoccurring.

This is the final update for the event.

So maybe it is now fixed! I’m going to test it out.