# Exploring Imaginary Coordinates: Disparity in the Shape of Quantum State
Space in Even and Odd Dimensions

Simon Morelli<EMAIL_ADDRESS>BCAM - Basque Center for Applied
Mathematics, Mazarredo 14, E48009 Bilbao, Basque Country - Spain  Santiago
Llorens<EMAIL_ADDRESS>Física Teòrica: Informació i Fenòmens
Quàntics, Departament de Física, Universitat Autònoma de Barcelona, 08193
Bellaterra, Spain  Jens Siewert<EMAIL_ADDRESS>Department of Physical
Chemistry and EHU Quantum Center, University of the Basque Country UPV/EHU,
E-48080 Bilbao, Spain  IKERBASQUE Basque Foundation for Science, E-48013
Bilbao, Spain

###### Abstract

The state of a finite-dimensional quantum system is described by a density
matrix that can be decomposed into a real diagonal, a real off-diagonal and
and an imaginary off-diagonal part. The latter plays a peculiar role. While it
is intuitively clear that some of the imaginary coordinates cannot have the
same extension as their real counterparts the precise relation is not obvious.
We give a complete characterization of the constraints in terms of tight
inequalities for real and imaginary Bloch-type coordinates. Our description
entails a three-dimensional Bloch ball-type model for the state space. We
uncover a surprising qualitative difference for the state-space boundaries in
even and odd dimensions.

##  I Introduction

From the very beginning, quantum mechanics was naturally represented in terms
of complex numbers. The state of a quantum system was identified with an
element of a complex Hilbert space Neumann (1927); Dirac (1930). Whether this
complex formulation is actually necessary or merely more elegant than a
hypothetical real version was an open question until very recently. Assuming
the dimension of the system to be bounded, it is not difficult to design
experiments that show that complex numbers are needed to describe the observed
data. If the dimension is bounded by two, a sequential Stern-Gerlach
experiment will suffice to come to this conclusion Sakurai and Napolitano
(2020). However, if no constraints on the dimension are assumed, it is always
possible to explain the measurement data of a single system by a real system
of higher dimension. This is even possible for two parties that are restricted
to local operations Pál and Vértesi (2008); McKague  _et al._ (2009). Only
recently it was shown that real quantum theory can be experimentally refuted
by designing an experiment in a quantum network involving three parties Renou
_et al._ (2021).

Thus, while complex numbers are intrinsically needed to describe quantum
mechanics, the role of ’imaginarity’ has yet to be fully understood, cf.,
e.g., Refs. Caves  _et al._ (2001); Wootters (2012); Chen  _et al._ (2023); Xu
(2023); Fernandes  _et al._ (2024). One might ask ’how real’ or ’how
imaginary’ a quantum state can be. The resource theory of imaginarity Hickey
and Gour (2018); Wu  _et al._ (2021a, b) measures imaginarity as a quantity
that cannot be increased under the set of free operations, real quantum
channels. We approach this fundamental question from a different perspective.
In analogy with the qubit Bloch ball description based on the three Pauli
matrices Bengtsson and Życzkowski (2017) we define a diagonal, a real off-
diagonal and an purely imaginary coordinate and ask what weight can be put on
these coordinates to be compatible with a positive operator. We then
completely characterize the set of attainable values for these coordinates and
obtain a Bloch ball-type model Bengtsson  _et al._ (2012) of the quantum state
space.

The Bloch representation of a qubit suggests the quantum space state to be
rotation invariant with respect to these three coordinates. As it turns out,
this only holds for the real diagonal and real off-diagonal coordinate in
arbitrary dimensions, while the imaginary coordinate has to be treated
separately. In this article we give a precise quantitative bound on the
imaginary Bloch length of a quantum state compared to both its real diagonal
and real off-diagonal Bloch components. Surprisingly, we thereby find a
qualitative difference between systems of even dimensions and systems of odd
dimensions. This difference is most pronounced for small system size and
vanishes in the asymptotic limit as one might expect. It is noteworthy that
the generic form for systems of odd dimension appears only from dimension 5
onwards.

##  II Notation

Every quantum state can be written in the following way,

$\displaystyle\rho\ =\ \frac{1}{d}(\mathds{1}_{d}+D+X+I)\ \ ,$ (1)

where $D$ is a diagonal matrix, $X$ a real off-diagonal matrix and $I$ a
purely imaginary (off-diagonal) and skew-symmetric matrix. The operators $D$,
$X$ and $I$ are all Hermitian, traceless, and orthogonal to each other, that
is $\operatorname{Tr}(DX)=\operatorname{Tr}(DI)=\operatorname{Tr}(XI)=0$. For
dimension $d=2$ we recover the Bloch representation in terms of the Pauli-
matrices, where $D=\langle\sigma_{Z}\rangle\sigma_{Z}$,
$X=\langle\sigma_{X}\rangle\sigma_{X}$ and
$I=\langle\sigma_{Y}\rangle\sigma_{Y}$. Let us introduce the quantities

$\displaystyle S_{\text{D}}=\sqrt{\frac{\operatorname{Tr}D^{2}}{d}},\qquad
S_{\text{X}}=\sqrt{\frac{\operatorname{Tr}X^{2}}{d}}\qquad
S_{\text{I}}=\sqrt{\frac{\operatorname{Tr}I^{2}}{d}}$

as weights of the diagonal, real off-diagonal and the imaginary part of the
state $\rho$. For a qubit we recover $S_{\text{D}}=\langle\sigma_{Z}\rangle$,
$S_{\text{X}}=\langle\sigma_{X}\rangle$ and
$S_{\text{I}}=\langle\sigma_{Y}\rangle$. It holds that

$\displaystyle\operatorname{Tr}\rho^{2}$ $\displaystyle\ =\
\frac{1}{d^{2}}(d+\operatorname{Tr}D^{2}+\operatorname{Tr}X^{2}+\operatorname{Tr}I^{2})$
$\displaystyle\ =\
\frac{1}{d}\left(1+S_{\text{D}}^{2}+S_{\text{X}}^{2}+S_{\text{I}}^{2}\right)\
\ .$ (2)

In dimensions $d>2$ the quantities $S_{\text{D}}$, $S_{\text{X}}$ and
$S_{\text{I}}$ can be seen as a coarse-graining of the Bloch vector of $\rho$.
Every quantum state $\rho$ can be expanded in an orthogonal matrix basis as

$\displaystyle\rho\ =\
\frac{1}{d}\left(\mathds{1}_{d}+\sum\limits_{k=1}^{d^{2}-1}v_{k}\mu_{k}\right)\
\ ,$ (3)

where we call a basis $\\{\mu_{k}\\}_{i=0}^{d^{2}-1}$ satisfying
$\mu_{0}=\mathds{1}_{d}$ and
$\operatorname{Tr}(\mu_{k}\mu_{l}^{\dagger})=d\delta_{kl}$ a Bloch basis
Bertlmann and Krammer (2008); Siewert (2022). The vector
$[\mathbf{v}]_{k}=v_{k}=\langle\mu_{k}\rangle$ is called the Bloch vector of
the state $\rho$, where $v_{0}=1$ is not included. Choosing a matrix basis
that includes only diagonal elements $\mu^{\text{d}}_{k}$, strictly real off-
diagonal elements $\mu^{\text{x}}_{k}$ and strictly imaginary elements
$\mu^{\text{i}}_{k}$, e.g., the generalized Gell-Mann matrices, the state can
be expanded as

$\displaystyle\rho\ =\
\frac{1}{d}\left(\mathds{1}_{d}+\sum\limits_{k=1}^{d-1}v^{\text{d}}_{k}\mu^{\text{d}}_{k}+\sum\limits_{k=1}^{d(d-1)/2}v^{\text{x}}_{k}\mu^{\text{x}}_{k}+\sum\limits_{k=1}^{d(d-1)/2}v^{\text{i}}_{k}\mu^{\text{i}}_{k}\right),$
(4)

where

$\displaystyle D=\sum\limits_{k=1}^{d-1}v^{\text{d}}_{k}\mu^{\text{d}}_{k}\
,\quad X=\sum\limits_{k=1}^{d(d-1)/2}v^{\text{x}}_{k}\mu^{\text{x}}_{k}\
,\quad I=\sum\limits_{k=1}^{d(d-1)/2}v^{\text{i}}_{k}\mu^{\text{i}}_{k}\ .$

It follows immediately that

$\displaystyle S_{\text{D}}^{2}=\sum\limits_{k=1}^{d-1}|v^{\text{d}}_{k}|^{2}\
,\quad S_{\text{X}}^{2}=\sum\limits_{k=1}^{d(d-1)/2}|v^{\text{x}}_{k}|^{2}\
,\quad S_{\text{I}}^{2}=\sum\limits_{k=1}^{d(d-1)/2}|v^{\text{i}}_{k}|^{2}\ .$

##  III Bounds

We now investigate which values of $S_{\text{D}}$, $S_{\text{X}}$ and
$S_{\text{I}}$ are compatible with a quantum state. The purity
$\operatorname{Tr}\rho^{2}$ of a quantum state is bounded by one and therefore
from Eq. (II) it follows that,

$\displaystyle S_{\text{D}}^{2}+S_{\text{X}}^{2}+S_{\text{I}}^{2}\ \leq\ d-1\
\ .$ (5)

For qubits this is the only restriction and the quantum set, that is, the set
$\\{(S_{\text{D}}(\rho),S_{\text{X}}(\rho),S_{\text{I}}(\rho):\rho\geq 0,\
\operatorname{Tr}\rho=1\\}$, is rotation invariant. We will see that the same
applies in higher dimension only for the values $S_{\text{D}}$ and
$S_{\text{X}}$, while the coordinate $S_{\text{I}}$ plays a special role. We
therefore start our investigation by bunching the two real coordinates
together to $S_{\text{R}}=\sqrt{S_{\text{D}}^{2}+S_{\text{X}}^{2}}$. It turns
out that the constraints we get for the $S_{\text{R}}$ and $S_{\text{I}}$
values are the only ones that exist, and that the real coordinates are subject
to rotational symmetry.

Every quantum state $\rho$ can be split into its real and imaginary parts,

$\displaystyle\rho\ =\ \frac{1}{d}(R+I)\ \ ,$ (6)

with $R=d(\rho+\rho^{T})/2$ and $I=d(\rho-\rho^{T})/2$ Hickey and Gour (2018).
We introduce the operator $R=\mathds{1}+D+X$, a real positive, symmetric
operator with $\operatorname{Tr}R=d$ which is orthogonal to the imaginary
part, $I$. Note that, while $R$ includes the identity $\mathds{1}$, the length
$S_{\text{R}}$ does not contain its contribution. That is,
$S_{\text{R}}^{2}=\operatorname{Tr}R^{2}/d-1$.

######  Proposition 1.

For every finite-dimensional quantum state it holds that the quantities
$S_{\text{R}}$ and $S_{\text{I}}$ satisfy

$\displaystyle S_{\text{I}}^{2}\ \leq\ 1+S_{\text{R}}^{2}\ \ .$ (7)

###### Proof.

It follows from the positivity of $\rho$ and $\rho^{T}$ that

$\displaystyle 0$ $\displaystyle\leq
d\operatorname{Tr}\left(\rho\rho^{T}\right)=\frac{1}{d}\operatorname{Tr}[(R+I)(R-I)]$
(8)
$\displaystyle=\frac{1}{d}(\operatorname{Tr}R^{2}-\operatorname{Tr}I^{2})=1+S_{\text{R}}^{2}-S_{\text{I}}^{2}\
\ .$

∎

(a) (b) (c)

Figure 1: The three figures display the bound of Eq. (5) in orange, the bound
of Eq. (7) in blue and the bound of Eq. (11) in green, (a) $d=3$, (b) $d=4$,
(c) $d=5$. Continuous lines show the actual bound, dotted lines are either not
valid or not tight.

The bound is saturated by states of the form

$\displaystyle\rho\ =\ \begin{pmatrix}\alpha_{2}&-i\alpha_{2}&&&&&\\\
i\alpha_{2}i&\alpha_{2}&&&&&\\\ &&\alpha_{4}&-i\alpha_{4}&&&\\\
&&i\alpha_{4}&\alpha_{4}&&&\\\ &&&&\ddots&&&\\\
&&&&&\alpha_{d}&-i\alpha_{d}\\\ &&&&&i\alpha_{d}&\alpha_{d}\end{pmatrix}$ (9)

for even dimension and states of the form

$\displaystyle\rho\ =\ \begin{pmatrix}\alpha_{2}&-i\alpha_{2}&&&&&&\\\
i\alpha_{2}&\alpha_{2}&&&&&&\\\ &&\alpha_{4}&-i\alpha_{4}&&&&\\\
&&i\alpha_{4}&\alpha_{4}&&&&\\\ &&&&\ddots&&&\\\
&&&&&\alpha_{d-1}&-i\alpha_{d-1}&\\\ &&&&&i\alpha_{d-1}&\alpha_{d-1}&\\\
&&&&&&&0\end{pmatrix}$ (10)

for odd dimensions if $S_{\text{R}}\geq 1/\sqrt{d-1}$. This is easy to see by
noting that in both cases
$\operatorname{Tr}R^{2}=\operatorname{Tr}I^{2}=d^{2}\sum\alpha_{k}^{2}$. This
bound is shown in blue in Figs. 1–3.

######  Proposition 2.

For a quantum state in odd dimension it holds that the quantities
$S_{\text{R}}$ and $S_{\text{I}}$ satisfy

$\displaystyle\sqrt{d}\ S_{\text{I}}\ \leq\ \sqrt{d-1}\ +\ S_{\text{R}}\ \ ,$
(11)

whenever $S_{\text{R}}\leq 1/\sqrt{d-1}$.

Before proving this bound in full generality, we first show the case
$S_{\text{R}}=0$. Every state satisfying this can be written as

$\displaystyle\rho\ =\ \frac{1}{d}(\mathds{1}+I)\ \ .$ (12)

The operator $\mathds{1}+I$ needs to be positive, that is, its eigenvalues
need to be positive. Let $U$ be a unitary diagonalizing $I$. Since unitary
transformations do not change the eigenvalues we can write

$\displaystyle U(\mathds{1}+I)U^{\dagger}\ =\ \mathds{1}+UIU^{\dagger}\ =\
\mathds{1}+I_{\text{diag}}\ \ .$ (13)

Therefore it must hold for the eigenvalues of $I$ that $|\lambda_{k}(I)|\leq
1$. Since $I$ is traceless it further holds that $\sum\lambda_{k}(I)=0$. The
quantity $\operatorname{Tr}I^{2}=\sum\lambda_{k}(I)^{2}$ is convex, hence
maximizing it gives a solution on the boundary. Under the constraints
$\sum\lambda_{k}(I)=0$ $|\lambda_{k}(I)|\leq 1$ we find the optimal solution
to be $\lambda_{2k-1}(I)=-\lambda_{2k}(I)=1$ with $\lambda_{d}(I)=0$ for odd
dimension. Therefore,

$\displaystyle S_{\text{I}}^{2}\ =\ \frac{1}{d}\operatorname{Tr}I^{2}\ \leq\
\frac{2}{d}\lfloor\frac{d}{2}\rfloor\ \ ,$ (14)

so that $S_{\text{I}}^{2}\leq 1$ for even dimension and
$S^{2}_{\text{I}}\leq(d-1)/d$ otherwise.

(a) (b) (c)

Figure 2: The parametrization of qudit states in Eqs. (1)–(4) defines a three-
dimensional model of the state space. The pure states saturate the bound in
Eq. (5). They are located on the surface of the model (shown in orange) and
have a minimum real coordinate $S_{\text{R}}\geq\sqrt{(d-2)/2}$. This is
because there is no pure-state projector corresponding to a superposition with
(nearly) purely imaginary off-diagonal elements. The shape of the mixed-state
surface part close to the imaginary axis varies as a function of the
dimension. (a) $d=3$: The boundary is described by the linear bound Eq. (11)
(green), the quadratic bound Eq. (7) (green) is not tight for any mixed state.
(b) $d=4$: For even dimensions the surface is given by the quadratic bound
(blue). (c) $d=5$: The generic case for odd dimensions where for small
$S_{\text{R}}$ the surface is conic (green) and for $S_{\text{R}}\geq
1/\sqrt{d-1}$ saturates the quadratic bound (blue).

Subsequently we prove Proposition 2 in the general case.

###### Proof.

We know that $I$ is a skew-symmetric matrix and that it has the same
eigenvalues as its transpose. Therefore the eigenvalues of $I$ come in pairs
with opposite sign, with an additional 0 for odd dimensions. Let
$\lambda_{k}(I)$ be ordered such that $\lambda_{2k}(I)=-\lambda_{2k-1}(I)$. We
also know that both $R+I$ and $R-I$ are positive matrices. Let $U$ be a
unitary diagonalizing $I=UI_{\text{diag}}U^{\dagger}$. It then holds that
$U^{\dagger}RU\pm I_{\text{diag}}\geq 0$.

Since $R$ and $I$ are orthogonal to each other, also $\tilde{R}=U^{\dagger}RU$
and $I_{\text{diag}}$ are orthogonal,

$\displaystyle 0$
$\displaystyle=\operatorname{Tr}(RI)=\operatorname{Tr}(RUI_{\text{diag}}U^{\dagger})=\operatorname{Tr}(U^{\dagger}RUI_{\text{diag}})=$
$\displaystyle=\operatorname{Tr}(\tilde{R}I_{\text{diag}})=\sum\limits_{k=1}^{d}\tilde{R}_{kk}(I_{\text{diag}})_{kk}=\sum\limits_{k=1}^{d}\tilde{R}_{kk}\lambda_{k}(I)\
.$ (15)

It holds that $\tilde{R}_{kk}\geq|\lambda_{k}(I)|$ and it is known that the
diagonal $\tilde{R}_{kk}$ is majorized by the eigenvalues
$\lambda_{k}(\tilde{R})=\lambda_{k}(R)$. It then holds that
$\sum\limits_{k=1}^{d}\tilde{R}_{kk}^{2}\leq\sum\limits_{k=1}^{d}\lambda_{k}(R)^{2}$
and we conclude

$\displaystyle\operatorname{Tr}I^{2}=\sum\lambda_{k}(I)^{2}\leq\sum\limits_{k=1}^{d-1}\tilde{R}_{kk}^{2}\leq\sum\limits_{k=1}^{d-1}\lambda_{k}(R)^{2}\leq\operatorname{Tr}R^{2}\
.$ (16)

With this we recover the previous result. The first and the second inequality
are saturated if all eigenvalues satisfy
$\lambda_{2k-1}(I)=-\lambda_{2k}(I)=\lambda_{2k-1}(R)=\lambda_{2k}(R)$. For
the third inequality to be saturated we have to choose $\lambda_{d}(R)=0$ in
odd dimensions. But this implies $S_{\text{R}}\geq 1/\sqrt{d-1}$ so that the
bound cannot be tight for $S_{\text{R}}<1/\sqrt{d-1}$. Set now the smallest
eigenvalue of $R$ $\lambda_{d}(R)=t\leq 1$, it immediately follows that
$\operatorname{Tr}R^{2}\geq d(d-2t+t^{2})/(d-1)$ where the minimum is attained
for $\lambda_{k}(R)=(d-t)/(d-1)$. For a given $\operatorname{Tr}R^{2}$ it must
therefore hold that

$\displaystyle t\ \geq\
1-\frac{\sqrt{(d-1)\operatorname{Tr}R^{2}-d^{2}+d}}{\sqrt{d}}\ =\
1-\sqrt{d-1}S_{\text{R}}\ .$ (17)

It now holds in odd dimensions for $S_{\text{R}}\leq 1/\sqrt{d-1}$,

$\displaystyle dS_{\text{I}}^{2}$
$\displaystyle=\operatorname{Tr}I^{2}=\sum\lambda_{k}(I)^{2}\leq\sum\limits_{k=1}^{d-1}\lambda_{k}(R)^{2}=\operatorname{Tr}R^{2}-t^{2}\leq$
$\displaystyle\leq
d+dS_{\text{R}}^{2}-(1-\sqrt{d-1}S_{\text{R}})^{2}=(\sqrt{d-1}+S_{\text{R}})^{2},$

which proves the result.

∎

The inequality (11) for odd dimensions and $S_{\text{R}}\leq 1/\sqrt{d-1}$ is
saturated by states of the form

$\displaystyle\rho\ =\ \begin{pmatrix}\alpha&-i\alpha&&&&&&\\\
i\alpha&\alpha&&&&&&\\\ &&\alpha&-i\alpha&&&&\\\ &&i\alpha&\alpha&&&&\\\
&&&&\ddots&&&\\\ &&&&&\alpha&-i\alpha&\\\ &&&&&i\alpha&\alpha&\\\
&&&&&&&1-(d-1)\alpha\end{pmatrix}$ (18)

with $1/(d-1)\geq\alpha\geq 1/d$. To see this it suffices to note that
$\operatorname{Tr}R^{2}=d^{2}(d(d-1)\alpha^{2}-2(d-1)\alpha+1)$ and
$\operatorname{Tr}I^{2}=d^{2}(d-1)\alpha^{2}$. Figures 1–3 show this bound in
green.

For even dimension $d>2$, Eqs. (5) and (7) describe the boundary, they
intersect at $S_{\text{R}}=\sqrt{(d-2)/2}$. For odd dimension the boundary
(for $S_{\text{R}}\leq 1/\sqrt{d-1}$) is described by Eq. (11), it
tangentially touches the bound in Eq. (7) at $S_{\text{R}}=1/\sqrt{d-1}$.

Going back to our original coordinates $S_{\text{D}}$, $S_{\text{X}}$ and
$S_{\text{I}}$, we immediately find the following result.

######  Corollary 1.

The three quantities $S_{\text{D}}$, $S_{\text{X}}$ and $S_{\text{I}}$ satisfy
the bounds

$\displaystyle S_{\text{I}}^{2}$ $\displaystyle\ \leq\
1+S_{\text{D}}^{2}+S_{\text{X}}^{2}$ (19a) $\displaystyle\sqrt{d}S_{\text{I}}$
$\displaystyle\ \leq\ \sqrt{d-1}+\sqrt{S_{\text{D}}^{2}+S_{\text{X}}^{2}}\ \
,$ (19b)

where the last inequality holds only for
$S_{\text{D}}^{2}+S_{\text{X}}^{2}\leq 1/(d-1)$.

###### Proof.

The bounds follows trivially from Eq. (7) and (11) by replacing
$S_{\text{R}}^{2}=S_{\text{D}}^{2}+S_{\text{X}}^{2}$. ∎

######  Proposition 3.

The bounds in Corollary 1 define a tight upper bound. Together with Eq. (5)
they are optimal, in the sense that there exist no further constraints on the
quantities $S_{\text{D}}$, $S_{\text{X}}$ and $S_{\text{I}}$ that do not
trivially follow from them.

###### Proof.

The states in Eq. (9),(10) and (18) have no real off-diagonal contribution and
thus saturate the bounds in Corollary 1 for $S_{\text{X}}=0$, together with
the pure states
$\beta\left|\right.\\!{0}\\!\left.\right\rangle+i\sqrt{1-\beta^{2}}\left|\right.\\!{1}\\!\left.\right\rangle$,
where $0\leq\beta\leq 1$.

We will now define a continuous orthogonal transformation that shifts weight
from the diagonal component to the real off-diagonal component as long as
$S_{\text{D}}>0$. Note that any orthogonal (i.e., real) transformation leaves
the coordinates $S_{\text{R}}$ and $S_{\text{I}}$ unchanged. Consider an
orthogonal transformation
$O_{kl}(\theta)=\cos{\theta}(|{k}\rangle\\!\langle{k}|+|{l}\rangle\\!\langle{l}|)+\sin{\theta}(|{k}\rangle\\!\langle{l}|-|{l}\rangle\\!\langle{k}|)$
acting on the subspace spanned by the states
$\\{\left|\right.\\!{k}\\!\left.\right\rangle,\left|\right.\\!{l}\\!\left.\right\rangle\\}$.
Start acting with this transformation on the first and the last entry until
either one of the new diagonal entries becomes $1/d$. If it is the last entry
we perform a second orthogonal transformation from
$\left|\right.\\!{0}\\!\left.\right\rangle$ to
$\left|\right.\\!{d-2}\\!\left.\right\rangle$ until one of them reaches $1/d$.
If it is the first entry we apply the transformation from
$\left|\right.\\!{1}\\!\left.\right\rangle$ to
$\left|\right.\\!{d-1}\\!\left.\right\rangle$. We repeat this process until
all diagonal entries are equal to $1/d$. This procedure continuously shifts
weight from the diagonal coordinate $S_{\text{D}}$ onto the real off-diagonal
coordinate $S_{\text{X}}$ until the diagonal coordinate vanishes. The orbits
of the states in Eqs. (9), (10) and (18) form the boundary. This concludes the
proof.

∎

Figure 3: The figure shows the bound of Eq. (5) in orange, the bound of Eq.
(7) in blue and the bound of Eq. (11) in green for dimension $d=101$.

##  IV Bloch ball for a qudit

We now discuss the geometric implications of our investigation. In recent
years considerable effort was devoted to the question of constructing models
for the quantum state space of dimension $d$, e.g., Refs. Bengtsson  _et al._
(2012); Eltschka  _et al._ (2021); Khvedelidze  _et al._ (2021); Levitt and
Bengs (2021); Rau (2021); Jarov and Raamsdonk (2023); Sharma  _et al._ (2024);
Morelli  _et al._ (2024); Shravan  _et al._ (2023). That is, one asks for the
shape of this $(d^{2}-1)$-dimensional object if it is represented in a lower
dimension, thereby maintaining as many geometric properties of the original
state space as possible. Because of the reduction in the number of parameters
for dimensions $d\geq 3$ it is clear that any model, while correctly
displaying some of the properties of the state space, will suffer from a loss
of information and inadequately represent other features. Consequently, any
model is the result of a judicious choice of the coordinates, depending on the
set of properties that are to be maintained. The corresponding objects may
have rather different shapes.

Our work provides a striking illustration for these considerations. As is
evident from Fig. 2, our parametrization of the qudit state Eqs. (1), (II) in
imaginary, real diagonal and off-diagonal coordinates leads to a three-
dimensional model for the qudit state space for all $d\geq 2$. While, e.g.,
the model in Ref. Eltschka  _et al._ (2021) emphasizes the simplex of diagonal
states (in $d=3$) the present model focuses on the bounds for the imaginary
coordinates and, for example, is not convex for $d\geq 3$. Note that convexity
is restored for $d=3$ if one uses just one real coordinate $S_{R}$ (instead of
$S_{X}$ and $S_{D}$), as can be observed in Fig. 1 (a).

Another salient feature of the present model is its rotation invariance about
the imaginary axis, cf. Fig. 2. It is a direct consequence of the unitary
invariance of the purity, Eq. (II): Any transformation that leaves $S_{I}$
unchanged, necessarily preserves also the radius $S_{\text{R}}$ in the real
plane.

Intriguingly, the bounds in Eqs. (7), (11) reveal that the geometry of the
state space boundary is different in even vs. odd dimensions: While for odd
dimensions there is always a flat surface part (of mixed states) close to the
most distant point on the imaginary axis, the surface is curved in the
corresponding region for even dimensions, cf. Fig. 2 (b). We note that the
concave part of the model in $d=3$ is completely described by the linear bound
Eq. (11). Hence the first dimension for which the generic odd-$d$ behavior is
observed is $d=5$: In the vicinity of $S_{\text{I}}=\sqrt{(d-1)/d}$ the linear
bound describes the surface before the quadratic bound, Eq. (7), takes effect
for $S_{\text{R}}=1/\sqrt{d-1}$. The linear surface part remains present for
all odd dimensions but becomes negligibly small for large $d$, see Fig. 3. At
the same time the restriction imposed by Eq. (7) becomes more stringent. The
respective part in $\left(S_{\text{R}},S_{\text{I}}\right)$ coordinates that
remains compatible with a quantum state decreases, until asymptotically only
half of the original circular area defined by the purity bound in Eq. (II)
remains, see Fig. 3.

##  V Relation to resource theory

Recently, the resource theory of imaginarity has received considerable
attention Hickey and Gour (2018); Wu  _et al._ (2021a, b). A measure of
imaginarity is a quantity that is non-increasing under real quantum channels,
i.e., completely positive and trace-preserving (CPTP) maps that allow a
description with purely real Kraus operators. The robustness of imaginarity is
defined as $\mathcal{I}(\rho)=\|I/d\|_{1}$ and the geometric measure of
imaginarity is defined as
$\mathcal{I}_{G}(\psi)=1-\sup_{\phi\in\mathcal{R}}|\langle\phi|\psi\rangle|^{2}$,
with the convex roof extension for mixed states. While these quantities are
imaginarity monotones, our imaginary coordinate $\|\rho_{\text{I}}\|_{2}$ is
not an imaginary measure Chen  _et al._ (2023). This stems from the fact that
the Hilbert-Schmidt norm is generally not contractive under CPTP maps for
dimension larger than two Ozawa (2000), in contrast to the trace norm Ruskai
(1994). Our goal is not the study of imaginarity as a resource, rather we
characterize the constraints on coordinates describing the quantum state
space. Nonetheless, our analysis establishes a relation between the real
weight and the robustness of imaginarity $\mathcal{I}$ for odd dimensions. For
$S_{R}\geq 1/\sqrt{d-1}$ there exist states that achieve $\mathcal{I}=1$ (cf.
the states saturating the bound in Proposition 1), while for $S_{R}=0$ no
state can reach full imaginarity. The question remains open for the region
$0<S_{R}<1/\sqrt{d-1}$, as none of our presented states reaches maximum
imaginarity. On the other hand, for even dimensions, no restriction exists
concerning real weight and imaginarity, showing again remarkable differences
between even and odd dimensions.

##  VI Conclusion

We generalize the Bloch coordinates of a qubit describing the diagonal, real
off-diagonal and imaginary part of a quantum state to arbitrary finite
dimensions. We completely characterize the set of coordinates compatible with
a quantum state. While for the simplest quantum system of a qubit these
coordinates are interchangeable, this property is lost in higher dimensions.
The imaginary coordinate plays a distinctive role and is bounded with respect
to the other coordinates. Surprisingly, this bound exhibits a qualitative
difference between even and odd dimensions, where the general bound for odd
dimensions is first observed in dimension 5. With these findings we obtain a
three-dimensional model of the generally higher-dimensional quantum state
space that joins the already established models. It further illustrates the
peculiar properties of finite-dimensional quantum state spaces and represents
an important step towards their understanding.

##  VII Acknowledgements

The authors thank Asier Izquierdo for discussions. S.M. was supported by the
Basque Government through IKUR strategy and through the BERC 2022-2025 program
and by the Ministry of Science and Innovation: BCAM Severo Ochoa accreditation
CEX2021-001142-S / MICIN / AEI / 10.13039/501100011033, PID2020-112948GB-I00
funded by MCIN/AEI/10.13039/501100011033 and by ”ERDF A way of making Europe”.
S.L. acknowledges funding from the Spanish MICINN with funding from European
Union NextGenerationEU (PRTRC17.I1) and the Generalitat de Catalunya, and from
the Spanish Agencia Estatal de Investigación and the MICCINN (grant
PID2022-141283NB-I00). J.S. was supported by Grant PID2021-126273NB-I00 funded
by MCIN/AEI/10.13039/501100011033 and by ”ERDF A way of making Europe” as well
as by the Basque Government through Grant No. IT1470-22.

## References

  * Neumann (1927) J. v. Neumann,  _Mathematische Begründung der Quantenmechanik,_Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse , 1 (1927).
  * Dirac (1930) P. A. M. Dirac,  _The Principles of Quantum Mechanics_ (Clarendon Press, Oxford, 1930).
  * Sakurai and Napolitano (2020) J. J. Sakurai and J. Napolitano,  _Modern Quantum Mechanics_ , 3rd ed. (Cambridge University Press, 2020).
  * Pál and Vértesi (2008) K. F. Pál and T. Vértesi,  _Efficiency of higher-dimensional Hilbert spaces for the violation of Bell inequalities,_Physical Review A 77 (2008).
  * McKague  _et al._ (2009) M. McKague, M. Mosca, and N. Gisin,  _Simulating quantum systems using real hilbert spaces,_Physical Review Letters 102 (2009).
  * Renou  _et al._ (2021) M.-O. Renou, D. Trillo, M. Weilenmann, T. P. Le, A. Tavakoli, N. Gisin, A. Acín, and M. Navascués,  _Quantum theory based on real numbers can be experimentally falsified,_Nature 600, 625 (2021).
  * Caves  _et al._ (2001) C. Caves, C. Fuchs, and P. Rungta,  _Entanglement of Formation of an Arbitrary State of Two Rebits ,_Foundation of Physics Letters 114, 199 (2001).
  * Wootters (2012) W. Wootters,  _Entanglement Sharing in Real-Vector-Space Quantum Theory,_Found. Phys. 42, 19 (2012).
  * Chen  _et al._ (2023) Q. Chen, T. Gao, and F. Yan,  _Measures of imaginarity and quantum state order,_Science China Physics, Mechanics & Astronomy 66 (2023).
  * Xu (2023) J. Xu,  _Imaginarity of Gaussian states,_Physical Review A 108 (2023).
  * Fernandes  _et al._ (2024) C. Fernandes, R. Wagner, L. Novo, and E. F. Galvão,  _Unitary-invariant witnesses of quantum imaginarity,_ (2024), arXiv:2403.15066 [quant-ph].
  * Hickey and Gour (2018) A. Hickey and G. Gour,  _Quantifying the imaginarity of quantum mechanics,_Journal of Physics A: Mathematical and Theoretical 51, 414009 (2018).
  * Wu  _et al._ (2021a) K.-D. Wu, T. V. Kondra, S. Rana, C. M. Scandolo, G.-Y. Xiang, C.-F. Li, G.-C. Guo, and A. Streltsov,  _Operational resource theory of imaginarity,_Physical Review Letters 126 (2021a).
  * Wu  _et al._ (2021b) K.-D. Wu, T. V. Kondra, S. Rana, C. M. Scandolo, G.-Y. Xiang, C.-F. Li, G.-C. Guo, and A. Streltsov,  _Resource theory of imaginarity: Quantification and state conversion,_Physical Review A 103 (2021b).
  * Bengtsson and Życzkowski (2017) I. Bengtsson and K. Życzkowski,  _Geometry of Quantum States: An Introduction to Quantum Entanglement, 2nd edition_ (Cambridge University Press, 2017).
  * Bengtsson  _et al._ (2012) I. Bengtsson, S. Weis, and K. Życzkowski,  _Geometry of the Set of Mixed Quantum States: An Apophatic Approach_ (Springer Basel, 2012) p. 175.
  * Bertlmann and Krammer (2008) R. A. Bertlmann and P. Krammer,  _Bloch vectors for qudits,_Journal of Physics A 41, 235303 (2008).
  * Siewert (2022) J. Siewert,  _On orthogonal bases in the Hilbert-Schmidt space of matrices,_Journal of Physics Communications 6 (2022).
  * Eltschka  _et al._ (2021) C. Eltschka, M. Huber, S. Morelli, and J. Siewert,  _The shape of higher-dimensional state space: Bloch-ball analog for a qutrit,_Quantum 5, 485 (2021).
  * Khvedelidze  _et al._ (2021) A. Khvedelidze, D. Mladenov, and A. Torosyan,  _Parameterizing qudit states,_Discrete and Continuous Models and Applied Computational Science 29, 361 (2021).
  * Levitt and Bengs (2021) M. H. Levitt and C. Bengs,  _Hyperpolarization and the physical boundary of Liouville space,_Magnetic Resonance 2, 395 (2021).
  * Rau (2021) A. R. P. Rau,  _Symmetries and Geometries of Qubits, and Their Uses,_Symmetry 13 (2021).
  * Jarov and Raamsdonk (2023) S. Jarov and M. V. Raamsdonk,  _Mapping the space of quantum expectation values,_ (2023), arXiv:2310.13111 [quant-ph].
  * Sharma  _et al._ (2024) G. Sharma, S. Ghosh, and S. Sazim,  _Bloch sphere analog of qudits using Heisenberg-Weyl Operators,_Physica Scripta 99, 045105 (2024).
  * Morelli  _et al._ (2024) S. Morelli, C. Eltschka, M. Huber, and J. Siewert,  _Correlation constraints and the Bloch geometry of two qubits,_Physical Review A 109 (2024).
  * Shravan  _et al._ (2023) S. Shravan, S. Morelli, O. Gühne, and S. Imai,  _Geometry of two-body correlations in three-qubit states,_ (2023), arXiv:2309.09549 [quant-ph].
  * Ozawa (2000) M. Ozawa,  _Entanglement measures and the HilbertSchmidt distance,_Physics Letters A 268, 158 (2000).
  * Ruskai (1994) M. B. Ruskai,  _Beyond strong superadditivity? Improved bounds on the contraction of generalized relative entropy,_Reviews in Mathematical Physics 06, 1147 (1994).


# Partially Ordered Sets Corresponding to the Partition Problem

Susumu Kubo

###### Abstract

The partition problem is a well-known basic NP-complete problem. We mainly
consider the optimization version of it in this paper. The problem has been
investigated from various perspectives for a long time and can be solved
efficiently in practice. Hence, we might say that the only remaining task is
to decide whether the problem can be solved in polynomial time in the number
$n$ of given integers.

We propose two partially ordered sets (posets) and present a novel methodology
for solving the partition problem. The first poset is order-isomorphic to a
well-known poset whose structures are related to the solutions of the subset
sum problem, while the second is a subposet of the first and plays a crucial
role in this paper. We first show several properties of the two posets, such
as size, height and width (the largest size of a subset consisting of
incomparable elements). Both widths are the same and $O(2^{n}/n^{3/2})$ for
$n$ congruent to $0$ or $3$ (mod $4$). This fact indicates the hardness of the
partition problem. We then prove that in general all the candidate solutions
correspond to the elements of the second poset, whose size is
$2^{n}-2\binom{n}{\lfloor n/2\rfloor}$. Since a partition corresponds to two
elements of the poset, the number of the candidate partitions is half of it,
that is, $2^{n-1}-\binom{n}{\lfloor n/2\rfloor}$. We finally prove that the
candidate solutions can be reduced based on the partial order. In particular,
we give several polynomially solvable cases by considering the minimal
elements of the second poset.

Our approach offers a valuable tool for structural analysis of the partition
problem and provides a new perspective on the P versus NP problem.

##  1 Introduction

The partition problem is formulated as follows: given positive integers
$c_{1},\ldots,c_{n}$, the objective is to decide whether there exists a subset
$S$ of $\\{1,\ldots,n\\}=:[n]$ such that $\Delta(S)=0$, where

$\Delta(S):=\sum_{i\in S}c_{i}-\sum_{i\in[n]\setminus S}c_{i}.$ (1)

In this paper, we mainly consider the optimization version of it: to find a
subset $S$ of $[n]$ that minimizes the absolute value $|\Delta(S)|$. Without
loss of generality, we can assume that the integers are indexed in non-
increasing order, that is,

$c_{1}\geq c_{2}\geq\cdots\geq c_{n},$

and that $c_{n}\geq 0$ for the simplicity of proof though originally
$c_{n}>0$.

The partition problem is one of Karp’s 21 NP-complete problems [11] and is
also one of Garey and Johnson’s six basic NP-complete problems [5]. Therefore,
the optimization version is known to be NP-hard. It has important applications
such as task scheduling [3, 21], and is equivalent to the two-identical-
parallel-machine scheduling problem to minimize the makespan.

The problem has been investigated from various perspectives. Several optimal
algorithms give exact solutions in exponential time in $n$ [5, 8, 12, 17].
Moreover, a variety of heuristic and metaheuristic algorithms have been
developed [1, 4, 9, 10, 16]. Thus, we can solve the problem efficiently in
practice. An “easy-hard” phase transition was observed and the solution
structure has been studied based on the notion and tools from statistical
mechanics [2, 6, 7, 15]. An algebraic expression was presented based on the
max-plus algebra [13]. We might say that the only remaining task is to decide
whether the problem can be solved in polynomial time in $n$.

Furthermore, the number of solutions to the subset sum problem, a special case
of which is the partition problem, has been studied. The subset sum problem
with positive inputs is to decide whether there exists a subset $S$ of $[n]$
such that

$\sum_{i\in S}c_{i}=t,$

where $t$ is a given constant, a target. Let $N(\\{c_{1},...,c_{n}\\},t)$
denote the number of the solutions. It is known that

$N\left(\\{c_{1},...,c_{n}\\},t\right)\leq
N\left([n],\left\lfloor\frac{n(n+1)}{4}\right\rfloor\right)$

[14, 19]. The number $N\left([n],\lfloor n(n+1)/4\rfloor\right)$ is Sequence
A025591 in the On-Line Encyclopedia of Integer Sequences [22] and is known to
be $O(2^{n}/n^{3/2})$ for $n$ congruent to $0$ or $3$ (mod $4$)[20]. The
inequality is established using the properties of a partially ordered set
(poset).

The poset is a well-known poset, denoted by $M(n)$ in Stanley’s paper [19,
Subsection 4.1.2]. The elements of $M(n)$ are all the subsets of $[n]$. Let
$A$ and $B$ be two subsets of $[n]$ with elements $a_{1},a_{2},\ldots,a_{j}$
and $b_{1},b_{2},\ldots,b_{k}$, respectively, and assume that the elements of
$A$ and $B$ are indexed in decreasing order. The partial order is defined as
follows: $A\leqslant B$ if and only if $j\leq k$ and $a_{i}\leq b_{i}$ for
$i\in[j]$.

To the best of our knowledge, there is no work applying the poset to the
partition problem in terms of optimization.

#### Main results

To define two posets that correspond to the partition problem, we first
consider the set $\mathbb{R}^{n}$ of $n$-dimensional vectors of real numbers.
Let $\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ and
$\mathbf{y}=(y_{1},\ldots y_{n})\in\mathbb{R}^{n}$, and define a partial order
on the set: $\mathbf{x}\preceq\mathbf{y}$ if and only if

$\displaystyle x_{1}$ $\displaystyle\leq y_{1},$ $\displaystyle x_{1}+x_{2}$
$\displaystyle\leq y_{1}+y_{2},$ $\displaystyle\;\;\vdots$ $\displaystyle
x_{1}+x_{2}+\cdots+x_{n}$ $\displaystyle\leq y_{1}+y_{2}+\cdots+y_{n}.$

In other words, $\mathbf{x}\preceq\mathbf{y}$ means that any entry of the
cumulative sum of $\mathbf{x}$ is less than or equal to the corresponding one
of $\mathbf{y}$.

Let us define a poset $P(n)$ that corresponds to the partition problem. Let
$P(n)$ be the set of all $n$-dimensional vectors with entries in $\\{1,-1\\}$.
The size of $P(n)$ is of course $2^{n}$. The partial order is defined to be
the restriction of $\preceq$ on $P(n)$, denoted by $\preceq_{P}$. The poset is
order-isomorphic to $M(n)$ under the mapping $f$ from $P(n)$ to $M(n)$ defined
by the following rule: Given $\mathbf{v}=(v_{1},\dots,v_{n})\in P(n)$, we have
that $i\in f(\mathbf{v})$ if and only if $v_{n+1-i}=1$.

######  Example.

The Hasse diagrams of $M(5)$ and $P(5)$ are shown in Figures 1 and 2
respectively. We can see that the two posets are order-isomorphic under $f$.
For example, $f((1,-1,1,-1,-1))=\\{5,3\\}$. Note that a partial order is shown
horizontally due to space limitation, though it is usually shown vertically.
The horizontal position indicates rank.

Figure 1: The Hasse diagram of $M(5)$. Figure 2: The Hasse diagram of $P(5)$.

Let us define another poset $Q(n)$ to be the subset of $P(n)$ obtained by
deleting from $P(n)$ the elements that are less than or greater than
$\mathbf{0}$, that is, $Q(n)=P(n)\setminus\\{{\mathbf{v}\in
P(n)}\colon{\mathbf{v}\preceq\mathbf{0}}\allowbreak\text{or
}{\mathbf{0}\preceq\mathbf{v}}\\},$ where $\mathbf{0}=(0,\dots,0)$. The
partial order is defined to be the restriction of $\preceq_{P}$ on $Q(n)$,
denoted by $\preceq_{Q}$. The poset $Q(n)$ can be constructed by truncating
the upper part and lower part of $P(n)$. The size of $Q(n)$ is proved to be
$2^{n}-2\binom{n}{\lfloor n/2\rfloor}$.

######  Example.

Let us consider $Q(n)$ for $n\leq 6$. We can easily see that
$Q(1)=Q(2)=\emptyset$ and $Q(3)=\\{(1,-1,-1),(-1,1,1)\\}$, the elements of
which are incomparable. The Hasse diagrams of $Q(4),Q(5)$ and $Q(6)$ are shown
in Figure 3.

(a) $Q(4)$

(b) $Q(5)$

(c) $Q(6)$

Figure 3: The Hasse diagrams of $Q(4),Q(5)$ and $Q(6)$.

To investigate the relationship between the partition problem and the posets
$P(n)$ and $Q(n)$, we rewrite the difference (1) of the partition problem.
There is a one-to-one correspondence between $P(n)$ and the set of all subsets
of $[n]$. We introduce a mapping $\mathbf{p}$ from $2^{[n]}$ to $P(n)$. To
each subset $S$ of $[n]$, we assign $\mathbf{p}(S)=(p_{1},\dots,p_{n})$
defined by

$p_{i}=\begin{cases}\phantom{-}1&\text{ if }i\in S\\\ -1&\text{ if }i\notin
S.\end{cases}$

Let $\mathbf{c}=(c_{1},c_{2},\ldots,c_{n})$. Then

$\Delta(S)=\mathbf{p}(S)\cdot\mathbf{c},$

where the dot indicates the usual inner product. Note that
$\mathbf{p}([n]\setminus S)=-\mathbf{p}(S)$ and hence $\Delta([n]\setminus
S)=-\mathbf{p}(S)\cdot\mathbf{c}$, the absolute value of which is equal to
$\lvert\Delta(S)\rvert$. A pair of two elements $\mathbf{p}(S)$ and
$-\mathbf{p}(S)$ corresponds to the partition $\\{S,\;[n]\setminus S\\}$. We
can show that we have only to consider $Q(n)$ for solving the partition
problem.

######  Theorem 1.

The candidate solutions to the partition problem are the subsets that
correspond to the elements of $Q(n)$.

The number of the candidate partitions is half of the size of $Q(n)$, i.e.,
$2^{n-1}-\binom{n}{\lfloor n/2\rfloor}$, since a partition comprises a subset
and its complement. Furthermore, the candidate solutions can be reduced based
on the partial order of $Q(n)$.

######  Theorem 2.

Given an instance $\mathbf{c}$ of the partition problem, the following holds:

  1. (1)

If $\mathbf{p}(S)\cdot\mathbf{c}\geq 0$ for some subset $S$ of $[n]$
satisfying $\mathbf{p}(S)\in Q(n)$, then
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$
for any $S^{\prime}$ that satisfies
$\mathbf{p}(S^{\prime})\preceq_{Q}-\mathbf{p}(S)$ or
$\mathbf{p}(S)\preceq_{Q}\mathbf{p}(S^{\prime})$.

  2. (2)

If $\mathbf{p}(S)\cdot\mathbf{c}\leq 0$ for some subset $S$ of $[n]$
satisfying $\mathbf{p}(S)\in Q(n)$, then
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$
for any $S^{\prime}$ that satisfies
$\mathbf{p}(S^{\prime})\preceq_{Q}\mathbf{p}(S)$ or
$-\mathbf{p}(S)\preceq_{Q}\mathbf{p}(S^{\prime})$.

Using this result, we provide several polynomially solvable cases by
considering the minimal elements of $Q(n)$.

######  Theorem 3.

Let $\mathbf{v}$ be a minimal element of $Q(n)$. If
$\mathbf{v}\cdot\mathbf{c}\geq 0$, then the subset $S$ such that
$\mathbf{p}(S)=\mathbf{v}$ is a solution and the optimal value is
$\mathbf{v}\cdot\mathbf{c}$.

All the minimal elements are explicitly obtained, as shown in Proposition 15.
This is a generalization of the obvious fact that the subset $\\{1\\}$ is a
solution and the optimal value is $c_{1}-(c_{2}+\cdots+c_{n})$ if
$c_{1}-(c_{2}+\cdots+c_{n})\geq 0$, which is the case where the minimal
element is $(1,-1,\dots,-1)$.

Our results are very simple once we realize them. However, the realization was
the hard part. The key points are to use $\\{1,-1\\}$ instead of $\\{1,0\\}$
when defining the posets and not to limit the candidate solutions to half by
assuming, for instance, that a subset of $[n]$ always contains $1$. We believe
that our approach offers a valuable tool for structural analysis of the
partition problem and provides a new perspective on the P versus NP problem.

#### The organization in the paper

The paper is organized as follows. In Section 2 we provide some fundamental
concepts relevant to posets and the properties of $P(n)$ and $Q(n)$. In
Section 3 we explore the relationship between the partition problem and the
posets and prove our main results.

##  2 Two posets corresponding to the partition problem

###  2.1 Preliminaries

In this subsection, we review some standard facts on posets and give some
properties of the poset $M(n)$.

Let $(P,\preceq)$ be a finite poset. We simply denote the poset by $P$ and
define the relation $\prec$ by $x\prec y$ if and only if $x\preceq y$ and
$x\neq y$. A subset of $P$ is a chain if it is totally ordered, and a subset
of $P$ is an antichain if no pair of elements in it is comparable. A chain is
a maximal chain if no other element can be added to it without losing the
property of being totally ordered. The height (width) of $P$ is the largest
size of a chain (antichain, resp.) in $P$. An element of $P$ is a maximal
(minimal) element if it is not less (greater, resp.) than any other element.
An element of $P$ is the greatest (least) element if it is greater (less,
resp.) than any other element.

A poset $P$ is graded111There are several competing definitions for graded
posets. if it is equipped with a rank function $\rho$ from $P$ to $\mathbb{Z}$
that satisfies:

  1. (i)

if $x\prec y$, then $\rho(x)<\rho(y)$;

  2. (ii)

if $y$ covers $x$, i.e., $x\prec y$ and there is no $z\in P$ such that $x\prec
z\prec y$, then $\rho(y)=\rho(x)+1$.

An element $x\in P$ has rank $i$ if $\rho(x)=i$. By setting the minimum value
of the rank function to zero, any graded poset $P$ can be partitioned into
$P=\bigcup_{i=0}^{r}P_{i}$, where $P_{i}=\\{x\in P\colon\rho(x)=i\\}$. We
denote the size of $P_{i}$ by $s_{i}$. The poset $P$ is rank-symmetric if
$s_{i}=s_{r-i}$ for each $i$. The poset $P$ is rank-unimodal if $s_{0}\leq
s_{1}\leq\cdots\leq s_{i}\geq s_{i+1}\geq\cdots\geq s_{r}$ for some $i$, and
$P$ is Sperner if the width of $P$ is equal to $\max_{i}\\{s_{i}\\}$. The
width is lower bounded by $\max_{i}\\{s_{i}\\}$ since every $P_{i}$ is an
antichain. In a Sperner poset, the largest one among
$P_{0},P_{1},\ldots,P_{r}$ provides an antichain of maximum size.

A poset $P$ is a lattice if any two elements $x,y\in P$ have a least upper
bound and a greatest lower bound, denoted by $x\vee y$ and $x\wedge y$
respectively. A lattice $L$ is distributive if $x\vee(y\wedge z)=(x\vee
y)\wedge(x\vee z)$ for each $x,y,z\in L$.

The poset $M(n)$ has the following properties [18]:

  * •

The rank function with minimum rank 0 is the sum of elements of a subset. The
maximum rank is $n(n+1)/2$.

  * •

The poset $M(n)$ is rank-symmetric, rank-unimodal and Sperner. Therefore, its
width is equal to the size of the middle rank, which is
$N\left([n],\left\lfloor n(n+1)/4\right\rfloor\right)$.

  * •

Its height is $n(n+1)/2+1$.

  * •

The poset $M(n)$ is a distributive lattice with the greatest element $[n]$ and
the least element $\emptyset$.

###  2.2 Properties of the two posets

We will provide the properties of $P(n)$ and $Q(n)$. We need first to become
familiar with some elementary properties of the partial order $\preceq$.

######  Proposition 4.

For $\mathbf{x},\mathbf{y},\mathbf{z}\in\mathbb{R}^{n}$, the following holds:

  1. (1)

$\mathbf{x}\preceq\mathbf{y}\Longleftrightarrow\mathbf{x}+\mathbf{z}\preceq\mathbf{y}+\mathbf{z}$.

  2. (2)

$\mathbf{x}\preceq\mathbf{y}$ and $\,k\geq 0\Longrightarrow k\mathbf{x}\preceq
k\mathbf{y}$.

  3. (3)

$\mathbf{x}\preceq\mathbf{y}$ and $\,k\leq 0\Longrightarrow k\mathbf{y}\preceq
k\mathbf{x}$.

###### Proof.

Straightforward. ∎

In particular, $\mathbf{x}\preceq\mathbf{y}$ is equivalent to
$\mathbf{0}\preceq\mathbf{y}-\mathbf{x}$. In order to examine the poset
$P(n)$, we define two operators. Let us denote the $i$th entry of a vector
$\mathbf{v}$ by $v_{i}$ hereafter.

######  Definition 5 (Addition operator).

For $k\in[n]$, the addition operator $\mathcal{A}^{(k)}$ takes the input
$\mathbf{v}\in P(n)$ with $v_{k}=-1$ and sets the $k$th entry to $1$, that is,

$\left(\mathcal{A}^{(k)}\mathbf{v}\right)_{i}=\begin{cases}1&\text{ if
}\;i=k\\\ v_{i}&\text{ if }\;i\neq k.\end{cases}$

For other elements $\mathbf{v}$, the operation $\mathcal{A}^{(k)}\mathbf{v}$
is not defined.

######  Definition 6 (Swap operator).

For $j$, $k\in[n]$ with $j<k$, the swap operator $\mathcal{S}^{(j,k)}$ takes
the input $\mathbf{v}\in P(n)$ with $v_{j}=-1$ and $v_{k}=1$, and swaps
$v_{j}$ and $v_{k}$, that is,

$\left(\mathcal{S}^{(j,k)}\mathbf{v}\right)_{i}=\begin{cases}\phantom{-}1&\text{
if }\;i=j\\\ -1&\text{ if }\;i=k\\\ \phantom{-}v_{i}&\text{ if
}\;i\notin\\{j,k\\}.\end{cases}$

For other elements $\mathbf{v}$, the operation $\mathcal{S}^{(j,k)}\mathbf{v}$
is not defined.

We prove some relationships between the operators and the partial order
$\preceq_{P}$.

######  Proposition 7.

In the poset $P(n)$, $\mathbf{v}\prec_{P}\mathbf{w}$ if and only if
$\mathbf{w}$ is obtained from $\mathbf{v}$ by applying addition and/or swap
operators.

###### Proof.

Assume that $\mathbf{w}$ is obtained from $\mathbf{v}$ by applying addition
and/or swap operators. For each $\mathbf{u}\in P(n)$ and any possible integers
$j$ and $k$, we have $\mathbf{u}\prec_{P}\mathcal{A}^{(k)}\mathbf{u}$ and
$\mathbf{u}\prec_{P}\mathcal{S}^{(j,k)}\mathbf{u}$. Therefore,
$\mathbf{v}\prec_{P}\mathbf{w}$.

Conversely, assume that $\mathbf{v}\prec_{P}\mathbf{w}$. Let
$\mathbf{x}=\mathbf{w}-\mathbf{v}$. Then $x_{i}$ is $\pm 2$ or $0$ for
$i\in[n]$. Denote the indices of $x_{i}$’s equal to $-2$ by
$k_{1},\ldots,k_{l}$ in increasing order. Since any entry of the cumulative
sum of $\mathbf{x}$ is nonnegative, we can pair each entry equal to $-2$ with
an entry equal to 2 on the left, that is, we can choose distinct indices
$j_{1},\ldots,j_{l}$ of $x_{i}$’s equal to $2$ such that
$j_{1}<k_{1},\cdots,j_{l}<k_{l}$. Hence, $\mathbf{x}$ is decomposed as
follows:

$\displaystyle\mathbf{x}$
$\displaystyle=(\underbrace{0,\ldots,0}_{j_{1}-1},2,\underbrace{0,\ldots,0}_{k_{1}-j_{1}-1},-2,0,\ldots,0)+\dots+(\underbrace{0,\ldots,0}_{j_{l}-1},2,\underbrace{0,\ldots,0}_{k_{l}-j_{l}-1},-2,0,\ldots,0)$
$\displaystyle\quad+(\underbrace{0,\ldots,0}_{i_{1}-1},2,0,\ldots,0)+\dots+(\underbrace{0,\ldots,0}_{i_{m}-1},2,0,\ldots,0),$

where $i_{1},\dots,i_{m}$ are the indices of the remaining $2$’s. Since the
indices are all distinct, we have
$\mathbf{w}=\mathcal{A}^{(i_{m})}\cdots\mathcal{A}^{(i_{1})}\mathcal{S}^{(j_{l},k_{l})}\cdots\mathcal{S}^{(j_{1},k_{1})}\mathbf{v}.$
This means that $\mathbf{w}$ is obtained from $\mathbf{v}$ by applying
addition and/or swap operators. ∎

######  Proposition 8.

In the poset $P(n)$, $\mathbf{w}$ covers $\mathbf{v}$ if and only if
$\mathbf{w}$ is obtained from $\mathbf{v}$ by applying a single operator of
the addition operator $\mathcal{A}^{(n)}$ and the swap operators
$\mathcal{S}^{(1,2)},\ldots,\mathcal{S}^{(n-1,n)}$.

###### Proof.

Assume that $\mathbf{w}$ covers $\mathbf{v}$, that is,
$\mathbf{v}\prec_{P}\mathbf{w}$ and there is no $\mathbf{u}\in P(n)$ such that
$\mathbf{v}\prec_{P}\mathbf{u}\prec_{P}\mathbf{w}$. Suppose, contrary to our
claim, that $\mathbf{w}$ is not obtained from $\mathbf{v}$ by one of the
operators. We have the following three cases:

Case 1: $\mathbf{w}$ is obtained from $\mathbf{v}$ by two or more addition
and/or swap operators. Then there exists $\mathbf{u}\in P$ such that
$\mathbf{v}\prec_{P}\mathbf{u}\prec_{P}\mathbf{w}$ since one of the operators
always makes the input larger. This is a contradiction.

Case 2: $\mathbf{w}=\mathcal{A}^{(i)}\mathbf{v}$ for some $i\in[n-1]$. Then
$v_{i}=-1$. If $v_{i+1}=1$ then
$\mathbf{w}=\mathcal{A}^{(i+1)}\mathcal{S}^{(i,i+1)}\mathbf{v}$. If
$v_{i+1}=-1$ then
$\mathbf{w}=\mathcal{S}^{(i,i+1)}\mathcal{A}^{(i+1)}\mathbf{v}$. Both lead to
Case 1, a contradiction.

Case 3: $\mathbf{w}=\mathcal{S}^{(j,k)}\mathbf{v}$ for some $j$ and $k$ with
$k-j\geq 2$. Then $v_{j}=-1$ and $v_{k}=1$. If $v_{j+1}=1$ then
$\mathbf{w}=\mathcal{S}^{(j+1,k)}\mathcal{S}^{(j,j+1)}\mathbf{v}$. If
$v_{j+1}=-1$ then
$\mathbf{w}=\mathcal{S}^{(j,j+1)}\mathcal{S}^{(j+1,k)}\mathbf{v}$. Both lead
to Case 1, a contradiction.

Conversely, assume that $\mathbf{w}$ is obtained from $\mathbf{v}$ by applying
one of the operators. It is clear that $\mathbf{v}\prec_{P}\mathbf{w}$.
Suppose, contrary to our claim, that there exists $\mathbf{u}\in P(n)$ such
that $\mathbf{v}\prec_{P}\mathbf{u}\prec_{P}\mathbf{w}$. If
$\mathbf{w}=\mathcal{A}^{(n)}\mathbf{v}$, then $v_{i}=w_{i}$ for $i\in[n-1]$,
$v_{n}=-1$ and $w_{n}=1$. Thus, $u_{i}=v_{i}=w_{i}$ for $i\in[n-1]$ and
$u_{n}$ must be equal to $\pm 1$, which is a contradiction. If
$\mathbf{w}=\mathcal{S}^{(k,k+1)}\mathbf{v}$ for some $k\in[n-1]$, then
$v_{i}=w_{i}$ for $i\notin\\{k,k+1\\}$, $v_{k}=-1$, $v_{k+1}=1$, $w_{k}=1$ and
$w_{k+1}=-1$. Thus, $u_{i}=v_{i}=w_{i}$ for $i\in[k-1]$, $u_{k}+u_{k+1}=0$,
and $u_{i}=v_{i}=w_{i}$ for $i\in[n]\setminus[k+1]$, which is also a
contradiction. ∎

######  Proposition 9.

The poset $P(n)$ is order-isomorphic to $M(n)$.

###### Proof.

We need to show that $\mathbf{v}\preceq_{P}\mathbf{w}$ if and only if
$f(\mathbf{v})\leqslant f(\mathbf{w})$ for each $\mathbf{v}$ and $\mathbf{w}$
in $P(n)$.

Assume that $\mathbf{v}\preceq_{P}\mathbf{w}$. From Proposition 7 it follows
that $\mathbf{w}$ is obtained from $\mathbf{v}$ by applying addition and/or
swap operators. An addition operator increases 1’s of the input by one and a
swap operator shifts one of 1’s of the input to the left. Now let $\mathbf{v}$
have $m$ 1’s. Then $\mathbf{w}$ has at least $m$ 1’s, which implies that
$f(\mathbf{w})$ has at least as many elements as $f(\mathbf{v})$. The $m$
left-most 1’s of $\mathbf{w}$ do not lie more to the right than the 1’s of
$\mathbf{v}$, which implies that in decreasing order the $i$th element of
$f(\mathbf{w})$ is not less than that of $f(\mathbf{v})$ for $i\in[m]$. Hence,
$f(\mathbf{v})\leqslant f(\mathbf{w})$.

Conversely, assume that $f(\mathbf{v})\leqslant f(\mathbf{w})$. Let
$f(\mathbf{v})=\\{a_{1},\ldots,a_{j}\\}$ and
$f(\mathbf{w})=\\{b_{1},\ldots,b_{k}\\}$ in decreasing order. Then $j\leq k$,
which means that $\mathbf{w}$ has at least as many 1’s as $\mathbf{v}$, and
$a_{i}\leq b_{i}$ for $i\in[j]$, which means that the $j$ left-most 1’s of
$\mathbf{w}$ do not lie more to the right than the 1’s of $\mathbf{v}$. By the
properties of addition and swap operators, $\mathbf{w}$ is obtained from
$\mathbf{v}$ by applying addition and/or swap operators, that is,
$\mathbf{v}\preceq_{P}\mathbf{w}$. ∎

The poset $P(n)$ has the following symmetry.

######  Proposition 10.

In the poset $P(n)$, $\mathbf{v}\prec_{P}\mathbf{w}$ if and only if
$-\mathbf{w}\prec_{P}-\mathbf{v}$.

###### Proof.

For each $\mathbf{v}\in P(n)$, it holds that $-\mathbf{v}\in P(n)$. The
statement follows immediately from Proposition 4 (3). ∎

It follows from Proposition 9 and its proof and Proposition 10 that the poset
$P(n)$ has the following properties:

  * •

The rank function with minimum rank 0 is

$\frac{1}{2}\left(\mathbf{v}\cdot\mathbf{c}_{0}+\frac{1}{2}n(n+1)\right)$ (2)

for $\mathbf{v}\in P(n)$, where $\mathbf{c}_{0}=(n,n-1,\ldots,2,1)$.

  * •

The poset $P(n)$ is rank-symmetric, rank-unimodal and Sperner.

  * •

Its width is $N\left([n],\left\lfloor n(n+1)/4\right\rfloor\right)$.

  * •

Its height is $n(n+1)/2+1$.

  * •

The poset $P(n)$ has a certain symmetry:
$\mathbf{v}\prec_{P}\mathbf{w}\Longleftrightarrow-\mathbf{w}\prec_{P}-\mathbf{v}$.

  * •

The poset $P(n)$ is a distributive lattice. The greatest element and the least
one are respectively $(1,\ldots,1)$ and $(-1,\ldots,-1)$.

######  Remark.

An element of $P(n)$ can be also regarded as a path of the random walk on the
integer number line which starts at 0 and at each step moves $+1$ or $-1$. The
relation $\mathbf{v}\preceq_{P}\mathbf{w}$ means that the path corresponding
to $\mathbf{v}$ does not “exceed” the one corresponding to $\mathbf{w}$.
Figure 4 shows an example.

Figure 4: Some elements of $P(6)$ as paths of the random walk.

We investigate the other poset $Q(n)$. Hereafter, let $n\geq 3$. We will show
some properties of $Q(n)$.

Let $R_{+}(n)=\\{\mathbf{v}\in P(n)\colon\mathbf{0}\prec\mathbf{v}\\}$ and
$R_{-}(n)=\\{\mathbf{v}\in P(n)\colon\mathbf{v}\prec\mathbf{0}\\}$. We can see
that the subposets $R_{+}(n)$ and $R_{-}(n)$ of $P(n)$ are sublattices of
$P(n)$. The least element of $R^{+}(n)$ is $(1,-1,1,-1,...)$, the rank of
which in $P(n)$ is $n/4+n(n+1)/4$ if $n$ is even and $(n+1)/4+n(n+1)/4$ if $n$
is odd. The elements of $R_{+}(n)$ are not in the middle rank of $P(n)$. This
is true for $R_{-}(n)$ by the symmetry of $P(n)$. Therefore, we obtain the
next proposition.

######  Proposition 11.

The width of $Q(n)$ is the same as that of $P(n)$.

For the size of $Q(n)$, the next proposition holds.

######  Proposition 12.

The size of $Q(n)$ is $2^{n}-2\binom{n}{\lfloor n/2\rfloor}$.

###### Proof.

By definition, $\\#Q(n)=\\#P(n)-\\#R_{+}(n)-\\#R_{-}(n)$, where $\\#$
indicates the size of a set. Since $\\#P(n)=2^{n}$ and
$\\#R_{+}(n)=\\#R_{-}(n)$, it is sufficient to show that
$\\#R_{+}(n)=\binom{n}{\lfloor n/2\rfloor}$. Let us regard the elements of
$R_{+}(n)$ as the paths of the random walk. The size is the number of $n$-step
paths from 0 never going below 0 (for example, see $\mathbf{w}$ in Figure 4).
Denote the number by $X_{n}$ and define $X_{0}=1$. Then we have

$X_{n}=\begin{cases}2X_{n-1}-C_{(n-1)/2}&\text{ if $n$ is odd}\\\
2X_{n-1}&\text{ if $n$ is even},\end{cases}$

where $C_{m}$ is the number of $2m$-step paths from 0 to 0 never going below
0, known as the Catalan number. The sequence $X_{n}$ is known to be
$\binom{n}{\lfloor n/2\rfloor}$. ∎

The poset $Q(n)$ also has the symmetry.

######  Proposition 13.

In the poset $Q(n)$, $\mathbf{v}\prec_{Q}\mathbf{w}$ if and only if
$-\mathbf{w}\prec_{Q}-\mathbf{v}$.

###### Proof.

For each $\mathbf{v}\in Q(n)$, we show that $-\mathbf{v}\in Q(n)$. Suppose,
contrary to our claim, that $-\mathbf{v}\notin Q(n)$. Then
$-\mathbf{v}\prec\mathbf{0}$ or $\mathbf{0}\prec-\mathbf{v}$, which
contradicts $\mathbf{v}\in Q(n)$. The statement follows immediately from
Proposition 4 (3). ∎

######  Proposition 14.

The poset $Q(n)$ is graded and one of the rank functions is the same as the
rank function (2) of $P(n)$.

###### Proof.

Denote the rank function of $P(n)$ by $\rho$. We show that a rank function of
$Q(n)$ is $\rho$. Since $Q(n)$ is a subposet of $P(n)$, if
$\mathbf{v}\prec_{Q}\mathbf{w}$ then $\rho(\mathbf{v})<\rho(\mathbf{w})$. When
$\mathbf{w}$ covers $\mathbf{v}$ in $Q(n)$, suppose, contrary to our claim,
that $\rho(\mathbf{w})\geq\rho(\mathbf{v})+2$. Then there exists some
$\mathbf{u}\in P(n)\setminus Q(n)$ such that
$\mathbf{v}\prec_{P}\mathbf{u}\prec_{P}\mathbf{w}$ and
$\rho(\mathbf{u})=\rho(\mathbf{v})+1$. Since $\mathbf{u}$ is not in $Q(n)$,
$\mathbf{u}\prec\mathbf{0}$ or $\mathbf{0}\prec\mathbf{u}$. If
$\mathbf{u}\prec\mathbf{0}$ then $\mathbf{v}\prec\mathbf{0}$. If
$\mathbf{0}\prec\mathbf{u}$ then $\mathbf{0}\prec\mathbf{w}$. Either case is a
contradiction. ∎

Let $\ell=\lfloor(n-1)/2\rfloor$. For $k\in\\{0,1,\dots\ell\\}$ we denote by
$\mathbf{m}_{k}$ the element of $Q(n)$

$(\underbrace{1,\ldots,1}_{k},\underbrace{-1,\ldots,-1}_{k+1},1,\ldots,1).$

Thus, $-\mathbf{m}_{k}$ stands for the element of $Q(n)$

$(\underbrace{-1,\ldots,-1}_{k},\underbrace{1,\ldots,1}_{k+1},-1,\ldots,-1).$

######  Proposition 15.

The maximal (minimal) elements of $Q(n)$ are $\mathbf{m}_{0}$,
$\mathbf{m}_{1}$, $\ldots,\mathbf{m}_{\ell}\>(-\mathbf{m}_{0}$,
$-\mathbf{m}_{1}$, $\ldots,-\mathbf{m}_{\ell}$, resp.).

###### Proof.

We first prove that $\mathbf{m}_{k}$ for $k\in\\{0,1,\dots\ell\\}$ is maximal.
It is sufficient to show that the elements covering $\mathbf{m}_{k}$ on $P(n)$
are not in $Q(n)$. If $n$ is even, then the last entry of $\mathbf{m}_{k}$ is
always $1$ for each $k$. From this fact and Proposition 8 it follows that the
unique element covering $\mathbf{m}_{k}$ is
$\mathcal{S}^{(2k+1,2k+2)}\mathbf{m}_{k}$, that is,

$(\underbrace{1,\ldots,1}_{k},\underbrace{-1,\ldots,-1}_{k},1,-1,1,\ldots,1),$

which is greater than $\mathbf{0}$. If $n$ is odd, then the last entry of
$\mathbf{m}_{k}$ might be $-1$. The unique element covering $\mathbf{m}_{k}$
is $\mathcal{S}^{(2k+1,2k+2)}\mathbf{m}_{k}$ if $k<\ell$, and
$\mathcal{A}^{(n)}\mathbf{m}_{k}$, that is,

$(\underbrace{1,\ldots,1}_{k},\underbrace{-1,\ldots,-1}_{k},1)$

if $k=\ell$. Both are greater than $\mathbf{0}$.

We next prove that no other elements are maximal. Consider a maximal element
$\mathbf{v}\in Q(n)$. Now we distinguish two cases.

Case 1: $\mathbf{v}$ contains no $(-1,1)$ sequence. Then $\mathbf{v}$ is a
vector with $1$’s up to some position (possibly none) and then $-1$’s for the
rest of the entries, that is, $(1,\ldots,1)$, $(-1,\ldots,-1)$ or
$(1,\ldots,1,-1,\ldots,-1)$. The first two are not obviously in $Q(n)$. Since
$\mathbf{v}\in Q(n)$ and $\mathcal{A}^{(n)}\mathbf{v}\in R_{+}(n)$, the sum
$v_{1}+\cdots+v_{n}$ must be equal to $-1$. Therefore, $\mathbf{v}$ is

$(\underbrace{1,\ldots,1}_{(n-1)/2},\underbrace{-1,\ldots,-1}_{(n-1)/2},-1),$

where $n$ is odd. This is exactly $\mathbf{m}_{\ell}$.

Case 2: $\mathbf{v}$ contains $(-1,1)$ sequences. We assume that the left-most
sequence lies at the $j$th and $(j+1)$th positions. Then
$\mathcal{S}^{(j,j+1)}\mathbf{v}\in R_{+}(n)$. Hence, $v_{1}+\cdots+v_{j}$
must be equal to $-1$. If $\mathbf{v}$ contains another $(-1,1)$ sequence at
the $j^{\prime}$th and $(j^{\prime}+1)$th positions, then
$\mathcal{S}^{(j^{\prime},j^{\prime}+1)}\mathbf{v}\in Q(n)$, which contradicts
the maximality. Therefore, the subsequences $(v_{1},\ldots,v_{j-1})$ and
$(v_{j+2},\ldots,v_{n})$ contain no $(-1,1)$ sequence. By a similar argument
to Case 1, they are $(1,\ldots,1)$, $(-1,\ldots,-1)$,
$(1,\ldots,1,-1,\ldots,-1)$ or empty. Since $v_{1}+\cdots+v_{j-1}=0$, we get

$(v_{1},\ldots,v_{j-1})=(\underbrace{1,\ldots,1}_{(j-1)/2},\underbrace{-1,\ldots,-1}_{(j-1)/2}),$

where $j$ is odd (if $j=1$ then the subsequence is empty). On the other hand,
if $v_{n}=-1$ then $\mathcal{A}^{(n)}\mathbf{v}\in Q(n)$, which contradicts
the maximality. Hence, $(v_{j+2},\ldots,v_{n})$ is $(1,\dots,1)$ or empty.
Consequently, $\mathbf{v}$ is

$(\underbrace{1,\ldots,1}_{(j-1)/2},\underbrace{-1,\ldots,-1}_{(j-1)/2},-1,1,\underbrace{1,\ldots,1}_{n-(j+1)}),$

which is exactly $\mathbf{m}_{k}$, where $k=(j-1)/2$ and $j\leq n-1$. Note
that $k\in\\{0,1,\dots,\ell\\}$ if $n$ is even and $k\in\\{0,\dots,\ell-1\\}$
if $n$ is odd.

By symmetry, if $\mathbf{v}$ is a maximal element, then $-\mathbf{v}$ is a
minimal element.

∎

######  Lemma 16.

In the poset $Q(n)$ with $n\geq 4$, a minimal element $-\mathbf{m}_{k}$ is
less than a maximal element $\mathbf{m}_{k^{\prime}}$ with $k^{\prime}\neq k$,
that is, $-\mathbf{m}_{k}\prec_{Q}\mathbf{m}_{k^{\prime}}$.

###### Proof.

Let $k_{0}=\min\\{k,k^{\prime}\\}$ and $k_{1}=\max\\{k,k^{\prime}\\}$. If
$k_{0}<k_{1}\leq 2k_{0}+1$, then

$\mathbf{m}_{k^{\prime}}-(-\mathbf{m}_{k})=(\underbrace{2,\ldots,2}_{k_{0}},\underbrace{0,\ldots,0}_{k_{1}-k_{0}},\underbrace{-2,\ldots,-2}_{2k_{0}+1-k_{1}},\underbrace{0,\ldots,0}_{2(k_{1}-k_{0})},2,\ldots,2),$

which is greater than $\mathbf{0}$ since $k_{0}\geq 2k_{0}+1-k_{1}$. If
$2k_{0}+1<k_{1}$, then

$\mathbf{m}_{k^{\prime}}-(-\mathbf{m}_{k})=(\underbrace{2,\ldots,2}_{k_{0}},\underbrace{0,\ldots,0}_{k_{0}+1},\underbrace{2,\ldots,2}_{k_{1}-(2k_{0}+1)},\underbrace{0,\ldots,0}_{k_{1}+1},2,\ldots,2),$

which is evidently greater than $\mathbf{0}$. ∎

Note that in the case where $n=3$, the maximal elements
$\mathbf{m}_{0}=(-1,1,1)$ and $\mathbf{m}_{1}=(1,-1,-1)$ are also minimal
elements.

######  Proposition 17.

The height of $Q(n)$ is

$\displaystyle\frac{1}{2}n(n-1)-\left(n-\frac{3}{2}\ell\right)(\ell+1)+1$
$\displaystyle\text{ for }\>n\leq 7,\text{ and}$
$\displaystyle\frac{1}{2}(n-2)(n-3)+1$ $\displaystyle\text{ for }\>n\geq 8.$

###### Proof.

We first consider the case where $n\geq 4$. From Lemma 16 it follows that two
elements $-\mathbf{m}_{k}$ and $\mathbf{m}_{k^{\prime}}$ with $k^{\prime}\neq
k$ are comparable. Let us take a maximal chain containing the two elements.
Since $Q(n)$ is graded, the size of the maximal chain is
$\rho(\mathbf{m}_{k^{\prime}})-\rho(-\mathbf{m}_{k})+1$, where $\rho$ denotes
the rank function (2) of $P(n)$ and $Q(n)$. Therefore, the height is

$\max_{k\neq
k^{\prime}}\left\\{\rho(\mathbf{m}_{k^{\prime}})-\rho(-\mathbf{m}_{k})+1\right\\}.$
(3)

Since $\rho(\mathbf{v})=\left(\mathbf{v}\cdot\mathbf{c}_{0}+n(n+1)/2\right)/2$
for $\mathbf{v}\in Q(n)$, we have

$\displaystyle\rho(\mathbf{m}_{k^{\prime}})$
$\displaystyle=\frac{1}{2}n(n+1)-n(k^{\prime}+1)+\frac{3}{2}k^{\prime}(k^{\prime}+1),$
$\displaystyle\rho(-\mathbf{m}_{k})$ $\displaystyle=n(k+1)-\frac{3}{2}k(k+1).$

Substituting these expressions into (3), we obtain

$\max_{k\neq
k^{\prime}}\left\\{\frac{3}{2}\left(k-\frac{2n-3}{6}\right)^{2}+\frac{3}{2}\left(k^{\prime}-\frac{2n-3}{6}\right)^{2}-3\left(\frac{2n-3}{6}\right)^{2}+\frac{1}{2}n(n-3)+1\right\\}.$

The objective function is symmetric in $k$ and $k^{\prime}$, and we can assume
that $k>k^{\prime}$. In the $k$-$k^{\prime}$ plane the farthest point from the
center point $\left((2n-3)/6,(2n-3)/6\right)$ provides the maximum value.
Therefore, the candidate points are $(1,0)$ and $(\ell,0)$. Determining the
position of the center point relative to the line $k=(1+\ell)/2$, equidistant
from the two points, we conclude that the optimal point is $(\ell,0)$ for
$n\leq 7$ and $(1,0)$ for $n\geq 8$. Hence, the height is
$n(n-1)/2-(n-3\ell/2)(\ell+1)+1$ for $n\leq 7$ and $(n-2)(n-3)/2+1$ for $n\geq
8$.

In the case where $n=3$, the height is $1$, which is obtained by the
expression above for $n\leq 7$. ∎

Summarizing, we have the following properties of $Q(n)$:

  * •

The rank function with minimum rank 0 is

$\frac{1}{2}\left(\mathbf{v}\cdot\mathbf{c}_{0}+\frac{1}{2}n(n+1)\right)-n$

for $\mathbf{v}\in Q(n)$.

  * •

Its size is $2^{n}-2\binom{n}{\lfloor n/2\rfloor}$.

  * •

The poset $Q(n)$ is rank-symmetric and Sperner.

  * •

Its width is the same as that of $P(n)$, i.e., $N\left([n],\left\lfloor
n(n+1)/4\right\rfloor\right)$.

  * •

Its height is $n(n-1)/2-\left(n-3\ell/2\right)(\ell+1)+1$ for $n\leq 7$ and
$(n-2)(n-3)/2+1$ for $n\geq 8$.

  * •

The poset $Q(n)$ also has the same symmetry as $P(n)$:
$\mathbf{v}\prec_{Q}\mathbf{w}\Longleftrightarrow-\mathbf{w}\prec_{Q}-\mathbf{v}$.

  * •

The minimal elements and the maximal ones are respectively
$-\mathbf{m}_{0},-\mathbf{m}_{1},\ldots,-\mathbf{m}_{\ell}$ and
$\mathbf{m}_{0},\mathbf{m}_{1},\ldots,\mathbf{m}_{\ell}$.

It does not seem easy to determine whether $Q(n)$ is rank-unimodal or not. As
a side note, we observed that $Q(n)$ is rank-unimodal for $n\leq 21$.

##  3 Relationship between the partition problem and the posets

We will discuss the relationship between the partition problem and the posets
$P(n)$ and $Q(n)$. We first show the relationship between the difference of
the partition problem and the partial order $\preceq_{P}$ or $\preceq_{Q}$. To
this end, we introduce another expression of the difference
$\mathbf{p}(S)\cdot\mathbf{c}$. Let $\mathbf{d}=(d_{1},\dots,d_{n})$ defined
by $d_{i}=c_{i}-c_{i+1}$ for $i\in[n]$, where $c_{n+1}=0$. Note that
$\mathbf{d}\geq\mathbf{0}$, which is a componentwise inequality. Denote the
cumulative sum of $\mathbf{p}(S)$ by $\mathbf{r}(S)$, that is,
$\mathbf{r}(S)=(p_{1},p_{1}+p_{2},\dots,p_{1}+\dots+p_{n})$ when
$\mathbf{p}(S)=(p_{1},p_{2},\dots,p_{n})$. Then
$\mathbf{p}(S)\cdot\mathbf{c}=\mathbf{r}(S)\cdot\mathbf{d}$. In addition, the
relation $\mathbf{p}(S)\preceq_{P}\mathbf{p}(S^{\prime})$ can be succinctly
written as the componentwise inequality
$\mathbf{r}(S)\leq\mathbf{r}(S^{\prime})$.

######  Proposition 18.

Given two subsets $S$ and $S^{\prime}$ of $[n]$, the inequality
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$ holds
for any $\mathbf{c}$ if and only if
$\mathbf{p}(S)\preceq_{P}\mathbf{p}(S^{\prime})$.

###### Proof.

We denote $\mathbf{p}(S)$ and $\mathbf{p}(S^{\prime})$ by
$(p_{1},\ldots,p_{n})$ and $(p^{\prime}_{1},\ldots,p^{\prime}_{n})$,
respectively.

We first assume that
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$ for
any $\mathbf{c}$. Suppose, contrary to our claim, that
$p_{1}+\cdots+p_{k}>p^{\prime}_{1}+\cdots+p^{\prime}_{k}$ for some $k\in[n]$.
Take

$\mathbf{c}^{\prime}=(\underbrace{1,\ldots,1}_{k},0,\ldots,0).$

Then
$\mathbf{p}(S)\cdot\mathbf{c}^{\prime}>\mathbf{p}(S^{\prime})\cdot\mathbf{c}^{\prime}$,
which is a contradiction.

We next prove the converse. We assume that
$\mathbf{p}(S)\preceq_{P}\mathbf{p}(S^{\prime})$, that is,
$\mathbf{r}(S)\leq\mathbf{r}(S^{\prime})$. Suppose, contrary to our claim,
that $\mathbf{p}(S)\cdot\mathbf{c}>\mathbf{p}(S^{\prime})\cdot\mathbf{c}$ for
some $\mathbf{c}$. Then we have
$(\mathbf{r}(S)-\mathbf{r}(S^{\prime}))\cdot\mathbf{d}>0$. Since
$\mathbf{r}(S)-\mathbf{r}(S^{\prime})$ is nonpositive and $\mathbf{d}$ is
nonnegative, the left-hand side is nonpositive, a contradiction. ∎

A similar statement holds for the poset $Q(n)$.

######  Corollary 19.

Given two subsets $S$ and $S^{\prime}$ of $[n]$ satisfying $\mathbf{p}(S)$,
$\mathbf{p}(S^{\prime})\in Q(n)$, the inequality
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$ holds
for any $\mathbf{c}$ if and only if
$\mathbf{p}(S)\preceq_{Q}\mathbf{p}(S^{\prime})$.

We next provide subsets unnecessary to be considered in the partition problem.

######  Lemma 20.

If a subset $S$ of $[n]$ satisfies $\mathbf{p}(S)\prec\mathbf{0}$ or
$\mathbf{0}\prec\mathbf{p}(S)$, then there exists some subset $S^{\prime}$ of
$[n]$, not equal to $S$ or $[n]\setminus S$, such that
$\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert$
for any $\mathbf{c}$.

###### Proof.

We denote $\mathbf{p}(S)$ by $(p_{1},\ldots,p_{n})$. For the complement of
$S$, we have $\mathbf{p}([n]\setminus S)=-\mathbf{p}(S)$ and
$\lvert\mathbf{p}([n]\setminus
S)\cdot\mathbf{c}\rvert=\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert$. Without
loss of generality, we can thus assume that $\mathbf{p}(S)\prec\mathbf{0}$. We
need to consider two cases:

Case 1: $\mathbf{p}(S)$ contains no $(-1,1)$ sequence. Since
$\mathbf{p}(S)\prec\mathbf{0}$, it holds that $S=\emptyset$. Take $\\{n\\}$ as
$S^{\prime}$. Then $\mathbf{p}(S)\prec_{P}\mathbf{p}(S^{\prime})$ and
$\mathbf{p}(S^{\prime})\prec\mathbf{0}$. It follows from the former relation
and Proposition 18 that
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$ holds
for any $\mathbf{c}$. The latter relation is equivalent to
$\mathbf{r}(S^{\prime})\leq\mathbf{0}$. The inner product of
$\mathbf{r}(S^{\prime})$ with the nonnegative vector $\mathbf{d}$ is
nonpositive. Thus,
$\mathbf{r}(S^{\prime})\cdot\mathbf{d}=\mathbf{p}(S^{\prime})\cdot\mathbf{c}\leq
0$ for any $\mathbf{c}$. Therefore,
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}\leq 0$
for any $\mathbf{c}$.

Case 2: $\mathbf{p}(S)$ contains $(-1,1)$ sequences. We assume that the left-
most sequence lies at the $j$th and $(j+1)$th positions. Take $S^{\prime}$
such that $\mathbf{p}(S^{\prime})=\mathcal{S}^{(j,j+1)}\mathbf{p}(S)$. Then
$\mathbf{p}(S)\prec_{P}\mathbf{p}(S^{\prime})$ by Proposition 7. On the other
hand, subtracting $-\mathbf{p}(S)$ from $\mathbf{p}(S^{\prime})$, we have

$\mathbf{p}(S^{\prime})-(-\mathbf{p}(S))=(2p_{1},\ldots,2p_{j-1},0,0,2p_{j+2},\ldots,2p_{n}).$

This gives $\mathbf{p}(S^{\prime})\prec_{P}-\mathbf{p}(S)$, since
$\mathbf{p}(S)\prec\mathbf{0}$. Consequently, it follows from Proposition 18
that
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}\leq-\mathbf{p}(S)\cdot\mathbf{c}$
for any $\mathbf{c}$. ∎

By this lemma, it turns out that it is unnecessary to consider the elements of
$P(n)\setminus Q(n)$. We then show that in general we must consider all the
elements of $Q(n)$.

######  Lemma 21.

Let a subset $S$ of $[n]$ satisfy $\mathbf{p}(S)\in Q(n)$. Then there exists
some $\mathbf{c}$ such that
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert<\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$
for any $S^{\prime}$ that satisfies $\mathbf{p}(S^{\prime})\in Q(n)$ and is
not equal to $S$ or $[n]\setminus S$.

###### Proof.

We will prove this by contradiction. Suppose that for any $\mathbf{c}$ there
exists some $S^{\prime}$ such that
$\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert$.
In particular, $\mathbf{p}(S)\cdot\mathbf{c}=0$ implies
$\mathbf{p}(S^{\prime})\cdot\mathbf{c}=0$. Considering another expression of
the difference, we deduce that for $\mathbf{d}\geq 0$ satisfying
$\mathbf{r}(S)\cdot\mathbf{d}=0$ there exists some $S^{\prime}$ such that
$\mathbf{r}(S^{\prime})\cdot\mathbf{d}=0$. By regarding these expressions as
inequalities for $\mathbf{d}$, we obtain

$\\{\mathbf{d}\in\mathbb{Z}^{n}:\mathbf{r}(S)\cdot\mathbf{d}=0,\;\mathbf{d}\geq\mathbf{0}\\}\subset\bigcup_{S^{\prime}\neq
S,[n]\setminus
S}\\{\mathbf{d}\in\mathbb{Z}^{n}:\mathbf{r}(S^{\prime})\cdot\mathbf{d}=0,\;\mathbf{d}\geq\mathbf{0}\\}.$

We will denote the left-hand side and the set in the union on the right-hand
side by $C_{S}$ and $C_{S^{\prime}}$ respectively. From the notation and the
expression above, we can deduce that $C_{S}$ is equal to the union of the
intersections of $C_{S}$ with each $C_{S^{\prime}}$, that is,

$C_{S}=\bigcup_{S^{\prime}\neq S,[n]\setminus S}(C_{S}\cap C_{S^{\prime}}).$

Now choose a minimal decomposition

$C_{S}=\bigcup_{i=1}^{m}(C_{S}\cap C_{S^{\prime}_{i}})$ (4)

with $m$ minimal. Then $m\geq 2$, since $\mathbf{r}(S)$ and
$\mathbf{r}(S^{\prime}_{i})$ are linearly independent and $\mathbf{p}(S)$ and
$\mathbf{p}(S^{\prime}_{i})$ are both in $Q(n)$. By minimality, no $C_{S}\cap
C_{S^{\prime}_{i}}$ is contained in the union of other $C_{S}\cap
C_{S^{\prime}_{j}}$’s. Take vectors $\mathbf{d}_{1}$ and $\mathbf{d}_{2}$ such
that $\mathbf{d}_{1}\in C_{S}\cap C_{S^{\prime}_{1}}$ but
$\mathbf{d}_{1}\notin C_{S}\cap C_{S^{\prime}_{i}}$ for $i\neq 1$ and
$\mathbf{d}_{2}\in C_{S}\cap C_{S^{\prime}_{2}}$ but $\mathbf{d}_{2}\notin
C_{S}\cap C_{S^{\prime}_{i}}$ for $i\neq 2$. Consider the intersection of
$C_{S}\cap C_{S^{\prime}_{i}}$ and the infinite set
$K=\\{\alpha\mathbf{d}_{1}+\mathbf{d}_{2}:\alpha\in\mathbb{Z},\alpha\geq
0\\}\subset C_{S}$. If $i=1$, then the intersection is empty since
$\mathbf{r}(S^{\prime}_{i})\cdot\mathbf{d}_{1}=0$ and
$\mathbf{r}(S^{\prime}_{i})\cdot\mathbf{d}_{2}\neq 0$. If $i\neq 1$, then the
intersection is at most one point since
$\mathbf{r}(S^{\prime}_{i})\cdot\mathbf{d}_{1}\neq 0$. So $K$ intersects each
$C_{S}\cap C_{S^{\prime}_{i}}$ in at most one point. Since (4) holds, $K$ is a
finite set, a contradiction. ∎

We thus can prove Theorem 1.

###### Proof of Theorem 1.

This follows immediately from Lemmas 20 and 21. ∎

We will consider an instance of the partition problem, that is, we take a
concrete $\mathbf{c}$ into account. We can reduce the candidate solutions by
using the partial order.

######  Proposition 22.

Given an instance $\mathbf{c}$ of the partition problem, the following holds:

  1. (1)

If $\mathbf{p}(S)\cdot\mathbf{c}\geq 0$ for some subset $S$ of $[n]$, then
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$
for any $S^{\prime}$ that satisfies
$\mathbf{p}(S^{\prime})\preceq_{P}-\mathbf{p}(S)$ or
$\mathbf{p}(S)\preceq_{P}\mathbf{p}(S^{\prime})$.

  2. (2)

If $\mathbf{p}(S)\cdot\mathbf{c}\leq 0$ for some subset $S$ of $[n]$, then
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$
for any $S^{\prime}$ that satisfies
$\mathbf{p}(S^{\prime})\preceq_{P}\mathbf{p}(S)$ or
$-\mathbf{p}(S)\preceq_{P}\mathbf{p}(S^{\prime})$.

###### Proof.

We show the first statement. From Proposition 18 it follows that
$\mathbf{p}(S^{\prime})\cdot\mathbf{c}\leq-\mathbf{p}(S)\cdot\mathbf{c}$ or
$\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$.
Hence,
$\mathbf{p}(S^{\prime})\cdot\mathbf{c}\leq-\mathbf{p}(S)\cdot\mathbf{c}\leq 0$
or
$0\leq\mathbf{p}(S)\cdot\mathbf{c}\leq\mathbf{p}(S^{\prime})\cdot\mathbf{c}$.
Either case implies that
$\lvert\mathbf{p}(S)\cdot\mathbf{c}\rvert\leq\lvert\mathbf{p}(S^{\prime})\cdot\mathbf{c}\rvert$.

In the same manner, we can prove the second. ∎

###### Proof of Theorem 2.

It immediately follows from Proposition 22. ∎

If the height of $Q(n)$ is large, we can reduce efficiently the candidate
solutions by using Theorem 2. However, this is not the case; its height is
$O(n^{2})$, while its width is $O(2^{n}/n^{3/2})$ for $n$ congruent to 0 or 3
(mod 4). The large width indicates the hardness of the partition problem.

We will give some polynomially solvable cases by considering the minimal
elements of $Q(n)$. To this end, we show an interesting property of the
minimal elements of $Q(n)$.

######  Lemma 23.

Given a subset $S$ of $[n]$, any minimal element of $Q(n)$ is less than or
equal to either $\mathbf{p}(S)$ or $-\mathbf{p}(S)$.

###### Proof.

Let $-\mathbf{m}_{k}$ be a minimal element of $Q(n)$, where
$k\in\\{0,1,\dots\ell\\}$. We prove that there are $2^{n-1}$ subsets
$S^{\prime}$ such that $-\mathbf{m}_{k}\preceq_{P}\mathbf{p}(S^{\prime})$. Now
$-\mathbf{m}_{k}$ is

$(\underbrace{-1,\ldots,-1}_{k},\underbrace{1,\ldots,1}_{k+1},\underbrace{-1,\ldots,-1}_{n-2k-1}).$

By Proposition 7, $\mathbf{p}(S^{\prime})$ is obtained from $-\mathbf{m}_{k}$
by applying addition and/or swap operators. We denote $\mathbf{p}(S^{\prime})$
by $(\mathbf{p}_{1},\mathbf{p}_{2})$, where $\mathbf{p}_{1}\in
P(2k+1),\,\mathbf{p}_{2}\in P(n-2k-1)$. For a nonnegative integer $m\leq k$,
any $\mathbf{p}_{1}$ containing $m$ $-1$’s is greater than or equal to

$(\underbrace{-1,\ldots,-1}_{k},\underbrace{1,\ldots,1}_{k+1})\in P(2k+1).$

The number of elements $\mathbf{p}_{1}$ containing $m$ $-1$’s is
$\binom{2k+1}{m}$ and the total number is as follows:

$\binom{2k+1}{0}+\cdots+\binom{2k+1}{k}=2^{2k}.$

On the other hand, any $\mathbf{p}_{2}\in P(n-2k-1)$, the number of which is
$2^{n-2k-1}$, is obviously greater than or equal to $(-1,\ldots,-1)\in
P(n-2k-1)$. Therefore, we can obtain $2^{2k}\times 2^{n-2k-1}$ distinct
subsets satisfying the condition, which contain no complementary pair, because
otherwise $\mathbf{m}_{k}$ and $-\mathbf{m}_{k}$ are comparable by symmetry
and this contradicts $\mathbf{m}_{k}\in Q(n)$

Consequently, for each subset $S$ of $[n]$, either
$-\mathbf{m}_{k}\preceq_{P}\mathbf{p}(S)$ or
$-\mathbf{m}_{k}\preceq_{P}-\mathbf{p}(S)$ holds. ∎

In some cases, we can easily solve the partition problem.

###### Proof of Theorem 3.

Let $\mathbf{v}=-\mathbf{m}_{k}$. It follows from Lemma 23 that
$-\mathbf{m}_{k}\preceq_{Q}\mathbf{p}(S)$ or
$-\mathbf{m}_{k}\preceq_{Q}-\mathbf{p}(S)$ for any $\mathbf{p}(S)\in Q(n)$.
Either way, using Theorem 2 (1) we have
$|\mathbf{m}_{k}\cdot\mathbf{c}|\leq|\mathbf{p}(S)\cdot\mathbf{c}|$. The left-
hand side, the optimal value, is equal to $-\mathbf{m}_{k}\cdot\mathbf{c}$. ∎

We obtain the following statement for the maximal element $\mathbf{m}_{k}$ of
$Q(n)$.

######  Corollary 24.

If $\mathbf{m}_{k}\cdot\mathbf{c}\geq 0$,
$\left(\mathbf{m}_{k}-\mathcal{S}^{(k,k+1)}(-\mathbf{m}_{k})\right)\cdot\mathbf{c}\leq
0$ (applicable for $k\neq 0$), and
$\left(\mathbf{m}_{k}-\mathcal{A}^{(n)}(-\mathbf{m}_{k})\right)\cdot\mathbf{c}\leq
0$ (applicable for $k\neq(n-1)/2$) for some $k\in\\{0,1,\dots\ell\\}$, then
the subset $S$ such that $\mathbf{p}(S)=\mathbf{m}_{k}$ is a solution and the
optimal value is $\mathbf{m}_{k}\cdot\mathbf{c}$.

###### Proof.

Rewriting the three inequalities, we have

$0\leq\mathbf{m}_{k}\cdot\mathbf{c}\leq\mathcal{S}^{(k,k+1)}(-\mathbf{m}_{k})\cdot\mathbf{c},\quad
0\leq\mathbf{m}_{k}\cdot\mathbf{c}\leq\mathcal{A}^{(n)}(-\mathbf{m}_{k})\cdot\mathbf{c}.$
(5)

Since $\mathcal{S}^{(k,k+1)}(-\mathbf{m}_{k})\cdot\mathbf{c}\geq 0$,
$\mathcal{A}^{(n)}(-\mathbf{m}_{k})\cdot\mathbf{c}\geq 0$ and the elements
covering the minimal element $-\mathbf{m}_{k}$ are only
$\mathcal{S}^{(k,k+1)}(-\mathbf{m}_{k})$ for $k\neq 0$ and
$\mathcal{A}^{(n)}(-\mathbf{m}_{k})$ for $k\neq(n-1)/2$, it follows from
Theorem 2 (1) and Lemma 23 that the candidate solutions are reduced to six
elements: $\pm\mathbf{m}_{k},\pm\mathcal{S}^{(k,k+1)}(-\mathbf{m}_{k})$, and
$\pm\mathcal{A}^{(n)}(-\mathbf{m}_{k})$. The inequalities (5) imply that the
subsets $S$ such that $\mathbf{p}(S)=\pm\mathbf{m}_{k}$ are solutions and the
optimal value is $\mathbf{m}_{k}\cdot\mathbf{c}$. ∎

It is possible that these conditions could be written down for other elements
as well. It is a future problem.

## References

  * [1] B. Alidaee, F. Glover, G. A. Kochenberger, and C. Rego.  A new modeling and solution approach for the number partitioning problem.  Journal of Applied Mathematics and Decision Sciences, 2:113–121, 2005.
  * [2] C. Borgs, J. Chayes, and B. Pittel.  Phase transition and finete-size scaling for the integer partitioning problem.  Random Structures & Algorithms, 19:247–288, 2001.
  * [3] E. G. Coffman Jr. and G. S. Lueker.  Probabilistic Analysis of Packing and Partitioning Algorithms.  Wiley, Chichester, 1991.
  * [4] L. Fuksz and P. C. Pop.  A hybrid genetic algorithm with variable neighborhood search approach to the number partitioning problem.  In 8th International Conference on Hybrid Artificial Intelligence Systems, pages 649–658, 2013.
  * [5] M. R. Garey and D. S. Johnson.  Computers and intractability: A guide to the theory of NP-completeness.  W. H. Freeman, New York, 1979.
  * [6] I. P. Gent and T. Walsh.  Phase transitions and annealed theories: Number partitioning as a case study.  In W. Wahlster, editor, ECAI 96 : 12th European Conference on Artificial Intelligence, pages 170–174, Chichester, 1996. Wiley.
  * [7] A. K. Hartmann, A. Mann, and W. Radenbach.  Solution-space structure of (some) optimization problems.  Journal of Physics: Conference Series, 95:012011, 2008.
  * [8] E. Horowitz and S. Sahni.  Computing partitions with applications to the knapsack problem.  Journal of the ACM, 21:277–292, 1974.
  * [9] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon.  Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning.  Operations Research, 39:378–406, 1991.
  * [10] N. Karmarkar and R. M. Karp.  The differencing method of set partitioning.  Technical Report, Computer Science Division, University of California, Berkeley, 82/113, 1982.
  * [11] R. M. Karp.  Reducibility among combinatorial problems.  In R. E. Miller, J. W. Thatcher, and J. Bohlinger, editors, Complexity of Computer Computations, pages 85–103, Boston, 1972. Springer.
  * [12] R. E. Korf.  A complete anytime algorithm for number partitioning.  Artificial Intelligence, 106:181–203, 1998.
  * [13] S. Kubo and K. Nishinari.  An algebraic expression of the number partitioning problem.  Discrete Applied Mathematics, 285:283–296, 10 2020.
  * [14] Lindström.  Conjecture on a theorem similar to Sperner’s.  In R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinatorial Structures and Their Applications, page 241, New York, 1970. Gordon and Breach.
  * [15] S. Mertens.  Phase transition in the number partitioning problem.  Physical Review Letters, 81:4281–4284, 1998.
  * [16] W. Ruml, J. T. Ngo, J. Marks, and S. M. Shieber.  Easily searched encodings for number partitioning.  Journal of Optimization Theory and Applications, 89:251–291, 1996\.
  * [17] R. Schroeppels and A. Shamir.  A ${T}={O}(2^{n/2})$, ${S}={O}(2^{n/4})$ algorithm for certain NP-complete problems.  SIAM Journal on computing, 10:456–464, 1981.
  * [18] R. P. Stanley.  Weyl groups, the hard Lefschetz theorem, and the Sperner property.  SIAM Journal on Algebraic and Discrete Methods, 1:168–184, 1980\.
  * [19] R. P. Stanley.  Some applications of algebra to combinatorics.  Discrete Applied Mathematics, 34:241–277, 1991.
  * [20] B. D. Sullivan.  On a conjecture of Andrica and Tomescu.  Journal of Integer Sequences, 16:Article 13.3.1, 2013.
  * [21] L.-H. Tsai.  Asymptotic analysis of an algorithm for balanced processor scheduling.  SIAM Journal on Computing, 21:59–64, 1992.
  * [22] D. W. Wilson.  Sequence A025591.  The On-Line Encyclopedia of Integer Sequences, 2023.