Minimal weight expansions in Pisot bases
| dc.creator | Frougny, Christiane | |
| dc.creator | Steiner, Wolfgang | |
| dc.date | 2008-03-19 | |
| dc.date | 2009-01-09 | |
| dc.date.accessioned | 2026-07-07T12:27:20Z | |
| dc.date.available | 2026-07-07T12:27:20Z | |
| dc.description | For applications to cryptography, it is important to represent numbers with a small number of non-zero digits (Hamming weight) or with small absolute sum of digits. The problem of finding representations with minimal weight has been solved for integer bases, e.g. by the non-adjacent form in base~2. In this paper, we consider numeration systems with respect to real bases $β$ which are Pisot numbers and prove that the expansions with minimal absolute sum of digits are recognizable by finite automata. When $β$ is the Golden Ratio, the Tribonacci number or the smallest Pisot number, we determine expansions with minimal number of digits $\pm1$ and give explicitely the finite automata recognizing all these expansions. The average weight is lower than for the non-adjacent form. | |
| dc.identifier | https://arxiv.org/abs/0803.2874 | |
| dc.identifier | http://arxiv.org/abs/0803.2874 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/215172 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Cryptography and Security | |
| dc.subject | Number Theory | |
| dc.title | Minimal weight expansions in Pisot bases | |
| dc.type | text |