text:
Order Invariance on Decomposable Structures

Order Invariance on Decomposable Structures

Michael Elberfeld    Marlin Frickenschmidt    Martin Grohe
rwth Aachen University
Aachen, Germany
{elberfeld|frickenschmidt|grohe}@informatik.rwth-aachen.de
July 22, 2019
Abstract

Order-invariant formulas access an ordering on a structure’s universe, but the model relation is independent of the used ordering. They are frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order (mso) and first-order (fo) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width).

While order-invariant mso is more expressive than mso and, even, cmso (mso with modulo-counting predicates) in general, we show that order-invariant mso and cmso are equally expressive on graphs of bounded tree width and on planar graphs. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant fo are also definable in mso on these classes. These results are applications of a theorem that shows how to lift up definability results for order-invariant logics from the bags of a graph’s tree decomposition to the graph itself.

Keywords: finite model theory, first-order logic, monadic second-order logic, order-invariant logic, modulo-counting logic, bounded tree width, planarity

\setitemize

label=– \setenumeratefont=

1 Introduction

A formula is order-invariant if it has access to an additional total ordering on the universe of a given structure, but its answer is invariant with respect to the given order. The concept of order invariance is used to formalize the observation that logical structures are often encoded in a form that implicitly depends on a linear order of the elements of the structure; think of the adjacency-matrix representation of a graph. Yet the properties of structures we are interested in should not depend on the encoding and hence the implicit linear order, but just on the abstract structure. Thus, we use formulas that access orderings, but define unordered properties. This approach can be prominently found in database theory where formulas from first-order (fo) and monadic second-order (mso) logic are used to model query languages for relational databases and (hierarchical) xml documents, respectively. Being order-invariant means in this setting that the formula evaluation process is always independent of low-level aspects of databases like, for example, the encoding of elements as indices. Another example approach can be found in descriptive complexity theory where formulas whose evaluation is invariant with respect to specific encodings of the input structure capture unordered problems decidable by certain complexity classes. The famous open problem of whether there is a logic that captures all unordered properties decidable in polynomial time falls into this category.

Gurevich [17] proved that order-invariant fo (<-inv-fo) is more expressive than fo (also see [24] for details). The same holds for order-invariant mso (<-inv-mso) and mso with modulo-counting predicates (cmso); Ganzow and Rubin showed that <-inv-mso is able to express more properties than cmso on general finite structures [15]. Since it is not possible to decide, for a given fo-formula, whether it is order-invariant or not, this opens up the question of whether we can find alternative logics that are equivalent to the order-invariant logics <-inv-fo and <-inv-mso. While on general logical structures no logics that are equivalent to <-inv-fo or <-inv-mso are known, this changes if we consider classes of structures that are well-behaved. Benedikt and Segoufin [1] showed that <-inv-fo and fo have the same expressive power on the class of all strings and the class of all trees (we write on to indicate that the properties definable in <-inv-fo equal the properties definable in fo when considering structures from a class ). Considering <-inv-mso, Courcelle [7] showed that it has the same expressive power as cmso on the class of trees (that means, on trees). Recently it was shown that and hold on classes of graphs of bounded tree depth [12]. More general results that apply to graphs of bounded tree width or planar graphs have not been obtained so far. This is due to the fact that, whenever we want to move from an order-invariant logic to another logic on a class of structures, we need to understand both (1) the expressive power of the order-invariant logic when restricted to these structures, and (2) the ability of the other logic to handle the structures in terms of, for example, definable decompositions.

Results.

Our results address both of these issues to better understand the expressive power of order-invariant logics on decomposable structures.

Addressing issue (1), we prove two general results, which show how to lift-up definability results for order-invariant logics from the bags of tree decompositions up to the whole decomposed structure. We show that, whenever we are able to use mso-formulas to define a tree decomposition whose adhesion is bounded (that means, bags have only bounded size intersections) and we can define total orderings on the vertices of each bag individually, then (Theorem 3.1) and (Theorem 3.2). Lifting theorems of this kind can be seen to be implicitly used earlier [1, 5, 6], but so far they only applied to the case where the defined tree decomposition has a bounded width. In this case, the whole structure can be easily transformed into an equivalent tree. Our theorems also handle the case where bags have an unbounded width: they merely assume the additional definability of a total ordering on bags, possibly using arbitrary parameters (which may be sets in the case of mso-definability). This is a much weaker assumption than having bounded width, and it covers larger graph classes. The proofs of the lifting theorems use type-composition methods to show how one can define the logical types of structures from the logical types of substructures. The main challenge lies in trading the power of the used types (in our case these are certain order-invariant types based on orderings that are compatible with the given decomposition) with the ability to prove the needed type-composition methods. The latter need to work with bags of unbounded size and, thus, are more general than the type-composition methods that are commonly used for the case of bounded size bags.

Addressing issue (2), we study two types of classes of graphs where it is possible to meet the assumptions of the lifting theorems and, thus, show that and hold on these classes. The first two results (formally stated as Theorems 5.6 and 5.7) apply to classes of graphs of bounded tree width. For the proof, we show that one can define tree decompositions of bounded adhesion in mso, where the bags admit mso-definable total orderings. Let us remark that in proving these results we do not rely on the mso-definability of width-bounded tree decompositions, a result announced by Lapoire [18], but only proved recently (and independently of our work) by Bojańczyk and Pilipczuk [3] [4]. Benedikt and Segoufin [1] had shown earlier how to prove these results using the mso-definability of width-bounded tree decompositions. Our second application of the lifting theorem is concerned with classes of graphs that, for some , do not contain as a minor. This includes the class of planar graphs and all classes of graphs embedabble in a fixed surface [22, 23]. Using an mso-definable tree decomposition into 3-connected components due to Courcelle [8] along with proving that there are mso-definable total orderings for the 3-connected bags of the decomposition, we are able to apply the lifting theorems to prove that (Theorem 5.10) and (Theorem 5.11) hold on every class of graphs that exclude as a minor for some .

Organization of the paper.

The paper starts with a preliminary section (Section 2) containing definitions related to graphs and logic. In Section 3, we formally state and prove the lifting theorems. Section 4 shows how to mso-define tree decompositions along clique separators and reviews the known mso-definable tree decomposition into 3-connected components. Section 5 picks up the decomposed graphs and shows how to define total orderings for bags. This is combined with the lifting theorems to prove the results about bounded tree width graphs and -minor-free graphs stated above.

2 Background

In the present section, we introduce the necessary background related to logical structures and graphs (Section 2.1), monadic second-order logic and its variants (Section 2.2), logical games and types (Section 2.3), and transductions (Section 2.4).

2.1 Structures and Graphs

A vocabulary is a finite set of relational symbols where an arity is assigned to each . A structure over a vocabulary consists of a finite set , its universe, and a relation for every . We sometimes write by , in particular if is a symbol like .

An expansion of a -structure is a -structure for some vocabulary such that and for all . If is a -structure and , then the induced substructure is the -structure with universe and relations for all . Furthermore, we let .

Graphs  are structures over the vocabulary with . When working with graphs, we also write for the graph’s universe (its set of vertices) and call its set of edges. The graphs we are working with are undirected. That means, for every two vertices and , we have if, and only if, and . The Gaifman graph of a structure has vertices and for every pair of distinct elements and that are part of a common tuple in , we insert the edge into ; thus, is always undirected.

A tree decomposition of a structure is a tree together with a labeling function satisfying the following two conditions. (Connectedness condition) For every element , the induced subtree is nonempty and connected. (Cover condition) For every tuple of a relation in , there is a with . It will be convenient to assume that the trees underlying our tree decompositions are directed. That means, all edges are directed away from a root. The set of neighbors of a node in a directed tree consists of its children (if is not a leaf) and its parent (if is not the root). The set of children of a node in a directed tree is denoted by . We omit from and if it is clear from the context. The sets for every are the bags of the tree decomposition. The width of the tree decomposition is and its adhesion is . The tree width, , of a structure is the minimum width of a tree decomposition for it. Structures and their Gaifman graphs have the same tree decompositions. In particular . The torso of a node in a tree decomposition for a structure with Gaifman graph is together with edges between all pairs for .

2.2 Monadic Second-Order Logic and its Variants

Monadic second-order logic (mso-logic) is defined by taking all second-order formulas without second-order quantifiers of arity 2 and higher. More specifically, to define its syntax, we use element variables for and set variables for . Formulas of mso-logic (mso-formulas) over a vocabulary are inductively defined as usual (see, for example, [19]). Such formulas are also called -formulas to indicate the vocabulary along with the logic. The set of free variables of an mso-formula , denoted by , contains the variables of that are not used as part of a quantification. By renaming a formula’s variables, we can always assume for some ; we write to indicate that the free variables of are exactly to and to . Given an mso-formula , indicates that together with the assignment , for , and , for , to ’s free variables satisfies . A formula without free variables is also called a sentence.

Monadic second-order logic with modulo-counting (cmso-logic) extends mso-logic with the ability to access (built-in) modulo-counting atoms for every where is a relation symbol. Given a structure over a vocabulary that contains , we have exactly if divides (that means, ). Atoms where  is a set variable are used in the same way.

Let be a vocabulary and a binary relation symbol not contained in . An mso-sentence of vocabulary is order-invariant if for all -structures and all linear orders of we have if, and only if, . We can now form a new logic, order-invariant monadic second-order logic (<-inv-mso-logic), where the sentences of vocabulary are the order-invariant sentences of vocabulary , and a -structure satisfies an order-invariant sentence if satisfies in the usual sense for some (and hence for all) linear orders of . There is a slight ambiguity in the definition of order-invariant sentences in which binary relation symbol we are referring to as our special “order symbol” (there may be several binary relation symbols in ). But we always assume that is clear from the context. Alternatively, we could view as a “built-in” relation symbol that is fixed once and for all and is not part of any vocabulary. However, this would be inconvenient because we sometimes need to treat just as an ordinary relation symbol and the sentences of <-inv-mso-logic of vocabulary just as ordinary mso-sentences of vocabulary .

First-order logic (fo-logic) and order-invariant first-order logic (<-inv-fo-logic) are defined by taking all sentences of mso-logic and <-inv-mso-logic, respectively, that do not contain set variables.

2.3 Games and Types

The quantifier rank of an mso-formula , denoted by , is the maximum number of nested quantifiers in . For structures and , we write if and satisfy the same mso-sentences of quantifier rank at most . We write if and satisfy the same order-invariant mso-sentences of quantifier rank at most . For every , we write if and satisfy the same cmso-sentences of quantifier rank at most and only numbers are used in the modulo-counting atoms.

It will sometimes be convenient to use versions of mso and cmso without element variables (see, for example, [25]). In particular, in the context of Ehrenfeucht-Fraïssé games. We will freely do so. We assume that the reader is familiar with the characterizations of mso-equivalence and cmso-equivalence by Ehrenfeucht-Fraïssé games (see, for example, [11, 15]). Corresponding to the versions of the logics without element variables, we use a version of the games where the players only select sets and never elements, and a position induces a partial isomorphism if the mapping between the singleton sets of the position is a partial isomorphism. (The rules of the game require the Duplicator to answer to a singleton set with a singleton set and to preserve the subset relation.) Then a position of the game on structures is a sequence of pairs of subsets and . The position is a -move winning position for one of the players if this player has a winning strategy for the -move game starting in this position.

We also use the concept of types. Let be a vocabulary and . Then for all -structures and sets , the mso-type of of quantifier rank is

 tp\textscmsoq(A,P1,…,Pp) :={φ(X1,…,Xp)∣φ is {mso}-% formula with qr(φ)≤q and A⊨φ(P1,…,Pp)}.

Moreover, the class of all types over with respect to rank and free set variables is

 \textsctp\textscmso(τ,q,p) :={tp\textscmsoq(A,P1,…,Pp)∣A is τ-structure,P1,…,Pp⊆U(A)},

and we let . For , we say that a cmso-formula has rank at most if it has quantifier rank at most and only contains modulo-counting atoms with . Based on this notion of rank, we define the cmso-type , and sets and .

Note that if, and only if, is a -move winning position for the Duplicator in the mso-game on . Furthermore, for we have if, and only if, . Similar remarks apply to cmso-types.

For a vocabulary and a binary relation symbol , we say that a subset is order-invariant if for all -structures and all linear orders of we have if, and only if, . If is inclusion-wise minimal order-invariant, then we call it an order-invariant type. Note that every is contained in exactly one order-invariant type, which we denote by . We set , the set of all order-invariant types. For a -structure , we call the set for some and, hence, for all linear orders of the order-invariant mso-type of of quantifier rank . It may seem more natural to define the order-invariant type of a structure as the set of all order-invariant sentences it satisfies. The following proposition says that this would lead to an equivalent notion, but our version is easier to work with, because it makes the connection between types of ordered structures and order-invariant types more explicit.

Lemma 2.1.

For all -structure , the following statements are equivalent.

1. .

2. .

3. There is a sequence of -structures and linear orders with , , and for all .

If , we say that sequences , , and as in statement 3 of Lemma 2.1 witness .

Proof of Lemma 2.1.

We prove each of the implications from the chain (1)(3)(2)(1).

For proving (1)(3), suppose . Let for some linear order of and for some linear order of . Let be the class of all ordered -structures such that there is a sequence of -structures and linear orders such that and and for all , and let the class of types for . An easy induction on the length of the witnessing sequence shows that . Moreover, is order-invariant, and thus . Similarly, we define and prove that . Thus , and this implies (3).

To prove (3)(2), just note that all structures in a witnessing sequence satisfy the same order-invariant formulas.

Finally, to prove (2)(1), suppose that . Let for some linear order of . Then . Let with . Then is an order-invariant mso-sentence of quantifier rank . As , we have , and thus satisfies as a sentence of <-inv-mso. Hence satisfies as a sentence of <-inv-mso, and thus for some linear order of . Thus there is a such that , which implies . Hence . ∎

2.4 Transductions

Transductions define new structures out of a given structure. We use -copying mso-transductions as defined in [10], but based on the below terminology. They are able to (1) enlarge the universe of a given structure by establishing copies of each element, (2) define relations over the new universe from the given structure, and (3) not only define a single structure, but a set of new structures parameterized by adding monadic relations to the given structure.

An mso-transduction of width with parameters for some is defined via a finite collection of mso-formulas over where the relation symbols are monadic and not part of . consists of a group of mso-formulas ,…, for defining the universe of a new structure and for each with some arity a group of formulas for . Given a -structure and , they define the universe of a -structure via

 U(Λ[A,P1,…,Pp]) :={(a,i)∈U(A)×{1,…,w}∣(A,P1,…,Pp)⊨λiU(a)}

and for each relation symbol the relation

 R(Λ[A,P1,…,Pp]) :={((a1,i1),…,(ar,ir))∈(U(A)×{1,…,w})r∣A⊨λ(i1,…,ir)R(a1,…,ar)}.

Finally, by ranging over all possible parameters, defines the set

 Λ[A]:={Λ[A,P1,…,Pp]∣P1,…,Pp⊆U(A)∧(A,P1,…,Pp)⊨λ\textscvalid}

for a given structure where is a formula that is also part of the transduction, which singles out the valid combinations of the given structure and parameters. Moreover, for a -structure , we set . For an element , we call its level.

mso-transductions preserve mso-definability (formally stated by Fact 2.2) and they can be composed to form new transductions (formally stated by Fact 2.3). For a formal proof of Fact 2.3, which implies Fact 2.2, see [10]. The facts also hold if we replace all occurrences of mso by cmso.

Fact 2.2 (mso is closed under mso-transductions).

Let be an mso-definable property of -structures and an mso-transduction. Then the property of -structures is mso-definable.

Fact 2.3 (mso-transductions are closed under composition).

Let be an -transduction and be an for some vocabularies . Then there is an -transduction with for every -structure .

3 Lifting Definability

An ordered tree decomposition of a structure is a tree decomposition of together with a linear order for each bag. We represent ordered tree decompositions by logical structures in the following way. An ordered tree extension (otx for short) of a -structure is a structure that extends by a tree decomposition of and a linear order of for each . The adhesion of is the adhesion of the tree decomposition . Formally, we view as a structure over the vocabulary , where and are unary, and are binary, and is ternary. Of course we assume that none of these symbols appears in . In the -structure , these symbols are interpreted as follows:

 VS(A⋆) :=U(A), VT(A⋆) :=V(TA), ET(A⋆) :=E(TA), Rβ(A⋆) :={(t,v)∣t∈V(TA),v∈βA(t)},and R⪯(A⋆) :={(t,v,w)∣t∈V(TA) and v,w∈βA(t) with v⪯Atw}.

An -transduction defines an otx (of adhesion at most ) of a -structure if every is isomorphic to an otx of (of adhesion at most ) and is nonempty. We say that defines otxs (of adhesion at most ) on a class of -structures if defines an otx (of adhesion at most ) of every . Moreover, admits mso-definable ordered tree decompositions (of bounded adhesion) if there is such a transduction that defines otxs (of adhesion at most for some constant ) on . We make similar definitions for the logic cmso.

We prove the following theorems, which show how to use the tree decompositions and the bag orderings to define properties of order-invariant formulas without using order invariance.

Theorem 3.1 (Lifting theorem for <-inv-mso).

Let be a class of structures that admits cmso-definable ordered tree decompositions of bounded adhesion. Then on .

Theorem 3.2 (Lifting theorem for <-inv-fo).

Let be a class of structures that admits mso-definable ordered tree decompositions of bounded adhesion. Then on .

Theorem 3.1 is proved in three steps: First, in Section 3.1, we modify the given ordered tree extension, such that its tree decomposition follows a certain normal form that allows to partition its nodes into two different classes (called a-nodes and b-nodes). The partition of the nodes along with a global partial order that is based on the local orderings in the bags is then encoded as part of the structure, turning every otx into an expanded otx. Second, in Section 3.2, we prove type-composition lemmas for both the a-nodes and the b-nodes. They show how one can define the type of an expanded otx with respect to total orderings that respect the already existing partial order from the types of substructures that arise by adding such compatible orderings to them. Third, Section 3.3 shows how these type-composition lemmas can be used in the context of order-invariance. Finally, Section 3.4 applies the type compositions to prove Theorem 3.1. The proof of Theorem 3.2 proceeds in a similar way. The modifications that we need to apply to the proof of Theorem 3.1 in order to prove Theorem 3.2 are mentioned along the way.

3.1 Segmented Ordered Tree Extensions

Recall that we view the tree in a tree decomposition as directed. A tree decomposition of a structure is segmented if the set can be partitioned into a set of adhesion nodes and a set of bag nodes (a-nodes and b-nodes, for short) satisfying the following conditions.

1. For all edges , either and or and .

2. For all a-nodes and all distinct neighbors , we have .

3. For all b-nodes and all distinct neighbors we have .

4. All leaves of are b-nodes.

We can transform an arbitrary tree decomposition into a segmented tree decomposition as follows. In the construction, we view as an undirected tree. We will have . Thus we can direct the edges of away from the root of , which will remain the root of . We first contract all edges with , resulting in a decomposition where for all . Then, for all edges , we introduce a new node , where , and edges from to and . Then we identify all nodes and such that . We let be the resulting tree. The nodes from the original tree are the b-nodes, and the nodes are the a-nodes. We define on by for and for all . The resulting tree decomposition is segmented. This transformation is definable by an mso-transduction. Thus we may assume that the tree decompositions in ordered tree extensions are segmented, because there is an -transduction that transforms every otx into an otx where the tree decomposition is segmented.

For the rest of this section, we fix a vocabulary that does not contain the order symbol and a . In the rest of this section, we only consider otxs of -structures. We assume that the adhesion of these otxs is at most and their tree decomposition is segmented.

It will be convenient to introduce some additional notation. As before, whenever we denote an otx by , we denote the underlying structure by and the tree decomposition by . We denote the descendant order in the tree of an otx by . For every node , we let be the subtree of rooted in , that is, . We let , called the cone of , be the union of all bags for . If is the parent of we let ; this is the separator at . For the root we let . In all these notations we may omit the index if is clear from the context. Note that for all a-nodes of and all we have .

We expand an otx to a structure over the vocabulary , where are unary and are binary relation symbols that do not appear in . We let and be the sets of a-nodes and b-nodes of the tree , respectively, and

 Rσ(A⋆⋆) :={(t,v)∣t∈V(TA),v∈σA(t)}, Rγ(A⋆⋆) :={(t,v)∣t∈V(TA),v∈γA(t)}.

We let be the partial order on defined as follows. We first define the restriction of to . For all b-nodes , we let be the linear order on defined by if the set is lexicographically smaller than or equal to the set with respect to the linear order on , for all children . This is indeed a linear order because is a linear order of and for all distinct . Then we let the restriction of to be the reflexive transitive closure of the “descendant order” on and all the relations for b-nodes . To define the restriction of to , for every we let be the topmost (that is, -minimal) node such that . Then we let if, and only if, or and . To complete the definition of , we let for all and .

Finally, we define the relations by letting be the set of all pairs , where and is the th element of with respect to the partial order , which is a linear order when restricted to . Recall that we have by our general assumption that the adhesion of all otxs is at most . This completes the definition of . It is easy to see that there is an -transduction that defines in .

We call an expanded otx (otxx for short) of . More generally, we call a -structure an expanded otx if there is a -structure such that is an otxx of . Let be an expanded otx. For every , we let

 A⋆⋆t :=A⋆⋆[γ(t)∪V(Tt)], and A⋆⋆(t) :=A⋆⋆[β(t)∪N+(t)].

We call a -structure a sub-otxx if there is an otxx and a node with . The only difference between an otxx and a sub-otxx is that in an otxx the set is empty for the root whereas in a sub-otxx it may be nonempty.

Lemma 3.3.

There are mso-sentences otxxs and sub-otxx of vocabulary defining the classes of all otxx and sub-otxx (satisfying our general assumptions: the tree decomposition is segmented and has adhesion at most ).

Proof.

Straightforward. ∎

We will later modify an otxx by replacing a sub-otxx , for some , by another sub-otxx . Let be the root node of the tree . The replacement is possible if the induced substructures and are isomorphic. If they are, there is a unique isomorphism, because and are linearly ordered by the restrictions of , . Now replacing by in just means deleting all elements in except those in , adding a disjoint copy of , and identifying the elements in and according to the unique isomorphism. Note that the substructures and are isomorphic if the sub-otxxs and satisfy the same first-order sentences of quantifier rank , where denote the maximum arity of a relation symbol in the vocabulary . To express isomorphism, we use the relations and the fact that the root of an otxx can be defined by a formula of quantifier rank . Thus in particular, if for some , we can replace by .

Finally, we say that a linear order on an otxx or sub-otxx is compatible if it extends the partial order . If is a compatible linear order, then denotes the -expansion of by this order, and denotes the induced substructure where is restricted to the sub-otxx . We can extend the replacement operation to such ordered expansions of otxxs; in the same way we replace a sub-otxx by , we can replace a by for some compatible linear order of .

3.2 Ordered Type Compositions

As all structures we are working with in this subsection are otxxs and sub-otxx, we denote them by rather than . Apart from that, we use the same notation as before. In particular, if is an otxx then by we denote the tree of its tree decomposition, and for a node , by we denote the sub-otxx rooted in , and we let .

Throughout this subsection, we fix a such that and and is at least the quantifier rank of the formulas otxx and sub-otxx of Lemma 3.3. This means that if is an otxx (or sub-otxx) and an arbitrary -structure with , then is an otxx (a sub-otxx) as well. Furthermore, if are the root nodes of , , respectively, then the induced substructures and are isomorphic. Finally, if are otxxs and are linear orders of , respectively, such that then is compatible if, and only if, is compatible.

We let . Furthermore, we assume that .

Let be an otxx, a compatible linear order of , and (usually for a node ). For all , let be the set of all such that . We call the type partition of . (Note that some of the may be empty. We always allow partitions to have empty parts.) The following lemma extends classical type-composition theorems [21, 14] to our situation, where substructures are combined through b-nodes.

Lemma 3.4 (Ordered type composition at b-nodes).

For every there is an -formula such that for every otxx , every b-node , and every compatible linear order of , if is the type partition of , then

 A(t)⊨b-typeθ(P1,…,Pm)% if, and only if, tp\textscmsoq(At,≤)=θ.
Proof.

For , let , and suppose that . Then and , and we may assume that for all . Let . The core of the proof is the following claim.

Claim.

Let be otxxs and compatible linear orders of , respectively. Let and . Let and be the type partitions of and , respectively. If

 tp\textscmsoq′(A(t),P01,…,P0m0)=tp\textscmsoq′(B(t′),Q01,…,Q0m0), (1)

then .

The claim implies that only depends on the type of


text:
# Math Help - Inverse Laplace Transform

1. ## Inverse Laplace Transform

Find the IVL of $\frac{(s-2)e^{-s}}{s^2-4s+3}$.

I am not understanding how my textbook gets the answer $u_1(t)e^{2(t-1)}cosh(t-1)$

I end up with

$e^{-s}\left(\frac{1}{2(s-1)}+\frac{1}{2(s-3)}\right)$

$=u_1(t)\left(\frac{1}{2}e^{(t-1)}+\frac{1}{2}e^{3(t-1)}\right)$

2. Originally Posted by petition Edgecombe
Find the IVL of $\frac{(s-2)e^{-s}}{s^2-4s+3}$.

I am not understanding how my textbook gets the answer $u_1(t)e^{2(t-1)}cosh(t-1)$

I end up with

$e^{-s}\left(\frac{1}{2(s-1)}+\frac{1}{2(s-3)}\right)$

$=u_1(t)\left(\frac{1}{2}e^{(t-1)}+\frac{1}{2}e^{3(t-1)}\right)$
$= u_1(t) e^{2(t-1)} \left(\frac{1}{2}e^{-(t-1)}+\frac{1}{2}e^{(t-1)}\right) \, ....$

3. OK, so my answer wasn't wrong, it just wasn't simplified. I've got to remember my hyperbolic functions.

format: plain


text:
# To which extent is general relativity a gauge theory?

In quantum mechanics, we know that a change of frame -- a gauge transform -- leaves the probability of an outcome measurement invariant (well, the square modulus of the wave-function, i.e. the probability), because it is just a multiplication by a phase term.

I was wondering about general relativity. Is there something left invariant by a change of frame? (of course, energy, momentum, ... are invariants of Lorentz transform, but these are special relativity examples. I guess there is something else, more intrinsic and related to the mathematical structure of the theory, like a space-time interval or something).

I've tried looking at the Landau book on field theory, but it is too dense for me to have a quick answer to this question. I have bad understanding about GR -- I apologize for that. I'm trying to understand to which respect one calls the GR theory a gauge theory: for me a gauge transform leaves something invariant.

Best regards.

EDIT: Thanks to the first answers, I think I should refine my question and first ask this: To which extent is general relativity a gauge theory? If you have good references to this topic, that would be great(The Wikipedia pages are obscure for me for the moment). Thanks in advance. Best regards.

• Parallel transport involves moving around in a manifold, while a change of frame is, well just that. The title of the question is a bit misleading.
– user10851
Dec 9, 2012 at 2:13
• Thanks Chris White, that's partly my problem: I see the parallel transport as a change of frame with one extra condition (the moving frame remains as much as possible parallel to the original one). My second problem was that in QM, the invariant quantity is an extra structure (the wave function modulus, whereas the wave function is displaced / covariant). This you partly answered with Namehere: only scalar are invariant, tensor are covariant. I was asking if it exists an extra structure kept invariant when changing frame of reference. Thanks to both of you. Dec 9, 2012 at 9:40
• @Oaoa Tensors are not covariant, they are invariant. It is their components that are covariant. And by the way there are many scalars that can be constructed from tensors, such as norms of vectors, traces of matrices and others. Oh, and was there anything else you think I missed or could improve in my answer(I didn't edit my question to include Chris White's comment since I felt it would be like stealing)? Dec 9, 2012 at 9:59
• I faintly remember that there is a nice way to think about GR as a gauge theory (or gauge theories as geometry), and it had to do with viewing the Levi-Civita connection as a gauge field. Unfortunately I don't know enough GR to write down the argument.
– jdm
Dec 9, 2012 at 12:10
• Related discussion here physics.stackexchange.com/q/12461 Dec 9, 2012 at 15:30

Consider a gauge theory with gauge group $GL(n,R)$.

First of all, let me remind you the basics of gauge transformations:

Let $G$ be a gauge group, $g(x)∈ G$ be an element of $G$. Then:

$\psi (x)→g(x)\psi (x)$

$A_\alpha→g(x)A_\alpha g^{-1}(x)-\frac{∂g(x)}{∂x^{\alpha}}g^{-1}(x)$

is a gauge transformation, and covariant derivative defined as

${\nabla}_{\alpha}\psi = \frac{∂\psi}{∂x^{\alpha}}+A_\alpha \psi$

Now consider coordinates $(x^1, ..., x^n)$ in region $U$. They define basis of vectors space $\frac{∂}{∂x^1},...,\frac{∂}{∂x^n}$. So, tangent vector fields in region $U$ can be considered as vector-valued functions: $\xi = (\xi^1,...,\xi^n)$. Change of coordinates in $U$: $x^{\nu}→x^{{\nu^{\prime}}}=x^{{\nu^{\prime}}}(x)$ defines local transformation:

$\xi^\nu→\xi^{\nu^\prime} = \frac{∂x^{\nu^\prime}}{∂x^\nu}\xi^\nu = g(x)\xi$.

Here matrix $g(x) = (\frac{∂x^{\nu^\prime}}{∂x^\nu})$ belongs to $GL(n,R)$, and inverse matrix has the form $g^{-1}(x)=(\frac{∂x^\nu}{∂x^{\nu^\prime}})$.

Lie algebra of $GL(n,R)$ is formed by all matrices of degree $n$, so the "gauge field" $A_\mu (x)$ is also matrix of degree $n$. Let us denote it's elements as follows:

$(A_\mu)^{\nu}_{\lambda}=\Gamma^{\nu}_{\lambda \mu}$.

Covariant derivative of the vector $\xi$ reads as follows:

$(\nabla_{\mu}\xi)^\nu=\frac{∂\xi^\nu}{∂x^\mu}+\Gamma^{\nu}_{\lambda \mu}\xi^\lambda ↔ \nabla_\mu \xi=\frac{∂\xi}{∂x^\mu}+A_\mu \xi$ (right side is in matrix form!)

There is only one thing left to check, namely the form of gauge field transformation.

Using general rule of transforming gauge field we obtain:

$\Gamma^{\nu}_{\lambda \mu}→\Gamma^{\nu^\prime}_{\lambda^\prime \mu}=\frac{∂x^{\nu^\prime}}{∂x^\nu}\Gamma^{\nu}_{\lambda \mu}\frac{∂x^\lambda}{∂x^{\lambda^\prime}}+\frac{∂x^{\nu^\prime}}{∂x^\nu}\frac{∂}{∂x^\mu}(\frac{∂x^\nu}{∂x^{\lambda^\prime}})$.

Since $A_\mu$ is a covariant vector, then $A_{\mu^\prime}=\frac{∂x^\mu}{∂x^{\mu^\prime}}A_\mu$. Hence we obtain:

$\Gamma^{\nu^\prime}_{\lambda^\prime \mu^\prime}=\frac{∂x^\mu}{∂x^{\mu^\prime}}\frac{∂x^{\nu^\prime}}{∂x^\nu}\Gamma^{\nu}_{\lambda \mu}\frac{∂x^\lambda}{∂x^{\lambda^\prime}}+\frac{∂x^{\nu^\prime}}{∂x^\nu}\frac{∂^2 x^\nu}{∂x^{\lambda^\prime}∂x^{\mu^\prime}}$.

Q.E.D.

And final remark: the commutator of two covariant derivatives leads to expression of the Riemann tensor:

$(F_{\mu\nu})^\rho_\lambda = R^\rho_{\lambda ,\mu\nu}$

EDIT:

Dear Oaoa,

I’m not a GR specialist, so what I have written below might be wrong.

My first advise is as follows: do not read Landau who is mixing up two fundamental concepts: connection and metric.

In order to answer your question let us first separate the roles of connection and metrics.

1. Connection is used for parallel transport and enables to compare two vectors in different points. Important consequence is that using connection one can introduce the curvature tensor (that can further be contracted to curvature scalar). Curvature appears when you transport vector along the closed curve and then compare with the initial vector. Curvature scalar is then used to construct “field action” just like in all gauge theories.

As shown in Schrödinger’s book, connection can also be used to measure distance along geodesic line (it worth noting that the expression for such “measure” is so much similar to the expression of Feynman’s path integral action!). But in general, connection cannot be used for measuring distances between arbitrary points.

1. Metric is introduced for measuring distances between arbitrary points and defining vector products.

2. Connection and Metric are independent concepts. Only additional condition of their consistency (i.e. when you require that vector product is invariant when both vectors are parallel transported) allows to express connection via metric tensor.

Let’s get back to your question now. All that is written about $GL(n,R)$ above is related to connection only. In the first place, it allows expressing “field action” in terms of a scalar curvature. But what you are most interested in is probably not this, but conservation laws related to matter fields. In the theory with point particles functions $\xi$ (or $\psi$) can be associated with vectors $\frac{dx^\nu}{ds}$. I’m not sure, but consequent conservation law is probably energy-momentum conservation. I think it is the same in Special relativity where space is flat and all connections are zero, but indirectly the conservation of energy-momentum in SR might be a consequence of “conservation” of null curvature by Lorentz transformations (please note that homogeneity of space-time means zero curvature). I know you expect to see some other conserved quantities similar to “electric charge” conservation in Dirac theory of electron. But please note that in Dirac theory the “global” conservation of “charge” is practically indistinguishable from conservation of energy-momentum. As for local theories – I do not know, concrete model need to be considered.

• thanks. So you've shown that the Christofell symbols behave mathematically like a connection under a general GL gauge group transform. What is the field $\psi(x)$ in your notations ? Is it by some extent conserved ? Thanks in advance. Dec 9, 2012 at 17:21
• But $GL(n)$ doesn't admit finite dimensional unitary representations, which cause problems when we want to write down components of fields...because you end up with an infinite number of components...which is why people usually use $SO(4)$ (or $SO(3,1)$ depending on your religion) instead. Dec 9, 2012 at 21:28
• @AlexNelson Thank you for this comment. Indeed, that's part of the problem when trying to use gauge theory. Dec 10, 2012 at 9:31
• @MurodAbdukhakimov Thank again and so much for your new update. Thanks also for the two references (I actually tried to read Utiyama paper last year, without big success). I will try to read the book by Schrödinger for the holidays. Thanks a lot again. Dec 10, 2012 at 9:33
• I think one has to be a little bit careful here. The above construction essentially shows that the Christoffel symbols can be thought of as components of a connection on the tangent bundle of the space-time manifold (as you mention one has additional conditions such that this is compatible with the metric, leading to the Levi-Civita metric). But GR is NOT like a Yang-Mills theory since its action cannot be written in a form which resembles such types of gauge theories (of spin-one fields). (continued) Dec 11, 2012 at 0:35

GR has some formal resemblance to Yang-Mills gauge theory. But it isn't quite the same thing.

We formulate YM in terms of gauge fields, AKA, connections on G-bundles on our manifold. We also make use of a connection when we formulate GR, the Levi-Civita connection on the tangent bundle of our spacetime, which is determined by the metric and some assumptions (metric is covariantly constant, no torsion). But the metric is the more fundamental degree of freedom, and there's nothing like this in YM theory. (You can do functional integration on the space of YM fields with enough mathematical rigor to satisfy most physicists, but in 4d, it's not possible to do this with metrics.)

Another similarity: The observables in YM theory are invariants of the group of gauge transformations. Similarly, in GR, the true observables are generally supposed to be invariant under the group of spacetime diffeomorphisms (n.b., not the same thing as the group of gauge transformations for the tangent bundle). These observables aren't generally local observables, like the curvature at a point, but instead more complicated expression constructed from local observables, like the average of the curvature over the spacetime. This is also in contrast to Yang-Mills theory, where there are plenty of local observables, like the energy density of the YM field at a point.

The common theme is that we have to introduce weird auxilliary unphysical variables into both theories to make locality and Lorentz invariance manifest; physical observables are then obtained by forgetting the redundant information.

• Your answer seems to indicate that "gauge theory = Yang-Mills", which might confuse people. Jun 7, 2017 at 15:22
• @jinawee what's the most important between the two ? May 1 at 21:09

The precise sense in which general relativity is a gauge theory has been known (but apparently largely overlooked) for decades. The original sources for what I'm summarizing in the following are a series of papers by Andrzej Trautman, in particular "Fibre bundles associated with space-time", "On Gauge Transformations and Symmetries" and "Fiber Bundles, Gauge Fields and Gravitation". This answer will be a bit lengthy since it rehashes the essential bits of the theory of bundles necessary to get at least an idea of what we're doing. The upshot is this:

Both Yang-Mills theories and general relativity are "gauge theories" if we pick an idea of a gauge theory where some bundle - a structure "over spacetime" - has transformations, and some of these transformations can preserve the physics we care about. Yang-Mills theories are cases where these transformations split neatly into finite-dimensional "spacetime" and infinite-dimensional "internal" symmetries, while general relativity produces infinite-dimensional spacetime and no internal symmetries. This lack of internal symmetries - usually seen as the hallmark of "gauge theories" - explains why there are many claims that general relativity is "not a gauge theory": This claim is correct if one takes the definition in terms of internal symmetries.

In any case, our generic notion of a gauge theory which will encompass both Yang-Mills type theories and GR is that of a $$G$$-principal bundle $$\pi : P\to M$$ over our spacetime $$M$$ on which we have a connection 1-form $$\omega$$. $$\omega$$ descends for charts $$\phi_i : U_i \to M$$ over which $$P$$ is trivial to $$\mathfrak{g}$$-valued 1-forms $$\omega_i$$ on $$M$$, these $$\omega_i$$ are what we usually call "the gauge field". We have $$\omega_i = (\omega_i)_\mu^a T^a\mathrm{d}x^\mu$$ for $$T^a$$ a set of generators for the group, the $$(\omega_i)_\mu^a$$ are the connection coefficients. In the case of a Yang-Mills theory, we usually write these as $$A_\mu^a$$ and call them the gauge field or the gauge potential.

The group of gauge transformations $$\mathscr{G}$$ is the group of all bundle automorphisms $$P\to P$$ (this full group we will just write as $$\mathrm{Aut}(P)$$) that additionally preserve the "fundamental structures" of our theory. A diffeomorphism $$f : P\to P$$ is a bundle automorphism if there is a diffeomorphism of the base $$\bar{f} : M \to M$$ such that $$\pi\circ f = \bar{f}\circ \pi$$. A vertical or pure gauge transformation $$g : P\to P$$ is one that preserves the fibers $$\pi\circ g = \pi$$, i.e. acts only in the "internal space" of the gauge theory. We call the group of pure gauge transformations $$\mathscr{G}_0$$. It is usually the case that $$\mathscr{G_0}$$ connects "physically equivalent" configurations, while $$\mathscr{G}/\mathscr{G}_0$$ is some sort of spacetime symmetry. Note that by the definition of a bundle automorphism, we have a map $$\bar{} : \mathscr{G}\to \mathrm{Diff}(M)$$, and two gauge transformations that differ only by a pure gauge transformation have the same image under this map, so we can think of $$\mathscr{G}/\mathscr{G}_0\subset \mathrm{Diff}(M)$$.

For instance, for a Yang-Mills type theory, the essential structure that needs to be preserved is the Yang-Mills Lagrangian $$\mathrm{tr}(F\wedge{\star}F)$$, where $$F = \mathrm{d}_\omega \omega$$ is the curvature associated with a connection $$\omega$$. All vertical transformations preserve this since the trace is invariant under the action of the gauge group, so $$\mathscr{G}_0$$ is just all smooth functions $$g : P\to G$$, which are in bijection with local gauge transformations $$g_i : U_i\to G$$ for trivializing patches $$U_i$$. The Hodge star $$\star$$ involves the metric of the underlying space, so $$\mathscr{G}/\mathscr{G_0}$$ is just the isometries of $$M$$ connected to the identity.1 For the case of $$M=\mathbb{R}^{3,1}$$ and a trivial bundle $$M\times G$$, we have $$\mathscr{G} = \mathscr{G}_0 \ltimes \mathrm{P}_0(3,1)$$, where $$\mathrm{P}_0$$ is the identity component of the Poincaré group.

For general relativity, the metric on the base space is dynamic and hence nothing we need to preserve. This makes the theory different from the outset, since nothing really seems to restrict $$\mathscr{G}/\mathscr{G}_0$$. Furthermore, the principal bundle $$P$$ in general relativity is the frame bundle $$FM$$, which is the bundle of all possible choices of bases for the tangent spaces of $$M$$. That is, a point in $$FM$$ is given by $$(x,v)$$, where $$x\in M$$ and $$v$$ is a basis of $$T_x M$$. We can think about the data necessary for a basis in terms of a linear isomorphism $$v : \mathbb{R}^{\mathrm{dim}(M)}\to T_x M$$, or as the images of the standard basis $$e_i$$ of $$\mathbb{R}^n$$, $$v_i := v(e_i)$$. In any case, the frame bundle is a $$\mathrm{GL}(n)$$-principal bundle over $$M$$ that inherits its bundle structure from the tangent bundle: If $$\phi_i : \pi_T^{-1}(U_i) \to U_i\times\mathbb{R}^n$$ are a trivialization of the tangent bundle, then $$F(\phi_i) : \pi_F^{-1}(U_i) \to U_i\times\mathrm{GL}(n), (x,v)\mapsto (x,\phi_{i,x}\circ v)$$ is a trivialization of the frame bundle. There are natural coordinates for the frame bundle induced by a coordinate chart of $$M$$, which means that we often don't really appreciate when an object lives in the frame bundle rather than on $$M$$ itself. 2

Since we have defined $$FM$$ via the tangent bundle $$TM$$, it is "attached" to $$TM$$ and therefore $$M$$ itself in a way that a generic principal bundle is not. We say that it is soldered to $$M$$, and this soldering is expressed by the solder form $$\theta_{(x,v)}(X) = v^{-1}\mathrm{d}\pi_F(X)$$, which is a $$\mathbb{R}^n$$-valued 1-form on $$FM$$. This form is horizontal and equivariant, and by general arguments it corresponds therefore to a $$TM$$-valued form on $$M$$. The form it corresponds to is just the identity $$TM\to TM$$, read as a form $$\mathrm{id}_x(X) = X$$ (or, in coordinates, $$\mathrm{id} = \delta^\mu_\nu \partial_\mu\otimes \mathrm{d}x^\nu$$).

This form is the crucial object that distinguishes general relativity from Yang-Mills type theories. It allows us to define a lot of the oft-studied objects such as the Ricci curvature and Ricci scalar: We can think of the solder form as a collection of $$\mathbb{R}$$-valued 1-forms $$\theta^\mu$$. These form a basis of horizontal equivariant 1-forms, i.e. we have $$G = G_{\mu_1\dots \mu_k} \theta^{\mu_1}\wedge\dots\wedge \theta^{\mu_k}$$ for any equivariant horizontal $$k$$-form $$G$$ and in particular $$x^\ast \theta^\mu = \mathrm{d}x^\mu$$ for any coordinate system $$x$$. This allows us to write things like $$F_\omega = {{F_\omega}^\mu}_\nu {T^\nu}_\mu = {R^\mu}_{\nu\sigma\rho}{T^\nu}_\mu (\theta^\sigma\wedge \theta^\rho)$$ and define the Riemann tensor with its usual four indices without reference to any particular coordinate system - its contractions then yields the usual quantities of interest. In order for these constructions to be preserved, gauge transformations need to preserve the solder form, i.e. $$g\in\mathscr{G}$$ must fulfill $$g^\ast\theta = \theta$$.

It turns out that this means $$\mathscr{G}\cong \mathrm{Diff}_0(M)$$ and $$\mathscr{G}_0\cong \{1\}$$ (see this answer of mine for an explanation of Trautman's argument for this), i.e. the group of gauge transformations is isomorphic to the group of small (= generated as the flow of vector fields) diffeomorphisms and contains no non-trivial pure gauge transformations. This explains a) how general relativity is a "gauge theory" in a broad sense and b) why we often find the puzzling claim that the crux of general relativity is "diffeomorphism invariance". What it is invariant under is not actually simple "diffeomorphisms", but transformations of the frame bundle that are in bijection to these diffeomorphisms. Infinitesimally and for a connection without torsion, the generators of these induced transformations of the frame bundle are given by a vector field $$X^\mu$$ and its covariant derivatives $$\nabla_\mu X^\nu$$, interpreted as a $$\mathfrak{gl}(n)$$ matrix.

Footnotes

1. Diffeomorphisms not connected to the identity cannot in general lift to bundle automorphisms, see this MO answer.

2. A coordinate chart $$x:\mathbb{R}^n\to U\subset M$$ defines a frame $$F(x)$$ on $$U$$ by $$e_i\mapsto \partial_i$$ and a frame $$v$$ in turn defines coordinates on $$FU$$ by expanding any $$(y,w)\in F_y M$$ into $$w_i = w^j_i v_j$$ and the $$w^j_i$$ are $$\mathbb{R}^{n^2}$$-valued coordinates for $$FU$$, so using this for the frame $$F(x)$$ gives coordinates $$(x^\mu, w^\nu_\sigma)$$. In these coordinates, we have a basis $$T^i_j$$ of the vertical part $$V(FM)\subset T(FM)$$ given by $$T^i_j = \partial_{w^i_j}$$, and expanding $$\omega$$ in this basis gives the Christoffel symbols: $$\omega = \Gamma_\mu \mathrm{d}x^\mu = {{\Gamma_\mu}^\nu}_\sigma \partial_{w^\nu_\sigma} \otimes \mathrm{d}x^\mu$$.

In general relativity, tensor fields(e.g. the metric tensor, the Riemann curvature tensor, the energy momentum tensor) are left unchanged by changes of frames. Tensors are naturally unchanged under changes of frames. They form the basis of general relativity and is the key to how general relativity is generally covariant.

Update:

A note on the invariance of tensors: while tensors are invariant their components certainly do vary under different frames. There are also scalars which are 'single numbers' that don't change at all.

I do not think general relativity can be considered a gauge theory at all. In general, there are no local or global symmetries in the Langrangian of general relativity. Any spacetime can occur in general relativity; just define the energy momentum tensor according to Einstein's field equations.

• Also, while tensors as a whole are "invariant" in their own geometric sense, their components certainly change. If you want a single number to be unchanged, then you have to restrict yourself to scalars.
– user10851
Dec 9, 2012 at 2:16
• @ChrisWhite Yes, I should have included that too. Thank you for reminding me. Dec 9, 2012 at 2:54
• @Oaoa No problem :) Dec 9, 2012 at 13:25
Consider a classical field theory with gauge group $\mathcal G$. Suppose that $\mathcal G ⊂ \mathrm{Aut}(Y)$, the automorphism group of the covariant configuration bundle $Y$. We may distinguish two basic types of field theories based upon the relationship between the gauge group $\mathcal G$ and the (spacetime) diffeomorphism group $\mathrm{Diff}(X)$.
The first consists of those which are parametrized in the sense that the natural homomorphism $\mathrm{Aut}(Y) \to \mathrm{Diff}(X)$ given by $η_Y \mapsto η_X$ maps $\mathcal G$ onto $\mathrm{Diff}(X)$ (or at least onto a “sufficiently large” subgroup thereof, such as the compactly supported diffeomorphisms). This terminology reflects the fact that such a theory is invariant under (essentially) arbitrary relabeling of the points of the parameter “spacetime” $X$. (In relativity theory, cf. Anderson [1967], one would say that $X$ is a relative object in the theory.) The parametrized theory par excellence is of course general relativity, in which case $\mathcal G$ equals the spacetime diffeomorphism group.


text:
Dynamic programming: Maximize total value

I was trying to solve this problem using dynamic programming.

We have $$n$$ objects in a row where each object has a value represented with a positive number. This is encoded with an array $$V[1], . . . , V[n]$$ where $$V [1]$$ is the value of the first object in the row, $$V [2]$$ is the value of the second object in the row and so on. We want to select a set $$I \subseteq \{1, . . . , n\}$$ of objects in such a way that the sum of its values, $$\sum\limits_{i\in I} V [i]$$, is as large as possible. However, we cannot select objects that occupy consecutive positions in the row. That is, if we select object $$i$$, then we cannot select object $$i − 1$$ nor object $$i + 1$$. For example, if $$V = (6, 4, 3, 7, 3)$$ then the best option would be to select the first object (with value $$6$$) and the fourth object (with value $$7$$). It is easy to see that any other option would have smaller total value. We want a dynamic programming algorithm that, given as input array $$V$$ , computes the value of the set with highest value. Note that, in order to simplify matters, we do not ask that the algorithm returns the set, only its total value.

The probleem comes when it says "we cannot select object $$i − 1$$ nor object $$i + 1$$". For $$i-1$$, the recursive case should be Optimal$$(j-2)$$+Value$$(j)$$, but no idea about $$i+1$$.

For $$k \in [\![1, n]\!]$$, you can define $$f(k)$$ as the maximum value reachable using objects $$1$$, $$2$$, …, $$k$$, without two consecutives objects.
$$\forall k \in [\![3, n]\!], f(k) = \max(f(k-1), f(k-2) + V[k])$$
The reason is that to compute $$f(k)$$, you can either keep the $$k$$-th object or not. If you keep it, then you cannot keep the $$k-1$$-th object.
Finally, you want to compute $$f(n)$$.


text:
# Kile autocompletion not working [closed]

I am using Kile Version 2.9.60 on Windows. For some reason the autocompletion of environments does not work anymore, i.e. when you press enter after typing \begin{enviroment} nothing happens besides going to the next line ...

I have checked settings->configure kile->enviroments-> Automatically complete \begin{env} with \end{env}.

-

## closed as unclear what you're asking by Joseph Wright♦Aug 3 at 9:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

I had that sometimes. I never found out why it happened (and also never bothered to find out). Restarting kile usually helps. –  cgnieder Feb 2 '13 at 13:11
restarting does not help here –  Nadori Feb 2 '13 at 14:41
This sounds like a 'one-off' issue: certainly without more detail a solution is unlikely –  Joseph Wright Aug 3 at 9:07


text:
# What are the reactions for amines and amides?

Sep 22, 2017

An amine is an organic compound, related to ammonia, that contains a nitrogen atom bonded to one or more alkyl groups on each molecule

$\text{Primary amine}$

$\text{an example of Secondary amine}$

$\text{Tertiary amine}$

Nitrogen atoms that are part of an aromatic ring have planar configuration(sp2 configuration ) and not stereogenic centres.Because of aromacity amines in aromatic rings are stable.
As the hybridation of the nitrogen its effects its power as an acid and base.
Higher s character of the nitrogen makes the compound acidic for example in pyridine and nitriles.

Secondly, aniline and p-nitroaniline are weaker bases due to delocalization of the nitrogen non-bonding electron pair into the aromatic ring (and the nitro substituent). This is the same delocalization that results in activation of a benzene ring toward electrophilic substitution.

The following resonance equations, which are similar to those used to explain the enhanced acidity of ortho and para-nitrophenols illustrate electron pair delocalization in p-nitroaniline.

Although resonance delocalization generally reduces the basicity of amines, a dramatic example of the reverse effect is found in the compound guanidine (pKa = 13.6).

Amines are mostly basic but some have reduced basicity because of these reasons
color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

When reacted with acids, amines donate electrons to form ammonium salts.

Acid halides react with amines to form substituted amides

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

Production of Schiff bases from primary amines

Aldehydes and ketones react with primary amines to give a reaction product (a carbinolamine) that dehydrates to yield aldimines and ketimines (Schiff bases)

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

If you react secondary amines with aldehydes or ketones, enamines form.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
Amines react with sulfonyl chlorides to produce sulfonamides. A typical example is the reaction of benzene sulfonyl chloride with aniline.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

The Hinsberg test

The Hinsberg test, which can distinguish primary, secondary, and tertiary amines, is based upon sulfonamide formation. In the Hinsberg test, an amine is reacted with benzene sulfonyl chloride. If a product forms, the amine is either a primary or secondary amine, because tertiary amines do not form stable sulfonamides. If the sulfonamide that forms dissolves in aqueous sodium hydroxide solution, it is a primary amine. If the sulfonamide is insoluble in aqueous sodium hydroxide, it is a secondary amine. The sulfonamide of a primary amine is soluble in an aqueous base because it still possesses an acidic hydrogen on the nitrogen, which can be lost to form a sodium salt.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

Oxidation of amines
Although you can oxidize all amines, only tertiary amines give easily isolated products. The oxidation of a tertiary amine leads to the formation of an amine oxide.

Arylamines tend to be easily oxidized, with oxidation occurring on the amine group as well as in the ring.
color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
Reaction with nitrous acid

Nitrous acid is unstable and must be prepared in the reaction solution by mixing sodium nitrite with acid.

Primary amines react with nitrous acid to yield a diazonium salt, which is highly unstable and degradates into a carbocation that is capable of reaction with any nucleophile in solution. Therefore, reacting primary amines with nitrous acid leads to a mixture of alcohol, alkenes, and alkyl halides.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
Primary aromatic amines form stable diazonium salts at zero degrees.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

Secondary aliphatic and aromatic amines form nitrosoamine with nitrous acid.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

Tertiary amines react with nitrous acid to form N‐nitrosoammonium compounds.

color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc) color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)
color(white)(cccccccccccccccccccccccccccccccccccccccccccc)

Reactions of aromatic diazonium salts
Diazonium salts of aromatic amines are very useful as intermediates to other compounds. Because aromatic diazonium salts are only stable at very low temperatures (zero degrees and below), warming these salts initiates decomposition into highly reactive cations. These cations can react with any anion present in solution to form a variety of compounds. The following figure illustrates the diversity of the reactions.

Sep 22, 2017

Amides can undergo some special reaction or types of reaction which are the following ones

1) Nucleophilic Acyl Subsctitution

2) Reduction of amides with LiAl4

3) Reaction with nitrous acid

5) Dehydration of Amides

Nucleophilic Acyl Subsctitution

Heat helps in dissociation of water

"RCONR'"_2 + "H"^(+) + "OH"^(-) rarr ("RCO"+"OH"^(-)) + ("R'"_2"N"+"H"^+)

Mechanism

To begin, we know that in the first step, a strong base is going to be used like $\text{NaOH}$, where the $\textcolor{b l u e}{\text{OH"^(-) "will act as the}}$ $\textcolor{b l u e}{\text{nucleophile and attack the electrophile, the partial}}$ $\textcolor{b l u e}{\text{positive carbon of the carbonyl group}}$

Now, when the bond forms between the $\text{oxygen}$ of the ${\text{OH}}^{-}$ group and the carbon, the $\text{pi bond}$ of the carbonyl is broken and the electrons are pushed toward oxygen, leaving it with a negative $- 1$ charge.

$- - - - - - - - - - - - - - - - - - - - -$

$\textcolor{p u r p \le}{2.}$

$\textcolor{b l u e}{\text{Oxygen will try to remove this negative charge by}}$$\textcolor{b l u e}{\text{reforming a double bond with the carbon.}}$$\textcolor{b l u e}{\text{But since we know that the carbon atom}}$$\textcolor{b l u e}{\text{cannot form more than 4 bonds, the bond between it }}$$\textcolor{b l u e}{\text{and the amine's nitrogen has to be broken.}}$$\textcolor{b l u e}{\text{The electrons will be pushed onto the nitrogen of the}}$$\textcolor{b l u e}{\text{ amine and the amine will act as the leaving group (a poor one at that)}}$

*The reason the amine is a poor leaving group is because the amine is a strong base, and strong bases are very unstable. Leaving groups are based off their stability in solution, like the halides, tosylate, $\text{H"_2"O}$

$- - - - - - - - - - - - - - - - - - - - -$

$\textcolor{p u r p \le}{3.}$

$\textcolor{b l u e}{\text{Here, the NH"_2^(-) "will act as a base and pluck off the}}$$\textcolor{b l u e}{\text{ H from the carboxylic acid -type of acid-base}}$ $\textcolor{b l u e}{\text{reaction. When this happens, a 'carboxylate anion'}}$ $\textcolor{b l u e}{{\text{forms and NH}}_{3}}$.

Mechanism of acid catalysed amide hydrolysis

Step 1)An acid/base reaction. Since we only have a weak nucleophile and a poor electrophile we need to activate the ester. Protonation of the amide carbonyl makes it more electrophilic

Step 2:
The water O functions as the nucleophile attacking the electrophilic C in the C=O, with the electrons moving towards the oxonium ion, creating the tetrahedral intermediate.

Step 3:
An acid/base reaction. Deprotonate the oxygen that came from the water molecule.

Step 4:
An acid/base reaction. Need to make the -NH2 leave, but need to convert it into a good leaving group first by protonation.

Step 5:
Use the electrons of an adjacent oxygen to help "push out" the leaving group, a neutral ammonia molecule.

Step 6:
An acid/base reaction. Deprotonation of the oxonium ion reveals the carbonyl in the carboxylic acid product and regenerates the acid catalyst.

Reduction of amides with LiAl4

Leaving group removal

Nucleophilic attach by the hydride

Hoffman Degradation is a reaction between an amide and a mixture of bromine and sodium hydroxide solution.Heat is needed.

Mechanism

Step 1) Base abstracts an acidic N-H proton, yielding an anion

Step 2) The anion reacts with bromine in an α-substitution reaction to give an N-bromoamide.

Step 3) Base abstraction of the remaining amide proton gives a bromoamide anion.

Step 4) The bromoamide anion rearranges as the R group attached to the carbonyl carbon migrates to nitrogen at the same time the bromide ion leaves, giving an isocyanate.

Step 5) The isocyanate adds water in a nucleophilic addition step to yield a carbamic acid (aka urethane).

Step 6) The carbamic acid spontaneously loses CO2, yielding the amine product.

Dehydration of amides

Amines are dehydrated by reacting it with phosphorus(V) oxide or phosphorus oxychloride and heating the mixture


text:
## 2009 m. lapkričio 1 d., sekmadienis

### Dienos klausimas - austrų ekonomikos mokykla ir investicijos

"Does malinvestment include investments that should have been made but weren't? I usually assume so, but many people talk as though it only includes investments that shouldn't have been made but were. I think this blinds some to the kind of malinvestment that occurs during deflation, because it primarily is in the form of investments that should be made but aren't."

Lee Kelly - Bill Woolsey blogo komentatorius


text:
# Cantor's unspeakable numbers

An unspeakable number is a number which is divisible by seven or has seven as one of its digits. A children game is to count skipping unspeakable numbers

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

Cantor's version of the game is the sequence defined by recursively filling in the sequence "1 2 3 4 5 6 ( ) 8..." into the gaps ( ) above.

1 2 3 4 5 6 1 8 9 10 11 12 13 2 15 16 3 18 19 20 4 22 23 24 25 26 5 6 29 30 31 32 33 34 1 36 8 38 ...

Print/output at least the first 7^7 numbers of Cantor's unspeakable number game...

While the definition is given recursively, you are not obliged to use recursion in the code.

This is , so the program with the shortest byte count wins!

Note: The sum of numbers in 1 to 7^7 is 203511962727. The last 10 numbers in that range are 823534 823535 221563 108068 823538 823539 823540 823541 823542 221565.

Pastebin dump of first 1000 iterates: http://pastebin.com/Ksiu9Svf

• Please provide the first 7^7 numbers of that sequence such that we can check our solutions. Nov 27 '16 at 10:20
• Related Nov 27 '16 at 10:29
• In case anybody wants to generate some more numbers and compare results: The sum of the first 7^77 numbers in the sequence is 3336402440238885119980169136020683586413168645292341926482898521634332654984279162327502549917668322950744929983987545341421076028 Nov 28 '16 at 23:46
• Sure, the number of 1's in that sequence is 22977, which means if you pick an element out of the first 7^77 uniformly at random, you have a 2 * 10^-61 chance of it being a 1 Nov 29 '16 at 8:10
• In case you are interested, here is a graph showing the growth of the number of repeated ones: drive.google.com/file/d/0B71iQwGfNtw5NGladjdOZVhoNkk/… Nov 29 '16 at 9:41

# Python 2, 777574 70 bytes

Thanks to @MartinEnder for suggesting the limit of 9e5 which enderd up working after a change.
Thanks to @mschauer for suggesting an infinite stream, saving 4 bytes.

def f(n=0):
i=f()
while 1:n+=1;yield next(i)if'7'innor n%7<1else n

This is a generator that yields an infinite stream of the numbers.

• Could you not remove the upper bound entirely? Nov 27 '16 at 13:30
• @mschauer Thanks, didn't think of that one. Nov 27 '16 at 13:57
• if n%7<1or'7'innelse n might be slightly faster (same byte count), since n%7<1 is faster than checking the string, and or is short-circuiting. It's too bad that yield[n,next(i)][n%7<1or'7'inn] won't work. Nov 29 '16 at 23:03
• @mbomb007 I don't think speed is an issue here, but thanks. :) Nov 29 '16 at 23:04

# Perl, 474641 39 bytes

Saved 5 bytes thanks to @Dada

say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6  Try It Online! TIO Nexus, now with Perl support! This will truncate the output after a certain point, but if you have Perl installed, you can run it locally to produce the full output. The code makes use of a couple of strange quirks of Perl's syntax, so I'll break down how it works below. ### Code breakdown: say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6
@a=1..1e6 #Assign the range (1..1,000,000) to the array @a
for          #and then loop through this list, with $_ as an alias for the list member. As an alias, modifying$_ modifies @a.
$_%7*!/7/?$_:$a[$b++]             #Ternary operation
$_%7 #Returns the residue modulo 7... *!/7/ #...and multiplies it by the negation of whether or not there exists a 7$_
#Since % and * have the same operator precedence, it must be evaluated in this order
#otherwise we would get (!/7/*$_)%7 instead of ($_%7)*!/7/
?$_ #If the result is non-zero (i.e. truthy), then return$_
:$a[$b++]             #Otherwise, return the $b-th element of @a, and increment$b
$_= #Reassign the result back to$_, modifying @a
say                                     #Prints the result of the assignment, separated by newlines

• say$a[@a]=$_=... to win 2 bytes if I'm not mistaken.
– Dada
Nov 27 '16 at 22:30
• @Dada actually since that saves me from having to assign to $_, it saves me 5 bytes. Thanks! Nov 27 '16 at 22:39 • Oh indeed, I just had a quick look and didn't noticed that assignment in the middle.. good job :) – Dada Nov 27 '16 at 22:41 • It is at this moment (and this moment only!) that I have understood the statement "Perl can be quite the write-only language". Nov 28 '16 at 4:52 • @Grimy please don't edit others code. If you want to improve an answer add a comment including the improvement or post your own answer. As you probably won't reach the OP by a comment just post your own answer. – ovs Oct 24 '17 at 20:02 # Pyth, 2523 22 bytes Thanks to @Maltysen for -2 bytes .V1=+Y ?}7+PbjbT@Y~hZb  A program that prints an infinite stream. Try it online! (Output flushed at intervals and times out at 1 min) How it works .V1=+Y ?}7+PbjbT@Y~hZb Z = 0, Y = [] Implicit variable assignment .V1 Infinite incrementing for loop with variable b, starting at 1: =+Y Y = Y + (newline) (Implicitly print the result of the following:) ? If }7 7 is in Pb the prime factorisation of b + or jbT the digits of b: @Y Index into Y at index Z Z ~h (Increment Z) else: b b  • 23 bytes. It works cuz 7 is prime, so divisibility is can be done through checking the prime factorization, which fits in well with the other check Nov 27 '16 at 21:15 • you can post it, the main part of its yours Nov 27 '16 at 21:19 • Congratulation for winning this contest. I also like @Maltysen 's trick! Nov 30 '16 at 23:06 ## Haskell, 67 66 bytes i#x|mod x 7<1||'7'elemshow x=f!!i:(i+1)#(x+1)|y<-x+1=x:i#y f=0#1  f is an infinite list of the numbers. Try it online! f starts a new iteration with 1 and an index which number to pick of 0. Whenever there's a gap we take a new iteration an pick it's ith element and continue the current iteration with i+1. If there's no gap, we take the current number x and go on without increasing i. Edit: -1 byte thanks to @BMO. # PHP, 80 (Wahooka) 57 54 bytes While the idea is from Wahooka. I think my version is different enough to make it an own answer: for(;;)echo$a[]=strpos(++$n,55)<-$n%7?"$n ":$a[+$b++];  # MATL, 26 25 bytes 9e5:t7\yFYA!7-A*~s:2M(2M  Try it online! with 9e5 replaced by 9e4, so that the maximum running time and output size of the online compiler are not exceeded. ### How it works This uses iteration instead of recursion. (In fact, MATL doesn't have recursion). An array of numbers from 1 to 9e5 is first generated (this is enough, because 9e5 exceeds 7^7). Then, numbers that are multiples of 7 or have 7 as digit are identified, and replaced by 1, 2, ... The process is iterated until there are no numbers that need to be replaced. 9e5: % Generate array of numbers [1 2 ... 9e5]. This array will become the % output, after some numbers have been replaced  % Do...while t % Duplicate the array of numbers 7\ % Modulo 7. Gives zero for multiples of 7 y % Duplicate the array of numbers FYA! % Matrix of decimal digits, with a column for each number 7- % Subtract 7 to each entry of that matrix A % Array that contains "true" for columns that only contain nonzeros; % that is, for numbers that do not have 7 as digit * % Multiply. This corresponds to a logical "and" of the two conditions. % A zero indicates that the number at that index needs to be replaced ~ % Logical negate. Each "true" corresponds to a number to be replaced s % Sum. This is the amount of numbers to be replaced, say n : % Push array [1 2 ... n] 2M % Push array of logical values again ( % Replace the numbers at the positions indicated by the logical array % by the values [1 2 ... n] 2M % Push n again. This is used as loop condition, so if it is nonzero % the next iteration will be executed. Note that this executes one % too many iterations: the exit condition is that no replacing has % been needed in the current iteration; but then the current iteration % (which will be the last) was not really necessary. This does not % matter; the last iteration is useless but also harmless % End do...while implicitly. Display implicitly  # Tcl, 121 Bytes The trivial solution using infinite loop, nothing fancy.. set r 0;set n 0;while {[set r [expr$r+1]]} {if {![expr $r%7]||(7 in[split$r ""])} {puts [set n [expr $n+1]]} {puts$r}}

Ungolfed:

set r 0
set n 0
while {[set r [expr $r+1]]} { if {![expr$r % 7] || (7 in [split $r ""])} { puts [set n [expr$n+1]]
} {
puts $r } }  • You can use incr. And if tcl version >= 8.6, incr assumes the first iteration an increment of a new variable from 0 to 1 if that variable was not set before; so you can get rid of the first two set instructions. May 28 '17 at 15:01 • golfed by me — I removed also some non needed white space. May 28 '17 at 15:30 • The site where I posted my golfing suggestions for you has lost them, so I made a my new answer May 25 '18 at 23:50 # PHP, 106 80 bytes Thank you Ismael Miguel for help with the ternary solution and shorter loop code using for instead of while. Could not verify the last parts of the full sequence due to PhpFiddle's 30 second max runtime. Seems to work at least up to 1K based on the sample output provided by the OP. Golf: for($n=1;;$n++)echo$a[]=!(strpos($n,"7")>-1||$n%7==0)?"$n ":array_shift($a)." ";

Original golfed version:

$n=1;while(1){if(!(strpos($n,"7")>-1||$n%7==0)){echo$a[]=$n." ";}else{echo$a[]=array_shift($a)." ";}$n++;}

• for($n=1;;$n++)echo$a[]=!(strpos($n,7)>-1||$n%7==0)?"$n ":array_shift($a)." "; I don't know the byte count, but I'm sure it is a lot lower than 106 bytes. Try it out and see if it works. Nov 27 '16 at 18:36 • Very nice, thanks for the help. The only modification to your code was to put the first 7 in quotations which added two bytes to your 78 byte version. Nov 27 '16 at 19:11 • You can save 3 bytes or so by doing for($n=1;;$n++)echo$a[]=strpos($n,"7")>-1||$n%7==0?array_shift($a)." ":"$n ";. I'm not sure if you can replace $n%7==0 with !$n%7 but it's worth a try. Nov 27 '16 at 20:08
• Keep going -6 : $n=0 is useless, "7" can be 7. Nov 28 '16 at 10:43 • why shift? for(;;)echo$a[]=strpos(++$n,55)<-1&&$n%7?"$n ":$a[++$b-1]; (58 byte). ++$b-1 because $a[null] === null Nov 28 '16 at 14:13 # Julia, 62 bytes x=[];j=0;for i=1:7^7;x=[x;i%7<1||('7' in "$i")?x[j+=1]:i]end;x

Nothing fancy. Uses that the sequence within the gaps is the sequence itself. Makes excessive array copies to save some bytes.

# Dyalog APL, 39 bytes

{(⍵⍴⍨⍴i)@(i←⍸('7'∊¨⍕¨⍵)∨0=7|⍵)⊢⍵}⍣≡⍳7*7

⍳7*7 is 1 2 3...77

{ }⍣≡ is the fixed point operator - apply a function repeatedly until the result stabilises

A@I⊢B amend operator - replace the elements at indices I in B with A

0=7|⍵ bitmask for where the argument is divisible by 7

'7'∊¨⍕¨⍵ bitmask for where the decimal formatting of the argument contains a 7

∨ or

⍸ at what indices is either of the above bitmasks true?

i← assign to i

⍵⍴⍨⍴i reshape the argument to the number of elements in i

• This is nice. Does it help if you multiply ⍳7*7 with the bitmask and take the fixpoint of amending the zeros in the sequence? Nov 28 '16 at 20:59

# Perl 6,  74 57 54  53 bytes

sub u{my@u;(1..*).map: {if $_%%7||.comb('7') {@u||=u;@u.shift} else {$_}}}

sub u{(1..*).map: {$_%%7||.comb('7')??(@||=u).shift!!$_}}

sub u{map {$_%%7||.comb('7')??(@||=u).shift!!$_},1..*}

sub u{map {$_%%7||.comb(~7)??(@||=u).shift!!$_},1..*}

Try it

## Expanded:

sub u{
map             # for each element transform using:

{ # bare block lambda with implicit parameter ｢$_｣$_ %% 7     # if it is divisible by 7
||          # or
.comb(~7)   # contains the number 7 (implicit method call on ｢$_｣) ?? # then ( @ ||= u ) # store a new instance of the Seq into an unnamed state array if it is empty # ( it is only empty the first time it is seen in this Seq instance ) .shift # pull one off of the front !! # else$_          # return the value
},

1 .. *          # infinite range starting at one ( elements to be mapped over )
}

## Test:

9\*"~"g9+1:+1::p00:<+3$_^#g01$$<v"~":/"~"p9g00%"~"::+1+g9\*"~"+g :#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>%00g1+9p"~"/00g2+9p::7%!10>>p#0  The second version only works with interpreters that have 32-bit memory cells, and thus isn't strictly standard Befunge, but that lets us store larger values in memory without having to split them across cells. "O":0>\#09#:p#-:#1_v<0.< %7::p9g00:+1g9:p00:<+1_^#g01$$<v01! :#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>p#0  In both cases the program runs indefinitely, but the first version will overflow around the 2 million mark, while the second version should get up to the max int value (around 2 billion). You can Try it online, but you'll need to kill the process to prevent it from trying to run forever. ## Clojure, 130 bytes #(let[R(range(inc %))](rest((reduce(fn[[r s]i](if(or(=(mod i 7)0)((set(str i))\7))[(assoc r i(r s))(inc s)][r s]))[(vec R)0]R)0)))  Basic reduce, keeping track of contents of the result vector and how many values have been skipped. The last 0 takes first element of the reduced [r s], rest drops first element of the 0-indexed result. ## Perl6, 41 bytes put {($_=++$)%%7|m/7/??@_[$++]!!$_}…1e6  # JavaScript, 64 bytes for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);;)alert(f(f))  output=[];index=0;for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);index<100;)output[index++]=f(f);console.log(output.join(',')) • p.s. to compare with the other few (console.log) JavaScript answers, it's 70 bytes – l4m2 May 26 '18 at 13:10 # Japt, 25 bytes []L³õ@pX%7«/7/tX ?X:UgV°  Generates first 1,000,000 entries of the sequence and prints them. One million is the shortest number over 7**7 == 823543 in Japt. The trailing newline is significant, as it activates the implicit assignment to U. Generating the list only takes around a second, but outputting the entire array will likely make your browser hang. ### Unpacked & How it works []L³õX{UpX%7&&!/7/tX ?X:UgV++ [] Assign empty array to U L³õX{ Map over 1 to 1,000,000 inclusive... X%7&& If X is not divisible by 7 and !/7/tX X does not have a digit 7 ?X:UgV++ then X, otherwise the next element already in U Up Push it to the end of U Implicit print U  Uses the property that the recursive definition can be resolved by looking at the already generated sequence. # Tcl, 72 bytes while 1 {puts [expr {[incr i]%7&&7ni[split$i ""]?\$i:([incr s]-1)%6+1}]}

Try it online!

• nice! much shorter than mine…
– hdrz
May 26 '18 at 9:36
• This writes "...33 34 7 36 8 38..." instead of "...33 34 1 36 8 38..." May 28 '18 at 13:27
• @mschauer: Ok, I will fix it when I have time... Jun 5 '18 at 14:38
• @hdrz I tried your solution and it has the same issue mschauer told about! Jun 5 '18 at 14:39
• @mschauer: fixed. 2 days ago

# 05AB1E, 17 bytes

[N>ÐÑª˜7åi¯¾è¼}=ˆ

Port of @TheBikingViking's Pyth answer, so make sure to upvote him as well!
Also outputs the infinite sequence, each number on a separated line.

Try it online.

Explanation:

[               # Start an infinite loop:
N>             #  Push the 0-based loop-index + 1
Ð            #  Triplicate this now 1-based index
Ñ           #  Pop one and push a list of its divisors
ª          #  Implicitly convert another number to a list of digits, and
#  append this list of divisors to it
˜         #  Flatten it
7åi      #  Pop and if it contains a 7
#  (so either the digits contained a 7 or the divisors):
¯     #   Push the global array
¾è   #   Index the counter variable into it
¼  #   And increase the counter variable by 1 afterwards
}      #  Close the if-statement
=     #  Print the top number (without popping)
ˆ    #  Pop and add it to the global array

If we only want to output the first $$\7^7\$$ results instead of printing indefinitely, the [N> could be 7mEN instead.


text:
Make a font “imperfect”

I want to simulate text from a early 20th century book. I chose the font librecaslon, as it seems to match quite well, and Latex renders it beautiful - too beautiful for my taste. Rather, I'd like to have it more "imperfect", like the following example:

As you can see, the letters are not clear-cut but somewhat frayed as per the (then more than now) imperfect printing process (image is from a printed and scanned book).

Is something like this possible (without changing the font)? Or are there alternatives (e.g. postprocessing the produced pdf file somehow)?

I saw this similar question: Simulate printing imperfections and defects with TeX? However, suggestions were to use another font, or add ink blots to the document, which is subtly different from my usecase.

Edit: Added sample output for my Latex-made text. Lower row is with anti-aliasing disabled in Adober Reader. This comes a bit closer to what I want to have in the end, but would be impractical to produce (using Reader).

• Are you sure the imperfection is present in the book itself, and not from the scan of the book? :-) Can you upload a higher-resolution image of the kind of imperfection you're seeking? E.g. simply making the letters more pixelated, as in your “anti-aliasing disabled” example and as in David's answer, might be enough if that's the kind of imperfection you want… but I have a feeling that the defects in actual books were of a different nature (as their type was not made of pixels!) – ShreevatsaR Aug 19 '17 at 15:04
• Thanks for your comment, you're actually right - I had a look into another scan of the document (archive.org/stream/steerageshamimmi00heat#page/n5/mode/2up) which is of higher quality, and does not show the same amount of imperfection. – Wang Tang Aug 19 '17 at 15:21

The image shows the document

\documentclass{article}

\usepackage{librecaslon}
\usepackage[T1]{fontenc}

\begin{document}
We lay at Queenstown. Something was wrong with.
\end{document}

typeset via:

latex file
dvips -X 100 -Y 100 -V file
ps2pdf file

then

latex file
dvips -X 200 -Y 200 -V file
ps2pdf file

then

latex file
dvips -X 300 -Y 300 -V file
ps2pdf file

then

pdflatex file

• Hadn't thought of toying with the resolution, as most I do in Latex is using my editor with pre-set compile commands. Good idea, I'll work with that! – Wang Tang Aug 19 '17 at 15:22
• @WangTang don't think I've used those dvips options since last century, but they perhaps come in useful here:-) – David Carlisle Aug 19 '17 at 15:34
• toying with the resolution will certainly result in imperfections, but not the same kind that would result from the impression of worn type on paper. – barbara beeton Aug 19 '17 at 16:10
• @barbarabeeton I know but the OP had already said that turning off anti-aliasing was good enough so ..... – David Carlisle Aug 19 '17 at 16:20

A note on the nature of these “imperfections”: we find a lot of pre-1923 books available online in scanned versions (such as on Google Books), read a lot of them on screen, get used to their appearance, and seek a similar appearance, or even begin to think that this is how the actual books looked! But in fact, many of the “imperfections” are actually from the scanning process (and of decaying books at that), and not indicative of the actual printing technology of the time.

The books of the time weren't really terrible: people didn't, by and large, have lower standards. Although you cannot go back in time and see how these books looked when new, at least you can eliminate the artifacts of the scanning process, by visiting a library and picking up an old volume, rather than looking at one on screen.

Consider the example image in the question:

and compare it to the equivalent region from a slightly (just barely) higher-resolution scan from here:

You'll notice that some of the imperfections in the former image are not present in the latter. Here's an animation that may help compare (focus on one of the letters):

The lowercase L in "lay" and the uppercase Q in "Queenstown" are good examples.

Potential sources of imperfection leading up the first image:

Printing

These old books would invariably have been produced with hot metal typesetting (the pieces of type were made of lead), either set with a typecasting machine (Linotype/Monotype for example), or set by hand.

One thing that could go wrong is that when the ink hits the page, it could spread a little. Or the letter positions may be off by a bit: notably, slightly higher or lower than the baseline. You could reproduce this by randomizing the positions in the "set char" and "put" instructions in the DVI file: slightly twiddle the y and x offsets. (But probably never decrease the x-offsets within an individual word, as the type sorts for letters couldn't get any closer than the minimum?)

Time

As the book gets older with time, the page yellows, so the contrast between ink and paper decreases. The page gets worn with usage, along with the print on it, unevenly and there may be specks of dust. The answer at the linked question has some ways of reproducing this (exaggerated there for effect; you probably don't want so much).

Scanning

After such a book gets onto a scanner is where most of the “imperfections” creep in: the image of the book (closer to the second one) is taken at some passable resolution. Then some threshold of darkness/contrast is chosen as demarcating the ink from the page, thus making it black-and-white. This is where most of the errors come in: on top of already limited resolution, the wear-and-tear on the page, the dust and speckles, etc., lead to decisions that don't exactly match the reality of what's ink and what's not. That explains most of the artifacts you see in the example.

Part of this you can reproduce by processing the DVI using low-resolution bitmap fonts, as the fonts are forced to make similar decisions about where to put their pixels.

• Thank you very much for the research and insight, and for clearing up my misconceptions! Very interesting to read, and thanks as well for the suggestions for changing the look. – Wang Tang Aug 19 '17 at 22:45


text:
# Log/Exponential problem

• Apr 18th 2010, 08:24 PM
desiderius1
Log/Exponential problem
$
\frac{e^x-e^{-x}}{2}=10
$

$
x = ln (10 + \sqrt{101} )
$

What I'm doing (More than likely wrong)

$
\frac{e^x - e}{2^x} = 10

$

$
e^x-e=10(2^x)
$

$
e^x-e=20^x
$
• Apr 18th 2010, 08:33 PM
sa-ri-ga-ma
According to the answer, the given problem is wrong.
The equation should be equated to 10 rather than 7.
• Apr 18th 2010, 08:37 PM
Failure
Quote:

Originally Posted by desiderius1
$
\frac{e^x-{\color{blue}e^{-x}}}{{\color{red}2}}=7
$

$
x = ln (10 + \sqrt{101} )
$

This answer is wrong, assuming that you have managed to write down the correct equation that you were asked to solve.

Quote:

What I'm doing (More than likely wrong)

$
\frac{e^x - {\color{blue}e}}{{\color{red}2^x}} = 7
$

The above equation is very different from the one that you were given.

Quote:

$
e^x-e=7(2^x)
$

$
e^x-e=14^x
$

That last step is not valid. More generally, you have that in general $a\cdot b^n\neq (a\cdot b)^n$.
• Apr 18th 2010, 08:58 PM
desiderius1
Sorry, there are two identical problems, one equating to 10 and the other 7, I misread while typing.

The problem is:
$
\frac{e^x-e^{-x}}{2}=10
$
• Apr 19th 2010, 05:03 AM
Failure
Quote:

Originally Posted by desiderius1
Sorry, there are two identical problems, one equating to 10 and the other 7, I misread while typing.

The problem is:
$
\frac{e^x-e^{-x}}{2}=10
$

The easy way to solve this equation would be to recognize that the left side really is $\sinh(x)$, and that the solution is simply $x=\arsinh(10)$.

Or else you can first multiply the equation by $2e^x$ to get a quadratic equation for $e^x$:

$\frac{e^x-e^{-x}}{2}=10 \qquad | \cdot 2e^x$

$\left(e^x\right)^2-1=20 e^x \qquad | -20e^x$

$\left(e^x\right)^2-20e^x-1=0$
Thus, we get

$\left(e^x\right)_{1,2} = \frac{-(-20)\pm \sqrt{(-20)^2-4\cdot 1\cdot (-1)}}{2\cdot 1}=10\pm \sqrt{101}$
But only the $+$ case is possible, thus we have

$e^x=10+\sqrt{101}\qquad | \ln$

$x=\ln(10+\sqrt{101})$


text:
# Integration Center of Mass Problem -Really frustrated

1. Apr 15, 2008

### bcjochim07

Integration Center of Mass Problem --Really frustrated

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

An 800 g steel plate has the shape of the isosceles triangle shown in the figure. What are the x and y coordinates of the center of mass?

2. Relevant equations

3. The attempt at a solution

I am getting really frustrated with this one because I can't seem to relate dm to dx. I know that while dx is constant, dm is increasing because the height of the slices you cut the triangle into is increasing. Could someone please give me a push in the right direction? I am having trouble applying integration to center of mass problems.

2. Apr 15, 2008

### stingray78

The center of mass would be the baricenter of the triangle. If you wanna do it in an analytic way; it's also easy. Just use the superficial density of the plate. density=mass/Area of triangle. Then the center of mass will be: Integral (x*dm)/Total Mass. But dm=density*da. then the center of mass is: Integral (density*x*da)/Total mass
Where density is constant Total mass is knownk and u just need to integrate in the triangle area.

Cheers!!!

3. Apr 15, 2008

### bcjochim07

I followed what you were saying, but I still can't integrate it because I don't have dx in my integral, so I'm stilll confused.

My book says to divide the triangle into vertical strips with width dx, then relate the mass dm of a strip at position x to the values of x and dx.

4. Apr 15, 2008

### stingray78

Uhh!! you have da in your integral, you need elevated calculus to make that kind of integrals. Anyway to make it more simple Area=base*height/2 where the base is the x axis and the height can be a function of x, F(x)= straight line1+straight line2. then u can write ir as: Integral(density*x*F(x)*dx)/total mass where dx goes through all the base of the triangle and F(x) is the height function of the trinangle. (Twho straight lines, u have to split the integral in two)

5. Apr 15, 2008

### bcjochim07

I'm not sure I'm getting it yet:

Ok so dm= (kg/m^2)*F(x)*dx

kg/m^2= 26.67 kg/m^2
F(x)= (1/3)x

Cm= (1/M) * Integral xdm
Cm= (1/.8kg)* Integral x*(26.67)(1/3)*x dx evaluated from 0 to .3 m
= I got x= .1 m but the answer for the x coordinate is .2m. What am I doing wrong?

and then do I go about finding the y coordinate in the same way?

6. Apr 15, 2008

### kamerling

dm = (length of the strip) * dx, now you just need to find the length of the vertical strip as a function of x (use similar triangles)

7. Apr 15, 2008

### bcjochim07

How can dm= length of the strip * dx? That doesn't yield units of kg. I found the function for the height to be y=(1/3)x

8. Apr 16, 2008

### corochena

First we assume that the body is uniform, so its mass is proportional to its area in any section. So I am going to use area (A) instead of mass for my calculations.

dA = height of vertical strip . dx

height of vertical strip = 2/3 . x

Then you use the formula for center of mass:

Integral of x . dm = Total Mass of Triangle . Xo

Xo is the coordinate of the center of mass

as I told before you can use area instead of mass (assuming that the body is homogeneus)

so...

Integral of x . 2/3 . x . dx = Total Area of Triangle . Xo

You solve this equation and get the answer Xo = 20 cm

9. Apr 16, 2008

### kamerling

sorry I thought about integrating over the area.

10. Apr 16, 2008

### corochena

No, it does not. OK, in order to yield units of kg we have to to this:

Total Mass = density of area . Total Area

density of area = M / A

so dm = M / A . dA

then dm = M / A . lenght of strip . dx ... and you have Kg

11. Apr 17, 2008

### stingray78

Ok with the drawing it's easier for me to explain. You did everything right, you just forgot to take into consideration the other half of the triangle. Which means you have to multiplicate your result by two!!! (Remember integrals are really areas so its valid) and the you have your right x coordinate. U can rapeat it in the y coordinate but it's kind of obvious that the y coordiante for the center ofa mass is going to be cero.

Cheers Hope I helped!!!

12. Apr 17, 2008

### stingray78

Hey if I was helpful u should check out my homepage. It's really cool. I put a lot of effort!!!
Cheers again mate