Low autocorrelation binary sequences : statistical mechanics and configuration space analysis

Abstract
Binary sequences with low off-peak autocorrelations play an important role in several communication engineering applications. The problem of finding such sequences is equivalent to the problem of determining the low-energy configurations of a specific spin model with long-range 4-spin interactions. Using a simulated annealing procedure, the statistical mechanics of this spin model, which exhibits frustration without disorder, is analysed in detail. Comparison is made with predictions based on a simple « ergodicity assumption » which moreover may be used to derive an estimate for the true ground-state energy. Our results are consistent with the occurrence of an « ergodicity-breaking » phase transition at a finite temperature. For long sequences, the energy minima found with the simulated annealing procedure differ by about a factor of 2 from the conjectured groundstate energy, indicating that the lowest-energy configurations must be extremely isolated in configuration space. The annealed minima, finally, do not seem to exhibit a non-trivial ultrametric structure.

Résumé
Des suites binaires avec faible autocorrélation jouent un rôle important dans divers problèmes de communication. Le problème de trouver de telles suites est équivalent au problème de la détermination des configurations de faible énergie dans un modèle particulier de spin avec interactions à 4 spins de longue portée. Utilisant une méthode de recuit simulé, nous analysons en détail la mécanique statistique de ce modèle de spin, qui présente des frustrations mais pas de désordre. Nous comparons nos résultats avec des prédictions basées sur une hypothèse simple d'ergodicité qui, de plus, conduit à une estimation de l'énergie de l'état fondamental. Nos résultats suggèrent l'apparition d'une transition de phase du type « brisure d' ergodicité », à temperature finie. Pour des suites longues, les minima d'énergie trouvés par la méthode de recuit simulé diffèrent d'un facteur 2 de l'énergie du fondamental conjecturé, ce qui indique que les configurations d'énergie minimale sont extrêmement isolées dans l'espace de configuration. Enfin les minima trouvés par le recuit simulé ne semblent pas présenter de structure ultramétrique non triviale.