login
Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.
2

%I #19 May 05 2016 18:06:36

%S 1,3,6,10,14,18,23,29,36,44,52,60,68,76

%N Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.

%C Label the entries in the left edge and top row (reading from the bottom left to the top right) with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where the matrix contains 1's. Then the matrix has the no-subsquare property iff S contains no three-term arithmetic progression.

%e n, a(n), example of optimal S:

%e 1, 1, [1]

%e 2, 3, [1, 2]

%e 3, 6, [1, 3, 4]

%e 4, 10, [1, 2, 4, 5]

%e 5, 14, [2, 3, 5, 6]

%e 6, 18, [3, 4, 6, 7]

%e 7, 23, [1, 5, 7, 8, 10]

%e 8, 29, [1, 2, 7, 8, 10, 11]

%e 9, 36, [1, 3, 4, 9, 10, 12, 13]

%e 10, 44, [1, 2, 4, 5, 10, 11, 13, 14]

%e 11, 52, [2, 3, 5, 6, 11, 12, 14, 15]

%e 12, 60, [3, 4, 6, 7, 12, 13, 15, 16]

%e 13, 68, [4, 5, 7, 8, 13, 14, 16, 17]

%e 14, 76, [5, 6, 8, 9, 14, 15, 17, 18]

%e ...

%e For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix

%e 11000

%e 01100

%e 10110

%e 11011

%e 01101

%e and the value a(5) = 14.

%Y This is a lower bound on A227133.

%Y See A269746 for the analogous sequence for a triangular grid.

%Y Cf. A003002.

%K nonn,more

%O 1,2

%A _Warren D. Smith_ and _N. J. A. Sloane_, Mar 19 2016

%E a(14) from _N. J. A. Sloane_, May 05 2016