A269745 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.

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

Offset

1,2

Comments

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.

Links

Table of n, a(n) for n=1..14.

Example

n, a(n), example of optimal S:
1, 1, [1]
2, 3, [1, 2]
3, 6, [1, 3, 4]
4, 10, [1, 2, 4, 5]
5, 14, [2, 3, 5, 6]
6, 18, [3, 4, 6, 7]
7, 23, [1, 5, 7, 8, 10]
8, 29, [1, 2, 7, 8, 10, 11]
9, 36, [1, 3, 4, 9, 10, 12, 13]
10, 44, [1, 2, 4, 5, 10, 11, 13, 14]
11, 52, [2, 3, 5, 6, 11, 12, 14, 15]
12, 60, [3, 4, 6, 7, 12, 13, 15, 16]
13, 68, [4, 5, 7, 8, 13, 14, 16, 17]
14, 76, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix
11000
01100
10110
11011
01101
and the value a(5) = 14.

Crossrefs

This is a lower bound on A227133.

See A269746 for the analogous sequence for a triangular grid.

Cf. A003002.

Sequence in context: A145913 A130246 A167381 * A310065 A310066 A310067

Adjacent sequences: A269742 A269743 A269744 * A269746 A269747 A269748

Keyword

nonn,more

Author

Warren D. Smith and N. J. A. Sloane, Mar 19 2016

Extensions

a(14) from N. J. A. Sloane, May 05 2016

Status

approved