text:
zbMATH — the first resource for mathematics

Roush, Fred William

Compute Distance To:
 Author ID: roush.fred-william Published as: Roush, F.; Roush, F. W.; Roush, Fred; Roush, Fred N.; Roush, Fred W.; Roush, Fred William External Links: MGP
 Documents Indexed: 148 Publications since 1973, including 8 Books
all top 5

Co-Authors

 4 single-authored 132 Kim, Ki Hang 8 Gibson, Richard G. jun. 5 Wagoner, John B. 3 Bratteli, Ola 3 Jørgensen, Palle E. T. 3 Stallworth, Daniel T. 2 Dénes, József 2 Makar-Limanov, Leonid G. 2 Rosen, Harvey 1 Boyle, Mike 1 Brüning, Jochen 1 Cao, Zhongqing 1 Damm, Carsten 1 Hong, Sungpyo 1 Intriligator, Michael D. 1 Kellum, Kenneth R. 1 Ki Hang Kim 1 Kwak, Jin Ho 1 Markowsky, George 1 Neggers, Joseph 1 Ormes, Nicholas S. 1 Putcha, Mohan S. 1 Rogers, Douglas G. 1 Rosen, Harvey S. 1 Schönfeld, Wolfgang 1 Williams, Susan G.
all top 5

Serials

 18 Mathematical Social Sciences 11 Proceedings of the American Mathematical Society 10 Semigroup Forum 10 Linear Algebra and its Applications 6 Journal of Algebra 6 Ergodic Theory and Dynamical Systems 6 PU.M.A. Pure Mathematics and Applications. Ser. B 4 Journal of Mathematical Psychology 3 Fuzzy Sets and Systems 3 Journal of Combinatorics, Information & System Sciences 3 Journal of Economic Theory 3 Real Analysis Exchange 3 Journal of the American Mathematical Society 3 PU.M.A. Pure Mathematics and Applications. Ser. A 3 Topology Proceedings 2 Acta Cybernetica 2 Acta Scientiarum Mathematicarum 2 Journal of Pure and Applied Algebra 2 Acta Applicandae Mathematicae 2 Forum Mathematicum 2 PU.M.A. Pure Mathematics and Applications 2 Electronic Research Announcements of the American Mathematical Society 1 American Mathematical Monthly 1 Communications in Algebra 1 Periodica Mathematica Hungarica 1 The Mathematical Intelligencer 1 Algebra Universalis 1 Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Mathematica 1 Colloquium Mathematicum 1 Glasgow Mathematical Journal 1 International Journal of Game Theory 1 Journal of Combinatorial Theory. Series A 1 Journal of Combinatorial Theory. Series B 1 Journal of the London Mathematical Society. Second Series 1 Kyungpook Mathematical Journal 1 Mathematica Slovaca 1 Pure & Applied Mathematika Sciences 1 Simon Stevin 1 PU.M.A. Pure Mathematics and Applications. Ser. C 1 Aequationes Mathematicae 1 Algebra Colloquium 1 Annals of Mathematics. Second Series 1 Lecture Notes in Pure and Applied Mathematics
all top 5

Fields

 35 Group theory and generalizations (20-XX) 32 Game theory, economics, social and behavioral sciences (91-XX) 31 Linear and multilinear algebra; matrix theory (15-XX) 27 General topology (54-XX) 21 Combinatorics (05-XX) 16 Mathematical logic and foundations (03-XX) 14 Order, lattices, ordered algebraic structures (06-XX) 12 Associative rings and algebras (16-XX) 9 Dynamical systems and ergodic theory (37-XX) 7 Number theory (11-XX) 5 Real functions (26-XX) 4 Field theory and polynomials (12-XX) 4 Measure and integration (28-XX) 4 Functional analysis (46-XX) 4 Computer science (68-XX) 4 Operations research, mathematical programming (90-XX) 4 Information and communication, circuits (94-XX) 3 General mathematics (00-XX) 3 General algebraic systems (08-XX) 3 Commutative algebra (13-XX) 3 Algebraic geometry (14-XX) 3 Manifolds and cell complexes (57-XX) 2 History and biography (01-XX) 2 Ordinary differential equations (34-XX) 2 Algebraic topology (55-XX) 2 Numerical analysis (65-XX) 2 Biology and other natural sciences (92-XX) 1 $K$-theory (19-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Convex and discrete geometry (52-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistics (62-XX) 1 Systems theory; control (93-XX)


text:
Maximal lattice-free convex sets in linear subspaces

# Maximal lattice-free convex sets in linear subspaces

Amitabh Basu
Carnegie Mellon University, abasu1@andrew.cmu.edu

Michele Conforti

Gérard Cornuéjols
Carnegie Mellon University and Université d’Aix-Marseille
gc0v@andrew.cmu.edu

Giacomo Zambelli
Supported by NSF grant CMMI0653419, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.
March 30, 2009, Revised April 21, 2010.
###### Abstract

We consider a model that arises in integer programming, and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that these sets are polyhedra. The latter result extends a theorem of Lovász characterizing maximal lattice-free convex sets in .

## 1 Introduction

The study of maximal lattice-free convex sets dates back to Minkowski’s work on the geometry of numbers. Connections between integer programming and the geometry of numbers were investigated in the 1980s starting with the work of Lenstra [22]. See Lovász [23] for a survey. Recent work in cutting plane theory [1],[2],[3],[4],[5],[8],[10],[13],[14],[15],[17],[19],[25] has generated renewed interest in the study of maximal lattice-free convex sets. In this paper we further pursue this line of research. In the first part of the paper we consider convex sets in an affine subspace of that are maximal with the property of not containing integral points in their relative interior. When this affine subspace is rational, these convex sets are characterized by a result of Lovász [23]. The extension to irrational subspaces appears to be new, and it has already found an application in the proof of a key result in [10]. It is also used to prove the main result in the second part of this paper: We consider a model that arises in integer programming, and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace.

Let be an affine subspace of . Assume that contains an integral point, i.e. . We say that a set is a maximal lattice-free convex set in if , is convex, has no integral point in its interior with respect to the topology induced on by , and is inclusionwise maximal with these three properties. This definition implies that either contains no integral point in its relative interior or has dimension strictly less than .

The subspace is said to be rational if it is generated by the integral points in . So, if we denote by the affine hull of the integral points in , if and only if is rational. If is not rational, then the inclusion is strict. When is not rational, we will also say that is irrational. An example of an irrational affine subspace is the set of points satisfying the equation . The affine hull of is the set of points satisfying the equations .

###### Theorem 1.

Let be an affine space containing an integral point and the affine hull of . A set is a maximal lattice-free convex set of if and only if one of the following holds:

• is a polyhedron in whose dimension equals , is a maximal lattice-free convex set of whose dimension equals , the facets of and are in one-to-one correspondence and for every facet of , is the facet of corresponding to ;

• is an hyperplane of of the form , where and is an irrational hyperplane of ;

• is a half-space of that contains on its boundary.

A characterization of maximal lattice-free convex sets of , needed in of the previous theorem, is given by the following.

###### Theorem 2.

(Lovász [23]) Let be a rational affine subspace of containing an integral point. A set is a maximal lattice-free convex set of if and only if one of the following holds:

• is a polyhedron of the form where is a polytope, is a rational linear space, , does not contain any integral point in its relative interior and there is an integral point in the relative interior of each facet of ;

• is an affine hyperplane of of the form , where and is an irrational hyperplane of ;

The polyhedron in Theorem 2(i) is called a cylinder over the polytope and can be shown to have at most facets [16].

Theorem 1 is new and it is used in the proof of our main result about integer programming, Theorem 3 below. It is also used to prove the last theorem in [10]. Theorem 2 is due to Lovász ([23] Proposition 3.1). Lovász only gives a sketch of the proof and it is not clear how case (ii) in Theorem 2 arises in his sketch or in the statement of his proposition. Therefore in Section 2 we will prove both theorems.

Figure 1 shows examples of maximal lattice-free convex sets in a 2-dimensional affine subspace of . We denote by the affine space generated by . In the first picture is rational, so , while in the second one is a subspace of of dimension 1.

We now give an example of Theorem 1(ii). Let be the set of points satisfying the equation . The affine hull of is the set of points satisfying the equations . The set defined by the equations , satisfies Theorem 1(ii). Indeed, . Furthermore, and is the line satisfying the equations and it is an irrational subspace since the only integral point it contains is .

Next we highlight the relation between lattice-free convex sets and valid inequalities in integer programming. This was first observed by Balas [6].

Suppose we consider rows of the optimal tableau of the LP relaxation of a given MILP, relative to basic integer variables . Let be the nonbasic variables, and be the vector of components of the optimal basic feasible solution. The tableau restricted to these rows is of the form

 x=f+k∑j=1rjsj,x≥0 integral,s≥0, % and sj∈Z,j∈I,

where , , and denotes the set of integer nonbasic variables. Gomory [18] proposed to consider the relaxation of the above problem obtained by dropping the nonnegativity conditions . This gives rise to the so called corner polyhedron. A further relaxation is obtained by also dropping the integrality conditions on the nonbasic variables, obtaining the mixed-integer set

 x=f+k∑j=1rjsj,x∈Zq,s≥0.

Note that, since is completely determined by , the above is equivalent to

 f+k∑j=1rjsj∈Zq,s≥0. (1)

We denote by the set of points satisfying (1). The above relaxation was studied by Andersen et al. [1] in the case of two rows and Borozan and Cornuéjols [10] for the general case. In these papers they showed that the irredundant valid inequalities for  correspond to maximal lattice-free convex sets in . In [1, 10] data are assumed to be rational. Here we consider the case were may have irrational entries.

Let be the linear space generated by . Note that, for every , the point , hence we assume contains an integral point. Let be the affine hull of . Notice that and coincide if and only if is a rational space. Borozan and Cornuéjols [10] proposed to study the following semi-infinite relaxation, which is a special case of Gomory and Johnson’s group problem [20]. Let be the set of points of satisfying

 f+∑r∈Wrsr∈Zq sr≥0,r∈W (2) s∈W

where is the set of all with finite support, i.e. the set has finite cardinality. Notice that .

Given a function and , the linear inequality

 ∑r∈Wψ(r)sr≥α (3)

is valid for if it is satisfied by every .

Note that, given a valid inequality (3) for , the inequality

 k∑j=1ψ(rj)sj≥α

is valid for . Hence a characterization of valid linear inequalities for provides a characterization of valid linear inequalities for .

Next we observe how maximal lattice-free convex sets in give valid linear inequalities for . Let be a maximal lattice-free convex set in containing in its interior. Since, by Theorem 1, is a polyhedron and since is in its interior, there exist such that . We define the function by

 ψB(r)=maxi=1,…,tair. (4)

Note that the function is subadditive, i.e. , and positively homogeneous, i.e. for every . We claim that

 ∑r∈WψB(r)sr≥1

is valid for .

Indeed, let , and . Since and is lattice-free, . Then

 ∑r∈WψB(r)sr=∑r∈WψB(rsr)≥ψB(∑r∈Wrsr)=ψB(x−f)≥1,

where the first equation follows from positive homogeneity, the first inequality follows from subadditivity of and the last one follows from the fact that .

We will show that all nontrivial irredundant valid linear inequalities for are indeed of the type described above. Furthermore, if is irrational, we will see that is contained in a proper affine subspace of , so each inequality has infinitely many equivalent forms. Note that, by definition of , if is not in the recession cone of , when is in the interior of the recession cone of , while when is on the boundary of the recession cone of . We will show that one can always choose a form of the inequality so that is a nonnegative function. We make this more precise in the next theorem.

Given a point , then . Recall that we denote by the affine hull of . Thus is contained in the affine subspace of defined as

 V={s∈W|f+∑r∈Wrsr∈V}.

Observe that, given and such that , we have

 V={s∈W|∑r∈W(Cr)sr=d−Cf}. (5)

Given two valid inequalities and for , we say that they are equivalent if there exist and such that and . Note that, if two valid inequalities and for are equivalent, then

A linear inequality that is satisfied by every element in is said to be trivial.

We say that inequality dominates inequality if for all . Note that, for any such that for all , if satisfies the first inequality, then also satisfies the second. A valid inequality for is minimal if it is not dominated by any valid linear inequality for such that . It is not obvious that nontrivial valid linear inequalities are dominated by minimal ones. We will show that this is the case. Note that it is not even obvious that minimal valid linear inequalities exist.

We will show that, for any maximal lattice-free convex set of with in its interior, the inequality is a minimal valid inequality for . The main result is a converse, stated in the next theorem. We need the notion of equivalent inequalities, which define the same region in .

###### Theorem 3.

Every nontrivial valid linear inequality for is dominated by a nontrivial minimal valid linear inequality for .
Every nontrivial minimal valid linear inequality for is equivalent to an inequality of the form

 ∑r∈WψB(r)sr≥1

such that for all and is a maximal lattice-free convex set in with in its interior.

This theorem generalizes earlier results of Borozan and Cornuéjols [10]. In their setting it is immediate that all valid linear inequalities are of the form with nonnegative. From this, it follows easily that must be equal to for some maximal lattice-free convex set . The proof is much more complicated for the case of when is an irrational space. In this case, valid linear inequalities might have negative coefficients. For minimal inequalities, however, Theorem 3 shows that there always exists an equivalent one where all coefficients are nonnegative. The function is nonnegative if and only if the recession cone of has empty interior. Although there are nontrivial minimal valid linear inequalities arising from maximal lattice-free convex sets whose recession cone is full dimensional, Theorem 3 states that there always exists a maximal lattice-free convex set whose recession cone is not full dimensional that gives an equivalent inequality. A crucial ingredient in showing this is a new result about sublinear functions proved in [9].

In light of Theorem 3, it is a natural question to ask what is the subset of obtained by intersecting the set of nonnegative elements of with all half-spaces defined by inequalities as in Theorem 3. In a finite dimensional space, the intersection of all half-spaces containing a given convex set is the closure of . Things are more complicated in infinite dimension. First of all, while in finite dimension all norms are topologically equivalent, and thus the concept of closure does not depend on the choice of a specific norm, in infinite dimension different norms may produce different topologies. Secondly, in finite dimensional spaces linear functions are always continuous, while in infinite dimension there always exist linear functions that are not continuous. In particular, half-spaces (i.e. sets of points satisfying a linear inequality) are not always closed in infinite dimensional spaces (see Conway [12] for example).

To illustrate this, note that if is endowed with the Euclidean norm, then belongs to the closure of with respect to this norm, as shown next. Let be an integral point in and let be defined by

 ¯sr={1k if r=k(¯x−f),0 otherwise.

Clearly, for every choice of , , and for that goes to infinity the point is arbitrarily close to with respect to the Euclidean

distance. Now, given a valid linear inequality for , since the hyperplane separates strictly from even though is in the closure of . This implies that is not a closed hyperplane of , and in particular the function is not continuous with respect to the Euclidean norm on .

A nice answer to our question is given by considering a different norm on . We endow with the norm defined by

 ∥s∥H=|s0|+∑r∈W∖{0}∥r∥|sr|.

It is straightforward to show that is indeed a norm. Given , we denote by the closure of with respect to the norm .

Let be the family of all maximal lattice-free convex sets of with in their interior.

###### Theorem 4.
 ¯¯¯¯¯¯¯¯¯¯¯conv(Rf(W))={s∈V|∑r∈WψB(r)sr≥1B∈BWsr≥0r∈W}.

Note that Theorems 3 and 4 are new even when .

A valid inequality for is said to be extreme if there do not exist distinct functions and satisfying , such that , , are both valid for . The above definition is due to Gomory and Johnson [20]. Note that, if an inequality is not extreme, then it is not necessary to define .

The next theorem exhibits a correspondence between extreme inequalities for the infinite model and extreme inequalities for some finite problem where . The theorem is very similar to a result of Dey and Wolsey [15].

###### Theorem 5.

Let be a maximal lattice-free convex set in with in its interior. Let and let . Then , is a rational space, and is a polytope. Let be the vertices of , and be a rational basis of . Define for .

Then the inequality is extreme for if and only if the inequality is extreme for .

Even though the data in integer programs are typically rational and studying the infinite relaxation (1) for seems natural [10, 13], some of its extreme inequalities arise from maximal lattice-free convex sets that are not rational polyhedra [13].

For example, the irrational triangle defined by the inequalities is a maximal lattice-free convex set in the plane, and it gives rise to an extreme valid inequality for for any rational in the interior of . In fact, every maximal lattice-free triangle gives rise to an extreme valid inequality for  [13]. Therefore, even when in (1), irrational coefficients are needed to describe some of the extreme inequalities for . Indeed, it follows from Theorem 3 and from [10] that the extreme inequalities for are precisely the restrictions to of the extreme inequalities for . This suggests that the more natural setting for (1) might in fact be .

The paper is organized as follows. In Section 2 we will state and prove the natural extensions of Theorems 1 and 2 for general lattices. In Section 3 we prove Theorem 3, while in Section 4 we prove Theorem 4 and in Section 5 we prove Theorem 5.

## 2 Maximal lattice-free convex sets

Given , we denote by the linear space generated by the vectors in . The underlying field is in this paper. The purpose of this section is to prove Theorems 1 and 2. For this, we will need to work with general lattices.

###### Definition 6.

An additive group of is said to be finitely generated if there exist vectors such that .

If a finitely generated additive group of can be generated by linearly independent vectors , then is called a lattice of the linear space . The set of vectors is called a basis of the lattice .

###### Definition 7.

Let be a lattice of a linear space of . Given a linear subspace of , we say that is a -subspace of if there exists a basis of contained in .

For example, in , consider the lattice generated by vectors and . The line is a -subspace, whereas the line is not.

Given and , we will denote by the open ball centered at of radius . Given an affine space of and a set , we denote by the interior of with respect to the topology induced on by , namely is the set of points such that for some . We denote by the relative interior of , that is .

###### Definition 8.

Let be a lattice of a linear space of , and let be a linear space of containing . A set is said to be a -free convex set of if , is convex and , and is said to be a maximal -free convex set of if it is not properly contained in any -free convex set.

The next two theorems are restatements of Theorems 1 and  2 for general lattices.

###### Theorem 9.

Let be a lattice of a linear space of , and let be a linear space of containing . A set is a maximal -free convex set of if and only if one of the following holds:

• is a polyhedron in , , is a maximal -free convex set of , the facets of and are in one-to-one correspondence and for every facet of , is the facet of corresponding to ;

• is an affine hyperplane of of the form where and is a hyperplane of that is not a lattice subspace of ;

• is a half-space of that contains on its boundary.

###### Theorem 10.

Let be a lattice of a linear space of . A set is a maximal -free convex set of if and only if one of the following holds:

• is a polyhedron of the form where is a polytope, is a -subspace of , , does not contain any point of in its interior and there is a point of in the relative interior of each facet of ;

• is an affine hyperplane of of the form where and is not a -subspace of .

### 2.1 Proof of Theorem 9

We assume Theorem 10 holds. Its proof will be given in the next section.

() Let be a maximal -free convex set of . We show that one of holds. If , then cannot occur and either or follows from Theorem 10. Thus we assume .

Assume first that . Then there exists a hyperplane of containing , and since , then by maximality of . Since is a hyperplane of , then either or is a hyperplane of . If , then let be one of the two half spaces of separated by . Then , contradicting the maximality of . Hence is a hyperplane of . We show that is a maximal -free convex set of . Indeed, let be a convex set in such that and . Since , then . By maximality of , , hence .
Given , for some hyperplane of , and . Applying Theorem 10 to , we get that is not a lattice subspace of , and case holds.

So we may assume . Since is convex, then . We consider two cases.

Case 1. .

Since and are nonempty disjoint convex sets, there exists a hyperplane separating them, i.e. there exist and such that for every and for every . Since is a linear space, then for every , hence . Then the half space contains and lies on the boundary of . Hence is a maximal -free convex set of containing , therefore by the maximality assumption, so holds.

Case 2. .

We claim that

 intW(S)∩V=intV(S∩V). (6)

To prove this claim, notice that the direction is straightforward. Conversely, let . Then there exists such that . Since , there exists . Then there exists such that . We may assume since otherwise the result holds. Since , there exists such that is in the relative interior of the segment . Since , and therefore . The ball with radius is contained in . By convexity of , and therefore . Thus . Since , it follows that .

Let . By (6) and because , we have . We show that is a maximal -free convex set of . Indeed, let be a convex set in such that and . Since , Claim (6) implies that . By maximality, , hence .

Since , by Theorem 10 applied to , is a polyhedron with a point of in the relative interior of each of its facets. Let be the facets of . For , let be a point in . By (6), . By the separation theorem, there exists a half-space of containing such that . Notice that is on the boundary of . Then . By construction , hence by maximality of , . For every , contains . Therefore defines a facet of for .

() Let be a set in satisfying one of . Clearly is a convex set in and , so we only need to prove maximality. If satisfies , then this is immediate. This is also immediate when satisfies and . So we may assume that either satisfies (i) and , or satisfies .

Suppose that there exists a closed convex set strictly containing such that . Let . Then . To conclude the proof of the theorem, it suffices to prove that is strictly contained in . Indeed, by maximality of , this claim implies that the set contains a point in . Now implies that contains a point of , a contradiction.

It only remains to prove that . This is clear when is a hyperplane satisfying (ii). The statement is also clear if . Assume now that is a polyhedron satisfying (i) and and that . Let be a facet of that separates from . If is contained in a proper face of , then is contained in at least two facets of , a contradiction to the one-to-one correspondence property. So is not contained in proper face of . Therefore, there exists . Choose such that . Note that since otherwise but this is a contradiction since , and , .

Let . Note that and are distinct affine hyperplanes of . Let be the two open half-spaces of defined by , and assume w.l.o.g. that . Since , contains some point . Since , it follows that . Let be the line segment joining and . Since and it follows that contains exactly one point, say . Note that . Since and , we have that but . ∎

### 2.2 Proof of Theorem 10

To simplify notation, given , we denote simply by .

The following standard result in lattice theory provides a useful equivalent definition of lattice (see Barvinok [7], p. 284 Theorem 1.4).

###### Theorem 11.

Let be the additive group generated by vectors . Then is a lattice of the linear space if and only if there exists such that for every .

In this paper we will only need the “only if” part of the statement, which is easy to prove (see [7], p. 281 problem 5). Theorem 11 implies the following result (see [7], p. 281 problem 3).

###### Corollary 12.

Let be a lattice of a linear space of . Then every bounded set in contains a finite number of points in .

Throughout this section, will be a lattice of a linear space of . The following lemma proves the “only if” part of Theorem 10 when is bounded and full-dimensional.

###### Lemma 13.

Let be a bounded maximal -free convex set with . Then is a polytope with a point of in the relative interior of each of its facets.

###### Proof.

Since is bounded, there exist integers such that is contained in the box . For each , since is convex there exists a closed half-space of such that and . By Corollary 12, is finite, therefore is a polyhedron. Thus is a polytope and by construction . Since and for every , it follows that . By maximality of , , therefore is a polytope. We only need to show that has a point of in the relative interior of each of its facets. Let be the facets of , and let be the closed half-space defining , . Then . Suppose, by contradiction, that one of the facets of , say , does not contain a point of in its relative interior. Given , the polyhedron is a polytope since it has the same recession cone as . The polytope contains points of in its interior by the maximality of . By Corollary 12, has a finite number of points in , hence there exists one minimizing , say . By construction, the polytope does not contain any point of in its interior and properly contains , contradicting the maximality of . ∎

We will also need the following famous theorem of Dirichlet.

###### Theorem 14 (Dirichlet).

Given real numbers with , there exist integers and such that

 ∣∣∣αi−piq∣∣∣<εq, for i=1,…,n, and 1≤q≤ε−1. (7)

The following is a consequence of Dirichlet’s theorem.

###### Lemma 15.

Given and , then for every and , there exists a point of at distance less than from the half line

###### Proof.

First we show that, if the statement holds for , then it holds for arbitrary . Given , let be the set of points of at distance less than from . Suppose, by contradiction, that no point in has distance less than from . Then is contained in . By Corollary 12, is finite, thus there exists an such that every point in has distance greater than from , a contradiction. So we only need to show that, given , there exists at least one point of at distance at most from . We may assume .

Without loss of generality, assume . Let and be a basis of . Then there exists such that . Denote by the matrix with columns , and define where, for a vector , denotes the Euclidean norm of . Choose such that and . By Dirichlet’s theorem, there exist and such that

 ∥α−pλ∥= ⎷m∑i=1∣∣∣αi−piλ∣∣∣2≤δ√mλ≤ε∥A∥λ.

Let . Since , then . Note that since , where the first inequality follows from the definition of and the last one follows from the assumptions on , and . Therefore, . Furthermore

 ∥(y+λr)−z∥=∥λr−Ap∥=∥A(λα−p)∥≤∥A∥∥λα−p∥≤ε.

###### Lemma 16.

Let be a -free convex set, and let . Then also is -free.

###### Proof.

Let , . We only need to show that is -free. Suppose there exists . We show that . Suppose not. Then

format: plain


text:
# Present Value Calculator

Instructions:Use this Present Value Calculator to compute the present value ($$PV$$) by indicating the future value ($$FV$$), the interest rate ($$r$$), number of years ($$n$$) the money will be invested, and the type of compounding (yearly, bi-yearly, quarterly, monthly, weekly, daily or continuously):

Future Value $$(FV)$$ =
Number of Years $$(n)$$ =
Interest Rate $$(r)$$ =
Compounding Period:

## Present Value Calculator

More about the this present value calculator so you can better understand how to use this solver: The present value ($$PV$$) of a certain amount of money that will have certain future value ($$FV$$) after a number of years, depends on the number of years $$n$$ when the money will be received, the interest rate $$r$$, the type of compounding (yearly, bi-yearly, quarterly, monthly, weekly, daily or continuously). Let $$k$$ be the number of times the money is compounded in a year. For example, for yearly compounding we have $$k = 1$$, for bi-yearly compounding we have $$k = 2$$, for quarterly compounding we have $$k = 4$$, etc. The present value ($$PV$$) can be computed using the following formula:

$PV = \frac{FV}{\left( 1+\frac{r}{k}\right)^{ k \times n} }$

For continuous compounding, we get that $$k \to \infty$$, in which case we need to use the following formula instead.

$PV = \frac{FV}{e^{r \times n}}$

What this present value calculator does is simply find a compounding factor, which is used to bring future money into present money. The same task can be conducted with Excel, using the PV() function, with the difference that this calculator shows all the steps.

Notice that this calculator does include the possibility of payments. If there are periodic payments, then you should use an annuity calculator, and the more general case of computing the net present value of a sequence of flows, you can use this net present value calculator.

If instead you know the present value and you want to compute the future value, use this calculator.

In case you have any suggestion, or if you would like to report a broken solver/calculator, please do not hesitate to contact us.


text:
[Tex/LaTex] Highlighting haskell listings in large *.tex document

beamerlistingstex-core

Suppose, there is a large *.tex document, which has many nested \input directives with many Haskell listings surrounded by \begin{code} \end{code}
commands.

How can all this code listings be highlighted like all haskell code is highlighted in many haskell papers (functional pearls is a good example)?

I heard, that many haskell papers written in lhs and then transferred to tex via lhs2tex. Yep, this is a nice tool, but it produces whole tex document and it is hard to be usable for the task like mine.

Btw, I've tried lstlistings and fancyvrb – it's far away from ideal.

I was pleased with my lstlistings setup which I used in my bachelor thesis:

\lstset{
frame=none,
xleftmargin=2pt,
stepnumber=1,
numbers=left,
numbersep=5pt,
numberstyle=\ttfamily\tiny\color[gray]{0.3},
belowcaptionskip=\bigskipamount,
captionpos=b,
escapeinside={*'}{'*},
tabsize=2,
emphstyle={\bf},
stringstyle=\mdseries\rmfamily,
showspaces=false,
keywordstyle=\bfseries\rmfamily,
columns=flexible,
basicstyle=\small\sffamily,
showstringspaces=false,
morecomment=[l]\%,
}

You can find some examples in my thesis: https://www.dropbox.com/sh/zu56xcp1mj57ikq/TtFoHKmOLV/thesis.pdf

I can also provide the whole .tex source if needed.


text:
# What is the difference between an open equation and a closed equation?

Question 144105: What is the difference between an equation and an expression? Answer by nabla(475) (Show Source): You can put this solution on YOUR website! - Read more

... What is the difference between the diffusion equation and the wave equation? : ... wave equation in one space dimension has two ... If someone opens a ... - Read more

## What is the difference between an open equation and a closed equation? resources

### What Is the Difference Between Open & Closed Chamber ...

Open and closed chamber cylinder ... The difference between an open and closed syllable ... though a supercharger adds a complicating factor to the equation.

### DSP- difference between Differential and Difference equation

What is the difference between a Differential equation and a Difference ... This is a second order differential equation Difference equation is type of recurrence ...

### Describe the difference between an open equation and a ...

Describe the difference between an open equation and a closed equation.

### Difference Between Expression and Equation

Difference Between Expression and Equation. ... if you were to ask the difference between an expression ... Difference Between Difference Equation and ...

### What is the difference between a differential equation and ...

What is the difference between a differential equation and a ... "Solving the equation" means finding a closed form ... difference equation ? Differential ...

### What Is the Difference Between a Quadratic and a Linear ...

Students are often tripped up by the difference between quadratic ... to recognize the differences between these equations and ... opens downward and ...

### SOLUTION: What is the difference between a solution and an ...

SOLUTION: What is the difference between a solution and an equation? ... Equations often contain one or more unknowns, or variables, as "x" in the examples above.

### What Is The Difference Between Degree And Order Of The ...

What Is The Difference Between A Complete Ionic Equation And A Net Ionic Equation? Chemistry.

### thermodynamics - Difference between Clausius-Clapeyron and ...

I was wondering what is the difference between the Clausius-Clapeyron equation and the Van't Hoff equation.

### What is the difference between a function and an equation ...

What is the difference between a mathematical function ... what is the difference between a function and a equation what's ...

### The Difference Between an Expression and an Equation - YouTube

This video explains the difference between an expression and an equation. Site: http://mathispower4u.com Blog: http://mathispower4u.wordpress.com.

### Difference Between Expression and Equation | Difference ...

"Difference Between Expression and Equation." DifferenceBetween.net. December 9, ... Differences between gender and sexuality; Most Emailed Comparisons.

### What Is the Difference Between Resolution & Ending When ...

What Is the Difference Between Resolution & Ending ... The English department at the University of New Mexico defines narratives as having either a closed or an open ...

### Chapter 2.1 – Open Sentences and Solution Sets The ...

The difference between an expression and an equation: ... ≥ are equations (math sentences). • open sentences contain variables that ... • Closed sentences ...

### What is the difference between an algebraic expression and ...

What is the difference between an algebraic expression and an equation? What clues could help determine between equations and expressions?

### What Is The Difference Between An Instantaneous ...

What is the difference between an instantaneous rate equation and an integrated rate equation? USE GRAPHS OR DRAWINGS IN YOUR EXPLANATION!!

### Difference between an equation and an expression

Difference between an equation and an ... First, I need to clarify a common misunderstanding between 'solving equation' and 'simplifying expression' before explaining ...

### Differential equation - Wikipedia, the free encyclopedia

5 Connection to difference equations; ... to bridge design, to interactions between neurons. Differential equations such ... MIT Open CourseWare Videos; Paul ...

### Differences between MathType and Equation Editor format in ...

Differences between MathType and Equation Editor format in Microsoft Word? up vote 3 down vote favorite. ... I'm not sure what the difference between the formats is.

### Difference between a formula and a equation

... the difference between a formula and a equation. Any help would be much apreciated. chris: ... An equation is a relation between two parts, ...

### math mode - What's the difference between  and \begin ...

I don't know the difference between $$... end{equation}. What's the difference between$$... and ... from the conductor at an open circuit under the ...

### What is the difference between an equation and an ...

What is the difference between an equation and an expression? Include an example of each. Can you solve for a variable in an expression? Explain.

### Difference Between Parabola and Hyperbola | Difference ...

... they are not closed curves like a circle or an ellipse. ... The parabola is given by the equation y2=X ... "Difference Between Parabola and Hyperbola."

### What is the difference between chemical formula, chemical ...

Science Homework Help. Question: What is the difference between chemical formula, chemical symbol, and chemical equation?, Topics: Science, Tags: chemistry, Science

### What are the differences between a linear equation and a ...

A quadratic equation is only different from a linear equation in one respect: one or more of the figures is squared. ... Ok, we know the difference between the two.

### terminology - What is the difference between the terms ...

What is the difference between the terms 'equation' and ... I'm actually a Creative Writing major and writing a story where a character explains the difference ...

### What is the Difference Between an Equation and an Expression

If you are wondering what the difference between an equation and an expression is, ... What is the Difference Between an Equation and an Expression

Related Questions

Recent Questions


text:
+0

# cylinders

-1
139
1
+204

A cylindrical quarter has a $\frac{15}{16}$ inch diameter and a $\frac{1}{16}$ inch height. What would be the number of inches in the height of a coin whose volume is exactly four times that of the given quarter and whose diameter equals $1 \frac{1}{8}$ inches? Express your answer as a common fraction.

Feb 25, 2021

The volume is proportional to $r^2$, so we multiply by $\left(\frac{\frac{9}{8}}{\frac{15}{16}}\right)^2=\left(\frac{6}{5}\right)^2=\frac{36}{25}$. It's proportional to the height itself, so we want to multiply by $\frac{4}{\frac{36}{25}}=\frac{25}{9}$. So $\frac{1}{16}*\frac{25}{9}=\boxed{\frac{25}{144}}$.


text:
Tag Info

Hot answers tagged spectrogram

17

If the spectrogram was computed as the magnitude of short time fourrier transforms from overlapping windows, then the spectrogram contains implicitly some phase information. The following iterations do the job : $$x_{n+1} = \text{istft}(S\cdot\exp(i\cdot\text{angle}(\text{stft}(x_n))))$$ $S$ is the spectrogram, $\text{stft}$ is the forward-short time ...

8

Definitely you will have to calibrate your system. You need to know what is the relationship between dBFS (Decibel Full-Scale) and dB scale you want to measure. In case of digital microphones, you will find sensitivity given in dBFS. This corresponds to dBFS level, given 94 dB SPL (Sound Pressure Level). For example this microphone for input $94 \;\mathrm{... 8 Since this is a constant spectrogram, you could just as well have just averaged the |FFT|² and plotted that! (The most colorful way of visualizing things isn't always the optimal one; your signal doesn't change over time, so you don't need the time axis of the spectrogram at all.) Quite possibly, in that "easier" representation, you would have ... 7 You don't have a loss in time precision when using FFTs because the FFT is fast. The FFT is just a fast algorithm for implementing the discrete Fourier transform (DFT), nothing more. Instead, there is an inherent tradeoff in time and frequency resolution due to the Heisenberg uncertainty principle. While its statement is explicitly focused at quantum ... 7 The problem is not the spectrogram parameters, these are correct since they only depend on what resolution you want in time and frequency domain. Also, the spectrogram interpretation is correct, there are multiple frequency peaks. The problem may be: I expected to see one high power frequency after pressure rise, instead of multiple frequencies Why? If ... 6 For the first few experiments I would recommend using a scripting language like Matlab or Python. They're much easier to understand and much quicker to write than "lower level programming languages" like C++. Matlab has a signal processing toolbox and can read and write audio files, do windowing, FFTs etc. as well as a very simple playback mechanism. Basic ... 6 Why are my peaks capped? Your amplification gain is set to too high, or you are too close to the microphone. The amplifier is driven to its limits and it clips the output. Keep this recording and make another one where you are a little bit further away from the microphone to later compare the differences in the spectrogram. It will be interesting to see how ... 5 Both taking a magnitude spectrogram and a Mel filter bank are lossy processes. Important information needed to reconstruct the original will have been lost. Thus you need to go back and use the original audio samples to do the reconstruction by determining a time or frequency domain filter equivalent to your dimensionality reduction. You can make ... 5 Please check this answer, which describes a few approaches to the same problem. Given that bird song is a monophonic signal (only one fundamental frequency at any point in time - as opposed to polyphonic) - and given that the timbre is irrelevant, the most interesting feature to extract for this classification task is a pitch contour. 5 This happens because your window is too short. I don't have access to a plotting tool right now, but imagine for a second a slowly varying sinusoid that you chop up into pieces, and these pieces are shorter than the period of your sinusoid. If you take the Fourier transform of each of these pieces, some of your chunks will capture more energy of this ... 5 In discrete signal processing the frequency domain axis topology is surprisingly not a straight line, but a closed circle. Therefore the upper and lower edge of your image are really "identified", meaning they are connected and direct neighbors. The modulation you're seeing is the beating of the two interfering components coming closer. The window size has ... 5 Another thing the OP can do is use the "complex" chirp. What you really have to do is (at two different times and both times sweeping all frequencies from -Nyquist through DC to +Nyquist) pass the real part,$x_r(t)=\cos(\pi \beta t^2)$and then pass the imaginary part$x_i(t)=\sin(\pi \beta t^2)$of the complex chirp through the material under test and ... 5 Since the input signal is real, half of the FFT data is "useless" because it is simply the complex conjugate of the other half. More precisely, a 256-long FFT of a real signal will give you: the DC amplitude, 127 amplitudes, the amplitude at Nyquist, and 127 conjugate amplitudes. Among the 700 chunks, 256 / 32 - 1 = 7 extend outside the boundaries of the ... 5 I understand the concept of the STFT. In order to avoid spectral leakage, you use a hann window that overlaps by 50%. I'm sorry but you have a misunderstanding of spectral leakage in addition to how a spectogram should be computed. To be exact you cannot avoid spectral leakage completely; all you can do is to make a compromise between the spectral ... 5 I recommend a Synchrosqueezed Continuous Wavelet Transform representation, available in ssqueezepy. Synchrosqueezing arose in context of audio processing (namely speaker identification), and there's much literature on applying CWT for audio tasks. Advantage over STFT is the inherently logarithmic nature of the feature extractor, matching audio structuring. ... 4 None of these spectrograms show music. I would validate your algorithms by substituting a known signal, e.g. a 440 Hz pure tone. That should be a single line in your spectrogram. Audacity can generate that as a .wav file, but you can also numerically generate the signal in Python. Next, mix two known tones and check if your spectrogram is lineair (i.e. ... 4 Polyphonic pitch estimation is still a difficult problem. Search on the MIREX forum for current research papers. Simplistic spectrum based approaches usually require component pitches with extremely simple timbres (nearly pure unmodulated sine waves, etc.) rarely found in real-life polyphonic music. More typical polyphonic music can contain a dense set of ... 4 After wasting forever on this problem, I found that it was just a question of window function. Doh! Window functions that are not zero-ended produce these vertical lines. For example, Rectangular Window, Hamming Window, Gaussian Window (with low sigma) produce these lines, and Barlett Window, Hanning Window, Blackmann Window, Welch Window, don't. I had ... 4 I had a bit of a hard time to understand the answer of @edouard, which is doing the right thing. Compare to https://dsp.stackexchange.com/a/3410/9031 , which I used to implement my reconstruction. Note that$i$is the imaginary number, and$x_n$is the reconstructed signal at the$n^{\text{th}}$iteration. Start with$x_0\$ being a random vector of length ...

4

To illustrate what both @Jazzmaniac and @Phonon are telling you, let's look at the same plot, but for different window lengths. Another change is to look at the plots using the fftshift view --- so that it's clearer that the low positive frequency peaks are close to the low negative frequency peaks. The picture below plots the contour plot of the data you ...

4

After subtracting Fs/2 from F to get a frequency axis from -Fs/2 -> Fs/2 rather than from 0->Fs You can't center the frequency by changing the labels on the x-axis. Use 'fftshift' instead.

4

Wavelets are ideal for localized events. The Fourier Transform represents a function as a sum of sines and cosines, neither of which are localized. The spectrogram does keep some time information, at the expense of frequency resolution In your case, the signal is not localized at all. The spectrogram smears your 15 Hz band over several Hz, as it captures ...

4

Yes, the easiest way to do this is using reshape and FFT, since reshape will give you a matrix and the FFT will operate along a dimension of the matrix. I've applied a 1024 rectangular window on a data set of 65536 points, sampling frequency Fs (1024), and signal frequency (100). x = randn(1, 65536) + cos(2*pi*100/1024*(0:65536-1)); z = reshape(x, 1024, []);...

4

The answer from @orgeGT is quite detailed. It really looks like, to me, a pressure signal from a knocking gazoline engine, where you observe a wide band effect (the impulse part of the knock) and resonant frequencies and their harmonics (the wiggling part of the knock), and a (slight) decay in their amplitude, related to the variations of the volume of the ...

4

Looking at the spectrogram, the prominent artifacts go up or down in frequency synchronously to the 138 MHz signal but have larger bandwidths. That is an indication that they are its harmonics, due to a nonlinearity somewhere in the system. With the sampling frequency of 500 MHz some of the positive and negative harmonics alias to the following (bold) ...

4

The "dimensions" of the spectrogram are not chosen based on where will the spectrogram be fed to but rather depend on your application. Therefore, it is key to understand the spectrogram itself first, as a means of generating features for one or more signals and to an extent, understand the Discrete Fourier Transform (DFT) as well, which is the key operation ...

4

Real/imaginary or modulus/phase are two representations of a complex number that carry the same level of information. Then, a STFT is a redundant mapping from a space of functions over a 1D variable (time) onto a space of functions over a 2D variable (time and frequency). Under mild conditions on the window, there are an infinity of inverses, due to the ...

3

Firstly $$abs(z)^{2}=Re \left \{ z \right \}^{2}+Im \left \{z \right \}^{2}=z*z^{^{'}}$$ These are all mathematically identical, so either one will work. That leaves the question of whether the square should be applied or not. In nearly all cases the original signal will represent a "linear" quantity such as voltage, current, force, pressure, particle ...

3

The vertical lines you see could be clipping. I assume you took a loud MP3 file, decoded it to something like a linear PCM-Wave whith clipping and feed your program with it. As far as, I know Audacity decodes MP3 to 32bit floats internally which does not suffer from clipping issues. This could explain why the Audacity spectrogram looks clean. So, if this is ...

3

Windowing is nothing more than element-wise multiplication of your signal by window function. Let's assume that you want to apply Hanning window. In your case signal is stored inside myRecording(start_sample:end). Create the window values vector of your signal length: win = hann(length(myRecording(start_sample:end))) Multiply by your signal and store it ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Streaming support

Both input and output bodies can be mapped to a stream, by using stream[*]Body(streams). The parameter streams must implement the Streams[S] capability, and determines the precise type of the binary stream supported by the given non-blocking streams implementation. The interpreter must then support the given capability. Refer to the documentation of server/client interpreters for more information.

Note

Here, streams refer to asynchronous, non-blocking, “reactive” stream implementations, such as akka-streams, fs2 or zio-streams. If you’d like to use blocking streams (such as InputStream), these are available through e.g. inputStreamBody without any additional requirements on the interpreter.

Adding a stream body input/output influences both the type of the input/output, as well as the 5th type parameter of Endpoint, which specifies the requirements regarding supported stream types for interpreters.

When using a stream body, a schema must be provided for documentation. By default, when using streamBinaryBody, the schema will simply be that of a binary body. If you have a textual stream, you can use streamTextBody. In that case, you’ll also need to provide the default format (media type) and optional charset to be used to determine the content type.

To provide an arbitrary schema, use streamBody. Note, however, that this schema will only be used for generating documentation. The incoming stream data will not be validated using the schema validators.

For example, to specify that the output is an akka-stream, which is a (presumably large) serialised list of json objects mapping to the Person class:

import sttp.tapir._
import sttp.tapir.generic.auto._
import sttp.capabilities.akka.AkkaStreams


text:
Of Wiggle Photography [CoffeeScript]

Demo

Click to test any of those !
[ poulejapon ] [ boobs ] [ finger ]

Wiggle Stereoscopy

Wiggle stereoscopy is probably the cheapest trick to give your brain a 3D feeling. While most technics try to take advantage of binocular vision by giving your left eye and your right eye different pictures, wiggle stereoscopy is just about looping on a couple of pictures with a slight shift of point of view. Your brain will interpret the parallax and give you a sense of 3D. What’s parallax ? Imagine you’re in the mountain driving in a car. You’re looking out the window. Objects far away are moving slowly, objects closer seem to move very fast. That’s parallax!

In this post, I’ll show how to implement this effect with CoffeeScript, Canvas (no need for WebGL, Flash or anything), and simple image editor.

Depth Map

But first, we need to be able to get a description of the 3D shape of our picture. The three animation above have been created very simply from 2D-images.. The 3D information has been added using a “depth map”. A depth consists of an image of the same size of your original picture, but encoding the z-coordinates of each pixel. Basically it’s encoding how close to us the pixel is supposed to be.

To create one, just open your favorite image editor, and create a new picture. Fill it with black. Black will be our background background. It is assumed to be far away. Now just pain very roughly in grays shades the region you want to “pop out”. The brighter it is, the closer it will feel. Don’t try to be too accurate, 3 shades are probably sufficient.

At this point the resulting depth map probably consists of a couple of wide areas associated to different levels. But let’s get real, most of the world is not that square. One very neat trick here is to smooth your depth map with a gaussian blur. It will very likely make everything look more natural. And to tell the truth, our rendering will look very shitty if your depth map is not smooth.

The poor man’s 3D

We could write a ray-tracer, but I’m afraid it might take a little too long at execution (And I’m lazy, so proove me wrong internet!). Instead we’re going to do something very cheap. High Schooler cheap actually. We’ll do the opposite of ray tracing and compute the project of the point of our initial image into our camera’s sensor.

So let’s take a look at the geometry of our little problem here. Given (i,j) and its depth d(i,j), we want to find the coordinates (x,y) of its projection in our camera. In order to get a nice effect we decided that all the camera were pointing at a very specific point of the image, which would always be projected at the center of our rendered image (x0, y0).

For simplification I did a little schema in 2D but it is actually to adapt it to 3D. We just apply Thales theorem to this problem in order to get the distance x of the projected point to the center of our rendered image x0.

Ok so we assume we are looking to the center O of our scene, and take this point as the depth 0 reference. It means that the image of O is the center Q of our scene. H is the projection of the camera C on the scene plan.

Given a pixel at a position i, it’s image A is at a depth d(i). We want to find the coordinates of its image on the projection screen (Or rather, the sensor of our camera). Basically we want to find the distance QB=y.

Thalès gives us the answer to this problem : $y=QB=\frac{L}{L-d}\left(i - {c_x} \right ) +{c_x}$

So if we have a value for a pixel at coordinates (i,j) it should be projected into the pixel (x,y) such that :

$\left\{\begin{matrix} x=\frac{L}{L-d}\left(i-{c_x}\right)+{c_x}\\ y=\frac{L}{L-d}\left(j-{c_y}\right)+{c_y} \end{matrix}\right.$

where cx and cy is the coordinates of the projection of the camera on the scene.

Actually here our projection screen has been considered parallele to the scene for this simple version, we might want to keep it perpendicular to the axis of the camera. With the value we used for our camera, the correcting factor was however neglectable (0.99 instead of 1).

render_scene = (img, depth, camera)->
# the poor man's 3d
W = img.width
H = img.height
dest = create_image_data W,H
imgp = img.data
depthp = depth.data
destp = dest.data
x0 = Math.ceil (W/2)
y0 = Math.ceil (H/2)
d0 = depthp[ (x0+W*y0)*4 ]
c = 0
N = W*H*4
for j in [0...H]
for i in [0...W]
d = (depthp[c]-d0)
r = camera.L  / (camera.L - d)
# compute x,y : the projection of pixel (i,j,d)
# according to our camera.
x = Math.floor(x0 - camera.x + (camera.x + i - x0)) * r
y = Math.floor(y0 - camera.y + (camera.y + j - y0)) * r
destc = (x+W*y)*4
if (0 <= destc < N)
for v in [0..3]
destp[destc+v] = imgp[c+v]
c+=4
fill_with_average destp, W, H
for c in [0...W*H*4] by 4
destp[c+3] = 255
return dest

At the end of the function we are calling a function called fill_with_average. It is here to fill the gap. Since we are just moving pixels, some pixel are likely to get moved to the same destination pixels… Which means that we get some gaps in the destination image. Yes that’s a cheap algorithm, but we just run a small method to detect these gap pixels and fill them with an average of their neighbors.

Wiggle stereography typically use two pictures. Actually I found that the effect was much more efficient if we were rendering a lot of pictures, just turning around given point of view.

You can check out the final script on github.


text:
# Geometric norm

(Redirected from Bulk norm)

The geometric norm is a measure of the magnitude of an element that possesses the geometric property. It is the ratio of the bulk norm and the weight norm.

## Bulk Norm

The bulk norm of an element $$\mathbf a$$, denoted $$\left\Vert\mathbf a\right\Vert_\unicode{x25CF}$$, is the magnitude of its bulk components. It can be calculated by taking the square root of the geometric product of $$\mathbf a_\unicode{x25CF}$$ with its own reverse:

$$\left\Vert\mathbf a\right\Vert_\unicode{x25CF} = \sqrt{\mathbf a_\unicode{x25CF} \mathbin{\unicode{x27D1}} \mathbf{\tilde a}_\unicode{x25CF}}$$ .

If $$\mathbf a$$ possesses the geometric property, then the $$\unicode{x25CF}$$ subscripts inside the radical can be dropped because $$\mathbf a_\unicode{x25CF} \mathbin{\unicode{x27D1}} \mathbf{\tilde a}_\unicode{x25CF} = \mathbf a \mathbin{\unicode{x27D1}} \mathbf{\tilde a}$$.

An element that has a bulk norm of 1 is said to be bulk normalized.

The following table lists the bulk norms of the main types in the 4D projective geometric algebra $$\mathcal G_{3,0,1}$$.

Type Definition Bulk Norm
Point $$\mathbf p = p_x \mathbf e_1 + p_y \mathbf e_2 + p_z \mathbf e_3 + p_w \mathbf e_4$$ $$\left\Vert\mathbf p\right\Vert_\unicode{x25CF} = \sqrt{p_x^2 + p_y^2 + p_z^2}$$
Line $$\mathbf L = v_x \mathbf e_{41} + v_y \mathbf e_{42} + v_z \mathbf e_{43} + m_x \mathbf e_{23} + m_y \mathbf e_{31} + m_z \mathbf e_{12}$$ $$\left\Vert\mathbf L\right\Vert_\unicode{x25CF} = \sqrt{m_x^2 + m_y^2 + m_z^2}$$
Plane $$\mathbf f = f_x \mathbf e_{234} + f_y \mathbf e_{314} + f_z \mathbf e_{124} + f_w \mathbf e_{321}$$ $$\left\Vert\mathbf f\right\Vert_\unicode{x25CF} = |f_w|$$
Motor $$\mathbf Q = r_x \mathbf e_{41} + r_y \mathbf e_{42} + r_z \mathbf e_{43} + r_w {\large\unicode{x1d7d9}} + u_x \mathbf e_{23} + u_y \mathbf e_{31} + u_z \mathbf e_{12} + u_w$$ $$\left\Vert\mathbf Q\right\Vert_\unicode{x25CF} = \sqrt{u_x^2 + u_y^2 + u_z^2 + u_w^2}$$
Flector $$\mathbf G = s_x \mathbf e_1 + s_y \mathbf e_2 + s_z \mathbf e_3 + s_w \mathbf e_4 + h_x \mathbf e_{234} + h_y \mathbf e_{314} + h_z \mathbf e_{124} + h_w \mathbf e_{321}$$ $$\left\Vert\mathbf G\right\Vert_\unicode{x25CF} = \sqrt{s_x^2 + s_y^2 + s_z^2 + h_w^2}$$

## Weight Norm

The weight norm of an element $$\mathbf a$$, denoted $$\left\Vert\mathbf a\right\Vert_\unicode{x25CB}$$, is the magnitude of its weight components. It can be calculated by taking the square root of the geometric antiproduct of $$\mathbf a_\unicode{x25CB}$$ with its own antireverse:

$$\left\Vert\mathbf a\right\Vert_\unicode{x25CB} = \sqrt{\mathbf a_\unicode{x25CB} \mathbin{\unicode{x27C7}} \smash{\mathbf{\underset{\Large\unicode{x7E}}{a}}}_\unicode{x25CB}\vphantom{\mathbf{\tilde a}}}$$ .

Note that the square root in this case is taken with respect to the geometric antiproduct. If $$\mathbf a$$ possesses the geometric property, then the $$\unicode{x25CB}$$ subscripts inside the radical can be dropped because $$\mathbf a_\unicode{x25CB} \mathbin{\unicode{x27C7}} \smash{\mathbf{\underset{\Large\unicode{x7E}}{a}}}_\unicode{x25CB} = \mathbf a \mathbin{\unicode{x27C7}} \smash{\mathbf{\underset{\Large\unicode{x7E}}{a}}}$$.

An element that has a weight norm of $$\large\unicode{x1D7D9}$$ is said to be weight normalized or unitized.

The following table lists the weight norms of the main types in the 4D projective geometric algebra $$\mathcal G_{3,0,1}$$.

Type Definition Weight Norm
Point $$\mathbf p = p_x \mathbf e_1 + p_y \mathbf e_2 + p_z \mathbf e_3 + p_w \mathbf e_4$$ $$\left\Vert\mathbf p\right\Vert_\unicode{x25CB} = |p_w|{\large\unicode{x1D7D9}}$$
Line $$\mathbf L = v_x \mathbf e_{41} + v_y \mathbf e_{42} + v_z \mathbf e_{43} + m_x \mathbf e_{23} + m_y \mathbf e_{31} + m_z \mathbf e_{12}$$ $$\left\Vert\mathbf L\right\Vert_\unicode{x25CB} = {\large\unicode{x1D7D9}}\sqrt{v_x^2 + v_y^2 + v_z^2}$$
Plane $$\mathbf f = f_x \mathbf e_{234} + f_y \mathbf e_{314} + f_z \mathbf e_{124} + f_w \mathbf e_{321}$$ $$\left\Vert\mathbf f\right\Vert_\unicode{x25CB} = {\large\unicode{x1D7D9}}\sqrt{f_x^2 + f_y^2 + f_z^2}$$
Motor $$\mathbf Q = r_x \mathbf e_{41} + r_y \mathbf e_{42} + r_z \mathbf e_{43} + r_w {\large\unicode{x1d7d9}} + u_x \mathbf e_{23} + u_y \mathbf e_{31} + u_z \mathbf e_{12} + u_w$$ $$\left\Vert\mathbf Q\right\Vert_\unicode{x25CB} = {\large\unicode{x1D7D9}}\sqrt{r_x^2 + r_y^2 + r_z^2 + r_w^2}$$
Flector $$\mathbf G = s_x \mathbf e_1 + s_y \mathbf e_2 + s_z \mathbf e_3 + s_w \mathbf e_4 + h_x \mathbf e_{234} + h_y \mathbf e_{314} + h_z \mathbf e_{124} + h_w \mathbf e_{321}$$ $$\left\Vert\mathbf G\right\Vert_\unicode{x25CB} = {\large\unicode{x1D7D9}}\sqrt{h_x^2 + h_y^2 + h_z^2 + s_w^2}$$

## Geometric Norm

The geometric norm is a scalar value representing the magnitude of an element, which corresponds to a distance in Euclidean space.

The following table lists the geometric norms of the main types in the 4D projective geometric algebra $$\mathcal G_{3,0,1}$$.

Type Definition Geometric Norm Interpretation
Point $$\mathbf p = p_x \mathbf e_1 + p_y \mathbf e_2 + p_z \mathbf e_3 + p_w \mathbf e_4$$ $$\left\Vert\mathbf p\right\Vert = \dfrac{\sqrt{p_x^2 + p_y^2 + p_z^2}}{|p_w|}$$ Distance from the origin to the point $$\mathbf p$$.

Half the distance that the origin is moved by the flector $$\mathbf p$$.

Line $$\mathbf L = v_x \mathbf e_{41} + v_y \mathbf e_{42} + v_z \mathbf e_{43} + m_x \mathbf e_{23} + m_y \mathbf e_{31} + m_z \mathbf e_{12}$$ $$\left\Vert\mathbf L\right\Vert = \sqrt{\dfrac{m_x^2 + m_y^2 + m_z^2}{v_x^2 + v_y^2 + v_z^2}}$$ Perpendicular distance from the origin to the line $$\mathbf L$$.

Half the distance that the origin is moved by the motor $$\mathbf L$$.

Plane $$\mathbf f = f_x \mathbf e_{234} + f_y \mathbf e_{314} + f_z \mathbf e_{124} + f_w \mathbf e_{321}$$ $$\left\Vert\mathbf f\right\Vert = \dfrac{|f_w|}{\sqrt{f_x^2 + f_y^2 + f_z^2}}$$ Perpendicular distance from the origin to the plane $$\mathbf f$$.

Half the distance that the origin is moved by the flector $$\mathbf f$$.

Motor $$\mathbf Q = r_x \mathbf e_{41} + r_y \mathbf e_{42} + r_z \mathbf e_{43} + r_w {\large\unicode{x1d7d9}} + u_x \mathbf e_{23} + u_y \mathbf e_{31} + u_z \mathbf e_{12} + u_w$$ $$\left\Vert\mathbf Q\right\Vert = \sqrt{\dfrac{u_x^2 + u_y^2 + u_z^2 + u_w^2}{r_x^2 + r_y^2 + r_z^2 + r_w^2}}$$ Half the distance that the origin is moved by the motor $$\mathbf Q$$.
Flector $$\mathbf G = s_x \mathbf e_1 + s_y \mathbf e_2 + s_z \mathbf e_3 + s_w \mathbf e_4 + h_x \mathbf e_{234} + h_y \mathbf e_{314} + h_z \mathbf e_{124} + h_w \mathbf e_{321}$$ $$\left\Vert\mathbf G\right\Vert = \sqrt{\dfrac{s_x^2 + s_y^2 + s_z^2 + h_w^2}{h_x^2 + h_y^2 + h_z^2 + s_w^2}}$$ Half the distance that the origin is moved by the flector $$\mathbf G$$.


text:
Polymorphism is great, it means that we don’t need to repeat the same conceptually-polymorphic definition at multiple monomorphic types (I’m looking at you, Go). It unfortunately means that we need something a little smarter than equality for determining if a function application is well-typed.

As with the other CoCo memos, this is a Literate Haskell file. In the rendered output, highlighted source is literate source, non-highlighted source is just commentary.

We’re going to re-use the Typeable machinery as much as possible, as implementing it all ourself is nasty.

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE PolyKinds #-}

import Data.Function (on)
import Data.List (nub)
import Data.Maybe (fromMaybe, isJust)
import Data.Proxy (Proxy(..))
import Data.Typeable

## Type Variables

Firstly, we need a representation of type variables. We can’t use actual type variables, because Typeable only works with monomorphic types. So we’ll need to introduce some specific types that we shall treat as variables during type-checking. We can get an arbitrary number of these by using a polymorphic type:

data TyVar t = TyVar deriving (Bounded, Enum, Eq, Ord, Read, Show)

For convenience, we shall also have four named type variables:

type A = TyVar 0
type B = TyVar 1
type C = TyVar 2
type D = TyVar 3

If any type needs more than four distinct type variables, it can always introduce its own.

Finally, we can check if a type is a type variable:

isTypeVar :: TypeRep -> Bool
isTypeVar = ((==) on (fst . splitTyConApp)) (typeRep (Proxy :: Proxy A))

## Typing Function Applications

The Data.Typeable module has a handy little function for checking that a function application is well-typed:

funResultTy :: TypeRep -> TypeRep -> Maybe TypeRep

which takes the function type, the argument type, and returns the result type if the application is well-typed. We want something similar, but supporting our type variables. We don’t just want equality, want unification. We want a function like so:

-- | Applies a type to a function type.  If type-correct, returns an environment binding type
-- variables to types, and the result type (with bindings applied).
polyFunResultTy :: TypeRep -> TypeRep -> Maybe (TypeEnv, TypeRep)
polyFunResultTy fty aty = do
-- get the function and argument types
let funTyCon = typeRepTyCon (typeRep (Proxy :: Proxy (() -> ())))
(argTy, resultTy) <- case splitTyConApp fty of
(con, [argTy, resultTy]) | con == funTyCon -> Just (argTy, resultTy)
_ -> Nothing
-- produce a (possibly empty) type environment
env <- unify aty argTy
-- apply the type environment to the result
pure (env, applyBindings env resultTy)

Type Environments: Firstly, let’s define what a type environment actually is. We’ll keep it very simple: just a map from types to types:

-- | An environment of type bindings.
type TypeEnv = [(TypeRep, TypeRep)]

The first in every tuple will be a TyVar, but there isn’t really a good way to statically enforce that.

Now that we have type environments, let’s apply them to a type. This need not make a type fully monomorphic, the bindings may not cover every type variable used, or may define some type variables in terms of others (as long as a variable isn’t defined in terms of itself). This is fine.

-- | Apply type environment bindings to a type.
applyBindings :: TypeEnv -> TypeRep -> TypeRep
applyBindings env = go where
go ty
-- look up type variables in the environment, but fall-back to the naked variable if not found
| isTypeVar ty = fromMaybe ty (lookup ty env)
-- otherwise continue recursively through type constructors
| otherwise = let (con, args) = splitTyConApp ty in mkTyConApp con (map go args)

Unification: For reasons that will become apparent later, we’re going to define a few variants of this.

Firstly, our standard unification function. It’ll take two types (the order doesn’t matter) and attempt to unify them. Two types unify if:

1. They’re structurally equal; OR
2. At least one is a type variable; OR
3. They have the same constructor with the same number of arguments, and all the arguments unify, with compatible environments.

Hey, that sounds like a recursive function!

-- | Attempt to unify two types.
unify :: TypeRep -> TypeRep -> Maybe [(TypeRep, TypeRep)]
unify = unify' True

This next function is the actual workhorse. It implements the recursive decision procedure described above and constructs the environment. It takes a flag to determine if unifying with a naked type variable is allowed here. It always is in the recursive case. This will turn out to be useful in the next section, when we’re talking about polymorphic uses of the state type.

-- | Attempt to unify two types.
unify'
:: Bool
-- ^ Whether to allow either type to be a naked type variable at this level (always true in
-- lower levels).
-> TypeRep -> TypeRep -> Maybe TypeEnv
unify' b tyA tyB
-- check equality
| tyA == tyB = Just []
-- check if one is a naked type variable
| isTypeVar tyA = if not b || occurs tyA tyB then Nothing else Just [(tyA, tyB)]
| isTypeVar tyB = if not b || occurs tyB tyA then Nothing else Just [(tyB, tyA)]
-- deconstruct each and attempt to unify subcomponents
| otherwise =
let (conA, argsA) = splitTyConApp tyA
(conB, argsB) = splitTyConApp tyB
in if conA == conB && length argsA == length argsB
then unifyAccum True id argsA argsB
else Nothing
where
-- check if a type occurs in another
occurs needle haystack = needle == haystack || any (occurs needle) (snd (splitTyConApp haystack))

The recursive listy case is handled by this unifyAccum function, which is mutually recursive with unify':

-- | An accumulating unify: attempts to unify two lists of types pairwise and checks that the
-- resulting assignments do not conflict with the current type environment.
unifyAccum :: Bool -> (Maybe TypeEnv -> Maybe TypeEnv) -> [TypeRep] -> [TypeRep] -> Maybe TypeEnv
unifyAccum b f as bs = foldr go (Just []) (zip as bs) where
go (tyA, tyB) (Just env) =
unifyTypeEnvs b env =<< f (unify' b tyA tyB)
go _ Nothing = Nothing

The final piece of the unification puzzle is how to combine type environments. This is necessary to be able to unify types like T A A and T Int B. One option is to enforce equality of bindings, but that is too restrictive (it won’t work in the T example, as Int is not B, yet both do unify). The correct solution is to unify the bindings. This is yet another mutually recursive function:

-- | Unify two type environments, if possible.
unifyTypeEnvs :: Bool -> TypeEnv -> TypeEnv -> Maybe TypeEnv
unifyTypeEnvs b env1 env2 = foldr go (Just []) (nub $map fst env1 ++ map fst env2) where go tyvar acc@(Just env) = case (lookup tyvar env, lookup tyvar env1, lookup tyvar env2) of (_, Just ty1, Just ty2) -> unifyTypeEnvs b env . ((tyvar, ty1):) =<< unify' b ty1 ty2 (x, Just ty1, _) | isJust x -> unifyTypeEnvs b env [(tyvar, ty1)] | otherwise -> Just ((tyvar, ty1):env) (x, _, Just ty2) | isJust x -> unifyTypeEnvs b env [(tyvar, ty2)] | otherwise -> Just ((tyvar, ty2):env) _ -> acc go _ Nothing = Nothing  And now, an example: λ> data T a b = T λ> unify (typeOf (undefined :: T A A)) (typeOf (undefined :: T Int B)) Just [(TyVar Nat 0,TyVar Nat 1),(TyVar Nat 1,Int)] λ> let funTy = typeOf (undefined :: A -> B -> Bool -> Either A B) λ> polyFunResultTy funTy (typeOf (undefined::Int)) Just ([(TyVar Nat 0,Int)],TyVar Nat 1 -> Bool -> Either Int (TyVar Nat 1)) ## Monomorphising the State Type In a CoCo signature, the state type is monomorphic, but it can be nice to treat it as polymorphic for two reasons: 1. Needing to change the types inside the signature because the type of the signature changed is a pain. 2. It helps avoid repetition. Here are a couple of function types that may appear in a signature: MVar Concurrency Int -> Concurrency Int MVar Concurrency Int -> Int -> Concurrency () If the state type is MVar Concurrency Int, then (1) is saying that if we change it to MVar Concurrency Bool we now need to change those two types above, and (2) is saying that we’re needlessly repeating the Int. It would be much nicer to have these types in the signature: MVar Concurrency A -> Concurrency A MVar Concurrency A -> A -> Concurrency () Now that we have implemented type unification, we can do this! For a function type in the signature: 1. Try to unify every argument, excluding naked type variables, against the state type. 2. Check that the environments are compatible. 3. Apply the combined environment to the function type. This effect of this is to monomorphise polymorphic uses of the state type. This is good because the state type often determines other argument types, and once we know the concrete types of function arguments we can infer what hole types we need. If functions have totally polymorphic types, hole inference doesn’t work so well. -- | Monomorphise polymorphic uses of the state type in a function type. monomorphise :: Typeable s => Proxy s -- ^ The state type. -> TypeRep -- ^ The function type. -> TypeRep monomorphise s ty0 = fromMaybe ty0$ do
let stateTy = typeRep s
argTys <- funArgTys ty0
env    <- unifyAccum False (maybe (Just []) Just) (repeat stateTy) argTys
pure (applyBindings env ty0)

Now we see the purpose of the boolean argument to unify'. If we have the type A -> MVar Concurrency A -> Concurrency (), we don’t want to unify MVar Concurrency Int with A, we want to skip that over! More generally, we want to avoid unifying a fully-polymorphic type with our state type but, as all our type variables have kind *, just preventing the top-level unification suffices.

Oh, we’ll also need this helper function to get all the argument types of a function:

-- | Get all of a function's argument types.  Returns @Nothing@ if not a function type.
funArgTys :: TypeRep -> Maybe [TypeRep]
funArgTys ty = case splitTyConApp ty of
(con, [argTy, resultTy]) | con == funTyCon -> Just \$
argTy : fromMaybe [] (funArgTys resultTy)
_ -> Nothing
where
funTyCon = typeRepTyCon (typeRep (Proxy :: Proxy (() -> ())))

And we’re done!

λ> let s = Proxy :: Proxy (Either Int Bool)
λ> let f = typeOf (undefined :: A -> Either A B -> B)
λ> monomorphise s f
Int -> Either Int Bool -> Bool


text:
## Cauchy-Riemann equations

1. The problem statement, all variables and given/known data

write down the C-R equations and use them to determine those points at which the following functions are analytic
(i)h(z)=$x^2-y^2-x + i(2xy+y)$
(ii)h(z)=cos2xcosh2y - isin2xsinh2y

2. Relevant equations

3. The attempt at a solution

ok so C-R equations are for z=u+iv eq1 = $\frac{\partial u}{\partial x} = \frac{\partial v}{\partial y}$ and eq2= $\frac{\partial u}{\partial y} = - \frac{\partial v}{\partial x}$

for for (i) i get $\frac{\partial u}{\partial x} = 2x-1 and \frac{\partial v}{\partial y} = 2x+1$
and $\frac{\partial v}{\partial x} = 2y and \frac{\partial u}{\partial y} = -2y$ equation 2 holds but equation 1 does not hold. So am i right in thinking the function is not analytic? both equations have to be satisfied right? its the way the question is worded is throwing me "those points" ...
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Recognitions: Gold Member Science Advisor Staff Emeritus A function is "analytic" at a given point if and only if it satisfies the C-R equation in some neighborhood of that point. Here, you are correct that the first function is not analytic for any points and the second function is analytic for all points.
 and for part (ii) i got the reverse as in $\frac{\partial u}{\partial x} = -\frac{\partial v}{\partial y}$ $\frac{\partial u}{\partial y} = \frac{\partial v}{\partial x}$ which leads me to believe this function isnt analytic either...

## Cauchy-Riemann equations

Hi Hallsofivy,
Thanks a million for that. I didnt realise youd got in there between my question and me reply!
So I guess what your saying is it doesnt matter which equation has the negative?

 Quote by gtfitzpatrick So I guess what your saying is it doesnt matter which equation has the negative?
A function is analytic if (slightly hand-wavingly) it only depends on z, and not it's complex conjugate. You can see that in i), your function can be written as $f(z) = z^2 - \bar{z}$, meaning it's not analytic for sure.

If you have the C-R-equations holding with an additional minus sign, then the function only depends on complex conjugate of z (and not z itself). I think people call this kind of functions antianalytic.

 Similar discussions for: Cauchy-Riemann equations Thread Forum Replies Calculus & Beyond Homework 1 Calculus & Beyond Homework 5 Calculus & Beyond Homework 14 Calculus 3 Calculus 0


text:
# HITB PRO CTF - cells

The cells service allows users to save their secret data in “DNA of cells”.

The service’s frontpage provides a login and registration form, as well as a search function:

Via the search function, we can also search for users matching a pattern and download their cells.

The webinterface is implemented as a python flask service, however, the store and check endpoints offload their main functionality to an ELF-binary simply called cells.elf.

## The Flagstore

Unsurprisingly, flags are stored in other users’ cells. However, without a password, these cell-files seemingly only contain binary garbage. Thus, in order to get some flags, we either need to obtain a user’s password, or find some other way to recover the flag.

## A custom VM

After spending some hours with Ghidra, we find that cells.elf actually implements a custom virtual machine. Storing a secret is implemented as generating a program which will output the flag and a checksum when given the corresponding password as input. Checking a secret is then simply executing the generated program with the provided password and verifying the checksum. This also explains the content of the downloadable cell-files: The presumed binary garbage is actually VM bytecode.

For example, in one cell the gameserver stored the flag OADJUIS7KNBFLTNY4P5MZFEE0EDC381= using the password U0VSegNW, which resulted in the following cell:

And indeed, executing this cell returns the flag plus a hex-encoded checksum separated by a comma:

\$ ./cells.elf cell.pk.cell U0VSegNW

## VM internals

The VM uses 3 bytes to encode an instruction. Bits 21-18 denote the opcode, and bits 18-0 encode the arguments: three six-bit arguments for comparison operators, two eight-bit arguments for arithmetic instructions, or a single 16- or 18-bit argument (I/O and jump instructions). In most cases, arguments are interpreted relative to the program counter. In addition, the two highest bits have special functions: Bit 23 (restart) signals that after this instruction, the program counter shall be reset to zero, while bit 22 (remove) indicates that the instruction should be removed from the program once it has been executed.

Execution operates on an array structure, where each slot stores a 4-byte value. The array is initialized by loading 3-byte chunks from the input cells file. During execution, the slot pointed to by the program counter will be decoded as an instruction, executed, and the result written back into the current slot, if a new value was generated. Execution terminates, once the current slot cannot be decoded as a valid instruction, on a JMP instruction to address 0, or when a given number of steps is exceeded (5000 by default).

In total, the VM has 17 opcodes:

opcode instruction
0   illegal instruction
1 add x y arr[pc] = arr[pc + x] + arr[pc + y]
2 sub x y arr[pc] = arr[pc + x] - arr[pc + y]
3 mul x y arr[pc] = arr[pc + x] * arr[pc + y]
4 div x y arr[pc] = arr[pc + x] / arr[pc + y]
5 rem x y arr[pc] = arr[pc + x] % arr[pc + y]
6 xor x y arr[pc] = arr[pc + x] ^ arr[pc + y]
7 or x y arr[pc] = arr[pc + x] | arr[pc + y]
8 and x y arr[pc] = arr[pc + x] & arr[pc + y]
9 copy imm16 arr[pc] = signext(imm16)
a input imm16 arr[pc + imm16] = getchar() (input is taken from cmdline argument, not stdin)
b output imm16 putchar(arr[pc + signext(imm16)])
c ifzero x y z arr[pc] = arr[x] (presumably should have been arr[pc] = (arr[pc + x] == 0) ? arr[pc + y] : arr[pc + z])
d ifgt x y z arr[pc] = arr[x] (presumably should have been arr[pc] = (arr[pc + x] < 1) ? arr[pc + z] : arr[pc + y])
e ifls x y z arr[pc] = arr[x] (presumably should have been arr[pc] = (arr[pc + x] < 0) ? arr[pc + y] : arr[pc + z])
f skip imm18 pc = pc + imm18
10 skipref imm18 pc = arr[pc + imm18] (cannot be decoded, instruction decoder truncates opcodes to 4 bits)

Given that the generated programs are quite short, the number of opcodes is small, and the password length is limited to eight characters, we did what anyone with a background in writing symbolic execution engines for weird VMs would do: re-implement the VM in python to make a symbolic execution engine.

The idea here was that if we can execute a cell program symbolically, we might have enough information to feed to z3 to recover the flag and password.

To keep things simple (and since it was already way past midnight at that point), we only handled the easy cases and ignored symbolic program counters etc. The implementation is mostly straightforward, though in some cases python integers and z3 BitVecs require individual handling (e.g. integer division):

Given an array of eight symbolic input bytes, this function provides us with an array of output-expressions:

We further know that all input and output bytes are in the printable range:

In addition we can make use of the checksum: The ninth-last output must be a comma, and the remaining eight characters must be hexdigits:

Lastly, we can also recompute the checksum. Fortunately, for this we use the given python code as is, and only need to provide a to_hex function that can handle symbolic values:

From here we should have given z3 enough to work with to recover the password and the flag:

which, indeed, works:

In [1]: with open('cell.pk.cell','rb') as f:
...:

In [2]: solve(cell)

Patching the cells service proved quite difficult: Restricting the search function to patterns longer than two characters is impossible, since the gameserver checks for such short patterns. The only way out is therefore to make the generated cell programs more complicated. For example, to defend against our exploit, it would have been enough to obfuscate the code by XORing it with one of the input bytes. As the resulting expressions would have been symbolic, we could have no longer decoded the instructions correctly. However, during the CTF a overwhelming desire for sleep meant that our cells service remained unpatched.


text:
# Homology (mathematics)

Homology (mathematics)

In mathematics (especially algebraic topology and abstract algebra), homology (in Greek ὁμός "homos" "identical") is a certain general procedure to associate a sequence of abelian groups or modules with a given mathematical object such as a topological space or a group. See homology theory for more background, or singular homology for a concrete version for topological spaces, or group cohomology for a concrete version for groups.

For a topological space, the homology groups are generally much easier to compute than the homotopy groups, and consequently one usually will have an easier time working with homology to aid in the classification of spaces.

Construction of homology groups

The procedure works as follows: Given an object such as a topological space $X$, one first defines a "chain complex" $A=C\left(X\right)$ that encodes information about $X$. A chain complex is a sequence of abelian groups or modules $A_0, A_1, A_2, dots$ connected by homomorphisms $d_n : A_n ightarrow A_\left\{n-1\right\}$, such that the composition of any two consecutive maps is zero: $d_n circ d_\left\{n+1\right\} = 0$ for all "n". This means that the image of the "n"+1-th map is contained in the kernel of the "n"-th, and we can define the "n"-th homology group of "X" to be the factor group (or quotient module)

:$H_n\left(X\right) = ker\left(d_n\right) / mathrm\left\{Im\right\}\left(d_\left\{n+1\right\}\right)$

The standard notation is $ker\left(d_n\right)=Z_n\left(X\right)$ and $operatorname\left\{im\right\}\left(d_\left\{n+1\right\}\right)=B_n\left(X\right)$. Note that the computation of these two groups is usually rather difficult, since they are very large groups. On the other hand, machinery exists that allows one to compute the corresponding homology group easily.

The "simplicial homology" groups $H_n\left(X\right)$ of a "simplicial complex" $X$ are defined using the simplicial chain complex $C\left(X\right)$,with $C\left(X\right)_n$ the free abelian group generated by the $n$-simplices of $X$. The "singular homology" groups $H_n\left(X\right)$ are defined for any topological space $X$, and agree with the simplicial homology groups for a simplicial complex.

A chain complex is said to be "exact" if the image of the ("n" + 1)-th map is always equal to the kernel of the "n"th map. The homology groups of $X$ therefore measure "how far" the chain complex associated to $X$ is from being exact.

Cohomology groups are formally similar: one starts with a cochain complex, which is the same as a chain complex but whose arrows, now denoted $d^n$ point in the direction of increasing "n" rather than decreasing "n"; then the groups $ker\left(d^n\right) = Z^n\left(X\right)$ and $operatorname\left\{im\right\}\left(d^\left\{n - 1\right\}\right) = B^n\left(X\right)$ follow from the same description and:$H^n\left(X\right) = Z^n\left(X\right)/B^n\left(X\right)$, as before.

Examples

The motivating example comes from algebraic topology: the simplicial homology of a simplicial complex $X$. Here $A_n$ is the free abelian group or module whose generators are the "n"-dimensionaloriented simplexes of $X$. The mappings are called the "boundary mappings" and send the simplex with vertices

:$\left(a \left[0\right] , a \left[1\right] , dots, a \left[n\right] \right)$

to the sum

:$sum_\left\{i=0\right\}^n \left(-1\right)^i\left(a \left[0\right] , dots, a \left[i-1\right] , a \left[i+1\right] , dots, a \left[n\right] \right)$

(which is considered $0$ if $n=0$).

If we take the modules to be over a field, then the dimensionof the "n"-th homology of $X$ turns out to be the number of "holes" in $X$ at dimension "n".

Using this example as a model, one can define a singular homology for any topological space $X$. We define a chain complex for $X$ by taking $A_n$ to be the free abelian group (or free module) whose generators are all continuous maps from "n"-dimensional simplices into $X$. The homomorphisms $d_n$ arise from the boundary maps of simplices.

In abstract algebra, one uses homology to define derived functors, for example the Tor functors. Here one starts with some covariant additive functor $F$ and some module $X$. The chain complex for $X$ is defined as follows: first find a free module $F_1$ and a surjective homomorphism $p_1 : F_1 ightarrow X$. Then one finds a free module $F_2$ and a surjective homomorphism $p_2 : F_2 ightarrow mathrm\left\{ker\right\}\left(p_1\right)$. Continuing in this fashion, a sequence of free modules $F_n$ and homomorphisms $p_n$ can be defined. By applying the functor $F$ to this sequence, one obtains a chain complex; the homology $H_n$ of this complex depends only on $F$ and $X$ and is, by definition, the "n"-th derived functor of $F$, applied to $X$.

Homology functors

Chain complexes form a category: A morphism from the chain complex $\left(d_n colon A_n ightarrow A_\left\{n-1\right\}\right)$ to the chain complex $\left(e_ncolon B_n ightarrow B_\left\{n-1\right\}\right)$ is a sequence of homomorphisms $f_ncolon A_n ightarrow B_n$ such that $f_\left\{n-1\right\} circ d_n = e_\left\{n\right\} circ f_n$ for all "n". The "n"-th homology "Hn" can be viewed as a covariant functor from the category of chain complexes to the category of abelian groups (or modules).

If the chain complex depends on the object "X" in a covariant manner (meaning that any morphism "X → Y" induces a morphism from the chain complex of "X" to the chain complex of "Y"), then the "Hn" are covariant functors from the category that "X" belongs to into the category of abelian groups (or modules).

The only difference between homology and cohomology is that in cohomology the chain complexes depend in a "contravariant" manner on "X", and that therefore the homology groups (which are called "cohomology groups" in this context and denoted by "Hn") form "contravariant" functors from the category that "X" belongs to into the category of abelian groups or modules.

Properties

If $\left(d_n : A_n ightarrow A_\left\{n-1\right\}\right)$ is a chain complex such that all but finitely many $A_n$ are zero, and the others are finitely generated abelian groups (or finite dimensional vector spaces), then we can define the "Euler characteristic"

:$chi = sum \left(-1\right)^n , mathrm\left\{rank\right\}\left(A_n\right)$

(using the rank in the case of abelian groups and the Hamel dimension in the case of vector spaces). It turns out that the Euler characteristic can also be computed on the level of homology:

:$chi = sum \left(-1\right)^n , mathrm\left\{rank\right\}\left(H_n\right)$

and, especially in algebraic topology, this provides two ways to compute the important invariant $chi$ for the object $X$ which gave rise to the chain complex.

Every short exact sequence

:$0 ightarrow A ightarrow B ightarrow C ightarrow 0$

of chain complexes gives rise to a long exact sequence of homology groups

:$cdots ightarrow H_n\left(A\right) ightarrow H_n\left(B\right) ightarrow H_n\left(C\right) ightarrow H_\left\{n-1\right\}\left(A\right) ightarrow H_\left\{n-1\right\}\left(B\right) ightarrow H_\left\{n-1\right\}\left(C\right) ightarrow H_\left\{n-2\right\}\left(A\right) ightarrow cdots ,$

All maps in this long exact sequence are induced by the maps between the chain complexes, except for the maps $H_n\left(C\right) ightarrow H_\left\{n-1\right\}\left(A\right).$ The latter are called "connecting homomorphisms" and are provided by the snake lemma.

*Simplicial homology
*Singular homology
*Homology theory
*Homological algebra

References

* Cartan, Henri Paul and Eilenberg, Samuel (1956) "Homological Algebra" Princeton University Press, Princeton, NJ, [http://worldcat.org/oclc/529171 OCLC 529171]
* Eilenberg, Samuel and Moore, J. C. (1965) "Foundations of relative homological algebra" (Memoirs of the American Mathematical Society number 55) American Mathematical Society, Providence, R.I., [http://worldcat.org/oclc/1361982 OCLC 1361982]
* Hatcher, A., (2002) " [http://www.math.cornell.edu/~hatcher/AT/ATchapters.html Algebraic Topology] " Cambridge University Press, ISBN 0-521-79540-0. Detailed discussion of homology theories for simplicial complexes and manifolds, singular homology, etc.
*planetmath reference|id=3720|title=Homology (Topological space)

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Homology — may refer to:* Homology (anthropology), analogy between human beliefs, practices or artifacts due to genetic or historical connections. * Homology (biology): similar structures due to shared ancestry. * Homology (chemistry): a compound of a… …   Wikipedia

• Homology theory — In mathematics, homology theory is the axiomatic study of the intuitive geometric idea of homology of cycles on topological spaces. It can be broadly defined as the study of homology theories on topological spaces. Simple explanation At the… …   Wikipedia

• homology — /heuh mol euh jee, hoh /, n., pl. homologies. 1. the state of being homologous; homologous relation or correspondence. 2. Biol. a. a fundamental similarity based on common descent. b. a structural similarity of two segments of one animal based on …   Universalium

• mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

• Homology sphere — In algebraic topology, a homology sphere is an n manifold X having the homology groups of an n sphere, for some integer n ≥ 1. That is, we have: H 0( X ,Z) = Z = H n ( X ,Z)and : H i ( X ,Z) = {0} for all other i .Therefore X is a connected space …   Wikipedia

• Homology manifold — In mathematics, a homology manifold (or generalized manifold)is a locally compact topological space X that looks locally like a topological manifold from the point of view of homology theory.DefinitionA homology G manifold (without boundary) of… …   Wikipedia

• List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

• Areas of mathematics — Mathematics has become a vastly diverse subject over history, and there is a corresponding need to categorize the different areas of mathematics. A number of different classification schemes have arisen, and though they share some similarities,… …   Wikipedia

• Intersection homology — In topology, a branch of mathematics, intersection homology is an analogue of singular homology especially well suited for the study of singular spaces, discovered by Mark Goresky and Robert MacPherson in the fall of 1974 and developed by them… …   Wikipedia

• Floer homology — is a mathematical tool used in the study of symplectic geometry and low dimensional topology. First introduced by Andreas Floer in his proof of the Arnold conjecture in symplectic geometry, Floer homology is a novel homology theory arising as an… …   Wikipedia