Multiplicative tilings in finite vector spaces

Some time ago, I came across an article due to Iosevich, Lai and Mayeli titled Tight wavelet frame sets in finite vector spaces. I’m not exactly sure why the suggestion system of ScienceDirect thought I might like this article from Applied and Computational Harmonic Analysis, but I was intrigued. For one, because Ingrid Daubechies, the person commonly accredited with the development of wavelets for applications, is an alumnus of Vrije Universiteit Brussel, where I am currently at. Secondly, finite vector spaces is something I am familiar with, so why not take a look?

It turned out that there was a particular problem in the paper posed as an open question on the very last page:

Question #1. Does there exist tight frame wavelet sets when q \equiv 1 \pmod{4}?”

I managed to solve this question, and I will record it here, mainly for my own convenience. The what and why of tight frame wavelet sets is not very important, the most important aspect is the fact that someone from a finite geometrical background can contribute to problems in harmonic analysis. We have more in common than we think!

Going through the paper, it turns out that to solve this problem, all one needs is a multiplicative tiling (X,A) of \mathbb{F}_q^2, i.e. a set of q-1 non-zero vectors X \subseteq \mathbb{F}_q^2 and a set of q+1 automorphisms A \subseteq \mathrm{GL}(\mathbb{F}_2^q) such that every non-zero vector in \mathbb{F}_q^2 can be uniquely written as \phi(x), x \in X, \phi \in A. This is a ‘multiplicative’ analogue of translational tilings which consists of two sets of vectors X,Y such that every vector in \mathbb{F}_q^2 can be uniquely written as x+y, x \in X, y \in Y.

When q \equiv 3 \pmod{4} the authors took X to be a set of representatives of the circles defined by x^2+y^2=r, r \neq 0, which are the orbits of \mathbb{F}_q^2 under a group of rotations (which can be written down explicitly). The problem with q \equiv 1 \pmod{4} is that the circle with radius zero consists of more points than just the origin, as -1 is a square!

This problem with squares and non-squares appearing in computations over finite fields is very common and working around it often uses a solid geometrical background. In fact, the obstacle here can be circumvented by considering ellipses defined by x^2-ny^2=r instead, where n is a non-square in \mathbb{F}_q. One can do the computations and see that after some adaptions, everything works out just fine. However, there is an even more elegant approach to this construction, which is the one we will show.

Instead of considering \mathbb{F}_q^2, we can consider the isomorphic vector space \mathbb{F}_{q^2}. We will make the isomorphism explicit by constructing the field extension \mathbb{F}_{q^2} as \mathbb{F}_q[X]/(X^2-n) (where n is the same non-square as before). In this way, if i \in \mathbb{F}_{q^2} such that i^2=n, we can identify every element (a,b) \in \mathbb{F}_q^2 with a+bi \in \mathbb{F}_{q^2}. In this bigger field, we can consider the standard norm function N: \mathbb{F}_{q^2} \rightarrow \mathbb{F}_q, N(a+bi) = (a+bi)(a+bi)^q = a^2-nb^2.

Now take X to be a set of q-1 points, one from each of the norm curves N(x)=r, r \neq 0, and A the set of q+1 points with norm 1 (which is in fact a subgroup). Then it is immediately checked that (X,A) is a multiplicative tiling set, and these computations are reduced to one-line proofs, as opposed to the work that is necessary when working in \mathbb{F}_q^2 (which takes 2 pages in the aforementioned paper). Finally, adapting this multiplicative tiling into a tight wavelet frame set works exactly the same as in the paper, which completely answers their question.

Posted in Geen categorie | Tagged , | Leave a comment

The return of the polarity graph

Every now and then, I seem to circle back to a tantalizing question in graph theory: the independence number of the polarity graph. Let’s recall this graph, which is defined in terms of projective planes and their polarities: let \pi be a finite projective plane of order q (not necessarily a prime power!) and \perp a polarity. Then the polarity graphs has the points of \pi as vertices and two distinct vertices x and y are adjacent iff x \in y^\perp. By definition this is indeed an undirected, loopless graph, but depending on \pi and \perp, this graph can behave very differently. The most-discussed polarity graph is probably the one where \perp has the least possible number of absolute points, i.e. points incident with their image under \perp. This minimum is q+1, by a classical result due to Baer.

Continue reading
Posted in Geen categorie | Tagged , | 1 Comment

Proofs and papers in the 21st century

It’s strange how mathematics has evolved over the last few centuries, but the way research mathematics is presented hasn’t changed in a meaningful way. Sure, since the advent of internet, it is easier and faster to propagate your work to the mathematical community, but the form in which this happens seems quite archaic, considering the tools available nowadays. What I mean is the following: since the 15th-16th century, people were able to spread their ideas to an audience broader than ever before, due to the invention of printing. This practice of putting your mathematical research into print has carried all the way to today, with the only difference that printed journals are nowadays also available online. Although the opportunities offered by the online medium are enormous, it seems to me that no meaningful changes have been made since the transition from paper to screen. One of the few features is that you are now able to quickly click-through to references and citations using hyperlinks (which is a feature that actually could use improvement in my opinion, see later). Other than that, the linear structure of text on paper (read from top to bottom) has been preserved, as is the lack of interactivity.

Although I realize that many mathematicians like to complain that there is no need to change what works (I also prefer blackboards to smartboards for teaching purposes, I admit), I would like to propose a thought experiment on how research mathematics is presented and how it could be improved. One of the first links you will stumble upon in a quick Google search is Leslie Lamport‘s “How to write a 21st century proof” (pdf). In this note, Leslie proposes a new style of proofs, which admittedly, seems a bit extreme the first time you come across it. However, extreme does not necessarily imply bad or useless. Let me give you some motivation why change is not always bad. As Leslie puts it himself in “How to write a proof”, an earlier version of the aforementioned essay:

Mathematical notation has improved over the past few centuries. In the
seventeenth century, a mathematician might have written

There do not exist four positive integers, the last being greater than two, such that the sum of the first two, each raised to the power of the fourth, equals the third raised to that same power.

How much easier it is to read the modern version

There do not exist positive integers x, y, z, and n, with n > 2, such that x^n+y^n=z^n.

Surely, he has a point. The added value of using notation and symbols to shorten the language in which you want to convey your mathematical idea cannot be understated. It is this same evolution of natural language to a more structured language that Leslie (and I) would like to see in proofs. I will refer to his Section 2 for an explicit example of how he proves things nowadays.

Personally, my frustration with the current limitations of static pdfs arose while reading a paper, and having to scroll all the way down for the nth time to check a reference, only to scroll all the way up. I’m sure this has to be a familiar feeling for other people. It made me reflect on the shortcomings of the current state, and try to think of some improvements, so here’s two improvements which should be feasible in the near future.

References on hover

The first suggestion is related to my own frustration. It is already possible to click through on references in recent articles, however, wouldn’t it be nice to have a little pop up box appear when hovering over an article in text. In the last few years, YouTube introduced a similar concept for their videos, allowing you to hover the mouse over the timeline at the bottom of a video and see a preview of what will be shown at that specific time. It should not be that hard to replicate a similar ‘textbox-on-hover’ when hovering over a reference, no?


I started thinking more about the way a paper is presented in a pdf and came across the idea of hypertext, or what is apparently called accordions. A Google search revealed that Leslie Lamport had had this idea when I was still in diapers. I will show a rough sketch of a similar example to demonstrate the merit of the idea. It gives the opportunity for quick first readings, skip things you already know or understand but also delve into proof steps that might be unclear. You can write for several audiences (e.g. students and more advanced researchers) at the same time while still catering to their respective needs (e.g. students might need more explanations or motivations on why and how certain things are done). However, there is also a certain drawback to this method. It forces authors to more concise and precise, which is not necessarily a bad thing, but surely there’s a lot more work involved. Secondly, opinions on the depth of detail that should be given are inevitably going to differ so clear guidelines on just how much should be explained might not be feasible. It might improve a lot of texts, but new technology will not suddenly solve the problem of badly-written papers as this is a classical PEBCAK problem.

Without further ado, let me demonstrate the simple example which I recently needed in my own research. The implementation is very rough and also doesn’t allow for LaTeX typesetting, so I’ll have to ask to use your imagination a little. Ideally, there would also be some form of hierarchy as described in Leslie’s paper, but again my limitations with HTML prevent me to show this. In short, we want to prove that a certain group acts transitively on a set of points in the affine plane \mathrm{AG}(2,q), q an odd prime power, which could be an exercise in an undergraduate course.

Posted in Geen categorie | Tagged , | Leave a comment

G2R2: the aftermovie

Wow. As I was interviewed before camera, I figured that there would be some footage afterwards, but the quality of this clip is much more than I expected. All credit goes to the Novosibirsk State University and their wonderful team. It deserves to be shared, so here it is, starring yours truly!


Posted in Geen categorie | Tagged , | Leave a comment

G2R2: week 2

Onto the second week.

The first week consisted of six days of classes and conferences talks, for which we were rewarded with one free day, including a visit to the local zoo. Here, you have the opportunity to see a liger (lion-tiger hybrid) and supposedly, a liliger has also been born here! Although it sounds intriguing, the actual animal resembled Garfield more than anything, being just a big, fat cat. Maybe they overfeed, maybe genetics are at play, who knows.

liger at novosibirsk zoo

The liger at Novosibirsk Zoo

In any case, our brains got some well-deserved rest, which was needed for the upcoming classes.

Continue reading

Posted in Geen categorie | Tagged , | Leave a comment

G2R2: week 1

Well, I severely overestimated the available time I would have the last few weeks to write a recap. I’ll do it anyway, but not so fresh from memory. Since both weeks contained a lot of material, I will split it in two posts.

The first week had lectures from Roman Nedela and Sasha Mednykh, who replaced a sick Gareth Jones. Personally, these lectures were an added bonus on top of the lectures of the second week, which were my real goal, as they lie much closer to my field of research. But, one can always pick up interesting ideas from another domain, so of we went.

Continue reading

Posted in Geen categorie | Tagged , , , | Leave a comment

G2R2: first week

So classes have started, leaving very little time for other things. Especially since the lectures are interwoven with conference talks, keeping us busy from 10am to 10pm. Anyway, a quick write-up from the cultural program of the first week.

Continue reading

Posted in Geen categorie | Tagged , | Leave a comment