Does the likelihood of these tables exist?

Question

Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.

Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the tagline "Almost all finite algebras are finitely based". After a series of restrictions and reductions, the proof of the result involves showing that a table (finite algebra with one binary operation; think of the operation as represented by an $n \times n$ matrix or table with rows and columns indexed by the same set from which table entries are taken) may generate a variety whose equational theory has an equivalent finite set of equations, only if this table does not belong to one of eight classes of tables (or one of ten, in a rewrite by Bob Quackenbush; I do not know the location online or offline of the rewrite, sorry); then one shows for each class, the ratio of the number of tables on an $n$ element set in that class to the number of all binary operation tables on that set goes to zero, as $n$ grows large. Rather than talk about a probability, I use the term likelihood to talk about (the limiting ratio as $n$ grows over the number of all $n \times n$ tables of the number of $n \times n$ tables with) a property of tables. For certain kinds of properties, one can show the limit as $n$ grows large of the ratio exists.

One of the properties used was a notion of deficiency. If a table on $n$ elements has the property that there is a subset of $k$ elements such that the set of $k^2$ products has at most $k$ elements, then we call that table $k$-deficient. If a table is $k$-deficient for any value of $k$ ranging from $3$ up to $n-1$, we call the table deficient. Every table on $n$ elements is clearly $n$-deficient as well as $0$-deficient and $1$-deficient, so excluding those values of k makes sense. But why exclude $k=2$?

Well, the likelihood of deficient tables (excluding $k=2$) goes to zero as $n$ gets large. Roughly, expecting a $k \times k$ array from an $n \times n$ table to have $k$ or fewer distinct values gets pretty rare as $n$ grows, and one can use union bounds and other simple techniques to show the likelihood (meaning limit of ratio) is zero. With more care, one can show the likelihood is of order $n^{-6}$, which is what one gets from the $k=3$ case.

However, there is a positive number $\epsilon$ so that the ratio for $2$-deficient tables always stays above $\epsilon$ for every $n$. So this line of proof would not go through if $2$-deficient tables had to be part of the property of deficient tables.

There is a formula for the number of $2$-deficient tables on an $n$-element set. Take all possible $n$-tuples of $n$ elements, and consider this as the diagonal of the table. For each distinct pair of coordinates from the tuple, if the values at the two coordinates are equal use a weight of $(n-1)(n-2)$, otherwise use a weight of $(n-2)(n+2)$. Multiply all these weights together for a given tuple to give a product $P$. Sum over all tuples the value $P$ for each tuple, and the resulting sum $S$ counts those tables that are not $2$-deficient. I can show that ratio $S/(n^{n^2})$ stays away from $1$ as $n$ grows. I also have a positive lower bound for this which involves $e^{-3/2}$, and computer calculations from another millennium suggest the ratio is eventually monotonic in $n$.

So first question: is the ratio involving $S$ actually monotonic in $n$ for all $n \gt 5$. If so, it would positively answer the second question which is in the title, which is does the limiting value exist? Finally, if it does exist, what is the actual value? (If you prove to me the value for tables that are not $2$-deficient, I can derive the value for tables that are $2$-deficient.)

Gerhard "It Is Time To Share" Paseman, 2019.01.04.

Answer 1

I have not yet found my original write-up, so I tried recreating it. I remember one bound was straightforward and the other used AM-GM. When I do it now, I get a value of $e^{-2}$ for both. Let me see if it holds up when I post it. (Oops, it didn't. I'll post it, even though this does not answer the question. Treat this as a spoiler anyway.)

This value of $e^{-2}$ is for the complement of 2-deficient tables which (modulo a bit of summing) is easy to determine. To expand upon the enumeration in the question, for each given diagonal of a table, we will count the number of tables which both contain that diagonal and are not 2-deficient. This means that for every pair of distinct entries from the diagonal, either those two values are different (and so the two associated cross-diagonal entries need to contain a third element, which is $n^2-4$ out of $n^2$ possible), or the two values are the same (and now the two other entries need to be distinct from each other and from the diagonal, meaning $(n-1)(n-2)$ choices). Representing the number of like pairs for a given diagonal by $a$ (so $a$ can range from 0 up to as high as $b=\binom{n}{2}$), we get the number of tables with that diagonal that have no 2-element subtable with two or fewer values is $(n^2-4)^b((n-1)/(n+2))^a$, out of a total of $n^{2b}$ many tables with that diagonal.

So for a given diagonal (with number of like pairs represented by $a$), the fraction of tables that are not 2-deficient is some number at most $e^{-2}$ and at least a tiny amount greater than 0. The $e^{-2}$ comes from upper bounding $(1 -4/n^2)^b$ and noting $4b/n^2$ approaches $2$ as $n$ grows, and this represents an upper bound (so a lower bound of $1-e^{-2}$ for the likelihood of 2-deficient tables).

To improve on the lower bound of 0 (actually, $(n-1)/(n+2)^a $ is comparable in size to $e^{-3n/2}$, but this is still too small) we will try the arithmetic mean geometric mean inequality. After all, the only diagonals where $a=b$ are the $n$ many diagonals with a constant value one of the elements of the underlying set, while there are $n!$ many diagonals with $a=0$, so the small values of $a$ should "win out". So instead of looking at the arithmetic average of the sum of $n^n$ terms of the form $((n^2-4)/n^2)^b((n-1)/(n+2))^a$, we look at the geometric mean of the product. Pulling out the $b$th power common to all of the terms, this means looking at $((n-1)/(n+2))^m$, where $m$ is the average of the sum over all diagonals of the $a$ values for each diagonal.

However, the sum of the $a$'s over all diagonals is easily computed: for each pair of coordinates, $1/n$ of the $n^n$ possibilities are given by like coordinates, so the sum of the $a$'s is $(bn^n)/n$, so $m=b/n=(n-1)/2$. So the geometric mean is close to $e^{-2}$ times $(1 - 3/(n+2))^{(n-1)/2}$ which is close to $e^{-7/2}$. So a lower bound for this implies an upper bound for the likelihood of 2-deficient tables of $1 - e^{-7/2}$.

Gerhard "Still Some Wiggle Room Left" Paseman, 2019.01.06.