New directions in additive combinatorics: day 2

I forgot to write the report last night as I got carried away with some mathematical discussions with a colleague; better late than never! First, I missed two talks today, due to forgetting the time mainly when I was talking with Simeon Ball about (q+1)-arcs of projective spaces. We’ve ended up doing something, and that’s what has occupied me in the last while. Anyway, Aart Blokhuis and Simeon Ball began their mini-course on “Polynomial methods in finite geometry” yesterday, beginning with blocking sets. What I took away was that Hasse derivatives do something that the standard derivatives do not, but I’m still at a bit of loss why they are so successful in capturing the information about directions determined by a function. After morning tea, Lev spoke on the state of the art on quadratic residues and difference sets. I found this harder to follow, but there were some very interesting tables on computer output where some strange things happen. Five primes come out as solutions on a test of trillions of integers. Luckily we will have the slides posted on the webpage so I can remember exactly what these computations were about. Then Stefaan De Winter gave a beautiful talk on partial difference sets, where he and his co-authors have knocked off most of Ma’s list of parameters on at most 100 vertices. This was very impressive. There’s more on this talk over at Peter Cameron’s blog.

In the afternoon, Ben Green gave the second part of his series; this time on Rusza’s results and various improvements and advances thereof. Today (the third day) he will be giving a colloquium in the mathematics department here. As I said above, I lost track after afternoon tea and missed Ken Smith and Jim Davis’s talks; but then regained my composure and attended Oktay Olmez’s talk on directed strongly regular graphs and partial geometric designs; a great finish to another fantastic day at NUS!

Advertisements

New directions in additive combinatorics: day 1

I know I’m not going to be able to keep this up, but I felt I needed to report on the first day of what is turning out to be an excellent conference at the National University of Singapore. This will leave me with the issue that my reporting of subsequent talks in this conference will not be at the same degree as I will present here, even though they might be of the same standard. So I apologise in advance.

First of all, we kicked off with Ben Green’s first lecture in his series on Finite Field Models (and in particular, to problems simulating outstanding problems in additive combinatorics). What was quite novel about this talk was that the news about the Sunflower Conjecture was placed in the centre of his talk: it was a news breaking talk. Add to this Tao’s reformulation of the Croot-Lev-Pach principle, and it really felt like everything we were being told was hot off the press. The next talk was by Peter Cameron, and he spoke about some problems to do with synchronisation (for automata and permutation groups). I was reminded that we still not have an idea what is going on with S_n acting on k-subsets for k>3. Something perhaps worth thinking about when I have time. Then Kai-Uwa Schmidt spoke about his recent results on o-polynomials; which are the functions you get when you coordinatise a hyperoval in a finite Desarguesian projective plane. I remember seeing his papers on the arxiv some time ago, so it was nice to see it all placed in context: some very nice recent results there on a problem that hasn’t seen many advances for a while. There were two citations of SymOmega in his talk: one of them was a comment I made about hyperovals, the second was a comment from Tim Penttila.

In the afternoon, Peter Keevash set the scene for his series on designs. He gave his big result of yesteryear, and all of its many consequences: Wilson’s Conjecture and the Existence Conjecture. He has only just outlined the strategy behind the proof, so the best is yet to come. I then gave the first talk after afternoon tea: it was a tad rushed, but I managed to get to the end. After my talk was a summary of the EKR problem for finite polar spaces by Klaus Metsch. Klaus has produced many interesting results in this area of late, and often by applying the Hoffmann bound to linear combinations of adjacency matrices of an association scheme! He showed that good old finite geometry techniques pair up well with the algebraic combinatorial techniques, when both cannot do the job alone.

There might be more reporting tomorrow … if I have time.

 

 

 

 

Marketing campaign trivialises research

All the universities in Australia are having their “Open Day” events, which usually consists of a mix of a children’s carnival plus some information on courses and degrees for secondary school students. Just when you thought the marketing fraternity could not get lower, the geniuses at La Trobe University have introduced an instagrants campaign. The idea was that if you took a selfie in front of a designated research poster, then $150 would be given by the university to that research area. I wonder how long it will take the other universities to come up with this idea too!

An interesting formula in combinatorial representation theory

Some research projects give you more than others in terms of reward and enjoyment. I’ve been very lucky to have been part of an enthusiastic team in Stephen Glasby, Luke Morgan, and Alice Niemeyer on a problem concerning automorphisms of p-groups; but more of that in a later post. In our investigations, we needed to know some basic data on polynomial representations of the general linear group GL(d,p). Consider the natural action of GL(d,p) on the tensor power T^n V where V is the vector space \mathbb{F}_p^d. It is a well-known result of Schur (and I won’t elaborate on it here) that if p>n, then we can parameterise the irreducible GL(d,p)-modules by the partitions of n. (Well actually, the characteristic 0 analogue is due to Schur, but it was folklore for a long time until a paper of Benson and Doty). For example, let us take the tensor square (n=2). If p is odd, then it is a classical fact that T^2 V breaks up into two smaller GL(d,p)-modules, namely

T^2 V \cong S^2 V \oplus A^2 V

where S^2 V is the symmetric square of V and A^2 V is the alternating square of V. The partitions here are the trivial partitions of the number 2. The partition (1,1) corresponds to A^2V and the partition (2,0) corresponds to S^2 V.

We are interested in something slightly more difficult. We actually want to know the irreducible constituents of the free Lie algebra L(V) generated by V. The connection between the two settings is cute. Define a bracket operation on the tensor algebra T(V) by [u,v] = u\otimes v-v\otimes u. Then we obtain a graded Lie algebra L(V)=\bigoplus_{n=1}^\infty L_n where each L_n is just L(V)\cap T^n(V). Each L_n then breaks up into irreducibles indexed by partitions of n, except we don’t know the multiplicities of each submodule. Write V^\lambda for the GL(V)-module corresponding to a partition \lambda of n. Note that the multiplicities here could be 0, that is, the V^\lambda  may not even appear. So think of the partitions now as being a superset of parameterising objects. For n=2, it is well known that L_2(V)\cong A^2V, that is, the symmetric square vanishes (just think of what the Lie bracket does here!).

Well I came across a beautiful result of Kraśkiewicz and Weyman that yields the answer. Consider standard tableaux of type \lambda. As an example, consider the partition (2,2,1,1) of the number 6. Then there are 9 possible standard tableaux:

tableauxA descent is an entry i of a standard tableaux such that i+1 appears in a row lower than it. So for example, 2, 4, and 5 are descents of the first tableau above. The major index of a standard tableaux is the sum of its descents. So for our nine tableaux we have major indices 11, 10, 9, 13, 9, 8, 12, 7, 11 accordingly. Then the magic number for the multiplicity of a V^\lambda is the number of standard tableaux of type \lambda that have major index congruent to 1 modulo n. In our example, there are two such young tableaux, the 4th and 8th one. So V^\lambda has multiplicity 2.

Peace and quiet

In a colleague’s research grant proposal, under a heading about resources and equipment, he wrote something along the lines of:

All a mathematician needs is some paper, some pens, good access to online journals, and most importantly, a quiet place to work.

Of course, we also rely on good coffee, a buzzing environment of enthusiastic colleagues, natural light, and administrative support.

For other disciplines, lab equipment and technicians are extremely important, and not having the best equipment would severely cripple an experimental chemist, for example. So if you needed to find a way to stifle the progress of a group of mathematicians, what changes to their work environment would you make?

  • You could take their blackboards/whiteboards away, but they might be just as happy with their endless supply of foolscap paper.
  • You could take their paper away. This is difficult to do, as paper is easy to buy and very cheap. Mathematicians would bring their own paper, or just write on their desks and other flat surfaces.
  • You could take their pens away. Again, pens are cheap and easy to buy, so it would be difficult to outlaw pens in the workplace. And anyway, where would you draw the line? Pencils, chalk, and crayons would have to be outlawed too.

Perhaps the best way is to create tension within the group, and somehow put in place a situation where the ambient noise in the workplace was disruptive and unpredictable. For those who wear headphones, they would need to be distracted by visible movement in their periphery. How can this be done effectively? Even more insidiously, we could create an environment that would increase the rate of infection due to colds, influenza, or other airborne viruses. Have you tried to solve a difficult mathematics problem whilst your head is congested and your joints feel like jelly?

So I leave the question to you: how can you create a work environment that not even a resource-minimalist mathematician can bear? To summarise:

  1. it needs to organically create tension between colleagues,
  2. it needs to be cost efficient,
  3. it needs to be noisy,
  4. it needs to have visual distractions,
  5. it needs to foster airborne viruses.

I can only think of one solution to this problem. What is your solution?

Some Tikz pictures

Most LaTeX-ers know about Tikz, which allows the user to create images in LaTeX without having to embed images created from an external program. The main advantages are that

  1. The ambient LaTeX fonts are used in the image, so labels and such conform to the ambient style of the document.
  2. The size of the .tex file is kept small, since it is only text you are creating.
  3. It yields a picture that is smooth and that looks good upon zooming in (i.e., the resolution of the picture is good).
  4. It is functional code so that you can automate the drawing of many pictures by giving commands such as “draw a line between these two points”.

The main disadvantage, is that there is a steep learning curve. The best way to learn is through examples, and even though I’m still a hack, my tikz code has improved via my copying segments of other people’s code. For geometry, there isn’t much out there, so I thought that I would dump some images here. Below are some Tikz pictures of configurations in finite geometry that I’ve collected and think should be available for everyone else to use. A big thanks to Stephen Glasby who went to a lot of trouble to make the two generalised hexagons of order 2. If you have suggestions on how I can simplify my code, please let me know.

Desargues’ configuration, two ways

Desargues1

\begin{tikzpicture}
\tikzstyle{point1}=[ball color=cyan, circle, draw=black, inner sep=0.1cm]
\tikzstyle{point2}=[ball color=green, circle, draw=black, inner sep=0.1cm]
\tikzstyle{point3}=[ball color=red, circle, draw=black, inner sep=0.1cm]
\node (v1) at (0,8) [ball color=blue, circle, draw=black, inner sep=0.1cm] {};
\node (v2) at (0,6) [point1] {};
\node (v3) at (2,5.5) [point1] {};
\node (v4) at (1.5,4) [point1] {};
\node (v5) at (0,0) [point2] {};
\node (v6) at (2.75*2,8-2.75*2.5) [point2] {};
\node (v7) at (1.5*1.5,8-1.5*4) [point2] {};
\draw (v1) -- (v2) -- (v5);
\draw (v1) -- (v3) -- (v6);
\draw (v1) -- (v4) -- (v7);
\draw (v2) -- (v3) -- (v4) -- (v2);
\draw (v5) -- (v6) -- (v7) -- (v5);
\node (v8) at (intersection of v2--v3 and v5--v6) [point3] {};
\node (v9) at (intersection of v2--v4 and v5--v7) [point3] {};
\node (v10) at (intersection of v3--v4 and v6--v7) [point3] {};
\draw (v3) -- (v8) -- (v6);
\draw (v4) -- (v9) -- (v7);
\draw (v4) -- (v10) -- (v7);
\draw (v8) -- (v9) -- (v10);
\end{tikzpicture}

… and the second one:
Desargues2

\begin{tikzpicture}
\tikzstyle{point} = [ball color=black, circle,  draw=black, inner sep=0.1cm]
\foreach\x in {0, 72, 144, 216, 288}{
    \begin{scope}[rotate=\x]
      \coordinate (o1) at (-0.588, -0.809);
      \coordinate (o2) at (0.588, -0.809);
      \coordinate (c1) at (-1.1, 4.6);
      \coordinate (c2) at (1.1, 4.6);
      \coordinate (o3) at (0, 3.236);
      \draw[color=black] (o3) -- (3.236*-0.588, 3.236*-0.809);
      \draw[color=blue] (o1) ..  controls (c1) and (c2) ..  (o2);
     \end{scope}
}
\foreach\x in {0, 72, 144, 216, 288}{
    \begin{scope}[rotate=\x]
      \coordinate (o2) at (0.588, -0.809);
      \coordinate (o3) at (0, 3.236);
      \fill[point] (o2) circle (2pt);
      \fill[point] (o3) circle (2pt);
    \end{scope}
}
\end{tikzpicture}

The generalised quadrangle of order 2

I think Gordon gave me the original tikz code for this and then I tweaked it.
GQ2

\begin{tikzpicture}
\tikzstyle{point}=[ball color=magenta, circle, draw=black, inner sep=0.1cm]
\foreach \x in {18,90,...,306}{
\node [point] (t\x) at (\x:2.65){};
}
\foreach \x in {54,126,...,342}{
\draw [color=blue, double=green](\x:1cm) circle (1.17557cm);
}
\fill [white] (0,0) circle (1cm);
\foreach \x in {54,126,...,342}{
\node[point] (i\x) at (\x:1cm) {};
\node[point] (o\x) at (\x:2.17557cm) {};
}

\draw [color=blue,double=green] (t90)--(o126)--(t162)--(o198)--(t234)--(o270)--(t306)--(o342)--(t18)--(o54)--(t90);
\draw (t90)--(i270)--(o270);
\draw (t162)--(i342)--(o342);
\draw (t234)--(i54)--(o54);
\draw (t306)--(i126)--(o126);
\draw (t18)--(i198)--(o198);
\end{tikzpicture}

The two generalised hexagons of order 2

These pictures were originally drawn by Schroth in his 1999 paper, and then appeared in Burkard Polster’s book “A geometrical picture book”.

GH2_1

\begin{tikzpicture}
    \foreach\n in {0, 1,..., 6}{
      \begin{scope}[rotate=\n*51.4286]
        \coordinate (a0) at (10,0);
        \coordinate (b0) at (7,0);
        \coordinate (c0) at (1.45,0);
        \coordinate (d0) at (4.878,-0.4878);
        \coordinate (e0) at (2.1729,0.37976);
        \coordinate (f0) at (1.45,0.612);
        \coordinate (g0) at (2.78,-0.585);
        \coordinate (h0) at (4.074,0.7846);
        \coordinate (i0) at (6.0976,2.9268);
        \foreach\k in {1, 2,..., 6}{
          \foreach\p in {a,b,c,d,e,f,g,h,i}{
            \coordinate (\p\k) at ($ (0,0)!1! \k*51.4286:(\p0) $);
          }
        }
        \draw[thick,blue] (a0)--(b0)--(c0);
        \draw[thick,blue] (d0)--(e0)--(f0);
        \draw[thick,black] (g0)--(h0)--(i0);
        \draw[thick,black] (a0)--(g1)--(a3);
        \draw[thick,green] (i0)--(d1)--(i2);
        \draw[thick,black] (c0)--(g3)--(d3);
        \draw[thick,color=purple] (b0) .. controls (5.7,-1.8) and (4.6,-2.2)
           .. (h6) .. controls (1.5,-3.2) and (-1,-2.4) .. (e4);
        \draw[thick,black] (b0)--(h0)--(e2);
        \draw[thick,purple] (f6)--(c0)--(f0);
        \foreach\k in {1, 2,..., 6}{
          \foreach\p in {a,b,c,d,e,f,g,h,i}{
            \draw[fill] (\p\k) circle [radius=0.12];
          }
        }
     \end{scope}
   }
\end{tikzpicture}

 

GH2_2

\begin{tikzpicture}
  \foreach\n in {0, 1,..., 6}{
      \begin{scope}[rotate=\n*51.4286]
        \coordinate (a0) at (85,0);
        \coordinate (b0) at (55,0);
        \coordinate (c0) at (12.5,0);
        \coordinate (d0) at (8.5,1.3);
        \coordinate (e0) at (16.2,9);
        \coordinate (f0) at (30,14.3);
        \coordinate (g0) at (26.6,17.0);
        \coordinate (h0) at (26.3,22.4);
        \coordinate (i0) at (29.5,28);
        \foreach\k in {1, 2,..., 6}{
          \foreach\p in {a,b,c,d,e,f,g,h,i}{
            \coordinate (\p\k) at ($ (0,0)!1! \k*51.4286:(\p0) $);
          }
        }
        \draw[thick,black] (a0)--(e1)--(a3);
        \draw[thick,green] (b0)--(h0)--(b2);
        \draw[thick,purple] (f0)--(g0)--(f1);
        \draw[thick,blue] (h0)--(i0)--(a1);
        \draw[thick,purple] (h6)--(c0)--(d0);
        \draw[thick,purple] (f0)--(e0)--(i3);
        \draw[thick,black] (b0)--(i6)--(g6);
        \draw[thick,color=blue] (g0) .. controls (27,2) and (17,-5)
           .. (d6) .. controls (-7,-5) and (-5,-5) .. (c3);
        \draw[thick,color=blue] (c0) .. controls (16,3) and (17,5)
           .. (e0) .. controls (15,13) and (8,15) .. (d1);
        \foreach\k in {1, 2,..., 6}{
          \foreach\p in {a,b,c,d,e,f,g,h,i}{
            \draw[fill] (\p\k) circle [radius=1.1];
          }
        }
      \end{scope}
  }
\end{tikzpicture}

The first is the Split Cayley hexagon as it is usually given, whilst the second is its dual.

 

The projective plane of order 2

Fano

\begin{tikzpicture}
\tikzstyle{point}=[ball color=cyan, circle, draw=black, inner sep=0.1cm]
\node (v7) at (0,0) [point] {};
\draw (0,0) circle (1cm);
\node (v1) at (90:2cm) [point] {};
\node (v2) at (210:2cm) [point] {};
\node (v4) at (330:2cm) [point] {};
\node (v3) at (150:1cm) [point] {};
\node (v6) at (270:1cm) [point] {};
\node (v5) at (30:1cm) [point] {};
\draw (v1) -- (v3) -- (v2);
\draw (v2) -- (v6) -- (v4);
\draw (v4) -- (v5) -- (v1);
\draw (v3) -- (v7) -- (v4);
\draw (v5) -- (v7) -- (v2);
\draw (v6) -- (v7) -- (v1);
\end{tikzpicture}

Parameters of generalised hexagons

Up to duality, there are two known families of finite (thick) generalised hexagons:

  1. the Split Cayley hexagons of order (q,q) related to the Dickson exceptional groups G_2(q).
  2. the Twisted Triality hexagons of order (q,q^3) related to the Steinberg exceptional groups \,^3D_4(q).

Since I will only consider generalised hexagons up to duality, I will assume that the order (s,t) of a given one has s\le t. The parameter s is one less than the number of points on a line, and t+1 is the number of lines on a point. To date, we do not know much about the possible values of these positive integers s and t. Here is what we know:

  • s\le t^3 and t\le s^3 (Haemers and Roos, 1981)
  • s^2+st+t^2 divides s^3(s^2t^2+st+1) (from the multiplicities of the eigenvalues of the point graph).
  • There are two (up to duality) generalised hexagons with s=2 and they have t\in\{2,8\} respectively (Cohen and Tits 1985).

We do not know that s+1 divides t+1, even though the known examples satisfy this simple divisibility relation.

Here is a cool number theoretic thing I’ve observed recently, but I can’t (quite yet) prove that it is true:

Claim: If s,t are integers greater than 1, satisfying s+1 \mid t+1 and s^2+st+t^2\mid s^3(s^2t^2+st+1), then apart from a small finite number of exceptions, we have t=s or t=s^3.

I claim that the only exception is (s,t)=(14,224).

We know that the known examples satisfy the extra relation s+1\mid t+1, and it is conceivable that such a simple looking relation holds for generalised hexagons and that it arises for some combinatorial reason. It’s simplicity is the only reason to believe that it might hold, but wouldn’t it be cool if every generalised hexagon satisfied it?

 

Groups, Computation & Geometry at Pingree Park

Last week, I attended an excellent conference “Groups, Computation and Geometry” at the Pingree Park Conference Centre in the Colorado mountains. It was organised magnificently by Peter Brooksbank, Alexander Hulpke, Bill Kantor, Tim Penttila, and James Wilson. Pingree Park is at 9,000 feet (2,700 metres) and I did have headache on the last two days. My trip started badly with a case of gastro, but luckily I had arrived some three days before the conference, so by the second day of talks, I was feeling much better. My 50 minute talk had to be rescheduled to the Friday of the conference, because of this. Apart from your’s truly, the invited talks were given by Colva Roney-Dougal, Şükrü Yalçınkaya, Eric Moorhouse, and Simon Blackburn. Colva spoke about using pregroups to solve problems in combinatorial group theory, mainly word problems, and getting around in a Van Kampen diagram. Şükrü waved the flag for the computational group theorists and spoke on black-box recognition of classical groups. Eric waved the geometry flag and spoke on p-ranks of incidence matrices, and in particular, on ways to attack the “prime-order projective plane implies Desarguesian” conjecture. Simon’s talk carried the main theme of different types of discrete logarithm problems and their application to elliptic curve cryptography. All of these talks were amazing, and I followed each one with keen interest.

Bill Kantor was the master of the schedule, and I was one of only a few that enjoyed the format: only Bill knew who was speaking when, and the program for the subsequent day would be posted on a door each evening. No titles or abstracts, just the expectation that you would see the next talk and you would know then and there what it would be about. It’s good reasoning: if you wanted to know the title and abstract before hand, it might be because you were choosing whether to go or not, and with such a cosy conference, that is out of the question! The other argument, might be that you wanted to do some prior reading before the talk, but would you really? Continue reading “Groups, Computation & Geometry at Pingree Park”

AMSI Summer Vacation Scholarship

Below is a guest blog post of Melissa Lee, who took part in a six-week summer vacation research project supported by the Australian Mathematical Sciences Institute.

 

Hi everyone! My name is Melissa Lee and I’ve recently started honours with John and Dr. Eric Swartz here at UWA. This past summer I have been working with John on an AMSI Vacation Research Scholarship. My AMSI VRS project was based on looking at structures embedded in an affine space by viewing them in terms of a game called SET. Continue reading “AMSI Summer Vacation Scholarship”

Up ↑