The discrete Laplace asymptotic method and its application to the 3XOR satisfiability problem

J. William Helton, Jared A. Hughes, Peter Schlosser · 2025

Read The discrete Laplace asymptotic method and its application to the 3XOR satisfiability problem by J. William Helton, Jared A. Hughes, Peter Schlosser (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16420.txt.

Introduction

Sums over fine grids can behave like the integrals that the classic Laplace method handles, peaking sharply near one point. Jared A. Hughes, J. William Helton, and Peter Schlosser prove a discrete version of that method, covering sums whose terms only settle into shape in the limit. Grid sums and their weights both converge as the grid refines.

The driving use is a landmark 2002 result on when random 3XOR logic problems flip from solvable to unsolvable. That proof sketched several analytic steps, and the appendix here fills them all in with recent tools. The theorems should serve other counting problems too.

Catalog record

CREATORJ. William Helton, Jared A. Hughes, Peter Schlosser
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-16420

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The discrete Laplace asymptotic method and its application to the 3XOR satisfiability problem J. William Helton, Jared A. Hughes, Peter Schlosser Abstract . A standard way to calculate the asymptotic behavior of integrals of the form ∫ 𝒲 g ⁡ ( x ) ​ e − n ​ h ​ ( x ) ​ 𝑑 x \int_{\mathcal{W}}g(x)e^{-nh(x)}dx is the (continuous) Laplace asymptotic method. However, also discrete sums like ∑ x ∈ 𝒲 ∩ Λ n g n ​ ( x ) ​ e − n ​ h n ​ ( x ) \sum_{x\in\mathcal{W}\cap\Lambda_{n}}g_{n}(x)e^{-nh_{n}(x)} have similar behavior, when Λ n \Lambda_{n} is a discrete grid which becomes infinitely fine, and the functions g n g_{n} and h n h_{n} converge to g g and h h respectively. We go even further, and also derive the asymptotic formula for sums of the form ∑ x ∈ 𝒲 ∩ Λ n 𝒮 n ​ ( x ) \sum_{x\in\mathcal{W}\cap\Lambda_{n}}\mathcal{S}_{n}(x) , where the summand 𝒮 n ​ ( x ) \mathcal{S}_{n}(x) asymptotically behaves as g n ​ ( x ) ​ e − n ​ h n ​ ( x ) g_{n}(x)e^{-nh_{n}(x)} . The motivation, and also an immediate application, will be filling in all details in the classical breakthrough paper [ 5 ] , which gives the solvability (phase transition) threshold of the 3XOR-SAT problem using the second moment method. Various analytical arguments there were lightly described, but the appendix to this paper combines recent results to fill all of them in. We would expect our theorems on asymptotics to apply to other (especially combinatorial) problems as well. For example, they seem effective on 3XOR-GAME problems. [title=Index,columns=2] 2020 Mathematics Subject Classification Primary 41A60; Secondary 68Q87 Acknowledgements : Peter Schlosser was funded by the Austrian Science Fund (FWF) under Grant No. J 4685-N and by the European Union–NextGenerationEU. 1. Introduction The basic problem the discrete Laplace asymptotic method addresses goes as follows. The setting is in a bounded region \mathcal{W}\subseteq\mathbb{R}^{d} , for a fixed integer d\geq 1 . Moreover, we consider a sequence of lattices (1.1) \Lambda_{k}\coloneqq\frac{1}{n_{k}}A_{k}\mathbb{Z}^{d}+v_{k}, where (n_{k})_{k}\in\mathbb{N} is a sequence of integers with n_{k}\geq k , (v_{k})_{k}\in\mathbb{R}^{d} a sequence of vectors with \lim_{k\to\infty}v_{k}=v\in\mathbb{R}^{d} , and (A_{k})_{k}\in\mathbb{R}^{d\times d} is a sequence of matrices which converge as \lim_{k\to\infty}A_{k}=A to an invertible matrix A\in\mathbb{R}^{d\times d} . Given \mathcal{S}_{k}:\mathcal{W}\cap\Lambda_{k}\to\mathbb{C} a sequence of functions with asymptotic approximation \mathcal{S}_{k}(x)\sim g_{k}(x)e^{-n_{k}h_{k}(x)} , we want to see how \displaystyle\sum_{x\in\mathcal{W}\cap\Lambda_{k}}\mathcal{S}_{k}(x) behaves asymptotically as k\to\infty . If we are in a case where g_{k}\to g and h_{k}\to h , the sum may behave like a Riemann sum, and we optimistically obtain \displaystyle\sum_{x\in\mathcal{W}\cap\Lambda_{k}}\mathcal{S}_{k}(x)\sim\sum_{x\in\mathcal{W}\cap\Lambda_{k}}g_{k}(x)e^{-n_{k}h_{k}(x)}\sim\frac{n_{k}^{d}}{|\det(A_k)|}\int_{\mathcal{W}}g_{k}e^{-n_{k}h_{k}}dx\sim\Omega_{k}, where the classical Laplace method for integrals applies to give \displaystyle\Omega_{k}\coloneqq\frac{(2\pi n_{k})^{\frac{d}{2}}g(x_{0})e^{-n_{k}h(x_{0})}}{|\det(A)|\sqrt{\det(\mathcal{H}\{h\}(x_0))}}. Here, x_{0}\in\mathcal{W} is the point where the global minimum of the function h is obtained, and \mathcal{H}\{h\}(x_{0}) is the Hessian matrix evaluated at this point. The goal of this paper is to give reasonably general conditions under which these results do hold. More precisely, our first main result, Theorem 2.7 , implies that \displaystyle\sum_{x\in\mathcal{W}\cap\Lambda_{k}}g_{k}(x)e^{-n_{k}h_{k}(x)}\sim\Omega_{k} holds under precise conditions. Our second main result, Theorem 2.8 , then even proves \sum_{x\in\mathcal{W}\cap\Lambda_{k}}\mathcal{S}_{k}(x)\sim\Omega_{k}, in the same setting, plus a few assumptions connecting \mathcal{S}_{k} to g_{k}e^{-n_{k}h_{k}} . The papers’ final section, Section 3 , describes two applications to special systems of linear equations over the binaries; these correspond to classical 3XOR satisfiability problems (3XOR-SAT) and to 3XOR games (3XOR-GAME). The issue is the ratio of number of equations m to number of unknowns n for which the system of equations is likely to be solvable: Does there exist a “solvability threshold” c^{*} , so that asymptotically m/n<c^{*} implies solvable, and m/n>c^{*} implies not solvable, with high probability? The classic beautiful tour de force of Dubois–Mandler [ 5 ] says yes for 3XOR-SAT and computes c^{*} . One of the many steps in their proof is [ 5 , Lemma 3.6] , which asserts a discrete Laplace asymptotic formula, and gives the intuitive justification that it is analogous to the classical integral Laplace asymptotic formula. Section 3 rigorously proves their conclusion as an application of our theorems. In support of this, and also using recent results of [ 2 , 3 ] , we produced an appendix, which fills in all of the analytical details which were alluded to, but not included in [ 5 ] . After this, in Section 3.4 , we point out that analysis of the 3XOR-GAME thresholds produce a big messy sum whose asymptotics our theory addresses. In unpublished work we have filled in most of the details. 2. The discrete Laplace asymptotic method This section gives and proves a discrete variation of the Laplace asymptotic method. As a motivation, in Theorem 2.1 it starts with the (already known) continuous analog of what we are proving. Discretizing the domain of integration then turns the continuous Laplace method into the discrete Laplace method, see Theorem 2.7 . Finally, in Theorem 2.8 , we further generalize our results by replacing the function g_{k}e^{-n_{k}h_{k}} by arbitrary discrete summands S_{k} , which only asymptotically behave as g_{k}e^{-n_{k}h_{k}} . 2.1. The continuous Laplace method To give context for the situation, we start with the classical continuous Laplace method, which our discrete Laplace method in Section 2.2 will imitate, and which the asymptotics for discrete summands in Section 2.3 extends. The following Theorem 2.1 is a slight variation of the statement in [ 8 , Theorem 15.2.2] . For further terms in the respective asymptotic expansion, see [ 8 , Theorem 15.2.5] , which relies on g,h being infinitely often differentiable. Theorem 2.1 (Continuous Laplace method) . Let \mathcal{W}\subseteq\mathbb{R}^{d} be open and bounded, and h\colon\mathcal{W}\to\mathbb{R} . Let us assume that there exists some x_{0}\in\mathcal{W} , such that h\in C^{2}(\mathcal{N}_{0}) in an open neighborhood \mathcal{N}_{0} of x_{0} , and there holds the following two assumptions: i) The Hessian \mathcal{H}\{h\}(x_{0}) is strictly positive definite. ii) For every open neighborhood \mathcal{N} of x_{0} , there is \inf_{x\in\mathcal{W}\setminus\mathcal{N}}h(x)>h(x_{0}) . Then for every Riemann integrable function g\colon\mathcal{W}\to\mathbb{C} , which is continuous near x_{0} , there converges (2.1) \lim\limits_{n\to\infty}n^{\frac{d}{2}}e^{nh(x_{0})}\int_{\mathcal{W}}g(x)e^{-nh(x)}dx=\frac{(2\pi)^{\frac{d}{2}}g(x_{0})}{\sqrt{\det(\cH\{h\}(x_0))}}. Remark 2.2 . Before we start the Discrete Laplace Method, we emphasize that integrability over all of \mathcal{W} is not significant, since the Discrete Laplace Method concerns sums over a lattice intersected with \mathcal{W} . Instead, we only need integrability over a small neighborhood \mathcal{N}_{0} where h is minimized, and relevant bounds outside the neighborhood. 2.2. The Discrete Laplace method The idea of the discrete Laplace method is to approximate the integral on the left hand side of ( 2.1 ) by its Riemann sum. In other words, we will partition the integration domain \mathcal{W} into a lattice \Lambda_{k} of the form ( 1.1 ), and approximate (2.2) \int_{\mathcal{W}}g(x)e^{-n_{k}h(x)}dx\sim\frac{\absolutevalue{\det(A_k)}}{n_{k}^{d}}\sum\limits_{x\in\mathcal{W}\cap\Lambda_{k}}g_{k}(x)e^{-n_{k}h_{k}(x)}, where the prefactor \frac{|\det(A_k)|}{n_{k}^{d}} is the cell volume of the lattice. In Theorem 2.7 we then show that under the following 2.3 , the right hand side of this approximation still converges to the same limit as the continuous Laplace method in Eq.( 2.1 ) suggests. Assumption 2.3 . Let \mathcal{W}\subseteq\mathbb{R}^{d} be bounded, and for every k\in\mathbb{N} consider a lattice \Lambda_{k} as in Eq.( 1.1 ), as well as functions g_{k}\colon\mathcal{W}\cap\Lambda_{k}\to\mathbb{C} and h_{k}\colon\mathcal{W}\to\mathbb{R} . Then we say that these objects satisfy the discrete Laplace assumptions , if there exists some x_{0}\in\Int(\mathcal{W}) , such that

Read the complete text