A d-dimensional permutation of order n is an n-by-n-by

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Fix an integer $d\geq1$ and write $[n]=\{1,\ldots,n\}$. A $d$-dimensional permutation of order $n$ is a function $A:[n]^{d+1}\to\{0,1\}$ such that for each $k\in\{1,\ldots,d+1\}$ and each fixed choice of the other $d$ coordinates, \[\sum_{t=1}^n A(j_1,\ldots,j_{k-1},t,j_{k+1},\ldots,j_{d+1})=1.\] Let $P(n,d)$ count these arrays, so $P(n,1)=n!$ and $P(n,2)$ counts Latin squares of order $n$. The original source establishes an upper bound with the asymptotic scale below.

Statement recorded in the supplied source.

For every fixed $d\geq1$, does the matching lower bound hold as $n\to\infty$, and hence \[P(n,d)=\left((1+o(1))\frac{n}{e^d}\right)^{n^d}?\] Equivalently, is $\log P(n,d)=n^d(\log n-d+o(1))$ for each fixed $d$? [S2]

Short English statement

Does the number of fixed-dimensional permutation arrays have the asymptotic size predicted by the Linial--Luria upper bound?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3100037 (AMR-030-0037). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Nathan Linial and Zur Luria, An Upper Bound on the Number of High-dimensional Permutations (2012), Definition 1.2, Conjecture 1.3 and Theorem 1.4, pp. 2--4. https://arxiv.org/abs/1106.0649.