Homework: I will collect and grade only homework marked with ♠, but it is essential for your understanding to do all problems. I will sometimes give quizzes based on the HW, usually on Fridays, to be announced the previous Monday. References: D = Diestel, HHM = Harris, Hirst & Mossinghof handout.
Recall the Hamilton ring of quaternionsH, defined as the set of allsymbols α = a + bi + cj + dk with a,b,c,d ∈ R endowed with the obvious addition, and with the multipication defined by the relations:
i² = j² = k² = -1 , ij = k = -ji , jk = i = -kj , ki = j = -ik .
This multiplication is non-commutative and (less obviously) it is associative.
Conclude that H is a division ring, meaning every non-zero element is invertible.
Show that our description of H is isomorphic to the ring of complex matrices in M2×2(C) of the form:
a+bi
c+di
-c+di
a-bi
with addition and multiplication of matrices.For a quaternion α = a + bi + cj + dk, we denote the corresponding matrix by M(α).
Show that |α|² = det M(α) .
Now consider the integral quaternions: HZ := { a + bi + cj + dk with a,b,c,d ∈ Z } .
Let Q = { α ∈ HZ such that α-1 ∈ HZ } . Show that Q = { ±1, ±i, ±j, ±k }, the 8-element group of quaternion units.
Let Sn+ = { α ∈ HZ with |α|² = n } .Show that Sn+ is invariant under multiplication by Q : that is, Q Sn+ = Sn+. Conclude that #Sn+ is always divisible by 8.
Furthermore, Sn+ is invariant under conjugation: Sn+ = Sn+.Does this mean that #Sn+ is always divisible by 16 ? Extra Credit: Use the above to give a simple test for when #Sn+ is divisible by 16.
Jacobi's Four-Square Theorem says that #Sn+ = 8 Σd | n d . That is, the number of integer solutions to a² + b² + c² + d² = n is 8 times the sum of the divisors of n . For example, for n = 1 , we have the 4 permutations of the 2 basic solutions (a,b,c,d) = (±1,0,0,0) . This is what we expect, since 8 Σd | n d = 8 × 1 . Verify the theorem for n = 3 by listing all 8(1+3) = 32 solutions (in as efficient notation as possible). Do the same for n = 4 , which has 8(1+2+4) = 56 solutions.
We define Sn ⊂ Sn+ by choosing one element from each Q-orbit in such a way that if α ∈ Sn , then either α or -α ∈ Sn. Verify the following scheme for selecting such a subset. For each β = a + bi + cj + dk, there is one coefficient of different parity from the other three. To get the corresponding element α = mβ ∈ Sn, we multiply β by the element m ∈ Q which moves the different-parity coefficient to be the first coefficient, and makes it positive. For example, if n = 13 and β = 2 + 2i + j + 2k ∈ Sn+, then α = -jβ = 1 - 2j - 2i + 2k.
Recall GL2(q), the general linear group of 2×2 invertible matrices with entries in the clock arithmetic field Fq = Z/qZ , where q is a prime number. We also have the special linear, projective general linear, and projective special linear groups:
SL2(q) = { A ∈ GL2(q) with det(A) = 1 } , PGL2(q) = GL2(q) / Fq× I , and PSL2(q) = SL2(q) / ±I .
Here we take the quotient of GL2(q) by the normal subgroup Fq× I of all invertible scalar matrices, and the quotient of SL2(q) by the normal subgroup ±I of determinant 1 scalar matrices.
Show that the number of elements of GL2(q) , SL2(q) , PGL2(q) , and PSL2(q) is respectively q(q²-1)(q-1) , q(q²-1) , q(q²-1) , ½q(q²-1) .
For Γ a group, define its center Z(Γ) = { g ∈ G | gg' = g'g for all g' ∈ Γ }. Show that Z(SL2(q)} = {±I} and Z(PGL2(q)) = {I, I'}, where I' = diag(1,-1) is a diagonal matrix. Conclude that PGL2(q) = PSL2(q) × C2 , the product of PSL2(q) and the two-element group.
Extra Credit: For which q are SL2(q) and PGL2(q) isomorphic groups? That is, when is there a bijection φ between them which respects multiplication, or equivalently a way of relabelling the multiplication table of one group to obtain the other? For q = 2, both are non-commutative groups of order 6, so they must both be isomorphic to S3. I'm not sure of the full answer myself.
Define the matrices E =
1
1
0
1
F = transpose(E) , and D = diag(d,1) where d ∈ Fq× is a generator of the multiplicative group. Then {E,F} are generators for the group SL2(q), and thus for PSL2(q), and {E,F,D} generate GL2(q) and PGL2(q). Show the above for q = 2, and draw the Cayley graphs. Extra Credit: Show the above for q = 3, and for a general prime q .
Ramanujan graphs Xp,q
Suppose q = 1 mod 4, so that there is an element i ∈ Fq with i² = -1. Define the map Mq : HZ→ M2×2(Fq) by the same formula as before, except we interpret i ∈ Fq instead of i ∈ C , and let Sp,q = Mq(Sp) mod Fq× I, where Sp is from the previous problem and p is some prime. Show that Sp,q has p + 1 elements, and contains all its inverses: if A ∈ Sp,q , then A-1 ∈ Sp,q. Thus the Cayley graph is (p+1)-regular and its directed edges come in opposite pairs, which we may regard as simple undirected edges.
Suppose p = k² mod q for some k. Show that Sp,q ⊂ PSL2(q).In fact, Sp,q is a set of generators of PSL2(q) , and the Cayley graph is non-bipartite.. Suppose p ≠ k² mod q for any k. Then Sp,q is a set of generators of PGL2(q) , and the Cayley graph is bipartite with edges going between the cosets PSL2(q) , I' PSL2(q) ⊂ PGL2(q). Verify these facts for some p,q, or try to prove them in general.
The Ramanujan graph Xp,q is the Cayley graph of PSL2(q) or PGL2(q) with respect to the generators Sp,q. It is k-regular with k = p + 1 and any eigenvalue μ of the adjacency matrix with |μ| ≠ k has |μ| ≤ 2√(k-1) = 2√p , which gives the largest possible spectral gap asymptotically for p fixed, q → ∞. Verify these facts for some p,q.
For the PSL2(q) case, girth(Xp,q) ≥ 2logpq . Thus the chromatic number of G = Xp,q satisfies:
χ(G) ≥ 1 + k / |min(μ)| > 1 + 2(p+1)/√p.
Thus if we let p → ∞ and q ≥ pN with N → ∞, we get graphs with arbitrarily large chromatic number and large girth. Use this to construct a graph with girth(G) ≥ 4 and χ(G) ≥ 4.
The article deals with multigraphs (with loops and multiple edges allowed), but it is easy to turn these into simple graphs. A multi-graph G~ has adjacency matrix A = (avw) where avw = number of edges between v ≠ w , and avv = number of loops at v . The degree of a vertex is the number of loops plus the sum of the edge multiplicities:d(v) = ∑w avw .For example, the 2-regular multi-graph
⊂•—•—•⊃
has adjacency matrix A =
1
1
0
1
0
1
0
1
1
Given a multi-graph G~ with N vertices, D-regular, we can define a simple graph G with EN vertices, D-regular, as follows.Define E as the smallest positive integer such that:
E > avv and Eavv is even for all v , E ≥ avw - 1 for all v ≠ w .
To construct G, we replace each vertex v ∈ G~ with some avv-regular graph on E vertices, and replace each multi-edge between v and w with some avw-regular bipartite graph on E vertices. In our example, we replace each vertex vi with E = 2 vertices vi1,vi2 ; each loop at vi with an edge vi1—vi2 ; and each edge vi—vj with 2 edges vi1—vj1 and vi2—vj2 .The resulting G is a 6-cycle.
Prove that the vertex-expansion g½(G~) , defined in the obvious way for multi-graphs, is equal to the vertex expansion g½(G) of the corresponding simple graph.Since g½(G) is asymptotically equivalent to the expander constant c(G), a family of expander multi-graphs produces a family of expander simple graphs.
Directly compare the various other expansion measures for G~ to those for G : namely g(G~) vs. g(G), μ1(G~) vs. μ1(G) , etc.
Zigzag article: O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the ziz-zag graph product, and new constant-degree expanders, Annals of Mathematics 155 (2002), pp 157-187. Also available on the Math ArXiv.