text:
# Fast Deterministic Fully Dynamic Distance Approximation

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular we obtain improved dynamic algorithms that, given an unweighted and undirected graph G=(V,E) undergoing edge insertions and deletions, and a parameter 0 < ϵ≤ 1, maintain (1+ϵ)-approximations of the st distance of a single pair of nodes, the distances from a single source to all nodes ("SSSP"), the distances from multiple sources to all nodes ("MSSP”), or the distances between all nodes ("APSP"). Our main result is a deterministic algorithm for maintaining (1+ϵ)-approximate single-source distances with worst-case update time O(n^1.529) (for the current best known bound on the matrix multiplication coefficient ω). This matches a conditional lower bound by [BNS, FOCS 2019]. We further show that we can go beyond this SSSP bound for the problem of maintaining approximate st distances by providing a deterministic algorithm with worst-case update time O(n^1.447). This even improves upon the fastest known randomized algorithm for this problem. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining (1+ϵ, β)-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improvements for randomized approximate diameter maintenance.

## Authors

• 13 publications
• 9 publications
• 8 publications
09/24/2019

### Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time

Consider the following distance query for an n-node graph G undergoing e...
08/24/2021

### Deterministic Dynamic Matching In Worst-Case Update Time

We present deterministic algorithms for maintaining a (3/2 + ϵ) and (2 +...
09/17/2020

### Near-Optimal Decremental Approximate Multi-Source Shortest Paths

We provide new algorithms for maintaining approximate distances in a wei...
08/19/2021

### Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds

In their breakthrough ICALP'15 paper, Bernstein and Stein presented an a...
10/20/2020

### New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners

Maintaining and updating shortest paths information in a graph is a fund...
04/09/2018

### Counting Triangles under Updates in Worst-Case Optimal Time

We consider the problem of incrementally maintaining the triangle count ...
06/22/2021

### Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems

We consider the directed minimum weight cycle problem in the fully dynam...
##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

From the procedural point of view, an algorithm is a set of instructions that outputs the result of a computational task for a given input. This static viewpoint neglects that computation is often not a one-time task with input data in successive runs of the algorithm being very similar. The idea of dynamic graph algorithms is to explicitly model the situation that the input is constantly undergoing changes and the algorithm needs to adapt its output after each change to the input. This paradigm has been highly successfully applied to the domain of graph algorithms. The major goal in designing dynamic graph algorithms is to spend as little computation time as possible for processing each update to the input graph.

Deterministic algorithms avoid these two issues.

While these restrictions are not prohibitive in certain settings, they obstruct the general-purpose usage of dynamic algorithms as “black boxes”. Thus, the “gold standard” in the design of dynamic algorithms should be deterministic fully dynamic algorithms with worst-case update time bounds. To date, there is only a limited number of problems that admit such algorithms and additionally have almost optimal time bounds. To the best of our knowledge, this is the case only for -approximate maximum fractional matching and minimum vertex cover [BhattacharyaHN17], -edge coloring [BhattacharyaCHN18], -approximate densest subgraph [SawlaniW20], connectivity [ChuzhoyGLNPS20], minimum spanning tree [ChuzhoyGLNPS20], and edge connectivity [JinS21].

In this paper, we add an important problem to this list: -approximate single-source distances in unweighted, undirected graphs. More specifically, our main result is a deterministic fully dynamic algorithm that after each edge insertion or deletion outputs a -approximation of the distances from a given source node to all other vertices in worst-case update time222To simplify the presentation of running time bounds in the introductory part of this paper we assume that is a constant. We will later make them explicit in our theorem statements. Throughout this paper, we use -notation to suppress terms that are polylogarithmic in , the number of nodes of the graph. , or, more generally, time for any where denotes the matrix-multiplication exponent.333Two matrices can be multiplied in operations with [Williams12, Gall14, AlmanW21]. We write for the complexity of multiplying an by matrix [GallU18]. Note that our update time matches a conditional lower bound for this problem (up to subpolynomial factors) [BrandNS19]. We also match the randomized worst-case time bound for approximate single-source shortest paths in unweighted undirected graphs implicitly obtained by [BHGWW2021] against an oblivious adversary. Prior to our work, the fastest algorithm for maintaining approximate single-source distances against an adaptive adversary had an update time of , which applied to more general graphs [BrandN19].

We also give deterministic algorithms for maintaining -approximate distances from sources with update time , and thus all-pairs distances with update time . Note that this almost matches the trivial lower bounds of and , respectively, for explicit distance maintenance (up to subpolynomial factors). This further matches (up to subpolynomial factors) the randomized worst-case time bound for maintaining approximate all-pairs distances in unweighted undirected graphs obtained by [BrandN19] against an adaptive adversary.444For general graphs, [BrandN19] obtain an update time of . Our techniques also lead to improved fully-dynamic bounds for several other distance problems, such as - distance, near-additive emulators, and diameter approximation. See Section 1.1 for details of our results.

We believe that another virtue of our algorithms is that they are conceptually simpler with a more direct approach than prior works. In particular, our results follow from a combination of algebraic distance maintenance data structures and near-additive emulators. While the state-of-the-art algebraic data structures based on maintaining matrix inverses are rather involved, we use them only to optimize the -dependence in our running times. If we were fine with a slightly worse -dependence, then – since we only use the algebraic data structures to maintain relatively small distances – we could resort to the simpler and well-known path-counting approach for directed acyclic graphs (DAGs) that was introduced by King and Sagert [KingS02] and subsequently refined by Demetrescu and Italiano [DemetrescuI00] (see Appendix A for details on this approach). We believe that overall this results in a pretty accessible combination of algebraic and combinatorial approaches.

### 1.1 Our Results

In this section, we summarize our main results for deterministic fully dynamic distance computation (, SSSP, APSP, and MSSP supporting distance queries) and emulators. A summary of our algorithms for maintaining -approximate distances with their worst-case update time guarantees can be found in Table 1. In addition to these deterministic results, our techniques also give improved randomized solutions for diameter approximation, and subquadratic update-time -APSP distance oracles555By a “distance oracle”, we mean a data structure that supports fast queries. Our goal – unlike many static algorithms – is not optimizing the space of this data structure. with sublinear query time. We next discuss each of these results and compare them with related work. Throughout this paper we assume that we are given an unweighted graph with nodes and edges.

#### Optimal Deterministic (1+ϵ)-Sssp.

Our first result is a conditionally optimal deterministic algorithm for maintaining -single source distances. Formally we show the following.

###### Theorem 1.1.

Given an unweighted undirected graph and a single source , and , there is a deterministic fully-dynamic data structure for maintaining -distances from with

• [nosep]

• Preprocessing time of , where .

• Worst-case update time of for any . For current bounds on and the best choice of , this is .

This running time matches a conditional lower bound stated in [BrandNS19], meaning it is unlikely that an algorithm can improve our running time by any polynomial factor. More specifically, the lower bound states that no dynamic -approximate SSSP algorithm on unweighted undirected graphs can run in worst-case time per edge update for any constant . Prior to this work,666In general, when we state bounds from previous work we sometimes hide terms unless our dependence on is substantially different from those results. the fully-dynamic algorithms for single-source distances were randomized and either much slower with time per update [BrandN19] (albeit for more general classes of graphs), or only worked against an oblivious adversary implied by techniques of [BHGWW2021].777It is worth noting that the techniques in [BHGWW2021] are path reporting, while our deterministic SSSP algorithm is suitable for distance computation. It seems challenging to obtain path reporting deterministically. Note that, similar to our work, the techniques of [BHGWW2021] are also restricted to unweighted, undirected graphs. Additionally, we remove the superpolynomial dependence on in the update time inherent to the approach of [BHGWW2021].

#### Deterministic (1+ϵ)-st distances.

Next, we show that our techniques lead to a faster algorithm for maintaining distance from a fixed pair of nodes . Specifically, we give an algorithm for this problem with a worst-case update time smaller than the time required for single-source distances (based on the conditional lower bound).

###### Theorem 1.2.

Given an unweighted undirected graph and a pair of nodes and , there is a fully-dynamic data structure for maintaining -distances between and deterministically with

• [nosep]

• Preprocessing time of , where .

• Worst-case update time of for any parameter , which is for current .

When relaxing determinism to randomization against adaptive adversaries, the previously fastest fully-dynamic algorithms for -distances had update time [BrandNS19] and maintained the distance exactly for unweighted directed graphs.

Our algorithm improves upon this time bound and, unlike all previous work ([Sankowski05, BrandNS19, BrandN19, BHGWW2021]), is deterministic. Moreover, this bound has only a small gap to the conditional lower bound for -approximate dynamic -distances on unweighted undirected graphs, which for current is [BrandNS19].888The conditional lower bound states that no algorithm can run in time for any constant . Thus no algorithm using current fast matrix multiplication algorithms can beat time by a polynomial factor.

#### Sparse Emulators.

Our deterministic dynamic algorithms are based on several emulator constructions with various tradeoffs. We show here that we can also maintain more general emulators, which may be of independent interest. We start by defining -emulators and spanners.

###### Definition 1.3.

Given an input graph , an -emulator of is a graph (that is not necessarily a subgraph of and might be weighted) in which

 dG(u,v)≤dH(u,v)≤α⋅dH(u,v)+β

for all pairs of nodes .

If the graph above is a subgraph of then we call an -spanner of . Note that a spanner of an unweighted graph remains unweighted.

In this paper, we obtain the following result for maintaining near-additive emulators.

###### Lemma 1.4.

Given an unweighted, undirected graph , and , we can maintain a -emulator of with size , where deterministically with worst-case update time of . The preprocessing time of this algorithm is .

The static running time for constructing a -emulator, also called a near-additive emulator, with size is . For our applications in APSP and MSSP, we are interested in the special case where and the emulator has size .999In static settings there are somewhat more involved algorithms for near-additive emulators that lead to slightly better tradeoffs in specific parameter settings (e.g. see [EN2018]). For our applications in distance approximation the current simpler algorithms suffice. In this special case, our results can be compared to the -spanner construction of [BHGWW2021]. They provide a randomized algorithm against an oblivious adversary with worst-case update time of , whereas we give a deterministic algorithm with worst-case update time of . Hence we improve over [BHGWW2021] both in running time and by having a deterministic algorithm. We note however that [BHGWW2021] maintain a spanner, whereas we maintain an emulator.

#### (1+ϵ)-Mssp.

Another implication of our techniques is an an algorithm for -multi-source distances. In Section 3.6, we give an algorithm that combines our sparse emulator construction with the algebraic techniques to prove the following theorem.

###### Theorem 1.5.

Given an unweighted, undirected graph , and , and a fixed set of sources , we can maintain -approximate distances from deterministically with:

• Preprocessing time of .

• Worst-case update of .

Hence we can maintain distances from up to sources in almost (up to an factor) the same time as maintaining distances from a single-source.

#### Deterministic near-optimal (1+ϵ)-Apsp.

One implication of Theorem 1.5 (by simply setting ) is a deterministic fully-dynamic algorithm for maintaining all-pair-shortest path that nearly (up to an factor) matches the trivial lower bound of time per update for this problem. More formally,

###### Corollary 1.6.

Given an unweighted, undirected graph , and , we can maintain -all-pairs distances deterministically with:

• Preprocessing time of .

• Worst-case update time of .

It is worth mentioning that there is another (simpler) approach to obtain this bound that we will discuss in Section 3.7. The previous comparable bounds for this problem either used randomization [BrandN19] or have amortized bounds [DemetrescuI04, Thorup04].

Next we discuss two other implications of our multi-source data structure, which unlike our previous bound are randomized.

#### Diameter Approximation.

We can maintain a -approximation of the diameter in unweighted graphs by using our emulator to compute -MSSP algorithms for certain sets of size based on an algorithm by [RV13]. Formally we have,

###### Corollary 1.7.

Given an unweighted graph with diameter , and

, we can maintain an estimate

such that101010Note that the term is only relevant for graphs with very small diameter .:

 (2/3−ϵ)D−1/3≤^D≤(1+ϵ)D

with the following guarantees:

• Pre-processing time of .

• worst-case update time that holds with high probability against an adaptive adversary.

Previously the fastest fully-dynamic algorithm for this problem was by [BrandN19] with a worst-case update time of against an adaptive adversary. We get better bounds by combining our sparse emulator algorithms with the algorithm of [BrandN19]. The algorithm and the parameter setting for obtaining this bound is included in Appendix B.

#### APSP distance oracle with sub-quadratic update time.

Another implication of our dynamic -MSSP algorithm is improved bounds for maintaining a data structure with subquadratic update time that supports all-pair queries with a small polynomial query time. This type of data structure for undirected and unweighted graph was proposed by [RZ12] and also studied in [BrandN19]. We show that our improved -MSSP algorithm directly improves their update time.

###### Corollary 1.8.

Given an unweighted, undirected graph , and , we can maintain a data structure that supports all-pair -approximate distance queries with following guarantees:

• Preprocessing time: .

• Worst-case update time: .

• Query time: .

This result demonstrates that our techniques lead to improved bounds over [BrandN19] for a data structure explicitly designed for unweighted graphs. Their algorithm has an update time of with the same query time. While the analysis is similar to [BrandN19], we give a sketch of this algorithm in Appendix B.2 for completeness.

## 2 Technical Overview

In this section we give a high-level overview of our contributions based on the following outline: First, we give an algorithm for maintaining a deterministic -emulator. We then describe how the update time can be improved by maintaining a low-recourse hitting set. Then in Section 2.2, we give an overview of the algebraic techniques that, combined with our deterministic emulators, lead to a conditionally optimal time bound for -SSSP. Finally, we show that by maintaining sparser emulators with different guarantees, we can get improved bounds for - distances, multi-source distances, and APSP.

### 2.1 Dynamic Emulators via Low-Recourse Hitting Sets

#### Deterministic (1+ϵ,2)-emulator and (1+ϵ)-Sssp.

We start with a deterministic algorithm for maintaining a -emulator. This algorithm is inspired by a randomized algorithm (working against an oblivious adversary) used by [HKN2013] in the decremental setting, which in turn is based on the purely additive static construction of [DorHZ00]. Given an unweighted graph , we maintain an emulator with size as follows:

1. [nosep]

2. Let be a degree threshold. For any node where , add all the edges incident to to . These edges have weight .

3. Construct a hitting set of size , such that every node with degree at least , called a heavy node, has a neighbor in .

4. For any node , add an edge to all nodes within distance to . Set the weight of such an edge to .

It is easy to see that if we were interested in a randomized algorithm that only works against an oblivious adversary, we could simply construct a hitting set by uniformly sampling a fixed set of size  [UllmanY91]. We could then maintain the corresponding -bounded distances from this fixed set with a worst-case update time of , which matches the lower bound of [BrandNS19]. As we will discuss in Section 2.2, this could be done by using an algebraic data structure by [Sankowski05] for maintaining and then querying -bounded distances for all pairs in after each update. Note that the distance bound of in our algorithms leverage the power of algebraic distance maintenance data structures as their running times scale with the given distance bound. However, these ideas alone are not enough for obtaining an efficient deterministic algorithm.

Before explaining how to maintain both the hitting set and the corresponding distances deterministically, let us sketch the properties of this emulator and how it can be used for maintaining -SSSP. It is easy to see that has size : we add edges incident to low-degree nodes, and edges in . For the stretch analysis, consider any pair of nodes , and let be the shortest path between . We can divide into segments of equal length , an possibly one additional smaller segment. Consider one such segment . If all the nodes on this segment are low-degree, then we have included all the corresponding edges in the emulator. Otherwise there is a node that is adjacent to the first heavy node on this segment. We have , and thus in the third step of the algorithm we have added (weighted) an edge in the emulator. It is easy to see that the path going through either provides a multiplicative factor, or (for the one smaller segment) an additive term of .

Given a emulator, we can now maintain -SSSP by (i) using algebraic techniques to maintain -bounded distances from the source to all nodes in , and (ii) statically running Dijkstra’s algorithm on the emulator in time , and finally (iii) taking the minimum of the two distance values for each pair . We observe that if , then we are maintaining a correct estimate in step (i). Otherwise in step (ii) the combination of the multiplicative factor and the additive term, leads to an overall -approximate estimate.

#### Deterministic low-recourse hitting set.

As discussed, we can easily obtain a fixed hitting set using randomization, but we are interested in a deterministic algorithm. One natural approach for constructing the hitting set deterministically is as follows: For each node with degree at least , consider a set of exactly neighbors of . After each update we can statically and deterministically compute an -approximation to this instance of the hitting set problem. We use a simple greedy algorithm that proceeds by sequentially adding nodes to that hit the maximum number of uncovered heavy nodes.

This can be done in time and gives us a hitting set of size as well. This time is within our desired update-time bound, but we also need to maintain -bounded distances from elements in this hitting set. As we will see in Section 2.2, by using the naive approach of recomputing a hitting set in each update and employing off-the-shelf algebraic data structures (e.g. by [BrandN19]) for maintaining bounded distances in , we would get an update time of for current . However there is a conditional lower bound of for this problem [BrandNS19], and our goal is to design an algorithm that matches this bound.

To get a better running time, we change our construction and the algebraic data structure to use a low-recourse hitting set instead to ensure that in each update only a constant number of nodes are added to the set. More formally in Section 3.3 we will prove the following lemma:

###### Lemma 2.1.

Given a graph undergoing edge insertions and edge deletions and a degree threshold , call a node heavy if it has degree larger than . We can deterministically maintain a hitting set of size with worse-case recourse and worst-case time per update such that all heavy nodes have a neighbor in .

At a high-level our dynamic low recourse hitting set proceeds as follows: we start by using the static greedy hitting set algorithm. We then note that each update (insertion or deletion) can make at most heavy nodes uncovered. We can keep on adding such nodes to our hitting set until the size of the hitting set doubles, and then reset the construction. This leads to an amortized constant recourse bound, and we can then use a standard technique to turn this into a worst case constant recourse bound.

Note that this hitting set problem can be seen as a set cover instance of size , where each set consists of exactly neighbor of a heavy node. Dynamic set cover approximation has received significant attention in recent years (e.g. [abboud2019, BHN2019, gupta2017, BHNW2021]). The most relevant result to our setting is a fully-dynamic -approximate set cover algorithm by [gupta2017]). However we cannot use their result directly, as they state that their polynomial time algorithm only leads to constant amortized recourse, and their update-time guarantees are also only amortized111111Of course the goal in [gupta2017] is a generic set cover approximation algorithm, which is why they are not comparable to our specialized algorithm. Also, the other set cover algorithms cited lead to approximation ratio dependent on , that can be as large as in our case.. Here we use a simple approach that utilizes the properties of our hitting set instance, which is enough to get worst-case recourse bounds.

We next move on to explaining how to design algebraic data structures that maintain the distances required for this algorithm more efficiently.

### 2.2 Dynamic Pairwise Bounded Distances via Matrix Inverse

As outlined before, for obtaining our desired bounds, we need to efficiently maintain bounded pairwise distances for some sets , where the sets and change over updates. We additionally use the fact that even though these sets change, they do not change substantially after each update because of our low-recourse hitting sets.

Previous algebraic distance algorithms only considered maintaining pairwise distances for (a) some fixed sets , that do not change [Sankowski05, BrandNS19, BHGWW2021], or (b) a completely new sets , in each iteration [BrandN19]. Case (a) can be used if we randomly sample a hitting set and keeping this set fixed over the sequence of edge updates. This will only useful for randomized algorithms against oblivious adversaries. Case (b) can be used when constructing a new hitting set from scratch after each update, which works against adaptive adversaries. However, querying the distance for a new set in each update turns out to be slower and does not allow us to match the conditional lower bound for approximate SSSP. More specifically, the complexities in these case are as follows:

###### Lemma 2.2 ([Sankowski05, BrandNS19]).

There exist randomized dynamic algorithms that, after preprocessing a given unweighted directed121212The algebraic algorithms for -bounded distances all work on directed graphs. Restrictions to undirected graphs in our main results stem from the emulator arguments that extend the results to unbounded distances. graph and a parameter in time, supports edge-updates to in time.

The algorithm supports queries that return for any given the pairwise -bounded distances in time where such that , . [BrandNS19]

The algorithm can also support maintaining the pairwise distances for some fixed sets by increasing the update time by . [Sankowski05]

In our SSSP algorithm, as discussed in Section 2.1, we have , . For the current , this leads to a query time of (by choosing ), while the conditional lower bound for SSSP is .

We improve the query time for the case where sets are slowly changing with each update. This allows us to reach the conditional lower bound. We do this by reducing dynamic -bounded pairwise distances for slowly changing sets to existing dynamic matrix inverse algorithms.

We start by explaining the existing reduction from dynamic distances to matrix inverse. Afterward, we explain how to use this reduction for maintaining pairwise distances.

#### Reducing distances to matrix inverse.

Previous dynamic algebraic algorithms that maintain distances work by reducing the task to the so called “dynamic matrix inverse” problem [Sankowski05, BrandNS19, BrandN19, BrandS19, GuR21]. Here the dynamic algorithms are given some matrix and must support updates that change any entry of and queries that return any entry of . Such dynamic matrix inverse algorithms can be used to maintain distances in dynamic graphs via the following reduction: Given an adjacency matrix , note that is the number of (not necessarily simple) paths from to of length . Specifically, the smallest with is the distance from to .

We can maintain these powers of dynamically via the following reduction. For any , we write for the ring of polynomials over (with variable ) modulo , i.e. polynomials over where we truncate all monomials of degree . We now consider matrices whose entries are from .

Let be the matrix with on the diagonal and for all edges . Note that . To see this, consider

 (I−XA)⋅h−1∑k=0XkAk=h−1∑k=0XkAk−h∑k=1XkAk=I

by because of the entrywise mod . Thus a dynamic algorithm that maintains the inverse of matrix is able to maintain distances of length in dynamic graphs. The task of maintaining pairwise distances for thus reduces to the task of maintaining the submatrix for some dynamic matrix .131313Throughout, we use for sets and matrix to denote the submatrix consisting of rows with index in and columns with index in .

#### Submatrix maintenance.

In this work, we show how to extend the previous algorithms to efficiently maintain a submatrix of an inverse for some dynamic matrix . Obviously, any dynamic matrix algorithm can maintain such a submatrix by just querying all entries after each change to , but this would not be fast enough for our algorithm to match the conditional lower bounds. We now show a blackbox reduction that is able to maintain the submatrix more efficiently. For simplicity assume is a matrix over some field .141414The reduction does extend to matrices of form (as required to maintain distances ), but for simplicity we just consider instead. Consider an entry update where we add to some entry , i.e. we add some to . The Sherman-Morrison identity [ShermanM50] states

 (M+eie⊤jc)−1=M−1−M−1eice⊤jM−11+ce⊤jM−1ei.

Note that and are just th column and th row of . So to obtain the submatrix of the new inverse we just need to compute

 ((M+eiejc)−1)S,T=M−1S,T−M−1S,icM−1j,T1+cM−1i,j.

This allows us to maintain throughout all updates by just querying and from some dynamic matrix algorithm instead of the entire submatrix. Updates to set (or ) are handled by querying the missing row (or column), i.e. adding some to just requires us to query in order to know the new submatrix . In Section 4, we use these ideas to formally prove the following results by reducing to existing dynamic matrix inverse algorithms from [Sankowski04, Sankowski05, BrandNS19]:

###### Lemma 2.3.

There exist two deterministic dynamic algorithms that, after preprocessing a given unweighted directed graph and sets , support edge-updates to and set-updates to and (i.e. adding or removing a node to or ). After each edge-update the algorithms return the -bounded pairwise distances of in .

The first algorithm has preprocessing time , edge-update time and set-update time for updating and for updating .

The second algorithm has preprocessing time , edge-update time and set-update time for updating and for updating .

For both algorithms, all update times are worst-case.

The complexity dependence stems from determinism. With a standard Monte-Carlo randomization technique (see e.g. [Sankowski05]), one could improve the complexity of Lemma 2.3 by an factor, which is comparable to the previous randomized bounds stated in Lemma 2.2.

### 2.3 Sparsification for Approximate st distances, APSP, MSSP.

#### Deterministic (1+ϵ,4)-emulator for st distances.

Next, we outline how we can improve the update time to in case of -distances. For this purpose, we construct a -emulator with size , which again is inspired by the purely additive construction of [DorHZ00] in the static setting, by making the following modifications to the algorithm described in Section 2.1 above: We set the degree threshold to . More importantly, rather than adding edges corresponding to bounded distances in , we only add pairwise edges between nodes (with bounded distance) in . This has two advantages: First, we need to run Dijkstra on a sparser graph. Second, the algebraic steps can be performed much faster when we only need to maintain pairwise distances between two sets of sublinear size (here , rather than from a set of size to all nodes in .

It is easy to see that this emulator has size . There are edges corresponding to low-degree nodes, and corresponding to edges in . The stretch argument follows a similar structure to the one for the -emulator. Again, for each pair of nodes , we divide the shortest path to segments of equal length . The main difference is that here we should consider the first and last heavy nodes on each segment, which we denote by and . Then there must be nodes that are adjacent to and respectively. We have and thus we have added an edge in the emulator. The path using this edge will lead to either a -multiplicative stretch for this segment, or an additive term of for the (at most) one smaller segment.

Note that this algorithm does not lead to better bounds for single-source distances since querying -bounded single-source distances still takes time using the algebraic techniques. However, if we are interested in the -bounded distance between a fixed pair of nodes and , the algebraic approach leads to better bounds. In this case, we get an improved bound of , as outlined in Section 2.2, which is less than the conditional lower bounds for approximate SSSP.

#### Sparser emulators with applications in APSP and MSSP.

Finally, we give another algorithm that leads to improvements when we need to maintain distances from many sources, such as all-pairs distances.

We start by describing how we maintain multi-source distances from many sources with an update time almost the same as the time required for single-source distances. For this purpose, given a set of sources , we maintain two emulators simultaneously: first maintain a -emulator of . Then statically construct a much sparser -emulator of size . The key idea here is to use in order to construct more efficiently. We use a static deterministic emulator algorithm (based on [RTZ2005, TZ2006emulators]) that can construct such an emulator in time . This leads to a fully-dynamic algorithm for maintaining -emulators deterministically in worst-case update time.

Then, similar to before, in each update we find distance estimates for pairs in by computing the minimum of the following estimates: i) -bounded distances from all sources maintained by an algebraic data structure, ii) distances from all sources on emulator , computed in time .

This lets us maintain -MSSP from up to sources in almost (up to an factor) the same running time as maintaining distances from a single-source by computing multi-source distances statically on this very sparse emulator and querying small distances from the algebraic data structure. This approach naturally extends to maintaining all-pairs distances deterministically and yields a worst-case update time of by setting .

#### Further Applications.

Our sparse emulators can also be used to maintain a (nearly) -approximation of the diameter. Our algorithm is an adaptation of the dynamic algorithm by [BrandN19], which is in turn based on an algorithm by [RV13]. At a high-level, we need to query (approximate) multi-source distances from three sets of size at most . We show that our emulators can be used to maintain such approximate distances much more efficiently than the data structures of [BrandN19]. Note that the diameter approximation of [RV13] is inherently randomized.

Finally, we maintain a data structure with worst-case subquadratic update time that supports sublinear all-pairs -approximate distance queries. Our algorithm is based on ideas of [RZ12, BrandN19] that utilize well-known path hitting techniques (e.g. [UllmanY91]). In order to get improved bounds we again use our sparse -emulators. We need to handle some technicalities both in the algorithm and its analysis introduced by the additive factor , combined with -bounded distances maintained in the algorithm of [BrandN19] for an appropriately chosen parameter .

## 3 Approximate Distances via Emulators

In this section we focus on constructing emulators with various tradeoffs and describing how they can be combined with the algebraic data structure of Lemma 2.3 for obtaining (conditionally) optimal dynamic single-source distance approximations.

First, assuming that we have a low-recourse dynamic hitting set, we maintain a -emulator and explain how it can be used for maintaining -SSSP. We then show how to maintain a -emulator, that can be used for maintaining - distances more efficiently.

We will then move on to give a deterministic algorithm that maintains low-recourse hitting sets, and the required distances from the nodes in this hitting set to other nodes.

### 3.1 Deterministic (1+ϵ,2)-Emulators and (1+ϵ)-Sssp

In this section we describe how to maintain -SSSP with conditionally optimal worst-case update time. We start by describing how to maintain a -emulator, assuming that we have a low-recourse hitting set, and can compute bounded-hop distances from elements in this set. The algorithm is summarized in Algorithm LABEL:alg:2_emulator. Assume that we are given two functions:

• , which returns a dynamically maintained hitting set satisfying Lemma 2.1. We provide an efficient algorithm for this function in Section 3.3.

• , which can query -bounded distances between pairs in as specified in Lemma 2.3. In Section 4, we formally explain how these distances can be maintained and then queried for our low-recourse hitting sets.

algocf[h]

Observe that even though we start with an unweighted graph, we need to add weighted edges to the emulator (with weight corresponding to the distance between the endpoints). We note that a similar, but randomized version of this emulator construction (working only against an oblivious adversary) was used in [HKN2013] for maintaining approximate shortest paths decrementally. For completeness we provide a full analysis of the properties of this emulator here. Assuming that we can maintain hitting set for satisfying Lemma 2.1 and -bounded distances in , Algorithm LABEL:alg:2_emulator can be used to show the following theorem:

###### Theorem 3.1.

Given an unweighted graph , , we can deterministically maintain a -emulator with size . The worst-case update time is , and preprocessing time is .

###### Proof.

The size analysis is straightforward. We set , and add edges for sparse nodes, and by Lemma 2.1, we have nodes in the hitting set and thus we add an overall edges for all of them.

We next move on to the stretch analysis. Consider any pair of nodes . Let be the shortest path between and in . If all the nodes on this path have degree less than , then this whole path exists in .

We divide into segments of equal length of , with possibly one segment with smaller length. Note that if , there will be only one segment. We show that for all but one segment there is a path with stretch in the emulator. Consider the -th segment that we denote by , and let be the shortest path between and . Same as before if all the nodes on are low-degree, then all the edges in the segment are in . Otherwise, let be the first heavy node on . Since is a heavy node, by Lemma 2.1 there is a node adjacent to . First assume that . Note that since and is a neighbor of and on the shortest path between and , we have . Thus we have added an emulator edge between and . Consider the path in going through . For the length of this path we have,

 dH(ui,ui+1) ≤dG(ui,v)+1+wH(w,ui+1)=dG(ui,v)+1+dG(w,ui+1) (1) ≤dG(ui,v)+1+dG(v,ui+1)+1 (2) ≤dG(ui,ui+1)+2 (3) ≤dG(ui,ui+1)+ϵdG(ui,ui+1) (4) ≤(1+ϵ)dG(ui,ui+1) (5)

Now assume that and hence . Then we have added an edge from to in the emulator. Using the same analysis as above, and by inequality 4 we have .

Since is the shortest path in , the overall multiplicative stretch is and there will be one additive term of .

The running time (update time and preprocessing) follows from Lemma 2.1 for maintaining a low-recourse hitting set , and Lemma 2.3 for maintaining -bounded distances in , by setting and . Note that we also need to maintain edges incident to heavy nodes that overlap with any node added to , but this only takes time per update. ∎

#### Using an emulator for maintaining (1+ϵ)-Sssp.

Given an unweighted graph , we first maintain a -emulator for . Given a single-source and , we can now maintain the distances by:

1. Using the algebraic data structure of Lemma 2.3: -hop bounded distances from on ,

2. After each update, statically computing SSSP on in time.

See 1.1

###### Proof.

The distance estimate stored at each node is the minimum of the two estimates (i) and (ii) described above. To see the correctness (stretch), we simply observe that for any node where , we have:

 dH(s,v)≤(1+ϵ2)dG(s,v)+2≤(1+ϵ2)dG(s,v)+ϵ2⋅dG(s,v)≤(1+ϵ)dG(s,v)

Hence a -approximate estimate is returned in step (ii) above. On the other hand, if , then we directly maintained the exact distance in step (i).

Next, we analyze the running time. The update time for maintaining the emulator, as described in Theorem 3.1 is . Then use Lemma 2.3 again for maintaining -hop bounded distances from the source. Additionally, we statically compute single source distance on an emulator of size in time. ∎

### 3.2 Deterministic (1+ϵ,4)-Emulator and (1+ϵ)-st Distances

In this section, we give another emulator-based algorithm that lets us maintain the approximate distance from a given source to a given destination with better update time than the time bound we showed for SSSP. We maintain a sparser emulator with a slightly larger additive stretch that supports faster computation of the approximate distance estimate. In particular, we maintain a emulator of size .

Compared to the emulator of Section 3.1, for this emulator construction we need to maintain bounded distances with our algebraic data structure for a smaller number of pairs of nodes, which increases efficiency. This, combined with the fact that our emulators are sparser, leads to a faster algorithm for maintaining -approximate distances.

#### (1+ϵ,4)-emulator.

We start by maintaining a sparse emulator with slightly larger additive stretch term. The algorithm is summarized in Algorithm LABEL:alg:4_emulator.

algocf[h]     Assuming that we can maintain a low-recourse hitting set and -bounded distance between pairs , Algorithm LABEL:alg:4_emulator leads to an emulator with the following guarantees:

###### Theorem 3.2.

Given an unweighted graph , , we can deterministically maintain a -emulator of size with worst-case update time of , and preprocessing time of .

###### Proof.

It is easy to see that Algorithm LABEL:alg:4_emulator leads to an emulator of size . This follows from the fact that we add at most pairwise edges between nodes in , and we add edges for non-heavy node where .

Next we move on to stretch analysis. Consider any pair of nodes . We let be the shortest path between and .

We divide into segments of equal length at most , and possibly one smaller segment that we handle separately (which could be the only segment if ). We show that for each segment there is a path with stretch in the emulator. Consider the -th segment that we denote by , and let the corresponding path shortest path between and be . Same as before, if all the nodes on have degree less than , then all the edges in the segment are in .

Otherwise, let be the first heavy node, and let the last (furthest from ) heavy node on . By Lemma 2.1 we know that there are nodes where is adjacent to and is adjacent to . The case where is a special easy case, so let us assume . First assume . Since are on the shortest path between and , we have and thus we have added an emulator edge between and . Consider the path in going through . For the length of this path we have,

 dH(ui,ui+1) ≤dG(ui,v)+1+wH(w1,w2)+dG(w2,ui+1) (6) =dG(ui,v)+1+dG(w1,w2)+dG(w2,ui+1) (7) ≤dG(ui,v)+1+dG(v,w2)+1+dG(w2,ui+1)+1 (8) ≤dG(ui,v)+1+dG(v,u)+1+1+dG(w2,ui+1)+1 (9) ≤dG(ui,ui+1)+4 (10) ≤dG(ui,ui+1)+ϵdG(ui,ui+1) (11) ≤(1+ϵ)dG(ui,ui+1) (12)

Now assume that there is a segment . We have again added an edge in . Using the same analysis as before, by inequality 10, we have . Hence the overall multiplicative stretch is and there will be at most one additive factor of .

The running time analysis now follows by applying Lemma 2.3 to maintain -bounded distances from the low-recourse hitting set obtained by Lemma 2.1. For this we use the second algorithm of 2.3, and set , where . ∎

We can now use the emulator of Theorem 3.2 to maintain -approximate -distances using the same approach as in Section 3.1. We set the distance estimate to be the minimum obtained by maintaining -bounded distances on (using the second algorithm in Lemma 2.3), and statically running Dijkstra’s on the emulator. Formally we have,

See 1.2

###### Proof.

We use Theorem 3.2 to maintain a -emulator with worst-case update time of . Then we use Lemma 2.3 again for maintaining -bounded distances. Additionally, we statically compute single source distance on an emulator of size . The stretch analysis is the same as in Theorem 1.1. ∎

### 3.3 Deterministic Dynamic Low-Recourse Hitting Sets

In this section, we focus on the deterministic maintenance of the hitting sets in order to efficiently maintain the emulators described in the previous two sections.

Let us first review a very simple static deterministic construction and later discuss how to obtain a low-recourse dynamic algorithm. Given a graph , we create a sparse subgraph of with size , which we denote by as follows: For any heavy node (a node with degree at least ), we choose an arbitrary set of neighbors of , denoted by .

We then statically compute an -approximate hitting set for deterministically (i.e., exceeds the size of a minimum hitting set on by a factor of ). Consider the following simple greedy algorithm: in each step consecutively we add to the node that hits (i.e. is incident to) the maximum number of uncovered heavy nodes. It is well-known that such an algorithm leads to the following guarantees.

###### Lemma 3.3 (Greedy Hitting Set, [johnson1974]).

Given a graph , and a degree threshold , we can deterministically construct a hitting set with size in time, such that every heavy node has a neighbor in .151515This lemma can also be seen as an -approximation greedy algorithm for set cover, where the sets that we need to cover are formed by set of node incident to each heavy node.

It is easy to see that the hitting set obtained has size : by a simple sampling procedure we know that there exists a hitting set of size , and we are using an -approximate hitting set algorithm. A tighter analysis (e.g. see [BHK2017]) will lead to a total size of .

Next we move on to a dynamic maintenance of hitting sets. Our goal is to prove the following lemma.

See 2.1

First, we start with an algorithm with amortized constant recourse, and then turn it into a an algorithm with worst-case constant recourse.

The amortized low-recourse hitting set algorithm is as follows:

• Preprocess a hitting set in time, using Lemma 3.3

• After each updates, reset, i.e. construct a new hitting set from scratch.

• When an edge is deleted: if either of the endpoints, w.l.o.g , is a high-degree node, and is the only node covering , add to .

• When an edge is inserted: if one endpoint, w.l.o.g , becomes high-degree and it is not covered by any other node, add to .

It is easy to see that this construction has low amortized recourse, since over a sequence of updates, only are added to the hitting set. The amortized update time is , since we reset the algorithm every time steps, and the size of the input of the hitting algorithm has size . Hence the amortized time per update is . We next turn this into a worst-case recourse bound using a standard reduction.

#### Worst-case constant recourse bound.

In order to ensure a worst-case recourse bound, we use a standard technique in which we run two copies of the algorithm at the same time. One copy maintains the hitting set whenever the other copy gradually perform the reset operation spread out over some sequence of updates.

###### Proof of Lemma 2.1.

We maintain two copies of the previously described hitting set algorithm in parallel. We denote the hitting sets maintained by these algorithms by and


text:
# Math Help - Question about line integral

1. ## Question about line integral

let $\kappa$ denote the curvature of a closed spacecurve $\alpha$. Find $\oint_{\alpha} \frac{1}{\kappa} \ d\kappa$

Looking at this, I would imagine that this would either be $0$ since $\alpha$ is closed or $T$, the tangent Vector, but I'm not to sure on how to achieve the desired result.

My other idea would have been to write it down as follows:

$\oint_{\alpha} \frac{\|\alpha'\|^3}{\|\alpha' \times \alpha''\|} \cdot \|\alpha'\| \ dt$

But these attempts don't seem to lead to anything.

2. $\oint_{\alpha} \frac{1}{\kappa} \ d\kappa = \oint_{\alpha} d \ln | \kappa | = 0$

format: plain


text:
local fundamental group of elliptic singularities - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:21:54Z http://mathoverflow.net/feeds/question/111278 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111278/local-fundamental-group-of-elliptic-singularities local fundamental group of elliptic singularities Benoît 2012-11-02T14:26:54Z 2012-11-02T14:26:54Z
Is the local fundamental group of an elliptic singularity virtually solvable ? Here (the terminology is sometimes divergent) an elliptic singularity is a (germ of) normal surface $(X,x)$ such that $X$ is Gorenstein ($K_X$ is Cartier) and $R^1\pi_* \mathcal{O}_Y=\mathbb{C}_x$ where $\pi:Y\to X$ is a resolution of the singularity.

Equivalently: $\pi_*\omega_Y=m_x\omega_X$.

Thanks in advance, Benoit


text:
Exact Equation

• September 11th 2010, 09:49 PM
staevobr
Exact Equation
$(e^x \sin{y} -3x^2) \,dx +(e^x \cos{y} + \frac{y^{-2/3}}{3}) \, dy = 0$

$(e^x \sin{y} -3x^2) +(e^x \cos{y} + \frac{y^{-2/3}}{3}) \frac{dy}{dx} = 0
$

$M = e^x \sin{y} -3x^2 \,, N = e^x \cos{y} + \frac{y^{-2/3}}{3}$

$\frac{\partial M}{\partial y} = e^x \cos{y}$

$\frac{\partial N}{\partial x} = e^x \cos{y}$

Since
$\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}$,
there exists an F such that
$\frac{d}{dx}F(x, y) = 0$

$F = \int{M dx}$
$F = \int{e^x \sin{y} -3x^2 dx} = e^x \sin{y} -x^3 + h(y)$

$\frac{\partial F}{\partial y} = N$

$e^x \cos{y} + \frac{y^{-2/3}}{3} = e^x \sin{y} -x^3 + h'(y)$

I can't find any way to get past this point. Is there any possible function $h'(y)$ that would satisfy this equality? Or have I made an error?
• September 11th 2010, 09:58 PM
Prove It
Your working is a little off...

Since $\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}$

that means

$\frac{\partial F}{\partial x} = M$ and $\frac{\partial F}{\partial y} = N$.

So

$\frac{\partial F}{\partial x} = e^x\sin{y} - 3x^2$

$F = \int{e^{x}\sin{y} - 3x^2\,dx}$

$= e^x\sin{y} - x^3 + g(y)$.

$\frac{\partial F}{\partial y} = e^x\cos{y} + \frac{y^{-\frac{2}{3}}}{3}$

$F = \int{e^x\cos{y} + \frac{y^{-\frac{2}{3}}}{3}\,dy}$

$= e^x\sin{y} + y^{\frac{1}{3}} + h(x)$.

So we have at the same time...

$F = e^x\sin{y} - x^3 + g(y)$ and $F = e^x\sin{y} + y^{\frac{1}{3}} + h(x)$.

This means $g(y) = y^{\frac{1}{3}} + C_1$ and $h(x) = -x^3 + C_2$.

Putting everything together gives

$F = e^x\sin{y} - x^3 + y^{\frac{1}{3}} + C$ where $C = C_1 + C_2$.
• September 11th 2010, 10:08 PM
staevobr
Thanks.


text:
extensions:tropicalcubics

# TropicalCubics

This is the software companion to the article “The Schläfli fan” by Michael Joswig, Marta Panizzut and Bernd Sturmfels, arXiv:1905.11951

Smooth tropical cubic surfaces are parameterized by maximal cones in the unimodular secondary fan of the triple tetrahedron. There are 344 843 867 such cones, organized into a database of 14 373 645 symmetry classes. The Schläfli fan gives a further refinement of these cones. It reveals all possible patterns of the 27 or more lines on tropical cubic surfaces, thus serving as a combinatorial base space for the universal Fano variety. This article develops the relevant theory and offers a blueprint for the analysis of big data in tropical algebraic geometry. We conclude with a sparse model for cubic surfaces over a field with valuation.

While the database or rather the relevant collection TropicalCubics can be accessed directly via a web front end or though mongodb's API, using this extension to polymake is recommended for an enhanced experience.

TropicalCubics-0.2.tar.xz [04 Feb 2020], for polymake version 4.0

TropicalCubics-0.1.tar.xz [28 May 2019], for polymake versions 3.5 and 3.6

This requires an installation of polymake, version 4.0. For polymake 3.5 or 3.6 use version 0.1 of this extension instead.

tar Jxpf TropicalCubics-0.2.tar.xz

Suppose this ends up at /your/path/TropicalCubics-0.2. Then you start up polymake. Within the polymake shell do:

import_extension "/your/path/TropicalCubics-0.2";

Do not forget to use an absolute path! Afterwards you are good to run the code. This import needs to be performed only once. The reference to the extension is permanently stored in $HOME/.polymake/settings. For more details there is a guide to polymake's extension system. This extension contributes to the applications fan and tropical. In the application tropical you can create a dense tropical cubic surface by just specifying the coordinates. The monomials, which correspond to the 20 lattice points in the triple tetrahedron$3 \Delta_3$, have a fixed ordering. >$S = new CubicSurface<Min>(COEFFICIENTS=>[5,1,1,5,2,0,2,2,2,5,2,0,2,0,0,1,2,2,1,5]);
> print $S->DEGREE; 3 A CubicSurface is derived fromHypersurface; so it has all its properties. The bulk of the functionality sits in the application fan and the type DualSubdivisionOfCubic. The latter is derived from SubdivisionOfPoints. > print$S->DUAL_SUBDIVISION->type->full_name;
DualSubdivisionOfCubic
> $T = new DualSubdivisionOfCubic(MAXIMAL_CELLS=>[[0,1,4,10],[9,13,14,15],[11,12,13,16],[15,16,17,18],[16,17,18,19],[13,15,16,17],[5,8,11,12],[1,4,5,11],[5,7,9,13],[5,6,8,12],[13,14,15,17],[1,5,11,12],[1,2,5,12],[4,5,7,13],[8,9,13,14],[3,5,6,12],[2,3,5,12],[4,11,13,16],[12,13,14,17],[5,8,9,13],[5,8,11,13],[1,4,11,16],[1,4,10,16],[8,11,12,13],[12,13,16,17],[8,12,13,14],[4,5,11,13]]); > print$T->GKZ_VECTOR;
1 6 2 2 7 12 2 2 7 4 2 9 11 15 5 4 8 6 2 1

In the article we consider the running example #5054117. This is how you can get that regular unimodular triangulation of $3 \Delta_3$ from the database. Everything below requires common::polydb.rules to be correctly configured.

> $X=retrieve_by_id(5054117); > print$X->MAXIMAL_CELLS;
{0 1 4 10}
{1 2 5 11}
{1 4 7 13}
...

This example has one occurrence of the motif 3J.

> print $X->N_MOTIF_TYPES; 6 5 0 24 0 2 4 7 2 1 >$X->MOTIFS3J->[0]->properties();
type: Motif

TYPE
J

POINTS
11 9 15 1 2

EXITS
0 3 1 2

TETRAHEDRA
10 19

Suppose you have a triangulation of $3 \Delta_3$ and you want to find it. The next example comes from §6.2 of Hampe & Joswig: Tropical computations in polymake, in: Algorithmic and experimental methods in algebra, geometry, and number theory, Springer 2017. This is again in application tropical.

> $F = toTropicalPolynomial("min(12+3*x0,-131+2*x0+x1, -67+2*x0+x2,-9+2*x0+x3,-131+x0+2*x1,-129+x0+x1+x2, -131+x0+x1+x3,-116+x0+2*x2,-76+x0+x2+x3,-24+x0+2*x3,-95+3*x1, -108+2*x1+x2,-92+2*x1+x3,-115+x1+2*x2,-117+x1+x2+x3, -83+x1+2*x3,-119+3*x2,-119+2*x2+x3,-82+x2+2*x3,-36+3*x3)"); >$V = new Hypersurface<Min>(POLYNOMIAL=>$F); >$h = canonical_hash($V->DUAL_SUBDIVISION->MAXIMAL_CELLS); >$Y = retrieve_by_canonical_hash($h); > print$Y->name;
5054117

So this corresponds to the triangulation #5054117 constructed above (and stored in the variable \$X). For about 99.5% of all triangulations the canonical hash value (computed by nauty) identifies the triangulations uniquely. In the remaining cases the function retrieve_by_canonical_hash returns the first triangulation and issues a warning.

• extensions/tropicalcubics.txt


text:
Let's say scientists created a pill, that would satisfy our daily nutritional needs. It would have all vitamins needed, all calories, minerals - everything that a human body needs in order to function properly. The side effects are unknown.

How much is this pill in the "fiction" section? Is it really possible to create such pill?

How would this pill change our diets? I believe the price would have a great impact, so let's discuss three possible prices: 1, 100, 10000 american dollars. But would it replace natural meals entirely?

Assuming that this pill is used by 25% of Earth's population for a long period of time (100 years). Would they look, feel, behave different than the rest of humans? What about 100% of Earth's population?

EDIT: My thoughts:

• This pill would cause obesity for some people - using it wouldn't make you feel "full" so you could just eat the same amount of food that you ate previously.
• Many people would be affraid of side effects which are currently unknown
• This would solve hunger in third world countries, IF the prices would be right. This might cause economic growth.
• The pill could improve or even save million of lives, so I'm guessing the price would be high (maybe thousands or dollars), so only the wealthy ones would afford it.
But the wealthy ones have enough money to buy food on the regular basis so they could use it only if they were to travel to space or somewhere where food would be not so easily available.
• Note that even in 24th century Star Trek, some people make a point of making "real food" rather than "replicated stuff". In our world of today, quite a few people (for varying reasons) seek to live a simpler life using primarily or exclusively the technologies of yestercentury. Assuming such a pill can be made, I think it's safe to say that something similar would happen in your world: even if it is widely adopted, there will be some fraction of people who will shun it, for any number of reasons. – a CVn Aug 7 '15 at 9:20
• This seemed to be a common idea of what the future would be like, in the 1960s. It fails to note that people actually enjoy eating. – David Richerby Aug 7 '15 at 17:18
• Answer in one word: Fiber. – jamesqf Aug 7 '15 at 18:22
• Agree with @jamesqf ... Fiber is the down fall of any kind of purely liquid diet. Your body isn't going to be happy shutting down the solids processing heh. – Kaithar Aug 7 '15 at 19:33
• @Kaithar - I'm not so sure. Studies of people adrift on rafts without food show that defecation ceases but starts up again naturally when food is eaten once more. (remembered facts from reading years ago) I think that the body would cope with pure nutrients. – chasly from UK Sep 2 '15 at 12:59

Being total sci-fi geek, I got introduced to the idea of Soylent drink.

Disclaimer: I am not connected to the site in any manner

So, the pill itself is pure sci-fi. But being able to eat only prefabricated food is not so sci-fi.

The hardest part is, that everyone is forgetting the sheer amount of inputs which human body needs

# No

My answer to a similar (but not identical) question was that there's a limit to how nutrient dense you can make your food or the human body can't absorb it.

The problem is that very nutrient dense foods suck water out of your body through osmosis. This leaves the consumer dehydrated and they still aren't able to absorb the nutrients.

If you perform the math on the numbers provided in the answer linked above and for a 2000 kcal diet (average for a male), the densest nutrient concentrations a person could easily tolerate would require them to consume about 6-8 $Ensure^{TM}$ per day. The total mass of this would be $7 \times 240 g$ ~ $1.7 kg$. To this you'd need to include an extra supply of water since the quantity provided in $Ensure^{TM}$ would be insufficient to sustain a person.

I realize this number seems high, but realize that this 1.7 kg (3.7 lbs) of food includes 1.3 liters (2.8 lbs) of your daily water requirements.

# Yes

Instead of consuming your "food pill" directly, if you instead dropped it into a container of water and drank the results, that would probably work if you got the quantities right.

In this case, your "food pill" for a day's rations would mass about 0.4 kg (0.9 lb) and would need to be dissolved in the quantity of water identified above.

# Other Stuff

## Preferences

As a person with digestive issues, I've been forced to use $Ensure^{TM}$ to supplement my diet. I never drank it because I liked it. This stuff tastes OK but it isn't something most people would choose over regular food.

## Long-term Use

Perhaps more important, we still do not know all the nutrients the human body needs to stay healthy. We know the macronutrients (fat, carbohydrates, protein, and water); we know the micronutrients (vitamins & minerals) but we do not know the trace nutrients that are beneficial.

The trace nutrients are those chemicals are the ones scientists look for in wine, coffee, chocolate, etc. Scientists are constantly changing their minds about whether this food or that are good or bad for you.

A diet of only these concentrates will keep you going but might lead in the long-term to a variety of difficult to diagnose issues. We just don't know enough about it right now.

## Costs

Right now, these concentrated foods are substantially more expensive than the food that they'd replace (perhaps \$10 / day). If you wish to solve world hunger it does have some advantages though:

1. Light weight - easy to transport
2. Shelf stable - no spoilage

## Solving Obesity

As our knowledge of obesity increases, this answer may become dated but current research implicates many factors of which layman are unaware.

Factors which may cause obesity:

Of these, the "food pills" might only solve #1 or possibly #5 if the "food pills" were laced with gut biota known to be a good & healthy mix.

I suppose it's possible that a sophisticated society could generate "food pills" based upon a doctor's prescription in which case #3, #4, & #6 might also be addressed by taking your and only your "food pills".

## Hunger

as a motivational state.

The hunger mechanism in people is fairly complicated, can be triggered or suppressed by several different factors, and has different processes over short and long terms.

Short-term regulation of hunger and food intake involves neural signals from the GI tract, blood levels of nutrients, and GI tract hormones.

A food pill can be designed in a way that triggers all the right GI tract and blood monitoring triggers as long as the "pill" contains "bulk" for the GI tract to work on. Fiber would fill this need quite well. Furthermore, current diet nutritional shakes already include fiber in their formulations for just this reason.

## Eating as a sensory experience

I think one area in which this idea fails would be when "eating as a sensory experience" When humans really indulge in the pleasures of eating, we engage more senses than just taste. We enjoy different textured food (touch), foods with pleasing aromas (smell), colorful arrangement (sight), and even sometimes foods that make sounds when eaten (sound).

Food pills might be able to accommodate taste and to a lesser extent smell but would leave out the other senses. For these reasons (and a few others), I don't think food pills would ever replace "real food" on the luxury market.

• The Factors "Causing" obesity you listed are actually only contributing factors. No genetic predisposition can make you gain wait if you are not exceeding your calorie needs, they can only be more or less friendly in today's calorie rich diets. Nothing can make calories out of nothing. Diet alone CAN prevent obesity in all cases if tailored to a person's individual needs. Now, there a many other serious health concerns that those other issues can cause that diet CAN'T fix, but obesity is not one of them. – wedstrom Aug 7 '15 at 17:42
• Perhaps expand your answer with something addressing the issue of lack of solids and particularly fiber? – Kaithar Aug 7 '15 at 19:37
• @westrom, actually research indicates this isn't true. That when subjects are fed the same diet some will get fat and others will stay a health weight. In my own personal case, I need to consume about 3000 kcal / day to maintain weight because my body has difficulty absorbing the nutrients. There are many factors and they interact in ways we can't predict. We are discovering that "blame the fat person" is very often wrong. Perhaps in 20 years we'll know enough to assign blame where it really belongs. – Jim2B Aug 7 '15 at 21:11
• @kaithar, due to damage to my gut, I've spent many years (5-10) with extremely low fiber diets with little directly quantifiable ill effects. These very low fiber diets increase your odds of various ailments but in some cases those risks are a better choice than the alternatives (intestinal blockage is extremely painful, potentially life threaten, and can require emergency major surgery to correct). – Jim2B Aug 7 '15 at 21:13
• As for Ensure--I've had to do worse: Vivonex. It's basically pure nutrition. I don't think any adult would need less than a pound a day of it. That's an awful lot of pills! You could get somewhat smaller by getting most of your calories from fat (Vivonex has a little fat as medically acceptable) but you're still going to be near a pound for an average adult. – Loren Pechtel Aug 10 '15 at 1:31

While the vitamins would probably be relatively cheap and easy to supply, calories would be another matter.

The most calorie-dense foodstuff is pure lard, at about 892 calories per 100 grams; for reference, a stick of butter usually weights around 100 grams.

An average adult human needs between 2000 and 2400 calories every day, so someone looking for the bare minimum calories would need to eat bout 224 grams of pure fat. This would obviously be too much for one pill to handle.

For the sake of creating a fictional world, you could possibly get around this with the invention of a new kind of synthetic organic molecule which packs about 2000 calories into a single gram, with a second gram used for traditional multivitamins.

This would solve the energy issues, but it would still leave people with too little actual matter for their bodies to work with; they wouldn't be able to do things like develop muscle or hydrate themselves. The best the pill could do would be stave off starvation.

It's total fiction

One pill a day to satisfy a person's nutritional needs is a very old trope in SF. The problem is that physics, chemistry and human physiology (and maybe psychology) simply don't support it. Having a human survive on just a single pill every day without any supplemental energy sources is complete and utter fiction.

Limited Nutrient Compressibility

DIY Soylent is an excellent place to experiment with different nutritional profiles. For example, the recommended nutritional intake for an adult male for a vitamin C alone is 2 grams. The density of Vitamin C is 1.69 g/cm³. Even without doing any math to find out exactly how big the pill is, it's becoming larger than many people will want to swallow, and this is just one nutrient! For an idea of scale, the below photo is 1 cubic centimeter cubes in a child's hand:

Granted, many other nutrients take up far less space, biotin in particular is needed in vanishingly small amounts. These small nutrients are just statistical noise compared with the larger nutrients like calcium carbonate at2.71 g/cm³ and an adult male needs 1 gram. Females need more than that. Calcium is a sizable pill even without binders to keep it all together.

Calorie Requirements

Let's start with the standard 2000 calorie diet in the form of protein, fats and carbs. The human body needs a certain amount of protein every day or it will start consuming its own muscles to get it. While human muscles and organs can survive on ketone bodies (the energy transport mechanism for energy derived from fat) the brain requires sweet, sweet carbs. (From personal experience, trying to fuel the brain on just ketones won't work. Just don't do it. Sugar cravings like you wouldn't believe!) Thus, we have minimal intake requirements for protein and carbs; all the other energy requirements can be made up with fats/oils/lipids.

For quick reference, carbs are 4 calories (nutritional calories, not physics calories) per gram, protein is 4 calories per gram, alcohol is 7 calories per gram and fats are 9 calories per gram.

Without addressing macronutrient ratios, let's just assume that all calories will come from fats thus giving a lower bound on the required mass to fuel a human body for a day. 2000 calories / 9 calories/gram = 222.2 grams of fats. Using canola oil (at 0.92 g/ml) for fuel gives us 241 cubic centimeters. For comparison, a Rubik's Cube is a mere 185cm^3. No one swallows Rubik's cubes.

Mush, no matter how sweet is not tasty

As this scene from the Matrix so perfectly describes, humans don't like eating tasteless, monotonous slop. Sure they will if they have to, to survive but they won't like it. From an evolutionary biology perspective, it's not hard to make the jump that an early human that ate the same thing every day, all day soon developed nutritional deficiencies and could not compete. An instinct for varied foods and varied textures helps cover nutritional deficiencies.

But what if you could do it all in a pill...

Okay, okay, what if you could make a pill that filled a person's nutrient and caloric needs for one day?

• A great deal of nutritional and inflammation based diseases would go away.
• The obesity epidemic in the US would vanish.
• The populations body fat percentage would settle at levels particular to that person's genetic. Ectomorphs would stay thin. Endomorphs would stay heavy. In both cases, they would be more easily able to accept their body shape because they know they're giving their bodies what they need/want.
• Caloric requirements depend on activity level. So you would still be able to slim down by exersise. – Taemyr Aug 10 '15 at 11:54

Outside of issues like how many calories a pill could pack, the human body has evolved to process natural food. We need a certain amount of fibre in order to push things through the intestines, for example.

The other issue is that different humans have different needs. You can eat things off a plate or ignore them, and order individual meals to meet dietary, social, religions or other requirements. I'm not sure many people would believe your pill is Kosher, Gluten free or an appropriate snack food for watching the game. Taking a prospective mate to dinner would be a totally different thing (think of all the rituals involved around taking a date to dinner).

Pill food might be appropriate for emergency situations (for example, a box of emergency rations in a survival kit would be much more portable if they could be replaced by pills), or perhaps for extreme adventurers (hiking with a pack of pills across the Amazon rain forest), but even then, the social aspects of sitting around the camp at night and sharing a meal wold be lost.

So the other answers have made it pretty clear that you can't pack a full day's nutrients into a single pill, even if it's a large "horse pill".

But what if, instead of digestible nutrients, this pill contains an array of chemical- or nuclear-fueled nanomachines and a stock of raw elements? What if these nanomachines could use these elements together with some amount of ingested water to build nutrients and then exhaust them into the stomach? Then, later, when the machines run out of fuel, they make their way naturally down the digestive tract to be excreted.

As for the effects of such a technology:

Obviously the users of such a pill would stop defecating for the most part. Reportedly this already happens with soldiers who subsist entirely on military rations. That alone would save humanity a lot of time and water, which would contribute positively to the economy.

If the pill was very cheap, it might result in a population explosion. If it was very expensive, most likely no one would really use it, and it would remain a laboratory curiosity except in certain contexts where space and weight is at a premium, for example, space travel.

It's not certain what problems prolonged use might entail. Obesity rates might drop, since it's a (very) controlled portion and it kind of removes the fun from mealtimes. Even if it's pretty safe, the medical profession might recommend "real" food every once in a while to flush out the system.

• Oh, by the way, there's no way that I'd swallow a nuclear-fueled robo-nano-pill, no matter how safe they said it was. : ) – Doug Warren Aug 7 '15 at 15:50

It is complete fiction with today and near-term technology. I think most current answers cover that aspect.

If you were looking far into the future though, it is theoretically possibly that a bionic upgrade could allow you to just shove your daily energy intake, as a pill, into a hatch which would slowly push the nutrients into your body throughout the day. Depending on just how advanced we can get with stuff like that, maybe the bionic upgrade completely optimizes and replaces our current digestive system for our processed bricks of material.

How much is this pill in the "fiction" section?

Very much so, unless you plan on taking a very large pill every 4 minutes. (This number comes from @Greens answer, which suggests that 241cm^3 sized pills would be needed for a day's worth of Calories. Subtracting 8 hours for sleeping, you could take 1cm^3 pill every 4 minutes to get the correct amount. - but then you have to add in all the other stuff your body needs as well, likely making that pill much larger

How would this pill change our diets?

We wouldn't have to worry about our diets! That and the pill being slightly more compact than normal food are really the only positive things about it.

But would it replace natural meals entirely?

Unlikely, people like to eat and try new tastes. It makes us feel good to eat. Doing otherwise just isn't "natural", there would have to be a huge reason not to do it.

Assuming that this pill is used by 25% of Earth's population for a long period of time (100 years). Would they look, feel, behave different than the rest of humans? What about 100% of Earth's population?

If you go with the bionic thing, then people would look very different due to that - but people's looks wouldn't drastically change because of what form they are getting their food in, especially not in only 100 years.

No one is thinking long term here. It's my understanding that one of the most important differences between us and other species is the cooking of foods with fire. Leading to smaller intestine and bigger brains. If a pill or several pills taken throughout the day could replace our current food situation wouldn't it seem to imply even less intestinal need and even bigger brains?????

When I was in my twenties I experimented for several weeks by surviving only on milk mixed with a well-known British energy drink (Lucozade) supplemented with vitamin pills. At the time I used to cycle to work ending with a hill.

At the end of the trial I felt fitter and was slimmer than when I started. I had no adverse symptoms at all. (see disclaimer)

The biggest effect of all came from joining colleagues at mealtimes. After only four days I lost any cravings for what they were eating but it was just so boring. The whole business of eating is important socially or alone and was the reason I stopped. I had a huge desire to chew and swallow and even to use eating utensils.

Disclaimer

I am not in any way medically qualified. I was young and in good health at the time and I cannot say what effects, good or bad, such a diet would have on anyone else.


text:
• KEY TAKEAWAYS

• We adjust our recommendation over time, taking less risk as you approach your goal, but the amount of risk and path to get there may differ for each goal.

• We are constantly optimizing your portfolio and savings or withdrawal recommendations based on a quantitative assessment of potential outcomes.

By Dan Egan

## Introduction

If you have ever worked with a traditional investment manager or have a 401(k) plan at work, you have likely answered a “standard” risk questionnaire. It often starts with your estimated retirement date and how much money you have, and then ask you what kind of returns you want to see.

But these questionnaires measure what kind of risk-taker you think you are, not what kind you need to be in order to achieve your goals.

At Betterment, we believe that your investment horizon—how long until you will need your money—is one of the most important determinants of how much risk you should take. The more long-term your investing goals, the more risk you can afford to safely take. Money saved for short- and medium-term goals, such as saving for a house or buying a car, can be invested at a different risk level than a longer-term goal, such as retirement.

Another consideration is how you plan to use the money when you need it. Will you take out the investment in a lump sum or will you gradually make withdrawals over time and use that money for income? These are key pieces of information we use when providing personalized investment advice.

Below, we walk you through the rationale of our risk advice model. Unlike the standard risk questionnaires, our algorithm weights investment time horizon and downside risk more heavily, and allows you to deviate from our advice if you want to deviate.

This is the heart of Betterment’s risk advice algorithm.

First, let’s talk about goals. At Betterment, you can think of goals like different investment buckets. They are technically subaccounts that you can use to silo your retirement savings from vacation savings, for example. Every goal you set up at Betterment (and every customer can set up several) will have its own customized allocation of stocks and bonds.

Each goal has different final liquidation assumptions, so it is important to select the one that most closely matches your real intentions. Below we can see the diversity of goals you can manage at Betterment.

##### …and then look at your investment horizon.

Once we know your goal, we next consider how long you will be invested in that goal, as well as the withdrawal plan for that goal. Is it a goal that you plan on cashing out in 10 years, or a goal such as retirement in 30 years, give or take a few years? That actually makes a big difference in the advice we’ll give.

We assume you will spend your Major Purchase goal savings at a specific point in time. You might withdraw your entire House goal investment after 10 years when you have hit the savings mark for your down payment. In contrast, with a Retirement goal, we assume you will spend funds over a number of years rather than in one lump sum withdrawal. That’s the nature of a nest egg—it’s the basis for your monthly income in retirement.

If you don’t have a specific investment horizon or target amount, we will use your age to set your investment horizon (our default target date is your 65th birthday) in a General Investing goal. It has a similar spending assumption as retirement, but maintains a slightly riskier portfolio even when you hit the target date, since it’s not clear you’ll liquidate those investments soon.

With this information about your time horizon and goals, we can determine an optimal risk level for your investment horizon. We do this by assessing the possible outcomes for your time horizon across a wide variety of bad to average markets.

Getting to an optimal risk level, generally attained through exposure to stocks versus bonds, involves weighing the trade-offs between potential gains from higher risk investments and the potential for falling short by playing it safe. We have designed our formula so that it works especially well with our portfolio, which contains multiple globally diversified asset classes.

Now, we know we can’t predict what the future will be. So we use a projection model that includes this uncertainty by including many possible futures, weighted by how likely we believe they are.  We use these probability-weighted futures to build our recommendation based on a range of outcomes, giving slightly more weight to potential negative outcomes and building in a margin of safety—which technically is called ‘downside risk’ and uncertainty optimization. If you’re interested, you can also read more about our projection methodology.

Paying particular attention to below-average scenarios we are able to select a level of risk that aims to minimize potential downside risk at every investment horizon. By some standards, we have a fairly conservative allocation model—but as we mentioned above, our mission is to help you get to your goal through steady saving and appropriate allocation, rather than taking on unnecessary risk.

## How we balance risk and time

Now, let’s consider now how risk and time work together. The example below shows the forecasted growth of $100,000 in a 70% stock portfolio over three years. The expected return, or median outcome, for this portfolio is$121,917, but the range of possible outcomes moves from at least $180,580 for the top 5% of potential outcomes to no better than$82,312 for the bottom 5%. This is a great example of how stocks can bring both a lot of upside—as well as downside in the short-term.

#### Outcome and risk over a three-year term

If the graph above shows an example of the predicted volatility that stocks can bring to very short-term time horizons, what happens to the same portfolio over a 10-year time horizon?

#### Outcome and risk over a 10-year term

After 10 years, our models predict that you are less likely to lose money and more likely to come out ahead on an absolute dollar basis.

## How we manage downside risk

Now that the relationship between risk and time is clear, let’s turn back to allocation.

In order to make an appropriate recommendation of stocks and bonds, we have to look at potential outcomes for everything from 0% stocks to 100% stocks. To do this, we evaluate stock allocations and look at how they might perform at similar percentiles over a fixed investment horizon. This analysis helps us finely tune the stock-and-bond ratio.

In the example below, we see the 15th percentile outcome for every stock allocation over a 20-year investment horizon. We use the 15th percentile to represent a ‘bad’ outcome, i.e., poor predicted market performance. With shorter-term horizons (seven years and less), our modeling shows a majority bond portfolio beats a majority stock portfolio in this ‘bad case.’  However, by year 12, the same model predicts higher stock allocations begin to overcome bond-heavy portfolios. By year 20 all majority stock portfolios (at least 50.1%) have better outcomes than majority bond portfolios, even though this is still a ‘bad’ outcome in terms of investment performance.

#### Returns at the 15th percentile, or a ‘bad case’ scenario

Within this bad outcome scenario let’s focus on the best allocation at each time period. Measured by returns, the best expected outcomes are equivalent to the top of this graph (traced in red).

Another way to view this best allocation line is to change the y-axis from absolute value in dollars to the stock allocation. If we plot the same 15th percentile best allocation line on a new plot we get the following graph.

#### Portfolio value as a measure of stock allocation at the 15th percentile

This new view of the same line clearly shows which allocation would have performed best for a given period. For example, in the ‘bad’ scenario, a 65% stock portfolio would have performed best over a period that lasted 10 years and nine months on the predicted model.

#### Allocation and time

Our advice doesn’t only consider the bad outcomes. We seek to find the best stock allocation for outcomes from the expected 50th percentile to the 5th percentile (a ‘worst case’ scenario, but not THE worst case scenario). You can see the result of this exercise in the graph below, which maps investment horizon against best stock allocation, given the percentile chosen.

#### Percentiles by 5%, from 5th to 50th

Our goal is to provide the best possible expected returns. That means aiming to provide you with the best chance of making money and not losing it. To do that, we then must look at the the median outcome—and an average of all the outcomes that are considered bad, which is everything from the 5th percentile to the 50th. (Why 50th? Percentiles over the 50th, the median will always show that 100% stocks are the best allocation.)

The dark blue line represents the average ‘best’ stock allocation across all percentiles. Since we have included more downside scenarios in this average, it weighs the potential for loss more than equivalent upside. But note that over longer time periods, even with a downside risk focus, we predict that it is still better to be in a majority stock portfolio compared to a majority bond portfolio.

#### Average of all percentiles

For long-term goals, those with time horizons over 20 years or more, we recommend 90% stocks. For short-term time horizons, we recommend 10% stocks. And for intermediate-term goals, the recommended stock allocation rises very quickly. This is based on a conservative downside-weighted risk measure which accounts for your specific time horizon in each goal to help ensure you are taking on the right risk for the level of return you should realize.

## The result is Betterment’s glide path

The result is a general framework for the risk allocation advice Betterment uses across all goals, which can supply a goal-specific glide path recommendation.

In investing, a glide path is the formula used for asset allocation that progressively gets more and more conservative as the liquidation date nears. Many retirement-oriented target-date funds are based on a glide path (though every firm has its own formula.)

At Betterment, we adjust the recommended allocation and portfolio weights of the glide path based on your specific goal and time horizon. This means Betterment glide path recommendations are more personalized to your specific goals and investment horizons.

For example, in our Major Purchase goals, shown below, the recommended glide path takes a more conservative path than a recommended retirement glide path—moving to near-zero risk—for very short time horizons. Why is that? This is because we expect that you will fully liquidate your investment at the intended date and will need the full balance.

With Retirement goals, in contrast, the glide path we recommend remains at a higher risk allocation even when the target date is reached, as we assume liquidation will be gradual, and you still have years in retirement for your investments to grow before they are liquidated. If you’d like to understand how this advice varies by goal type, you can read more here.

#### Mixing bonds and stocks across percentiles

The bottom line: Our allocation advice is designed at a goal level to help ensure you’re taking on the right level of risk based on your personal situation, unlike the impersonal and often unexplained glide path offered by target-date funds.

## Including customer risk preference

How should we modify this analysis for a conservative or aggressive approach?

The glidepath derived above is downside optimized because it gives equal weight to each percentile outcome from the median down to the first percentile over a given time horizon. To tailor this guidance to a more conservative or aggressive approach, we’ll change the weights to reflect the degree to which investors care about the worse outcomes versus median average outcomes.

### A quantitative approach

We’ll define a ‘conservative’ approach as giving the median (50th percentile outcome) about 40% of the weight of the 5th percentile outcome. Conversely, the ‘aggressive’ approach gives the 5th percentile outcome about 40% of the weight of the median.

#### Weight Given to Outcome for Different Approaches

The result is a set of optimal aggressive and conservative glidepaths, as shown below for a major purchase goal.

#### Deviation from the Recommended Approach

This approach does allow for deviation by risk level, which produces a non-linear guidance range. It is wider at moderate allocations, and tighter at the bottom and top of the risk range.

#### Optimal Stock Allocation

One reason is simply mechanical: at higher risk levels, you can’t deviate up very much. At lower risk levels, you can’t deviate down much.

Taken across the entire range our outcomes, we have determined that ± 7% is a reasonable deviation. We believe a stable range across recommended levels is easier to understand and follow, and there is sufficient noise in the more extreme tails of these estimates to justify allowing a higher range at the tails. We therefore give guidance that the acceptable range of deviation is -7% for customers wanting a conservative approach, and +7% for customers wanting an aggressive approach to that goal.

### Goal-term guidance

Our quantitative approach above allows us to establish a set of recommended risk ranges given our goals. However, an investor may choose to deviate from our risk guidance if they see fit, and there may be appropriate reasons for those deviations. That being said, we provide investors with feedback regarding the potential implications of such deviations and, in doing so, we treat upwards and downwards deviations differently.

If an investor decides to take on more risk than we recommend, we communicate the fact that we believe their approach is “too aggressive” given their goal and time horizon. We flag this because even in a setting where an investor cares about the downsides less than the average outcome, it still isn’t rational to take on more risk (viewing this particular goal in isolation). If the investor is unlucky with returns over that period, the losses in a portfolio flagged as “too aggressive” will be very difficult to recover from.

In contrast, if an investor chooses a risk level lower than our “conservative” band, we’ll communicate that their choice is “very conservative.” This is because the downside of taking on a lower risk level in a moderate outcome scenario is simply needing to save more. And we believe investors should choose a level of risk which is aligned with their ability to stay the course through the short term.

### Aligning risk level with short-term risk tolerance

An allocation cannot be optimal if the investor is not comfortable committing to it in both good markets and bad ones. As a point of reference, our 70% stock portfolio would have lost 46% from Nov. 2007 to Mar. 2009, and been in the red until 2011. While this performance would have been very disappointing, it is important to remember we only recommend 70% stock allocations for goals expected to be held eight years or longer. To ensure that investors understand and feel comfortable with the short term risk in their portfolios, we present them with both extremely good and extremely poor return scenarios for their selection over a one-year time period.


text:
Essential singularity: Residue at $0$ or $\infty$?

All my doubts came from the following exercise:

Given

$$f(z) = z^3 e^{-\frac{2}{z}}$$

find the singularities of the function in $\bar{\mathbb{C}}$ and specify their nature (removable, pole of order $N$, essential singularities) and the residue at these points.

Solution: $z = 0$ essential singularity, $z = \infty$ pole; $\operatorname{Res}(f(z), 0) = \frac{2}{3} = - \operatorname{Res}(f(z), \infty)$

So I started considering the expansion of $e^z$ about $0$: $$e^z = \sum\limits_{n = 0}^{\infty}\frac{z^n}{n!}$$ and then I substituted $z\to-\frac{2}{z}$ $$e^{-\frac{2}{z}} = \sum\limits_{n = 0}^{\infty}\frac{(-1)^n2^n}{n!}\left(\frac{1}{z}\right)^n$$ Multiplying everything for $z^3$ I get the function $f(z)$ expanded in Laurent series: $$f(z) = \sum\limits_{n = 0}^{\infty}\frac{(-1)^n2^n}{n!}z^{-n+3}$$

Then considering the $c_{-1}$ coefficient I got the residues of the function in $0$: $$\operatorname{Res}(f(z), 0) = \left(\sum\limits_{n = 0}^{\infty}\frac{(-1)^n2^n}{n!}z^{-n+3}\delta_{4}^{n}\right) = \frac{(-1)^42^4}{4!} = \frac{2}{3}$$ where $\delta_j^i$ in the Kronecker delta. Now, since a friend of mine was doing the same exercise he developed a solution expanding the function at $\infty$ and he got the same result as me, with the same sign (so wrong because $\frac{2}{3}$ should be the right in $0$, but not in $\infty$), but now I'm not sure of what I have done, since it appears to me that this expansion is not in $0$ but in $\infty$, so $\frac{2}{3}$ should be the residue of $f(z)$ at $\infty$ and not in $0$ (as my expansion is valid at $\infty$, since is $e^{-\frac{2}{z}}$.

Last I tried computing with Mathematica the series and the result and I got:

Basically Mathematica in $0$ is not computing results, while in $\infty$ it's giving me the same series that I thought I get in $0$, but the residue computed at $\infty$ is the same that I got with my calculations.

What's going on? Am I calculating the series in $\infty$ without knowing? And if it's so, how is it possible that the residue at $\infty$ is the opposite of the $c_{-1}$ at $\infty$?

• I would start by looking at limits where we get singularities points which are $0$ and $\infty$ Now: a. if the limit exists so it is removable singularity b. if the limit is $\pm \infty$ it is a pole and c. if the limit does not exist it is essential singularity – gbox Sep 12 '17 at 11:34

What you did to compute the residue at $0$ is correct.

The residue at $\infty$ is$$-\operatorname{res}_0\left(\frac1{z^2}f\left(\frac1z\right)\right)=-\operatorname{res}_0\left(\frac1{z^2}\cdot\frac1{z^3}e^{-2z}\right)=-\operatorname{res}_0\left(\frac{e^{-2z}}{z^5}\right)=-\frac23.$$

How exactly do you define the residue at $\infty$? A definition I'm working with is: $\DeclareMathOperator{\Res}{Res}$

Let $\infty$ be an isolated singularity of $f$, meaning there exists $R > 0$ such that $f$ is holomorphic at $\mathbb{C}\setminus \overline{B(0,R)}$. Then: $$\Res(f, \infty) = -\frac{1}{2\pi i}\int\limits_{|z|=R} f(z)\,dz$$

Furthermore, $f$ has a Laurent expansion on $\mathbb{C}\setminus \overline{B(0,R)}$:

$$f(z) = \sum_{n=-\infty}^\infty c_nz^n, \quad|z| > R$$ We see that $\Res(f, \infty) = -c_{-1}$.

A result which follows from this definition is:

Let $z_1, \ldots, z_k \in \mathbb{C}$ be all isolated singularities of $f$ and $f$ is holomorphic on $\mathbb{C}\setminus\{z_1, \ldots, z_k\}$. Then: $$\sum_{i=1}^k \Res(f,z_i) + \Res(f, \infty) = 0$$

In your case, $f(z) = z^3e^{-\frac{2}{z}}$ has a Laurent series $$f(z) = \sum_{n = 0}^{\infty}\frac{(-1)^n2^n}{n!}z^{-n+3}, \quad z\ne 0$$ on $\mathbb{C}^\times$ so using this series we get $\Res(f,0) = c_{-1} = \frac{2}{3}$ and $\Res(f, \infty) = -c_{-1} = -\frac{2}{3}$. We verify that $\Res(f,0) + \Res(f,\infty) = 0$, since $0$ is the only isolated singularity of $f$.

Laurent series can't be about $\infty$; they are always about a finite complex number. They are power series, so that's the only thing that makes sense!

However, the same function can have multiple Laurent series that converge in different annuluses. For example, the function $f(z) = \frac{1}{1-z} + \frac{1}{2-z}$ has three different Laurent series centered on $z=0$:

$$\sum_{n=0}^{\infty} \left(1 + 2^{-1-n} \right) z^n \qquad \qquad |z| < 1$$ $$\sum_{n=-\infty}^{-1} (-1) z^n + \sum_{n=0}^{\infty} 2^{-1-n} z^n \qquad \qquad 1 < |z| < 2$$ $$\sum_{n=-\infty}^{-1} (-1 - 2^{-1-n}) z^n \qquad \qquad 2 < |z|$$

When you ask for the series at infinity, what you're telling Mathematica to do is to give you the series for which $\infty$ is in (or on the boundary of) the domain of convergence. Mathematica seems to default to picking 0 as the center when you ask this.

Regarding the series around zero.... I don't think Mathematica explicitly documents its semantics, but presumably what's going on here is that the series command intends to return a finite approximation. For example, something of the sort

$$\frac{1}{1-z} \approx 1 + z + z^2 + O(z^3)$$

The problem with your example is there aren't any finite approximations. The essential singularity means that you need all of the leading terms to get an approximation near $z=0$.

So, what Mathematica does is it instead factors out an analytic function expressing the essential singularity, and then gives a series approximation for what's leftover.

• So my expansion (the one i made with the series of $e^z$) is about $0$ and my method is right? – opisthofulax Sep 12 '17 at 12:08


text:
2 tags edited
1

# interval exchange maps and surfaces

I apologize if the question is a well-known theorem, but I'm just starting to learn about laminations, so I don't know much.

The question is roughly, if interval exchange maps have an underlying closed smooth surface, or if not, what is known about conditions on that.

Now I try to be more precise.

Usual interval exchange functions are bijective functions $\mathbb R/\mathbb Z=S^1\to S^1$ which are piecewise translations where "piecewise" is defined using a finite partition of $S^1$ in segments $s_i$.

Given a interval exchange function $\phi:S^1\to S^1$ one can consider its suspension $S_\phi=[0,1]\times S^1/\sim$ where the nontrivial identifications are $(0,x)\sim (1,\phi(x))$. Then one has a smooth 1-dimensional structure on $S_\phi$, given by the differentiable structure on $[0,1]$, which can be extended with continuity through the identifications. In the $S^1$-direction there is just some piecewise $C^1$-structure on the pieces $]0,1[\times s_i$, since $\phi$ is not even assumed to be continuous.

Then if I understood correctly one defines $\partial S_\phi=\cup_i [0,1]\times\partial s_i/\sim$, and this set is an union of (topological but not $C^1$, since there are cusps) copies of $S^1$. Then one obtains a surface by gluing some annuli to these circles.

The question is if there is some way of obtaining a smooth surface in this way. The case where the lenghts of $s_i$ are rational and $\phi$ is piecewise equal to translations by rational numbers is simple (one refined the segments and gets a longer, smooth, boundary), so I am interested if there is a result in the other case.