# A simple quantum model related to decisions

Inge S. Helland
Department of Mathematics, University of Oslo
P.O.Box 1053 Blindern, N-0316 Oslo, Norway
Orcid: 0000-0002-7136-873X
Telephone: (047)93688918
E-mail<EMAIL_ADDRESS>
###### Abstract

This article may be seen as a summary and a final discussion of the work that
the author has done in recent years on the foundation of quantum theory. It is
shown that quantum mechanics as a model follows under certain specific
conditions from a quite different, much simpler model. This model is connected
to the mind of an observer, or to the joint minds of a group of communicating
observers. The model may also be connected to a theory of decisions. The
result is discussed from several angles.

Keywords: Accessible variables; conceptual variables; decisions; maximally
accessible conceptual variables; models; reproducing quantum mechanics; simple
model.

##  1 Introduction

Through a book [1] and two recent articles [2, 3], this author has developed a
different apprach towards quantum mechanics. Instead of taking the abstract
Hilbert space apparatus as a point of departure, I start with what is called
conceptual variables and some simple ideas connected to these. This, together
with a general epistemic interpretation, gives a completely new approach to
the foundation of quantum theory. This foundation can be communicated to
outsiders, and not least, it may in some sense be seen to solve the serious
problem of ‘understanding’ quantum mechanics. Thus these are really quite
radical ideas.

As an author, I have not yet received any comments, neither negative nor
postive on this book and the articles. The articles have been published in
recognized theoretical physical journals, so at least from this point of view,
there must be something to the ideas expressed there. How can then the lack of
reactions be explained? Admittedly, the papers require a new way of thinking,
and a new conceptual framework to learn. I choose to rely on something that
Carlo Rovelly recently said in a video interview: The difficult thing about
learning new things, is to dislearn what you already have learned.

Therefore it will be tried here to explain the essence of the ideas as simply
and precisely as possible, basing the whole thing on conceptual variables and
the associated decisions that we all make. It is all first formulated in terms
of a simple masurement model. The derivation of quantum mechanics from this
model under a certain condition is given explicitly, and some consequences of
the theory are discussed.

The plan of the article is: In Section 2 the basic concepts are explained, and
some literature on quantum decisions is briefly mentioned. Then Section 3
contains the main model of this article. The model is described and discussed.
In Section 4 it is shown, partly using earlier work of the author, that
quantum mechanics under certain conditions is implied by the model. This is
considered to be an important result. So-called paradoxes are addressed in
Section 5, and Section 6 gives two important examples. Macroscopic decisions
are discussed in Section 7, while Section 8 gives the final discussion.

##  2 Decisions, conceptual variables, and some corresponding literature

Of course, the phenomenon of decisions is crucial to all of us. We go through
life making decision after decision. Some of our decisions are automatic. Many
of the decisions may partly be caused by our past experiences, people that we
have met, or people that we look up to; it might be that some of these have
made similar decisions before. Our decisions may also depend in general on the
context that we are in, say the social context. But still there will be
something important left. In this article, a single actor $B$ in some context
is first considered, and it is assumed that his decisions partly depend on the
variables that he has in his mind at the moment when he makes these decisions.

These variables will be seen as primitive elements, and they will be called
conceptual variables. In [1] and [2] such variables were used as important
elements in a derivation of essential parts of quantum mechanics, using
technical assumptions related to symmetry, more concretely, group actions and
group representations. The decision involved may simply be the choice of what
to measure. The relevant decisions may be made by an actor $B$, or by a group
of communicating actors.

But the theory of decisions addressed in this article is more general. As
such, it is discussed in more detail in [3], and some of this is recapitulated
below.

In the process of making decisions, we will in general be far from perfect. So
also the actor $B$. In [3] the following is shown, using arguments connected
to one of Bell’s inequalities: Any actor may be limited when making a
decision, and this limitation may be due to the fact that he is not, at the
same time as doing the decision, able to keep enough variables in his mind.

Also, when doing decisions, $B$ may need to observe his environment, and try
to interpret these observations. Then all this is consistent with the Convival
Solipsism proposed by Zwirn [4]: Every description of the world must be
related to the mind of some actor. But other persons also have their minds,
and different persons can communicate. In a quantum mechanic setting we need
observations and variables connected to these observations, that is a
measurement theory. This will be explicitly discussed below.

Before making decisions, it may be important to achieve as much relavant
knowledge as possible. The process of achieving knowledge - an epistemic
process - is the basis for the book [1].

Alternative to a single actor making decisions, we can look at joint decisions
made by a communicating group of people. The same theory can be used, with the
following limitation: All variables must, to enable communication, be possible
to define in terms of words.

Note that in any case, the process of making decisions will be assumed to be
intimately connected to the conceptual variables that the actor or actors have
in their minds at the moment of decision.

The term ‘variable’ has not been defined here. In a physical context these may
be just physical variables. In general, a conceptual variable $\theta$ can be
one for which the question ‘What will $\theta$ be if I measure/ observe it?’
can seem meaningfull.

A conceptual variable can be a scalar or a vector, and also more general.

The purpose of this article is to describe in simple terms a model for the
process of making decisions, and from this a rather elementary quantum-like
model, a model which can be described without any advanced mathematics. The
point is now that this model can be seen as extending ordinary quantum
mechanics, in the sense that the ordinary quantum model can be derived under
the model by making some additional assumptions [1, 2].

There is a large literature on quantum decisions, and it is all related to
what I will say below. I see no reason for going into details here. A
poineering article was the one by Yukalov and Sornette [5], a couple of
authors who have since written many articles on the subject. The area is
surveyed and tied to the literature on quantum models of cognition in [6]. The
latter literature is reviewed recently in [7]. Weak points of the models and
open questions are also discussed in these articles.

This literature can be seen as a background and motivation for my development,
but it is in no way assumed in formulating the model below.

##  3 A simple measurement or decision model

A conceptual variable $\theta$ can be one for which the question ‘What will
$\theta$ be if I measure it?’ can be made meaningful. In a physical context,
the variable $\theta$ can be any physical variable like time, space variable,
momentum or spin component. A crucial assumption is that $\theta$, in addition
to its physical existence, also before, during and after measurement also
exists in the mind of an actor $B$. The variable $\theta$ may be assumed to
vary over some space $\Omega_{\theta}$.

A completely different situation, also covered below, is that $\theta$ is a
decision variable. Assume that $B$ is to choose between the prospects
$\\{\pi_{k};k=1,...,r\\}$ (a larger set of prospects may also be considered).
Define $\theta=k$ as corresponding to the case where $\pi_{k}$ is chosen. A
‘measurement’ is then thought of as the process of realizing the decision.

In any case, a set of possible conceptual variables
$\\{\theta^{a};a\in\mathcal{A}\\}$, where $\mathcal{A}$ is some index set, may
exist in the mind of the actor.

The only property that these variables are required to satisfy, is: If
$\theta$ is a conceptual variable, and $f$ is some function on
$\Omega_{\theta}$, then $\xi=f(\theta)$ is also a conceptual variable.

A conceptual variable is called _accessible_ if it is possible to find some
accurate value of $\theta$ at some point of time. An example of a physical
inaccessible variable may be the vector (position, momentum), another may be
the full spin vector. A decision variable will be inaccessible if it is
impossible for the actor to make a decision.

A partial ordering among the conceptual variables, and also among the
accessible ones, may be defined: Say that the variable $\theta$ is less than
the variable $\lambda$ if $\theta=f(\lambda)$ for some function $f$. I will
assume that, if $\lambda$ is accessible and $\theta$ is less than $\lambda$,
then $\theta$ is accessible.

An essential part of the model is now: Assume that there exists an
inaccessible variable $\phi$ such that all accessible variables can be seen as
functions of $\phi$. We can write $\theta=f(\phi)$, where $f=f_{\theta}$, or
simply $\theta=\theta(\phi)$.

In a physical context, the variable $\phi$ may be rather concrete, say a
particle’s spin vector. The psychological case is a little bit more
complicated.

In this case one may assume that $\phi$ in contained in the subconsciousness
of $B$. The actor $B$ himself will not be able to know $\phi$ consciously, but
a friend of $B$, knowing some psychology, may guess parts of $\phi$.

Using a religious language, one may say that $\phi$ is known by God. It must
be stressed, however, that what will be said in this article, does not in any
way depend on religion. (Although concrete ideas on religion [8] definitely
have inspired the writings of this author.)

Assuming the existence of such a $\phi$ may in general be seen as a
simplification. But it is a useful simplification, and it determines the
model.

The first thing that then will be done, is to introduce the important notion
of _maximally accessible_ conceptual variables. In the partial ordering
defined above, all accessible conceptual variables are dominated by $\phi$.
Therefore maximal such variables exist by assuming Zorn’s lemma. In a simple
physical setting, it follows from Heisenberg’s inequality that variables like
position, momentum - and spin components - are maximal.

Then it will be defined what is meant mean by _related_ maximal variables, say
$\theta$ and $\eta$. These are said to be related if there exists a
transformation $k$ in $\Omega_{\phi}$ such that $\eta(\phi)=\theta(k\phi)$. If
no such $\phi$ and $k$ may be found, $\theta$ and $\eta$ are said to be
essentially different.

This is all there is to the model. Note that the model may be associated with
a concrete context, physically or otherwise.

A symmetry version of the model may be defined by assuming that group actions,
transitive and with a trivial isotropy group are defined on the maximally
accessible conceptual variables, and that this group induces an invariant
measure. In the spin component, qubit, case one can take the group actions as
switching the two possible values, in the case of position or momentum one can
use the translation group.

In Section 10 of [3] a general theory of a mind’s limitation is described.
This theory is particularly relevant during the process of making decisions.
Theorem 2 in [3] says the following: Assume that the individual $B$ has two
related maximally accessible variables $\theta$ and $\eta$ in his mind. Assume
that the transformation $k$ of $\Omega_{\phi}$ belongs to a class $K$ which
has a certain property relative to the function $\theta(\cdot)$
(permissibility; see below). In this situation $B$ can not have in mind any
other maximally accessible variable which is related to $\theta$, but
essentially different from $\eta$. This result is shown in [3] to be a
consequence of what is called Theorem 1 and Theorem 2 in the next section.

##  4 Derivation of quantum mechanics

Assume now, in a concrete context, a symmetry version of the model above. In
[2] the following theorem is proved:

Theorem 1. Let $\theta$ and $\eta$ be two related maximally accessible
conceptual variables, and let $G$ be the group acting on $\theta$. Make the
following assumption:

There exists a unitary irreducible representation $U(\cdot)$ of $G$ such that
the coherent states $U(g)|\theta_{0}\rangle$ are in one-to-one correspondence
with the values of $g\in G$ and hence with the values of $\theta$.

Then there exists a Hilbert space $\mathcal{H}$ connected to the situation,
and to every accessible conceptual variable there can be associated a
symmetric operator on $\mathcal{H}$.

A symmetric operator $A$ is one for which $\langle\alpha,A\beta\rangle=\langle
A\alpha,\beta\rangle$ for all $|\alpha\rangle$, $|\beta\rangle$ in the domain
of $A$. There is a close connection between the property of being symmetric
and the property of being self-adjoint [9].

Important note.

In the setting behind this theorem, one must explicitly exclude the trivial
case where $\phi=(\theta,\eta)$, and $k$ just exchanges these two values. If
this was allowed, all maximal variables would have been related. The point is
that the proof of Lemma 1 in [2] cannot be carried out for this case.

In Theorem 1, $\theta$ and $\eta$ can be any variables. In this Section it is
important that they are physical variables. But they can also be decision
variables. It is essential that the two variables are related. The important
content of Theorem 1 is not that the Hilbert space exists, but that every
conceptual variable has an operator associated with it. In [1], these
operators are first constructed for the maximal variables, for other variables
the construction uses the spectral theorem for these operators.

The task now is to derive the rest of quantum mechanics. Then we first need a
new definition.

Definition 1. The function $\theta(\cdot)$ on the space $\Omega_{\phi}$ upon
which a group $K$ of transformations $K$ is defined is said to be
_permissible_ if the following holds: $\theta(\phi_{1})=\theta(\phi_{2})$
implies $\theta(k\phi_{1})=\theta(k\phi_{2})$ for all $k\in K$.

This notion is studied thoroughly in [10]. The main conclusion is that if
$\theta(\cdot)$ is permissible, then there is a group $G$ acting on the image
space $\Omega_{\theta}$ such that $g(\theta(\phi))$ is defined as
$\theta(k\phi)$; $k\in K$. The mapping from $K$ to $G$ is an homomorphism. If
$K$ is transitive on $\Omega_{\phi}$, then $G$ is transitive on
$\Omega_{\theta}$. (Lemma 4.3 in [1].) In the maximally accessible case it is
easy to show that $G$ has a trivial isotropy group if $K$ has a trivial
isotropy group.

A first possible application of the concept of permissibility, is the
following: Can the simple model of Section 3 really reproduce quantization?
This can perhaps be approached taking a group $K$ acting on $\Omega_{\phi}$ as
a point of departure. One can ask whether the mechanism of model reduction can
lead to quantization. Specifically, if $\theta(\cdot)$ is not permissible, it
may happen that a reduced version of $\theta$ is permissible, and that this
reduced version is discrete. This issue was briefly discussed in [1], but
requires much further investigation.

The following important result is Theorem A1 in [3]:

Theorem 2 Assume that the function $\theta(\cdot)$ is permissible with respect
to a group $K$ acting on $\Omega_{\phi}$. Assume that $K$ is transitive and
has a trivial isotropy group. Let $T(\cdot)$ be a unitary representation of
$K$ such that the coherent states $T(k)|\psi_{0}\rangle$ are in one-to-one
correspondence with $k$. For any transformation $t\in K$ and any such unitary
representation $T$ of $K$, the operator $T(t)^{\dagger}A^{\theta}T(t)$ is the
operator corresponding to $\theta^{\prime}$ defined by
$\theta^{\prime}(\phi)=\theta(t\phi)$.

By using this result in the same way as Theorem 4.2 is used in [1], a rich
theory follows. The results will first be limited to the case where $\theta$
is a discrete conceptual variable. Then one can show:

1) The eigenvalues of $A^{\theta}$ coincide with the possible values of
$\theta$.

2) The variable $\theta$ is maximally accessible if and only if the
eigenvalues of $A^{\theta}$ are non-degenerate.

3) For the maximal case the following holds in a given context: a) For a fixed
$\theta$ each question ‘What is the value of $\theta$?’ together with a sharp
answer ‘$\theta=u$’ can be associated with a normalized eigenvector of the
corresponding $A^{\theta}$. b) If there in the context is a set
$\\{\theta^{a};a\in\mathcal{A}\\}$ of maximally accessible conceptual
variables (these must by Theorem 1 be related to each other) one can consider
all ket vectors that are normalized eigenvectors of some operator
$A^{\theta^{a}}$. Then each of these may be associated with a unique question-
and-answer as above.

4) For any accessible variable $\theta$, the eigenspaces of the corresponding
operator can be associated with a question-and answer set as above. The
eigenvalues are the possible values of $\theta$.

The pure states corresponding to a question-and-answer are abundant and easy
to interpret. For instance in the spin component case, it can be proved [1]
that these constitute all possible pure states. To characterize in general
situations where this is the case, is an open problem, a problem that was
presented to the quantum community in [11]. So far, no comments on this
important problem have been received.

The mixed states are as usual formed from probability distributions over pure
states.

What is left now to construct the full text book version of quantum mechanics,
is to derive the Born formula and the Schrödinger equation from certain
assumptions. For this, the reader is referred to Chapter 5 in [1].

By considering continuous variables as limits of discrete states, a general
theory can be constructed also for these variables; see Section 5.3 in [1].
Note that Theorem 1 and Theorem 2 above also are valid for these variables.

##  5 Linear combination of states, an entangled state and so-called paradoxes

A general ket vector $|v\rangle\in\mathcal{H}$ is always an eigenvector of
_some_ operator associated with a conceptual variable. It is natural to
conjecture that this operator at least in some cases can be selected in such a
way that the accessible variable is maximally accessible. Then $|v\rangle$ is
in a natural way associated with a question-and-answer pair. It is of interest
that Höhn and Wever [12] recently derived quantum theory for sets of qubits
from such question-and-answer pairs; compare also the present derivation. Note
that the interpretation implied by such derivations is relevant for both the
preparation phase and the measurement phase of a physical system.

One may also consider linear combinations of ket vectors from this point of
view. Let the maximally accessible variable $\theta^{b}$ admits values
$u_{i}^{b}$ that are single eigenvalues of the operator $A^{b}$, uniquely
determined from $\theta^{b}$. Let $|b;i\rangle$ be the eigenvector associated
with this eigenvalue. Then one can write

$|b;i\rangle=(\sum_{j}|a;j\rangle\langle a;j|)|b;i\rangle=\sum_{j}\langle
a;j|b;i\rangle|a;j\rangle.$ (1)

This state can be interpreted in terms of a question ‘What is the value of
$\theta^{b}$?’ with the sharp answer ‘$\theta^{b}=u_{i}^{b}$’. But if one
tries to ask questions about $\theta^{a}$ for a system where the observer or
the set of observers is in this state, the answer is simply ‘I (we) do not
know’.

Also, entangled states may be considered from this point of view. Consider two
qubits 1 and 2, each having possible spin values in some fixed direction given
by +1 and -1, and look at the entangled state

$|\psi\rangle=\frac{1}{\sqrt{2}}(|1+\rangle\otimes|2-\rangle-|1-\rangle\otimes|2+\rangle).$
(2)

As discussed in [1] and references given there, this is an eigenvector of the
operator for the conceptual variable
$\delta=\theta_{x}\eta_{x}+\theta_{y}\eta_{y}+\theta_{z}\eta_{z}$
corresponding to the eigenvalue -3. Here
$\mathbf{\theta}=(\theta_{x},\theta_{y},\theta_{z})$ and
$\mathbf{\eta}=(\eta_{x},\eta_{y},\eta_{z})$ are the total spin vectors of the
two qubits, and $\delta$ is accessible to an observer observing both qubits.
Note that $\delta=-3$ implies
$\theta_{x}\eta_{x}=\theta_{y}\eta_{y}=\theta_{z}\eta_{z}=-1$, which again
implies that $\theta_{a}=-\eta_{a}$ for any direction $a$. It is trivial that
this state can be interpreted in terms of the question ‘What is $\delta$?’
together with the sharp answer ‘$\delta=-3$’. (The other possible value for
$\delta$ is -1, which corresponds to a three-dimensional eigenspace for the
operator.)

From a general point of view it may be considered of some value to have an
epistemic interpretation which is not necessarily tied to a strict Bayesian
view (see for instance [13] on this). Under an epistemic interpretation, one
may also discuss various “quantum paradoxes” like Schrödinger’s cat, Wigner’s
friend and the two-slit experiment.

In Example 1 and Example 2 below I limit myself to quantum states that can be
interpreted in terms of question-and-answers for maximally accessible
variables. In the contexts discussed, this gives an understanding where the
relevant observers are not able to distinguish between superposition and
mixture.

Example 1. Schrödinger’s cat. The discussion of this example concerns the
state of the cat just before the sealed box is opened. Is it half dead and
half alive?

To an observer outside the box the answer is simply: “I do not know”. Any
accessible e-variable connected to this observer does not contain any
information about the status of life of the cat. But on the other hand – an
imagined observer inside the box, wearing a gas mask, will of course know the
answer. The interpretation of quantum mechanics is epistemic, not ontological,
and it is connected to the observer. Both observers agree on the death status
of the cat once the box is opened.

Example 2. Wigner’s friend. Was the state of the system only determined when
Wigner learned the result of the experiment, or was it determined at some
previous point?

My answer to this is that at each point in time a quantum state is connected
to Wigner’s friend as an observer and another to Wigner, depending on the
knowledge that they have at that time. The superposition given by formal
quantum mechanics corresponds to a ‘do not know’ epistemic state. The states
of the two observers agree once Wigner learns the result of the experiment.

Example 3. The two-slit experiment. This is an experiment where all real and
imagined observers communicate at each point of time, so there is always an
objective state.

Look first at the situation when we do not know which slit the particle goes
through. This is a ‘do not know’ situation. Any statement to the effect that
the particles somehow pass through both slits is meaningless. The interference
pattern can be explained by the fact that the particles are (nearly) in an
eigenstate in the component of momentum in the direction perpendicular to the
slits in the plane of the slits. And by de Broglie’s theory, momentum is
connected to a wave. On the other hand, if an observer finds out which slit
the particles goes through, the state changes into an eigenstate for position
in that direction. In either case the state is an epistemic state for each of
the communicating observers, which might indicate that it in some sense can be
seen as an ontological state. But this must be seen as a state of the screen
and/or the device to observe the particle, not as an ontological state of the
particle itself.

##  6 Two special cases

a) Consider the spin of a spin 1/2 particle, and let $\theta^{a}$ be the spin
component in direction $a$. Then the group $G$ consists just of holding fixed
or switching the two possible values $-1$ and $+1$. To construct the Hilbert
space and the relevant operators, we need according to Theorem 1 spin
components in two directions $a$ and $b$. Let $\phi$ be the unit vector
pointing in a certain direction in the plane that is spanned by the vectors
$a$ and $b$. Let then $K$ be the rotation in this plane, and let $\theta^{a}$
be the sign of the component of $\phi$ in the $a$-direction. Then according to
Proposition 2 in [2], $\theta^{a}(\cdot)$ is permissible. To satisfy the
reqirements of Theorem 1, we also need to construct a suitable representation
of the group $G$. This group contains two elements, the unit $e$ and the group
element $g$ switching the values $-1$ and $+1$. The Hilbert space
corresponding to $\theta^{a}$ is just the space spanned by the vectors
$(0,1)^{\prime}$ and $(1,0)^{\prime}$, and for $|\theta^{a}\rangle$ being one
of these vectors, we define the coherent states

$U(g)|\theta^{a}\rangle=e^{-i\theta^{a}}|g\theta^{a}\rangle.$ (3)

This gives two coherent states. If then $|\theta^{a}\rangle$ is a linear
combination of $(0,1)^{\prime}$ and $(1,0)$, let $U(g)|\theta^{a}\rangle$ be
the corresponding linear combination of the two coherent states above. From
this, $U(g)$ can be found as a $2x2$ unitary matrix. $U(e)$ is just the unity.
It should be clear then, that by choosing some initial state
$|\theta^{a}_{0}\rangle$, the states $U(h)|\theta^{a}_{0}\rangle;h\in G$ are
in one-to-one correspondence with $h\in G$.

A further discussion of this example is given in [2].

b) Look at a single particle at some fixed time $t$. Let $\theta$ be its
position and $\eta$ its momentum. In [1], Section 5.3, this example is
considered as a limit of a discrete case, and the operators in a well-known
Hilbert space are constructed. In this example we can take
$\phi=(\theta,\eta)$, and take as the group $K$ the two-dimensional
translation group

$\theta\mapsto\theta+a,\ \ \ \eta\mapsto\eta+b.$ (4)

With respect to this group, it is obvious that $\theta$ is a permissible
function of $\phi$, and that the resulting transformation group on $\theta$ is
the onedimensional translation group $G$, which is transitive and has a
trivial isotropy group. A unitary representation $G$ with representation space
$L^{2}(\Omega_{\theta},d\theta)$, is given by

$U(g)f(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{+\infty}e^{it\theta}f(\theta)d\theta.$
(5)

By using Proposition 1 in [2], it can be proved that $\\{U(g)\\}$ is in one-
to-one correspondence with the translations $\\{g\\}$.

The resulting Hilbert space will then of course be
$L^{2}(\Omega_{\theta},d\theta)$, and the operator attached to $\theta$ is
simply to multiply by $\theta$ (cf. [1], Section 5.3). This is the position
representation, which also gives a operator for the momentum $\eta$. A
corresponding momentum representation is found by interchanging $\theta$ and
$\eta$.

The standard textbook treatment of this example follows.

##  7 Macroscopic decisions

The previous 3 Sections required some more mathematics, and a reference to
several recent or previous works. By contrast, the model of Section 3 was
relatively simple. And, importantly, the model is relevant both for
microscopic and macroscopic situations. I will here discuss aspects of such
model considerations in relation to decisions, and give some philosophy around
decisions in general.

As said in the introduction; we go through life making decision after
decision. Some of our decisions are automatic. Many of the decisions may
partly be caused by our upbringing, our past experiences, people that we have
met, or people that we look up to; it might be that some of these have made
similar decisions before. Our decisions may also depend in general on the
context that we are in, say the social context. But in addition to this, at
least some of our decisions correspond to concrete choices made specifically
by ourselves. These decisions are modelled in Section 3 by assuming that we,
as actors, have certain conceptual variables in our minds, and that our
decicions are related to these variables, either by taking the variables as
decision variables, or, in relation to measurements, choosing which maximal
variable to measure.

Decisions may be made by a single person, or by a group of communicating
persons. In the last case the persons in the group must exchange information,
and information is exchanged by using words.

Let us go back to the model of Section 3 in connection to the decisions made
by a group of people. It is no problem by assuming that the group has common
conceptual variables $\theta,\xi,\lambda,...$. A greater problem is to
establish the existence of a dominating variable $\phi$. In a physical
context, $\phi$ can correspond to a pair of variables which from physical
reasons must be seen as maximally accessible, but often, $\Omega_{\phi}$ will
be greater than the set of these pairs. (The group $K$ must be another than
the group given by exchanging the variables; conf. the note given after
Theorem 1 above.) Such variables are called, after Niels Bohr, complementery.
In the last chapter of [1], I try to generalize the complemantarity concept to
other situations than the purely physical situations. This is useful, but it
cannot give everything about common decisions.

At last, some words about political decisions, which is a large, important,
but difficult field. Ideally such decisions should be preceded by as much
knowledge as possible, and ideally again, this knowledge, to the extent that
it is not already available, should be found by scientific investigations. In
some cases this may be impractical, but on important issues, like the climate
issue, it is imperative.

It is interesting that Niels Bohr’s concept of complementarity, deeply
connected to physics, also can be seen to have applications in politics. In
the language of this article, two conceptual variables are complementary if
they are different and both maximally accessible. And conceptual variables can
be anything.

A large problem is conflicts between nations and group of nations. Often these
have a background in complementary _world views_ , a problem discussed in [1].
My general opinion is that these conflicts ought to be solved by negotiations,
not wars. In the light of complementarity or near complementarity, this may be
extremely difficult, but at least it demands good political leaders that are
capable of taking into account different cultures.

Some brief words about cultures in science. Scientific investigations are made
by single researchers or by groups of researchers, who are not always perfect
in their decisions. It is also a problem that communication may be difficult
in situations which requires researchers from different disciplines. Then a
common language may be helpful. One of the goals of the present investigation
has been to develop such a language in the case where one of the disciplines
is related to quantum theory.

But back to politics and political leaders. Some leaders may make really cruel
decisions. Examples in connection to human rights are decisions made by Stalin
or by certain chinese leaders. Adolf Hitler and his collaborators are well
known historical cases. A very actual example now are the decisions made
before, under and after the attack of Ukraine the 24. of february this year,
decisions made by Vladimir Putin and his government. These decisions are now
mainly up to president Putin to reverse. Unfortunately, his decisions are
partly made on the basis of misguided theology and philosophy founded by other
leaders.

One possibility might be that he, as a religious man, really begins to
understand the sufferings that he has induced to the Ukrainian people. Another
possibility is that the people around him start to make sensible decisions.
The sanctions made by EU and others, may have some influence, but more
important is perhaps that relevant good leaders within Russia both could be
brave enough and sensible enough to start to think independently and
rationally.

This is a scientific article, but nevertheless it must be allowed to express
here hopes for a better world.

##  8 Discussion

The interpretation of quantum mechanics that is implied by the discussion
here, is a general epistemic one, where QBism [13] is just a special case, see
arguments in [1]. Even so, ontological aspects can be discussed under this
umbrella; see [16].

The arguments of this article have been a mixture of mathematics, physics and
psychology. Many scientists, also important ones, have said that they did not
quite understand quantum mechanics. In my opinion, to really attempt a serious
understanding, we need such a mixture of arguments.

Albert Einstein [15] claimed that quantum mechanics was not a complete theory.
I prefer to use the word ‘model’ instead of ‘theory’ for quantum mechanics as
such. Together with one of its many interpretations it then constitutes a
theory. In all my writings I have advocated a general epistemic interpretation
of quantum mechanics.

As I see it, the simple model of Section 3, the symmetry version, constitutes
an extention of quantum mechanics as a model. The arguments for this are
presented in Section 4.

Another extension in a completely different direction, was recently proposed
in connection to quantum field theory by Sanctuary [17]. It is possible that
the final model could be found using such extensions.

Quantum field theory depends on abstract groups; in my opinion, more focus on
group actions on concrete variables must be desirable.

A very important requirement for the final theory should be that it should be
reconcilable with general relativity theory. Using the present approach, this
can in principle be formulated in simple terms: The purpose of relativity
theory has been to find scientific laws that are the same for all observers,
whether they move uniformly or in accelerated motions with respect to each
other. In my opinion, the goal of the reconciled theory should be the same,
only that the term ‘observer’ should be understood in the meaning of the actor
or person described in Section 3 above. Some ideas in that direction are under
preparation [18].

## References

[1] Helland, I.S. (2021). Epistemic Processes. A Basis for Statistics and
Quantum Theory. 2\. edition. Springer, Cham, Switzerland.

[2] Helland, I.S, (2022a). On reconstructing parts of quantum theory from two
related maximal conceptual variables. International Journal of Theoretical
Physics 61, 69.

[3] Helland, I.S. (2022b). The Bell experiment and the limitation of actors.
Foundations of Physics 52, 55.

[4] Zwirn, H. (2016). The measurement problem: Decoherence and convivial
solipsism. Foundations of Physics 46, 635-667.

[5] Yukalov, V.I. and Sornette, D. (2014). How brains make decisions. Springer
Procedings in Physics 150, 37-53.

[6] Ashtiani, M. and Azgomi, M.A. (2015). A survey of quantum-like approaches
to decision making and cognition. Mathematical Social Sciences 75, 49-80.

[7] Pothos, E.M. and Busemeyer, J.R. (2022). Quantum Cognition. Annual Review
of Psychology 73, 749-778.

[8] Helland, I.S. (2022). On religious faith, Christianity, and the foundation
of quantum mechanics. Eur. J. Theor. Philos. 2 (1), 10-17.

[9] Hall, B.C. (2013). Quantum Theory for Mathematicians Springer, New York.

[10] Helland, I.S. (2010). Steps Towards a Unified Basis for Scientific Models
and Methods. World Scientific, Singapore.

[11] Helland, I.S. (2019). When is a set of questions to nature together with
sharp answers to those questions in one-to-one correspondence with a set of
quantum states? arXiv: 1909.08834 [quant-ph].

[12] Höhn, P.A. and Wever, C.S.P. (2017). Quantum theory from questions.
Physical Review A 95, 012102.

[13] Fuchs, C.A. (2010). QBism, the perimeter of quantum Bayesianism. arXiv:
1003.5209 [quant-ph].

[14] Perelomov, A. (1986) Generalized Coherent States and Their Applications
Springer-Verlag, Berlin.

[15] Einstein, A., Podolsky, B. and Rosen, N. (1935). Can quantum-mechanical
description of physical reality be considered complete? Physical Review 47,
777-780.

[16] Helland, I.S. (2021). Epistemological and ontological aspects of quantum
theory. arXiv: 2112.10484 [quant.ph].

[17] Sanctuary, B. (2022). Hyper-helicity and the foundation of QM. Preprint.

[18] Helland, I.S. (2022). Links between general relativity theory and a
version of quantum theory based on conceptual variables. In preparation.

## Appendix

To further illustrate the mixture of mathematics and psychology advocated in
this paper, consider the following discussion. The conclusion must perhaps be
taken ‘with a tongue-in-cheek’.

The saying that one cannot have more than two thoughts in one’s mind at the
same time, is made precise using concepts from the author’s published work.
This precise version is proved mathematically under certain assumptions.

This Appendix is written in the spirit of Section 3 above, but it is also
written in such a way that it can be read independently, without reading
Section 3 first.

### A1. Introduction

In some way or other, we all have some kind of mental model behind what we do
and what we say. And in what we say, we also must have in mind the persons
that we are talking to.

This Appendix is primarily intended for mathematicians. Its purpose is to try
to formulate, and prove under some assumptions a precise version of the common
saying:

‘One cannot have more than two thoughts in one’s mind at the same time.’ (6)

It is then crucial that in the above sentence, ‘thought’ means ‘maximal
thought’, a concept that can be made precise. Two different situations seem to
contradict this sentence. Either the thoughts are closely related, and then
the may in some sense seen as one thought. Or all the thoughts are essentially
different. These notions may be made precise, and what I will show, is that
these two situations are the only possible situations. Any in between case,
say two are related and two others are essentially different, is logically
impossible, using some weak assumptions and a model describing the thoughts.

The arguments follow some articles and books that I have publised on
mathematical models and on the foundation of scientific theories, among those
statistics and quantum theory; see the references above. The resulting theorem
can in fact also be applied to any ideas connected to the models behind these
theories: Either all are related, or they are all essentially different. In
the book [1] I have argued for a relationship between certain ideas.

### A2. Thoughts

First, we will need some sort of idea of what we will mean by a ‘thought’. It
will be taken here as a primitive concept. In practice, it can be anything,
from the name of the person that we are confronting now, via some sentence
that we have formulated, to a substantial scientific theory.

The only condition is that a thought $\theta$ shall belong to some space of
possible thoughts $\Omega_{\theta}$, and that functions between such spaces
can be defined. We also need a concept of ‘accessible’ thoughts, thoughts that
can be ‘realised’ in some future. This can be made precise in different ways.
One example may be that the thoughts are decision variables, that these
decisions are related to something concrete, and that that each decision will
have specific impacts on this ‘something’ later. The only formal rquirement
that, if $\lambda$ is accessible, and there is a function $f$ from
$\Omega_{\lambda}$ to a new space $\Omega_{\theta}$, then $\theta=f(\lambda)$
is also accessible.

### A3. Preliminaries

Every theory is based on some assumptions, so also in this case. First, I will
assume that Zorn’s lemma is valid. (This is related to the axiom of choice.)
Next, I will base my reasoning on some specific model of our way of thinking.
As any model, it can be critizised, but I will try to argue that it is
reasonable, at least in some cases.

The model runs as follows: A person has, at some fixed moment of time, a
number of thoughts in his mind. I will assume that there exists some
inaccessible variable $\phi$, varying in a space $\Omega_{\phi}$, with the
following property: For each possible thought $\theta$ there is a function $f$
such that $\theta=f(\phi)$.

Here is a physical example: An experimentalist will be confronted with a
concrete particle at some fixed time $t$, and thinks of measuring either
position or momentum of that particle at $t$. By Heisenberg’s inequality, the
future measurement of the vector (position, momentum) will necessarily be
connected to an inaccessible thought $\phi$ in the mind of the
experimentalist. The thoughts $\theta$ connected to position and $\xi$
connected to momentum can be seen as functions of $\phi$, and in some sense
that will be made precise below, these may be seen as maximal thoughts in this
context.

In a more general psychological situation, $\phi$ may be some abstract thought
belonging to the subconsciousness of a concrete person $A$. As a model, all
thoughts in the mind of $A$ in some context may be thought of as functions of
$\phi$. The thought $\phi$ will of course be inaccessible to $A$ himself, but
some friend of $A$, knowing some psychology, may be able to guess parts of
$\phi$.

In a religious setting, $\phi$ may be thought of as being related to $A$’s
faith in God. This is of course just an example; the theory of this paper is
not in any way related to religion.

The model above may, as any model, be seen as a simplification. But I will
claim that it is a useful simplification.

Two thoughts $\theta$ and $\xi$ are seen as related if there is an
inaccessible $\phi$ and a transformation $k$ on $\Omega_{\phi}$ such that
$\theta=f(\phi)$ and $\xi=f(k\phi)$ for some function $f$. This requires that
$\Omega_{\theta}$ and $\Omega_{\xi}$ are in one-to-one correspondence. If no
such $k$ can be found, we say that $\theta$ and $\xi$ are essentially
different. If the choice of variable $\phi$ is fixed, we will say that
$\theta$ and $\xi$ are related relative to $\phi$.

Now appeal to Zorn’s lemma. We can define a partial ordering of the thoughts
of a person $A$: We say that the thought $\xi$ is ‘less than’ the thought
$\theta$ if $\xi=h(\theta)$ for some function $h$. This is a partial ordering
both among all thoughts in $G$ and also among the accessible thoughts in $G$.
Then, since all thoughts in $G$ are dominated by $\phi$, it follows from
Zorn’s lemma that there exist maximally accessible thoughts. These are
important.

### A4. Permissibility

It may be useful to assume that transformations can be defined on a space of
thoughts.

Definition The function $f(\cdot)$ from a space $\Omega_{\phi}$ upon which a
group of transformations $K$ is defined, to a space $\Omega_{\theta}$, is said
to be permissible if the following holds: $f(\phi_{1})=f(\phi_{2})$ implies
$f(k\phi_{1})=f(k\phi_{2})$ for all $k\in K$.

It is relatively easy to show that if $f$ is permissible, then group-actions
$G$ may be defined on $\Omega_{\theta}$ by $g(f(\phi))=f(k\phi)$ for $k\in K$.
The mapping from K to G here is a homomorphism.

In [3] the following is proved:

Theorem A1 Assume that the individual $A$ has two related maximally accessible
variables $\theta$ and $\xi$ in his mind. Then by definition
$\xi(\phi)=\theta(k\phi)$ for a transformation $k$ of $\Omega_{\phi}$.

Assume that a group $K$ of transformations of $\Omega_{\phi}$ can be defined
such that $k\in K$ and $\theta(\cdot)$ is permissible with respect to $K$. In
this situation $A$ can not simultaneously have in mind any other maximally
accessible variable which is related to $\theta$, but essentially different
from $\xi$.

### A5. The main theorem and its proof

I am now able to formulate and prove my main theorem, based on the assumptions
above. It is intended to be a precise version of the sentence which started
this article.

This will require that thoughts are seen as special cases of what I have
called conceptual variables. As I have said before, a conceptual variable may
be anything, also something as general as a thought. The actions of
mathematical groups on these thoughts may of course be discussed, but if one
assumes this, the results are quite interesting.

Theorem A2 Assume that a person $A$ in some context at some fixed time has a
set of different maximally accessible thoughts in his mind, more than two.

Assume that there is a one-to-one correspondence between the spaces behind
each of these thoughts. Then either all the thoughts are related, or they are
all essentially different.

’Proof’. Consider the three thoughts $\theta$, $\xi$ and $\lambda$. Assume
that $\theta$ and $\xi$, say, are essentially different, but that $\lambda$
and $\theta$ are related. The only other possibility, except for a symmetric
assumption, is that all three are related, or they are all essentially
different, I will prove that the assumption above, following Theorem A1, leads
to a contradiction.The proof will be complete if we can show that the
transformation $k$ relating $\lambda$ and $\theta$ is contained in a group $K$
such that $\theta(\cdot)$ is permissible with respect to this group.

Let $K$ be a group on $\Omega_{\phi}$ generated by permuting the elements of
$\Omega_{\theta}$, and keeping any information outside the vector
$(\theta,\lambda,\xi)$ constant, a subgroup of the full permutaion group doing
this, such that this subgroup is transitive and has a trivial isotropy group.
Since there is a one-to-one correspondence between the two spaces, each
permutation of the values of $\theta$ generates a permutation of the values of
$\lambda$. By assumption, $\lambda(\phi)=\theta(k\phi)$, and then the
transformation $k$ may be taken as one of these permutations.

It is left to prove that $\theta(\cdot)$ is permissible. It is straightforward
to prove that the full permutation group is permissible. Assume that
$\theta(\phi_{1})=\theta(\phi_{2})$ for two elements $\phi_{1}$ and $\phi_{2}$
of $\Omega_{\phi}$. Let $t$ be any transformation in $K$. I have to show that
$\theta(t\phi_{1})=\theta(t\phi_{2})$. But this follows, since $t$ by
definition permutes the elements of $\Omega_{\theta}$. If $\phi_{1}$ and
$\phi_{2}$ belong to the same orbit of $K$, then $t\phi_{1}$ and $t\phi_{2}$
also must do that. When $\theta(\cdot)$ is permissible with respect to a
group, it is also permissible with respect to any subgroup.

Note that, if one has more than two thoughts in one’s mind, any three of them
may be the thoughts $\theta$, $\xi$ and $\lambda$.


elect\mathchar 45\relax share}},f_{\mathsf{a\mathchar 45\relax recon\mathchar
45\relax compute}},f_{\mathsf{a\mathchar 45\relax out\mathchar 45\relax
dist}})$-hybrid model

##### Simulating communication with the environment:

In order to simulate the communication with ${\cal Z}$, every input value that
${\cal S}$ receives from ${\cal Z}$ is written on ${\cal A}$’s input tape.
Likewise, every output value written by ${\cal A}$ on its output tape is
copied to ${\cal S}$’s own output tape.

##### Simulating the PKI:

The simulator ${\cal S}$ generates
$(\texttt{sk}_{i},\texttt{vk}_{i})\leftarrow\textsf{Gen}(1^{\kappa})$ for
every $i\in[n]$.

##### Simulating the protocol:

To simulate Step 1, the simulator emulates $f_{\mathsf{a\mathchar 45\relax
elect\mathchar 45\relax share}}^{(t^{\prime},n^{\prime})}$ towards ${\cal A}$
as follows. ${\cal S}$ receives from ${\cal A}$ input values
$\\{(x^{\prime}_{i},\texttt{sk}_{i}^{\prime})\\}_{i\in{\mathcal{I}}\cap[m]}$
(replace invalid inputs with default). Next, ${\cal S}$ samples uniformly at
random two subsets
${\mathcal{C}}_{1}=\\{i_{(1,1)},\ldots,i_{(1,n^{\prime})}\\}\subseteq[m]$ and
${\mathcal{C}}_{2}=\\{i_{(2,1)},\ldots,i_{(2,n^{\prime})}\\}\subseteq[m]$, and
sets $\texttt{sk}_{i}^{\prime}=\texttt{sk}_{i}$ for every
$i\in[m]\setminus{\mathcal{I}}$. For every $j\in[n^{\prime}]$, sign
$\sigma_{(1,j)}=\textsf{Sign}_{\texttt{sk}_{1},\ldots,\texttt{sk}_{m}}(i_{(1,j)})$
and
$\sigma_{(2,j)}=\textsf{Sign}_{\texttt{sk}_{1},\ldots,\texttt{sk}_{m}}(m+i_{(2,j)})$.
Finally, generate secret shares of zero for every $i\in[m]$ as
$(s_{i}^{1},\ldots,s_{i}^{n^{\prime}})\leftarrow\textsf{Share}(0^{\kappa})$,
and hand ${\cal A}$ the output
$(i_{(2,j)},\sigma_{i_{(1,j)}},\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$, with
${\boldsymbol{s}}_{j}=(s_{1}^{j}\ldots,s_{m}^{j})$, for every
$i=i_{(1,j)}\in{\mathcal{C}}_{1}\cap{\mathcal{I}}$.

To simulate Step 2, for every $j\in[n^{\prime}]$ such that
$i_{(1,j)}\notin{\mathcal{I}}$ and $m+i_{(2,j)}\in{\mathcal{I}}$, the
simulator ${\cal S}$ sends to ${\cal A}$ on behalf of the honest party
${P}_{i_{(1,j)}}$ the value
$(\sigma_{i_{(1,j)}},\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$, intended to
${P}_{m+i_{(2,j)}}$. In addition, ${\cal S}$ receives such values from the
adversary (${\cal S}$ ignores any invalid messages from ${\cal A}$).

To simulate Step 3, the simulator emulates $f_{\mathsf{a\mathchar 45\relax
recon\mathchar 45\relax compute}}^{\texttt{vk}_{1},\ldots,\texttt{vk}_{m}}$
towards ${\cal A}$ as follows. ${\cal S}$ receives from ${\cal A}$ input
values $\\{(x^{\prime}_{m+i},z_{m+i})\\}_{m+i\in{\mathcal{I}}\cap[m+1,2m]}$,
where either $z_{m+i}={\epsilon}$ or
$z_{m+i}=(\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$ (replace invalid inputs
with default). Next, ${\cal S}$ sends the values
$\\{x^{\prime}_{i}\\}_{i\in{\mathcal{I}}}$ to the trusted party (for
$i\in{\mathcal{I}}\cap[m]$ the values $x^{\prime}_{i}$ were obtained in the
simulation of Step 1, and for $i\in{\mathcal{I}}\cap[m+1,2m]$ in the
simulation of Step 3) and receives back the output value $y$. Finally, ${\cal
S}$ hands $y$ to ${\cal A}$ for every corrupted party ${P}_{m+i}$, with
$m+i\in{\mathcal{I}}\cap[m+1,2m]$.

To simulate Step 4, the simulator sends $y$ on behalf of every honest party
${P}_{m+i_{(2,j)}}$ with $i_{(2,j)}\in{\mathcal{C}}_{2}$ and
$m+i_{(2,j)}\notin{\mathcal{I}}$ to every corrupted party ${P}_{i_{(1,j)}}$
with $i_{(1,j)}\in{\mathcal{C}}_{1}\cap{\mathcal{I}}$, and receives such
values from the adversary.

To simulate Step 5, the simulator emulates the functionality
$f_{\mathsf{a\mathchar 45\relax out\mathchar 45\relax
dist}}^{(\texttt{vk}_{1},\ldots,\texttt{vk}_{m})}$ by receiving either a value
$(\sigma_{i},y_{i})$ or an empty string ${\epsilon}$ from ${\cal A}$ for every
$i\in{\mathcal{I}}\cap[m]$, and sending $y$ to every corrupted party ${P}_{i}$
with $i\in{\mathcal{I}}\cap[m]$.

##### Simulating corruption requests by ${\cal A}$:

Whenever the adversary ${\cal A}$ requests to corrupt an honest party
${P}_{i}$, the simulator ${\cal S}$ corrupts ${\tilde{{P}}}_{i}$, learn its
input $x_{i}$ and continues as follows to compute the internal state of
${P}_{i}$, based on the timing of the corruption request:

  * •

In Step 1, before calling $f_{\mathsf{a\mathchar 45\relax elect\mathchar
45\relax share}}$: The simulator ${\cal S}$ sets the contents of ${P}_{i}$’s
input tape to be $x_{i}$. The secret signing key is set to be
$\texttt{sk}_{i}$ and the verification keys are set to be
$\texttt{vk}_{1},\ldots,\texttt{vk}_{n}$.

  * •

In Step 1, after calling $f_{\mathsf{a\mathchar 45\relax elect\mathchar
45\relax share}}$: In addition to the above, if ${P}_{i}\in{\mathcal{P}}_{1}$,
the simulator ${\cal S}$ sets the input of ${P}_{i}$ to $f_{\mathsf{a\mathchar
45\relax elect\mathchar 45\relax share}}$ to be $(x_{i},\texttt{sk}_{i})$. If
$i=i_{(1,j)}\in{\mathcal{C}}_{1}$, set the output from $f_{\mathsf{a\mathchar
45\relax elect\mathchar 45\relax share}}$ to be
$(i_{(2,j)},\sigma_{i_{(1,j)}},\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$ as
computed in the simulation.

  * •

In Step 2: In addition to the above, if $i=i_{(1,j)}\in{\mathcal{C}}_{1}$, the
simulator sets the outgoing message of ${P}_{i}$ to ${P}_{m+i_{(2,j)}}$ to be
$(\sigma_{i_{(1,j)}},\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$. If
$i=m+i_{(2,j)}$ with $i_{(2,j)}\in{\mathcal{C}}_{1}$, the simulator set the
incoming message of ${P}_{i}$ from ${P}_{i_{(1,j)}}$ as follows: if
${P}_{i_{(1,j)}}$ is honest set it to be
$(\sigma_{i_{(1,j)}},\sigma_{i_{(2,j)}},{\boldsymbol{s}}_{j})$; otherwise, set
it according to the values sent by ${\cal A}$.

  * •

In Step 3, before calling $f_{\mathsf{a\mathchar 45\relax recon\mathchar
45\relax compute}}$: In addition to the above, if
${P}_{i}\in{\mathcal{P}}_{2}$, the simulator ${\cal S}$ sets the input of
${P}_{i}$ to $f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax
compute}}$ to be $(x_{i},z_{i})$, where if $i=m+i_{(2,j)}$ with
$i_{(2,j)}\in{\mathcal{C}}_{2}$, set
$z_{i}=(\sigma_{i_{(2,j)}},\tilde{{\boldsymbol{s}}}_{j})$ where
$\tilde{{\boldsymbol{s}}}_{j}=(\tilde{s}^{1}_{j},\ldots,\tilde{s}^{n^{\prime}}_{j})$,
such that if party ${P}_{i_{(1,k)}}$ was corrupted during Step 2 then
$\tilde{s}^{k}_{j}$ is set according to the values sent by ${\cal A}$, and if
${P}_{i_{(1,k)}}$ was honest then set $\tilde{s}^{k}_{j}=s^{k}_{j}$.
Otherwise, set $z_{i}={\epsilon}$.

  * •

In Step 3, after calling $f_{\mathsf{a\mathchar 45\relax recon\mathchar
45\relax compute}}$: In addition to the above, if
${P}_{i}\in{\mathcal{P}}_{2}$, the simulator ${\cal S}$ sets the output of
${P}_{i}$ from $f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax
compute}}$ to be $y$.

  * •

In Step 4: In addition to the above, if $i=m+i_{(2,j)}$ with
$i_{(2,j)}\in{\mathcal{C}}_{2}$, the simulator sets the outgoing message of
${P}_{i}$ to ${P}_{i_{(1,j)}}$ to be $y$. If
$i=i_{(1,j)}\in{\mathcal{C}}_{1}$, the simulator sets the incoming message of
${P}_{i}$ from ${P}_{m+i_{(2,j)}}$ as follows: if ${P}_{m+i_{(2,j)}}$ is
honest set it to be $y$; otherwise, set it according to the values sent by
${\cal A}$.

  * •

In Step 5, before calling $f_{\mathsf{a\mathchar 45\relax out\mathchar
45\relax dist}}$: In addition to the above, if
$i=i_{(1,j)}\in{\mathcal{C}}_{1}$, the simulator ${\cal S}$ sets the input of
${P}_{i}$ to $f_{\mathsf{a\mathchar 45\relax out\mathchar 45\relax dist}}$ to
be $(\sigma_{i_{(1,j)}},y)$.

  * •

In Step 5, after calling $f_{\mathsf{a\mathchar 45\relax out\mathchar 45\relax
dist}}$: In addition to the above, if $i=[m]$, the simulator ${\cal S}$ sets
the output of ${P}_{i}$ from $f_{\mathsf{a\mathchar 45\relax out\mathchar
45\relax dist}}$ to be $y$.

Next, ${\cal S}$ sends the internal state of ${P}_{i}$ to ${\cal A}$.

##### Simulating post-execution corruption requests by ${\cal Z}$:

Whenever the environment ${\cal Z}$ requests to corrupt an honest party
${P}_{i}$ in the post-execution corruption phase, the simulator ${\cal S}$
proceeds to compute the internal state of ${P}_{i}$ as in a corruption request
from ${\cal A}$ _in Step 5, after calling $f_{\mathsf{a\mathchar 45\relax
out\mathchar 45\relax dist}}$_, and sends it to ${\cal Z}$.

##### Proving security.

We prove computational indistinguishability between the execution of the
protocol $\pi^{\mathsf{a\mathchar 45\relax ne}}_{n}$ running with adversary
${\cal A}$ and the ideal computation of $f_{n}$ running with ${\cal S}$ via a
series of hybrids experiments. The output of each experiment is the output of
the honest parties and of the adversary.

##### The game $\mbox{\scriptsize{\sc HYB}}^{1}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$.

This game is defined to be the execution of the protocol
$\pi^{\mathsf{a\mathchar 45\relax ne}}_{n}$ in the $(f_{\mathsf{a\mathchar
45\relax elect\mathchar 45\relax share}},f_{\mathsf{a\mathchar 45\relax
recon\mathchar 45\relax compute}},f_{\mathsf{a\mathchar 45\relax out\mathchar
45\relax dist}})$-hybrid model on inputs
${\boldsymbol{x}}\in({\\{0,1\\}^{\ast}})^{n}$ and security parameter
${\kappa}$ with adversary ${\cal A}$ and environment ${\cal Z}$ running on
auxiliary information ${z}$.

##### The game $\mbox{\scriptsize{\sc HYB}}^{2}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$.

In this game, we modify $\mbox{\scriptsize{\sc HYB}}^{1}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$ as follows. Instead of verifying the
signatures of the index of every party that provides an additional input, the
functionality $f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax
compute}}$ takes the shares ${\boldsymbol{s}}_{j}$ from parties
${P}_{m+i_{(2,j)}}$, with the $i_{(2,j)}\in{\mathcal{C}}_{2}$ that was sampled
by $f_{\mathsf{a\mathchar 45\relax elect\mathchar 45\relax share}}$.

######  Claim .

$\\{\mbox{\scriptsize{\sc HYB}}^{1}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}\stackrel{{\scriptstyle\rm
c}}{{\equiv}}\\{\mbox{\scriptsize{\sc HYB}}^{2}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}$.

###### Proof.

The claim follows from the following observations. First, For a fixed
$j\in[n^{\prime}]$, if both parties ${P}_{i_{(1,j)}}$ and ${P}_{m+i_{(2,j)}}$
are honest, then ${P}_{m+i_{(2,j)}}$ will provide $f_{\mathsf{a\mathchar
45\relax recon\mathchar 45\relax compute}}$ with the correct signature of its
index.

Second, with overwhelming probability, for at least $\left\lceil
n^{\prime}/2\right\rceil$ of the $j$’s it holds that both ${P}_{i_{(1,j)}}$
and ${P}_{m+i_{(2,j)}}$ are honest. This follows from the strong honest-
majority assumption. In more detail, since the communication between honest
parties is hidden from the adversary, he can identify that an honest party
${P}_{i}$ is in the committee ${\mathcal{C}}_{1}$, i.e., $i=i_{(1,j)}$, only
if the corresponding party ${P}_{m+i_{(2,j)}}$ in ${\mathcal{C}}_{2}$ is
corrupted and receives a message from ${P}_{i_{(1,j)}}$ (and vice versa).
Assume towards a contradiction that for $\left\lceil n^{\prime}/2\right\rceil$
of the $j$’s at least one of ${P}_{i_{(1,j)}}$ or ${P}_{m+i_{(2,j)}}$ is
corrupted. This means that the fraction of corrupted parties in one of the
committees ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ is $\beta^{\prime}\geq
1/4$. However, since by assumption there are at most $(1/8-\delta)\cdot
n=(1/4-2\delta)\cdot m$ corrupted parties at any point during the protocol’s
execution (and after its completion), it holds that in ${\mathcal{P}}_{1}$ and
in ${\mathcal{P}}_{2}$ the fraction of corrupted parties is at most
$(1/4-2\delta)$. Now, since $n^{\prime}=\omega(\log{n})$ it follows from
Section A.1.2 with overwhelming probability that if all the corruption took
place at the onset of the protocol, then the fraction of corrupted parties in
the committees is at most $(1/4-\delta)$ (by setting $\epsilon=\delta$).

It is now remains to show that other than identifying “matching parties” in
the committees (i.e., the pair of parties ${P}_{i_{(1,j)}}$ and
${P}_{m+i_{(2,j)}}$) in Steps 2 and 4, the adversary does not gain any
advantage in increasing the fraction of corrupted parties in the committees by
dynamically corrupting parties. This follows since the communication is hidden
from the adversary, and its view in the protocol (except for Steps 2 and 4) is
independent of the committees. Therefore, we derive a contradiction.

Finally, by the security of the signature scheme, the functionality
$f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax compute}}$ will not
receive input with signed index from parties outside of ${\mathcal{C}}_{2}$. ∎

##### The game $\mbox{\scriptsize{\sc HYB}}^{3}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$.

In this game, we modify $\mbox{\scriptsize{\sc HYB}}^{2}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$ as follows. Instead of computing the
function $f$ using the inputs of ${\mathcal{P}}_{2}$ as provided to
$f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax compute}}$, and the
input values of ${\mathcal{P}}_{1}$ as reconstructed from the shares provided
by the parties in ${\mathcal{C}}_{2}$, the computation of $f$ is performed as
follows. Let ${\mathcal{I}}$ be the set of corrupted parties in Step 3 when
calling $f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax compute}}$.
The input values $\\{x^{\prime}_{i}\\}_{i\in{\mathcal{I}}\cap[m]}$ provided by
the adversary to $f_{\mathsf{a\mathchar 45\relax elect\mathchar 45\relax
share}}$ and the input values
$\\{x^{\prime}_{i}\\}_{i\in{\mathcal{I}}\cap[m+1,2m]}$ provided by the
adversary to $f_{\mathsf{a\mathchar 45\relax recon\mathchar 45\relax
compute}}$ are sent to an external party that computes
$y=f(x^{\prime}_{1},\ldots,x^{\prime}_{n})$, where $x^{\prime}_{i}=x_{i}$ for
every $i\in[n]\setminus{\mathcal{I}}$.

######  Claim .

$\\{\mbox{\scriptsize{\sc HYB}}^{2}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}\stackrel{{\scriptstyle\rm
s}}{{\equiv}}\\{\mbox{\scriptsize{\sc HYB}}^{3}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}$.

###### Proof.

The claim will follow as long as $|({\mathcal{C}}_{1}\cup\\{m+i\mid
i\in{\mathcal{C}}_{2}\\})\cap{\mathcal{I}}|\leq t^{\prime}$. This follows from
the proof of Section B.2. ∎

##### The game $\mbox{\scriptsize{\sc HYB}}^{4}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$.

In this game, we modify $\mbox{\scriptsize{\sc HYB}}^{3}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})$ as follows. instead of computing shares of
the input values $\\{x_{i}\\}_{i\in[m]}$, the functionality
$f_{\mathsf{a\mathchar 45\relax elect\mathchar 45\relax share}}$ computes
shares of $0^{\kappa}$.

######  Claim .

$\\{\mbox{\scriptsize{\sc HYB}}^{4}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}\stackrel{{\scriptstyle\rm
s}}{{\equiv}}\\{\mbox{\scriptsize{\sc HYB}}^{3}_{\pi,{\cal A},{\cal
Z}}({\boldsymbol{x}},{z},{\kappa})\\}_{{\boldsymbol{x}},{z},{\kappa}}$.

###### Proof.

The claim follows from the privacy of the ECSS scheme and since
$|{\mathcal{C}}_{1}\cap{\mathcal{I}}|\leq t^{\prime}$ and $|\\{m+i\mid
i\in{\mathcal{C}}_{2}\\}\cap{\mathcal{I}}|\leq t^{\prime}$ at any point during
the protocol, except for a negligible probability. ∎

The proof now follows since $\mbox{\scriptsize{\sc
HYB}}^{4}_{\pi,{\mathcal{I}},{\cal A}({z})}({\boldsymbol{x}},{\kappa})$
exactly describes the simulation done by ${\cal S}$, and in particular, does
not depend on the input values of honest parties. This concludes the proof of
Section B.2. ∎

######  Proposition .

The communication graph of $\pi^{\mathsf{ne}}$ is strongly not an expander.

###### Proof.

The proof follows in a similar way as the proof of Section 4.1.2. ∎

######  Proposition .

Let $\rho_{1},\rho_{2},\rho_{3}$, and $\pi^{f_{i}\rightarrow\rho_{i}}$ be the
protocols defined in Section 4.4, and let $\ell_{\rho}=\ell_{\rho}(m)$ be the
upper bound of the locality of $\rho_{1},\rho_{2},\rho_{3}$. Then
$\pi^{f_{i}\rightarrow\rho_{i}}$ has locality $\ell=2\cdot\ell_{\rho}+1$.

###### Proof.

Every party in ${\mathcal{P}}_{1}$ communicates with $\ell_{\rho}$ parties
when executing $\rho_{1}$, and with at most another $\ell_{\rho}$ parties when
executing $\rho_{3}$. In addition, every party in ${\mathcal{C}}_{1}$
communicates with exactly one party in ${\mathcal{C}}_{2}$. Similarly, every
party in ${\mathcal{P}}_{2}$ communicates with $\ell_{\rho}$ parties when
executing $\rho_{2}$, and parties in ${\mathcal{C}}_{2}$ communicates with
exactly one party in ${\mathcal{C}}_{1}$. It follows that maximal number of
parties that a party communicates with during the protocol is
$2\cdot\ell_{\rho}+1$. ∎

This concludes the proof of Section 4.4. ∎

##  Appendix C Expansion is Necessary for Correct Computation (Cont’d)

We now provide complementary material for Section 5.

###  C.1 Proof of the Graph-Theoretic Theorem (Theorem 5.2)

In this section, we prove Theorem 5.2, stating that an $(\alpha,d)$-partition
exists and can be efficiently computed when the minimal degree of a vertex in
the graph is sufficiently large.

######  Theorem 5.6.

Let $c>1$ be a constant integer, let $\alpha(n)\in o(n)$ be a fixed sublinear
function in $n$, and let $\\{G_{n}\\}_{n\in{\mathbb{N}}}$ be a family of
graphs, where $G_{n}=([n],E_{n})$ is defined on $n$ vertices, and every vertex
of $G_{n}$ has degree at least $\frac{n}{c}-1$. Then, for sufficiently large
$n$ it holds that:

  1. 1.

There exists an $(\alpha(n),n/c)$-partition of $G_{n}$, denoted $\Gamma$; it
holds that $\left|\Gamma\right|\leq c$.

  2. 2.

An $(\alpha(n),n/c)$-partition $\Gamma$ of $G_{n}$ can be found in
(deterministic) polynomial time.

In Section C.1, we prove the existence of such a partition; and in Section
C.1, we present a deterministic polynomial-time algorithm for computing it.
Recall that given a graph $G$ with $n$ vertices and a subset $S\subseteq[n]$,
we denote by $\textsf{edges}(S)=\textsf{edges}(S,\bar{S})$ the set of edges
from $S$ to its complement.

######  Lemma .

Consider the setting of Theorem 5.2. Then, there exists an
$(\alpha(n),n/c)$-partition $\Gamma$ of $G_{n}$, and it holds that
$\left|\Gamma\right|\leq c$. Furthermore, the number of $\alpha(n)$-cuts in
$G_{n}$ is at most $2^{c-1}$.

###### Proof.

Let $n\in{\mathbb{N}}$ and let

$\left\\{\\{S_{1},\bar{S}_{1}\\},\ldots,\\{S_{\ell},\bar{S}_{\ell}\\}\right\\}$

be the set of all $\alpha(n)$-cuts in $G_{n}$, i.e., for every $i\in[\ell]$ it
holds that

$\left|\textsf{edges}_{G_{n}}(S_{i})\right|\leq\alpha(n).$ (8)

We proceed by defining the following family of subsets

$\Gamma=\left\\{\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}:(b_{1},b_{2},\ldots,b_{\ell})\in\\{0,1\\}^{\ell}\right\\}\setminus\left\\{\emptyset\right\\},$

where for every $i\in[\ell]$ and $b\in\\{0,1\\}$, the set $S_{i}^{b}$ is
defined as

$S_{i}^{b}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\begin{cases}S_{i}&\text{\em
if }b=0,\\\ \bar{S_{i}}&\text{\em if }b=1.\end{cases}$

We will show that for sufficiently large $n$, the set $\Gamma$ is an
$(\alpha(n),n/c)$-partition of $G_{n}$ and that $|\Gamma|\leq c$. We start by
proving two useful claims.

######  Claim .

For every $S\subseteq[n]$, if $1\leq|S|\leq\frac{n}{c}-1$ then
$|\textsf{edges}_{G_{n}}(S)|\geq\frac{n}{c}-1$.

###### Proof.

Consider an arbitrary set $S\subseteq[n]$. The claim follows from the
following set of inequalities:

$\displaystyle|\textsf{edges}_{G_{n}}(S)|$ $\displaystyle=(\text{total degree
of the vertices in $S$})$ $\displaystyle\hskip 85.35826pt-2\cdot(\text{total
number of edges whose both vertices are inside $S$})$
$\displaystyle\geq|S|\cdot\left(\frac{n}{c}-1\right)-2\cdot\binom{|S|}{2}$
$\displaystyle=|S|\cdot\left(\frac{n}{c}-1\right)-|S|\cdot\left(|S|-1\right)$
$\displaystyle=|S|\cdot\left(\frac{n}{c}-|S|\right)$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{\geq}}\frac{n}{c}-1.$

The last inequality $(\ast)$ follows since for a constant $a$ and $1\leq x\leq
a-1$, if $f(x)=x(a-x)$ then $a-1\leq f(x)\leq\frac{a^{2}}{4}$. In our case
$1\leq|S|\leq\frac{n}{c}-1$; therefore

$\frac{n}{c}-1\leq\left|S\right|\cdot\left(\frac{n}{c}-\left|S\right|\right)\leq\frac{n^{2}}{4c^{2}}.$

This concludes the proof of Section C.1. ∎

######  Claim .

For every $(b_{1},b_{2},\ldots,b_{\ell})\in\\{0,1\\}^{\ell}$, either
$\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}=\emptyset$ or
$|\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}|\geq n/c$.

###### Proof.

Suppose, to the contrary, that there exists an $\ell$-bit vector
$(b_{1},b_{2},\ldots,b_{\ell})\in\\{0,1\\}^{\ell}$ such that
$1\leq|\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}|\leq\frac{n}{c}-1$. Let us consider
the following nested sequence of sets

$A_{\ell}\subseteq\ldots\subseteq A_{2}\subseteq A_{1},$

where for every $j\in[\ell]$ the set $A_{j}$ is defined as
$A_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bigcap_{i=1}^{j}S_{i}^{b_{i}}$.
Since $A_{1}=S_{1}^{b_{1}}$ and $S_{1}$ satisfies Equation 8, it holds that

$|\textsf{edges}_{G_{n}}(A_{1})|\leq\alpha(n).$ (9)

Also, since $A_{\ell}=\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}$ and
$|\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}|\leq\frac{n}{c}-1$ (by assumption), it
follows from Section C.1 that

$|\textsf{edges}_{G_{n}}(A_{\ell})|\geq\frac{n}{c}-1.$ (10)

The following two cases can occur:

##### Case 1.

For every $j\in[\ell-1]$, either $A_{j}\setminus A_{j+1}=\emptyset$ or
$|A_{j}\setminus A_{j+1}|\geq n/c$: Consider the set
$\mathcal{I}=\\{i\in[\ell-1]:A_{i}\setminus A_{i+1}\neq\emptyset\\}$. It
follows from the assumption that for every $i\in\mathcal{I}$, $|A_{i}\setminus
A_{i+1}|\geq n/c$. Since these sets are disjoint and $A_{\ell}$ is non-empty,
we have $|\mathcal{I}|\leq c-1$. Note that there are at least $n/c-1$ edges
which are coming out of $A_{\ell}$. Since
$|\textsf{edges}(A_{1})|\leq\alpha(n)$, at least $n/c-1-\alpha(n)$ of these
edges (whose one end-point is inside $A_{\ell}$) must have their other end-
point inside $A_{1}\setminus A_{\ell}$. Observe that $A_{1}\setminus
A_{\ell}=\bigcup_{i=1}^{\mathcal{I}}A_{i}\setminus A_{i+1}$, which implies
$|\textsf{edges}(A_{\ell},A_{k}\setminus
A_{k+1})|\geq\frac{(n/c)-1-\alpha(n)}{c-1}$ for some $k\in\mathcal{I}$. Since
$A_{\ell}\subseteq S_{k+1}^{b_{k+1}}$, which is disjoint from $A_{k}\setminus
A_{k+1}$, we have
$|\textsf{edges}(S_{k+1}^{b_{k+1}})|\geq\frac{(n/c)-1-\alpha(n)}{c-1}$. Now,
since $\alpha(n)$ is a sub-linear function in $n$, for sufficiently large $n$
we have that $|\textsf{edges}(S_{k+1}^{b+1})|>\alpha(n)$, which is a
contradiction to Equation 8.

##### Case 2.

$0<|A_{j}\setminus A_{j+1}|\leq n/c-1$ for some $j\in[\ell-1]$: As in the
previous case, consider the set $\mathcal{I}=\\{i\in[\ell-1]:A_{i}\setminus
A_{i+1}\neq\emptyset\\}$. Let $k\in\mathcal{I}$ be the first index such that
$0<|A_{k}\setminus A_{k+1}|\leq n/c-1$. Define another set
$\mathcal{I}^{\prime}=\\{i\in\mathcal{I}:i\leq k\\}$. Since $k\in\mathcal{I}$
is the first index such that $0<|A_{k}\setminus A_{k+1}|\leq n/c-1$, the
number of $i$’s such that $i\in\mathcal{I}$ and $i\leq k$ must be less than
$c$, which implies that $|\mathcal{I}^{\prime}|\leq c-1$. Note that $A_{k}$
and $A_{k}\setminus A_{k+1}$ can be written as
$A_{k}=\bigcap_{i\in\mathcal{I}^{\prime}}S_{i}^{b_{i}}$ and $A_{k}\setminus
A_{k+1}=\bigcap_{i\in\mathcal{I}^{\prime}}S_{i}^{b_{i}}\bigcap
S_{k+1}^{b_{k+1}\oplus 1}$, respectively. Let
$s\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=|\mathcal{I}^{\prime}|$.
For simplicity of notation, let us renumber these cuts from 1 to $s+1$, i.e.,
let
$\\{S_{1},S_{2},\ldots,S_{s+1}\\}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{S_{i}:i\in\mathcal{I}^{\prime}\\}\bigcup
S_{k+1}$. With this notation, there exists some
$(\hat{b}_{1},\hat{b}_{2},\ldots,\hat{b}_{s+1})\in\\{0,1\\}^{s+1}$, such that
$A_{k}\setminus A_{k+1}=\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}}$ Since
$0<|A_{k}\setminus A_{k+1}|\leq n/c-1$, we have from Section C.1 that
$|\textsf{edges}(\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}})|\geq n/c-1$.

Note that for any edge
$(u,v)\in\textsf{edges}(\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}})$, it holds
that $v\in\bigcap_{i=1}^{s+1}S_{i}^{e_{i}}$ for some
$(e_{1},e_{2},\ldots,e_{s+1})\in\\{0,1\\}^{s+1}$. Since
$|\textsf{edges}(\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}})|\geq n/c-1$, there
exists $(\hat{e}_{1},\hat{e}_{2},\ldots,\hat{e}_{s+1})\in\\{0,1\\}^{s+1}$ such
that
$|\textsf{edges}(\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}},\bigcap_{i=1}^{s+1}S_{i}^{\hat{e}_{i}})|\geq\frac{(n/c)-1}{2^{s+1}}$.
Since $s+1=|\mathcal{I}^{\prime}|+1\leq c$, we have

$\displaystyle\left|\textsf{edges}\left(\bigcap_{i=1}^{s+1}S_{i}^{\hat{b}_{i}},\bigcap_{i=1}^{s+1}S_{i}^{\hat{e}_{i}}\right)\right|\geq\frac{(n/c)-1}{2^{c}}.$
(11)

Since
$(\hat{b}_{1},\hat{b}_{2},\ldots,\hat{b}_{s+1})\neq(\hat{e}_{1},\hat{e}_{2},\ldots,\hat{e}_{s+1})$,
there exists $l\in[s+1]$ such that $\hat{b}_{l}\neq\hat{e}_{l}$. This,
together with Equation 11, implies that
$|\textsf{edges}(S_{l})|\geq\frac{(n/c)-1}{2^{c}}$. Since $c$ is a constant,
it holds $\frac{(n/c)-1}{2^{c}}>\alpha(n)$ for sufficiently large $n$,
implying that $|\textsf{edges}(S_{l})|>\alpha(n)$, which is a contradiction to
Equation 8. This concludes the proof of Section C.1. ∎

Now we show that $\Gamma$ is an $(\alpha(n),n/c)$-partition of $G_{n}$. First
observe that the union of all the sets in $\Gamma$ is indeed $[n]$. By Section
C.1 for every $S\in\Gamma$ it holds that $|S|\geq n/c$. Furthermore, for every
$\alpha(n)$-cut $\\{S_{j},\bar{S}_{j}\\}$ it holds that $S_{j}$ and
$\bar{S}_{j}$ can be represented as a union of some sets from $\Gamma$, more
precisely

$S_{j}=\bigcup_{(\vec{b}\in\\{0,1\\}^{\ell}\ :\
b_{j}=0)}\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}\quad\text{ and
}\quad\bar{S}_{j}=\bigcup_{(\vec{b}\in\\{0,1\\}^{\ell}\ :\
b_{j}=1)}\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}.$

In addition, it is easy to see that the sets in $\Gamma$ are pairwise
disjoint, and since each is of size at least $n/c$ it holds that $|\Gamma|\leq
c$.

To show that distinct sets from $\Gamma$ have at most $\alpha(n)$ crossing
edges, consider two different sets $U_{i},U_{j}\in\Gamma$. There exist
distinct binary vectors $\vec{b},\vec{e}\in\\{0,1\\}^{\ell}$ such that
$U_{i}=\bigcap_{k=1}^{\ell}S_{k}^{b_{k}}$ and
$U_{j}=\bigcap_{k=1}^{\ell}S_{k}^{e_{k}}$. Let $\hat{k}\in[\ell]$ be an index
such that $b_{\hat{k}}\neq e_{\hat{k}}$. Since (1) $U_{i}\subseteq
S_{\hat{k}}^{b_{\hat{k}}}$, (2) $U_{j}\subseteq S_{\hat{k}}^{e_{\hat{k}}}$,
(3) $S_{\hat{k}}^{b_{\hat{k}}}\cap S_{\hat{k}}^{e_{\hat{k}}}=\emptyset$, and
(4)
$|\textsf{edges}(S_{\hat{k}}^{b_{\hat{k}}},S_{\hat{k}}^{e_{\hat{k}}})|\leq\alpha(n)$,
it holds that $|\textsf{edges}(U_{i},U_{j})|\leq\alpha(n)$.

Finally, since $|\Gamma|\leq c$ and for every $\alpha(n)$-cut
$\\{S_{j},\bar{S}_{j}\\}$ it holds that $S_{j}$ and $\bar{S}_{j}$ can be
represented as a union of some sets from $\Gamma$, we have that $\ell\leq
2^{c}-1$ (which is the total number of nonempty subsets of $\Gamma$). However,
a cut is defined by two such subsets; therefore it holds that the total number
of $\alpha(n)$-cuts is at most $2^{c-1}$.

This completes the proof of Section C.1. ∎

Section C.1 proved existence of a partition. In Section C.1, we show how to
efficiently find such a partition. A core element of our algorithm is the
algorithm for enumerating all cuts of a weighted graph due to Vazirani and
Yannakakis [87] that runs in polynomial time with $\tilde{O}(n^{2}m)$ delay
between two successive outputs (i.e., once the $i$’th cut was found, this is
the running time needed to produce the $(i+1)$’th cut). Yeh et al. [88]
reduced the delays to $\tilde{O}(nm)$.

######  Theorem C.1 ([87, 88]).

Let $G=(V,E)$ be a weighted undirected graph on $n$ vertices and $m$ edges.
There exists a deterministic polynomial-time algorithm to enumerate all the
cuts of $G$ by non-decreasing weights with $\tilde{O}(nm)$ delay between two
successive outputs.

######  Lemma .

Consider the setting of Theorem 5.2. Then, for sufficiently large $n$, an
$(\alpha(n),n/c)$-partition $\Gamma$ of $G_{n}$ can be found in polynomial
time (precisely in $\tilde{O}(n^{3})$ time).

###### Proof.

We start by assigning weight $1$ to every edge of our graph $G_{n}$ and run
the algorithm from Theorem C.1 on this weighted graph. We enumerate all cuts
by non-decreasing weights until we hit a cut whose weight is more than
$\alpha(n)$. Since the total number of $\alpha(n)$-cuts is at most $2^{c-1}$,
we stop this algorithm after it has enumerated at most $2^{c-1}$ cuts.

Let $\\{S_{1},\bar{S}_{1}\\},\ldots,\\{S_{\ell},\bar{S}_{\ell}\\}$ denote all
the $\alpha(n)$-cuts of $G_{n}$. We define the partition $\Gamma$ as above

$\Gamma=\left\\{\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}:(b_{1},b_{2},\ldots,b_{\ell})\in\\{0,1\\}^{\ell}\right\\}\setminus\left\\{\emptyset\right\\}.$

Following the proof of Section C.1, the partition $\Gamma$ is an
$(\alpha(n),n/c)$-partition of $G_{n}$.

##### Running time analysis.

Since $c$ is a constant and total number of edges in our graph is $O(n^{2})$,
we can generate all the $\alpha(n)$-cuts in $\tilde{O}(n^{3})$ time using the
algorithm of Yeh et al. [88]. Once we have found all the $\alpha(n)$-cuts,
generating the $(\alpha(n),n/c)$-partition takes $O(n)$ time: since the total
number of cuts $\ell$ is constant, computing
$\bigcap_{i=1}^{\ell}S_{i}^{b_{i}}$ for any fixed vector
$(b_{1},b_{2},\ldots,b_{\ell})\in\\{0,1\\}^{\ell}$ takes $O(n)$ time. We are
computing $2^{\ell}\leq 2^{2^{c-1}}$ such intersections corresponding to the
$2^{\ell}$ vectors. Because $c$ is a constant, the total time is still $O(n)$.
Hence, the total time required by our procedure for finding an
$(\alpha(n),n/c)$-partition is $\tilde{O}(n^{3})$. This completes the proof of
Section C.1. ∎