text:
# Morphing tree drawings in a small 3D grid

We study crossing-free grid morphs for planar tree drawings using 3D. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speed. A crossing-free morph is known between two drawings of an n-vertex planar graph G with 𝒪(n) morphing steps and sometimes Ω(n) steps is necessary even when G is a path [Alamdari et al., 2017], while using 3D can reduce the number of steps to 𝒪(log n) for an n-vertex tree [Arseneva et al., 2019]. However, these morphs do not bound one practical parameter, the resolution. Recently [Barrera-Cruz et al., 2019] a 2D crossing-free morph was devised between two planar drawings of an n-vertex tree in 𝒪(n) steps with polynomial resolution, that is, all intermediate drawings are grid drawings on a grid of polynomial size. Can the number of steps in this setting be reduced substantially by using 3D? We answer this question in affirmative and present a 3D non-crossing morph between two planar grid drawings of an n-vertex tree in 𝒪(√(n)log n) morphing steps. Each intermediate drawing lies in a 3D grid of polynomial volume.

## Authors

• 8 publications
• 1 publication
• 1 publication
• ### Pole Dancing: 3D Morphs for Tree Drawings

We study the question whether a crossing-free 3D morph between two strai...
08/31/2018 ∙ by Elena Arseneva, et al. ∙ 0

• ### How to Morph a Tree on a Small Grid

In this paper we study planar morphs between straight-line planar grid d...
09/16/2019 ∙ by Fidel Barrera-Cruz, et al. ∙ 0

• ### Upward Planar Morphs

We prove that, given two topologically-equivalent upward planar straight...
08/31/2018 ∙ by Giordano Da Lozzo, et al. ∙ 0

• ### Crossing Numbers of Beyond-Planar Graphs Revisited

Graph drawing beyond planarity focuses on drawings of high visual qualit...
05/26/2021 ∙ by Nathan van Beusekom, et al. ∙ 0

• ### 4-connected planar graphs are in B_3-EPG

We show that every 4-connected planar graph has a B_3-EPG representation...
10/12/2017 ∙ by Therese Biedl, et al. ∙ 0

• ### Extending Nearly Complete 1-Planar Drawings in Polynomial Time

The problem of extending partial geometric graph representations such as...
07/08/2020 ∙ by Eduard Eiben, et al. ∙ 0

• ### Proportional Representation under Single-Crossing Preferences Revisited

We study the complexity of determining a winning committee under the Cha...
10/16/2020 ∙ by Andrei Constantinescu, et al. ∙ 0

##### This week in AI

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

## 1 Introduction

Given an -vertex graph , a morph between two drawings (i.e., embeddings in ) of

is a continuous transformation from one drawing to the other through a family of intermediate drawings. One is interested in well-behaved morphs, i.e., those that preserve essential properties of the drawing at any moment. Usually this property is that the drawing is

crossing-free; such morphs are called crossing-free morphs. This concept finds applications in multiple domains: animation, modeling, and computer graphics, etc. [13, 14, 15, 12]. A drawing of is a straight-line drawing if it maps each vertex of to a point in and each edge of to the line segment whose endpoints correspond to the endpoints of this edge. In this work, we focus on the case of drawings in the Euclidean plane () and drawings (); a non-crossing drawing of a graph in is called planar.

The study of crossing-free graph morphs began in 1944 from a non-constructive proof that such morphs for maximal planar graphs exist between two topologically equivalent drawings [11]; a matching algorithmic result appeared in 1983 [21]. Recently crossing-free morphs of straight-line drawings are considered, where the vertex trajectories are simple. Of particular interest is linear morph transforming one straight-line drawing of a graph to another such drawing through a sequence of straight-line drawings. Morph is called a morphing step, or simply a step, for brevity. In each step of a linear morph each vertex of moves along a straight-line segment at a constant speed. Results [2, 4, 7, 3] led up to a seminal paper by Alamdari et al. [1] showing that for any two topologically equivalent planar drawings of a graph , there is a linear morph that transforms one drawing to the other in steps. This bound is asymptotically optimal in the worst case even when the graph is a path. A natural further question is how the situation changes when we involve the third dimension. For general 3D graph drawings the problem seems challenging: it is tightly connected to unknot recognition problem, that is in  [16, 18], and its containment in P is widely open. If the given graph is a tree, the worst-case tight bound of steps holds for crossing-free linear morph [5] (and the lower-bound example is again a path). If both the initial and the final drawing are planar, then steps suffice [5].

Both algorithmic results [1, 5] have a drawback crucial from the practical point of view. Their intermediate steps use infinitesimal or very small distances, as compared to distances in the input drawings. This may blow up the space requirements and affect the aesthetical aspect. This raises a demand for morphing algorithms that operate on a small grid, i.e., of size polynomial in the size of the graph and parameters of the input drawings. All the intermediate drawings are then restricted to be grid drawings, where vertices map to nodes of the grid. Two crucial parameters of a straight-line grid drawing are: the area (or volume for the 3D case) of the required grid, and the resolution, that is the ratio between the maximum edge length and the minimum vertex-edge distance. If the grid area (or volume) is polynomially bounded, then so is the resolution [6].

Barrera-Cruz et al. [8] gave an algorithm to morph between two straight-line planar Schnyder drawings of a triangulated graph in steps; all the intermediate drawings of this morph lie in a grid of size . Very recently Barrera-Cruz et al. [6] gave an algorithm that linearly morphs between two planar straight-line grid drawings and of an -vertex rooted tree in steps while each intermediate drawing is also a planar straight-line drawing in a bounded grid. In particular, the maximum grid length and width is respectively and , where , and , and are the length and the height of the drawing respectively. Note that is .

Here we study morphing one straight-line grid drawing of a tree to another such drawing in sublinear number of steps using 3D for intermediate steps. Effectively we ask the same question as in [5], but now with additional restriction for all drawings throughout the algorithm to lie in a small grid. We give two algorithms that require steps and steps, respectively. All the intermediate drawings require a grid of length , width and height , where is the diameter of the drawing . At the expense of using an extra dimension we significantly decrease the number of morphing steps, and also the required (horizontal) area, as compared to the planar result [6]. Our algorithm is the first one to morph between planar drawings of a tree in steps on a grid of polynomial volume.

## 2 Preliminaries and Definitions

#### Tree drawings.

For a tree , let be its root, and be the subtree of rooted at a vertex . Let and be respectively the set of vertices end edges of , and let denote the number of vertices in .

In a straight-line drawing of , each vertex is mapped to a point in and each edge is mapped a straight-line segment connecting its end-points. A - (respectively, a -) grid drawing of is a straight-line drawing where each vertex is mapped to a point with integer coordinates in (respectively, ).A drawing of is said to be crossing-free if images of no two edges intersect except, possibly, at common end-points. A crossing-free -grid drawing is called a planar grid drawing. For a crossing-free drawing , let denote the open disc of radius in X0Y plane centered at the image of . Unless stated otherwise, by the projection, denoted by , we mean the vertical projection to plane. Let , and respectively denote the length, width and height of , i.e., the maximum absolute difference between the -,- and -coordinates of vertices in . Let denote the diameter of , defined as the ceiling of the maximum pairwise distance between its vertices. Given a vertex and an edge of the tree , denotes the distance between and . Similarly, is the distance between and .

###### Observation 1

For , , where

. Thus to estimate the space required by

, it is enough to estimate .

###### Lemma 1
1. [6] For any vertex and edge not incident to in a planar grid drawing of , .

2. For each , let be equal to where is an integral constant. The distance between any two distinct vertices in is at least .

###### Proof
1. Let fix vertex and . Denote by the height in the triangle from the vertex , is the distance from to the line that contains the edge by its definition. Let be the area of triangle .

The .

On the other hand from the Pick’s theorem we know, that the area of the triangle with vertices lying in the lattice points of the grid is at least .

Then .

2. For any pair of distinct vertices , either or is at least since all vertices has integer coordinates in . This implies that, for each pair of distinct vertices , either or is at least since each coordinate of each vertex in is multiplied by to obtain . ∎

#### Path decomposition

of a tree is a decomposition of its edges into a set of disjoint paths as follows. Choose a path in and store it in . Removal of this path may disconnected the tree; recurse on the remaining connected components. In the end, contains disjoint paths whose union is . The way of choosing path may differ. The depth of a vertex in , denoted by , is defined as the length of the path from to . Head of the path , denotes as , is the vertex with the minimum depth in tree . Let internal vertices of the path be all vertices except . Any path decomposition of induces a linear order of the paths: path succeeds , i.e., , if and only if is deleted before during the construction of . Note that the subtree of each internal vertex of a path is a subset of the union of the paths that precede .

In the long-path decomposition [9], the path chosen in every iteration is the longest root-to-leaf path (ties are broken arbitrarily). Let be the ordered set of paths of a long-path decomposition of . For , .

Heavy-rooted-pathwidth decomposition [5]. The Strahler number or Horton-Strahler number of a tree is a parameter which was introduced by Horton and Strahler [17, 19, 20]. The same parameter was recently rediscovered by Biedl [10] with the name of rooted pathwidth when addressing the problem of computing upward tree drawings with optimal width.

The rooted pathwidth of a tree , which we denote by , is defined as follows. If , then . Otherwise, let be the maximum rooted pathwidth of any subtree rooted at a child of . Then if exactly one subtree rooted at a child of has rooted pathwidth equal to , and if more than one subtree rooted at a child of has rooted pathwidth equal to ; see Figure (a)a. Clearly is an integer number.

The heavy-rooted-pathwidth decomposition of a tree is defined as follows refer to Figure (b)b. For each non-leaf vertex of , let be the child of in such that is maximum (ties are broken arbitrarily). Then is a heavy edge; further, each child of is a light child of , and the edge is a light edge. Connected components of heavy edges form set of paths , called heavy paths, which may have many incident light edges. The path tree of is a tree whose vertices correspond to heavy paths in ; see Fig. (c)c. The parent of a heavy path in the path tree is the heavy path that contains the parent of the vertex with minimum depth in . The root of the path tree is the heavy path containing .

For convenience, we will also consider the light edge immediately above a heavy path to be a part of the path. When it is clear from the context we will refer to simply as .

We denote by the root of the path tree of ; let be the ordered sequence of the vertices of , where . For , we let be the light children of in any order. Let be the sequence of the light children of ordered so that: (i) any light child of a vertex precedes any light child of a vertex , if ; and (ii) the light child of a vertex precedes the light child of . For a vertex , we denote by its parent; note that . It is known [10] that the height of the path tree of an -vertex tree is at most .

Fig. (a)a shows the heavy-rooted-pathwidth decomposition of our running example where heavy paths are shown in different colors.

Canonical 3D drawing of a tree , introduced in [5], is the crossing-free straight-line 3D drawing of that maps each vertex of to its canonical position defined from heavy-rooted pathwidth decomposition.

The canonical drawing of a tree , denoted by , is defined as follows:

• First, we set for the root of .

• Second, for each , we set , where is the -coordinate of .

• Third, for each and for each , we determine as follows. If , then we set , where is the -coordinate of ; otherwise, we set , where is the -coordinate of .

• Finally, in order to determine the canonical positions of the vertices in , for each and each , we recursively construct the canonical 3D drawing of

, and translate all the vertices by the same vector so that

is sent to .

We use the fact that lies in the positive quarter-plane, inside a bounding box of height and width such that the left-bottom point of the box represents the image of the root and is mapped to the origin. Since tree never changes throughout our algorithm, we refer as .

For any vertex of , the relative canonical drawing of is the drawing of obtained by cropping and translating the obtained drawing of so that is mapped to the origin.

#### Morph:

Let and be two planar straight-line drawings of . Then a morph is a sequence of 3D straight-line drawings of such that , and is a linear morph, for each .

## 3 Tools for morphing algorithms

#### Stretching with a constant S1.

Let the drawing be lying in the plane. During stretching morph each coordinate of each vertex in is multiplied by a common positive integer constant . Thereby, it is a linear morph that ”stretches” the vertices apart.

###### Lemma 2

Stretching morph is crossing-free.

###### Proof

For each the drawing , where the image of any vertex of is is the same drawing scaled by . Since the original drawing was crossing-free, so is the drawing . ∎

###### Lemma 3
1. For any pair of vertices disks and do not cross in plane.

2. For a vertex disk does not enclose any other vertices or any part of non-incident to edges in .

3. For every vertex and every edge in there is lattice point such that and .

###### Proof
1. As disk contains no other vertices , then does not contain other vertices too. The — disk with half that radius — does not intersect with any for .

2. Due to Lemma 1 no non-incident edges intersected the disk of radius around in . That means that in , where all distances are multiplied by no non-incident edges intersect the disk of radius around . Other vertices do not lie in as .

3. Every edge from has been stretched by . If and , then and . The integral point and is .∎

#### Mapping around a pole

Let the pole through be vertical line in through point . Let be vertical half-planes containing the pole through a point with integer coordinates. Suppose and contain infinitely many points with integer coordinates. Mapping around the pole is a morphing step to obtain a drawing which lies in from which lies in . Each vertex moves along a horizontal vector between and . The direction of this vector is common for all vertices of and is defined by and . Let us fix a horizontal plane which passing through the point where is an integer. Let be points that lie on and , respectively; such that and be the minimum non-zero distances from the to the integer points lying in and . The vector of mapping is defined as . Mapping is a unidirectional morph since all vertices of move along the vectors parallel to the vector of mapping till they reach the half-plane . See Fig. (c)c.

###### Proposition 1

[1] Let be a unidirectional morph between two planar straight-line drawings and of . Let be a vertex of , let be an edge of and, for any drawing of , let be the line through the edge oriented from to . Suppose that is to the left of both in and in . Then is to the left of throughout .

###### Lemma 4

For each the drawing lies in one half-plane. Moreover, for each this half-plane has the vertical borderline , which is a borderline of half-planes and .

###### Proof

Recall that mapping is a unidirectional morph that transforms drawings between two half-planes that share a common pole. Note that the length of the vector of movement of any vertex in is proportional to its distance to the pole. Let denote the point on the pole with the same coordinate as , once again for each we denote by the drawing, where the image of any vertex of is . For any two vertices from with the same height that are being mapped to the half-plane , from proportionality of distances, we can cay that at any moment for the intermediate drawing we have . If the angle between the edge and the plane is the same for all points at some height, then it is the same for all vertices in , because points with the same -coordinates had the same vector of movement.

###### Lemma 5

Mapping is a crossing-free morph.

###### Proof

From Lemma 4 we know that at any moment the whole lies within one half-plane and as the mapping is a unidirectional morph, one can get that drawing is a result of projection from half-plane to intermediate half-plane . We restricted angle between and not to be equal to and . With this resctiction drawing is the rotated drawing stretched in horizontal direction by some constant. Then is crossing-free as was crossing-free.

The rotation is a mapping when are half-planes of planes parallel to respectively and thus . Vector of mapping for rotation is lying in the set, see Fig. 10:

 {(√22,√22,0),(√22,−√22,0),(−√22,√22,0),(−√22,−√22,0)}

We denote by a half-plane parallel to with vertical border-line going through vertex in X-positive direction from that pole. are defined analogously.

A horizontal pole is a line parallel to axis. Horizontal pole through the point, mapping around horizontal pole and horizontal rotation are defined analogously. Corresponding set of possible directions of movement for horizontal rotation are:

 {(0,√22,√22),(0,√22,−√22),(0,−√22,√22),(0,−√22,−√22)}

#### Shrinking lifted subtrees.

Let be a vertex of such that the image of subtree in is , i.e., it lies in . Let be the ordered set of the children of which are ordered according to their -coordinates in . For a tuple , where , let us consider the ordered set such that the members of are ordered according to their -coordinates in . Let us consider the new subtree which is obtained by deleting the vertices in and their subtrees. Consider the canonical drawing of with respect to . For each satisfying , lies inside a box of height and width on the plane such that the down-left corner of the box coincides with since they are in a canonical position with respect to their roots. We define the shrink subtree procedure on as follows. We move each vertex from to . Vertices of the subtree rooted at also move along the same vector. Let us denote the shrinked subtree by . The height of the shrinked subtree is equal to the number of vertices in .

###### Observation 2

The height of the shrinked subtree is equal to the number of vertices in .

###### Proof

Note that the subtree rooted at has a canonical drawing in . This implies that for the subtree rooted at also has a canonical drawing with respect to in . Each lies inside a box of height . Also, note that the z-coordinate of is equal to . This implies that in , lies inside a box of height and the down-left corner of the box coincide with Also note that .

###### Lemma 6

Shrinking is a crossing-free morph.

###### Proof

Note that the and coordinates of each vertex in and are the same and -coordinate can only decrease, shrinking is obviously a unidirectional morph in vertical plane which passes through . Also, note that through out the morphing process all vertices in maintain the relative orders among themselves since they move along parallel vectors. Also note that shrinking satisfies the conditions of Proposition 1. This implies that shrinking is a crossing free morph. ∎

#### Turning in horizontal plane.

Let be the canonical drawing of a subtree on the horizontal plane , i.e. relative canonical drawing rotated around horizontal pole through in any direction to lie in or half-plane. We discuss the case when lies in , the other case is similar. Let be the drawings obtained from by rotating the horizontal plane around the point by the angles respectively. Using a lemma from [6, Lemma pinwheel], we show the following.

###### Lemma 7

(Pinwheel) [6] Let and be two canonical drawings of a rooted ordered tree , where is at the same point in and . If and are (i) upward and leftward, or (ii) leftward and downward, or (iii) downward and rightward, or (iv) rightward and upward, respectively, then the morph is planar and lies in the interior of the right, top, left, or bottom half of the -box centered at , respectively. See Fig. 11.

###### Lemma 8

The drawing can be obtained from the drawing in one morphing step, , where by we mean .

###### Proof

Proof of this fact is the same as the proof of the Lemma 7 of [6].∎

## 4 Morphing through lifting paths

Let be an -vertex tree with vertices and be a path decomposition of into paths. In this section, we describe an algorithm that morphs a plane drawing in plane of tree to the canonical 3D drawing of in steps. It lifts the paths of one by one applying procedure Lift. Note that the final positions for the vertices in are defined through heavy-rooted-pathwidth decomposition, and do not depend on . Also, a morph from to can be obtained by playing the morph from to backwards. At all times during the algorithm, the following invariant holds: a path is lifted only after all the children of the internal vertices of are lifted. After the execution of Lift, path moves to its canonical position with respect to . See Fig. 12-17.
Step 0: Preprocessing. This step is a single stretching morph with , see Section 3, stretching is a crossing-free morph.

### 4.1 Procedure Lift(P)

Let be the first path in that has not been processed yet and be the current drawing of . We lift the path . For any vertex let lifted subtree be the portion of subtree that has been lifted after execution of Lift for some . The following invariants hold after every iteration of Lift procedure.

• the drawing of in is the canonical drawing of with respect to for any ,

• vertices of paths lie within X0Y plane.

We prove that these conditions hold after lifting . Let the processing vertices be the internal vertices of along with the vertices of their lifted subtrees.

###### Lemma 9

The subtrees of all internal vertices in are already lifted.

###### Proof

All the paths that precede in are exactly the paths that are left after deleting from the forest of subtrees of (see paragraph Path decomposition in Section 2). From this fact it follows that all internal vertices of have become roots of some trees after deleting the edges of and edges of that trees were processed in Lift procedures for some . ∎

###### Lemma 10

The maximum height of vertices in the drawing is strictly less than .

###### Proof

As all vertices of the processed paths are part of lifted subtrees of their head vertices, and by (I) have height as in canonical drawing, their height is strictly less than the number of vertices in a corresponding subtree, which does not exceed number of vertices in . ∎

###### Lemma 11

For any vertex and its lifted subtree . The maximum horizontal distance in the lifted subtree of , i.e. the difference between -coordinates between any pair of vertices in in , does not exceed .

###### Proof

Note that the drawing of in is the canonical drawing of with respect to . This implies that the maximum horizontal distance between any vertex in and in is at most . ∎

Step 1: Shrink. For every internal vertex of the path its lifted subtree morphs into shrinked lifted subtree, see Sec. 3. All subtrees are shrinked simultaneously in one morphing step.

###### Lemma 12

Step 1 is crossing-free.

###### Proof

For each lifted subtree this is a shrinking step and by Lemma 6 it is crossing-free.

All lifted subtrees were not overlapping in projection to X0Y plane due to Condition (I) and Lemmas 3 and 11 in the drawing . As all vectors of movement are vertical, projections of lifted subtrees can not overlap during this morphing step and can not cross with each other.

In shrinked drawing every vertex of except has strictly positive -coordinate which means that remains strictly above X0Y plane and can not cross with the part of that is still lying in X0Y. Internal vertices of do not change their positions during this morph. ∎

Step 2: Move others. This step consists of two morphs .

For , if projection overlaps with , we rotate twice the drawing of around the vertical pole through . Since every lifted subtree lies in , after this step all lifted subtrees lie in or .

###### Lemma 13

Step 2 is crossing-free.

###### Proof

Two different lifted subtrees cannot cross as due to Lemma 11: and due to Lemma 3 disks around vertices with radius do not cross with each other.

No edges within rotating lifted subtree can intersect as rotating is a mapping and mapping is a crossing-free morph (Lemma 5). Due to condition (II), all edges that do not lie in lifted subtrees are lying in X0Y plane. No lifted subtree can intersect with any edges in X0Y by condition (I): is the canonical drawing with respect to and lies strictly above X0Y plane except for the point . Rotation morph does not change -coordinate of points during the movement, so throughout the morph drawing of lies above X0Y plane, vertex does not move during the rotation as it lies on the pole.

No vertices move in X0Y plane during Step 2 and no crossing can happen within the plane X0Y. ∎

Step 3: Go up: This is one morphing step that moves each internal vertex of path vertically to the height defined recursively as follows: for : ; for : . Note that is an integer number equal to the height of shrinked lifted subtree .

###### Lemma 14

Step 3 is crossing-free

###### Proof

Every internal vertex in the path moves with its subtree along the vertical vector. In the beginning of this morphing step no intersections existed in projection to plane between different subtrees and the path edges. Nothing changes in projection to plane during this step, all movements happen strictly above plane. That means that there can be no crossings during this step of an algorithm. ∎

###### Lemma 15
1. After Step 3, all internal vertices of along with vertices of their subtrees are horizontally separated from the rest of the vertices of the tree by a horizontal plane.

2. The subtrees of internal vertices of are horizontally separated from each other.

###### Proof
1. Due to Lemma 10, -coordinates of all vertices that do not lie on the path are strictly below , also they are integer. By height definition in internal vertices of and vertices in their lifted subtrees have -coordinates at least .

So the plane is the horizontal plane of separation.

2. For every pair of internal vertices of , let us define the plane of separation as follows. From the definition of the height the horizontal plane separates lifted subtree of vertex from lifted subtree of vertex . ∎

Step 4: Rotate subtrees to horizontal plane. In this morphing step all lifted subtrees of internal vertices of path are rotated around a horizontal pole through to lie in a horizontal plane. The direction of rotation is chosen in such a way that does not cross with an edge throughout this morph. That is we rotate in the half-space that does not contain edge .

###### Lemma 16

With the proper direction of rotation, Step 4 is crossing-free.

###### Proof

If the crossing happens it must include one of the moving edges, i.e., edges of lifted subtrees.

As subtrees are horizontally separated from each other after Step 3 by Lemma 15, edges of different lifted subtrees can not cross. Also by Lemma 15, subtrees can not cross with non-processing vertices or edges between them as they also are horizontally separated in the beginning and in the end of this step.

If for some the edge lied in the vertical plane through there was no crossings in and after the beginning of movement will no longer lie in that plane and no crossing can happen. If lied strictly within one of the half-planes defined by , then by the choice of direction of rotation we rotate through the half-space that does not contain and thus can not cross with this edge either. ∎

Step 5: Correct the path: In morph , each vertex () of the path moves together with its subtree along the vector , where denotes -coordinate of vertex in drawing . At the end of this step, the and coordinates of each are same as their and coordinates in the canonical drawing with respect to .

###### Lemma 17

Step 5 is crossing-free

###### Proof

Step is crossing-free because all edges of the path and all subtrees of different vertices of the path (that lie in horizontal planes) are horizontally separated from each other. All moving edges are horizontally separated from already lifted subtrees with the plane by Lemma 15. ∎

Step 6: Go down: During the morphing step , every vertex of the path moves together with its subtree along the same vertical vector , where means -coordinate of vertex in drawing . At the end of this step, the coordinate of is the same as the coordinate of it in canonical drawing with respect to .

###### Lemma 18

Step 6 is crossing-free

###### Proof

All moving edges are horizontally separated from already lifted subtrees with the plane . During the morph the vertical order of internal vertices of the path does not change as is a portion of a root-to-leaf path. From that it follows that horizontal separation of remains for different . ∎

Step 7: Turn subtrees in horizontal planes: It consists of two morphing steps , and turns every lifted subtree of internal vertices of to lie in positive -direction with respect to vertex . For every subtree that lies in negative -direction in the drawing , we use the morphing step from Lemma 8 to obtain a planar point reflection of across the point in horizontal plane containing .

###### Lemma 19

Step 7 is crossing-free

###### Proof

The fact that point reflection of a tree across the point of its root can be performed as two steps and those steps are crossing-free follows from Lemma 8.

Vertices of different lifted subtrees are horizontally separated and separated from non-processing vertices and edges, which means no crossings can happen between them. ∎

Step 8: Stretch in -direction: This morphing step transforms lifted subtrees of internal vertices of in horizontal planes from shrinked to canonical size.

###### Lemma 20

Step 8 is crossing-free.

###### Proof

Stretching here is a shrinking morph played backwards and is a crossing-free morph for every by Lemma 6.

As all are horizontally separated from each other and from unprocessed part of the tree and morph is horizontal no crossings can happen between different or and unprocessed part of the graph. ∎

Step 9: Rotate to canonical positions: In morph all lifted subtrees of the internal vertices of the path rotate around horizontal axes to lie in vertical plane in positive direction such that the subtree is in canonical position with respect to vertex .

###### Lemma 21

Step 9 is crossing-free.

###### Proof

Let be the vertical plane parallel to X0Z and containing .

Vertices in subtrees lie from one side of in parallel planes at any moment of this morphing step. The half-planes that contain different are parallel because we can look at the rotation of the half-plane containing as at the rotation of the half-plane containing translated by the vector . Then at every moment angle which means that these half-planes are parallel to each other. So the vertices of do not cross.


text:
# Tips And Tricks And Shortcuts For Elementary Statistics

## Shortcuts For Questions of Elementary Statistics

Statistics is an important topic for the recruitment exams. Although the topic is lengthy and the calculations are time taking. Therefore, Tips And Tricks For Elementary Statistics are really important. These questions are totally data based and require attention and knowledge of formulas as the questions are generally formula based but with good amount of calculations.

The image below consists of Tips And Tricks and formulas For Elementary Statistics that are specifically used in solving Statistics problems.Before attempting the problems going through these formulas will make your task easier and it will help you in solving most of the questions based on elementary statistics.

### Tips and Shortcuts to Solve Elementary Statistics:

Type 1: Find the Mean,Median and Mode of the following set of data.

2,5,3,4,2,7,9,2,3

##### Solution:

As we know through the given formulas, Mean =$\frac {\text{sum of all the elements}}{\text{number of elements}}$

=$\frac{2+5+3+4+2+7+9+2+3}{9}$

=$\frac{37}{9}$

=4.111

In order to find Median we’ll arrange the numbers in ascending order first.

=2,2,2,3,3,4,5,7,9

Since,the middle term of the series (in which number of observations is odd) is the median.

Hence,3 is the median of the above series.

Now, Mode=The most frequent value in the set

In the above set we can see 2 is the most number of repeated value hence,the mode is 2.

Type 2: Consider the following set of data and find the variance and the standard deviation.

2,4,4,4,5,5,7,9

Solution:

Mean of these numbers=$\frac{2+4+4+4+5+5+7+9}{8}$

=$\frac{40}{8}$

=5

Variance =$\sigma ^{2} =\frac{\sum(x_{i}-\bar{x})^{2}}{N-1}$

=$(2-5)^{2}=-3^{2}=9$

=$(4-5)^{2}=-1^{2}=1$

=$(4-5)^{2}=-1^{2}=1$

=$(4-5)^{2}=-1^{2}=1$

=$(5-5)^{2}=0^{2}=0$

=$(5-5)^{2}=0^{2}=0$

=$(7-5)^{2}=2^{2}=4$

=$(9-5)^{2}=4^{2}=16$

= $Variance=\frac{9+1+1+1+0+0+4+16}{8}$

=$Variance=\frac{32}{8}$

=> variance=4 and,Standard deviation=$\sqrt{4} =2$

You can also solve more questions on elementary statistics to improve your command on this topic.

format: plain


text:
# Precalculus with Limits (2010)

## Educators

Problem 1

The ________ of a nonhorizontal line is the positive angle (less than measured counterclockwise from the axis to the line.

Check back soon!

Problem 2

If a nonvertical line has inclination $\theta$ and slope $m,$ then $m=$________.

Check back soon!

Problem 3

If two nonperpendicular lines have slopes $m_{1}$ and $m_{2},$ the angle between the two lines is $\tan \theta=$___________.

Check back soon!

Problem 4

The distance between the point $\left(x_{1}, y_{1}\right)$ and the line $A x+B y+C=0$ is given by $d=$________.

Check back soon!

Problem 5

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
GRAPH CANNOT COPY

Check back soon!

Problem 6

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
GRAPH CANNOT COPY

Check back soon!

Problem 7

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
GRAPH CANNOT COPY

Check back soon!

Problem 8

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
GRAPH CANNOT COPY

Check back soon!

Problem 9

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
$$\theta=\frac{\pi}{3}\text{radians}$$

Check back soon!

Problem 10

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
$$\theta=\frac{5 \pi}{6}\text{radians}$$

Check back soon!

Problem 11

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
$$\theta=\text{1.27 radians}$$

Check back soon!

Problem 12

In Exercises $5-12,$ find the slope of the line with inclination $\theta$
$$\theta=\text{2.88 radians}$$

Check back soon!

Problem 13

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=-1$$

Check back soon!

Problem 14

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=-2$$

Check back soon!

Problem 15

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=1$$

Check back soon!

Problem 16

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=2$$

Check back soon!

Problem 17

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=\frac{3}{4}$$

Check back soon!

Problem 18

In Exercises $13-18,$ find the inclination $\theta$ (in radians and degrees) of the line with a slope of $m .$
$$m=-\frac{5}{2}$$

Check back soon!

Problem 19

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(\sqrt{3}, 2),(0,1)$$

Check back soon!

Problem 20

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(1,2 \sqrt{3}),(0, \sqrt{3})$$

Check back soon!

Problem 21

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(-\sqrt{3},-1),(0,-2)$$

Check back soon!

Problem 22

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(3, \sqrt{3}),(6,-2 \sqrt{3})$$

Check back soon!

Problem 23

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(6,1),(10,8)$$

Check back soon!

Problem 24

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(12,8),(-4,-3)$$

Check back soon!

Problem 25

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(-2,20),(10,0)$$

Check back soon!

Problem 26

In Exercises $19-26,$ find the inclination $\theta$ (in radians and degrees) of the line passing through the points.
$$(0,100),(50,0)$$

Check back soon!

Problem 27

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$2 x+2 y-5=0$$

Check back soon!

Problem 28

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$x-\sqrt{3} y+1=0$$

Check back soon!

Problem 29

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$3 x-3 y+1=0$$

Check back soon!

Problem 30

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$\sqrt{3} x-y+2=0$$

Check back soon!

Problem 31

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$x+\sqrt{3} y+2=0$$

Check back soon!

Problem 32

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$-2 \sqrt{3} x-2 y=0$$

Check back soon!

Problem 33

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$6 x-2 y+8=0$$

Check back soon!

Problem 34

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$4 x+5 y-9=0$$

Check back soon!

Problem 35

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$5 x+3 y=0$$

Check back soon!

Problem 36

In Exercises $27-36,$ find the inclination $\theta$ (in radians and degrees) of the line.
$$2 x-6 y-12=0$$

Check back soon!

Problem 37

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
\begin{aligned} 3 x+y &=3 \\ x-y &=2 \end{aligned}

Check back soon!

Problem 38

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{x+3 y=2} \\ {x-2 y=-3}\end{array}$$

Check back soon!

Problem 39

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
\begin{aligned} x-y &=0 \\ 3 x-2 y &=-1 \end{aligned}

Check back soon!

Problem 40

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{2 x-y=2} \\ {4 x+3 y=24}\end{array}$$

Check back soon!

Problem 41

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
\begin{aligned} x-2 y &=7 \\ 6 x+2 y &=5 \end{aligned}

Check back soon!

Problem 42

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{5 x+2 y=16} \\ {3 x-5 y=-1}\end{array}$$

Check back soon!

Problem 43

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{x+2 y=8} \\ {x-2 y=2}\end{array}$$

Check back soon!

Problem 44

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{3 x-5 y=3} \\ {3 x+5 y=12}\end{array}$$

Check back soon!

Problem 45

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{0.05 x-0.03 y=0.21} \\ {0.07 x+0.02 y=0.16}\end{array}$$

Check back soon!

Problem 46

In Exercises $37-46,$ find the angle $\theta$ (in radians and degrees) between the lines.
$$\begin{array}{l}{0.02 x-0.05 y=-0.19} \\ {0.03 x+0.04 y=0.52}\end{array}$$

Check back soon!

Problem 47

ANGLE MEASUREMENT In Exercises $47-50$ , find the slope of each side of the triangle and use the slopes to find the measures of the interior angles.
GRAPH CANNOT COPY

Check back soon!

Problem 48

ANGLE MEASUREMENT In Exercises $47-50$ , find the slope of each side of the triangle and use the slopes to find the measures of the interior angles.
GRAPH CANNOT COPY

Check back soon!

Problem 49

ANGLE MEASUREMENT In Exercises $47-50$ , find the slope of each side of the triangle and use the slopes to find the measures of the interior angles.
GRAPH CANNOT COPY

Check back soon!

Problem 50

ANGLE MEASUREMENT In Exercises $47-50$ , find the slope of each side of the triangle and use the slopes to find the measures of the interior angles.
GRAPH CANNOT COPY

Check back soon!

Problem 51

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{cc}{\text {Point}} & {\text {Line}} \\ {(0,0)} & {4 x+3 y=0}\end{array}$$

Check back soon!

Problem 52

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{cc}{\text {Point}} & {\text {Line}} \\ {(0,0)} & {2 x-y=4}\end{array}$$

Check back soon!

Problem 53

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(2,3)} & {3 x+y=1}\end{array}$$

Check back soon!

Problem 54

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(-2,1)} & {x-y=2}\end{array}$$

Check back soon!

Problem 55

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(-6,2)} & {x+1=0}\end{array}$$

Check back soon!

Problem 56

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(2,1)} & {-2 x+y-2=0}\end{array}$$

Check back soon!

Problem 57

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(0,8)} & {6 x-y=0}\end{array}$$

Check back soon!

Problem 58

In Exercises $51-58$ , find the distance between the point and the line.
$$\begin{array}{ll}{\text { Point }} & {\text { Line }} \\ {(4,2)} & {x-y=20}\end{array}$$

Check back soon!

Problem 59

In Exercises $59-62,$ the points represent the vertices of a triangle. (a) Draw triangle $A B C$ in the coordinate plane, (b) find the altitude from vertex $B$ of the triangle to side $A C$ , and (c) find the area of the triangle.
$$A=(0,0), B=(1,4), C=(4,0)$$

Check back soon!

Problem 60

In Exercises $59-62,$ the points represent the vertices of a triangle. (a) Draw triangle $A B C$ in the coordinate plane, (b) find the altitude from vertex $B$ of the triangle to side $A C$ , and (c) find the area of the triangle.
$$A=(0,0), B=(4,5), C=(5,-2)$$

Check back soon!

Problem 61

In Exercises $59-62,$ the points represent the vertices of a triangle. (a) Draw triangle $A B C$ in the coordinate plane, (b) find the altitude from vertex $B$ of the triangle to side $A C$ , and (c) find the area of the triangle.
$$A=\left(-\frac{1}{2}, \frac{1}{2}\right), B=(2,3), C=\left(\frac{5}{2}, 0\right)$$

Check back soon!

Problem 62

In Exercises $59-62,$ the points represent the vertices of a triangle. (a) Draw triangle $A B C$ in the coordinate plane, (b) find the altitude from vertex $B$ of the triangle to side $A C$ , and (c) find the area of the triangle.
$$A=(-4,-5), B=(3,10), C=(6,12)$$

Check back soon!

Problem 63

In Exercises 63 and $64,$ find the distance between the parallel lines.
$$\begin{array}{l}{x+y=1} \\ {x+y=5}\end{array}$$

Check back soon!

Problem 64

In Exercises 63 and $64,$ find the distance between the parallel lines.
$$\begin{array}{l}{3 x-4 y=1} \\ {3 x-4 y=10}\end{array}$$

Check back soon!

Problem 65

ROAD GRADE A straight road rises with an inclination of 0.10 radian from the horizontal (see figure). Find the slope of the road and the change in elevation over a two-mile stretch of the road.

Check back soon!

Problem 66

Check back soon!

Problem 67

PITCH OF A ROOF A roof has a rise of 3 feet for every horizontal change of 5 feet (see figure). Find the inclination of the roof.

Check back soon!

Problem 68

CONVEYOR DESIGN A moving conveyor is built so that it rises 1 meter for each 3 meters of horizontal travel.
(a) Draw a diagram that gives a visual representation of the problem.
(b) Find the inclination of the conveyor.
(c) The conveyor runs between two floors in a factory. The distance between the floors is 5 meters. Find the length of the conveyor.

Check back soon!

Problem 69

TRUSS Find the angles and shown in the drawing of the roof truss.

Check back soon!

Problem 70

The Falls Incline Railway in Niagara Falls, Ontario, Canada is an inclined railway that was designed to carry people from the City of Niagara Falls to Queen Victoria Park. The railway is approximately 170 feet long with a 36% uphill grade (see figure).
(a) Find the inclination $\theta$ of the railway.
(b) Find the change in elevation from the base to the top of the railway.
(c) Using the origin of a rectangular coordinate system as the base of the inclined plane, find the equation of the line that models the railway track.
(d) Sketch a graph of the equation you found in part (c).

Check back soon!

Problem 71

TRUE OR FALSE? In Exercises 71 and $72,$ determine whether the statement is true or false. Justify your answer.
A line that has an inclination greater than $\pi / 2$ radians has a negative slope.

Check back soon!

Problem 72

TRUE OR FALSE? In Exercises 71 and $72,$ determine whether the statement is true or false. Justify your answer.
To find the angle between two lines whose angles of inclination $\theta_{1}$ and $\theta_{2}$ are known, substitute $\theta_{1}$ and $\theta_{2}$ for $m_{1}$ and $m_{2},$ respectively, in the formula for the angle between two lines.

Check back soon!

Problem 73

Consider a line with slope $m$ and $y$ -intercept $(0,4)$ .
(a) Write the distance $d$ between the origin and the line as a function of $m .$
(b) Graph the function in part (a).
(c) Find the slope that yields the maximum distance between the origin and the line.
(d) Find the asymptote of the graph in part (b) and interpret its meaning in the context of the problem.

Check back soon!

Problem 74

CAPSTONE Discuss why the inclination of a line can be an angle that is larger than $\pi / 2,$ but the angle between two lines cannot be larger than $\pi / 2 .$ Decide whether the following statement is true or false: "The inclination of a line is the angle between the line and the $x$ -axis." Explain.

Check back soon!

Problem 75

Consider a line with slope $m$ and $y$ -intercept $(0,4)$ .
(a) Write the distance $d$ between the point $(3,1)$ and the line as a function of $m .$
(b) Graph the function in part (a).
(c) Find the slope that yields the maximum distance between the point and the line.
(d) Is it possible for the distance to be 0 ? If so, what is the slope of the line that yields a distance of 0$?$
(e) Find the asymptote of the graph in part (b) and interpret its meaning in the context of the problem.

Check back soon!


text:
en:ph

# pH

In this term we means acidity and alkalinity of soulution. Definition of pH:

$pH=-\log a(H^+)$

In words it is negative decimal logarithm of activity of hydrogen cations. In ideal conditions we can assume activity to be the same as the concentration. And the equation become to more favourable form: pH = – log c(H+) So it is a concentration of hydrogen cations expressed on logarithmic scale, which means that, if we want to change pH about one degree we must scale up ion concentration ten times. It means, the higher the concentration of hydrogen cations is, the lower is pH(remember negative sign before logarithm). So for pH=7 it is c(H+) 10-7 and for pH 3 it is c(H+)10-3.

### Why measure pH

Acidity of nutrient solution is essential for plant. It affects possibility of roots soak up ions dissolved in solution. In inappropriate pH, the plant will suffer by deficit of some nutrients.

### Principle of measuring pH

Value of pH can be taken by potentiometric measuring (Measuring potentional of elektrochemical cell). We measure potencial between two electrodes, referent (with constatn potentional) and the measured one. You can find more about this topic here. Most often reference electrode used is silver-chloride electrode and for measuring electrode it is glass electrode. Usaly we have both electrodes in one compact unit (on picture) called , “pH electrode” or better pH probe.

The potencial of chloride electrode is given by:

$E=E^0-\frac{RT}{F}\ln a_{cl^-}$

Because concentration of chloride ions inside pH probe is same during the time, the electrode has constant potential in constant temperature .

Second one is glass electrode. This electorde is made from special very thin hydrogen sensitive glass. This electrode hydrolyze in water solution, that means that the hydrogen ions changes with sodioum ions in glass, as result of this this change is grow of potential on the surface of glass electrode. Potential of ion-selecting electrode is given by Nicolsky-Eisenman equation:

$E=K+\frac{RT}{z_xF}\ln ([x]+\sum_i(K_i[i]^\frac{z_x}{z_i}))$

If we assume that the electrode interact only with cations of hydrogen, we can simlify the equation:

$E=K+\frac{RT}{F}\ln a_{H^+}$

So the potential of all cell is given by:

$U=U_m-U_{ref}$

From combination of above equations we get potential of pH probe.

### Code and schematic

Potential of pH probe is in range of hundreds of millivolts and has impedance of MΩ. If we want to process this signal by arduino, it is necessary to amplify it. Good solution can be use of operational amplifier. E.g. like in schema on picture.

This schema is one of the simplest, but for our purposes it is more then sufficient. It is originaly taken from this pages of project wiki. In first step signal is amplified by operational amplifier in “closed loop” mode. It is possible to change amplify by potentiometer pot1 (gain):

$V_{out}=-\frac{R1}{R2}V_{in}$

In second step signal is looped and offset is set by potentiometer pot2. On output we get signal which can be meassure by arduino.

Circuit simulation in java applet by Paul Falstad.

Sorry, you need a Java-enabled browser to see the simulation.

Kód:

ph.ino
#define PHInput A1

#define SAMPLES 100 //number of samples readed by voltage() function

float PHa=1; //koeficients of aproximation line
float PHb=1; //for correct pH reading need calibration

float ph;

void setup()
{
}

void loop()
{
delay(500);
}

float PHf;
PHf=(voltage()/PHa)+PHb;
return PHf;
}

float voltage(){
long sensorValue=0;
for(int i=0;i<SAMPLES;i++){
delay(10);
}
sensorValue/=SAMPLES;
return sensorValue;
}

### Temperature dependency of pH

At first the temperature move with dissociation constant of molecules. So it affect pH. As you can see on table copied from calibration solution:

teplota[°C] pH
0 7,13
5 7,10
10 7,07
15 7,04
20 7,03
25 7,01
30 7,00
35 6,99
40 6,98
45 6,98
50 6,98

From table is obvious decreasing pH with increasing temperature. But I am not sure by generality of this rule.

From above equations one can be seen dependency of potential of electrodes on temperature.

Although temperature dependency of pH is inherent fact, for purposes of measuring acidity of nutrient solution, with temperature range 15-25°C, we can neglect the efect of temperature without making big mistake.


text:
#### Which of these statements do you think is correct?

In total, the 10,000 people generated enough electricity to:


text:
ï»¿ Comment upon the statement: A vector in XY plane can be split into only two components. from Physics Motion in A Plane Class 11 Manipur Board

### Book Store

Currently only available for.
CBSE Gujarat Board Haryana Board

### Previous Year Papers

Download the PDF Question Papers Free for off line practice and view the Solutions online.
Currently only available for.
Class 10 Class 12
Comment upon the statement:
A vector in XY plane can be split into only two components.

The given statement is wrong. A vector in XY plane can be split into more than two components.Â
115 Views

What are the basic characteristics that a quantity must possess so that it may be a vector quantity?

A quantity must possess the direction and must follow the vector axioms. Any quantity that follows the vector axioms are classified as vectors.Â

814 Views

Give three examples of vector quantities.

Force, impulse and momentum.
865 Views

Give three examples of scalar quantities.

Mass, temperature and energy
769 Views

What is a vector quantity?

A physical quantity that requires direction along with magnitude, for its complete specification is called a vector quantity.
835 Views

What is a scalar quantity?

A physical quantity that requires only magnitude for its complete specification is called a scalar quantity.
1212 Views


text:
mersenneforum.org Have Found Principle to generate infinitive PRIME NUMBERS
 Register FAQ Search Today's Posts Mark Forums Read

 2003-12-07, 17:19 #23 Evgeny Dolgov   22·1,667 Posts Hi! i'm continue using my new method that results i posted yerstaday and have obtained easily next prime numbers count of digits in prime numbers (using my algorithm) (i have tested and all success) (http://www.alpertron.com.ar/ECM.HTM i used this site to test next my prime numbers) # of digits 7 11 15 17 25 35 91 127 203 355 629 647 685 all of these numbers are primes if you want i can send you this numbers like examples So i have found easy method to generate infinitive prime numbers using my very simple rule. All prime numbers i have tested using my notebook in one evening . it is most hard - to input numbers in field of test form i 'll want to use some automatic cases or tool to input more huge numbers i think i'll post results at monday of prime numbers with in 10 000 digits using only my notebook and my simple rule. I know how looks PRIME NUMBER with 10 000 000 digits or more digits today at this moment! but i have only notebook i need more cases or computers to verify primility of generated prime numbers (i fully tested for primility last prime numbers with 685 digits about 4 hours ) but if the number is composite - it takes 2 seconds!!!! i can predict very very huge prime number - with any count of digits (1 000 000 000 and more) now i'm testing properties So any help or advices will be good if you can help with automatic cases that help to input very large numbers http://www.alpertron.com.ar/ECM.HTM - is the best tool that i'm using today Evgeny Dolgov This is previous 647 digit PRIME number you can test it to proof 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003 tnanks for reply
 2003-12-07, 17:22 #24 Evgeny Dolgov   33·59 Posts corrected post with sample 647 digit prime number you cant test it to proof 100000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000100000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 0000000000003 Evgeny Dolgov
2003-12-07, 18:12   #25
smh

"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts

Quote:
 (i fully tested for primility last prime numbers with 685 digits about 4 hours ) but if the number is composite - it takes 2 seconds!!!!

This is only for 685 digit numbers

How long do you think it will take to just test a 1 million digit?

And what about a primality test for a number of only a couple of thousand digits?

If you need faster tools, try primo for primality test and winpfgw for prp tests.

 2003-12-07, 18:30 #26 Raptor   Dec 2003 28 Posts @Evgeny Dolgov Even if your prime generator produces hundreds or thousands of primes in a lower digit range (where you can brute-force attack the numbers) this does not prove that the next number the generator ejects is also a prime. What is needed is a _mathematical_ proof, which can only come from the algorithm you use. A number with 10 Million digits is far beyond the range where you can proof its primalty with any known algorithm. Numbers in this range can only be attacked if they have a special form - like 2^p-1 . So again: A proof can only come from your algorithm. So my suggestion to you: just publish your algorithm in the math section of this forum and become famous - or learn.
 2003-12-07, 21:28 #27 flava     Feb 2003 2×59 Posts If you want to test numbers of the form 10^(2*n)+10^n+3, you can use pfgw.exe for probable prime testing. If you use the following input file: ABC2 10^(2*$a)+10^$a+3 a: from 1 to 2000 b: from 0 to 0 you get the following probable primes: 10^(2*1)+10^(1)+3 10^(2*2)+10^(2)+3 10^(2*3)+10^(3)+3 10^(2*5)+10^(5)+3 10^(2*7)+10^(7)+3 10^(2*8)+10^(8)+3 10^(2*12)+10^(12)+3 10^(2*17)+10^(17)+3 10^(2*45)+10^(45)+3 10^(2*63)+10^(63)+3 10^(2*101)+10^(101)+3 10^(2*177)+10^(177)+3 10^(2*314)+10^(314)+3 10^(2*323)+10^(323)+3 10^(2*342)+10^(342)+3 10^(2*367)+10^(367)+3 10^(2*792)+10^(792)+3 10^(2*894)+10^(894)+3 10^(2*1475)+10^(1475)+3 10^(2*1913)+10^(1913)+3 As you can see, the distribution is quite normal and they are more and more distanced. It is very probable that there are in fact very few primes of this forms that have more than a couple of thousend digits. The bad news is the numbers of this form are very hard to proove prime (when they get big).
 2003-12-08, 08:19 #28 Evgeny Dolgov   24×5×41 Posts Hi all! why i'm choosing this form of numbers 10^(n*2)+10^(n)+3 1. simple view 2. symmetric and asymmetric in one time well balanced 3. Predictable step (distribution) 4. Using this tool http://www.alpertron.com.ar/ECM.HTM i have found that if the test number is compiste (not prime) it takes little time to fail this number if the number is fail (not prime) it breaks very fast on parts but if this tool show is unknown and it takes more than 2-3 seconds on numbers with in 685 digits - i know 100% that number is prime!!! and tests show this. (i fully tested) now i'm begining to test numbers with 9555-10000 digits now fail test takes about 1-2 minute - in most hard but in simple - 5 seconds for fail - but if test takes nore than 4-5 (10) minutes with 100% guarantee i say that this number is PRIME (before all this my try was the numbers like 11119 1113 10003 ... - it's wrong numbers they are not productive like that 10....010....03 form or in exponenta 10^(2*n)+10^(n)+3 ) SO MAIN FEATURE - IF TEST NUMBERS in (10....010....03 form or in exponenta 10^(2*n)+10^(n)+3 ) ARE NOT PRIME THEY FAIL VERY FAST!!!!! so the effective search: use test algorithm like in tool http://www.alpertron.com.ar/ECM.HTM and comparing relatively time of success test and time of fail test example if test number - "685 digits" - and test is not failing after 10 seconds the number is PRIME. (100%) (main feature) Evgeny Dolgov You can test this 100000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000100000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 0000000000003 this numbers is prime - the tool (http://www.alpertron.com.ar/ECM.HTM) is showing "is unknown" - 2 hours and then - is PRIME!!! if you add or remove one digit "0" at the end of this number it fails very fast - not more than 10 seconds on pentium 4 computer. So repeat if test (10^(2*n)+10^(n)+3 form number) using algorithm (http://www.alpertron.com.ar/ECM.HTM) is not failing after relatively short time the number is PRIME. (100%) (main feature) Evgeny Dolgov
2003-12-08, 22:43   #29
ET_
Banned

"Luigi"
Aug 2002
Team Italia

12CE16 Posts

Quote:
 100000000000000000000000000000000000000000000000
The number is certified prime with Primo 2.2.0 beta in 15 minutes on a Athlon XP 2100+

But it's only 685 digits...

Luigi

 2003-12-08, 22:45 #30 BMgf     Dec 2003 24 Posts High level math Let just say that you found some 10 000 000+ digit number for witch you can't find any factor for more than 10 days. What's you next step? Something like GIMPS? Last fiddled with by BMgf on 2003-12-08 at 22:48
 2003-12-08, 22:58 #31 mark hemmeyer   24×7×89 Posts does it help if n is prime?
2003-12-09, 08:39   #32
BMgf

Dec 2003

208 Posts

Quote:
 Originally posted by mark hemmeyer does it help if n is prime?
If 685 digits number is prime then n is even. 10^684 + 10^342 + 3. N=342

2003-12-09, 16:13   #33
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×29×83 Posts

Quote:
 If 685 digits number is prime then n is even. 10^684 + 10^342 + 3. N=342
Hey, would you mind explaining this one?

Luigi

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil ONeil 27 2018-12-03 01:52 Philly314 Aliquot Sequences 3 2014-11-16 14:58 James Heinrich Miscellaneous Math 10 2012-03-08 07:20 Xyzzy Miscellaneous Math 41 2008-11-08 17:57 Evgeny Dolgov Math 1 2003-12-08 09:25

All times are UTC. The time now is 09:21.

Wed May 12 09:21:25 UTC 2021 up 34 days, 4:02, 0 users, load averages: 1.21, 1.47, 1.59


text:
### FAST: Disk Encryption and Beyond

Debrup Chakraborty, Sebati Ghosh, Cuauhtemoc Mancillas Lopez, and Palash Sarkar

##### Abstract

This work introduces \sym{FAST} which is a new family of tweakable enciphering schemes. Several instantiations of \sym{FAST} are described. These are targeted towards two goals, the specific task of disk encryption and a more general scheme suitable for a wide variety of practical applications. A major contribution of this work is to present detailed and careful software implementations of all of these instantiations. For disk encryption, the results from the implementations show that \sym{FAST} compares very favourably to the IEEE disk encryption standards XCB and EME2 as well as the more recent proposal AEZ. \sym{FAST} is built using a fixed input length pseudo-random function and an appropriate hash function. It uses a single-block key, is parallelisable and can be instantiated using only the encryption function of a block cipher. The hash function can be instantiated using either the Horner's rule based usual polynomial hashing or hashing based on the more efficient Bernstein-Rabin-Winograd polynomials. Security of \sym{FAST} has been rigorously analysed using the standard provable security approach and concrete security bounds have been derived. Based on our implementation results, we put forward \sym{FAST} as a serious candidate for standardisation and deployment.

Note: Added detailed comparison to AEZ instantiated with the full AES.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
disk encryptiontweakable enciphering schemespseudo-random functionHornerBRW
Contact author(s)
debrup @ isical ac in
sebati_r @ isical ac in
palash @ isical ac in
cuauhtemoc mancillas83 @ gmail com
sebati1987 @ gmail com
History
2019-12-13: last of 3 revisions
See all versions
Short URL
https://ia.cr/2017/849

CC BY

BibTeX

@misc{cryptoeprint:2017/849,
author = {Debrup Chakraborty and Sebati Ghosh and Cuauhtemoc Mancillas Lopez and Palash Sarkar},
title = {FAST: Disk Encryption and Beyond},
howpublished = {Cryptology ePrint Archive, Paper 2017/849},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/849}},
url = {https://eprint.iacr.org/2017/849}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
• ### Band renormalization of blue phosphorus on Au(111)(1803.08862)

March 31, 2018 cond-mat.mes-hall
Most recently, theoretical calculations predicted the stability of a novel two-dimensional phosphorus honeycomb lattice named blue phosphorus. Here, we report on the growth of blue phosphorus on Au(111) and unravel its structural details using diffraction, microscopy and theoretical calculations. Most importantly, by utilizing angle-resolved photoemission spectroscopy we identify its momentum-resolved electronic structure. We find that Au(111) breaks the sublattice symmetry of blue phosphorus leading to an orbital-dependent band renormalization upon the formation of a (4x4) superstructure. Notably, the semiconducting two-dimensional phosphorus realizes its valence band maximum at 0.9 eV binding energy, however, shifted in momentum space due to the substrate-induced band renormalization.
• ### Quantum oscillations and Dirac dispersion in the BaZnBi2 semimetal guaranteed by local Zn vacancy order(1801.07474)

March 27, 2018 cond-mat.str-el
We have synthesized single crystals of Dirac semimetal candidates AZnBi2 with A=Ba and Sr. In contrast to A=Sr, the Ba material displays a novel local Zn vacancy ordering, which makes the observation of quantum oscillations in out-of-plane magnetic fields possible. As a new Dirac semimetal candidate, BaZnBi2 exhibits small cyclotron electron mass, high quantum mobility, and non-trivial Berry phases. Three Dirac dispersions are observed by ARPES and identified by first- principles band-structure calculations. Compared to AMn(Bi/Sb)2 systems which host Mn magnetic moments, BaZnBi2 acts as non-magnetic analogue to investigate the intrinsic properties of Dirac fermions in this structure family.
• ### Negative longitudinal magnetoresistance from anomalous N=0 Landau level in topological materials(1704.02021)

Aug. 11, 2017 cond-mat.mes-hall
Negative longitudinal magnetoresistance (NLMR) is shown to occur in topological materials in the extreme quantum limit, when a magnetic field is applied parallel to the excitation current. We perform pulsed and DC field measurements on Pb1-xSnxSe epilayers where the topological state can be chemically tuned. The NLMR is observed in the topological state, but is suppressed and becomes positive when the system becomes trivial. In a topological material, the lowest N=0 conduction Landau level disperses down in energy as a function of increasing magnetic field, while the N=0 valence Landau level disperses upwards. This anomalous behavior is shown to be responsible for the observed NLMR. Our work provides an explanation of the outstanding question of NLMR in topological insulators and establishes this effect as a possible hallmark of bulk conduction in topological matter.
• ### Suppression of electron scattering resonances in graphene by quantum dots(1707.05577)

Transmission of low-energetic electrons through two-dimensional materials leads to unique scattering resonances. These resonances contribute to photoemission from occupied bands where they appear as strongly dispersive features of suppressed photoelectron intensity. Using angle-resolved photoemission we have systematically studied scattering resonances in epitaxial graphene grown on the chemically differing substrates Ir(111), Bi/Ir, Ni(111) as well as in graphene/Ir(111) nanopatterned with a superlattice of uniform Ir quantum dots. While the strength of the chemical interaction with the substrate has almost no effect on the dispersion of the scattering resonances, their energy can be controlled by the magnitude of charge transfer from/to graphene. At the same time, a superlattice of small quantum dots deposited on graphene eliminates the resonances completely. We ascribe this effect to a nanodot-induced buckling of graphene and its local rehybridization from sp$^{2}$ to sp$^{3}$ towards a three-dimensional structure. Our results suggest nanopatterning as a prospective tool for tuning optoelectronic properties of two-dimensional materials with graphene-like structure.
• ### Laser-induced persistent photovoltage on the surface of a ternary topological insulator at room temperature(1705.07078)

May 19, 2017 cond-mat.mes-hall
Using time- and angle-resolved photoemission, we investigate the ultrafast response of excited electrons in the ternary topological insulator (Bi$_{1 x}$Sb$_{x}$)$_2$Te$_3$ to fs-infrared pulses. We demonstrate that at the critical concentration $x$=0.55, where the system becomes bulk insulating, a surface voltage can be driven at room temperature through the topological surface state solely by optical means. We further show that such a photovoltage persists over a time scale that exceeds $\sim$6 $\mu$s, i.e, much longer than the characteristic relaxation times of bulk states. We attribute the origin of the photovoltage to a laser-induced band-bending effect which emerges near the surface region on ultrafast time scales. The photovoltage is also accompanied by a remarkable increase in the relaxation times of excited states as compared to undoped topological insulators. Our findings are relevant in the context of applications of topological surface states in future optical devices.
• ### Surface Fermi arc connectivity in the type-II Weyl semimetal candidate WTe$_{2}$(1608.05633)

Aug. 19, 2016 cond-mat.mtrl-sci
We perform ultrahigh resolution angle-resolved photoemission experiments at a temperature T=0.8 K on the type-II Weyl semimetal candidate WTe$_{2}$. We find a surface Fermi arc connecting the bulk electron and hole pockets on the (001) surface. Our results show that the surface Fermi arc connectivity to the bulk bands is strongly mediated by distinct surface resonances dispersing near the border of the surface-projected bulk band gap. By comparing the experimental results to first-principles calculations we argue that the coupling to these surface resonances, which are topologically trivial, is compatible with the classification of WTe$_{2}$ as a type-II Weyl semimetal hosting topological Fermi arcs. We further support our conclusion by a systematic characterization of the bulk and surface character of the different bands and discuss the similarity of our findings to the case of topological insulators.
• ### Nonmagnetic band gap at the Dirac point of the magnetic topological insulator (Bi$_{1-x}$Mn$_x)_2$Se$_3$(1603.02881)

March 9, 2016 cond-mat.mes-hall
Magnetic doping is expected to open a band gap at the Dirac point of topological insulators by breaking time-reversal symmetry and to enable novel topological phases. Epitaxial (Bi$_{1-x}$Mn$_{x}$)$_{2}$Se$_{3}$ is a prototypical magnetic topological insulator with a pronounced surface band gap of $\sim100$ meV. We show that this gap is neither due to ferromagnetic order in the bulk or at the surface nor to the local magnetic moment of the Mn, making the system unsuitable for realizing the novel phases. We further show that Mn doping does not affect the inverted bulk band gap and the system remains topologically nontrivial. We suggest that strong resonant scattering processes cause the gap at the Dirac point and support this by the observation of in-gap states using resonant photoemission. Our findings establish a novel mechanism for gap opening in topological surface states which challenges the currently known conditions for topological protection.
• ### Spin Mapping of Surface and Bulk Rashba States in Ferroelectric a-GeTe(111) Films(1512.01363)

Dec. 4, 2015 cond-mat.mtrl-sci
A comprehensive mapping of the spin polarization of the electronic bands in ferroelectric a-GeTe(111) films has been performed using a time-of-flight momentum microscope equipped with an imaging spin filter that enables a simultaneous measurement of more than 10.000 data points (voxels). A Rashba type splitting of both surface and bulk bands with opposite spin helicity of the inner and outer Rashba bands is found revealing a complex spin texture at the Fermi energy. The switchable inner electric field of GeTe implies new functionalities for spintronic devices.
• ### Rashba splitting of 100 meV in Au-intercalated graphene on SiC(1510.02291)

Intercalation of Au can produce giant Rashba-type spin-orbit splittings in graphene but this has not yet been achieved on a semiconductor substrate. For graphene/SiC(0001), Au intercalation yields two phases with different doping. Here, we report the preparation of an almost pure p-type graphene phase after Au intercalation. We observe a 100 meV Rashba-type spin-orbit splitting at 0.9 eV binding energy. We show that this giant splitting is due to hybridization and much more limited in energy and momentum space than for Au-intercalated graphene on Ni.
• ### Ultrafast spin polarization control of Dirac fermions in topological insulators(1505.02742)

May 11, 2015 cond-mat.mes-hall
Three-dimensional topological insulators (TIs) are characterized by spin-polarized Dirac-cone surface states that are protected from backscattering by time-reversal symmetry. Control of the spin polarization of topological surface states (TSSs) using femtosecond light pulses opens novel perspectives for the generation and manipulation of dissipationless surface spin currents on ultrafast timescales. Using time-, spin-, and angle-resolved spectroscopy, we directly monitor for the first time the ultrafast response of the spin polarization of photoexcited TSSs to circularly-polarized femtosecond pulses of infrared light. We achieve all-optical switching of the transient out-of-plane spin polarization, which relaxes in about 1.2 ps. Our observations establish the feasibility of ultrafast optical control of spin-polarized Dirac fermions in TIs and pave the way for novel optospintronic applications at ultimate speeds.
• ### Anisotropic effect of warping on the lifetime broadening of topological surface states in angle-resolved photoemission from Bi$_2$Te$_3$(1504.01691)

April 7, 2015 cond-mat.mes-hall
We analyze the strong hexagonal warping of the Dirac cone of Bi$_2$Te$_3$ by angle-resolved photoemission. Along $\overline{\Gamma}$$\overline{\rm M}, the dispersion deviates from a linear behavior meaning that the Dirac cone is warped outwards and not inwards. We show that this introduces an anisotropy in the lifetime broadening of the topological surface state which is larger along \overline{\Gamma}$$\overline{\rm K}$. The result is not consistent with nesting. Based on the theoretically predicted behavior of the ground-state spin texture of a strongly warped Dirac cone, we propose spin-dependent scattering processes as explanation for the anisotropic scattering rates. These results could help paving the way for optimizing future spintronic devices using topological insulators and controlling surface-scattering processes via external gate voltages.
• ### Samarium hexaboride: A trivial surface conductor(1502.01542)

Feb. 5, 2015 cond-mat.str-el
Recent theoretical and experimental studies suggest that SmB$_6$ is the first topological Kondo insulator: A material in which the interaction between localized and itinerant electrons renders the bulk insulating at low temperature, while topological surface states leave the surface metallic. While this would elegantly explain the material's puzzling conductivity, we find the experimentally observed candidates for both predicted topological surface states to be of trivial character instead: The surface state at $\bar{\Gamma}$ is very heavy and shallow with a mere $\sim 2$ meV binding energy. It exhibits large Rashba splitting which excludes a topological nature. We further demonstrate that the other metallic surface state, located at $\bar{X}$, is not an independent in-gap state as supposed previously, but part of a massive band with much higher binding energy (1.7 eV). We show that it remains metallic down to 1 K due to reduced hybridization with the energy-shifted surface 4$f$ level.
• ### Photoemission of Bi$_2$Se$_3$ with Circularly Polarized Light: Probe of Spin Polarization or Means for Spin Manipulation?(1310.1160)

Oct. 4, 2013 cond-mat.mes-hall
Topological insulators are characterized by Dirac cone surface states with electron spins aligned in the surface plane and perpendicular to their momenta. Recent theoretical and experimental work implied that this specific spin texture should enable control of photoelectron spins by circularly polarized light. However, these reports questioned the so far accepted interpretation of spin-resolved photoelectron spectroscopy. We solve this puzzle and show that vacuum ultraviolet photons (50-70 eV) with linear or circular polarization probe indeed the initial state spin texture of Bi$_2$Se$_3$ while circularly polarized 6 eV low energy photons flip the electron spins out of plane and reverse their spin polarization. Our photoemission calculations, considering the interplay between the varying probing depth, dipole selection rules and spin-dependent scattering effects involving initial and final states explain these findings, and reveal proper conditions for light-induced spin manipulation. This paves the way for future applications of topological insulators in opto-spintronic devices.
• ### Tunneling Tuned Spin Modulations in Ultrathin Topological Insulator Films(1307.5485)

July 21, 2013 cond-mat.mes-hall
Quantitative understanding of the relationship between quantum tunneling and Fermi surface spin polarization is key to device design using topological insulator surface states. By using spin-resolved photoemission spectroscopy with p-polarized light in topological insulator Bi2Se3 thin films across the metal-to-insulator transition, we observe that for a given film thickness, the spin polarization is large for momenta far from the center of the surface Brillouin zone. In addition, the polarization decreases significantly with enhanced tunneling realized systematically in thin insulating films, whereas magnitude of the polarization saturates to the bulk limit faster at larger wavevectors in thicker metallic films. Our theoretical model calculations capture this delicate relationship between quantum tunneling and Fermi surface spin polarization. Our results suggest that the polarization current can be tuned to zero in thin insulating films forming the basis for a future spin-switch nano-device.
• ### Reversal of the circular dichroism in the angle-resolved photoemission from Bi2Te3(1303.6161)

The helical Dirac fermions at the surface of topological insulators show a strong circular dichroism which has been explained as being due to either the initial-state spin angular momentum, the initial-state orbital angular momentum, or the handedness of the experimental setup. All of these interpretations conflict with our data from Bi2Te3 which depend on the photon energy and show several sign changes. Our one-step photoemission calculations coupled to ab initio theory confirm the sign change and assign the dichroism to a final-state effect. The spin polarization of the photoelectrons, instead, remains a reliable probe for the spin in the initial state.
• ### Massless Dirac fermions in epitaxial graphene on Fe(110)(1212.6866)

Dec. 31, 2012 cond-mat.mtrl-sci
Graphene grown on Fe(110)by chemical vapor deposition using propylene is investigated by means of angle-resolved photoemission. The presence of massless Dirac fermions is clearly evidenced by the observation of a fully intact Dirac cone. Unlike Ni(111) and Co(0001), the Fe(110) imposes a strongly anisotropic quasi-one-dimensional structure on the graphene. Certain signatures of a superlattice effect appear in the dispersion of its \sigma-bands but the Dirac cone does not reveal any detectable superlattice or quantum-size effects although the graphene corrugation is twice as large as in the established two-dimensional graphene superlattice on Ir(111).
• ### Magnetically induced spin reorientation on the surface of a topological insulator (a surface magnetic topological insulator MBE film)(1206.2090)

Dec. 13, 2012 cond-mat.mes-hall
The surface of topological insulators is proposed as a promising platform for spintronics and quantum information applications. In particular, when time- reversal symmetry is broken, topological surface states are expected to exhibit a wide range of exotic spin phenomena for potential implementation in electronics. Such devices need to be fabricated using nanoscale artificial thin films. It is of critical importance to study the spin behavior of artificial topological MBE thin films associated with magnetic dopants, and with regards to quantum size effects related to surface-to-surface tunneling as well as experimentally isolate time-reversal breaking from non-intrinsic surface electronic gaps. Here we present observation of the first (and thorough) study of magnetically induced spin reorientation phenomena on the surface of a topological insulator. Our results reveal dramatic rearrangements of the spin configuration upon magnetic doping contrasted with chemically similar nonmagnetic doping as well as with quantum tunneling phenomena in ultra-thin high quality MBE films. While we observe that the spin rearrangement induced by quantum tunneling occurs in a time-reversal invariant fashion, we present critical and systematic observation of an out-of-plane spin texture evolution correlated with magnetic interactions, which breaks time-reversal symmetry, demonstrating microscopic TRB at a Kramers' point on the surface.
• ### Probing two topological surface bands of Sb2Te3 by spin-polarized photoemission spectroscopy(1201.4323)

Oct. 30, 2012 cond-mat.mes-hall
Using high resolution spin- and angle-resolved photoemission spectroscopy, we map the electronic structure and spin texture of the surface states of the topological insulator Sb2Te3. In combination with density functional calculations (DFT), we directly show that Sb2Te3 exhibits a partially occupied, single spin-Dirac cone around the Fermi energy, which is topologically protected. DFT obtains a spin polarization of the occupied Dirac cone states of 80-90%, which is in reasonable agreement with the experimental data after careful background subtraction. Furthermore, we observe a strongly spin-orbit split surface band at lower energy. This state is found at 0.8eV below the Fermi level at the gamma-point, disperses upwards, and disappears at about 0.4eV below the Fermi level into two different bulk bands. Along the gamma-K direction, the band is located within a spin-orbit gap. According to an argument given by Pendry and Gurman in 1975, such a gap must contain a surface state, if it is located away from the high symmetry points of the Brillouin zone. Thus, the novel spin-split state is protected by symmetry, too.
• ### Graphene for spintronics: giant Rashba splitting due to hybridization with Au(1208.4265)

Aug. 21, 2012 cond-mat.mtrl-sci
Graphene in spintronics has so far primarily meant spin current leads of high performance because the intrinsic spin-orbit coupling of its pi-electrons is very weak. If a large spin-orbit coupling could be created by a proximity effect, the material could also form active elements of a spintronic device such as the Das-Datta spin field-effect transistor, however, metal interfaces often compromise the band dispersion of massless Dirac fermions. Our measurements show that Au intercalation at the graphene-Ni interface creates a giant spin-orbit splitting (~100 meV) in the graphene Dirac cone up to the Fermi energy. Photoelectron spectroscopy reveals hybridization with Au-5d states as the source for the giant spin-orbit splitting. An ab initio model of the system shows a Rashba-split dispersion with the analytically predicted gapless band topology around the Dirac point of graphene and indicates that a sharp graphene-Au interface at equilibrium distance will account for only ~10 meV spin-orbit splitting. The ab initio calculations suggest an enhancement due to Au atoms that get closer to the graphene and do not violate the sublattice symmetry.
• ### High spin polarization and circular dichroism of topological surface states on Bi2Te3(1108.1053)

May 25, 2012 cond-mat.mes-hall
Topological insulators have been successfully identified by spin-resolved photoemission but the spin polarization remained low (~20%). We show for Bi2Te3 that the in-gap surface state is much closer to full spin polarization with measured values reaching 80% at the Fermi level. When hybridizing with the bulk it remains highly spin polarized which may explain recent unusual quantum interference results on Bi2Se3. The topological surface state shows a large circular dichroism in the photoelectron angle distribution with an asymmetry of ~20% the sign of which corresponds to that of the measured spin.
• ### Topological surface state under graphene for two-dimensional spintronics in air(1104.3308)

Spin currents which allow for a dissipationless transport of information can be generated by electric fields in semiconductor heterostructures in the presence of a Rashba-type spin-orbit coupling. The largest Rashba effects occur for electronic surface states of metals but these cannot exist but under ultrahigh vacuum conditions. Here, we reveal a giant Rashba effect ({\alpha}_R ~ 1.5E-10 eVm) on a surface state of Ir(111). We demonstrate that its spin splitting and spin polarization remain unaffected when Ir is covered with graphene. The graphene protection is, in turn, sufficient for the spin-split surface state to survive in ambient atmosphere. We discuss this result along with evidences for a topological protection of the surface state.
• ### Quantitative determination of spin-dependent quasiparticle lifetimes and electronic correlations in hcp cobalt(1008.3414)

We report on a quantitative investigation of the spin-dependent quasiparticle lifetimes and electron correlation effects in ferromagnetic hcp Co(0001) by means of spin and angle-resolved photoemission spectroscopy. The experimental spectra are compared in detail to state-of-the-art many-body calculations within the dynamical mean field theory and the three-body scattering approximation, including a full calculation of the one-step photoemission process. From this comparison we conclude that although strong local many-body Coulomb interactions are of major importance for the qualitative description of correlation effects in Co, more sophisticated many-body calculations are needed in order to improve the quantitative agreement between theory and experiment, in particular concerning the linewidths. The quality of the overall agreement obtained for Co indicates that the effect of non-local correlations becomes weaker with increasing atomic number.
• ### About the strength of correlation effects in the electronic structure of iron(0910.4360)

The strength of electronic correlation effects in the spin-dependent electronic structure of ferromagnetic bcc Fe(110) has been investigated by means of spin and angle-resolved photoemission spectroscopy. The experimental results are compared to theoretical calculations within the three-body scattering approximation and within the dynamical mean-field theory, together with one-step model calculations of the photoemission process. This comparison indicates that the present state of the art many-body calculations, although improving the description of correlation effects in Fe, give too small mass renormalizations and scattering rates thus demanding more refined many-body theories including non-local fluctuations.
• ### Correlated Electrons Step-by-Step: Itinerant-to-Localized Transition of Fe Impurities in Free-Electron Metal Hosts(0907.2911)

High-resolution photoemission spectroscopy and realistic ab-initio calculations have been employed to analyze the onset and progression of d-sp hybridization in Fe impurities deposited on alkali metal films. The interplay between delocalization, mediated by the free-electron environment, and Coulomb interaction among d-electrons gives rise to complex electronic configurations. The multiplet structure of a single Fe atom evolves and gradually dissolves into a quasiparticle peak near the Fermi level with increasing the host electron density. The effective multi-orbital impurity problem within the exact diagonalization scheme describes the whole range of hybridizations.
• ### Observation of Hubbard Bands in $\gamma$-Manganese(cond-mat/0112430)

Dec. 22, 2001 cond-mat.str-el
We present angle-resolved photoemission spectra of the $\gamma$-phase of manganese as well as a theoretical analysis using a recently developed approach that combines density functional and dynamical mean field methods (LDA+DMFT). The comparison of experimental data and theoretical predictions allows us to identify effects of the Coulomb correlations, namely the presence of broad and undispersive Hubbard bands in this system.