The following is an approach to the maximality conjecture for S_N\subset S_N^+ which asks what happens to a counterexample S_N\subsetneq \mathbb{G}_N\subsetneq S_N^+ when you quotient C(\mathbb{G}_N)\to C(\mathbb{G}_N)/\langle 1-u_{NN}\rangle. If C(\mathbb{G}_N)/\langle 1-u_{NN}\rangle is noncommutative, you generate another counterexample S_{N-1}\subsetneq \mathbb{G}_{N-1}\subsetneq S_{N-1}^+.}

Most of my attempts at using this approach were doomed to fail as I explain below.

Let \mathbb{G}\subseteq S_N^+ be a quantum permutation group with (universal) algebra of continuous functions C(\mathbb{G}) generated by a fundamental magic representation u\in M_N(C(\mathbb{G})). Say that \mathbb{G} is classical when C(\mathbb{G}) is commutative and genuinely quantum when C(\mathbb{G}) is noncommutative.


Definition 1 (Commutator and Isotropy Ideals)

Given \mathbb{G}\subseteq S_N^+, the commutator ideal J_N\subset C(\mathbb{G}) is given by:


\displaystyle J_N=\langle [u_{ij},u_{kl}]\,\mid\, 1\leq i,j,k,l\leq N\rangle.

The isotropy ideal I_N\subset C(\mathbb{G}) is given by:

\displaystyle I_N=\langle 1-u_{NN}\rangle.

Lemma 1

The commutator ideal J_N\subset C(\mathbb{G}) is equal to the ideal

\displaystyle K_N:=\langle u_{i_1j_1}u_{i_2j_2}u_{i_1j_3},u_{i_1j_1}u_{i_2j_2}u_{i_3j_1}\,\mid \, 1\leq i_k,j_k\leq N,\,j_1\neq j_3,i_1\neq i_3\rangle.

Proof:

\begin{aligned} [u_{i_2j_2},u_{i_3j_1}] & =u_{i_2j_2}u_{i_3j_1}-u_{i_3j_1}u_{i_2j_2} \\ \implies u_{i_1j_1}[u_{i_2j_2},u_{i_3j_1}] & = u_{i_1j_1}u_{i_2j_2}u_{i_3j_1}\qquad (i_1\neq i_3)\\ \implies u_{i_1j_1}u_{i_2j_2}u_{i_3j_1} & \in J_N, \end{aligned}
with a similar statement for u_{i_1j_1}u_{i_2j_2}u_{i_1j_3}.

On the other hand:
\begin{aligned} [u_{i_1j_1},u_{i_2j_2}] & =u_{i_1j_1}u_{i_2j_2}-u_{i_2j_2}u_{i_1j_1} \\ & =u_{i_1j_1}u_{i_2j_2}\sum_{k=1}^Nu_{i_1k}-\sum_{l=1}^{N}u_{i_1l}u_{i_2j_2}u_{i_1j_1} \\ & = u_{i_1j_1}u_{i_2j_2}u_{i_1j_1}+u_{i_1j_1}u_{i_2j_2}\sum_{k\neq j_1}u_{i_1j_1}u_{i_2j_2}u_{i_1k}-\\&u_{i_1j_1}u_{i_2j_2}u_{i_1j_1}\sum_{l\neq j_1}u_{i_1l}u_{i_2j_2}u_{i_1j_1}\\ \implies [u_{i_1j_1},u_{i_2j_2}]& \in K_N \end{aligned}

Proposition 1

The commutator and isotropy ideals are Hopf*-ideals. The quotient C(\mathbb{G})\to C(\mathbb{G})/J_N gives a classical permutation group G\subset S_N, the classical version G\subseteq \mathbb{G}, and the quotient C(\mathbb{G})\to C(\mathbb{G})/I_N giving an isotropy quantum subgroup. If \mathbb{G} is classical, this quotient is the isotropy subgroup of N for the action \mathbb{G}\curvearrowright {1,2,\dots,N}.

Via C(S_N^+)\to C(S_N^+)/J_N, the classical permutation group is a quantum subgroup S_N\subset S_N^+. It is conjectured that for all N it is a maximal subgroup.


Theorem 1 (Wang/Banica/Bichon)

S_N\subseteq S_N^+ is maximal for 1\leq N\leq 5.

Read the rest of this entry »

This is just a little exercise in partial differentiation

Introduction

So, you have a password of length L from an alphabet A. Suppose you have a choice to increase the length, L\to L+1, vs the alphabet size |A|\to |A|+1. Which will make your password more secure?

In this sense we will assume that passwords are subject only to random guesses, and so we make the simple assumption that given the data (|A|,L), the larger the number of possible passwords, the more secure the password.

The set of passwords is \underbrace{A\times A\times \cdots \times A}_{L\text{ times}}. This has size |A|^L.

Simple Numerics

A simple approach is to simply make a table:

An eyeballing of this will tell you that most of time it appears that increasing the length is preferable to increasing the alphabet size. But then again, alphabet size jumps tend to be larger, e.g. 26 to 52, 52 to 62, etc.

Suppose you have a length L password from the alphabet A=\{a,b,\dots,z\}. Are you better off going to length L, or going to the alphabet of size 62, with the capital letters and the numebers? As it happens, it depends on L. For L<5, you should increase the length, but for L\geq 6, you should double the size of the alphabet. This is typical.

Some analysis

Consider a password from a set of |A|^L. Consider the two options, for constant \alpha,\beta:

  • increase the alphabet size: |A|\to \alpha|A|, or
  • increase the password length L\to L+\beta.

If we look what these do to the number of passwords:

  • |A|^L\to (\alpha|A|)^L\to \alpha^L|A|^L vs
  • |A|^{L+\beta}\to |A|^\beta|A|^L,

we are comparing \alpha^L to |A|^\beta, and \alpha,\,\beta are constant, we are comparing the exponential function x\mapsto \alpha^x and the polynomial function x\mapsto x^\beta. While increasing the password length initially can do better, as |A| and particularly L increases, the exponential function speeds past the polynomial function, so eventually, it will make more sense to increase the alphabet size. Our eyeballing has let us down.

For example, from the table above, at |A|=20 and L=14, it doesn’t appear to be even close, here at \alpha=21/20, and \beta=1, you get far more security increasing the length.

But for a fixed |A|=20, there exists a length for which it makes more sense to increase the alphabet by a factor of 21/20. The answer is 61.

So, if you have a length 61 password from an alphabet of size 20, you are better off increasing the alphabet size.

I guess what is relevant here are the following questions: at |A|=26,\,52,\,62,\,94 (adding the special characters), what are the answers?

  • If |A|=26, and L<5, you could increase the length of the password rather than jumping to |A|=52.
  • If |A|=52, and L<23, you could increase the length of the password rather than jumping to |A|=62.
  • If |A|=62, and L<10, you could increase the length of the password rather than jumping to |A|=94.

Going to special characters only makes sense in our framework if there is also a password length condition of 10 or more.

Partial Differentiation

This wasn’t even what I wanted to do here, which was to approximate this question using partial differentiation. In all these questions we are asking about what happens to |A|^L when we change |A| and keep L constant and vice versa. So partial differentiation. I guess the problem is |A| and L are discrete, rather than continuous, but sure x^L and |A|^x are perfectly good functions to differentiate. Let N:=|A|^L.

Even I can differentiate with respect to |A| (in fact, on first go I wrote with respect to L here, and got it wrong!):

\displaystyle \dfrac{\partial N}{\partial |A|}=L\cdot |A|^{L-1}.

We might use some logs to differentiate with respect to L:

\ln(N)=\ln(|A|^L)

\ln(N)=L\cdot \ln(|A|)

\displaystyle \implies \dfrac{1}{N}\dfrac{\partial N}{\partial L}=\ln(|A|)

\displaystyle \implies \dfrac{\partial N}{\partial |A|}=N\ln(|A|)=\ln |A|\cdot |A|^L.

These partial derivatives estimate that if |A|\to \alpha|A| (a change of (\alpha-1)|A| and L\to L+\beta,

\Delta N\approx \dfrac{\partial N}{\partial |A|}\Delta |A|=L|A|^{L-1}(\alpha-1)|A|=(\alpha-1)L|A|^L=(\alpha-1)LN

\Delta N\approx \dfrac{\partial N}{\partial L}\Delta L=\ln |A|\cdot |A|^L\beta=\beta \ln(|A|)N,

so, approximately, we are left comparing \beta \ln(|A|) and (\alpha-1)\cdot L. And here we see \ln(|A|) vs L… eventually L\gg \ln(|A|) if both grow, giving us the same answer as before.

Consider the symmetric group S_N. Let \mathrm{fix}_N \in C(S_N) count the number of fixed points of a permutation \sigma\in S_N. Where X\sim \mathrm{Poi}[1], we have that for a random permutation \xi_N\in S_N chosen with respect to the uniform distribution, the \mathrm{fix}_N converges in distribution to X in the sense that:

\displaystyle \lim_{N\to \infty}\mathbb{P}[\mathrm{fix}_N(\xi_N)=m]=\mathbb{P}[X=m].

In this note we will look at the distribution in the case where the uniform distribution is conditioned on \xi_N(1)=1.

Theorem

Let \xi_N\in S_N be chosen according to the distribution uniform on permutations for which one is a fixed point. The number of fixed points has distribution 1+\mathrm{Poi}[1] in the sense that, where X\sim \mathrm{Poi}[1],

\displaystyle \lim_{N\to \infty}\mathbb{P}[\mathrm{fix}_N(\xi_N)=m]=\mathbb{P}[X=m-1].

Proof: What can be shown, ostensibly from stuff from the quantum permutation side of the house is that, where h_N is integration against the uniform distribution, and \widetilde{h_N} is integration against the uniform distribution on permutations with one a fixed point, that, for k<N:

\displaystyle \widetilde{h_N}(\mathrm{fix}_N^k)=h_N(\mathrm{fix}_N^{k+1})=B_{k+1},

the (k+1)-st Bell number. Now consider the moments of 1+X:

\displaystyle \sum_{t=0}^\infty t^k\mathbb{P}[1+X=t]=\sum_{t=0}^\infty t^k\mathbb{P}[X=t-1]

\displaystyle =\sum_{t=1}^\infty t^k\frac{e^{-1}}{(t-1)!}

\displaystyle \underset{s=t-1}{=}\sum_{s=0}^\infty(s+1)^k\frac{e^{-1}}{s!}

\displaystyle =\sum_{s=0}^\infty\sum_{i=0}^k\binom{k}{i}s^i \frac{e^{-1}}{s!}

\displaystyle =\sum_{i=0}^k\binom{k}{i}\sum_{s=0}^\infty s^i\frac{e^{-1}}{s!}

\displaystyle =\sum_{i=0}^k \binom{k}{i} B_k=B_{k+1},

using the fact that the Bell numbers are the moments of that Poisson distribution and the standard recurrence for the Bell numbers.

Local vs Global Conditioning of Quantum Permutations

In the quantum case we define

\displaystyle \mathrm{fix}_N:=\mathrm{Tr}(u),

where u\in M_N(C(S_N^+)) is the fundamental magic representation. The moments of \mathrm{fix}_N with respect to the Haar state are the Catalan numbers and it follows that the law of \mathrm{fix}_N is a Marchenko-Pastur distribution, with density

\displaystyle \dfrac{1}{2\pi}\sqrt{\frac{4}{t}-1}:

Note that when we measure the Haar state with some finite spectrum version of \mathrm{fix}_N we find:

  • the probability of finding an integer number of fixed points is zero, and
  • independently of N, the probability of finding more than four fixed points is zero.

In the classical case above when we chose the permutation uniformly from those who fix one, there are two ways of viewing it:

  • we pick an element of S_N that fixes one, OR
  • we consider the isotropy subgroup S_{N-1}\subset S_N and choose our permutation from S_{N-1}.

Classically, these are the same thing. In the quantum case these two things can be interpreted differently. The second case is quite clear in the quantum case. For N>4, we take the isotropy S_{N-1}^+\subset S_N^+ via the quotient C(S_N^+)\to C(S_N^+)/\langle1-u_{11}\rangle.

The analogue of the uniform distribution on S_{N-1}\subset S_N here is the Haar idempotent h_{C(S_{N-1}^+)}\circ \pi. Note this maps \mathrm{fix}_N to 1+\mathrm{fix}_{N-1}. Now, using the fact that h_{C(S_{N-1}^+)}(\mathrm{fix}_{N-1})=C_k, the Catalan number, we have that the moments of \mathrm{fix}_N with respect to h_{C(S_{N-1}^+)}\circ \pi is the binomial transform of the Catalan numbers (the binomial transform of B_1,\dots,B_k is B_{k+1}). It follows, using similar stuff to the above, that the distribution of \mathrm{fix}_N with respect to h_{C(S_{N-1}^+)}\circ \pi is just a shifted version of Marchenko–Pastur:

I guess this is marginally more interesting than the unshifted version.

Now, what about an analogue of “we pick an element of S_N that fixes one”. So if we take the Haar state and measure the observable u_{11}\in C(S_N^+) that asks of a quantum permutation, does it fix one, we get, conditioned on this, the state:

\displaystyle h_1(f):=N\cdot h(u_{11}fh_{11})=\dfrac{h(u_{11}fu_{11})}{h(u_{11})}\qquad (f\in C(S_N^+)).

And, it turns out, as above, using stuff from the quantum permutation side of the house:

\displaystyle h_1(\mathrm{fix}_N^k)=h(\mathrm{fix}_N^{k+1})=C_{k+1}.

Quite quickly from here we find that the density of the distribution of \mathrm{fix}_N with respect to h_1 is

\displaystyle \frac{t}{2\pi}\sqrt{\frac{4}{t}-1}

This is so interesting:

  • it doesn’t change the support — we still find between 0 and 4 fixed points,
  • we have a new symmetry about \mathrm{fix}_N=2, we had another unexpected symmetry here.
  • the mean jumps from one to two, that is not unexpected, but
  • the mode jumps from zero to two!
  • even though we have observed one to one, there can still be less than one fixed point when we measure… and this happens with probability \approx 1/5.

The next obvious question is what happens with:

\displaystyle f\mapsto \dfrac{h_1(u_{22}fu_{22})}{h_1(u_{22})}\qquad (f\in C(S_N^+))

Epilogue?

So what about this local vs global conditioning? Well, no matter what subsequent measurements are made to h_{C(S_{N-1}^+)}\circ \pi, we will always find that one is a fixed point. That conditioning is ‘global’.

This is not the case with h_1, and why the support of the law is not bounded above one, like that of the globally conditioned h_{C(S_{N-1}^+)}\circ \pi. In fact, there is a non-zero probability that h_1 is observed to fix two but then subsequently not fix one anymore. That conditioning was only local: the probability that h_1 fixes one is 100%… but subsequent measurements can destroy that conditioning… it is only local.

Remaining Assessment

Expect updates early next week giving information about the final two assessments.

Oh, and there is one more round to go in the MCQ with cash prizes available.

Written Assessment Solutions

See here:

Week 9

We finished our work on Laplace’s Equation and then started – and finished looking at the Heat Equation.

Students who missed the lecture on Wednesday can catch up with the Lecture videos on Canvas.

We looked at Lab 7, based on Laplace’s Equation

Here on is provisional on when I go on paternity leave

Week 10

We will have tutorial time towards the 40% Written Assessment on Tuesday and Wednesday.

For Lab 8, the theory is examinable in the final written assessment but the VBA not examinable outside of Autumn repeat exam.

If I go on paternity leave a number of videos will have been produced:

  • an intro to Lab 8,
  • and outro to Lab 8,
  • four hours and 10 minutes of worked examples

You will be instructed to replace your four hours of lab and lecture time with engagement with these materials.

Week 11

I will almost certainly be on paternity leave. Your VBA 2 assessment will take place and it will be invigilated. NOTE DME2D will have their assessment at A285 and NOT B151 (at the usual time slot)

You will be instructed to replace your two hours of lecture time with engagement with the four hours and 10 minutes of worked examples.

Week 12

I will probably be on paternity leave. Your Written Assessment 2 will take place in the Melbourne.

You will be instructed to replace your Tuesday lecture time with engagement with the four hours and 10 minutes of worked examples.

If I am back from paternity leave your Tuesday lecture will be a tutorial.

Study

Study should consist of

  • doing exercises from the notes
  • completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

Students who did not take advantage of the ample tutorial time this week (and those who did) are free to email me questions over Easter. Please send screenshots of your attempts.

15% Assignment 2

Assignment 2 is in the manual. It could be started now.

Week 9

We had a bumper week of Chapter 3 tutorials.

Week 10

I will probably not be on paternity leave yet, in which case we will have a final Chapter 3 tutorial on Tuesday before doing systems of differential equations on Wednesday and Thursday, with some tutorial time possible on Thursday.

If I do go on paternity leave, a colleague of mine is due to take ye. If it happens that this cover is late, only coming on Thursday, I will have pre-recorded lectures on systems of differential equations which you should watch instead of the lectures on Tuesday and Wednesday. Then my colleague will do a Chapter 3/ systems of differential equations tutorial with you on Thursday.

Week 11

I will be on paternity leave.

Tuesday will be a tutorial on systems of differential equations and then ye will work on double integration and when we finish that section we will have tutorials.

Week 12

I might be back from paternity leave.

Tuesday will be a tutorial on double integration and then ye will work on triple integration. When finished ye will have tutorial time on that topic.

Week 13, Review Week

We will have tutorial time.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

Again, things are more serious now as we start Chapter 3. We must work hard on this material:

  1. because without doing so you could be very, very lost on 15% Assignment 2 (and 35% exam question), and
  2. because if you are going into Level 8 Structural Engineering it will be assumed that you are competent with the Chapter 3 material

Students who missed today, Thursday 14 March should really watch the videos covering Section 3.4 before Tuesday.

Week 8

The week will be focused on finishing the part of Chapter 3 examinable in Assignment. We did this, by looking at partial fractions, the inverse Laplace transform, and the application of the Laplace Transform to differential equations. We managed some tutorial time on Wednesday but the double was all lecture.

15% Assignment 2

Assignment 2 is in the manual, has a hand-in date of 12 April, and once you have had some tutorial time, you can start this.

Week 9

This will be a bumper week of Chapter 3 tutorials.

Week 10

I will probably not be on paternity leave yet, in which case we will have a final Chapter 3 tutorial on Tuesday before doing systems of differential equations on Wednesday and Thursday, with some tutorial time possible on Thursday.

If I do go on paternity leave, a colleague of mine is due to take ye. If it happens that this cover is late, only coming on Thursday, I will have pre-recorded lectures on systems of differential equations which you should watch instead of the lectures on Tuesday and Wednesday. Then my colleague will do a Chapter 3/ systems of differential equations tutorial with you on Thursday.

Week 11

I will be on paternity leave.

Tuesday will be a tutorial on systems of differential equations and then ye will work on double integration and when we finish that section we will have tutorials.

Week 12

I might be back from paternity leave.

Tuesday will be a tutorial on double integration and then ye will work on triple integration. When finished ye will have tutorial time on that topic.

Week 13, Review Week

We will have tutorial time.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

Assessment Corrections

The VBA results have been released and all groups will have one chance to get some quick feedback on what they submitted. If this doesn’t or hasn’t worked for you, please feel free to send an email.

I have set a target of Week 9 for your Written Assessment results.

Week 8

We continued with Chapter 2, describing the implementation of the Gauss-Seidel method. We have stopped (geddit) short of giving the stopping rule, ye will see this on Tuesday.

We did Lab 6 on boundary value problems, and it is relevant for VBA Assessment 2 in Week 11.

Week 9

We will finish our work on Laplace’s Equation and then start looking at the Heat Equation.

We will look at Lab 7, based on Laplace’s Equation

Because every lab counts, the Bank Holiday labs of DME2A are going to be rescheduled to Tuesday: on Tuesday March 19 we will have the following:

  • DME2A, 14:40-16:20, DME2E 16:20-18:00, A285

Here on is provisional on when I go on paternity leave

Week 10

We will finish our work on the Heat Equation and have tutorial time on Wednesday.

For Lab 8, the theory is examinable in the final written assessment but the VBA not examinable outside of Autumn repeat exam.

If I go on paternity leave a number of videos will have been produced:

  • a video covering the last lecture of new material,
  • an intro to Lab 8,
  • and outro to Lab 8
  • two hours and 40 minutes of worked examples

You will be instructed to replace your four hours of lab and lecture time with engagement with these materials.

Week 11

I will almost certainly be on paternity leave. Your VBA 2 assessment will take place and it will be invigilated.

You will be instructed to replace your two hours of lecture time with engagement with the two hours and 40 minutes of worked examples.

Week 12

I will probably be on paternity leave. Your Written Assessment 2 will take place in the Melbourne.

You will be instructed to replace your Tuesday lecture time with engagement with the two hours and 40 minutes of worked examples.

If I am back from paternity leave your Tuesday lecture will be a tutorial.

Assessment

See Canvas for the assessment schedule.

Study

Study should consist of

  • doing exercises from the notes
  • completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

Again, things are more serious now as we start Chapter 3. We must work hard on this material:

  1. because without doing so you could be very, very lost on 15% Assignment 2 (and 35% exam question), and
  2. because if you are going into Level 8 Structural Engineering it will be assumed that you are competent with the Chapter 3 material

Assessment 1 Remarks

With a mountain of other corrections to get done, I have made very few remarks on individual reports. Please look at these remarks to see where most people went wrong:

Week 7

On Monday, we had a final Chapter 2 tutorial.

Then the rest of the class will be given over to partial fractions and then the inverse Laplace transform.

On Wednesday and Thursday we had some tutorial time on partial fractions and the cover up method.

Week 8

The week will be focused on finishing Chapter 3.

15% Assignment 2

Assignment 2 does not yet have a hand-in date (watch this space). Assignment 2 is in the manual, and once you finish the exercises in the manual you will be in a great position to start.

Week 9

This should be a bumper week of Chapter 3 tutorials if we have finished Chapter 3.

The below is very much provisional

Week 10

We will do systems of differential equations.

Week 11

We will work on double integration and when we finish that section we will have tutorials.

Week 12

We will work on triple integration. When finished we will have tutorial time on that topic.

Week 13, Review Week

We will go through an exam paper, answer questions, and have tutorial time as appropriate.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

Week 7

We finished looking at boundary value problems and then started Chapter 2, Partial Differential Equations.

We had Written Assessment 1.

In VBA we finished what we are doing on Lab 4 and then looked at Lab 5. Lab 5 is not examinable as VBA but the theory of it, the theory of RK, that is examinable in Written Assessments 1 and 2. Some students instead used the time to prepare for Written Assessment 1.

Assessment Corrections

Let us set a target of Week 8 for your VBA results and Week 9 for your Written Assessment results.

Week 8

We will continue with Chapter 2.

Lab 6 is on boundary value problems and relevant for VBA Assessment 2 in Week 11.

Week 9

Section 2.1

Lab 7

Because every lab counts, the Bank Holiday labs of DME2A are going to be rescheduled to Tuesday: on Tuesday March 19 we will have the following:

  • DME2A, 14:40-16:20, DME2E 16:20-18:00, A285

Here on is provisional:

Week 10

Section 2.2

Lab 8 (theory examinable in final written assessment but VBA not examinable outside of Autumn repeat exam)

Week 11

Finish Section 2.2 and then tutorial time

Assessment

See Canvas for the assessment schedule.

Study

Study should consist of

  • doing exercises from the notes
  • completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

I am now available to help students at all levels in the Glanmire and Bishopstown areas.

Contact me on  086-1089437 or jpmccarthymaths@gmail.com.