## Variations on Cantor's celebrated diagonal argument

### Srečko Brlek (UQAM)

Abstract: Given a square $n \times n$ tableau $T=\left(a_i^j\right)$ on a finite alphabet $A$, let $L$ be the set of its row-words. The permanent $\Perm(T)$ is the set of words $a_{\pi(1)}^1a_{\pi(2)}^2\cdots a_{\pi(n)}^n$, where $\pi$ runs through the set of permutations of $n$ elements. Cantorian tableaux are those for which $\Perm(T)\cap L=\emptyset.$ Let $s=s(n)$ be the cardinality of $A$. We show in particular that for large $n$, if $s(n) <(1-\epsilon) n/\log n$ then most of the tableaux are non-Cantorian, whereas if $s(n) >(1+\epsilon) n/\log n$ then most of the tableaux are Cantorian. We conclude our article by the study of infinite tableaux. Consider for example the infinite tableaux whose rows are the binary expansions of the real algebraic numbers in the unit interval. We show that the permanent of this tableau contains exactly the set of binary expansions of all the transcendental numbers in the unit interval.

Algebraic Combinatorics Seminar home