[seqfan] Re: distinct sums in a square

[Robert Gerbicz]

<hv at crypt.org> ezt írta (időpont: 2021. jan. 11., H, 1:57):

> 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.
>
> 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.
>
>
--
> Seqfan Mailing list - http://list.seqfan.eu/


a(n)<1/10*n^4+48*n^3+1299/10*n^2+4*n for every n value with an explicit
construction!

So almost matching the conjectured (trivial) lower bound,
of course the lower term 48*n^3 is very likely not optimal.
[the actual construction gives a very slightly better result,
just summed an easy upper bound for the matrixsum].

The natural grid numbering is good (at least for the inner-inner squares,
so squares that has no neighbour edge square),
so using A[x,y]=n*x+y is good because the von Neumann sum is 5*(n*x+y) for
each square. But it is giving 5 times larger total matrixsum, easy
solution, regard:
A[x,y]=floor((n*x+y)/5), the problem with this is that it is good only if
n%5=2 or 3 in the inner-inner square, hack it (and we really need to do
this, because
we don't know if the a() sequence is an increasing function or not):
A[x,y]=floor((n*x+y)/5)+E(y,n), where abs(E(y,n))<=1 and depends only on n
mod 5,y mod 5.
Since we have few, only 8*n-16 not inner-inner square where we could see
duplicate sums we can perturbate the matrix a little, even using terms on
the edges (only!) up to O(n^2) to get a valid solution and still keeping
the good upper bound.

[notice that Pari-gp is indexing from 1, not from 0.]
To get the explicit matrix solution call F(n);
this also checks if the matrix is a good solution or not.
c(x,y,n)={if(x>1&&x<n&&y>1&&y<n,return(0));
if(x==1&&y==1,return(31));
if(x==1&&y==n,return(61));
if(x==n&&y==n,return(77));
if(x==n&&y==1,return(55));
if(x==1,return(2));
if(y==n,return(10));
if(x==n,return(15));
if(y==1,return(19))}
F(n)={A=matrix(n,n,i,j,floor((n*(i-1)+j-1)/5)+
(n%5==0)*((j-1)%5==3)+
(n%5==1)*(((j-1)%5==4)-((j-1)%5==1))+
(n%5==4)*(((j-1)%5==2)-((j-1)%5==4))+
c(i,j,n)*n^2);
for(j=2,n-1,A[1,j]+=(j-1)*n;A[n,j]+=(j-1)*n);
for(i=2,n-1,A[i,1]+=(i-1)*n;A[i,n]+=(i-1)*n);
S=matrix(n,n,i,j,0);w=vector(n^2);dx=[0,1,-1,0,0];dy=[0,0,0,1,-1];
ans=0;for(i=1,n,for(j=1,n,ans+=A[i,j];for(h=1,5,x=i+dx[h];y=j+dy[h];
if(x>0&&x<=n&&y>0&&y<=n,S[i,j]+=A[x,y]));w[n*(i-1)+j]=S[i,j]));
if(length(Set(w))<n^2,return(0));print(ans);return(A)}

We can see the following numbers with at most 9/5 error
on the 4 corners, 4 edges and in the inner square:

31*n^2                  2*n^2+n*y+y/5             61*n^2+(n-1)/5
19*n^2+6*x*n/5    (x*n+y)/5                      10*n^2+(6*x+1)*n/5-1/5
(276*n^2-n)/5       (76*n^2-n+y)/5+y*n      (386*n^2-1)/5

For example A[x,0]=19*n^2+6*x*n/5 with a maximum absolute error of 9/5,
where 0<x<n-1. [using 0..n-1 indexing]

With at most 5*9/5=9 error we see the following von Neumann sums
for the 25 different type of square, at the beginning on each line
giving the possible values for floor(S(x,y)/n^2), assuming n>18  (we can
easily verify that the the construction is good for n<=18).

[if you see x,y in the table then 1<x<n-2 and 1<y<n-2].
52:    S(0,0)=52*n^2+(11*n+1)/5
35:    S(0,1)=35*n^2+(16*n+4)/5
6,7,8: S(0,y)=6*n^2+((15*y+1)*n+4*y)/5
66:    S(0,n-2)=67*n^2-4*n-8/5
73,74: S(0,n-1)=74*n^2-(n+4)/5
69:    S(1,0)=69*n^2+(19*n+1)/5
21:    S(1,1)=21*n^2+3*n+1
2,3:   S(1,y)=2*n^2+(y+1)*n+y
13:    S(1,n-2)=13*n^2+n-2
81:    S(1,n-1)=81*n^2+23/5*n-1
57,58,59,60: S(x,0)=57*n^2+(19*x*n+1)/5
19,20: S(x,1)=19*n^2+2*x*n+1
0:     S(x,y)=n*x+y
10,11: S(x,n-2)=10*n^2+(2*x+1)*n-2
30,31,32,33: S(x,n-1)=30*n^2+(19*x+4)*n/5-1
95:    S(n-2,0)=(479*n^2-33*n+1)/5
35:    S(n-2,1)=36*n^2-3*n+1
15,16: S(n-2,y)=16*n^2+(y-2)*n+y
27:    S(n-2,n-2)=28*n^2-5*n-2
99:    S(n-2,n-1)=(499*n^2-29*n)/5-1
90:    S(n-1,0)=(453*n^2-9*n+1)/5
85:    S(n-1,1)=(429*n^2+4)/5+2*n
45,46,47,48: S(n-1,y)=(229*n^2+4*y)/5+(3*y-1)*n
109:   S(n-1,n-2)=(549*n^2-26*n-8)/5
104:   S(n-1,n-1)=(523*n^2-21*n-4)/5

Notice that for different lines we see different integers in the front
line, the only exception is for S(0,1) and S(n-2,1), but we can easily
verify that these will give different numbers for our large n.
Hence we need to check only that on each line there is no collision, this
is trivial if it contains only one number. If it contains more than one
number then for the inner square we have seen this (for S[x,y]).
For other line, say for example S[1,y]=2*n^2+(y+1)*n+y
the values are close to an arithmetic progression, where the progression's
difference is n+1>18, larger than the twice of the error=2*9=18, giving
that this line will contain increasing numbers, so here there is no
duplicate number.