Optimal Depth-Three Circuits for Inner Product Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard Abstract We show that Inner Product in 2 ​ n 2n variables, 𝐈𝐏 n ​ ( x , y ) = x 1 ​ y 1 ⊕ … ⊕ x n ​ y n {\mathbf{IP}}_{n}(x,y)=x_{1}y_{1}\oplus\ldots\oplus x_{n}y_{n} , can be computed by depth-3 bottom fan-in 2 circuits of size 𝚙𝚘𝚕𝚢 ⁡ ( n ) ⋅ ( 9 / 5 ) n {\mathtt{poly}}(n)\cdot(9/5)^{n} , matching the lower bound of Göös, Guan, and Mosnoi (Inform. Comput.’24). Our construction is given via the following steps. 1. We provide a general template for constructing optimal depth-3 circuits with bottom fan-in k k for an arbitrary function f f . We do this in two steps. First, we partition the accepting inputs to f f into several carefully defined orbits . Second, for each orbit, we construct one k k -CNF that (a) accepts the largest number of inputs from that orbit and (b) rejects all inputs rejected by f f . This partitioning of inputs into orbits is based on the symmetries of f f . 2. We instantiate the template for 𝐈𝐏 n {\mathbf{IP}}_{n} and k = 2 k=2 . Guided by a modularity principle that these optimal 2-CNFs may be constructed by composing variable-disjoint copies of small formulas, we use computer search to identify a small set of 2-CNFs each on at most 4 variables which we call building blocks . 3. We then use analytic combinatorial techniques to determine optimal ways to combine these building blocks and construct these optimal 2-CNFs. We believe that the above steps can be applied to a wide range of functions to determine their depth-3 complexity. 1 Introduction A \Sigma_{3} circuit, is a depth-3 OR-AND-OR circuit with unbounded fan-in. Despite their simplicity, these circuits are surprisingly powerful. Any n -variate Boolean function can be computed by a \Sigma_{3} circuit of size O(2^{n/2}) [ 6 ] , a quadratic speed-up over the trivial construction. More strikingly, Valiant [ 21 ] showed that any linear-size fan-in 2 circuit of logarithmic depth can be computed by a \Sigma_{3} circuit of size 2^{O(n/\log\log n)} size. Therefore, truly exponential lower bounds for depth-3 circuits imply non-linear lower bounds for log-depth circuits. However, the best known depth-3 lower bound for an explicit function is only 2^{\Omega(\sqrt{n})} and beating this barrier remains a major open problem in the field [ 12 ] . Even a further restriction of depth-3 circuits shows surprising power. Let \Sigma^{k}_{3} to be the class of \Sigma_{3} circuits in which every bottom OR gate is connected to at most k input bits. Equivalently, these circuits can be viewed as disjunctions of k -CNFs and the number of these formulas serves as a natural measure of size for the circuit. We denote the smallest number of k -CNFs needed to express a function f by \size^{k}_{3}(f) 1 1 1 Note that this quantity is off by a factor of n^{k} from the smallest \Sigma_{3}^{k} sized circuit computing f . However, since k is small enough in this paper and the circuit size is exponential, this difference is immaterial. . Valiant’s depth reduction shows that linear-size log-depth circuits can in fact be computed by \Sigma^{n^{\epsilon}}_{3} circuits of subexponential size where \epsilon>0 can be chosen arbitrarily. More recently, Golovnev, Kulikov, and Williams [ 10 ] showed that unrestricted circuits of size cn for every c<3.9 can be computed by \Sigma^{16}_{3} circuits of size 2^{\epsilon n} for some \epsilon<1 . Therefore, near-maximal lower bounds for \Sigma^{16}_{3} , i.e., lower bounds of the form 2^{n-o(n)} , imply unrestricted circuit lower bounds beyond the state-of-the-art which is only 3.1n-o(n) [ 8 , 15 ] . Near-maximal lower bounds are only known for \Sigma^{2}_{3} and are due to Paturi, Saks, and Zane [ 19 ] . For k\geq 3 , the state-of-the-art is due to Paturi, Pudlák, Saks, and Zane [ 17 ] who showed a \Sigma^{k}_{3} lower bound of 2^{cn/k} where c>1 is a constant, building on a previous work by Paturi, Pudlák, and Zane [ 18 ] who proved a tight lower bound of \Omega(2^{n/k}) for Parity. Near-maximal lower bound arguments. Paturi, Saks, and Zane [ 19 ] proved a crucial property of 2-CNFs. They showed that any 2-CNF with 2^{\Omega(n)} satisfying assignments, must accept a large projection , i.e., an affine space with dimension \Omega(n) defined by equations of the form x=0,1 , x=y , and x=y+1 . Therefore, any good affine disperser , i.e., any function that is not constant under large affine spaces, requires \Sigma^{2}_{3} circuits of size 2^{n-o(n)} . Several explicit constructions of such functions are known (see e.g. [ 2 , 16 ] ). Affine dispersers serve as a natural candidate for near-maximal lower bounds; the known explicit constructions are complicated poly-time algorithms, and the only known circuit construction has super-linear size [ 13 ] . Furthermore, state-of-the-art unrestricted circuit lower bounds hold for affine dispersers [ 8 , 15 ] . In order to prove strong \Sigma^{k}_{3} lower bounds for affine dispersers, we cannot hope to apply the projection argument; there are 3-CNF formulas accepting exponentially many assignments which only accept projections of constant dimension [ 9 ] . However, a more general statement can be true. In particular, we do not know the answer to the following question: is it true that every k -CNF with exponentially many satisfying assignments must accept an affine space of linear dimension? An affirmative answer yields a near-maximal \Sigma^{k}_{3} lower bound for every good affine disperser. However, if the answer is negative, then there may not be a unified proof showing the hardness of every affine disperser. Instead, the hardness of each affine disperser may have to be demonstrated in a unique way. This suggests that by determining the complexity of concrete affine dispersers, we may be able to develop techniques that will ultimately allow us to prove near-maximal lower bounds. Depth-3 complexity of Inner Product. The Inner Product modulo 2 function {\mathbf{IP}} on n coordinates defined as {\mathbf{IP}}_{n}(x,y)=x_{1}y_{1}\oplus\cdots\oplus x_{n}y_{n} , serves as an ideal starting point since it has a very simple and concrete definition and it is known to be a moderately good affine disperser (see e.g. [ 4 ] ). Frankl, Gryaznov, and Talebanfard [ 9 ] pointed out that even for \Sigma^{2}_{3} the exact complexity of {\mathbf{IP}}_{n} is unclear as the projection technique fails to yield a strong bound. Golovnev, Kulikov, and Williams [ 10 ] initiated the study of depth-3 complexity of {\mathbf{IP}}_{n} for independent reasons. {\mathbf{IP}}_{n} can be trivially computed by a \Sigma^{2}_{3} circuit of size O(2^{n}) : {\mathbf{IP}}_{n}=\bigvee_{I\subseteq[n],|I|=\text{odd}}(\wedge_{i\in I}(x_{i}\wedge y_{i})\wedge_{i\not\in I}(\neg x_{i}\vee\neg y_{i})) . A simple lower bound of \Omega(2^{n/2}) follows by a reduction from Parity. Göös, Guan, and Mosnoi [ 11 ] showed, somewhat unexpectedly, that both of these bounds can be improved: (9/5)^{n}\simeq 2^{0.847n}\leq\size^{2}_{3}({\mathbf{IP}}_{n})\leq 2^{0.965n} . They proved the lower bound by identifying a hard probability distribution on inputs to {\mathbf{IP}}_{n} and characterizing the formulas that maximize the probability of accepting an input under this restriction. For the upper bound, they used the above construction to cover solutions with small weight, i.e., the number of coordinates on which both x and y variables are 1 is small. For the remaining solutions, they used a small number of the matching formulas. We will discuss these formulas later as we will also use them in our construction. Amano [ 1 ] improved the upper bound even further to 2^{0.952n} ; this was done by observing that a depth-3 circuit for {\mathbf{IP}}_{n} can be constructed by partitioning the coordinates into blocks of size b for a small value of b , and then combining depth-3 circuits that compute {\mathbf{IP}}_{b} and \neg{\mathbf{IP}}_{b} on these blocks. To find such depth-3 circuits for a fixed b , the paper used computer search. Our Results In this paper we determine \size^{2}_{3}({\mathbf{IP}}_{n}) up to polynomial factors by showing that the lower bound of [ 11 ] is in fact tight. Theorem 1 (Main result) . \size^{2}_{3}({\mathbf{IP}}_{n})\leq{\mathtt{poly}}(n)\cdot(9/5)^{n} 2 A recipe for constructing depth-3 circuits Let f:\Q^{n}\rightarrow\Q be an arbitrary Boolean function and consider the task of proving an upper bound on \size_{3}^{k}(f) , the size of the smallest \Sigma_{3}^{k} circuit computing f . In this section, we will provide a general framework for tackling such a task and will instantiate it to construct optimal circuits for {\mathbf{IP}} . We find it valuable to abstract out this framework since it provides a systematic way of constructing near optimal circuits for many classes of Boolean functions and also without this framework, our construction may seem to be constructed out of the blue. Our framework reduces the task of constructing \Sigma_{3}^{k} circuits for f to the task of constructing many different k -CNFs, each consistent with f , and each one maximizing the number of satisfying assignments with a certain property. We say a k -CNF F is consistent with the function f if for all x\in\{0,1\}^{n} , it holds that F(x)=1\implies f(x)=1 , i.e., \mathbf{sol}(F)\subseteq f^{-1}(1) , where \mathbf{sol}(F) is the set of satisfying assignments of F . To describe our framework, we need to define the notion of automorphism group and orbit of f . Definition 2.1 (Automorphism group and orbits) . For any f:\{0,1\}^{n}\to\{0,1\} , define the automorphism group of f , \aut_{f} , to be the group of permutations \pi such that for all x\in\Q^{n} , f(x_{\pi(1)},\ldots,x_{\pi(n)})=f(x_{1},\ldots,x_{n}) . Consider the action of \aut_{f} on f^{-1}(1) and denote the set of orbits of this action by \orb_{f} . Note that for each S\in\orb_{f} we have S\subseteq f^{-1}(1) . We now define the following quantities associated with orbits of f and how k -CNFs capture it. Definition 2.2 . For any f:\{0,1\}^{n}\to\{0,1\} and S\in\orb_{f} , define \mu_{f,S,k}:=\max_{F:F\text{ is a }k\text{-CNF on }n\text{ variables consistent with }f}\{|\mathbf{sol}(F)\cap S|\}, Furthermore, define \rho_{f,S,k}:=|S|/\mu_{f,S,k} , and \rho^{*}_{f,k}=\max_{S\in\orb_{f}}\{\rho_{f,S,k}\} . In words, \mu_{f,s,k} is the largest number of assignments in the orbit that are accepted by a k -CNF which is consistent with f , \rho_{f,s,k} is the contribution of that orbit to \Sigma_{3}^{k} circuit for f and \rho_{f,k}^{*} is the maximum such contribution. With this, we present the main result of our framework that \rho^{*}_{f,k} along with the number of orbits, governs the size of optimal \Sigma_{3}^{k} circuits for f . Formally, Lemma 2.3 . For all k,n\in\mathbb{N} and all functions f:\{0,1\}^{n}\to\{0,1\} , we have \rho^{*}_{f,k}\leq\size^{k}_{3}(f)\leq O\left(n\cdot|\orb_{f}|\cdot\rho^{*}_{f,k}\right) . We prove this lemma in Section 2.1 . Notice that when \left\lvert\orb_{f}\right\rvert is bounded by a polynomial, then \size^{k}_{3}(f) and \rho^{*}_{f,k} are within a polynomial factor of each other. Therefore, to determine the \Sigma^{k}_{3} complexity of such a function, it is enough to find for each orbit S , a k -CNF consistent with the function with maximum number of solution in S . This is indeed the case with {\mathbf{IP}}_{n} and is exactly the strategy we will use to construct optimal \Sigma_{3}^{2} circuits for {\mathbf{IP}} . 2.1 Depth-3 upper bound - proof of Lemma 2.3 We will need the following claim that shows how we can use a single k -CNF consistent with f that covers some fraction of an obit S of f and use it to find not too many k -CNFs that completely cover the orbit S of f . Claim 2.4 . Let S\in\orb_{f} and let F be an n -variate k -CNF consistent with f . There are k -CNFs F_{1},\ldots,F_{t} all consistent with f such that S\subseteq\mathbf{sol}(F_{1})\cup\ldots\cup\mathbf{sol}(F_{t}) and t=O(n|S|/|\mathbf{sol}(F)\cap S|) . We will prove this claim at the end of this section. We first show how the proof of our desired lemma regarding the construction of optimal circuits for f follows using the claim. Proof of Lemma 2.3 . We prove the lower bound and the upper bound part of the inequality separately. For the lower bound, fix any \Sigma_{3}^{k} circuit C for f . We express C=\bigvee_{i=1}^{m}F_{i} where m\in\mathbb{N} and each F_{i} is a k -CNF. We will show that for all S\in\orb_{f} , it holds that m\geq\rho_{f,S,k} , which implies m\geq\rho^{*}_{f,k} , thus proving the lower bound. Fix any S\in\orb_{f} . We observe that each F_{i} must be consistent with f and so for all i\in[m] , we must have that \left\lvert\mathbf{sol}(F_{i})\cap S\right\rvert\leq\mu_{f,S,k} . We next observe that for all S\in\orb_{f} , each assignment in S must be covered by some F_{i} . Indeed, for each \alpha\in S , since C(\alpha)=f(\alpha)=1 and C=\lor_{i=1}^{m}F_{i} , there must exist some i\in[m] such that F_{i}(\alpha)=1 . Hence, we must we have m\geq|S|/\mu_{f,S,k}=\rho_{f,S,k} as desired. For the upper bound, we construct our desired circuit C for f as follows. For all S\in\orb_{f} , we let F_{S} be the k -CNF consistent with f that maximizes \left\lvert\mathbf{sol}(F_{S})\cap S\right\rvert . By definition, each F_{S} accepts \mu_{f,S,k} many assignments from S . We now apply 2.4 and construct k -CNFs F_{S,1},\ldots,F_{S,t} consistent with f which cover all S where t=t(S)=O(n|S|/|\mathbf{sol}(F)\cap S|)=O(n\rho_{f,S,k}) . Our final depth-3 circuit C is defined as C=\lor_{S\in\orb_{f},i\in[t(S)]}F_{S,i} . Hence, C accepts all assignments from each of the orbits S , showing that C accepts all assignments from f^{-1}(1) . Since each F_{S,i} is consistent with f , C correctly rejects all assignments from f^{-1}(0) and hence C indeed computes the function f . The total number of k -CNFs that C is expressed as an OR of is O(n\sum_{S\in\orb_{f}}\rho_{f,S,k})=O(n\cdot|\orb_{f}|\cdot\rho^{*}_{f,k}) as desired. ∎ We finally prove our remaining claim of using a single k -CNF covering small fraction of an orbit to construct many different k -CNFs that entirely cover an orbit. Proof of 2.4 . Let t=2|S|\ln|S|/|\mathbf{sol}(F)\cap S|=O(n|S|/|\mathbf{sol}(F)\cap S|) . For each i\in[t] define F_{i}=F^{\pi_{i}} to be the permutation of F under a random permutation \pi_{i}\in\aut_{f} . Fix \alpha\in S . It follows from the Orbit-Stabilizer theorem that for a random \pi\in\aut_{f} , \Pr[\alpha\in\mathbf{sol}(F^{\pi})]=|\mathbf{sol}(F)\cap S|/|S| . We then compute \displaystyle\Pr[\alpha\not\in\mathbf{sol}(F_{1})\cup\ldots\cup\mathbf{sol}(F_{t})] \displaystyle\leq\left(1-|\mathbf{sol}(F)\cap S|/|S|\right)^{t} \displaystyle\leq\exp\left(-t\cdot|\mathbf{sol}(F)\cap S|/|S|\right) \displaystyle<1/|S| where the last inequality follows by the choice of t and the fact that \left\lvert S\right\rvert\leq 2^{n} . By a union bound over all \alpha\in S , we conclude that there indeed exists a choice of F_{i} s covering all assignments in S as desired. ∎ 3 Construction for IP In this section, we instantiate our framework from Section 2 and use it to construct an optimal \Sigma_{3}^{2} circuit for {\mathbf{IP}} . We will prove the following main lemma that together with Lemma 2.3 proves the main result 1 . Lemma 3.1 . There exists a universal constant C such that for all integer n\geq 2 , \rho^{*}_{{\mathbf{IP}}_{n},2}\leq n^{C}\cdot(9/5)^{n} . Towards proving the main lemma, we will identify the orbits of {\mathbf{IP}}_{n} in Section 3.1 to reduce the task to provide constructions of 2 -CNFs for each of these orbits. These 2 -CNFs will be constructed by taking appropriate ‘disjoint product’ of few 2 -CNFs, each over at most 4 variables. We will describe these building blocks in Section 3.2 . Then, we will reduce this main lemma to a version of the main lemma that holds only for infinitely many n and orbits within it - Lemma 3.10 - in Section 3.3 . Finally, we will split the orbits of {\mathbf{IP}}_{n} into 5 regions in Section 3.4 to reduce the main lemma to Lemma 3.12 . We will prove Lemma 3.12 in Section 7 . 3.1 Orbits of IP and spectra of 2-CNFs We now describe the orbits of {\mathbf{IP}}_{n} and also introduce an associated quantity with 2 -CNFs - their spectra. We first observe that the set \aut_{{\mathbf{IP}}_{n}} consists of all permutations that permute the n coordinates, and within each coordinate permute x_{i} and y_{i} . Thus |\aut_{{\mathbf{IP}}}|=n!2^{n} . We now describe the orbits of {\mathbf{IP}}_{n} . For input (x,y)\in(\{0,1\}^{n})^{2} , define the following quantities: 1. d_{2}(x,y)=\left\lvert\{i\in[n]:x_{i}=y_{i}=1\}\right\rvert . 2. d_{1}(x,y)=\left\lvert\{i\in[n]:x_{i}\neq y_{i}\}\right\rvert . 3. d_{0}(x,y)=\left\lvert\{i\in[n]:x_{i}=y_{i}=0\}\right\rvert . We see that d_{2}(x,y)+d_{1}(x,y)+d_{0}(x,y)=n . More importantly, when a permutation from \aut_{{\mathbf{IP}}_{n}} acts on (x,y) , the resultant (x^{\prime},y^{\prime})\in(\{0,1\}^{n})^{2} is such that d_{j}(x,y)=d_{j}(x^{\prime},y^{\prime}) for j\in\{0,1,2\} . We also see that for any (x^{\prime},y^{\prime})\in(\{0,1\}^{n})^{2} such that d_{j}(x,y)=d_{j}(x^{\prime},y^{\prime}) for j\in\{0,1,2\} , there exists a permutation \pi\in\aut_{{\mathbf{IP}}_{n}} such that \pi(x,y)=(x^{\prime},y^{\prime}) . Hence, these quantities precisely determine the orbits of {\mathbf{IP}}_{n} . In particular we have |\orb_{{\mathbf{IP}}_{n}}|=O(n^{2}) . We parameterize the orbits of {\mathbf{IP}}_{n} as follows: Definition 3.2 (Orbits of {\mathbf{IP}}_{n} ) . For d_{2},d_{1},d_{0}\in[n] such that d_{2}+d_{1}+d_{0}=n , let S(d_{2},d_{1},d_{0})\subseteq(\{0,1\}^{n})^{2} denote the set of assignments (x,y)\in(\{0,1\}^{n})^{2} such that d_{j}(x,y)=d_{j} for all j\in\{0,1,2\} . For any (x,y)\in S(d_{2},d_{1},d_{0}) , we have that {\mathbf{IP}}_{n}(x,y)=d_{2}\mod 2 . Observe that the sets S(d_{2},d_{1},d_{0}) capture all the orbits of {\mathbf{IP}} as well as \neg{\mathbf{IP}} . We record the following fact regarding size of each of the orbits: Fact 3.3 . |S(d_{2},d_{1},d_{0})|=\binom{n}{d_{2}}\binom{n-d_{2}}{d_{0}}2^{n-d_{2}-d_{0}}=\binom{n}{d_{2}}\binom{d_{1}+d_{0}}{d_{1}}2^{d_{1}} . We define one more quantity associated with a 2 -CNF F that will capture how its satisfying assignments intersect various orbits of {\mathbf{IP}}_{n} . We will do this by associating a generating function to each such F where the monomials represent an orbit of {\mathbf{IP}}_{n} and the coefficient for the monomials will represent the number of satisfying assignments of F from that orbit. Formally, Definition 3.4 (Spectrum of 2-CNF) . For a 2 -CNF F over 2n variables, define the spectrum of F to be the generating function G(x,y,z)=\sum_{p,q,r\in\mathbb{N}}C_{p,q,r}x^{p}y^{q}z^{r} where for each p,q,r\in\mathbb{N} , C_{p,q,r} is the number of assignments \alpha\in\{0,1\}^{2n} such that F(\alpha)=1 , d_{2}(\alpha)=p,d_{1}(\alpha)=q , and d_{0}(\alpha)=r . Notice that the spectrum of 2 -CNF is always a finite homogeneous polynomial. 3.2 Building blocks for our constructions To construct consistent 2 -CNFs maximizing the number of solutions from a fixed orbit, we identify a small number of building block 2-CNFs and show that each orbit of {\mathbf{IP}} can be optimally captured by appropriately combining them. We first describe our building block 2 -CNFs. Since any function over 2 variables can expressed as a 2 -CNF, we will provide descriptions that involve AND of constraints over 2 variables. Definition 3.5 (Building block 2 -CNFs and their spectra) . We define the following 2 -CNFs that we will refer to as building block 2 -CNFs: • \mathbf{Id}_{2} . This denotes the 2 -CNF over 1 coordinate, i.e., 2 variables that accepts iff both variables equal 1 . Hence, its spectrum is x . • \mathbf{Id}_{1} . This denotes the 2 -CNF over 1 coordinate, i.e., 2 variables that accepts iff both variables do not equal each other. Hence, its spectrum is 2y . • \mathbf{Id}_{0} . This denotes the 2 -CNF over 1 coordinate, i.e., 2 variables that accepts iff both variables equal 0 Hence, its spectrum is z . • \mathbf{NAND} . This denotes the 2 -CNF over 1 coordinate, i.e., 2 variables, that accepts iff both variables do not equal 1 . Hence, its spectrum is 2y+z . • \mathbf{Matching} . This denotes the 2 -CNF over over 2 coordinates, i.e., over 4 variables defined as follows. On input (x,y)\in(\{0,1\}^{2})^{2} , the 2 -CNF accepts iff x_{1}=x_{2} , and y_{1}=y_{2} . Simple computation reveals that its spectrum is x^{2}+2y^{2}+z^{2} . • \mathbf{2Imp} . This denotes the 2 -CNF over over 2 coordinates, i.e., over 4 variables defined as follows. On input (x,y)\in(\{0,1\}^{2})^{2} , the 2 -CNF accepts iff the following holds: x_{1}=x_{2} , x_{1}\implies y_{1} , and x_{2}\implies y_{2} . Simple computation reveals that its spectrum is x^{2}+y^{2}+2yz+z^{2}=x^{2}+(y+z)^{2} . We now define our operation of combining over building blocks which will be the disjoint AND of 2 -CNFs. Formally, Definition 3.6 (Combine operation) . Let F_{1} and F_{2} be arbitrary 2 -CNFs over n_{1},n_{2} variables respectively. Then, F_{1}\land F_{2} is the 2 -CNF over n_{1}+n_{2} variables obtained by adding all clauses from both F_{1} and F_{2} where we associate the first n_{1} variables with variables of F_{1} and the last n_{2} variables with variables of F_{2} . Often we will use this notion to combine many different 2 -CNFs. In such cases, we will not care about the order in which the combining happens and just apply the operation one after the other in some canonical order. We next record the following simple yet crucial observation regarding the spectrum of the combined 2 -CNF: Fact 3.7 (Spectra of combined 2 -CNFs) . Let F_{1} and F_{2} be arbitrary 2 -CNFs over n_{1},n_{2} variables respectively with spectra G_{1} and G_{2} respectively. Then, the spectrum of F_{1}\land F_{2} equals G_{1}\cdot G_{2} . For b\in\{0,1\} , we define the function {\mathbf{IP}}_{n}^{b} to equal {\mathbf{IP}}_{n} if b=1 and to equal \neg{\mathbf{IP}}_{n} if b=0 . We observe that for a 2 -CNF F is consistent with {\mathbf{IP}}_{n}^{b} for some b\in\{0,1\} if and only if the following holds: for each monomial x^{p}y^{q}z^{r} with non-zero coefficient in the spectrum of F , p\pmod{2}=b . Using this and 3.7 , we obtain the following fact regarding consistency of combined 2 -CNFs: Fact 3.8 . Let F_{1} and F_{2} be 2 -CNFs on n_{1} and n_{2} variables respectively. Furthermore, assume that there exist b_{1},b_{2}\in\{0,1\} such that F_{1} is consistent with {\mathbf{IP}}_{n_{1}}^{b_{1}} and that F_{2} is consistent with {\mathbf{IP}}_{n_{2}}^{b_{2}} . Then, F_{1}\land F_{2} is consistent with {\mathbf{IP}}_{n_{1}+n_{2}}^{b_{1}\oplus b_{2}} . By examining the spectra of the building blocks, we see that each building block from Section 3.2 is consistent with {\mathbf{IP}}_{n}^{b} for some b\in\{0,1\} and some n\in\mathbb{N} . Hence, we obtain: Corollary 3.9 . Let F be a 2 -CNF over n variables obtained by repeatedly combining many different building blocks from Section 3.4 . Then, there exists b\in\{0,1\} such that F is consistent with {\mathbf{IP}}_{n}^{b} . 3.3 Reducing to infinitely often case To help prove Lemma 3.1 , we will show the following key lemma that only proves the statement for infinitely many n , each a multiple of some universal constant: Lemma 3.10 . There exist universal constants C,m\in\mathbb{N} such that the following holds: For all p,q,r,n\in\mathbb{N} such that n=p+q+r and m divides each of p,q,r,n , there exists a 2 -CNF F over n variables that is consistent with {\mathbf{IP}}_{n}^{p\pmod{2}} and satisfies: \frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert}\leq n^{C}\cdot(9/5)^{n}. We will prove this key lemma in Section 3.4 . Let’s see how using this key lemma, Lemma 3.1 follows. Proof of Lemma 3.1 . Fix any integer n\geq 2 . Now consider any orbit S of {\mathbf{IP}}_{n} . It suffices to show that there exists a 2 -CNF F consistent with {\mathbf{IP}} such that \frac{\left\lvert S\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S\right\rvert}\leq n^{C_{0}}\cdot(9/5)^{n} where C_{0} is a universal constant. As discussed in Section 3.1 , S is parameterized by integers p,q,r\in\mathbb{N} such that p+q+r=n where p is odd and S=S(p,q,r) . Let p^{\prime}\leq p,q^{\prime}\leq q,r^{\prime}\leq r be the largest multiples of m less than or equal to p,q,r respectively. Let n^{\prime}=p^{\prime}+q^{\prime}+r^{\prime} . Note that n^{\prime} must also be a multiple of m and that n-n^{\prime}\leq 3m . We apply Lemma 3.10 with values p^{\prime},q^{\prime},r^{\prime},n^{\prime} to obtain 2 -CNF F^{\prime} over n^{\prime} variables such that \frac{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}{\left\lvert\mathbf{sol}(F^{\prime})\cap S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}\leq(n^{\prime})^{C_{0}}\cdot(9/5)^{n^{\prime}} where C_{0} is a universal constant. Let F be the 2 -CNF over n variables obtained by combining (as by Definition 3.6 ) p-p^{\prime} copies of \mathbf{Id}_{2} , (q-q^{\prime}) copies of \mathbf{Id}_{1} , (r-r^{\prime}) copies of \mathbf{Id}_{0} , and 1 copy of F^{\prime} . We know that F^{\prime} is consistent with {\mathbf{IP}}_{n^{\prime}}^{p^{\prime}\pmod{2}} , \mathbf{Id}_{1} and \mathbf{Id}_{0} are consistent with {\mathbf{IP}}_{1}^{0} and \mathbf{Id}_{2} is consistent with {\mathbf{IP}}_{1}^{1} . Using this and applying 3.8 , we infer that F will be consistent with {\mathbf{IP}}_{n}^{p\pmod{2}} and hence {\mathbf{IP}} (since p is odd) as desired. Next, using 3.3 and the fact that n-n^{\prime}\leq 3m,p-p^{\prime}\leq m,q-q^{\prime}\leq m,r-r^{\prime}\leq m , we infer that there exists a universal constant C_{1} such that \frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}\leq n^{C_{1}} . Also by definition of F , we see that \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert=2^{q-q^{\prime}}\left\lvert\mathbf{sol}(F^{\prime})\cap S(p^{\prime},q^{\prime},r^{\prime})\right\rvert . Using all these, we compute that \displaystyle\frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert} \displaystyle=\frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}\cdot\frac{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert} \displaystyle=2^{q^{\prime}-q}\cdot\frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}\cdot\frac{\left\lvert S(p^{\prime},q^{\prime},r^{\prime})\right\rvert}{\left\lvert\mathbf{sol}(F^{\prime})\cap S(p^{\prime},q^{\prime},r^{\prime})\right\rvert} \displaystyle\leq 2^{m}\cdot n^{C_{1}}\cdot n^{C_{0}}\cdot(9/5)^{n} \displaystyle\leq n^{C}\cdot(9/5)^{n} where C is a large enough universal constant (since m is a constant) as desired. ∎ 3.4 Splitting orbits into regions In this subsection, we will prove Lemma 3.10 . We will prove this by dividing the orbits of {\mathbf{IP}}_{n} into 5 regions and proving the lemma for each of the five regions. Formally, Definition 3.11 . For i\in[5] and n\in\mathbb{N} , we define \mathcal{R}_{i}(n)\subseteq\mathbb{N}\times\mathbb{N}\times\mathbb{N} as follows: 1. We define \mathcal{R}_{1}(n) as set of triples (p,q,r)\in\mathbb{N} such that p+q+r=n that satisfy: • \frac{1}{2}n-\frac{25}{32}p\geq 0 . • \frac{5}{4}n-\frac{25}{32}p-\frac{25}{4}r\geq 0 . • \frac{-5}{4}n+\frac{25}{16}p+\frac{25}{4}r\geq 0 . 2. Next, define \mathcal{R}_{2}(n) as set of triples (p,q,r)\in\mathbb{N} such that p+q+r=n that satisfy: • \frac{1}{2}n-\frac{25}{32}p\leq 0 . 3. Next, define \mathcal{R}_{3}(n) as the set of triples (p,q,r)\in\mathbb{N} such that p+q+r=n that satisfy: • \frac{1}{2}n-\frac{25}{32}p\geq 0 . • \frac{5}{4}n-\frac{25}{32}p-\frac{25}{4}r\leq 0 . 4. Next, we define \mathcal{R}_{4}(n) as the set of triples (p,q,r)\in\mathbb{N} such that p+q+r=n that satisfy: • \frac{1}{2}n-\frac{25}{32}p\geq 0 . • \frac{-5}{4}n+\frac{25}{16}p+\frac{25}{4}r\leq 0 . • r-10^{-5}n\geq 0 . 5. Lastly, we define \mathcal{R}_{5}(n) as the set of triples (p,q,r)\in\mathbb{N} such that p+q+r=n that satisfy: • \frac{1}{2}n-\frac{25}{32}p\geq 0 . • r-10^{-5}n\leq 0 . For a fixed region \mathcal{R}_{i} , we will construct 2 -CNFs for all orbits in that region using the same technique. In particular, we will show: Lemma 3.12 . For all i\in[5] , there exist universal constants K_{i},m_{i}\in\mathbb{N} such that the following holds: For all p,q,r,n\in\mathbb{N} such that n=p+q+r , m divides each of p,q,r,n , and (p,q,r)\in\mathcal{R}_{i} , there exists a 2 -CNF F over n variables that is consistent with {\mathbf{IP}}_{n}^{p\pmod{2}} and satisfies: \frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert}\leq n^{K_{i}}\cdot(9/5)^{n}. We will prove this lemma for each of the regions in Section 7 . First using Lemma 3.12 , we easily show how Lemma 3.10 follows. Proof of Lemma 3.10 . We apply Lemma 3.12 , and let our final m to be the least common multiple of m_{1},m_{2},m_{3},m_{4},m_{5} and let our final universal constant C to be the maximum amongst K_{1},K_{2},K_{3},K_{4},K_{5} . We carefully observe that our four regions cover all set of triples p,q,r\in\mathbb{N} such that p+q+r=n . ∎ 4 Overview of constructions for each region Here we provide overview of how we construct 2 -CNFs for each of the regions above, proving Lemma 3.12 . Setup and Common analysis The general setup is that for given p,q,r from some region \mathcal{R}_{i} , we want to construct a 2 -CNF F such that \frac{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert}{\left\lvert S(p,q,r\right\rvert}\leq{\mathtt{poly}}(n)\cdot(9/5)^{n} where n=p+q+r and where F is consistent with {\mathbf{IP}}_{n}^{p\pmod{2}} . We will ensure that p is even so that this reduces to showing that F is consistent with {\mathbf{IP}}_{n}^{0} . Our F will be formed by carefully combining (as per Definition 3.6 ) an appropriate number of building block 2 -CNFs (as defined in Definition 3.5 ). We will ensure that when doing so, F remains consistent with {\mathbf{IP}}_{n}^{0} (using Corollary 3.9 ) so that the only remaining task is to argue that F captures many assignments from S(p,q,r) . To do so, we will obtain an expression for the spectrum of F (using 3.7 ) and will lower bound the coefficient of the monomial x^{p}y^{q}z^{r} in that generating function. This is the common analysis for all regions and from here on the analysis will differ depending upon the region and how we construct 2 -CNFs for that region. Constructions and sketch of analysis for each region We will now go region by region, specify the exact construction for orbits in that region, and briefly mention the analysis for that region. We will provide a detailed presentation of the construction and the analysis for \mathcal{R}_{1} at the end of this section. Region 1. For each orbit in \mathcal{R}_{1} , we will construct a specialized 2 -CNF obtained by combining an appropriate number of \mathbf{Matching},\mathbf{2Imp},\mathbf{Nand} gates. We will purely use analytical combinatorics based techniques to obtain our desired bound. We sketch exact details below. Region 2. Here we will construct a single 2 -CNF for all orbits in \mathcal{R}_{2} . The single 2 -CNF we take will be obtained by combining n/2 copies of \mathbf{Matching} . We will directly use combinatorial arguments and elementary techniques to obtain our desired bound. Region 3. Here we will fix two 2 -CNFs and for each orbit in \mathcal{R}_{3} , we will pick the best one, i.e., the one that captures the most assignments from S(p,q,r) . The two 2 -CNFs we consider will be the following (a) First will be obtained by combining 0.34n copies of \mathbf{2Imp} with 0.32n copies of \mathbf{Nand} . (b) Second will be obtained by combining 0.465n copies of \mathbf{2Imp} with 0.07n copies of \mathbf{Nand} . We will use analytical combinatorics ideas to reduce the problem to upper bounding a multivariate optimization problem over reals in [0,1] . The formal statement of the optimization problem and the bound that we need is specified in Lemma 7.4 . To solve the optimization problem, we will use a standard optimization solver and get a computer assisted proof that our bound holds. Region 4. Just like region 3, here too we will fix two 2 -CNFs and for each orbit from \mathcal{R}_{4} , we will pick the best 2 -CNF for it. The two 2 -CNFs we consider will be: (a) One obtained by combining 0.34n copies of \mathbf{Matching} with 0.32n copies of \mathbf{Nand} . (b) Second obtained by combining 0.355n copies of \mathbf{Matching} with 0.29n copies of \mathbf{Nand} . Here too we will use analytical combinatorics based techniques to reduce the task to a multivariate optimization problem over reals in [0,1] . The formal statement for this optimization bound is specified in Lemma 7.6 ; we will use an optimization solver to obtain a computer assisted proof of our desired bound. Region 5. We will follow the same strategy as region 2 - we will fix a single 2 -CNF for all orbits from \mathcal{R}_{5} . The single 2 -CNF will be obtained by combining 0.355n copies of \mathbf{Matching} and 0.29n copies of \mathbf{Nand} . To obtain the desired bound, we will use directly combinatorial arguments and elementary techniques as well. Sketch of construction and analysis for \mathcal{R}_{1} . We here sketch the proof of Lemma 3.12 for i=1 . Let A=\frac{5}{4}n-\frac{25}{32}p-\frac{25}{4}r,B=\frac{-5}{4}n+\frac{25}{16}p+\frac{25}{4}r,C=\frac{1}{2}n-\frac{25}{32}p . By inequalities that p,q,r satisfy from being in \mathcal{R}_{1} , A,B,C are non-negative. We take A copies of \mathbf{Matching} , B copies of \mathbf{2Imp} and 2C copies of \mathbf{Nand} building blocks and combine them to form F . We ensure that F is consistent with {\mathbf{IP}}_{n}^{0} by requiring that each of A,B,C is even by imposing divisibility requirements on p,q,r (by setting m=8000 say). Then, the spectrum of F equals P(x,y,z)=(x^{2}+2y^{2}+z^{2})^{A}(x^{2}+(y+z)^{2})^{B}((2y+z)^{2})^{C} and the coefficient of x^{p}y^{q}z^{r} in P equals \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert . To help bound this, we define f(u,v)=P(u^{1/2},v,1) . Since p+q+r=n and P is a homogeneous polynomial, the coefficient of u^{p/2}v^{q} in f(u,v) equals the coefficient of x^{p}y^{q}z^{r} in P(x,y,z) . We now take partial derivatives of f(u,v) , set them to 0 and consider the non-negative real values where the gradient is set to 0 . When we do this computation, we get that the unique ‘critical point’ is at (16,2) . We then apply a standard result in analytic combinatorics - Lemma 8.1 - that states that under reasonable properties satisfied by f , the value of the coefficient of u^{p/2}v^{q} (upto polynomial factors) will equal \frac{f(16,2)}{16^{p/2}2^{q}}=\frac{25^{A+B+C}}{16^{p/2}2^{q}}=\frac{5^{n}}{2^{2p+q}} where we used the fact that A+B+C=n/2 . See Lemma 7.1 for details. Hence, we infer that for our F , upto polynomial factors, \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert=\frac{5^{n}}{2^{2p+q}} . By 3.3 , we have that \left\lvert S(p,q,r)\right\rvert=\binom{n}{p}\binom{n-p}{r}\cdot 2^{n-p-r} . We compute (using the fact that p+q+r=n ): \displaystyle\frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert} \displaystyle\leq\binom{n}{p}\binom{n-p}{r}\cdot 2^{n-p-r}\cdot\frac{2^{2p+q}}{5^{n}} \displaystyle=\binom{n}{p,q,r}\cdot 4^{-r}\cdot(4/5)^{n} \displaystyle\leq\sum_{i,j,k\in\mathbb{N}:i+j+k=n}\binom{n}{i,j,k}\cdot 1^{i}\cdot 1^{j}\cdot 4^{-k}\cdot(4/5)^{n} \displaystyle=(9/4)^{n}\cdot(4/5)^{n} \displaystyle=(9/5)^{n} where we used binomial theorem in the second last line. Hence, our F has the desired properties. Organization The rest of the paper is organized as follows: In Section 5 , we provide conclusion and discussion; in Section 6 , we setup preliminaries and notation; in Section 7 , we provide constructions for each region, relying on bounds on coefficients of appropriate monomials of generating functions; in Section 8 we prove these required bounds on coefficients using a result in analytic combinatorics; in Appendix A we prove the exact result from that we need using basic results in analytic combinatorics (even though the result we require seems standard in the area, we could not find it in the literature in the precise form that we needed). 5 Conclusion 5.1 Open Questions The immediate question left open is to determine \size^{k}_{3}({\mathbf{IP}}_{n}) for every k\geq 3 . We believe that a similar methodology should work for upper bounds. However, the challenge is to find an argument that scales with k . It also remains open to find a non-trivial lower bound argument for any k\geq 3 . Another related open question is to construct an explicit degree 2 polynomial that requires \Sigma_{3}^{k} circuits of size 2^{n-o(n)} for all constant k ; this is open even for k=2 . Existentially, Impagliazzo, Paturi, and Zane showed that a random degree 2 polynomial requires maximal \Sigma_{3}^{k} circuits [ 14 ] . 5.2 How did we discover these circuits? We here document our journey of constructing optimal circuits for {\mathbf{IP}}_{n} . We hope this inspires future works that try to find small \Sigma_{3}^{k} circuits for various explicit functions. Modular constructions As a starting point, we believed that optimal circuits for {\mathbf{IP}}_{n} must be modular, i.e., obtained by combining disjoint copies of smaller 2 -CNFs. Our reasons for such a belief were twofold: first that all previous best known constructions of {\mathbf{IP}}_{n} had this property; and second that optimal (and conjectured to be optimal) \Sigma_{3}^{k} circuits for other simple functions such as Parity and Majority have this property. Searching for better circuits for small n . Our first improvement came from examining the construction of \Sigma_{3}^{2} circuits for {\mathbf{IP}}_{n} by Amano [ 1 ] . To construct such circuits, the paper used an integer programming solver on a set of constraints to find a disjunction of 7 2 -CNFs that compute {\mathbf{IP}}^{1}_{4} , and another disjunction of 7 2 -CNFs that compute {\mathbf{IP}}^{0}_{4} . To obtain the final circuit, the paper combines these small circuits to construct such a circuit larger n . We used a similar set of constraints, solving using Kissat SAT solver, to identify a disjunction of 14 2 -CNF formulas that compute {\mathbf{IP}}^{1}_{5} , and another disjunction of 13 2 -CNF formulas that compute {\mathbf{IP}}^{0}_{5} ; repeated use of these in Amano’s construction gives a slightly improved construction of circuits for {\mathbf{IP}}_{n} with size 2^{cn} where c\approx 0.9509 . This inspired us to seek further improvements. Search for small Pareto-optimal building blocks Suppose A and B are 2 -CNFs consistent with {\mathbf{IP}}^{b}_{n} for some b\in\{0,1\} and n\in\mathbb{N} . Then, we say A dominates B if each coefficient in A ’s spectrum is at least as large as the corresponding coefficient in B ’s spectrum. We performed an exhaustive computer search for Pareto-optimal (non-dominated) 2-CNF building blocks for {\mathbf{IP}}^{0}_{2} that identified three distinct Pareto-optimal building blocks: \mathbf{Matching},\mathbf{2Imp} and two copies of \ \mathbf{Nand} . In particular, \mathbf{2Imp} was a new building block first identified by this exhaustive search, and was crucial in our optimal constructions. We also identified many more such Pareto-optimal building blocks for other small values of n that we did not end up using for our construction. Search for compositions of building blocks After identifying building blocks, we next empirically tried to find out for some large fixed values of n , for each orbit of {\mathbf{IP}}_{n} , how to combine our Pareto-optimal building blocks to construct a 2 -CNF consistent with {\mathbf{IP}}_{n} that maximizes the number of solutions from that orbit. To do this, we enumerated all distinct compositions of these building blocks. This exercise not only pointed us the best composition for each orbit but also let us identify the hardest orbit for our compositions (the one with that maximizes the ratio of size of the orbit to the number of solutions from that orbit). We did this for n=50 , n=100 , and n=200 , as well as restricted enumeration for n=400 and n=800 near our conjectured hardest orbits. These identified best compositions using \mathbf{Matching},\mathbf{2Imp},\mathbf{Nand} , similar to the constructions later used in our proof. The compositions found by enumeration correspond to depth-3 circuits of size {\mathtt{poly}}(n)\cdot 2^{cn} , with: n=50 c=0.8344320 n=100 c=0.8414042 n=200 c=0.8447647 n=400 c=0.8463819 n=800 c=0.8471913 A least-squares fit to the data yields 0.8479999-0.6470509/n , suggesting eventual convergence to 0.8479999 for large n . This is extremely close to \log(9/5)=0.8479969 , which would match the lower bound from [ 11 ] , motivating us to pursue an upper bound with c=\log(9/5) . Restricted compositions to cover regions After this, we analytically solved for optimal constructions using \mathbf{Matching},\mathbf{2Imp},\mathbf{Nand} using saddle point methods. Doing this led us to identifying regions 2, 3, 4 from Definition 3.11 and pointed us to the fact that optimal constructions from these regions use at most 1 or 2 building blocks. We then performed a search for optimal compositions (using at most 2 types of building blocks) for each of these regions for n=200 . During this search, we wanted to minimize the number of distinct compositions required to ‘cover’ a region so that the ratio of size of orbit to number of solutions from that orbit is at most (9/5)^{n} . This search helped us successfully identify one or two compositions (involving only 1 or 2 gates) that we used in our constructions. 6 Preliminaries and notation We use \log(x) to denote logarithm of x with base 2 ; we will use \ln(x) to denote natural logarithm, i.e., logarithm of x with base e . We will also often make use of the well known binary entropy function H:[0,1]\to[0,1] defined as H(x)=x\log(1/x)+(1-x)\log(1/(1-x)) . We will utilize the following well known approximation for binomial coefficients (see for instance equation 7.14 from [ 5 ] ): Theorem 6.1 . For all m,k\in\mathbb{N} such that m\geq k , we have that \frac{1}{m+1}2^{mH(k/m)}\leq\binom{m}{k}\leq 2^{mH(k/m)} where H is the binary entropy function. 7 Constructing 2-CNFs for each region In this section, we will go over each of the 5 regions (in each subsequent subsection), as described in Definition 3.11 and prove Lemma 3.12 for each of these regions by constructing 2 -CNFs for an arbitrary orbit from that region. The proofs provided will be complete except some results regarding asymptotes of coefficients of fixed multivariate generating functions that we will prove in Section 8 . 7.1 Constructing 2-CNFs for orbits in region 1 In this subsection, we will prove Lemma 3.12 for triplets in \mathcal{R}_{1} . We will rely on the following result regarding asymptotes of a coefficient of a monomial from a generating function, that we will prove in Section 8.1 . Lemma 7.1 . There exists a universal constant K_{0} such that the following holds. Let A,B,C,p,q,r,n be nonnegative integers such that n\geq C_{0} , n=p+q+r,A=\frac{5}{4}n-\frac{25}{32}p-\frac{25}{4}r,B=\frac{-5}{4}n+\frac{25}{16}p+\frac{25}{4}r,C=\frac{1}{2}n-\frac{25}{32}p . Then, the coefficient of the monomial x^{p}y^{q}z^{r} in P(x,y,z)=(x^{2}+2y^{2}+z^{2})^{A}(x^{2}+(y+z)^{2})^{B}((2y+z)^{2})^{C} is at least \frac{1}{n^{C_{0}}}\frac{5^{n}}{2^{2p+q}} . Let’s see how using this, our desired claim easily follows: Proof of Lemma 3.12 for i=1 . We let m=32 . Now consider any (p,q,r)\in\mathcal{R}_{1} such that m divides each of them (and hence also divides n ). We will construct 2 -CNF F that is consistent with {\mathbf{IP}}_{n}^{p\pmod{2}} and such that \frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert}\leq n^{C_{0}}\cdot(9/5)^{n} for some universal constant K_{0} (that is also independent of the choice of p,q,r ). Let A=\frac{5}{4}n-\frac{25}{32}p-\frac{25}{4}r,B=\frac{-5}{4}n+\frac{25}{16}p+\frac{25}{4}r,C=\frac{1}{2}n-\frac{25}{32}p . We claim that A,B,C are non-negative integers. Since m divides each of n,p,q,r , we must have that A,B,C are integers. Moreover, by definition of \mathcal{R}_{1} (given in Definition 3.11 ), we must have that A,B,C\geq 0 . With this, we let our F be obtained by combining (as defined in Definition 3.6 ) A copies of \mathbf{Matching} , B copies of \mathbf{2Imp} and 2C copies of \mathbf{Nand} (as defined in Definition 3.5 ). Since m divides p , and p is even, we require F to be consistent with {\mathbf{IP}}_{n}^{0} . Using Corollary 3.9 and the fact that each of \mathbf{Matching} , \mathbf{2Imp} , \mathbf{Nand} is consistent with {\mathbf{IP}}_{n}^{0} , we indeed have that F is consistent with {\mathbf{IP}}_{n}^{0} . Using 3.7 and the spectra of these building blocks from Definition 3.5 , we see that the spectrum of F will be P(x,y,z)=(x^{2}+2y^{2}+z^{2})^{A}(x^{2}+(y+z)^{2})^{B}((2y+z)^{2})^{C} . We now apply Lemma 7.1 and use the fact that the coefficient of x^{p}y^{q}z^{r} in P determines \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert , to infer that \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert\geq n^{-K_{1}}\cdot\frac{5^{n}}{2^{2p+q}} where K_{1} is a universal constant. Also recall that from 3.3 , \left\lvert S(p,q,r)\right\rvert=\binom{n}{p}\binom{n-p}{r}\cdot 2^{n-p-r} . Using these, we infer that \displaystyle\frac{\left\lvert S(p,q,r)\right\rvert}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert} \displaystyle\leq\binom{n}{p}\binom{n-p}{r}\cdot 2^{n-p-r}\cdot n^{-K_{1}}\cdot\frac{2^{2p+q}}{5^{n}} \displaystyle=n^{-K_{1}}\cdot\binom{n}{p,q,r}\cdot n^{-K_{1}}\cdot 4^{-r}\cdot(4/5)^{n} where the last equality follows using the fact that p+q+r=n . To prove \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert}\leq n^{-K_{0}}\cdot(9/5)^{n} , it suffices to show that \binom{n}{p,q,r}\cdot 4^{-r}\leq(9/4)^{n} where K_{2} is a universal constant. We compute: \displaystyle\binom{n}{p,q,r}\cdot 4^{-r} \displaystyle=\binom{n}{p,q,r}1^{p}\cdot 1^{q}\cdot 4^{-r} \displaystyle\leq\sum_{i,j,k\in\mathbb{N}:i+j+k=n}\binom{n}{i,j,k}\cdot 1^{i}\cdot 1^{j}\cdot 4^{-k} \displaystyle=(9/4)^{n} where the last equality follows from the binomial theorem. Hence, our construction F indeed has the desired properties. ∎ 7.2 Constructing 2-CNFs for orbits in region 2 In this subsection, we will prove Lemma 3.12 for triplets in \mathcal{R}_{1} . To help prove this, we will utilize the following general claim regarding binomial coefficients. Claim 7.2 . For all m,k\in\mathbb{N} such that m\geq k and m,k are even, we have that \binom{m}{k}\leq(m/2+1)^{2}\binom{m/2}{k/2}^{2} We prove this claim later towards the end of this subsection. Let’s see how using it, our proof follows. Proof of Lemma 3.12 for i=2 . Let m=4 and consider any (p,q,r)\in\mathcal{R}_{2} such that m divides each of them (and hence also divides n=p+q+r ). We will construct 2 -CNF F that is consistent with {\mathbf{IP}}_{n}^{p\pmod{2}}={\mathbf{IP}}_{n}^{0} (since p is even) and such that \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert}\leq n^{K_{0}}(9/5)^{n} where K_{0} is a universal constant. We let our F be obtained by combining (as defined in Definition 3.6 ) n/2 copies of \mathbf{Matching} (as defined in Definition 3.5 ). Since \mathbf{Matching} is consistent with {\mathbf{IP}}_{n}^{0} , we apply Corollary 3.9 to infer that F is indeed consistent with {\mathbf{IP}}_{n}^{0} as desired. We now show the desired upper bound on \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert} . We apply 3.7 to obtain that the spectrum of F is given by P(x,y,z)=(x^{2}+2y^{2}+z^{2})^{n/2} and that \left\lvert\mathbf{sol}(F)\cap S(p,q,r)\right\rvert equals the coefficient of the monomial x^{p}y^{q}z^{r} in P(x,y,z) . Examining P , we easily count that this coefficient equals \binom{n/2}{p/2}\binom{n/2-p/2}{q/2}2^{q/2} . Using this and 3.3 , we have that \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert}=\frac{\binom{n}{p}\binom{n-p}{r}2^{q}}{\binom{n/2}{p/2}\binom{(n-p)/2}{q/2}2^{q/2}}=\frac{\binom{n}{p}}{\binom{n/2}{p/2}}\cdot\frac{\binom{n-p}{q}}{\binom{(n-p)/2}{q/2}}\cdot 2^{q/2} where the last equality follows using the fact that p+q+r=n . We apply 7.2 to the last expression and obtain: \displaystyle\frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert} \displaystyle\leq n^{4}\cdot\binom{n/2}{p/2}\cdot\binom{(n-p)/2}{q/2}\cdot 2^{q/2} \displaystyle\leq n^{4}\cdot\binom{n/2}{p/2}\cdot\sum_{i=0}^{(n-p)/2}\binom{(n-p)/2}{i}\cdot 2^{i} \displaystyle=n^{4}\cdot\binom{n/2}{p/2}\cdot 3^{(n-p)/2} (by binomial theorem) Recall that by assumption we are in \mathcal{R}_{2} which means p\geq p_{0}=16n/25 . So, p/2\geq(n/2)/2 , implying that the term \binom{n/2}{p/2} decreases as p increases. Also trivially the term 3^{(n-p)/2} decreases as p increases. Hence, n^{4}\cdot\binom{n/2}{p/2}\cdot 3^{(n-p)/2}\leq n^{4}\cdot\binom{n/2}{p_{0}/2}\cdot 3^{(n-p_{0})/2} . Therefore we obtain \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert}\leq n^{4}\cdot\binom{n/2}{p_{0}/2}\cdot 3^{(n-p_{0})/2} We apply Theorem 6.1 on the last expression to get: \frac{S(p,q,r)}{\left\lvert\mathbf{sol}(F)\cap S(p,q,r\right\rvert}\leq n^{4}\cdot 2^{(n/2)H(p_{0}/n)}\cdot 3^{(n-p_{0})/2}=n^{4}\cdot\left(2^{H(16/25)/2}\cdot 3^{9/50}\right)^{n}0 . With that, we will conclude that \max_{y\in[0,0.64]}g(y)=g(0.64)\leq 0.813 as desired. Recall that the derivative of the binary entropy function H is H^{\prime}(x)=\log((1-x)/x) . Using this, we compute that \displaystyle g^{\prime}(y) \displaystyle=\log((1-y)/y)-\frac{1}{2}-\frac{1}{2}\log((2a-y)/y) \displaystyle=\log\left(\frac{1-y}{\sqrt{2y(2a-y)}}\right) Therefore, to show that g^{\prime}(y)>0 for all y\in(0,0.64] , it suffices to show that for y in this domain, 1-y>\sqrt{2y(2a-y)} . Since both sides of this inequality are positive, this is equivalent to showing that (1-y)^{2}>2y(2a-y) . We simplify this to obtain that this is equivalent to showing 3y^{2}-y(4a+2)+1>0 . Let h(y)=3y^{2}-y(4a+2)+1 . We will show that for all y , h(y)>0 . The discriminant of this quadratic h(y) is (4a+2)^{2}-12=(3.42)^{2}-12<0 . This means h(y) as no real roots. Since h(0)=1>0 , we conclude that for all y , h(y)>0 as desired. ∎ 8 Coefficient extraction for each region In this section, we obtain asymptotic bounds for coefficients of a specific monomial from a specific generating function. These generating functions and monomials will arise from some region from Section 3 . To prove these results, we will require the following lemma regarding bounding coefficients of a power series: Lemma 8.1 . Let p,q\in\mathbb{N} be such that p^{2}+q^{2}\geq 4 . Let f:\mathbb{C}^{2}\to\mathbb{C} be analytic on a compact neighborhood \mathcal{N} around (0,0) . Let f(u,v)=\sum_{r=(r_{1},r_{2})\in\mathbb{N}^{2}}C_{r}u^{r_{1}}v^{r_{2}} where for all i\in\mathbb{N}^{2} , C_{i}\in\mathbb{R} and C_{i}\geq 0 . Let h:\mathbb{C}^{2}\to\mathbb{C} be defined as h(u,v)=\ln(f(u,v))-p\ln(u)-q\ln(v) . Assume there exists (u_{0},v_{0})\in\mathbb{R}^{2} such that u_{0},v_{0} are non-negative, \nabla_{h}(u_{0},v_{0})=0 and that \mathcal{H}_{h}(u_{0},v_{0}) is positive definite. Assume that on the torus \left\lvert u\right\rvert=u_{0},\left\lvert v\right\rvert=v_{0} , \left\lvert f(u,v)\right\rvert attains its unique global maximum at (u_{0},v_{0}) . Then, C_{p,q}=\frac{f(u_{0},v_{0})}{2\pi u_{0}^{p+1}v_{0}^{q+1}\sqrt{\det(\mathcal{H}_{h}(u_{0},v_{0}))}}\left(1+O\left(\frac{1}{\sqrt{p^{2}+q^{2}}}\right)\right). where \mathcal{H}_{h}(u_{0},v_{0}) is the Hessian of h evaluated at u_{0},v_{0} . Such a result is standard in analytic combinatorics but since we could not find an explicit statement of exactly this form, we will provide a somewhat self contained proof of this in Appendix A . For this section we assume it. In each of the next subsections, we will obtain a bound on the coefficient of the generating function to help compute {\mathbf{IP}} . In Section 8.1 these will come from \mathcal{R}_{1} , in Section 8.2 , these will come from \mathcal{R}_{3} , and in Section 8.3 , these will come from \mathcal{R}_{4} . 8.1 Bound for region 1 In this subsection, we obtain asymptotic bound on coefficient of generating function from \mathcal{R}_{1} . Proof of Lemma 7.1 . Let f(u,v)=P(u^{1/2},v,1) . Notice that since x appears in squared form in each of the three polynomials, it is still the case that f(u,v) is a product of powers of three polynomials. Since 2A+2B+2C=p+q+r=n and since each of the three polynomials is homogeneous, we infer that the coefficient of u^{p/2}v^{q} in f(u,v) equals the coefficient of x^{p}y^{q}z^{r} in P(x,y,z) . Define h:\mathbb{C}^{2}\to\mathbb{C} as h(u,v)=\ln(f(u,v))-(p/2)\ln(u)-q\ln(v) . We first see that \nabla_{h}(16,2)=0 . Next, we claim that the Hessian of h - \mathcal{H} is such that \mathcal{H}_{h}(16,2) positive definite. To show this, let \alpha(x,y)=h(\exp(x),\exp(y)) . It is well known (see section 4.5 from [ 3 ] ) that the function \alpha we defined is convex (note that h has nonnegative coefficients in its power series). By picking any three non-zero terms of the power series and checking that they don’t lie in a line, we see that \alpha will be strictly convex and hence that \mathcal{H}_{\alpha}(16,2) will be positive definite. Since \nabla_{h}(16,2)=0 , we apply the chain rule to infer that \mathcal{H}_{\alpha}(16,2)=D\cdot\mathcal{H}_{h}(16,2)\cdot D where D is the diagonal matrix with entries (16,2) . Since \mathcal{H}_{\alpha}(16,2) is positive definite and D is invertible, we infer that \mathcal{H}_{h}(16,2) is positive definite as well. We next apply triangle inequality to infer that in the (complex) torus where \left\lvert u\right\rvert=16,\left\lvert v\right\rvert=2 , the unique global maximum occurs at (16,2) (we need to use that at (\pm 16,\pm 2) , the value is smaller). Lastly, we claim that at least one of p or q must have value at least 0.01n . Indeed, if they are smaller then it must be that r\geq 0.98n , implying that A<0 . However, that is a contradiction since we assume A is a nonnegative integer. We will let our final universal constant C_{0} be large enough so that n is always assumed to be large enough such that we always have (p/2)^{2}+q^{2}\geq 4 . Therefore, we satisfy all conditions to apply Lemma 8.1 with u_{0}=16,v_{0}=2 where we want to extract coefficient (p/2,q) . We infer that there exists a universal constant C_{1} such that the coefficient equals \displaystyle\frac{25^{A+B+C}}{C_{1}4^{p}2^{q}{\mathtt{poly}}(p,q)}\left(1+\frac{1}{\sqrt{p^{2}+q^{2}}}\right) \displaystyle\geq\frac{5^{n}}{C_{1}4^{p}2^{q}{\mathtt{poly}}(n)}\left(1+\frac{1}{{\mathtt{poly}}(n)}\right) where in the last equality we used the fact that either p or q will be at least 0.01n . Hence, our desired lower bound on the coefficient indeed holds. ∎ 8.2 Bound for region 3 In this subsection, we obtain asymptotic bound on coefficient of generating function from \mathcal{R}_{3} . Proof of Lemma 7.3 . For i\in[2] , let f_{i}(u,v)=P_{i}(u^{1/2},v,1) . Since x appears in squared form, f_{i} is still product of three polynomials. Furthermore, since 2B_{i}+2C_{i}=p+q+r=n , and both the polynomials are homogeneous, we infer that the coefficient of u^{p/2}v^{q} in f_{i}(x,y,z) equals the coefficient of x^{p}y^{q}z^{r} in P_{i}(x,y,z) . Define h_{i}:\mathbb{C}^{2}\to\mathbb{C} by h(u,v)=\ln(f_{i}(u,v))-(p/2)\ln(u)-q\ln(v) . We will find non-negative (u_{i},v_{i})\in\mathbb{R}^{2} such that \nabla_{h_{i}}(u_{i},v_{i})=0 . We compute that \frac{\partial h_{i}}{\partial u}=-\frac{p}{2}\cdot\frac{1}{u}+\frac{B_{i}}{u+(v+1)^{2}} . Setting this to 0 and rearranging, we infer that \displaystyle u_{i}=\frac{p(v_{i}+1)^{2}}{2B_{i}-p} ( 1 ) We next compute that \frac{\partial h_{i}}{\partial v}=\frac{4C_{i}}{2v+1}+\frac{2B_{i}(v+1)}{u+(v+1)^{2}}-\frac{q}{v} . Setting this to 0 , rearranging, substituting in Equation 1 , and using the fact that 4C_{i}+2(2B_{i}-p)-2q=2r (since 2B_{i}+2C_{i}=p+q+r=n ), we infer that v_{i} satisfies the following quadratic equation: 2r\cdot(v_{i})^{2}+\beta_{i}\cdot v_{i}-q=0 where \beta_{i}=4C_{i}+(2B_{i}-p)-3q . This means v_{i} could equal \frac{\beta_{i}\pm\sqrt{\beta_{i}^{2}+8rq}}{4r} . By the inequalities satisfied by p,q,r , it must be the case that rq is at least a universal constant. This makes the value inside the square root comes out to be strictly larger than \beta_{i}^{2} and so one root is strictly negative and other is strictly positive. We reject the negative root since Lemma 8.1 requires the special point (u_{i},v_{i}) to have non-negative real values. With this value of u_{i},v_{i} , we show that \mathcal{H}_{h_{i}}(u_{i},v_{i}) is positive definite where \mathcal{H}_{h_{i}} is the the Hessian of h_{i} . For this, let \alpha_{i}(x,y)=h_{i}(\exp(x),\exp(y)) . Using the fact that h has nonnegative coefficients in its power series, we use the well known result (see section 4.5 from [ 3 ] ) that the function \alpha_{i} as we defined is convex. Also by picking any three non-zero terms of the power series and checking that they don’t lie in single line, we see that \alpha_{i} will be strictly convex and so \mathcal{H}_{\alpha_{i}}(u_{i},v_{i}) is positive definite. Using the fact that \nabla_{h_{i}}(u_{i},v_{i})=0 and chain rule, we obtain that \mathcal{H}_{\alpha_{i}}(u_{i},v_{i})=D\cdot\mathcal{H}_{h_{i}}(u_{i},v_{i})\cdot D where D is the diagonal matrix with entries (u_{i},v_{i}) . Since D is invertible, we infer that \mathcal{H}_{h_{i}}(u_{i},v_{i}) is indeed positive definite. We next apply the triangle inequality to infer that in the complex torus with \left\lvert u\right\rvert=u_{i},\left\lvert v\right\rvert=v_{i} , the unique global maximum for f_{i} occurs at (u_{i},v_{i}) (carefully checking that the values at (\pm u_{i},\pm v_{i}) are smaller). Also since r\leq n-8 , p+q+r=n and n\geq K_{0} where we will set K_{0} to be large enough universal constant, it must be the case that (p/2)^{2}+q^{2}\geq 4 . Therefore we satisfy all conditions to apply Lemma 8.1 with (u_{0},v_{0})=(u_{i},v_{i}) , we infer that the coefficient of u^{p/2}v^{q} in f_{i}(u,v) equals \frac{f(u_{i},v_{i})}{2\pi u_{i}^{p+1}v_{i}^{q+1}\sqrt{\mathcal{H}_{h_{i}}(u_{i},v_{i})}}\left(1+O\left(\frac{1}{\sqrt{p^{2}+q^{2}}}\right)\right). Since p^{2}+q^{2}\geq 4 , and u_{i},v_{i}\leq n , and that the entries of \mathcal{H}_{h_{i}} are bounded by {\mathtt{poly}}(u_{i},v_{i}) , we infer that there exists a universal constant K_{1} such that the coefficient is at least n^{-K_{1}}\cdot\frac{f(u_{i},v_{i})}{u_{i}^{p/2}v_{i}^{q}}=n^{-K_{1}}\cdot\frac{(u_{i}+(v_{i}+1)^{2})^{B_{i}}(2v_{i}+1)^{2C_{i}}}{u_{i}^{p/2}v_{i}^{q}} ∎ 8.3 Bound for region 4 In this subsection, we obtain asymptotic bound on coefficient of generating function from \mathcal{R}_{4} . Proof of Lemma 7.5 . We first prove that Q_{i} has a unique real nonnegative root. First, since Q_{i} has degree 3 , it has at least one real root. Let x_{0} be any such real root. Since Q_{i}(x_{0})=0 , we rearrange to infer that x_{0} must satisfy: \frac{4C_{i}x_{0}}{2x_{0}+1}+\frac{2x_{0}^{2}(2A_{i}-p)}{2x_{0}^{2}+1}=q We see that the left side at x=0 equals 0 and as x\rightarrow+\infty , it approaches 2C_{i}+2A_{i}-p=q+r (this is because n=2A_{i}+2C_{i}=p+q+r ). Since q and r are nonnegative and right side equals q , by intermediate value theorem, there must exist a unique value y\geq 0 such that left side equals q , proving our result. We now prove the asymptotic bound. For i\in[2] , let f_{i}(u,v)=P_{i}(u^{1/2},v,1) . Since x appears in squared form, f_{i} is still product of three polynomials. Furthermore, since 2A_{i}+2C_{i}=p+q+r=n , and both the polynomials are homogeneous, we infer that the coefficient of u^{p/2}v^{q} in f_{i}(x,y,z) equals the coefficient of x^{p}y^{q}z^{r} in P_{i}(x,y,z) . Define h_{i}:\mathbb{C}^{2}\to\mathbb{C} by h(u,v)=\ln(f_{i}(u,v))-(p/2)\ln(u)-q\ln(v) . We will find non-negative (u_{i},v_{i})\in\mathbb{R}^{2} such that \nabla_{h_{i}}(u_{i},v_{i})=0 . We compute that \frac{\partial h_{i}}{\partial u}=\frac{A_{i}}{u+2v^{2}+1}-\frac{p}{2u} . Setting this to 0 and rearranging, we infer that \displaystyle u_{i}=\frac{p(2v_{i}^{2}+1)}{2A_{i}-p} ( 1 ) We next compute that \frac{\partial h_{i}}{\partial v}=\frac{4C_{i}}{2v+1}+\frac{4vA_{i}}{u+2v^{2}+1}-\frac{q}{v} . Setting this to 0 , rearranging, substituting in Equation 1 , and using the fact that 8C_{i}+4(2A_{i}-p)-4q=4r (since 2A_{i}+2C_{i}=p+q+r=n ), we infer that v_{i} satisfies the following cubic equation: (4r)\cdot v_{i}^{3}+(4A_{i}-2p-2q)\cdot v_{i}^{2}+(4C_{i}-2q)\cdot v_{i}-q=0 In other words, Q_{i}(v_{i})=0 . From above, we know that there is a unique nonnegative root of Q_{i} and we will let v_{i} be that. With this value of u_{i},v_{i} , we show that \mathcal{H}_{h_{i}}(u_{i},v_{i}) is positive definite where \mathcal{H}_{h_{i}} is the the Hessian of h_{i} . For this, let \alpha_{i}(x,y)=h_{i}(\exp(x),\exp(y)) . Using the fact that h has nonnegative coefficients in its power series, we use the well known result (see section 4.5 from [ 3 ] ) that the function \alpha_{i} as we defined is convex. Also by picking any three non-zero terms of the power series and checking that they don’t lie in single line, we see that \alpha_{i} will be strictly convex and so \mathcal{H}_{\alpha_{i}}(u_{i},v_{i}) is positive definite. Using the fact that \nabla_{h_{i}}(u_{i},v_{i})=0 and chain rule, we obtain that \mathcal{H}_{\alpha_{i}}(u_{i},v_{i})=D\cdot\mathcal{H}_{h_{i}}(u_{i},v_{i})\cdot D where D is the diagonal matrix with entries (u_{i},v_{i}) . Since D is invertible, we infer that \mathcal{H}_{h_{i}}(u_{i},v_{i}) is indeed positive definite. We next apply the triangle inequality to infer that in the complex torus with \left\lvert u\right\rvert=u_{i},\left\lvert v\right\rvert=v_{i} , the unique global maximum for f_{i} occurs at (u_{i},v_{i}) (carefully checking that the values at (\pm u_{i},\pm v_{i}) are smaller). Also since r\leq n-8 , p+q+r=n and n\geq K_{0} where we will set K_{0} to be large enough universal constant, it must be the case that (p/2)^{2}+q^{2}\geq 4 . Therefore we satisfy all conditions to apply Lemma 8.1 with (u_{0},v_{0})=(u_{i},v_{i}) , we infer that the coefficient of u^{p/2}v^{q} in f_{i}(u,v) equals \frac{f(u_{i},v_{i})}{2\pi u_{i}^{p+1}v_{i}^{q+1}\sqrt{\mathcal{H}_{h_{i}}(u_{i},v_{i})}}\left(1+O\left(\frac{1}{\sqrt{p^{2}+q^{2}}}\right)\right). Since p^{2}+q^{2}\geq 4 , and u_{i},v_{i}\leq n , and that the entries of \mathcal{H}_{h_{i}} are bounded by {\mathtt{poly}}(u_{i},v_{i}) , we infer that there exists a universal constant K_{1} such that the coefficient is at least n^{-K_{1}}\cdot\frac{f(u_{i},v_{i})}{u_{i}^{p/2}v_{i}^{q}}=n^{-K_{1}}\cdot\frac{(u_{i}+v_{i}^{2}+1)^{A_{i}}(2v_{i}+1)^{2C_{i}}}{u_{i}^{p/2}v_{i}^{q}} ∎ Appendix A Proving coefficient asymptotics In this section, we will prove our required lemma regarding bounding coefficients of power series of an analytic function - Lemma 8.1 . To help prove this, we will require the following well known result that coefficient expansion of a generating function can be expressed as a Cauchy integral (see equation 1.5 from [ 20 ] ): Theorem A.1 (Bivariate Cauchy integral formula) . Let f:\mathbb{C}^{2}\to\mathbb{C} be analytic on a compact neighborhood \mathcal{N} around (0,0) . Let f(u,v)=\sum_{r=(r_{1},r_{2})\in\mathbb{N}^{2}}C_{r}u^{r_{1}}v^{r_{2}} where for all i\in\mathbb{N}^{2} , C_{i}\in\mathbb{R} and C_{i}\geq 0 . Then, for all r\in\mathbb{N}^{2} , it holds that C_{r}=\oint_{x\in\mathcal{N}}\left(\frac{1}{2\pi i}\right)^{2}f(x)\cdot x_{1}^{-r_{1}-1}\cdot x_{2}^{-r_{2}-1}\,dx. We will utilize the following result regarding bounding Cauchy integral: Theorem A.2 (Theorem 5.2 from [ 20 ] , specialized) . Let A,\phi:\mathbb{C}^{2}\to\mathbb{C} be analytic on a compact neighborhood \mathcal{N} around (0,0) . Furthermore assume that the real part of \phi is nonnegative on \mathcal{N} and vanishes only at (0,0) , and that the Hessian matrix \mathcal{H}_{\phi} of \phi is such that \mathcal{H}_{\phi}(0,0) is nonsingular. Let, I(\lambda)=\int_{\mathcal{N}}A(z)e^{-\lambda\phi(z)} . Then for \lambda\leq\frac{1}{2} , we have that: I(\lambda)=A(0,0)\frac{2\pi}{\sqrt{\det(\mathcal{H}_{\phi}(0,0))}}\cdot\frac{1}{\lambda}\left(1+O\left(\frac{1}{\lambda}\right)\right). Using these, we obtain the following estimate regarding estimating coefficient of an analytic function: Proof of Lemma 8.1 . We apply Theorem A.1 with the contour \mathcal{C} being product of circles with \left\lvert u\right\rvert=u_{0},\left\lvert v\right\rvert=v_{0} so that C_{p,q}=\frac{-1}{4\pi^{2}}\int_{(u,v)\in\mathcal{C}}f(u,v)u^{-p-1}v^{-q-1}dudv. For \theta=(\theta_{1},\theta_{2})\in[-\pi,\pi]^{2} , we perform change of variables to express the points in the contour as u=u(\theta)=u_{0}e^{i\theta_{1}},v=v(\theta)=v_{0}e^{i\theta_{2}} . We see that du=u_{0}ie^{i\theta_{1}}d\theta_{1} and dv=v_{0}ie^{i\theta_{2}}d\theta_{2} . We also use the fact that \exp(h(u,v))=\frac{f(u,v)}{u^{p}v^{q}} to obtain that C_{p,q}=\frac{1}{4\pi^{2}}\int_{\theta\in[\pi,\pi]^{2}}\exp(h(u(\theta),v(\theta)))d\theta. Let \lambda=\sqrt{p^{2}+q^{2}} . We perform one last change of variables where we let h^{\prime}(u,v)=h(u,v)/\lambda to express the integral as: C_{p,q}=\frac{\exp(h(u_{0},v_{0}))}{4\pi^{2}}\int_{\theta\in[\pi,\pi]^{2}}\exp\left(\lambda\cdot\left(h^{\prime}(u(\theta),v(\theta))-h^{\prime}(u_{0},v_{0})\right)\right)d\theta. We will apply Theorem A.2 with A(\theta)=1 , \phi(\theta)=h^{\prime}(u_{0},v_{0})-h^{\prime}(u(\theta),v(\theta)) . We claim the following: Claim A.3 . \det(\mathcal{H}_{\phi}(0,0))=\left(\frac{u_{0}v_{0}}{\lambda}\right)^{2}\det(\mathcal{H}_{h^{\prime}}(u_{0},v_{0})). We will prove this at the end and for now will just assume it. We first show that we satisfy all of the preconditions laid out by Theorem A.2 . First, we have that \phi(0,0)=0 and by unique maximality of u_{0},v_{0} that for all \theta\neq(0,0) , it follows that \phi(\theta)>0 . Second, we show that \mathcal{H}_{\phi}(0,0) is non-singular. By assumption, we know that \mathcal{H}_{h}(u_{0},v_{0}) is positive definite and so must be true for \mathcal{H}_{h^{\prime}}(u_{0},v_{0}) , making it singular. Therefore by A.3 , it follows that \mathcal{H}_{\phi}(0,0) is non-singular as well. Lastly, by assumption we have that \lambda\leq\frac{1}{2} . Hence, we can indeed apply Theorem A.2 with the same \lambda to infer that C_{p,q}=\frac{\exp(h(u_{0},v_{0}))}{4\pi^{2}}\cdot\frac{2\pi}{\sqrt{\det({\mathcal{H}_{\phi}(0,0)})}}\cdot\frac{1}{\lambda}\cdot\left(1+O\left(\frac{1}{\lambda}\right)\right). Using A.3 and the fact that \exp(h(u_{0},v_{0}))=\frac{f(u_{0},v_{0})}{u_{0}^{q}v_{0}^{q}} , our desired bound on C_{p,q} follows. We lastly prove our helper claim that relates \det(\mathcal{H}_{\phi}(0,0)) and \det(\mathcal{H}_{h^{\prime}}(u_{0},v_{0})) . Proof of A.3 . Let g(\theta)=-h^{\prime}(u(\theta),v(\theta)) so that \phi(\theta)=h^{\prime}(u_{0},v_{0})+g(\theta) . Since h^{\prime}(u_{0},v_{0}) is a constant, we have that \mathcal{H}_{g}(0,0)=\mathcal{H}_{\phi}(0,0) . Hence, it suffices to show that \det(\mathcal{H}_{g}(0,0))=\left(\frac{u_{0}v_{0}}{\lambda}\right)^{2}\det(\mathcal{H}_{h^{\prime}}(u_{0},v_{0})) . Using chain rule, we see that for i\in[2] : \frac{\partial g}{\partial\theta_{i}}=\frac{\partial h^{\prime}}{\partial u}\frac{\partial u}{\partial\theta_{i}}+\frac{\partial h^{\prime}}{\partial v}\frac{\partial v}{\partial\theta_{i}} When we evaluate this at (0,0) , we will evaluate \frac{\partial h^{\prime}}{\partial u} and \frac{\partial h^{\prime}}{\partial v} at (u_{0},v_{0}) . By assumption \nabla_{h}(u_{0},v_{0})=0 and so \nabla_{h^{\prime}}(u_{0},v_{0})=0 . Using above, this implies that \nabla_{g}(0,0)=0 . Using chain rule, the fact that \nabla_{g}(0,0)=0 , and recalling the definition of u(\theta) and v(\theta) , we obtain that \mathcal{H}_{g}(0,0)=D\mathcal{H}_{h^{\prime}}(u_{0},v_{0})D where D is the 2\times 2 diagonal matrix with entries iu_{0},iv_{0} . With this we finally compute that \displaystyle\det(\mathcal{H}_{g}(0,0)) \displaystyle=\det(D\mathcal{H}_{h^{\prime}}(u_{0},v_{0})D) \displaystyle=\det(D)\cdot\det(\mathcal{H}_{h^{\prime}}(u_{0},v_{0}))\cdot\det(D) \displaystyle=(u_{0}v_{0})^{2}\det(\mathcal{H}_{h^{\prime}}(u_{0},v_{0})) \displaystyle=\frac{(u_{0}v_{0})^{2}}{\lambda^{2}}\det(\mathcal{H}_{h}(u_{0},v_{0})) where for the last equality we used the fact that h^{\prime}=h/\lambda , which implies \mathcal{H}_{h^{\prime}}(u_{0},v_{0})=\frac{1}{\lambda}\mathcal{H}_{h}(u_{0},v_{0}) . ∎ ∎