Roots of the $k$-XORSAT threshold equation

edit · history · discussion · files · long url · statistical mechanics probability theory

Numbers

$k$

$\xi_k$

2.149125799907062542079080149425149925528828496714285459034660801183768221524370129087681616217046728

comment: The associated satisfiability threshold is $\alpha_{3}$.

3.593511969447426082272169884555315798860946340951301392760865045230967927293167350976509334752600022

comment: The associated satisfiability threshold is $\alpha_{4}$.

4.801007549722517843402554184936876206309580045670987737307642940448096932959992199826971793616174495

comment: The associated satisfiability threshold is $\alpha_{5}$.

5.903000058948943810458175385422799724242893481515842146827627134583507853576375177519654679441566068

comment: The associated satisfiability threshold is $\alpha_{6}$.

6.953455713353474571757750459668776777157703675694193843415968941936946472738479953900380174362202268

comment: The associated satisfiability threshold is $\alpha_{7}$.

7.978107736977070325801043211904953879262698393828180241246253405412112875926606187603354958634672340

comment: The associated satisfiability threshold is $\alpha_{8}$.

8.989912519269479737859486962678439859820876867181214191191759058921700750894868987723157685967200046

comment: The associated satisfiability threshold is $\alpha_{9}$.

10:

9.995441133814842741400932592133052045659869599058257396947103091116896080275781481170753765750751443

comment: The associated satisfiability threshold is $\alpha_{10}$.

11:

10.99797533724523459964809795243574469075450093882819090308597431902540854000078754311674399450335085

comment: The associated satisfiability threshold is $\alpha_{11}$.

12:

11.99911450952184187994188030867116719218749935503081985334373686869595954724308587188802621404555431

comment: The associated satisfiability threshold is $\alpha_{12}$.

Definition

For an integer $k\geq3$, $\xi_k$ is the unique positive real solution of $k=\xi(1-e^{-\xi})/(1-e^{-\xi}-\xi e^{-\xi})$ [1].

Parameters

$k$

— number of variables in each equation ($k\geq3$)

Formulas

(1)

$\psi(\xi_k)=k$, where $\psi(x)=\frac{x(1-e^{-x})}{1-e^{-x}-xe^{-x}}$.

(2)

$\alpha_k=\frac{\xi_k}{k(1-e^{-\xi_k})^{k-1}}$ for $k\geq3$ [1].

Comments

(3)

$\xi_k$ is the value of $x$ at $\alpha=\alpha_k$ in the 2-core description of the satisfiability threshold of random $k$-XORSAT [3], where $x=k\alpha q^{k-1}$ and $q=1-e^{-x}$ [1].

Programs

(P1)

Python

from mpmath import mp
mp.dps = 50
k = 3
psi = lambda x: x*(1-mp.e**(-x))/(1-mp.e**(-x)-x*mp.e**(-x))
xi = mp.findroot(lambda x: psi(x) - k, k)
print(xi)

References

[1]

B. Pittel and G. B. Sorkin, The satisfiability threshold for $k$-XORSAT, Combinatorics, Probability and Computing 25 (2016), 236-268. (arXiv) (doi)

[2]

M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh and M. Rink, Tight thresholds for cuckoo hashing via XORSAT, Proceedings of ICALP 2010, Lecture Notes in Computer Science 6198, 213-225. (arXiv) (doi)

Links

[3]

Wikipedia: XOR-SAT

Similar tables

Satisfiability thresholds of random $k$-XORSAT — thresholds obtained from these roots by the formula for $\alpha_k$

Roots of the cuckoo hashing threshold equation — the same roots in the rows with bucket capacity $\ell=1$ and $k\geq3$

Data properties

Entries are of type: real number

How well the digits are known: proven

Sources of data: [1]

Table is complete: no (it holds $\xi_k$ for every $k$ with $3\leq k\leq12$, the range of the satisfiability thresholds $\alpha_k$; at the end of this range, $0<12-\xi_{12}<10^{-3}$)

How they were obtained:

Each entry is computed in ball arithmetic with 64 guard bits beyond the 100 digits written. The root $\xi_k$ is enclosed by bisection on the sign of $\psi(x)-k$, down to a bracket of half-width $10^{-106}$, with the signs at the two ends checked in ball arithmetic; that bracket is the stored ball.

The generator compares every row with an mpmath solve at 120 digits, and compares the derived thresholds for $3\leq k\leq7$ with the ten-decimal table in [2].