Efficient Evaluations of Weighted Sums over the Boolean Lattice inspired by conjectures of Berti, Corsi, Maspero, and Ventura

Shalosh B. EKHAD and Doron ZEILBERGER

Abstract: In their study of water waves, Massimiliano Berti, Livia Corsi, Alberto Maspero, and Paulo Ventura, came up with two intriguing conjectured identities involving certain weighted sums over the Boolean lattice. They were able to prove the first one, while the second is still open. In this methodological note, we will describe how to generate many terms of these types of weighted sums, and if in luck, evaluate them in closed-form. We were able to use this approach to give a new proof of their first conjecture, and while we failed to prove the second conjecture, we give overwhelming evidence for its veracity. In this second version, we are happy to announce that Mark van Hoeij was able to complete the proof of the second conjecture, by explicitly solving the second-order recurrence mentioned at the end.

An Intriguing Email message from Alberto Maspero

Awhile ago one of us (DZ) received an email message [M], with the following.

In our current study of water waves [BCMV], continuing our work in [BMV], and other papers, we came across the following sums.

Let p ≥ 2, 1 ≤ q ≤ p − 1 and 0 < j_{1} < j_{2} < … < j_{q} < p be positive integers. Define

n_{q}^{(p)}(j_{1}, …, j_{q}) := (−12)^{q}j_{1} ⋯ j_{q} \frac{j_{1}(j_{2} − j_{1}) ⋯ (j_{q} − j_{q−1})(p − j_{q})}{(p^{3} − p + j_{1} − j_{1}^{3}) ⋯ (p^{3} − p + j_{q} − j_{q}^{3})} ,  (1)

and

g_{q}^{(p)}(j_{1}, …, j_{q}) := −\frac{28}{9}p^{2} + \frac{49}{45}q + \frac{32}{9}j_{1}^{2} − \frac{4}{9} − \frac{4}{9} \frac{p^{3} − p}{j_{1}} + \frac{5}{18}(p^{3} − p) (\frac{1}{j_{1}} + ⋯ + \frac{1}{j_{q}} ) (2)

\frac{38}{15} (j_{1}^{2} + ⋯ + j_{q}^{2})+\frac{p^{3} − p}{5} (\frac{p + j_{1}}{p^{2} + j_{1}^{2} + pj_{1} − 1} + … + \frac{p + j_{q}}{p^{2} + j_{q}^{2} + pj_{q} − 1})−\frac{13}{9}(j_{1}j_{2}+j_{2}j_{3}+⋯+j_{q}p) .

The following identities seem to hold.

∑_{q=1}^{p−1} ∑_{0<j_{1}<...<j_{q}<p} n_{q}^{(p)}(j_{1}, …, j_{q}) = −p .  (3)

∑_{q=1}^{p−1} ∑_{0<j_{1}<...<j_{q}<p} n_{q}^{(p)}(j_{1}, …, j_{q}) g_{q}^{(p)}(j_{1}, ….j_{q}) = p(p + 1)^{2} .  (4)

Maspero concluded:

“We actually managed, after dire efforts, to prove (3), whereas claim (4) seems out of reach. We just verified it for p = 2, …, 21.”

Why are such sums interesting?

Note that the sums in (3) and (4) are weighted sums defined over all non-empty subsets of the set {1...p − 1}. Hence to compute many terms, straight from the definition, is exponentially expensive.

They are a bit unnatural in that the symbol p has both the roles of integer and of variable. Our first step is to decouple these two roles of p, introduce a formal variable x, and define

N(x; j_{1}, …, j_{q}) := (−12)^{q}j_{1} ⋯ j_{q} \frac{j_{1}(j_{2} − j_{1}) ⋯ (j_{q} − j_{q−1})(x − j_{q})}{(x^{3} − x + j_{1} − j_{1}^{3}) ⋯ (x^{3} − x + j_{q} − j_{q}^{3})} ,  (1′)

G(x; j_{1}, …, j_{q}) := −\frac{28}{9}x^{2} + \frac{49}{45}q + \frac{32}{9}j_{1}^{2} − \frac{4}{9} − \frac{4}{9} \frac{x^{3} − x}{j_{1}} + \frac{5}{18}(x^{3} − x) (\frac{1}{j_{1}} + ⋯ + \frac{1}{j_{q}} ) (2′)

\frac{38}{15} (j_{1}^{2} + ⋯ + j_{q}^{2})+\frac{x^{3} − x}{5} (\frac{x + j_{1}}{x^{2} + j_{1}^{2} + xj_{1} − 1} + … + \frac{x + j_{q}}{x^{2} + j_{q}^{2} + xj_{q} − 1})−\frac{13}{9}(j_{1}j_{2}+j_{2}j_{3}+⋯+j_{q−1}j_{q}+j_{q}x) .

Note that N(p; j_{1}, …, j_{q}) = n_{q}^{(p)}(j_{1}, …, j_{q}) and G(p; j_{1}, …, j_{q}) = g_{q}^{(p)}(j_{1}, …, j_{q}).

We are interested in efficient computation, and if possible, explicit evaluation of

A_{p}(x) := ∑_{q=1}^{p−1} ∑_{0<j_{1}<...<j_{q}<p} N(x; j_{1}, …, j_{q}) ,  (3′)

and

C_{p}(x) := ∑_{q=1}^{p−1} ∑_{0<j_{1}<...<j_{q}<p} N(x; j_{1}, ….j_{q})G(x; j_{1}, ….j_{q}) .  (4′)

In order to facilitate dynamical programming, it is natural to consider these weighted sums where the largest member of the subset, j_{q}, is fixed. So we define

B_{p}(x) := ∑_{0<j_{1}<...<j_{q}=p} N(x; j_{1}, …, j_{q}) ,  (3′′)

and

D_{p}(x) := ∑_{0<j_{1}<...<j_{q}=p} N(x; j_{1}, …, j_{q})G(x; j_{1}, …, j_{q}) .  (4′′)

Once the quantities B_{p}(x) and D_{p}(x) are known, our original quantities of interest, A_{p}(x) and C_{p}(x), can be evaluated using

A_{p}(x) = ∑_{p′=1}^{p−1} B_{p′}(x) .

C_{p}(x) = ∑_{p′=1}^{p−1} D_{p′}(x) .

The general framework Note that the weights N(x; j_{1}, …, j_{q}) and G(x; j_{1}, …, j_{q}) have a recursive “Markovian” structure.

• If you know N(x; j_{1}, …, j_{q−1}), you can quickly get N(x; j_{1}, …, j_{q−1}, j_{q}), by multiplying by a certain function of (j_{q−1}, j_{q}).

• If you know G(x; j_{1}, …, j_{q−1}), you can quickly get G(x; j_{1}, …, j_{q−1}, j_{q}), by adding a certain (different) function of (j_{q−1}, j_{q}). This leads us to consider the following general set-up. Definition: Let f_{1}(X) be an arbitrary uni-variate function, and f_{2}(X, Y) an arbitrary bivariate function. Define the weight, for singleton sets {j_{1}}

W (f_{1}, f_{2}; [j_{1}]) := f_{1}(j_{1}) ,

and for sets with more than one element, recursively (where we write j_{1}, …, j_{q} in increasing order):

W (f_{1}, f_{2}; [j_{1}, …, j_{q}]) := W (f_{1}, f_{2}; [j_{1}, …, j_{q−1}]) · f_{2}(j_{q−1}, j_{q}) .

Similarly let g_{1}(X) and g_{2}(X, Y) be arbitrary univariate and bivariate functions and define

V (g_{1}, g_{2}; [j_{1}]) := g_{1}(j_{1}) ,

and for sets with more than one element, recursively V (g_{1}, g_{2}; [j_{1}, …, j_{q}]) := V (g_{1}, g_{2}; [j_{1}, …, j_{q−1}]) + g_{2}(j_{q−1}, j_{q}) .

Note that the original [BCMV] summations have the following f_{1}, f_{2}, g_{1}, g_{2}:

f_{1}(X) = −\frac{12X^{2} (x − X)}{−X^{3} + x^{3} + X − x} ,

f_{2}(X, Y) = −\frac{12Y (Y − X) (x − Y)}{(x − X) (−Y^{3} + x^{3} + Y − x)} ,

g_{1}(X) = −\frac{28x^{2}}{9} + \frac{29}{45} + \frac{274X^{2}}{45} − \frac{x^{3} − x}{6X} + \frac{(x^{3} − x) (x + X)}{5X^{2} + 5xX + 5x^{2} − 5} − \frac{13xX}{9} ,

g_{2}(X, Y) = \frac{\frac{5}{18}x^{3} − \frac{5}{18}x}{Y} + \frac{38Y^{2}}{15} + \frac{(x^{3} − x) (x + Y)}{5Y^{2} + 5xY + 5x^{2} − 5} − \frac{13XY}{9} − \frac{13 (Y − X) x}{9} + \frac{49}{45} .

The general analogs of A_{p}(x), B_{p}(x), C_{p}(x) and D_{p}(x), let’s call them a_{p}, b_{p}, c_{p}, and d_{p}, respectively: are

b_{p} := ∑_{0<j_{1}<...<j_{q}=p} W (f_{1}, f_{2}; [j_{1}, …, j_{q}]) ,

and then

a_{p} = ∑_{p′=1}^{p−1} b_{p′} .

d_{p} := ∑_{0<j_{1}<...<j_{q}=p} W (f_{1}, f_{2}; [j_{1}, …, j_{q}]) V (f_{1}, f_{2}; [j_{1}, …, j_{q}]) ,

and then

c_{p} = ∑_{p′=1}^{p−1} d_{p′} .

Let’s first try to examine b_{p}. We can break-up the sum that defines b_{p}, where every summand has j_{q} = p, according to the value of j_{q−1}:

b_{p} := ∑_{{0<j_{1}<...<jq \atop jq =p}} W (f_{1}, f_{2}; [j_{1}, …, j_{q}]) = ∑_{p′=1}^{p−1} ∑_{{0<j_{1}<...<j_{q−1}<p \atop j_{q−1}=p′}} W (f_{1}, f_{2}; [j_{1}, …, j_{q−1}, p]) =

∑_{p′=1}^{p−1} ∑_{{0<j_{1}<...<j_{q−1} \atop j_{q−1}=p′}} W (f_{1}, f_{2}; [j_{1}, …, j_{q−1}]) · f_{2}(p′, p) =

∑_{p′=1}^{p−1} f_{2}(p′, p) ( ∑_{0<j_{1}<...<j_{q−1}=p′} W (f_{1}, f_{2}; [j_{1}, …, j_{q−1}])) = ∑_{p′=1}^{p−1} f_{2}(p′, p) b_{p′} .

Hence the sequence b_{p} can be computed in quadratic-time using the recurrence

b_{p} = ∑_{p′=1}^{p−1} f_{2}(p′, p) b_{p′} ,

subject to the initial condition

b_{1} = f_{1}(1) .

A similar argument, that we omit, enables us to get a quadratic-time recurrence for d_{p}, that assumes that b_{p} is already known. Once we get a hold of b_{p} and d_{p}, we can recover a_{p} and c_{p} using a_{p} = ∑_{p′=1}^{p−1} b_{p′} and c_{p} = ∑_{p′=1}^{p−1} d_{p′}. Let’s go back to specializing to the [BCMV] (already proved by them) conjecture (3). If we are lucky and we can conjecture an explicit expression for B_{p}(x), then all we have to do is verify that this conjectured expression also satisfies the same recurrence and initial condition. With the above f_{2}(X, Y) the recurrence becomes

B_{p}(x) = −12\frac{p(x − p)}{x^{3} − x + p − p^{3}} (p + ∑_{p′=1}^{p−1} \frac{p − p′}{x − p′} B_{p′}(x)) ,  (5)

with the initial condition B_{0}(x) = 0.

Cranking out the first 20 terms one easily conjectures

B_{p}(x) = \frac{12p^{2} (p − x)}{x (x + 1) (x − 1)} ,

and it is routine to verify (even by hand, but Maple is glad to do it for you) that (5) is satisfied if B_{p}(x) is replaced by the above right side. Then we ask Maple to kindly sum

A_{p}(x) = ∑_{p′=1}^{p−1} \frac{12p^{′2} (p′ − x)}{x (x + 1) (x − 1)} ,

giving

A_{p}(x) = \frac{p (p − 1) (3 p^{2} − 4 xp − 3 p + 2 x)}{x (x − 1) (x + 1)} .

Now what [BCMV] are really interested in is not A_{p}(x), in general, but the special case x = p, i.e. in A_{p}(p). Plugging-in x = p above, and simplifying gives that indeed

A_{p}(p) = −p .

So we have a new proof of the already-proved-by-them identity (3) of [BCMV].

We can get similar dynamical programming (quadratic-time) recurrence for D_{p}(x) that expresses it in terms of previous values {D_{p′}(x) : 1 ≤ p′ ≤ p − 1} and (the already known) B_{p}(x). Using the above proved expression for the latter, we can compute many terms. Alas, it is no longer a nice rational function, and the sequence seems very complicated. But using the holonomic ansatz [Z] (see [K] for a great Mathematica implementation) one can first guess (very complicated!) linear recurrences for both D_{p}(x) and C_{p}(x), that nevertheless, to our pleasant surprise, are mere second order (but with very complicated coefficients). See procedures DxH(p,x) and CxH(p,x) in our Maple package mentioned below. These recurrences are first guessed, using undetermined coefficients, implemented in our Maple package FindRec.txt, available from:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/FindRec.txt .

Once guessed, they are all automatically and rigorously provable using the holonomic ansatz as implemented by Koutschan, i.e. the sequences defined by these second-order recurrences also satisfy the original recurrences.

This enables us to easily compute the first 2000 terms of the sequence {C_{p}(x)} that are all very complicated rational functions of x. But when we plug-in x = p the sequence {C_{p}(p)} coincides with the conjectured sequence {p(p + 1)^{2}}. Of course, this is not a rigorous proof, but being empiricists, knowing that it is true for the first 2000 terms, is good enough for us. Maple package and input and output files Everything is implemented in the Maple package BCMV.txt available from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/BCMV.txt .

The front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bcmv.html ,

contains the input and output files that rigorously prove the above explicit expressions for A_{p}(x) and B_{p}(x), and that empirically verifies (4) all the way to p = 2000. Postscript written Feb. 28, 2024: Mark van Hoeij met our challenge, to explicitly solve the recurrence satisfied by C_{p}(x), that enables plugging-in x = p into it and proving that indeed C_{p}(p) = p(p + 1)^{2}. See:

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bcmvChallenge.txt .

For a detailed explanation, see the postscript kindly written by Mark van Hoeij:

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bcmvMvH.html .

This completes the (rigorous!) proof of Conjecture (4). A donation of 100 dollars to the OEIS, in Mark van Hoeij’s honor, has been made. References

[BCMV] M. Berti, L. Corsi, A. Maspero, and P. Ventura, Study of water waves, in preparation.

[BMV] M. Berti, A. Maspero, and P. Ventura, Full description of Benjamin-Feir instability of stokes waves in deep water, Inventiones mathematicae 230 (2022), 651-711.

https://link.springer.com/content/pdf/10.1007/s00222-022-01130-z.pdf ,
arxiv version: https://arxiv.org/abs/2204.00809 .

[K] Christoph Koutschan, Advanced applications of the holonomic systems approach, PhD thesis,

http://www.koutschan.de/publ/Koutschan09/thesisKoutschan.pdf .

[M] Alberto Maspero, Email message to Doron Zeilberger, Jan. 26, 2024.

[Z] Doron Zeilberger, A Holonomic Systems approach to special functions, J. Computational and Applied Math 32 (1990), 321-368.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/holonomic.html .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

First version: Feb. 22, 2024 ; This second version: Feb. 28, 2024 .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org