Blog de Frédéric

More than half a year has passed since my last status report on the MathML project and so I think it is time to provide the latest updates. A lot of pending bugs that I mentioned in previous reports has been fixed. A noticeable exception being support for Arabic mathematics, since people who showed interest on this work could not finally make it. Because Mozilla uses a rapid release process now, the description in this post covers four different versions of Gecko that I indicate in parentheses.

The most exciting thing has been to see contributors getting involved or continuing to work on the MathML project. I would like to thank Bill Gianopoulos for finishing the work on MathML linking and regularly testing all the MathML patches as well as Florian Scholz for starting to work on Gecko and continuing to write MathML documentation. Obviously, I'm also particularly grateful to my intern Jonathan Hage, who has definitely been helpful this summer. I've appreciated the assistance of all the other developers, reviewers, bug reporters and documentation authors and I hope that participation will continue to grow!

Below is a summary of the work accomplished since Firefox 4. I also expect to update the planning for MathML.

• Stretching of Operators and Mathematical operators
  • Embellished operators are now entirely supported. (Gecko 5.0)
  • The MathML Operator Dictionary has been upgraded to the version proposed in the MathML 3 REC. (Gecko 5.0)
  • The set of XML entity definitions for characters - including many mathematical operators - has been upgraded to follow the corresponding W3C recommendation (Gecko 5.0). I've reported this bug to several other browser authors and hope they will align on this set of definitions. Anyway, for compatibility reasons, I recommend Web authors to directly Unicode characters or their numeric entity references.
  • The Asana-Math font is now usable for stretching mathematical operator (Gecko 7.0) To test it, you may want to modify the font.mathfont-family entry in about:config.

  It would really be interesting to support more mathematical Open Type fonts. If you want to help us, have a look to the preliminary bug to work on (a student wanted to work on this bug as a summer project but was not able to do so...).

• Linking

  One of the most essential feature of the Web is back in the MathML world! There is still some undergoing work to improve rendering/UI but you can now use links in mathematical formula. Support for the old XLink syntax has been restored but it is recommended to use the new MathML 3 href, that avoids the use of XML namespaces.

• MathML elements/attributes

  The implementation of mstyle has been fixed (Gecko 6.0). In particular, the mathvariant attribute on a <mstyle/> now applies correctly to its <mi/> descendants. The <math/> element should now be usable as an mstyle (Gecko 8.0). Names for negatives spaces are recognized (Gecko 7.0). There are many other improvements for <mfrac/>, <mfenced/>, <mpadded/>, <mtable/> and <munderover/> including new MathML 3 attributes. As usual, you can read the current status on the MathML project page.

• MathML Documentation

  The MDN documentation has been expanded and updates have been made to indicate fixes or support for new features. Old MathML demo pages are still being updated and prepared for migration to MDN.

Firefox 4 has just been released and it's already time for developers to turn their attention to the next releases. If you are a student, you also have your role to play in order to make Firefox (remain) the best browser! You will find below two subjects for a summer internship in the Mozilla MathML Project. If you are interested, please contact me at fred dot wang at free dot fr. Also, recall that this week you may apply to the Google Summer of Code 2011 program. In particular, I have proposed two additional projects on SVG/MathML clipboard features and improving MathML font support.

Implementing new MathML features in Mozilla's layout engine

MathML 3 - a language for describing mathematical expressions in Web pages - was released as a W3C Recommendation last October, opening new perspectives for sciences on the Web. Mozilla has provided a good MathML support for more than ten years and improvements are still underway. The goal of the internship is to improve support for MathML 2 and to implement new features of MathML 3. You are assumed to have:

• Good knowledge of Web languages (HTML, CSS, Javascript...). Knowledge of MathML is definitely a plus.
• Ability to program in C/C++ and basic knowledge of compilation, debugging and revision control tools.

You will start to work on layout bugs of medium difficulty in order to let you time to discover, get and build Mozilla's souce code as well as to get familiar with Mozilla's tracking system, review process, automated tests and documentation. Then, you will implement features requiring a gradually increasing amount of work. For each of them, you are supposed to analyse the problem, submit patches, create non-regression tests and finally write documentation / demos of the new feature implemented.

Quality Assurance and Documentation in the Mozilla MathML project

One interesting feature of Firefox 4 is the possibility to include MathML inside standard HTML pages, which will certainly enable more people to use MathML. Hence there is a need to track missing features and important bugs of Mozilla's MathML implementation as well as to provide good documentation for users. The goal of the internship is to improve the Mozilla MathML documentation and to find & analyse MathML issues in Firefox. You are expected to have:

• Good knowledge of Web languages (HTML, CSS, Javascript...). Knowledge of MathML is definitely a plus.
• Familiarity with bug tracking systems, Wikis and other social software tools.
• Arabic/Persian writing skills is a big plus (to test right-to-left mathematical notation)

The work to update MathML documentation has started since last year. You will continue to update former MathML demos and write new documentation pages. You will also try to collect feedback from discussion forums, blogs, etc and test Mozilla's MathML implementation against various test pages including the MathML3 test suite. Finally, you will report new issues to Mozilla's tracking system and do bug triage.

This is an updated description of the activities of the Mozilla MathML Project since the overview I gave half year ago. I have selected four items for which progress have happened (I will not mention old patches that have not changed). I think that many bug fixes and new features are likely to require important changes in the MathML code and I will probably discuss them in a later post.

• Stretching of Operators and Mathematical Fonts
  Jacques Distler has reported a regression due to changes in the release version of STIX fonts. This regression has been fixed on trunk and hopefully the support for STIX fonts 1.0 is now complete and ready for Firefox 4. We have also received several feedback comments from people complaining of bad rendering, even with STIX fonts installed. Hence I think it is important to recall that the current release still requires the beta version of the STIX fonts (however if someone wants to help, note that it has been proposed to write a patch for old versions...). An easy way to check your installation is to look the stretching of the brace in the example below. $$\underbrace{a+b+c+d+e}$$ and compare with the right images of this blog post. Another test is with radical symbols: they should really stretch, contrary to what can be seen on the screenshot of this old post from hacks.mozilla.org. If you have any problems, then I recommend you to read the documentation on the project page.
• MathML Project Documentation
  The main contribution in this area has been made by Florian Scholz: he wrote MathML element reference pages on MDN during the Web Standards documentation sprint and has subsequently updated these pages. We are also still working on the migration of documentation from mozilla.org to MDN. We have fixed many markup errors on the demo pages but the work is still not complete and help is welcome...
• linking
  Let's first recall that MathML2 used XLink and that MathML 3 allows to create a link via an attribute href on a MathML element. These features are currently broken / not implemented in Mozilla, but here is an example for testing:$$\left(\frac{a}{p}\right)=\{\begin{array}{l}1\text{if}{a}^{(p-1)/2}\equiv 1(modp)\\ -1\text{if}{a}^{(p-1)/2}\equiv -1(modp)\\ 0\text{if}a\equiv 0(modp).\end{array}$$

  Some patches to restore XLink and add support for href have been written so I hope this issue will be fixed soon.

• mstyle
  Our implementation of the mstyle element has several bugs, with attributes having no effect on the rendering of children. There is now a set of patches fixing several bugs of this kind. Moreover, a patch allows all the attributes of mstyle on the top-level math element, as specified by MathML 3.

Finally, for people who are interested in testing the MathML improvements, Bill Gianopoulos makes available Testing Builds of Firefox which include several MathML patches.

Infinite ordinals and cardinals are beautiful mathematical objects, extending in a natural way $\mathbb{N}$ and sharing most of its properties. I have always wondered whether it would be possible to generalize the constructions of $\mathbb{Z}$ or $\mathbb{Q}$ to get transfinite integers or rationals. In general, putting a group structure on classes extending $\mathrm{Ord}$ or $\mathrm{Card}$ is not possible as I indicated some years ago (fr). Basically, we would have $1+{\aleph }_0={\aleph }_0$ (and also $1+\omega =\omega$) which would imply $1=0$. However, we can consider a slightly modified problem with weaker constraints, as follows. First we assume we have a class of cardinals $C\subseteq \mathrm{Card}$ containing zero and stable by addition.

$$\text{(1)}\{\begin{array}{l}0\in C\\ \forall \kappa ,\lambda \in C,\kappa +\lambda \in C\end{array}$$

We define the class $Z_C=C\cup C^{-}$, where $C^{-}=\{-\kappa \mid \kappa \in C,\kappa \ne 0\}$ is a representation of "negative" cardinals. As we have seen, the class $Z_C$ need not be a group. Nevertheless, we can try to find an equivalence class $R$ over $Z_C$ such that $G_C=\raisebox{1ex}{$Z_C$}\!\left/ \!\raisebox{-1ex}{$R$}\right.$ is a group. Moreover, we want this equivalence class to be compatible with addition and opposite i.e.

Of course this implies that $\overline{0}$ is the identity element $0$ of the expected group. Similarly, we can settle the same problem for a class $C\subseteq \mathrm{Ord}$ and + is now understood as the ordinal addition. Can we follow this schema to contruct interesting infinite algebraic structures?

For $C\subseteq \mathrm{Card}$, we have for any infinite $\kappa \in C$ the relation $\overline{\kappa }=\overline{\kappa +\kappa }=\overline{\kappa }+\overline{\kappa }$ so $\overline{\kappa }=0$. Hence $G_{C\cap \omega }=G_C$ and the initial problem is reduced to the case where $C\subseteq \omega$ contains only finite cardinals (= finite ordinals) and so the problem is still not really exciting. What about the case $C\subseteq \mathrm{Ord}$? In general it is possible to have ${\beta }_1+\gamma ={\beta }_2+\gamma$ without ${\beta }_1,{\beta }_2$ being equal and so for any $\alpha$ such that ${\beta }_1\alpha ,{\beta }_2\alpha ,\mathrm{\gamma \alpha }\in C$, we get that $\overline{{\beta }_1\alpha }=\overline{{\beta }_2\alpha }$. In particular for any infinite ordinal $\gamma$ and $\alpha \in C$ such that $\mathrm{\gamma \alpha }\in C$ we obtain $\overline{\alpha }=0$ because $1+\gamma =\gamma$ (if this is not obvious to you, a more general statement is proved below). As a consequence, more general assumptions on the class $C$ strongly limit the structure of the group. For example if $C$ is closed under an infinite sum ($C=\mathrm{Ord}$ for example) then ${\text{G}}_{\text{C}}$ is trivial. Similarly, if we require $C$ to be stable by multiplication (in order to define a ring structure for example) then ${\text{G}}_{\text{C}}$ is trivial whenever $C$ contains an infinite ordinal $\gamma$ (hence the remaining case is again $C\subseteq \omega$). If $G_C$ is not trivial, we denote ${\alpha }_0\in C$ the least element such that $\overline{{\alpha }_0}\ne 0$ (in particular ${\alpha }_0>0$).

One additional natural hypothesis should be added. We know that for any ordinal $\alpha <\beta$ there exists a unique ordinal $\gamma$ such that $\alpha =\beta +\gamma$. We would very like $\overline{\gamma }$ to match the difference "$-\overline{\beta }+\overline{\alpha }$". For that purpose, we only require $\gamma$ to belong to $C$. Hence we assume that

$$\text{(3)}\forall \alpha ,\beta \in C,\forall \gamma \in \mathrm{Ord},\alpha =\beta +\gamma \Rightarrow \gamma \in C$$

Let's come back to the case $C\subseteq \omega$ with the new assumption (3) and suppose that $G_C$ is not trivial. Then ${\alpha }_0<\omega$ and any finite $m\in C$ and be written $m={\alpha }_{0}q+r$ with $r<{\alpha }_0$. By (3), $r\in C$ and because $C$ is stable by finite sums, $\overline{m}=\overline{{\alpha }_0}q+\overline{r}=\overline{{\alpha }_0}q$. Thus $G_C$ is the monogenic group generated by $\overline{{\alpha }_0}$.

What about the general case? Unfortunately, it turns out that if $G_C$ is not trivial it is still a monogenic group generated by $\overline{{\alpha }_0}$. To prove this, we need to recall some equalities on ordinals. First, for any $\alpha >0$, we have $1+{\omega }^{\alpha }={\omega }^{\alpha }$. This is clearly true for $\alpha =1$ and we prove the general case by induction on $\alpha$: $1+{\omega }^{\alpha +1}=1+\omega {\omega }^{\alpha }=1+\left(1+\omega \right){\omega }^{\alpha }=\left(1+{\omega }^{\alpha }\right){+\omega }^{\alpha +1}={\omega }^{\alpha }+{\omega }^{\alpha +1}=\left(1+\omega \right){\omega }^{\alpha }=\omega {\omega }^{\alpha }={\omega }^{\alpha +1}$ and $1+{\omega }^{\lambda }=\underset{0<\alpha <\lambda }{sup}\left({1+\omega }^{\alpha }\right)=\underset{0<\alpha <\lambda }{sup}{\omega }^{\alpha }={\omega }^{\lambda }$. Now, if we have two ordinals $\alpha <\beta$ and if $\gamma >0$ is such that $\beta =\alpha +\gamma$ we have ${\omega }^{\alpha }+{\omega }^{\beta }={\omega }^{\alpha }\left(1+{\omega }^{\gamma }\right)={\omega }^{\alpha }{\omega }^{\gamma }={\omega }^{\beta }$. Finally, if we have two ordinals ${\gamma }_1<{\gamma }_2$ we can write their Cantor Normal Forms:

$$\text{(4)}\begin{array}{c}{\gamma }_1={\omega }^{{\beta }_1^1}{k}_1^1+{\omega }^{{\beta }_2^1}{k}_2^1+\dots +{\omega }^{{\beta }_n^1}{k}_n^1\\ {\gamma }_2={\omega }^{{\beta }_1^2}{k}_1^2+{\omega }^{{\beta }_2^2}{k}_2^2+\dots +{\omega }^{{\beta }_n^2}{k}_m^2\end{array}$$

where ${\beta }_1^2\ge {\beta }_1^i>{\beta }_2^i>\dots >{\beta }_2^i$ and $k_j^i$ are positive integers. Using the equality ${\omega }^{\alpha }+{\omega }^{\beta }={\omega }^{\beta }$ for $\alpha <\beta$ it is clear that ${\gamma }_1+{\gamma }_2={\gamma }_2$ if ${\beta }_1^2>{\beta }_1^1$.

Now our element ${\alpha }_0\in C$ can be written ${\alpha }_0={\omega }^{\beta }k+\gamma$ where ${\omega }^{\beta }k$ is the first term of its Cantor Normal Form. For any $\delta \in C$, we can write its euclidean division by ${\alpha }_0$: $\delta ={\alpha }_{0}l+\epsilon$ where $\epsilon <{\alpha }_0$. By the previous discussion, if $l\ge \omega$ then we can write the Cantor Normal Forms of the two elements ${\alpha }_0<\delta$ as in (4) and see that ${\beta }_1^2>{\beta }_1^1$. Hence ${\alpha }_0+\delta =\delta$ and so $\overline{{\alpha }_0}=0$, which is a contradiction. So $l<\omega$ and because $C$ is stable by finite sums, ${\alpha }_{0}l\in C$ and by the property (3) we get $\epsilon \in C$. This means that $\overline{\delta }=\overline{{\alpha }_0}l+\overline{\epsilon }=\overline{{\alpha }_0}l$ and hence $G_C$ is generated by $\overline{{\alpha }_0}$ as claimed above.

As a conclusion, if $C\subseteq \mathrm{Card}$ satisfies the properties (1), (2) above and $G_C=\raisebox{1ex}{$Z_C$}\!\left/ \!\raisebox{-1ex}{$R$}\right.$ is a group then $C\subseteq \omega \subseteq \mathrm{Ord}$. If $C\subseteq \mathrm{Ord}$ satisfies properties (1), (2), (3) above and $G_C=\raisebox{1ex}{$Z_C$}\!\left/ \!\raisebox{-1ex}{$R$}\right.$ is a group then $G_C$ is isomorphic to $\mathbb{Z}$ or to $\raisebox{1ex}{$\mathbb{Z}$}\!\left/ \!\raisebox{-1ex}{$n\mathbb{Z}$}\right.$. Conversely, we can build these groups from $C=\omega$ by defining the relation $R$ as the equality (respectively the equality modulo $n$). But we do not get any new groups...

New solutions of some exercises from chapter 4 of Thomas Jech's book Set Theory.

So I'm finally done with the implementation of itex2MML in my mathparser. The current set of patches is available here and can be used in any Mozilla product based on mozilla-central. For those who don't know, itex2MML is a converter from a LaTeX-like syntax to MathML which was originally written, about ten years ago, by Paul Gartside for the Mozilla MathML Project. It has been maintained since then by Jacques Distler, who has made a great work to improve and extend it (and has also reported several bugs that helped us to make our MathML layout engine better ;-). Hence it is a mature tool and it is worth being based on it in order to provide a decent LaTeX-like parser.

You can find a list of itex2MML commands as well as various examples. All itex2MML commands are supported in my mathparser, except inclusion of SVG graphics, XML entities and obsolete maction's commands. There are also some additional features such that support for Unicode characters in the LaTeX input. Below are random demos:

$$\int_M K\;dA+\int_{\partial M}k_g\;ds=2\pi\chi(M), \, $$

$${\int }_{M}K\mathrm{dA}+{\int }_{\partial M}{k}_g\mathrm{ds}=2\pi \chi (M),$$

$$\oint_S \mathbf{E} \cdot \mathrm{d}\mathbf{A} = \frac{Q}{\varepsilon_0},$$

$${\oint }_{S}E\cdot \mathrm{d}A=\frac{Q}{{\epsilon }_0},$$

$$u = \root{3}{-{q \over 2} \pm \sqrt{{q^2 \over 4} + {p^3 \over 27}}}$$

$$u=\sqrt[3]{-\frac{q}{2}\pm \sqrt{\frac{q^2}{4}+\frac{p^3}{27}}}$$

$$\frac{a_0}{2} + \sum_{n=1}^\infty \, [a_n \cos(n x) + b_n \sin(n x)]$$

$$\frac{a_0}{2}+\sum _{n=1}^{\mathrm{\infty }}[a_n\cos (nx)+b_n\sin (nx)]$$

Så bliver det tre uger siden jeg forlod Århus. Jeg vil gerne take alle for et hyggeligt ophold og jeg håber at vi mødes igen! Jeg regner også med at blive en datalogiingeniør snart. De to næste år, skal jeg læse matematik ved Paris' Universitet. Så hvis i kommer til fransk hovedstad, i er meget velkommen til at besøge mig ;-)

Après une année Erasmus, j'ai finalement terminé ma formation d'ingénieur ENSIIE et espère obtenir mon diplôme bientôt ! Je suis maintenant de retour sur Paris et compte poursuivre ma formation en mathématiques à l'Université Pierre et Marie Curie (Paris VI). Au premier semestre mon choix se porte sur les modules de théorie de Galois et d'analyse réelle. J'envisage aussi de commencer une nouvelle langue parmi allemand, russe ou chinois... affaire à suivre !

One of my main idea after having studied the Hidden Subgroup Problem is that subgroup simplification is likely to play an important role. Basically, rather than directly finding the hidden subgroup $H$ by working on the whole initial group $G$, we only try to get partial information on $H$ in a first time. This information allows us to move to a simpler HSP problem and we can iterate this process until the complete determination of $H$. Several reductions of this kind exist and I think the sophisticated solution to HSP over 2-nil groups illustrates well how this technique can be efficient.

Using only subgroup reduction, I've been able to design an alternative algorithm for the Dedekindian HSP i.e. over groups that have only normal subgroups. Recall that the standard Dedekindian HSP algorithm is to use Weak Fourier Sampling, measure a polynomial number of representations ${\rho }_1,\dots ,{\rho }_m$ and then get with high probability the hidden subgroup as the intersection of kernels $H=\bigcap _i\mathrm{Ker}{\rho }_i$. When the group is dedekindian, we always have $H\subseteq \mathrm{Ker}{\rho }_i$. Hence my alternative algorithm is rather to start by measuring one representation ${\rho }_1$, move the problem to HSP over $\mathrm{Ker}{\rho }_1$ and iterate this procedure. I've been able to show that we reach the group $H$ after a polynomial number of steps, the idea being that when we measure a non-trivial representation the size of the underlying group becomes at least twice smaller. One difficulty of this approach is to determine the structure of the new group $\mathrm{Ker}{\rho }_i$ so that we can work on it. However, for the cyclic case this is determination is trivial and for the abelian case I've used the group decomposition algorithm, based on the cyclic HSP. Finally I've two open questions:

1. Can my algorithm work for the Hamiltonian HSP i.e. over non-abelian dedekindian groups?
2. Is my algorithm more efficient than the standard Dedekindian HSP?

For the first question, I'm pretty sure that the answer is positive, but I admit that I've not really thought about it. For the second one, it depends on what we mean by more efficient. The decomposition of the kernel seems to increase the time complexity but since we are working on smaller and smaller groups, we decrease the space complexity. However, if we are only considering the numbers of sample, my conjecture is that both algorithms have the same complexity and more precisely yield the same markov process. In order to illustrate this, let's consider the cyclic case $G={\mathbb{Z}}_{18}$ and $H=6{\mathbb{Z}}_{18}$. The markov chain of the my alternative algorithm is given by the graph below, where the edge labels are of course probabilities and the node labels are the underlying group. We start at $G={\mathbb{Z}}_{18}$ and want to reach $H\cong {\mathbb{Z}}_3$.

One can think that moving to smaller and smaller subgroups will be faster than the standard algorithm which always works on ${\mathbb{Z}}_{18}$. However, it turns out that the markov chain of the standard algorithm is exactly the same. The point being that while it is true that working over ${\mathbb{Z}}_9$ or ${\mathbb{Z}}_6$ provides less possibilities of samples (3 and 2 respectively, instead of 6 for ${\mathbb{Z}}_{18}$) the repartition of "good" and "bad" samples is the same and thus we get the same transition probabilities. I guess it would be possible to formalize this for a general cyclic group. The general abelian case seems more difficult, but I'm sure that the same phenomenon can be observed.

I've submitted my report on The Hidden Subgroup Problem to arXiv.org and I expect it to be published soon.

Comments are welcome on this blog entry.

--update 03/08/2010: a pdf version is available on arXiv.org. You can still find a Web version as well as my slides on my website.

Back to the DHSP again (see part 1 and part 2 in previous blog posts)... This time, I've tried to approximate the value of $d$ rather than finding its parity. For convenience, we assume $N$ to be even and define $N\text{'}=2M=\frac{N}{2}$. We consider for $a\in {\mathbb{Z}}_N$ and $b\in {\mathbb{Z}}_2$ the sets of $N\text{'}$ successive values$$F_a^b=\{f(a+i,b),i\in {\mathbb{Z}}_{N\prime }\}$$

We suppose that we can efficiently create uniform superposition over these states. As in part 2, we have $F_a^1=F_{a-d}^0=F_s^0$ with $-N<s<N$ and we measure the tensor product of the uniform superpositions over $F_a^1=F_s^0$ and $F_0^0$ in the basis ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$. We define $l=\mid F_0^0\cap F_a^1\mid$ the number of common elements.

The figure above shows that in the case $0\le s\le N\text{'}$, we have $l=N\text{'}-s$. In general, the expression is

$$l=\mid N\text{'}-\mid s\mid \mid =\mid N\text{'}-\mid d-a\mid \mid$$

Using an analysis similar to the one part 2, we get the probability to measure an element in ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$:

$$P=\frac{1}{2}[1-{\left(\frac{l}{N\prime }\right)}^2]$$

Repeating the measurements, we can approximate $P$, and consequently $l,s$ and finally $d$. We can also play with the value $a$, to improve the approximation. Unfortunately, using a number of repetitions polynomial in $\log N$, it does not seem possible to bound the error better than $O\left(N\right)$. It seems however that it is still a better result than the one that I obtained with the standard Coset Sampling method. Hence it is another hint of the fact that using a superposition over several oracles values would yield improvement.

I'm still wondering how to create efficiently an uniform superposition over several oracle values. One thing I've read in many papers, is given a superposition over elements $\mid x⟩\mid f(x)⟩$, erase or uncompute the first register to get a superposition over elements $\mid f(x)⟩$. However, I'm not sure what are the requirements to apply such an operation. If it could work for the algorithm of part 2, then this would solve the case $N=2^n$.