# Variations on the Choi-Jamiołkowski isomorphism

Markus Frembs<EMAIL_ADDRESS>Eric G. Cavalcanti
<EMAIL_ADDRESS>Centre for Quantum Dynamics, Griffith University,
Yugambeh Country, Gold Coast, QLD 4222, Australia

###### Abstract

We address various aspects of a widely used tool in quantum information
theory: the Choi-Jamiołkowski isomorphism [A. Jamiołkowski, Rep. Math. Phys.,
3, 275 (1972)]. We review different versions of the isomorphism, their
properties and propose a unified description that combines them all. To this
end, we identify the physical reason for the appearance of the (basis-
dependent) operation of transposition in the isomorphism as used in Choi’s
theorem [M.-D. Choi, Lin. Alg. Appl., 10, 285 (1975)]. This requires a careful
distinction between Jordan algebras and the different $C^{*}$-algebras they
arise from, which are distinguished by their order of composition.

Physically, the latter encodes a choice of time orientation in the respective
algebras, which relates to a number of recent results, including a
characterisation of quantum from more general non-signalling bipartite
correlations [M. Frembs and A. Döring, arXiv:2204.11471] and a classification
of bipartite entanglement [M. Frembs, arXiv:2207.00024].

##  I Choi and Jamiołkowski - two isomorphisms, two theorems

Let $\mathcal{L}(\mathcal{H}_{A})=M_{n}(\mathbb{C})$ and
$\mathcal{L}(\mathcal{H}_{B})=M_{m}(\mathbb{C})$ be two finite-dimensional
matrix algebras over the complex numbers. The _Choi-Jamiołkowski isomorphism_
Jamiolkowski1972 ; Choi1975  refers to an identification of linear operators
in the tensor product algebra
${\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}\cong\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
and linear maps
$\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B}):=\\{\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}\mid\phi\text{\
linear}\\}$ between these algebras. This identification is not unique, a
number of different versions exist, each with different properties. This
section contains a brief review of the most common versions of the
isomorphism.

The main part of this paper is Sec. II, where we highlight the physical
significance of the (relative) operator ordering between algebras
${\mathcal{L}(\mathcal{H}_{A})}$ and ${\mathcal{L}(\mathcal{H}_{B})}$ in the
Choi-Jamiołkowski isomorphism (Sec. II.1), give a reformulation of Choi’s
theorem that makes explicit the dependence on the choice of (relative)
operator ordering (Thm. 6 in Sec. II.2), and based on that propose a unified
version of the Choi-Jamiołkowski isomorphism (Sec. II.3).

###  I.1 Jamiołkowski’s isomorphism and theorem

Ref. Jamiolkowski1972  defines a linear isomorphism
$J:\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})\rightarrow\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
by

$\displaystyle\begin{split}\rho^{J}_{\phi}=J(\phi)&:=\sum_{k}e_{k}^{*}\otimes\phi(e_{k})\;,\\\
J^{-1}(\rho)(a)&:=\mathrm{tr}_{\mathcal{H}_{A}}[\rho(a\otimes\mathbbm{1}_{B})]\;,\end{split}$
(1)

for all $a\in{\mathcal{L}(\mathcal{H}_{A})}$, where
$\\{e_{k}\\}_{k}\in\mathrm{ONB}({\mathcal{L}(\mathcal{H}_{A})})$ is any
orthonormal basis in ${\mathcal{L}(\mathcal{H}_{A})}$ with respect to the
Hilbert-Schmidt inner product (see Eq. (10) below).111Following notation in
Ref. Jamiolkowski1972  and related work FrembsDoering2019b ;
FrembsDoering2022a ; FrembsDoering2022b ; Frembs2022a , we use $*$ instead of
$\dagger$ for the (Hermitian) adjoint. In particular, $J$ is _basis-
independent_ : let
$\\{f_{l}\\}_{l}\in\mathrm{ONB}({\mathcal{L}(\mathcal{H}_{A})})$ be another
orthonormal basis in ${\mathcal{L}(\mathcal{H}_{A})}$, then222Here,
$\sum_{l}f_{l}f^{*}_{l}$ and $\sum_{k}e_{k}e^{*}_{k}$ are resolutions of the
identity in the inner product space ${\mathcal{L}(\mathcal{H}_{A})}$; in
particular, note that Eq. (2) involves no matrix multiplication.

$\displaystyle\begin{split}\rho^{J}_{\phi}=\sum_{k}e_{k}^{*}\otimes\phi(e_{k})&=\sum_{k}\big{(}(\sum_{l}f_{l}f_{l}^{*})e_{k}\big{)}^{*}\otimes\phi(e_{k})\\\
&=\sum_{k}\sum_{l}\overline{(e_{k},f_{l})}_{\mathcal{L}(\mathcal{H}_{A})}f_{l}^{*}\otimes\phi(e_{k})\\\
&=\sum_{k}\sum_{l}f_{l}^{*}\otimes(f_{l},e_{k})_{\mathcal{L}(\mathcal{H}_{A})}\phi(e_{k})\\\
&=\sum_{l}f_{l}^{*}\otimes\phi\big{(}(\sum_{k}e_{k}e_{k}^{*})f_{l}\big{)}=\sum_{l}f_{l}^{*}\otimes\phi(f_{l})\;.\end{split}$
(2)

Moreover, the following theorems hold for $J$.

######  Theorem 1 (de Pillis dePillis1967 ).

Let $\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})$. Then $\phi$ is
Hermiticity-preserving, that is,
${}^{*}\phi(a):=(*\circ\phi)(a)=(\phi\circ*)(a)=:\phi^{*}(a)$ for all
$a\in{\mathcal{L}(\mathcal{H}_{A})}$, if and only if $J(\phi)$ is Hermitian.

######  Theorem 2 (Jamiołkowski Jamiolkowski1972 ).

Let $\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})$.

  1. (a)

$\phi$ is positive if and only if $J(\phi)$ is _positive on pure tensors
(POPT)_ _(_ or _block positive, cf.PaulsenShultz2013 ; Kye2022 )_, that is,
$\mathrm{tr}[J(\phi)(a\otimes b)]\geq 0$ for all
$a\in{\mathcal{L}(\mathcal{H}_{A})}_{+}$,
$b\in{\mathcal{L}(\mathcal{H}_{B})}_{+}$.

  2. (b)

Let further ${}^{*}\phi=\phi^{*}$. Then $\phi$ is trace-preserving if and only
if $\mathrm{tr}_{\mathcal{H}_{B}}[J(\phi)]=\mathbbm{1}_{A}$.

###  I.2 Choi’s isomorphism and theorem

The most commonly used version of the Choi-Jamiołkowski isomorphism is
motivated by a theorem due to Choi Choi1975  (Thm. 3), who defines a map
$C:\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})\rightarrow\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
by

$\displaystyle\begin{split}\rho^{C}_{\phi}=C(\phi)&:=\sum_{ij}|i\rangle\langle
j|\otimes\phi(|i\rangle\langle j|)\;,\\\
C^{-1}(\rho)(a)&:=\mathrm{tr}_{\mathcal{H}_{A}}[\rho(a^{T}\otimes\mathbbm{1}_{B})]\;,\end{split}$
(3)

for all $a\in{\mathcal{L}(\mathcal{H}_{A})}$, where $\\{|i\rangle\langle
j|\\}_{ij}$ denotes the orthonormal basis in ${\mathcal{L}(\mathcal{H}_{A})}$
built from an orthonormal basis
$\\{|i\rangle\\}_{i}\in\mathrm{ONB}(\mathcal{H}_{A})$, and $T$ denotes
transposition in that basis.333This is sometimes written
$\rho^{C}_{\phi}:=(\mathrm{id}\otimes\phi)(|\Phi\rangle\langle\Phi|)$, where
$|\Phi\rangle=\sum_{i}|i\rangle\otimes|i\rangle$ is an (unnormalised)
maximally entangled state. Note that if $\phi$ is trace-preserving, then
$\mathrm{tr}[\rho^{C}_{\phi}]=\mathrm{tr}[\rho^{J}_{\phi}]=d_{A}$ (cf. Thm.
2). Unlike Eq. (1), Eq. (3) depends on the choice of basis, in particular,
note that transposition (in $C^{-1}$) is a basis-dependent operation.444We
emphasise that basis-dependence refers to the operator basis
$\\{|i\rangle\langle
j|\\}_{ij}\in\mathrm{ONB}({\mathcal{L}(\mathcal{H}_{A})})$, not the basis
$\\{|i\rangle\\}_{i}\in\mathrm{ONB}(\mathcal{H}_{A})$. Necessary and
sufficient conditions for the validity of Choi’s theorem (Thm. 3) with respect
to different choices of bases
$\\{e_{i}\\}_{i}\in\mathrm{ONB}({\mathcal{L}(\mathcal{H}_{A})})$ are analysed
in Ref. PaulsenShultz2013 ; Kye2022 . Nevertheless, as a special case of
Stinespring’s theorem Stinespring1955 , Choi’s theorem yields the following
useful characterisation of completely positive maps.

######  Theorem 3 (Choi Choi1975 ).

Let $\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})$. Then $\phi$ is
completely positive (CP) if and only if $\rho^{C}_{\phi}$ is positive. That
is, $C$ restricts to a map
$C|_{\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{CP}}}:\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{CP}}\rightarrow\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})_{+}$.

###  I.3 A basis-independent variant of the Choi-Jamiołkowski isomorphism

The basis dependence in Eq. (3) is unappealing and has prompted alternative
definitions of the Choi-Jamiołkowski isomorphism. Of course, one can just
resort to Eq. (1), yet Thm. 3 does not hold in this case: given a completely
positive map $\phi$, $\rho^{J}_{\phi}$ is generally not positive (cf. Ref.
LeiferSpekkens2013 ; PaulsenShultz2013 ; Kye2022 ). A formal trick to bypass
this issue has been suggested in Refs. AllenEtAl2017 ;
BarrettLorenzOreshkov2020  (see also Ref. Ozawa2014 ), which define a map
${JC}:\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})\rightarrow\mathcal{L}(\mathcal{H}^{*}_{A}\otimes\mathcal{H}_{B})$
by555Ref. AllenEtAl2017  defines
$a_{A^{*}}:=\mathrm{tr}_{\mathcal{H}_{A}}[\tau^{\mathrm{id}}_{A}a]$ for
$\tau^{\mathrm{id}}_{A}:=\sum_{ij}|i\rangle_{A^{*}}\langle
j|\otimes|i\rangle_{A}\langle j|$; hence, $(a_{A})_{mn}=(a_{A^{*}})_{nm}$ as
matrices. In this way, the transposition in Eq. (3) is absorbed into the
mapping between $\mathcal{H}_{A}$ and its dual $\mathcal{H}^{*}_{A}$.

$\displaystyle\begin{split}\rho^{{JC}}_{\phi}={JC}(\phi)&:=\sum_{ij}|i\rangle_{A^{*}}\langle
j|\otimes\phi(|i\rangle\langle j|)\;,\\\
{JC}^{-1}(\rho)(a)&:=\mathrm{tr}_{\mathcal{H}^{*}_{A}}[\rho(a_{A^{*}}\otimes\mathbbm{1}_{B})]\;,\quad
a_{A^{*}}:=a^{T}\quad\quad\forall
a\in{\mathcal{L}(\mathcal{H}_{A})}\;.\end{split}$ (4)

Here, $\\{|i\rangle_{A^{*}}\in\mathcal{H}^{*}_{A}\\}_{i}$ corresponds to the
dual basis of $\\{|i\rangle_{A}\in\mathcal{H}_{A}\\}_{i}$,666Recall that the
dual basis $\\{\langle j|_{A}\\}_{j}$ of $\\{|i\rangle_{A}\\}_{i}$ is uniquely
defined by the condition $\langle j|i\rangle_{A}=\delta_{ij}$. yet the
elements $|i\rangle_{A*}$ are thought of as vectors (rather than dual vectors)
such that $\langle j|i\rangle_{A^{*}}=\langle i|j\rangle_{A}=\overline{\langle
j|i\rangle}_{A}$, and thus

$\displaystyle\begin{split}\mathrm{tr}_{\mathcal{H}^{*}_{A}}[\rho^{{JC}}_{\phi}(a_{A^{*}}\otimes\mathbbm{1}_{B})]&=\mathrm{tr}_{\mathcal{H}^{*}_{A}}[(\sum_{ij}|i\rangle_{A^{*}}\langle
j|\otimes\phi(|i\rangle\langle j|))(\sum_{mn}|m\rangle(a_{A^{*}})_{mn}\langle
n|\otimes\mathbbm{1}_{B})]\\\ &=\sum_{ijkmn}\langle k|i\rangle_{A^{*}}\langle
j|m\rangle_{A^{*}}(a_{A^{*}})_{mn}\langle n|k\rangle_{A^{*}}\
\phi(|i\rangle\langle j|)\\\ &=\sum_{ijkmn}\langle
k|n\rangle_{A}(a_{A})_{nm}\langle m|j\rangle_{A}\langle i|k\rangle_{A}\
\phi(|i\rangle\langle j|)\\\
&=\mathrm{tr}_{\mathcal{H}_{A}}[(\sum_{ij}|j\rangle\langle
i|\otimes\phi(|i\rangle\langle j|))(\sum_{mn}|m\rangle a_{mn}\langle
n|\otimes\mathbbm{1}_{B})]=\mathrm{tr}_{\mathcal{H}_{A}}[\rho^{J}_{\phi}(a\otimes\mathbbm{1}_{B})]\;.\end{split}$

Consequently, Eq. (4) is basis-independent by Eq. (2), and by comparison with
Eq. (3), ${JC}$ restricts to a map from completely positive maps $\phi$ to
positive matrices
$\rho^{{JC}}_{\phi}\in\mathcal{L}(\mathcal{H}^{*}_{A}\otimes\mathcal{H}_{B})_{+}$.

Nevertheless, a core feature remains hidden in the details (cf. Araujo_CJI ).
In the next section, we explicitly identify the physical significance of the
transposition in Eq. (3) with the choice of operator ordering in
${\mathcal{L}(\mathcal{H}_{A})}$ and ${\mathcal{L}(\mathcal{H}_{B})}$, which
suggests a unified version of the Choi-Jamiołkowski isomorphism that retains
Thm. 1, Thm. 2, Thm. 3, and recovers Eq. (4).

##  II A unified version of the Choi-Jamiołkowski isomorphism

###  II.1 Background - Jordan algebras, complex structure and inner product

At the heart of the the different versions and properties of the Choi-
Jamiołkowski isomorphism lies the subtle distinction between Jordan and
$C^{*}$-algebras. We will only need the bare essentials here, and liberally
refer to Ref. Hanche-OlsenStormer1984JordanOA ; AlfsenShultz1998a ;
AlfsenShultz1998b  for many more details.

Jordan algebras. The operator product on ${\mathcal{L}(\mathcal{H})}$ admits
the decomposition,

$ab=\frac{1}{2}\\{a,b\\}-\frac{1}{2}[a,b]\;,$ (5)

where $[a,b]=ab-ba$ denotes the commutator and $\\{a,b\\}:=ab+ba$ denotes the
anti-commutator. $({\mathcal{L}(\mathcal{H})},[\cdot,\cdot])$ defines a Lie
algebra while
${\mathcal{J}(\mathcal{H})}:=({\mathcal{L}(\mathcal{H})},\\{\cdot,\cdot\\})$
defines a Jordan algebra.777A Jordan algebra $(J,\circ)$ is commutative (but
generally non-associative) and satisfies the Jordan identity: $(a\circ
b)\circ(a\circ a)=a\circ(b\circ(a\circ a))$ for all $a,b\in J$. For a
classification of Jordan algebras, see Ref. JordanVNWigner1934 ; Hanche-
OlsenStormer1984JordanOA ; McCrimmon2004 .888Overloading notation slightly, we
write ${\mathcal{L}(\mathcal{H})}$ for the linear space and for the algebra of
operators on $\mathcal{H}$.  Importantly, already
${\mathcal{J}(\mathcal{H})}_{\mathrm{sa}}$ defines a real Jordan algebra, in
particular, the anti-commutator closes on self-adjoint (Hermitian)
elements—unlike the operator product in ${\mathcal{L}(\mathcal{H})}$. Indeed,
this was the original motivation to study Jordan algebras in Ref. Jordan1933 ;
JordanVNWigner1934 , viz. as generalisations of observable algebras in quantum
mechanics.

Not every real Jordan algebra $\mathcal{J}$ arises as a self-adjoint part
(closed under the anti-commutator) from a $C^{*}$-algebra $\mathcal{A}$, i.e.,
$\mathcal{J}\not\subseteq(\mathcal{A}_{\mathrm{sa}},\\{\cdot,\cdot\\})$ in
general.8 If it does, $\mathcal{J}$ is called _special_ , otherwise it is
called an _exceptional_ Jordan algebra. The key to identify special Jordan
algebras is the double role played by self-adjoint operators in
${\mathcal{L}(\mathcal{H})}$: as observables and as generators of symmetries
GrginPetersen1974 ; AlfsenShultz1998b .999Jordan algebras whose elements mimic
this dichotomy are characterised by the existence of a _dynamical
correspondence_ AlfsenShultz1998a ; AlfsenShultz1998b  (see also Ref. Baez2022
). In turn, for every dynamical correspondence on $\mathcal{J}$, there is an
associative $C^{*}$-algebra $\mathcal{A}$ from which $\mathcal{J}$ arises as a
self-adjoint part
$\mathcal{J}\subseteq(\mathcal{A}_{\mathrm{sa}},\\{\cdot,\cdot\\})$ (Thm. 23
in Ref. AlfsenShultz1998a ). In the case of
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$, there are exactly two such
associative products that extend the anti-commutator in
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$ (cf. AlfsenShultz1998a ),

$a\cdot_{+}b:=\frac{1}{2}\\{a,b\\}+\frac{1}{2}[a,b]=ab\quad\quad\quad
a\cdot_{-}b:=\frac{1}{2}\\{a,b\\}-\frac{1}{2}[a,b]=ba\;,$ (6)

for all $a,b\in{\mathcal{J}(\mathcal{H})}$. In other words,
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$ arises as the self-adjoint part of
both ${\mathcal{L}(\mathcal{H})}=({\mathcal{L}(\mathcal{H})},\cdot_{+})$ and
its opposite algebra
${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}=({\mathcal{L}(\mathcal{H})},\cdot_{-})$,
for which the order of composition is reversed with respect to
${\mathcal{L}(\mathcal{H})}$.8 Since transposition $T$ is an order-reversing
involution on ${\mathcal{L}(\mathcal{H})}$, it maps between
${\mathcal{L}(\mathcal{H})}$ and ${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}$.
We will see that the distinction between associative $C^{*}$-algebras
${\mathcal{L}(\mathcal{H})}$ and ${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}$
is at the heart of the different versions of the Choi-Jamiołkowski isomorphism
and in turn of Choi’s theorem (see Thm. 6 below). Before doing so, we briefly
expand on the physical meaning of this distinction.

Time orientations and complex structure. Note that the two (associative)
products in Eq. (6) are readily distinguished from one another by the sign in
front of the commutator. This sign obtains a physical interpretation as the
_direction of time_ as follows (cf. Ref. AlfsenShultz1998a ;
FrembsDoering2019b ; Doering2014 ; FrembsDoering2022a ; Frembs2022a ). When
described by ${\mathcal{L}(\mathcal{H})}$, the evolution of the system can be
expressed via the map

$\Psi(t,a)(b)=e^{ita}be^{-ta}\quad\quad\forall
a,b\in\mathcal{J}(\mathcal{H})_{\mathrm{sa}},t\in\mathbb{R}\;.$ (7)

Note that $\Psi$ describes unitary evolution in ${\mathcal{L}(\mathcal{H})}$
(as opposed to anti-unitary evolution Wigner_GruppentheorieUndQM ;
Bargmann1964 ). With Ref. FrembsDoering2022a ; FrembsDoering2019b ;
Frembs2022a , we therefore call it the _canonical time orientation on
${\mathcal{L}(\mathcal{H})}$_. The relation to the choice of sign in Eq. (5)
follows by differentiation: for all
$a\in\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$

$\displaystyle\frac{d}{dt}\big{|}_{t=0}\Psi(t,a)=i[a,\cdot]\;.$ (8)

This suggests a slight reformulation of the decomposition in Eq. (5) into

$\delta_{a}(b):=a\circ b-ia\star b\;,$ (9)

where $a\circ b:=\frac{1}{2}\\{a,b\\}$ and $a\star b:=\frac{i}{2}[a,b]$ for
all $a,b\in{\mathcal{J}(\mathcal{H})}$. Indeed, Eq. (9) describes the natural
decomposition of the _order derivation_ 101010An order derivation $\delta$ on
a Jordan algebra $\mathcal{J}$ is a bounded linear operator such that
$e^{t\delta}(b)\in\mathcal{J}_{+}$ for all $b\in\mathcal{J}_{+}$ and
$t\in\mathbb{R}$ AlfsenShultz1998a .
$\delta_{a}:{\mathcal{J}(\mathcal{H})}_{+}\rightarrow{\mathcal{J}(\mathcal{H})}_{+}$,
$a\in{\mathcal{J}(\mathcal{H})}$ given by
$\delta_{a}(x):=\frac{1}{2}(ax+xa^{*})=\delta_{a}(x)+\delta_{ia}(x)$, into a
_self-adjoint_ part $\delta_{a}$, $a\in\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$
and a _skew_ part $\delta_{ia}$, $a\in\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$
(Lm. 11 in Ref. AlfsenShultz1998a ).111111Note that while the operator product
in ${\mathcal{L}(\mathcal{H})}$ does not close on self-adjoint elements, since
the commutator of two Hermitian operators is skew-Hermitian, the product
$\star$ _does_ close on self-adjoint elements. Moreover, it turns out that
skew order derivations induce Jordan homomorphisms of the form
$\Psi(t,a)=e^{2t\delta_{ia}}$ (Lm. 9 and Lm. 14 in Ref. AlfsenShultz1998a ).

Importantly, Eq. (9) defines a complex structure on
${\mathcal{J}(\mathcal{H})}$—viewed as the space of order derivations on
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$ Connes1974 —and it follows with Eq.
(6) and Eq. (8) that such a complex structure promotes the Jordan algebra
${\mathcal{J}(\mathcal{H})}$ to the $C^{*}$-algebra
${\mathcal{L}(\mathcal{H})}$.121212A complex structure on the order
derivations of a Jordan algebra is also called a _Connes orientation_
Connes1974 . Furthermore, we find that under this identification the ‘complex
conjugation’ map
${\mathcal{L}(\mathcal{H})}=\mathcal{L}(\mathcal{H})_{\mathrm{sa}}+i\mathcal{L}(\mathcal{H})_{\mathrm{sa}}\leftrightarrow{\mathcal{L}(\mathcal{H})}^{*}:=\mathcal{L}(\mathcal{H})_{\mathrm{sa}}-i\mathcal{L}(\mathcal{H})_{\mathrm{sa}}$
is given by the Hermitian adjoint $*$ on ${\mathcal{L}(\mathcal{H})}$ (cf.
Prop. 15 in Ref. AlfsenShultz1998a ). Clearly, $*$ is an order-reversing
involution on ${\mathcal{L}(\mathcal{H})}$, and by comparing Eq. (5), Eq. (8)
and Eq. (9) it induces a change in time orientation on
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$.131313This central observation is at
the heart of Thm. 3 in Ref. FrembsDoering2022a  and Thm. 2 in Ref. Frembs2022a
. To emphasise the relation with (skew) order derivations and time
orientations, below we will use the Hermitian adjoint as order-reversing map
between $C^{*}$-algebras ${\mathcal{L}(\mathcal{H})}$ and
${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}\cong{\mathcal{L}(\mathcal{H})}^{*}$.

Inner product and Born rule. The Hilbert-Schmidt inner product on
${\mathcal{L}(\mathcal{H})}$,

$(a,b)_{{\mathcal{L}(\mathcal{H})}}:=\mathrm{tr}_{\mathcal{H}}[b^{*}a]\;,$
(10)

can be used to succinctly encode Eq. (1) as follows (cf. Jamiolkowski1972 ):
for all $a\in{\mathcal{L}(\mathcal{H}_{A})}$,
$b\in{\mathcal{L}(\mathcal{H}_{B})}$,

$(\rho^{J}_{\phi},a^{*}\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}=\mathrm{tr}_{\mathcal{H}_{A}\otimes\mathcal{H}_{B}}[\rho^{J}_{\phi}(a\otimes
b^{*})]=\mathrm{tr}_{\mathcal{H}_{B}}[\phi(a)b^{*}]=(\phi(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\;.$
(11)

Note that (for a single system) Eq. (10) is a property of
${\mathcal{J}(\mathcal{H})}$ only,

$(a,b)_{\mathcal{L}(\mathcal{H})}=\mathrm{tr}_{\mathcal{H}}[b^{*}a]=\frac{1}{2}\mathrm{tr}_{\mathcal{H}}[\\{b^{*},a\\}]\;,$
(12)

since $\mathrm{tr}[ab-ba]=0$ for all $a,b\in{\mathcal{L}(\mathcal{H})}$. The
Hilbert-Schmidt inner product therefore restricts to the (complexified) Jordan
algebra ${\mathcal{J}(\mathcal{H})}$. What is more, restricting to the real
part ${\mathcal{J}(\mathcal{H})}_{\mathrm{sa}}$, Eq. (12) is readily
identified with the Born rule of the system described by
$\mathcal{J}(\mathcal{H})_{\mathrm{sa}}$. In particular, note that we obtain
the same Born rule from the inner product on
${{{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}}$,

$(a,b)_{{{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}}:=\mathrm{tr}_{\mathcal{H}^{*}}[b\cdot_{-}a^{*}]=\frac{1}{2}\mathrm{tr}_{\mathcal{H}^{*}}[\\{b,a^{*}\\}]=(\mathrm{tr}_{\mathcal{H}}[b^{*}\cdot_{+}a])^{*}=\overline{(a,b)}_{\mathcal{L}(\mathcal{H})}\;.$
(13)

Together with Eq. (11) this suggest to study the Choi-Jamiołkowski isomorphism
under restriction to Jordan algebras.141414While we do not pursue this here,
we remark that this raises the question of defining a tensor product of
(special) Jordan algebras. This is naturally done in reference to their
ambient complex $C^{*}$-algebras Hanche-Olsen1983  (see also Ref.
GrginPetersen1976 ), which requires a choice of dynamical correspondence
AlfsenShultz1998a , equivalently time orientation in addition to the mere
Jordan algebra structure. Importantly, this choice is not arbitrary, i.e., the
Born rule of a composite quantum system _does_ depend on the relative choice
of $C^{*}$-algebras FrembsDoering2022a ; FrembsDoering2022b ; Frembs2022a . In
the next section, we will show that Thm. 1 and Thm. 2 obtain under the
restriction to Jordan algebras. In contrast, we will see that Thm. 3 _does_
depend on the choice of complex structure Connes1974  (equivalently, dynamical
correspondence AlfsenShultz1998a  or time orientation FrembsDoering2022a ;
Frembs2022a ) and thus on the choice of $C^{*}$-algebra
${\mathcal{L}(\mathcal{H})}$ or
${{{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}}$.

###  II.2 Hermiticity-preserving, positive, decomposable and completely
positive maps

In order to expose the significance of the choice of operator ordering on
${\mathcal{J}(\mathcal{H}_{A})}$ and ${\mathcal{J}(\mathcal{H}_{B})}$ in Thm.
1, Thm. 2 and Thm. 3, we study the (linear) isomorphism $J$ as defined in Eq.
(11) under the restriction to Jordan algebras for different types of maps
$\phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow{\mathcal{J}(\mathcal{H}_{B})}$.
Note that ${\mathcal{L}(\mathcal{H}_{A})}\cong{\mathcal{J}(\mathcal{H}_{A})}$
(${\mathcal{L}(\mathcal{H}_{A})_{\mathrm{sa}}}\cong{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}})$
as complex (real) linear spaces (similarly for
${\mathcal{L}(\mathcal{H}_{B})}$).

De Pillis’s theorem and Jamiołkowski’s theorem revisited. We start with
Hermiticity-preserving maps,
$\phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow{\mathcal{J}(\mathcal{H}_{B})}$
such that ${}^{*}\phi=*\circ\phi=\phi\circ*=\phi^{*}$. This is equivalent to
the condition that $\phi$ preserves the self-adjoint parts of
${\mathcal{J}(\mathcal{H}_{A})}$ and ${\mathcal{J}(\mathcal{H}_{B})}$, i.e.,
that $\phi$ restricts to a linear map
$\phi|_{{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}}:{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}\rightarrow{\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$.151515Conversely,
every linear map
$\phi:{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}\rightarrow{\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$
has a unique linear extension to the complexification
${\mathcal{J}(\mathcal{H}_{A})}:={\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}+i{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$,
given by $\phi(a+ib):=\phi(a)+i\phi(b)$. The same is true for Hermiticity-
preserving maps with additional structure (see Thm. 4 and Thm. 5).

It follows that the set of operators $\rho_{\phi}^{J}$ corresponding to
Hermiticity-preserving maps
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
under Eq. (1) is the same as the set of operators $\rho_{\phi}^{J}$
corresponding to linear maps
$\phi:{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}\rightarrow{\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$.
Thm. 1 thus applies to (complex) Jordan algebras:

######  Theorem 4 (de Pillis for Jordan algebras dePillis1967 ).

Let
$\phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow{\mathcal{J}(\mathcal{H}_{B})}$.
Then $\phi$ restricts to a map
$\phi|_{{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}}:{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}\rightarrow{\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$
if and only if $J(\phi)$ is Hermitian.

Next, recall that a map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is positive if and only if $\phi(a)\in{\mathcal{L}(\mathcal{H}_{B})}_{+}$
whenever $a\in{\mathcal{L}(\mathcal{H}_{A})}_{+}$, and that a positive
operator is in particular self-adjoint. Hence,
${\mathcal{L}(\mathcal{H}_{A})}_{+}\subset{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$
(as real linear spaces) such that the identification between operators
$\rho_{\phi}^{J}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ that
are positive on pure tensors and positive maps
$\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{+}$ also holds on the
level of Jordan algebras:

######  Theorem 5 (Jamiołkowski for Jordan algebras Jamiolkowski1972 ).

Let
$\phi:{\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}\rightarrow{\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$.

  1. (a)

$\phi$ is positive if and only if $J(\phi)$ is positive on pure tensors
(POPT).

  2. (b)

Let further ${}^{*}\phi=\phi^{*}$. Then $\phi$ is trace-preserving if and only
if $\mathrm{tr}_{\mathcal{H}_{B}}[J(\phi)]=\mathbbm{1}_{A}$.

Decomposable and completely positve maps. We can study the isomorphism under
the restriction to Jordan algebras for maps with even more structure. Recall
that a Jordan $*$-homomorphism
$\Phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow{\mathcal{J}(\mathcal{H}_{B})}$
is a map such that ${}^{*}\Phi=*\circ\Phi=\Phi\circ*=\Phi^{*}$, and which
preserves the anti-commutator in the respective algebras, i.e.,
$\Phi(\\{a,a^{\prime}\\})=\\{\Phi(a),\Phi(a^{\prime})\\}$ for all
$a,a^{\prime}\in{\mathcal{J}(\mathcal{H}_{A})}$. More generally, a map
$\phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow{\mathcal{J}(\mathcal{H}_{B})}$
is called decomposable, denoted by
$\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{D}}$, if it is
of the form $\phi=v^{*}\Phi v$, where
$v:\mathcal{H}_{B}\rightarrow\mathcal{K}$ is linear and
$\Phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow\mathcal{J}(\mathcal{K})$ is a
Jordan $*$-homomorphism Stormer1982 . Since decomposable maps are by
definition maps between Jordan algebras, we can define the corresponding set
of operators $\rho_{\phi}^{J}$ (under $J$ in Eq. (1)), denoted by
$\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})_{\mathrm{D}}$.

What about completely positive (CP) maps? Can we capture the set of CP maps
(and thus the set of operators under Eq. (3)) by studying their restriction to
real Jordan algebras? This is not the case! To see this, it is helpful to
consider the classification of completely positive maps due to Stinespring
Stinespring1955 : every completely positive map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is of the form $\phi=v^{*}\Phi v$, where
$v:\mathcal{H}_{B}\rightarrow\mathcal{K}$ is linear and
$\Phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow\mathcal{L}(\mathcal{K})$ is a
$C^{*}$-algebra homomorphism, i.e., ${}^{*}\Phi=\Phi^{*}$ and
$\Phi(aa^{\prime})=\Phi(a)\Phi(a^{\prime})$ for all
$a,a^{\prime}\in{\mathcal{L}(\mathcal{H}_{A})}$.

Of course, every $C^{*}$-algebra homomorphism restricts to a Jordan
$*$-homomorphism
$\Phi|_{{\mathcal{J}(\mathcal{H}_{A})}}:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow\mathcal{J}(\mathcal{K})$,
however, the converse is generally not true: a Jordan $*$-homomorphism
$\Phi:{\mathcal{J}(\mathcal{H}_{A})}\rightarrow\mathcal{J}(\mathcal{K})$ only
preserves commutators up to sign AlfsenShultz1998a . More precisely, either
$\Phi(aa^{\prime})=\Phi(a)\Phi(a^{\prime})$ or
$\Phi(aa^{\prime})=\Phi(a^{\prime})\Phi(a)$, equivalently either
$\Phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow\mathcal{L}(\mathcal{K})$ or
$\Phi:{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}\rightarrow\mathcal{L}(\mathcal{K})$
is a $C^{*}$-algebra homomorphism Kadison1951 .

Recall (from Eq. (6)) that both ${\mathcal{L}(\mathcal{H}_{A})}$ and
${\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}$ reduce to the same Jordan
algebra ${\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$. It thus follows from
Stinespring’s theorem that restricting the Choi-Jamiołkowski isomorphism to
Jordan algebras involves both CP maps $\phi=v^{*}\Phi
v:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$ and
CP maps $\phi=v^{*}\Phi
v:{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$.
Evidently, a CP map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is generally not also completely positive as a map
$\phi:{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$,161616Analysing
when this is the case is closely related to Peres’ separability criterion
Peres1996 ; Horodeckisz1996  (see also Ref. Frembs2022a ). As an immediate
consequence, we deduce that set of operators
$\rho_{\phi}^{J}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})_{\mathrm{D}}$
(corresponding to decomposable maps) is strictly larger than the set of
operators $\rho_{\phi}^{J}$ corresponding to CP maps, since

$\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{CP}}\subsetneq\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{D}}\;.$

The above argument shows that Choi’s theorem cannot be restricted to Jordan
algebras as in the case of Thm. 4 and Thm. 5; in essence: _positivity of
(quantum) states
$\rho\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})_{+}$ (equivalently
by Thm. 3, complete positivity for maps $C^{-1}(\rho)$) depends on the
(relative) operator ordering between the algebras
${\mathcal{L}(\mathcal{H}_{A})}$ and ${\mathcal{L}(\mathcal{H}_{B})}$_ (cf.
FrembsDoering2022a ; FrembsDoering2022b ; Frembs2022a ).

Choi’s theorem revisited. The distinction between $C^{*}$-algebras in Sec.
II.1 exposes why Choi’s theorem (Thm. 3) does not hold for the isomorphism $J$
in Eq. (1):171717That is, given a completely positive map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$,
$\rho_{\phi}^{J}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ is
generally not positive. _$J$ and $C$ are implicitly defined with respect to
different $C^{*}$-algebras_. Explicitly, since transposition changes the order
of composition from ${\mathcal{L}(\mathcal{H})}$ to
${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}$, $C^{-1}(\rho)$ in Eq. (3) is
more naturally identified with a map
$C^{-1}(\rho):{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
rather than with a map
${\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$—the
latter being the natural identification for $J^{-1}(\rho)$ (see also Eq. (15)
below). Taking this into account will lead to a reformulation of Thm. 3 in
Thm. 6 below.

In order to distinguish between the different operator orderings in
${\mathcal{L}(\mathcal{H})}$ and ${{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}$
in a basis-independent way, we replace the basis-dependent operation of
transposition with the order-reversing involution on the complex structure in
Eq. (9), given by the Hermitian adjoint $*$ (cf. Sec. II.1). Note from above
that
${\mathcal{L}(\mathcal{H})}^{*}\cong{{\mathcal{L}(\mathcal{H})}^{\mathrm{op}}}$.

We will need the following straightforward result, which is implicit in Ref.
FrembsDoering2022a ; FrembsDoering2022b ; Frembs2022a .181818Lm. 1 becomes Lm.
4 in Ref. Frembs2022a , when expressed in terms of time orientations (see also
Ref. FrembsDoering2022a ).

######  Lemma 1.

Let $\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})$. Then
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive if and only if
$\phi\circ*:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive.

###### Proof.

By Stinespring’s theorem Stinespring1955 , every completely positive map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is of the form $\phi=v^{*}\Phi v$ for a linear map
$v:\mathcal{H}_{B}\rightarrow\mathcal{K}$ and
$\Phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow\mathcal{L}(\mathcal{K})$ a
$C^{*}$-algebra homomorphism. It follows that
$\Phi\circ*:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow\mathcal{L}(\mathcal{K})$
is also a $C^{*}$-algebra homomorphism,

$(\Phi\circ*)(a\cdot_{-}a^{\prime})=\Phi((a^{\prime}a)^{*})=\Phi(a^{*}a^{\prime*})=\Phi(a^{*})\Phi(a^{\prime*})=(\Phi\circ*)(a)(\Phi\circ*)(a^{\prime})\;.$

Hence,
$\phi\circ*=v^{*}(\Phi\circ*)v:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive Stinespring1955 . ∎

Note that a similar result holds for $*$ replaced by any order-reversing
involution on ${\mathcal{L}(\mathcal{H}_{A})}$, in particular, it also holds
for $T$. We thus obtain the following reformulation of Thm. 3.

######  Theorem 6 (Choi (reformulated) Choi1975 ).

Let $\phi\in\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})$. Then
$\phi^{*}=\phi\circ*:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive if and only if
$\rho^{J}_{\phi^{*}}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ is
positive. That is, $J$ restricts to a map
$J|_{+}:(\mathcal{L}(\mathcal{H}_{A},\mathcal{H}_{B})_{\mathrm{CP}}\circ*)\rightarrow\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})_{+}$.

###### Proof.

By Eq. (1), $\rho_{\phi^{*}}^{J}=\sum_{k}e^{*}_{k}\otimes\phi^{*}(e_{k})$,
where $\\{e_{k}\\}_{k}\in\mathrm{ONB}({\mathcal{L}(\mathcal{H}_{A})})$ is any
orthonormal basis in ${\mathcal{L}(\mathcal{H}_{A})}$. From this we compute

$\displaystyle\rho^{J}_{\phi^{*}}=\sum_{k}e^{*}_{k}\otimes\phi^{*}(e_{k})=\sum_{ij}|i\rangle\langle
j|\otimes(\phi\circ*)(|j\rangle\langle i|)=\sum_{ij}|i\rangle\langle
j|\otimes\phi(|i\rangle\langle j|)=\rho^{C}_{\phi}\;,$

where we fixed the choice of basis to $\\{e_{k}\\}_{k}=\\{|i\rangle\langle
j|\\}_{ij}$ in the second step. By Choi’s theorem (Thm. 3),
$\rho^{J}_{\phi^{*}}=\rho^{C}_{\phi}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
is positive if and only if
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive, if and only if
$\phi^{*}:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive by Lm. 1. ∎

Note that Thm. 6 complements the results in Ref. PaulsenShultz2013 ; Kye2022 :
since the action on itself by (unitary) conjugation preserves the order of
composition (cf. Eq. (7)), Thm. 6 explains the invariance of Choi’s theorem
under the basis change in Ref. PaulsenShultz2013 ; Kye2022 .

We emphasise that—unlike Hermiticity-preserving, positive and decomposable
maps, which are maps between Jordan algebras (see Thm. 4 and Thm.
5)—completely positive maps are maps between $C^{*}$-algebras: a completely
positive map $\phi$ and its corresponding operator $\rho_{\phi}^{J}$ depend on
the relative operator ordering between the respective
algebras.191919Equivalently, $\rho_{\phi}^{J}$ depends on the (relative) time
orientation between the respective algebras (cf. FrembsDoering2022a ;
Frembs2022a ). Since quantum states correspond with completely positive maps
under Choi’s theorem, they too are generally sensitive to the relative
operator ordering in subalgebras FrembsDoering2022a .202020In fact, by Ref.
Frembs2022a  a quantum state is sensitive to the relative order if and only if
it is entangled.

###  II.3 Variations on the Choi-Jamiołkowski isomorphism

With Thm. 6, we define the following version of the Choi-Jamiołkowski
isomorphism:

$\displaystyle\begin{split}&(\rho^{CJ}_{\phi},a^{*}\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}:=(\phi_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\Longleftrightarrow\hskip 29.4487pt&(\rho^{CJ}_{\phi},a^{*}\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}:=(\phi^{*}_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a^{*}),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\Longleftrightarrow\hskip 29.4487pt&(\rho^{CJ}_{\phi},a\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
5.12128pt:=(\phi^{*}_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\end{split}$
(14)

for all $a\in{\mathcal{L}(\mathcal{H}_{A})}$,
$b\in{\mathcal{L}(\mathcal{H}_{B})}$, where (for added emphasis) we indicate
the signature of a map
$\phi:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
in subscript
$\phi_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}$.
Clearly, the isomorphism is basis-independent since Eq. (14) is expressed in
terms of inner products (similar to $J$ in Eq. (11)), and Thm. 4 and Thm. 5
apply since ${CJ}$ agrees with $J$ under restriction to Jordan algebras.
Finally, by comparison with Thm. 6,
$\rho^{CJ}_{\phi}\in{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}\cong\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
is positive if and only if
$\phi:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive, if and only if
$\phi^{*}:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive by Lm. 1. Eq. (14) therefore fixes a choice of operator
ordering on the Jordan algebras ${\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$
and ${\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$; by analogy with the order-
reversal imposed by transposition in Eq. (3), we denote the isomorphism in Eq.
(14) by ${CJ}$.212121We remark that this version of the isomorphism is
implicit in Ref. FrembsDoering2022a ; Frembs2022a .

This is not the only possible choice of operator orderings on
${\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$ and
${\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$. In particular, note
that—different from Eq. (14)—$\phi$ in Eq. (11) is implicitly interpreted as a
map
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$.
The latter signature arises from Eq. (14) under a change of (time orientation
in) $C^{*}$-algebras
${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\cong{\mathcal{L}(\mathcal{H}_{A})}^{*}$:
for all $a\in{\mathcal{L}(\mathcal{H}_{A})}$,
$b\in{\mathcal{L}(\mathcal{H}_{B})}$,

$\displaystyle\begin{split}&(\rho^{CJ}_{\phi},a\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
16.36024pt=(\phi^{*}_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$}}}{{\longleftrightarrow}}\quad&(\rho^{JC}_{\phi},a^{*}\otimes
b)_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
0.85355pt:=(\phi^{*}_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a^{*}),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\Longleftrightarrow\hskip 29.4487pt&(\rho^{JC}_{\phi},a^{*}\otimes
b)_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
0.85355pt:=(\phi_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\;.\end{split}$
(15)

Observe that ${JC}$ arises from $J$ under a change of identification from
$\rho_{\phi}^{J}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ to
$\rho^{JC}_{\phi}\in\mathcal{L}(\mathcal{H}^{*}_{A}\otimes\mathcal{H}_{B})$.
Indeed, using Eq. (13) between the first and the second line yields
$\rho_{\phi}^{JC}=(\rho^{CJ}_{\phi})^{*_{A}}$, where $*_{A}$ denotes the
Hermitian adjoint on ${\mathcal{L}(\mathcal{H}_{A})}$. We thus denote the
isomorphism in Eq. (15) by ${JC}$. Similar to ${CJ}$, we find that ${JC}$ is
basis-independent and Thm. 4 and Thm. 5 apply. Moreover, by comparison with
Thm. 6,
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive if and only if
$\rho^{JC}_{\phi}\in{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{\mathcal{L}(\mathcal{H}_{B})}\cong\mathcal{L}(\mathcal{H}^{*}_{A}\otimes\mathcal{H}_{B})$
is positive. In this way, Eq. (15) recovers Eq. (4); in particular, the
identification of the dual Hilbert space in Eq. (4) merely reflects the fact
that ${{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$ naturally acts on
$\mathcal{H}^{*}_{A}$ rather than on $\mathcal{H}_{A}$.

Finally, note that
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive if and only if
$\phi:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$
is completely positive; similarly,
$\phi:{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}$
is completely positive if and only if
$\phi:{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$
is completely positive. It follows that Eq. (14) and Eq. (15) are invariant
under an overall change:
${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$
and
${\mathcal{L}(\mathcal{H}_{B})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$,
which corresponds to the symmetry of those equations under complex conjugation
(cf. Eq. (13)). In other words, $\rho^{CJ}_{\phi}=(\rho^{CJ}_{\phi})^{*}$ is a
state on both
${\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}$ and
${{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$;
similarly, $\rho^{JC}_{\phi}=(\rho^{JC}_{\phi})^{*}$ is a state on both
${{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{\mathcal{L}(\mathcal{H}_{B})}$
and
${\mathcal{L}(\mathcal{H}_{A})}\otimes{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$.
Consequently, positivity of $\rho_{\phi}^{CJ}$ (similarly $\rho_{\phi}^{JC}$)
encodes a _relative choice of operator ordering between
${\mathcal{J}(\mathcal{H}_{A})_{\mathrm{sa}}}$ and
${\mathcal{J}(\mathcal{H}_{B})_{\mathrm{sa}}}$_. In summary, we record our
_variations on the Choi-Jamiołkowski isomorphism_ : for all
$a\in{\mathcal{L}(\mathcal{H}_{A})}$, $b\in{\mathcal{L}(\mathcal{H}_{B})}$,

$\displaystyle\begin{split}&(\rho^{CJ}_{\phi},a\otimes
b)_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}\hskip
2.13387pt=(\phi^{*}_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}(a),b)_{{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}\\\
\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$}}}{{\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{B})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$}}}{{\longleftrightarrow}}}}\quad&(\rho^{CJ}_{\phi},a\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
19.20569pt=(\phi^{*}_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\stackrel{{\scriptstyle\scalebox{0.6}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}{${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$}}}}{{\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$}}}{{\longleftrightarrow}}}}\quad&(\rho^{JC}_{\phi},a^{*}\otimes
b)_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\otimes{\mathcal{L}(\mathcal{H}_{B})}}\hskip
6.544pt=(\phi_{{\mathcal{L}(\mathcal{H}_{A})}\rightarrow{\mathcal{L}(\mathcal{H}_{B})}}(a),b)_{\mathcal{L}(\mathcal{H}_{B})}\\\
\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{A})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}$}}}{{\stackrel{{\scriptstyle\scalebox{0.6}{${\mathcal{L}(\mathcal{H}_{B})}\leftrightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}$}}}{{\longleftrightarrow}}}}\quad&(\rho^{JC}_{\phi},a^{*}\otimes
b)_{{\mathcal{L}(\mathcal{H}_{A})}\otimes{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}\hskip
6.544pt=(\phi_{{{{\mathcal{L}(\mathcal{H}_{A})}^{\mathrm{op}}}}\rightarrow{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}(a),b)_{{{{\mathcal{L}(\mathcal{H}_{B})}^{\mathrm{op}}}}}\;.\end{split}$
(16)

##  III Conclusion

We have identified the physical significance of the basis-dependent definition
of the Choi matrix ($\rho^{C}_{\phi}$ in Eq. (3)) in Choi’s theorem (Thm. 3)
with the relative operator ordering between the $C^{*}$-algebras describing
the two subsystems (Thm. 6). Moreover, different choices of relative operator
orderings distinguish between different versions of the Choi-Jamiołkowski
ismorphism (Eq. (16)). Our analysis is closely related with the intrinsic
dynamics in subsystems, as described by their respective time orientations
Doering2014 ; FrembsDoering2022a ; FrembsDoering2022b ; Frembs2022a . The
latter play a crucial role for the classification of bipartite quantum states
from more general non-signalling correlations FrembsDoering2022a , and further
allow for a classification of bipartite entanglement Frembs2022a .

Since the Choi-Jamiołkowski isomorphism is a basic tool across all of quantum
information theory, we expect the techniques used here will also shed light on
various other results in the field. For instance, due to its importance in the
framework of process matrices OreshkovCostaBrukner2012 ; CostaShrapnel2016
and quantum causal models LeiferSpekkens2013 ; CostaShrapnel2016 ;
AllenEtAl2017 ; BarrettLorenzOreshkov2020 , we suspect that an analysis which
parallels the one given here will prove useful in the further advancement of
the subject.

#### Acknowledgements.

MF thanks Francesco Buscemi and Andreas Döring for discussions. The authors
acknowledge financial support through grant number FQXi-RFP-1807 from the
Foundational Questions Institute and Fetzer Franklin Fund, a donor advised
fund of Silicon Valley Community Foundation, and ARC Future Fellowship
FT180100317.

## References

  * (1) E. M. Alfsen and F. W. Shultz, On orientation and dynamics in operator algebras. Part I, Commun. Math. Phys., 194 (1998), pp. 87–108.
  * (2) E. M. Alfsen and F. W. Shultz, Orientation in operator algebras, Proc. Natl. Acad. Sci. U.S.A., 95 (1998), pp. 6596–6601.
  * (3) J.-M. A. Allen, J. Barrett, D. C. Horsman, C. M. Lee, and R. W. Spekkens, Quantum common causes and quantum causal models, Phys. Rev. X, 7 (2017), p. 031021.
  * (4) M. Araújo, Global and local aspects of causality.  website accessed: 2022-11-30.
  * (5) J. C. Baez, Getting to the bottom of Noether’s theorem, Cambridge University Press, 2022, p. 66–99.
  * (6) V. Bargmann, Note on Wigner’s theorem on symmetry operations, J. Math. Phys., 5 (1964), pp. 862–868.
  * (7) J. Barrett, R. Lorenz, and O. Oreshkov, Quantum causal models, ArXiv e-prints, (2019).
  * (8) M.-D. Choi, Completely positive linear maps on complex matrices, Lin. Alg. Appl., 10 (1975), pp. 285 – 290.
  * (9) A. Connes, Caractérisation des espaces vectoriels ordonnés sous-jacents aux algèbres de von neumann, Ann. Inst. Fourier, 24 (1974), pp. 121–155.
  * (10) F. Costa and S. Shrapnel, Quantum causal modelling, New J. Phys., 18 (2016), p. 063032.
  * (11) J. de Pillis, Linear transformations which preserve Hermitian and positive semidefinite operators, Pac. J. Math., 23 (1967), pp. 129 – 137.
  * (12) A. Döring, Two new complete invariants of von Neumann algebras, ArXiv e-prints, (2014).
  * (13) M. Frembs, Bipartite entanglement and the arrow of time, ArXiv e-prints, (2022).
  * (14) M. Frembs and A. Döring, No-signalling, contextuality and the arrow of time, ArXiv e-prints, (2019).
  * (15) M. Frembs and A. Döring, From no-signalling to quantum states, ArXiv e-prints, (2022).
  * (16) , Gleason’s theorem for composite systems, ArXiv e-prints, (2022).
  * (17) E. Grgin and A. Petersen, Duality of observables and generators in classical and quantum mechnics, J. Math. Phys., 15 (1974), pp. 764–769.
  * (18) E. Grgin and A. Petersen, Algebraic implications of composability of physical systems, Commun. Math. Phys., 50 (1976), pp. 177–188.
  * (19) H. Hanche-Olsen, On the structure and tensor products of JC-algebras, Can. J. Math., 35 (1983), p. 1059–1074.
  * (20) H. Hanche-Olsen and E. Størmer, Jordan Operator Algebras, Monographs and studies in mathematics, Pitman Advanced Pub. Program, 1984.
  * (21) M. Horodecki, P. Horodecki, and R. Horodecki, Separability of mixed states: necessary and sufficient conditions, Phys. Lett. A, 223 (1996), pp. 1–8.
  * (22) A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys., 3 (1972), pp. 275 – 278.
  * (23) P. Jordan, Über Verallgemeinerungsmöglichkeiten des Formalismus der Quantenmechanik, Nachr. Ges. Wiss. Göttingen, 41 (1933), pp. 209–214.
  * (24) P. Jordan, J. v. Neumann, and E. Wigner, On an algebraic generalization of the quantum mechanical formalism, Ann. Math., 35 (1934), pp. 29–64.
  * (25) R. V. Kadison, Isometries of operator algebras, Ann. Math., 54 (1951), pp. 325–338.
  * (26) S.-H. Kye, Choi matrices revisited, J. Math. Phys., 63 (2022), p. 092202.
  * (27) M. S. Leifer and R. W. Spekkens, Towards a formulation of quantum theory as a causally neutral theory of Bayesian inference, Phys. Rev. A, 88 (2013), p. 052130.
  * (28) K. Mccrimmon, A Taste of Jordan Algebras, Springer, 2004.
  * (29) O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nat. Commun., 3 (2012), p. 1092.
  * (30) M. Ozawa, Error-disturbance relations in mixed states, ArXiv e-prints, (2014).
  * (31) V. I. Paulsen and F. Shultz, Complete positivity of the map from a basis to its dual basis, J. Math. Phys., 54 (2013), p. 072201.
  * (32) A. Peres, Separability criterion for density matrices, Phys. Rev. Lett., 77 (1996), pp. 1413–1415.
  * (33) W. F. Stinespring, Positive functions on $C^{*}$-algebras, Proc. Am. Math. Soc., 6 (1955), pp. 211–216.
  * (34) E. Størmer, Decomposable positive maps on $C^{*}$-algebras, Proc. Am. Math. Soc., 86 (1982), pp. 402–402.
  * (35) E. P. Wigner, Gruppentheorie und ihre Anwendung auf die Quantenmechanik der Atomspektren, Friedrich Vieweg und Sohn, Braunschweig, 1931.


# An asymptotic lower bound on the number of bent functions

V. N. Potapov1, A. A. Taranenko1, Yu. V. Tarannikov2,3<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(1Sobolev Institute of Mathematics, Novosibirsk, Russia
2Lomonosov Moscow State University, Moscow, Russia
3Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia)

###### Abstract

A Boolean function $f$ on $n$ variables is said to be a bent function if the
absolute value of all its Walsh coefficients is $2^{n/2}$. Our main result is
a new asymptotic lower bound on the number of Boolean bent functions. It is
based on a modification of the Maiorana–McFarland family of bent functions and
recent progress in the estimation of the number of transversals in latin
squares and hypercubes. By-products of our proofs are the asymptotics of the
logarithm of the numbers of partitions of the Boolean hypercube into
$2$-dimensional affine and linear subspaces.

Keywords: bent functions, asymptotic bounds, plateaued functions, affine
subspaces, transversals in latin hypercubes, perfect matchings

##  1 Definitions, preliminaries, and main results

Boolean functions and, in particularly, bent functions are widely used in
cryptography [8, 21, 28], and problems of their existence and enumeration are
important. Asymptotic bounds on the numbers of certain cryptographic functions
were obtained, for example, in [6, 22, 29].

The literature on bent functions is usually devoted to their existence and
constructions whereas it does not pay much attention to bounds on
cardinalities of classes of bent functions. The most known general bounds are
the cardinality of the Majorana–McFarland family as well as a cumbersome
Agievich’s formula [3]. There are also enumerative results for bent functions
on small number of variables $n$ (see, e.g., [18] for bent function on $8$
variables). Meanwhile, in this paper we are interested in asymptotic bounds
and do not compare them with exact results for small $n$. One of the problems
with estimations for small $n$ is that an affine equivalence still gives a
substantial contribution to the number of bent functions.

In Table 1 we present without proof our analysis of the logarithms of
cardinalities for some relatively rich classes of bent functions on $n$
variables. It is well known that bent functions exist if and only if $n$ is
even.

Class and reference Asymptotics of $\log_{2}$ of cardinality MM family [20]
$\log_{2}|{\cal M}(n)|={n\over 2}\cdot 2^{n/2}(1+o(1))$ completed MM family
[21] $\log_{2}|{\cal M}^{\\#}(n)|={n\over 2}\cdot 2^{n/2}(1+o(1))$ iterative
construction CC [7, 8] $\log_{2}|CC(n)|\leq 3^{n/2}(1+o(1))$ special subclass
of CC [29] $\log_{2}|CC^{\prime}(n)|=2^{n/2}(1+o(1))$ ${\cal C}$ class [10]
$\log_{2}|{\cal C}(n)|={n\over 2}\cdot 2^{n/2}(1+o(1))$ ${\cal D}$ class [10]
$\log_{2}|{\cal D}(n)|={n\over 2}\cdot 2^{n/2}(1+o(1))$ Agievich bound [3]
$\log_{2}A(n)={n\over 2}\cdot 2^{n/2}(1+o(1))$ special subclass of ${\cal PS}$
[21] $\log_{2}|{\cal PS}_{ap}(n)|=2^{n/2}(1+o(1))$ ${\cal P}{\rm
artial}\,\,{\cal S}{\rm pread}$ family [21] $\log_{2}|{\cal
PS}(n)|\leq{n^{2}\over 8}\cdot 2^{n/2}(1+o(1))$ Construction (K) [1, 5, 13]
$\log_{2}|K_{(n/2)-k}(n)|\leq{(2k+1)n\over 2^{k+1}}\cdot 2^{n/2}(1+o(1))$
Construction (K) [1, 5, 13] $\log_{2}|K_{(n/2)-1}(n)|={3n\over 4}\cdot
2^{n/2}(1+o(1))$

Table 1. Cardinalities of some classes of bent function on $n$ variables.

The upper bounds on the number of functions given by the Partial Spread or
iterative constructions are obtained by the means of rough estimations of
their components, and, in fact, they may be quite far from true values. The
main result of the present paper is the asymptotics in the last row of Table
1. Here $K_{(n/2)-k}(n)$ stands for the class of bent functions on $n$
variables given by the construction (K) with $n_{1}=(n/2)-k$.

Our lower bound is given by a class (K) of bent functions proposed in [5] that
is a variance of a construction from [1]. A similar construction of bent
functions over finite fields of characteristic $p\neq 2$ was also proposed in
[13]. Moreover, in [9] and [3] it was considered an analog of the construction
(K) that uses axis-aligned planes instead of affine ones. In [14, Theorem 4,
5] it is proved that the ternary analog of the construction (K) gives bent
functions outside the completed Maiorana–McFarland family, as well as it does
not produce all bent functions.

We show that the construction (K) gives more bent functions than any other
known explicit construction. Nevertheless, it is not improbable that some of
the above general methods produce even more bent functions, when their
parameters are appropriately chosen and estimated.

Let $F_{2}=\\{0,1\\}$. The set $F_{2}^{n}$ is called the $n$-dimensional
Boolean hypercube (or the Boolean $n$-cube). The hypercube $F_{2}^{n}$
equipped with scalar multiplication and coordinate-wise modulo $2$ addition
$\oplus$ is an $n$-dimensional vector space. Its zero element is
$\overline{0}=(0,\ldots,0)$. A set $C\subseteq F_{2}^{n}$ is called a
$k$-dimensional affine subspace if $C=a\oplus S$ for some $a\in F_{2}^{n}$ and
a $k$-dimensional linear subspace $S$ of $F_{2}^{n}$.

For $x,y\in F_{2}^{n}$, $x=(x_{1},\ldots,x_{n})$, $y=(y_{1},\ldots,y_{n})$, we
define their inner product as

$\langle x,y\rangle=x_{1}y_{1}\oplus\cdots\oplus x_{n}y_{n}.$

A function $f:F_{2}^{n}\rightarrow F_{2}$ is said to be a Boolean function on
$n$ variables.

The Walsh transform of a Boolean function $f$ is a function
$W_{f}:F_{2}^{n}\rightarrow\mathbb{Z}$ such that

$W_{f}(u)=\sum\limits_{x\in F_{2}^{n}}(-1)^{\langle u,x\rangle\oplus f(x)}.$

The values $W_{f}(u)$ are called Walsh coefficients, and the set of all Walsh
coefficients is called the Walsh spectrum of $f$. The support of the Walsh
spectrum is the set $\\{u:W_{f}(u)\neq 0\\}$.

A Boolean function $f$ on $n$ variables is said to be a bent function if the
Walsh spectrum of $f$ consists of $\pm 2^{n/2}$, and $f$ is a plateaued
function if all its Walsh coefficients are equal to $\pm 2^{k}$ or $0$, for
some integer $k$. We use $b_{n}$ to denote the number of bent functions on $n$
variables.

Bent functions $f$ and $g$ are affinely equivalent, if there is a
nondegenerate binary matrix $L$ of size $n\times n$ and $a\in F_{2}^{n}$ such
that

$g(x)=f(Lx\oplus a).$

For each bent function $f$ there are no more than $2^{n^{2}+n}$ affinely
equivalent bent functions.

It is well known (see [8, 12, 21]) that the algebraic degree (the degree of
the Zhegalkin polynomial which is also known as the algebraic normal form) of
a bent function $f$ on $n$ variables is at most $n/2$. Therefore, the number
$b_{n}$ of bent functions is not greater than
$2^{\sum\limits_{i=0}^{n/2}{n\choose i}}$, and, consequently,
$\log_{2}b_{n}\leq 2^{n-1}+\frac{1}{2}{n\choose n/2}$. In [11] and [2] there
are slightly better upper bounds on the number of bent functions, but
asymptotically both of them are $\log_{2}b_{n}\leq 2^{n-1}(1+o(1))$. In [23]
the following improvement of the upper bound is stated.

######  Theorem 1 ([23]).

Let $b_{n}$ be the number of bent functions on $n$ variables. Then it is not
greater than $6^{3\cdot 2^{n-6}}2^{\cdot 2^{n-2}(1+o(1))}$ as
$n\rightarrow\infty$. In particular,

$\log_{2}b_{n}\leq 3\cdot 2^{n-3}(1+o(1)).$

Note that Tokareva’s conjecture [29] on the decomposition of Boolean functions
into a sum of bent functions suggests that $\log_{2}b_{n}\geq
2^{n-2}+\frac{1}{2}{n\choose n/2}$.

Till now the class of Maiorana–McFarland functions [20] was considered as the
richest family of bent functions (up to some extensions). This class consists
of functions of the form

$f(x,y)=f(x_{1},\ldots,x_{m},y_{1},\ldots,y_{m})=\psi(y)\bigoplus\limits_{i=1}^{m}x_{i}\pi_{i}(y)$

and functions that are affinely equivalent to them. Here $n=2m$, $\psi(y)$ is
an arbitrary Boolean function on $m$ variables, and $\pi$ is an arbitrary
permutation of $F_{2}^{m}$, $\pi(y)=(\pi_{1}(y),\ldots,\pi_{m}(y))$.

The choice of permutation $\pi$ and Boolean function $\psi$ contributes
$2^{n/2}!\cdot 2^{2^{n/2}}$ bent functions to the Maiorana–McFarland family.
Taking into account affinely equivalent functions, we see that the completed
Maiorana–McFarland family contains no more than $2^{n/2}!\cdot
2^{2^{n/2}}\cdot 2^{n^{2}+n}$ bent functions.

Using the Stirling’s approximation,

$\log_{2}N!=N\log_{2}N-N\log_{2}e+o(N),$ (1)

we conclude that the logarithm of the number $b_{n}$ of bent functions on $n$
variables satisfies

$\log_{2}b_{n}\geq\frac{n}{2}\cdot 2^{n/2}+(1-\log_{2}e)\cdot
2^{n/2}+o(2^{n/2}).$

The main result of the present paper is the following asymptotic bound on the
number of bent functions.

######  Theorem 2.

Let $b_{n}$ be the number of bent functions on $n$ variables, where $n$ is
even. Then

$\log_{2}b_{n}\geq\frac{3n}{4}\cdot 2^{n/2}-2\log_{2}e\cdot
2^{n/2}+o(2^{n/2}).$

For additional information on bent functions and their number the reader is
reffered to papers and monographs [12, 21, 28, 29].

##  2 Construction of bent functions

For a Boolean variable $a\in F_{2}$, we use a notation $a^{1}=a$ and
$a^{0}=a\oplus 1$. In particular, $a^{b}=1\Leftrightarrow a=b$. Moreover, for
$x,y\in F^{n}_{2}$, $x=(x_{1},\ldots,x_{n})$, $y=(y_{1},\ldots,y_{n})$, we
define $x^{y}=x_{1}^{y_{1}}\cdots x_{n}^{y_{n}}$.

Let us describe a family of Boolean functions that gives the lower bound in
Theorem 2.

Construction (K): Let $n=n_{1}+n_{2}$, $n_{2}\geq n_{1}$, $n$ and
$n_{2}-n_{1}$ be even. Assume that $\\{C_{a}\\}_{a\in F_{2}^{n_{1}}}$,
$C_{a}\subseteq F_{2}^{n_{2}}$ is an ordered partition of $F_{2}^{n_{2}}$ into
$2^{n_{1}}$ affine subspaces of dimensions $n_{2}-n_{1}$. Define a Boolean
function $f$ on $n$ variables as

$f(x,y)=\bigoplus\limits_{{a}\in F_{2}^{n_{1}}}f_{a}(y){x}^{a},$

where $x\in F_{2}^{n_{1}},y\in F_{2}^{n_{2}}$, and $f_{a}$ are plateaued
functions such that the support of the Walsh spectrum of $f_{a}$ is exactly
$C_{a}$.

Note that the choice of different ordered partitions of $F_{2}^{n_{2}}$ into
$(n_{2}-n_{1})$-dimensional affine subspaces or different plateaued functions
$f_{a}$ for the same partition results in different functions $f$.

To prove that such a function $f$ is well defined, it is sufficient to
construct a plateaued function $g$ such that the support of its Walsh spectrum
is equal to any given affine subspace $C$ of even dimension. This fact was
previously established in [27], but we prove it here for the sake of
completeness.

For this purpose, we need the following properties of Walsh coefficients. They
can be found, e.g., in books [21, 28] or can be derived directly from the
definitions.

######  Proposition 1.

Let $f$ be a Boolean function on $n$ variables.

  1. 1.

Suppose that $f$ has exactly $k$ essential variables: $f(x,y)=g(x)$, where
$x\in F_{2}^{k}$, $y\in F_{2}^{n-k}$, and $g$ is a Boolean function on $k$
variables. Then for all $u\in F_{2}^{k}$ we have
$W_{f}(u,\overline{0})=2^{n-k}W_{g}(u)$, and $W_{f}(u,v)=0$ if $v\in
F_{2}^{n-k}\setminus\\{\overline{0}\\}$.

  2. 2.

Let $f(x)=g(Lx)$ for some nondegenerate binary matrix $L$ of sizes $n\times n$
and a Boolean function $g$ on $n$ variables. Then
$W_{f}(u)=W_{g}((L^{-1})^{T}u)$.

  3. 3.

Assume that $f(x)=g(x)\oplus\langle a,x\rangle$ for some $a\in F^{n}_{2}$ and
a Boolean function $g$ on $n$ variables. Then $W_{f}(u)=W_{g}(u\oplus a)$.

######  Proposition 2 ([27]).

Let $C\subseteq F^{n}_{2}$ be an affine subspace of even dimension $k$. There
exists a one-to-one correspondence between plateaued functions $f$ on $n$
variables, whose support of the Walsh spectrum is equal to $C$, and bent
functions $g$ on $k$ variables. Moreover, the absolute value of all nonzero
Walsh coefficients $W_{f}$ of the function $f$ is $2^{n-k/2}$.

###### Proof.

Let $g$ be a bent function on $k$ variables. By the definition,
$|W_{g}(u)|=2^{k/2}$ for all $u\in F_{2}^{k}$. Using Proposition 1(1), we
construct a Boolean function $h$ on $n$ variables all of whose nonzero Walsh
coefficients are equal to $\pm 2^{n-k/2}$ and located in a $k$-dimensional
subcube of the Boolean $n$-cube. With the help of Proposition 1(2) and (3), we
put the support of the Walsh spectrum of $h$ to the affine subspace $C$ and
obtain the desired plateaued function $f$. Note that the absolute value of all
nonzero Walsh coefficients of $f$ is $2^{n-k/2}$.

Reversing this reasoning, we have the equivalence. ∎

Example. Let $n=6$, $n_{1}=2$, $n_{2}=4$. Consider the partition
$\\{C_{00},C_{01},C_{10},C_{11}\\}$ of $F_{2}^{4}$ into $2$-dimensional affine
subspaces:

$\displaystyle C_{00}=\\{0000,0100,1010,1110\\};\leavevmode\nobreak\
\leavevmode\nobreak\ C_{01}=\\{0010,0110,0011,0111\\};$ $\displaystyle
C_{10}=\\{1000,1100,1001,1101\\};\leavevmode\nobreak\ \leavevmode\nobreak\
C_{11}=\\{0001,0101,1011,1111\\}.$

Using Propositions 1, 2 and the bent function $y_{1}y_{2}$, we construct the
following plateaued functions $f_{a}$, whose support of the Walsh spectrum is
exactly $C_{a}$:

$\begin{array}[]{ll}f_{00}=y_{2}(y_{1}\oplus y_{3});&f_{01}=y_{2}y_{4}\oplus
y_{3};\\\ f_{10}=y_{2}y_{4}\oplus y_{1};&f_{11}=y_{2}(y_{1}\oplus y_{3})\oplus
y_{4}.\end{array}$

So the function $f$ given by the construction (K) is

$f(x,y)=(y_{1}\oplus y_{3}\oplus y_{4})(x_{1}x_{2}\oplus y_{2}x_{1}\oplus
y_{2}x_{2})\oplus y_{3}x_{2}\oplus y_{1}x_{1}\oplus y_{2}(y_{1}\oplus y_{3}).$

Let us prove now that the construction (K) produces only bent functions.

######  Theorem 3 ([5]).

Every function $f$ given by the construction (K) is bent.

###### Proof.

By the construction,

$f=\bigoplus\limits_{a\in F_{2}^{n_{1}}}f_{a}(y){x}^{a},$

where $f_{a}:F^{n_{2}}_{2}\rightarrow F_{2}$ are plateaued functions whose
supports of Walsh spectra equal $C_{a}$ and $\\{C_{a}\\}_{a\in F_{2}^{n_{1}}}$
is an ordered partition of $F^{n_{2}}_{2}$ into $(n_{2}-n_{1})$-dimensional
affine subspaces.

By Proposition 2, the absolute value of all nonzero Walsh coefficients
$W_{f_{a}}$ of the plateaued functions $f_{a}$ is
$2^{n_{2}-\frac{n_{2}-n_{1}}{2}}=2^{n/2}$.

Using the definition of Walsh coefficients and the function $f$, we have

$W_{f}(u,v)=\sum\limits_{x\in F_{2}^{n_{1}}}\sum\limits_{y\in
F_{2}^{n_{2}}}(-1)^{\langle u,x\rangle\oplus\langle
v,y\rangle\oplus\bigoplus\limits_{{a}\in F_{2}^{n_{1}}}f_{{a}}(y){x}^{a}},$

where $u\in F_{2}^{n_{1}}$ and $v\in F_{2}^{n_{2}}$.

From properties of the operation $x^{a}$, we see that for given $x\in
F_{2}^{n_{1}}$ the sum $\bigoplus\limits_{{a}\in
F_{2}^{n_{1}}}f_{{a}}(y){x}^{a}$ has the unique nonzero summand $f_{x}(y)$
(when $a=x$). Therefore,

$\displaystyle W_{f}(u,v)=\sum\limits_{x\in F_{2}^{n_{1}}}\sum\limits_{y\in
F_{2}^{n_{2}}}(-1)^{\langle u,x\rangle\oplus\langle v,y\rangle\oplus
f_{x}(y)}=\sum\limits_{x\in F_{2}^{n_{1}}}(-1)^{\langle
u,x\rangle}\left(\sum\limits_{y\in F_{2}^{n_{2}}}(-1)^{\langle
v,y\rangle\oplus f_{x}(y)}\right)$ $\displaystyle=\sum\limits_{x\in
F_{2}^{n_{1}}}(-1)^{\langle u,x\rangle}W_{f_{x}}(v).$

Note that for given $v\in C_{b}$ the sum $\sum\limits_{x\in
F_{2}^{n_{1}}}(-1)^{\langle u,x\rangle}W_{f_{x}}(v)$ has the unique nonzero
summand $(-1)^{\langle u,b\rangle}W_{f_{b}}(v)$, since all other plateaued
functions $f_{a}$ do not have $v$ in the support of their Walsh spectrum. Thus
$|W_{f}(u,v)|=|W_{f_{b}}(v)|=2^{n/2}$ for all $u\in F_{2}^{n_{1}}$ and $v\in
F_{2}^{n_{2}}$. It means that $f$ is a bent function. ∎

In what follows, we denote by $\widetilde{N}_{m}^{k}$ the number of ordered
partitions of the space $F_{2}^{m}$ into $k$-dimensional affine subspaces and
by $N_{m}^{k}$ the number of all such unordered partitions. (A partition of
$F_{2}^{m}$ into affine subspaces is unordered when the order of subspaces in
the partition does not matter). Proposition 2 and Theorem 3 easily imply the
following formula for the number of bent functions in the construction (K).

######  Theorem 4.

Let $n=n_{1}+n_{2}$, $n_{2}\geq n_{1}$, and $n$ and $n_{2}-n_{1}$ be even.
Then the number $B_{n}$ of bent functions given by the construction (K) is

$B_{n}=(b_{n_{2}-n_{1}})^{2^{n_{1}}}\cdot\widetilde{N}_{n_{2}}^{n_{2}-n_{1}},$
(2)

where $b_{n_{2}-n_{1}}$ is the number of bent functions over $n_{2}-n_{1}$
variables, $\widetilde{N}_{n_{2}}^{n_{2}-n_{1}}$ is the number of ordered
partitions of the space $F_{2}^{n_{2}}$ into $2^{n_{1}}$ affine subspaces of
dimensions $n_{2}-n_{1}$.

Note that there are other generalizations of the construction (K). For
example, instead of ordered partitions of $F_{2}^{n_{2}}$ into affine
subspaces of dimensions $n_{2}-n_{1}$, one can also use ordered partitions of
$F_{2}^{n_{2}}$ into appropriate sets $C_{a}$ of cardinality $2^{n_{2}-n_{1}}$
and look for plateaued functions $f_{a}$ whose spectrum supports are $C_{a}$.

Although this generalization obviously gives more bent functions, the
determination of the exact asymptotics of their number is quite hard. Indeed,
firstly we need to effectively enumerate partitions of $F_{2}^{n_{2}}$ into
sets $C_{a}$ of cardinality $2^{n_{2}-n_{1}}$ that can have a complicated
structure. Next, for every set $C_{a}$ used in the partition we should show
that there exists a plateaued function $f$ with the support of the Walsh
spectrum equal to $C_{a}$. More than that, we need good lower bounds on the
numbers of such plateaued functions.

Note that the exact values of the numbers of plateaued functions with a given
support of the Walsh spectrum are known only for narrow families [17], and
these numbers prove to be much smaller than the number of bent functions with
the same cardinality of the support of the Walsh spectrum. Thus, their
contribution to the total number is expected to be much less than the impact
of affine subspaces.

In [16] Hodžić et al. provide examples of partitions of Boolean hypercubes
into appropriate sets and construct a family of bent functions with the help
of such generalization of the construction (K). Unfortunately, the number of
these bent functions turns out to be relatively small.

Thus we will focus on what is more realistic to be accomplished. More exactly,
we estimate the value $\widetilde{N}_{n_{2}}^{n_{2}-n_{1}}$ and obtain a new
asymptotic lower bound on the logarithm of the number of Boolean bent
functions using the formula (2).

##  3 Proof of the lower bound

The key element of the proof of Theorem 2 is an estimation of the number of
ordered partitions of $F_{2}^{m}$ into $2$-dimensional affine subspaces.
Meanwhile, here we establish the asymptotics of the logarithm of the number of
the unordered ones. For shortness, we denote the number of unordered
partitions of $F_{2}^{m}$ into $2$-dimensional affine subspaces by $N_{m}$
($N_{m}=N^{2}_{m}$).

######  Theorem 5.

The number $N_{m}$ of all unordered partitions of $F_{2}^{m}$ into
$2$-dimensional affine subspaces satisfies

$\frac{m}{2}\cdot 2^{m}+c_{1}\cdot
2^{m}+o(2^{m})\leq\log_{2}N_{m}\leq\frac{m}{2}\cdot 2^{m}+c_{2}\cdot
2^{m}+o(2^{m}),$

where $c_{1}=-1-\frac{3}{4}\log_{2}e\approx-2.08$,
$c_{2}=\frac{7}{16}-\frac{11}{16}\log_{2}3\approx-0.65$.

It is easy to see that the numbers of ordered and unordered partitions of
$F_{2}^{m}$ into $k$-dimensional affine subspaces are connected in the
following way.

######  Proposition 3.

If $\widetilde{N}_{m}^{k}$ is the number of ordered partitions of the space
$F_{2}^{m}$ into $k$-dimensional affine subspaces and $N_{m}^{k}$ is the
number of unordered ones, then

$\widetilde{N}_{m}^{k}=2^{m-k}!\cdot N^{k}_{m}.$

The proof of Theorem 5 needs more definitions and some auxiliary results on
latin hypercubes, their transversals, and perfect matchings in hypergraphs.

A $d$-dimensional latin hypercube of order $n$ is a $d$-dimensional matrix
$Q=(q_{\alpha})$ of order $n$ whose entries indexed by
$\alpha=(\alpha_{1},\ldots,\alpha_{d})$, $\alpha_{i}\in\\{1,\ldots,n\\}$,
where $Q$ is filled by $n$ symbols so that each symbol appears in each line
(1-dimensional submatrix) exactly once. A transversal in a latin hypercube is
a collection of $n$ entries hitting each hyperplane ($(d-1)$-dimensional
submatrix) and each symbol exactly once.

Actually, we are interested in transversals in specific latin hypercubes. Let
$Q_{m}$ be the $3$-dimensional latin hypercube of order $2^{m}$ corresponding
to the Cayley table of the iterated group $\mathbb{Z}_{2}^{m}$. In more
details, its entry $q_{\alpha_{1},\alpha_{2},\alpha_{3}}=\alpha_{4}$,
$\alpha_{i}\in F_{2}^{m}$, if and only if
$\alpha_{1}\oplus\cdots\oplus\alpha_{4}=\overline{0}$. For more information
about latin hypercubes, their transversals, and iterated groups and
quasigroups, see e.g. [26].

In what follows, instead of entries of $Q_{m}$ we consider tuples
$(\alpha_{1},\ldots,\alpha_{4})$, $\alpha_{i}\in F_{2}^{m}$ satisfying
$\alpha_{1}\oplus\cdots\oplus\alpha_{4}=\overline{0}$. Such a notation
comprises the index and the value of an entry of the latin hypercube. Then a
transversal in the latin hypercube $Q_{m}$ is a collection of $2^{m}$ tuples

$(\alpha_{1}^{1},\ldots,\alpha_{4}^{1}),\ldots,(\alpha^{2^{m}}_{1},\ldots,\alpha_{4}^{2^{m}})$

such that for each $j=1,\ldots,4$ all $\alpha^{i}_{j}$ are different,
$i=1,\ldots,2^{m}$.

In [15, Theorem 7.2] it was found the asymptotics of the number of
transversals in iterated abelian groups. In particular, we have the following
estimation of the number of transversals in $Q_{m}$.

######  Theorem 6 ([15]).

The number $T_{m}$ of transversals in the $3$-dimensional latin hypercube
$Q_{m}$ of order $2^{m}$ that is the Cayley table of the iterated group
$\mathbb{Z}_{2}^{m}$ is

$T_{m}=(1+o(1))\frac{2^{m}!^{3}}{2^{m(2^{m}-1)}}$

as $m\rightarrow\infty$.

There is a connection between the number of unordered partitions of
$F_{2}^{m}$ into $2$-dimensional affine spaces and the number of transversals
in $Q_{m}$.

######  Proposition 4.

The number $N_{m}$ of unordered partitions of $F_{2}^{m}$ into $2$-dimensional
affine subspaces is not less than the number of transversals in the latin
hypercube $Q_{m-2}$:

$N_{m}\geq T_{m-2}.$

###### Proof.

For shortness, we use a notation $M=2^{m-2}$. Let a collection $R$ of $M$
tuples

$(\alpha_{1}^{1},\ldots,\alpha_{4}^{1}),\ldots,(\alpha^{M}_{1},\ldots,\alpha_{4}^{M})$

be a transversal in the latin hypercube $Q_{m-2}$. Recall that
$\alpha_{j}^{i}\in F_{2}^{m-2}$,
$\alpha_{1}^{i}\oplus\cdots\oplus\alpha_{4}^{i}=\overline{0}$ for all $i$, and
for a fixed $j$ all $\alpha^{i}_{j}$ are different.

To each such collection $R$ we put in correspondence a collection $R^{\prime}$
of $M$ sets

$\\{\beta_{1}^{1},\ldots,\beta_{4}^{1}\\},\ldots,\\{\beta^{M}_{1},\ldots,\beta_{4}^{M}\\},$

where $\beta^{i}_{j}\in F_{2}^{m}$ and

$\beta^{i}_{j}=\left\\{\begin{array}[]{l}(\alpha^{i}_{j},0,0)\mbox{ if
}j=1;\\\ (\alpha^{i}_{j},0,1)\mbox{ if }j=2;\\\ (\alpha^{i}_{j},1,0)\mbox{ if
}j=3;\\\ (\alpha^{i}_{j},1,1)\mbox{ if }j=4.\end{array}\right.$

Let us show that $R^{\prime}$ is an unordered partition of $F_{2}^{m}$ into
$2$-dimensional affine subspaces.

First of all, we still have
$\beta_{1}^{i}\oplus\cdots\oplus\beta_{4}^{i}=\overline{0}$ for all $i$. It
means that each set $\\{\beta_{1}^{i},\ldots,\beta_{4}^{i}\\}$ is a
$2$-dimensional affine subspace in $F_{2}^{m}$. Note that different tuples
$(\alpha_{1}^{i},\ldots,\alpha_{4}^{i})$ correspond to different
$2$-dimensional affine subspaces $\\{\beta_{1}^{i},\ldots,\beta_{4}^{i}\\}$.

Since $R$ is a transversal in the latin hypercube $Q_{m-2}$, for given
$\alpha\in F_{2}^{m-2}$ and $j\in\\{1,\ldots,4\\}$ there is a unique
$i\in\\{1,\ldots,M\\}$ such that $\alpha$ coincides with some $\alpha_{i}^{j}$
from the collection $R$. So by the construction, for each $\beta\in F_{2}^{m}$
there is a unique $\beta^{i}_{j}$ from the collection $R^{\prime}$ such that
$\beta=\beta_{i}^{j}$. Since each set in $R^{\prime}$ has all different
elements, we conclude that $R^{\prime}$ is a partition of $F_{2}^{m}$.

Thus, $R^{\prime}$ is an unordered partition of $F_{2}^{m}$ into
$2$-dimensional affine subspaces. Since different transversals $R$ in
$Q_{m-2}$ consist of different collections of tuples, they give different
partitions $R^{\prime}$. ∎

To prove the upper bound in Theorem 5, one can use bounds on the number of
perfect matchings in an appropriate hypergraph.

Let $H(X,W)$ be a hypergraph with the vertex set $X$ and a hyperedge set $W$.
A hypergraph $H$ is said to be $d$-uniform if each hyperedge consists of
exactly $d$ vertices and $k$-regular if each vertex appears in exactly $k$
hyperedges.

A perfect matching in a hypergraph $H$ is a collection of hyperedges that
cover each vertex of a hypergraph exactly once. Let $PM(H)$ denote the number
of perfect matchings in $H$.

Consider a hypergraph $\mathcal{H}_{m}$, whose vertex set $V(\mathcal{H}_{m})$
is the set $F_{2}^{m}$ and the hyperedge set $W(\mathcal{H}_{m})$ is the set
of all affine subspaces in $F_{2}^{m}$:

$\\{x_{1},\ldots,x_{4}\\}\in W(\mathcal{H}_{m})\Leftrightarrow
x_{1}\oplus\cdots\oplus x_{4}=\overline{0}.$

It is easy to see that $\mathcal{H}_{m}$ is a $4$-uniform $k$-regular
hypergraph on $2^{m}$ vertices, where $k=\frac{1}{6}(2^{m}-1)(2^{m}-2)$.
Moreover, the number $N_{m}$ of unordered partitions of $F_{2}^{m}$ is exactly
the number of perfect matchings in $\mathcal{H}_{m}$.

From [25, Corollary 2] we have the following upper bound on the number of
perfect matchings in uniform regular hypergraphs.

######  Theorem 7 ([25]).

Let $H$ be a $d$-uniform $k$-regular hypergraph on $n$ vertices, $d\geq 3$.
Then the number $PM(H)$ of perfect matchings in $H$ satisfies

$PM(H)\leq(\mu\cdot k)^{n/d},$

where $\mu=\mu(d)=\frac{d^{d}d!^{1/d}}{d!^{2}}$ for $d\geq 4$ and
$\mu=\frac{3}{2^{2/3}}$ for $d=3$.

Now we are ready to find the asymptotics of the logarithm of the number of
unordered partitions of $F_{2}^{m}$ into $2$-dimensional affine subspaces.

###### Proof of Theorem 5.

We start with the proof of the lower bound. By Proposition 4, the number
$N_{m}$ of unordered partitions of $F_{2}^{m}$ into $2$-dimensional affine
subspaces is not less than the number of transversals in the latin hypercube
$Q_{m-2}$:

$N_{m}\geq T_{m-2}.$

By Theorem 6, we have that

$T_{m-2}=(1+o(1))\frac{2^{(m-2)}!^{3}}{2^{(m-2)\cdot(2^{m-2}-1)}}\mbox{ as
}m\rightarrow\infty.$

Using the Stirling’s approximation (1), we deduce

$\displaystyle\log_{2}N_{m}\geq\log_{2}T_{m-2}=\frac{m}{2}\cdot
2^{m}-\left(1+\frac{3}{4}\log_{2}e\right)\cdot 2^{m}+o(2^{m}).$

For the upper bound we use Theorem 7 and the fact that $N_{m}$ is the number
of perfect matchings in the hypergraph $\mathcal{H}_{m}$:

$N_{m}\leq\left(\frac{\mu}{6}\cdot(2^{m}-1)(2^{m}-2)\right)^{2^{m-2}}.$

$\log_{2}N_{m}\leq\frac{m}{2}\cdot 2^{m}+\frac{1}{4}\log_{2}\frac{\mu}{6}\cdot
2^{m}+o(2^{m}).$

Since $\mu=\frac{4^{4}\cdot 4!^{1/4}}{4!^{2}}$, we have
$\log_{2}\frac{\mu}{6}=\frac{7}{4}-\frac{11}{4}\log_{2}3$. ∎

######  Remark 1.

In [19] it was announced another upper bound on the number of perfect
matchings with $\mu=e^{-3}$ in the case of hypergraph $\mathcal{H}_{m}$. If we
use it instead of Theorem 7, then we obtain

$\log N_{m}\leq\frac{m}{2}\cdot 2^{m}+c^{\prime}_{2}\cdot 2^{m}+o(2^{m}),$

where $c^{\prime}_{2}=-\frac{1}{4}(1+\log_{2}3+3\log_{2}e)\approx-1.73$.

At last, let us prove the lower bound on the number of bent functions.

###### Proof of Theorem 2.

Let $n$ be even, $n_{1}=n/2-1$, $n_{2}=n/2+1$.

By Theorem 4 and Proposition 3, the number of bent functions given by the
construction (K) for these $n_{1}$ and $n_{2}$ is

$B_{n}=2^{3\cdot 2^{n/2-1}}\cdot 2^{n/2-1}!\cdot N_{n/2+1},$

since there are $8=2^{3}$ bent functions on $2$ variables.

Using Theorem 5 and the Stirling’s approximation (1), we get

$\displaystyle\log_{2}B_{n}\geq\frac{3n}{4}\cdot 2^{n/2}-2\log_{2}e\cdot
2^{n/2}+o(2^{n/2}).$

∎

######  Proposition 5.

The asymptotically maximal number of bent functions given by the construction
(K) for fixed $n_{2}-n_{1}$ is achieved when $n_{1}=n/2-1$, $n_{2}=n/2+1$.

###### Proof.

If $n_{1}=n_{2}=n/2$, then the construction (K) coincides with the
Maiorana–McFarland family of bent functions, whose number is smaller than one
from Theorem 2.

Let $n_{1}=n/2-k$, $n_{2}=n/2+k$, where $k\in\mathbb{N}$, $k\geq 1$ is fixed.
A fundamental contribution to the number of such bent functions is given by
the number $\widetilde{N}_{n_{2}}^{2k}$ of ordered partitions of
$F_{2}^{n_{2}}$ into $2k$-dimensional affine subspaces. For this purpose we
again use a connection to perfect matchings in a special hypergraph and
Theorem 7.

Let $\mathcal{H}_{n_{2}}^{k}$ be $2^{2k}$-uniform hypergraph on $2^{n_{2}}$
vertices, where each hyperedge is a $2k$-dimensional affine subspace in
$2^{n_{2}}$. The degree of this hypergraph (number of $2k$-dimensional affine
subspaces containing a given $x\in F_{2}^{n_{2}}$) is not greater than
$2^{2kn_{2}}$. By Theorem 7 and Proposition 3,

$\widetilde{N}_{n_{2}}^{2k}\leq 2^{n/2-k}!\cdot(2^{2k(n/2+k)})^{2^{n/2-k}},$

since the constant $\mu$ in Theorem 7 is not greater than $1$. Using the
Stirling’s approximation (1), we see that

$\displaystyle\log_{2}\widetilde{N}_{n_{2}}^{2k}\leq(n/2-k)\cdot
2^{n/2-k}+2k(n/2+k)\cdot 2^{n/2-k}+o(n2^{n/2})=$
$\displaystyle\frac{2k+1}{2^{k+1}}\cdot n2^{n/2}+o(n2^{n/2}).$

This number is maximal when $k=1$. ∎

For a more detailed study of the number of partitions of $F_{2}^{n}$ into
$k$-dimensional affine subspaces see [4].

##  4 Bounds on the number of $2$-spreads

A collection $\mathcal{S}=\\{S_{1},\ldots,S_{M}\\}$ of $d$-dimensional linear
spaces $S_{i}\subseteq F_{2}^{n}$, where $M=\frac{2^{n}-1}{2^{d}-1}$, is
called a (full) $d$-spread if each $x\in F_{2}^{n}\setminus\\{\overline{0}\\}$
belongs to exactly one $S_{i}$. Equivalently, a $d$-spread is a partition of
$F_{n}^{2}\setminus\\{\overline{0}\\}$ into
$S_{i}\setminus\\{\overline{0}\\}$, where $S_{i}$ are $d$-dimensional linear
subspaces. Although spreads are interesting in themselves, they are often used
as components of other combinatorial designs. For example, the ${\cal PS}$
construction [21] of bent functions on $n$ variables is based on partial
$(n/2)$-spreads.

Acting similarly to the proof of Theorem 5, we find the asymptotics of the
logarithm of the number of $2$-spreads.

######  Theorem 8.

Let $n$ be even and $W_{n}$ be the number of unordered partitions of
$F_{2}^{n}$ into $2$-dimensional linear subspaces (number of $2$-spreads).
Then

$\log_{2}W_{n}=\frac{n}{3}\cdot 2^{n}+o(n2^{n}).$

Since the number of subspaces composing a $2$-spread is $M=\frac{2^{n}-1}{3}$,
$2$-spreads exist only if $n$ is even.

To prove this theorem, we use a connection between the number of $2$-spreads
$\mathcal{S}$ in $F_{2}^{n}$ and the number of transversals in specific latin
squares.

Let us denote by $L_{n}$ the latin square of order $2^{n}$ correspoding to the
Cayley table of the group $\mathbb{Z}_{2}^{n}$: the latin square $L_{n}$ has
entries $l_{\alpha_{1},\alpha_{2}}=\alpha_{3}$, where $\alpha_{i}\in
F_{2}^{n}$, if and only if
$\alpha_{1}\oplus\alpha_{2}\oplus\alpha_{3}=\overline{0}$.

In what follows, we denote entries of $L_{m}$ by tuples
$(\alpha_{1},\alpha_{2},\alpha_{3})$, $\alpha_{i}\in F_{2}^{n}$, satisfying
$\alpha_{1}\oplus\alpha_{2}\oplus\alpha_{3}=\overline{0}$. A transversal in
the latin square $L_{n}$ is a collection of $2^{n}$ entries

$(\alpha_{1}^{1},\alpha_{2}^{1},\alpha_{3}^{1}),\ldots,(\alpha^{2^{n}}_{1},\alpha_{2}^{2^{n}},\alpha_{3}^{2^{n}})$

such that for each $j=1,\ldots,3$ all $\alpha^{i}_{j}$ are different,
$i=1,\ldots,2^{n}$.

From [15, Theorem 1.2] we have the following asymptotics of the number of
transversals in $L_{n}$.

######  Theorem 9 ([15]).

The number $T_{n}$ of transversals in the Cayley table $L_{n}$ of the group
$\mathbb{Z}_{2}^{n}$ of order $2^{n}$ is

$T_{n}=(e^{-1/2}+o(1))\frac{2^{n}!^{2}}{2^{n\cdot(2^{n}-1)}}$

as $n\rightarrow\infty$.

###### Proof of Theorem 8.

The proof of the lower bound is based on transversals in the latin square
$L_{n-2}$. For shortness, denote the order of $L_{n-2}$ by $m=2^{n-2}$.

Let a collection $R$ of $m$ entries

$(\alpha_{1}^{1},\alpha_{2}^{1},\alpha_{3}^{1}),\ldots,(\alpha^{m}_{1},\alpha_{2}^{m},\alpha_{3}^{m}),$

$\alpha^{i}_{j}\in F_{2}^{n-2}$, be a transversal in $L_{n-2}$. In particular,
$\alpha^{i}_{1}\oplus\alpha_{2}^{i}\oplus\alpha_{3}^{i}=\overline{0}$ for each
$i=1,\ldots,m$ and for given $j$ all $\alpha^{i}_{j}$ are different.

For every such collection $R$, consider a collection $R^{\prime}$ of $m$ sets

$\\{\beta_{1}^{1},\beta_{2}^{1},\beta_{3}^{1}\\},\ldots,\\{\beta^{m}_{1},\beta_{2}^{m},\beta_{3}^{m}\\},$

where $\beta^{i}_{j}\in F_{2}^{n}$ and

$\beta^{i}_{j}=\left\\{\begin{array}[]{l}(\alpha^{i}_{j},0,1)\mbox{ if
}j=1;\\\ (\alpha^{i}_{j},1,0)\mbox{ if }j=2;\\\ (\alpha^{i}_{j},1,1)\mbox{ if
}j=3.\end{array}\right.$

Note that for each $i=1,\ldots,m$ and
$\\{\beta_{1}^{i},\beta_{2}^{i},\beta_{3}^{i}\\}\in R^{\prime}$ the set
$\\{\overline{0},\beta_{1}^{i},\beta_{2}^{i},\beta_{3}^{i}\\}$ is a
$2$-dimensional linear subspace in $F_{2}^{n}$, since
$\overline{0}\oplus\beta^{i}_{1}\oplus\beta_{2}^{i}\oplus\beta_{3}^{i}=\overline{0}$.
Since $R$ is a transversal, all of these linear subspaces intersect only at
$\overline{0}$. Let
$R^{\prime\prime}=\\{\\{\overline{0},\beta_{1}^{i},\beta_{2}^{i},\beta_{3}^{i}\\}:\\{\beta_{1}^{i},\beta_{2}^{i},\beta_{3}^{i}\\}\in
R^{\prime}\\}$ be a collection of such linear subspaces in $F_{2}^{n}$.

Subspaces from $R^{\prime\prime}$ cover all nonzero elements of $F_{2}^{n}$
except for elements of the form $(\alpha_{j}^{i},0,0)$. In order to cover
them, consider a $2$-spread
$\mathcal{S}=\\{\\{\overline{0},\gamma_{1}^{i},\gamma_{2}^{i},\gamma_{3}^{i}\\}\\}_{i=1}^{r}$
in $F_{2}^{n-2}$, $r=\frac{2^{n-2}-1}{3}$. For each such collection of linear
subspaces $\mathcal{S}$ in $F_{2}^{n-2}$, we construct a collection
$\mathcal{S}^{\prime}$ of linear subspaces
$\\{\\{\overline{0},\delta_{1}^{i},\delta_{2}^{i},\delta_{3}^{i}\\}\\}_{i=1}^{r}$
in $F_{2}^{n}$, where $\delta^{i}_{j}=(\gamma^{i}_{j},0,0)$.

It is easy to see that
$\\{\overline{0},\delta_{1}^{i},\delta_{2}^{i},\delta_{3}^{i}\\}\in
S^{\prime}$ are linear spaces in $F_{2}^{n}$ and all of them intersect only at
$\overline{0}$. Moreover, linear subspaces from $\mathcal{S}^{\prime}$ and
$R^{\prime\prime}$ also intersect only at $\overline{0}$. At last, for each
$x\in F_{2}^{n}\setminus\\{\overline{0}\\}$ there is a linear subspace $S\in
R^{\prime\prime}\cup\mathcal{S}^{\prime}$ such that $x\in S$.

Consequently, $R^{\prime\prime}\cup\mathcal{S}^{\prime}$ is a $2$-spread in
$F_{2}^{n}$ and we have the inequality

$W_{n}\geq T_{n-2}\cdot W_{n-2}.$

Using Theorem 9 and the Stirling’s approximation (1), we see that

$\log_{2}T_{n}\geq n2^{n}+o(n2^{n}).$

Solving the recurrence relation

$\log_{2}W_{n}\geq\log_{2}W_{n-2}+(n-2)\cdot
2^{n-2}+o(n2^{n}),\leavevmode\nobreak\ \leavevmode\nobreak\ W_{2}=1,$

we obtain

$\log_{2}W_{n}\geq\frac{n}{3}\cdot 2^{n}+o(n2^{n}).$

To bound the number of $2$-spreads from above, we utilize a correspondence
between $2$-spreads and perfect matchings in an appropriate hypergraph.

Let $\mathcal{G}_{n}$ be a $3$-uniform hypergraph with the vertex set
$F_{2}^{n}\setminus\\{\overline{0}\\}$ such that $\\{v_{1},v_{2},v_{3}\\}$ is
a hyperedge in $\mathcal{G}_{n}$ if and only if $v_{1}\oplus v_{2}\oplus
v_{3}=\overline{0}$. Note that the degree of each vertex in the hypergraph
$\mathcal{G}_{n}$ is $2^{n-1}-1$ and every perfect matching in
$\mathcal{G}_{n}$ is a $2$-spread in $F_{2}^{n}$.

Using Theorem 7, we have that

$W_{n}\leq(\mu(2^{n-1}-1))^{\frac{2^{n}-1}{3}}.$

Consequently,

$\log_{2}W_{n}\leq\frac{n}{3}\cdot 2^{n}+o(n2^{n}).$

∎

## Acknowledgements

The work of V. N. Potapov and A. A. Taranenko was carried out within the
framework of the state contract of the Sobolev Institute of Mathematics
(project no. FWNF-2022-0017).

### Data deposition information

The paper has no associated data.

### Conflict of interests

There are no competing interests.

## References

  * [1] Agievich, S.: Bent rectangles. In: Proceedings of the NATO advanced study institute on Boolean functions in cryptology and information security, NATO Science for Peace and Security Series D: Information and Communication Security 18, 3–22, Amsterdam (2008).
  * [2] Agievich, S. V.: On the continuation to bent functions and upper bounds on their number. Prikl. Diskr. Mat. Suppl. 13, 18–21 (2020)
  * [3] Agievich, S. V.: On the representation of bent functions by bent rectangles. In: Probabilistic Methods in Discrete Mathematics, Proceedings of the Fifth International Petrozavodsk Conference, pp. 121–135, Utrecht, Boston (2002)
  * [4] Baksova, I. P., Tarannikov, Yu. V.: The bounds on the number of partitions of the space $\textbf{F}_{2}^{m}$ into $k$-dimensional affine subspaces. Moscow University Mathematics Bulletin. 77, 131–135 (2022)
  * [5] Baksova, I. P., Tarannikov, Yu. V.: On a construction of bent functions. Surveys on Applied and Industrial Math. 27(1), 64–66 (2020)
  * [6] Canfield, E. R., Gao, Z., Greenhill, C., McKay, B. D., Robinson, R. W.: Asymptotic enumeration of correlation-immune Boolean functions. Cryptogr. Commun. 2(1), 111–126 (2010)
  * [7] Canteaut, A., Charpin, P.: Decomposing bent functions. IEEE Transactions on Information Theory, 49(8), 2004–2019 (Aug. 2003)
  * [8] Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press (2020)
  * [9] Carlet, C.: On the confusion and diffusion properties of Maiorana-McFarland’s and extended Maiorana-McFarland’s functions. In: Special Issue “Complexity Issues in Coding and Cryptography”, dedicated to Prof. H. Niederreiter on the occasion of his 60th birthday, pp. 182–204, J. of Complexity 20, (2004)
  * [10] Carlet, C.: Two New Classes of Bent Functions. In: Helleseth T. (eds) Advances in Cryptology — EUROCRYPT’93. EUROCRYPT 1993. Lecture Notes in Computer Science 765. Springer, Berlin, Heidelberg (1994)
  * [11] Carlet, C., Klapper, A.: Upper bounds on the number of resilient functions and of bent functions. In: Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium (2002)
  * [12] Carlet, C., Mesnager, S.: Four decades of research on bent functions. Des. Codes Cryptogr. 78(1), 5–50 (2016)
  * [13] Çeşmelioğlu, A., Meidl, W.: A construction of bent functions from plateaued functions. Des. Codes Cryptogr. 66(1–3), 231–242 (2013)
  * [14] Çeşmelioğlu, A., Meidl, W., Pott, A: Generalized Maiorana-McFarland class and normality of $p$-ary bent functions. Finite Fields Appl. 24, 105–117 (2013)
  * [15] Eberhard, S.: More on additive triples of bijections, https://arxiv.org/abs/1704.02407.
  * [16] Hodžić, S., Pasalic, E., Wei Y., Zhang F.: Designing plateaued Boolean functions in spectral domain and their classification, IEEE Transactions on Information Theory, 65(9), 5865–5879 (Sept. 2019)
  * [17] Khalyavin, A. V., Lobanov M. S., Tarannikov Yu. V.: On plateaued Boolean functions with the same spectrum support, Sib. Electron. Mat. Izv., 13, 1346–1368 (2016)
  * [18] Langevin, P., Leander, G.: Counting all bent functions in dimension eight 99270589265934370305785861242880. Des. Codes Cryptogr. 59(1–3), 193–205 (2011)
  * [19] Luria, Z.: New bounds on the number of $n$-queens configurations, https://arxiv.org/abs/1705.05225.
  * [20] McFarland, R. L.: A family of difference sets in non-cyclic groups. J. Combinatorial Theory Ser. A 15, 1–10 (1973)
  * [21] Mesnager, S.: Bent functions. Fundamentals and results. Springer, Cham (2016)
  * [22] Potapov, V. N.: A lower bound on the number of Boolean functions with median correlation immunity. In: Proceedings of XVI International Symposium “Problems of Redundancy in Information and Control Systems”, pp. 45–46. IEEE, Moscow, Russia (2019)
  * [23] Potapov, V. N.: An Upper Bound on the Number of Bent Functions. In Proceedings of XVII International Symposium “Problems of Redundancy in Information and Control Systems”, pp. 95–96. IEEE, Moscow, Russia (2021)
  * [24] Potapov, V. N., Taranenko, A. A., Tarannikov, Yu. V.: Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces, https://arxiv.org/abs/2108.00232
  * [25] Taranenko, A. A.: On the numbers of 1-factors and 1-factorizations of hypergraphs. Discrete Math. 340(4), 753–762 (2017)
  * [26] Taranenko, A. A.: Transversals, plexes, and multiplexes in iterated quasigroups. Electron. J. Combin. 25(4), Paper 4.30 (2018)
  * [27] Tarannikov, Yu. V.: On the values of the affine rank of the support of a spectrum of a plateaued function. Diskret. Mat. 18(3), 120–137 (2006)
  * [28] Tokareva, N.: Bent functions. Elsevier/Academic Press, Amsterdam (2015)
  * [29] Tokareva, N.: On the number of bent functions from iterative constructions: lower bounds and hypothesis. Adv. Math. Commun. 5(4), 609–621 (2011)