# Scale-Free Random SAT Instances
## 3 Scale-Free Random Formulas
### Some Properties of the Model  
In the case of the graph generator, we reject self-loops and repeated edges between two nodes. This makes the distribution of degrees follow a power-law, only asymptotically and for sparse graphs. In our case, we reject clauses with repeated variables. This is the reason that the reverse direction is invalid in the previous inequality. It also makes formulas follow a power-law distribution in the number of variable occurrences only asymptotically (see Theorem 1). In the following, we will discuss when the approximation for \(P(l_{1}\vee\cdots\lor l_{k})\approx\frac{k!\prod_{j=1}^{k}|l_{j}|^{-\beta}}{(2 \sum_{i=1}^{n}i^{-\beta})^{k}}\) is tight (Lemma 1). Notice that \(\sum_{i=1}^{n}i^{-\beta}=H_{n,\beta}\) are the _generalized harmonic numbers_. When \(n\) tends to infinity and \(\beta\
eq 1\), using the Euler-Maclaurin formula, they can be approximated as  
\[\sum_{i=1}^{n}i^{-\beta}=\zeta(\beta)+\frac{1}{1-\beta}n^{1-\beta}+\frac{1}{2 }n^{-\beta}+\mathcal{O}(n^{-\beta-1}) \tag{3}\]  
where \(\zeta(\beta)\) is the Riemann zeta function. When \(\beta=1\), we have  
\[\sum_{i=1}^{n}i^{-1}=\gamma+\log n+\mathcal{O}(n^{-1}) \tag{4}\]  
where \(\gamma\) is the Euler constant. This means that, when \(n\) tends to infinity, the probability of sampling variable \(x_{i}\) is \(P(x_{i})=o(1)\), when \(0\leq\beta\leq 1\), and \(P(x_{i})=i^{-\beta}/\zeta(\beta)+o(1)\), when \(\beta>1\). Due to the fact that the probability of sampling a variable does not vanish, when the number of variables tend to infinity and \(\beta>1\), may be troublesome. In particular, the probability of generating clauses with duplicated variables does not vanish, even for constant clause sizes. Similarly, to avoid duplicated variables, we also have to impose an upper bound \(k=o(n^{\min\{1/2,1-\beta\}})\). **Lemma 1**. : _When \(0\leq\beta<1\), the sizes of clauses are \(k=o(n^{\min\{1/2,1-\beta\}})\) and \(n\) tends to infinity, the probability of generating a clause with a duplicated variable tends to zero._  
_In these conditions, the probability of a random variable and the probability of a random clause in a formula are_  
\[P(x=x_{i})\approx\frac{i^{-\beta}}{\sum_{j=1}^{n}j^{-\beta}}\]  
\[P(C=l_{1}\vee\cdots\lor l_{k})\approx\frac{k!\prod_{i=1}^{k}|l_{i}|^{-\beta}}{ (2\sum_{i=1}^{n}i^{-\beta})^{k}}\]  
Proof. : We will use a result known as _surname problem_[33], which generalizes the _birthday paradox_. Let \(X_{1},\ldots,X_{k}\) be independent random variables which have an identical discrete distribution \(P(X=i)=p_{i}\), for \(i\geq 1\). Let \(R_{k}\) be the coincidence probability that at least two \(X_{j}\) have the same value. Let \(r_{k}=1-R_{k}\) be the non-coincidence probability. Then, \(r_{k}\) may be computed using the recurrence \(r_{0}=1\) and  
\[r_{k}=\sum_{j=1}^{k}(-1)^{j-1}\frac{(k-1)!}{(k-j)!}\,P_{j}\,r_{k-j}\]where \(P_{k}=\sum_{i\geq 1}(p_{i})^{k}\). The coincidence probability can be computed as \(R_{1}=0\) and  
\[R_{k}=R_{k-1}+\sum_{j=2}^{k}(-1)^{j}\frac{(k-1)!}{(k-j)!}\,P_{j}(1-R_{k-j})\]  
In our case, we face the problem of choosing \(k\) independent variables, and we want to compute the probability of obtaining a duplicated variable, i.e., a rejected clause. When \(\beta<1\), we have  
\[P_{k}=\frac{\sum_{i\geq 1}i^{-\beta k}}{(\sum_{i\geq 1}i^{-\beta})^{k}}=\frac{ \frac{1}{1-\beta k}n^{1-\beta k}+\zeta(\beta k)+\mathcal{O}(n^{-\beta k})}{( \frac{1}{1-\beta}n^{1-\beta}+\mathcal{O}(1))^{k}}=\frac{(1-\beta)^{k}}{1-\beta k }n^{1-k}+\zeta(\beta k)(1-\beta)^{k}n^{-(1-\beta)k}+\mathcal{O}(n^{-k})\]  
Depending on whether \(\beta k\) is greater or smaller than \(1\), the first or the second term of \(P_{k}\) will dominate. Since \(\frac{(k-1)!}{(k-j)!