Phase transitions in number theory: from the birthday problem to Sidon sets

Luque Serrano, Bartolome and Torre, Ivan G. and Lacasa Saiz de Arce, Lucas (2013). Phase transitions in number theory: from the birthday problem to Sidon sets. "Physical Review e" ; pp.. ISSN 1539-3755. https://doi.org/10.1103/PhysRevE.88.052119.

Description

Title: Phase transitions in number theory: from the birthday problem to Sidon sets
Author/s:
  • Luque Serrano, Bartolome
  • Torre, Ivan G.
  • Lacasa Saiz de Arce, Lucas
Item Type: Article
Título de Revista/Publicación: Physical Review e
Date: 12 November 2013
Subjects:
Faculty: E.T.S.I. Aeronáuticos (UPM)
Department: Matemática Aplicada y Estadística [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (228kB)

Abstract

In this work, we show how number theoretical problems can be fruitfully approached with the tools of statistical physics. We focus on g-Sidon sets, which describe sequences of integers whose pairwise sums are different, and propose a random decision problem which addresses the probability of a random set of k integers to be g-Sidon. First, we provide numerical evidence showing that there is a crossover between satisfiable and unsatisfiable phases which converts to an abrupt phase transition in a properly defined thermodynamic limit. Initially assuming independence, we then develop a mean-field theory for the g-Sidon decision problem. We further improve the mean-field theory, which is only qualitatively correct, by incorporating deviations from independence, yielding results in good quantitative agreement with the numerics for both finite systems and in the thermodynamic limit. Connections between the generalized birthday problem in probability theory, the number theory of Sidon sets and the properties of q-Potts models in condensed matter physics are briefly discussed

More information

Item ID: 29159
DC Identifier: http://oa.upm.es/29159/
OAI Identifier: oai:oa.upm.es:29159
DOI: 10.1103/PhysRevE.88.052119
Deposited by: Memoria Investigacion
Deposited on: 10 Oct 2014 15:46
Last Modified: 13 Nov 2014 18:10
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM