text:
# The integral under the variation $\delta$ sign

In physics books on classical field theory, the authors usually define the action as $$S = \int\mathcal{L(\phi,\partial_\mu\phi)d^4x}$$ where $\mathcal{L}$ is the lagrangian density. Then, they say that the principle of least action states that systems evolve along a path in configuration space for which $S$ is an extremum. So far, so good.

Then, when deriving Euler-Lagrange Equations, they write $$\delta S=0 \\ \iff \int\{\mathcal{\frac{\partial\mathcal{L}}{\partial\phi}\delta\phi+ \frac{\partial L}{\partial(\partial_\mu\phi)}}\delta(\partial_\mu \phi) \} d^4x =0$$

But they do not justify why this is true. Also, I do not have a clear, rigorous notion of what this "variation" $\delta$ is. Also: I have read somewhere that the principle of least action "is valid only in compact supported variations of the fields". Is this true? Although I know what compactly supported means, I do not know how that concept applies to this case.

Note: This argument can be found, for example, in Peskin and Schroeder's book on QFT.

## 1 Answer

Here is the usual ansatz they are referring to. If you are unsatisfied and still interested in learning it very rigorously you should refer to math texts on calculus of variations, but the physics books almost always repeat some variation of the following.

The action $S$ is a functional of your field and $\delta$ is a variation of the path. Specifically by $\delta S=0$ we mean that $S$ has no first order variation (in particular the variation vanishes in all directions).

So for a first order variation in the field (note the field is a function of the coordinates), e.g. $\phi\to\phi+\delta\phi$, you have:

$$\delta S=\int\mathcal{L(\phi+\delta\phi,\partial_\mu\phi+\delta(\partial_\mu\phi))}\,\mathrm{d}^4x-\int\mathcal{L(\phi,\partial_\mu\phi)}\,\mathrm{d}^4x=0$$

and then expanding the first $\mathcal{L}$ in Taylor series and only leaving first order terms, you have your equation. You then use integration by parts on the second term in your equation and drop the boundary terms (since they vanish on the edge of the support). You will later use that the variation vanishes at the end points (in all directions) to eliminate a term and that $\delta\to 0$ to finally get the variant of the Euler-Lagrange equations you're looking for.

• I'd add that the compact support condition is used to drop boundary terms in integration by parts. – J.G. Jul 26 '17 at 23:09
• @J.G. Thanks, added – GPhys Jul 26 '17 at 23:22


text:
## LaTeX forum ⇒ LyX ⇒ Question about LyX and Maxima Collaboration

Information and discussion about LyX, a WYSIWYM editor, available for Linux, Windows and Mac OS X systems.
dpa2007
Posts: 16
Joined: Sat Apr 19, 2014 1:39 pm

### Question about LyX and Maxima Collaboration

Greetings i'm using LyX and Maxima as CAS a few weeks.
Trying to compute the limit of a sequence i get no answer.
is a problem of my notation,problem of LyX or Maxima?
in other problems when changing the notation Maxima computed successfully the limit.
Any help...?

the limit is:
\lim_{n\rightarrow\infty}\left(\frac{\sin\left(\frac{n\cdot\pi}{3}\right)}{n^{2}}\right)

lim.png (966 Bytes) Viewed 6072 times
Last edited by cgnieder on Tue Jun 17, 2014 11:45 am, edited 6 times in total.
Reason: uploaded picture to latex-community server (this is preferable to external links)

Tags:

Johannes_B
Site Moderator
Posts: 4163
Joined: Thu Nov 01, 2012 4:08 pm
To be honest, i don't understand the question.
Can you be a bit more coomprehensive on your workflow? Is the problem typesetting, i.e. getting a valid pdf file?
The smart way: Calm down and take a deep breath, read posts and provided links attentively, try to understand and ask if necessary.

dpa2007
Posts: 16
Joined: Sat Apr 19, 2014 1:39 pm
LyX does not calculate the limit when i call Maxima from the path:
Edit>Math>use Computer Algebra System>Maxima.
in other cases Maxima gives back the correct answer,calculating for example the limit.
I'm wondering if this is a problem of Maxima or LyX.
It seems to calculate some limits for example and few others not.

StarValkyrie
Posts: 89
Joined: Fri Jan 24, 2014 12:42 am
Can you post the source for at least one problem that does get solved and at least one that doesn't get solved please?

dpa2007
Posts: 16
Joined: Sat Apr 19, 2014 1:39 pm
Solved!
the problem was in pi symbol,
when using the pi from the Greek's lyx menu (π) maxima did not understand( ) the symbol and returns the same expression.
when i change the Pi symbol with the 3.14 maxima has return the correct output.

and the result:
\lim_{n\rightarrow\infty}\left(\frac{\sin\left(\frac{n\cdot\pi}{3}\right)}{n^{2}}\right)&=&\lim_{n\rightarrow\infty}{\frac{\sin\left(\frac{n\,\pi}{3}\right)}{n^{2}}}\hspace{10 mm}\lim_{n\rightarrow\infty}\left(\frac{\sin\left(n\cdot3.14\right)}{n^{2}}\right)	=0

lim.png (2.5 KiB) Viewed 6072 times

Is it a way to make maxima understand pi from LyX?
Last edited by cgnieder on Tue Jun 17, 2014 11:47 am, edited 1 time in total.
Reason: uploaded picture to latex-community server (this is preferable to external links)

StarValkyrie
Posts: 89
Joined: Fri Jan 24, 2014 12:42 am
I don't use Maxima, but looking at the code you posted, nothing is jumping out as wrong. Maxima clearly isn't understanding something in the top of that fraction, but I don't know what. You mentioned using the Insert menu for pi so my first thought was that you might have ended up with the non-math code LyX uses for single symbols which would have been \textgreek{p}, but you're obviously in math mode and LyX did the conversion to \pi correctly there according to the code you posted, so that's probably not the issue. Just in case though, to get the math symbol while in math mode (or a math environment found in the Insert>Math menu), you don't need to go through the Insert menu --- just type "\pi " - the space after is important - and then you can be sure the code will be correct and Maxima will be able to read it. You can accomplish the same thing using the greek button (it has an alpha on it - if there aren't two toolbars at the bottom of your screen when you're in math mode, you can toggle the first by hitting the sigma button at the top of your screen and then the second by hitting the pi button on the one that appears at the bottom.) on the math toolbar and choosing pi there, but it's usually faster to just type the LaTeX.

dpa2007
Posts: 16
Joined: Sat Apr 19, 2014 1:39 pm
correct!
maxima did not understand the pi.
i have tried the use of % in LyX and Maxima returned the correct answers.

\lim_{n\rightarrow\infty}\left(\frac{\sin\left(n\cdot3.14\right)}{n^{2}}\right)=0\hspace{10 mm}\newline\lim_{n\rightarrow\infty}\left(\frac{\sin\left(n\cdot\%pi\right)}{n^{2}}\right)=0\hspace{10 mm}\newline\lim_{n\rightarrow\infty}\left(\frac{\sin\left(\frac{n\cdot\%pi}{3}\right)}{n^{2}}\right)=0

lim1.png (3.67 KiB) Viewed 6072 times

and another one example with the use of % in LyX
\lim_{n\rightarrow\infty}\left(\frac{\sin\left(\frac{n\cdot\%\pi}{3}\right)}{n^{2}}\right)&=&0

lim2.png (1.36 KiB) Viewed 6072 times

The answer is correct and Maxima returned no error result.
Last edited by cgnieder on Tue Jun 17, 2014 11:49 am, edited 1 time in total.
Reason: uploaded picture to latex-community server (this is preferable to external links)

format: plain


text:
3 Tutor System
Starting just at 265/hour

# Composition of the nuclei of two atomic species X and Y are given as under $$\space \space \space$$ X $$\space \space \space$$ Y Protons = 6 $$\space \space \space$$ 6 Neutrons = 6 $$\space \space \space$$ 8 Give the mass numbers of X and Y. What is the relation between the two species?

Mass number of X : Protons + neutrons = 6 + 6 = 12

Mass number of Y : Protons + neutrons = 6 + 8 = 14

They are the same element as they have same number of protons which means their atomic numbers are also the same.

Thus they are isotopes as they differ in the number of neutrons and hence they also differ in their mass numbers.


text:
# DEVS

DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems. DEVS is a timed event system.

## History

DEVS is a formalism for modeling and analysis of discrete event systems (DESs). The DEVS formalism was invented by Bernard P. Zeigler, who is emeritus professor at the University of Arizona. DEVS was introduced to the public in Zeigler's first book, Theory of Modeling and Simulation, in 1976, while Zeigler was an associate professor at University of Michigan. DEVS can be seen as an extension of the Moore machine formalism,[1] which is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input). The extension was done by

1. associating a lifespan with each state [Zeigler76],
2. providing a hierarchical concept with an operation, called coupling [Zeigler84].

Since the lifespan of each state is a real number (more precisely, non-negative real) or infinity, it is distinguished from discrete time systems, sequential machines, and Moore machines, in which time is determined by a tick time multiplied by non-negative integers. Moreover, the lifespan can be a random variable; for example the lifespan of a given state can be distributed exponentially or uniformly. The state transition and output functions of DEVS can also be stochastic.

Zeigler proposed a hierarchical algorithm for DEVS model simulation in 1984 [Zeigler84] which was published in Simulation journal in 1987. Since then, many extended formalism from DEVS have been introduced with their own purposes: DESS/DEVS for combined continuous and discrete event systems, P-DEVS for parallel DESs, G-DEVS for piecewise continuous state trajectory modeling of DESs, RT-DEVS for realtime DESs, Cell-DEVS for cellular DESs, Fuzzy-DEVS for fuzzy DESs, Dynamic Structuring DEVS for DESs changing their coupling structures dynamically, and so on. In addition to its extensions, there are some subclasses such as SP-DEVS and FD-DEVS have been researched for achieving decidability of system properties.

Due to the modular and hierarchical modeling views, as well as its simulation-based analysis capability, the DEVS formalism and its variations have been used in many application of engineering (such as hardware design, hardware/software codesign, communications systems, manufacturing systems) and science (such as biology, and sociology)

## Formalism

Fig. 1. A DEVS Model for Ping-Pong Game
Intuitive Example

DEVS defines system behavior as well as system structure. System behavior in DEVS formalism is described using input and output events as well as states. For example, for the ping-pong player of Fig. 1, the input event is ?receive, and the output event is !send. Each player, A, B, has its states: Send and Wait. Send state takes 0.1 seconds to send back the ball that is the output event !send, while Wait lasts the state until the player receives the ball that is the input event ?receive.

The structure of ping-pong game is to connect two players: Player A 's output event !send is transmitted to Player B 's input event ?receive, and vice versa.

In the classic DEVS formalism, Atomic DEVS captures the system behavior, while Coupled DEVS describes the structure of system.

The following formal definition is for Classic DEVS [ZKP00]. In this article, we will use the time base, ${\displaystyle \mathbb {T} =[0,\infty )}$ that is the set of non-negative real numbers; the extended time base,${\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}$ that is the set of non-negative real numbers plus infinity.

### Atomic DEVS

An atomic DEVS model is defined as a 7-tuple

${\displaystyle M=}$

where

• ${\displaystyle X}$ is the set of input events;
• ${\displaystyle Y}$ is the set of output events;
• ${\displaystyle S}$ is the set of sequential states (or also called the set of partial states);
• ${\displaystyle s_{0}\in S}$ is the initial state;
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ is the time advance function which is used to determine the lifespan of a state;
• ${\displaystyle \delta _{ext}:Q\times X\rightarrow S}$ is the external transition function which defines how an input event changes a state of the system, where ${\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}$ is the set of total states, and ${\displaystyle t_{e}}$ is the elapsed time since the last event;

[2]

• ${\displaystyle \delta _{int}:S\rightarrow S}$ is the internal transition function which defines how a state of the system changes internally (when the elapsed time reaches to the lifetime of the state);
• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ is the output function where ${\displaystyle Y^{\phi }=Y\cup \{\phi \}}$ and ${\displaystyle \phi \not \in Y}$ is a silent event or an unobserved event. This function defines how a state of the system generates an output event (when the elapsed time reaches to the lifetime of the state);
The atomic DEVS Model for Ping-Pong Players

The atomic DEVS model for player A of Fig. 1 is given Player=${\displaystyle }$ such that

{\displaystyle {\begin{aligned}X&=\{?{\textit {receive}}\}\\Y&=\{!{\textit {send}}\}\\S&=\{(d,\sigma )|d\in \{{\textit {Wait}},{\textit {Send}}\},\sigma \in \mathbb {T} ^{\infty }\}\\s_{0}&=({\textit {Send}},0.1)\\t_{a}(s)&=\sigma {\text{ for all }}s\in S\\\delta _{ext}((({\textit {Wait}},\sigma ),t_{e}),?{\textit {receive}})&=({\textit {Send}},0.1)\\\delta _{int}({\textit {Send}},\sigma )&=({\textit {Wait}},\infty )\\\delta _{int}({\textit {Wait}},\sigma )&=({\textit {Send}},0.1)\\\lambda ({\textit {Send}},\sigma )&=!{\textit {send}}\\\lambda ({\textit {Wait}},\sigma )&=\phi \end{aligned}}}

Both Player A and Player B are atomic DEVS models.

#### Behavior of Atomic DEVS

Simply speaking, there are two cases that an atomic DEVS model ${\displaystyle M}$ can change its state ${\displaystyle s\in S}$: (1) when an external input ${\displaystyle x\in X}$ comes into the system ${\displaystyle M}$; (2) when the elapsed time ${\displaystyle t_{e}}$ reaches the lifespan of ${\displaystyle s}$ which is defined by ${\displaystyle ta(s)}$. (At the same time of (2), ${\displaystyle M}$ generates an output ${\displaystyle y\in Y}$ which is defined by ${\displaystyle \lambda (s)}$.) .

For formal behavior description of given an Atomic DEVS model, refer to the page Behavior of DEVS. Computer algorithms to implement the behavior of a given Atomic DEVS model are available at Simulation Algorithms for Atomic DEVS.

### Coupled DEVS

The coupled DEVS defines which sub-components belong to it and how they are connected with each other. A coupled DEVS model is defined as an 8-tuple

${\displaystyle N=}$

where

• ${\displaystyle X}$ is the set of input events;
• ${\displaystyle Y}$ is the set of output events;
• ${\displaystyle D}$ is the name set of sub-components;
• ${\displaystyle \{M_{i}\}}$ is the set of sub-components where for each ${\displaystyle i\in D,M_{i}}$ can be either an atomic DEVS model or a coupled DEVS model.
• ${\displaystyle C_{xx}\subseteq X\times \bigcup _{i\in D}X_{i}}$ is the set of external input couplings;
• ${\displaystyle C_{yx}\subseteq \bigcup _{i\in D}Y_{i}\times \bigcup _{i\in D}X_{i}}$ is the set of internal couplings;
• ${\displaystyle C_{yy}:\bigcup _{i\in D}Y_{i}\rightarrow Y^{\phi }}$ is the external output coupling function;
• ${\displaystyle Select:2^{D}\rightarrow D}$ is the tie-breaking function which defines how to select the event from the set of simultaneous events;
The coupled DEVS model for Ping-Pong Game

The ping-pong game of Fig. 1 can be modeled as a coupled DEVS model ${\displaystyle N=}$ where ${\displaystyle X=\{\}}$;${\displaystyle Y=\{\}}$;${\displaystyle D=\{A,B\}}$; ${\displaystyle M_{A}{\text{ and }}M_{B}}$ is described as above; ${\displaystyle C_{xx}=\{\}}$; ${\displaystyle C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}}$; and ${\displaystyle C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi }$.

#### Behavior of Coupled DEVS

Simply speaking, like the behavior of the atomic DEVS class, a coupled DEVS model ${\displaystyle N}$ changes its components' states (1) when an external event ${\displaystyle x\in X}$ comes into ${\displaystyle N}$; (2) when one of components ${\displaystyle M_{i}}$ where ${\displaystyle i\in D}$ executes its internal state transition and generates its output ${\displaystyle y_{i}\in Y_{i}}$. In both cases (1) and (2), a triggering event is transmitted to all influencees which are defined by coupling sets ${\displaystyle C_{xx},C_{yx},}$ and ${\displaystyle C_{yy}}$.

For formal definition of behavior of the coupled DEVS, you can refer to Behavior of Coupled DEVS. Computer algorithms to implement the behavior of a given coupled DEVS mode are available at Simulation Algorithms for Coupled DEVS.

## Analysis Methods

### Simulation for Discrete Event Systems

The simulation algorithm of DEVS models considers two issues: time synchronization and message propagation. Time synchronization of DEVS is to control all models to have the identical current time. However, for an efficient execution, the algorithm makes the current time jump to the most urgent time when an event is scheduled to execute its internal state transition as well as its output generation. Message propagation is to transmit a triggering message which can be either an input or output event along the associated couplings which are defined in a coupled DEVS model. For more detailed information, the reader can refer to Simulation Algorithms for Atomic DEVS and Simulation Algorithms for Coupled DEVS.

### Simulation for Continuous State Systems

By introducing a quantization method which abstracts a continuous segment as a piecewise const segment, DEVS can simulate behaviors of continuous state systems which are described by networks of differential algebraic equations. This research has been initiated by Zeigler in 90's[3] and many properties have been clarified by Prof. Kofman in 2000's and Dr. Nutaro. In 2006, Prof. Cellier who is the author of Continuous System Modeling[Cellier91], and Prof. Kofman wrote a text book, Continuous System Simulation[CK06] in which Chapters 11 and 12 cover how DEVS simulates continuous state systems. Dr. Nutaro's book [Nutaro10], covers the discrete event simulation of continuous state systems too.

### Verification for Discrete Event Systems

As an alternative analysis method against the sampling-based simulation method, an exhaustive generating behavior approach, generally called verification has been applied for analysis of DEVS models. It is proven that infinite states of a given DEVS model (especially a coupled DEVS model ) can be abstracted by behaviorally isomorphic finite structure, called a reachability graph when the given DEVS model is a sub-class of DEVS such as Schedule-Preserving DEVS (SP-DEVS), Finite & Deterministic DEVS (FD-DEVS) [HZ09], and Finite & Real-time DEVS (FRT-DEVS) [Hwang12]. As a result, based on the rechability graph, (1) dead-lock and live-lock freeness as qualitative properties are decidable with SP-DEVS [Hwang05], FD-DEVS [HZ06], and FRT-DEVS [Hwang12]; and (2) min/max processing time bounds as a quantitative property are decidable with SP-DEVS so far by 2012.

## Variations of DEVS

### Extensions (Superclassing)

Numerous extensions of the classic DEVS formalism have been developed in the last decades. Among them formalisms which allow to have changing model structures while the simulation time evolves.

G-DEVS [Giambiasi01][Zacharewicz08], Parallel DEVS, Dynamic Structuring DEVS, Cell-DEVS [Wainer09], dynDEVS, Fuzzy-DEVS, GK-DEVS, ml-DEVS, Symbolic DEVS, Real-Time DEVS, rho-DEVS

### Restrictions (Subclassing)

There are some sub-classes known as Schedule-Preserving DEVS (SP-DEVS) and Finite and Deterministic DEVS (FD-DEVS) which were designated to support verification analysis. SP-DEVS and FD-DEVS whose expressiveness are E(SP-DEVS) ${\displaystyle \subset }$ E(FD-DEVS)${\displaystyle \subset }$ E(DEVS) where E(formalism) denotes the expressiveness of formalism.

## Footnotes

1. ^ automata were the mathematical models of Dr. Zeigler's Ph.D. thesis [Zeigler68]
2. ^ We can also define the external transition function as ${\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}$ where ${\displaystyle Q=S\times \mathbb {T} ^{\infty }\times \mathbb {T} }$ such that for a total state ${\displaystyle (s,t_{s},t_{e})\in Q}$, ${\displaystyle s\in S}$ is a partial state, ${\displaystyle t_{s}\in \mathbb {T} ^{\infty }}$ is the lifespan of ${\displaystyle s}$, and ${\displaystyle t_{e}\in (\mathbb {T} \cap [0,t_{s}])}$ is the elapsed time since last update of ${\displaystyle t_{s}}$. For more how to understand this function, refer to the article, Behavior of DEVS.
3. ^ the use of quantized values in order to simulate continuous systems by means of a discrete event method was empirically tried out a few years sooner - in the early 90's - by a French engineer <We need any reference for this argument>. He was then working for a company spun off from University of Valenciennes and Hainaut-Cambresis, and now part of the Schneider Electric. This quantization is a feature of a simulation software of which this engineer is the conceptor and main developer, that is used for PLC programs checking and operator training.

## References

• [Cellier91] Francois E. Cellier (1991). Continuous System Modeling (first ed.). Springer. ISBN 978-0-387-97502-3.
• [CK06] Francois E. Cellier; Ernesto Kofman (2006). Continuous System Simulation (first ed.). Springer. ISBN 978-0-387-26102-7.
• [Giambiasi01] Giambiasi N., Escude B. Ghosh S. “Generalized Discrete Event Simulation of Dynamic Systems”, in: Issue 4 of SCS Transactions: Recent Advances in DEVS Methodology-part II, Vol. 18, pp. 216–229, dec 2001
• [Hwang05] M.H. Hwang, "Tutorial: Verification of Real-time System Based on Schedule-Preserved DEVS", Proceedings of 2005 DEVS Symposium, San Diego, Apr. 2-8, 2005, ISBN 1-56555-293-8,
• [HZ06] M.H. Hwang and B. P. Zeigler, "A Modular Verification Framework using Finite and Deterministic DEVS", Proceedings of 2006 DEVS Symposium, pp57–65, Huntsville, Alabama, USA,
• [HZ09] M.H. Hwang and B.P. Zeigler, "Reachability Graph of Finite and Deterministic DEVS Networks", IEEE Transactions on Automation Science and Engineering, Volume 6, Issue 3, 2009, pp. 454–467,
• [Hwang12] M.H. Hwang, "Qualitative verification of finite and real-time DEVS networks", Proceedings of the 2012 Symposium on Theory of Modeling and Simulation - DEVS Integrative M&S Symposium, Article No. 43,
• [Mittal13] Saurabh Mittal; Jose L. Risco Martin (2013). Netcentric System of Systems Engineering with DEVS Unified Process (first ed.). CRC Press. ISBN 978-1439827062.
• [Nutaro10] James Nutaro (2010). Building Software for Simulation: Theory, Algorithms, and Applications in C++ (first ed.). Wiley. ISBN 0-470-41469-3.
• [Sarjoughian09] Hessam S. Sarjoughian; Vignesh Elamvazhuthi (2009). "CoSMoS: A Visual Environment for Component-Based Modeling, Experimental Design, and Simulation". Proceedings of the International Conference on Simulation Tools and Techniques.
• [Wainer09] Gabriel A. Wainer (2009). Discrete-Event Modeling and Simulation: A Practitioner's Approach (first ed.). CRC Press. ISBN 978-1-4200-5336-4.
• [Wainer10] Gabriel A. Wainer and Pieter Mosterman Eds. (2010). Discrete-Event Modeling and Simulation: Theory and Applications (first ed.). CRC Press. ISBN 978-1-4200-7233-4.
• [Zacharewicz08] Gregory Zacharewicz, Claudia Frydman, and Norbert Giambiasi (2008) G-DEVS/HLA Environment for Distributed Simulations of Workflows, SIMULATION May 2008 84: 197-213, doi:10.1177/0037549708092833.
• [Zeiger68] Bernard Zeigler (1968). On the Feedback Complexity of Automata (Ph.D. Thesis ed.). University of Michigan.
• [Zeigler76] Bernard Zeigler (1976). Theory of Modeling and Simulation (first ed.). Wiley Interscience, New York. ISBN 0-12-778455-1.
• [Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
• [Zeigler87] Bernard Zeigler (1987). "Hierarchical, modular discrete-event modelling in an object-oriented environment". Simulation 49 (5): 219–230. doi:10.1177/003754978704900506.
• [ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 978-0-12-778455-7.


text:
What is meant by a 95% confidence interval?

Feb 19, 2018

A confidence interval is the probability that a value will fall between an upper and lower bound of a probability distribution.

Explanation:

An essential part of statistics is accounting for the variability of the estimate. Statistical analysis can also describe how far from the estimates the actual values are likely to be. To describe the precision of an estimate, statisticians use margins of error and confidence intervals.

The margin of error and the confidence interval apply to the estimated value of the parameter for the entire population, not for the value of the variable for particular individuals.

A confidence interval is an interval that will contain a population parameter a specified proportion of the time. The confidence interval can take any number of probabilities, with the most common being 95% or 99%.

For example: $\text{ }$ If repeated samples were taken and the 95% confidence interval computed for each sample, 95% of the intervals would contain the population mean. Naturally, 5% of the intervals would not contain the population mean.


text:
To kick things off, I thought I’d post some of my earliest research-oriented scripts.

In the summers of my degree, we had a large research group in combinatorics, with tons of problems presented and then worked on in small groups. A number of them were combinatorial games: games of perfect information in which 2 players take alternating turns.

Several games arose as variations of one introduced to us as “Chaos”, based on a discrete chip-firing/sandpile process. (We were, or at least I was, astonished to learn the extent to which sandpile models appear in different branches of mathematics.) A graph is given as the game board, and players alternate turns adding a chip to a vertex. Between players’ turns, the chip-firing process occurs: if a vertex has at least as many chips as its degree, then it sends one chip to each of its neighbors, and this repeats. It is possible, and indeed necessary when enough chips have been played, that the chip-firing goes on forever, in which case our game ends.

I want to focus on two of the variants we studied, and we’ll just stick to complete graphs for the game boards. The two variants I’ll discuss here are impartial, meaning that the two players have the same play options throughout; for complete graphs, this means we can forget the graphs and just consider the chip counts at each vertex. (For non-complete boards, we did make similar scripts, using the graph utility nauty.) Hence our game state is just a non-increasing list of integers, and the chip-firing (which we were calling “toppling”) can be achieved by the following code common to both variants.

def topple(G):
ret = ""
for i in range(len(G)):
if G[i]>=len(G)-1:
G[i] -= len(G)-1
for j in range(len(G)):
if j != i:
G[j] += 1
if G[0]>=len(G)-1:
ret = "End Game"
G.sort(reverse=True)    #could make more efficient with targeted sort...(?)
return ret

Last play wins

The first variant is won by the player who sets off the infinite chip-firing sequence. Using the following script, we found that the first player wins on any complete graph with up to ten vertices.

import sys

def winner(G, player, E):
if G in E:
return E[G]
else:
#check value of subgames:
subgames = populate_subgames(G)
if len(subgames)==0:
E[G] = player
return E[G]
E[G]=1-player #set initial winner as NOT this player
for option in subgames:
if winner(option, 1-player, E)==player:
E[G] = player
break
return E[G]

def populate_subgames(G):  #returns empty if there is a winning move
subgames=set()
H=list(G)
for i in range(len(G)):
if i==0 or H[i]<H[i-1]:
#create gameboard with new token there
newH = H[:]
newH[i] += 1
if topple(newH)=="End Game":
subgames=set()
break
else:
newG=tuple(newH)
return subgames

def main():
n = int(sys.argv[1])
G = tuple([0]*n)

E={}
print winner(G, 0, E)

if __name__ == '__main__':
main()

There’s no real reason to expect a change after ten vertices. To try to prove that, it seemed helpful to consider the full game tree, to see what moves the first player should make. For that we need some small tweaks throughout to save the subgames from each position, and an addition to the main function to describe the game tree in graphviz code and automatically run that to produce a graphic:

import subprocess    #to run graphviz code to produce graphical game tree

def main():
n = int(sys.argv[1])
G = tuple([0]*n)

E={}  #holds values
S={}  #holds subgames
whowins = winner(G,0,E,S)

gvcode = "digraph G{"
for graph in E:
gvcode += '\"'+str(graph)+"\" "
if E[graph]==1:
gvcode += "[shape=box] "
for child in S[graph]:
if E[graph]==0:
gvcode += '\"'+str(graph)+"\"->\""+str(child)+"\" "
if E[graph]==0 and E[child]==1:
gvcode += "[color=red] "
gvcode += "}"
filename="K"+str(n).zfill(2)
f=open(filename+".gvz",'w')
f.write(gvcode)
f.close()

subprocess.call(["dot","-Tpng",filename+".gvz","-o"+filename+".png"])

And here are the first few game trees. (Most of the tree anyway. Since we “knew” that player 1 should win, we cut off the subtrees rooted at a second-player-win node. Those nodes are boxed, and the arrows going into them made red to draw attention to the first player’s losing moves.)

K6 A/B game tree

We did actually manage to prove that the first player wins when the number of vertices is odd.

Max-min variant

In this variant, the two players have opposing goals: one tries to maximize the number of chips played (which is also the length of the game) while the other tries to minimize it. Thus optimal play gives a parameter of the graph, the game chip number.

We cannot cut off branches when the maximizing player could end the game, so populate_subgames gets changed a bit (in particular, the ending state is recorded as an empty tuple). The most relevant change is in the winner function, which now returns a score instead:

def bBetter(option1, option2, player):
return True if ((option1>option2 and player==0) or
(option1<option2 and player==1)) else False

def score(G, player, E, S):
if G in E:
return E[G]
else:
#check value of subgames:
S[G] = populate_subgames(G)
if ( () in S[G] ) and (player==1 or S[G]==set([()]) ):
#if Min can end the game or the game must end
E[G] = sum(G)+1
S[G] = set([()])  #if Min's turn, kill any child nodes
return E[G]
bestoption=(0 if player==0 else len(G)**2 ) #set initial best option as bad for player
for option in S[G]:
if option!=():
newoption=score(option[:], 1-player, E, S)
if bBetter( newoption, bestoption, player ):
bestoption=newoption
E[G] = bestoption
return E[G]

Here are a couple of the game trees; the number in front of a position is the score when play starts from that node.

I imagine we had more data than this at some point, but here’s what I have about the game chip number of the complete graph on n vertices:

n 2 3 4 5 6 7 8
game chip number 1 4 8 12 18 26 34

Oh, and there are “easy” upper and lower bounds that we could include:

n 2 3 4 5 6 7 8
lower bound 1 3 6 10 15 21 28
game chip number 1 4 8 12 18 26 34
upper bound 1 4 9 16 25 36 49

The game chip number hovers (for these small n) about 1/3 of the way from the lower bound to the upper bound, but I don’t see any pattern in the particular numbers; do you?

REGS page


text:
complex geometry

# Moduli space of curves and

## Idea

The moduli space of algebraic curves/Riemann surfaces is a sort of space of parameters parametrizing algebraic curves of given genus.

Deligne and Mumford have found a nontrivial compactification of a moduli space of Riemann surfaces of fixed genus which is a Deligne-Mumford stack, see at Deligne-Mumford compactification.

There is also a decorated version of curves with marked points, and of the corresponding compactified moduli space of stable curves of genus $g$ with $n$ marked points $\mathcal{M}_{g,n}$ which plays an important role in the mathematical study of Gromov-Witten invariants and of conformal blocks.

The special case of $g = 1$, $n =1$ is the moduli stack of elliptic curves $\mathcal{M}_{1,1}= \mathcal{M}_{ell}$.

## Properties

### Orbifold Euler characteristic

The orbifold Euler characteristic $\chi$ of $\mathcal{M}_{g,1}$ is given by the Riemann zeta function at negative integral values as follows (Zagier-Harer 86):

$\chi(\mathcal{M}_{g,1}) = \zeta(1-2g) \,.$

By the expression of the Riemann zeta function at negative integral values by the Bernoulli numbers $B_n$, this says equivalently that

$\chi(\mathcal{M}_{g,1}) = -\frac{B_{2g}}{2g} \,.$

For instance for $g = 1$ (once punctured complex tori, hence complex elliptic curves) this yields

$\chi(\mathcal{M}_{1,1}) = -\frac{1}{12}$

## References

• David Mumford, Towards an enumerative geometry of the moduli space of curves, Arithmetic and geometry, Vol. II, Birkhäuser Boston, Boston, MA, 1983, pp. 271–328, MR85j:14046

• Pierre Deligne, David Mumford, The irreducibility of the space of curves of given genus . Publications Mathématiques de l’IHÉS (Paris) 36: 75–109 (1969) numdam

• John Harer, The cohomology of the moduli space of curves, Lec. Notes in Math. 1337, p. 138–221. Springer, Berlin, 1988.

• Ib Madsen, Michael Weiss, The stable moduli space of Riemann surfaces: Mumford's conjecture, Ann. of Math. (2) 165 (2007), no. 3, 843–941, MR2009b:14051, doi, math.AT/0212321

• G. Mondello, Combinatorial classes on $\mathcal{M}_{g,n}$ are tautological, Int. Math. Res. Not. 44 (2004), 2329-–2390, MR2005g:14056, doi, math.AG/0303207

• Gabriele Mondello, Riemann surfaces, ribbon graphs and combinatorial classes, in: Handbook of Teichmüller theory. Vol. II, 151–215, IRMA Lect. Math. Theor. Phys., 13, Eur. Math. Soc., Zürich, 2009; draft with index: pdf, arxiv version math.AG/0705.1792, MR2010f:32012

• Alastair Hamilton, Classes on compactifications of the moduli space of curves through solutions to the quantum master equation, Lett. Math. Phys. 89 (2009), no. 2, 115–130.

• The moduli of curves pdf

The orbifold Euler characteristic of the moduli space of curves was originally computed in

• Don Zagier, John Harer, The Euler characteristic of the moduli space of curves, Inventiones mathematicae (1986) Volume: 85, page 457-486 (EUDML)

Reviews include

• Mathematical ideas and notions in quantum field theory – 5. The Euler characteristic of the moduli space of curves (pdf)

Revised on April 9, 2014 08:35:51 by Urs Schreiber (145.116.131.80)


text:
# Understanding of the proof of “$d$ solutions for $kx \equiv l \pmod{m}$”

The question is from the proof of a theorem in Hardy's An Introduction to the Theory of Numbers.

THEOREM 57. If $(k, m) = d$, then the congruence $$(5.4.1)\qquad kx \equiv l \pmod{m}$$ is soluble if and only if $d|l$. It has then just $d$ solutions. In particular, if $(k, m) = 1$, the congruence has always just one solution.

Proof:
The congruence is equivalent to $$kx-my=l,$$

so that the result is partly contained in Theorem 25. It is naturally to be understood, when we say that the congruence has "just d" solutions, that congruent solutions are regarded as the same.

If $d = 1$, then Theorem 57 is a corollary of Theorem 56. If $d > 1$, the congruence (5.4.1) is clearly insoluble unless $d|l$. If $d|l$, then $$m = dm', \quad k = dk',\quad l = dl',$$ and the congruence is equivalent to $$(5.4.2)\qquad k'x \equiv l'\pmod{m'}.$$ Since $(k', m') = 1$, (5.4.2) has just one solution.

If this solution is $$x\equiv t\pmod{ m'},$$ then $$x=t+ym',$$ and the complete set of solutions of (5.4.1) is found by giving $y$ all values which lead to values of $t + ym'$ incongruent to modulus $m$. Since $$t+ym'\equiv t+zm'\pmod{m}\Leftrightarrow m|m'(y-z)\Leftrightarrow d|(y-z),$$ there are just $d$ solutions, represented by $$t, t + m', t + 2m',\cdots, t+(d-1)m'.$$ This proves the theorem.

Originally, the second last sentence is

Here are my questions:

• Is there a typo in the original text?

• Why are the $d$ solutions represented like that? What do the commas mean here? (Do they mean "or" or "and"?)

• What's the relationship between the last step in the proof and the question here?

-
Since Theorem 25 and Theorem 56 in the book are not directly related to my questions, I do not post them here. – Jack Jun 18 '11 at 2:07
The $t+tm'$ is a typo. Also, the final entry on that line looks like $t+(d-l)m'$ to me. If so, it's wrong, it should be $t+(d-1)m'$. Hardy and Wright is a lovely book to read, once you know some Number Theory. Something more modern might give a better start. There are even free texts online. – André Nicolas Jun 18 '11 at 2:31
Just for fun, I'm mentioning the worst typo I had ever seen... first time I read number theory, I came across this :  Wilson's Theorem. If $p$ is a prime, then $(p-1) \equiv -1 (\!\!\!\! \mod p)$. Proof. If $p=2$ or $p=3$, the congruence is easily verified. Thus we may assume that $p \ge 5$. Suppose that $1 \le a \le p-1$. Then $(a,p) = 1$, so that by Theorem 2.9 there is a unique integer $\overline a$ such that $a \overline a \equiv 1 (\!\!\!\! \mod p)$. (Few lines later, I saw the $(p-1)!$ appear and I googled.) Man did that proof scare me at first... – Patrick Da Silva Jul 30 '11 at 7:47

Edit: As mentioned in the comments, yes, it's not just the $t + tm'$, but the last one should read $t + (d-1)m'$. So there are two typos in that line from the book.

For congruences, you have both "and" and "or"! For example, consider \begin{align*} 3x \equiv 3 (\bmod 12) \end{align*} Now $\gcd(3,12) = 3$, so we expect 3 different solutions. One can easily find 1, 5, and 9 all work. Now the congruences classes of 1,5 and 9 modulo 12 are all different, hence in this setting they are 3 different solutions.

However, notice that 13 also works. In fact, any number of the form $12n + 1, 12n + 5$ or $12n + 9$ will work, as the 12 disappears modulo 12. So when you are considering multiple solutions to a congruence, \begin{align*} kx \equiv l (\bmod m) \end{align*} you want the "and" meaning for all the solutions that are distinct modulo $m$, and you want the "or" meaning when they are the same modulo class.

Hope this helps!

Added: I should add, for a congruence modulo $m$, we call the congruence class of $x$, the set $\{mn + x: n\in \mathbb{Z}\}$.

-
A nitpick: There is a second typo in the original text. The last solution in the list should be $(d-1)m'$ rather than $(d-l)m'$. – Doug Chatham Jun 18 '11 at 2:27
Oh yes, I didn't look that far.. At least that tells us for sure the 1 is not formatted oddly like a $t$ or and $l$ though! :) – Alex Jun 18 '11 at 2:29

First - there is a typo in the original text. Texts (mathematical or otherwise) are always full of typos, though some are worse than others. Use your common sense.

Second - there is more than one way to represent the solutions. For example, any $d$ consecutive multiples of $m'$ would do. More concretely, you could replace all $+$s with $-$s. The specific set was chosen for no particular reason. No, that's actually a lie. It was chosen since it is the first that comes to mind.

Third - the commas here serve to separate items in a list. For example "in this shop one could buy apples, oranges, pears and bananas". Or "please get me an apple, an orange or a pear". Or "please select two of the following pieces for your test: Hamlet, Macbeth, King Lear, Othello".

-


text:
## Tuesday, January 12, 2010

### The Kondo screening cloud

The Kondo screening cloud: what it is and how to observe it
The Kondo effect involves the formation of a spin singlet by a magnetic impurity and conduction electrons. It is characterized by a low temperature scale, the Kondo temperature, $T_K$, and an associated long length scale, $\xi_K = \hbar v_F/(k_BT_K)$ where $v_F$ is the Fermi velocity. This Kondo length is often estimated theoretically to be in the range of .1 to 1 microns but such a long characteristic length scale has never been observed experimentally. In this review, I will examine how $\xi_K$ appears as a crossover scale when one probes either the dependence of physical quantities an distance from the impurity or when the impurity is embedded in a finite size structure and discuss possible experiments that might finally observe this elusive length scale.

### Ultra High Energy Cosmic Rays (UHECR)

UHECR Maps: mysteries and surprises
The rise of nucleon UHECR above GZK astronomy made by protons is puzzled by three main mysteries: an unexpected nearby Virgo UHECR suppression, a rich crowded clustering frozen vertically (north-south) along Cen A, a composition suggesting nuclei and not nucleons. The UHECR map, initially consistent with GZK volumes, to day seem to be not much correlated with expected Super Galactic Plane. Moreover slant depth data of UHECR from AUGER airshower shape do not favor the proton but points to a nuclei, while HIRES, on the contrary favors mostly nucleons. We tried to solve the contradictions assuming UHECR as light nuclei (mostly He) spread by planar galactic fields, randomly at vertical axis. The He fragility and its mass and charge explains the Virgo absence (due to opacity above few Mpc) and the Cen A spread clustering (a quarter of the whole sample). However more events and rare doublets and clustering elsewhere are waiting for an answer. Here we foresee hint of new UHECR component: galactic ones. Moreover a careful updated views of UHECR sky over different (Radio,IR,Optics, X,gamma, TeV) background are also favoring forgotten revolutionary Z-shower model. Both Z-Shower, proton GZK and Lightest nuclei UHECR models have dramatic influence on expected UHE neutrino Astronomy: to be soon revealed by UHE tau neutrino induced air-showers in different ways.

Observation of Ultra-high Energy Cosmic Rays
The measurement of ultra-high energy cosmic rays is an unique way to study article interactions at energies which are well above the capability of current accelerators. Significant progress in this field has occurred during last years, particularly due to the measurements made at the Pierre Auger Observatory. The important results which were achieved during last years are described here. Also future plans for the study of cosmic rays are presented.

High Energy Radiation from Black Holes: A Summary
Bright gamma-ray flares observed from sources far beyond our Galaxy are best explained if enormous amounts of energy are liberated by black holes. The highest-energy particles in nature--the ultra-high energy cosmic rays--cannot be confined by the Milky Way's magnetic field, and must originate from sources outside our Galaxy. Here we summarize the themes of our book, "High Energy Radiation from Black Holes: Gamma Rays, Cosmic Rays, and Neutrinos", just published by Princeton University Press. In this book, we develop a mathematical framework that can be used to help establish the nature of gamma-ray sources, to evaluate evidence for cosmic-ray acceleration in blazars, GRBs and microquasars, to decide whether black holes accelerate the ultra-high energy cosmic rays, and to determine whether the Blandford-Znajek mechanism for energy extraction from rotating black holes can explain the differences between gamma-ray blazars and radio-quiet AGNs.

### Galaxy Structure

Nearby Galaxies and Problems of Structure Formation; a Review
The relativistic hot big bang cosmology predicts gravitational gathering of matter into concentrations that look much like galaxies, but there are problems reconciling the predictions of this cosmology with the properties of the galaxies at modest distances that can be observed in greatest detail. The least crowded place nearby, the Local Void, contains far fewer dwarf galaxies than expected, while there are too many large galaxies in the less crowded parts of our neighborhood. The structures of large galaxies show little relation to their environment, contrary to the standard picture of assembly of galaxies by the gathering of material from the surroundings, and the continued accretion of extragalactic debris has prevented establishment of an acceptable picture of formation of common galaxies with the properties of our Milky Way. There is the possibility that the indirect evidence astronomy affords us has been misinterpreted. But the variety of different challenges makes a strong case that we need a better theory, one that does not disturb the agreement with the network of cosmological tests applied on larger scales and fits what is observed on the scales of galaxies. A promising direction is more rapid structure formation, as happens in theoretical ideas under discussion.


text:
# Friction/ Newtons Laws

1. Jan 8, 2014

### KiNGGeexD

Hi I am stuck with a question which I have attached a photo of, it is one involving friction! I have done a few of these questions already and find it is when I am defining forces etc it's where I go wrong, not the easy computational part:(

I also have attached my attempt at the solution and have drawn my free body diagram as clear as possible:)

Any help would be great:) thanks

2. Jan 8, 2014

### voko

I see no mistake in your attempt so far.

3. Jan 8, 2014

### KiNGGeexD

Excellent I shall continue onwards and reply shortly:)

4. Jan 8, 2014

### KiNGGeexD

Ok I went on and done this to find the acceleration but the model answer is 3.71 m/s^2

5. Jan 8, 2014

### voko

In your computation you assumed that static friction will not be strong enough to prevent motion. Part (a) of the problem required you to determine whether this was the case.

6. Jan 8, 2014

### KiNGGeexD

It is not strong enough

7. Jan 8, 2014

### KiNGGeexD

It is the two fractions which are confusing me, kinetic friction is the friction between two moving bodies and static is between two non moving bodies would there be a case where both would have to come into a computation?

8. Jan 8, 2014

### voko

Can you demonstrate that?

9. Jan 8, 2014

### voko

I did not see #7 when I wrote #8. Please explain how you determined that static friction was not strong enough to prevent motion. That will help clarify what you confusion really is.

10. Jan 8, 2014

### KiNGGeexD

So for the block to move mg sinθ must be greater than static friction?

11. Jan 8, 2014

### KiNGGeexD

Sorry F cosθ

12. Jan 8, 2014

### voko

Yes, the horizontal component of force must be greater than the maximal static friction. The maximal static friction is given by $\mu_s N$.

13. Jan 8, 2014

### KiNGGeexD

14. Jan 8, 2014

### voko

I agree with your result, but it is not correct to write $F \cos \theta - \text{fr} = 0$. You should write $F \cos \theta - \text{fr} > 0$.

15. Jan 8, 2014

### CWatters

Check what value you used for μ.

I put 0.2 into your earlier equation and got 3.7 as the answer.

16. Jan 8, 2014

### KiNGGeexD

Oh! Haha I think I've got it now lol


text:
# The Set Cover problem

I’m lucky enough to work in a company that employs people from many different countries. We were comparing the ease of travel given by different passport using passportindex.org. So we wondered: what’s the minimum set of passports necessary to travel in any country visa-free?

A passport. Photo by Nicole Geri on Unsplash

Turns out that it’s impossible. Some countries, like Saudi Arabia and North Korea, are only accessible using passports of countries that don’t allow dual citizenship. But if we pretend that all countries allow multiple citizenship without restriction, what would be the minimum set of passports that would cover the whole world?

This is an example of set cover problem, which is one of Karp’s 21 NP-complete problems1. The definition of the problem goes like this:

Given a collection of elements $$U = \lbrace 1, 2, \ldots, n\rbrace$$ called universe, and a collection $$S$$ of $$m$$ subsets of $$U$$ whose union is equal to $$U$$ (formally: $$\bigcup_{i=1}^m m_i = U$$), what is the smallest sub-collection of $$S$$ such that the union of its members still equals $$U$$?

The image above shows an example of set cover problem. The most obvious greedy algorithm to solve the problem is: until there are uncovered elements, select the set that covers the maximum amount of elements. In the example above at the first iteration we would select $$S_1$$ because it covers 6 elements, then $$S_4$$ because adds 3 more elements, then $$S_3$$, and finally one between $$S_5$$ or $$S_6$$. However there’s a smaller solution: $$\lbrace S_3, S_4, S_6\rbrace$$. Imagine now how hard it’d be to find the optimal solution if there were hundreds or more elements and sets.

Set cover problem is definitely not just an interesting theoretical problem, it also has very real world applications. One that is known to everyone is Sudoku, which can be re-stated in the form of set cover. Another one which is not universally known but has a very high monetary impact is shift scheduling: for example airline companies must find a number with different specializations for each shift, often with additional constraints (e.g.: due to labor laws, holidays, and so on). Sometimes set cover problems are hidden in plain sight: imagine to have a database of tagged items, and you want to find the smallest set of tags such that all items are represented at least once. This is another version of the minimal set cover problem.

# Travelling everywhere as minimum set cover problem

Seeing how the visa-free travel problem maps to the minimal set problem is straightforward: the universe $$U$$ is the set of countries, and each passport selects a subset of countries where it allows visa-free travel. We want to select the minimum number of passports that covers all the countries. Easy! But finding the optional solution is way less simple.

## Getting the data

I used https://github.com/ilyankou/passport-index-dataset/, which provides a useful CSV file (passport-index-tidy.csv). Each row of the CSV file contains the country that issued a passport, a destination country, and “3” if the passport allows visa-free travel, and “-1” if the country that issued the passport and the destination country are the same. Now that we have the data, we can find an answer to our question.

I first solved the problem using the CP-SAT solver provided by Google OR-Tools and its Python implementation. The installation of OR-Tools is straightforward:

pip3 install --user ortools

In general the CP-SAT solver works by creating a Constraint Programming model (CP), populating it with variables, adding constraints to those variables, imposing metrics that should me minimized or maximized, and then asking a CP Solver to find a solution.

First, let’s open and parse passport-index-tidy.csv and create a CP-SAT boolean variable for each passport. Under the hood OR-Tools implements boolean variables as integers with two additional constraints: each variable x must satisfy x >= 0 && x<= 1.

We are going to create a set for each country, and we are going to put into each set the passport variables that allow visa-free travel. Here’s the code:

#!/usr/bin/env python3

import csv
from ortools.sat.python import cp_model

if __name__ == '__main__':
# model is the Constraint Programming model
model = cp_model.CpModel()

# visa_free is a map from a destination country to the set of passport
# that allow visa free travel
visa_free = {}

# passport_vars maps passport names to variables managed by the CP-SAT
# model
passport_vars = {}

# Load the passport data, provided by
# https://github.com/ilyankou/passport-index-dataset/ , each row is in
# the format:
# passport country, destination country, <type of access>
with open('passport-index-tidy.csv', 'r') as f:
# p is the passport being used
p = row[0]
# d is the destination country
d = row[1]

# Get the boolean variable for this passport, otherwise create a
# new one.
p_var = passport_vars.setdefault(p, model.NewBoolVar(p))
# Get the set of passports that allow visa-free travel to country
# d if it exists, otherwise create a new one.
passport_set = visa_free.setdefault(d, set())

# '3' represents visa-free travel, '-1' means that the passport
# is issued by the destination country
if row[2] == '3' or row[2] == '-1':
# Add passport p_var to the set of passports that allow
# visa-free travel to country d_var

At this point visa_free will contain a map from countries to all the passport that allow visa-free travel to it. To be able to travel anywhere, we want at least one passport from each set of passports. Since booleans are actually integers constrained to be 0 or 1, we can express this constraint as: the sum of all passport variables for a given destination must be 1 or higher. The code that does this is almost a literal translation:

    # For each set of passports that allows visa-free travelling to a country…
for destination, allowed_passports in visa_free.items():
if not allowed_passports:
print(f'No valid passports for {destination}. Ignoring.')
continue
# …at least one of the passports must be selected

The last line of code is the one that actually adds the constraint to the CP model. Variables created with CpModel.NewBoolVar overload the __add__ function, so summing them returns a new object (specifically a SumArray) that can store constraints. With model.Add(sum(allowed_passports) >= 1) we are asking the solver to make sure that for that given set at least one of the variables is set to 1.

If we didn’t ask for anything else then a trivial solution would be to have all the passports. To avoid this, we also ask the solver to minimize the total number of passports:

    model.Minimize(sum(passport_vars.values()))

Here we are taking all the passport variables and asking the optimizer to minimize its sum, i.e. to select the minimum number of passports.

We can now ask the solver to search for a solution:

    solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
selected_passports = [p for p in passport_vars
if solver.Value(passport_vars[p])]
print('Passports: %d' % len(selected_passports))
print(', '.join(sorted(selected_passports)))
else:
print('Unable to find an optimal solution')

That’s it!

Running this code will print:

\$ ./passports_ortools.py
Passports: 23

Afghanistan, Bulgaria, Canada, Comoros, Equatorial Guinea, Ethiopia, Georgia,
Hong Kong, Ivory Coast, Madagascar, Maldives, Nepal, New Zealand, North Korea,
Papua New Guinea, Singapore, Somalia, Sri Lanka, Tunisia, Turkey, Uganda,
United Arab Emirates, Zimbabwe

There we go! We need just 23 passports! This is not a viable solution in the real world because some of these countries do not allow dual citizenship, but it does satisfy the constraints that we gave to the CP-SAT solver.

This code takes 2m40s to run on my machine (Intel i7-8700K). Implementing a cp_model.CpSolverSolutionCallback to print intermediate solution shows that the optimal solution is found after just 1.20s, but it takes 2m39s for the solver to be convinced that the solution is, in fact, optimal.

## Solving with Microsoft Z3

Z3 is a theorem prover from Microsoft Research. Z3 made quite a splash when it was released, and it even won the 2015 ACM SIGPLAN Programming Languages award.

Installing Z3 is matter of:

pip3 install --user z3-solver

Z3 is more flexible than Google’s CpSolver, but for this specific problem the structure of our program is going to be almost the same, modulo API changes.

First, let’s read the data, exactly in the same way as we did wit OR-Tools:

#!/usr/bin/env python3

import csv
import z3

if __name__ == '__main__':
# optimizer is the z3 Optimizer, which provides functions to minimize
# or maximize objectives.
optimizer = z3.Optimize()

# visa_free is a map from a destination country to the set of passport
# that allow visa free travel
visa_free = {}

# passport_vars maps passport names to variables managed by the CP-SAT
# model
passport_vars = {}

# Load the passport data, provided by
# https://github.com/ilyankou/passport-index-dataset/ , each row is in
# the format:
# passport country, destination country, <type of access>
with open('passport-index-tidy.csv', 'r') as f:
# p is the passport being used
p = row[0]
# d is the destination country
d = row[1]

Z3 provides boolean variables that are not built on top of integers variable (at least in the public API). This makes it harder to define the function that we want to minimize (i.e.: select the minimum number of passports), therefore we are going to use integers instead:

            # retrieve the passport variable if it already exists…
if p in passport_vars:
p_var = passport_vars[p]
else:
# … otherwise create a new one, and make sure that it's
# 0 ≤ p_var ≤ 1
p_var = z3.Int(p)
optimizer.add(p_var >= 0, p_var <= 1)
passport_vars[p] = p_var
passport_set = visa_free.setdefault(d, set())
# '3' represents visa-free travel, '-1' means that the passport
# is issued by the destination country
if row[2] == '3' or row[2] == '-1':
# Add passport p_var to the set of passports that allow
# visa-free travel to country d_var

Next step: make sure that for each set of passports we select at least one. The code is remarkably similar to the one we wrote for OR-Tools:

    # For each set of passports that allows visa-free travelling to a country…
for destination, allowed_passports in visa_free.items():
if not allowed_passports:
print(f'No valid passports for {destination}. Ignoring.')
continue
# …at least one of the passports must be selected

Now let’s add the optimization goal: try to select the minimum number of passports:

    optimizer.minimize(sum(passport_vars.values()))

Now we can check if the model can be satisfied, and if yes what are the selected passports:

    # If the optimizer can find a solution then…
if optimizer.check() == z3.sat:
m = optimizer.model()
selected_passports = []
for p_name, p_var in passport_vars.items():
# Check in the model if the passport is selected
if m[p_var] == 1:
selected_passports.append(p_name)

selected_passports.sort()
print('Passports: %d' % len(selected_passports))
print(', '.join(selected_passports))
else:
print('Unable to find an optimal solution')

That’s it!

We can now run the binary:

Passports: 23

Afghanistan, Australia, Bulgaria, Canada, Comoros, Djibouti, Equatorial Guinea,
Georgia, Hong Kong, India, Madagascar, Malaysia, Maldives, Nigeria,
North Korea, Papua New Guinea, Somalia, Sri Lanka, Tunisia, Turkey, Uganda,
United Arab Emirates, Zimbabwe

This version is phenomenally faster than the one implemented with OR-Tools. It takes just 0.6s on my machine for Z3 to find the optimal solution (300x faster than OR-Tools).


text:
Suggested problems

Move-to-front transform (decode)

Oct. 10, 2012, 8:54 p.m. by Maxim

Given: A encoded string $s$ of length at most 1000 numbers.

Return: Decode string of nucleotides

Sample Dataset

1 1 1 1 3 3 3 2 1 3 2
2 2 1 1 3 1 2 2 0 0 0

Sample Output

CACATGCTCAT
GCGCTCGTTTT


text:
### Author Topic: Tag each equation in an IVP  (Read 1748 times)

#### Jingxuan Zhang

• Elder Member
• Posts: 106
• Karma: 20
##### Tag each equation in an IVP
« on: February 10, 2018, 04:14:10 PM »
I am trying to typeset in latex a system such as
$$\left\{\begin{array}{cc}f(x)&=k_1\\g(x)&=k_2\end{array}\right..$$
Is there anyway that allows me to label each individual equation such as with \tag? True, with align I can label but i need also the brace. True, with array I can brace but then cannot label. Thanks.

#### Victor Ivrii

• Administrator
• Elder Member
• Posts: 2563
• Karma: 0
##### Re: Tag each equation in an IVP
« Reply #1 on: February 10, 2018, 05:30:32 PM »
There is a package empheq, which allows you to do it in the normal LaTeX

Does not work in MathJax (so far, at least)


text:
# A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l_1-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report numerical experience with solving the l_1-regularization of unconstrained optimization problems from More et al. and from the CUTEr set. Comparison with L-BFGS-B and MINOS, applied to a reformulation of the l_1-regularized problem as a bound-constrained optimization problem, is also reported.

## Citation

Report, Mathematics Department, University of Washington, Seattle; June 2006; revised April 2007; to appear in Math Programming, B.


text:
# Using transfer function model to generate state space model

I am trying to generate the state space model for the following system:

However, the following code does not generate the state space model I expect:

tf = TransferFunctionModel[{{1/s}, {1/(s + 2)}}, s]
ssm = StateSpaceModel[tf]

What I'm expecting is

$A = \begin{bmatrix} -2 & 0 \\ 1 & 0 \end{bmatrix}$ $B = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ $C = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ $D = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$

but what I'm getting is

$A = \begin{bmatrix} 0 & 1 \\ 0 & -2 \end{bmatrix}$ $B = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ $C = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}$ $D = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$

The state equations are:

$$\dot{x_1}(t) = -2 x_1 (t) + w_1 (t)$$ $$\dot{x_2}(t) = x_1(t) + u(t)$$ $$y_1(t) = x_2(t)$$ $$y_2(t) = \dot{x}_2(t)$$

where $w_1(t)$ denotes the white noise added to the system, and $x_2(t)$ denotes the system error, $e$.

How should I enter my transfer function model to generate such a state space model?

-
I think you have a typo, because the matrices you expect do not give the transfer function you started with. In any case, look at the option StateSpaceRealization and see if that will solve your problem. – Suba Thomas Apr 5 '13 at 16:29
It looks like you are entering it in the form TransferFunctionModel[{num,den},s]. I don't see the relation between this num, den and your picture. What variable is the input and what variable is the output of your transfer function? – bill s Apr 5 '13 at 16:29
No, it's not {num,den}, but a matrix, as it's a MIMO system with one input and two outputs. The input to the system is the white noise, and two outputs are $e$ and $\dot{e}$. I'll add the state equations to hopefully make more sense. – Gerrit Apr 8 '13 at 8:20
The state is {x1, x2}. So your C matrix says that $y_2(t)=x_2(t)$, not that $y_2(t)=\dot{x}_2(t)$ as in your state equation. – bill s Apr 8 '13 at 9:01
But more fundamentally, how is u ("control input") calculated from $e$ and $\dot{e}$? If you don't specify this, then you have a 2-input ($u$ and white noise) and 2-output ($e$ and $\dot{e}$) system. So you have neither the state equations nor the state space equations correct. – bill s Apr 8 '13 at 9:12

System sys1 has inputs $u(t)$ and the white noise.

sys1 = StateSpaceModel@TransferFunctionModel[{{1, 1/((s + 2))}}, s];

We are only interested in the input $u(t)$ and so we extract the subsystem corresponding to that.

sys2 = SystemsModelExtract[sys1, 1];

The desired output of the overall system is 1) $e(t)$ which is the integral of the output of sys1 and 2) $\dot{e}(t)$ which can just be taken as the output of sys1. So I am going to construct a system that I plan to connect in series with sys2.

sys3 = TransferFunctionModel[{{1/s}, {1}}, s];

Now the series connection will give the desired result.

SystemsModelSeriesConnect[sys2, sys3]

StateSpaceModel[{{{-2, 0}, {1, 0}}, {{0}, {1}}, {{0, 1}, {1, 0}}, {{0}, {1}}}, SamplingPeriod -> None, SystemsModelLabels -> None]

-
In sys1 if you remove StateSpaceModel and then wrap the final result in StateSpaceModel, you will get yet another i-o equivalent state-space represenation. The interal dynamics of these are different and they are sometimes very very important. – Suba Thomas Apr 12 '13 at 0:01

An answer based on the discussion above. For the system with inputs comprising of the deterministic feedback input $u(t)$ and the white noise input $w(t)$, and outputs $e(t)$ and $\dot{e}(t)$, a state-space representation would be

StateSpaceModel@TransferFunctionModel[{{1/s, 1/(s (s + 2))}, {1, 1/(s + 2)}}, s]

which gives StateSpaceModel[{{{0, 0, 0}, {0, 0, 1}, {0, 0, -2}}, {{1, 0}, {0, 0}, {0, 1}}, {{1, 1, 0}, {0, 0, 1}}, {{0, 0}, {1, 0}}}, SamplingPeriod ->None, SystemsModelLabels -> None]

You could then use this to design a feedback controller.

-
While I believe that you're right, can you please explain how you got to that conclusion? For reference, I'm working from pg. 177 of this report (on my dropbox). The original link is down for maintenance. – Gerrit Apr 11 '13 at 16:34
Thanks for the reference. That helps. State-space representations are not unique, so we could go through two different routes and end up with two different but input-output equivalent state-space representations. I will give detailed explanations in my next answer. I am leaving this answer as is, because it is also correct. – Suba Thomas Apr 11 '13 at 23:50
I expected there would be equivalent state-space representations, but wanted to know how I can use Mathematica to produce the same matrices as in the reference. Your other answer does this beautifully, thank you. – Gerrit Apr 12 '13 at 10:24


text:
# Mechanical Energy | conservation of Mechanical energy – derivation Class 11

SHARING INCREASES KNOWLEDGE

Here we will know what is mechanical energy of a system under study , when we can conserve the mechanical energy of system ? We will derive it.

## Mechanical Energy

### Introduction to mechanical energy

In classical mechanics , we deal with macroscopic systems , velocities and forces operating on them. Mechanical energy of a macroscopic system is the sum of energy of the system due to its motion and configuration of system i.e it’s the sum of potential energy and kinetic energy of a system . The principle of conservation of Mechanical energy States that the mechanical energy of an isolated system which is acted upon only by conservative forces remains constant. We’d already discussed the analysis of conservative force on an system.

Note

In situations which we deal in real life there are non conservative forces like friction are present but sometimes these are very negligible in comparison to the total energy and energy lost due to this will be very minute in amout , in such cases Energy conservation holds to a very good approximation.

When non conservative forces like friction acts on system then there is a loss in mechanical energy in the form of heat energy, sound energy which we’d observed in our daily life.

We’d also observed that if in a system friction acts then there is a rise in temperature of any system there is a relation  the mechanical energy lost equals  the change in the temperature of the system which was given discovered by James Prescott joule.

#### Kinetic Energy

Kinetic energy of a object is the energy due to motion of a object and the kinetic energy of a system is the sum of the kinetic energies of individual objects in motion in the system. Because energy is the quantity having magnitude and there is no meaning of direction of energy as we say how much energy a body contains not in which direction energy is in body, hence it’s a scalar quantity.

Qualitatively, the work done by the total forces equals the energy gained by the object and this energy is kinetic energy it comes out to be equal to
[Latexpage]
\begin{align*}
K = \frac{1}{2}mv^2
\end{align*}
Where v is the speed of the all object. Must see the derivation of kinetic energy.

#### Potential energy

If a system is being acted upon by conservative forces then there is energy defined due to configuration of system as potential energy , corresponding to each conservative force potential energy is defined seperately. Must see how potential energy is defined.

## Principle of Conservation of Mechanical energy

The principle of conservation of Mechanical energy States that

the total mechanical energy of an isolated system having no external forces and all internal forces are conservative forces , remains constant .

Mechanical energy is sum of kinetic energy and potential energy i.e.
\begin{align*}
E_{mechanical} = K.E + P.E.
\end{align*}
This sum of potential energy and kinetic energy remains constant individually potential energy and kinetic energy can change but the summation of this remains constant.

### Derivation of conservation of Mechanical energy

#### Basic Qualitative derivation

We know from Work-Energy theorem that the work done by total forces whether internal or external forces equals the change in kinetic energy of system.
\begin{align*}
W_{total forces} = \Delta K.E
\end{align*}
$$\text{forces classified as internal and external}$$
\begin{align*}
W_{internal} + W_{external} = \Delta K.E
\end{align*}
Internal forces classified as conservative and non conservative.
\begin{align*}
W_{C} + W_{N.C.} + W_{ext} = \Delta K.E
\end{align*}
$$\text{if}$$
\begin{align*}
W_{N.C} = 0 , W_{ext} = 0
\end{align*}

$$\text{then}$$
\begin{align*}
W_{C} = \Delta K.E
\end{align*}
$$\text{also we know}$$
\begin{align*}
W_{C} = -\Delta U \end{align*}

\begin{align*}
\implies -\Delta U = \Delta K.E
\end{align*}
\begin{align*}
– ( U_{final}- U_{initial} ) = K_{final} – K_{initial}
\end{align*}
\begin{align*}
U_{i} – U_{f} = k_{f} – K_{i}
\end{align*}
$$\text{rearranging terms}$$
\begin{align*}
\implies U_{i} + K_{i} = U_{f} + K_{f}
\end{align*}

The above expression states that the sum of initial kinetic energy and initial potential energy equals to the sum of final kinetic energy and final potential energy, means
That the initial mechanical energy equals to the final mechanical energy hence the mechanical energy is conserved when work done by non conservative forces and external forces equals zero.

#### Derivation Using Calculus

Let’s take a system acted upon by conservative forces only.
\begin{align}
|\vec{F}| = m|\vec{a}|
\\
F – ma = 0
\\
F – m\frac{dv}{dt}= 0
\end{align}
$$\text{multiply both sides by v }$$
\begin{align}
F.v – mv\frac{dv}{dt} = 0
\end{align}
$$\text{also we can see that }$$
\begin{align*}
\frac{dv^2}{dt} = \frac{dv^2}{dv} \times \frac{dv}{dt}
\\
\frac{dv^2}{dt} = 2v\frac{dv}{dt}
\end{align*}
\begin{align}
\implies v\frac{dv}{dt} = \frac{1}{2} \frac{dv^2}{dt}
\end{align}
From equation (2) and (3)
\begin{align*}
F.v – m\frac{1}{2} \frac{dv^2}{dt} = 0
\end{align*}
\begin{align}
F.v – \frac{d}{dt}\left(\frac{1}{2}mv^2\right) = 0
\end{align}
$$\text{since forces are conservative}$$
\begin{align}
\vec{F}.\vec{dx} = -dU
\\
\implies F = -\frac{dU}{dx}
\end{align}
Also
\begin{align}
v = \frac{dx}{dt}
\end{align}
Using equation (5) and (6) equation (4) becomes
\begin{align*}
-\frac{dU}{dx} \times \frac{dx}{dt} – \frac{d}{dt}\left(\frac{1}{2}mv^2\right) = 0
\\
– \left[ \frac{dU}{dt} +\frac{d}{dt}\left(\frac{1}{2}mv^2\right) \right] = 0
\end{align*}
\begin{align}
\implies \frac{d}{dt}\left(\frac{1}{2}mv^2 + U \right) = 0
\end{align}

The Quantity inside brackets in equation (7) is known as mechanical energy of a system and is the sum of kinetic energy and potential energy. As the derivative of Mechanical energy w.r.t time is zero this implies that the mechanical energy isn’t changing w.r.t time, hence it’s conserved and constant, provided non conservative forces and external forces doesn’t work on system as stated earlier while doing derivation.

Equation (7) can also be seen as a derivation for kinetic energy formula since we derived it without using the concept of kinetic energy.

SHARING INCREASES KNOWLEDGE


text:
# scale¶

## Purpose¶

Fixes the scaling for subsequent graphs. The axes endpoints and increments are computed as a best guess based on the data passed to it.

Note

This function is for use with the deprecated PQG graphics.

pgraph

## Format¶

scale(x, y)
Parameters
• x (matrix) – the x-axis data.

• y (matrix) – the y-axis data.

## Remarks¶

x and y must each have at least 2 elements. Only the minimum and maximum values are necessary.

This routine fixes the scaling for all subsequent graphs until graphset is called. This also clears xtics and ytics whenever it is called.

If either of the arguments is a scalar missing, the main graphics function will set the scaling for that axis using the actual data.

If an argument has 2 elements, the first will be used for the minimum and the last will be used for the maximum.

If an argument has 2 elements, and contains a missing value, that end of the axis will be scaled from the data by the main graphics function.

If you want direct control over the axes endpoints and tick marks, use xtics or ytics. If xtics or ytics have been called after scale, they will override scale.

pscale.src


text:
# plugins.aea-test-autonomy.aea_test_autonomy.base_test_classes.agents

End2end tests base class.

## RoundChecks Objects

@dataclass
class RoundChecks()

Class for the necessary checks of a round during the tests.

name: is the name of the round for which the checks should be performed. event: is the name of the event that is considered as successful. n_periods: is the number of periods this event should appear for the check to be considered successful.

## BaseTestEnd2End Objects

@pytest.mark.e2e

@pytest.mark.integration

Base class for end-to-end tests of agents with a skill extending the abstract_abci_round skill.

The setup test function of this class will configure a set of 'n' agents with the configured (agent_package) agent, and a Tendermint network of 'n' nodes, one for each agent.

Test subclasses must set agent_package, wait_to_finish and check_strings.

#### set_config

@classmethod
def set_config(cls, dotted_path: str, value: Any, type_: Optional[str] = None, aev: bool = True) -> Result

Set config value.

#### prepare

def prepare(nb_nodes: int) -> None

Set up the agents.

#### prepare_and_launch

def prepare_and_launch(nb_nodes: int) -> None

Prepare and launch the agents.

#### terminate_processes

def terminate_processes() -> None

Terminate processes

#### missing_from_output

@classmethod
def missing_from_output(cls, happy_path: Tuple[RoundChecks, ...] = (), strict_check_strings: Tuple[str, ...] = (), period: int = 1, is_terminating: bool = True, **kwargs: Any, ,) -> Tuple[List[str], List[str]]

Check if strings are present in process output.

Read process stdout in thread and terminate when all strings are present or timeout expired.

Arguments:

• happy_path: the happy path of the testing FSM.
• strict_check_strings: tuple of strings expected to appear in output as is.
• period: period of checking.
• is_terminating: whether the agents are terminated if any of the check strings do not appear in the logs.
• kwargs: the kwargs of the overridden method.

Returns:

tuple with two lists of missed strings, the strict and the round respectively.

#### check_aea_messages

def check_aea_messages() -> None

Check that each AEA prints these messages.

First failing check will cause assertion error and test tear down.

## BaseTestEnd2EndExecution Objects

class BaseTestEnd2EndExecution(BaseTestEnd2End)

Test that an agent that is launched later can synchronize with the rest of the network

• each agent starts, and sets up the ABCI connection, which in turn spawns both an ABCI server and a local Tendermint node (using the configuration folders we set up previously). The Tendermint node is unique for each agent
• when we will stop one agent, also the ABCI server created by the ABCI connection will stop, and in turn the Tendermint node will stop. In particular, it does not keep polling the endpoint until it is up again, it just stops.
• when we will restart the previously stopped agent, the ABCI connection will set up again both the server and the Tendermint node. The node will automatically connect to the rest of the Tendermint network, loads the entire blockchain bulit so far by the others, and starts sending ABCI requests to the agent (begin_block; deliver_tx*; end_block), plus other auxiliary requests like info , flush etc. The agent which is already processing incoming messages, forwards the ABCI requests to the ABCIHandler, which produces ABCI responses that are forwarded again via the ABCI connection such that the Tendermint node can receive the responses

#### check

def check() -> None

Check pre-conditions of the test

#### test_run

def test_run(nb_nodes: int) -> None

Run the test.


text:
# Lattice problem

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector space (often ${\displaystyle \mathbb {Q} ^{n}}$) or free modules (often ${\displaystyle \mathbb {Z} ^{n}}$) are generally considered.

For all the problems below, assume that we are given (in addition to other more specific inputs) a basis for the vector space V and a norm N. The norm usually considered is the Euclidean norm L2. However, other norms (such as Lp) are also considered and show up in a variety of results.[1] Let ${\displaystyle \lambda (L)}$ denote the length of the shortest non-zero vector in the lattice L, that is,

${\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}.}$

## Shortest vector problem (SVP)

This is an illustration of the shortest vector problem (basis vectors in blue, shortest vector in red).

In the SVP, a basis of a vector space V and a norm N (often L2) are given for a lattice L and one must find the shortest non-zero vector in V, as measured by N, in L. In other words, the algorithm should output a non-zero vector v such that ${\displaystyle N(v)=\lambda (L)}$.

In the γ-approximation version SVPγ, one must find a non-zero lattice vector of length at most ${\displaystyle \gamma \cdot \lambda (L)}$ for given ${\displaystyle \gamma \geq 1}$.

### Hardness results

The exact version of the problem is only known to be NP-hard for randomized reductions.[2][3]

By contrast, the corresponding problem with respect to the uniform norm is known to be NP-hard.[4]

### Algorithms for the Euclidean norm

To solve the exact version of the SVP under the Euclidean norm, several different approaches are known, which can be split into two classes: algorithms requiring superexponential time (${\displaystyle 2^{\omega (n)}}$) and ${\displaystyle \operatorname {poly} (n)}$ memory, and algorithms requiring both exponential time and space (${\displaystyle 2^{\Theta (n)}}$) in the lattice dimension. The former class of algorithms most notably includes lattice enumeration[5][6][7] and random sampling reduction,[8][9] while the latter includes lattice sieving,[10][11][12] computing the Voronoi cell of the lattice,[13][14] and discrete Gaussian sampling.[15] An open problem is whether algorithms for solving exact SVP exist running in single exponential time (${\displaystyle 2^{O(n)}}$) and requiring memory scaling polynomially in the lattice dimension.[16]

To solve the γ-approximation version SVPγ for ${\displaystyle \gamma >1}$ for the Euclidean norm, the best known approaches are based on using lattice basis reduction. For large ${\displaystyle \gamma =2^{\Omega (n)}}$, the Lenstra–Lenstra–Lovász (LLL) algorithm can find a solution in time polynomial in the lattice dimension. For smaller values ${\displaystyle \gamma }$, the Block Korkine-Zolotarev algorithm (BKZ)[17][18][19] is commonly used, where the input to the algorithm (the blocksize ${\displaystyle \beta }$) determines the time complexity and output quality: for large approximation factors ${\displaystyle \gamma }$, a small block size ${\displaystyle \beta }$ suffices, and the algorithm terminates quickly. For small ${\displaystyle \gamma }$, larger ${\displaystyle \beta }$ are needed to find sufficiently short lattice vectors, and the algorithm takes longer to find a solution. The BKZ algorithm internally uses an exact SVP algorithm as a subroutine (running in lattices of dimension at most ${\displaystyle \beta }$), and its overall complexity is closely related to the costs of these SVP calls in dimension ${\displaystyle \beta }$.

## GapSVP

The problem GapSVPβ consists of distinguishing between the instances of SVP in which the length of the shortest vector is at most ${\displaystyle 1}$ or larger than ${\displaystyle \beta }$, where ${\displaystyle \beta }$ can be a fixed function of the dimension of the lattice ${\displaystyle n}$. Given a basis for the lattice, the algorithm must decide whether ${\displaystyle \lambda (L)\leq 1}$ or ${\displaystyle \lambda (L)>\beta }$. Like other promise problems, the algorithm is allowed to err on all other cases.

Yet another version of the problem is GapSVPζ, γ for some functions ${\displaystyle \zeta ,\gamma }$. The input to the algorithm is a basis ${\displaystyle B}$ and a number ${\displaystyle d}$. It is assured that all the vectors in the Gram–Schmidt orthogonalization are of length at least 1, and that ${\displaystyle \lambda (L(B))\leq \zeta (n)}$ and that ${\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}$ where ${\displaystyle n}$ is the dimension. The algorithm must accept if ${\displaystyle \lambda (L(B))\leq d}$, and reject if ${\displaystyle \lambda (L(B))\geq \gamma (n).d}$. For large ${\displaystyle \zeta }$ (i.e. ${\displaystyle \zeta (n)>2^{n/2}}$), the problem is equivalent to GapSVPγ because[20] a preprocessing done using the LLL algorithm makes the second condition (and hence, ${\displaystyle \zeta }$) redundant.

## Closest vector problem (CVP)

This is an illustration of the closest vector problem (basis vectors in blue, external vector in green, closest vector in red).

In CVP, a basis of a vector space V and a metric M (often L2) are given for a lattice L, as well as a vector v in V but not necessarily in L. It is desired to find the vector in L closest to v (as measured by M). In the ${\displaystyle \gamma }$-approximation version CVPγ, one must find a lattice vector at distance at most ${\displaystyle \gamma }$.

### Relationship with SVP

The closest vector problem is a generalization of the shortest vector problem. It is easy to show that given an oracle for CVPγ (defined below), one can solve SVPγ by making some queries to the oracle.[21] The naive method to find the shortest vector by calling the CVPγ oracle to find the closest vector to 0 does not work because 0 is itself a lattice vector and the algorithm could potentially output 0.

The reduction from SVPγ to CVPγ is as follows: Suppose that the input to the SVPγ is the basis for lattice ${\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}$. Consider the basis ${\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}$ and let ${\displaystyle x_{i}}$ be the vector returned by CVPγ(Bi, bi). The claim is that the shortest vector in the set ${\displaystyle \{x_{i}-b_{i}\}}$ is the shortest vector in the given lattice.

### Hardness results

Goldreich et al. showed that any hardness of SVP implies the same hardness for CVP.[22] Using PCP tools, Arora et al. showed that CVP is hard to approximate within factor ${\displaystyle 2^{\log ^{1-\epsilon }(n)}}$ unless ${\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}$.[23] Dinur et al. strengthened this by giving a NP-hardness result with ${\displaystyle \epsilon =(\log \log n)^{c}}$ for ${\displaystyle c<1/2}$.[24]

### Sphere decoding

Algorithms for CVP, especially the Fincke and Pohst variant,[6] have been used for data detection in multiple-input multiple-output (MIMO) wireless communication systems (for coded and uncoded signals).[25][13] In this context it is called sphere decoding due to the radius used internal to many CVP solutions.[26]

It has been applied in the field of the integer ambiguity resolution of carrier-phase GNSS (GPS).[27] It is called LAMBDA method in that field. In the same field, the general CVP problem is referred to as Integer Least Squares.

## GapCVP

This problem is similar to the GapSVP problem. For GapSVPβ, the input consists of a lattice basis and a vector ${\displaystyle v}$ and the algorithm must answer whether one of the following holds:

• there is a lattice vector such that the distance between it and ${\displaystyle v}$ is at most 1.
• every lattice vector is at a distance greater than ${\displaystyle \beta }$ away from ${\displaystyle v}$.

The opposite condition is that the closest lattice vector is at a distance ${\displaystyle 1<\lambda (L)\leq \beta }$, hence the name GapCVP.

### Known results

The problem is trivially contained in NP for any approximation factor.

Schnorr, in 1987, showed that deterministic polynomial time algorithms can solve the problem for ${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}$.[28] Ajtai et al. showed that probabilistic algorithms can achieve a slightly better approximation factor of ${\displaystyle \beta =2^{O(n\log \log n/\log n)}}$.[10]

In 1993, Banaszczyk showed that GapCVPn is in ${\displaystyle {\mathsf {NP\cap coNP}}}$.[29] In 2000, Goldreich and Goldwasser showed that ${\displaystyle \beta ={\sqrt {n/\log n}}}$ puts the problem in both NP and coAM.[30] In 2005, Aharonov and Regev showed that for some constant ${\displaystyle c}$, the problem with ${\displaystyle \beta =c{\sqrt {n}}}$ is in ${\displaystyle {\mathsf {NP\cap coNP}}}$.[31]

For lower bounds, Dinur et al. showed in 1998 that the problem is NP-hard for ${\displaystyle \beta =n^{o(1/\log {\log {n}})}}$.[32]

## Shortest independent vectors problem (SIVP)

Given a lattice L of dimension n, the algorithm must output n linearly independent ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ so that ${\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}$ where the right hand side considers all bases ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$ of the lattice.

In the ${\displaystyle \gamma }$-approximate version, given a lattice L with dimension n, find n linearly independent vectors ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ of length ${\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}$, where ${\displaystyle \lambda _{n}(L)}$ is the ${\displaystyle n}$'th successive minimum of ${\displaystyle L}$.

## Bounded distance decoding

This problem is similar to CVP. Given a vector such that its distance from the lattice is at most ${\displaystyle \lambda (L)/2}$, the algorithm must output the closest lattice vector to it.

Given a basis for the lattice, the algorithm must find the largest distance (or in some versions, its approximation) from any vector to the lattice.

## Shortest basis problem

Many problems become easier if the input basis consists of short vectors. An algorithm that solves the Shortest Basis Problem (SBP) must, given a lattice basis ${\displaystyle B}$, output an equivalent basis ${\displaystyle B'}$ such that the length of the longest vector in ${\displaystyle B'}$ is as short as possible.

The approximation version SBPγ problem consist of finding a basis whose longest vector is at most ${\displaystyle \gamma }$ times longer than the longest vector in the shortest basis.

## Use in cryptography

Average case hardness of problems forms a basis for proofs-of-security for most cryptographic schemes. However, experimental evidence suggests that most NP-hard problems lack this property: they are probably only worst case hard. Many lattice problems have been conjectured or proven to be average-case hard, making them an attractive class of problems to base cryptographic schemes on. Moreover, worst-case hardness of some lattice problems have been used to create secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers.

The above lattice problems are easy to solve if the algorithm is provided with a "good" basis. Lattice reduction algorithms aim, given a basis for a lattice, to output a new basis consisting of relatively short, nearly orthogonal vectors. The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) was an early efficient algorithm for this problem which could output an almost reduced lattice basis in polynomial time.[33] This algorithm and its further refinements were used to break several cryptographic schemes, establishing its status as a very important tool in cryptanalysis. The success of LLL on experimental data led to a belief that lattice reduction might be an easy problem in practice. However, this belief was challenged when in the late 1990s, several new results on the hardness of lattice problems were obtained, starting with the result of Ajtai.[2]

In his seminal papers, Ajtai showed that the SVP problem was NP-hard and discovered some connections between the worst-case complexity and average-case complexity of some lattice problems.[2][3] Building on these results, Ajtai and Dwork created a public-key cryptosystem whose security could be proven using only the worst case hardness of a certain version of SVP,[34] thus making it the first result to have used worst-case hardness to create secure systems.[35]

## References

1. ^ Khot, Subhash (2005). "Hardness of approximating the shortest vector problem in lattices". J. ACM. 52 (5): 789–808. doi:10.1145/1089023.1089027. S2CID 13438130.
2. ^ a b c Ajtai, M. (1996). "Generating hard instances of lattice problems". Proceedings of the Twenty-Eighth annual ACM symposium on Theory of computing. Philadelphia, Pennsylvania, United States: ACM. pp. 99–108. doi:10.1145/237814.237838. ISBN 9780897917858. S2CID 6864824.
3. ^ a b Ajtai, Miklós (1998). "The shortest vector problem in L2 is NP-hard for randomized reductions". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 10–19. doi:10.1145/276698.276705. ISBN 9780897919623. S2CID 4503998.
4. ^ van Emde Boas, Peter (1981). "Another NP-complete problem and the complexity of computing short vectors in a lattice". Technical Report 8104. University of Amsterdam, Department of Mathematics, Netherlands.
5. ^ Kannan, Ravi (1983). "Improved Algorithms for Integer Programming and Related Lattice Problems". Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: ACM. pp. 193–206. doi:10.1145/800061.808749. ISBN 978-0897910996. S2CID 18181112.
6. ^ a b Fincke, U.; Pohst, M. (1985). "Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis". Math. Comp. 44 (170): 463–471. doi:10.1090/S0025-5718-1985-0777278-8.
7. ^ Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded (2010-05-30). Lattice Enumeration Using Extreme Pruning. Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. Springer, Berlin, Heidelberg. pp. 257–278. doi:10.1007/978-3-642-13190-5_13. ISBN 978-3-642-13189-9. S2CID 1938519.
8. ^ Schnorr, Claus Peter (2003-02-27). "Lattice Reduction by Random Sampling and Birthday Methods". Stacs 2003. Lecture Notes in Computer Science. Vol. 2607. Springer, Berlin, Heidelberg. pp. 145–156. CiteSeerX 10.1.1.137.4293. doi:10.1007/3-540-36494-3_14. ISBN 978-3540364948. {{cite book}}: Missing or empty |title= (help)
9. ^ Aono, Yoshinori; Nguyen, Phong Q. (2017-04-30). Random Sampling Revisited: Lattice Enumeration with Discrete Pruning (PDF). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10211. Springer, Cham. pp. 65–102. doi:10.1007/978-3-319-56614-6_3. ISBN 978-3-319-56613-9. S2CID 39082279.
10. ^ a b Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "A sieve algorithm for the shortest lattice vector problem". Proceedings of the thirty-third annual ACM symposium on Theory of computing. Hersonissos, Greece: ACM. pp. 601–610. doi:10.1145/380752.380857. ISBN 1581133499. S2CID 14982298.
11. ^ Micciancio, Daniele; Voulgaris, Panagiotis (2010). Faster Exponential Time Algorithms for the Shortest Vector Problem. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '10. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 1468–1480. doi:10.1137/1.9781611973075.119. ISBN 9780898716986. S2CID 90084.
12. ^ Becker, A.; Ducas, L.; Gama, N.; Laarhoven, T. (2015-12-21). "New directions in nearest neighbor searching with applications to lattice sieving". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings. Society for Industrial and Applied Mathematics. pp. 10–24. doi:10.1137/1.9781611974331.ch2. ISBN 978-1-61197-433-1.
13. ^ a b Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Closest Point Search in Lattices". IEEE Trans. Inf. Theory. 48 (8): 2201–2214. doi:10.1109/TIT.2002.800499.
14. ^ Micciancio, Daniele; Voulgaris, Panagiotis (2010). A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations. Proceedings of the Forty-Second ACM Symposium on Theory of Computing. STOC '10. New York, NY, USA: ACM. pp. 351–358. CiteSeerX 10.1.1.705.3304. doi:10.1145/1806689.1806739. ISBN 9781450300506. S2CID 2449948.
15. ^ Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). Solving the Shortest Vector Problem in 2N Time Using Discrete Gaussian Sampling: Extended Abstract. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC '15. New York, NY, USA: ACM. pp. 733–742. doi:10.1145/2746539.2746606. ISBN 9781450335362. S2CID 10214330.
16. ^ Micciancio, Daniele (2017-07-01). "Lattice Cryptography – Shortest Vector Problem".
17. ^ Schnorr, C. P. (1987-01-01). "A hierarchy of polynomial time lattice basis reduction algorithms". Theoretical Computer Science. 53 (2): 201–224. doi:10.1016/0304-3975(87)90064-8.
18. ^ Schnorr, C. P.; Euchner, M. (1994-08-01). "Lattice basis reduction: Improved practical algorithms and solving subset sum problems" (PDF). Mathematical Programming. 66 (1–3): 181–199. doi:10.1007/bf01581144. ISSN 0025-5610. S2CID 15386054.
19. ^ Chen, Yuanmi; Nguyen, Phong Q. (2011-12-04). BKZ 2.0: Better Lattice Security Estimates. Advances in Cryptology – ASIACRYPT 2011. Lecture Notes in Computer Science. Vol. 7073. Springer, Berlin, Heidelberg. pp. 1–20. doi:10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
20. ^ Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Proceedings of the 41st annual ACM symposium on Theory of Computing. Bethesda, MD, USA: ACM. pp. 333–342. doi:10.1145/1536414.1536461. ISBN 9781605585062. S2CID 1864880.
21. ^ Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. Springer.
22. ^ Goldreich, O.; et al. (1999). "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors". Inf. Process. Lett. 71 (2): 55–61. doi:10.1016/S0020-0190(99)00083-6.
23. ^ Arora, Sanjeev; et al. (1997). "The hardness of approximate optima in lattices, codes, and systems of linear equations". Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. J. Comput. Syst. Sci. Vol. 54. pp. 317–331. doi:10.1109/SFCS.1993.366815. ISBN 978-0-8186-4370-5. S2CID 44988406.
24. ^ Dinur, I.; et al. (2003). "Approximating CVP to Within Almost-Polynomial Factors is NP-Hard". Combinatorica. 23 (2): 205–243. doi:10.1007/s00493-003-0019-y. S2CID 45754954.
25. ^ Biglieri, E.; Calderbank, R.; Constantinides, Anthony G.; Goldsmith, A.; Paulraj, A.; Poor, H. V. (2007). MIMO Wireless Communications. Cambridge: Cambridge U. P.
26. ^ Wang, Ping; Le-Ngoc, Tho (2011). "A List Sphere Decoding Algorithm with Improved Radius Setting Strategies". Wireless Personal Communications. 61 (1): 189–200. doi:10.1007/s11277-010-0018-4. S2CID 30919872.
27. ^ Hassibi, A.; Boyd, S. (1998). "Integer Parameter Estimation in Linear Models with Applications to GPS". IEEE Trans. Sig. Proc. 46 (11): 2938–2952. Bibcode:1998ITSP...46.2938H. CiteSeerX 10.1.1.114.7246. doi:10.1109/78.726808.
28. ^ Schnorr, C. P. "Factoring integers and computing discrete logarithms via diophantine approximation". Advances in Cryptology: Proceedings of Eurocrypt '91.
29. ^ Banaszczyk, W. (1993). "New bounds in some transference theorems in the geometry of numbers". Math. Ann. 296 (1): 625–635. doi:10.1007/BF01445125. S2CID 13921988.
30. ^ Goldreich, Oded; Goldwasser, Shafi (1998). "On the limits of non-approximability of lattice problems". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 1–9. doi:10.1145/276698.276704. ISBN 0897919629. S2CID 3051993.
31. ^ Aharonov, Dorit; Oded Regev (2005). "Lattice problems in NP ${\displaystyle \cap }$ coNP". J. ACM. 52 (5): 749–765. CiteSeerX 10.1.1.205.3730. doi:10.1145/1089023.1089025. S2CID 1669286.
32. ^ Dinur, I.; Kindler, G.; Safra, S. (1998). "Approximating-CVP to within Almost-Polynomial Factors is NP-Hard". Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. p. 99. ISBN 978-0-8186-9172-0.
33. ^ Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients" (PDF). Math. Ann. 261 (4): 515–534. doi:10.1007/BF01457454. S2CID 5701340. Archived from the original (PDF) on 2011-07-17.
34. ^ Ajtai, Miklós; Dwork, Cynthia (1997). "A public-key cryptosystem with worst-case/average-case equivalence". Proceedings of the Twenty-Ninth annual ACM symposium on Theory of computing. El Paso, Texas, United States: ACM. pp. 284–293. doi:10.1145/258533.258604. ISBN 0897918886. S2CID 9918417.
35. ^ Cai, Jin-Yi (2000). "The Complexity of Some Lattice Problems". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1838. pp. 1–32. doi:10.1007/10722028_1. ISBN 978-3-540-67695-9.