The Satisfiability Threshold for k-XORSAT

Introduction

Random instances of many problems of this sort undergo phase transitions around some critical ratio $c^{*}$ of $m/n$, meaning that for $m,n\to\infty$ with $\lim m/n<c^{*}$, the probability that a random instance $F_{n,m}$ is satisfiable (or possesses some similar property) approaches $1$, while if $\lim m/n>c^{*}$ the probability approaches . (There is no loss of generality in hypothesizing the existence of a limit since, in a broad context, a result as stated implies the same with the weaker hypotheses $\liminf m/n>c^{*}$ and $\limsup m/n<c^{*}$.) Friedgut proved that a wide range of problems have such sharp thresholds, but with the possibility that the threshold $c^{*}=c^{*}(n)$ does not tend to a constant. The relatively few cases in which $c^{*}$ is known to be a constant include 2-SAT, by Chvátal and Reed , Goerdt , and Fernandez de la Vega (with the scaling window detailed by Bollobás, Borgs, Chayes, Kim, and Wilson, ), an extension to Max 2-SAT, by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin , and the pure-literal threshold for a $k$-SAT formula, by Molloy .

The most natural random model of the $k$-XORSAT problem is the “unconstrained” model in which each of the $m$ equations’ $k$ variables are drawn uniformly (without replacement) from the set of all $n$ variables, and the right hand side values are uniformly 0 or 1; equivalently a random instance $Ax=b$ is given by a matrix $A\in\{0,1\}^{m\times n}$ drawn uniformly at random from the set of all such matrices with each row sum equal to $k$, and $b\in\{0,1\}^{m}$ chosen uniformly at random.

The case $k=2$ has been extensively studied. As shown by Kolchin and Creignon and Daudé , the random instance has a solution with limiting probability $p(2m/n)+o(1)$, where $p(x)\in(0,1)$ for $x<1$, $p(1-)=0$, and $p(x)\equiv 0$ for $x>1$. Daudé and Ravelomanana , and Pittel and Yeum , analyzed the near-critical behavior of the solvability probability for $2m/n=1+\varepsilon$, $\varepsilon=o(n^{-1/4})$.

For $k>2$, Kolchin analyzed the expected number of nonempty “critical row sets” (nonempty collections of rows whose sum is all-even), whose presence is necessary and sufficient for the (Boolean) rank of $A$ to be less than $m$. He determined the thresholds $c_{k}$ such that the expected number of nonempty critical sets goes to 0 if $\lim m/n<c_{k}$ and to infinity if $\lim m/n>c_{k}$; in particular, $c_{3}=0.8894\dots$. Thus, for $\lim m/n<c_{k}$, with high probability $A$ is of full rank, so $Ax=b$ is solvable. It follows that the satisfiability threshold $c^{*}_{k}$ is at least $c_{k}$. It is an easy observation (see Remark 3) that $c^{*}_{k}\leq 1$. However, Kolchin could not resolve the precise value, or even the existence, of the satisfiability threshold.

Dubois and Mandler (see also ) introduced a “constrained” random $k$-XORSAT model, where $b$ is still uniformly random, but $A$ is uniformly random over the subset of matrices in which each column sum is at least 2. For $k=3$ (3-XORSAT) they showed that its threshold for $m/n$ is 1. This is of interest because from the threshold for the constrained model, they were able to derive that for the unconstrained model. Dubois and Mandler suggested that their methods could be extended to the general constrained $k$-XORSAT, $k\geq 3$. However, their approach — the second-moment method for the number of solutions — requires solving a hard maximization problem with $\Theta(k)$ variables, a genuinely daunting task.

Our main result is that 1 continues to be the threshold for all $k>3$.

Let $Ax=b$ be a uniformly random constrained $k$-XORSAT instance with $m$ equations and $n$ variables. Suppose $k\geq 4$. If $m,n\to\infty$ with $\lim m/n\in(2/k,1)$ then $Ax=b$ is asymptotically almost surely (a.a.s.) satisfiable, with satisfiability probability $1-O(m^{-(k-2)})$, while if $m,n\to\infty$ with $\lim m/n>1$ then $Ax=b$ is a.a.s. unsatisfiable, with satisfiability probability $O(2^{-(m-n)})$.

We treat $k$ as fixed, and the constants implicit in the $O(\dot{)}$ notation may depend on $k$. We are also able to treat the case when the gap between $m$ and $n$ is not linear but arbitrarily slowly growing, obtaining the following stronger theorem.

Let $Ax=b$ be a uniformly random constrained $k$-XORSAT instance with $m$ equations and $n$ variables, with $k\geq 3$ and $m,n\to\infty$ with $\liminf m/n>2/k$. Then, for any $w(n)\to+\infty$, if $m\leq n-w(n)$ then $Ax=b$ is a.a.s. satisfiable, with satisfiability probability $1-O(m^{-(k-2)}+\exp(-0.69\,w(n)))$, while if $m\geq n+w(n)$ then $Ax=b$ is a.a.s. unsatisfiable, with satisfiability probability $O(2^{-w(n)})$.

Rather than using the second-moment method on the number of solutions, as Dubois and Mandler do, we use the critical-set approach of Kolchin. Remark 5 shows that the two methods are equivalent, but Kolchin’s leads us to more tractable calculations, specifically, to a maximization problem with a number of variables that is fixed, independent of $k$. Using Kolchin’s approach, but in the constrained model, we will establish that $c^{*}_{k}\geq 1$. In the constrained and unconstrained models, a simple argument shows that $c^{*}_{k}\leq 1$ (again see Remark 3). Thus, for the constrained model (unlike the constrained one), the two bounds coincide, establishing the threshold.

Dubois and Mandler extended the threshold for the constrained 3-XORSAT model to that for the unconstrained model by observing that, in an unconstrained instance, any variable appearing in just one clause (or none), can be deleted along with that clause (if any), to give an equivalent instance, and this process can be repeated. The key observation is that a uniformly random unconstrained instance reduces to a uniformly random constrained instance with a predictable edge density; the threshold for the unconstrained model is the value for which the corresponding constrained instance has density 1. The same approach works for any $k$, and we capitalize on existing analyses of the 2-core of a random $k$-uniform hypergraph to establish the unconstrained $k$-XORSAT threshold in Theorem 16.

Work on the rank of random matrices over finite fields is not as extensive as that on real random matrices, but nonetheless a survey is beyond our scope. In addition to the work already described, we note that the rank of matrices with independent random 0–1 entries was explored over a decade ago by Blömer, Karp and Welzl , and Cooper , among others.

Recently, Darling, Penrose, Wade and Zabell have explored a random XORSAT model replacing the constant $k$ with a distribution, but the satisfiability threshold has not yet been determined for this generalization.

To translate our result for the constrained model to the unconstrained one, we exploit results on the core of a random hypergraph. For usual graphs, the threshold for the appearance of an $r$-core was first obtained by Pittel, Spencer, and Wormald . For $k$-uniform hypergraphs, the $r$-core thresholds were obtained roughly concurrently by Cooper , Kim , and Molloy . Two aspects of Cooper’s treatment are noteworthy. First, he works with a degree-sequence hypergraph model; taking Poisson-distributed degrees reproduces the results for a simple random hypergraph. Also, he observes [8, Section 5.2] that the point at which a random $k$-uniform hypergraph’s core has a (typical) edges-to-vertices ratio of 1 is an upper bound on the satisfiability threshold of unconstrained $k$-XORSAT; proving that this is the true threshold is the main subject of the present paper.

Outline

The remainder of the paper is organized as follows. Section 2 formalizes our introductory observations about the first- and second-moment methods, the number of solutions, and the number of critical sets. Section 3 shows that for the constrained model, instead of considering random 0–1 matrices $A$, it is asymptotically equivalent to consider random nonnegative integer matrices $A$ subject to the same constraints on row sums (equal to $k$) and column sums (at least $2$). Section 4, using generating functions and Chernoff’s method, obtains an exponential bound for the expected number of critical sets of any given cardinality. Section 5 uses this bound to show that, for $\lim m/n\in(2/k,1)$ and $k>3$, the expected number of nonempty critical sets is $O(m^{-(k-2)})$. Hence, with high probability, there is no such set, $A$ is of full rank, and the instance is satisfiable. We conclude that 1 is a sharp threshold for satisfiability of $Ax=b$ in the constrained case for all $k\geq 3$.

Section 6 builds on the earlier results to treat the case $\lim m/n=1$ and prove Theorem 2. Section 7 derives the unconstrained $k$-XORSAT threshold from the constrained one, using standard results on the 2-core of a random hypergraph.

Proof background

Let $N$ be the number of solutions to the system of equations $Ax=b$.

Note that the collection of critical sets is sandwiched between the minimal linearly dependent sets of rows, and all linearly dependent sets of rows. It is useful because the minimal sets are hard to characterize, while the collection of all linearly dependent row sets is too large (as it includes all sets containing any linearly dependent sets); the critical sets are a happy medium.

where $n(A^{\mathsf{T}})$ denotes the nullity of the transpose of $A$.

Probability spaces

This section will establish Corollary 8, showing that the uniform distribution over constrained $k$-XORSAT matrices $A\in\mathcal{A}_{m,n}$ (see below) is for our purposes equivalent to a model $C\in\mathcal{C}_{m,n}$ allowing a variable to appear more than once within an equation.

Let $\mathcal{A}_{m,n}$ denote the set of all $m\times n$ matrices with 0–1 entries, such that all $m$ row sums are $k$, and all $n$ column sums are at least 2. For $\mathcal{A}_{m,n}$ to be nonempty it is necessary that $km\geq 2n$, and we will assume that $m,n\to\infty$ with $\lim m/n\in(2/k,1)$.

A matrix $A\in\mathcal{A}_{m,n}$ may be interpreted as an outcome of the following allocation scheme. We have an $m\times n$ array of cells with $k$ indistinguishable chips assigned to each of the $m$ rows. For each row, the $k$ chips are put in $k$ distinct cells (so there is at most one chip per cell), subject to the constraint that each column gets at least two chips.

Let us consider an alternative model, with the same constraints but where the chips in each row are distinguishable, giving allocations $B\in\mathcal{B}_{m,n}$. Then each allocation in $\mathcal{A}_{m,n}$ is obtained from $(k!)^{m}$ allocations in $\mathcal{B}_{m,n}$, and the uniform distribution on $\mathcal{A}_{m,n}$ is equivalent to that on $\mathcal{B}_{m,n}$.

Let $\mathcal{C}_{m,n}$ be a relaxed version of $\mathcal{B}_{m,n}$, without the requirement that each of the $mn$ cells gets at most one chip. Let $B$ and $C$ be distributed uniformly on $\mathcal{B}_{m,n}$ and $\mathcal{C}_{m,n}$, respectively. Crucially, and obviously, $B$ is equal in distribution to $C$, conditioned on $C\in\mathcal{B}_{m,n}$.

To state a key lemma on $\left|\mathcal{A}_{m,n}\right|$, $\left|\mathcal{B}_{m,n}\right|$, and $\left|\mathcal{C}_{m,n}\right|$ we need some notation, much of which will recur throughout the paper.

with $\psi(0)=2$ defined by continuity, and the truncated Poisson random variable $Z=Z(\lambda)$,

(With $\psi=xf^{\prime}(x)/f(x)$, (3) and (3) hold for $f$ and $Z$ defined by any series $a_{j}x^{j}$, not just $x^{j}/j!$, assuming convergence.)

From (3) it is immediate that $\psi^{\prime}(\lambda)>0$ for any $\lambda>0$. (See also a general formulation in [31, Chapter 4, problem 6, p. 77].) The next claim shows that $\psi$ is convex as well as increasing, and establishes both facts for all $\lambda$ (though we only require them for positive $\lambda$).

$\psi(x)$ is strictly increasing, and convex.

We begin with convexity. Differentiating (1) shows that $\psi^{\prime\prime}=g/f^{3}$, where

Write $g(x)=\sum_{j\geq 0}g_{j}x^{j}$. Expanding (5) as a sum of terms $x^{a}e^{bx}=\sum_{j\geq 0}\tfrac{b^{j}x^{a+j}}{j!}$, and collecting like terms, we find that $g_{j}=0$ for $j\leq 5$, while for all $j\geq 6$,

Positivity is trivial for $j\geq 8$ and easily checked for $j=6$ and $7$. This establishes that $g(x)>0$ for $x>0$. Substituting $x=-y$ in $g(x)$, writing $g(x)=e^{-2y}\sum_{j\geq 0}g^{\prime}_{j}y^{j}$, and using the same method yields $g^{\prime}_{j}=0$ for $j\leq 5$, while for $j\geq 6$, $g^{\prime}_{j}=\frac{1}{j!}(2^{j+1}-j^{3}+4j^{2}-7j-4)>0$. This establishes that $g(x)>0$ for $x<0$. Finally, $\psi^{\prime\prime}(0)=1/9$. Therefore $\psi^{\prime\prime}(x)>0$ for all $x$.

That $\psi^{\prime}(x)>0$ follows from $\lim_{x\to-\infty}\psi^{\prime}(x)=0$ and $\psi^{\prime\prime}>0$. ∎

Under our assumption that $m/n>2/k$, the equation $\psi(x)=km/n$ has a unique root, and it is positive. This follows from the facts that $\psi(x)$ is strictly increasing (see Claim 6), $\psi(0)=2$, and $\psi(x)\to\infty$ as $x\to\infty$. Henceforth, let

be this root. Since by Claim 6 $\psi$ is strictly increasing, so is $\lambda=\psi^{-1}$.

From Claim 6, for $\lambda>0$, $\psi^{\prime}(\lambda)$ lies between $\psi^{\prime}(0)=1/3$ and $\lim_{x\to\infty}\psi^{\prime}(x)=1$, and thus

With these preliminaries done, we focus on asymptotics of $\left|\mathcal{A}_{m,n}\right|$, $\left|\mathcal{B}_{m,n}\right|$ and $\left|\mathcal{C}_{m,n}\right|$.

Suppose $m,n\to\infty$ with $\lim m/n\in(2/k,\infty)$. Then, with $\lambda$ as in (6),

so that the fraction $\left|\mathcal{B}_{m,n}\right|/\left|\mathcal{C}_{m,n}\right|$ is bounded away from zero. Consequently

Under the hypotheses of Lemma 7, uniformly for all non-negative, matrix-dependent functions $r$,

The first equality is trivial. To show the second, for any $S\subseteq\mathcal{B}_{m,n}$,

Equation (11) is immediate from (9) and (10). Proving (9) and (10) will occupy the rest of this section.

We first prove (9). To determine $\left|\mathcal{C}_{m,n}\right|$, recall that each row $i\in m$ is given its own $k$, mutually distinguishable, chips. We can get an allocation $C\in\mathcal{C}_{m,n}$ by permuting all the chips and allocating the first $j_{1}\geq 2$ chips to column 1, the next $j_{2}\geq 2$ chips to column 2, etc.; each chip goes to its predetermined row and its random column. Up to the irrelevant permutation of chips within the first $j_{1}$, the next $j_{2}$, etc., an allocation $C\in\mathcal{C}_{m,n}$ is uniquely determined by such a scheme.

Observe that the probability generating function (p.g.f.) of the truncated Poisson random variable $Z(\lambda)$ defined in (2) is

Following the notational convention that for $h(z)=\sum_{j}h_{j}z^{j}$, $[z^{j}]\,h(z):=h_{j}$, we have

where $Z_{1}(\lambda),\dots,Z_{n}(\lambda)$ are independent copies of $Z(\lambda)$. Now, since $\operatorname{Var}[Z(\lambda)]=\Theta(\lambda)$ (by (8)) and $\liminf\lambda>0$ (by $\lambda=\lambda(km/n)$ and the hypothesis that $\lim m/n>2/k$), we have $\liminf\operatorname{Var}[Z(\lambda)]>0$. So, by a local limit theorem (Aronson, Frieze and Pittel [2, equation (5)]),

We now prove (10). Let $C=\{c_{i,j}\}$ be distributed uniformly on $\mathcal{C}_{m,n}$. Let $M$ denote the number of cells that house $2$ or more chips, i.e., M=\bigl{|}\{(i,j)\colon c_{i,j}\geq 2\}\bigr{|}. Let $\overline{M}$ be the number of pairs of chips hosted by the same cell, i.e.,

$\overline{M}=M$ iff there are no cells hosting more than $2$ chips. Clearly

Denoting the indicator of an event $E$ by $\boldsymbol{1}(E)$, we write

where $E(i,j;u,v)$ is the event that, of the $k$ chips owned by row $i$, at least the two chips $u$ and $v$ were put into cell $(i,j)$. Each of these $mn\binom{k}{2}$ event indicators has the same expected value,

To see why (17) is so, compare with (14) and note that once we have put two selected chips into a cell $(i,j)$ we allocate the remaining $(km-2)$ chips amongst $n$ columns, at least two per column, with the exception (hence the sole $e^{x}$ factor) that the $j$th column receives an unconstrained number of additional chips (as it already has two). Arguing as for (15),

where $X(\lambda)$ stands for an independent, usual (not truncated) Poisson$(\lambda)$ random variable. This last probability equals

with the usual falling-factorial notation $(a)_{b}:=a(a-1)\cdots(a-b+1)$. Recalling (6) and setting

More generally, we now show that for every fixed $t\geq 1$ we have

Let $\boldsymbol{T}$ be the set of all 4-tuples $(i,j,u,v)$ as before, with $i\in[m]$, $j\in[n]$, and $1\leq u<v\leq k$. Now let $(\boldsymbol{T})_{t}$ denote the collection of $t$-tuples of such 4-tuples with all the 4-tuples distinct. Where $\{(i_{\tau},j_{\tau},u_{\tau},v_{\tau})\}_{\tau=1}^{t}\in(\boldsymbol{T})_{t}$, in a slight abuse of notation we will write $(\boldsymbol{i},\boldsymbol{j},\boldsymbol{u},\boldsymbol{v})\in(\boldsymbol{T})_{t}$, where $\boldsymbol{i}=(i_{1},\dots,i_{t})$, $\boldsymbol{j}=(j_{1},\dots,j_{t})$, $\boldsymbol{u}=(u_{1},\dots u_{t})$, $\boldsymbol{v}=(v_{1},\dots,v_{t})$. Then we have

We break the sum into two parts, $\Sigma_{1}$ and the remainder $\Sigma_{2}$, where $\Sigma_{1}$ is the restriction to $\boldsymbol{i}$ and $\boldsymbol{j}$ each having all its components distinct. In $\Sigma_{1}$ the number of summands is $(m)_{t}(n)_{t}\binom{k}{2}^{t}$, and each summand is

see the explanation following (17). Analogously to (18),

where the $n$ truncated and ordinary Poisson random variables $Z_{j}(\lambda)$ and $X_{s}(\lambda)$ are mutually independent. Since $t$ is fixed, the probability remains asymptotic to \bigl{(}2\pi n\operatorname{Var}[Z(\lambda)]\bigr{)}^{-1/2}. So, using (9) and recalling (19), we have

In the case of $\Sigma_{2}$, letting $I=\{i_{1},\dots,i_{t}\}$, $J=\{j_{1},\dots,j_{t}\}$, we have $|I|+|J|\leq 2t-1$. So the number of attendant pairs $(I,J)$ is at most (m+n)^{2t-1}=O\bigl{(}m^{2t-1}\bigr{)}. The number of pairs $(\boldsymbol{i},\boldsymbol{j})$ inducing a given pair $(I,J)$ is bounded above by a constant $s(t)$. For every one of those $s(t)$ choices, we select pairs of chips for each of the chosen $t$ cells; there are at most $\binom{k}{2}^{t}$ ways of doing so. Lastly, we allocate the remaining $(km-2t)$ chips in such a way that every column $j\in[n]\setminus J$ gets at least $2$ chips. As in the case of $\Sigma_{1}$, this can be done in

ways. Again, the probability is asymptotic to \bigl{(}2\pi n\text{Var}[Z(\lambda)]\bigr{)}^{-1/2}. So, as $e^{\lambda}>f(\lambda)$, the sum $\Sigma_{2}$ is of order

Combining (21) and (22), and recalling (19), we conclude that for each fixed $t\geq 1$,

Therefore $\overline{M}$ is asymptotic, with all its moments and in distribution, to $\operatorname{Po}(\gamma)$. In particular,

Counting critical row subsets, and the main result

This section will prove Theorem 1. Remark 3 already dealt with the case $\lim m/n>1$. It suffices, then, to show that with $\lim m/n\in(2/k,1)$, the expected number of nonempty critical row sets goes to 0: then with high probability there is no such set, $A$ is of full rank, and the instance is satisfiable.

Lemma 10 is established by several claims deferred to Section 5, and Section 7 extends Theorem 1 to the unconstrained $k$-XORSAT model (Theorem 16).

by continuity we define $x\ln x=0$ at $x=0$, and $H(\alpha)$ is the usual entropy function

By the independence of constraints on column sums for the upper and the lower submatrices of the matrices $C$ in question,

Since the coefficients of the Taylor expansion around $z=0$ of $e^{z\nu}f(z)^{n-\nu}$ are non-negative, we use these identities in a standard (Chernoff) way to bound

The bound (34) follows from three components: the Cauchy integral formula

and (with $z=z_{2}e^{i\theta}$) the identity |e^{z}|=e^{z_{2}}\exp\bigl{[}-z_{2}(1-\cos\theta)\bigr{]} and the less obvious inequality

(See Pittel [26, Appendix] for the inequality, and Aronson, Frieze and Pittel [2, inequality (A2)] for how it works in combination with the Cauchy formula.)

Using (29), (30), (33), (34), with $\left|\mathcal{C}_{m,n}\right|$ from (9) and $\operatorname{Var}{Z(\lambda)}$ from (8), we obtain that, $\forall\,z_{1},z_{2}>0$,

Now, it is immediate from (25), (26), and (29) that

Recall the definition of $H_{k}(\alpha,\boldsymbol{\zeta};c)$ from (24). Roughly speaking, the following lemma establishes the existence of $\boldsymbol{\zeta}$ making $H_{k}(\alpha,\boldsymbol{\zeta};c)$ negative. An intuitive description of the behavior of $H_{k}(\alpha,\boldsymbol{\zeta};c)$ is given at the start of the next section.

For all $k\geq 4$ and $c\in(2/k,1)$, there exist $\varepsilon=\varepsilon(c,k)>0$ and $\zeta_{0}=\zeta_{0}(c,k)>0$, both functions continuous in $c$, such that

The lemma follows immediately from Claims 12, 13 and 15, all stated and proved in Section 5, respectively treating $\alpha$ in the ranges $(0,0.99\alpha_{k}]$, $[0.99\alpha_{k},1/2]$, and $(1/2,1]$. A suitable function $\boldsymbol{\zeta}$ is given explicitly in each case. ∎

The lemma yields the following corollary.

For $k\geq 4$ and $m,n\to\infty$ with $\lim m/n\in(2/k,1)$,

Since $\lim m/n\in(2/k,1)$, there exists a closed interval $I\subset(2/k,1)$ such that, for all but finitely many cases, $c=m/n\in I$. Where $\varepsilon(c,k)$ and $\zeta_{0}(c,k)$ satisfy the conditions of Lemma 10 define $\varepsilon=\varepsilon(I)=\min\{\varepsilon(c,k)\colon c\in I\}$, and $\zeta_{0}=\zeta_{0}(I)$ likewise; the minima exist by continuity of $\varepsilon$ and $\zeta_{0}$ in $c$. Then, for all but finitely many pairs $m,n$, inequalities (40) and (41) hold true.

Adding the two partial sums yields Corollary 11. ∎

Recall the notation $\bar{\alpha}=1-\alpha$ and $\boldsymbol{\zeta}=(\zeta_{1},\zeta_{2})$ as well as the definition of $H_{k}(\alpha,\boldsymbol{\zeta};c)$ from (24). In this section we use an explicit function $\boldsymbol{\zeta}=\boldsymbol{\zeta}(c,k,\alpha)$, taking different forms in different ranges of $\alpha$, to establish Claims 12, 13 and 15 and thus Lemma 10.

For intuition about $H_{k}(\alpha,\boldsymbol{\zeta};c)$, the case $k=4$ is indicative. Figure 1 shows a graph of the function value against $\alpha$, for a few choices of $c$, with $\boldsymbol{\zeta}$ given by (43) for small $\alpha$, and by $\boldsymbol{\zeta}=(\alpha,\bar{\alpha})$ otherwise. Numerical experiments suggest that the optimal choice of $\boldsymbol{\zeta}$ leads to qualitatively similar results, though of course without the kinks where we change from one functional form for $\boldsymbol{\zeta}$ to another. As shown, $H_{k}(\alpha,\boldsymbol{\zeta};c)$ tends to 0 at $\alpha=0$ (treated in Claim 12), but the dependence on $c$ here is not critical: an analog of the claim, with different parameters, could be obtained as long as $c$ is bounded away from 0 and infinity. At $\alpha=1/2$ (treated in Claim 13), the function tends to 0 as $c$ tends to 1, so this is where $c<1$ is required. Claim 13 also covers values of $\alpha$ between 0 and $1/2$ but bounded away from them; here the function value is bounded away from 0 (for $c\leq 1$) and could be dealt with by cruder means, such as that by interval arithmetic in . Function values for $\alpha>1/2$ (treated in Claim 15) are dominated by their symmetric counterparts at $1-\alpha$, except for some special treatment required near $1$.

Lemma 10 only considers $k>3$. The lemma can be extended to $k=3$, but this case was already treated by and the proof poses additional difficulties for us; see further discussion after the proof of Claim 13, and in Section 6, specifically at (76).

For all $k\geq 3$ and all $c\in(2/k,1]$, taking

yields $H_{k}(\alpha,\boldsymbol{\zeta};c)\leq(c\alpha)(\tfrac{k}{2}-1)\ln(\alpha/\alpha_{k})$ for all $\alpha\in(0,\alpha_{k})$. Also, for any $\delta=\delta(k)>0$ there exists $\varepsilon=\varepsilon(k)>0$ such that $H_{k}(\alpha,\boldsymbol{\zeta};c)<-\varepsilon$ for all $\alpha\in[\delta,0.99\alpha_{k}]$. In both cases, $\zeta_{2}\geq\zeta_{0}(k):=1-\alpha_{k}>0$.

The first part of the claim establishes (40), and the second part, with $\delta=\alpha_{k}/3$, establishes (41) for $\alpha\in[\alpha_{k}/3,0.99\alpha_{k}]$. As both $\varepsilon$ and $\zeta_{0}$ depend only on $k$ they are automatically continuous (constant) with respect to $c$, thus satisfying the hypothesis of Lemma 10.

Trivially, $\zeta_{2}=\bar{\alpha}\geq 1-\alpha_{k}>0$, since $\alpha_{k}=ek^{-k/(k-2)}<e/k<1$. The issue in this range of $\alpha$ is to control the final logarithmic term of $H_{k}(\alpha,\boldsymbol{\zeta};c)$ when the two summands within the logarithm are nearly equal. Note that $\ln f(x)$ is concave on either side of 0 (diverging to $-\infty$ at , it is not concave as a whole), as

Since $\left.\frac{d}{d\Delta}\ln f(\lambda(1+\Delta))\right|_{\Delta=0}=\frac{\lambda f^{\prime}(\lambda)}{f(\lambda)}$, if $\lambda$ and $\lambda\!\cdot\!(1+\Delta)$ are on the same side of 0 (i.e., if $1+\Delta\geq 0$) then concavity gives $\ln f(\lambda(1+\Delta))\leq\ln f(\lambda)+\Delta\frac{\lambda f^{\prime}(\lambda)}{f(\lambda)}$. Or, with $\zeta=1+\Delta$, if $\zeta\geq 0$ then

recalling from (6) that $\lambda f^{\prime}(\lambda)/f(\lambda)=ck$. It is easily checked that (39) gives $\alpha_{k}<0.2$, hence from (43) $\zeta_{2}>0.8$ and $\zeta_{1}<0.4$, so $\zeta_{2}-\zeta_{1}\geq 0$ and of course $\zeta_{2}+\zeta_{1}\geq 0$. Thus for the final term of $H_{k}(\alpha,\boldsymbol{\zeta};c)$, from (45) we have

using the well known inequality $\cosh x\leq e^{x^{2}/2}$ Now also using $-\bar{\alpha}\ln\bar{\alpha}\leq\alpha$ for all $\bar{\alpha}\in[0,1)$, substituting $\boldsymbol{\zeta}$ from (43) into $H_{k}(\alpha,\boldsymbol{\zeta};c)$,

Pessimistically taking $c=1$ within the logarithm and recalling $\alpha_{k}$ from (39),

(A different upper bound for $c$ would simply call for a different value for $\alpha_{k}$.) This proves the first part of the claim.

Clearly, for all $\alpha\in(0,\alpha_{k})$, $\alpha\ln(\alpha/\alpha_{k})$ is negative, so for any $\delta=\delta(k)>0$, over $\alpha\in[\delta,0.99\alpha_{k}]$ it is bounded away from 0. By hypothesis, $c\geq 2/k$ (any positive constant would do), thus $H_{k}(\alpha,\boldsymbol{\zeta};c)$ is also bounded away from 0, i.e., there is some $\varepsilon=\varepsilon(k)>0$ for which $H_{k}(\alpha,\boldsymbol{\zeta};c)\leq-\varepsilon$. This proves the second part of the claim. ∎

For all $k\geq 4$ and all $c\in(2/k,1)$, there exists $\varepsilon=\varepsilon(c,k)>0$, with $\varepsilon(c,k)$ continuous in $c$, such that for all $\alpha\in[0.99\alpha_{k},1/2]$, taking

yields $H_{k}(\alpha,\boldsymbol{\zeta};c)<-\varepsilon$ and (trivially) $\zeta_{2}\geq\zeta_{0}:=1/2$.

Recall the definition of $H_{k}(\alpha,\boldsymbol{\zeta};c)$ in (24), including its use of $\lambda=\lambda(kc)=\psi^{-1}(kc)$, i.e., $\psi(\lambda)=kc$ (see (6)). If we let

The advantage of $H_{k}(\alpha;\lambda)$ over $H_{k}(\alpha,\boldsymbol{\zeta};c)$ is that the former is an explicit function of the “hidden” parameter $\lambda=\lambda(ck)$, while the latter depends on $c$ both explicitly, and implicitly via $\lambda(ck)$. (To put it another way, $\lambda$ appears repeatedly in $H_{k}(\alpha,\boldsymbol{\zeta};c)$ and is only implicitly defined as $\psi^{-1}$ (see (6)), where $\psi$ appears just once in $H_{k}$ and is explicitly defined (see (1)).)

Since $\lambda(\cdot)$ is increasing (see after (6)) and $c\in(2/k,1)$,

We now argue that it suffices to consider only the largest possible value of $c$, namely $c=1$, or correspondingly of $\lambda$, namely $\lambda=\lambda_{k}$. Referring back to the original question about the $k$-XORSAT phase transition, in the unconstrained model such a form of monotonicity is obvious: if random instances of given density are a.a.s. satisfiable, the same is true of sparser instances, as there is a coupling in which we simply eliminate some constraints. But in the constrained model in which we are now working, monotonicity is not obvious: it is not clear that sparser instances are more likely to be satisfiable than denser ones. We attempted unsuccessfully to show this by converting to and from the unconstrained model.

In the next part we prove a more limited form of monotonicity, in a short following section we show as a consequence that it suffices to show that $H_{k}(\alpha;\lambda_{k})\leq 0$, and in a third part we do so.

For $k\geq 4$, there exists a $\sigma_{k}>0$ such that for all $\alpha\in[0.99\alpha_{k},1/2]$ and $\lambda\in[0,\lambda_{k}]$,

In words, as a function of $\lambda$, $H_{k}(\alpha;\lambda)$ is strictly increasing when it is non-negative.

By (50), the condition $H_{k}(\alpha;\lambda)\geq 0$ is equivalent to

Differentiating (50), under the assumption that $H_{k}(\alpha;\lambda)>0$ and using (53) and (54) in the first inequality,

where the second inequality uses that $\psi^{\prime}(\lambda)>0$ and, by convexity of $\psi$ (see Claim 6 for both), that $\psi(\lambda(1-2\alpha))-\psi(\lambda)\geq-2\lambda\alpha\psi^{\prime}(\lambda)$.

Now, regarding $g(\alpha;\lambda)$ as an independent quantity, the RHS of (55) is decreasing with $g(\alpha;\lambda)$, and for $\lambda\leq 1/2$

since concavity of $\ln f(x)$ for $x>0$ (see (44)) means that $\ln g(\alpha;\lambda)\leq-2\alpha\lambda\frac{d}{d\lambda}(\ln f(\lambda))=-2\alpha\lambda\frac{f^{\prime}(\lambda)}{f(\lambda)}=-2\alpha\psi(\lambda)$. It follows then from (55) that

Using $\ln(x)\leq x-1$ we can confirm that $\ln\frac{2}{1+e^{-x}}=-\ln(\tfrac{1}{2}+\tfrac{1}{2}e^{-x})\geq-(\tfrac{1}{2}e^{-x}-\tfrac{1}{2})=\frac{\sinh(x)}{1+e^{x}}$, from which

By definition (see (6)), $\psi(\lambda)=ck$, and here, $x=2\alpha\psi(\lambda)=2\alpha ck\leq k$. With this, (57) and (58),

For the final inequality, calling again on Claim 6, $\psi^{\prime}$ is increasing, so $\psi^{\prime}(\lambda)\geq\psi^{\prime}(0)=1/3$. Here we in the range $\alpha\geq 0.99\alpha_{k}$, and again $\psi(\lambda)=ck$, which by hypothesis is $>2$. This establishes (52) with $\sigma_{k}:=1.7\alpha_{k}^{3}/(1+e^{k})$.

Application of monotonicity

For $c\in(2/k,1)$ as hypothesized in the Claim, we will show that

By continuity of $H_{k}(\alpha;\lambda)$, the supremum is attained at some $(\hat{\alpha},\hat{\lambda})$. Recall from (51) that $\lambda(ck)<\lambda_{k}$. By (52), if $H_{k}(\hat{\alpha};\hat{\lambda})\geq 0$ then $\partial H_{k}(\hat{\alpha};\lambda)/\partial\lambda\geq\sigma_{k}$ for all $\lambda\in[\hat{\lambda},\lambda_{k}]$, implying that $H(\hat{\alpha},\lambda_{k})>0$. In the next part we will show that this is impossible — that $H(\alpha,\lambda_{k})\leq 0$ — and thus that $m_{k}(c)<0$. For Claim 13 we may thus take $\varepsilon(c,k)=-m_{k}(c)$. That this is continuous in $c$ is immediate from continuity of $H_{k}(\alpha;\lambda)$.

Analysis of the extreme case

The proof of the Claim is complete except for treatment of the extreme case, $c=1$ or equivalently $\lambda=\lambda_{k}$, namely showing that

for all $\alpha\in[0.99\alpha_{k},1/2]$. (Observe, e.g. from (61) below, that $H_{k}(1/2)=0$.) We begin with

where inequality (62) uses that, as $H^{\prime\prime}(\alpha)\leq-4$,

Case $\alpha$ near $1/2$. It is immediate from (62) that $H_{k}(\alpha)\leq 0$ for $\alpha$ sufficiently close to $1/2$, namely for $\alpha\in[{\alpha^{*}_{k}},1/2]$, where

Let us confirm that ${\alpha^{*}_{k}}\in(0,1/2)$, i.e., that $\frac{1}{\lambda_{k}}\ln(f(\lambda_{k})/\lambda_{k}^{2})\in(0,1)$. First, we show that for all $k\geq 3$, $\lambda_{k}>k-1$. This is equivalent to $k>\psi(k-1)$, or explicitly to $e^{k-1}>1+k(k-1)$, which follows for $k\geq 7$ by use of $e^{x}>1+\tfrac{1}{6}x^{3}$, and simply by checking for $k<7$. Then, by definition, $k=\psi(\lambda_{k})=\lambda_{k}+{\lambda_{k}^{2}}/{f(\lambda_{k})}$, so $\lambda_{k}>k-1$ implies that $\lambda_{k}^{2}/f(\lambda_{k})<1$, giving $\tfrac{1}{\lambda_{k}}\ln(f(\lambda_{k})/\lambda_{k}^{2})>0$. Also, $\lambda_{k}>k-1$ implies $\lambda_{k}\geq 1$, from which $f(\lambda_{k})/\lambda_{k}^{2}\leq f(\lambda_{k})<e^{\lambda}_{k}$, and $\tfrac{1}{\lambda_{k}}\ln(f(\lambda_{k})/\lambda_{k}^{2})<1$.

Case $\alpha$ away from $1/2$. We now treat $\alpha\in[0.99\alpha_{k},{\alpha^{*}_{k}}]$ through two sub-cases.

Subcase $k\geq 7$. Since $\frac{f(\lambda_{k}\!\cdot\!(1-2\alpha))}{f(\lambda_{k})}=g(\alpha;\lambda)\leq e^{-2\alpha k}$ (by (48) and (56), the latter relying on $\alpha\leq{\alpha^{*}_{k}}\leq 1/2$), we have from (61) that

Let us show that ${\alpha^{*}_{k}}$ decreases with $k$, implying that $H({\alpha^{*}_{k}})\leq H(\alpha^{*}_{7})$. Since $\lambda(\cdot)$ is increasing (see after (6)), it suffices to show that $\tfrac{1}{x}\ln(f(x)/x^{2})$ increases with $x$ for $x\geq\lambda_{3}$; we will show it for all $x>0$. Differentiating,

so we must show that $G(x)<0$ for $x>0$. Now, $\lim_{x\downarrow 0}G(x)=-\ln 2<0$, so it suffices to show that G^{\prime}(x)=\bigl{(}\psi(x)-2-x\psi^{\prime}(x)\bigr{)}/x\leq 0, or equivalently $\psi(x)-2-x\psi^{\prime}(x)\leq 0$. This is true, since this expression is at $x=0$ and its derivative is simply $-\psi^{\prime\prime}(x)$, which is $\leq 0$ by convexity of $\psi$ (see Claim 6).

Also, recalling the definition of $\alpha_{k}$ from (39), differentiation immediately shows that $\alpha_{k}k=ek^{-2/(k-1)}$ increases with $k$, so that $\alpha_{k}k\geq 7\,\alpha_{7}$.

So, for $k\geq 7$ and $\alpha\in[0.99\alpha_{k},{\alpha^{*}_{k}}]$, (66) yields the cruder bound

Subcase $k=4,5,6$. Notice that, for $\alpha\in[0,1/2]$, the entropy term $H(\alpha)$ in (61) for $H_{k}(\alpha)$ is increasing, while the logarithmic term is decreasing. Consequently, if $0<x<x^{\prime}\leq 1/2$ are such that

then $H_{k}(\alpha)<0$ for all $\alpha\in[x,x^{\prime}]$. A collection of such intervals $[x,x^{\prime}]$ covering $[0.99\alpha_{k},{\alpha^{*}_{k}}]$ gives an “interval arithmetic” proof that $H_{k}(\alpha)\leq 0$ on $[0.99\alpha_{k},{\alpha^{*}_{k}}]$, and there is an elegant iterative procedure for finding such a cover.

by convexity of $H$. Thus, inequality (68) is satisfied if the RHS of (69) is 0, i.e., if

(Note that $H_{k}(x)<0$, so $x^{\prime}>x$.) We apply (70), reminiscent of Newton-Raphson, as an iterative update rule, with $x_{i}=x$ and $x_{i+1}=x^{\prime}$, to cover the interval $[0.99\alpha_{k},{\alpha^{*}_{k}}]$.

For $k=6$, taking $x_{0}=x=0.99\alpha_{k}\approx 0.1831$ gives $x_{1}=x^{\prime}\approx 0.2620$, showing that $H_{6}(\alpha)\leq 0$ on $[x_{0},x_{1}]$. Then, taking $x=x_{1}$ gives $x_{2}=x^{\prime}\approx 0.3421$, showing that $H_{6}(\alpha)\leq 0$ on $[x_{1},x_{2}]$. Since $\alpha^{*}_{6}<0.3024<x_{2}$, for $k=6$ these two intervals suffice to prove negativity of $H_{k}(\alpha)$ over $[0.99\alpha_{k},{\alpha^{*}_{k}}]$.

For $k=5$, following the same procedure covers $[0.99\alpha_{k},{\alpha^{*}_{k}}]$ with 3 intervals. Likewise, for $k=4$, $[0.99\alpha_{k},{\alpha^{*}_{k}}]$ is covered with 8 intervals.

In fact, (67) and a check of the intervals for $k=4,5,6$ yields that, for $k\geq 4$,

We have not addressed $k=3$, already treated by , and indeed with $\boldsymbol{\zeta}$ as above, $H_{3}(\tfrac{1}{2},\boldsymbol{\zeta};1)$ is positive. We remark that we can extend Claim 13 to $k=3$ by choosing $\boldsymbol{\zeta}$ differently, notably as given by (76). The motivation is that the equalities (76) hold for the optimal $\boldsymbol{z}=\lambda\boldsymbol{\zeta}$ at the stationary points $(\hat{\alpha},\hat{k})$ of the function $\min_{\boldsymbol{z}}H_{k}(\alpha,\boldsymbol{z}/\lambda;\psi^{-1}(ck))$, assuming (without justification) that the implicit-differentiation rules apply. The monotonicity condition (the equivalent of (52)) then applies for all $\alpha\in(0,1/2]$. For details, see [27, Appendix (b)]. An interval arithmetic argument verifies that this choice makes $H_{3}(\alpha,\boldsymbol{\zeta};1)<0$ for $\alpha\in[0.99\alpha_{3},\alpha^{*}_{3}]$, as we will show after (76) where this is needed to treat the phase transition more precisely. If we make this extension, Claim 15 also extends immediately to $k=3$.

We also remark that if we alter the hypotheses of Claim 13 to exclude $\alpha$ near $1/2$ then we may allow $c=1$, as formalized below (where the choice of $0.49$ is arbitrary). This will be used when we narrow the phase transition window in Section 6.

For all $k\geq 4$ there exists $\varepsilon=\varepsilon(k)>0$, such that for all $\alpha\in[0.99\alpha_{k},0.49]$ and all $c\in[2/k,1]$, taking $\zeta_{1}=\alpha,\quad\zeta_{2}=\bar{\alpha}$ yields $H_{k}(\alpha,\boldsymbol{\zeta};c)<-\varepsilon$ and (trivially) $\zeta_{2}\geq\zeta_{0}:=1/2$.

The substitution gives $H_{k}(\alpha,\boldsymbol{\zeta};c)=H_{k}(\alpha;\lambda)$ (see (50)), the range $c\in[2/k,1]$ corresponds to $\lambda\in[0,\lambda_{k}]$, and it suffices to show that

In analogy with (59), by continuity, the supremum over this closed domain is achieved at some $(\hat{\alpha},\hat{\lambda})$. We prove by contradiction that $H_{k}(\hat{\alpha},\hat{\lambda})<0$. If not, $H_{k}(\hat{\alpha},\hat{\lambda})\geq 0$. If $\hat{\lambda}<\lambda_{k}$ then as argued previously this implies $H_{k}(\hat{\alpha},\lambda_{k})=H_{k}(\hat{\alpha})>0$, while if $\hat{\lambda}=\lambda_{k}$ then, directly, $H_{k}(\hat{\alpha})\geq 0$. We now show that $H_{k}(\alpha)<0$ for $\alpha\in[0.99\alpha_{k},0.49]$, by modifying the previous argument that $H_{k}(\alpha)\leq 0$ for $\alpha\in[0.99\alpha_{k},1/2]$. Referring to (65), for any ${\alpha^{+}_{k}}$ with ${\alpha^{*}_{k}}<{\alpha^{+}_{k}}<0.49$, inequality (62) shows that $H_{k}(\alpha)<0$ for $\alpha\in[{\alpha^{+}_{k}},0.49]$. (Recall that ${\alpha^{*}_{k}}$ is decreasing in $k$ — see after (66) — so for all $k\geq 3$, ${\alpha^{*}_{k}}\leq\alpha^{*}_{3}<{0.4630}$.) And from (67), continuity shows that for some $\alpha^{+}_{7}$ slightly larger than $\alpha^{*}_{7}$ we have $H_{k}(\alpha)<-0.018$ for all $\alpha\in[0.99\alpha_{k},\alpha^{+}_{7}]$ and $k\geq 7$. Likewise, for the numerically treated cases $k=4,5,6$, (71) extends by continuity to show that, for some ${\alpha^{+}_{k}}$ slightly larger than ${\alpha^{*}_{k}}$, $H_{k}(\alpha)<-0.0011$ for all $\alpha\in[0.99\alpha_{k},{\alpha^{+}_{k}}]$. ∎