Pierre Popoli (LORIA, Univ. de Lorraine)

The sum of digits function in base 2, also called the Hamming weight, is the number of non-zero binary digits of an integer. This function is a central object for all my present research and appears in many scientific fields, such as number theory, combinatorics on words, and coding theory. In this talk, I will present how this function is a central object of my research.

The first part of my research work focused on generating pseudorandom sequences from non-random ones. Pseudorandom sequences are generated by a deterministic algorithm and behave like random sequences. Many scientific fields use pseudorandom sequences, such as cryptography for a cryptographic key generation or numerical integration for Monte Carlo methods. One of the challenges of this research area is to generate a pseudorandom sequence efficiently. In particular, automatic sequences are generated by an automaton, and their structures are deterministic. The Thue-Morse sequence, the sum of digits function in base two modulo 2, is the most well-known example of an automatic sequence. We use indicators called measures of complexity to qualify a sequence of pseudorandom. My two first papers deal with the maximum order complexity of a sequence, namely the length of the shortest Feedback Shift Register (FSR) that generates the sequence. This measure of complexity evaluates if a sequence is predictable and suitable for cryptographic applications. In the first paper, I proved a lower bound on the maximum order complexity of polynomial subsequences of the Thue-Morse sequence, depending on the degree of the polynomial. In a second paper, with D. Jamet and T. Stoll, we study the analog of the Thue-Morse sequence in the Zeckendorf numeration system based on the Fibonacci sequence. The sum of digits function in this numeration system is close to the one associated with the Thue-Morse but has very different properties. Hence, we proved a lower bound for the maximum order complexity of these sequences along polynomial subsequences. Still, this result differs slightly from the previous one since the carry propagation works differently.

The second part of my research deals with specific Diophantine equations related to the sum of digits function in base two. Firstly Bennett, Bugeaud, and Mignotte (2012) have proved that there is only a finite number of perfect odd squares with four binary digits. Also, they conjectured that the set of solutions is 13,15, 47, and 111. In a recent paper, we have proved that this conjecture is true for odd integers with at most 17 non-zero binary digits and a similar result for the case of perfect odd squares with five binary digits. Secondly, Hare, Laishram, and Stoll (2012) studied odd integers with the same number of bits as their square, and they proved a global result for most cases. Finally, we have proved most of the remaining cases in the same paper. The proofs rely on elementary properties of the sum of digits function, combinatorics, and two efficient algorithms. This paper is a joint work with Aloui, Jamet, Kaneko, Kopecki, and Stoll.