On the number of functions that break subspaces of dimension $3$ and higher

N. A. Kolomeets

Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 34-37

Résumé

We consider the sets $\mathcal{P}_{n}^{k}$ consisting of invertible functions $F: \mathbb{F}_2^{n} \to \mathbb{F}_2^{n}$ such that any $U \subseteq \mathbb{F}_2^{n}$ and its image $F(U)$ are not simultaneously $k$-dimensional affine subspaces of $\mathbb{F}_2^{n}$, where $3 \leq k \leq n - 1$. We present lower bounds for the cardinalities of all such $\mathcal{P}_{n}^{k}$ and $\mathcal{P}_{n}^{k} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that improve the result of W. E. Clark et al., 2007 providing that these sets are not empty. We prove that almost all permutations of $\mathbb{F}_2^{n}$ belong to $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$. Asymptotic lower and upper bounds of $|\mathcal{P}_{n}^{3}|$ and $|\mathcal{P}_{n}^{3} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}|$ up to $o(2^n!)$ are obtained as well. The number of functions from $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that map exactly one $3$-dimensional affine subspace of $\mathbb{F}_2^{n}$ to an affine subspace is estimated.

Détail

Keywords: affine subspaces, invariant subspaces, asymptotic bounds.
Mots-clés : permutations