text:
# Budget Constraints in Prediction Markets

We give a detailed characterization of optimal trades under budget constraints in a prediction market with a cost-function-based automated market maker. We study how the budget constraints of individual traders affect their ability to impact the market price. As a concrete application of our characterization, we give sufficient conditions for a property we call budget additivity: two traders with budgets B and B' and the same beliefs would have a combined impact equal to a single trader with budget B+B'. That way, even if a single trader cannot move the market much, a crowd of like-minded traders can have the same desired effect. When the set of payoff vectors associated with outcomes, with coordinates corresponding to securities, is affinely independent, we obtain that a generalization of the heavily-used logarithmic market scoring rule is budget additive, but the quadratic market scoring rule is not. Our results may be used both descriptively, to understand if a particular market maker is affected by budget constraints or not, and prescriptively, as a recipe to construct markets.

## Authors

• 5 publications
• 23 publications
• 27 publications
• 16 publications
• ### A New Understanding of Prediction Markets Via No-Regret Learning

We explore the striking mathematical connections that exist between mark...
02/26/2010 ∙ by Yiling Chen, et al. ∙ 0

• ### An Axiomatic Study of Scoring Rule Markets

Prediction markets are well-studied in the case where predictions are pr...
09/28/2017 ∙ by Rafael Frongillo, et al. ∙ 0

• ### Design and Analysis of a Synthetic Prediction Market using Dynamic Convex Sets

We present a synthetic prediction market whose agent purchase logic is d...
01/05/2021 ∙ by Nishanth Nakshatri, et al. ∙ 0

• ### Comparing Prediction Market Structures, With an Application to Market Making

Ensuring sufficient liquidity is one of the key challenges for designers...
09/08/2010 ∙ by Aseem Brahma, et al. ∙ 0

• ### Learning Performance of Prediction Markets with Kelly Bettors

In evaluating prediction markets (and other crowd-prediction mechanisms)...
01/31/2012 ∙ by Alina Beygelzimer, et al. ∙ 0

• ### The Possibilities and Limitations of Private Prediction Markets

We consider the design of private prediction markets, financial markets ...
02/24/2016 ∙ by Rachel Cummings, et al. ∙ 0

• ### Markets for Efficient Public Good Allocation

Public goods are often either over-consumed in the absence of regulatory...
05/21/2020 ∙ by Devansh Jalota, et al. ∙ 0

##### 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

A prediction market is a central clearinghouse for people with differing opinions about the likelihood of an event—say Hillary Clinton to win the 2016 U.S. Presidential election—to trade monetary stakes in the outcome with one another. At equilibrium, the price to buy a contract paying $1 if Clinton wins reflects a consensus of sorts on the probability of the event. At that price, and given the wagers already placed, no agent is willing to push the price further up or down. Prediction markets have a good track record of forecast accuracy in many domains [11, 19]. The design of combinatorial markets spanning multiple logically-related events raises many interesting questions. What information can be elicited—the full probability distribution, or specific properties of the distribution? What securities can the market allow traders to buy and sell? How can the market support and ensure a variety of trades? For example, in addition to the likelihood of Clinton winning the election, we may want to elicit information about the distribution of her electoral votes. 111 A U.S. Presidential candidate receives a number of electoral votes between 0 and 538. The candidate who receives a plurality of electoral votes wins the election. If we create one security for each possible outcome between 0 and 538, each paying$1 iff Clinton gets exactly that many electoral votes, the market is called complete, allowing us to elicit a full probability distribution. Alternatively, if we create just two securities, one paying out $if Clinton wins electoral votes, and the other paying out$

, we cannot elicit a full distribution, but we can still elicit the mean and variance of the number of electoral votes.

When agents are constrained in how much they can trade only by risk aversion, prediction market prices can be interpreted as a weighted average of traders’ beliefs [20, 2], a natural reflection of the “wisdom of the crowd” with a good empirical track record [14] and theoretical support [2]. However, when agents are budget constrained, discontinuities and idiosyncratic results can arise [16, 7] that call into question whether the equilibrium prices can be trusted to reflect any kind of useful aggregation.

We consider prediction markets with an automated market maker [1, 13, 4] that maintains standing offers to trade every security at some price. Unlike a peer-to-peer exchange, all transactions route through the market maker. The common market makers have bounded loss and are (myopically) incentive compatible: the best (immediate) strategy is for a trader to move the market prices of all securities to equal his own belief. The design of such an automated market maker boils down to choosing a convex cost function [1]. This amount of design freedom presents an opportunity to seek cost functions that satisfy additional desiderata such as computational tractability [1, 6].

Most of the literature assumes either risk-neutral or risk-averse traders with unbounded budgets. In this paper, we consider how agents with budget constraints trade in such markets, a practical reality in almost all prediction markets denominated in both real and virtual currencies. Our results help with a systematic study of the market’s liquidity parameter, or the parameter controlling the sensitivity of prices to trading volume. Setting the liquidity is a nearly universal practical concern and, at present, is more (black) art than science. We adopt the notion of the “natural budget constraint” introduced by Fortnow and Sami [8]: the agent is allowed only those trades for which the maximum loss for any possible outcome does not exceed the budget.

Of greatest practical interest is the application of our results to markets consisting of several independent questions, with each question priced according to a separate logarithmic market scoring rule. This setup constitutes a de facto industry standard, and the companies that use (or used) it include Inkling Markets, Consensus Point, Microsoft and Yahoo! [17]. Our Theorems 5.6 and 5.8 show that these markets are budget additive.

Previously, Fortnow and Sami [8] considered a different question: do budget-constrained bidders always move the market prices in the direction of their beliefs? They showed that the answer to this is no: there always exist market prices, beliefs and budgets such that the direction of price movement is not towards the belief. We give a richer characterization of how the market prices move in the presence of budget constraints, by charting the path the prices take with increasing budgets. The impossibility result of Fortnow and Sami [8] can be easily derived from our characterization (see Appendix D).444The full version of this paper on arXiv includes the appendix.

A designer of a prediction market has a lot of freedom but little guidance, and our results can be used both descriptively and prescriptively. As a descriptive tool, our results enable us to analyze commonly used market makers and understand if budget constraints hamper information aggregation in these markets. As a prescriptive tool, our results can be used to construct markets that are budget additive. In particular, we speculate that budget additivity simplifies the choice of the liquidity parameter in the markets, because it allows considering trader budgets in aggregate.

Proof overview and techniques. Our analysis borrows heavily from techniques in convex analysis and builds on the notion of Bregman divergence. We use the special case of Euclidean distance (corresponding to a quadratic market scoring rule) to form our geometric intuition which we then extend to arbitrary Bregman divergences. For the sake of an example, consider a complete market over a finite set of outcomes, where the market prices lie in a simplex, exactly coinciding with the set of probability distributions over outcomes. Every possible outcome imposes a constraint on the set of prices to which a trader can move the market, because the trader is not allowed to exceed the budget if that outcome occurs. The prices satisfying this constraint form a ball with the outcome at its center. The set of feasible prices to which the trader can move the market is therefore the intersection of these balls (see Figure 1).

The key structural result we obtain is the chart of the price movement. Suppose that there is an infinite sequence of agents with infinitesimally small budgets all with the same belief. What is the path along which the prices move from some initial values? This is determined by the agents’ belief and the set of budget constraints that are tight at any point, corresponding to the highest risk outcomes (outcomes with the highest potential loss). We show that the price vector can always be written as a convex combination of these highest risk outcomes and the agents’ belief. Further, the market prices move in a direction that is perpendicular to the affine space of these outcomes.

The agents’ belief partitions the simplex interior into regions, where each region is the interior of the convex hull of the agent belief and a particular subset of outcomes. For a region that is full-dimensional, every interior point can be uniquely written as a convex combination of the agent belief and all except one outcome. Assume that the current price vector lies in this region. In the anticipation of the further development, we call this outcome profitable and others risky. Motivated by the characterization above, we move perpendicular to the risky outcomes in the direction towards the agents’ belief. As a result, we increase the risk of risky outcomes (equally for all outcomes), while getting closer to the one profitable outcome (and hence increasing its profit). The characterization then guarantees that the prices along this path are indeed those chosen by traders at increasing budgets, because the risky outcomes yield tight constraints.

We would like the same to be true for the lower dimensional regions as well; that is, for the set of tight constraints to be exactly the corresponding set of outcomes defining the convex hull. In fact, this property is sufficient to guarantee budget additivity. The markets for which the tight constraints are exactly the minimal set of outcomes that define the region the price lies in are budget additive. (We conjecture that the converse holds as well.) The entire path is then as follows: w.l.o.g. you start at a full-dimensional region, move along the perpendicular until you hit the boundary of the region and you are in a lower-dimensional region, move along the perpendicular in this lower-dimensional region, and so on until you reach the belief (see Figure 1). The set of tight constraints is monotonically decreasing. We show that such markets are characterized by a certain acute angles assumption on the set of possible outcomes. Loosely speaking, this assumption guarantees that outcomes outside the minimal set behave as the profitable outcome in the above example.

Other related work. There is a rich literature on scoring rules and prediction markets. Two of the most studied scoring rules are the quadratic scoring rule [3] and the logarithmic market scoring rule [13]. We consider cost-function-based prediction markets [12, 4], a fully general class under reasonable assumptions [1, 5]. Their equivalence with proper scoring rules has been implicitly noted by Gneiting and Raftery [10]. Several authors have studied relationships between utility functions and price dynamics in prediction markets, drawing a parallel to online learning [5, 2, 9]. Our analysis touches on the problem of setting the market maker’s liquidity parameter [17, 15], which determines how (in)sensitive prices are to trading volume. With budget additivity, the market designer can optimize liquidity according to aggregate budgets, without worrying about how budgets are partitioned among traders.

## 2 Preliminaries

Securities and payoffs. Consider a probability space with a finite set of outcomes . A security is a financial instrument whose payoff depends on the realization of an outcome in

. In other words, the payoff of a security is a random variable of the probability space. We consider trading with

securities corresponding to coordinates of the outcomes . A security can be traded before the realization is observed with the intention that the price of a security serves as a prediction for the expected payoff, i.e., the expected value of the corresponding coordinate.

Cost function, prices and utilities. An automated market maker always offers to trade securities, for the right price. In fact the price vector is the current prediction of the market maker for the expectation of . A cost function based market maker is based on a differentiable convex cost function, . It is a scalar function of an -dimensional vector representing the number of outstanding shares555We allow trading fractions of a security. Negative values correspond to short-selling. for our securities. We also refer to as the state of the market.

The vector of instantaneous prices of the securities is simply the gradient of at , denoted by The prices of securities change continuously as the securities are traded, so it is useful to consider the cost of trading a given quantity of securities. The cost of buying units of securities (where a negative value corresponds to selling) is determined by the path integral , where is any smooth curve from to .

When the outcome is realized, the vector of units of securities pays off an amount of . Thus, the realized utility of a trader whose trade moved the market state from to is

 U(q′,ω;q)\coloneqq(q′−q)⋅ω−C(q′)+C(q).

We make a standard assumption that the maximum achievable utility, which is also the maximum loss of the market maker, is bounded by a finite constant (in Section 4, we introduce a standard approach to check this easily). Let be the convex hull of the payoff vectors, . It is easy to see that contains exactly the vectors which can be realized as expected payoffs for some probability distribution over . For a trader who believes that , the expected utility takes form

 U(q′,μ;q)\coloneqqE[U(q′,ω;q)]=(q′−q)⋅μ−C(q′)+C(q).

Throughout, we consider a single myopic trader who trades as if he were the last to trade. A key property satisfied by expected utility is path independence: for any , , that is, risk-neutral traders have no incentive to split their trades. For a risk-neutral trader, is an optimal action if and only if (this follows from the first-order optimality conditions). In other words, the trader is incentivized to move the market to the prices corresponding to his belief as long as such prices exist. In general, there may be multiple states yielding the same prices, so the inverse map returns a set, which can be empty if no state yields the price vector .

Commonly-used cost functions include the quadratic cost, logarithmic market-scoring rule (LMSR) and the log-partition function. They are described in detail in Appendix A. The quadratic cost is defined by and . Log-partition function is defined as . It subsumes LMSR as a special case for the complete market with the outcomes corresponding to vertices of the simplex. The prices under log-partition cost correspond to the expected value of under the distribution over , i.e., .

Budget constraints. Trading in prediction markets needs an investment of capital. It is possible that an agent loses money on the trade, in particular could be negative for some . One restriction on how an agent trades could be that he is unable to sustain a big loss, due to a budget constraint. We consider the notion of natural budget constraint defined by Fortnow and Sami [8] which states that the loss of the agent is at most his budget, for all . Given a starting market state and a budget of , a trader with the belief then solves the problem:

 maxq∈Rn U(q,μ;q0) (2.1) \ s.t.\ U(q,ω;q0)≥−B∀ω∈Ω.

For quadratic costs, each constraint corresponds to a sphere with one of the outcomes at its center, so the feasible region is an intersection of these spheres. We will later see that this generalizes to an intersection of balls w.r.t. a Bregman divergence for general costs.

In general, there may be multiple optimizing this objective. In the following definition we introduce notation for various solution sets we will be analyzing. The belief is fixed throughout most of the discussion, so we suppress the dependence on .

###### Definition 2.1 (Solution sets).

Let denote the set of solutions of Convex Program (2.1) for a fixed initial state and budget. Let denote the set of solutions of (2.1) for a fixed initial state across all budgets. Let denote the set of states that optimize (2.1) for some budget and yield the market price vector .

The next theorem shows that solutions for a fixed initial state and budget always yield the same price vector. It is proved in Appendix B.

###### Theorem 2.2.

If , then .

Geometry of linear spaces. We finish this section by reviewing a few standard geometric definitions we use in next sections. Let . Then denotes the affine hull of the set (i.e., the smallest affine space including ). We write to denote the orthogonal complement of : . We use the convention . A set is called a cone if it is closed under multiplication by positive scalars. If a cone is convex, it is also closed under addition. Since is finite, the realizable set is a polytope. Its boundary can be decomposed into faces. More precisely, , , forms a face of if is the set of maximizers over of some linear function.666Strictly speaking, this is the definition of an exposed face, but all faces of a polytope are exposed, so the distinction does not matter here. The exposed face is typically defined to be , but in this paper, it is more convenient to work with directly. We also view as a face of . With this definition, for any two faces , , also their intersection is a face.

## 3 Characterizing Solution Sets

We start with the optimality (KKT) conditions for the Convex Program (2.1), as characterized by the next lemma. One of the key conditions is that the solution prices must be in the convex hull of the belief and all the ’s for which the budget constraints are tight. The set of tight constraints is always a face of the polytope . We allow an empty set as a face, which corresponds to the case when none of the constraints are tight and the solution prices coincide with . The proof follows by analyzing KKT conditions (see Appendix C of the full version for details).

###### Lemma 3.1 (KKT lemma).

Let . Then if and only if there exists a face such that the following conditions hold:

1. [label=(),topsep=0pt]

2. , or equivalently
, for all

3. , or equivalently
, for all ,

4. for all if , or
if

where conditions 1 and 2 hold vacuously for .

The condition 1 requires that be orthogonal to the active set . The set of points satisfying conditions 1 and 3 will be called the Bregman perpendicular and will be defined in the next section. The condition 2 is a statement about acuteness of the angle between (the perpendicular) and the outcomes. It will be the basis of our acute angles assumption. The condition 4 just states how the budget is related to the active set .

Witness cones and minimal faces. We now introduce some notation to help us state reinterpretations of the conditions in Lemma 3.1. First of all, given a face , what is the set of ’s that satisfy conditions 1 and 2? This is captured by what we call the witness cone.

###### Definition 3.2.

The witness cone for a face is defined as if , and if .

The following two properties of witness cones are immediate from the definition:

• [topsep=0pt]

• Anti-monotonicity: if , then .

• Orthogonality: .

A state satisfies conditions 1 and 2 for a given face if and only if . Now given a state , consider the set of faces that could satisfy condition 3. This set has a useful structure, namely that there is a unique minimal face (proved in Appendix C of the full version).

###### Definition 3.3.

Given a price vector , the minimal face for is the minimal face (under inclusion) s.t. . The minimal face for is denoted as .

With the existence of a minimal face and the anti-monotonicity of the witness sets, it follows that if and satisfy conditions 1, 2 and 3, then so do and . Thus we obtain the following version of Lemma 3.1 (proved in Appendix C of the full version).

###### Theorem 3.4 (Characterization of Solution Sets).

if and only if .

Using Theorem 3.4, we immediately obtain a characterization of when a price vector could be the price vector of an optimal solution to (2.1).

###### Corollary 3.5.

. In particular, is the price vector of an optimal solution to (2.1) if and only if

We now study an example using the above characterization. More examples can be found in Appendix E of the full version.

###### Example 3.6 (Quadratic cost on an obtuse triangle; see Example e.2 in the full version for details).

Consider the following outcome space, belief, and the sequence of market states (depicted in Figure 2):

 ω1=(0.0,0.0)q0=ν0=1114ω2+314ω3ω2=(1.8,0.0)q1=ν1=13ω2+23μω3=(6.0,4.2)q2=ν2=19ω1+89μμ=qμ=(2.7,1.8)q3=ν3≈119ω1+1819μ

Using the KKT lemma, we can show for , that is an optimal action at under belief , with the corresponding budgets as:

 ω1 ω2 ω3U(q1,⋅;q0)0.45 −0.09 −0.09B01=0.09U(q2,⋅;q1)−0.56 −0.56 1.12B12=0.56U(q3,⋅;q2)−0.565 −0.28… 0.82…B23=0.565U(qμ,⋅;q0)−1.215 −1.215 2.565B0μ=1.215

The above table also shows that the budget suffices to move directly from to . However, note that the sum but , i.e., after the sequence of optimal actions with budgets , , and , the market is still not at the belief shared by all agents, even though with the budget , it would have reached it.

The above example suggests that multiple traders with the same belief may have less power in moving the market state towards their belief compared to a single trader with the same belief and the combined budget. Since prediction markets aim to efficiently aggregate information from agents, it is natural to ask under what conditions multiple traders with the same beliefs do have a combined impact equal to a single trader with the combined budget.

Next, we formally define this property as budget additivity. We then define the Euclidean version of the acute angles condition that we show is sufficient for budget additivity.

We say that a prediction market is budget additive on if for all beliefs and all initial states the following holds: For any budgets and any sequence of solutions and , we have and .

In other words, the market is budget additive if the sequence of optimal actions of two agents with the same belief and budgets and is also an optimal action of a single agent with the same belief and a larger budget . Thanks to Theorem 2.2 we then also obtain that the price vector following the sequence of optimal actions by the two agents is the same as the price vector after the optimal action by an agent with the combined budget (all with the same beliefs).

We now state the acute angles assumption for the Euclidean case, to give an intuition. Our acute angles assumption (Definition 5.1) is a generalization of this. We later show that the acute angles property is sufficient for budget additivity (Theorem 5.2).

###### Definition 3.8.

We say that the Euclidean acute angles hold for a face , if the angle between any point , its projection on the affine hull of and any payoff is non-obtuse (the angle is measured at the projection).

Based on the above example, one may hypothesize that the obtuse angles are to blame for the lack of budget additivity. In the following sections we will show that this is indeed the case, but that the notion of obtuse/acute angles depends on the Bregman divergence. In particular, the above example would have been budget-additive if we used the log-partition cost instead of the quadratic cost.

## 4 Bregman Divergence and Perpendiculars

We will see next that the utility function can be written as the difference of two terms measuring the distance between the belief and the market state before and after the trade. This distance measure is the mixed Bregman divergence.777Our notion of Bregman divergence is more general than typically assumed in the literature. To define the Bregman divergence, first let be the convex conjugate of defined as Since is a supremum of linear functions, it is convex lower semi-continuous. Up to a constant, it characterizes the maximum achievable utility on an outcome for a fixed initial state as . The term in the brackets is always finite, but might be positive infinite. We make a standard assumption that for all , i.e., that the maximum achievable utility, which is also the maximum loss of the market maker, is bounded by a finite constant. By convexity, this implies that for all . The Bregman divergence derived from is a function measuring the maximum expected utility under belief at a state

 D(q,μ)\coloneqqC(q)+C∗(μ)−q⋅μ=supq′∈RnU(q′,μ;q).

From the convexity of and and the definition of , it is clear that: (i) is convex and lower semi-continuous in each argument separately; (ii) is non-negative; and (iii) is zero iff . By the bounded loss assumption, Bregman divergence is finite on . For , we can write

 U(q′,μ;q)=D(q,μ)−D(q′,μ). (4.1)

Thus, maximizing the expected utility is the same as minimizing the Bregman divergence between the state and the belief . From Eq. (4.1) it is also clear that each constraint in (2.1) is equivalent to , and the geometric interpretation is that the agent seeks to find the state closest to his belief, within the intersection of Bregman balls

For the quadratic cost, we have and , i.e., the Bregman divergence coincides with the Euclidean distance squared. For log-partition cost, we have where is the distribution maximizing entropy among satisfying . The Bregman divergence is the KL-divergence between and : .

Convex analysis. We overview a few standard definitions and results from convex analysis. For , we write for the relative interior of (i.e., the interior relative to the affine hull). For a convex function , we define its effective domain as (i.e., the set of points where it is finite). The subdifferential of at a point is the set . We say that is subdifferentiable at if . A standard result of convex analysis states that is always subdifferentiable on a superset of . If is not only convex, but also lower semi-continuous, then and are inverses in the sense that iff . If is differentiable everywhere on , then is strictly convex on .

Let denote the set of prices that can be expressed by market states. The implications for our setting are that: (i) is subdifferentiable on ; (ii) for all ; (iii) all beliefs in can be expressed by some state ; (iv) is strictly convex on , and similarly is strictly convex on as a function of the second argument.

Assumptions on the cost function.

• [topsep=0pt]

• Convexity and differentiability on . is convex and differentiable on .

• Finite loss. , i.e., is finite on .

• Inclusion of the relative interior. .

The first two assumptions are standard. The third assumption is a regularity condition that we require in our results. Here we briefly discuss how it compares with the finite loss assumption. While the two assumptions look similar, neither of them implies the other. For example, if is an -dimensional simplex and is one of its lower dimensional faces, which are lower dimensional simplices, then the finite loss assumption holds, but the inclusion assumption does not. Similarly, for and , the inclusion assumption is satisfied by the conjugate on and on , but this conjugate does not satisfy the finite loss assumption.

We do not view the inclusion assumption as very restrictive, since it is satisfied by many common cost functions. For instance, it always holds when is constructed as in [1], because their construction guarantees . However, the inclusion assumption might not hold for cost functions that allow arbitrage (e.g., [6]).

Our main result relies on strict convexity of on , so some of our statements will require that the market prices and beliefs lie in that set. The inclusion assumption above guarantees that at the minimum , but the boundary of is not necessarily included. To allow some generality beyond , we define the set

 ~M\coloneqq{Mif M⊆ridomC∗riMotherwise.

In either case we obtain that , i.e., beliefs in can be expressed by some state . For the quadratic cost, . For the log-partition cost, .

Perpendiculars. We now define the notion of a Bregman perpendicular to an affine space. This is a constructive definition. It plays a central role in the definition of the acute angles assumption, and also in the proof of the main result (Theorem 5.2). We will see that the set of optimal price vectors for different budgets is a sequence of Bregman perpendiculars. Naturally, perpendiculars are closely related to the conditions in Lemma 3.1; in particular to the set of ’s that satisfy conditions 1 and 3 for a given face .

For quadratic costs, Bregman perpendiculars coincide with the usual Euclidean perpendiculars. Consider an affine space and a point not in it. A projection of the point onto the space is the point in the space that is closest in Euclidean distance to the given point. Now consider moving this affine space towards the projected point. The locus of the projection as we move the space is the perpendicular to the space through the given point. We extend this definition to arbitrary Bregman divergences by defining the projection using the corresponding Bregman divergence.

A Bregman perpendicular is determined by three geometric objects within the affine hull . The first of these is an affine space, say . The second is a point . The affine space will be the ambient space that will contain the perpendicular. Define parallel spaces to in , for an arbitrary point , as for . Note that the definition of is independent of the choice of . The third geometric object is a market state such that . For technical reasons, we will define a perpendicular at rather than a more natural notion, which would be at . Our reason for switching into -space is that inner products, defining optimality of the Bregman projection, are between elements of -space and -space (the two spaces coincide for Euclidean distance). For all define a Bregman projection of onto as

 νλ\coloneqqargminν∈AλD(q,ν).

Since is bounded from below and lower semi-continuous, the minimum is always attained (but it may be equal to ). If it is attained at more than one point, we choose an arbitrary minimizer. Whenever we can choose , this must be the unique minimizer by strict convexity of on , and the minimum is finite. We use these ’s to define the perpendicular:

###### Definition 4.1.

Given , and as above, the -perpendicular to at is a map defined over . We call the domain of the perpendicular. We define a total order on as iff .

In Appendix F.2 of the full version, we show that perpendiculars are continuous maps. The name perpendicular is justified by the following proposition which matches our Euclidean intuition that the perpendiculars can be obtained by intersecting the ambient space with the affine space which passes through and is orthogonal to . It also shows that the perpendicular corresponds to the set of prices that satisfy conditions 1 and 3 with the convex hull relaxed to the affine hull (when is the affine hull of face , point coincides with and is the initial state). Recall that for an arbitrary set , its orthogonal complement is defined as .

###### Proposition 4.2.

Let be the -perpendicular to at , and let . The following two statements are equivalent for any :

• [topsep=0pt]

• ,

Proposition 4.2 is proved in Appendix F of the full version. The perpendiculars have the following closure property which is useful for showing budget additivity (also proved in Appendix F of the full version):

###### Proposition 4.3.

Under the assumptions of Proposition 4.2, is also the -perpendicular to at any .

We now state the acute angles property which links the Bregman perpendicular and Corollary 3.5, and is sufficient for budget additivity.

###### Definition 5.1.

We say that the acute angles hold for a face , if for every -perpendicular to at , such that and , the following holds: If and , then .

The motivation for the name “acute angles” comes from the Euclidean distance case, where this assumption is equivalent to Definition 3.8 (see Proposition G.1 in the full version). The acute angles property is non-trivial and we have seen that without this property, budget additivity need not hold; we conjecture that it is also a necessary condition. After stating the main theorem, we analyze in more detail when the acute angles are satisfied by the quadratic and log-partition costs.

We now state the main result, that the acute angles are sufficient for budget additivity:

###### Theorem 5.2 (Sufficient conditions for budget additivity).

If acute angles hold for every face , then the prediction market is budget additive on .

Sufficient conditions for acute angles. We next give the sufficient conditions when the acute angles hold for the quadratic and log-partition cost functions. We also show that the acute angles hold for all one-dimensional outcome spaces, and that they are preserved by taking direct sums of markets. Recall that a set is called a cone if it is closed under multiplication by positive scalars. A cone is called acute, if for all . An affine cone with the vertex is a set of the form where is a cone.

###### Theorem 5.3 (Sufficient condition for quadratic cost).

Let be a face and be the affine space for an arbitrary . Acute angles hold for the face and the quadratic cost if and only if the projection of (or, equivalently, ) on is contained in an affine acute cone with the vertex .

###### Corollary 5.4.

Acute angles hold for the quadratic cost and a hypercube .

###### Corollary 5.5.

Acute angles hold for the quadratic cost and simplex where and is the -th vector of the standard basis in .

###### Theorem 5.6 (Log-partition over affinely independent outcomes).

If the set is affinely independent then acute angles assumption is satisfied for the log-partition cost.

###### Theorem 5.7 (One-dimensional outcome spaces).

Acute angles hold for any cost function if is a line segment.

Let and be outcome spaces with costs and . We define the direct sum of and to be the outcome space with the cost defined as .

###### Theorem 5.8 (Acute angles for direct sums).

If acute angles hold for with cost , and with cost , then they also hold for their direct sum.

As a direct consequence of this theorem, we obtain that the log-partition cost function satisfies the acute angles assumption on a hypercube. More generally, any direct sum of costs on line segments satisfies the acute angles. This means that all cost-based prediction markets consisting of independent binary questions are budget additive, regardless of costs used to price individual questions.

As mentioned in the introduction, a vast number of deployed cost-based prediction markets consists of independent questions (not necessarily binary), each priced according to an LMSR (i.e., a log-partition cost on a simplex). Theorems 5.6 and 5.8 imply that this industry standard is budget additive.

### 5.1 Proof of Theorem 5.2

In this section we sketch the proof of Theorem 5.2 (for a complete proof see Appendix H of the full version). We proceed in several steps. Let . Assuming acute angles, we begin by constructing an oriented curve joining with , by sequentially choosing portions of perpendiculars for monotonically decreasing active sets. We then show that budget additivity holds for any solutions with prices in , and finally show that the curve is the locus of the optimal prices of solutions , as well as optimal prices of solutions for any .

Part 1: Construction of the solution path . In this part, we construct:

• [topsep=0pt]

• a sequence of prices with and

• a sequence of oriented curves where each goes from to

• a monotone sequence of sets , such that the following minimality property holds: is the minimal face for all for , and is the minimal face for .

• a sequence of states such that

The curves will be referred to as segments. The curve obtained by concatenating the segments through will be called the solution path and denoted . In the special case that , we have , and is a degenerate curve with .

If , we construct the sequence of segments iteratively. Let be the minimal face such that . By the minimality, . Let be the -perpendicular to at . The curve passes through and eventually reaches the boundary of at some by continuity of (see Theorem F.3). Let segment be the portion of going from to .

This construction gives us the first segment . There are two possibilities:

1. [topsep=0pt]

2. ; in this case we are done;

3. lies on a lower-dimensional face of ; in this case, we pick some , which can be done by the acute angles assumption, and use the above construction again, starting with , and obtaining a new set and a new segment ; and iterate.

The above process eventually ends, because with each iteration, the size of the active set decreases. This construction yields monotonicity of and the minimality property.

The above construction yields a specific sequence of . We show in Appendix H of the full version that actually and that the construction of is independent of the choice of .

Part 2: Budget additivity for points on . Let such that . Let and such that and . In this part we show that .

First, consider the case that . To see that , first note that the constraints of Convex Program (2.1) hold, because for all by path independence of the utility function. As noted in the introduction, in the absence of constraints, the utility is maximized at any with . Thus, is a global maximizer of the utility and satisfies the constraints, so . If , we must also have and the statement holds by previous reasoning.

In the remainder, we only analyze the case . This means that and for . By Theorem 3.4, we therefore must have and . By anti-monotonicity of witness cones, and hence, , yielding

We now argue that the budgets add up. Let . By Lemma 3.1, we obtain that for , and for , and finally for . However, by path independence of the utility function

 ¯B=−U(q′,x;q0)=−U(q′,x;q)−U(q,x;q0)=B′+B.

Part 3: as the locus of all solutions. See Appendix H of the full version for the proof that

 ^Q(q0)=⋃ν∈imL^Q(ν;q0).

Part 3’: as the locus of solutions starting at a midpoint. Let and . Since , Part 1’ (Appendix H of the full version) yields that the solution path for coincides with the portion of starting at . Applying the proof of Part 3 to , we obtain

 ^Q(q)=⋃ν′∈imL:ν′⪰ν^Q(ν′;q).

Part 4: Proof of the theorem. Let and and . From Parts 3 and 3’, we know that and for some such that . By Part 2, we therefore obtain that , proving the theorem.

## References

• Abernethy et al. [2011] Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan. An optimization-based framework for automated market-making. In ACM Conference on Electronic Commerce, pages 297–306, 2011.
• Beygelzimer et al. [2012] Alina Beygelzimer, John Langford, and David M. Pennock. Learning performance of prediction markets with Kelly bettors. In International Conference on Autonomous Agents and Multiagent Systems, pages 1317–1318, 2012.
• Brier [1950] GW Brier. Veriﬁcation of forecasts expressed in terms of probability. Monthly Weather Review, 78:1–3, 1950.
• Chen and Pennock [2007] Yiling Chen and David M. Pennock. A utility framework for bounded-loss market makers. In

Conference on Uncertainty in Artificial Intelligence

, pages 49–56, 2007.
• Chen and Wortman Vaughan [2010] Yiling Chen and Jennifer Wortman Vaughan. A new understanding of prediction markets via no-regret learning. In ACM Conference on Electronic Commerce, pages 189–198, 2010.
• Dudík et al. [2012] Miroslav Dudík, Sébastien Lahaie, and David M. Pennock. A tractable combinatorial market maker using constraint generation. In ACM Conference on Electronic Commerce, 2012.
• Eisenberg and Gale [1959] Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. Annals of Mathematical Statistics, 30:165–168, 1959.
• Fortnow and Sami [2012] Lance Fortnow and Rahul Sami. Multi-outcome and multidimensional market scoring rules. CoRR, abs/1202.1712, 2012.
• Frongillo et al. [2012] Rafael Frongillo, Nicolas Della Penna, and Mark Reid. Interpreting prediction markets: a stochastic approach. In Advances in Neural Information Processing Systems 25, pages 3275–3283. 2012.
• Gneiting and Raftery [2007] Tilmann Gneiting and Adrian E Raftery.

Strictly proper scoring rules, prediction, and estimation.

Journal of the American Statistical Association, 102(477):359–378, 2007.
• Goel et al. [2010] Sharad Goel, Daniel M. Reeves, Duncan J. Watts, and David M. Pennock. Prediction without markets. In ACM Conference on Electronic Commerce, pages 357–366, New York, NY, USA, 2010. ACM.
• Hanson [2003] Robin Hanson. Combinatorial information market design. Information Systems Frontiers, 5(1):107–119, 2003.
• Hanson [2007] Robin Hanson. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets, 1(1):3–15, February 2007.
• Jacobs [1995] Robert A. Jacobs. Methods for combining experts’ probability assessments. Neural Computation, 7(5):867–888, September 1995.
• Li and Wortman Vaughan [2013] Xiaolong Li and Jennifer Wortman Vaughan. An axiomatic characterization of adaptive-liquidity market makers. In ACM Conference on Electronic Commerce, 2013.
• Manski [June 2006] Charles F. Manski. Interpreting the predictions of prediction markets. Economics Letters, 91(3):425–429, June 2006.
• Othman et al. [2010] Abraham Othman, Tuomas Sandholm, David M. Pennock, and Daniel M. Reeves. A practical liquidity-sensitive automated market maker. In ACM Conference on Electronic Commerce, 2010.
• Rockafellar [1970] R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, Princeton, New Jersey, 1970.
• Wolfers and Zitzewitz [2004] Justin Wolfers and Eric Zitzewitz. Prediction markets. Journal of Economic Perspectives, Winter, 2004.
• Wolfers and Zitzewitz [2006] Justin Wolfers and Eric Zitzewitz. Interpreting prediction market prices as probabilities. IZA Discussion Papers 2092, Institute for the Study of Labor (IZA), April 2006.

## Appendix A Examples of Cost Functions

The first example of a cost function, applicable to arbitrary outcome sets , is the quadratic cost function defined by . In this case, , and . It is clear that the expected utility is maximized when .

Convex conjugate and Bregman divergence: and , i.e., the Bregman divergence is a monotone transformation of the Euclidean distance.

###### Example A.2 (Lmsr).

Our second example is Hanson’s logarithmic market-scoring rule (LMSR) [12, 13], which is applied to complete markets whose outcomes coincide with basis vectors, i.e., where denotes the -th basis vector and denotes the set . In this case is the simplex in and beliefs are in one-to-one correspondence with probability distributions over . The LMSR cost function is

 C(q)=ln(∑ni=1eq[i])

where denotes the -th coordinate of . The price vector is

 p(q)[i]=∂C(q)∂q[i]=eq[i]∑nj=1eq[j]=eq[i]−C(q).

For , the expected utility function takes form

 U(q′,μ;q) =n∑i=1μ[i](lnp(q′)[i]−lnp(q)[i]) =KL(μ∥p(q))−KL(μ∥p(q′)),

where is the KL-divergence. KL-divergence is not symmetric, but it is non-negative, and zero only if the arguments are equal. Thus, the expected utility is clearly maximized if and only if .

Convex conjugate and Bregman divergence: if is not a probability measure on , and otherwise, with the convention . The Bregman divergence is .

###### Example A.3 (Log-partition cost).

Next example is the log-partition function, which is applicable to arbitrary outcome sets and which generalizes LMSR:

 C(q)=ln(∑ω∈Ωeq⋅ω).

Let be the probability measure over defined by

 Pq(ω)=eq⋅ω−C(q).

The prices then correspond to expected values of under :

 p(q)=∑ω∈ΩPq(ω)ω.

For , let denote the distribution of maximum entropy among with (this distribution is unique and always exists). Note that we are overloading notation on and and use the “type” of the subscript to indicate which probability distribution we have in mind. The expected utility function can be written as

 U(q′,μ;q) =(q′−q)⋅Eω∼Pμ[ω]−C(q′)+C(q) =Eω∼Pμ[lnPq′(ω)−lnPq(ω)] =Eω∼Pμ[ln(Pμ(ω)Pq(ω))−ln(Pμ(ω)Pq′(ω))] =KL(Pμ∥Pq)−KL(Pμ∥Pq′).

A standard duality result shows that the infimum of over the set


text:
Couple questions about complex integrals

1. Apr 15, 2005

cAm

we recently started integrals over the complex plane, in complex analysis. But, im confused on the iterpretation of some of it. From what i've heard/understand, there Is no geometrical interpretation of a complex integral. Why is this? Also, why is it 'illegal' to do an indefinate integral. What's the difference between doing that, and an antiderivative?

2. Apr 18, 2005

cAm

small bump?

3. Apr 19, 2005

HallsofIvy

"From what i've heard/understand, there Is no geometrical interpretation of a complex integral. Why is this? Also, why is it 'illegal' to do an indefinate integral. "

I can't answer this because I've never heard either of those things. Certainly, a complex function of a complex variable would have to be represented in 4 dimensions. Perhaps that is what was meant- 4 dimension geometry is hard to imagine!
The indefinite integral of f(z)= 2z is z2+ C whether z is a real variable or complex. Nothing "illegal" about that!

4. Apr 19, 2005

cAm

hmm... we've beent tought that indefinate integrals are undefined, though we can do antiderivatives.

And, do you know what the geometrical representation is, even if it is hard to conceptualize in 4d?

5. Apr 19, 2005

HallsofIvy

"hmm... we've beent tought that indefinate integrals are undefined, though we can do antiderivatives"

Indefinite integrals ARE anti-derivatives.

6. Apr 19, 2005

cAm

That's what i always thought, but my teacher is specifically saying that if we use an 'indefinate integral' then we'll lose some points. Whereas, an antiderivative is fine.

7. Apr 20, 2005

James Jackson

4d geometry is a good thinking exercise to try and visualise. Right, imagine a function that takes and returns a real number (ie it exists on the 'normal' number line). You can represent this as a line on a 2d graph, with aeis, say, x and y being at a $$90^\circ$$ angle to each other. In this 2 dimensional space, the axes x and y are said to be orthogonal - finding out the x position of a point gives you no information on the y position. You then extend this to three dimensions, we get the x, y and z axes. Again, knowledge of a point in 3D's position on one axis contains no information about the point's position on the other two axes - the three axes are again orthogonal.

Now think of this - you can project a 3D graph onto a 2D graph by taking a slice through at, say, a given Z value. For example, a sphere in 3d withh describe either nothing, a circle or a point when projected for a given 'slice' into 2D.

This all works nice and easy because we live in 3D. The conceptual leap comes when you consider 4 orthogonal axes. In a function taking and returning complex values we require 4 values to describe the function's behaviour:

$$f(z_{1}) = f(a+bi)= z_{2} = c+di$$

Where $$z_{1,2}$$ are complex and a, b, c, d are real. These four numbers can represent four orthogonal axis, just as for f(x)=y, x and y represent values on two orthogonal axes.

Try to imagine slices through this 4D space. They will be able to be represented as 3D graphs that you can visualise.

I hope that helps - mull it over a bit.

8. Apr 22, 2005

GCT

perhaps this question is in regard to the definition of the integral in the respect to Riemann sums. By the way, what would be the geometrical interpretation of a antiderivative F(a) on the graph of f(x)? I have an idea, but perhaps there's a more formal definition to this.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

format: plain


text:
# Dispersion Relations and Refractive INdex

## Homework Statement

The conductivity of a plasma is defined as $\sigma = i\frac{Ne^{2}}{m\omega}$ where N is the electron density.

a) Prove the refractive index is: $n = \sqrt{1- (\frac{\omega}{\omega_{p}})^{2}}$ with $\omega_{p} = \sqrt{\frac{Ne^{2}}{m\epsilon_{0}}}$

b) Show the Attenuation length is $L = \frac{c}{\omega} \sqrt{\frac{1}{(\omega_{p}/\omega)^{2}-1}}$

## Homework Equations

$k^{2} = \mu\epsilon\omega^{2} + i\mu\sigma\omega$

## The Attempt at a Solution

I can't find equations linking the refractive index to the dispersion relation. Also, don't know anything about the attenuation length.

Can I grab a push in the right direction?
Thanks

Edit: Right, for the first part, I stumbled upon the equation $n^{2} = \frac{c^{2}}{\omega^{2}} k^{2}$ but I get an answer inverse to the required answer, with an extra factor of $c^{2}$. Can someone just verify I've almost got there or that that equation is completely wrong. Thanks.

Last edited:

Related Advanced Physics Homework Help News on Phys.org
diazona
Homework Helper

## Homework Statement

The conductivity of a plasma is defined as $\sigma = i\frac{Ne^{2}}{m\omega}$ where N is the electron density.

a) Prove the refractive index is: $n = \sqrt{1- (\frac{\omega}{\omega_{p}})^{2}}$ with $\omega_{p} = \sqrt{\frac{Ne^{2}}{m\epsilon_{0}}}$

b) Show the Attenuation length is $L = \frac{c}{\omega} \sqrt{\frac{1}{(\omega_{p}/\omega)^{2}-1}}$

## Homework Equations

$k^{2} = \mu\epsilon\omega^{2} + i\mu\sigma\omega$

## The Attempt at a Solution

I can't find equations linking the refractive index to the dispersion relation. Also, don't know anything about the attenuation length.

Can I grab a push in the right direction?
Thanks

Edit: Right, for the first part, I stumbled upon the equation $n^{2} = \frac{c^{2}}{\omega^{2}} k^{2}$ but I get an answer inverse to the required answer, with an extra factor of $c^{2}$. Can someone just verify I've almost got there or that that equation is completely wrong. Thanks.
I think you're right, and what you are being asked to prove is slightly wrong. It should be
$$n = \sqrt{1 - \biggl(\frac{\omega_p}{\omega}\biggr)^2}$$
according to e.g. http://farside.ph.utexas.edu/teaching/em/lectures/node98.html (By the way, that's a good read)

As for the attenuation length: the intensity of EM radiation inside a material decreases exponentially as a function of the distance penetrated into the material. Mathematically,
$$I \propto e^{-x/\lambda}$$
The constant $\lambda$ is the attenuation length. It's related to the imaginary part of the permittivity $\epsilon$ (and also related to the dispersion relation). Check your notes or references and see whether that helps you find anything relevant.


text:
# Set process/task name from native win32 ? (for Java use)

4 views

### Morten Christensen

Oct 14, 1998, 3:00:00 AM10/14/98
to
Hi,

Does anyone know how to change the process/task (+ maybe window) name
from win32 under Windows NT etc.

I need this feature for solving a java problem: When running multiple
java programs in a production environment, each one in it's own
window/wm, is it a problem that all programs appear under the same title
and process name "java" or "jre". This is a problem when I want to kill
or view OS information for a particular Java program which is running.
Since they all have the same process name where should I look ? Also my
"kill.exe" utility which does this automatically requires the name of
the process to kill.

To solve this I am planning to make a native library (DLL file using
JNI) which makes it possible to specify the process name from a pure
java program. However I have one problem. I don't know "which bit to
turn" to change the process/task/window name from win32. Can anyone help
?

Thanks,
Morten Christensen,
Odense, Denmark

### dave porter

Oct 14, 1998, 3:00:00 AM10/14/98
to
There's no such thing as a process name under NT. Therefore you
cannot change it.

The process structure points (loosely speaking) to the image file
(e.g. c:\foo\bar.exe) which was used as the 'main' image in the process.
Programs which want to list processes often use this file name
to label the process in the display, since it's handy for the
humans. But it's not really the name of the process in any pure
sense.

If the program has a window, then you can set the window name
to anything you like - try something like SetWindowText. However,
be aware that whatever programming framework you are using
may have other fixed ideas about how to name windows (e.g.,
an MFC MDI program typically sets the window name based on
the active document).

This is not a kernel programming question. A kernel programming
question is one about writing code which executes in kernel mode.
quite so much.

dave

--

Morten Christensen <m...@oss.dk> wrote in article
<362486CF...@oss.dk>...

### Gary Nebbett

Oct 14, 1998, 3:00:00 AM10/14/98
to
dave porter <por...@wultranet.com> wrote in article
<01bdf776$a5ea4fc0$0ba17392@glastonbury>...

> There's no such thing as a process name under NT. Therefore you
> cannot change it.
>
> The process structure points (loosely speaking) to the image file
> (e.g. c:\foo\bar.exe) which was used as the 'main' image in the process.
> Programs which want to list processes often use this file name
> to label the process in the display, since it's handy for the
> humans. But it's not really the name of the process in any pure
> sense.
>

The EPROCESS structure contains 16 bytes that the kernel debugger extension
command "processfields" labels "ImageFileName[0]". I believe that this field
can be freely modified (i.e. I don't think that there are any consistency
checks which would detect a modification). The text in the field is returned
by ZwQuerySystemInformation and is used by pstat.exe, perfmon.exe and

There are some utilities which obtain the loaded module list of a process and
use the name of the .exe file as the process name - these utilities would not
reflect the changes made to the EPROCESS structure.

> This is not a kernel programming question. A kernel programming
> question is one about writing code which executes in kernel mode.

I don't think that there is any function (documented or not) which will
change the ImageFileName field of the EPROCESS structure from user or kernel
mode. One would have to call PsGetCurrentProcess() from kernel mode and
update the field directly.

Gary

### msnews.microsoft.com

Oct 19, 1998, 3:00:00 AM10/19/98
to
Try using some windows Interrupts to change application title. I hope this
helps

----------------------------------------------------------------------------
-----------------------------------------
INT 2F - Windows95 - TITLE - SET APPLICATION TITLE
AX = 168Eh
DX = 0000h
ES:DI -> ASCIZ application title (max 79 chars+NUL)
Return: AX = status
0000h failed
0001h successful
Note: if ES:DI is 0000h:0000h or points at an empty string, the current
title is removed
BUG: this function can return a successful status even though the title
was
not changed; reportedly, waiting for two clock ticks after program
startup solves this problem
SeeAlso: AX=168Eh/DX=0001h,AX=168Eh/DX=0002h
----------------------------------------------------------------------------
-----------------------------------------

INT 2F - Windows95 - TITLE - GET APPLICATION TITLE
AX = 168Eh
DX = 0002h
ES:DI -> buffer for ASCIZ application title
CX = size of buffer in bytes
Return: AX = status
0000h failed
0001h successful
Desc: copy as much of the application's window title as possible to the
given
buffer, appending a terminating NUL to the buffer
SeeAlso: AX=168Eh/DX=0000h,AX=168Eh/DX=0003h
----------------------------------------------------------------------------
-----------------------------------------

>Morten Christensen wrote

>Hi,
>
>Does anyone know how to change the process/task (+ maybe window) name
>from win32 under Windows NT etc.
>
>I need this feature for solving a java problem: When running multiple
>java programs in a production environment, each one in it's own
>window/wm, is it a problem that all programs appear under the same title
>and process name "java" or "jre". This is a problem when I want to kill
>or view OS information for a particular Java program which is running.
>Since they all have the same process name where should I look ? Also my
>"kill.exe" utility which does this automatically requires the name of
>the process to kill.
>
>To solve this I am planning to make a native library (DLL file using
>JNI) which makes it possible to specify the process name from a pure
>java program. However I have one problem. I don't know "which bit to
>turn" to change the process/task/window name from win32. Can anyone help
>?

>Thanks,
>Morten Christensen,
>Odense, Denmark


text:
## Endomorphism ring of Q is a division algebra

We show that $Q$ is not semisimple nor simple, but $\text{End}_\mathbb{Z}(\mathbb{Q})$ is a division algebra.

Consider $A=\mathbb{Z}$ (as a $\mathbb{Z}$-algebra). Consider $M=\mathbb{Q}$ as a right $\mathbb{Z}$-module.
Lemma:
$\mathbb{Q}$ is not semisimple nor simple.

Suppose to the contrary $\mathbb{Q}=\bigoplus_{i\in I}N_i$, where $N_i$ are simple $\mathbb{Z}$-modules (i.e. $N_i\cong\mathbb{Z}/p_i\mathbb{Z}$). Then there exists nonzero $x\in\mathbb{Q}$ such that $x$ has finite order (product of primes). This is impossible in $\mathbb{Q}$.
Lemma:
$\text{End}_\mathbb{Z}(\mathbb{Q})\cong\mathbb{Q}$ as $\mathbb{Z}$-algebras.

Define $\Psi:\mathbb{Q}\to\text{End}_\mathbb{Z}(\mathbb{Q})$ where $q\in\mathbb{Q}$ is mapped to $\lambda_q\in\text{End}_\mathbb{Z}(\mathbb{Q})$, where $\lambda_q(x)=qx$. Let $k\in\mathbb{Z}$, $q,q_1,q_2\in\mathbb{Q}$.

We can check that $\Psi$ is a $\mathbb{Z}$-algebra homomorphism.

Let $q\in\ker\Psi$. Then $\Psi(q)=\lambda_q=0$, $\lambda_q(x)=qx=0$ for all $x\in\mathbb{Q}$. This implies $q=q\cdot 1=0$. Hence $\Psi$ is injective.

Let $\phi\in\text{End}_\mathbb{Z}(\mathbb{Q})$. Let $x=\frac{a}{b}\in\mathbb{Q}$, where $a,b\in\mathbb{Z}$. $\phi(x)=a\phi(\frac 1b)=\frac ab\cdot b\phi(\frac 1b)=\frac ab\cdot\phi(1)=\phi(1)\cdot x=\lambda_{\phi(1)}(x)$. Hence $\Psi$ is surjective.

Thus $\text{End}_\mathbb{Z}(\mathbb{Q})\cong\mathbb{Q}$ is a division algebra, but $\mathbb{Q}$ is not simple.


text:
# THE TORSIONAL-WAGGING TUNNELING PROBLEM AND TORSIONAL-WAGGING-ROTATIONAL PROBLEM IN HYDRAZINE

Please use this identifier to cite or link to this item: http://hdl.handle.net/1811/12101

Files Size Format View
1985-ME-07.jpg 91.80Kb JPEG image

 Title: THE TORSIONAL-WAGGING TUNNELING PROBLEM AND TORSIONAL-WAGGING-ROTATIONAL PROBLEM IN HYDRAZINE Creators: Ohashi, N.; Hougen, Jon T. Issue Date: 1985 Publisher: Ohio State University Abstract: Results derived previously for the rotational levels of the eight-framework and three-large-amplitude vibrational problem in $H_{2}$N-NH$_{2}$, using a tunneling formalism based on a treatment of the vibration-rotation problem as a whole, are rederived here in a much simpler fashion, using a tunneling formalism based on separate treatment of the vibrational and rotational problems. The present formalism is thus much more akin to the usual vibration-rotation formalism, and the origins of the various contributions to the vibration-rotation energy levels can be understood relatively easily. It is convenient here, as in earlier treatments, to make extensive use of permutation-inversion and extended-group (double-group) ideas, but it is necessary in the present treatment to consider tunneling between 16 minima in molecular coordinate space, i.e. between a number of minima which is twice the number of non-superimposable molecular frameworks that can actually be constructed for $H_{2}$N-NH$_{2}$. Description: Author Institution: Department of Physics, Faculty of Science, Kanazawa University; Molecular Spectroscopy Division, National Bureau of Standards URI: http://hdl.handle.net/1811/12101 Other Identifiers: 1985-ME-7


text:
Mapping Wikidata and Wikipedia entities to each other

## Project description

This small Python library helps you to map Wikipedia page titles (e.g. Manatee to Q42797) and vice versa. This is done by creating an index of these mappings from a Wikipedia SQL dump. Precomputed indices can be found under Precomputed indices. Redirects are taken into account.

## Installation

This package can be installed via pip, the Python package manager.

pip install wikimapper

If all you want is just mapping, then you can also just download wikimapper/mapper.py and add it to your project. It does not have any external dependencies.

## Usage

Using the mapping functionality requires a precomputed index. It is created from Wikipedia SQL dumps (see Create your own index) or can be downloaded for certain languages (see Precomputed indices). For the following to work, it is assumed that an index either has been created or downloaded. Using the command line for batch mapping is not recommended, as it requires repeated opening and closing the database, leading to a speed penalty.

from wikimapper import WikiMapper

mapper = WikiMapper("index_enwiki-latest.db")
wikidata_id = mapper.title_to_id("Python_(programming_language)")
print(wikidata_id) # Q28865

or from the command line via

$wikimapper title2id index_enwiki-latest.db Germany Q183 ### Map Wikipedia URL to Wikidata id from wikimapper import WikiMapper mapper = WikiMapper("index_enwiki-latest.db") wikidata_id = mapper.url_to_id("https://en.wikipedia.org/wiki/Python_(programming_language)") print(wikidata_id) # Q28865 or from the command line via $ wikimapper url2id index_enwiki-latest.db https://en.wikipedia.org/wiki/Germany
Q183

It is not checked whether the URL origins from the same Wiki as the index you created!

from wikimapper import WikiMapper

mapper = WikiMapper("index_enwiki-latest.db")
titles = mapper.id_to_titles("Q183")
print(titles) # Germany, Deutschland, ...

or from the command line via

$wikimapper id2titles data/index_enwiki-latest.db Q183 Germany Bundesrepublik_Deutschland Land_der_Dichter_und_Denker Jerman ... Mapping id to title can lead to more than one result, as some pages in Wikipedia are redirects, all linking to the same Wikidata item. ### Create your own index While some indices are precomupted, it is sometimes useful to create your own. The following section describes the steps need. Regarding creation speed: The index creation code works, but is not optimized. It takes around 10 minutes on my Notebook (T480s) to create it for English Wikipedia if the data is already downloaded. 1. Download the data The easiest way is to use the command line tool that ships with this package. It can be e.g. invoked by $ wikimapper download enwiki-latest --dir data

The abbreviation for the Wiki of your choice can be found on Wikipedia. Available SQL dumps can be e.g. found on Wikimedia, you need to suffix the Wiki name, e.g. https://dumps.wikimedia.org/dewiki/ for the German one. If possible, use a different mirror than the default in order to spread the resource usage.

2. Create the index

The next step is to create an index from the downloaded dump. The easiest way is to use the command line tool that ships with this package. It can be e.g. invoked by

$wikimapper create enwiki-latest --dumpdir data --target data/index_enwiki-latest.db This creates an index for the previously downloaded dump and saves it in data/index_enwiki-latest.db. Use wikimapper create --help for a full description of the tool. ## Precomputed indices Several precomputed indices can be found here . ## Command line interface This package comes with a command line interface that is automatically available when installing via pip. It can be invoked by wikimapper from the command line. $ wikimapper

usage: wikimapper [-h] [--version]

positional arguments:
sub-command help
custom index.
title2id            Map a Wikipedia title to a Wikidata ID.
url2id              Map a Wikipedia URL to a Wikidata ID.
id2titles           Map a Wikidata ID to one or more Wikipedia titles.

optional arguments:
-h, --help            show this help message and exit
--version             show program's version number and exit

## Development

The required dependencies are managed by pip. A virtual environment containing all needed packages for development and production can be created and activated by

virtualenv venv --python=python3 --no-site-packages
source venv/bin/activate
pip install -e ".[test, dev, doc]"

The tests can be run in the current environment by invoking

make test

or in a clean environment via

tox

## FAQ

### How does the parsing of the dump work?

jamesmishra has noticed that SQL dumps from Wikipedia almost look like CSV. He provides some basic functions to parse insert statements into tuples. We then use the Wikipedia SQL page dump to get the mapping between title and internal id, page props to get the Wikidata ID for a title and then the redirect dump in order to fill titles that are only redirects and do not have an entry in the page props table.

### Why do you not use the Wikidata SPARQL endpoint for that?

It is possible to query the official Wikidata SPARQL endpoint to do the mapping:

prefix schema: <http://schema.org/>
SELECT * WHERE {
}

This has several issues: First, it uses the network, which is slow. Second, I try to use that endpoint as infrequent as possible to save their resources (my use case is to map data sets that have easily tens of thousands of entries). Third, I had coverage issues due to redirects in Wikipedia not being resolved (around ~20% of the time for some older data sets). So I created this package to do the mapping offline instead.

## Acknowledgements

I am very thankful for jamesmishra to provide mysqldump-to-csv . Also, mbugert helped me tremendously understanding Wikipedia dumps and giving me the idea on how to map.

## Project details

Uploaded source


text:
# Finding the volume of two intersecting cylinders at arbitrary angles

Suppose we know the length, radius, position and orientation of two cylinders. Is there a general formula to calculate the volume of space shared by the intersection of the cylinders?

• Wow. This seems very difficult. A closed form solution is almost unrealistic. I recommend you simplify by starting with some assumptions. It would be helpful to assume the lines through the centers of the cylinders intersect at an angle $\alpha$. Then, assume that the cylinders are very long, so they don't intersect at their bases. Even with all of these simplifications, the problem is not easy. – Jared Dec 24 '13 at 6:54
• @Jared I feared someone would say that. Although I thought there might be at least some approximate solution. For example in Computer Aided Design programs I have seen people cutout shapes using the intersection of another shape to define the volume to be removed. If we have the original cylinders volume then cut a portion out using the intersection with a second cylinder we could get an approximate volume somehow. – Stephen Tierney Dec 24 '13 at 10:51
• You can probably write a triple integral for the volume, and compute it numerically, but this integral will be rather nasty: you have to plug in all you know, like directions of the cylinders and their radii. There will be a geometrical condition for a point $M$ to be inside the intersection, then you integrate $\mathrm dV$ on the domain thus defined. Good luck :-) I bet CAD programs make first an approximation of figures as polyhedra, then the volume is easier (the intersection is still a polyhedron). – Jean-Claude Arbaut Dec 24 '13 at 11:18
• This comment is to link this post as one of the (abstract) duplicates to the current choice of mother/target post. Even though this post is older, the target post has an existing duplicate-link. – Lee David Chung Lin Jan 22 at 11:44

This answer is about the particular case in which the axes of the two cylinders meet at a point, both have the same radius, and both cylinders extend to infinity (this last assumption is to avoid complexities regarding truncated cylinder intersections). We can take the radius as $1$ and then re-scale to radius $a$ by inserting a factor of $a^3$.

Let the $x$ axis be the axis of cylinder $A$, and for some $m>0$ let the line $y=mx$ be the axis of cylinder $B$. The (signed) distance between a point $(x,y)$ and the line $y=mx$ is $\frac{y-mx}{r}$ where $r=\sqrt{1+m^2}$ Then the restriction that $(x, y)$ lies under cylinder $B$ is that $-1 \le \frac{y-mx}{r} \le 1,$ while $(x, y)$ lies under cylinder $A$ provided $-1 \le y \le 1$.

Note we're considering the part of the intersection lying above the $xy$ plane; then the height over cylinder $A$ is $\sqrt{1-y^2}$ and the height over cylinder $B$ is $\sqrt{1-\left[\frac{y-mx}{r}\right]^2}.$ These heights are the same over a point $(x, y)$ (i.e. the two cylinders intersect over that point) iff $y^2-\left[\frac{y-mx}{r}\right]^2=0$, which factors into two lines $y=-\frac{mx}{r-1}$ and $y=\frac{mx}{r+1}$. The product of these slopes is $-1$ so the lines are orthogonal.

If $L_B$ is the axis $y=mx$ of cylinder $B$, and for convenience $L_A$ is the $x$-axis, the axis of cylinder $A$, we'll use the notations $L_B^+$ and $L_B^-$ for the lines parallel to $L_B$ and one unit away from it, above and below respectively. Similar notation for $L_A^+$ and $L_A^-.$ The first two of these are the upper and lower boundaries of the projection of cylinder $B$ onto the $xy$ plane, and similarly the second two are the upper and lower boundaries of the projection of cylinder $A.$ Equations for these are

$$L_B^+ : y=mx+r \\ L_B^- : y=mx-r \\ L_A+ : y=1 \\ L_A^- : y=-1$$ The intersections of these lines consist of four points $P, Q, R, S$ which form an equilateral parallelogram. We have $$P=\left(\frac{1-r}{m}, 1\right), \ Q=\left(\frac{1+r}{m}, 1\right), \ R=\left(\frac{-1+r}{m}, -1\right), \ S=\left(\frac{-1-r}{m}, -1\right)$$ Now if we denote the origin $(0, 0)$ by $O$, we can see there are four triangular regions each having $O$ as one vertex, and two adjacent vertices of the parallelogram as the other two vertices. Above each of these triangles we know which of the two cylinders lies below the other.

It turns out that the contributions to the volume from each of these triangles (i.e. the volume of the intersection of the cylinders lying above that triangle) is the same.

This can be seen by symmetry, since e.g. the part lying above $\triangle OQR$ could be set up with the line $y=mx$ playing the role of the $x$ axis, and taking an orthogonal axis pointing downwards from $O$, so that the "old" $x$ axis is now at the same slope $m$ in this rotated and flipped coordinate system.

It remains now to find the volume over $\triangle OPQ$, which may be described as $0 \le y \le 1$ and $\frac{y(1-r)}{m} \le x \le \frac{y(1+r)}{m}$. Now over this triangle it is cylinder $A$ whose height is lower. This means we're integrating $\sqrt{1-y^2}$ over $\triangle OPQ$. At any specific $y$ the height being constant, we only need multiply by the length of the horizontal section of $\triangle OPQ$ at distance $y$ from the $x$ axis, and integrate. Thus we get $$\int_0^1 \frac{(2r)}{m y \sqrt{1-y^2}} dy=(2r/m)\cdot(1/3).$$ Recalling that we have found only the volume above the $xy$ plane, and that there are four triangles each giving the above contribution to the part above the $xy$ plane, we arrive at $$\frac{16}{3}\cdot \frac{\sqrt{1+m^2}}{m}$$ for the volume of the intersection of the cylinders.

Note as $m \to \infty$ (so that the angle of intersection goes to 90 degrees) this formula approaches the correct $16/3$ (the usual formula $(16/3)a^3$ when $a=1.$) And also as expected it becomes infinite as $m \to 0^+.$

Added note: If $\theta$ is the angle between the two axes, then $m=\tan \theta.$ I used the letter $r$ during the derivation to mean $\sqrt{1+m^2}$ only for convenience. If we reset $r$ to now mean the common radius of the cylinders, and apply a trig identity, we can reexpress the volume in the form $$V=\frac{16}{3 \sin \theta} \cdot r^3,$$ which is only off by the $sin \theta$ divisor from the result $(16/3)r^3$ when the cylinders are orthogonal.


text:
## Design of noise and period-time robust high-order repetitive control, with application to optical storage.(English)Zbl 1138.93347

Summary: Repetitive control is useful if periodic disturbances or setpoints act on a control system. Perfect (asymptotic) disturbance rejection is achieved if the period time is exactly known. The improved disturbance rejection at the periodic frequency and its harmonics is achieved at the expense of a degraded system sensitivity at intermediate frequencies. A convex optimization problem is defined for the design of high-order repetitive controllers, where a trade-off can be made between robustness for changes in the period time and for reduction of the error spectrum in-between the harmonic frequencies. The high-order repetitive control algorithms are successfully applied in experiments with the tracking control of a CD-player system.

### MSC:

 93B51 Design techniques (robust design, computer-aided design, etc.) 93B35 Sensitivity (robustness) 68P20 Information storage and retrieval of data 93C95 Application models in control theory
Full Text:

### References:

 [1] Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: Analysis, algorithms and engineering applications, MPS-SIAM series on optimization. · Zbl 0986.90032 [2] Bodson, M., Sacks, A., & Khosla, P. (1994). Harmonic generation in adaptive feedforward cancellation schemes. IEEE Transactions on Automatic Control (September) 1939-1944. · Zbl 0816.93048 [3] Cao, Z., & Ledwich, G. (2001). Tracking variable periodic signals with fixed sampling rate. In Proceedings of the 40th IEEE conference on decision and control (Vol. 5, pp. 4885-4890). [4] Chang, W.S.; Such, I.H.; Kim, T.W., Analysis and design of two types of digital repetitive control systems, Automatica, 31, 5, 741-746, (1995) · Zbl 0825.93447 [5] Chang, W. S., Suh, I. H., & Oh, J. H. (1998). Synthesis and analysis of digital multiple repetitive control systems. In Proceedings of the American control conference (pp. 2687-2691). [6] Chen, Y. Q., Ding, M., Xiu, L., Ooi, K., & Tan, L. (2003). Optimally designed parsimonious repetitive learning compensator for hard disc drives having high track density. US Patent 6,574,067 (pp. 1-13). [7] Chen, Y. Q., & Moore, K. L. (2002). Harnessing the nonrepetitiveness in iterative learning control. In Proceedings of the 41st IEEE conference on decision and control (pp. 3350-3355). [8] Chew, K. K., & Tomizuka, M. (1990). Digital control of repetitive errors in disk drive systems. In Proceedings of the American control conference (pp. 540-548). [9] Choi, G. H., Oh, J. H., & Choi, G. S. (1999). Repetitive tracking control of a coarse-fine actuator. In Proceedings of the IEEE/ASME international conference on advanced intelligent mechatronics (pp. 335-340). [10] Choi, G.S.; Lim, Y.A.; Choi, G.H., Tracking position control of piezoelectric actuators for periodic reference inputs, Mechatronics, 12, 5, 669-684, (2002) [11] Dötch, H. G. M., Smakman, H. T., Van den Hof, P. M. J., & Steinbuch, M. (1995). Adaptive repetitive control of a compact disc mechanism. In Proceedings of the 1995 IEEE conference on decision and control (pp. 1720-1725), New Orleans, December. [12] Francis, B.A.; Wonham, W.M., The internal model principle for linear multivariable regulators, Applied mathematics and optics, 2, 170-194, (1975) · Zbl 0351.93015 [13] Fung, R.F.; Huang, J.S.; Chien, C.G.; Wang, Y.C., Design and application of a continuous repetitive controller for rotating mechanisms, International journal of mechanical sciences, 42, 9, 1805-1819, (2000) · Zbl 0968.70008 [14] Gotou, M., Ueta, E., Nakamura, A., & Matsuo, K. (1991). Development of multirate sampling repetitive learning servo system and its application to a compact camcorder. In IEEE/RSJ international workshop on intelligent robots and systems IROS ’91 (pp. 647-654), November 1991. [15] Guo, L., Reducing the manufacturing costs associated with hard disk drives—a new disturbance rejection control scheme, IEEE/ASME transactions on mechatronics, 2, 2, 77-85, (1997) [16] Hara, S.; Yamamoto, Y.; Omata, T.; Nakano, M., Repetitive control system—a new type servo system, IEEE transactions on automatic control, AC-33, 659-668, (1988) · Zbl 0662.93027 [17] Hillerström, G., Adaptive suppression of vibrations—a repetitive control approach, IEEE transactions on control systems technology, 4, 1, 72-77, (1996) [18] Inoue (1990). Practical repetitive control system design. In Proceedings of the 29th conference on decision and control (pp. 1673-1678), December. [19] Kim, B.S.; Li, J.; Tsao, T.C., Two-parameter robust repetitive control with application to a novel dual-stage actuator for noncircular machining, IEEE/ASME transactions on mechatronics, 9, 4, 644-652, (2004) [20] Kim, D.H.; Tsao, T.C., Robust performance control of electrohydraulic actuators for electronic Cam motion generation, IEEE transactions on control systems technology, 8, 2, 220-227, (2000) [21] Köroğlu, H., & Morgül, Ö. (1999). Discrete-time LQ optimal repetitive control. In Proceedings of the American control conference (Vol. 5, pp. 3287-3291). [22] Köroğlu, H.; Morgül, Ö., Time-varying repetitive control for better transient response and stochastic behaviour, Electronics letters, 37, 17, 1101-1102, (2001) [23] Lee, R.C.H.; Smith, M.C., Robustness and trade-offs in repetitive control, Automatica, 34, 7, 889-896, (1998) · Zbl 0961.93019 [24] Li, J., & Tsao, T. C. (1999). Rejection of repeatable and non-repeatable disturbances for disk drive actuators. In Proceedings of the American control conference (pp. 3615-3619). [25] Luo, Z., & Mahawan, B. (1998). Repetitive control of tracking systems with time-varying periodic references. In Proceedings of the 37th IEEE conference on decision and control (Vol. 2, pp. 1247-1249). · Zbl 1006.93538 [26] Manayathara, Th.J.; Tsao, T.-C.; Bentsman, J.; Ross, D., Rejection of unknown periodic load disturbances in continuous steel casting process using learning repetitive control approach, IEEE transactions on control systems technology, 4, 3, 259-265, (1996) [27] Messner, W., & Bodson, M. (1994). Design of adaptive feedforward controllers using internal model equivalence. In Proceedings of the American control conference (pp. 1619-1623). [28] Moon, J.; Lee, M.; Chung, M., Repetitive control for the track-following servo system of an optical disk drive, IEEE transactions on control systems technology, 6, 5, 663-670, (1998) [29] Moore, K. L., & Chen, Y. Q. (2002). On monotonic convergence of high-order iterative learning update laws. In Proceedings of the IFAC World congress, Barcelona, Spain. [30] Rogers, E.; Owens, D.H., Stability analysis for linear repetitive processes, (1992), Springer Berlin · Zbl 0772.93072 [31] de Roover, D.; Bosgra, O.H.; Steinbuch, M., Internal model based design of repetitive and iterative learning controllers for linear multivariable systems, International journal of control, 73, 10, 914-929, (2000) · Zbl 1006.93602 [32] Schootstra, G., & Steinbuch, M. (1998). Control system for a process that exhibits periodic disturbances. US Patent nr. 5,7842,272, July, 21. [33] Singh, T.; Vadali, S.R., Robust time delay control, ASME journal of dynamic systems, measurement and control, 115, 2(A), 303-306, (1993) · Zbl 0775.93040 [34] Stan, S.G., Optimization of the CD-rom system towards higher data throughputs, (1999), PhD thesis Technische Universiteit Eindhoven [35] Steinbuch, M., Repetitive control for systems with uncertain period-time, Automatica, 38, 12, 2103-2109, (2002) · Zbl 1018.93023 [36] Steinbuch, M., van den Eerenbeemt, J. , Weiland, S., & Singh, T. (2004). On noise and period-time sensitivity in high order repetitive control. In IEEE 43rd IEEE conference on decision and control (pp. 1295-1300), IEEE, Bahamas, United States. [37] Steinbuch, M.; van Groos, P.J.M.; Schootstra, G.; Wortelboer, P.M.; Bosgra, O.H., $$\mu$$-synthesis of a compact disc player, International journal of robust and nonlinear control, 8, 169-189, (1998) · Zbl 0900.93241 [38] Steinbuch, M., & Norg, M. L. (1998). Advanced motion control: An industrial perspective. European Journal of Control 278-293. · Zbl 0925.93706 [39] Steinbuch, M., & Schootstra, G. (1998). Filter, repetitive control system and learning control system both provided with such filter. US Patent nr. 5,740,090, April 14. [40] Tomizuka, M., Zero phase error tracking algorithm for digital control, Journal of dynamic systems, measurement and control, 109, 65-68, (1987) · Zbl 0621.93017 [41] Tomizuka, M., Tsao, T. C., & Chew, K. K. (1988). Discrete-time domain analysis and synthesis of repetitive controllers. In Proceedings of the American control conference (pp. 860-866), June. [42] Tsao, T. C., & Nemani, M. (1992). Asymptotic rejection of periodic disturbances with uncertain period. In Proceedings of the American control conference (pp. 2696-2699). [43] Xu, L., & Yao, B. (2001). Adaptive robust repetitive control of a class of nonlinear systems in normal form with applications to motion control of linear motors. In Proceedings of the IEEE/ASME international conference on advanced intelligent mechatronics (Vol. 1, pp. 527-532). [44] Yamada, M., Riadh, Z., & Funahashi, Y. (2000). Design of robust repetitive control systems for multiple periods. Proceedings of the 39th IEEE conference on decision and control (Vol. 4, pp. 3739-3744). [45] Yamada, M.; Riadh, Z.; Funahashi, Y., Design of discrete-time repetitive control system for pole placement and application, IEEE/ASME transactions on mechatronics, 4, 2, 110-118, (1999) [46] Yau, W., & Tsai, W. (1999). Repetitive control design for linear servo systems. In Proceedings of the American control conference (Vol. 5, pp. 3728-3732).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
## Understanding the rules of parsing table construction

I’m studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules.

Example grammer is like this

S → ( S ) S | $$\epsilon$$

How can I derive like below table?

I read all explanations of textbook, but I cannot totally understand the process of table construction. Are there anyone who can explain more easily about this process?

## Fare construction decoded by Matrix ITA

I often use Matrix ITA first for best flight options and rates. Then check with airline’s site and Expedia for rates

What are your first 3 steps to finding the best prices?

## Writing down a recursive construction

The standard practice when doing a recursive construction seems to be to list all of the desired properties for the construction first:

We construct $$(x_n)$$, $$(y_n)$$, $$(z_n)$$ such that

(1)

(2)

(3)

… (a bunch of properties about the individual items $$x_n,z_n,y_n$$ and their relationships to $$x_k, y_k,z_k$$‘s when $$k)

and then explicitly write out the construction for $$n=0$$, and then do the “recursive step”.

My question is, if the list of items is sufficiently short and the construction is not too complex, is it necessary to write the construction like this? Would it be acceptable to simply begin the construction, do a few cases at the beginning, $$n=0,1,2$$ until you get the feel for things, and then just say “continue in this manner”? And then when proving things about the construction, just say “By construction,…”.

When I say acceptable, I mean acceptable for publication in a good journal.

Are there any mathematical advantages to actually writing the conditions (1),(2),(3),… beforehand?

## How to hide a construction site without hindering the workers?

Let’s say you have a building site that could fit in a roughly 100 feet square. And you want to hide it without hindering workers.

Now you could use the mirage arcane spell to hide the building but, a.) the workers would not be hidden, and b.) even the workers would not see the building (which seems counter-productive).

Or, you could use Mordenkainen’s private sanctum, which would hide the build site in a not at all conspicuous 100 feet square fog (insert sarcasm sign here).

So, can you use hallucinatory terrain to hide the fog, by making the original terrain there? If yes, how would that work for the workers? Or could you create a terrain that hides the fog and is even more inconspicuous? Or am I thinking too much into that and there is a completely different approach to this? Is it even possible in 5e?

Buy cheap argumentative research paper best literature review on online gaming

Professional Term Paper and Essay Writing Service

Custom Essay Writing Service – CONTINUE

Maya Turovskaya, Russian Critic and Documentarian, Dies at 94
AirAsia holds huge sale offering…

## Construction of a K(pi_1)- space?

I was advised to post my question here. A colleague suggested a proof of a fact which I have hard time to believe. Since I am not a topologist by training I wonder if this can be true in such a generality.

Consider any finite CW-complex structure on the 𝑑-dimensional sphere $$𝑆^𝑑$$. Let $$𝐾$$ be $$𝑆^𝑑$$ with all strata of codimension at least 2 removed, i.e. we keep just 𝑑 and (𝑑−1)-dimensional strata of the complex under consideration.

Claim. K is contractible to a graph (the dual graph of the preserved strata). Thus it is a $$K(\pi_1, 1)$$– space where $$\pi_1$$ is a free group.

The claim is trivially true for d=2, but looks suspicious for higher d. Also if it is true then it might work for more general CW-complexes as well.

Best regards, Boris Shapiro/Stockholm University/

## Coordinate-free B.Feix construction of a hyperkähler metric

In the 2001’s paper ‘Hyperkähler metrics on cotangent bundles’ B.Feix gives a construction of a hyperkähler metric on a neighbourhood of zero section in $$T^*X$$ where $$X$$ is a real analytic Kähler manifold.

As for me, this construction is awful. It’s not difficult to understand the general steps of it and I’m really inspired by them but if you look at details it’s just awful. Almost everything is written in local coordinates without explaining why everything can be glued globally, the article starts with choosing a local antiholomorphic involution on $$X$$ without mentioning it properly, she calls ‘the complexified Kähler form on $$X^\mathbb C$$‘ a form which is not the analytic continuation of the Kähler form on $$X$$ etc.

I’ve spent several days trying to rewrite the paper in a coordinate-free way changing some steps as it’d be more similar to constructions of a Kähler metric on a neighbourhood of zero section in $$T^*X$$ where $$X$$ is a real analytic Riemannian manifold due to Lempert, Szöke and Guillemin, Stenzel. I’m not completely successful yet, though. So I ask, perhaps this paper is already written? I know about D.Kaledin’s paper but his approach is rather different, I want something which looks like Feix’s construction.

I’m writing some code which loads a dataset and then performs some transformations on this (relatively large, ~5 GB) dataset. I need different sub-sets of this data for use with analysis code I have wrote in a Jupyter notebook. I’m approaching the problem as follows, but have been learning about different decorators (specifically, class methods) and was wondering if there is a better way of doing the following, particularly could load_data be a class method?

class Data():      def __init__(self, filename='/path_to_data'):         self.df = self._load_data(filename)         self._transform_df()      def _load_data(self, filename):         """doc string to write"""         data = pd.read_csv(filename)         # do other stuff to data         return data     def _transform_df(self):         """doc string to write"""         self.df['Date'] =  pd.to_datetime(self.df['Date'], format="%Y/%m/%d %H:%M:%S")     def get_subset_data(self, p1, p2):        """doc string to write"""        mask = ((self.df['value_1']==p1) &                 (self.df['value_2']==p2)                )        return self.df[mask]      def __repl__():         return 'Data({})'.format(filename)       # more definitions

Then what I will do is load the data once and generate the different subsets when needed:

global_df = Data() subset_1_df = global_df.get_subset_data(p1=1, p2=2) subset_2_df = global_df.get_subset_data(p1=10, p2=20)  ...

## The Construction of a Basis of Holomorphic Differential 1-forms for a given Planar Curve

Working over the complex numbers, consider a function $$F\left(x,y\right)$$ and a curve $$C$$ defined by $$F\left(x,y\right)=0$$.

I know that to construct the Jacobian variety associated to $$C$$, one integrates a basis of global holomorphic differential forms over the contours of the curve’s homology group. I’m looking for information that is oriented toward actually computing things for given concrete examples; everything I’ve seen so far, however, has been uselessly abstract or non-specific. Note: I’m new to this—I’m an analyst who knows next to nothing about algebra and even less about differential geometry or topology.

In my quest for a sensible answer, I turned to a H.F. Baker’s wonderful (though densely written) text from the start of the 20th century. Just reading through the first few pages makes it abundantly clear that there is a general procedure for constructing a basis of holomorphic differential forms for a given curve. Ted Shifrin’s comment on this math-stack-exchange problem only makes me more certain than ever that the answers I seek are out there, somewhere.

Broadly speaking, my goals are as follows. In all of these, my aim is to be able to use the answers to these questions to compute various specific examples, either by hand, or with the assistance of a computer algebra system. So, I’m looking for formulae, explanations and/or step-by-step procedures/algorithms, and/or pertinent reference/reading material.

(1) In the case where $$F$$ is a polynomial, what is/are the procedure(s) for determining a basis of holomorphic differential 1-forms over $$F$$? If the procedure varies depending on certain properties of $$F$$ (say, if $$F$$ is an affine curve, or a projective curve, or of a certain form, or some detail like that), what are those variations?

(2) In the case where $$F$$ is a polynomial of $$x$$-degree $$d_{x}$$, $$y$$-degree $$d_{y}$$, and $$C$$ is a curve of genus $$g$$, I know that the basis of holomorphic differential 1-forms for $$C$$ will be of dimension $$g$$. In the case, say, where $$C$$ is an elliptic curve, with:

$$F\left(x,y\right)=4x^{3}-g_{2}x-g_{3}-y^{2}$$

the classical Jacobi Inversion Problem arises from considering a function $$\wp\left(z\right)$$ which parameterizes $$C$$, in the sense that $$F\left(\wp\left(z\right),\wp^{\prime}\left(z\right)\right)$$ is identically zero. Using the equation: $$F\left(\wp\left(z\right),\wp^{\prime}\left(z\right)\right)=0$$ we can write: $$\wp^{-1}\left(z\right)=\int_{z_{0}}^{z}\frac{ds}{4s^{3}-g_{2}s-g_{3}}$$ and know that the multivaluedness of the integral then reflects the structure of the Jacobian variety associated to $$C$$.

That being said, in the case where $$C$$ is of genus $$g\geq2$$, and where we can write $$F\left(x,y\right)=0$$ as: $$y=\textrm{algebraic function of }x$$ nothing stops us from performing the exact same computation as for the case with an elliptic curve. Of course, this computation must be wrong; my question is: where and how does it go wrong? How would the parameterizing function thus obtained relate to the “true” parameterizing function—the multivariable Abelian function associated to $$C$$? Moreover, how—if at all—can this computation be modified to produce the correct parameterizing function (the Abelian function)?

(3) My hope is that by understanding both (1) and (2), I’ll be in a position to see what happens when these classical techniques are applied to non-algebraic plane curves defined but with $$F$$ now being an analytic function (incorporating exponentials, and other transcendental functions, in addition to polynomials). Of particular interest to me are the transcendental curves associated to exponential diophantine equations such as: $$a^{x}-b^{y}=c$$ $$y^{n}=b^{x}-a$$

That being said, I wonder: has this already been done? If so, links and references would be much appreciated.

Even if it has, though, I would still like to know the answers to my previous questions, even if it’s merely for my personal edification alone.


text:
# How to calculate this functional derivative?

How can I calculate the functional derivative of this functional?

$$F[x](t) = \int_{0}^{t}x(t_1)a(t_1)\left \{ \int_{0}^{t_1}x(t_2)b(t_2) \,dt_2\right \} dt_1 .$$

Where $a(t)$ and $b(t)$ are real fixed functions. Following the usual method, I'm getting

$$\frac{\delta F\left [ x \right ]}{\delta x(s) } = \int_{0}^{s}\left [ a(t')b(s)+a(s)b(t') \right ]x(t')dt'.$$

which seems odd since that is also a functional, and I think that I should be getting a function.

• I cannot edit because it's just a 3 character-change, but in the first equation it should be $F[x]$ instead of $F[x(t)]$. – anderstood Sep 4 '14 at 2:55

Use the identity \begin{align} \frac{\delta x(t)}{\delta x(s)} = \delta(t-s) \end{align} to obtain \begin{align} \frac{\delta}{\delta x(s)}\Big(x(t_1)x(t_2)a(t_1)b(t_2)\Big) &= \delta(t_1-s)x(t_2)a(t_1)b(t_2) + x(t_1)\delta(t_2-s)a(t_1)b(t_2) \end{align} from which it follows that \begin{align} \frac{\delta F}{\delta x(s)}[x] = a(s)\int_0^s x(t_2)b(t_2)\,dt_2 + b(s)\int_s^tx(t_1)a(t_1)\, dt_1 \end{align} where we have assumed $0<s<t$ and $0<s<t_1$.
• I think that the lower limit of the second integral is $s$, because $t_1>t_2=s$ – Trimok Sep 4 '14 at 10:41
• Thanks for the answer! One more thing, is it possible now to take the derivative of this new expression? Which would be the second order derivative of the functional? Would that be $$\frac{\delta ^2 F\left [ x \right ]}{\delta x(y)\delta x(s) } = b(s)a(y)+a(s)b(y)$$ ??? – Martin Drech Sep 4 '14 at 18:39


text:
## Algebra: A Combined Approach (4th Edition)

$\mid\frac{4x-6}{3}\mid$=6 Resolving the absolute value in $+\frac{4x-6}{3}=6$ and $-\frac{4x-6}{3}=6$ Simply resolve the equations 4x-6=18 and -4x+6=18 4x=24 and -4x=12 x=6 and x=-3