[seqfan] Re: Corrections to A072368

[Rob Pratt]

I confirmed your corrections via integer linear programming, with a binary decision variable for each possible triple.  Here are the values for n <= 50:

6 54 214 594 1334 2614 4645 7676 11992 17912 25791 36021 49028 65269 85247 109493 138575 173094
213694 261048 315863 378888 450907 532730 625213 729244 845748 975679 1120035 1279848 1456176
1650123 1862831 2095469 2349237 2625387 2925197 3249976 3601072 3979879 4387811 4826324 5296910
5801102 6340458 6916565 7531074 8185650 8881988 9621838

-----Original Message-----
From: SeqFan <seqfan-bounces at list.seqfan.eu> On Behalf Of martin_n_fuller via SeqFan
Sent: Friday, July 21, 2023 9:17 AM
To: seqfan at list.seqfan.eu
Cc: martin_n_fuller <martin_n_fuller at btinternet.com>
Subject: [seqfan] Corrections to A072368

EXTERNAL

A072368 "Minimal total volume of n bricks with integer sides, all sides being different. Lowest value of sum of products of triples p*q*r chosen from [1,3n]."

I have found lower values for A072368(12) and A072368(14).  Can anyone confirm that these are the only corrections?  My method is described below along with some proofs.
There are further corrections and many missing sums in the "Illustration of initial terms" linked to A072368.  Should I replace it with my file (up to n=33) or should I add a comment on the existing file that some terms are not the lowest value or are incomplete?

a(12) <= 36021 (was 36022)
1*35*36 + 2*33*34 + 3*31*32 + 4*28*29 + 5*22*30 + 6*21*26 + 7*19*25 +
8*17*24 + 9*16*23 + 10*12*27 + 11*15*20 + 13*14*18

a(14) <= 65269 (was 65270)
1*41*42 + 2*39*40 + 3*37*38 + 4*35*36 + 5*30*34 + 6*26*33 + 7*24*31 +
8*20*32 + 9*21*27 + 10*22*23 + 11*16*29 + 12*17*25 + 13*14*28 + 15*18*19 and 5 other sums

Also improvements for n=26, 31, 32, 33 in the "Illustration of initial terms".  My calculations only go to n=33.
a(26) <= 729244 (was 729245)
a(31) <= 1456176 (was 1456177)
a(32) <= 1650123 (was 1650124)
a(33) <= 1862831 (was 1862833)
The worst case for missing sums is a(30).  "Illustration of initial terms" gives 66 optimal sums but my program finds 1943.  NB My file size with n=30 is 700 KB, file size up to n=29 is 120 KB.


Method: My program uses the branch and bound algorithm.  A branch is to try each possible product that contains the smallest remaining number.
The bound for the remaining set is defined as follows.
Let S be the set of 3m remaining numbers, and define a(S) to be the minimal sum of products of triples covering S.  Claim that the following are lower bounds:
LB1: a(S) >= m * product(S)^(1/m).
LB2: Let p be the smallest element in S and let q<r be the largest 2 elements in S.  Let S2 = S\{p,q,r}.  If pqr < product(S)^(1/m), then
a(S) >= pqr + (m-1) * product(S2)^(1/(m-1))
LB3: If LB2 applies, then let t be the smallest element in S2 and let u<v be the largest elements.  Let S3 = S2\{t,u,v}.  If tuv < product(S2)^(1/(m-1)), and tu > pr, then a(S) >= pqr + tuv + (m-2) *
product(S3)^(1/(m-2))

Proof for LB1:
This is based on the AM-GM inequality. The geometric mean of the products is product(S)^(1/m), which is a lower bound for the arithmetic mean. This gives the stated bound for the sum.
OEIS currently states this for the initial case: a(n) >= ceiling(n*(3n!)^(1/n)).  This is exact for n=1..3, but by n=19 the gap is over 9000.

Proof for LB2:
Let x be the unknown product containing the smallest element of S.  Then AM-GM inequality says that the a(S) >= x + (m-1) * (product(S)/x)^(1/(m-1)).
Treat product(S) and m as fixed and differentiate wrt x.  Can show that RHS is strictly decreasing for x < product(S)^(1/n), and strictly increasing for x > product(S)^(1/n).
Therefore to minimise RHS, want to take x as close as possible to product(S)^(1/n).
This bound is exact for the initial case for n<=6.  At n=19 the gap is 3207.

Proof for LB3:
Let a<b<c<d<e<f.  Claim that aef+bcd is the minimal sum-of-products-of-triples iff bc>=af.
There are 10 sums-of-products-of-triples (there are 5-choose-2 pairs that can be multiplied by a).  aef+bcd is one option; the other 9 can be formed by swapping one letter between the summands.
Consider swapping a and b, leaving ef and cd untouched.  aef+bcd minimal requires 0 <= (bef+acd) - (aef+bcd) = ef(b-a) + cd(a-b) = (ef-cd)(b-a).
This is true by the initial assumption a<b<c<d<e<f.
Same result swapping a and either c or d, because we get a similar inequality, and cd>bd>bc and d>c>b from the initial assumption.
Now consider swapping e and d, leaving af and bc untouched.  aef+bcd minimal requires 0 <= (adf+bce) - (aef+bcd) = bc(e-d) + af(d-e) = (bc-af)(e-d).  e-d>0 by initial assumption. Therefore require bc>=af.
Initial assumption gives that cd>bd>bc and af>ae.  Therefore bc>=af implies that aef+bcd is minimal compared to all remaining swaps.
This bound is exact for the initial case for n<=10 except n=7.  At n=19 the gap is 1008.

Unproved extension to LB3:  It would be nice to repeat LB3 as many times as it applies, but I have no proof that this greedy algorithm is globally optimal.  The proof for LB3 only shows that it is pairwise optimal.
This greedy algorithm is exact for n=1..6 and 8..11, and is less than the best known value by no more than 3 up to n=33.  My program uses this as an initial upper bound for the branch and bound algorithm.

Martin Fuller

--
Seqfan Mailing list - http://list.seqfan.eu/