Back to Search
Start Over
Phase transitions in Number Theory: from the Birthday Problem to Sidon Sets
Phase transitions in Number Theory: from the Birthday Problem to Sidon Sets
- Source :
- Physical Review e, ISSN 1539-3755, 2013-11-12, Archivo Digital UPM, Universidad Politécnica de Madrid
- Publication Year :
- 2013
-
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.<br />Submitted for publication
- Subjects :
- Discrete mathematics
Statistical Mechanics (cond-mat.stat-mech)
010102 general mathematics
Crossover
Complex system
FOS: Physical sciences
Decision problem
16. Peace & justice
01 natural sciences
Birthday problem
Aeronáutica
Number theory
Probability theory
0103 physical sciences
Thermodynamic limit
0101 mathematics
010306 general physics
Independence (probability theory)
Condensed Matter - Statistical Mechanics
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Physical Review e, ISSN 1539-3755, 2013-11-12, Archivo Digital UPM, Universidad Politécnica de Madrid
- Accession number :
- edsair.doi.dedup.....74fc1217998fe72ad640229731f02a06