Distribution results for low weight representations for pairs of integers

Peter Grabner, Clemens Heuberger and Helmut Prodinger

This item was put here on January 30, 2003.

It all began when I detected the Solinas paper on the internet. When I visited Graz last year, we started to discuss it. Peter used his old Thuswaldner method and said bong, finished. I was not completely happy with that and started to draw and plot patterns of 0 and 1. So, the fractal structure was empirically discovered. Meanwhile, Clemens translated Solinas' algorithms into transducers. He has some software to minimize automata. Without that, no chance. And also amazing software to print them! One sunday afternoon, I asked myself, what would I do if I would have to create as many double zeros as possible - and the simple joint sparse form was born. We nicknamed it Cheap Solinas. The same evening, we had dinner at Clemens' place - yes, this guy can even cook - and we discussed it. I was a bit too optimistic about something, but still. Then I left Graz, and the poor guys had to continue alone. Meanwhile, a baby was born to one of us which slowed the process down a bit. I transmitted the idea of the d-dimensional generalization to Clemens, and he worked it all out on a train ride to Berlin. Several nice graphics did not make it to the paper, e.g. an automation with 9 states, sitting in the 9 countries, and the borders printed as a background pattern.


This paper is available in the PostScript and PdF format.
(Back to List of Papers)