{'fraction_non_alphanumeric': 0.049116550494407524, 'fraction_numerical': 0.015669746582374237, 'mean_word_length': 3.783665029723443, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the critical exponents of random k-SAT

There has been much recent interest in the satisfiability of random Boolean formulas. A random k-SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2-SAT this happens when m/n -->1, for 3-SAT the critical ratio is thought to be m/n ~ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called \nu=\nu_k (the smaller the value of \nu the sharper the transition). Experiments have suggested that \nu_3 = 1.5+-0.1, \nu_4 = 1.25+-0.05, \nu_5=1.1+-0.05, \nu_6 = 1.05+-0.05, and heuristics have suggested that \nu_k -->1 as k -->infinity. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well-defined). This result holds for each of the three standard ensembles of random k-SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q-colorability and the appearance of a q-core in a random graph.


Introduction
In the past decade many researchers have studied the satisfiability of random Boolean formulas, in an attempt to understand the "average case" of NP-complete problems. See [15] for a survey. Let n denote the number of Boolean variables. A literal is either a Boolean variable or its negation. A k-clause is the OR (disjunction) of k literals whose underlying variables are all distinct. A random k-SAT formula is the AND (conjunction) of m uniformly random k-clauses. A formula is satisfiable if there is an assignment to the Boolean variables for which the formula evaluates to TRUE. For random 3-SAT it has been observed empirically [23] that there is a critical value α 3 ≈ 4.2 such that when n is large and m/n < α 3 − ε, the formula is nearly always satisfiable, while if m/n > α 3 + ε, the formula is nearly always unsatisfiable. Furthermore, determining whether or not a formula is satisfiable appears to be the hardest when the ratio m/n is about α 3 [23]. Similar phenomenona occur for other values k, except that for k = 2 the formulas are always easy (deterministically). Consequently there have been many empirical as well as rigorous studies of this transition from satisfiable to unsatisfiable.
It is known rigorously [12] that the SAT-to-UNSAT transition is sharp, i.e. that at some critical ratio of m/n the probability of satisfiability rapidly drops from close to 1 to close to 0. But for k > 2 it has not been proved that the critical ratio of m/n tends to a constant, as opposed to being a slowly varying function of n that oscillates between its known lower and upper bounds of (log 2)2 k−1 − (log 2 + 1)/2 − o k (1) [3] and (log 2)2 k [8]. (When k = 3, the tighter bounds of 3.42 [16] and 4.506 [11] are known.) One basic feature of the SAT-to-UNSAT transition is its characteristic width. This width is the amount ∆ by which m needs to be increased for the probability of satisfiability to drop from 2/3 to 1/3, or more generally, to drop from 1 − ε to ε. The characteristic width is thought to grow as a polynomial in n, so that ∆ = Θ(n 1−1/ν ), where the constant hidden by the Θ() depends on ε, but the critical exponent ν does not. (Using ν to denote this critical exponent is a rather unfortunate k "ν" for SAT-to-UNSAT transition width conjectured rigorous choice of notation, since in statistical mechanics ν refers to a related but different critical exponent, see e.g. [14,Chapter 7]. The exponent for the width would be denoted 2 − α, but we use ν in this paper to facilitate comparison with earlier studies of the k-SAT transition.) It is not obvious a priori that ν is well-defined, as it could in principle slowly oscillate with n or depend upon ε. For 2-SAT it was proved recently [5] that the characteristic width does in fact grow polynomially in n, and that ν = 3. There have been a number of experimental studies aimed at measuring the critical exponent ν for random k-SAT, as summarized in the above table, and several authors have conjectured that the exponent ν tends to 1 as k gets large. The purpose of this note is to provide a simple proof that for each fixed k, the characteristic width is always at least Θ(n 1/2 ), so that in particular, if the exponent ν is well-defined, it is always at least 2.
Remark: There is a related ensemble of random k-SAT formulas, in which each possible k-clause appears in the formula with probability p independently of the other clauses. For convenience we let M denote the total number 2 k n k of possible clauses. When pM ≈ m, this F n,p ensemble of random formulas will behave much like the F n,m ensemble of formulas defined above. But there is a limit on how sharp the SAT-to-UNSAT transition can be for the F n,p ensemble, due to the approximate relationship between p and the number of clauses in the formula. Even if pM = m, the number of clauses will be m ± Θ(m 1/2 ). It is thus straightforward to show that in the F n,p ensemble, the critical exponent ν must be at least 2. (This bound is closely related to the "Harris criterion" for disordered statistical mechanical systems [6] [7].) The (by now) standard proof of ν ≥ 2 for the F n,p ensemble depends on the variance in the number of clauses, which is zero for the F n,m ensemble. It is simple to define properties on sets of clauses such that there is a much sharper transition in the F n,m ensemble, with a smaller value of ν < 2 -one trivial example is the property "m ≤ 4.2n", for which ν = 1 in F n,m while ν = 2 in F n,p . Until now it has been suggested (on the strength of Monte Carlo experiments and heuristic arguments) that satisfiability is one such property. Despite this, we proceed to show that even for the F n,m ensemble, the characteristic width is at least Θ(n 1/2 ), so that ν (if it is well-defined) must be at least 2.
There are also a number of questionable conjectures about other features of random k-SAT formulas. For instance, for 3-SAT Crawford and Auton [10] study the value of m = m 1/2 (n), where m r (n) denotes the smallest value of m for which the fraction of satisfiable k-SAT formulas is ≤ r.
They fit m 1/2 (n) to a curve of the form m 1/2 (n) = α 3 n + An 1−1/ν , obtaining ν = 1 [9] and then later ν = 3/5 [10]. (The integrality of m by itself strongly suggests that ν ≥ 1.) While it is in principle conceivable that m 1/2 (n) = α 3 n + O(1), it is an easy consequence of our work that there can be at most one value of r for which m r (n) = α 3 n + o(n 1/2 ) (otherwise the SAT-to-UNSAT transition would be too sharp). For 2-SAT the special value of r is empirically about 91%, and for 3-SAT there is no reason to believe (and experimental reason not to believe) that the special value of r is 1/2. Selman and Kirkpatrick [28] estimated exponents for the characteristic width of the median computational difficulty of determining whether or not a random formula is satisfiable, where computational difficulty was measured in terms of the number of recursive calls made by Crawford and Auton's SAT-solver (Tableau). The exponents they obtained were 1.3 for 3-SAT, 1.25 for 4-SAT, and 1.1 for 5-SAT. We do not analyze the specific SAT-solver Tableau, but we can say something about the characteristic width of the computationally difficult problems for other SATsolvers. Many SAT-solvers use the "pure literal rule" before starting a backtracking search for a satisfying assignment. A SAT-solver using this rule will look for literals y in the formula such that y's negationȳ does not also appear in the formula. If such a literal y exists, then the SAT-solver sets y to TRUE and removes from the formula any clauses containing y, since the resulting simpler formula is satisfiable if and only if the original formula was satisfiable. Rigorously analyzing the median computational difficulty seems not so easy, but using our methods one can show that for these SAT-solvers the typical computational difficulty has critical exponent at least 2. By this we mean the following: if for m clauses there is probability p that the number of recursive calls is between L and U , then when there are m + ∆ clauses, the probability is Our method is general enough to be applicable to other types of sharp transitions. For instance, Pittel, Spencer, and Wormald [27] prove that there is a sharp transition for the appearance of a q-core in a random graph. (The q-core is the maximal subgraph for which each vertex has degree at least q.) They prove that the width of this transition is at most n 1/2+o(1) , but gave no lower bound. We prove that the width is at least Θ(n 1/2 ). (Independent of this present work, Kirkpatrick [19] has reported that experiments suggest that the width is Θ(n 1/2 ).) We can also supply lower bounds on the transition width of other graph properties, such as q-colorability.

Proofs of theorems
We now give a proof that ν ≥ 2 in F n,m that works simultaneously for k-SAT, q-colorability, the existence of a q-core, and a variety of other properties. Let M denote the number of possible items. In the case of k-SAT, the items will be the possible clauses on n variables, and M = 2 k n k . In the case of the q-core or q-colorability, the items will be the possible edges of a graph on n vertices, and M = n 2 . A property classifies sets of items into two types: sets which have the property (for convenience call them proper sets), and sets which do not have the property (improper sets). Satisfiability is a property on sets of clauses, q-colorability is a property on sets of edges, and the existence of a q-core of a graph is also a property on sets of edges. We may also be interested in non-monotone properties, such as the property that a certain SAT-solver does more than L recursive calls to determine the satisfiability of a set of clauses.
A bystander rule is a way of partitioning a set of items into two classes: the relevant items, and the bystander items. A bystander rule must satisfy the following constraint. Given a set of items A, let R be the relevant items, and let G be the bystander items. Then for any B ⊆ A, it must be that B has the property if and only if B \ G has the property. In this sense, the only relevant items for the property are those that are contained in R -that is, if one restricts attention to sets of items contained in A, the bystander items never affect the property.
In the case of k-SAT, we will use the "partially-free" bystander rule, which declares a clause to be a bystander if the underlying variable of one of its literals does not appear anywhere else in the formula. (Recall that the formula is the AND of the clauses in the set.) By setting this variable to an appropriate value, the clause can be satisfied without affecting our ability to satisfy the remaining clauses of the formula. Thus partially-free is in fact a valid bystander rule.
For the q-core and q-colorability, we also use the "partially-free" bystander rule, which in the context of graphs (and hypergraphs) declares an edge to be a bystander if one of its endpoints has degree 1. It is simple to check that partially-free is a valid bystander rule for these properties.
Remark: We could in principle use instead other bystander rules. One possibility is to declare any clause that eventually gets resolved by repeated application of the pure literal rule to be a bystander. But it is easier to analyze the partially-free bystander rule, and our objective to provide a simple rigorous proof.
where the o(1) term becomes small if m gets large while β and γ remain fixed.
Informally, Theorem 1 says that if there are many bystanders, then the transition cannot be too sharp. To prove this we use the following lemma: .
Here the o(1) term becomes small when the expected number of sampled red balls, sampled green balls, unsampled red balls, and unsampled green balls are each large.
We postpone the proof of this lemma to § 3, and proceed to the more interesting part of the proof. is unimodal in ℓ (from Lemma 2). Let the critical integers be ℓ 1 , ℓ 2 , . . . , ℓ c , and suppose that of these, ℓ µ maximizes f (). Then we can write Thus by Lemma 2, and then assuming g m ≥ γm and βm ≤ b ≤ (1 − β)m we get + Pr[f m has less than γm bystanders] To apply Theorem 1 to k-SAT, we need to show that many clauses are bystanders, and to apply it to the q-core and q-colorability thresholds, we need to show that many edges are bystanders.
Lemma 3. Suppose that the items are k-clauses, edges, or hyperedges on k vertices. Assume that k is fixed, and that m = O(n) random items are selected, either with replacement or without replacement. With high probability there will be This lemma says that the number of partially-free clauses or hyperedges is with high probability close to what one might naively expect. Since we use the lemma to disprove a number of experimental results and heuristic arguments, we give a careful proof of it in § 3. But first let us see how to use the lemma with Theorem 1.
Corollary 4. Let p 1 and p 2 be fixed numbers such that 1 > p 1 > p 2 > 0. Suppose that a random 3-SAT formula with n variables and m 1 clauses is satisfiable with probability ≥ p 1 and a random 3-SAT formula with n variables and m 2 clauses is satisfiable with probability ≤ p 2 . Then where the o(1) goes to 0 when n → ∞. In particular, Proof. For 3-SAT, when n is large, we know that m 1 /n and m 2 /n are both close to the critical ratio c 3 (n), where 3.42 ≤ c 3 (n) ≤ 4.571. (Details of the 4.506 upper bound are not available at this time, so here we use the established bound of 4.571 [18].) More generally for k-SAT, we know that for i = 1 or 2,č k − o(1) ≤ m i /n ≤ĉ k + o(1), whereč k andĉ k are lower and upper bounds on the critical k-SAT ratio c k (n) (which could conceivably be a function of n). Let m = n(c k (n) + t), where t is a positive constant that we will choose in a moment. By Lemma 3, the fraction of clauses which are partially-free is w.h.p.
Note that γ is monotone decreasing in c k (n), and that mβ(1 − β) = ntc k (n)/(c k (n) + t) is monotone increasing in c k (n), so that our bound from Theorem 1 is at least as good as For 3-SAT we take t = 0.3 to get the above-stated constant of 0.0015.
For the appearance of a q-core in a random graph, there is a sharp threshold, and furthermore the precise values of the critical ratio m/n = c q are known. It is known e.g. that c 3 ≈ 3.35, c 4 ≈ 5.14, c 5 ≈ 6.81, and c k = k + √ k log k + O(log k) [27]. We can lower bound the characteristic width for the appearance of the q-core in essentially the same that we did for k-SAT, except that here k = 2 even as q varies. (A larger value of k would correspond to the appearance of the q-core within a k-uniform hypergraph.) Corollary 5. For q ≥ 3, the transition for existence of a q-core has characteristic width ≥ Θ( √ n).
When one randomly adds edges one a time, w.h.p. the q-core jumps from size 0 to size Θ(n) with the addition of a single edge [27] -Corollary 5 is a statement about the timing of this jump. With q-colorability, it is known that there is a sharp threshold [1] for the number of edges that a random graph can have while still being q-colorable, but as with k-SAT, it is not known that c q is a bona fide constant rather than a slowly varying function of n that oscillates between its known upper and lower bounds. Luczak proved proved that c q /(q log q) → 1 as q → ∞, and it is known that 2.01 ≤ c 3 ≤ 2.495 [2] [17]. As with the q-core, here k = 2 even as q varies, and we have Corollary 6. For q ≥ 3, the transition for q-colorability has characteristic width at least Θ( √ n).

Proofs of lemmas
Proof of Lemma 2. For convenience let g = γm be the number of green balls, r = (1 − γ)m be the number of red balls, and b = βm be the number of balls selected. The precise probability that the bth ball is the ℓth red ball is The ratio of successive terms is which is monotone in ℓ and implies the unimodality claim. Next we identify the mode: so that the optimal ℓ is given by ℓ = ⌈rb/(r + g + 1)⌉, which is within 1 of rb/(r + g).
Since ℓ ≤ r, r − ℓ ≤ m − b, b − ℓ ≤ b, and g − b + ℓ ≤ g, the error term will be ≤ 1, so we may drop it to get an upper bound. If the second term on the right were larger than 1, then we could increase m while keeping the ratios g/m, ℓ/m, and b/m fixed, and thereby make the probability as large as we like, and in particular larger than 1. Thus we can drop this term as well: and upon substituting λ = (1 − γ)β ± 1/m we find (1)

Remark:
One referee suggested an alternative to Lemma 3, which has worse constants but a much shorter proof. The proof of the alternative lemma focuses on "nearly free" variables/vertices rather than clauses/edges, and uses standard large deviation inequalities for martingales. We give here the original proof since it requires less background.
Proof of Lemma 3. Let r = 2 if the items we are interested in are clauses of k Boolean variables, and let r = 1 if the items are edges of a graph (k = 2) or k-uniform hypergraph (k ≥ 2). Recall that n is the number of variables or vertices. In each of these cases, the number M of possible items is M = r k n k . Recall our assumption that k is fixed and that we are looking at sets of m = O(n) items, so that functions of k and m/n may be written as O(1). A more detailed analysis could determine what happens when e.g. k → ∞ with n, but we do not attempt this.
Say that an item is d-free (1 ≤ d ≤ k), with respect to a set of items, if the first d variables (if the item is a clause) or the first d vertices (if the item is an edge or hyperedge) do not occur in any other items in the set.
The probability that an item is d-free when the m items are randomly selected without replacement is easily seen to be We use the identity to estimate each term in the product: (1) In the same manner as above we estimate each term in the product: Recall that an item is partially free if at least one of its variables/vertices is not contained in any of the other items. We use inclusion-exclusion to estimate the number of partially free items. Let X + C denote the event that item C is partially free, and X j 1 ,...,j d C denote the event that item C is free in positions j 1 , . . . , j d . Then