# Integer sets without singular matrices

Let’s say that a set $A\subset \mathbb N$ contains an $n\times n$ singular matrix if there exists an $n\times n$ matrix with determinant zero whose entries are distinct elements of $A$. For example, the set of prime numbers does not contain any $2\times 2$ singular matrices; however, for every $n\ge 3$ it contains infinitely many $n\times n$ singular matrices.

I don’t know of an elementary proof of the latter fact. By a 1939 theorem of van der Corput, the set of primes contains infinitely many progressions of length 3. (Much more recently, Green and Tao replaced 3 with an arbitrary $k$.) If every row of a matrix begins with a 3-term arithmetic progression, the matrix is singular.

In the opposite direction, one may want to see an example of an infinite set $A\subset \mathbb N$ that contains no singular matrices of any size. Here is one:

Let $\displaystyle A=\lbrace 2^{2^k}\colon k=0,1,2,3,\dots\rbrace$: these numbers are 1 less than Fermat’s should-have-been-primes. Suppose that an $n\times n$ matrix is filled with distinct elements of $A$. Then
$\displaystyle \det A = \sum_{\sigma\in S_n} \mathrm{sign}\,(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}$ where each product over $i$ is a power of 2. Moreover, these powers of 2 are distinct by the uniqueness of binary representation of integers. It follows that the sum over $\sigma$ is nonzero — again, by the uniqueness of binary representation.

This set is very sparse, because the sequence $2^{2^k}$ grows super-exponentially. Is there such an example with exponential growth? or even with polynomial growth?

Disclaimer: This being a weekend blog post (and not a research proposal), I did not study the literature.

Credit: Once again, to Colin Carroll for “Prime Matrices I,II”.