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, 85, 94, 103, 114, 125

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

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.

Prog

(Python)
from itertools import product
from scipy.linalg import toeplitz
import numpy as np
def A269745(n):
    count = 0
    for p in product([0, 1], repeat=2*n-1):
        m = toeplitz(p[:n], p[n-1:])
        for r, c in zip(*np.nonzero(m)):
            for j in range(c+1, min(n, n-r+c)):
                if m[r, j] and m[r+j-c, c] and m[r+j-c, j]:
                    break
            else:
                continue
            break
        else:
            count = max(count, np.count_nonzero(m))
    return count # Chai Wah Wu, Dec 07 2025
(Python)
from itertools import product, combinations
def A269745(n):
    c = 0
    for p in product([0, 1], repeat=2*n-1):
        a = sum((i+1 if i<n else 2*n-1-i)*p[i] for i in range(2*n-1))
        if a>c:
            m = {k for k, d in enumerate(p, 1) if d}
            for i, j in combinations(m, 2):
                if i+j&1^1 and i+j>>1 in m:
                    break
            else:
                c = a
    return c # Chai Wah Wu, Dec 10 2025

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 * A380548 A310065 A310066

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

a(15) from Chai Wah Wu, Dec 08 2025

a(16)-a(18) from Chai Wah Wu, Dec 10 2025

a(19) from Chai Wah Wu, Dec 28 2025

Status

approved