RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2024 Issue 17, Pages 34–37 (Mi pdma638)

Discrete Functions

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

N. A. Kolomeets

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: 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.

Keywords: affine subspaces, invariant subspaces, permutations, asymptotic bounds.

UDC: 519.7

DOI: 10.17223/2226308X/17/8



© Steklov Math. Inst. of RAS, 2024