Blogue

Wooden laser-cut Jeandel-Rao tiles

07 septembre 2018 | Catégories: sage, slabbe spkg, math, découpe laser | View Comments

I have been working on Jeandel-Rao tiles lately.

Before the conference Model Sets and Aperiodic Order held in Durham UK (Sep 3-7 2018), I thought it would be a good idea to bring some real tiles at the conference. So I first decided of some conventions to represent the above tiles as topologically closed disk basically using the representation of integers in base 1:

With these shapes, I created a 33 x 19 patch. With 3cm on each side, the patch takes 99cm x 57cm just within the capacity of the laser cut machine (1m x 60 cm):

With the help of David Renault from LaBRI, we went at Coh@bit, the FabLab of Bordeaux University and we laser cut two 3mm thick plywood for a total of 1282 Wang tiles. This is the result:

One may recreate the 33 x 19 tiling as follows (note that I am using Cartesian-like coordinates, so the first list data[0] actually is the first column from bottom to top):

sage: data = [[10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 5, 6, 1, 8, 10],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 6, 1, 3, 7, 6, 1, 7, 2],
....:  [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 6, 1, 3, 8],
....:  [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 3, 7, 0, 9, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [8, 10, 4, 0, 9, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [7, 5, 5, 0, 9, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3]]

The above patch have been chosen among 1000 other randomly generated as the closest to the asymptotic frequencies of the tiles in Jeandel-Rao tilings (or at least in the minimal subshift that I describe in the preprint):

sage: from collections import Counter
sage: c = Counter(flatten(data))
sage: tile_count = [c[i] for i in range(11)]

The asymptotic frequencies:

sage: phi = golden_ratio.n()
sage: Linv = [2*phi + 6, 2*phi + 6, 18*phi + 10, 2*phi + 6, 8*phi + 2,
....:      5*phi + 4, 2*phi + 6, 12/5*phi + 14/5, 8*phi + 2,
....:      2*phi + 6, 8*phi + 2]
sage: perfect_proportions = vector([1/a for a in Linv])

Comparison of the number of tiles of each type with the expected frequency:

sage: header_row = ['tile id', 'Asymptotic frequency', 'Expected nb of copies',
....:               'Nb copies in the 33x19 patch']
sage: columns = [range(11), perfect_proportions, vector(perfect_proportions)*33*19, tile_count]
sage: table(columns=columns, header_row=header_row)
  tile id   Asymptotic frequency   Expected nb of copies   Nb copies in the 33x19 patch
+---------+----------------------+-----------------------+------------------------------+
  0         0.108271182329550      67.8860313206280        67
  1         0.108271182329550      67.8860313206280        65
  2         0.0255593590340479     16.0257181143480        16
  3         0.108271182329550      67.8860313206280        71
  4         0.0669152706817991     41.9558747174880        42
  5         0.0827118232955023     51.8603132062800        51
  6         0.108271182329550      67.8860313206280        65
  7         0.149627093977301      93.8161879237680        95
  8         0.0669152706817991     41.9558747174880        44
  9         0.108271182329550      67.8860313206280        67
  10        0.0669152706817991     41.9558747174880        44

I brought the \(33\times19=641\) tiles at the conference and offered to the first 7 persons to find a \(7\times 7\) tiling the opportunity to keep the 49 tiles they used. 49 is a good number since the frequency of the lowest tile (with id 2) is about 2% which allows to have at least one copy of each tile in a subset of 49 tiles allowing a solution.

A natural question to ask is how many such \(7\times 7\) tilings does there exist? With ticket #25125 that was merged in Sage 8.3 this Spring, it is possible to enumerate and count solutions in parallel with Knuth dancing links algorithm. After the installation of the Sage Optional package slabbe (sage -pip install slabbe), one may compute that there are 152244 solutions.

sage: from slabbe import WangTileSet
sage: tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3),
....: (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)]
sage: T0 = WangTileSet(tiles)
sage: T0_solver = T0.solver(7,7)
sage: %time T0_solver.number_of_solutions(ncpus=8)
CPU times: user 16 ms, sys: 82.3 ms, total: 98.3 ms
Wall time: 388 ms
152244

One may also get the list of all solutions and print one of them:

sage: %time L = T0_solver.all_solutions(); print(len(L))
152244
CPU times: user 6.46 s, sys: 344 ms, total: 6.8 s
Wall time: 6.82 s
sage: L[0]
A wang tiling of a 7 x 7 rectangle
sage: L[0].table()  # warning: the output is in Cartesian-like coordinates
[[1, 8, 10, 4, 5, 0, 9],
 [1, 7, 2, 5, 6, 1, 8],
 [1, 3, 8, 7, 6, 1, 7],
 [0, 9, 7, 5, 6, 1, 3],
 [0, 9, 3, 7, 6, 1, 8],
 [1, 8, 10, 4, 6, 1, 7],
 [1, 7, 2, 2, 6, 1, 3]]

This is the number of distinct sets of 49 tiles which admits a 7x7 solution:

sage: from collections import Counter
sage: def count_tiles(tiling):
....:     C = Counter(flatten(tiling.table()))
....:     return tuple(C.get(a,0) for a in range(11))
sage: Lfreq = map(count_tiles, L)
sage: Lfreq_count = Counter(Lfreq)
sage: len(Lfreq_count)
83258

Number of other solutions with the same set of 49 tiles:

sage: Counter(Lfreq_count.values())
Counter({1: 49076, 2: 19849, 3: 6313, 4: 3664, 6: 1410, 5: 1341, 7: 705, 8:
293, 9: 159, 14: 116, 10: 104, 12: 97, 18: 44, 11: 26, 15: 24, 13: 10, 17: 8,
22: 6, 32: 6, 16: 3, 28: 2, 19: 1, 21: 1})

How the number of \(k\times k\)-solutions grows for k from 0 to 9:

sage: [T0.solver(k,k).number_of_solutions() for k in range(10)]
[0, 11, 85, 444, 1723, 9172, 50638, 152244, 262019, 1641695]

Unfortunately, most of those \(k\times k\)-solutions are not extendable to a tiling of the whole plane. Indeed the number of \(k\times k\) patches in the language of the minimal aperiodic subshift that I am able to describe and which is a proper subset of Jeandel-Rao tilings seems, according to some heuristic, to be something like:

[1, 11, 49, 108, 184, 268, 367, 483]

I do not share my (ugly) code for this computation yet, as I will rather share clean code soon when times come. So among the 152244 about only 483 (0.32%) of them are prolongable into a uniformly recurrent tiling of the plane.

Read and Post Comments

Installing Ubuntu 18.04 on Aspire ES 11 ES1-132-C6LG

20 mai 2018 | Catégories: ubuntu | View Comments

I tried to install Ubuntu 18.04 on a Aspire ES 11 ES1-132-C6LG and got troubles because I get the screen "No Bootable Device found" after installation. The first help I found on Google is this posts on itsfoss.com but at step 3, the option "Select an UEFI file as trusted for executing" is unavailable so the proposed solution does not work for me.

Some comments on the same post shows that I am not alone with this problem:

Alex 2 months ago

I cannot “Select an UEFI file”… Maybe Windows 10 configured my BIOS to
reject any other drive (SSD) that has not Windows on it?

Tom 1 month ago

No, you need to install ubuntu without bootloader, mount the partitions
after the installation, modprobe efivars and then install grub-efi

After looking at what grub-uefi and modprobe mean, I found this discussion (April 2017, Ubuntu 17.04) and this discussion (Dec. 2016) on askubuntu and this discussion (Dec 2016) on community acer very close to my problem. In the end, the most simple (no need to modprobe anything or install grub-efi) and usefull one (it worked) was this discussion (Jan 2017) on community acer especially the two posts by Spektro37 (on page 1, the second on page 2) that I recopy and adapt a little bit below.

Install Ubuntu;
Boot using Ubuntu USB and select "Try without installing";
Launch Gparted to get the EFI partition address. In my case it's /dev/mmcblk0p1;
Open the Terminal (ctrl + alt + T);
In the Terminal execute the following to create a directory in the media folder and to mount the EFI partition to that folder:
```
sudo mkdir /media/EFI
sudo mount {replace_this_with_the_address_from_step_3} /media/EFI
```

In my case it would look like:

sudo mkdir /media/EFI
sudo mount /dev/mmcblk0p1 /media/EFI

Create the /EFI/Linux/ folder:
```
sudo mkdir /media/EFI/EFI/Linux
```
Copy all the existing files from the folder that was created during Ubuntu instalation. In my case, the default folder was /EFI/ubuntu/:
```
sudo ls /media/EFI/EFI/ubuntu
BOOTX64.CSV  fw  fwupx64.efi  grub.cfg  grubx64.efi  mmx64.efi  shimx64.efi
```
To do so, you can use the following command:
```
sudo cp -R /media/EFI/EFI/ubuntu/* /media/EFI/EFI/Linux/
```
Copy the BOOTX64.EFI from the BOOT directory to the Linux folder (without it, I confirm it didn't work):
```
sudo cp /media/EFI/EFI/BOOT/BOOTX64.EFI /media/EFI/EFI/Linux
```

According to Spectro37, /EFI/Linux/BOOTX64.efi is an hardcoded path for Linux.

Read and Post Comments

Plus de 3000 questions maintenant disponibles en français dans l'interface WebWork

24 mars 2018 | Catégories: webwork | View Comments

Six ans après avoir utilisé et entamé la traduction de WebWork en français dans un cours que j'avais donné à l'Université du Québec à Montréal, je viens de voir sur internet que WebWork est maintenant utilisé à grande échelle en français au Québec.

Le projet Développement de WeBWorK pour le réseau des cégeps francophones a porté ses fruits. Un serveur du Centre collégial de développement de matériel didactique (CCDMD), donne facilement accès à un compte sur la plateforme WeBWorK. Selon le site, plus de 3000 questions sont maintenant traduites en français dans la Banque de problèmes libres (BPL) en français dans un répertoire sur github. De plus, des ressources en ligne sont disponibles notamment sur ce sujet sur le site de MathemaTIC.

Félicitations à toutes celles et ceux qui ont été impliqués dans la poursuite du projet dans les 6 dernières années.

Read and Post Comments

De la purée de pomme des Labbé chez Mange ta main

14 novembre 2017 | Catégories: Uncategorized | View Comments

Si vous passez par Lac-Mégantic cette semaine, il faut faire un arrêt chez Mange ta main: ils servent de la purée de pomme des Labbé:)

Read and Post Comments

What makes Montréal, Québec and Canada exceptional in terms of ultimate frisbee

26 août 2017 | Mise à jour: 10 septembre 2017 | Catégories: ultimate | View Comments

As the 2017 American Ultimate Disc League (AUDL) Championship starts in Montreal today, I thought it would be a nice timing to show an aspect that makes Montreal (and more generally Quebec and Canada) so exceptional concerning Ultimate Frisbee.

Remark: all of the data and computations made for this post are available as a Jupyter Notebook in a github repository.

1. The density of population playing ultimate in the Country

The World Health Organization website has a lot of data on the density of physicians (counted as total number per 1000 population). Some coutry have a lot of physicians: as of today, Cuba has 7.519 physicians for each 1000 population while Canada has 2.477, USA has 2.554 and France has 3.227 physicians for each 1000 population. Some other country have a few like Mali that I visited in 2006 which has only 0.085 physicias per 1000 population.

I propose now to do the same for Ultimate Frisbee players as WHO does for physicians. For this we may use the data that was made public by the WFDF in 2014 before deciding how many bids where given to each country to compete in the World Club Ultimate Championships that took place in 2014 in Lecco. And we may get the population by country in 2014 from the World Bank website.

Lot of countries have very few ultimate players. For example, there are only 13 countries having at least 1000 players: United States, Canada, Australia, Germany, Japan, United Kingdom, France, Austria, Colombia, Norway, Netherlands, Philippines, Belgium. And only 22 countries having at least 500 players.

Above all, it is the density of people playing ultimate that makes Canada so exceptional. The next graphics including countries with at least 500 players declared to WFDF in 2014 says it all:

For every 1000 population, there is a ultimate player. Since everybody knows something like 1000 people. This means that in Canada everybody knows someone which plays ultimate. This makes a big difference in the country in terms of recognition. People do not ask if you play with a dog on the beach anymore in Canada when you say you play ultimate. They know this sport! In comparison, in France there is 1 ultimate player for each 24664 population. You got to be lucky to know one.

So many people play ultimate in Canada that there are almost as many players as in the United States:

The above graphics explains something more: it is much much more difficult to represent your country at WFDF competitions when you come from USA or Canada.

Note that these computations were done based on the number of active ultimate frisbee players declared to WFDF. It is possible that some countries do not declare all of them for some reasons. For example, USA Ultimate declares to WFDF only its own members which are in general people taking part in USA Ultimate competitions.

2. Women play ultimate in Canada

Canada is among the most egalitarian countries in terms of women playing ultimate. For each 7 ultimate players on the line in Canada, 2.800 are female. Among countries with at least 500 declared active players in 2014, only Philippines (2.996) and New Zealand (2.827) are more egalitarian.

In other countries, like France where only 1.771 female play ultimate for each 7 players, it is just impossible to get your club to play in the mixed division. This is also why we find much more women playing in the open division in Europe than in America up to a certain level of play.

The density of women playing ultimate in Canada is just exceptional:

In absolute value, this makes Canada the second country with the most female active players in 2014, just behind USA, with a lot of advance over the next countries:

3. The density of population playing ultimate in Quebec regions

In 2017, according to this page of the Quebec Ultimate Federation there are 6908 registered ultimate player in Quebec province of Canada. With 8.18 millions of population, this makes a density of 0.844 ultimate player in Quebec province for every 1000 of population.

Most of the people playing ultimate are in the big cities (Montréal and Québec city). There are 3454 active ultimate frisbee players in Montreal. If Montreal was a country, it would be ranked 7th for the total number of active player in the 2014 list of WFDF just behind Germany (3632), Japan (3621) and United Kingdom (3621).

Note that in the above graphic, Capitale-Nationale is the name of the region of Quebec city and Estrie is the name of the region of Sherbrooke city. Should I recall that Quebec city is hosting every year the Mars Attaque tournament which is without doubt the largest indoor ultimate tournament in the world with 120 teams gathering more than 1000 players (see this video of the most recent edition). Also team ONYX which finished 2nd in the mixed division during the Prague 2010 World Club Ultimate Championships was from Quebec city.

This gives even bigger densities if we look at densities per region. In the Montreal administrative region, there are 1.727 ultimate frisbee players for each 1000 population. Two other regions are above 2.000 including the region of Quebec city.

The data for the population in each Quebec region was taken from the associated wikipedia page about Quebec administrative regions.

Note that there is a difficulty in counting the density for regions that are near a big city (Longueil and Laval are near of Montreal, Chaudière-Appalaches is a region south of Quebec city, and Outaouais is the Quebec region that is near to Ottawa). The low density in these regions might be explained by the fact that people drive to the big city to play ultimate.

4. The density of population playing ultimate in Canada provinces

There are a lot of ultimate frisbee players in Ontario (including Ottawa and Toronto cities) and in British Columbia. Here is the number of ultimate frisbee players per provinces in each of the years 2014, 2015 and 2016 according to the 2016 Ultimate Canada Annual Report that was given to me by Danny Saunders (executive director of Ultimate Canada). I do not know if this annual report can be found online.

Using data on the population by Canada provinces and territories found on this wikipedia page, we can compute the density of ultimate frisbee players in each province. We discover that, if there is a high density of ultimate frisbee players in Quebec, it is even higher in the other provinces.

The province of Manitoba is the province with the highest rate with more than 3.5 players per 1000 population.

The density of population playing ultimate in some other cities

Below I am adding a graphic on the density of people playing ultimate in some cities I know. Cities in Quebec are much more dense in ultimate frisbee players than cities in Europe amongst this short list.

More to do

I am missing data to do more of those graphics. How many frisbee players are there in every states of the USA? in every province of Canada? in every city of the world? how many female? If you can help me gather this data, do not hesitate to contact me or add a comment below.

Read and Post Comments

« Previous Page -- Next Page »