[1]VS Morales-Salgado

[1]CEDIP, Cámara de Diputados, H. Congreso de la Unión 66, El Parque,
Venustiano Carranza, 15960, Mexico City, Mexico

# Social Mechanics

<EMAIL_ADDRESS>*

###### Abstract

Social physics is the application of ideas, concepts and tools from physics to
study social phenomena. In this article, we present a mechanical theory
underlying a mathematical treatment of social physics. We explore the
possibility of using fundamental concepts like position, motion, inertia, and
interaction, to effectively regard social phenomena analogously to particles
interacting with each other in physics. From these concepts, along with
heuristics of social change, we investigate the notions of free motion, motion
under the influence of a net deterministic, as well as stochastic force. To
test these ideas we model partisan preferences in the United States according
to the outcomes of presidential elections.

###### keywords:

Social change, human behaviour, partisan preferences

##  1 Introduction

The objective of this work is to employ the key idea behind social physics
that, under appropriate conditions, the tools developed to describe physical
systems can be used to describe certain social systems [2, 1]. We focus on
fundamental mechanical concepts to contribute towards understanding social
change, its nature and its causes. Even more, establishing appropriate
analogues of mechanics in social phenomena contributes to further explore
connections of other physical concepts in a systematic way. This may be so
since mechanical concepts are foundational to other areas of physics like
thermodynamics, quantum mechanics, and general relativity, given the
appropriate mechanisms like statistical mechanics, quantization and covariant
formulations, respectively.

We are looking for a description of social phenomena in terms of stances about
a social question (position) [3, 4, 5], social change (motion) [6, 7, 17],
predisposition to change (inertia) [8, 9, 10, 11], advocacy and compellingness
(forces and interactions) [12, 13], and others in a similarly fashion.
However, we expect the analogy not to be perfect, but a useful approximation
[14, 16]. We also expect there to be differences in the relations among them
compared to what happens in physics. In other words, one would expect that a
possible mechanical theory of social change be a genuine _social mechanics_ in
its own right.

In a substantial part, this proposal aims to provide a mathematical framework
to observations about social change like the following, taken from [17]: “It
is important to emphasize that with small variations in starting points and
inertia, resistance, or participation at the crucial points, social change may
or may not happen. Suppose that a community has long had a norm in favor of
discrimination based on sexual orientation; that many people in the community
abhor that norm; that many others dislike it and that many others do not care
about it; that many others are mildly inclined to favor it; and that many
others firmly believe in it. If norm entrepreneurs make a public demonstration
of opposition to the norm, and if the demonstration reaches those with
relatively low thresholds for opposing it, opposition will immediately grow.
If the growing opposition reaches those with relatively higher thresholds, the
norm might rapidly collapse. But if the early public opposition is barely
visible or if it reaches only those with relatively high thresholds, it will
fizzle out and the norm might not even budge”. This considerations show
similarities between evolution of social systems and that of physical systems.
Indeed, the coincidences mostly distil from the more fundamental concept of
change with respect of time.

Indeed, the work presented here belongs to the realm of quantitative methods
and mathematical models for human and social research [15]. As such, it does
not give a fundamental explanation of why such systems behave the way they do.
What it does is to provide tools to model this behaviour to help investigate
its nature through measurable traits. We do not pretend to substitute already
existing theories about social behaviour, but to aid them by introducing
quantitative tools based on well known results about analogous models in
physics.

We are confident that the results will prove interesting to both social
researchers, as well as physicists. On the one hand, investigators of social
phenomena can put these results to test while also using them to characterize
individuals and populations, their traits and conditions, as well as the
possible relations among all of them. On the other hand, we believe that
physicists will find that the resulting generalizations of physical concepts
yield novel and fascinating possibilities to further develop them.

The rest of the article is organized as follows: In Section 2 we introduce and
develop fundamental concepts for a mechanical theory of social change
analogously to classical mechanics in its Newtonian formulation. In Section 3
we use those fundaments to describe some initial models. Specifically, we
study the motion of a particle subject to free motion, a force described by
Hooke’s law, and a stochastic interaction, governed by the Smoluchowski
equation. As an example of the use of this last one for modelling real data,
we describe partisan preferences in the United States as outlined by
presidential elections. In Section 4 we briefly discuss how other formulations
of mechanics, known to be equivalent to the famous Newton’s laws can be
understood in the light of our proposal. Finally, in Section 5 we present the
concluding remarks of this investigation, as well as a some prospective lines
to continue this research.

##  2 Fundamental concepts

In this section we will present the concepts that will allow us to build a
mechanical theory of social change. A particle in our social models represents
an single conviction held by a unit of the social universe. Just like in
physics, here a particle is an idealization [18]. It helps to describe the
simplest component of matter, here understood as a society, and upon
aggregation with other particles yields more complicated forms of social
matter. Actually, this illustrates a powerful trait of physics: it departs
from simple cases to be aggregated non-trivially to explain more complex
phenomena.

Since societies are composed of individuals, a particle can be readily
identified with the convictions of an individual person. However, other
realizations of a particle could be made [19]. For example, a social group
fairly homogeneous with respect to a trait of interest could be identified
with a particle, just like the centre of mass of an extended object, e.g. a
ball, can be identified with a particle, although it is composed of more
fundamental particles.

###  2.1 Position

The first concept that we wish to discuss is that of _position_ or, more
generally, _configuration_. The position of a social system should describe
its status with respect to an attribute of which change (or lack thereof)
occurs. More concretely, a positions can be identified with beliefs,
convictions or stances about a social question. Then, a position in social
mechanics is treated here in the sense of the common phrasing “what is your
position on this topic?—My position on it is…” and others similar to these.

We also require the position to be describable by coordinates in a space.
Thus, this _space_ is generally the set of all possible positions an
individual can take on a topic. More specifically, the system at hand shall
give us hints on the mathematical properties of such a space. For brevity, we
can think of this space as a subset of $\mathbb{R}^{n}$, that is, we can
specify a position by $n$ real coordinates in the usual notation
$(x_{1},x_{2},\dots,x_{n})$.

This picture has some underlying assumptions about the type of characteristics
that can be modelled by it. We suppose that in the space of social positions
we can assign univocally a set of coordinates $(x_{1},x_{2},\dots,x_{n})$ to a
given stance. That is, we can somehow measure stances or, at least, there is a
proxy way of measuring them. We also suppose that there is a “well-behaved”
way of comparing different stances. This is a matter that is readily found in
the fundaments of some already existing conceptual frameworks around social
phenomena, like in the utility theory of economics.

###  2.2 Motion

Since we wish to describe _motion_ , i.e. evolution or change with respect to
time $t$, each $x_{i}$, where $i=1,\dots,n$, is in general a function of time:
$x_{i}=x_{i}(t)$. For example, consider the somewhat common affirmation that
“fashion is cyclical”. This statement refers to a social trait: a stance on a
way of dressing, but it also depicts heuristically an observation about how
this trait evolves in time. Even more, it claims a change in time very much
familiar to physics: an oscillatory motion. Such a model of a trait varying in
time is not new in social sciences and should be understood closely related to
the method of analysing time series.

To illustrate motion in social mechanics, let us suppose that $n=1$, then we
only need one number or coordinate $x$ to describe the stance of an individual
or group of individuals regarding an issue like, for instance, a policy. As an
example, this evolution could look like in Figure 1, where a positive $x$
means an stance favourable towards the policy, the more positive, the more
favourable; a negative $x$ implies an unfavourable view of the policy, the
more negative, the more critical; and $x=0$ is a position of indifference
towards the policy.

Figure 1: Example of a possible evolution of a stance $x=x(t)$.

We can see that the exemplified evolution describes a strong initial negative
stance on the issue, followed by a change towards a strong positive view and
further oscillations the settle in a rather positive althoug moderate stance.
The heuristics behind the example is an agent exploring different stances,
possibly in response to new evidence, maturing towards a definite position on
the topic. Of course, we have assumed a continuous behaviour of the stance
with respect to time. However, this is an illustration and assumptions can be
dropped or added according to the phenomena of interest.

Note that a trivial state of motion is possible: no motion at all, also called
_rest_. In fact, we can see that the particle described in Figure 1 tends
towards rest as time goes by.

###  2.3 Inertia

So far the concepts we presented have not been particularly heavy on physics.
Position as a stance on social issues and motion as a a change in position
over time have been used in social sciences by other names in a transparent
way. Now, we proceed to a concept that is in the kernel of mechanical
treatments in physics: inertia.

Inertia is the tendency to maintain a specific state of motion, usually called
_free motion_. Conversely, this tendency can be understood as an opposition to
change the state of motion in response to efforts to modify it. Upon
observations of different systems we can assign a parameter quantifying said
opposition. We call it _inertial mass_ or just mass, for now. This mass,
usually denoted by $m$, provides us with a powerful quantifiable property to
characterize how individuals, or groups of them, respond to change. In
physical heuristics, there are individuals that are heavier or lighter than
others depending on how difficult or easy it is to provoke a change in their
motion, respectively.

From Newton’s first law of mechanics, the state of free motion in physics is
the uniform linear motion. In turn, this is closely related to the idea of
particles having a constant inertial parameter, that is, mass. However, there
is no reason for this to be the case for social phenomena. In fact, we shall
see that it makes sense to have _social masses_ that depend on the position of
the particle. This is one of the interesting generalizations resulting from
applying physical ideas to social studies.

There is another quantity closely related to mass. It is the _momentum_ ,
usually denoted by $p=m\,\frac{{\rm d}x_{i}}{{\rm d}t}$, that is, the product
of the mass $m$ and the velocity $\frac{{\rm d}x_{i}}{{\rm d}t}$, which is the
rate of change of the position $x_{i}$ in time, obtained by deriving $c_{i}$
with respect to time $t$. It is closely related because, as we shall see, it
is the quantity upon which externalities act more directly and transparently.
The reason being that $p$ encompasses, by definition, both the state of motion
and the opposition to change it. Thus, when we refer to the state of motion we
mean a given momentum $p$.

###  2.4 Interaction

Mass is a property of the particle susceptible of motion, even if it depends
on its position. On the other hand, we still need to describe externalities,
that is, the action of others on the particle. We do this through the concept
of _force_. Forces are in general functions of position and time:
$F=F(x_{i},t)$, where $i=1,\dots,n$ and the specific mathematical expression
is proposed and confirmed for each social phenomena.

In line with previously introduced concepts, a force is an influence causing a
change in the state of motion of a particle. Similarly, here an _interaction_
is the exercise of forces among several particles. We say “here” because in
physics there are other formulations of mechanics. For now, we shall stick to
the use of forces since they are valuable in explaining intuitively the
comparison between physical and social phenomena.

A concept closely related to motion and force is that of _equilibrium_ in that
it is observed as a lack of change in the motion due to the exact balance of
opposing forces. Indeed, the lack of a net resulting force on a particle is
not rest but the continuance of its current motion.

Before we move on, a caveat is at hand. we have described position as points
in a space of possible stances and, with it, we have disregarded physical
space, that is geographical separation between individuals and societies. So,
how are they interacting? Certainly, there must be a physical channel carrying
interactions. Whether it be in-person conversations, interactions through
social media, action through an intermediate individual, or other ways, it
does not matter for our current formulation.

In this work we are concerned about the effect of the interaction on the
stances of each participant in a social group and with a given social
environment. We do not mean to say that physical distance is unimportant.
Rather that we assume that a channel for communicating interactions is already
established of which the physical separation, as well as other properties,
form the set of parameters shaping the interaction in the space of social
positions.

Modernity is key to the relevance of this framework. In the past, when social
systems contained a smaller population, the exchange of ideas only occurred
when people physically encountered each other and in a slower rate. Nowadays,
there is a bigger, faster and more interacting community. There is also more
data available to be understood on itself, but also to better understand
social change, in general.

##  3 A mechanical theory of social change

Here we put all the ideas from the past section to work by building
mathematical relations among them. We also derive some consequences and
develop intuition through some general examples.

###  3.1 The motion of a particle

Again, analogously to classical mechanics, we rely on an idealization of the
minimal unit of study. In physics it is the _particle_ , while for social
systems this could be an individual person, for example. Next, from the
conceptual considerations discussed in previous sections, we may present the
law of change for an individual in terms of the momentum $p$:

$F=\frac{{\rm d}p}{{\rm d}t}\,.$ (1)

This realizes the ideas exposed since it can be read as “the net force $F$ on
a particle produces a change, with respect to time, in the state of motion
$\frac{{\rm d}p}{{\rm d}t}$”. It is rather convenient too, because the
momentum helps describe the tendency of a change in the state of the
individual as well as a way to compare the opposition to change between
different individuals. This is clearer in the known presentation of mechanical
momentum as $p=mv$, where the velocity is given by $v=\frac{{\rm d}x}{{\rm
d}t}$. Thus, we can write

$F=\frac{{\rm d}}{{\rm d}t}\left(m\,\frac{{\rm d}x}{{\rm d}t}\right)\,.$ (2)

Now, some common simplifying assumptions from physics are not so immediately
applied in human behaviour scenarios. For example, mass in classical mechanics
is readily assumed as a positive quantity. However, for the mechanical theory
proposed here, one can imagine that an opposition to change could produce an
overcompensation or repulsion from an individual effectively yielding a
_negative mass_. As we will further see, many other assumptions common to
physics can be also dropped, leading to models that hopefully result
interesting to physicists as new playgrounds for their methods; as well as for
social and behavioural scientists, as new tools emerge.

As another example of dropped assumptions, consider that, for human behaviour
it is difficult to imagine that resistance to change, represented by inertial
mass, does not depend on the particle’s configuration. More specifically, we
consider the general case where mass is a function of position: $m=m(x)$.
Thus, the law of individual change looks like follows:

$F=m\,\frac{{\rm d}^{2}}{{\rm d}t^{2}}x+\left(\frac{{\rm d}}{{\rm
d}x}m\right)\left(\frac{{\rm d}}{{\rm d}t}x\right)^{2}\,,$ (3)

where we have used de notation ${\rm d}_{t}=\frac{{\rm d}}{{\rm d}t}$ and
${\rm d}_{x}=\frac{{\rm d}}{{\rm d}x}$. We shall use this notation from now
on, as well as its partial derivative forms $\partial_{t}$ and $\partial_{x}$.
Therefore, a key proposal of this work, in terms of a mathematical formalism,
is that individual evolution might be modelled as particles with position-
dependent masses.

Since the force $F=F(x,t)$ is a cause external to the individual tending to
modify its evolution, the first term in the right-hand-side explains the
usual: a greater force $F$ produces a greater change in the state of motion of
the particle $\frac{{\rm d}^{2}}{{\rm d}t^{2}}x$. But, also, a greater inertia
$m$ requires the application of a greater force $F$ to obtain a given change
in motion.

The second term in the right-hand-side also yields a relation between the
magnitude of the force $F$ and a change in the state of the individual
$\frac{{\rm d}}{{\rm d}t}x$. However, this time the change is in position and
the relation is quadratic, and the proportionality between them is given by
the rate of change of the mass with respect to the position. Thus, it is
increasingly harder for a forcing agent to raise the speed of change,
irrespective of the direction. Nonetheless, this is mediated by the the way
the inertia of the individual depends on the stance of the individual.
Arguably, such a model is reasonable for changes of individuals interacting in
a society.

A first interesting case of equation (3) is when there is no force: $F=0$, and
whose general solution is implicitly given by

$x+c_{1}=\int_{1}^{x}\frac{m(s)}{c_{1}}\,{\rm d}s\,.$ (4)

This represents an individual evolving under no external interactions. Of
course, just like in physics, this is an idealize scenario, although very
useful as an initial system. Particles, whether physical or social, are very
often subject to forces changing their motion.

For illustrative purposes, consider a mass function $m(x)=x^{2}$. As a
positive-concavity function, it is a reasonable position-dependent mass for
the type of phenomena we are trying to study, since such a mass describes
individuals that move freely around a prescribed position consistent with a
preferred conviction, here denoted by $x=0$. Nonetheless, the ultimate test
for a model is its comparison with measurements. Any other mass function
adequate with systematic observations can be used.

There is another reason (well known to physicists) to use $m(x)=x^{2}$ as a
starting example: approximations by power series of more complicated mass
functions can be truncated to second order and still reveal a vast information
about the system.

In any case, let us proceed with the example by considering the equation of
free motion:

$0=x^{2}\,{\rm d}_{t}^{2}x+2x\left({\rm d}_{t}x\right)^{2}\,.$ (5)

The solution to this equation is

$x(t)=c_{2}\,(c_{1}+3t)^{1/3}\,,$ (6)

where $c_{1}$ and $c_{2}$ are constants fixed by the initial conditions of the
system.

Figure 2 shows examples of curves describing the evolution in time resulting
from varying the first initial condition, $c_{1}$, while keeping the second
one, $c_{2}$, fixed. Figure 3 shows examples of curves describing the
evolution in time resulting from fixing the first initial condition, $c_{1}$,
while varying the second one, $c_{2}$.

Figure 2: Free evolution of a system with a squared position-dependent mass
and different initial conditions.

Figure 3: Free evolution of a system with a squared position-dependent mass
and different initial conditions.

Notice that in the Figure 3 one can find the simplest scenario: no motion at
all. This can be seen here for the case where $c_{1}=c_{2}=0$, that
corresponds to an static undisturbed system.

Trajectories are similar for other concave up parabolic mass functions of the
form $m=a(x-x_{0})^{2}+m_{0}$. These result from translating the vertex from
the origin $(0,0)$ to the point $(x_{0},m_{0})$. Thus, they model individuals
with different minimal value of mass $m_{0}$ at a characteristic position
$x_{0}$. Parameter $x_{0}$ can be understood as the stance where an individual
moves with the most freedom, while parameter $m_{0}$ can be seen as a measure
of how difficult it is to move the individual from that position.

Actually, parameters $x_{0}$ and $m_{0}$ allow us to have a diverse population
with respect to the position around which they move more freely and how much
they oppose to an intended change, respectively. Figure 4 illustrate three of
these individuals through their corresponding parabolic mass functions with
distinct parameters $x_{0}$ and $m_{0}$.

Figure 4: Concave up parabolic mass functions of three particles with
different.

Before moving on, there is an extra consideration coming from this example.
Note that a parabolic position mass function has domain $(-\infty,\infty)$.
However, other positively concave functions could be used to model more
confined individuals. Also, in the many scenarios of social phenomena, one
could encounter systems where a mass function with negative concavity serves
as a better model. In such a case, one has a repelling effect around a given
conviction fixed by the position of the maximum of the mass function. For
reasons already stated, we expect that concave up mass functions are more
natural and frequent in describing convictions.

###  3.2 Forces acting on individuals

Having described how to build a model for an particle evolving freely, now,
let us investigate the behaviour of a particle subject to a net force
$F=F(x,t)$. Again, we use a simple, yet illustrative, initial model: a
modified version of Hooke’s law. The functional form proposed for the force is
a linear function:

$F=ar+b\,,$ (7)

where $r=|x-x_{c}|$ is the distance between the position $x$ of the individual
and a certain position $x_{c}$ around which the force is centered. Also, $a$
and $b$ are constants to describe the particular form and properties of the
force. Note that this type of forces can be obtained from a potential function

$U=-\left(\frac{a}{2}r^{2}+br\right)\,,$ (8)

by means of $F=-\partial_{r}\,U$.

Figure 5 shows an example of a this potential, where $a<0<b$. Then, there is
an attractive and a repulsive region.

Figure 5: Simple model of a potential function $U$ given by equation (8) with
parameters $a=2$ and $b=-2$.

Indeed, the change of sign in $F$ is important. The negative part, closest to
$r=0$ is the region where _affinity_ or proximity of the individual to the
position $s_{c}$ produces an attractive force, thus, a negative force as is
conventional in physics. On the other hand, in this model, there is a single
point where the force is null, $F=0$, after which the distance $r$ between the
individual’s position to the centre $s_{c}$ yields a repulsive force. Due to
these properties, one can note that, although simple,this model is a useful
first approximation to human interactions.

Since the force is linear in $r$, $a$ describes the overall strength of the
force, whether in the attractive or repulsive regions, while $b$ describes the
maximum of the attractive force and, for a fixed value of $a$ the size of the
attractive region. Certainly this is a very simple model of a force. More
complicated models can be used, but $F=ar+b$ is a convenient starting point to
illustrate the possibilities of the ideas proposed here.

For the current example, with the simplifying assumption $x_{c}=0$, the
equation of motion becomes

$x^{2}\,{\rm d}_{t}^{2}x+2x({\rm d}_{t}x)^{2}=ax+b\,,$ (9)

whose general solution is implicitly given by

$\int\frac{x^{2}}{\sqrt{3ax^{4}+4bx^{3}+6C_{0}}}\,{\rm
d}x=C_{1}\pm\frac{t}{\sqrt{6}}\,,$ (10)

where $C_{0}$ and $C_{1}$ are constants to be determined from the initial
conditions.

To develop some intuition, consider the directional fields in Figures 6 and 7
describing two types of motion resulting from this model. The direction
forward in time is upward along the vertical axis. Without loss of generality,
motion is assumed from left to right. In the case of Figure 6 the conditions
are not enough for the individual to escape the attractive and repulsive
regions. These are the domains where the force $F$, that is, the derivative of
$U$, takes negative and positive values, respectively; see Figure 5).

Figure 6: Directional field of a motion with quadratic position-dependent
mass, under a force $F=2(x-1)$, compatible with initial conditions $x_{i}=1/2$
and $v_{i}=1$.

In the case of Figure 7 the conditions are _strong_ enough so that the
individual moves through the different regions.

Figure 7: Directional fields of a motion with quadratic position-dependent
mass, under a force $F=2(x-1)$, compatible with initial conditions $x_{i}=1/2$
and $v_{i}=3$.

The motion just presented can describe an individual’s position, stance,
belief, conviction in the presence of the given external force. However, such
a force could be produced by another particle, thus providing a model for an
interaction between them. Note, also, that such an interaction need not be
symmetrical, like in Newton’s third law. In this framework for social
mechanics we have a rich set of possible models: two particles could have
reciprocal interactions, but they could respond differently to it due to
differences in their mass functions; or they could have no reciprocal
interactions at all.

Thus far, quantities have possessed well determined values. However, the
aggregation of particles usually results in an intractable set of equations.
Now, we proceed to study how stochasticity can be included in our framework.

###  3.3 Stochastic motion

Let us proceed now to the case where the influences acting on a social
particle include an stochastic term. Thus, a practical uncertainty is added to
the laws governing its motion. This can help make assertions about social
behaviour even when interactions seem intractable. This is also in a closer
resemblance to the many ways in which individual stances on social issues are
influenced by many random signals in the social ambience.

First, to account for the added uncertainty, instead of using single position,
we consider a distribution of positions $f=f(x,t)$. In a probabilistic
interpretation, once normalized, $f(x,t)$ can be used to obtain the
probability of finding an individual in position $x$ at time $t$.

While there are many distributions used to describe populations in social
studies, the normal distribution is probably the most frequently used to
describe them, even if in an approximate fashion. Thus, let us use it to show
how the time evolution of the beliefs of a population could be treated in
terms of particle position distributions.

Consider the Smoluchowski equation

$\partial_{t}f=\partial_{x}^{2}\left(\alpha f\right)-\partial_{x}\left(\beta
f\right)\,,$ (11)

where, in general, $\alpha=\alpha(x,t)$ and $\beta=\beta(x,t)$ are called the
_diffusion_ and _drift_ , respectively. This equation can be obtained from the
overdamped Brownian motion of a particle, i.e. a particle subject to a force
$F(x,t)=\gamma\,{\rm d}_{t}x+\beta+\sqrt{2\alpha}\,\eta(t)$ with negligible
inertial term $m\,{\rm d}_{t}^{2}x$. Here, $\eta$ is an stochastic function
usually motivated by random collisions.

Thus, equation (11) describes the time evolution of the probability density
function of a particle under the influence of random and drag forces,
described by $\alpha$ and $\beta$, respectively. In a social mechanical sense,
this model describes a population subject to a compelling trend $\beta$ and
some noise $\alpha$ that scatters agglomerations of beliefs. For a simple
case, the result is a non-uniform distribution that moves in time changing
both its mean, as well as its variance. Let us see how.

Suppose that both the diffusion and drift are functions of time only:
$\alpha=\alpha(t)$ and $\beta=\beta(t)$. Thus, the external effort to shift
the stance of the population and the noise preventing uniformity act equally
across all stances, although it varies in time. Under this simplifying
assumptions, the well known solution of (11) is a normal distribution

$f(x,t)=A\,{\rm e}^{[x-\mu]^{2}/2\sigma^{2}}\,,$ (12)

with time dependent mean $\mu=\mu(t)$ and variance $\sigma^{2}=\sigma^{2}(t)$,
and $A$ a normalization factor. The parameters of the distribution can be
obtained from those of (11) by

$\partial_{t}\mu=\beta\,,\quad\partial_{t}\sigma^{2}=2\alpha\,.$ (13)

That is to say, at each moment in time the stances of the population are
described by a normal distribution, the only differences from moment to moment
are the parameters $\mu$ and $\sigma^{2}$ that characterize them. Even more,
the forces act in a transparent way since the drift (overall trend) influences
the centre of the distribution while the diffusion (noise) affects the
dispersion of the distribution.

As a concrete model consider that the diffusion and drift coefficients are
oscillations with distinct frequencies $\omega_{\alpha}$ and $\omega_{\beta}$,
respectively. Then, we can write these coefficients in the following form:

$\alpha=\frac{\omega_{\alpha}}{2}\sin(\omega_{\alpha}t)\,,\qquad\beta=-\omega_{\beta}\sin(\omega_{\beta}t)\,.$
(14)

The solution of equation (11) corresponding to these coefficients is then
given by

$f(x,t)=\frac{{\rm
e}^{\frac{[x-\cos(\omega_{\beta}t)]^{2}}{2(\cos[\omega_{\alpha}t)-2]}}}{\sqrt{2\pi[2-\cos(\omega_{\alpha}t)]}}\,.$
(15)

Indeed, this is a normal distribution whose mean $\mu=\cos(\omega_{\beta}t)$
and variance $\sigma^{2}=2-\cos(\omega_{\alpha}t)$ oscillate with frequencies
$\omega_{\alpha}$ and $\omega_{\beta}$, respectively.

Other models can be produced in a similar fashion by means of (13), given the
validity of assuming that the diffusion and drift depend of time only. Even
more models could be obtained by dropping these assumptions.

Now, how would one use a model thus constructed to describe stances of a
society? Let us show it with an example. Consider the outcomes of the USA
presidential elections since 1856. We have selected this period since then the
two party system is clearer, with democrats and republicans winning either the
first and second place, or vice versa, in majority of the popular vote; except
for the election of 1912, where the Progressive Party came in second.

The configuration of the model is as follows: We focus only on the population
that voted either for the Democrat or the Republican party. All else are
considered as external to this particular system. The position describes the
stance with respect to both parties. That is to say, the position space is
described by the real line $\mathbb{R}$, where the more to the left the
position is ($x<0$), the more the individual supports the Democrat party; the
more to the right the position is ($0<x$), the more the individual supports
the Republican party; and $0$ is for an indifferent stance with respect to
both parties.

Next, we suppose that the evolution of the population can be approximated by
the model described by equation (11), where the diffusion and drift are time
dependent only, so that the distribution of preferences in the population is
described by equation (12). Hence, even though all the data we have is the
percentage of people that voted democrat or republican, the model implies a
normal distribution of preferences within the population compatible with the
outcome of each election. The resulting means and variances of the elections
can be seen in Table 1.

Table 1: Mean and variances of normally distributed preferences compatible with the outcomes of USA’s presidential elections under the model described by equation (12). Year | Mean | Variance | Year | Mean | Variance | Year | Mean | Variance
---|---|---|---|---|---|---|---|---
1856 | -0.199 | 1.014 | 1912 | -0.373 | 1.016 | 1968 | 0.011 | 1.067
1860 | 0.195 | 1.054 | 1916 | -0.053 | 1.300 | 1972 | 0.305 | 1.018
1864 | 0.151 | 1.193 | 1920 | 0.361 | 1.018 | 1976 | -0.032 | 1.214
1868 | 0.068 | 1.025 | 1924 | 0.406 | 1.038 | 1980 | 0.145 | 1.085
1872 | 0.198 | 1.323 | 1928 | 0.233 | 1.047 | 1984 | 0.242 | 1.043
1876 | -0.046 | 1.215 | 1932 | -0.241 | 1.043 | 1988 | 0.114 | 1.167
1880 | 0.001 | 1.143 | 1936 | -0.331 | 1.041 | 1992 | -0.092 | 1.057
1884 | -0.008 | 1.039 | 1940 | -0.167 | 1.327 | 1996 | -0.125 | 1.051
1888 | -0.014 | 1.268 | 1944 | -0.103 | 1.089 | 2000 | -0.007 | 1.047
1892 | -0.044 | 1.029 | 1948 | -0.069 | 1.168 | 2004 | 0.034 | 1.088
1896 | 0.064 | 1.166 | 1952 | 0.143 | 1.042 | 2008 | -0.096 | 1.039
1900 | 0.081 | 1.030 | 1956 | 0.201 | 1.028 | 2012 | -0.052 | 1.049
1904 | 0.261 | 1.029 | 1960 | -0.002 | 1.110 | 2016 | -0.030 | 1.074
1908 | 0.124 | 1.094 | 1964 | -0.296 | 1.028 | 2020 | -0.059 | 1.030
|  |  |  |  |  |  |  |

To illustrate this, consider the distributions depicted in Appendix A.
Distributions for years 1872, 1912, 1924 and 1940 possess particularly
contrasting means, variances and overall outcomes. In each case, the popular
vote outcome for the democrat and republican candidate is well approximated by
the portion of the population to the left and right of the position of
indifference $x=0$, respectively.

Finally, the resulting modelling can be used to describe the forces acting on
the population, namely, those related to the drift and diffusion of partisan
stances. Assuming they can be approximated by continuous functions, one can
use (13) to obtain the drift and diffusion coefficient. Numerically
approximating them yields the graphs shown in Figure 8. Therefore, in the
framework proposed here, they characterize the effective forces acting on the
American society towards modifying its partisan preferences. We call them
effective because one can imagine that these forces are the net result of
various social interactions, efforts and compels of diverse nature, whether
deliberate or not.

Figure 8: Evolution of drift and diffusion for a simple model of USA’s two
party preferences.

It is worth noticing that distribution (12) is unimodal, in line with the
hypothesis of the _median voter model_ [22]. However, in the light of strongly
politically polarized societies, bimodal distributions have shown to be
effective in describing elections [23, 24].

Admittedly, this is are rather simplified models of the changes in political
stances in the USA, but very descriptive initial ones, nonetheless. This
models also show that the framework does not explain the nature of the
interactions. Although, it may shed some light on certain processes and, more
specifically, on effective phenomena.

As mentioned earlier, the Smoluchowski equation (11) governs the probability
density of finding a particle in the position $x$ at time $t$ given that it is
subject to an overdamped Brownian motion. However, we wish to include
considerations proposed in subsection 3.1, namely, inertial terms of the form
$m\,{\rm d}_{t}^{2}x+({\rm d_{x}}m)({\rm d}_{t}x)^{2}$. Then, consider the
motion of a particle with position-dependent mass subject to a random force
$\eta(x,t)$:

$m\,{\rm d}_{t}^{2}x+m^{\prime}({\rm d}_{t}x)^{2}=\eta\,,$ (16)

where $m^{\prime}={\rm d}_{x}m$. This is the stationary Kardar-Parisi-Zhang
equation for $x$ and $t$ playing the role of position $x$, instead. It has an
associated Fokker-Planck equation, similar to the Smoluchowski equation, that
admits a solution of the form [20]:

$f(t)\sim{\rm e}^{-\frac{m}{2D}\int({\rm d}_{t}x)^{2}{\rm d}t}\,,$ (17)

where $D$ is a diffusion coefficient that captures the effects of the random
noise. Notably, $f(t)$ does not depend on $m^{\prime}$. Expression (17) gives
the probability density for a given path $x(t)$.

##  4 Other formulations of mechanics

It is well known that classical mechanics can be formulated in terms of
extremal action principles instead of an interplay of forces. This alternative
formulation has helped discover a vast set of features in mechanical systems.
In fact, modern approaches to fundamental interactions in physics are based on
these principles. Let us investigate how similar formulations can contribute
to the framework presented here.

Consider, for example, that the evolution of an individual’s position in the
context described here is such that it extremizes a quantity, called _action_
:

$S=\int L\,{\rm d}t\,,$ (18)

where

$L=\frac{1}{2}mv^{2}-U\,,$ (19)

$m=m(x)$, $U=U(x)$ and $v=\frac{{\rm d}x}{{\rm d}t}$. Then, $L=L(x,v;t)$ and
the evolution of $x=x(t)$ is governed by the functional condition

$\delta S=0\,,$ (20)

subject to a constraint $F_{c}=-\frac{1}{2}v^{2}\partial_{x}m$. So that $x(t)$
satisfies the constrained Euler-Lagrange equation

$\frac{{\rm d}}{{\rm d}t}\left(\frac{\partial}{\partial
v}L\right)=\frac{\partial}{\partial x}L+F_{c}\,,$ (21)

that, in turn, yields eq. (3) with $F=-\frac{\partial}{\partial x}U$. The
extra term $F_{c}$ is commonly known as a _thrust_ force [21].

Equation (3) can also be presented as a constrained Hamiltonian system
satisfying Hamilton’s equations

$\frac{{\rm d}x}{{\rm d}t}=\frac{\partial H}{\partial p}\,,\qquad\frac{{\rm
d}p}{{\rm d}t}=-\frac{\partial H}{\partial x}+F_{c}\,,$ (22)

where the momentum $p=\frac{\partial L}{\partial v}=mv$ and the Hamiltonian
function is given by

$H=\frac{p^{2}}{2m}+U\,.$ (23)

Again, the extra thrust term $F_{c}$ is present.

One can also rewrite this system in a more convenient form by introducing the
following effective quantities, as in [21]:

$H_{\rm eff}=\frac{m}{m_{c}}\left(\frac{p^{2}}{2m}+U_{\rm eff}\right)\,,$ (24)

where

$U_{\rm eff}=U-\frac{1}{m}\int U\,\partial_{x}m\,{\rm d}x\,,$ (25)

and $m_{c}$ is a constant. Then, by defining new mass and momentum variables:
$\mu=m^{2}/m_{c}$ and $\phi=\mu v$, we can write

$H_{\rm eff}=\frac{\phi^{2}}{2\mu}+U_{\rm eff}$ (26)

and the system satisfies the following equations of motion in the common
Hamiltonian form:

$\frac{{\rm d}x}{{\rm d}t}=\frac{\partial H_{\rm
eff}}{\partial\phi}\,,\qquad\frac{{\rm d}\phi}{{\rm d}t}=-\frac{\partial
H_{\rm eff}}{\partial x}\,.$ (27)

A possible applications of these alternative formulations of mechanics that
immediately comes to mind is the connection with utility theory and others
similar where the extremization, whether towards a maximum or minimum, is used
to describe human behaviour. In such a case, one could connect the utility
with the action, up to a sign.

Another potential application is the inclusion of concepts of symmetries and
conserved quantities. Lagrangian and Hamiltonian formulations of mechanics are
rather transparent about the role of these concepts in mechanics. However, it
is not clear now what kind of symmetries and conservation laws would be
realized by social phenomena.

We shall not explore further these topics here, leaving it for future work.

##  5 Conclusions

In this work we have explored the idea behind social physics that analogies
between some social and physical systems may occur under certain
circumstances. While an analogy can take place as mathematical formulations
coincide, this work studies further comparisons. Thus, physical concepts are
employed to describe social change, taking advantage of the well established
heuristics behind physics. That is to say a more genuine social physics
framework than just a coincidence in mathematical tools.

For the sake of systematicity, the investigation commenced with the a proposal
to connect fundamental concepts in physics with notions regarding social
change. Specifically, we explored the concepts of particle, position, space,
motion, inertia, mass, momentum, force, interaction and equilibrium. They key
idea is to represent stances on a social question as positions in a
configuration space.

Once the initial concepts were established in a social change context, we used
the resulting connections to describe a particle moving freely and one moving
under the influence of a net force. An important caveat is the generalization
of the concept of mass. On the one hand, mass can be either positive or
negative. The first case represents a resistance to motion under an external
influence that increases with the magnitude of the mass. The second case can
be understood as a back reaction to the external influence that produces a
motion in the opposite direction of it and it also increases with its
magnitude.

On the other hand, the mass is also generalized to be a function of position.
With it, we can distinguish the responses to social influences and
characterize the social unit depending on its current stance on the topic.
This encompasses the assumption of a consistent individual, where, upon having
the same stance, it shows the same inertial response to a certain interaction.
Although one can imagine more general mass functions, like one that is also
explicitly time dependent or with hysteretical behaviour, these cases are not
explored here.

Notably, here we used the Newtonian formulation of classical mechanics. Thus,
a remark on well-known Newton’s laws is at hand. As in the first law, there is
a tendency to maintain a particular motion when no forces act on an object:
free motion; as well as a measure of this tendency: inertial mass. However,
these differ from the physical case since, although the mass is a
characteristic of the object, it varies with its position. Still, one can use
the mathematical expression for the second law, stating that the net force on
a particle produces a change in the state of motion through the derivative of
momentum with respect to time. Finally, generalizing the third law, while
human interactions can be two-way, one can imagine the reciprocity not being
identical. In this regard, some asymmetries could be incorporated in the model
by means of distinct mass functions among interacting particles. Nonetheless,
it seems that this would need to be validated for a given specific phenomenon.

We also briefly described the Lagrangian and Hamiltonian functions
corresponding to the proposed framework. However, as is well known, the
resulting system is non holonomicaly constraint due to the position dependent
mass. They could be connected to formulations of social behaviour based on
extremization of functions like utility theory.

Finally, we showed how stochastic considerations can be incorporated by
passing to a mechanical description based on distributions instead of
trajectories. As an example we used the Smoluchowski equation to describe
partisan stances corresponding to the outcomes of USA’s presidential elections
since 1856.

###  5.1 Future work

From the various considerations presented in this work, there are some
immediate prospective directions to continue the investigations presented
here. One can study other possible generalizations of mass functions or
different specific cases of forces and interactions. Notably, we have used
one-dimensional systems for simplicity, however multiple social issues in the
form af additional dimensions can be considered. One can also investigate the
many-body problem in social mechanics and even develop an statistical
mechanics explanation of how individuals aggregate to produce social
configurations, analogously to how small particles aggregate to produce
solids, liquids or gases, or even more complex states.

There are two more possible directions for the kind of research conducted
here: social systems analogous to quantum physics and general relativity.
Although seemingly strange, the first is a reasonable direction since quantum
mechanics incorporates fundamentally the notion of stochasticity of a single
particle. The uncertainty is fundamental and we do not know why it must be
accounted for in the quantum theory, so it is postulated. An attempt could be
made to see if the results from quantum mechanics yield mathematical tools to
deal with uncertainties in an individual’s motion, even if they are not
fundamental, but only effective due to the unpredictability of human behaviour
[25, 26].

General relativity offers possibilities in applying analogous reasoning to
social systems. The novelty of general relativity is an intertwine between the
nature of the space of positions and the objects moving on it. This can help
generalize the notion that the positions accessible, i.e. the space, are
previously fixed to be occupied by individuals, moving towards a picture in
which the space of stances is dynamical and changes as a society evolves.
While the mathematical framework for general relativity is differential
geometry, where space-time is a manifold, there are already social stances
describable in these terms, for example, the concept of _equilibrium manifold_
in economics [27]. Of course, no connection between them is claimed now, but
they are susceptible of investigation for possible analogies. It is worth
mentioning here that there is already an empirical result in economics known
as the _gravity model of international trade_ stating that “the volume of
trade between two countries is proportional to their economic mass and a
measure of their relative trade frictions” [28]. Although, it is analogous to
non-relativistic gravity.

In any of these prospectives there is always the opportunity to find data
susceptible to be described by each resulting model that, in turn, can help to
test and tune it.

Before we finish this exposition, a warning is necessary: as with other
frameworks exploiting analogies, the connections made through social mechanics
should be treated as effectively describing social phenomena, as opposed to
fundamental explanations. Any statement on the fundamental nature and
mechanisms of an attempted “true” description of human behaviour must be
rigorously tested against robust data, with great scepticism. People are not
machines.

## References

  * [1] Jusup, M. et al. Social physics. Physics Reports 948, 1-148 (2022).
  * [2] Wilson, A. Notes on some concepts in social physics. Papers in Regional Science 22, 159-193 (1969).
  * [3] Hurwitz, J.; Peffley, M. How are foreign policy attitudes structured? A hierarchical model. American Political Science Review 81, 1099-1120 (1987).
  * [4] Gardenfors, P. The dynamics of thought. SpringerLink Available at: https://link.springer.com book/10.1007/1-4020-3399-0. (Accessed: 15th December 2023).
  * [5] Shapiro, R. Y. Public opinion and american democracy. Public Opinion Quarterly 75, 982-1017 (2011).
  * [6] Eisenstadt, S. N. Tradition, change, and modernity. (John Wiley; Sons, 1973).
  * [7] Oesterdiekhoff, G. W. The role of developmental psychology to understanding history, culture and Social Change. Journal of Social Sciences 10, 185-195 (2014).
  * [8] Pitz, G. F. An inertia effect (resistance to change) in the revision of opinion. Canadian Journal of Psychology / Revue canadienne de psychologie 23, 24-33 (1969).
  * [9] Bourdieu, P. The social space and the genesis of groups. Social Science Information 24, 195-220 (1985).
  * [10] Zárate, M. A., Shaw, M., Marquez, J. A.; Biagas, D. Cultural inertia: The effects of cultural change on intergroup relations and the self-concept. Journal of Experimental Social Psychology 48, 634-645 (2012).
  * [11] Brook, S. Social inertia and the field of creative labour. Journal of Sociology 49, 309-324 (2013).
  * [12] Jackson, J. M. Social Impact Theory: A Social Forces model of influence. Theories of Group Behavior 111-124 (1987). doi:10.1007/978-1-4612-4634-3-6.
  * [13] Kalleberg, A. L. Social Forces Tomorrow. Social Forces 90, 345-347 (2011).
  * [14] Stonier, A.; Bode, K. A new approach to the methodology of the Social Sciences. Economica 4, 406 (1937).
  * [15] Sorensen, A. B. Mathematical models in sociology. Annual Review of Sociology 4, 345-371 (1978).
  * [16] Lynch, S. M.; Bartlett, B. Bayesian statistics in sociology: Past, present, and future. Annual Review of Sociology 45, 47-68 (2019).
  * [17] Sunstein, C. R. How change happens (2019). doi:10.7551/mitpress/11974.001.0001
  * [18] Grigorenko, A. N. Classical physics of particles and fields. Journal of Geometry and Physics 86, 94-100 (2014).
  * [19] Yurdusev, A. N. Level of analysis and unit of analysis: A case for distinction. Millennium: Journal of International Studies 22, 77-88 (1993).
  * [20] Rodríguez, Miguel A; Wio, Horacio S. Stochastic entropies and fluctuation theorems for a discrete one-dimensional Kardar-Parisi-Zhang system. Physical Review E 100, 032111 (2019).
  * [21] Rosas-Ortiz, O. Position-dependent mass systems: Classical and Quantum Pictures. Trends in Mathematics 351-361 (2020).
  * [22] Black, D. On the rationale of group decision-making. Journal of Political Economy 56, 23-34 (1948).
  * [23] Jones, M. I.; Sirianni, A. D.; Fu, F. Polarization, abstention, and the median voter theorem. Humanities and Social Sciences Communications 9, (2022).
  * [24] Medoff, M. H.; Dennis, C.; Bishin, B. G. Bimodal issues, the median voter model, legislator’s ideology, and Abortion. Atlantic Economic Journal 23, 293-303 (1995).
  * [25] Helland, I. S. On the foundation of Quantum Decision theory (2023). doi:10.32388/kcuq4n
  * [26] Ashtiani, M.; Azgomi, M. A. A survey of quantum-like approaches to decision making and cognition. Mathematical Social Sciences 75, 49-80 (2015).
  * [27] Balasko, Y. The equilibrium manifold (2009). doi:10.7551/mitpress/9780262026543.001.0001
  * [28] Baier, S.; Standaert, S. Gravity Models and empirical trade. Oxford Research Encyclopedia of Economics and Finance (2020).

##  Appendix A Selected examples of the distribution of partisan preferences
in presidential elections in the US

Figure 9: 1872

Figure 10: 1912

Figure 11: 1924

Figure 12: 1940


# Online Search for a Hyperplane
in High-Dimensional Euclidean Space

Antonios Antoniadis, Ruben Hoeksma11footnotemark: 1,
Sándor Kisfaludi-Bak, and Kevin Schewior Department of Applied Mathematics,
University of Twente, Enschede, The Netherlands.
<EMAIL_ADDRESS>for Theoretical Studies, ETH
Zürich, Zurich, Switzerland<EMAIL_ADDRESS>of
Mathematics and Computer Science, University of Cologne, Cologne, Germany.
<EMAIL_ADDRESS>
(September 2021)

###### Abstract

We consider the online search problem in which a server starting at the origin
of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The
best-possible competitive ratio and the length of the shortest curve from
which each point on the $d$-dimensional unit sphere can be seen are within a
constant factor of each other. We show that this length is in $\Omega(d)\cap
O(d^{3/2})$.

##  1 Introduction

In $d$-dimensional Euclidean space, given a set of objects
$\mathcal{T}\subseteq\mathcal{P}(\mathbb{R}^{d})$, the _online search problem
(for an object in $\mathcal{T}$)_ asks for a curve (or _search strategy_)
$\zeta:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}^{d}$ with $\zeta(0)=0$
that minimizes the competitive ratio [14]. We say that $\zeta$ is _$c$
-competitive_ if there exists an $\alpha\in\mathbb{R}_{\geqslant 0}$ such that

$\mathrm{length}(\zeta|_{[0,t^{\star}]})\leqslant
c\cdot\mathrm{dist}(0,T)+\alpha$

for all $T\in\mathcal{T}$, where $t^{\star}=\inf\\{t:\zeta(t)\in T\\}$. The
infimum over all such $c$ is the _competitive ratio_ of $\zeta$. Problems of
this type date back to Beck [4] and Bellman [6].

The arguably most basic and well-known such online search problem from this
class is the version in which $d=1$ and $\mathcal{T}=\mathbb{R}$, also known
as the cow-path problem, where the best-possible competitive ratio is $9$ [5],
achieved by visiting the points $(-2)^{0},(-2)^{1},\dots$ sequentially. In
fact, the class of all $9$-competitive strategies has been investigated more
closely [1]. Moreover, the competitive ratio can be improved to about $4.591$
using randomization [5]. The problem has been generalized to more than two
paths starting at the origin [13], searching various types of objects in the
plane or lattice [3], and many more scenarios. For a (slightly outdated)
survey, see the book by Gal [11].

Another very natural generalization is the case of general $d$ and
$\mathcal{T}$ being equal to $\mathcal{H}^{d-1}$, the set of all hyperplanes
in $\mathbb{R}^{d}$. We call this version the _$d$ -Dimensional Hyperplane
Search Problem_. When $\mathcal{T}$ is a set of affine subspaces, this is
arguably the most interesting case. Note that, if $\mathcal{T}$ contains all
affine subspaces of dimension $d^{\prime}\leq d-2$, any constant competitive
ratio is ruled out, even when $d$ is fixed. Surprisingly, in addition to the
case of $d=1$, results only seem to be known for $d=2$ and for offline
versions [9, 2], leaving a gap in the online-algorithms literature. For $d=2$,
it is conjectured that a logarithmic spiral that achieves a competitive ratio
of about $13.811$ is optimal [3, 10]. The present paper addresses the
aforementioned gap by providing the first asymptotic results for
$d\rightarrow\infty$.

For the remainder of the paper, we will consider the essentially equivalent
but arguably cleaner _Sphere Inspection Problem_ : The goal is to find a
$d$-dimensional minimum-length closed curve, $\gamma$, that _inspects the unit
sphere_ in $\mathbb{R}^{d}$, i.e., $\gamma$ sees every point $p$ on the unit
sphere $S^{d-1}$. Here, we say that an object $O\subseteq\mathbb{R}^{d}$
_sees_ a point $p^{\prime}$ on the surface of the unit sphere if there is a
point $p\in O$ such that the line segment $pp^{\prime}$ intersects the unit
_ball_ exclusively at $p^{\prime}$. Note that the curve is not required to
start in the origin any more. Such a minimum-length curve exists for any
dimension [12]. While this problem is trivial for $d\in\\{1,2\\}$, it has only
been shown recently that the best-possible length for $d=3$ is $4\pi$ [12]. No
results for higher dimensions are known. Such visibility problems have also
been considered from an algorithmic point of view, e.g., [7, 8].

While the connection between hyperplane search and sphere inspection seems to
be folklore (e.g., [12]), we state it formally and provide a short proof for
completeness. Let $I$ be an interval, and for $\beta\in\mathbb{R}$, a set
$T\subseteq\mathbb{R}^{d}$, and curve $\gamma:I\rightarrow\mathbb{R}^{d}$, we
denote by $\beta\cdot T$ the set $\\{\beta\cdot x:x\in T\\}$ and by
$\beta\cdot\gamma$ the curve
$I\rightarrow\mathbb{R}^{d},t\mapsto\beta\cdot\gamma(t)$.

######  Proposition 1.

Let $f:\mathbb{N}\rightarrow\mathbb{R}_{\geqslant 0}$. The following
statements are equivalent:

  * (i)

There exists a length-$O(f(d))$ closed curve in $\mathbb{R}^{d}$ that inspects
$S^{d-1}$.

  * (ii)

There exists an $O(f(d))$-competitive strategy for the $d$-Dimensional
Hyperplane Search Problem.

###### Proof.

We first show that (i) implies (ii). Fix $d\in\mathbb{N}$, let $\gamma$ be the
length-$\ell$ curve for the Sphere Inspection Problem in $\mathbb{R}^{d}$, and
let $\gamma_{0}$ be a point on $\gamma$. We show that there exists a
$(12\ell)$-competitive strategy for the $d$-Dimensional Hyperplane Search
Problem where the additive constant $\alpha$ is equal to $3\ell$. Our strategy
works in an infinite number of phases, starting with Phase $0$. In each Phase
$i$, the strategy $\zeta$ consists of a straight line from the origin to
$2^{i}\gamma_{0}$, the curve $2^{i}\cdot\gamma$, and a straight line back from
$2^{i}\gamma_{0}$ to the origin.

In the following, we show that, in Phase $i$, all hyperplanes of distance at
most $2^{i}$ from the origin are visited, and the total distance traversed in
Phase $i$ is at most $3\cdot 2^{i}\cdot\ell$, which implies the claim. We show
two parts separately:

  * •

We show that all claimed hyperplanes are visited by $\zeta$. Consider Phase
$i$ and a hyperplane $H\in\mathcal{H}^{d-1}$ at distance at most $2^{i}$ from
the origin. Let $n$ be a unit normal vector of $H$. Note that
$2^{i}\cdot\gamma$ sees both the point $2^{i}n$ and the point $-2^{i}n$. Let
$p_{1}$ be a point from which $2^{i}\cdot\gamma$ sees $2^{i}n$, and let
$p_{2}$ be a point from which it sees $-2^{i}n$. Note that, if
$\mathrm{dist}(0,H)=2^{i}$, then $p_{1}$ or $p_{2}$ may be on $H$. In that
case we are done. Otherwise $p_{1}$ and $p_{2}$ are on different sides of $H$,
and, by the intermediate value theorem, $2^{i}\cdot\gamma$ intersects $H$.

  * •

We next bound the distance traversed by $\zeta$ in Phase $i$. Note that it
suffices to show that the start point of $2^{i}\cdot\gamma$, which is equal to
its end point, has distance at most $2^{i}\ell$ from the origin. By scaling,
we can restrict to showing $\lVert\gamma_{0}\rVert_{2}\leqslant\ell$. Let $H$
be the hyperplane $\langle\gamma_{0},x\rangle=0$. Note that $\gamma$ must
intersect $H$ since otherwise $\gamma$ does not see
$-\gamma_{0}/\lVert\gamma_{0}\rVert_{2}$, thus
$\mathrm{dist}(\gamma_{0},H)\leq\ell$. Since this distance (of $\gamma_{0}$ to
$H$) is precisely $\lVert\gamma_{0}\rVert_{2}$, it follows that
$\lVert\gamma_{0}\rVert_{2}\leqslant\ell$.

We now show that (ii) implies (i). Again fix $d\in\mathbb{N}$. Assume that
there exists a curve $\gamma$ starting in the origin and
$\alpha\in\mathbb{R}_{\geqslant 0}$ such that, for all hyperplanes
$H\in\mathcal{H}^{d-1}$, $\gamma$ visits $H$ after traversing at most a length
of $c\cdot\mathrm{dist}(0,H)+\alpha$. We show that, for any $\varepsilon>0$,
there exists a, not necessarily closed, length-$(c+\varepsilon)$ curve that
inspects the sphere. This then implies the existence of a
length-$(2c+\varepsilon)$ closed curve that inspects the sphere. We define

$\zeta:=\frac{\varepsilon}{\alpha}\cdot\gamma|_{[0,t^{\star}]}\text{, where
}t^{\star}:=\sup_{H\in\mathcal{H}^{d-1}:\mathrm{dist}(0,H)\leqslant\nicefrac{{\alpha}}{{\varepsilon}}}\min\\{t:\gamma(t)\in
H\\}\,.$

Note that the minimum exists because $H$ is closed. Since for each
$H\in\mathcal{H}^{d-1}$ with
$\mathrm{dist}(0,H)\leqslant\nicefrac{{\alpha}}{{\varepsilon}}$, $\gamma$
visits $H$ after traversing at most a length of
$c\cdot\nicefrac{{\alpha}}{{\varepsilon}}+\alpha$, the length of
$\gamma|_{[0,t^{\star}]}$ is at most
$c\cdot\nicefrac{{\alpha}}{{\varepsilon}}+\alpha$, so the length of $\zeta$ is
at most $c+\varepsilon$.

It remains to be shown that $\zeta$ indeed sees every point $p\in S^{d-1}$.
Let $H$ be the hyperplane tangent to the unit sphere in $p$. Further let
$t:=\min\\{t:\gamma(t)\in\nicefrac{{\alpha}}{{\varepsilon}}\cdot H\\}$. By
definition of $t^{\star}$, we have $t\leqslant t^{\star}$. Further, by
definition of $\zeta$, we have $\zeta(t)\in H$, implying that $\zeta(t)$ sees
$p$. ∎

In Section 2, we give an auxiliary lemma. In Sections 3 and 4 we will use that
lemma and show the following two theorems.

######  Theorem 1.

Any curve in $\mathbb{R}^{d}$ that inspects $S^{d-1}$ has length at least
$2d$.

######  Theorem 2.

There exists a closed curve $\gamma$ in $\mathbb{R}^{d}$ of length
$(2d)^{3/2}$ that inspects $S^{d-1}$.

##  2 An Auxiliary Lemma

The following lemma simplifies thinking about the Sphere Inspection Problem.

######  Lemma 3.

Let $P\subset\mathbb{R}^{d}$ be the convex hull of some point set $V$. Then,
the following two statements are equivalent.

  1. (i)

We have $S^{d-1}\subset P$.

  2. (ii)

The set $V$ sees every point $p\in S^{d-1}$.

###### Proof.

We start by showing that (i) implies (ii). Let $H$ be the hyperplane that is
tangent to the unit sphere in $p$. If $H$ contains a point $v\in V$, then the
lemma directly follows since the line segment $vp$ lies completely within $H$
and therefore does not intersect the unit sphere other than at $p$. So assume
that there is no point $v\in V$ that is contained in $H$. Then, and since $P$
contains one point of the hyperplane ($p\in S^{d-1}$, which is contained in
$P$ by (i)), there must exist two points $v_{1},v_{2}\in V$ which are
separated by $H$. Without loss of generality, let $v_{1}$ be the point in the
halfspace defined by $H$ whose interior is disjoint from $S^{d-1}$. Then the
line segment $v_{1}p$ is completely contained in that halfspace, and since the
interior of the halfspace is disjoint from $S^{d-1}$, $v_{1}$ can see $p$.

Now we show that (ii) implies (i). Towards a contradiction, assume that there
exists $p^{\star}\in S^{d-1}$ with $p^{\star}\notin P$. Then consider a
hyperplane $H$ that separates $p^{\star}$ from $P$, and let $n$ be a unit
normal vector of $H$ pointing away from $P$. Consider the hyperplane
$H^{\prime}$ that is tangent to $S^{d-1}$ in $n$. Clearly, both $P$ and
$S^{d-1}\setminus\\{n\\}$ are contained in one open halfspace defined by
$H^{\prime}$. Note that no point in this halfspace can see $n$. Therefore, no
$v\in V$ can see $n$; a contradiction. ∎

##  3 Lower Bound

The goal of this section is to prove Theorem 1. Towards this, let $\gamma$ be
a curve in $\mathbb{R}^{d}$ that inspects the unit sphere. We cut $\gamma$
into a minimum number of contiguous portions of length at most $\delta$ for
some fixed $\delta<2$. Let $\xi_{1},\dots,\xi_{n}$ be the resulting tour
portions, where $n=\lceil|\gamma|/\delta\rceil$. Choose a portion $\xi$, and
let $x$ be its midpoint. Clearly $\xi$ is contained in the ball $B$ that has
center $x$ and radius $\delta/2$. Further define $C$ to be the cone that is
the intersection of all halfspaces that contain both $B$ and $S^{d-1}$ and
whose defining hyperplanes are tangent to both $B$ and $S^{d-1}$. Note that
the set of points on the sphere that can be seen by the curve $\xi$ can also
be seen from the apex of $C$, as visualized by Figure 1. This holds since the
radius of $B$ is $\delta/2<1$. Note that a single point $p\in\mathbb{R}^{d}$
can see some subset of an open hemisphere $H$ of the unit sphere. Let
$H_{1},\dots,H_{n}$ denote a set of open hemispheres such that $H_{i}$ covers
the portion of the sphere seen by $\xi_{i}$. Since $\gamma$ inspects the
sphere, we have that $(H_{i})_{i=1}^{n}$ covers the sphere.

$B$$S^{d-1}$$C$$\xi$ Figure 1: The apex of the cone $C$ sees all points on the
unit sphere that $B$ does.

We need the following lemma.

######  Lemma 4.

The minimum number of open hemispheres that cover $S^{d-1}$ is $d+1$.

###### Proof.

To show that $d+1$ points are sufficient, choose a simplex containing the
sphere. Now consider the set of open hemispheres whose poles are colinear with
the origin and a vertex of that simplex. Indeed, since the simplex contains
the sphere, by Lemma 3, the set of vertices of the simplex sees every point
$p\in S^{d-1}$. Since each point sees only a subset of the corresponding open
hemisphere, the upper bound follows.

For the lower bound, we can use induction on $d$. Clearly the circle $S^{1}$
needs at least three open half-circles to be covered. For $S^{d-1}$, we have
that the boundary of the first hemisphere $H_{1}$ is $S^{d-2}$, and each
hemisphere $H_{i}$ can cover at most an open hemisphere of $\partial H_{1}$.
So by induction at least $(d-2)+2=d$ hemispheres are needed to cover $\partial
H_{1}$, and thus we have that at least $d+1$ hemispheres are needed to cover
$S^{d-1}$. ∎

By Lemma 4 we have that $n\geqslant d+1$, implying
$\lceil\mathrm{length}(\gamma)/\delta\rceil\geqslant d+1$ and therefore
$\mathrm{length}(\gamma)/\delta\geqslant d$. With $\delta=2-\varepsilon$, we
have that $\mathrm{length}(\gamma)\geqslant(2-\varepsilon)\cdot d$ for all
$\varepsilon>0$, and thus $\mathrm{length}(\gamma)\geqslant 2d$.

##  4 Upper Bound

In this section we prove Theorem 2. Let $C^{d}$ be the $d$-dimensional cross-
polytope, i.e., the polytope $\\{x\in\mathbb{R}^{d}:\lVert x\rVert_{1}\leq
1\\}$. Define $\bar{C}^{d}:=\sqrt{d}\cdot
C^{d}=\\{x\in\mathbb{R}^{d}:\|x\rVert_{1}\leq\sqrt{d}\\}$, as shown in Figure
2. We claim that the vertices of $\bar{C}^{d}$ inspect the unit sphere.

######  Lemma 5.

For any point $p\in S^{d-1}$, there exists a vertex $v$ of $\bar{C}^{d}$ that
sees $p$.

###### Proof.

We prove that $\bar{C}^{d}$ contains the unit sphere; then Lemma 3 shows the
claim. In other words we prove that for any point $x\in\mathbb{R}^{d}$ with
$\lVert x\rVert_{2}\leq 1$ (so, $x\in S^{d-1}$), it also holds that $\lVert
x\rVert_{1}\leq\sqrt{d}$. Indeed, by the Cauchy-Schwartz inequality we have
that $\lVert x\rVert_{1}\leq\sqrt{d}\cdot\lVert x\rVert_{2}$ for any $x$ which
in turn can be upper bounded by $\sqrt{d}$ for any $x\in\mathbb{R}^{d}$ with
$\lVert x\rVert_{2}\leq 1$. ∎

Let $G(\bar{C}^{d})$ be the graph111The graph $G(P)$ of a polytope $P$ is a
graph with a node for each vertex of $P$ and an edge connecting those nodes if
$P$ has an edge between the corresponding vertices. The graph of $P$ is also
referred to as its $1$-skeleton. of polytope $\bar{C}^{d}$. Note that
$G(\bar{C}^{d})$ is the so-called _cocktail party graph_ which can be obtained
by removing a perfect matching from a complete graph on $2d$ vertices (indeed,
in $\bar{C}^{d}$ any vertex $v$ has an edge to any other vertex except $-v$).
We next prove that $G(\bar{C}^{d})$ is Hamiltonian.

######  Lemma 6.

The graph $G(\bar{C}^{d})$ is Hamiltonian.

###### Proof.

The proof is by induction on $d$. The statement clearly holds for
$\mathbb{R}^{2}$ where the cross polytope is a square, and $G(\bar{C}^{2})$
itself is a Hamiltonian cycle that we denote by $c^{2}$. Consider a
Hamiltonian cycle $c^{d-1}$ for $G(\bar{C}^{d-1})$. Note that $G(\bar{C}^{d})$
can be constructed by $G(\bar{C}^{d-1})$ and adding two nodes, $v^{\star}$ and
$-v^{\star}$ that are connected to each of the nodes of $G(\bar{C}^{d-1})$. To
construct a cycle $c^{d}$ of $G(\bar{C}^{d})$, take any two distinct edges
$\\{v_{1},v_{2}\\}$ and $\\{v_{3},v_{4}\\}$ contained in $c^{d-1}$ and replace
them with the edges $\\{v_{1},v^{\star}\\},\\{v^{\star},v_{2}\\}$ and
$\\{v_{3},-v^{\star}\\},\\{v_{3},-v^{\star}\\}$, respectively. The resulting
tour is connected, visits all nodes of $G(\bar{C}^{d})$ exactly once and the
used edges are contained in the edge set of $G(\bar{C}^{d})$, thus ensuring
the feasibility of $c^{d}$. ∎

Figure 2: The cross polytope that has vertices at distance $\sqrt{d}$ from the
origin contains the unit sphere, and thus, a tour of its vertices (thick)
inspects the unit sphere.

By Lemma 5 it directly follows that any closed curve that visits all the
vertices of $\bar{C}^{d}$ inspects the unit sphere, and therefore so does the
closed curve $\gamma$ corresponding to the Hamiltonian cycle ${c}^{d}$ in the
skeleton of $\bar{C}_{d}$. To complete the proof of Theorem 2, note that each
edge of $\bar{C}_{d}$ has a length of $\sqrt{2d}$ and that $\gamma$ traverses
$2d$ such edges.

##  5 Conclusion

In this paper, we narrowed down the optimal competitive ratio for the
$d$-Dimensional Hyperplane Search Problem to $\Omega(d)\cap O(d^{3/2})$. The
obvious open problem is closing this gap.

### Acknowledgements.

We thank Paula Roth for helpful discussions.

## References

  * [1] Spyros Angelopoulos, Christoph Dürr, and Shendan Jin.  Best-of-two-worlds analysis of online search.  In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 126, pages 7:1–7:17, 2019.
  * [2] Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, and Kevin Schewior.  A PTAS for euclidean TSP with hyperplane neighborhoods.  ACM Trans. Algorithms, 16(3):38:1–38:16, 2020.
  * [3] Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins.  Searching in the plane.  Information and Computation, 106(2):234–252, 1993.
  * [4] Anatole Beck.  On the linear search problem.  Naval Research Logistics, 2:221–228, 1964.
  * [5] Anatole Beck and D. J. Newman.  Yet more on the linear search problem.  Israel Journal of Mathematics, 8(4):419–429, 1970.
  * [6] Richard Bellmann.  An optimal search problem.  SIAM Review, 5:274, 1963.
  * [7] Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson.  Finding the shortest watchman route in a simple polygon.  Discret. Comput. Geom., 22(3):377–402, 1999.
  * [8] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell.  Touring a sequence of polygons.  In ACM Symposium on Theory of Computing (STOC), pages 473–482. ACM, 2003.
  * [9] Adrian Dumitrescu and Csaba D. Tóth.  The traveling salesman problem for lines, balls, and planes.  ACM Trans. Algorithms, 12(3):43:1–43:29, 2016.
  * [10] Steven R Finch and Li-Yan Zhu.  Searching for a shoreline.  arXiv preprint math/0501123, 2005.
  * [11] Shmuel Gal.  Search Games.  Academic Press, 1980.
  * [12] Mohammad Ghomi and James Wenk.  Shortest closed curve to inspect a sphere.  Journal für die reine und angewandte Mathematik (Crelle’s Journal), 2021.  Forthcoming, preprint on arXiv under abs/2010.15204.
  * [13] Ming-Yang Kao, John H. Reif, and Stephen R. Tate.  Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem.  Information and Computation, 131(1):63–79, 1996.
  * [14] Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator.  Competitive snoopy caching.  Algorithmica, 3:77–119, 1988.