[seqfan] Corrections to A072368

[martin_n_fuller]

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