[seqfan] Re: distinct sums in a square

[hv at crypt.org]

I'm glad you like it, Rainer. :)

Be aware that there appear to be many solutions. For n = 2, 3, 4 I found
3, 9, 755 distinct squares respectively yielding a(n). As such it is
possible some of the aspects that you noted are an artifact of
the manner in which I generated them.

Based on the insight from my earlier footnote that S_e + 2S_c is a relevant
constraint on optimal solutions, my code selects elements to generate in
this order, starting with the outer shell of the square:
  1  5 ... 7  2
  6           8
 ...         ...
  9          11
  3 10 ...12  4

Previously I then took the remaining inner elements in normal order,
but I have now refined that to repeat the above pattern for successive
inner shells. This has allowed me to improve my best candidate for n=6
and start to generate candidates for n=7 and n=8:

a(6) <= 131 (theoretical minimum 128):
  0  0  0  0  0  0    0  4  8 12 14  1
  0  4  8 12 14  1    5 24 26 34 32 15
  1 12  2  0  5  0   13 27 23 22 28  6
  0  8  1  3  9  0   10 36 19 20 35  9
  1 15  5  7 18  0   16 30 29 33 37 18
  0  1  1  0  3  0    2 17  7 11 21  3

a(7) <= 257 (theoretical minimum 237):
  0  0  0  0  0  0  0    0  4 11 21 14  6  1
  0  4 11 21 14  6  1    5 26 36 51 41 35  7
  1 11  0  5  0 14  0   12 37 34 27 42 40 15
  0 21  7  1  9 20  0   22 54 29 23 30 61 20
  0 15  0  1  0 18  0   16 43 38 25 44 48 18
  1  7 15 23 16 10  0    8 39 46 55 49 47 10
  0  1  1  0  0  3  0    2  9 17 24 19 13  3

a(8) <= 411 (theoretical minimum 405):
  0  0  0  0  0  0  0  0    0  4 11 20 22 14  6  1
  0  4 11 20 22 14  6  1    5 26 36 59 57 42 35  7
  1 11  1  6  1  0 14  0   12 37 32 41 53 29 43 15
  0 20  3 13 24  0 23  0   21 58 38 48 52 51 64 23
  0 24  1  2 14  4 27  0   24 60 33 30 46 45 72 27
  0 15  3  0  2  0 18  0   16 49 34 31 44 40 55 18
  1  7 15 24 28 16 10  0    8 39 50 67 70 54 47 10
  0  1  1  0  0  0  3  0    2  9 17 25 28 19 13  3

I'm astonished how close to optimal that a(8) solution is, and that
it falls out quite quickly when running my code, whereas my best a(7)
solution took much longer to find and is still much further from optimal:
I wonder if this is an early signal of divergence in the behaviour of
odd versus even n.

Hugo

Rainer Rosenthal <r.rosenthal at web.de> wrote:
:Hi Hugo
:
:Congratulations, what a wonderful puzzle!
:
:Solutions seem far from any ready-made pattern and look very sophisticated.
:n=3: one can get a matrix with sum 10 easily by putting 0, 1, 2, 3, 4 on
:the 5 diagonal points.
:At first this looks like a real champion, but then comes your solution
:with sum 9. Astonishing.
:n = 4: elements seem to need at least maximum size 6 in order to find
:proper places. I was able to find a solution with max 6 and sum 34, but
:better results exist for sure. It is another surprise that with larger
:maximum size 7 we can get smaller sums. Your record solution with max 7
:is beautiful, because the element-sums are exactly all the numbers from
:0 to 15.
:n = 5 and n = 6: fascinating to see the borders of the square filled
:with many zeroes and one zero in the middle. Everything very irregular
:and without symmetry - wonderful.
:
:Thanks for this beautiful puzzle, and a happy New Year 2021 for you all,
:Rainer
:
:
:
:Am 11.01.2021 um 01:47 schrieb hv at crypt.org:
:> Define a(n) as the least k such that an n x n grid of non-negative
:> integers summing to k can be found, in which each element when added
:> to its orthogonal neighbours yields a distinct sum.
:>
:> I believe the sequence starts 0, 6, 9, 27 which is not in the OEIS.
:>
:> I have (not necessarily minimal) candidates for a(5) and a(6), and no
:> candidate for n > 6. I'd appreciate confirmation of at least a(1) .. a(4)
:> before I submit to the OEIS - I have at best medium confidence in the
:> correctness of the code I've written to get these values.
:>
:> For n > 4, I believe [1] we need a(n) >= (n^4 - n^2 + 14) / 10, giving
:> a(5) > 61.4 and a(6) > 127.4, so my candidates approach but do not hit
:> the theoretical optimum. The only upper bound I have is the relatively
:> useless a(n) <= 2^(n^2) - 1.
:>
:> Examples (need fixed font!):
:>
:> a(1) = 0:                 element sums
:>    0                       0
:>
:> a(2) = 6:
:>    0 1                     3 4
:>    2 3                     5 6
:>
:> a(3) = 9:
:>    0 0 0                   0 1 3
:>    0 1 3                   2 8 4
:>    1 4 0                   5 6 7
:>
:> a(4) = 27:
:>    0 0 0 0                  0  1  3  7
:>    0 1 3 7                  4 10 14 11
:>    3 6 3 1                  9 15 13 12
:>    0 2 0 1                 11  8  6  2
:>
:> a(5) <= 63:
:>    0  0  0  0  0            0  9  4 13  1
:>    0  9  4 13  1           10 19 26 22 14
:>    1  6  0  4  0            7 21 17 25  5
:>    0  5  3  8  0            6 16 20 18  8
:>    0  2  4  3  0            2 11 12 15  3
:>
:> a(6) <= 134:
:>    0  0  0  0  0  0         0  4  6  7 12  1
:>    0  4  6  7 12  1         5 23 21 26 29 13
:>    1 13  4  1  9  0        14 30 24 22 33 10
:>    0  8  0  1 11  0         9 37 19 25 38 11
:>    0 16  6 12 17  0        16 32 34 36 43 17
:>    0  2  0  0  3  0         2 18  8 15 20  3
:>
:>
:> Ideas, constructions, better constraints or more values all welcome.
:>
:> Hugo
:>
:> ---
:>
:> [1] Justification of lower bound: letting S_c be the sum of the corner
:> elements and S_e the sum of the non-corner edge elements, then the total
:> of all the element sums is 5a(n) - S_e - 2S_c. However they are required
:> to be n^2 distinct non-negative integers, which must sum to at least
:> T(n^2 - 1) = n^2 (n^2 - 1) / 2.
:>
:> For n > 4, making the element sums at the corners distinct requires edge
:> or corner elements contributing to sums of at least { 0, 1, 2, 3 }.
:> The edge pieces adjacent to the corner with 0 sum must have their other
:> adjacent edge differ by at least 1, so we have S_e + 2S_c >= 7.
:>
:> Thus a(n) >= (T(n^2 - 1) + 7) / 5 = (n^4 - n^2 + 14) / 10.